基于词条聚合和决策树的文本分类方法

1、基于词条聚合和决策树的文本分类方法王煜1,张明1,马力2(1.河北大学数学与计算机学院,河北保定071002;2.河北大学出版社,河北保定071002摘要:根据词条聚合和决策树原理,提出了一种文本分类的新方法.决策树分类方法具有出色的数据分析效率和容易抽取易于理解的分类规则等优势,但只能应用于维数较低的特征空间.本方法将与各个类别相关程度相似的词条聚合为一个特征,有效地降低了向量空间的维数,然后再使用决策树进行分类,从而既保证了分类精度又获得了决策树易于抽取分类规则的优势.关键词:文本分类;互信息;决策树中图分类号:TP 391.1文献标识码:A 文章编号:1000-1565(200503-0

2、338-05随着网络的发展,网络信息出现爆炸性增长.Internet 上的这些信息多数以文本形式出现,这些非结构化的数据源中存在着大量的知识,在这些数据源中抽取潜在的有用模式和隐藏的信息已成为一个日益流行且重要的研究课题.此项工作就是文本挖掘.文本分类作为文本挖掘的一个重要内容也日趋重要.常用文本分类方法有贝叶斯分类方法、决策树方法、KNN 方法、支撑向量机SVM 、神经网络方法、L IST 和Voted Classfication 方法等1.这些方法除决策树方法外追求的是较高的文本分类正确率,却极难抽取出使人易于理解的文本分类规则.规则抽取也是文本分类中的一个难题,虽然也有基于规则抽取的文本

3、分类技术.但这种分类方法抽取易于理解的分类规则依然是困难的.例如基于粗糙集的文本分类规则抽取方法2-3就存在着明显的缺陷:决策表十分庞大,因而离散化和基于粗糙集的属性约简的工作量巨大;若分类规则包含特征项具有实型权值,则规则不易理解并且分类时不能直接利用,从而缺少实用性.决策树分类方法不仅具有出色的数据分析效率,并且很容易抽取出分类规则,抽取出的规则直观易懂,这是其他方法无法比拟的优势.但是决策树也存在着弱点:决策树方法在文本特征维数过高、数据量过大时建立决策树需要很长时间且分类精度降低,而且类别过多时容易出错.本文提出了一种基于词条聚合的决策树文本分类方法,即将各个类别相关程度相似的词条聚合

4、为一个特征,从而大大降低了建树时间,提高了分类正确率,也在一定程度上解决了利用高维属性发现规则的难题.这种方法既有决策树易于抽取可理解规则的优势又保证了分类精度.1决策树决策树可看作树型的预测模型,树的根结点是整个数据集合空间,每个分节点是一个分裂问题,它是对属性的测试,该测试将数据集合空间分割成2个或更多块,每个叶结点是带有分类的数据分割.从决策树的根结点到叶结点的一条路径就形成了对相应对象的类别预测.决策树建树的算法有很多,例如ID3,CL S ,C4.5,CAR T ,SL IQ ,SPRIN T 和Med G en 和Med G enAdjuet 算法等等4.这些算法均采用自顶向下的贪

5、婪算法,在每个结点选择分类效果最好的属性将结点分裂为2个或多个收稿日期:2004-10-28基金项目:河北省科学技术研究与发展计划项目(04213534作者简介:王煜(1971-,女,河北保定人,河北大学讲师,天津大学在读博士.第25卷第3期2005年5月河北大学学报(自然科学版Journal of Hebei University (Natural Science Edition Vol.25No.3May 2005子结点,继续这一过程直到这棵树能准确地分类训练样本,或所有属性都已被使用过.决策树的核心问题是选取测试属性和决策树的剪枝.1.1属性的选取建树算法的属性选择标准非常重要.属性选择

6、的方法有很多种,例如信息增益、信息增益比、gini 索引、距离度量、G 统计、2条件统计表法、证据权重、相关度等等方法5.ID3算法依据信息增益4选择属性.若属性a 的值将样本集T 划分成T 1,T 2,T m ,共m 个子集,信息增益为gain (a =info (T -mi =1|T i |T |×(T i ,(1其中:|T |为T 的样本个数,|T i |为子集T i 的样本个数,info (T 的计算公式为info (T =-sj =1freq (C j ,T ×log 2(freq (C j ,t ,(2其中,freq (Cj ,T 为T 中的样本属于Cj 类别的

7、频率,s 是T 中样本的类别数量.C4.5依据的信息增益比4的公式为G ainratio (a =gain (a splitinf (a .(3splitinf (a 表示拆分信息,即把T 分成m 部分而生成的潜在信息,计算公式为splitinf (a =-m i =1|T i |T |×log 2(|T i |T .(41.2决策树的剪枝为了防止决策树和训练样本集的过分拟合,需要对决策树进行剪枝.剪枝通常采用事前剪枝和事后剪枝2种方法.事前修剪方法是建树过程中判断当前结点是否需要继续划分的剪枝方法.通常是重要性检测2或信息增益等判断是否停止分裂结点.事后修剪方法让树“充分生长”之后

8、,再判断是否将某些分支变成结点.常用方法有根据分类错误率5或决策树编码长度6进行决策树的事后修剪方法.2一种基于词条聚合方法的特征抽取方法目前的文本分类方法几乎均使用经典的向量空间模型(VSM 的文本特征表示方法.向量空间模型(VSM 的向量维数一般为几千维,甚至几万、几十万维.过高的向量维数会导致文本分类时间代价的提高和分类精度的降低,因此需要进行特征抽取.本文采用互信息对文本特征进行特征抽取后,再根据词条与各个类别相关程度的相似程度进行合并,从而得到维数较低的文本特征矩阵.本文中测量词条间与各个类别的相似度的方法采用比较词条与各个类相关程度的比例.与各个类别相关程度比例相似的词条,虽然具有

9、不同的权值,但对于分类操作具有相同的作用,可以合成为一个特征.正是基于这个道理,词与各个类别相关程度相似的词条归结为同一个特征,这个工作称为词条聚合.没有进行词条聚合之前,每个特征只对应一个词条.词条聚合后的文本特征向量空间的每个特征将包含一个或多个词条,从而大大削减了文本向特征量的维数.2.1互信息特征抽取通常通过构造一个评估函数对特征集中的每个特征计算其评估值,然后对所有特征根据评估值大小进行排序,选取预定数目的最佳特征作为结果的特征子集.常用的特征评估函数有词条和类别的互信息、期望交叉熵、文本证据权和CHI 等等7.其中互信息体现的是词条和类别的相关程度,互信息越大,词条和类别的相关程度

10、也越大.词条word i 与类别C j 的互信息为933第3期王煜等:基于词条聚合和决策树的文本分类方法M I (word ,C j =log (P (word j |C j P (word j (5其中P (word i |C j 是word i 在C j 中出现的概率,其中P (word i 是word i 在整个训练集中出现的概率.M (word i ,C j 表示了词条word i 与类别C j 的相关程度,互信息越大,词条word i 和类别C j 的相关程度也越大.2.2基于词条聚合的特征抽取基于词条聚合的特征抽取步骤如下.1特征抽取:计算各个词条对每类的互信息.应用特征提取理论根

11、据互信息,选取和每类相关程度大的K 个特征词条,去掉重复的词条,则由此得到的具有N 维特征空间.2为比较各个词条与每类的相关程度是否相似,先将互信息归一处理到0,1之间,处理公式为M ij =M I (word j ,C j /(max -min (6其中max ,min 分别为词条word i 对各类的互信息的最大值和最小值.3采用简单的聚类算法将与各类相关程度相似的词条进行聚类.同一类的词条聚合为同一个新的特征,这样将得到L 个新模式,其中L 远小于N.文本采用的是凝聚的层次法进行聚类.距离测量采用最常用的曼哈坦距离d (i ,j =|M i 1-M j 1|+|M i 2-M j 2|+

12、|M i S -M j S |.(7其中,S 为类别数量.将曼哈坦距离d (i ,j 小于一定阈值的模式进行聚类.聚类之后,每个聚类中的词条合并为一个特征,此特征的词频就是这些词条的词频之和.3基于词条聚合的决策树文本分类方法3.1特征表示本文采用VSM 表示文本特征,每一个文档都可以表示成空间(W i 1,W i 2,.,W i L ,其中W ij 为词条word j 在文档i 中出现频率f ij 的函数.本文使用词条在文档中的出现频率作为特征值W ij =f ij .(83.2基于词条聚合的特征抽取采用第2节中基于互信息的方法进行特征抽取.然后用词条聚合进行降维处理,得到一个较小维数的特征

13、矢量空间.3.3采用C4.5算法建立决策树并剪枝C4.56是ID3的改进,引入信息增益比克服了ID3中的最大增益偏向于多值属性的特点,并且能处理连续属性,同时在其他方面也作了改进.初始状态为全部训练样本的根结点,用C4.5算法建立决策树:1如果样本集中样本属于一个类,则作为叶子结点;或者样本集无属性可测试或样本数小于一定数量,则该样本集也作为叶子结点,所属类别为该结点中样本比例最大的类.否则,选择信息增益比最大的属性将当前结点的样本集分成左右2个样子集.2用1方法构造左右子树.本文采用根据分类错误率的事后剪枝方法.在剪枝的样本集上,计算出每个结点若被修剪后所发生的分类错误率和不被修剪时的分类错

14、误率.如果修剪可以使分类错误率变小,相应结点分支变为叶结点,并将其标记为所包含样本中类别个数最多的类别.3.4规则抽取从决策树的根结点到任一个叶结点所形成的路径就构成了一条分类规则.IF-THEN 分类规则表达方式043河北大学学报(自然科学版2005年易于被人理解.在本文所建决策树中很容易抽取规则,例如规则1:IF (金、铁、铜、矿石、提炼在文章中出现比率大于等于6.91%THEN 该文章属于冶金工业类;规则2:IF (金、铁、铜、矿石、提炼在文章中出现比率小于6.91%AND (磁力矩器、探测器、无陀螺在文章中出现比率大于等于4.15%THEN 该文章属于航空航天类.4仿真实验为了验证此文

15、本分类规则抽取方法的可行性,本文使用来源于http :/ 的800篇短文对此进行了验证.这800篇短文共分为计算机、冶金工业、环境保护、航空航天和建筑工程5大类,其中500篇作为训练样本(每类100篇,测试样本300篇(每类60篇.对所有训练样本的文本进行预处理后,得到5212个特征词条.通过互信息提取出1393个特征词条.通过词条的聚合得到了153个特征项.4.1仿真实验1采用互信息理论进行特征抽取,不采用词条聚合.采用C4.5建立决策树和根据错误分类率的事后剪枝方法,建立文本分类系统.抽取的规则数量为47个,规则最大长度为45,且分类效果也不好.实验1的文本分类结果如表1所示.表1仿真实验

16、1的文本分类结果T ab.1T ext categorization outcome of emulation experiment one计算机冶金工业环境保护航空航天建筑工程错误篇数11071023正确篇数5950535037正确率/%98.3383.3388.3383.3361.674.2仿真实验2采用互信息理论进行特征抽取,然后采用词条聚合进行降维处理.采用C4.5建立决策树和根据错误分类率的事后剪枝方法,抽取的规则数量为12个,规则最大长度为6,且分类准确率也大幅提高.实验2的文本分类结果如表2所示.表2仿真实验2的文本分类结果T ab.2T ext categorization o

17、utcome of emulation experiment tw o计算机冶金工业环境保护航空航天建筑工程错误篇数60558正确篇数5460555552正确率/%9010091.6791.6786.675结论通过对实验结果的分析可得出以下结论:1应用决策树来实现文本分类是可行的,并且决策树进行文本分类很容易抽取利于理解的分类规则;2决策树具有一定局限性,若属性维数过高,则效率低且无法取得理想的分类效果;3词条聚合大大削减了向量的维数,提高了效率和分类精度.143第3期王煜等:基于词条聚合和决策树的文本分类方法仍存在的问题:对于特征词条相似度较大的文本,词条聚合理论的应用不能明显提高分类精度.

18、此外如何提高决策树在类数较多时的分类精度也是需要进一步研究改进的问题.参考文献:1Y AN G YI -MIN G.An Evaluation Of Statitical A pproches to Text CategorizaitonJ .Information retrieval ,1999,1:69-90.2SHEN Q IAN G ,CHOUCHOULAS A.A rough-fuzzy approach for generating classification rules J .Pattern Recogonition ,2002,35:2425-24383孟庆春,王汉萍,魏天滨

19、,等.一种基于粗糙集的文本分类规则抽取方法J .青岛海洋大学学报,2003,33(6:943-949.4赵庆玉.决策树算法的研究与实现D .北京:清华大学,2000.5朱明.数据挖掘M .合肥:中国科学技术大学出版社,2002.86-97.6孔令波.基于数据仓库的大规模数据集分类数据挖掘研究与设计D .青岛:青岛大学,2002.7秦进,陈笑蓉,汪维家,等.文本分类中的特征抽取J .计算机应用,2003,23(2:45-46.T ext C ategorization B ased on Word Aggregation and Decision T reeWANG Y u 1,ZH ANG M

20、ing 1,MA Li 2(1.College of Mathematics and Computer ,Hebei University ,Baoding 071002,China ;2.Hebei University Press ,Hebei University ,Baoding 071002,China Abstract :A new method of text classifying by using the theory of word aggregation and decision tree is pre 2senteal.The decision tree is appl

21、ied to text categorization ,which has the advantages of high efficiency of data analysis and easily abstracting the categorization rules that are able to understand.However ,decision tree has a defect that is only suitable for low dimension of features.The new method establishes the vector s pace mo

22、del of term weight in terms of the theory of Pattern Aggregation ,which merges such words as a new feature that has the similar mutuality with each class ,and so largely reduces the dimension of the vector space.After that ,the decision tree is applied to text categorization.Both the advantage of de

23、cision tree and better accuracy of catego 2rization can be acquired.K ey w ords :text categorization ;mutual information ;decision tree(责任编辑:孟素兰(上接第328页Exploit of IC L 7106/7107s Function That R ange and Z ero AdjustWANG Y ong-qing 1,2,CHE N Ming-xia 1,SONG Tie-rui 1,H AO Lei 1,G AO Y ue-hua 1(1.C ollege of Electronic &Informational Engineering