基于搜索的短文本分类算法研究-AET

0 引言

文本分类(Text Classification)是指在给定的分类体系下，由计算机通过某种分类算法将未知类别的文本进行自动归类的过程。最近十几年，文本分类得到了迅速的发展，并且被广泛应用到许多领域，包括：数字图书馆、网页分类、垃圾电子邮件过滤等。到目前为止，已经有许多基于统计学理论和机器学习的文本分类方法，如决策树（Decision Tree）、贝叶斯方法、KNN、神经网络、支持向量机(SVM)等^[1]。然而，这些分类方法的研究和应用都是基于长文本的，而目前短文本在网络上使用越来越普遍。最近新兴起的微博客的最大的特点就是“微”，一般发布的消息只能是只言片语。著名流量统计网站ALEXA的数据显示，Twitter日均访问量已近2 000万人次，在美国、英国、加拿大等地的网站排名中均列前15位。在专业或者垂直搜索领域，由于资源限制，无法对全文进行处理，转而根据文章标题或文章摘要进行分类。这些应用场合都需要短文本分类技术。针对实际的需求以及传统方法的不足，本文提出了一种新的分类方法，利用搜索实现基于类似NaiveBayes的文本分类方法。对比实验表明，在短文本的分类上，此方法比传统的分类方法提高了准确率和分类速度。

1 相关工作介绍

在过去的四十多年中，许多关于文本分类的研究工作都是围绕着Salton提出的向量空间模型(VSM)展开的，向量空间模型的基本思想是以向量来表示文本：(W₁，W₂，…，W_n)，首先将文本进行分词，由这些词作为向量的维数，用词频来表示特征项对应的向量分量，词频计算方法主要运用TF-IDF公式。对于向量空间法的研究工作主要集中在特征选取和特征权重的调整上来提高分类的性能，如陆玉昌先生在特征选取中利用评估函数代替TF-IDF公式进行权值调整^[2]。

神经网络学习算法在文本分类中的研究和应用也非常广泛，其中最流行的神经网络算法是1986年由RUMELHARD D E和MCCLELLAND J L提出的后向传播算法(简称BP算法)^[3]。由于BP算法存在收敛速度慢、容易陷入局部极小值等问题，后人对BP算法进行了多方面的改进，如李晓峰提出了BP神经网络动态全参数自动调整学习算法^[4]。神经网络拥有很好的对噪音数据的承受能力和文本分类能力，但是需要大量的参数，这些通常主要靠经验确定。另外神经网络需要很长的训练时间，因此它适用于有足够长训练时间的应用。

王建会等提出了基于互依赖和等效半径、简单但高效的分类算法SECTILE^[5]，该方法提出互依赖（Mutual Dependence，MD）模型，并将其与N-gram结合起来进行特征属性选择，提高了属性选择的准确性，实现了有效地降维。引入等效半径(Equivalent Radius，ER)的概念,用基于等效半径的相对距离代替传统的欧氏距离，提高了分类精度。SECTILE分类算法计算复杂度低，分类模型容易更新，适用于大规模信息样本分类场合。

石志伟等提出了向量空间法和k近邻的组合分类方法^[6]，该方法将整个实例空间划分为正实例、负实例和混合实例三部分，根据查询实例落入不同的区域调用不同的分类算法。该方法充分利用了向量空间法分类速度快和k近邻方法分类精度高的优势。

以上提到的各种分类方法都适用于长文本的分类，由于短文本相对于长文本要短得多，文本中的特征数很少，并且文本之间很少含有相同的特征，因此传统的文本分类方法并不适合短文本分类。目前专门研究短文本分类的工作还较少，大致分为两种研究方向：一种是通过外部资源来增加文本之间共享的特征，丰富文本的上下文，例如Wikipedia被作为外部资源引入短文本分类中

蒲强等提出基于独立分量分析（Independent Component Analysis，ICA）和潜在语义分析（Latent Semantic Analysis，LSA）的短文本分类方法^[8]，该方法首先通过LSA对文本进行预处理，然后对处理结果再进行独立分量分析。LSA利用奇异值分解（Singular Value Decomposition，SVD）降秩方法实现信息抽取和噪声去除，将文档的高维表示投影在低维的潜在语义空间中，从而呈现出潜在的语义结构。然而对原始词——文档矩阵进行SVD，选取最大的一些奇异值对应的特征作为潜在语义空间，目前没有理论证明奇异值最大的那些特征具有最好的分类能力，所以在该潜在语义空间上进行文本分类，分类效果并没有得到改善。

滕少华等提出基于条件随机场（Conditional Random Fields，CRFs）的短文本分类方法^[9]，该方法认为短文本通常集中于一个主题，从而文本中的特征也具有很强的相关性。根据这种性质，该方法利用中文分词中的字标注方法，将短文本分类问题转化成序列标注问题，从而可以使用CRFs来解决短文本分类问题。然而CRFs依赖于高置信度特征，高置信度特征也可以引入干扰，这样就很容易导致分词错误，这种困难很难依靠CRFs自身来解决。虽然可以通过对基于CRFs的分词结果进行后处理来解决该问题，但是这种方法有它的局限性，只能使用基于CRFs的中文分词。

综上所述，目前的短文本分类方法不能有效地选择那些分类能力好的特征，分类准确度低，分类速度慢；或者依赖于中文分词系统，扩展性差。本文提出的基于搜索的Na?觙veBayes文本分类方法在这些方面进行了改进。

2 基于搜索的朴素贝叶斯分类算法

基于搜索的朴素贝叶斯文本分类是将搜索技术应用到文本分类中，并对朴素贝叶斯分类算法进行改进，从而实现的一种适合短文本分类的分类方法。分类算法如下：

令C={c₁，c₂，…，c_m}是预定义的类别集，D={d₁，d₂，…，d_n}是待分类的文档集，d={w₁，w₂，…，w_n}是一个文档的特征向量，文档d_i

式(2)、式(4)中，|c|为文本的类别数，分子上的1是为了防止出现概率为零的情况进行的加权处理。

为了计算简便，不妨在选取训练数据时规定各类别中的文本数一样多。这样，对于每一个文本类别来说，先验概率是相等的，计算P(c_j)的过程也可以忽略不计。计算贝叶斯概率也就简化成了计算文档d_i属于类别c_j的后验概率：

在式(5)中，对于每一类别来说，分母部分N(c_j)+|c|是相等的，即不影响属于每一类别的概率大小比较，这样就直接计算：

而为了防止出现负无穷和零的情况，只需要知道每一个属性(词)在指定类别中出现的文档个数，即N(w_i|c_j)。

结合上面的公式推导，可以将基于搜索的NaiveBayes文本分类算法描述如下：

(1)假定有m个类别C₁

(2)给定一个没有类标号的数据样本X，对其进行中文分词(分词系统要和步骤(1)用到的分词系统保持一致)，每个词对应一个属性，分别为W₁，W₂，…，W_n；

(3)求将数据样本X分配给类别C_j的概率，即：

换言之，X被分配到使P(w|c_i)最大的类别C_i。

注意：步骤(1)也可以看作是建立分类模型，此步不影响分类的速度，因为建立分类模型是在进行文本分类之前做的。基于搜索的NaiveBayes分类器模型是对已知类标号的训练数据集建立的索引，并且各个类别的训练数据文本数是相等的。这也是基于搜索的NaiveBayes分类器和其他分类器的不同之处。为了提高速度，本文使用了Lucene.Net搜索技术。Lucene.Net中自带的StandardAnalyzer分词器是以字为单位索引的，对于中文文本分类来说，按单字分词会影响分类的精度，所以本文使用了KTDictSeg分词系统，KTDictSeg是由KaiToo搜索开发的一款基于字典的开源的中英文分词系统。KTDictSeg可以识别中文人名，还有对Lucene.net 的支持，提供KTDictSegAnalyzer 分析器给Lucene.net。

分类器效率的评估结果可以有多种，比如分类的准确率、速度、可规模性等。而评估的方法也有多种，最简单的是保持(Holdout)方法，即使用类标号已知的数据来测试分类器。在认为分类器的准确率可以接受时，就可以利用此分类器对类标号未知的数据进行分类预测。

3 实验及结果分析

对于中文文本分类而言，目前还没有标准的语料库可供使用。因此，本文使用搜狗实验室整理的语料库(SogouC.reduced.20061127)，此语料库包含了九个类别，分别是财经、IT、健康、体育、旅游、教育、招聘、文化、军事，每一类包含1 990篇文章。对此语料库做一下简单整理，从每一类中随机选出160篇文章作为测试数据，用剩余的1 830篇文章作为训练数据建立分类模型。用准备好的测试数据对基于搜索的NaiveBayes文本分类器和weka的NaiveBayes文本分类器进行测试，测试结果如表1所示。

从表1可以看出，基于搜索的NaiveBayes分类器和weka的NaiveBayes分类器不相上下。但是，为了体现基于搜索的NaiveBayes分类器对于短文本分类的优越性，对这1 440篇测试数据做一下简单处理后再次进行测试，即每一类中包含50字以内的文本50篇、50～200字的文本50篇、200～1 000字的文本50篇和1 000字以上的文本50篇。这样测试数据就按照文本字数的多少分为了不同的等级，并且测试数据文本数也增加到了1 800篇。然后用整理后的测试数据对两种分类器进行测试，测试结果如表2所示。

根据表2的数据绘制出分类准确率的曲线图，如图1所示。

通过图1可以清楚地看到，对于100字以内的短文本的分类，基于搜索的NaiveBayes分类器在分类精度方面表现出了优越的性能。通过表2和表1的比较也不难发现，对于1 440篇长文本的分类，基于搜索的NaiveBayes分类器耗时12.587 5 s；而对于加入了短文本的1 800篇文本的分类，基于搜索的NaiveBayes分类器耗时13.006 2 s。从数字上可以看出，对于短文本的分类，基于搜索的NaiveBayes分类器在分类速度上也明显提高。

这说明基于搜索的NaiveBayes分类方法对短文本的处理得到了很好的分类效果，并且并没有因为选取全部的文本特征而降低分类速度，相反，由于搜索技术的引入，从某种程度上还提高了文本分类的速度。

4 结论

本文针对传统的文本分类方法对短文本分类的不足，提出了基于搜索的NaiveBayes文本分类方法。该方法与传统的文本分类方法的不同之处在于，它将搜索引擎技术应用到了文本分类中，并对朴素贝叶斯分类算法进行了改进。实验结果表明，对于短本文的分类，基于搜索的NaiveBayes分类方法不仅大大提高了分类的准确度，同时降低了时间复杂度。另外，在文本特征提取和中文文本停词的处理方面，针对不同的应用背景还需要做进一步的研究。实验用的语料库不是标准的语料库，仅仅有17 910篇文章，因此，实验的规模有待进一步扩大。在应用前景方面，随着通信技术和互联网的发展，电子邮件、短信、微博信息等各种短文本信息迅速增加，基于搜索的NaiveBayes文本分类器必将会得到广泛的应用。

参考文献

[1] Wu Xindong，KUMAR V，QUINLAN J R，et al.Top 10 algorithms in data mining[J].Knowl.Inf.Syst.，2008(14)：24-27.

[2] 陆玉昌，鲁明羽，李凡，等.向量空间法中单词权重函数的分析和构造[J].计算机研究与发展，2002，39(10)：1205-1210.

[3] RUMELHART D E，MCCLELLAND J L.Parallel distributed processing：explorations in microstructure of cognition，Vol.1：Foundations[M].Cambridge：MIT Press，1986：318-364.

[4] 李晓峰.动态全参数自调整BP神经网络预测模型的建立[J].预测，2001，20(3)：69-71.

[5] 王建会，王洪伟，申展，等.一种实用高效的文本分类算法[J].计算机研究与发展，2005，42(1)：85-93.

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

[7] SCHONHOFEN P.Identifying document topics using the Wikipedia category network[C].Proc.the IEEE/WIC/ACM International Conference on Web Intelligence，2006：456-462.

[8] Pu Qiang，Yang Guowei.Short-text classification based on ICA and LSA[C].Berlin：Springer-Verlag Berlin/Heidelberg，2006：265-270.

[9] 滕少华.基于CRFs的中文分词和短文本分类技术[D].北京：清华大学，2009.

作者信息:

康 卫1，邱红哲2，焦冬冬1，房志奇1，于寅虎1

(1.华北计算机系统工程研究所，北京100083；2.北京航天飞行控制中心，北京100094）

閱讀更多 電子技術應用 的文章

關鍵字: 短文 分类 电子邮件