1000-9825/2005/16(06)0000 ?2005 Journal of Software 软 件 学 报 Vol.16, No.6 基于机器学习的文本分类研究综述? 题目?张博锋1+, 苏金树2, 徐昕3 作者 12
?
(单位全名 部门(系)全名,省 市(或直辖市) 邮政编码) 单位 (单位全名 部门(系)全名,省 市(或直辖市) 邮政编码) 3
(单位全名 部门(系)全名,省 市(或直辖市) 邮政编码)
Title Title NAME Name-Name1+, NAME Name2, NAME Name-Name3 Name 12
(Department of ****, University, City ZipCode, China) Depart.Correspond (Department of ****, University, City ZipCode, China) 3
(Department of ****, University, City ZipCode, China)
+ Corresponding author: Phn: +86-**-****-****, Fax: +86-**-****-****, E-mail: ****, http://**** Received 2004-00-00; Accepted 2004-00-00 Date Name NN, Name N, Name NN. Title. Journal of Software, 2004,15(1):0000~0000. Information http://www.jos.org.cn/1000-9825/16/0000.htm Abstract: *Abstract.* Abstract Key words: *key word; key word* Key words 摘 要: *摘要内容.* 摘要 关键词: *关键词;关键词* 关键词 中图法分类号: **** 文献标识码: A 分类号 近十几年来，分布于互联网，电子图书馆和新闻机构等信息源的电子化文本资源数量疾速增长，为有效地管理,过滤及和用这些资源,基于内容的文档管理逐渐成为信息系统领域占主导地位的一类技术,统称为信息检索（information retrieval, IR）.文本分类（text categorization, TC）是IR技术的重要组成部分，它的主要任务是在预先给定的类别集合下,根据自然语言文本的内容判定文本的类别,即为文本指派一些预先定义好的类别标记.文本分类应用十分广泛,如基于主题的文本自动索引,词的歧义消除,互联网(或其它) 信息的过滤,web资源的分级目录管理,选择性及自适应的文档分发等[1-9];Liao等人还将文本分类用于入侵检测[10, 11].
在20世纪80年代以前,文本分类使用的主要是知识工程(Knowledge Engineering, KE)方法,即需要领域专家手工定义一些在特定分类体系下归类文本的专家知识库并进行编码,分类器通过这些知识库中的规则进行分类,最著名的系统如CONSTRE系统[12]. 知识工程主要缺点是知识获取的瓶颈,即知识需要特定领域的专家手工定义,而且随着类别和领域的变化,都需要专家参与定制或修改知识.90年代后,机器学习(Machine Learning, ML)方法为越来越多的人所使用并逐渐成为这一领域的主导方法.ML方法更专注于分类器的自动生成,而不仅仅是分类的过程的自动,建立分类器所需要的知识或规则是通过归纳过程(称为学习)自动建立,在移植到其他领域时,分类器本身的建立不再需要领域专家的干涉,并且分类性能与KE方法相当,因此更具有优势.
? Supported by the **** Foundation of China under Grant No.****, **** (基金中文完整名称); the **** Foundation of China
under Grant No.****, **** (基金中文完整名称) 脚注文本 作者简介: 张博锋(1978－),男,陕西铜川人,博士研究生,主要研究领域为*****,****;作者(出生年－),性别,学位(或目前学历),
职称,主要研究领域为****,****;作者名(出生年－),性别,学位(或目前学历),职称,主要研究领域为****,****. 脚注文本1
2
Journal of Software 软件学报 2005,16(6)
本文主要综述了基于机器学习的文本分类方法中所用到的方法技术和评价手段,第一节讨论文本分类问题的定义;第二节概述文本分类的机器学习方法;第三节关于文本表示及降维技术,第四节详细阐述文本分类方法,第五节介绍分类器的性能评价方法,最后是关于中文文本分类的现状以及全文小节.
1 文本分类问题
关于文本分类问题的描述有很多种,其本质是根据文本的内容特征做出一个决策,即文本属于哪一个预先已知的类别.本文中采用的符号和定义都和[3]中基本一致. 1.1 文本分类定义
文本分类的主要任务是为给定的二元组?dj,ci??D?C指派一个布尔值，其中D?{d1,...,dD}是全体文本的集合,C?{c1,...,cC}是预先定义的已知类别集合.如果认为文本dj在分类ci中,则
对每一个类别ci?C,定义类别指示值(class status value)函数CSVi:D?[0.1], CSVi(dj)给出了dj与ci符合程度的指示值(CSVi(dj)的取值根据不同的学习方法而有不同的意义,例如在Na?ve Bayes方法中,定义为某种概率;
?而在Rocchio方法中,定义为两个向量的距离或夹角,等等),作为?(dj,ci)?T可能性的证据.很多情形下讨论的分类器仅限于对文档dj,要么给出其在每个类别c i下的指示值CSVi(dj),要么根据指示值的一个从大到小的分等(rank)或等级的前几位,而不明确给出?(dj,ci),称这种情况称为分等(ranking)分类(RTC).分等分类更便于讨论某些分类方法,也不会影响确定分类定义的概括性,事实上,为了得到?(dj,ci)的值, 可以通过一些方法确定阈值τi,这样CSVi(dj)≥τi解释为?(dj,ci)?T而CSVi(dj)<τi解释为?(dj,ci)?F.
需要指出的是,在本文讨论的文本分类问题中:(1)文本的类别只是一个用于标注文本的符号,不含任何额外的知识;(2)文本的分类只能依靠从文本本身抽取的知识来完成,不存在其它诸如文本类型,出版地等类似于元数据的外部知识. 1.2 单标注与多标注
文本可能属于多个分类,即给定一个自然数1 理论上,单标注问题是更一般的情形,因为用于二值标注问题的算法可以用于多标注,事实上总可以把C?{c1,...,cC}下的多标注问题转化为|C|个独立的在{ci,ci}下的二值标注问题,i=1,…,|C|.这种转化需要一个前 ??提,即对任何c?,c???C,?(dj,c?)与?(dj,c??)的值互不依赖,实际中均假设它是成立的. 1.3 文本分类与信息检索 TC是一种基于内容的文档管理技术,与IR有很多共同的特点,例如在基于ML的TC方法中,分类器的归纳以及使用过程中所遇到的文本经常使用IR风格的索引技术来处理,对分类器性能的评估也使用IR风格的评价指标等.因此,现阶段的TC技术是IR的某些技术为基础的. 2 基于机器学习的文本分类 基于机器学习的文本分类使用一个称为学习机的通用归纳过程,对领域专家预先建立起来的ci和ci类的样本文档的特征进行收集, 观测和学习,预测属于ci类的未知文档的应有特征,自动建立起一个ci的分类器,这是一种有指导的学习(supervised learning). 2.1 初始样本文集 初始样本文集(initial corpus) ??{d1,...,d?}?D是一个在C?{c1,...,cC}中预先分类(即每个Ω中的文本均 张博锋 等:基于机器学习的文本分类研究综述 3 ?被C中某些元素标注)的文本集合,对每一个序偶?dj,ci????C,全函数?:D?C?{T,F}的值已知.称dj为ci ??的正例,若?(dj,ci)?T;称dj为ci的反例,若?(dj,ci)?F.另外定义[[T]]?{[T]}?1,[[F]]?0且{[F]}??1. 初始样本文集一般是由是由领域专家搜集并标注,用于对分类器的归纳,需要注意的是,其本身并不含有除所属类别之外任何的显式的知识(例如规则,标记等).对于 2.2 训练,测试和验证 2.2.1 训练-测试 使用一部分已标定数据建立起分类器后,需要另一部分已标定数据来评价性能,称为训练-测试,因此将初始样本文集划分为两个子集(大小并不需要相同),分别称为: 训练验证集TV?{d1,...,dTV},训练过程通过观测此集合上文本的特征归纳出类别集合C?{c1,...,cC}的分类器?; 测试集Te?{d1,...,dTe},用于测试过程评估分类器的性能.在每一个dj?Te通过分类器后,我们可以比较 ???(dj,ci)与?(dj,ci)的值,分类器的最终性能以所有?(dj,ci)与?(dj,ci)的符合程度为依据. 为了得到可信科学的评价和结果,Te不能以任何方式参与分类器的归纳组成.在实际应用的过程中[13],为了提高性能,最终用于使用的分类器可能在整个初始文集Ω上进行训练,而在TV上训练并经过Te测试的结果可以看成是此分类器性能的一个悲观的估计. 2.2.2 k重交叉验证 将初始样本文集Ω分割为k个不相交的子集Te1,…,Tek,在每个 常使用验证(validation)步骤对分类器内部的一些参数进行优化,以得到更好的性能,这时需要将TV进一步分割为两个集合,分别称为: 训练集:Tv?{d1,...,dTv},用于分类器的归纳; 验证集Va?{d1,...,dVa},通过对Va的不断测试以达到参数优化的目标. 需要说明的是,在估计性能时仍旧需要将验证集Va与测试集Te分开. 为了下文讨论方便,给定文集??D,定义分类ci在Ω上的普及度(generality)g?(ci)为Ω中属于ci的文本的比例[3],即 g?(ci)??{dj??|?(dj,ci)?T}?, 可以很容易得到gTr(ci),gVa(ci),gTe(ci)的形式. 3 文本表示与降维 文本内容本身不可能直接被分类器或分类器生成算法所直接识别,因此需要利用数学模型将文本内容转换为一种简化的描述,以使其能方便地在训练,验证和测试阶段中使用,这个过程称为文本表示(representation)或索引(indexing).为了使文本的表示比较紧凑,还要对初始的表示进行降维. 3.1 文本表示 为了表达文本的内容或语义,大多数工作以文本中某些语义单元的统计性质为基础,这些语义单元称为项(term)或特征(feature).通常以词(或n-gram[14, 15])作为项.但为了能够反映文本中的一些语法及语义特征,有人采用一些复杂的项,如短语(phrase)和词义(word sense)等,实验中没有发现较大的性能提高,而且带来了效率和语义范围上的问题[3, 16, 17].本文讨论的项为词.另外,在进行表示之前,文本的预处理是必要的,包括停词(stop words)的剔除(如介词,助词等内容中性词),寻找同根词(word stemming)等;其次根据应用领域的不同,表示文本时一些主要的注意力可以放在文本的不同部分(如摘要,标题等)[18-20]. 分类方法与文本的表示方法是密切相关,绝大多数的分类方法都是基于VSM(vector space model)模型的,但近年来的研究也发现很多的其它表示方法也具有很好的效果. 3.1.1 VSM模型 VSM模型[21]是比较通用的一种模型,它将文本表示为一个项的权重的向量.设T?{t1,...,tT}是所有至少出 4 Journal of Software 软件学报 2005,16(6) j?现在Tr中的某个文本里一次的项的集合,文本dj的表示为一个权重的向量dj??w1j,...,wT?,其中,0≤wkj≤1 (不 严格地说)反映了项tk对文档dj的语义的贡献. 权重一般在0和1之间(也有例外[22],但不失一般性本文假设权重均在0和1之间),二值权重(即0和1分别代表项的出项或不出现)便是一种比较特殊的情况,称为set of words;非二值情况称为bag of words(BOW),此时对项tk可以使用任何IR中的方法来确定其在文档dj中的权重wkj[3].项的权重计算(term weighting)普遍使用的是tfidf(term frequency/ inverse document frequency)函数[23],其定义如下: Tr , tfidf(tk,dj)?#(tk,dj)?log#Tr(tk)其中#(tk, dj)表示tk在dj中出现的次数, #Tr(tk)表示tk的文档频率,即Tr中有tk出现的文档的数目. tfidf函数主要体现了这样一种现象,即(i)一个项在文档中出现的越多,它越能反映文档的内容,并且(ii)包含一个项的文本越多,项的区别能力就越弱.Joachims等的实验结果表明基于概率的分类器更适用于这种启发式的tfidf模型[24].为了使权重位于于[0,1]区间,并且使文档的表示向量有相同的长度,通常由下式进行标准化[23]: tfidf(tk,dj)wkj? . T2?s?1tfidf(tk,dj)??考虑到了不同项对类的区别能力不同,可以将TEF(见3.2.1小节)或其他与类别相关的统计量引入到wkj的计算中(例如采用tfidf*IG等),称之为有指导的(supervised)权重计算(STW),在不同的实验中, 很多STW获得的性能超过tfidf [25-27]. 其他的权重函数见[28-30],在#Tr(tk)一开始未知(如自适应的文本过滤)的情形下,对tfidf的估计也是必要的[31]. 3.1.2 项概率分布模型 每个文本dj和类别ci均可以看作是一个项的出现的概率分布(term probability distribution: TPD)P(tk,dj)和P(tk, ci),如果关于dj的分布在所有的类别中与ci最为相似,则可以认为dj属于ci类,这种相似性可以KL距离(Kullback-Leibler distance)来衡量[32]. 3.1.3 二维表示 文献[33]中采用了一种新颖的二维(Bidimensional)表示方法,用几个统计量参数揭示文本对本类的区分和表达程度与对其他类的区分和表达程度,将高维的向量空间中所隐含的信息压缩到二维平面上,可以将不同类别的文本基本区分.在这种表示下采用一种启发式的分类算法,性能与几种优秀的分类方法相当.另外二维的表示也给可视化带来了方便. 其他非VSM的表示方法还有如Darmstadt[34],将文本理解为信号序列[35],字符串核(string kernel)[36], 高阶词统计(higher order word statistics)[37] , NLP(Natural Language Processing)[38, 39]等,不再一一列举.非VSM的表示方法的主要缺点在于分类方法便于灵活推广,其适用性也需进一步研究. 3.2 降维 在TC中,基于VSM模型文本表示向量空间的高维数(即T的值很大)会带来存储空间和处理速度的问题,很多复杂的算法,如LLSF [40]无法扩展到较大的T值下.因此在进行分类器的归纳建立之前就需要一个称为降维（dimensionality reduction, DR）的步骤,它的作用主要是将向量空间的大小从T减少到T?< DR通常采用项选择(selection)和项提取(extraction)两类技术,主要区别在于降维后T?是否与T中的项还是同一类型,如前者所得到新项有可能是通过组合或变换初始项而得来. 3.2.1 项选择 项选择技术也称为项空间简化(term space reduction, TSR),从初始的项集合T中选出其子集T? (满足T?< TT?的情况下,还使得分类器的最终性能有一定的提高[49, 50]. Moulinier等使用一种称为wrapper的方法,通过使用和分类器相同的学习方法来确定T?,即从一个项的初 张博锋 等:基于机器学习的文本分类研究综述 5 始集开始,通过增加或删除一些项而不断改变项集合并在Tr上使用基于此项集合的表示进行学习,分类器在验证集上性能变化决定是否接受这个项集合,最终目标是找到一个能产生最好结果并且维数最低的项集合[51],这实际上是一种穷举的方法.在对web页的分类中,文献[52]中采用主成分分析(principle component analysis, PCA)方法,找出项权重的方差矩阵最大的特征值所对应的项.wrapper和PCA方法都存在效率上的问题. 绝大多数工作都采用效率更高,统计意义更充分的过滤(filtering)方法:根据一个称为TSR或TEF(term evaluation function)的函数对每个项的重要性进行打分,保留T?< 更为复杂的TEF基于信息论或来源于IR,目标都是选出那些在ci和ci中分布差别较大的项,因为这些项可能某种程度最能区别ci.这些差别的不同标准产生了不同的TEF,如(1)DIA相关因子z[53],(2)平衡准确率(Accuracy balanced, AccB)[50],(3)χ2统计量[37, 49],(4)NGL系数[43],(5)信息增益(information gain, IG)[37, 54],(6)互量信息(mutual information, MI)[41, 49],(7)让步比(odds ratio, OR)[37, 47],(8)关联得分(relevance score, RS)[46],(9)GGS系数[54] ,(10)BNS(bi-Normal separation)[50]等.以上TEF的数学定义列于表1[3, 50],其中,P(tk,ci)表示对任意随机的文档x,项tk不出现在x中且x属于类ci的概率,可通过以tk和ci的相互出现或不出现的次数来估计,P(tk,ci),P(tk,ci)和P(tk,ci)以及P(tk|ci)和P(tk|ci)都可以类似定义和估算;?(x)是标准正态分布的概率函数并指定 ??1(x)???1(0.0005),x?0.0005.表中所给出的形式都是TEF的局部定义的,为了得到tk的某些全局TEF值,可以 使用求和fsum(tk)??i?1f(tk,ci),最大值fmax(tk)?maxi?1f(tk,ci)或加权求和fwsum(tk)??i?1P(ci)f(tk,ci)等方式. CCC函数表示 z(tk, ci) AccB(tk, ci) MI(tk, ci) log数学形式 P(ci|tk) P(tk|ci)?P(tk|ci) logP(tk,ci) P(tk)P(ci)函数表示 BNS(tk, ci) GSS(tk, ci) NGL(tk, ci) χ2 (tk, ci) IG(tk, ci) 数学形式 ??1(P(tk|ci))???1(P(tk|ci)) P(tk,ci)?P(tk,ci)?P(tk,ci)?P(tk,ci) Tr?[P(tk,ci)?P(tk,ci)?P(tk,ci)?P(tk,ci)] P(tk)?P(tk)?P(ci)?P(ci)Tr?[P(tk,ci)?P(tk,ci)?P(tk,ci)?P(tk,ci)]2 P(tk)?P(tk)?P(ci)?P(ci)c?{ci,ci}t?{tk,tk}RS(tk, ci) OR(tk, ci) P(tk|ci)?d,(d是常数) P(tk|ci)?dlogP(tk|ci)?(1?P(tk|ci)) P(tk|ci)?(1?P(tk|ci))??P(t,c)?logP(t)P(c) P(t,c)表I. 项选择过滤方法的主要TEF [3, 50] 比较性的工作中,Yang的实验(没有考虑BNS)[49]发现IG和χ2对LLSF和kNN分类方法最有效的,在不影响性能的情况下,可以去掉98%的项, #Tr(tk)居次,可以去掉90%的项,并且还发现三者有着非常强的关联.George则从很多不同的方面评价了TEF[50], 证实IG和χ2对准确性的同时失效,并且发现BNS效果在很多方面超过IG. 过滤方法也是有缺陷的,例如多分类问题中一些类中过剩的强预测性项可能会使IG和χ2等TEF忽略其他类中的特征项,从而使评估效果下降, George通过一种轮换(round robin)调整的方式来解决[55]. 3.2.2 项提取 给定一个确定的T?< (1)项聚类 将具有很强语义相关性的项进行分组,就可以将组作为新的项的维.Lewis首先在TC中考虑项聚类,使用称为相互最近邻 (reciprocal nearest neighbor) 的聚类[56],文献[42]利用词之间在训练文本中相互出现和相互不出现信息来度量他们的相关性,上述方法的相同之处在于聚类不受文档类别的影响,是无指导(unsupervised)的; Baker等使用有指导的分布聚类(distributional clustering),利用了项在不同类别的分布信息.分布聚类在度量项与项之间的相似性时采用的方法如KL距离或IB(information bottleneck)等,都取得了很好的效果[57-59].可以看出,与TSR不通,项聚类针对意义相同或相近的项,而TSR的目标是去掉信息含量较少的项[3]. (2)潜在语义索引 (Latent Semantic Indexing, LSI) 认为在很多文本中,项使用的模式总是有很多潜在或隐含的结构,可以使用统计技术来估计这些结构,这样做的好处是可以将一些本身所携带类别信息较少的项(每个项均可能被TSR过滤)组合成为一个携带类别信息