©2005 Journal of Software 软件学报基于机器学习的文本分类研究综述*张博锋1+, 苏金树2, 徐昕31(单位全名部门(系)全名,省市(或直辖市) 邮政编码2(单位全名部门(系)全名,省市(或直辖市) 邮政编码3(单位全名部门(系)全名,省市(或直辖市) 邮政编码)NAME Name-Name1+, NAME Name2, NAME Name-Name3123(Department of ****, University, City ZipCode, China)Name NN, Name N, Name NN. Title. Journal of Software, 2004,15(1):0000~0000./1000-9825/16/0000.htmAbstract: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 Chinaunder Grant No.****, **** (基金中文完整名称作者简介: 张博锋(1978－),男,陕西铜川人,博士研究生,主要研究领域为*****,****;作者(出生年－),性别,学位(或目前学历),职称,主要研究领域为****,****;作者名(出生年－),性别,学位(或目前学历),职称,主要研究领域为2 Journal of Software 软件学报 2005,16(6)本文主要综述了基于机器学习的文本分类方法中所用到的方法技术和评价手段,第一节讨论文本分类问题的定义;第二节概述文本分类的机器学习方法;第三节关于文本表示及降维技术,第四节详细阐述文本分类方法,第五节介绍分类器的性能评价方法,最后是关于中文文本分类的现状以及全文小节.1 文本分类问题关于文本分类问题的描述有很多种,其本质是根据文本的内容特征做出一个决策,即文本属于哪一个预先已知的类别.本文中采用的符号和定义都和[3]中基本一致.1.1 文本分类定义文本分类的主要任务是为给定的二元组C D ⨯>∈<i j c d ,指派一个布尔值，其中},...,{1D D d d =是全体文本的集合,},...,{1C C c c =是预先定义的已知类别集合.如果认为文本d j 在分类c i 中,则<d j ,c i >的赋值为T (称作d j 被c i 标注或d j 属于c i 类),否则赋值为F .即通过建立一个函数},{:F T →⨯ΦC D 来估计未知的目标函数},{:F T →⨯ΦC D (Φ 定义了每一个文本的实际分类),使得Φ和Φ 能够尽量一致.将Φ称为分类器, Φ和Φ 的一致程度,称为分类器的性能,将在第5节中讨论.上述定义要求分类器对每一个<d j ,c i >给出一个显式的T 或F 的判别, 也称为确定(hard)分类(HTC).对每一个类别C ∈i c ,定义类别指示值(class status value)函数]1.0[:→D i CSV , CSV i (d j )给出了d j 与c i 符合程度的指示值(CSV i (d j )的取值根据不同的学习方法而有不同的意义,例如在Naïve Bayes 方法中,定义为某种概率;而在Rocchio 方法中,定义为两个向量的距离或夹角,等等),作为T c d i j =Φ),( 可能性的证据.很多情形下讨论的分类器仅限于对文档d j ,要么给出其在每个类别c i 下的指示值CSV i (d j ),要么根据指示值的一个从大到小的分等(rank)或等级的前几位,而不明确给出),(i j c d Φ,称这种情况称为分等(ranking)分类(RTC).分等分类更便于讨论某些分类方法,也不会影响确定分类定义的概括性,事实上,为了得到),(i j c d Φ的值, 可以通过一些方法确定阈值τi ,这样CSV i (d j )≥τi 解释为T c d i j =Φ),(而CSV i (d j )<τi 解释为F c d i j =Φ),(.需要指出的是,在本文讨论的文本分类问题中:(1)文本的类别只是一个用于标注文本的符号,不含任何额外的知识;(2)文本的分类只能依靠从文本本身抽取的知识来完成,不存在其它诸如文本类型,出版地等类似于元数据的外部知识.1.2 单标注与多标注文本可能属于多个分类,即给定一个自然数1<k ≤|C |,正好k （或≤k ,或≥k ）个C 中的元素标注每个D ∈j d ,上述情况称为多标注(multi-label)问题;而每个D ∈j d 只能属于一个分类的情况称为单标注(single-label)问题.单标记问题的一个特殊形式是二值(binary)标注问题,此时,对每个C ∈i c ,C 可以记为},{i i c c =C ,则对D ∈j d 要么认为它属于分类c i ,要么属于c i 的补i c .理论上,单标注问题是更一般的情形,因为用于二值标注问题的算法可以用于多标注,事实上总可以把},...,{1C C c c =下的多标注问题转化为|C |个独立的在},{i i c c 下的二值标注问题,i =1,…,|C |.这种转化需要一个前提,即对任何C ∈'''c c ,,),(c d j 'Φ 与),(c d j ''Φ 的值互不依赖,实际中均假设它是成立的.1.3 文本分类与信息检索TC 是一种基于内容的文档管理技术,与IR 有很多共同的特点,例如在基于ML 的TC 方法中,分类器的归纳以及使用过程中所遇到的文本经常使用IR 风格的索引技术来处理,对分类器性能的评估也使用IR 风格的评价指标等.因此,现阶段的TC 技术是IR 的某些技术为基础的.2 基于机器学习的文本分类基于机器学习的文本分类使用一个称为学习机的通用归纳过程,对领域专家预先建立起来的c i 和i c 类的样本文档的特征进行收集, 观测和学习,预测属于c i 类的未知文档的应有特征,自动建立起一个c i 的分类器,这是一种有指导的学习(supervised learning).2.1 初始样本文集初始样本文集(initial corpus) D ⊂=ΩΩ},...,{1d d 是一个在},...,{1C C c c =中预先分类(即每个Ω中的文本均张博锋 等:基于机器学习的文本分类研究综述 3被C 中某些元素标注)的文本集合,对每一个序偶C ⨯Ω>∈<i j c d ,,全函数},{:F T →⨯ΦC D 的值已知.称d j 为c i 的正例,若T c d i j =Φ),( ;称d j 为c i 的反例,若F c d i j =Φ),( .另外定义1}][{]][[==T T ,0]][[=F 且1}][{-=F .初始样本文集一般是由是由领域专家搜集并标注,用于对分类器的归纳,需要注意的是,其本身并不含有除所属类别之外任何的显式的知识(例如规则,标记等).对于2.2 训练,测试和验证2.2.1 训练-测试使用一部分已标定数据建立起分类器后,需要另一部分已标定数据来评价性能,称为训练-测试,因此将初始样本文集划分为两个子集(大小并不需要相同),分别称为: 训练验证集},...,{1TV d d TV =,训练过程通过观测此集合上文本的特征归纳出类别集合},...,{1C C c c =的分类器Φ; 测试集},...,{1Te d d Te =,用于测试过程评估分类器的性能.在每一个Te d j ∈通过分类器后,我们可以比较),(i j c d Φ与),(i j c d Φ 的值,分类器的最终性能以所有),(i j c d Φ与),(i j c d Φ 的符合程度为依据.为了得到可信科学的评价和结果,Te 不能以任何方式参与分类器的归纳组成.在实际应用的过程中[13],为了提高性能,最终用于使用的分类器可能在整个初始文集Ω上进行训练,而在TV 上训练并经过Te 测试的结果可以看成是此分类器性能的一个悲观的估计.2.2.2 k 重交叉验证将初始样本文集Ω分割为k 个不相交的子集Te 1,…,Te k ,在每个<TV i =Ω-Te i ,Te i >上使用测试-训练方法可以生成k 个不同的分类器k ΦΦ,...,1,估计其各自的性能,最终的分类器的性能是每个分类器性能的某种平均[13].2.2.3 验证常使用验证(validation)步骤对分类器内部的一些参数进行优化,以得到更好的性能,这时需要将TV 进一步分割为两个集合,分别称为:训练集:},...,{1Tv d d Tv =,用于分类器的归纳; 验证集},...,{1Va d d Va =,通过对Va 的不断测试以达到参数优化的目标.需要说明的是,在估计性能时仍旧需要将验证集Va 与测试集Te 分开.为了下文讨论方便,给定文集D ⊂Ω,定义分类c i 在Ω上的普及度(generality))(i c g Ω为Ω中属于c i 的文本的比例[3],即 Ω=ΦΩ∈=Ω}),(|{)(T c d d c g i j j i ,可以很容易得到)(i Tr c g ,)(i Va c g ,)(i Te c g 的形式.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]是比较通用的一种模型,它将文本表示为一个项的权重的向量.设},...,{1T T t t =是所有至少出4 Journal of Software 软件学报 2005,16(6)现在Tr 中的某个文本里一次的项的集合,文本d j 的表示为一个权重的向量>=<j j j w w d T ,...,1 ,其中,0≤w kj ≤1 (不严格地说)反映了项t k 对文档d j 的语义的贡献.权重一般在0和1之间(也有例外[22],但不失一般性本文假设权重均在0和1之间),二值权重(即0和1分别代表项的出项或不出现)便是一种比较特殊的情况,称为set of words;非二值情况称为bag of words(BOW),此时对项t k 可以使用任何IR 中的方法来确定其在文档d j 中的权重w kj [3].项的权重计算(term weighting)普遍使用的是tfidf (term frequency/ inverse document frequency)函数[23],其定义如下: )(#log ),(#),(k Tr j k j k t Tr d t d t tfidf ⋅=, 其中#(t k , d j )表示t k 在d j 中出现的次数, #Tr (t k )表示t k 的文档频率,即Tr 中有t k 出现的文档的数目. tfidf 函数主要体现了这样一种现象,即(i)一个项在文档中出现的越多,它越能反映文档的内容,并且(ii)包含一个项的文本越多,项的区别能力就越弱.Joachims 等的实验结果表明基于概率的分类器更适用于这种启发式的tfidf 模型[24].为了使权重位于于[0,1]区间,并且使文档的表示向量有相同的长度,通常由下式进行标准化[23]:()∑==T 12),(),(s j k j k kj d t tfidf d t tfidf w . 考虑到了不同项对类的区别能力不同,可以将TEF(见3.2.1小节)或其他与类别相关的统计量引入到w kj 的计算中(例如采用tfidf *IG 等),称之为有指导的(supervised)权重计算(STW),在不同的实验中, 很多STW 获得的性能超过tfidf [25-27].其他的权重函数见[28-30],在#Tr (t k )一开始未知(如自适应的文本过滤)的情形下,对tfidf 的估计也是必要的[31].3.1.2 项概率分布模型每个文本d j 和类别c i 均可以看作是一个项的出现的概率分布(term probability distribution: TPD)P (t k ,d j )和P (t k , c i ),如果关于d j 的分布在所有的类别中与c i 最为相似,则可以认为d j 属于c i 类,这种相似性可以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 '<<T ,T '称为缩减后的项集合.从范围来区分,降维可以是局部或全局的:如果对每一个类别c i ,寻找项的集合i T ',满足i T '<<T ,即对不同的分类,使用T 的不同子集,则称为局部DR [18, 41-46];如果对所有的分类},...,{1C C c c =,寻找相同的项集合T ',满足T '<<T ,则称为全局DR [37, 47-49].大部分的将维技术均可以应用于全局和局部DR.DR 通常采用项选择(selection)和项提取(extraction)两类技术,主要区别在于降维后T '是否与T 中的项还是同一类型,如前者所得到新项有可能是通过组合或变换初始项而得来.3.2.1 项选择项选择技术也称为项空间简化(term space reduction, TSR),从初始的项集合T 中选出其子集T ' (满足T '<<T ),使得当T '用于文档索引时能够产生最好的性能.很多针对某些特定分类方法的TSR 技术在获得一定简化强度(aggressivity)T T'的情况下,还使得分类器的最终性能有一定的提高[49, 50].Moulinier 等使用一种称为wrapper 的方法,通过使用和分类器相同的学习方法来确定T ',即从一个项的初张博锋 等:基于机器学习的文本分类研究综述 5 始集开始,通过增加或删除一些项而不断改变项集合并在Tr 上使用基于此项集合的表示进行学习,分类器在验证集上性能变化决定是否接受这个项集合,最终目标是找到一个能产生最好结果并且维数最低的项集合[51],这实际上是一种穷举的方法.在对web 页的分类中,文献[52]中采用主成分分析(principle component analysis, PCA)方法,找出项权重的方差矩阵最大的特征值所对应的项.wrapper 和PCA 方法都存在效率上的问题.绝大多数工作都采用效率更高,统计意义更充分的过滤(filtering)方法:根据一个称为TSR 或TEF(term evaluation function)的函数对每个项的重要性进行打分,保留T '<<T 个得分最高的项,即过滤到那些得分较低的项.这种方法非常有效,例如,最简的全局TEF 是t k 的文档频率#Tr (t k ),即只有那些出现在最多的文本中的项被保留[18, 24, 31],Yang 的实验中证实它可以将维数降低十倍左右而不降低性能,百倍左右的简化强度也只带来很小的性能下降[49].更为复杂的TEF 基于信息论或来源于IR,目标都是选出那些在c i 和i c 中分布差别较大的项,因为这些项可能某种程度最能区别c i .这些差别的不同标准产生了不同的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],其中,),(i k c t P 表示对任意随机的文档x ,项t k 不出现在x 中且x 属于类c i 的概率,可通过以t k 和c i 的相互出现或不出现的次数来估计,),(i k c t P ,),(i k c t P 和),(i k c t P 以及)|(i k c t P 和)|(i k c t P 都可以类似定义和估算;)(x φ是标准正态分布的概率函数并指定0005.0),0005.0()(11≤=--x x φφ.表中所给出的形式都是TEF 的局部定义的,为了得到t k 的某些全局TEF 值,可以使用求和∑=C ),()(i k k sum c t f t f ,最大值)(max )(,1i k i k max c t f t f C ==或加权求和∑=C),()()(i k i k wsum c t f c P t f 等方式.比较性的工作中,Yang 的实验(没有考虑BNS )[49]发现IG 和χ2对LLSF 和k NN 分类方法最有效的,在不影响性能的情况下,可以去掉98%的项, #Tr (t k )居次,可以去掉90%的项,并且还发现三者有着非常强的关联.George 则从很多不同的方面评价了TEF [50], 证实IG 和χ2对准确性的同时失效,并且发现BNS 效果在很多方面超过IG .过滤方法也是有缺陷的,例如多分类问题中一些类中过剩的强预测性项可能会使IG 和χ2等TEF 忽略其他类中的特征项,从而使评估效果下降, George 通过一种轮换(round robin)调整的方式来解决[55].3.2.2 项提取给定一个确定的T '<<T ,项抽取试图通过对T 中的项进行组合或变换产生一个合成项集合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 过滤)组合成为一个携带类别信息6 Journal of Software 软件学报 2005,16(6) 较多的项的结构.为了将文档的表示向量压缩到一个更低的维数,对由初始的文本表示向量组成的矩阵进行奇异值分解,将初始向量映射成一个新的紧凑的向量.LSI 取得了一些比较好的结果,主要工作集中在[42, 60, 61]. 4 分类方法分类方法指如何根据给定的Φ 在C ⨯Ω上的取值归纳出分类器Φ的内部构成,由第1.1小节关于RTC 的叙述,对某些分类方法,仅讨论CSV i 的选取即可.4.1 概率方法基于概率的分类器中, CSV i (d j )的取值总是与条件概率P (c i |d j )有关,即文本d j 属于类别c i 的概率.通常通过Bayes 理论来估算: ∑===C 1)|()()|()()()|()()|(i ij i i j i j i j i j i c d P c P c d P c P d P c d P c P d c P . 较大的T 给估计使估计P (d j |c i )变得困难,因此需要如下假设:任意文本中的两个项的出现,当被看作是随机变量时是相互独立的,此假设可以用下面的公式刻画(其中j k d t ∈表示项t k 在d j 中出现):∏∈=j k d t i k i j c t P c d P )|()|(.大多数基于概率的分类器使用类似的假设[30, 42, 62],均称为Naïve Bayes 分类器,因为在实际中,此假设并不被验证是否严格成立.P (c i )可以用下式估计; TrT c d Tr d c g c P i j j i Tr i }),(|{)()(=Φ∈== . 使用Laplace 估计来计算P (t k | c i ): ∑=++=T T 1),(),(1)|(k i k i k i k c t tf c t tf c t P , 其中∑∈=Φ=Tr d Trc d j k i k j i j d t c t tf ),(),(#),( ,表示t k 在所有的c i 类文本中出现的次数之和.最后,用于估计P (c i | d j )的公式为: ∑∏∏=∈∈=C 1),(),()|()()|()()|(i d t c t tf i k i d t c t tf i k i j i j k i k jk i k c t P c P c t P c P d c PNaïve Bayes 方法是机器学习中的重要方法,概率模型有所差异,如多变元Bernoulli 模型和多项式模,文献[63]是两者的一个很好的比较.4.2 线性方法类别c i 的线性分类器的主要构成是一个称为c i 的模板(profile)的向量>=<i i i w w c T ,...1 ,它与所有的文本表示向量处于相同T 维空间.对于文本d j ,取CSV i (d j )为向量j d 和i c 间的夹角的余弦值,称为余弦相似性或余弦距离,即 ∑∑∑====T T T 12121)(k kj k ki k kj ki j i w w w w d CSV . 线性分类器主要通过在线(on line)方法和批(batch)方法计算i c .4.2.1 在线方法在线方法在检查完第一个训练样本后即生成一个分类器,在新的训练样本到来时不断地改进分类器.最简单地在线方法是感知器(perceptron)算法[],它首先通过将所有的ki w 置为相同的正数而得到c i 的分类器,当新的训练样本d j (以二值权重向量j d 表示)来到时,用此分类器进行分类,如果分类正确,则检查下一个训练样本.否则,如果d j 是c i 的正例,则α+=ki ki w w (对于所有的k 使得w kj =1);如果d j 是c i 的正例,则α-=ki ki w w (对于所张博锋 等:基于机器学习的文本分类研究综述 7 有的k 使得w kj =1),其中α>0是常数.另外一个著名的在线方法是Widrow-Hoff 算法:它的目标是检查完第l 个样本后,求得i c ,使得平方误差21]))],([[(i j l j j T i c d d c Φ-∑= 最小.关于在线方法的研究集中在[][].4.2.2 Rocchio 方法 Rocchio 方法是最著名,研究最多的批方法.为了计算每个分类c i 的模板>=<i i i w w c T ,...1 ,使用下面的公式: ∑∑∈∈⋅-⋅=}{}{i j i j NEG d i kj POS d i kj ki NEG w POS w w γβ,其中}),(|{T c d Tr d POS i j j i =Φ∈= 且}),(|{F c d Tr d NEG i j j i =Φ∈= ,w kj 是项t k 在文本d j 中的权重.公式中β和γ是两个可调的参数.一般来说,反例不应过分强调,故β的取值较大而γ取值较小[].Rocchio 方法非常易于实现,但性能上的缺陷在于如果一个分类包含了两个不相交的领域(即可能同一类文本的主题比较分散),整个类别的模板就会偏离每个领域的模板,导致分类会做出错误的决策.实际上,Rocchio 方法产生的分类器和所有线性分类器一样,是将文本向量空间线性地划分,这是一个重要缺陷.Rocchio 方法简单且训练速度非常快,而联合其他方面的技术后也获得了巨大的性能提升,甚至性能不弱于一些较好的方法,因此近来又引起很多学者的兴趣. Ruiz 等在计算中取 ∑∑∈∈⋅-⋅=}{}{ij i j NPOS d i kj POS d i kj ki NPOS w POS w w γβ, 其中NPOS i 是接近正例(near positive)的反例[43, 46, 64, 65].这是因为在反例中,只有那些接近正例的反例样本对分类器的影响最大,这也带来一个NPOS i 的选取问题;Tsay 等先通过普通Rocchio 方法计算出所有分类的模板,用这些模板在Tr 上进行一次分类,然后将所有分到同一类的文档按一定标准划分为s 个子类,共得到|C |·s 个子类,在这些子类中再应用Rocchio 方法进行分类[66].4.3 决策树与决策规则方法TC 决策树(decision tree, DT)的内节点(internal node)被标定为项,从内节点出发的分枝标以测试文本中所含有的项的权重标定,分类作为它的叶子.这种分类器通过递归地测试向量j d 中所含项在决策树中相应内节点的权重来分类文档d j .通常这类分类器都使用二值索引,从而形成了二叉决策树.决策树的学习包括两个步骤:(1)树的归纳,即从训练集Tr 中归纳出一棵树,通常对每个分类c i ,通过是否包含相通同项t k (项的选择使用IG 或熵标准[])的准则递归地分割训练集,最终使得文本均有关于同一个类别的标号(c i 或i c ),这是一种分制策略的典型应用;(2)树的剪枝,去掉训练集上的任何统计相关性,使树更加简练和强壮.有很多DT 学习的软件包可用,最著名的如ID3,此外还有C4.5,C5等.DT 分类器常被作为基准(base-line)分类器.c i 的决策规则分类器包含前提为一个DNF(disjunctive conditional form)的条件规则.前提中的文字指示了一个关键词在文档d j 中的出现或不出现,结论则指示了在c i 下分类d j 的决策.与DT 类似,DNF 规则也可以对二值函数进行编码,但其优点在于可以生成更加紧凑的学习机.规则的学习方法试图从所有的规则中以某种最小原则挑选出最紧凑的规则.与DT 的分制策略不同,DNF 规则使用自底向上的方式生成.最初,每个样本文件d j 可以被认为是一个短句i n γηη→,...,1,其中n ηη,...,1是d j 中所含的项,γi 根据d j 是否属于分类c i 而等于c i 或i c ;学习过程使用泛化(generalization)步骤,使得规则通过一系列修改(例如去掉一些前提或合并短句)而简化,这种修改使得规则具有最大的紧凑性但不影响规则的能力;最后使用类似于DT 中的剪枝过程.用于文本分类的学习机如Charade[],DL-ESC[],SCAR[]等.4.4 回归方法在回归方法中,利用已知的函数值来估计未知的函数值,[]使用了线性最小方差拟合(LLSF).在LLSF 中,每一个文本d j 有两个向量和它关联T 维的权重向量j d 和|C |维的类的权重向量O (d j ) (对于训练数据是二值的,而对于测试数据就未必是二值,每个分量可作为CSV i (d j )的值).这样,分类器的归纳过程可以转化为一个计算一个C ×T 的矩阵M ˆ,使得)(ˆj j d d O M = 的问题.LLSF 通过最小方差拟和来使得在训练集上的误差最小,即O MD M M -=min arg ˆ,其中()Tr d d ,...,1=D 是T ×Tr 阶矩阵, ())(),...,(1Tr d O d O =O 是C ×Tr 阶矩阵,对C ×T 阶矩阵V ,∑∑==C T 12i ijdef v V .M ˆ通常通过在训练集上进行奇异值分解得到,其每一个分量ik m ˆ代表了项t k 与类别c i 的关联程度.。
