《一种基于向量空间模型的多层次文本分类方法_刘少辉.pdf》由会员分享，可在线阅读，更多相关《一种基于向量空间模型的多层次文本分类方法_刘少辉.pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、中?文?信?息?学?报第 16 卷 第 3 期?JOURNAL OF CHINESE INFORMATION PROCESSINGVol.16 No.3一种基于向量空间模型的多层次文本分类方法?刘少辉?董明楷?张海俊?李?蓉?史忠植(中国科学院计算技术研究所智能信息处理重点实验室?北京?100080)摘要:本文研究和改进了经典的向量空间模型(VSM)的词语权重计算方法,并在此基础上提出了一种基于向量空间模型的多层次文本分类方法。也就是把各类按照一定的层次关系组织成树状结构,并将一个类中的所有训练文档合并为一个类文档,在提取各类模型时只在同层同一结点下的类文档之间进行比较;而对文档进行自动分类时
2、,首先从根结点开始找到对应的大类,然后递归往下直到找到对应的叶子子类。实验和实际系统表明,该方法具有较高的正确率和召回率。关键词:文本分类;向量空间模型;信息增益;特征提取中图分类号:TP391.1An Approach of Multi?hierarchy Text Classification Based on Vector Space ModelLIU Shao?hui?DONG Ming?kai?ZHANG Hai?jun?LI Rong?SHI Zhong?zhi(Laboratory of Intelligent Information Processing,Institute o
3、f Computing Technology,Chinese Academy of Sciences?Beijing?100080)Abstract:This paper does research and improves on the classical approach of calculating the term weight in VectorSpace Model.Furthermore,an approach of multi?hierarchy text classification based on Vector Space Model is pro?posed.In th
4、is approach,all classes are organized as a tree according to some given hierarchical relations,and all thetraining documents in a class are combined into a class?document.In order to construct the class models,it is just onlyto compare among the class?documents attached to the same node of the same
5、layer.When it is going to classify the docu?ments,one matching process is hierarchically performedfrom the root node to the leaf nodes until a corresponding subclass isfound.The experiment and real systems indicate that the approach is of high classification Precision and Recall.Keywords:Text Classi
6、fication;Vector Space Model;Information Gain;Feature Selection一、引言随着信息技术的发展,特别是 Internet 应用的普及,人们已经从信息缺乏的时代过渡到信息极为丰富的时代。如何从大量信息中迅速有效地提取出所需信息也就成为一项重要的研究课题。由于分类可以在较大程度上解决目前网上信息杂乱的现象,方便用户准确地定位所需的信息,因此分类尤其是文本分类的研究变得越来越重要 1,11。文本分类的目标是在分析文本内容的基础上给文本分配一个或多个比较合适的类别。目8?收稿日期:2001-11-8本文得到国家自然科学基金(60173017)和北
7、京自然科学基金(4011003)支持作者刘少辉,男,1977 年生,博士研究生,主要研究方向为数据挖掘、信息检索.董明楷,男,1973 年生,博士研究生,主要研究方向为智能主体、描述逻辑.张海俊,男,1980 年生,硕士研究生,主要研究方向为智能主体、软件工程.李蓉,女,1973 年生,硕士研究生,主要研究方向为神经网络.史忠植,男,1941 年生,研究员,博士生导师,主要研究方向为人工智能、知识工程.前已经有许多机器学习方法应用到该领域:Vapnik 提出的支持向量机(SVM)2;在文本分类研究一开始就引起关注的 K 近邻(KNN)分类器 3;Yang 提出的一种线性最小二乘方拟合法(LLS
8、F)4;Apte 采用决策树方法进行分类 5。另外,神经网络(Nnet)和贝叶斯 6方法也被广泛地应用到文本分类中。上述大多数方法都采用了经典的向量空间模型(VSM)。在该模型中,文档的内容被形式化为多维空间中的一个点,以向量的形式给出,然后通过计算向量间的距离决定向量类别的归属。而在向量空间模型中,经典的词语权重计算方法将词频和倒排文档频率结合起来(称为tf.idf 方法)7。本文对 tf.idf 方法进行了分析并做了改进,使之更加合理。另外,在此改进的基础上,本文提出了一种多层次文本分类的方法。也就是把各类按照一定的层次关系组织成树状结构,并将一个文档类中的所有训练文档合并为一个类文档,在
9、提取各类模型时只在同层同一结点下的类训练文档间进行比较;而对文档进行自动分类时,首先从根结点开始找到对应的大类,然后递归往下直到找到对应的叶子子类。实验和实际系统表明:该方法是行之有效的,具有较高的分类正确率与召回率。本文组织如下:第 2 节介绍对词语权重计算方法的研究和改进;第 3节给出多层次文本分类的实现算法;第 4 节列出实验结果和分析;第 5 节给出结论。二、词语权重的计算在 VSM 中,每一篇文档都被映射成多维向量空间中的一个点,对于所有的文档类和未知文档,都可用此空间中的向量(T1,W1;T2,W2;?;Tm,Wm)来表示(其中 Ti为词,Wi为词对应的权值,用以刻画该词在描述此文
10、档内容时的重要程度),从而将文档信息的表示和匹配问题转化为向量空间中向量的表示和匹配问题来处理。对于词权重的计算,经典的 tf.idf 方法考虑两个因素:1)词语频率 tf(term frequency):词语在文档中出现的次数;2)词语倒排文档频率 idf(inverse document frequency):该词语在文档集合中分布情况的一种量化,常用的计算方法是 log2(N/nk+0?01),其中 N 为文档集合中的文档数目,nk为出现该词语的文章数。根据以上两个因素,可以得出公式:Wik=tfik?log2(N/nk+0?01),其中 tfik为词语Tk在文档Di中出现的次数,Wik
11、为词语Tk在文档Di中的权值,k=1,2,?,m(m 为词的个数)。为了计算方便,通常要对向量进行归一化,最后有:Wik=tfik?log2(N/nk+0?01)?mk=1(tfik?log2(N/nk+0?01)2(1)?以上公式的提出是基于这样一个考虑:对区别文档最有意义的特征词应该是那些在文档中出现频率足够高而在文档集合中的其它文档中出现频率足够少的词语。由于 Wik对特征词的选择起决定性的作用,有很多学者对此做了深入研究。Rocchio 提出了基于正例反例的批处理计算方法13;Widrow 提出了即时的线性计算方法14;李国臣等提出了基于对数似然比测试的词权重计算方法9;张月杰等结合了
12、词在文档中的位置,如标题、正文 15。我们所采用的方法是经典的 tf.idf 方法的改进,结合了词的信息量。也就是把文档集合D 看成一个符合某种概率分布的信息源,依靠文档集合的信息熵和文档中词语的条件熵之间信息量的增益关系确定该词语在文本分类中所能提供的信息量,即词语在分类中的重要程度,然后将该信息量综合到权重计算公式中。这样就弥补了 tf.idf 方法虽然考虑了词语在文档集9合中的分布情况,但是并没有考虑分布的比例情况的缺陷。具体的计算公式如下所示:Wik=tfik?log2(N/nk+0?01)?IGk?mk=1(tfik)2?log2(N/nk+0?01)?IGk2(2)IGk为词语Tk
13、的信息量,其计算公式为:IGk=H(D)?(H(DTk),其中文档集合 D 的信息熵,H(D)=-?di?D(P(di)?log2P(di),词 语Tk的 条 件 熵 H(DTk)=-?di?D(P(diTk)?log2P(diTk)。至于如何定义文档 di的概率,文 8 曾提到令P(di)=wordset(di)?dj?Dwordset(dj),wordset(di)表示文档 di中不同词语的个数。但是若采用该公式,则在计算文档的概率时只考虑到词语的数目,两篇词语相同但是词语频率不相同的文档都会被认为概率相同。为了能进一步更加准确地反映文档分布的比例情况,而且兼顾到在tf.idf方法中词频是
14、核心因素,我们定义 P(di)为:P(di)=wordf req(di)?djwordf req(dj)(3)?wordf req(di)表示文档 di中所有词的词频之和。改进后的效果将在第 4 节详细给出。三、多层次分类算法一般的分类方法都采用全部类别共享一个分类器或者每个类别设置一个分类器的方法,又称为单分类器方法或者多分类器方法,而且这些方法中的类别都是在同一个层次,即处于同一个平面类空间上。当类别的个数较多时,提取模型的时间耗费巨大,而且对新文档进行分类的时候要和全部类模型进行比较,以便给该文档分配合适的类别。针对以上不足,我们提出一种基于向量空间模型的多层次文本分类方法,也就是将全部
15、类别按照一定的层次关系组织成一个树状结构。该方法的提出是基于这样一个考虑:属于同一结点下的各类肯定比不属于同一结点下的各类更有共性,比如足球、篮球、羽毛球之间的共性肯定比足球、软件、音乐之间的共性多。正是基于以上的考虑,我们把分类任务划分成更小的与类层次结构对应的分类子问题。比如,存在一个区分体育和电脑网络的分类器,另外还存在一个仅用于体育类的分类器,用来区分足球、篮球、羽毛球。每一个子任务显然比原来的任务更加简单,因为在树结构中每个结点的分类器只需要在少部分类中区分,而且由于这部分类的共性较多,这样各类模型中所包含的特征词也比较少。3.1?构建类模型通过对给定的经过人工按照类层次结构进行分类
16、后的文档集合进行训练,并经过特征选取(特征词和权值的选取)就可以构建对应的类模型,为自动分类提供基础。在构造各类模型的算法中,每个模型由向量表示,包括该类的特征词和对应的权值。在特征词的选取中,我们综合考虑了频度和集中度两种因素。考虑频度因素的特征词选择方法认为,在某一类文档中出现次数越多的词越能够代表这类文档;考虑集中度因素的特征词选择方法认为,某类的特征词应该集中出现在该类的文档中,而不是均匀地分布在各类文档中9。另外,在实际应用中组成某个类的模型的特征项的个数也不易过多,可以只保留权值较高(超过某权值阈值)的项,否则会大大降低系统的处理速度 10。10在我们的算法中,每一个文档类中的所有
17、训练文档都合并为一个类文档以进行文档类的特征词的提取,至于权重的计算则采用第 2节所提到的公式(2)。为了进一步提高模型的代表性,我们的算法在考虑权值的基础上,也考虑了以上提到的词频、词的集中度因素。详细算法CCM(Create Class Model)如下:输入:人工确定的各类之间的层次关系,实际上是一树状结构,每一结点(除了根结点)代表一个类,各训练文档都被人工分在叶子结点对应的子类中输出:各类对应的类模型,以文本文件的方式存储步骤:对叶子结点到根结点每一层的所有结点自下而上进行处理:1.若该结点 Node 是叶子结点,则统计该结点对应的类文档中的词频信息,包括各词的词频统计、总词数和总词
18、频的统计2.若该结点 Node 是非叶子结点,假设该结点有 V1,V2,?,Vt共 t 个子结点,对应的文档类中有 T1,T2,?,Ts共s 个词1)根据公式(3)计算结点 Vi对应的类文档di出现的概率p(di),其中 i=1,2,?,t2)计算 H(D)和 H(D|Tk),得到 IGk,其中 k=1,2,?,s3)提取结点 Vi对应的类模型Ci,i=1,2,?,t?a)初始化类模型 Ci为空?b)根据公式(2)计算词 Tk的权值 Wik,k=1,2,?,s?c)对各个词按照权值从大到小的顺序重新排列成 T1,T2,?,Ts?d)依次对从 T1到 Ts的各词进行判断:若类模型 Ci中的特征词
19、个数已经达到阈值N UMT,则该类模型 Ci提取结束;否则若词 Tk的权值超过一定的阈值?、词频超过一定的阈值?、词的集中度超过一定的阈值?,而且该词不在事先已设定的停用词表中,则该词可以作为该类的特征词,和权值一起加入类模型中。不难看出,此算法提取各类模型时只在同层同一结点下的类训练文档间进行比较,这样不仅提取类模型的时间相对减少,而且由于同层同一结点下的类之间的共性相对较多,则各类模型中的特征词个数比较少,使得文档分类的耗时也相应减少。3.2?文档自动分类自动分类就是通过计算机对大量的新文档进行分类。我们首先要把这些文档用归一化后的向量来表示,包括该文档中的词和该词在文档中的权重,文档中词
20、权重的计算主要考虑词频、词的位置等因素;然后对该文档向量根据类层次结构从上往下逐层和各类模型匹配,即计算它们的相似程度,直到找到与叶子结点对应的合适的子类。详细算法 TC(Text Classifica?tion)如下:输入:人工确定的各类之间的层次关系,实际上是一树状结构(与算法 CCM 的相同),每一结点(除了根结点)代表一个类;根据算法 CCM 得到的各类模型;待分类的文档输出:分配好合适类别的文档步骤 1:对待分类的文档进行向量化,设对应的向量为 d=(T1,W1;T2,W2;?;Tm,Wm)步骤 2:结点 X?根结点,若结点 X 是非叶子结点,反复执行:?1)设结点 X 有 V1,V
21、2,?,Vt共 t 个子结点,结点 Vi对应的类模型为 Ci=(t1,w1;t2,w2;?,tn,wn),i=1,2,?,t?2)依次计算文档和各类之间的相似度,其中相似度 Sim(Ci,d)用向量 d 和 Ci之间11的夹角来度量:?a)Sim(Ci,d)=0?b)若 m?n,?)则对 Ci中的每个词tu(u=1,2,?,n)在向量 d 中查找是否存在,若存在,对应的词为 Tv,则 Sim(Ci,d)=Sim(Ci,d)+Wv?wu?)否则对 d 中的每个词Tv(v=1,2,?,m)在向量 Ci中查找是否存在,若存在,对应的词为 tu,则 Sim(Ci,d)=Sim(Ci,d)+Wv?wuc
22、)找到和向量 d 相似度最大的类 Cmax,即 Sim(Cmax,d)=Maxi?1,t(Sim(Ci,d),结点 X?结点 Vmax步骤 3:结点 X 对应的类就是自动分给文档的类四、实验结果及分析我们选取的实验数据有两种,首先是国际通用的文本分类标准测试集 Reuters-21578,它包含了路透社 1987 年的新闻,全部文档使用英语,并经路透社人工汇集和分类。该测试集本身没有预先定义类层次结构,我们选取了 8 个类别共 471 篇文档作为数据集一,其中362 篇作为训练集,109篇作为测试集,并根据这些类别的特点人为设定了类层次结构,如图 1 所示。此外,我们实验室为某著名 IT 公司
23、开发了关于文本分类方面的系统,主要思路是:按照公司的需要构建具有树状结构的分类体系,通过对给定的经过人工按照类层次结构进行分类后的文档集合进行训练,得到各个类对应的类模型;然后对网络蜘蛛(Spider)抓回来的网页信息提取相应的文档内容,并且对该内容进行自动分词(包括正反向最大匹配切词、歧义处理、姓名识别,音译名识别、地名识别),再根据自动分类算法将该网页分类。经过近半年的试运行和多次的修正,已取得了较为理想的分类效果。在测试阶段,我们从新浪、FM365、网易等网站下载的网页中整理出 11000 篇文档作为数据集二,其中的 9360 篇作为训练集,1740 篇作为测试集。这些文档对应的类结构如
24、图 2 所示。整个实验分成两部分:第一部分比较所有的类在同一层次和在不同层次下分类的准确率与召回率;第二部分比较多层次分类方法下不同的权重计算方法对应的分类的准确率和召回率。数据集一对应的实验结果分别见表 1 和表 2、数据集二对应的结果分别见表 3 和表 4。由表 1 和表 3可以看出,在对少数某些类别如 hog、冰雪运动等类的文档进行分类时多层结构下的召回率或者准确率比单层结构下的要低,这是因为在每一层进行模型匹配以选择最适合的类别时都会有一定的误差,层数越往下总误差就会越大。但是从总体看,多层结构下分类的召回率和准确率都要优于单层结构的,尤其是对于那些相对全部类来说特征比较模糊的类别提高
25、的效果就比较明显,如篮球其它、体育其它等类。另外,由表 1 和表 3 的对比分析,文档类别的数目越多,定义的类层次结构越合理,使用多层次分类方法获得的效果就越好。分析表 2 和表 4 的实验结果,可以看到,改进后的 tf.idf 方法总体上优于 tf.idf 方法。然而应该指出,尽管改进后的权重计算方法使得分类的召回率和准确率有所改善,但是针对整个文本分类问题的效果仍未出现明显提高。正如 Yang 在文 3 中所述:文本分类问题是涉及到文本表示、相似度计算和算法决策等多种复杂技术的综合应用。12图 1?数据集一的类层次结构图 2?数据集二的类层次结构表 1?数据集一对应的单层和多层类结构下的分
26、类的召回率和准确率类别单层多层召回率%准确率%召回率%准确率%barley92?676?992?680?3cocoa88?287?789?492?6rice95?591?897?095?6carcass89?391?594?794?7hog85?295?873?098?1copper98?710098?798?7iron?steel92?595?195?596?2tin90?990?990?993?8表 2?数据集一对应的多层类结构下不同的权重计算方法得到的分类的召回率和准确率类别tf.idf 方法改 进 后 的tf.idf 方法召回率%准确率%召回率%准确率%barley88?980?092
27、?680?3cocoa89?492?689?492?6rice92?591?197?095?6carcass90?791?994?794?7hog73?098?173?098?1copper94?994?998?798?7iron?steel92?593?195?596?2tin87?990?690?993?8五、结束语为了能进一步更加准确地反映文档分布的比例情况,本文对经典的词语权重的计算方法进一步做了改进,经过实验验证,其性能总体上优于传统的方法。考虑到各类别之间的关系,我们提出了一种基于向量空间模型的多层次文本分类方法,把分类任务划分成更小的与类层次结构对应的分类子问题,在提取各类模型时
28、也只在同层同一结点下的类训练文档间进行比较,以减少计算量,使类模型更加正确,这无疑是对分类方法一种有益的尝试。在此基础上我们开发的有关文本分类的系统运行状况良好,具有速度快、准确度较高等特点。由于类层次结构都是事先人为全部指定,能否通过计算机自动提取这些层次结构供人参考正是我们现在进行的工作。此外,考虑到向量空间模型中的文档表示方法丢失了大量的词语关联信息,如何在文档表示、分类模型提取、分类算法中弥补这些损失也将是我们今后研究的重点。13表 3?数据集二对应的单层和多层类结构下的分类的召回率和准确率类别单层多层召回率%准确率%召回率%准确率%冰雪运动92?186?795?485?3健身91?1
29、90?292?391?8NBA93?982?894?692?2中国篮球84?179?992?587?1篮球其它11?581?846?292?7排球91?592?690?992?8乒乓球96?296?296?296?2体育其它66?981?174?590?9棋牌93?392?393?392?3拳击91?793?394?091?8赛车88?986?792?992?9体操93?692?391?595?7田径94?592?488?594?4网球83?892?987?187?1游泳77?889?490?688?3羽毛球93?891?496?294?7中国足球92?087?593?787?3国际足球90?
30、988?792?188?9收藏88?375?892?679?4文苑荟萃87?181?697?189?8旋转舞台61?883?577?980?3艺术大观59?381?865?889?6音乐86?776?392?085?9影视87?285?890?590?7表 4?数据集二对应的多层类结构下不同的权重计算方法得到的分类的召回率和准确率类别tf.idf 方法改 进 后 的tf.idf 方法召回率%准确率%召回率%准确率%冰雪运动95?485?395?485?3健身89?890?992?391?8NBA95?991?794?692?2中国篮球92?589?692?587?1篮球其它41?689?746
31、?292?7排球90?992?890?992?8乒乓球96?292?396?296?2体育其它70?290?474?590?9棋牌93?392?393?392?3拳击94?091?894?091?8赛车88?992?988?992?9体操91?595?791?595?7田径88?594?488?594?4网球87?187?187?187?1游泳90?688?390?688?3羽毛球96?294?796?294?7中国足球92?488?693?787?3国际足球91?387?292?188?9收藏93?678?593?679?4文苑荟萃89?587?690?189?8旋转舞台75?672?577
32、?980?3艺术大观64?192?165?889?6音乐89?783?192?085?9影视89?388?890?590?7参?考?文?献1?李晓黎,刘继敏,史忠植.概念推理网及其在文本分类中的应用.计算机研究与发展,2000,37(9):1032-10382?Vapnik V.The Nature of Statistical Learning Theory.New York,Springer?Verlag,19953?Yang Y.Expert network:effective and efficient learning from human decisions in text cat
33、egorization andretrieval.In Proceedings of the Fourth Annual Symposium on Document Analysis and Information Re?trieval(SIGIR?94),1994,13-224?Yang Y.Chute C G.An example?based mapping method for text categorization and retrieval.ACMTransaction on Information Systems(TOIS),1994,12(3):252-2775?Apte C.D
34、amerau F,and Weiss S.Text mining with decision rules and decision trees.In Proceedings of the Confer?ence on Automated Learning and Discovery,Workshop 6:Learning from Text and the Web,1998(下转第 26 页)14参?考?文?献1?Salton.G,Automatic Text Processing:T he Transformation:Analysis and Retrieval of Informatio
35、n byComputer,Addison-Wesley,Reading,Mass,19892?李晓黎,刘继敏,史忠植.概念推理网及其在文本分类中的应用.计算机研究与发展,37(9):1032-1038,2000年 9月3?John M.Picrrc,On the automated classification of web sites,Linkoping Electronic Articles in Computerand Information Science,Vol.6,20014?Thomas Bayer,Ingrid Renz,Michael Stein,Ulrich Kressel
36、,Domain and language independent featureextraction for statistical text categorization,proceedings of workshop on language engineering for docu?ment analysis and recognition-ed.by L.Evett and T.Rose,part of the AISB 1996 Workshop Series,Sussex University,England,April 96,21-325?Antal van den Bosch,W
37、alter Daelemans,Ton Weijters,Morphological analysis as classification:an in?ductive-learning approach,Proceedings of NEMLAP-2,2,July,19966?Manuel de Buenaga Rodriguez,Jose Maria Gomez-llidalgo,Belen Diaz-agudo,Using WORDNET tocomplement training information in text categorization,Second Internationa
38、l Conference on Recent Ad?vances in Natural Language Processing,19977?Ellen Riloff and Wendy Lehnert,Information Extraction as Basis for High-precision Text Classifica?tion,ACM Transactions on Information System,July 1994,12(3)8?Zhu Jingbo,Yao Tianshun,FIFA:a simple and effective approach to text to
39、pic automatic identification,In:Proceedings of International Conference On Multilingual Information Processing 2002,Shenyang,China,Feb.2002,207-2159?姚天顺等,自然语言理解.清华大学出版社,1995(上接第 14 页)6?Mitchell T.Machine Learning.McGraw:Hill,19967?Salton G,Buckley B.Term weighting approaches in automatic text retrie
40、val.Information Processing andManagement,1998,24(5):513?5238?鲁松,李晓黎,白硕等.文档中词语权重计算方法的改进,中文信息学报,2000,14(6):8-139?李国臣.文本分类中基于对数似然比测试的特征词选择方法,中文信息学报,1999,13(4):16-2110?邹涛,王继成,黄源等.中文文档自动分类系统的设计与实现,中文信息学报,1999,13(3):26-3211?黄萱菁.大规模中文文本的检索、分类与摘要研究,复旦大学博士学位论文,199812?Yang Y.and Liu X.A re?examination of text
41、 categorization methods.In Proceedings of the 22nd An?nual ACM SIGIR Conference on Research and Development in Information Retrieval,42-49,199913?Rocchio Jr.,J.J.Relevance feedback in information retrieval.In Salton,G.,editor,The SMART Re?trieval System:Experiments in Automatic Document Processing,pp.313?323.Prentice?Hall,Inc.,En?glewood Cliffs,New Jersey,197114?Widrow B.,Stearns S.D.Adaptive Signal Processing.Prentice?Hall,Englewood Cliffs,NJ,197915?张月杰,姚天顺.基于特征相关性的汉语文本自动分类模型的研究,小型微型计算机系统,1998,19(8):49-5526