6
Journal of Software 软件学报 2005,16(6)
较多的项的结构.为了将文档的表示向量压缩到一个更低的维数,对由初始的文本表示向量组成的矩阵进行奇异值分解,将初始向量映射成一个新的紧凑的向量.LSI取得了一些比较好的结果,主要工作集中在[42, 60, 61].
4 分类方法
?分类方法指如何根据给定的?在??C上的取值归纳出分类器?的内部构成,由第1.1小节关于RTC的叙述,对某些分类方法,仅讨论CSVi的选取即可.
4.1 概率方法
基于概率的分类器中, CSVi(dj)的取值总是与条件概率P(ci|dj)有关,即文本dj属于类别ci的概率.通常通过Bayes理论来估算:
P(ci)P(dj|ci)P(ci)P(dj|ci)P(ci|dj)?? . CP(dj)P(c)P(d|c)?i?1iji较大的T给估计使估计P(dj|ci)变得困难,因此需要如下假设:任意文本中的两个项的出现,当被看作是随机变量时是相互独立的,此假设可以用下面的公式刻画(其中tk?dj表示项tk在dj中出现):
P(dj|ci)??tk?djP(tk|ci).
大多数基于概率的分类器使用类似的假设[30, 42, 62],均称为Na?ve Bayes分类器,因为在实际中,此假设并不被验
证是否严格成立.
P(ci)可以用下式估计;
?{dj?Tr|?(dj,ci)?T}P(ci)?gTr(ci)? .
Tr使用Laplace估计来计算P(tk| ci):
1?tf(tk,ci) , P(tk|ci)?TT??k?1tf(tk,ci)其中tf(tk,ci)?k??(dj,ci)?Trdj?Tr?#(t,dj),表示tk在所有的ci类文本中出现的次数之和.
最后,用于估计P(ci| dj)的公式为:
P(ci|dj)?P(ci)?t?dP(tk|ci)tf(tk,ci)kj?i?1P(ci)?t?dkCjP(tk|ci)tf(tk,ci)
[63]
Na?ve Bayes方法是机器学习中的重要方法,概率模型有所差异,如多变元Bernoulli模型和多项式模,文献是两者的一个很好的比较.
4.2 线性方法
?类别ci的线性分类器的主要构成是一个称为ci的模板(profile)的向量ci??w1i,...wTi?,它与所有的文本表
??示向量处于相同T维空间.对于文本dj,取CSVi(dj)为向量dj和ci间的夹角的余弦值,称为余弦相似性或余弦距
离,即
CSVi(dj)??线性分类器主要通过在线(on line)方法和批(batch)方法计算ci.
4.2.1 在线方法
在线方法在检查完第一个训练样本后即生成一个分类器,在新的训练样本到来时不断地改进分类器.最简单地在线方法是感知器(perceptron)算法[],它首先通过将所有的wki置为相同的正数而得到ci的分类器,当新的
?训练样本dj (以二值权重向量dj表示)来到时,用此分类器进行分类,如果分类正确,则检查下一个训练样本.否则,如果dj是ci的正例,则wki?wki?? (对于所有的k使得wkj=1);如果dj是ci的正例,则wki?wki?? (对于所
?k?1wkiwkjTT22?k?1wki?k?1wkjT.
张博锋 等:基于机器学习的文本分类研究综述
7
有的k使得wkj=1),其中α>0是常数.另外一个著名的在线方法是Widrow-Hoff算法:它的目标是检查完第l个样
????l本后,求得ci,使得平方误差?j?1(ciTdj?[[?(dj,ci)]])2最小.
关于在线方法的研究集中在[][]. 4.2.2 Rocchio方法
?Rocchio方法是最著名,研究最多的批方法.为了计算每个分类ci的模板ci??w1i,...wTi?,使用下面的公式:
wki?????其中POSi?{dj?Tr|?(dj,ci)?T}且NEGi?{dj?Tr|?(dj,ci)?F},wkj是项tk在文本dj中的权重.公式中
{dj?POSi}?wkjPOSi???{dj?NEGi}?wkjNEGi,
β和γ是两个可调的参数.一般来说,反例不应过分强调,故β的取值较大而γ取值较小[].
Rocchio方法非常易于实现,但性能上的缺陷在于如果一个分类包含了两个不相交的领域(即可能同一类文本的主题比较分散),整个类别的模板就会偏离每个领域的模板,导致分类会做出错误的决策.实际上,Rocchio方法产生的分类器和所有线性分类器一样,是将文本向量空间线性地划分,这是一个重要缺陷.
Rocchio方法简单且训练速度非常快,而联合其他方面的技术后也获得了巨大的性能提升,甚至性能不弱于一些较好的方法,因此近来又引起很多学者的兴趣. Ruiz等在计算中取
wkjwkj, wki???????? {d?POS}POSi{d?NPOS}NPOSijiji其中NPOSi是接近正例(near positive)的反例.这是因为在反例中,只有那些接近正例的反例样本对分
类器的影响最大,这也带来一个NPOSi的选取问题;Tsay等先通过普通Rocchio方法计算出所有分类的模板,用这些模板在Tr上进行一次分类,然后将所有分到同一类的文档按一定标准划分为s个子类,共得到|C|·s个子类,
[66]
在这些子类中再应用Rocchio方法进行分类. 4.3 决策树与决策规则方法
TC决策树(decision tree, DT)的内节点(internal node)被标定为项,从内节点出发的分枝标以测试文本中所
?含有的项的权重标定,分类作为它的叶子.这种分类器通过递归地测试向量dj中所含项在决策树中相应内节点的权重来分类文档dj.通常这类分类器都使用二值索引,从而形成了二叉决策树.决策树的学习包括两个步骤:(1)树的归纳,即从训练集Tr中归纳出一棵树,通常对每个分类ci,通过是否包含相通同项tk (项的选择使用IG或熵标准[])的准则递归地分割训练集,最终使得文本均有关于同一个类别的标号(ci或ci),这是一种分制策略的典型应用;(2)树的剪枝,去掉训练集上的任何统计相关性,使树更加简练和强壮.有很多DT学习的软件包可用,最著名的如ID3,此外还有C4.5,C5等.DT分类器常被作为基准(base-line)分类器.
ci的决策规则分类器包含前提为一个DNF(disjunctive conditional form)的条件规则.前提中的文字指示了一个关键词在文档dj中的出现或不出现,结论则指示了在ci下分类dj的决策.与DT类似,DNF规则也可以对二值函数进行编码,但其优点在于可以生成更加紧凑的学习机.规则的学习方法试图从所有的规则中以某种最小原则挑选出最紧凑的规则.与DT的分制策略不同,DNF规则使用自底向上的方式生成.最初,每个样本文件dj可以被认为是一个短句?1,...,?n??i,其中?1,...,?n是dj中所含的项,γi根据dj是否属于分类ci而等于ci或ci;学习过程使用泛化(generalization)步骤,使得规则通过一系列修改(例如去掉一些前提或合并短句)而简化,这种修改使得规则具有最大的紧凑性但不影响规则的能力;最后使用类似于DT中的剪枝过程.用于文本分类的学习机如Charade[],DL-ESC[],SCAR[]等. 4.4 回归方法
在回归方法中,利用已知的函数值来估计未知的函数值,[]使用了线性最小方差拟合(LLSF).在LLSF中,每
?一个文本dj有两个向量和它关联T维的权重向量dj和|C|维的类的权重向量O(dj) (对于训练数据是二值的,而对于测试数据就未必是二值,每个分量可作为CSVi(dj)的值).这样,分类器的归纳过程可以转化为一个计算一个
??d?O(d)的问题.LLSF通过最小方差拟和来使得在训练集上的误差最小,即?,使得MC×T的矩阵Mjj????argminMD?O,其中D?d,...,dM是T×Tr阶矩阵, O?O(d1),...,O(dTr)是C×Tr阶矩阵,对1MTr[43, 46, 64, 65]
????C×T阶矩阵V,V?def?i?1?CT2?通常通过在训练集上进行奇异值分解得到,其每一个分量m?ik代表了项.Mvijtk与类别ci的关联程度.
8
Journal of Software 软件学报 2005,16(6)
?的计算开销,很难扩展到实际的大 [][]的实验认为LLSF是效果最好的分类方法之一,但是,其缺点在于M型计算.
4.5 神经网络方法
神经网络(NN)分类器的输入单元是项,而输出单元是单个类别或一些类别.对一个测试文本dj,将其每个项的权重wkj加载到输入单元,这种激励沿网络传播,输出单元的最终值决定了分类器的决策.NN典型的训练方法是向后传播,即一个训练文本的权重被加载到输入单元,如果出现分类错误,则错误向后传播,修改网络的参数以达到消除错误或将错误最小化的目的.
感知器[]是最简单的线性NN分类器,[]实现了一种形式的对数回归线性NN分类器,产生很好的性能.也有很多非线性的NN分类器的研究,但是性能没有提高或提高很少[]. 4.6 基于实例的方法
基于实例的方法又称为懒惰学习机(lazy learner),或非参数的方法.对于类别ci,不生成显式的,明确的分类器,但对测试文本的决策依赖于训练文本中与之相似的样本.最著名的基于实例的方法是kNN(k nearest neighbors)[].
对于文档dj,要确定它是否属于类别ci,kNN方法考察训练文档中是否与之最相似的k个样本均属于ci,如果对于他们中足够比例的回答是肯定的,则做出肯定的决策,否则做出否定的决策.在Yang方法中定义:
?CSVi(dj)??RSV(dj,dz)?[[?(dz,ci)]],
dz?Trk(dj)其中RSV(dj,di)指dj与di间的某种距离,Trk(dj)是使得RSV(dj,di)最大的k个文本的集合.
方法需要考虑k取值,[]中认为30≤k≤45可能产生最好的效果.
kNN方法对文本向量空间的划分不是线性的,不会带来线性分类方法的问题,因此效果很好.但是它的缺点在于分类的效率,因为它没有将训练过程和分类过程分开,对于每次测试,它都需要在全部的训练样本上进行一次计算,这非常耗时.正是因为上述原因,Lam和Ho提出了对kNN方法的改进,在他们的方法中,进行kNN方法的全集不再是所有的训练文本,而是一些称为GIs(generalized instances)的文本的模板.将方法简要叙述如下:
(1)将训练文本集合的进行聚类,对每个得到一些簇(cluster)的集合Ki?{ki1,...,kiKi};
(2)使用线性方法(如Rocchio或Widrow-Hoff)为每个簇kiz计算出模板G(kiz)称为GI; (3)在所有的模板集上使用kNN方法,即对于文档dj,
?def{dj?kiz|?(dj,ci)?T}{dj?kiz}CSVi(dj)??RSV(dj,G(kiz))??Tr{d?k}kiz?Kijiz . ?{dj?kiz|?(dj,ci)?T}??RSV(dj,G(kiz))?Trkiz?Ki4.7 支持向量机方法
支持向量机(support vector machine, SVM)最初用于模式识别领域,由Joachims在TC首先领域使用,随后[][]
中使用SVM方法的实验都产生很好的性能,也是文本分类中最新的方法.SVM方法面向的是二值分类,给定类别集合{ci,ci},它希望通过一个(T-1)维的超曲面将ci类的正例和反例分开.
???对于线性可分的情形,希望用超平面wTx?b?0将训练样本中的正例和反例分开.根据Vapnik 的结构风险
???最小化理论[],SVM试图找到两个平行超平面wTx?b??1,使得ci的正例反例分别位于这两个超平面的两侧,
???并且两个超平面间的距离最大,分类过程中使用的分割超平面wTx?b?0正位于这两个超平面间的中心位置.
?T???wTx?b??1间的距离为2ww,使其最大相当于使wTw2最小,这样,得到下面的优化问题:
??minw,b
1?T?ww2???s.t.{[?(dj,ci)]}?(wTdj?b)?1,
j?1,...,Tr上述优化问题的约束条件即:
????wTdj?b?1if ?(dj,ci)?T . ???T?wdj?b??1if ?(dj,ci)?F
张博锋 等:基于机器学习的文本分类研究综述
9
对于近似线性可分和线性不可分的情形,可以引入松弛变量或使用核函数[][][].
SVM算法的优点在于它的高性能,在几乎所有的对比实验中,它的性能较其他分类方法总是位于前列,[]详细分析了SVM用于文本分类的优势.但是由于问题的求解实质上是一个带线性约束的二次规划问题,大训练样本量会带来时间和空间上的巨大开销,Dumais等使用一个很新的算法使得SVM的训练时间与Rocchio等计算简单的算法的时间相当,Joachims对此做了优化[],形成了一个SVM系统的实现SVMLight,另一个著名的实现是Chang等的LibSVM[],使用了SMO优化[].
SVM的分类是二值的,在实际应用中对多类问题的处理稍显繁琐,Wei在[]中讨论了一些有用的简化措施, 4.9将讨论的与Na?ve Bayes分类器进行串联的方法就是其中一种. 4.8 多重分类器
多重分类器(multiple classifier)的主要目标是将每个单独的分类器的能力进行组合以获得整个系统整体性能的提高,即将k个已知的分类器?1,...,?k应用于dj是否属于类别ci的决策,再将他们的结果综合起来.多重分类器的设计主要采用两种策略:
(1)决策优化(desicion optimization)
多重分类器使用已经完成训练的单分类器,检查文本后将他们的结果进行综合,这时单分类器和多重分类器的训练是分开的.结果的综合方法有很多种:最简单的方法是MV(majority voting)[],方法将k个单分类器的二值决策看作(肯定或否定的)投票,获得超过半数得票的决策成为多重分类器最后的决策;MV方法的改进是W(weighted)MV,此时,每个单分类器的投票均有权重;与之对应的是WLC(weighted linear combination), dj关于k个分类器CSVi值的加权和形成多重分类器的CSVi值,每个分类器的权重Wt反应了分类器?t的相对能力;如果在验证集上发现在所有分类器中?t对类别ci的效果最好,则在确定CSVi时选择?t的结果作为多重分类器CSVi的结果,这种方法称为DCS(dynamic classifier selection);ACC(adaptive classifier combination)是介于WLC和DCS之间的方法,所有的分类器结果加权求和,但权重由单分类器在与dj最相似的l个验证样本集上的性能确定;Wei将SVM分类器和Na?ve Bayes分类器进行串联式的综合,即先用Na?ve Bayes方法找出所有CSVi中最大的前N位类别(他发现N=3时dj属于这三类之一的比例超过90%),然后在这N类上使用SVM分类.此外,也有将Bayes,决策树等方法应用到分类器综合的例子[].
(2)范围优化(coverage optimization)
每个单分类器所用的算法相同,但是参加训练的样本集合不同,因此形成的不同分类器实质上只是参数不同,单分类器的WMV决定每个文本的分类.这时,单分类器和多重分类器是同时训练的.最成功的方法是Bagging方法和Boosting方法.在Bagging方法中,先给定一个确定的分类方法(或算法),然后胜成k个不同的训练集Tr1,…,Trk,每个Trt都是通过从Tr中随机挑出|Tr|个样本(挑出后再放回,则Trt中可能有重复样本), ?t是在Trt上训练所得的分类器,这样我们得到了k个不同的分类?1,...,?k. Boosting方法与Bagging方法类似,但它更关心?1,...,?t?1分错的样本,因此在选取Trt时会加大取这些样本的概率.BoosTexter系统测试了两种Boosting算法,AdaBoost.MH和AdaBoost.MR.这两种方法的研究集中在[][]. 4.9 其他方法
很多在ML领域,IR领域以及其他一些相关领域所用到的方法和技术在TC领域内都有应用, 如Bayes推理网络(inference network)[],遗传算法[],最大熵模型[]等,很多还不是成熟的应用,因此本文不再一一列举.
5 性能评价
分类器的能力评价是基于实验的,评价通常通过性能(effectiveness)来衡量,性能是指分类器做出正确分类决策的能力. 5.1 评价指标
(1)准确率(precision)和召回率(recall)
分类性能的度量仍旧使用IR领域中准确率(π)和召回率(ρ)的概念.每个类别ci下的准确率πi定义为条件概?率P(?(dx,ci)?T|?(dx,ci)?T),即一个随机的文本dx被分正确分入ci类的概率;对应的召回率ρi定义为条件
?概率P(?(dx,ci)?T|?(dx,ci)?T),即一个实际上属于ci类的文本dx被正确分类的概率.这种概率的定义度量了系统在处理一个实际属于ci类的未知文本时所能表现出的性能的数学期望. πi和ρi估计可以借助ci类在测试集上分类结果的邻接表(见表II):
10
?i??TPiTPi?i? ?,
TPi?FPiTPi?FNiJournal of Software 软件学报 2005,16(6)
表中,FPi是类别
ci下被错误分类的文本数,其他符号可相应理解. 类别ci 分类器决策 YES NO 专家标注 YES NO TPi FPi FNi TNi 表II类别ci的邻接矩阵
π和ρ的计算有两种不同的方法:
? 微平均：ρ和π通过将所有单个类别的决策求和获得，即
TP????TP?FP?CTP?? ??CTP?FN(TP?FP)?i?1ii??i?1TPiC?i?1TPi?i?1(TPi?FNi)CC,
其中TP??i?1TPi,其余符号类似定义:
?
??M宏平均：先计算局部的准确率和召回率,然后再求平均: ???i?1i?CC? ?M???i?1i?CC,
两种方法的结果有时相差很大,例如当一个分类ci的普遍度g?(ci)很小,即训练集中某个ci的正例相对很少时,我们应强调宏平均而不是微平均.因此使用哪一个作为系统的性能评价要视应用而定.
(2)综合评价
分开强调准确率和召回率是没有意义的,例如π值的提高往往以ρ值降低为代价,而即使ρ=1的情况下, π也可能会处于一个非常低的状态[].实际中,往往通过调节阈值τi使得分类器变得更开放(提高ρi,但可能带来πi的损失)或保守(提高πi,但可能带来ρi的损失).因此,分类器的应该结合π和ρ来评价.
? 十一点平均准确率:
调节πi使得ρi分别取到0.0,0.1,…,0.9,1.0十一个数值附近,计算相应的πi的十一个值再取平均.这种方法对二值的CSVi不起作用.
? 无亏损点(breakeven point)
和上面的方法相似,通过不断调节每个τi,可以得到π和ρ变化的曲线,两条曲线相交处π(=ρ)的值称为无亏损点.两条曲线可能不相交,这时取曲线最接近时的值的平均值.
? Fβ函数
对0≤β≤+∞,定义
(?2?1)?? . F???2???这里β可以看作是π和ρ相对重要性的衡量,因为当β=0时, Fβ = π,而β=+∞时, Fβ = ρ.MouLinier,Yang等指出分类器?的无亏损点值总是小于或等于F1.
仍就有很多少见的性能评价方法如准确性(accuracy)和误差(error)等[][],甚至[]中出现了不同于性能,而是效率(efficiency)的评价指标. 5.2 测评基准
关于文本分类的评测基准文集,最常使用Reuters文集,共有五个版本,第四个版本是用来比较分类器性能用到最多的,此外,OHSUMED,(二十类)新闻组,AP文集等也是常用的基准文集,这些文集均已按照相应的主题标注好类别.
文本分类器间性能的直接比较在下面的条件下才有意义:(1)相同的文本集和相同的分类;(2)训练集和测试集的划分相同;(3)相同的评价标准和相同的外部参数设置.然而,在获得一个基准(base-line)分类器在不同条件下的性能,其余两个分类器也可以通过与此基准分类器的直接比较而获得性能上的相对比较. 5.3 分类器性能比较
图I给出了本文中所讨论的分类方法在一些文献的实验中所表现出的性能,实验涉及了Reuters文集不同的版本.这些实验数据均来源于[],性能数据中极少数分类器给出的是(宏或微)F1值绝大部分均是(宏或微)无亏损点值.同一类型的分类器可能因不同的实现和设置而有不同的性能.