文本自动分类新探究

陈可华

（宁德师范学院 计算机与信息工程系，福建 宁德 352100）

文本自动分类新探究

陈可华

（宁德师范学院 计算机与信息工程系，福建 宁德 352100）

文本自动分类是一种有效的组织信息和管理信息的工具.传统分类方法一般在分类效果和运行效率两者上不可兼得.通过综合 Rocchio 和 KNN 两种分类方法的优点，设计了一种基于多代表点的文本分类方法，该方法通过对各类挖掘出多个有效的代表点(真实或虚拟的)，再使用基于这些代表点的 Rocchio 和 KNN 方法进行分类.实验表明，该方法以较少的训练时间达到令人满意的分类效果，并且能很好解决不平衡类问题，实验结果显示该方法能达到与 SVM 相当的分类效果.

文本分类；多代表点；Rocchio；KNN

1 介绍

随着因特网等信息技术的发展，各类信息资源的增长都呈现海量特征，而其中文本数据始终占据重要地位.如何有效地组织、管理和使用这些文本信息成为当前的迫切需求,这促进了文本自动分类技术的迅速发展和广泛应用[1,2,4].

近年来，随着如垃圾邮件过滤[3]等需求的激励，基于机器学习的文本自动分类技术的研究取得了很大的进展，提出 了 很 多 有 效 的 分 类 模 型[4]， 如 基 于 类 中 心 的 方 法 ，N a ïv e B a y e s算法，支持向量机 S V M，K N N，神经网络，决策树，B o o s t i n g等.

在这些分类方法中，基于类中心的 R o c c h i o方法由于其简单快速而得到了广泛的应用，但是该方法的精度常常不能令人满意，其只适用于各个类之间差异比较明显的简单分类问题，而对于较复杂的情况，特别是遇到不平衡类问题时它的分类结果通常要相对差一些；K N N(k近邻)也是一个常用的分类算法，并且在许多领域(简单情况和复杂情况)都显示出良好的性能，但是该方法是一种懒惰的方法，它不用经过任何的训练学习过程，只是在分类时在所有实例中选择最相近的k的实例，再根据这k个实例的类分布选择最可能的若干的类别作为目标类别，所以该方法的一个致命弱点就是它分类时的计算量较大：当它为一个未见实例分类时，它通常要遍历训练实例空间以找到查询实例的k个最近的邻居.而其他大多数分类算法如决策树等都因为计算复杂度太高而不适用于大规模的场合，而且当训练样本集增大时，都需要重新生成分类器，因而可扩展性差.

为了解决上述问题，提高分类效率但又不丢失分类的精度，需要研究新的分类算法.该工作不论在科学研究还是实际应用中都有重要的意义.本文通过对文本分类的研究，结合基于类中心和 K N N的优点，提出了一种新的简单有效的文本分类方法，通过给各类提取多个代表点，这些代表点可能是实际存在的文本也可能是虚拟的类中心，然后基于这些代表点对待分类文档使用 R o c c h i o和 K N N等方法进行分类.从而能够利用较少的时间获得较高的分类精度并且能很好的解决不平衡类分类问题.

2 基于多代表点的文本分类模型

2.1 文本分类模型

R o c c h i o算法来源于向量空间模型理论，在向量空间法中，每个文档被看成一个词袋，然后被表示成词项权重的向量：di=(wi,1,wi,2,……,wi,n)，其中 di表示文档，n表示词项空间的维数，wi,k表示文档词项 k在文档 i中的权重，该权重表示该词项 在文 档中 的重要 程度 ，通常 使用 t f-i d f方法 或者 其 他 权重表示方法.两文档的相似度可使用对应文档向量的余弦夹角 计 算（也 可 用 其 他 方 法 如 欧 氏 距 离 等）.首先训练分类模型时，每个类使用一 个中 心向 量(C e n t r o i d)代 表,然后在 分类 时通 过检查 待 分类文档和这些中心向量的相似度，把它分到最相似的中心向量所代表的类中.令表示预定义的类别 集合，每个类中包含所属该类的文档集合.

K N N是一种懒散的方法，即它没有学习过程，只是存放所有的训练例直到接到未知文本的时候才建立分类.对于每个待分类文档，首先计算其于训练集中所有文档的相似度，然后按照相似度从大到小选择前 K的文档(k近邻)，最后返回包含这 k个文档中最多的类标签.令表示预定义的类别集合，每个类中包含所属该类的文档集合，l(d)表示文档d的类标签.

2.2 基于多代表点的文本分类模型

第二种方法类似于 K N N方法，不过此时待分类文档不是与训练实例表中的文档进行相似度计算，而是与所有代表点进行计算，其他过程与 K N N类似，此处不累述.

2.3 多代表点挖掘方法

对类代表点的挖掘是本文所提出方法非常重要的一个步骤，我们使用两种方法进行代表点的挖掘，一种是基于聚类的方式，另一种是基于文档密度的方式.基于聚类的方式首先对每个类别都进行聚类，聚成若干个簇，使用簇中心作为类的代表点，我们使用 K-M e a n s[4]算法进行文档聚类；基于文档密度的方式认为类中密度大的文档能代表该类的大部分性质，首先计算类中任意文档间的余弦相似度，然后通过如下公式计算每个文档的度其中 #C(di)表示文档 di所属类别的文档数，最后返回度值较大的若干篇文档为该类的代表点.

3 实验与分析

3.1 文本分类数据集

现在用两个数据集上验证我们模型的效果，中文数据集选用复旦文本分类语料库①，英文数据集选用 2 0-N e w sg r o u p s②.其中 2 0-N e w s g r o u p s共有 2 0个类别，各类别文本数大致相等，每个类别约有 1 0 0 0篇左右的文档，我们随机选择若干篇文本为训练集，保持训练集与测试集比例约为 7:3.复旦文本分类语料库提供者已分好训练集和测试集.我们使用所提供的训练集进行训练分类模型，其类别总数也是 2 0，各类文档数目不等(每类文档数从 2 5到 1 6 0 0)，是个不均衡类问题，并使用测试集验证模型.实验中使用中科院分词软件 I C T C L A S③对中文文本做分词处理，英文词项使用 P o r t e r算法进行词干化处理，中英文文本同样去除停用词.使用L T C权重公式计算词项的权重，D F作为特征选择方法，删除 D F小于 3的词项.

3.2 评价指标

准确率和召回率是评价分类性能的两种常用的指标.对于给定的某个类别，令a表示被正确分到该类的实例的个数，b表示被误分到该类的实例的个数，c表示属于该类但被误分到其它类别的实例的个数，则准确率(p)和召回率(r)分别被定义为：r=a/(a+c)，p=a/(a+b).一般使用 F-指标平衡准备率和召回率，其定义为

其中参数 β 用来为准确率(p)和召回率(r)赋予不同的权重.

为了评估算是每一个类的性能指标的算术平均值，而微平均是每一个实例(文档)的性能指标的算术平法在整个数据集上的性能，一般使用两种平均的方法，分别称为宏平均和微平均.宏平均均.对于单个实例而言，它的准确率和召回率是相同的(要么都是 1，要么都是 0).因此准确率和召回率的微平均是相同的，对于同一个数据集的准确率、召回率和 F 1的微平均指标是相同的.

3.3 实验设计及时间复杂度分析

我们使用 T R表示 2.2节中方法一的分类方法，T K表示方法二的分类方法，并且在代表点挖掘方法上我们分别用 K M 和 D B表 示 K-M e a n s和基 于密 度 (D e n s i t y B a s e d)两种不同方法，所以通过组合我们有四种不同的分类方法，分别 用 T R+K M,T R+D B,T K+K M 和 T K+D B表 示 .我 们 使 用R o c c h i o，K N N，l i b S V M[6]作为基准模型进行比较.

在训练阶段，基于 K-M e a n s聚类算法的时间复杂度为O(I k n)，其中 I为迭代次数，k为聚成的簇数目，n为该类中文档总数，一般来说 K-M e a n s能很快达到收敛状态.基于密度的方法的时间开销主要用于计算文档间相似度和选择度最大的 k个文档其时间复杂度大约为 O(n2+k n).在分类阶段，方法一和方法二的时间复杂度都正比于代表点个数.几个算法的时间复杂度比较可见表 1，m表示类数，k表示每类的代笔点数，N表示训练集中文档总数，一般 k*m远小于 N.

表1 三种算法的时间复杂度比较

3.4 参数选择

该方法一个重要的步骤就是确定每个类的代表点，代表点个数的不同将会对分类结果产生很大的影响.下面分别通过实验说明如何选择以使结果更优，为了简化过程，我们设每个类别的代表点个数相同，下一小节的实验也表明这样的设置(各类拥有相同的代表点数)使得该方法能很好的解决不平衡类问题.我们分别验证代表点个数从 2到 1 0对分类结果的影响，由于方法 T K还有参数 k需要调整则此处省略.实验数据随机选择 2 0-N e w s g r o u p s中的 3类和 4类，限 于 篇 幅 只 给 出 3类 数 据 (分 别 是 h a r d w a r e,f o r s a l e和m i d e a s t)的准确率结果.

图1 不同代表点个数对应的分类准确率

从图1可看出，每类5个代表点分类结果即达到很好效果，并且随着代表点个数的增加分类准确率不增反而有稍许递减，我们认为5个左右的代表点就能够很好的表示该类的性质，过多反而会带来噪音.并且可以看到基于虚拟代表点的 K M方法效果大大好于基于真实代表点的 D B方法，这是因为 D B方法在选择代表点后就丢失了该类其他文档的信息，而 K M是通过综合簇中所有点形成质心所以不会丢失过多关键信息.

3.5 结果及分析

我们使用 K M方法挖掘代表点并设置每类代表点个数为 5，对于 T K方法我们分别选择了 k为 3和 5，并设置基准模 型 K N N中 k分别为 5、1 5和 3 0，l i b S V M 所 有 参 数 为 默 认值.表 2和表 3分别为这些方法在 2 0 N e w s g r o u p s和复旦数据集上的分类结果.从分类结果可以看出该方法能表现出很好的性能.对于两种分类方法 T R和 T K，我们发现还是基于 K N N的改进方法(T K)效果更好，这也从另一方面说明了K N N方法比 R o c c h i o方法在分类效果上更好.由于每类只有5个代表点(共 5*2 0个代表点)，对于 T K方法的 k值我们分别选择了 3和 5，我们认为让 k过大对分类效果不会有太大提高，反而会因为代表点的增加给分类器带来更多干扰因素.另外，从宏平均(大小类对宏平均贡献相同)结果可以看出，对于平衡类问题(2 0 N e w s g r o u p s)，我们所提出方法最好表现与 S V M相当；而对于不平衡类问题(复旦数据集)，我们的方法表现更优，我们认为原因是传统方法在遇到不平衡类问题时会偏向大类别使得分类效果会急剧下降，而我们的方法通过对各个类提取相同数量的代表点，消除了大类会淹没小类的可能.

表 2 算法在 2 0 N e w s g r o u p s上的分类结果

表3 算法在复旦数据集上的分类结果

4 总结与展望

本文通过对文本自动分类技术的研究，结合基于 R o cc h i o方法和 K N N方法的优点，提出了一种新的简单有效的文本分类方法，通过基于聚类和基于密度两种方法提取类的多个代表点，这些代表点可能是实际存在的文本也可能是虚拟的类中心，然后对这些代表点使用 R o c c h i o和 K N N的方法进行分类.从而能够利用较少的时间获得较高的分类精度并且能很好地解决不平衡类的分类问题.

该方法一个重要的步骤就是代表点的挖掘，本文使用了两种基本的挖掘方法.近年来，概率主题模型得到了广泛的研究和应用，我们将考虑使用更精确的概率主题模型挖掘文档集中的主题信息，如 L D A[7].并且在 K M方法中我们设置各代表点权重相同，这也是我们需要加以改进的地方，不仅应该找到类中很好的代表点，还应该刻画该代表的代表性，对该类性质描述的贡献程度等.

注 释：

① http://www.nlp.org.cn/docs/download.php?doc_id =294 http://www.nlp.org.cn/docs/download.php?doc_id=295

② http://www.cs.cmu.edu/afs/cs/project/theo -11/www/ naive-bayes/20_newsgroups.tar.gz

③http://ictclas.org/

〔1〕Sebastiani F.Machine learning in automated text categorization[J].ACM Computing Surveys,2002,34(1):1-47.

〔2〕苏金树,张博锋,徐昕.基于机器学习的文本 分类技术研 究进展[J].软件学报，2006，17(9):1848-1859.

〔3〕詹川.反垃圾邮件技术的研究[D].电子科技大学计算机 系统结构系博士毕业论文,2005：1-3.

〔4〕范明，范宏建.数据挖掘导论[M].北京:人民邮电出版社，2006.

〔5〕石志伟，刘涛，吴功宜.一种快速高效的文本分类方法[J].计算机工程与应用,2005,41(29):180-183.

〔6〕Chih-Chung Chang and Chih-Jen Lin,LIBSVM:a library for support vector machines,2001.Software available at http://www.csie.ntu.edu.tw/～cjlin/libsvm.

〔7〕Blei,D.M.,Ng,A.Y.,&Jordan,M.I.(2003).Latent Dirichlet Allocation.Journal of Machine Learning Research,3,993-1022.

T P 3 9 1

A

1673-260X（2011）04-0034-03

福建省教育厅 B 类科研项目(JB09235);宁德师范学院科研资助项目(2009303)