一种高性能的文本特征自动提取算法

一种高性能的文本特征自动提取算法

自动文本分类是检索和挖掘领域的研究热点和关键技术。近年来，它引起了人们的广泛关注和迅速发展。它在检索、新闻推荐、含义差异、文本识别、网络分类等领域发挥着广泛的作用。文本自动分类的主要难题之一是特征空间维数过高,如何降低特征空间维数成为文本自动分类中需要首先解决的问题。特征选择是文本特征降维的一种有效方法,很多学者对此进行了深入的研究,并提出了很多有效的方法,比较经典的有文档频率DF、信息增益IG、χ2统计量CHI、互信息MI和多种方法组合等。这些方法按其特征选择函数计算函数值,然后以降序选择靠前的特征集。在选择过程中,选择尺度是一个重要指标,直接影响着文本分类的性能。实验证明:多数分类器呈现出随特征数量增加,效果快速提高并能迅速接近平稳的特点;但若特征数过大,性能反而可能降低。这表明合理的特征选择尺度不仅能大量降低处理开销,而且在很多情况下可以改善分类器的效果。在确定特征选择尺度时,现有特征选择方法通常采用经验估算方法:如给定特征数的经验值(PFC)或比例(THR)、考虑统计量阈值(MVS)或向量空间稀疏性(SPA)、特征数与文本数成比例(PCS)等一些选择方法。这些方法在某些特定语料库上取得比较好的效果,但通常为观察所得或经验推断,理论基础不充分,不便于文本自动分类的进一步推广研究;因此,研究能适应文本特性的特征自动提取方法是非常必要的。云模型是一种定性定量转换模型,由于其具有良好的数学性质,可以表示自然科学、社会科学中大量的不确定现象。云模型不需要先验知识,它可以从大量的原始数据中分析其统计规律,实现从定量向定性的转化。本文作者结合特征在整体与局部上的χ2分布情况,利用云模型在定性知识表示以及定性、定量知识转换时的桥梁作用,引入云隶属度概念对特征分布加以修正,并且构建了一种逐级动态聚类算法来获取特征集,在此基础上提出一种高性能文本特征自动提取算法。该算法不需要指定聚类数目,能根据特征分布特点自动获取隶属度高的特征集。分析和开放性实验结果表明:该特征集具有特征个数少、分类精度高的特点,性能明显比当前主要的特征选择方法的优。1于词频的特征选择特征选择是通过构造一个特征评分函数,把测量空间的数据投影到特征空间,得到在特征空间的值,然后,根据特征空间中的值对每个特征进行评估。特征选择并没有改变原始特征空间的性质,只是从原始特征空间中选择了一部分重要的特征,组成一个新的低维空间。特征选择是文本特征降维的一种有效方法。目前已有的特征选择方法主要分为2类:(1)倾向于词频的特征选择方法,如DF,IG,χ2统计量CHI和MI等;(2)倾向于类别的特征选择方法,如CTD特征选择方法和带有强类别信息词SCIW特征选择方法等。第1类方法强调词频在所有类别上的整体分布;第2类方法强调类别信息,而对词频在所有类别上的整体分布考虑不充分。如果能有效地结合词频在所有类别的整体分布和在单个类别上的分布情况,将会明显改善特征选择性能。此外,还有期望交叉熵(ECE)、文本证据权(WET)、优势率(OR)等一些特征选择方法,文献对DF,IG,MI,CHI,ECE,WET和OR这些特征选择方法进行了比较,结果表明:OR方法的效果最好,IG,CHI和ECE的效果次之,WET和DF的效果再次之,MI的效果最差。而Yang等认为IG是最好的测度之一。Forman等分别从有效性、区分能力及获得最好效果的机会等方面对不同特征选择方法进行了广泛比较,结果表明:CHI和IG等统计量及组合方法具有一定的优势。从上述分析看,这些方法对提高文本分类的效果都没有绝对优势。这是因为文本分类本身涉及训练数据集合本身的特点,同时,不同分类器的分类效果也不尽相同。2类别特征的统计方法χ2统计量的概念来自列联表检验,用来衡量特征ti和类别Cj之间的统计相关性。实验证明是一种比较好的特征选择方法,它基于ti和Cj之间符合具有一阶自由度的χ2分布假设。ti关于Cj的χ2可由下式计算:式中:N为训练语料中文档总数;A为属于类Cj的文档频数;B为不属于Cj类但包含ti的文档频数;C为属于Cj类但不包含ti的文档频数;D是既不属于Cj也不包含ti的文档频数。可知当特征ti与类别Cj相互独立时,χ2(ti,Cj)=0,此时特征ti不包含任何与类别Cj有关的信息。特征ti与类别Cj的统计相关性越强,χ2(ti,Cj)越大,此时,特征ti包含的与类别Cj有关的信息就越多。由χ2计算公式可以看出:χ2统计方法作为特征选择方法时,只考虑了特征在所有文档出现的文档频数。若某一特征只在一类文档的少量文档中频繁出现,则通过χ2计算公式计算的χ2统计值很低,在特征选择时,这种特征词就会被排除,但这种在少量文档中频繁出现的特征词很有可能对分类的贡献很大,如专指概念。这是χ2统计的不足之处,它对低文档频的特征项不可靠。基于以上分析,考虑特征在各个类别之间的分布情况,建立特征关于类别的χ2分布矩阵。定义如下:从F的构造可以看出:F中的每一行反映了特征在不同类别中的分布情况,每一列反映了在同一类别中不同特征的分布情况。将二者结合起来,能够完整反映整个特征集的分布,而且客观上弥补了χ2统计量作为特征选择方法上的缺点。3类别中出现比较频繁的特征通过分析每一类别上不同特征的χ2分布情况可见:一些χ2较大的特征在类别中出现频率极低,而另一些在类别中出现比较频繁的特征χ2反而很小。这种异常的出现正是由于这些特征打破了χ2统计量基于ti和Cj之间符合具有一阶自由度的χ2分布,受整体分布影响较大,需要加以修正。由此,本文为每个特征引入一个模糊概念,用云模型对其在类别上的分布进行定量描述,将特征对于类别的χ2用相应的隶属度加以修正。3.1云域和云图中的概念云模型用语言值表示某个定性概念与其定量表示之间的不确定性,已经在智能控制、模糊评测等多个领域得到应用。定义1设U是一个用数值表示的定量论域,C是U上定性概念。若定量值x∈U是定性概念C的一次随机实现,x对C的确定度μ(x)∈[,0]1是有稳定倾向的随机数,μ:U→,∀x∈U,x→μ(x),则x在论域U上的分布称为云,记为云C(X)。每一个x称为一个云滴。如果概念对应的论域是n维空间,那么可以拓广至n维云。定义2设X是一个普通集合X={x},称为论域。隶属度在基础变量上的分布称为云。在对模糊集的处理过程中,论域中某一点到它的隶属度之间的映射是一对多的转换,不是一条明晰的隶属曲线,从而产生了云的概念。云用期望Ex(Expectedvalue)、熵En(Entropy)、超熵He(Hyperentropy)这3个数字特征来整体表征一个概念。期望Ex是云滴在论域空间分布的期望,是最能够代表定性概念的点;熵En代表定性概念的可度量粒度,熵越大,通常概念越宏观,也是定性概念不确定性的度量,由概念的随机性和模糊性共同决定。超熵He是熵的不确定性度量,即熵的熵,由熵的随机性和模糊性共同决定。用3个数字特征表示的定性概念的整体特征记作C(Ex,En,He),称为云的特征向量。正向云算法和逆向云算法是云模型中2个最基本、最关键的算法。前者把定性概念的整体特征变换为定量数值表示,实现概念空间到数值空间的转换;后者实现从定量值到定性概念的转换,将一组定量数据转换为以数字特征{Ex,En,He}来表示的定性概念。3.2动态聚类算法通过特征χ2分布矩阵,特征的取值不仅反映了特征对整个分类作用大小,也反映了该特征对于每一类别的贡献程度。通过云模型隶属度函数的引入,更修正了特征在类别中的分布情况。通过提取每一类别隶属度最高的特征集,合并而成最终的分类特征集合,不仅可以保留对整个分类贡献最大的特征集,同时兼顾某些特征集较少(或者在某一类中出现频率大,但总体出现概率低的特征)的类别。在对特征取值进行隶属度表示后,特征在类别上的取值表示成了区间上的连续值。特征对类别的相关性越大,其隶属度越高。但每一类别仍包含大量特征,其中很大一部分特征对于类别的隶属度极低,需要对特征集进行初步筛选,减少特征提取计算量。定义3一维论域中U中,任一小区间上的云滴群∆x对定性概念A的贡献∆C为:由定义3,可以计算得到U上所有元素对概念A的总贡献C为:基于以上分析,通过计算可以得到位于区间[Ex-0.67En,Ex+0.67En]的特征,占特征总量的22.33%,但它们对类别的贡献占50%,能够满足特征提取需要,故将在此区间的特征筛选为初选特征集。在特征的提取上,可以采用动态聚类方法进行处理。但是,在聚类过程中,类别个数应该是与数据本身特性有关,而不是一个经验值。因此,采用逐步试探聚类类别个数直至最终满足聚类要求的思路,提出了逐级动态聚类算法。算法1:逐级动态聚类算法。输入:类别向量Ci//即第2节中χ2分布矩阵F中的列向量。输出:特征集合Ti。算法步骤:(1)提取Ci中所有不重复的特征隶属度以升序构成新类别向量Ci′={dij,Clusterid},其中Clusterid为聚类类别编号。(3)初始类别K=1,v=e+1//v为循环控制变量。(4)WHILE(v>e)DO//当v≤e时,各类的聚合程度已经比较好,聚类结束。1)构建中心类别表TC:将Ci′平均分成K+1份,取区间右端点加入TC,作为C′在K情况下的初始类别,同时将Ci′各元素Clusterid置为0;2)设定临时循环控制变量e1=0;3)当e1≠v时,执行以下循环://聚类稳定后,各类的标准差将收敛为稳定值。(2)计算Ci′中每个值与TC中各类别距离,将其归并到距离最小的类别中;(3)根据加权平均修正TC中各类别的中心距离;(4)计算TC中各类别的标准差Si,令4)K=K+1//聚类类别数加1,进行下一轮的聚类处理。(5)聚类结束,K′=K-1即为聚类类别数。编号为K′的特征为类别Ci隶属度最大的特征集,(6)RETURNTi。算法1的复杂度分析:设类别Ci上特征的平均个数为n,算法时间复杂度主要由步骤(4)决定。步骤(4)是一个典型的k均值聚类,其时间复杂度为O(k×n),因此,步骤(4)的时间复杂度为O(k2×n)(其中,k为平均聚类个数)。故算法1的时间复杂度为O(k2×n),空间复杂度为O(n)。在算法1的基础上,提出了一种云隶属度下的文本特征自动提取算法。该算法不需要指定聚类数目,能根据特征分布特点自动获取隶属度高的特征集,具体见算法2。算法2:基于云隶属度的文本特征自动提取算法(FAS)。输入:特征χ2分布矩阵F,训练集TR。输出:经过特征选择后的训练集TR′。算法步骤:初始化特征集T=φ;依次选择F中每一列Ci,进行以下步骤处理:1)运用逆向云算法计算Ci的数字特征C(Ex,En,He);2)运用正向云算法将Ci特征值转化成对应隶属度;3)将Ci中区间[Ex-0.67En,Ex+0.67En]外的特征删除,得到初次约简类别向量Ci′;4)在Ci′基础上调用逐级动态聚类算法(算法1)得到选择后特征集Ti;6)删除TR中不属于T的所有特征项,得到选择处理后训练集TR′。算法2的复杂度分析:设训练集类别平均特征数为n,类别数为m,则算法2的时间复杂度为O(k2×n×m)(k为平均聚类个数),空间复杂度为O(n)。4文本分类测试为了测试本文算法的有效性,对FAS算法进行横向对比测试。实验中,采用性能较好的kNN分类器算法(k=30)进行文本分类测试。测试结果用准确率(即分类正确数/实际分类数)、查全率(即分类正确数/应有数)和宏平均(P为准确率;R为召回率)进行评测。4.1pv.0训练集、测试集的构建实验选用中文语料库TanCorpV1.0与英文语料库Reuters-21578。TanCorpV1.0包含文本14150篇,共分为12类。经过停用词移除、词干还原等处理后,得到词条72584个。对于Reuters-21578,使用只有1个类别且每个类别至少包含5个以上的文档。这样,得到训练集5273篇、测试集1767篇。经过停用词移除、词干还原等处理后,得到13961个词条。4.2fp3算法在reunths-1263-2000上的分类性能比较现有特征选择方法通常采用经验方式来确定特征数目,为了得到各特征选择方法在达到最佳分类性能时的特征数,采用了逐步增加特征数的方法来确定。测试结果如表1和2所示。从表1和2可以看出:IG和CHI方法随着特征数的增加,分类性能提升较快,而MI方法需要的特征数则较多,性能提升缓慢。同时,当特征数达到某个阈值时,各特征选择方法性能均会达到最佳状态。但此阈值的获取因特征选择方法的不同、语料库的差异而各有不同,需要大量实验才能得到。而使用FAS算法在TanCorpV1.0上自动提取的特征数平均为1380个,在Reuters-21578上自动提取的特征数平均为239个,不仅不需要任何经验知识,而且特征数明显少于已有特征选择方法的特征数。将FAS算法选择的特征集进行分类测试,性能比较结果见表3和4。从表3和4可以看出:与IG,CHI和MI这3种算法相比,FAS算法提取的特征集具有个数少、分类精度高的特点。kNN方法在TanCorpV1.0上的最好宏平均(F1=84.78%)与Reuters-21578上的最好宏平均(F1=86.1%)相比,基于FAS算法提取特征集上,kNN方法宏平均提高了5%~6%,说明该算法提取的特征集具有比较高的类别描述能力。从分类的时间开销来看