基于支持向量的迭代修正质心文本分类算法

王德庆 张 辉

(北京航空航天大学软件开发环境国家重点实验室，北京100191)

文本分类(TC，Text Categorization)是一项将未标记的自然语言文本分配到事先定义的主题类别中的任务［1］.文本分类技术已经被广泛应用到在线新闻分类［1］、软件 bug分类［2］及垃圾邮件过滤等实际的应用中.由于语料的高维、稀疏等特点，特征选择也是文本分类的重要组成部分［1］.

基于质心的分类算法 (CC，Centroid-based Classification)由于其简单性、高效性等特点受到研究人员越来越多的关注，并且Han等人已经证明质心分类算法对于文本分类来说是一个有效的、鲁棒的分类模型［3］.质心分类算法的基本观点是利用属于同类的训练实例来构造一个类别的质心向量 (Centroid Vector)，然而传统CC的分类精度要明显地低于其他分类器，如支持向量机分类器(SVMs，Support Vector Machines)［4］.导致分类精度低的原因之一是质心向量的构造函数存在问题［5］.因此研究人员针对质心向量的构造或者修正提出了很多改进型的算法，例如Class Feature Centroid 分 类 器［5］、DragPushing［6－7］、基 于 Term Distribution 方 法［8］、Weight Adjustment 方 法［9］.这些改进型方法的性能要优于传统质心分类算法与k最近邻等，但与最好的SVMs仍存在一定的差距.

值得注意的是:不论传统的还是改进的质心分类算法，它们都是将全部的训练实例作为支持集.然而，这样极有可能引起过度拟合问题，并且影响到质心分类器的泛化能力，即越多的训练样本不一定得到越准确的分类模型［10］.同时，支持向量机的出现及其在文本领域的成功应用［11－12］，激发对传统算法的重新思考与改进.通过大量实验发现:选择“部分”的训练实例来构造质心向量可能有助于推导出更加准确的分类预测模型.

尽管文本分类中最优子集选择的理论还没有建立，但是存在很多可以用来识别边界实例的成熟技术.例如，SVMs具有完备的理论与数学基础，并且SVMs擅长区分一个训练实例是靠近类别边界还是类别中心.因而，联合SVMs和迭代修正策略研究并提出基于支持向量的迭代修正质心分类算法 (IACC_SV，Support-Vector-based Iteratively Adjusted Centroid Classifier).

1 质心分类算法的问题分析

在将质心分类算法应用到文本分类之前，每篇文档通常采用向量空间模型［13］进行表示，权重计算采用 tf-idf(termfrequencyandinverse document frequency)［14］的标准形式 ltc［15］，为了消除文本长度对于项权重的影响，需要对权重进行归一化处理.

与SVMs相比，质心分类算法更加的简单与高效.但是，质心分类算法同样存在着明显的缺点，即在实际的系统中其分类精度较低.如图1所示，类别A在特征空间中的分布要比类别B更加广.如果一个来自类别A的训练实例向量dA落在该类别的质心向量CA附近(如图1中dA左箭头所指实心圆所示)，那么dA很容易被正确分类.但是，如果dA落在类别A与B的边界MidLine(CA，CB)附近，则dA很容易被误分(如图1中右箭头所指实心圆所示).为了避免上述情况发生，一种可行的方式就是通过训练集误差(training-set error)来迭代修正质心向量，即从CA到C'A.基于这种思路出现了很多的研究文献［5－7，9］，并且改进的算法确实能够提高传统的质心分类算法的性能.然而，改进算法的性能仍然劣于最新的分类算法，如SVMs.这意味着仅仅通过迭代修正策略是不够的，还需采用其他的技术来进一步提高质心分类算法的效能.

图1 经典质心分类器误分样本的可视化示例

仔细观察图1，如果类别A的初始质心向量是C'A而不是CA，则将出现如下情况:即图1中类别A与B的分类边界由MidLine(CA，CB)变为MidLine(C'A，C'B)，更加靠近最优分类边界 OptimalMidline(虚线所示).但是，以C'A作为初始质心向量，必须选择“部分”的样本而不是全部样本来构造质心向量，这是本文的第1个研究动机.

问题1 在传统的质心分类器中，选择部分样本构造的质心向量要优于采用全部样本构造的质心向量吗?

问题1的答案很可能是肯定的，因为SVMs就是一个很好的例子.SVMs通过从训练集中选择出的支持向量构建的分类模型具有较高的模型泛化能力，完成较高的分类预测准确率.因此，需要研究的第2个问题随之而来.

问题2 如何准确地和自动地选择部分样本才能使得构造的质心向量能够完成比传统的质心向量更优的分类性能?

对于文本分类来说，文本训练集往往是高维度、稀疏的向量，想要找到2类之间明确的边界是很困难的.一种可行的方法是借助于著名的SVMs，因为SVMs中的支持向量就是在映射后的高维空间中处于类别边界的训练实例，与需要的边界实例是相似的.

2IACC_SV算法

IACC_SV算法具有2个重要特点:①IACC_SV算法只利用由SVMs发现的支持向量构造初始的质心向量;②最终的质心向量是通过训练集误差迭代修正获得.IACC_SV算法的具体描述如下:

在IACC_SV算法中，首先利用线性SVMs找到所有的支持向量SV(第1行);然后，利用支持向量构造每类的初始质心向量(第2行);第3～10行用来迭代修正质心向量，即用已有的质心向量来预测支持向量SV中的训练实例，如果实例被误分，则按照公式(1)和公式(2)来调整质心向量.

其中，d为类别Ci中的一个实例向量，但是被第l步迭代获得的质心向量C(l)i误分到类别Cj中，|Ci|为类别Ci中文本总数.迭代修正直到最大迭代次数m.为避免过度拟合，m默认设定为3.同时，为避免实例读入顺序对于质心的影响，采用随机无放回的方式读取样本d(第4行);最后，第11行返回最终的质心向量用于后续的分类预测过程.

IACC_SV算法中有2点特别值得注意:

1)边界实例的选择问题，对于多类问题，采用“1对1”策略来获得每个类别的边界实例;

2)质心向量的迭代修正问题，不同于Tan的DragPushing［6－7］，IACC_SV 算法每发现一个误分样本都要对质心向量进行修正，这样做的好处是减少了误分样本的数量，从而加快了迭代收敛的速度.

时间复杂度.IACC_SV算法的时间由2部分组成:第1部分为获得支持向量SV所需的时间;第2部分为迭代修正质心向量所需的时间，与|SV|成线性关系.因此IACC_SV算法训练时间近似于SVMs的训练时间.分类预测时间复杂度为O(|T|KW)，其中|T|为测试集T的样本总数，K为类别总数，W为单词总数.

3 实验环境

3.1 实验语料

实验语料共 8 个常用的文本数据集［1，5－7，12］，表1列出了所有数据集的基本信息，其中变异系数(CV，Coefficient of Variation)［16］的值越大，说明数据集越不均衡.

表1 8个文本语料集基本信息

Reuters-21578［17］根据“ModApte”划分得到单标签语料共9100篇文档，52个类别.通过停靠词过滤、词根还原等文档预处理，总的单词数是 27953.通过删除重复文档，20Newsgroup［18］得到18828个文档，训练集和测试集按2∶1的比例随机划分，最终的单词总数为178456.

从 Tmdata［15］中选取 oh0，wap，fbis，tr11，tr21和tr23共6个语料，其特征维数分别为3 182，8460，2000，6429，7902 及5832.在每次实验中，训练集与测试集按4∶1的比例随机划分［3］.对于Tmdata中的数据集，采用10次实验取平均值的方式获得宏平均F1(macro-F1)与微平均F1(micro-F1)［19］.

3.2 分 类 器

为了比较分类算法的性能，设计实现了一系列的分类器，分别是支持向量机(SVMs)［11－12，20］，加权 k 近邻(kNN)［21］，经典的质心算法(CC)［3］，批量更新的质心算法(BUCC)［6－7］，迭代修正质心(IACC)算法，基于支持向量的质心分类器 (CC_SV)，基于支持向量的迭代修正质心分类器(IACC_SV).其中SVMs分类器采用开源软件LIBSVM［22］实现，选择线性核函数，并使用 5-fold交叉验证获取最佳参数C;其余的分类器采用Java编程实现.对于 kNN 分类器，设定 k=10［3］.BUCC的参数“Learnrate”根据文献［6］中的建议设为0.5.CC_SV与IACC_SV都是采用支持向量作为算法的输入，除了后者采用迭代修正策略来调整质心向量.

4 实验结果与分析

4.1 支持向量的作用

为了验证支持向量在CC的积极作用，首先比较CC与CC_SV在8个数据集上的性能.图2展示了在macro-F1指标上的比较.很明显，在所有的8个数据集中，CC_SV在6个数据集上的性能要优于CC，仅有2个略劣于CC分类器 (tr21与tr11).在micro-F1指标上的比较结果如图3所示，再一次验证了支持向量在质心分类器中起到的积极作用.相比于传统的CC算法，通过使用支持向量作为质心分类算法的输入，CC_SV算法在Reuters-21578语料上的macro-F1与micro-F1分别提高4.3%和3.2%，而在20 Newsgroup语料上的提高分别是2.2%与2.4%.

图2 采用支持向量与采用全部样本的macro-F1比较图

图3 采用支持向量与采用全部样本的micro-F1比较图

进一步观察到在迭代修正质心分类中，支持向量的作用仍然是正面的.如图2与图3所示，IACC_SV在7个数据集上取得优于IACC算法的macro-F1和 micro-F1，除了 oh0.尽管 IACC_SV 提高的程度不如CC_SV和CC之间的明显.

总之，使用支持向量来构造质心向量确实能够提高质心分类算法的泛化能力，这也回答了前面提出的问题1，即在文本分类中计算初始质心向量时选择部分实例要优于选择全部实例.

4.2 迭代修正策略的作用

图4与图5显示了CC_SV与IACC_SV在macro-F1及micro-F1上的性能比较图，其中迭代次数m设为3.图中可见，IACC_SV算法在8个数据集上都要优于CC_SV算法.相比于CC_SV算法，IACC_SV算法在tr23语料库上将macro-F1提高了8%，在Reuters-21578，fbis及tr21提高了5%;而对于micro-F1，IACC_SV在5个数据集上相比于CC_SV算法提高了3%，分别是Reuters-21578，20 Newsgroup，fbis，tr21 与 tr23.值得注意的是，迭代修正策略也有助于经典的质心分类算法CC性能的提高.从图2和图3可知，IACC算法的性能要优于CC算法.这些结果说明，利用训练集误差来迭代修正质心向量的方法能够提高基于质心的分类器的性能和分类预测的准确率.

图4 CC_SV与IACC_SV在macro-F1上的比较图

图5 CC_SV与IACC_SV在micro-F1上的比较图

4.3 参数确定

IACC_SV算法中，质心向量的最大迭代次数，即参数m，是需要人为设定的.越大的m意味着更多的时间消耗并且有可能导致过度拟合.图6给出了 IACC_SV算法的准确率在Reuters-21578与fbis上随参数m递增的变化情况.可以看出，当m由0增加到1时，IACC_SV算法的准确率提高比较明显，然而当m＞1，分类器的性能提升就趋向于平稳.例如，在Reuters-21578数据集上，当m=3时，IACC_SV算法取得最高的准确率:93.6%，大约比CC_SV算法提高5.4%;当m＞3时，分类器的准确率的提高趋于平稳甚至降低.相似的结果同样发生在fbis语料集上.因此，在所有实验中，将参数m的值设定为3.

图6 最大迭代次数m对分类算法准确率的影响

4.4 与其他分类算法的比较

本节继续比较IACC_SV算法与其他分类算法的性能比较，表2列出了5种分类算法的macro-F1值.从表中可以看出，在8个语料集上，IACC_SV，SVMs，BUCC，CC 分别完成 6，2，1 与 1个最优macro-F1，而kNN没有取得最优结果.最优结果用粗体标出.

表2 5种分类算法的macro-F1比较

首先，8个语料集上，IACC_SV在7个语料集上的macro-F1值都高于SVMs分类器，除了20 Newsgroup，并且在某些语料集上IACC_SV算法的提高幅度很明显.例如，在不均衡的 Reuters-21578数据集上，IACC_SV算法较SVMs算法提高了6%，同样在不均衡tr21语料集上，提高幅度高达 8%，这种提高主要是基于 2个方面:①SVMs分类算法是一个全局最优的算法，它可能导致分类器对于稀有类别的严重误分;②macro-F1给每个类别赋予相同的权重，因而可以惩罚分类器在稀有类别上的分类错误率.

接下来，比较IACC_SV与BUCC的性能，两者的不同是BUCC采用全部训练实例作为算法输入并且其迭代修正的公式与IACC_SV算法略有不同，其迭代公式参见文献［6］.从表2中可知，IACC_SV算法在7个数据集上的macro-F1值高于BUCC算法，这也验证了使用训练实例的子集，比如支持向量，可以提高CC的分类准确率.

IACC_SV算法要明显地提高经典的CC算法的性能，特别是在 Reuters-21578，20Newsgroup，fbis，tr21及tr23等5个数据集上.例如，相比于经典的CC算法，IACC_SV算法在 tr23语料库上提高了10%，在 Reuters-21578语料库上提高了8.8%，在20Newsgroup，fbis及tr21等3个语料库上提高了5%.但是，IACC_SV算法在oh0上的性能与CC相同，这是由于迭代次数过多引起的过度拟合问题，如果将IACC_SV算法的迭代次数由3次变为1次，那么IACC_SV算法在上述语料集上的性能就高于CC算法.

最后，从表2最后一行可知，在平均macro-F1上，本文提出的IACC_SV算法在比SVMs，kNN，CC，BUCC 分别提高 2.7%，9%，4.6% 和 1.3%，因此IACC_SV算法优于其他的分类算法.

5种分类器的micro-F1值如表3所示，在所有的8个数据集上，IACC_SV，SVMs及CC分别完成了5，2及1个最好的结果.可以看到IACC_SV算法在 micro-F1指标上同样优于BUCC，CC及kNN等3种分类算法.然而，IACC_SV与SVMs在micro-F1指标上的比较不同于macro-F1指标，两者在micro-F1上的差异要小的多.这是因为micro-F1指标给每个测试实例的权重相同，而不考虑类别特性，这就抵消了算法在稀有类别上较差的结果.同时，当SVMs取得最优结果的时候，IACC_SV算法都取得了次优的结果.在平均micro-F1上，IACC_SV 算法在比 SVMs，kNN，CC，BUCC 分别提高 0.1%，7.1%，4.9%及 1.1%.因此在micro-F1上，IACC_SV算法略优于其他的分类算法.

表3 5种分类算法的micro-F1比较

在所有的分类算法中，kNN算法的性能最差，IACC_SV算法的分类准确率与著名的SVMs分类器相接近，并且IACC_SV算法在macro-F1指标上要明显地优于SVMs分类算法.因此，本文提出的IACC_SV分类算法借助于SVMs选择出具有代表性的训练实例，然后利用迭代修正策略来调整质心向量，新的算法在8个文本数据集上的性能要优于 SVMs，BUCC，经典的 CC及 kNN算法.

4.5 在不均衡语料上的性能比较

IACC_SV算法在处理非均衡语料集的文本分类时具有很多的优势，选择了不均衡的语料集tr21，对应CV值为1.553.表4列出了5种分类算法在不均衡语料tr21中每个类别(只统计前4大类，第5、第6类由于文档数太小，不具统计意义而过滤掉)的F1值，其中|Tr|与|Te|分别表示该类训练集文档数及测试集文档数，从表中可以看出该语料集为一个不均衡的数据集.可以看到，IACC_SV在每个类别上的F1值都高于其他的分类算法;SVMs在大类上 (No.1)的准确率接近于IACC_SV算法，但是其在稀有类别上的准确率要明显地低于IACC_SV算法.整体上，IACC_SV算法比SVMs算法的平均F1高出10%.

表4 不均衡语料集tr21上的F1比较

5 结论

本文提出一种基于支持向量的迭代修正质心文本分类算法.该算法通过使用线性SVMs选出的支持向量作为质心分类算法的输入，并通过训练集误分样本来迭代修正初始的质心向量.新的算法在8个常用文本语料的分类效果要优于使用最佳参数训练的线性SVMs，BUCC，kNN及传统的质心分类算法，验证了新算法的有效性.特别是在非均衡语料集上的性能要明显地优于SVMs分类器及k最近邻分类.

References)

［1］Sebastiani F.Machine learning in automated text categorization［J］.ACM Computing Surveys，2002，34(1):1－47

［2］Wang D，Zhang H，Liu R，et al.Predicting bugs’components via mining bug reports ［J］.JournalofSoftware，2012，7(5):1149－1154

［3］Han E H，Karypis G.Centroid-based document classification:analysis ＆ experimental results［C］//Proceedings of PKDD’00.London:Springer-Verlag，2000:424－431

［4］Tam V，Santoso A，Setiono R.A comparative study of centroidbased，neighborhood-based and statistical approaches for effective document categorization［C］//Proceedings of 16th ICPR.Washington:IEEE Computer Society，2002:235－238

［5］Guan H，Zhou J，Guo M.A class-feature-centroid classifier for text categorization［C］//Proceedings of WWW.New York:ACM，2009:201－210

［6］Tan S.An improved centroid classifier for text categorization［J］.Expert Systems with Applications，2008，35(1/2):1279－1285

［7］Tan S，Wang Y，Wu G.Adapting centroid classifier for document categorization ［J］. Expert Systems with Applications，2011，38(8):10264－10273

［8］Lertnattee V，Theeramunkong T.Effect of term distributions on centroid-based text categorization［J］.Information Sciences，2004，158:89－115

［9］Shankar S，Karypis G.Weight adjustment schemes for a centroid based classifier［R］.TR 00－035，2000

［10］Foody G M.Issues in training set selection and refinement for classification by a feedforward neuralnetwork［C］//Proceedings of IGARSS.Seattle:IEEE，1998:409－411

［11］Cortes C，Vapnik V.Support-vector networks［J］.Machine Learning，1995，20:273－297

［12］Joachims T.Text categorization with support vector machines［R］.TR-23，University of Dortmund，1997

［13］Salton G，Buckley C.Term-weighting approaches in automatic text retrieval［J］.Information Processing ＆ Management，1988，24(5):513－523

［14］Jones K S.A statistical interpretation of term specificity and its application in retrieval［J］.J Documentation，1972，28(1):11－21

［15］HanE H.Tmdata［DB/OL］.Minnesota:Universityof Minnesota，2000［2011-07-02］.http://www.cs.umn.edu/～han/data/tmdata.tar.gz

［16］Xiong H，Wu J，Chen J.K-means clustering versus validation measures:a data-distribution perspective［J］.IEEE Transactions on Systems，Man，and Cybernetics Part B，2009，39(2):318－331

［17］Lewis D.Reuters-21578［DB/OL］.Dublin:Trinty College，2007［2011-07-01］.http://ronaldo.cs.tcd.ie/esslli07/sw/step01.tgz

［18］Lang Ken. 20Newsgroup ［ DB/OL ］. Massachusetts:Massachusetts Institute of Technology，2007［2011-07-01］.http://people.csail.mit.edu/jrennie/20Newsgroups/

［19］Lewis D D.Evaluating and optimizing autonomous text classification systems［C］//Proceedings of 18thSIGIR.New York:ACM，1995:246－254

［20］Yu H，Hsieh C J，Chang K W，et al.Large linear classification when data cannot fit in memory［C］//Proceedings of KDD'10.New York:ACM，2010:833－842

［21］Yang Y，Liu X.A re-examination of text categorization methods［C］//ProceedingsofSIGIR ’99.New York:ACM，1999:42－49

［22］Chang C C，Lin C J.Libsvm:a library for support vector machines［CP/OL］.Taiwan:Department of Computer Science and Information Engineering，National Taiwan University，2001［2011-07-01］.http://www.csie.ntu.edu.tw/～ cjlin/libsvm