一种基于紧密度的半监督文本分类方法

摘要：自动的文本分类已经成为一个重要的研究课题。在实际的应用情况下，很多训练语料都只有一个数目有限的正例集合，同时语料中的正例和未标注文档在数量上的分布通常也是不均衡的。因此这种文本分类任务有着不同于传统的文本分类任务的特点，传统的文本分类器如果直接应用到这类问题上，也难以取得令人满意的效果。因此，本文提出了一种基于紧密度衡量的方法来解决这一类问题。由于没有标注出来的负例文档，所以，本文先提取出一些可信的负例，然后再根据紧密度衡量对提取出的负例集合进行扩展，进而得到包含正负例的训练集合，从而提高分类器的性能。该方法不需要借助特别的外部知识库来对特征提取，因此能够比较好的应用到各个不同的分类环境中。在TREC'05(国际文本检索会议)的基因项目的文本分类任务语料上的实验表明，该算法在解决半监督文本分类问题中取得了优异的成绩。

关键词：计算机应用；中文信息处理；文本分类；半监督机器学习；支持向量机；紧密度

中图分类号：TP391　文献标识码．A

1 简介

文本分类是指对于一个给定的文档集合D＝{d1，d2，…，dj，…}和一个预定义的类别集合C={c1，c2，…ci，…}，把类别ci赋给文档dj，建立集合D和集合C之间的一个映射。sebastiani[1]指出文本分类任务就是用函数f′：D×C{0，1}来拟合未知函数f：D×C{0，1}，而f′就被称作是分类器。

在文本分类任务中，通常需要一个人工标注的训练集，包括正例和负例文档，在此基础上分类器进行学习，并调整参数，建立适应于当前分类任务的模板，最终实现对文本集合的正确自动分类。在大多数情况下，训练集合只有一小部分标注出的正例和大量未标记的文本，而未标注集合中仍存在着部分正例文档。如果简单的把包含有正例文档的未标注集合视作是负例来训练分类器，对最后的分类结果会有相当大的影响。然而，进行训练语料的标注不仅是相当耗时的工作，而且也比较困难，因为不仅要保证标注结果的正确性，同时也需要使得标注出的训练集能很好地反映语料的真实分布。

在训练集中，除去少数标注出的正例集合外，而只有一个未标注集合――也就是在整个的训练集合中，不属于任何类别的正例所构成的混合集。这种情况下的文本分类任务被称作是半监督的文本分类，这类的分类任务包含如下的一些特征：1)标注出的正例集合P的规模都比较小；2)训练集合中的大部分数据都是未标注的，其中包含的既有负例文档也有正例文档。

本文将主要讨论一种基于紧密度衡量的方法，从训练集合中提取出一个“适合”大小的负例文档集合来提高文本分类的性能。本文第二部分将介绍半监督文本分类的研究现状；第三部分将详细描述一种新的解决半监督文本分类的算法，第四部分介绍实验的结果并进行比较分析。

2　相关工作及研究现状

在过去的时间里，在信息检索、机器学习和数据挖掘等领域都对文本分类技术开展了大量的研究[2]，也发展了相当多的分类技术，诸如基于Roc－chio的分类器，朴素贝叶斯分类器(Naive BayesClassifier)，支持向量机(Support Vector Machine)，k近邻分类器(k-Nearest Neighbor)等等。但是这些技术都不能直接的应用到半监督的文本分类任务中，因此很多的研究人员对于这类的半监督的分类问题提出了一些解决方法。

Sun等人[3]提出了一种基于特征来选择相应训练实例的方法――FISA算法。FISA算法包含两个步骤，第一步是计算各个特征的区分能力，选择区分能力较高的特征进行实例选择；第二步是根据以上的特征来进行训练实例的选取。Yu在文献[4]中提出了PEBL算法，这是一种基于SVM分类器的分类方法，用来对仅给出正例的Web网页进行分类。在PEBL算法中，负例文档是通过对特征的分析提出来的，负例文档中的特征不能出现在任何一个正例文档中。PEBL算法对于正例文档的数目非常敏感，在正例文档特别少的情况下，通常性能比较差。Nigam[5]指出，在大量的未标注数据中包含着相当数量的关于特征的联合分布，因此，如果能够有效地把未标注文本和标注出来的正例文本共同利用起来，构造分类器，能够极大地提高系统的性能。Liu[6]针对半监督的文本分类提出了S-EM算法。S-EM算法利用朴素贝叶斯分类器和EM算法来解决该类问题。它把未标注的数据看作是一种不完整的数据，用EM(Expectation Maximization)算法给每一个未标注的文本赋一个类别的概率。用Spy技术从未标注文档集合中来找出那些确定是负例的文本，然后利用EM算法来最大化每个文档属于某一类别的概率，最后通过建立一个朴素贝叶斯分类器来进行文本分类。由于S-EM算法通过迭代求到的是局部最优参数，不能够保证整体的最优分类，所以对数据比较敏感。Blum和Mitchell[7]在作Web网页分类的时候，应用了联合训练(Co-training)的方法。首先从网页中提取出不同的特征，构成两个独立的特征子集合，然后分别根据不同的特征集合构造相应的判决函数，最后分别用不同的判决函数对未标注的文本属于某个类别的概率进行估计，并选择相应的具有最高后验概率的文本加入到训练集合，进行分类。Co-EM算法[8]则讨论了使用EM算法进行多角度学习，Ghani在实验中也证明了总体上看来，Co-EM算法要比联合学习方法性能更好，特别是在当联合学习中的兼容性和独立性的假设不满足的时候。Brefeld[9]提出了一种Co-EM SVM的学习方法，取得了理想的效果。但是联合训练对于自身没有多特征属性的文档却是不适用的。

3 一种基于紧密度的半监督文本分类算法

一个分类器通常是从正负例文本的特征分布中学习到相关类别的信息，并据此进行分类的。但是在这种没有标注出负例文档的分类任务中，无法全面的获得关于所有特征在正例和负例训练文档上的分布信息，仅有特征在正例中的分布情况。而由于未标注集合的数目与正例集合相比过于庞大，导致很多的分类器在分类时都会比较倾向于大的类别，如果只是简单的把未标注的文本视作负例进行处理，必然会导致由于负例集合过大，而将正例中的一些特征的区分程度减小。因此本文提出一种基于紧密度衡量的半监督的文本分类算法。其主要思路是首先从未标注的文档集合中找出可信的，典型的负 例，即初始负例集合；然后根据紧密度衡量，计算未标注集合中的文档与初始负例以及正例之间的相对紧密度，把最初生成的可信初始负例集合扩展到一个相对比较合适的规模，最后依据扩展好的负例集合和给出的正例集合对测试集进行文本分类。各个集合之间的关系见图1。

3.1 从未标注的集合U中提取初始负例集合N′

我们首先采用基于Rocchio的分类器从未标注的集合中提取出一个可信初始负例集合N′。

Roechio算法是一个在文本检索领域的相关反馈中得到广泛应用的一个算法。Li[10]指出在没有“纯”的标注负例的情况下，Rocchio分类器能够比较好的从U中提取出正确的负例。它最初由Roc-chio在文献[11]中提出，并且被证明是一个很有效的学习算法。Rocchio分类器由向量CRoc=＜ω1i，…，ωki，…，ωti>表示，其中ωki表示特征tk在类别ci中的权重，由如下公式计算：

其中ωki表示对于类别ci来说，特征tk在该类中的权重；ωki表示特征tk在文档dj中的权重，|Pi|、|Ni|分别表示对于类别ci来说，其正负例集合中文档的数目，而β和γ分别表示特征在正负例中形成最后的分类器时的相对重要度。公式(1)中，前半部分的值通常能够比较好的表示出某个类别ci的特异性，而后半部分则表示了训练集的一般特征。

利用Rocchio算法首先将未标注集合U，视作是负例集合，然后根据正例集合P和U建立分类器，再利用该分类器对集合U进行分类，这样可以把未标注集合U分为正例和负例。

我们采用交叉验证的方法，将给定的训练集随机的分成10份，依次把其中的9份用来做训练，其余1份作为测试，通过设定阈值，使得每一次分类的结果的召回率都达到100％，则剩下的那些被判为负例的文档就构成了初始的负例集合N′。算法的详细过程见表1。

3.2 根据聚类的紧密度扩展负例集合N′

在上一步提取出的负例集合N′中通常只包含关于训练集合的一些有限的信息，因此不能反映特征在全局状态下的分布，需要对N′进行扩展。

对这些聚类而言，通常会遇到的如下两个问题：1)由于样本空间的分布通常是不均匀的，即有些样本分布得相对比较紧密，而有些则相对要稀疏很多；在计算某一个未标注文档是否应归到正例或者负例中时，需要综合考虑它和初始负例集合N′中样本的相似度以及样本相互间的紧密程度；因此我们在此需要对集合N′进行聚类，用每一个聚类的中心以及这个聚类的紧密程度来代替该聚类；2)由于此处是对负例集合进行扩展，因此需要能够尽量将与负例较为相似的文档扩展到负例集合中去，而那些与正例和负例均比较相似的特征不明显的文档则不作处理；因此需要综合考虑每一篇未标注文档和正例以及负例间的平均差异。

首先使用聚类方法对集合N′进行聚类。在本算法中采用了应用广泛的K－means聚类算法，K－means算法把N′划分成了k个聚类，分别表示为N1，N2，…，Nk，而各个聚类的中心则用CN1，CN2，…，CNk表示。

在此，为表示初始负例聚类集合Nk的紧密程度以及正负例之间的差异程度，我们定义两个概念――紧密度和差异度。

定义1一个聚类的紧密程度Closeness，是表示该聚类中所有文档与聚类中心之间的平均相似度，由公式(2)表示：

其中，Cl(Ni)表示聚类Ni内部的紧密度，dj则是聚类Ni中的任意文档，CNi是聚类Ni的中心，|Ni|表示聚类Ni中的文档数目。

因此，对于集合N′来说，其平均紧密程度：

MeCl(N′)表示负例集合N′的平均紧密度，k则是N′所包含的聚类数目。

引申一下，可知聚类Ni与正例集合的中心Cp之间的紧密度为：

Cp表示正例集合的向量中心，故Cl(Ni，Cp)就表示聚类Ni与正例中心Cp之间的紧密度。

定义2　负例文档的平均相似度与正负例文档集合的差异度Differ则由公式(5)定义为：

例中心Cp的平均紧密程度，k为聚类数目，而Df(N′，C)则表示负例集合N′与正例中心Cp之间的紧密程度的差值。

因此，对于dj∈(U-N′)来说，是否能够加入到扩大的负例集合中，需要dj满足如下的两个条件：(i)dj与最近的一个聚类的相似程度必须足够的大，即对聚类Ni而言，它必须要有足够大的紧密度，即为：

maxi=1…k(S(dj，CNi))＞MeCl

(6)

(ii)dj与离其最近的负例中心和正例的间差异度必须要比正负例集合整体的平均差异度要大，即：

maxi=1…k(S(dj，CNi)-S(dj，Cp))＜Df

(7)

只要满足条件(6)和(7)，那么文档di就可以放入扩展的负例集合N中。

其中，两篇文档之间的相似度的定义为：

3.3 用支持向量机分类器进行文本分类

最近，很多的分类方法都被应用到了文本分类领域，Yang在文献[12]中指出在这些分类方法中，SVM分类器从效率和性能上来讲都较好。SVM分类器是由Vapnik[13]提出用于解决二元模式识别问题的。SVM分类器通过最大化支持向量和分界面的距离(Margin)，找出能够最好地将两个类别分出的分界面。它基于最小化结构风险原则，同时利用 最大化分类间隔来获得最好的分类泛化性能。并且通过引人松分类间隔超平面(Soft margin　hyper-plane)和将原始数据点映射到更高维空间的方法，SVM分类器可以成功运用到线形不可分的问题中。因此目前SVM分类器得到了广泛的应用，所以在本文的分类方法也采用了SVM分类器。

4　实验及结果分析

4.1 实验评价

文本分类任务有两个比较常用的评价标准，也就是F值和Utility值。F值通常定义为：

其中，Precision表示分类精度，而Recall则表示分类的召回率。

第二个比较常用的评价标准则是Utility值[4]，由于这个标准对于那些误分类的文档做出了一些惩罚，所以综合考虑了比较全面的信息：

Uram=(Ur×TP)+(unr×FP)

(10)

标准化Utility值则为Unorm=Uraw／Umax其中，TP指被正确分类出的正例――即应当为正例，最后通过分类系统也被确认为正例的文档数目；而FP则是被错误分类为正例的文档数――即负例文档经过分类系统错误的被认作是正例，其中μr表示相关文档的效用；而μnr表示不相关文档的效用。

4.2　实验数据集

我们参加了TREC′05基因项目的文本分类任务[15]，该任务的主要目的就是在取自于多本生物领域的期刊中的约14000多篇文档找出属于以下四个类别：A，E，G，T的相应文档。其中A(Alleles)类表示论述变异显型的等位基因类的文章，E(Em-bryologic)类表示胚胎的基因表达类的文章，G(GO)类表示基因本体类的文章，而T(Tumor)类则表示肿瘤生物学类文章。训练集中各个类别的分布如表3所示：

明显可以看出，在训练集合中正例与未标注文档的分布是不均衡的，T类的正例与未标注文档在数目上的比更是达到了1:160。而且通常给出的训练集合中由于未标注部分文档的不“纯净”，存在大量的未标注数据中包含应标注为正例的情况，所以不能简单地把未标注集合作为负例来处理――因为误判作负例的正例实际上对分类效果的影响是巨大的。因此有必要从未标注集合中提取出一个初始的可信的负例集合N。

4.3 实验方法及结果分析

首先对文档集合做预处理时，所有提取出的特征都是经过原型恢复和禁用词去除。

用交叉熵的方法来给每个特征赋不同的权重，我们仅取交叉熵值最大的前5000个特征项，假定c为类变量，C为类的集合，对于特征f，其交叉熵记为CE(f)，则有：

其中，P(c|f)表示特征厂和类别c共同出现的概率，P(c)表示类别c出现的概率，P(f)表示特征f出现的概率。

经过用Rocchio分类器获得可信负例集合同时对其进行依据紧密度的扩展之后，我们达到负例集合大小如表4所示。

在获得了扩展后的负例集合N之后，使用SVMlight[16]来进行文本分类。在本实验中，由于需要从语料中分别找出属于A、E、G、T四个类的文档，所以把该任务看作是4个二元分类的问题。我们采用了Fujita,sup>[17]在2004年TREC Genomics项目中SVMlight的参数。

TREC采用Utility值来做最后的测评标准。在实验中采用了三种方法对TREC′05的分类任务进行比较。

实验中各组数据采用的方法及其描述分别为：

a)NE(None Extracted)：没有作任何的负例提取工作，只是简单的把未标注的文档作为负例集合，按传统的文本分类方法用SVM分类器进行分类；

b)EO(Extracted Only)：直接把提取出来的负例N′用作训练时所需的负例集合，不对其做任何的扩展；

c)CE(Closeness―based Enlargement)：根据紧密度衡量，来对提取出来的负例集合N′进行扩展，得到最后用于分类的训练集合。

从表5中可以看出，如果我们仅仅使用提取出的最初负例集合N′作为最终分类时候使用的负例，性能比较低，这是因为在提取集合N′的时候，由于要保证N′中的为可信的负例，所以N′的规模比较小，所包含的特征也比较少，而采用基于紧密度衡量的方法对提取的负例进行扩展之后，能够很好的提高无标注负例的文本分类的分类效果。从A类到T类，Utility值分别提高了12.54％、28.79％、3.38％和1.85％。可见，本文提出的基于紧密度的方法对未标注集合进行负例提取和扩展的方法对于这种半监督的文本分类任务有着良好的分类效果。

TREC′05的基因项目有41个组参加并提交了结果，是TREC会议参加单位最多的一个任务。表6给出了TREC′05基因项目在每个类别上最高的组的得分。IBM T.J.Watson实验室使用了交互结构最优化算法(Alternating Structure Optimiza－tion，ASO)，并结合Logistic回归算法，他们的系统提交的结果在A类上取得了最高的成绩；英国Rut－gers大学利用GO、Swiss-prot等外部数据库的知识对特征进行选择，采用的是贝叶斯Logistic回归分类方法，他们的系统在T类上取得了很好的成绩；第三列是复旦大学WIM组提交的结果，在E类和G类上都取得了最好的成绩。他们使用的则是利用语料库对比的方法，通过与一个在一般领域内的语料相比较，找出在基因领域内比较独特表示文本的特征，并据此利用SVM分类器进行分类。

最后一列是使用基于紧密度的半监督学习的分类方法得到分类结果，可以看出，本文提出的方法在各个类别上的结果都比较优秀，而且在各个类别上表现比较稳定，平均的Utility值高于任何一组。

通过上述的几种方法的比较可以看出，在诸如生物学等特定的领域内，如果要提高分类系统的性能，传统的方法都是使用一些外部的知识源来辅助进行特征的提取，提取出依据先验的人工标注出的一系列知识库获得的特征。此时，能否取得比较好的性能不光与分类器或者学习算法本身有关还与选择的外部知识库是否全面有效也很有关系。另外，对于一个比较新兴的领域，如果尚未形成任何有效全面的知识库，这种依赖于外部知识库来进行分类的方法就难以适用。而本文提出的方法由于没有使用其它的外部知识源，而只是通过分析所给出的语料集合中正例及未标注文档的分布状况来进行分类，所以较前述的两种方法相比，能够比较好的应用 到其它的领域中。

5 结论

本文提出了一种基于紧密度的方法来解决半监督的文本分类问题。首先从负例集合中抽取出一些典型的负例，然后依据未标注集合中文档与正例和抽取出的负例的相应紧密度来对抽取出的负例集合进行相应的扩展，最后得到用于分类训练所需要的负例集合，结合训练集中原来给出的正例集，进行文本分类。该分类方法不需要借助特别的外部知识库来对特征提取，因此该方法能够比较好的应用到各个不同的分类环境中。同时实验也充分证明了该方法取得了比较好的效果。

在本文提出的基于聚类的紧密度来对抽取出的负例集合进行扩展的方法，有一个重要的步骤就是抽取良好的初始负例集合并对其进行有效的聚类，对于初始负例集合的抽取和聚类数目的选择也是相当重要的，这将需要进一步的研究，以期进一步提高该算法的性能。

收稿日期：2006－05－27　定稿日期：2007－01－31

基金项目：国家自然科学基金资助项目(60305006)

作者简介：郑海清(1982－)，男，硕士生，研究方向为自然语言处理与文本分类。

参考文献：

[1]Fabrizio Sebastiani,Machine learning in automated text categorization[J].ACM Computer Survey,2002,34(1):1－47.

[2]黄萱菁，吴立德，石崎洋之，徐国伟．独立于语种的文本分类方法[J]．中文信息学报，2000，14(6)：1－7．

[3]A,Sun,E.Lim,B.Benatallah and M.Hassan,FI-SA:Feature-based Instance Selection for ImbalancedText Classification[A].Pacific-Asia Conference onKnowledge Discovery and Date Mining[C].2006,250-254.

[4]H.Yu,J.Han and K.Chang.PEBL:Positive example based learning for Web page classification using SVM[A].Internatinal Conference on Knowledge Dis-covery and Data[C].2002.

[5]K.Nigam,A.K.McCallum,S.Thurn et a1.Text Classification from Labeld and Unlabeled Documents using EM[J].Machine Learning,2000,39,103-134.

[6]B.Liu,P.S.Yu,and X.Li,Partially supervised clas-sification of text documents[A].In:Proceedings of 19th International Conference on Machine Learning [C].2002.

[7]A.Blum,T.Mitchell,Combining labeled and unla-beled data with co-training[A].In:Proceedings of the 11th annual conference on Computational learning the-ory[C].1998.92-100.

[8]R.Ghani,Combining labeled and unlabeled data for multi-class text categorization[A].In:Proceeding of the 19th International Conference on Machine Learning [C].2002.

[9]U.Brefeld,T.Scheffer,Co-EM Support Vector Ma-chine[A].In:Proceeding of the 21st International Conference on Machine Learning[C].2004.

[10]X.Li,B.Liu,Learning to classify texts using posi-tive and unlabeled data[A].In:Proceedings of the 18th International Joint Conference on Artificial Intel-ligence[C].2003.

[11]J.Rocchio,Relevance feedback information retriev-al.In:G.Salton,editor,The Smart retrieval sys-tem-experiments in automatic document processing[M].Prentice Hall,1971,313-323.

[12]Y.Yang and X.Lin,A re-examination of the catego-rization methods[A].Special Interest Group on In-formation Retrieval[C].1999.

[13]V.Vapnik,The Nature of Statistical Learning Theo-ry[M].Springer,1995.

[14]W.Hersh,A.Cohen,J.Yang,et al,TREC 2005 Genomics Track Overview[A].In:Proceeding of Text Rretrieval Conference [C].2005.

[15]J.Niu,L.Sun,L.Lou,et al,WlM at TREC 2005[A].In:Proceeding of Text Retrieval Conference [C].2005.

[16]T.Joachims,Estimating the Generalization Perform-ance of a SVM Efficiently[A].In:Proceedings of the 17th International Conference on Machine Learning[C].2000.

[17]Fujita S.Revising again document length hypotheses TREC 2004 genomics track experiment at patolis[A].In:Proceeding of Text Retrieval Conference[C].2004.