Web文档预处理中的文本特征提取方法设计与实现

摘要：本文通过对词频矩阵中的每个项的出现频率(词频)进行统计，按照词频的大小选出预定数目的特征项构成为特征子集（即关键字），设计出词频空间特征提取方法。首先利用最大匹配算法对文件进行词语切分，然后导入词频矩阵，统计词频矩阵中各项出现的频率，最后提取出文本特征。 关键字：词频矩阵 特征 词频空间 最大匹配算法 词语切分 词频空间特征提取方法的研究 3.1词频空间特征提取方法概述 这类型算法通过构造评估函数,对特征集合中的每个特征进行评估,并对每个特征打分，这样每个词语都获得一个评估值,又称为权值。然后将所有特征按权值大小排序,提取预定数目的最优特征作为提取结果的特征子集。显然,对于这类型算法,决定文本特征提取效果的主要因素是评估函数的质量。 1、TF-IDF： 单词权重最为有效的实现方法就是TF*IDF, 它是由Salton在1988 年提出的。其中TF 称为词频, 用于计算该词描述文档内容的能力; IDF 称为反文档频率, 用于计算该词区分文档的能力。TF*IDF 的指导思想建立在这样一条基本假设之上: 在一个文本中出现很多次的单词, 在另一个同类文本中出现次数也会很多, 反之亦然。所以如果特征空间坐标系取TF 词频作为测度, 就可以体现同类文本的特点。另外还要考虑单词区别不同类别的能力, TF*IDF 法认为一个单词出现的文本频率越小, 它区别不同类别的能力就越大, 所以引入了逆文本频度IDF 的概念, 以TF 和IDF 的乘积作为特征空间坐标系的取值测度。 TFIDF 法是以特征词在文档d中出现的次数与包含该特征词的文档数之比作为该词的权重，即其中，Wi表示第i个特征词的权重，TFi(t，d)表示词t在文档d中的出现频率，N表示总的文档数，DF(t)表示包含t的文档数。用TFIDF算法来计算特征词的权重值是表示当一个词在这篇文档中出现的频率越高，同时在其他文档中出现的次数越少，则表明该词对于表示这篇文档的区分能力越强，所以其权重值就应该越大。将所有词的权值排序, 根据需要可以有两种选择方式:( 1) 选择权值最大的某一固定数n 个关键词;( 2) 选择权值大于某一阈值的关键词。一些实验表示,人工选择关键词, 4∽7 个比较合适, 机选关键词10∽15 通常具有最好的覆盖度和专指度。 TFIDF算法是建立在这样一个假设之上的：对区别文档最有意义的词语应该是那些在文档中出现频率高，而在整个文档集合的其他文档中出现频率少的词语，所以如果特征空间坐标系取TF词频作为测度，就可以体现同类文本的特点。另外考虑到单词区别不同类别的能力，TFIDF法认为一个单词出现的文本频数越小，它区别不同类别文本的能力就越大。因此引入了逆文本频度IDF的概念，以TF和IDF的乘积作为特征空间坐标系的取值测度，并用它完成对权值TF的调整，调整权值的目的在于突出重要单词，抑制次要单词。但是在本质上IDF是一种试图抑制噪音的加权 ，并且单纯地认为文本频数小的单词就越重要，文本频数大的单词就越无用，显然这并不是完全正确的。IDF的简单结构并不能有效地反映单词的重要程度和特征词的分布情况，使其无法很好地完成对权值调整的功能，所以TFIDF法的精度并不是很高。 此外，在TFIDF算法中并没有体现出单词的位置信息，对于Web文档而言，权重的计算方法应该体现出HTML的结构特征。特征词在不同的标记符中对文章内容的反映程度不同，其权重的计算方法也应不同。因此应该对于处于网页不同位置的特征词分别赋予不同的系数，然后乘以特征词的词频，以提高文本表示的效果。 2、词频方法(Word Frequency)： 词频是一个词在文档中出现的次数。通过词频进行特征选择就是将词频小于某一闭值的词删除，从而降低特征空间的维数。这个方法是基于这样一个假设，即出现频率小的词对过滤的影响也较小。但是在信息检索的研究中认为，有时频率小的词含有更多的信息。因此，在特征选择的过程中不宜简单地根据词频大幅度删词。 3、文档频次方法(Document Frequency)： 文档频数(Document Frequency, DF)是最为简单的一种特征选择算法,它指的是在整个数据集中有多少个文本包含这个单词。在训练文本集中对每个特征计一算它的文档频次，并且根据预先设定的阑值去除那些文档频次特别低和特别高的特征。文档频次通过在训练文档数量中计算线性近似复杂度来衡量巨大的文档集，计算复杂度较低，能够适用于任何语料，因此是特征降维的常用方法。 在训练文本集中对每个特征计算它的文档频数,若该项的DF 值小于某个阈值则将其删除,若其DF 值大于某个阈值也将其去掉。因为他们分别代表了“没有代表性”和“没有区分度”2 种极端的情况。DF 特征选取使稀有词要么不含有用信息,要么太少而不足以对分类产生影响,要么是噪音,所以可以删去。DF 的优点在于计算量很小,而在实际运用中却有很好的效果。缺点是稀有词可能在某一类文本中并不稀有,也可能包含着重要的判断信息,简单舍弃,可能影响分类器的精度。 文档频数最大的优势就是速度快,它的时间复杂度和文本数量成线性关系,所以非常适合于超大规模文本数据集的特征选择。不仅如此,文档频数还非常地高效,在有监督的特征选择应用中当删除90%单词的时候其性能与信息增益和x2 统计的性能还不相上下。DF 是最简单的特征项选取方法, 而且该方法的计算复杂度低, 能够胜任大规模的分类任务。 但如果某一稀有词条主要出现在某类训练集中,却能很好地反映类别的特征,而因低于某个设定的阈值而滤除掉,这样就会对分类精度有一定的影响。 4、互信息(Mutual Information)： 互信息衡量的是某个词和类别之间的统计独立关系,某个词t和某个类别Ci传统的互信息定义如下: 互信息是计算语言学模型分析的常用方法，它度量两个对象之间的相互性。在过滤问题中用于度量特征对于主题的区分度。互信息的定义与交叉嫡近似。互信息本来是信息论中的一个概念,用于表示信息之间的关系, 是两个随机变量统计相关性的测度，使用互信息理论进行特征抽取是基于如下假设:在某个特定类别出现频率高,但在其他类别出现频率比较低的词条与该类的互信息比较大。通常用互信息作为特征词和类别之问的测度，如果特征词属于该类的话，它们的互信息量最大。由于该方法不需要对特征词和类别之问关系的性质作任何假设，因此非常适合于文本分类的特征和类别的配准工作。 特征项和类别的互信息体现了特征项与类别的相关程度, 是一种广泛用于建立词关联统计模型的标准。互信息与期望交叉熵的不同在于没有考虑特征出现的频率, 这样导致互信息评估函数不选择高频的有用词而有可能选择稀有词作为文本的最佳特征。因为对于每一主题来讲，特征t的互信息越大，说明它与该主题的共现概率越大，因此，以互信息作为提取特征的评价时应选互信息最大的若干个特征。 互信息计算的时间复杂度类似于信息增益, 互信息的平均值就是信息增益。互信息的不足之处在于得分非常受词条边缘概率的影响。 实验数据显示,互信息分类效果最差,其次是文档频率、CC 统计,CHI 统计分类效果最好。 对互信息而言,提高分类精度的方法有:1) 可以增加特征空间的维数,以提取足够多的特征信息,这样就会带来了时间和空间上的额外开销;2) 根据互信息函数的定义,认为这些低频词携带着较为强烈的类别信息,从而对它们有不同程度的倚重. 当训练语料库没有达到一定规模的时候,特征空间中必然会存在大量的出现文档频率很低(比如低于3 次) 的词条,他们较低的文档频率导致了他们必然只属于少数类别. 但是从抽取出来的特征词观察发现,大多数为生僻词,很少一部分确实带有较强的类别信息,多数词携带少量的类别信息,甚至是噪音词. 5、期望交叉熵(Expected Cross Entropy)： 交叉嫡 ，也称KL距离。它反映了文本主题类的概率分布和在出现了某特定词汇的条件下文本主题类的概率分布之间的距离，词汇w的交叉嫡越大，对文本主题类分布的影响也越大。它与信息增益唯一的不同之处在于没有考虑单词未发生的情况，只计算出现在文本中的特征项。如果特征项和类别强相关, P ( Ci | w )就大,若P( Ci) 又很小的话,则说明该特征对分类的影响大。 交叉熵反映了文本类别的概率分布和在出现了某个特定词的条件下文本类别的概率分布之间的距离, 特征词t 的交叉熵越大, 对文本类别分布的影响也越大。熵的特征选择效果都要优于信息增益。 6、二次信息熵(QEMI)： 将二次熵函数应用于互信息评估方法中，取代互信息中的Shannon熵，就形成了基于二次熵的互信息评估函数。基于二次熵的互信息克服了互信息的随机性，是一个确定的量，因此可以作为信息的整体测度，另外它还比互信息最大化的计算复杂度要小，所以可以比较高效地用在基于分类的特征选取上。 7、信息增益方法(Information Gain)： 信息增益方法是机器学习的常用方法，在过滤问题中用于度量已知一个特征是否出现于某主题相关文本中对于该主题预测有多少信息。通过计算信息增益可以得到那些在正例样本中出现频率高而在反例样本中出现频率低的特征，以及那些在反例样本中出现频率高而在正例样本中出现频率低的特征。信息增益是一种基于熵的评估方法,涉及较多的数学理论和复杂的熵理论公式,定义为某特征项为整个分类所能提供的信息量,不考虑任何特征的熵与考虑该特征后的熵的差值。他根据训练数据,计算出各个特征项的信息增益,删除信息增益很小的项,其余的按照信息增益从大到小排序。 信息增益是信息论中的一个重要概念, 它表示了某一个特征项的存在与否对类别预测的影响, 定义为考虑某一特征项在文本中出现前后的信息熵之差。某个特征项的信息增益值越大, 贡献越大, 对分类也越重要。信息增益方法的不足之处在于它考虑了特征未发生的情况。特别是在类分布和特征值分布高度不平衡的情况下, 绝大多数类都是负类, 绝大多数特征都不出现。此时的函数值由不出现的特征决定, 因此, 信息增益的效果就会大大降低。信息增益表现出的分类性能偏低。因为信息增益考虑了文本特征未发生的情况，虽然特征不出现的情况肿可能对文本类别具有贡献，但这种贡献往往小于考虑这种情况时对特征分值带来的干扰。 8、x2统计量方法： x2统计量用于度量特征w和主题类C之间的独立性。而表示除w以外的其他特征，C表示除C以外的其他主题类，那么特征w和主题类C的关系有以下四种 情况: ，用A, B, C, D表示这四种情况的文档频次，总的文档数N=A+B+C+D,扩统计量的计算根据计算公式计算。当特征w和主题类C之间完全独立的时候，x2统计量为0。x2统计量和互信息的差别在于它是归一化的统计量，但是它对低频特征的区分效果也不好。X2 统计得分的计算有二次复杂度, 相似于互信息和信息增益。在 X2 统计和互信息之间主要的不同在于 X2 是规格化评价, 因而 X2 评估分值对在同类中的词是可比的, 但是 X2 统计对于低频词来说是不可靠的。 利用x2 统计方法来进行特征抽取是基于如下假设:在指定类别文本中出现频率高的词条与在其他类别文本中出现频率比较高的词条,对判定文档是否属于该类别都是很有帮助的。 采用x2估计特征选择算法的准确率在实验中最高，其分类效果受训练集影响较小，比较稳定。而且在对文教类和政治类存在类别交叉现象的文本进行分类时，采用x2估计的分类系统表现出了优于其它方法的分类性能。X2估计的可靠性较好，便于对程序的控制，无需因训练集的改变而人为的调节特征阀值的大小。 9、文本证据权(The Weight of Evidence forText) 文本证据权衡量类的概率和给定特征时类的条件概率之间的差别。 10、优势率(Odds Ratio)： ??? 优势率只适用于二元分类的情况，其特点是只关心文本特征对于目标类的分值。Pos表示目标类，neg表示非目标类。 11、遗传算法(Genetic Algorithm, GA)： 文本实际上可以看作是由众多的特征词条构成的多维空间,而特征向量的选择就是多维空间中的寻优过程,因此在文本特征提取研究中可以使用高效寻优算法。遗传算法(Genetic Algorithm, GA)是一种通用型的优化搜索方法,它利用结构化的随机信息交换技术组合群体中各个结构中最好的生存因素,复制出最佳代码串,并使之一代一代地进化,最终获得满意的优化结果。在将文本特征提取问题转化为文本空间的寻优过程中,首先对Web文本空间进行遗传编码,以文本向量构成染色体,通过选择、交叉、变异等遗传操作,不断搜索问题域空间,使其不断得到进化,逐步得到Web文本的最优特征向量。 基于协同演化的遗传算法不是使用固定的环境来评价个体,而是使用其他的个体来评价特定个体。个体优劣的标准不是其生存环境以外的事物,而是由在同一生存竞争环境中的其他个体来决定。协同演化的思想非常适合处理同类文本的特征提取问题。由于同一类别文本相互之间存在一定相关性,因而各自所代表的那组个体在进化过程中存在着同类之间的相互评价和竞争。因此,每个文本的特征向量,即该问题中的个体,在不断的进化过程中,不仅受到其母体(文本)的评价和制约,而且还受到种族中其他同类个体的指导。所以,基于协同演化的遗传算法不仅能反映其母体的特征,还能反映其他同类文本的共性,这样可以有效地解决同一主题众多文本的集体特征向量的提取问题,获得反映整个文本集合某些特征的最佳个体。 12、主成分分析法(Principal Component Analysis，PCA)： 它不是通过特征选取的方式降维的，而是通过搜索最能代表原数据的正交向量，创立一个替换的、较小的变量集来组合属性的精华，原数据可以投影到这个较小的集合。PCA由于其处理方式的不同又分为数据方法和矩阵方法。矩阵方法中，所有的数据通过计算方差一协方差结构在矩阵中表示出来，矩阵的实现目标是确定协方差矩阵的特征向量，它们和原始数据的主要成分相对应。在主成分方法中，由于矩阵方法的复杂度在n很大的情况 以二次方增长，因此人们又开发使用了主要使用Hebbian学习规则的PCA神经网络方法。 主成分分析法是特征选取常用的方法之一，它能够揭示更多有关变量_丰要方向的信息。但它的问题在于矩阵方法中要使用奇异值分解对角化矩阵求解方差一协方差。