信息检索中的文档表示综述.doc

1、信息检索中的文档表示综述摘 要：本文对信息检索中文本分类、文本聚类等技术所涉及到的文档表示问题进行了详细的阐述。文中给出了各种特征选择、特征抽取方法的基本原理和计算公式，并对各种方法的优缺点做了比较。 关键词：文档表示；特征选择；特征抽取 仔信息检索领域，文本分类和文本聚类是非常关键的两项技术。在这两项技术中，文档表示又是一个至关重要的问题。在过去的发展中，人们提出了许多方法和模型来处理它。 1 文档表示 文档表示有向量空间模型、n-gram 文档表示和概念文档表示等多种方法。其中最常用的文档表示方法是 VSM 法。该方法把文档集合中的每篇文档都表示为形如的 N 维向量，其中代表第 i 篇文档

2、，向量元素代表特征在第 i 篇文档中的权重。该权重可通过多种方法给定，如0-1 法、tf-idf 法等。 VSM 表示方法导致的一个问题是特征空间维度过高以及数据稀疏，这使得各种文本分类和聚类算法的性能大大降低。为了解决这个问题，人们提出了许多解决方法，主要分为特征选择和特征抽取两类。前者是从原特征集合中选取一部分特征，即得到的结果是一个原特征集合的子集。后者则是通过某种函数映射形成新集合，元素形式可能与原特征完全不同，比如原集合元素是词，而新集合元素则是合并词得到的短语。一个有效的特征集合必须具有： （1）完备性：特征集确实能表达目标内容； （2）区分性：特征集合能够将目标与其它文档区分开。

3、 2 特征选择 特征选择又可分为两类方法：包装法和过滤器法。 2.1 包装法 包装法将学习算法作为其评估函数的一部分，在特征空间里执行搜索，可分为顺序搜索、指数和随机算法两种。 2.1.1 顺序搜索 根据不同的启发式，顺序搜索又可分为前向选取、后向去除、双向搜索、最好优先等。 （1） 前向选取 该方法从一个空集合开始，每次增加一个特征，直到遍历所有特征。每个特征是否被添加依赖于它能否改善学习器的性能。 （2）后向去除 与前向选取正好相反，该方法从完整的特征集出发，每次去掉一个特征，并观察学习其性能的变化。如果去掉该特征导致学习器性能增强，则去掉它；反之，保留。 （3）双向搜索 该方法是前向选取

4、与后向去除两种方法的结合。由于运行过程中不会增加已经去掉的特征也不会去掉已添加的特征，所以可以保证搜索算法收敛。 （4）最好优先 最好优先从已经生成但尚未扩展的结点中选择最有希望的结点。进行扩展后，再从新生成的结点中选择最优，直到得到最优解。搜索目标是找到使预测准确性最大的特征子集。 2.1.2 指数和随机算法 由于在各种顺序搜索算法中，启发式决定算法的性能，所以容易陷入局部最小值。为了克服这个缺点，指数和随机算法在搜索过程中增加了随机性。主要的方法有光束搜索、模拟退火和遗传算法三种。 （1）光束搜索 光束搜索与宽度优先搜索类似，区别是它在每层只对搜索队列中最好的前 n 个结点进行扩展。当队列

5、无限长时，光束搜索退化为穷举搜索；而当队列长度为 1 时，该方法则退化成前向选取。 （2）模拟退火 模拟退火是一种随机最优搜索算法。该方法中，系统状态受一个较小随机变化的影响。如果新状态比旧状态好，就接受它；如果新状态比旧状态差，则以一定的概率来判断应该接受还是拒绝。 （3）遗传算法 遗传算法是借鉴达尔文生物进化论的基本原理形成的算法。算法中充分体现了“优胜劣汰“的思想。它从一个随机产生的初始种群开始，依次通过选择、复制、交叉、变异等步骤完成一次迭代过程。算法与实际问题的唯一接口是适应度函数的确定。 2.2 过滤器法 过滤器法与包装法的不同在于它对特征的评价独立于分类器，它经常使用一些统计和信

6、息领域的度量对特征进行加权，主要的方法有： 2.2.1 信息理论方法 （1）信息增益 信息增益用来衡量一个词在文档中出现或不出现对文档类别估计所带来的信息位数的影响。令，表示可能的分类，则词 t 的 IG 函数为： （1） 这里 P（）为第 i 类的出现频率，P（t）为词 t 的出现频率，P（|t）为词 t 出现时属于类的条件概率。 （2）期望交叉熵 期望交叉熵与信息增益惟一的不同在于它没有考虑单词不发生的情况，计算公式如下： （2） 在实验中，用期望交叉熵进行特征选择效果优于信息增益。 （3）互信息 互信息与期望交叉熵的差别在于没有考虑词发生的频度 ，实质上这也是它一个很大的缺点。 （3）

7、这里 P（）为第 i 类的出现频率，P（|t）为第 i 类中出现词的条件概率，P（t）为词 t 的出现频率。 这种方法假设各个类别中的文本量大致相等，忽略了类别中文本量的多少对词在每个类别中出现比率的影响，使得互信息评估函数经常倾向于选择稀有词。为此，可以引入类别文本量占整个文本集的比率对上面的公式进行修正。用 N（i）表示类别中出现的总词数，于是类别的文本量在整个文本集中所占的比率 R（i）可以如下计算： （4） 把 R（i）作为修正因子，原来的互信息公式可以改为： （5） MI 方法类似于 IG，其缺点是受边缘概率的影响较大。 2.2.2 统计方法 （1）（又叫 chi-square） 用

8、来衡量词与类别的相关性。它不但考虑了正例的作用，也考虑了反例的作用，但对正例反例的数量关系没有显式给出，而是仅通过平方隐式地给出。 （6） （2）CC（Correlation Coefficency） CC 法是的变体，它不考虑负特征的作用，其平方等于，所以有时也把它叫做“单边“。CC 的正值越大，成员关系越强；负值越小，非成员关系越强。 （7） （3）GSS coefficient GSS coefficient 也是的变体，其正值负值意义与 CC 相似。 （8） 特别需要说明的一点是：与相比，CC、GSS 都是非对称测度，只考虑正例。 （4）几率比（Odd Ratio，OR） 几率比是一个

9、用于二元分类的优秀测度，能够成功地找出与目标类最相关的特征集合。它的基本假设是特征在相关文档中的分布与在不相关文档中的分布不同。 （9） OR 值大于 1 对应成员特征，小于 1 对应非成员特征，只考虑相关文本。另外，可使用 ELE 平滑技术对上面的公式进行处理。 3 特征抽取 使用特征抽取降低维度分为两步进行：第一步从原始特征集中提取新特征；第二步将原文档转化成新的表示。主要有词聚簇和潜在语义索引两种方法。 3.1 词聚簇 它使用最相关的词簇、质心或代表点来表示文档。Lewis 是第一个探索该方法的人。他使用“互惠最近邻聚簇” ，根据某个度量将两个最相似的词语聚成簇。但测试结果表明该方法的性

10、能不如使用单个词好。Li 和Jain 考虑词的语义关系而不是词语互出现或互缺席，其性能比单个词的稍好。因为都不受文档类标签影响，所以以上两种方法都属于不受控方法。Baker 和 MacCallum 使用分布式聚簇进行处理，该方法属于受控方法。3.2 LSI LSI 来自于信息检索领域，最初用于解决文档表示中同义、近义和多义问题。它能反映文档中词相互之间的语义关系。缺点是新生成的维度直观上不可解释。而且，如果某些词的区分能力本来就很强，那么转化后可能反而会失去这种区分力。 4 结束语 在文本信息挖掘中，文档表示和维度降低是首先要解决的问题。各种降低文档表示维度的方法都有各自不同的优缺点。在具体应

11、用中，应结合要研究问题的特点和实际情况的差异进行选择，有时还应该通过实验验证的方法予以取舍。本文只对各种方法的原理和计算公式做了一般意义上的解释和初步的比较。将来进一步的工作是探讨各种方法的应用效果。另外，有必要对中文文本信息挖掘中的文档表示和维度降低问题进行专门研究，以给出适合于中文特点的公式和方法。 参考文献： 1 Baker， L. D. and McCallum， A. K. 1998. Distributional clustering of words for text classification. In Proceedings of SIGIR-98， 21st ACM Int

12、ernational Conference on Research and Development in Information Retrieval （Melbourne， AU， 1998） ， pp. 96-103. 2 Baranidharan Raman，Thomas R.Ioerger.Instance Based Filter for Feature Selection.Journal of Machine Learning Research 1（2002）1-23. 3 Web 文本挖掘中的特征选择研究. 4 王伟强，高文.Internet 上的文本数据挖掘J.计算机科学，2000，27（4）：32-37. 5 陆玉昌，鲁明羽，李凡，周立柱.向量空间法中单词权重函数的分析和构造.计算机研究与发展 39（10）.