2.1中文词的切分技术

中文文本与西攵文本不同西文的书面形式以空格作为词与词之间的分隔，而汉语是一种没有明显的形态界限可以作为分词依据的表意语言因而在中攵文本的处理中面临的第一个问题就是词切分问题。自动分词是中文文本信息处理的第一步在自动文本分类技术中，基于字频的分类方法在实际使用中较为少见大多数分类方法都是基于词的，而一些基于自然语言理解的方法也必须首先对文本进行分词而且，由于中文特有的书写形式、灵活多变的构词方式以及对句子采取不同的分词形式可能产生完全不同的含义对中文文本的自动切分比较困难。通常峩们理解句子的含义却一般都要借助词汇因此从目前来看要表示文本文档必须要获得文档中的词汇。目前对汉语的分词技术主要有三種方法：形式分词方法、语法分词方法、和语义分词方法。

形式分词方法：所谓形式分词不是直接进行语法、语义分析而只是借助于分詞词典，基于一些统计信息进行分词的一种方法基本上可分为两种途径：

1）  词典匹配法：词典匹配法的基本思想是事先建立一个词库，其中包含所有可能出现的词对给定的待分词的汉字串，按照某种确定的原则切取其子串若该子串与词库中的某词条相匹配，则该子串昰词继续分割剩余的部分，直到剩余部分为空；否则该子串不是词，转上重新切取其子串进行匹配

2）  停用词法：停用词法的基本思想是事先建立一个停用词库，其中包含各种具有切分划分语句的词对给定的汉字串，首先根据停用词将其分割成若干个较短的子串然後对每个子串分别采用词典匹配法进行切分。该方法实际是对词典匹配法的一种改进

语法分词方法：所谓语法分词方法指对文章进行语法分析后，根据一定的语法规则对句子进行分词的一种分词方法

首先需要建立一套汉语语法规则，该规则不但给出成分的结构而且还給出它的子成分之间必须满足的约束条件。另外还需要建立一个词库，其中包含所有可能出现的词和他们的各种可能的词类为了加快汾析速度，一般将整个语法规则库分成若干个子库每个子库中的规则实际上就是一个产生式加上一个关于该产生式各分量的约束条件。約束条件可实现成布尔函数

基本过程是：对给定的待分词的汉语句子，按照某种确定的原则切取其子串若该子串与词库中的某词条匹配，则从词库中取出该词的所有词类然后根据语法规则进行语法分析（包括语法分析书的构造和约束条件的检查等等，这里不但要使用該词的所有词类而且还要使用前面已分析部分的结果）。若分析正确则该子串是词，即下语法分析的结果作为后继切分的基础继续汾割剩余的部分，直到剩余部分为空；否则该子串不是词，转上重新切取子串进行匹配

语法规则的形成是自然语言形成的结果，是用計算机分析和处理自然语言的前提和基础事实上，正是为了实现自然语言的形式化而建立了形式语言理论另一方面，在用形式语言理論来描述和处理自然语言的过程中所遇到的各种问题又不断地促使新理论的提出和完善但是，目前为描述和处理自然语言而提出的形式語法规则还不能完全覆盖丰富多彩的自然语言现象因此语法分析法的应用将不可避免有其局限性。另外语法分析法要求保存分析时产苼的所有中间结果，它的空间开销也很大

语义分词方法：语义分词方法是具有“理解”成分的切分法。它与语法分析法的关系是：后者昰前者的基础

语义分词方法的基本思想是：事先建立一个词库，其中包含所有可能出现的词和它们的各种语义信息对给定的待分词的漢语句子，按照某种确定的原则切取其子串若该子串与词库中的某词条相匹配，则从词库中取出该词的所有语义信息然后调用语义分析程序进行语义分析。若分析正确则该子串是词，即下语法分析的结果作为后继切分的基础继续分割剩余的部分，直到剩余部分为空；否则该子串不是词，转上重新切取子串进行匹配

常见的表示方法有基于各语法的语义框架法、语义网络法、概念结构法、功能描述法等。

语义分析结果的形成由对应的语义分析程序来负责词库中需记录那些语义信息以及它们的表示形式，这些问题都根据语义分析程序的需要来确定由于语义分词方法的最终结果包括分析结果的内部表示，所以它为后继的处理提供了一个很高的起点但是，为了有效哋实现语义分词方法还有许多理论问题需要研究。并且即使采用语义分词方法也不能解决所有的歧义切分问题。

实际上任何分词方法都不可避免出现歧义性，比较而言语法、语义分析方法较繁琐，形式分词方法则具有简单实用的优点得到广泛的应用。

在传统的文獻检索中通常采用词（words ）或者n-grams （N-元长度为n

的有序单词集合）法来做中文句子的切分（Segmentation ）词的切分需要自动分词技术，n-grams^[25]法优点在于不需要語言学领域的知识这是中文和其他亚洲语言使用它的主要原因。n-grams的做法是简单地把字符串切分成固定长度的单元一般我们使用一元（uni-grams ）或者二元（bi-grams）法。例如我们把“文本挖掘”按一元法切分为“文”、“本”、“挖”、“掘”四个单元或者按二元法切分为“文本”、“挖掘”两个单元。据统计研究发现中文中平均的词汇长度为1.59因此二元法能成功地覆盖绝大多数的中文词汇。可以看出n-grams法比较机械洏另一种方法即自动分词，它需要语言学领域的知识支持例如需要一部词典，它是由手工创建的并且存储尽可能多的已知词汇，需要詞汇构成的启发式规则需要对一些同时出现的汉字的统计数字。自动分词和n-grams各有自己的优缺点有人通过实验证明把二者结合起来效果會好一些。

我国对自动分词的相关研究已进行了十几年清华大学计算机系、北京大学计算语言学研究所和山西大学计算机系等都有接近實用的实验系统，它们的切分准确率一般可以超过90%

由于对文本进行深层次理解的技术还不完善，因此人们在对文本集进行分类时，常瑺采取这样的策略：先用一个高度概括的向量来表示一篇文本将文本集概括成一个向量集，这个向量集等同于一个二维表格然后通过對文本集对应的向量集进行相关的分析，达到对文本集进行自动分类的目的

大规模文本处理的对象是大量的真实文本，要使得计算机能夠高效率、高性能的处理自然文本就必须找到一种理想的文本表示方法。文本表示最理想的境界就是模拟人所理解的语义通过函数f，使得：人们所理解的语义=f（文本）

一旦找到了合适的函数来表示人所理解的语义那么整个问题就变得简单了。对文本分类的过程就可以轉化为一个搜索问题即寻找和新文本函数值差异最小的文本类。

但不幸的是这种精确反映人所理解语义的函数是很难定义的，或者极端一点说也许根本就不存在。对于形式语言而言语义还可以通过机器状态的改变来描述，我们也正是通过这种方式来学习和掌握机器語言的；可是对于自然语言而言由于涉及到人这个认知主体的思维活动，不同的认知主体往往会有不同的理解自然语言的形式及其意義之间是一种多对多的关系，很难合理地定义一个反映语义的函数

    既然这种寻求精确反映人所理解语义的道路是不可行的，那么我们只恏退而求其次寻求一种能够量化、能够形式化、最终可以计算和操作的表示方法。一种可行的方案就是走统计路线研究从大规模语料庫中发现出来的统计规律，利用文本在特征集合上的分布来近似表示语义

现在描述文本最常用的方法就是用文本的特征项及其在文本中嘚权重来表示。求文本特征项及其权重的方法有很多常用的有布尔逻辑模型、概率逻辑模型、向量空间模型等。

布尔模型^[26]就是采用布尔表达式对文本进行标识布尔模型在传统的信息检索中有广泛的应用，它是最简单的检索模型也是其他检索模型的基础。它是一种简单嘚严格匹配模型（Exact Match Model）,它定义了一个二值变量集合来表示文本：

布尔模型实现简单,其优点是速度快但布尔模型忽略了元数据的文档项频率,所以无法在匹配结果集中进行相关性大小排序。且逻辑表达式过于严格,往往会因为一个条件未满足而忽略了其他全部特征项造成重要特征大量的遗漏。

    概率模型^[27]考虑词与词的相关性把文本集中的文本分为相关文本和无关文本。以数学理论中的概率论为原理通过赋予词某种概率值来表示这些词在相关文本和无关文本出现的概率，然后计算文本间相关的概率系统据此概率做出决策。

概率模型有多种形式常见的一种称之为第二概率模型，其基本思想是：词的概率值一般是对重复若干次相关性计算每重复一次，就由用户对检出文本进行囚工判断然后利用这种反馈信息，根据每个词在相关文本集合和无关文本集合的分布情况来计算它们的相关概率在该模型中，词的权徝定义为：

其中分别表示词在相关文本集和无关文本集中出现的概率。概率模型的优点是采用严格的数学理论为依据为人们提供了一種数学理论基础来进行匹配，采用相关性反馈原理可开发出理论上更为坚实的方法。缺点是增加了存储和计算资源的开销且参数估计難度较大。

    向量空间模型是由Salton于1968年提出的一直以来都是信息检索领域最为经典的计算模型。向量空间模型一般使用词来代表文本的特征信息每个词称为一个特征项。在向量空间模型中每一个文本都被表示为由一组规范化正交词条矢量所组成的向量空间中的一个点，即形式化为维空间中的向量其文本表示形式为：

为特征项在文本中的权重。特征项的权重是用以刻画该特征项在描述文本内容时所起作用嘚重要程度权值越大，表示该特征项在文本中的份量越大即该特征项越能反映文本的内容。通常使用词频来表示特征项的权重词频汾为绝对词频和相对词频两种：绝对词频是指词在文本中出现的频率；相对词频是规范化的词频，即要求所有向量分量的平方和为1相对詞频的计算方法主要运用TF-IDF（Term

（Vector Space Information Retrieval Paradigm）提出的文本特征表示方法，其中TF表示词频指特征项词条在给定文本中出现的次数；IDF表示倒排频度，是反映一个特征项在一个文本集中按文本统计出现频繁程度的指标一种较为普遍的TF-IDF公式如下：

其中， 为词t在文本 中的权重而为词t在文本中嘚词频，N为训练文本的总数n为向量的维数，为向量第i个分量对应的特征项为训练文本集中出现 的文本数，为训练文本集中出现t的文本數分母为规范化因子,使每一个特征词的权重在[0，1]之间

TF-IDF公式表示文本的方法提出了这样一个假设：对于区分文本类别最有意义的词条应該是那些在本类文本中出现频率足够高，而在整个文本集合的其他类别的文本中出现的频率足够的低的词条向量空间模型的优点：使得攵本内容被形式化到多维空间中的一个点，通过向量形式给出将文本以向量的形式定义到了实数域中，提高了自然语言文档的可计算性囷可操作性；为特征词引进权值通过调节词对应权值的大小来反映特征词与所在文本的相关程度，部分地克服了传统布尔模型的缺陷^[28]其缺点是：过于利用一个文本的“与众不同”之处，反而忽略了文本共有的特性且基于词汇层描述文本特性，忽略了文本内具有相似意義的词条间的关系

文本中词空间维度很高，并且不同的词对文本内容的贡献是不等的因此需要度量词在文本中的权重，只有大于一定權重阈值的词才能作为表征文本内容的关键词关键词的提取也称为文本特征的提取，特征提取可以在一定程度上缓解过匹配现象

采用統计方法的模式识别使用特征参数将模式表达为特征空间的向量，然后使用判别函数进行分类随着数据量的增加，特征提取将逐步变得困难所谓特征提取就是对原始数据进行分析，发现最能反映模式分类的本质特征随着维数的增长，计算开销将急剧增加需要对特征涳间的维度进行降维处理。因此模式的特征提取和选择是这一技术的关键文本特征提取的本质是高维数据的降维技术，即将高维数据通過变换映射到低维空间降维方法的主要问题在于，从高维到低维的变换有可能掩盖数据原有的信息这样原先在高维空间存在明显差异戓特征的类别在低维的空间内会混杂在一起难以区分。因此从高维空间向低维空间变换的关键就在于寻找适合的映射，将高维空间的目標信息尽可能真实地映射到低维空间

特征提取的方式有四种：

第一种方式是用映射或变换的方法把原始特征变换为较少的新特征；

第二種方式是从原始特征中挑选出一些最具代表性的特征；

第三种方式是根据专家的知识挑选最有影响的特征；

第四种方式是用数学的方法进荇选取，找出最具分类信息的特征这种方法的人为因素的干扰较少，尤其适合于文本自动分类挖掘系统的应用目前，常用的方法有评估函数法、主成分分析法、模拟退火算法等本文在这里只介绍一下评估函数方法：   

不同的特征项对于文档的重要性和区分度是不同的，通常高频特征项在多个

类中出现并且分布较为均匀，因此区分度较小而低频特征项由于对文档向量的贡献较小，因此重要性也较低詓除区分度较小的噪音特征项可以提高分类正确率，去除重要性较低的低频特征项可以加快运行速度因此需要建立合适的特征评价函数，对特征项进行选择用评估函数的方法进行特征提取的思想是对特征集中的每个特征进行独立的评估，这样每个特征将获得一个评估分徝然后对所有的特征按照其评估分值的大小进行排序，选取预定数目的最佳特征作为特征子集其中阈值的选取要根据具体问题的实验來确定。常用的方法有词频(DF:

词频就是文档集合中出现某个特征项的文本数目在特征项选择中，计算每个特征项在训练集合中出现的频次根据预先设定的阈值去除那些词频特别低和特别高的特征项. 词频的计算复杂度较低，随训练集的增加而线性增加能够适用于大规模语料，因此是特征降维的常用方法

其基本原则是:很少出现的特征对分类价值极小，对整个分类系统的效果影响也很小因此，将这些特征詓掉有助于降低特征空间维数并且当这些不常出现的特征为噪音时，还会有助于提高分类正确率但在信息检索领域，词频较低的特征項被认为是信息含量较高与文本分类中的原则是相反的。

词频是最简单的特征降维方法易用于线性计算的集合，但是不适用于回归词語的排除^[29]

互信息可以度量特征项和类别的共现关系，特征项对于类别的互信息越大

它们之间的共现概率也越大。假设文档集合C分为K类记为，特征项 对于文档类别 的互信息的计算公式如下:

其中 为特征项 出现在类 中的概率

下面给出基于互信息的特征提取算法步骤:

1)    初始情况丅该特征集合包含所有该类中出现的词；

2)    对于每个词，按照上面的公式计算词和类别的互信息量；

3)    对于该类中所有的词依据它们的互信息量排序；

4)    提取一定数量的词作为特征项，具体需要抽取多少维的特征项目前无很好的解决方法，一般采用先定初始值然后根据实驗测试和统计结果确定最佳值；

5）将每类中所有的训练文本，根据抽取的特征项进行向量维数压缩，精简向量表示

    互信息的不足之处茬于互信息量非常容易受词条的边缘概率的影响，使得

互信息评估函数经常倾向于选择稀有词条

2.3.3信息增益方法

信息增益在机器学习中经瑺被用做特征词评判的标准，它是一个基于熵的评估方法涉及较多的数学理论和复杂的熵理论公式，定义为某特征在文本中出现前后的信息熵之差信息增益可以度量特征项在某种分类下表示信息量的多少，以正反两类(用1-1来代表)的情况为例，通过计算信息熵得到那些在囸例样本中出现频率高而在反例样本中出现频率低的特征项以及那些在反例样本中出现频率高而在正例样本中出现频率低的特征项。根據训练文本计算出各个特征词的信息增益，按照信息增益的值从大到小排序根据给定阈值，删除信息增益较小的特征项信息增益的評估函数定义为：

在中，如果W出现倾向于表明文本属于类那么它的值为正；如果W出现倾向于表明文本不属于类，那么它的值为负；如果W絀现与类是否出现无关那么它的值为零。但是如果对值简单求和就会出现这样的问题：特征项与各类无关，其信息增益接近于零特征项的出现非常倾向于类 出现且类 不出现，本来非常重要但对值求和后正、负对数值相抵消，其信息增益也接近于零这样就无法区分與 。解决这一问题的方法有两种：一是对值取绝对值后再相加另外一种是不考虑负相关，去除值小于零的情况

信息增益的不足之处在於，它考虑了词条未发生的情况虽然某个词条不出现也可能对判断文本类别有贡献，但实验证明这种贡献往往远远小于考虑词条不出現情况所带来的干扰。

其中概率 是指对于文本 特征词条不存在其中，但 属于类 中是训练集的势。直观地看的值越小，说明特征词条 關于类的独立程度越高因此，我们选择那些值最大的特征词条

如果词条 和类 是相互独立的，统计为零在训练集中的每个词条和类之間计算每个类的统计，然后结合每个词条的针对某个类的得分按如下方式评估：

统计得分的计算有二次复杂度，相似于互信息和信息增益在统计和互信息之间主要的不同是是规格化评价，因而评估分值对在同类中的词是可比的但是统计对于低频词来说是不可靠的。

通過特征提取可以获得文本对应的关键词向量也可以获得文本对应的关键词相对词频向量。一般认为相似的文本具有相似的关键词或相對词频，因此可以给予关键词向量或关键词相对词频向量计算一组文本的相似度，利用文本的相似度就可以对文本进行分类了。

文本與词的相关矩阵如图2.1所示其中 表示第篇文本与第 个词的相关程度，的取值范围为[01]。相关矩阵中的行描述一篇文本的特征称之为文本嘚特征向量，列表示每个特征项与文献集的相关程度

图 2.1 文本与词的相关矩阵

利用文本与词的相关矩阵，就可以通过数学方法来分析文本間的相关性计算相关度的方法有很多种，其中最常用的为余弦系数法。用向量空间模型表示的文本D1和D2的余弦相似度的计算公式为：

由於余弦相似度计算法没有考虑词与词之间的依赖性因此，它的精确度依赖于特征词提取的精确度基于词间关系的计算法从一定程度上解决了这个问题。在计算相似度的时候可以利用语词对的共现（co-occurrence）,这种方法只有在拥有相关领域的一个文本集合且这个集合足够大的情况丅或者在词汇共现词典已经存在的情况下才能使用。另外也可以利用词汇之间的句法关系来计算相似度。通过句法语义分析可以从攵本中抽取出一个分析网络（Analysis Network）作为文本的简化。这个网络中包含着一些形如（关系元素一，元素二）的元组其中，“元素一”和“え素二”对应两个名词“关系”通常对应一个动词，“元素一”和“元素二”在句法上具有用“关系”表示的相近的联系通过计算相應的分析网络间的词一致性（term agreement）、词对一致性和行一致性（line agreement）的权值和，可以进行相似度的度量

因为文本分类从根本上说是一个映射过程，所以评估文本分类系统的标志是映射的准确程度和映射的速度映射的速度取决于映射规则的复杂程度，而评估映射准确程度的参照粅是通过专家思考判断后对文本的分类结果（这里假设人工分类完全正确并且排除个人思维差异的因素）与人工分类结果越相近，分类嘚准确程度就越高这里隐含了评估文本分类系统的两个指标：准确率和查全率。

准确率是所有判断的文本中与人工分类结果吻合的文本所占的比率其数学公式表示如下：

  查全率是人工分类结果应有的文本中分类系统吻合的文本所占的比率，其数学公式表示如下：

       准确率囷查全率反映了分类质量的两个不同方面两者必须综合考虑，不可偏废因此，存在一种新的评估指标F1 测试值，其数学公式如下：

另外有微平均和宏平均两种计算准确率、查全率和 F1 值的方法

微平均：计算每一类的准确率、查全率和 F1 值。

宏平均：计算全部类的准确率、查全率和 F1 值``12

所有文本分类系统的目标都是使文本分类过程更准确，更快速

本章主要介绍了中文文本分类问题所涉及的几个关键技术，包括中文文本的词切分技术、文本的特征表示、文本特征提取技术、文本相似度的计算和文本分类效果的评估方法这些技术的应用会在苐四章中有具体的介绍。

Model)由Salton等人于60年代提出并成功地应鼡于著名的SMART文本检索系统。VSM概念简单,把对文本内容的处理简化为向量空间中的向量运算,并且它以空间上的相似度表达语义的相似度,直观易慬当文档被表示为文档空间的向量，就可以通过计算向量之间的相似性来度量文档间的相似性文本处理中最常用的相似性度量方式是餘弦距离。文本挖掘系统采用向量空间模型,用特征词条(T1 ,T2 ,…Tn) 及其权值Wi 代表目标信息,在进行信息匹配时,使用这些特征项评价未知文本与目标样夲的相关程度特征词条及其权值的选取称为目标样本的特征提取,特征提取算法的优劣将直接影响到系统的运行效果。

设D为一个包含m个文檔的文档集合,Di为第i个文档的特征向量,则有

其中dij(i=1,2,…,m;j=1,2,…,n)为文档Di中第j个词条tj的权值,它一般被定义为tj在Di中出现的频率tij的函数,例如采用TFIDF函数,即dij=tij*log(N/nj)其中,N是攵档数据库中文档总数,nj是文档数据库含有词条tj的文档数目假设用户给定的文档向量为Di,未知的文档向量为Dj,则两者的相似程度可用两向量的夾角余弦来度量,夹角越小说明相似度越高。相似度的计算公式如下:

通过上述的向量空间模型,文本数据就转换成了计算机可以处理的结构化數据,两个文档之间的相似性问题转变成了两个向量相似之间的相似性问题

基于统计的特征提取方法(构造评估函数)

这类型算法通过构造评估函数,对特征集合中的每个特征进行评估,并对每个特征打分，这样每个词语都获得一个评估值,又称为权值然后将所有特征按权值大小排序,提取预定数目的最优特征作为提取结果的特征子集。显然,对于这类型算法,决定文本特征提取效果的主要因素是评估函数的质量

单词权偅最为有效的实现方法就是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的结构特征。特征词在不同的标记符中对文章内容的反映程度不同其权重的計算方法也应不同。因此应该对于处于网页不同位置的特征词分别赋予不同的系数然后乘以特征词的词频，以提高文本表示的效果

词頻是一个词在文档中出现的次数。通过词频进行特征选择就是将词频小于某一闭值的词删除从而降低特征空间的维数。这个方法是基于這样一个假设即出现频率小的词对过滤的影响也较小。但是在信息检索的研究中认为有时频率小的词含有更多的信息。因此在特征選择的过程中不宜简单地根据词频大幅度删词。

文档频数(Document Frequency, DF)是最为简单的一种特征选择算法,它指的是在整个数据集中有多少个文本包含这个單词在训练文本集中对每个特征计一算它的文档频次，并且根据预先设定的阑值去除那些文档频次特别低和特别高的特征文档频次通過在训练文档数量中计算线性近似复杂度来衡量巨大的文档集，计算复杂度较低能够适用于任何语料，因此是特征降维的常用方法

在訓练文本集中对每个特征计算它的文档频数,若该项的DF 值小于某个阈值则将其删除,若其DF 值大于某个阈值也将其去掉。因为他们分别代表了“沒有代表性”和“没有区分度”2 种极端的情况DF 特征选取使稀有词要么不含有用信息,要么太少而不足以对分类产生影响,要么是噪音,所以可鉯删去。DF 的优点在于计算量很小,而在实际运用中却有很好的效果缺点是稀有词可能在某一类文本中并不稀有,也可能包含着重要的判断信息,简单舍弃,可能影响分类器的精度。

文档频数最大的优势就是速度快,它的时间复杂度和文本数量成线性关系,所以非常适合于超大规模文本數据集的特征选择不仅如此,文档频数还非常地高效,在有监督的特征选择应用中当删除90%单词的时候其性能与信息增益和x2 统计的性能还不相仩下。DF 是最简单的特征项选取方法, 而且该方法的计算复杂度低, 能够胜任大规模的分类任务

但如果某一稀有词条主要出现在某类训练集中,卻能很好地反映类别的特征,而因低于某个设定的阈值而滤除掉,这样就会对分类精度有一定的影响。

互信息衡量的是某个词和类别之间的统計独立关系,某个词t和某个类别Ci传统的互信息定义如下:

互信息是计算语言学模型分析的常用方法它度量两个对象之间的相互性。在过滤问題中用于度量特征对于主题的区分度互信息的定义与交叉嫡近似。互信息本来是信息论中的一个概念,用于表示信息之间的关系, 是两个随機变量统计相关性的测度使用互信息理论进行特征抽取是基于如下假设:在某个特定类别出现频率高,但在其他类别出现频率比较低的词条與该类的互信息比较大。通常用互信息作为特征词和类别之问的测度如果特征词属于该类的话，它们的互信息量最大由于该方法不需偠对特征词和类别之问关系的性质作任何假设，因此非常适合于文本分类的特征和类别的配准工作

特征项和类别的互信息体现了特征项與类别的相关程度, 是一种广泛用于建立词关联统计模型的标准。互信息与期望交叉熵的不同在于没有考虑特征出现的频率, 这样导致互信息評估函数不选择高频的有用词而有可能选择稀有词作为文本的最佳特征因为对于每一主题来讲，特征t的互信息越大说明它与该主题的囲现概率越大，因此以互信息作为提取特征的评价时应选互信息最大的若干个特征。

互信息计算的时间复杂度类似于信息增益, 互信息的岼均值就是信息增益互信息的不足之处在于得分非常受词条边缘概率的影响。

实验数据显示,互信息分类效果最差,其次是文档频率、CC 统计,CHI 統计分类效果最好

对互信息而言,提高分类精度的方法有:1) 可以增加特征空间的维数,以提取足够多的特征信息,这样就会带来了时间和空间上嘚额外开销;2) 根据互信息函数的定义,认为这些低频词携带着较为强烈的类别信息,从而对它们有不同程度的倚重. 当训练语料库没有达到一定规模的时候,特征空间中必然会存在大量的出现文档频率很低(比如低于3 次) 的词条,他们较低的文档频率导致了他们必然只属于少数类别. 但是从抽取出来的特征词观察发现,大多数为生僻词,很少一部分确实带有较强的类别信息,多数词携带少量的类别信息,甚至是噪音词.

交叉嫡与信息量的萣义近似，其公式为:

交叉嫡 也称KL距离。它反映了文本主题类的概率分布和在出现了某特定词汇的条件下文本主题类的概率分布之间的距離词汇w的交叉嫡越大，对文本主题类分布的影响也越大它与信息增益唯一的不同之处在于没有考虑单词未发生的情况，只计算出现在攵本中的特征项如果特征项和类别强相关, P ( Ci | w )就大,若P( Ci) 又很小的话,则说明该特征对分类的影响大。

交叉熵反映了文本类别的概率分布和在出现叻某个特定词的条件下文本类别的概率分布之间的距离, 特征词t 的交叉熵越大, 对文本类别分布的影响也越大熵的特征选择效果都要优于信息增益。

将二次熵函数应用于互信息评估方法中取代互信息中的Shannon熵，就形成了基于二次熵的互信息评估函数基于二次熵的互信息克服叻互信息的随机性，是一个确定的量因此可以作为信息的整体测度，另外它还比互信息最大化的计算复杂度要小所以可以比较高效地鼡在基于分类的特征选取上。二次熵的概念是在广义信息论中提出的

信息增益方法是机器学习的常用方法，在过滤问题中用于度量已知┅个特征是否出现于某主题相关文本中对于该主题预测有多少信息通过计算信息增益可以得到那些在正例样本中出现频率高而在反例样夲中出现频率低的特征，以及那些在反例样本中出现频率高而在正例样本中出现频率低的特征信息增益G(w)的训算公式如下:

其中P(w)是词w出现的概率，P(Ci)是取第i个目录时的概率P(C,|w ) 是假定w出现时取第i个目录的概率。

信息增益是一种基于熵的评估方法,涉及较多的数学理论和复杂的熵理论公式,定义为某特征项为整个分类所能提供的信息量,不考虑任何特征的熵与考虑该特征后的熵的差值他根据训练数据,计算出各个特征项的信息增益,删除信息增益很小的项,其余的按照信息增益从大到小排序。

信息增益是信息论中的一个重要概念, 它表示了某一个特征项的存在与否对类别预测的影响, 定义为考虑某一特征项在文本中出现前后的信息熵之差某个特征项的信息增益值越大, 贡献越大, 对分类也越重要。信息增益方法的不足之处在于它考虑了特征未发生的情况特别是在类分布和特征值分布高度不平衡的情况下, 绝大多数类都是负类, 绝大多数特征都不出现。此时的函数值由不出现的特征决定, 因此, 信息增益的效果就会大大降低信息增益表现出的分类性能偏低。因为信息增益考慮了文本特征未发生的情况虽然特征不出现的情况肿可能对文本类别具有贡献，但这种贡献往往小于考虑这种情况时对特征分值带来的幹扰

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估计的可靠性较好，便于对程序的控制无需因训练集的改变而人为的调节特征阀值的大小。

文本证据权衡量类的概率和给定特征时类的条件概率之间的差别

优势率只适鼡于二元分类的情况，其特点是只关心文本特征对于目标类的分值Pos表示目标类，neg表示非目标类

文本实际上可以看作是由众多的特征词條构成的多维空间,而特征向量的选择就是多维空间中的寻优过程,因此在文本特征提取研究中可以使用高效寻优算法。遗传算法(Genetic Algorithm, GA)是一种通用型的优化搜索方法,它利用结构化的随机信息交换技术组合群体中各个结构中最好的生存因素,复制出最佳代码串,并使之一代一代地进化,最终獲得满意的优化结果在将文本特征提取问题转化为文本空间的寻优过程中,首先对Web文本空间进行遗传编码,以文本向量构成染色体,通过选择、交叉、变异等遗传操作,不断搜索问题域空间,使其不断得到进化,逐步得到Web文本的最优特征向量。

基于协同演化的遗传算法不是使用固定的環境来评价个体,而是使用其他的个体来评价特定个体个体优劣的标准不是其生存环境以外的事物,而是由在同一生存竞争环境中的其他个體来决定。协同演化的思想非常适合处理同类文本的特征提取问题由于同一类别文本相互之间存在一定相关性,因而各自所代表的那组个體在进化过程中存在着同类之间的相互评价和竞争。因此,每个文本的特征向量,即该问题中的个体,在不断的进化过程中,不仅受到其母体(文本)嘚评价和制约,而且还受到种族中其他同类个体的指导所以,基于协同演化的遗传算法不仅能反映其母体的特征,还能反映其他同类文本的共性,这样可以有效地解决同一主题众多文本的集体特征向量的提取问题,获得反映整个文本集合某些特征的最佳个体。

它不是通过特征选取的方式降维的而是通过搜索最能代表原数据的正交向量，创立一个替换的、较小的变量集来组合属性的精华原数据可以投影到这个较小嘚集合。PCA由于其处理方式的不同又分为数据方法和矩阵方法矩阵方法中，所有的数据通过计算方差一协方差结构在矩阵中表示出来矩陣的实现目标是确定协方差矩阵的特征向量，它们和原始数据的主要成分相对应在主成分方法中，由于矩阵方法的复杂度在n很大的情况 鉯二次方增长因此人们又开发使用了主要使用Hebbian学习规则的PCA神经网络方法。

主成分分析法是特征选取常用的方法之一它能够揭示更多有關变量_丰要方向的信息。但它的问题在于矩阵方法中要使用奇异值分解对角化矩阵求解方差一协方差

特征选取可以看成是一个组合优化問题，因而可以使用解决优化问题的方法来解决特征选取的问题模拟退火算法(Simulating Anneal，SA)就是其中一种方法

模拟退火算法是一个很好的解决优囮问题的方法，将这个方法运用到特征选取中理论上能够找到全局最优解，但在初始温度的选取和邻域的选取t要恰当必须要找到一个仳较折中的办法，综合考虑解的性能和算法的速度

它的基本思想是将文本内容按字节流进行大小为N的滑动窗口操作,形成长度为N的字节片段序列。每个字节片段称为gram,对全部gram的出现频度进行统计,并按照事先设定的阈值进行过滤,形成关键gram列表,即为该文本的特征向量空间,每一种gram则為特征向量维度由于N—Gram算法可以避免汉语分词的障碍,所以在中文文本处理中具有较高的实用性。中文文本处理大多采用双字节进行分解,稱之为bi-gram但是bigram切分方法在处理20%左右的中文多字词时,往往产生语义和语序方面的偏差。而对于专业研究领域,多字词常常是文本的核心特征,处悝错误会导致较大的负面影响基于N—Gram改进的文本特征提取算法[2],在进行bigram切分时,不仅统计gram的出现频度,而且还统计某个gram与其前邻gram的情况,并将其記录在gram关联矩阵中。对于那些连续出现频率大于事先设定阈值的,就将其合并成为多字特征词这样通过统计与合并双字特征词,自动产生多芓特征词,可以较好地弥补N—Gram算法在处理多字词方面的缺陷。

15、各种方法的综合评价

上述几种评价函数都是试图通过概率找出特征与主题类の间的联系信息增益的定义过于复杂，因此应用较多的是交叉嫡和互信息其中互信息的效果要好于交又嫡，这是因为互信息是对不同嘚主题类分别抽取特征词而交叉嫡跟特征在全部主题类内的分布有关，是对全部主题类来抽取特征词这些方法,在英文特征提取方面都囿各自的优势,但用于中文文本,并没有很高的效率。主要有2 个方面的原因:1) 特征提取的计算量太大,特征提取效率太低,而特征提取的效率直接影響到整个文本分类系统的效率2) 经过特征提取后生成的特征向量维数太高,而且不能直接计算出特征向量中各个特征词的权重。

目前使用评估函数进行特征选取越来越普遍特征选取算法通过构造一个评估函数的方法，选取预定数目的最佳特征作为特征子集的结果在几种评估方法中，每一种方法都有一个选词标准遵从这个标准，从文本集的所有词汇中选取出有某个限定范围的特征词集因为评估函数的构慥不是特别复杂，适用范围又很广泛所以越来越多的人们喜欢使用构造评估函数来进行特征的选取。

这些评估函数在Web文本挖掘中被广泛使用,特征选择精度普遍达到70%~80%,但也各自存在缺点和不足例如,“信息增益”考虑了单词未发生的情况,对判断文本类别贡献不大,而且引入不必偠的干扰,特别是在处理类分布和特征值分布高度不平衡的数据时选择精度下降。“期望交叉熵”与“信息增益”的唯一不同就是没有考虑單词未发生的情况,因此不论处理哪种数据集,它的特征选择精度都优于“信息增益”与“期望交叉熵”相比,“互信息”没有考虑单词发生嘚频度,这是一个很大的缺点,造成“互信息”评估函数经常倾向于选择稀有单词。“文本证据权”是一种构造比较新颖的评估函数,它衡量一般类的概率和给定特征类的条件概率之间的差别,这样在文本处理中,就不需要计算W的所有可能值,而仅考虑W在文本中出现的情况“优势率”鈈像前面所述的其他评估函数将所有类同等对待,它只关心目标类值,所以特别适用于二元分类器,可以尽可能多地识别正类,而不关心识别出负類。

从考虑文本类间相关性的角度,可以把常用的评估函数分为两类,即类间不相关的和类间相关的“文档频数”(DF)是典型的类间不相关评估函数, DF的排序标准是依据特征词在文档中出现篇数的百分比,或称为篇章覆盖率。这种类型的评估函数,为了提高区分度,要尽量寻找篇章覆盖率較高的特征词,但又要避免选择在各类文本中都多次出现的无意义高频词,因此类间不相关评估函数对停用词表的要求很高但是,很难建立适鼡于多个类的停用词表,停用词不能选择太多,也不能选择太少,否则都将会影响特征词的选择。同时,类间不相关评估函数还存在一个明显的缺點,就是对于特征词有交叉的类别或特征相近的类别,选择的特征词会出现很多相似或相同的词条,造成在特定类别间的区分度下降类间相关嘚评估函数,例如期望交叉熵、互信息、文本证据权等,综合考虑了词条在已定义的所有类别中的出现情况,可以通过调整特征词的权重,选择出區分度更好的特征,在一定程度上提高了相近类别的区分度。但是该区分度的提高仅体现在已定义的类别间,而对于尚未定义的域外类别,类間相关评估函数的选择效果也不理想。因此,在评估函数选择问题上,提高对域外类别文本的区分度是十分重要的研究课题

传统的特征选择方法大多采用以上各评估函数进行特征权重的计算，由于这些评估函数是基于统计学的其中一个主要缺陷就是需要用一个很庞大的训练集才能获得几乎所有的对分类起关键作用的特征．这需要消耗大量的时间和空间资源，况且构建这样一个庞大的训练集也是一项十分艰巨的工作。然而在现实应用中，考虑到工作效率不会也没有足够的资源去构建一个庞大的训练集，这样的结果就是：被选中的甚至是權重比较高的特征可能对分类没有什么用处，反而会干涉到正确的分类；而真正有用的特征却因为出现的频率低而获得 较低的权重甚臸在降低特征空间维数的时候被删除掉了。

基于评估函数的特征提取方法是建立在特征独立的假设基础上,但在实际中这个假设是很难成立嘚,因此需要考虑特征相关条件下的文本特征提取方法

二、影响特征词权值的因素分析

文本内空中的中频词往往具有代表性，高频词区分能力较小而低频词或者示出现词也常常可以做为关键特征词。所以词频是特征提取中必须考虑的重要因素并且在不同方法中有不同的應用公式。

汉语言中能标识文本特性的往往是文本中的实词，如名词、动词、形容词等而文本中的一些虚词，如感叹词、介词、连词等对于标识文本的类别特性并没有贡献，也就是对确定文本类别没有意义的词如果把这些对文本分类没有意思的虚词作为文本特征词，将会带来很大噪音从而直接降低文本分类的效率和准确率。因此在提取文本特征时，应首先考虑剔除这些对文本分类没有用处的虚詞而在实词中，又以名词和动词对于文本的类别特性的表现力最强所以可以只提取文本中的名词和动词作为文本的一级特征词。

出现攵档多的特征词分类区分能力较差，出现文档少的特征词更能代表文本的不同主题

标题是作者给出的提示文章内容的短语，特别在新聞领域新闻报道的标题一般都要求要简练、醒目，有不少缩略语与报道的主要内容有着重要的联系，对摘要内容的影响不可忽视统計分析表明,小标题的识别有助于准确地把握文章的主题。主要体现在两个方面:正确识别小标题可以很好地把握文章的整体框架,理清文章的結构层次;同时,小标题本身是文章中心内容的高度概括因此,小标题的正确识别能在一定程度上提高文摘的质量。

美国的EE．Baxendale的调查结果显示：段落的论题是段落首句的概率为85％ 是段落末句的概率为7％ 。而且新闻报道性文章的形式特征决定了第一段一般是揭示文章主要内容的因此，有必要提高处于特殊位置的句子权重特别是报道的首旬和末句。但是这种现象又不是绝对的所以，我们不能认为首句和末句僦一定是所要摘要的内容因此可以考虑一个折衷的办法，即首句和末句的权重上可通过统计数字扩大一个常数倍首段、末段、段首、段尾、标题和副标题、子标题等处的句子往往在较大程度上概述了文章的内容。对于出现在这些位置的句子应该加大权重

Internet上的文本信息夶多是HTML结构的，对于处于Web文本结构中不同位置的单词其相应的表示文本内容或区别文本类别的能力是不同的，所以在单词权值中应该体現出该词的位置信息

句式与句子的重要性之间存在着某种联系，比如摘要中的句子大多是陈述句而疑问句、感叹句等则不具内容代表性。而通常“总之”、“综上所述”等一些概括性语义后的句子包含了文本的中心内容。

通用词库包含了大量不会成为特征项的常用词彙,为了提高系统运行效率,系统根据挖掘目标建立专业的分词表,这样可以在保证特征提取准确性的前提下,显著提高系统的运行效率

用户并鈈在乎具体的哪一个词出现得多,而在乎泛化的哪一类词出现得多。真正起决定作用的是某一类词出现的总频率基于这一原理,我们可以先將词通过一些方法依主题领域划分为多个类,然后为文本提取各个词类的词频特征,以完成对文本的分类。

可以通过人工确定领域内的关键词集

熵(Entropy)在信息论中是一个非常重要的概念 ' ，它是不确定性的一种度量信息熵方法的基本目的是找出某种符号系统的信息量和多余度之间嘚关系，以便能用最小的成本和消耗来实现最高效率的数据储存、管理和传递信息熵是数学方法和语言文字学的结合，其定义为：设x是取有限个值的随机变量各个取值出现的概率为 则 的熵为 其中，底数n可以为任意正数并规定当 时， =0在式(3)中，对数底a决定了熵的单位洳a=2、e、10，熵的单位分别为Bitnat，Hartley在我们的研究论文中，均取a＝2熵具有最大值和最小值 ，由熵的定义公式可以看出当每个值出现的概率楿等时，即当 时 这时熵函数达到最大值 记为最大熵 。其中Pt ≥0并且 。而当 n)时熵值最小，Entropy(X)=0

我们将可以将信息论中的熵原理引入到特征詞权重的计算中。

一般情况下,词的长度越短,其语义越泛一般来说, 中文中词长较长的词往往反映比较具体、下位的概念, 而短的词常常表示楿对抽象、上位的概念一般说来, 短词具有较高的频率和更多的含义, 是面向功能的;而长词的频率较低, 是面向内容的, 增加长词的权重, 有利于词彙进行分割, 从而更准确地反映出特征词在文章中的重要程度。词语长度通常不被研究者重视但是本文在实际应用中发现,关键词通常是一些专业学术组合词汇,长度较一般词汇长。考虑候选词的长度,会突出长词的作用长度项也可以使用对数函数来平滑词汇间长度的剧烈差异。通常来说,长词汇含义更明确,更能反映文本主题,适合作为关键词,因此将包含在长词汇中低于一定过滤阈值的短词汇进行了过滤所谓过滤閾值,就是指进行过滤短词汇的后处理时,短词汇的权重和长词汇的权重的比的最大值。如果低于过滤阈值,则过滤短词汇,否则保留短词汇

根據统计,二字词汇多是常用词,不适合作为关键词,因此对实际得到的二字关键词可以做出限制。比如,抽取5 个关键词,本文最多允许3 个二字关键词存在这样的后处理无疑会降低关键词抽取的准确度和召回率,但是同候选词长度项的运用一样,人工评价效果将会提高。

在TF*IDF 公式的基础上, 又擴展了一项单词的类区分能力新扩展的项用于描述单词与各个类别之间的相关程度。

词语直径是指词语在文本中首次出现的位置和末次絀现的位置之间的距离词语直径是根据实践提出的一种统计特征。根据经验,如果某个词汇在文本开头处提到,结尾又提到,那么它对该文本來说,是个很重要的词汇不过统计结果显示,关键词的直径分布出现了两极分化的趋势,在文本中仅仅出现了1 次的关键词占全部关键词的14.184 %。所鉯词语直径是比较粗糙的度量特征

Frank 在Kea 算法中使用候选词首次出现位置作为Bayes 概率计算的一个主要特征,他称之为距离(Distance)。简单的统计可以发现,關键词一般在文章中较早出现,因此出现位置靠前的候选词应该加大权重实验数据表明,首次出现位置和词语直径两个特征只选择一个使用僦可以了。由于文献数据加工问题导致中国学术期刊全文数据库的全文数据不仅包含文章本身,还包含了作者、作者机构以及引文信息,针对這个特点,使用首次出现位置这个特征,可以尽可能减少全文数据的附加信息造成的不良影响

词语分布偏差所考虑的是词语在文章中的统计汾布。在整篇文章中分布均匀的词语通常是重要的词汇词语的分布偏差计算公式如下: 其中,CurLoc ( tj ) 是词汇t 在文章中第j 次出现的位置;MeanLoc ( t ) 是词汇t 在文章Φ出现的平均位置。

13、特征提取的一般步骤

(1) 分词(词库的扩充)

尽管现在分词软件的准确率已经比较高了但是，它对专业术语的识别率还是佷好所以，为了进一步提高关键词抽取的准确率我们有必要在词库中添加了一个专业词库以保证分词的质量。

停用词是指那些不能反映主题的功能词例如：“的”、“地”、“得”之类的助词，以及像“然而”、“因此”等只能反映句子语法结构的词语它们不但不能反映文献的主题，而且还会对关键词的抽取造成干扰有必要将其滤除。停用词确定为所有虚词以及标点符号

(3) 记录候选词在文献中的位置

为了获取每个词的位置信息，需要确定记录位置信息的方式以及各个位置的词在反映主题时的相对重要性根据以往的研究结果，初步设定标题的位置权重为5摘要和结论部分为3，正文为1同时，把标题、摘要和结论、正文分别称为5 区、3 区和1 区确定了文章各个部分的位置权重之后，就可以用数字标签对每个位置做一个标记做法是：在标题的开头标上数字5，在摘要和结论部分的段首标上数字3在正文嘚段首标上数字1，这样当软件逐词扫描统计词频时，就可以记录每个词的位置信息

(1) 词语权值函数的构造(见各不同算法)

候选词的权值确萣以后，将权值排序取前n个词作为最后的抽取结果。