根据机器知识学习的文本分类技术研究进展苏金树.pdf

《根据机器知识学习的文本分类技术研究进展苏金树.pdf》由会员分享，可在线阅读，更多相关《根据机器知识学习的文本分类技术研究进展苏金树.pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 ISSN 1000-9825, CODEN RUXUEW E-mail: Journal of Software, Vol.17, No.9, September 2006, pp.18481859 DOI: 10.1360/jos171848 Tel/Fax: +86-10-62562563 2006 by Journal of Software. All rights reserved. 基于机器学习的文本分类技术研究进展 苏金树 1, 张博锋 1+, 徐 昕 1,2 1(国防科学技术大学 计算机学院,湖南 长沙 410073) 2(国防科学技术大学 机电工程与自动化学院,湖南 长沙 4

2、10073) Advances in Machine Learning Based Text Categorization SU Jin-Shu1, ZHANG Bo-Feng1+, XU Xin1,2 1(School of Computer, National University of Defense Technology, Changsha 410073, China) 2(School of Mechantronics Engineering and Automation, National University of Defense Technology, Changsha 410

3、073, China) + Corresponding author: Phn: +86-731-4513504, E-mail: Su JS, Zhang BF, Xu X. Advances in machine learning based text categorization. Journal of Software, 2006,17(9):1848 1859. Abstract: In recent years, there have been extensive studies and rapid progresses in automatic text categorizati

4、on, which is one of the hotspots and key techniques in the information retrieval and data mining field. Highlighting the state-of-art challenging issues and research trends for content information processing of Internet and other complex applications, this paper presents a survey on the up-to-date d

5、evelopment in text categorization based on machine learning, including model, algorithm and evaluation. It is pointed out that problems such as nonlinearity, skewed data distribution, labeling bottleneck, hierarchical categorization, scalability of algorithms and categorization of Web pages are the

6、key problems to the study of text categorization. Possible solutions to these problems are also discussed respectively. Finally, some future directions of research are given. Key words: automatic text categorization; machine learning; dimensionality reduction; kernel method; unlabeled data set; skew

7、ed data set; hierarchical categorization; large-scale text categorization; Web page categorization 摘 要: 文本自动分类是信息检索与数据挖掘领域的研究热点与核心技术,近年来得到了广泛的关注和快速 的发展.提出了基于机器学习的文本分类技术所面临的互联网内容信息处理等复杂应用的挑战,从模型、 算法和 评测等方面对其研究进展进行综述评论.认为非线性、数据集偏斜、标注瓶颈、多层分类、算法的扩展性及 Web 页分类等问题是目前文本分类研究的关键问题,并讨论了这些问题可能采取的方法.最后对研究的方向进 行了

8、展望. 关键词: 自动文本分类;机器学习;降维;核方法;未标注集;偏斜数据集;分级分类;大规模文本分类;Web 页分类 中图法分类号: TP181 文献标识码: A Supported by the National Natural Science Foundation of China under Grant Nos.90604006, 60303012 (国家自然科学基金); the National Research Foundation for the Doctoral Program of Higher Education of China under Grant No.200499

9、98027 (国家教育部高校博 士点基金) Received 2005-12-15; Accepted 2006-04-03 苏金树 等:基于机器学习的文本分类技术研究进展 1849 随着信息技术的发展,互联网数据及资源呈现海量特征.为了有效地管理和利用这些分布的海量信息,基于 内容的信息检索和数据挖掘逐渐成为备受关注的领域.其中,文本分类(text categorization,简称 TC)技术是信息 检索和文本挖掘的重要基础,其主要任务是在预先给定的类别标记(label)集合下,根据文本内容判定它的类别. 文本分类在自然语言处理与理解、信息组织与管理、内容信息过滤等领域都有着广泛的应用.2

10、0 世纪 90 年代 逐渐成熟的基于机器学习的文本分类方法,更注重分类器的模型自动挖掘和生成及动态优化能力,在分类效果 和灵活性上都比之前基于知识工程和专家系统的文本分类模式有所突破,成为相关领域研究和应用的经典 范例1. 基于机器学习文本分类的基础技术由文本的表示(representation)、 分类方法及效果(effectiveness)评估 3 部 分组成.Sebastiani 在文献1中对文本分类发展历程及当时的技术进行了总结,主要内容包括:(1) 文本关于项 (term)或特征的向量空间表示模型(VSM)及特征选择(selection)与特征提取(extraction)两种表示空间

11、降维 (dimensionality reduction)策略,讨论了 2,IG,MI,OR 等用于特征过滤的显著性统计量及项聚类和隐含语义索引 (LSI)等特征提取方法;(2) 当时较成熟的分类模型方法,即分类器的归纳构造(inductive construction)或模型的 挖掘学习过程;(3) 分类效果评估指标,如正确率(precision)、召回率(recall)、均衡点(BEP)、F(常用 F1)和精度 (accuracy)等,以及之前报道的在 Reuters 等基准语料上的效果参考比较. 然而,互联网中分布传播的海量电子化文本所显现出的种类多样、分布偏斜、关系复杂、更新频繁及标注

12、 困难等新的特征,给近年来面向互联网海量信息处理需求的文本分类带来了巨大挑战.文献1对分类技术用于 解决上述问题时在不同程度上遇到的扩展性差、 语料缺乏及精度降低等困难和问题的论述不够,也无法涉及近 几年技术的发展以及信息检索、机器学习和数据挖掘等领域权威学术会议及刊物上讨论的重要问题和成果. 本文介绍基于机器学习文本分类技术的最新研究,重点讨论文本分类在互联网信息处理等实际应用中所 面临的问题及进展,从相关问题、现状和趋势等方面进行归纳和评论.第 1 节介绍基础技术的研究动态.第 2 节 讨论现阶段文本分类面向实际应用挑战的主要研究问题及最新进展.最后给出全文的总结和相关技术的展望. 1 文

13、本分类基础技术研究动态 近年来,将文本简化为所谓的 BOW(bag of words),在特征处理和统计学习算法的基础上获得对文本语义内 容及类别信息的估计与预测,已经成为文本分类的标准模式.通过统计理论和语言学(linguistics)两种途径进行 的文本表示和分类模型的研究也得到进一步拓宽或发展,相关领域的技术也在文本分类中得到新的应用. 1.1 文本表示 VSM 仍是文本表示的主要方法,相关研究仍然集中在以什么语义单元作为项及计算项的权重两个问题上. 大部分工作仍以词(或n-gram)作为项,以项的频率为基础计算权重,如tfidf等1.值得注意的是,Debole提出了有 监督的权重 ST

14、W,利用项的显著性统计量(如用 2等)来平衡其权重2;文献3,4等也使用类似的方法.相对使用 tfidf 权重,某些统计量的引入使得 SVM 及线性分类等方法的分类效果有了不同程度的提高. 除 VSM 以外,还有人提出基于项概率分布、 基于二维视图等模型.Bigi 认为,任意文本 d 和类别 c 均可视为 所有项的一个概率分布 P(ti,d)和 P(ti,c),i=1,|T T |( T T 为所有项或特征的集合),称为项分布概率表示.通过度量分 布间的 Kullback-Leibler 距离(KLD)相似性的分类方法,获得优于 VSM 表示下线性方法的效果5.项分布概率模 型本质上仅是在项的

15、权重计算和规格化(normalization)上与 VSM 不同.Nunzio 使用可视的二维表示方法,将所 有项的信息压缩到由局部能量和全局能量构成的二维平面上,采用启发式算法进一步计算后,在某些测试集上 得到了很高的准确性6;然而,方法仅是在小数据集上进行了测试,实际应用效果还需要进一步加以验证. 还有一些工作希望通过借鉴自然语言处理的技术考虑被 BOW 忽略的语义单元间的联系,因此,词义及短 语等复杂的项被应用到分类方法的文本表示中.但到目前为止,这些表示方法在分类效果上还没有明显的优势, 而且往往需要比较复杂的语言预处理,在分类时影响了分类器的吞吐速度7,8.到目前为止,非 VSM 的

16、表示在理 论上的合理性及面对实际应用的可扩展性还需要深入验证,适合它们的分类方法比较单一,而且未得到广泛的 应用. 1850 Journal of Software 软件学报 Vol.17, No.9, September 2006 1.2 表示空间降维 相关研究主要集中在降维的模型算法与比较,特征集与分类效果的关系,以及降维的幅度 3 个方面. 关于降维的模型和算法,很多研究仍按照传统的思路:(1) 用概率统计方法度量并比较项关于类别分布的 显著性,如 BNS(bi-normal separation)9等;(2) 从信息熵角度研究项分布相似性的项聚类方法,如基于全局信息 (GI)10等;(

17、3) 隐含语义分析途径,即通过矩阵的不同分解和化简来获取将向量语义或统计信息向低维空间压 缩的线性映射,如差量(differential)LSI11,12等.一些新颖的研究思路包括:(1) 多步骤或组合的选择方法,即首先 用基本的特征选择方法确定初始的特征集,然后以某种标准(如考虑其他项与初始集特征的同现(co-occurrence) 等13)进行特征的补充,或者综合其他因素(如依第 2 种显著性选择标准13,14或考虑线性分类器系数值大小15 等)进行冗余特征的删减;(2) 尝试借鉴语言学技术进行的研究有从手工输入的特征中学习特征信息16及基于 WordNet17的特征提取等方法,但方法所产

18、生的效果都不理想. 必须考虑降维对分类的影响,即关注分类器效果指标随特征数目增加的变化趋势.很多文献中914,18,19比 较一致的现象是:合理的降维方法会使多数分类器都呈现出随特征数量增加,效果快速提高并能迅速接近平稳; 但若特征数目过大,性能反而可能出现缓慢降低.这表明:降维不仅能大量降低处理开销,而且在很多情况下可 以改善分类器的效果.Forman 及 Yang 等人分别从有效性、区分能力及获得最好效果的机会等方面对不同的特 征选择方法进行了广泛比较.从结果来看:BNS,2,IG 等统计量及组合方法具有一定的优势;另外,不同分类器倾 向于接受不同的特定降维方法9,13,18,19.常用的

19、特征提取与特征选择算法的效果在不同情况下互有高低或相 当1,10,20.虽然选择方法因为复杂度较低而应用更为广泛,但提取得到的特征更接近文本的语义描述,因此有很 大的研究价值. 降维尺度的确定常用经验估算方法,如给定特征数的经验值(PFC)或比例(THR);或者考虑统计量阈值 (MVS)或向量空间稀疏性(SPA)等因素.Soucy 给出特征数与文本数成比例(PCS)的方法,并在精度标准下与其他 4 种方法做了比较,得出了 MVSPCSSPAPFCTHR 的结论21,传统的标准值得重新审视. 1.3 机器学习分类方法 分类方法研究的主要目标是提高分类效果,实用的系统还必须兼顾存储和计算能力受限等

20、条件下,学习过 程的可扩展性和分类过程的吞吐率(速度)2224.近年来,采用多(multiple)分类器集成学习(ensemble learning)的 方法被普遍接受;而支持向量机(SVM)仍然代表了单重(single)方法的发展水平. SVM 的应用是文本分类近年来最重要的进展之一.虽然 SVM 在大数据集上的训练收敛速度较慢,需要大 量的存储资源和很高的计算能力2428,但它的分隔面模式有效地克服了样本分布、冗余特征以及过拟合 (over-fitting)等因素的影响,具有很好的泛化(generalization)能力.有关文献的比较均显示:相对于其他所有方 法,SVM 占有效果和稳定性

21、上的优势2832.近年来又有很多文献1中未涉及的一些模型或方法被提出或应用, 有的还获得了较好效果,如最大熵模型33,34、模糊理论35,36、项概率分布的 KLD 相似性5、二维文本模型6 以及基于等效半径的方法(SECTILE)26等(见表 1),但它们仍局限于惯用的相似性度量的分类模式. Bayes、线性分类、决策树及 k-NN 等方法的能力相对较弱,但它们的模型简单,效率较高,这些方法的修正 和改进引起了人们持续的关注.Wu 指出分类器关于数据分布的假设是影响分类效果的重要因素,当模型不适 合数据集特点时,性能就可能变得很糟糕.这种模型偏差在弱分类方法中尤为突出,他给出了一种灵活的基于

22、错 误矫正的启发式改进策略25;GIS 方法将样本聚集成不同的实例集(instance set),每个实例集的质心称为推广实 例(GI),以 GI 的集合代替样本集合后减少了实例,使得 k-NN 方法的在线速度大为改善,分类效果也有所提 高37;Tsay 利用与 GIS 相反的思路,他增加类别的数目,实质上为原类别选择多个质心,部分地克服了单个质心 难以适应样本稀疏的弱点38;Tan 使用推拉(drag-pushing)策略对 Bayes 和基于质心的方法进行了改 进39;Chakrabarti 的 SIMPL 方法利用 Fisher 线性判别分析将文本表示投影到低维空间后,再进行决策树的构

23、造24.可以看出,多数分类模型和方法的研究,更侧重在特定测试集上效果基本相当的情况下,获得计算开销上 相对 SVM 的优势. 苏金树 等:基于机器学习的文本分类技术研究进展 1851 集成学习,也称为多重学习或分类器组合,主要通过决策优化(decision optimization)或覆盖优化(coverage optimization)两种手段将若干弱分类器的能力进行综合,以优化分类系统的总体性能.决策优化对于不同的分类 器均采用完整的样本集进行训练,测试时,通过对所有分类器的决策进行投票或评价(如 MV(majority voting),W (weighted)MV 及 WLC (weig

24、hted linear combination)等1,40),确定整个系统输出的类别;Bennett 将特定分类器看 作可靠性的指示(reliability indicator);系统利用概率方法综合不同分类器的输出确定最后的决策41;Xu 和 Zhang提出一种将 SVM与Rocchio算法进行串行集成方法的思想,即在Rocchio算法快速处理全部文本向量后, SVM 对部分感兴趣的类别进行误差校正,用较低的计算代价换取重要类别的精度42;覆盖优化对同一种学习采 用不同的训练子集,形成参数不同的单分类器,这些单分类器决策的某种综合(如WMV等)决定每测试样本的分 类,如 Bagging 和

25、Boosting 等方法43;在 Boosting 方法的迭代过程中,每一轮都关注上一轮的分类错误,用于提升 较弱的分类方法并获得了优于 SVM 的结果,AdaBoost.MH 和 AdaBoost.MR 等具体算法都有着广泛的应用44. Table 1 Properties and effectiveness for most of the categorization models or methods 表 1 主要分类模型或方法的性质和效果 Model or method Examples of algorithm or Implementation CR HD Bi Best rept

26、 eff. Remark Probabilistic Nave Bayes (NB) 0.773 Easy, highly depend on data distribution Decision tree (DT) ID3, C4.5, CART 0.794 Decision rule DL-ESC, SCAR, Ripper, Swap-1 0.823 Often used as base-lines, relatively weak Regression LLSF, LR, RR45 0.849 Effective but computing costly On-Line Winnow,

27、 Windrow-Hoff, etc. 0.822 Linear Centroid-Based Rocchio (and its enhancements) 0.799 Weaker but simple and efficient Neural networks Perceptron, Classi, Nnet 0.838 Not widely used TC Instance-Based k-NN 0.856 Inefficient in online classification SVM SVMlight, LibSVM46,47 0.920 State of arts effectiv

28、eness MV, Bagging N/A Not widely used and tested yet Ensemble learning WLC, DCS, ACC, adaboost 0.878 Boosting methods effective and popular STRIVE41 0.875 Complex in classifier construction Ensemble learning SVM with Rocchio ensemble42 +0.019* *Improvement in a small Chinese corpus Maximum entropy L

29、i. KAZAMA33,34 0.845 Effective but not widely used Fuzzy Liu, Widyantoro35,36 0.892* *Only accuracy reported Term prob. distri. KLD based5 0.671* *Better than Rocchio in the same test Bidimensional Heuristic approach6 0.871 Not extensively confirmed MD and ER based SECTILE26 0.950* *Onlytested in a

30、Chinese corpus, estimated Wus Refinement Rocchio/NB refined25 0.9/0.926 A little complex in training Tsays refinement Rocchio refined38 +0.018* *Improvement, a Chinese corpus Gener. instance set GIS-R GIE-W37 0.860 More efficient than k-NN in testing Dragpushing RCC, RNB27,39 0.859 Easy and computat

31、ionally efficient Linear discri. proj. SIMPL24 0.880* *Estimated form reported data LS kernel48 With SVM 0.903 Need expensive matrix processing Word seq. kernel49 With SVM 0.915 Complex and time spending in training String kernel50,51 With SVM 0.861* *Estimated form reported data 表1中数字角标表示的是: 模型方法;

32、算法实例或实现; 是否class ranking方法(输出测试文本关 于每个类的相对形似性参考值或排序); 是否 hard-decision 方法(输出测试文本的类别标记); 是否是二值 (binary)方法(方法接受或拒绝当前类,输出1); (reuters-21578 子集上)报道的最好分类效果(平均的 BEP,F1 或精度值,测试条件不同,结果仅供参考); 评注.表 1 的前两部分给出了上述以及文献1中涉及的部分方法的 主要特征及其在 Reuters-21578 某些子集上(或个别其他语料)上所报道的最好效果指标(平均的 BEP,F1或精度 值).由于测试集合和测试条件的差异,指标的数值

33、仅作为方法效果的参考,不能完全作为方法效果间比较的 依据. 1852 Journal of Software 软件学报 Vol.17, No.9, September 2006 1.4 评估方法 信号检测领域中的 ROC(receiver operating characteristics)曲线,近年来介入到对分类器的效果评估和优 化41,5254中.对类别 c,表 2 是其测试结果的邻接表.设 TPR=TP/(TP+FN),FRP=FP/(FP+TN),随着分类器阈值参数 的调整,ROC 空间(TPR,FPR)中的曲线不但能直观地反映分类器的性能,曲线下面积 AUC(area under c

34、urve)更可 以量化分类器接受正例的倾向性.另外,ROC 空间对样本在类别间的分布不敏感,可以反映错误代价(error cost) 等指标的变化,具有特别的优势52.有效地将 ROC 曲线用于分类器的评价、比较及优化,成为近期的一个热点. Table 2 The contingency table for category c 表 2 类别 c 测试结果邻接表 Expert judgments Category c True False PositiveTP FP Classifier judgments NegativeFN TN 在理论方面,Li 和 Yang 认为关于训练数据的误差及复

35、杂性惩罚使分类器能力间的比较明朗化.通过对常见 分类方法进行形式化分析,他们将与分类器获得最优效果条件和标准等价的损失函数(loss function)分为训练 损失(training loss)和模型复杂度两部分,从优化的角度给出了一种分类器之间相互比较的方法45. 方法间的实验比较常在基准语料上进行.Reuters 是重要的基准语料,其中在 Reuters-2157855版本上进行了 最多的测试.常见的语料还包括 OHSUMED,20 Newsgroups,WebKB 及 AP 等1,39.文献28给出了 Reuters-21578 子集的相对难度分析和参考.RCV1(reuters co

36、rpus volume I)是最新整理和发布的较完全的“官方”语料,它改进 了之前语料的一些缺点,以适应多层分类、数据偏斜及分类方法扩展性等研究的需要.语料的构建对文本分类 研究有着非常重要的促进和参考作用,文献31给出了RCV1的语料加工技术及部分方法的参考性能.中文分类 的公开语料大多处于建设中,特别是经过加工的基准语料相对缺乏,Tan 公开了一个较新的加工中文分类语料 TanCorp 及一些分类方法的参考性能39. 2 主要挑战和研究进展 基于机器学习的文本分类技术经过 20 多年的不断发展,特别是直接从机器学习等领域借鉴最新的研究成 果,已能较好地解决大部分具有数据量相对较小、标注比较

37、完整及数据分布相对均匀等特点的问题和应用.但 是,自动文本分类技术的大规模应用仍受到很多问题的困扰,如:单是刻画文本间(非线性的)语义联系的问题,都 被认为没有很好地得以解决.近年来面临的主要挑战来自于互联网上 Web 等海量信息的处理,其主要特征 是:(1) 大规模的类别体系给分类器训练带来扩展性的困难;(2) 建立分类器时所获得的样本相对于海量的未知 数据非常有限,模拟样本的空间分布变得困难,这可能带来过拟合(overfitting)及数据偏斜的问题;(3) 文本和类 别的更新频繁,在力求对每个类别获得更多的样本时,存在标注瓶颈的问题;(4) 类别间的关系也更加复杂,需要 有更好的类别组织

38、方法;(5) Web文本是一种半结构化(semi-structured)的数据,其结构信息(如链接关系、 主题等) 可能对分类提供某些帮助.综合来看,我们认为文本分类技术现阶段主要面临非线性、数据集偏斜、标注瓶颈、 多层分类、算法的规模扩展性及 Web 页面分类等几个关键的问题.下面主要论述解决这些关键问题可能采取 的方法. 2.1 非线性问题及核方法 多数文本分类问题的线性可分性29并未得到理论上的证明,用线性的模型表达复杂的语义内容必然会带 来许多误差,非线性的方法仍是处理复杂问题的重要手段.SVM 方法用二元核函数 K(x,y)计算高维空间 H H 中的 内积(x,y 是文本表示向量)2

39、9,以应对(降维后的)项空间上不可分的文本分类问题,表达了模型中的非线性变 换.SVM是使用核方法(kernel method)或者核技术(kernel trick)的典型代表,核方法也是SVM取得成功的主要因 素之一. 苏金树 等:基于机器学习的文本分类技术研究进展 1853 在核方法中,通过较复杂的非线性映射将项空间的非线性问题变换到高维特征空间 H H,就有可能在 H H 中运 用线性方法,使问题便于处理和建模;事实上,的显式构造可能未知或很复杂,但求解过程中却只需利用显式的 核函数 K 简单计算 H H 中的内积,使得复杂的非线性变换在计算上可行56.目前,核方法在机器学习领域炙手可

40、热,成为在已有线性算法基础上研究非线性问题的重要途径,如 Zaragoza 将核技巧运用到线性文本分类方法中, 此时,仅需将线性决策函数中的内积用核函数 K 进行替换,得到 = = | 1 | 1 )(),(),()( TrTr i ii i iiK fxxxxx, 其中:Tr 是训练样本集合;xi是训练样本的表示(i=1,|Tr|);x 是待测样本的表示57. 进一步的研究表明:核方法的效果与核函数的选择密切相关,总是希望它能反映样本相似性的本质.常见的 核函数有 RBF,Gauss 及 sigmoid 核等29.在文本分类中,由于文本空间的特殊性,采用数值核函数获得的分类性 能还不能令人满

41、意.因此,新的基于文本语义的核函数成为一个研究重点.文献48讨论了基于矩阵分解的隐含 语义(LS)核函数;文献4951中使用语法驱动的字符串核及词序列(word sequence)核,直接将文本作为字或词 的有序串来计算核;文献58讨论了核函数的合成对分类的影响,给出了能够提高分类效果的某些合成条件.核 方法的本质是通过核函数引入文本语义相似性的度量,常具有很高的分类准确性(见表 1),但计算开销也较高. 2.2 数据集偏斜 通过对机器学习领域的很多研究,发现数据集关于类别的分布往往是偏斜(skewed)或称不均衡的,即类别 间样本的数量可能存在数量级的差距,这是导致分类效果很不理想的一个重要

42、因素.在数据偏斜的情况下,样本 无法准确反映整个空间的数据分布,分类器容易被大类淹没而忽略小类.在文本分类特别是互联网信息的分类 中,大量存在数据偏斜的情况.尤其是在采用二值分类策略时,对某一类,正例的样本可能只占所有样本比例很 小的一部分59.Yang 进行了 SVM,NB 及 k-NN 等方法在样本分布受控情况下的健壮性及分类效果与数据分布 之间关系的对比30,结果表明:SVM 和 k-NN 对样本分布的健壮性要好于 NB 等方法,这印证了 SVM 的泛化性 能及 NB 对类别先验概率的依赖性,但所有方法在稀有类别上的准确性均很低. 解决数据偏斜问题的主要对策有:(1) 重取样(re-sa

43、mpling),可以适当屏蔽大类的信息量或提高小类的分类 错误代价60;(2) 采用新的分类策略,如单类(one-class)SVM 以原点作为未知类别的中心,构造包围训练样本的 分隔面,从而将问题转化为等价的不受类别分布影响的两类问题61;文献62讨论了在仅有少量正例情况下 SVM 的训练;文献63中提出的 NKNN 方法改进了 k-NN 在偏斜数据集上的效果;(3) 采用更好的效果评估方 法,如 ROC 曲线或代价曲线等在数据偏斜情况下能够更准确地评估分类器的整体性能52,59;(4) 在数据偏斜的 情况下,特征也很重要,可以分别通过优化特征选择框架或改进特征选择方法获得分类器对小类别特征

44、的重 视9,6466.目前,所有的方法都还不能将对稀有类别的识别水平(约 0.5 左右或更低的 BEP)整体提高到实际可以 接受的程度,相关的研究仍需要进一步的深入. 2.3 标注瓶颈 学习算法需要大量的标注样本,但已标注的样本所能提供的信息有限;另一方面,容易获得(如通过互联网) 的未标注样本数量相对于标注样本较多,且更接近整个样本空间上的数据分布.提供尽可能多的标注样本需要 艰苦而缓慢的手工劳动,制约了整个系统的构建,这就产生了一个标注瓶颈的问题.因此,如何用少量的已标注 样本和大量的未标注样本训练出一个好分类器,逐渐引起人们的关注.Nigam 首先利用基于期望最大化(EM)的 方法从未标

45、注样本中学习,利用测试样本改进了 Bayes 分类器的分类效果67;另一种用于未标注文本学习的方 法是直推(transductive inference),使得分类器首先通过对已标注样本的学习仅对当前的少量未知样本进行误差 最小的预测,而暂不考虑对未来所有实例预期性能的最优性.之后,将这些样本加入到学习过程中来,以改进分 类器的效果;Jaochims 使用了直推式支持向量机 TSVM 进行文本分类68,文献69中进行了改进;文献70中讨 论了直推式 Boosting 文本分类;文献71,72采用合作训练(co-training)的方法,使用未标注的样本进行 e-mail 与 文本的分类,其思想

46、是从两个视角将样本的特征划分为两个信息充足的子集,分别在两个子集上建立分类器,利 用标注样本进行合作学习.另外,文献73仅使用正例样本和未标注样本进行学习;文献74中利用了 SVM 主动 1854 Journal of Software 软件学报 Vol.17, No.9, September 2006 (active)学习.上述方法在标注样本较少的情况下对提高分类器的性能有很大的帮助(见表 3),虽然部分地缓解了 标注瓶颈问题,但也以大量迭代为代价.另外,不同的从未标注样本学习方法之间,还没有在同一标准下的比较 性工作. Table 3 Effectiveness of some learn

47、ing-from-unlabeled methods 表 3 一些从未标注样本学习方法的效果 Method/Competitor Data set Labeled/ Training set Unlabeled Effectiveness/ Effectiveness Remark 20/20 10000 0.36/0.21 20NG 500/500 10000 0.66/0.54 EM/NB67 4/4 2500 0.55/0.39 Accuracy, estimated from figures WebKB 9/9 3957 0.624/0.572 TSVM/SVM68 Ohsumed 1

48、20/120 10000 0.535/0.486 Macro-Average BEP TBoosting/Boosting70RWCP 100/100 1000 0.602/0.479 Macro-Average F1 Co-Train with SVM72N/A 9/9 1200 0.62/0.77 Accuracy, comparing with startup Active Learn/Inactive74Reuters-21578 22/22 978 0.46/0.69 Average BEP 2.4 多层分类 通常所讨论的分类问题中,类别间是孤立的,认为它们之间没有相互联系,称之为单

49、层(flat)分类.而在类别 较多且关系复杂的情况下,如互联网丰富的 Web 信息的管理等一大类应用,就需要更好的多层信息组织方式.多 层(hierarchical)分类是指多层类别关系下的分类问题7581,面对的类别间存在类似于树或有向非循环图的多层 分级类别结构,可以更好地支持浏览和查询,也使得部分规模较大的分类问题通过分治的方法得到更好的解决. 多层分类一般采用 big-bang 或自顶向下基于级别两种策略,前者在整个分类过程中使用同一个分类器,即 将处于类别树结构上的所有叶节点类别看成平等的类,这本质上还是一种单层分类,不能很好地应用类别间的 关系;后者可为不同的级别训练不同的分类器,枝节点的分类器只关心当前的不同分枝77.Sun 等人讨论了基于 类别相似度和类别距离的多层分类