（计算机应用技术专业论文）基于决策树中文文本分类技术的研究与实现.pdf

- kt h e s i sp a p e ri n t h er e s e c l a s s i f i c 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 二正 思。 学位论文储虢茁警砌 日期：抄孑7 彩 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 学位论文作者签名：芴警砌 副f 签名： 学位论文作者签名：勉。彳阎 导师签名： 签字日期：。伊8 7 石 签字日期：贻步 胂，7 莎 r 东北大学硕士学位论文摘要 基于决策树中文文本分类技术的研究与实现 摘要 随着互联网技术的迅速发展，网上的文档数据在飞速增长，在这些海量的w e b 结构页 面中蕴藏着巨大潜在价值的知识，如何快速、有效地发现潜在知识，成为数据挖掘技术 一个重要的研究方向。文本分类是w e b9 i h 识发现的一项重要的内容。有了文本分类的工 具，用户可以更加方便地阅览w e b 内容，而且通过限制搜索范围，可以在互联网上尽快 查找自己感兴趣的内容。文本分类是对信息的一种最基本的认知形式。目前的文本特征 降维算法、改进或创造适应文本数据的分类算法、抽取文本分类规则等方面的研究仍远 远不能满足实际的需要。本文主要研究文本特征空间的降维问题、决策树分类算法、决 策树剪枝及利用决策树抽取文本分类规则等问题。 本文对文本分类中所涉及的特征降维方法、决策树分类、剪枝、文本抽取规则进行 了研究。首先，针对文本特征降维提出了一种基于模式聚合和改进卡方原理的降维方法， 有效地降低文本维数并提高了分类精度；其次，在决策树常用c 4 5 分类算法上提出了 新的d c 4 5 分类算法，同时也对决策树的剪枝方法进行了改进：最后，根据对分类过程 中几处重要环节的改进，提出新的基于决策树的文本分类规则获取方法，并获得分类精 度较高且易于理解的文本分类规则。 本文首先对文本分类进行了简介，讲述了文本分类的相关技术，包括文本表示模型、 文本特征空间的降维、文本分类方法( k n n ，支持向量机，贝叶斯等) ，再次重点介绍了 决策树文本分类方法，针对决策树分类过程中特征降维、分类算法、后期剪枝等环节提 出了三种改进的方案。通过上述的改进，使用决策树进行文本分类，大大降低了建树时 f t j ，提高了分类正确率，也在一定程度上解决了利用高维属性发现规则的难题。经过测 试，表明根据改进方法实现的分类算法既有决策树易于抽取可理解舰则的优势又保证了 分类精度、提高了分类效率，具有较好的实用价值。 关键词：决策树；模式聚合；卡方原理；文本分类；剪枝方法 一i i ， 东北大学硕士学位论文 a b s t a c t t h er e s e a r c ha n di m p l e m e n t a t i o no fc h i n e s et e x tc l a s s i f i c a t i o n t e c h n o l o g yb a s e do nd e c i s i o nt r e e a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e m e tt e c h n o l o g y t h en u m b e ro fd a t af l e sg r o w s s h a r p l y t h e r ea r el o t so fk n o w l e d g ew i t he n o r m o u sp o t e n t i a lv a l u ei nt h e s em a s s i v ew e b p a g e s h o wt o i d e n t if yp o t e n t i a lk n o w l e d g eq u i c k l ya n de f f e c t i v e l yh a sb e c o m ea n i m p o r t a n tr e s e a r c hd i r e c t i o no fd a t am i n i n gt e c h n o l o g y t e x tc l a s s i f i c a t i o ni sa ni m p o r t a n t c o n t e n to fw e dk n o w l e d g ed i s c o v e r y w i t ht h et o o l so ft e x tc l a s s i f i c a t i o n ，u s e r sc a nr e a d w e bc o n t e n tm o r ee a s i l y a l s o ，b yl i m i t i n gt h es e a r c h i n gr a n g e ，o n ec a nf i n dt h ei n t e r e s t i n g c o n t e n to nt h ei n t e r n e ta ss o o na sp o s s i b l e t e x tc l a s s i f i c a t i o ni sab a s i cc o g n i t i v ef o r l t lo f i n f - o 咖a t i o n t h ec u r r e n tm e t h o d so ff e a t u r ed i m e n s i o n sr e d u c t i o n t e x tc a t e g o r i z a t i o na n d t e x tc a t e g o r i z a t i o nr u l ee x t r a c t i o na r es t i l lf a rf r o mm e e t i n gt h ea c t u a ln e e d s t h i sp a p e r m a i n l yp r e s e n t st h et e x tf e a t u r e sd i m e n s i o n sr e d u c t i o n ，t h ec l a s s i f i c a t i o n ，p r u n i n ga n dt e x t c a t e g o r i z a t i o nr u l ee x t r a c t i o nw i t ht h ed e c i s i o nt r e e i nt h i sp a p e r 。t h et e x tf e a t u r e sd i m e n s i o n sr e d u c t i o n ，t h ec l a s s i f i c a t i o n ，p r u n i n ga n dt e x t c a t e g o r i z a t i o nr u l ee x t r a c t i o nw i t ht h ed e c i s i o nt r e ea r er e s e a r c h e d f i r s t ad i m e n s i o n s r e d u c t i o nm e t h o db a s e do np a t t e r na g g r e g a t i o na n di m p r o v e dc h i s q u a r ep r i n c i p l ei s p r e s e n t e dt or e d u c et h ed i m e n s i o n a l i t ya n de n h a n c et h ec l a s s i f i c a t i o na c c u r a c ye f f e c t i v e l y t h e n an e wd c 4 5c l a s s i f i c a t i o na l g o r i t h mb a s e do nc 4 5o fd e c i s i o nt r e ei sp r o p o s e d m e a n w h i l e ，t h ep r u n i n gm e t h o do fd e c i s i o nt r e ei si r e p r o v e d a tl a s t ，b yi m p r o v i n gs e v e r a l i m p o r t a n ts t e p so fc l a s s i f i c a t i o np r o c e s s ，n e wt e x tc a t e g o r i z a t i o nr u l e sa r ee x t r a c t e db a s e d o nd e c i s i o nt r e et h a ta r eu n d e r s t o o de a s i l ya n dh a v eb e t t e ra c c u r a c yo fc a t e g o r i z a t i o n i nt h i sp a p e r ，f i r s ti n t r o d u c et h er e l a t e dt e c h n o l o g i e so ft e x tc l a s s i f i c a t i o n ，i n c l u d i n gt h e t e x tr e p r e s e n t a t i o nm o d e l ，t h et e x tf e a t u r e sd i m e n s i o n sr e d u c t i o na n dt h et e x tc l a s s i f i c a t i o n m e t h o d s ( k 】、j n ，s v m ，b a y e s ，e t c ) a g a i n ，e m p h a t i c a l l yi n t r o d u c et h et e x tc l a s s i f i c a t i o n m e t h o d sw i t hd e c i s i o nt r e e a l s o ，p r e s e n tt h r e ei m p r o v i n gm e t h o d sa i ma ts t e p ss u c ha st e x t f e a t u r e sd i m e n s i o n sr e d u c t i o n ，c l a s s i f i c a t i o na n dp r u n i n gt h r o u g hw h i c hg r e a t l yr e d u c et h e c o n s t r u c t i n gt i m eo fd e c i s i o nt r e ea n di m p r o v et h ec o r r e c tr a t eo fc l a s s i f i c a t i o n i tc a na l s o s o l v et h ep r o b l e mo fe x t r a c tr u l e sw i t hh i g hd i m e n s i o n a la t t r i b u t e t h ef o l l o w i n gt e s t i n d i c a t e st h ec l a s s i f i c a t i o na l g o r i t h mi m p l e m e n t e da c c o r d i n gt ot h ei m p r o v e dm e t h o d sn o t o n l yh a st h ea d v a n t a g eo fe a s i l ye x t r a c t i n gu n d e r s t a n d a b l e ，b u ta l s oe n s u r et h ec l a s s i f i c a t i o n a c c u r a c y ，i m p r o v et h ec l a s s i f i c a t i o ne m c i e n c ya n dh a sg o o dp r a c t i c a lv a l u e k e y w o r d s ：d e c i s i o nt r e e ；p a t t e r na g g r e g a t i o n ；c h i s q u a r ep r i n c i p l e ；t e x tc l a s s i f i c a t i o n ； p r u n i n gm e t h o d i i i ， 1 - 东北大学硕士学位论丈 目录 目录 独创性声明i 摘要i i a b s t r a c t i i i 第l 章绪论1 1 1 课题背景和意义1 1 2 研究历史与现状2 1 3 本文的研究内容4 1 4 论文的组织结构4 第2 章文本分类概述5 2 1 文本分类过程5 2 2 文本分类的关键技术6 2 2 1 特征选取6 2 2 2 阈值策略一8 2 3 文本分类方法概述9 2 3 1 基于关联规则的分类算法一9 2 3 2 贝叶斯分类1 0 2 3 3 支持向量机分类算法l o 2 3 4 粗糙集1 l 2 3 5 神经网络1 l 2 4 决策树分类算法概述1 2 2 4 1 决策树的基本概念12 2 4 2 决策树的生成一13 2 4 3 决策树的测试属性选择1 4 2 4 4 决策树的剪枝1 5 2 4 5 决策树的规则抽取1 5 2 4 6 决策树的优缺点1 6 第3 章文本分类的改进与实现1 7 3 。1 一种改进的特征降维方法1 7 一一 东北大学硕士学位论文 目录 3 1 1 改进的c h i 统计量1 8 3 1 2 基于模式聚合理论的特征降维1 9 3 1 3 关键实现2 2 3 2 决策树算法的改进2 4 3 2 1c 4 5 算法2 4 3 2 2 改进的基本思想2 5 3 2 3 算法描述与实现2 8 3 3 决策树的修剪3 2 3 3 1 修剪原则3 3 3 3 2 新的修剪方法3 4 3 3 3 修剪过程与实现3 6 3 4 基于模式聚合和决策树的文本分类规则抽取方法3 9 3 4 1 文本分类的规则抽取3 9 3 4 2 基于决策树的文本分类规则抽取4 0 3 5 本章小结4 3 第4 章实验分析4 5 4 1 聚合特征降维4 5 4 1 1 测试方法4 5 4 1 2 结果及分析4 7 4 2d c 4 5 分类算法4 8 4 2 1 测试方法4 8 4 2 2 结果及分析4 9 4 3 改进的剪枝方法5 0 4 3 1 测试方法5 0 4 3 2 结果及分析5 0上 4 4 综合测试5 2 4 4 1 测试方法5 2 ， 4 4 2 结果及分析5 2 4 5 本章小结5 3 第5 章结论与展望5 5 参考文献5 7 致谢61 一v 一 东北大学硕士学位论文第1 章绪论 1 1 课题背景和意义 第1 章绪论 目前，世界范围内的信息技术革命依然汹涌向前，正进入一个新阶段。网络技术、 数据库技术的普及和发展为信息革命提供了技术保证和平台。现在，人类的大部分信息 己经由纸质载体过渡到电子载体，而且这种过渡正在加速发展。i n t e r n e t 更是一个透明 的、覆盖全球的信息网。通过i n t e r n e t ，人们可以方便地获取世界各地的信息资源，也 可以向世界发布自己拥有的信息。这种丌放、自由的信息共享和流动方式带来了信息的 巨大积累，第五次中国互联网络信息资源数量调查报告内容显示：全国域名2 ，5 9 2 ，4 1 0 ， 全国网站数约6 9 4 ，2 0 0 个，网页数己经达到3 1 1 ，8 6 4 ，5 9 0 ，其中9 1 3 的网站提供简 体中文阅读阱1 。人们己经从一个信息匾乏的时代过渡到信息极为丰富的数字化时代。在 这些信息中，大部分是非结构化或半结构化的文本信息。用户希望获得越来越多的信息， 并能够准确有效地找到自己所需要的信息。现在的搜索引擎由于其本身的缺陷也难以满 足大部分用户的需求。要想从这些海量信息中迅速有效地获得需要的信息首先就要对这 些信息进行分门别类。文本分类( t e x tc a t e g o r i z a t i o n ) 是根据给定文本的内容，将 其判别为事先确定的若干个文本类别中的某一类或者某几类的过程，是大规模文本处理 的基本功能，也是提高其他文本处理功能和质量的有效手段，通过文本分类，人们可 以按类别进行文本存储、检索和进一步处理。现在，文本分类正在各个领域得到广泛的 应用。但是，随着信息量同趋丰富，人们对于内容搜索的准确率、查全率等方面的要求 会越来越高，因而对文本分类技术需求大为增加，如何构造一个有效的文本分类系统仍 然是信息处理的一个主要研究方向。 文本分类是特殊的数据挖掘技术，其分类技术也有着其特殊性，既需要充分利用数 据挖掘本身的原理和技术，又要为适应文本数据本身具备的主观性、不精确性、不确定 性等特点进行特殊的研究。大量的高维数据是文本数据最重要的特点，由此带来计算瓶 颈问题会使分类方法失去其实用价值“钔。并且由于文本数据的特殊结构，造成文本分类 技术中很难象数据挖掘那样抽取出易于理解的分类规则。现有的特征降维算法、改进或 创造适应文本数据的分类算法、抽取文本分类规则等课题的研究仍远远不能满足实际的 需要。因而无论在理论上，还是实践环节上，这些研究都存在巨大的发展余地。 东北大学硕士学位论文第1 章绪论 决策树分类模型之所以被广泛使用，因为决策树的分类原理简单易懂，易于生成可 以理解的规则；基于决策树的分类模型建立速度快，计算量相对来说不是很大：决策树 分类模型还可以清晰地显示哪些属性比较重要。因而可以利用决策树的特点研究文本规 则抽取。决策树用于文本处理也存在一些问题，当特征维数过高、类别过多，错误可能 就会增加得比较快，另外直接使用词频表示文本分类规则，离散化的好坏直接影响分类 规则的精度并且规则容易出现过于拟合现象。为了使其适用于文本分类规则抽取，就需 针对其缺点进行规则抽取的优化。 1 2 研究历史与现状 文本分类的研究历史可以追溯到2 0 世纪5 0 年代，美国i b m 公司的h p l u h n 提出 了词频统计思想，在这一领域进行了开创性的研究。肖明博士对此做了大量的分析和总 结：在5 0 年代后，文本分类主要经历了四个发展阶段：第一阶段( 1 9 5 8 一1 9 6 4 ) ，研究 文本自动分类的可能性；第二阶段( 1 9 6 5 1 9 7 4 ) ，进入自动分类的试验性阶段；第三 阶段( 1 9 7 5 1 9 8 9 ) ，自动分类的实用性阶段：第四阶段( 1 9 9 0 至今) ，因特网自动分类 的研究阶段心1 。 长期以来，文本分类都是自然语言处理的一个重要应用领域。但直到八十年代末， 在文本分类方面占主导地位的一直是基于知识工程的分类方法，即采用人工方式来构建 分类器，需要专业人员手工编写分类规则来指导分类。著名的国际网站y a h o o 雇用了一 百多名领域专家，即使满负荷的工作，也不能及时地对每天像潮水般涌现在互联网上的 新网页进行阅读、标注和分类。这一时期最著名的系统是为路透社( r e u t e r s ) 开发的 c o n s t r u e 系统c h u r e h 9 5 系统。九十年代以后，随着电子文本的大量出现，基于机器学 习的自动文本分类系统丌始兴起，其效果明显超过知识工程方法，成为信息系统学科最 重要的研究领域之一。目前，自动文本分类技术己经成为机器学习技术和信息检索技术 的交汇点和结合点，成为所有基于内容的自动文本管理技术的重要基础。已经提出了 多种分类方法，如k n n 、回归模型、支持向量机、最大嫡模型等，研究了一些相当成功 的分类系统，建立了o h s u m e d ，r e u t e r s 等开放的分类语料库。 但是，文本分类研究仍然缺乏一个大规模的、真实的、权威的语料库，缺乏一种客 观的评价机制，对不同方法和系统作出客观的比较。九十年代以后，情况有了很大的改 善，著名的文本检索会议( t e x t r e r t i v e a l c o n e r f e n c e ，简称t r e c ) 与主题检测和跟踪会 议( t o p i c d e t e c t i o n n a d t r a e k i n g ，简称t d t ) 都把文本分类作为重要的评测内容，通过提 一2 一 东北大学硕士学位论文第1 章绪论 供规范的大规模语料( g b 级) 对文本分类系统性能进行客观、公正的评测，来促进技术的 交流、发展和产业化。这就在很大程度上促进了文本分类研究的发展。 从文本分类的方法来看，现有的文本分类技术主要采用三种类型的方法：基于统计 的方法，基于连接的方法和基于规则的方法。 基于统计的方法本质上是一种非确定性的定量推理方法，定量是基于概率的，因此 其必然会掩盖小概率事件的发生。基于统计的方法是一种经验主义方法，其优势在于它 的全部知识是通过对大规模语料库分析得到的，可以取得很好的一致性和非常高的覆盖 率，对语言处理提供了比较客观的数据依据和可靠的质量保证。常用的基于统计的方法 有n a i v e b a y e s 、k n n 、类中心向量、回归模型、支持向量机、最大嫡模型等。 基于连结的方法，即人工神经网络，是设计来模拟人脑神经网络的，并期望其能像 大脑一样地运作，像大脑一样地学习，从而产生智慧。这种方法具有信息分布存放、运 算全局并行、处理的非线性、容错性等特点，适用于学习一个复杂的非线性映射。但是 使用它学习所形成的知识结构是人所难以理解的，系统本身对于使用的人来说就象是一 个变魔术的黑盒子，根据输入给出输出，答案j 下确但不知道是怎么算出来的。 基于规则的方法是一种唯理主义方法，本质上是一种确定性的演绎推理方法，优点 在于根据上下文对确定性事件进行定性描述，能充分利用现有的语言学成果。它成立的 前提是有大量的知识，而这些知识是人类专家总结出来的，至少解释这些知识的各种“事 实”以及对事实的解释“规则”是专家总结归纳的。由于必须有人的参与，所以对于知 识的可理解性，可读性非常重视。同时，在不确定性事件的描述，规则之间的相容性等 方面存在一些缺陷和限制。但是，有些统计方法无法解决的问题，利用舰则却很容易解 决。常用的基于规则的方法有决策树、关联规则等。 从文本分类使用的文档特征来看，不再仅仅限于词、短语或n - g r a r n ，词性、标点 符号等词法特征也被引入到了文本分类中。而且，随着研究的进一步深入，人们发现词 法特征携带的信息己经越来越无法满足文本分类技术的要求。所以，基于文本语法层次 的一些特征开始应用，但是这些特征的自动获取还是一个悬而未决的问题引。 国内文本分类的研究起步相对较晚，开始于8 0 年代初期，经历了可行性分析、辅 助分类系统和自动分类系统三个阶段n 钊。1 9 8 1 年，侯汉清首先对计算机在文献分类工作 中的应用作了探讨。到目前，国内有包括清华大学、中国科学院、复旦大学、上海交通 大学、东北大学等多家单位从事该领域的研究，已陆续研制出了一批计算机辅助分类系 统和自动分类系统，较好的是由中科院开发的智多星中文文本分类器。 一3 一 东北大学硕士学位论文第1 章绪论 1 3 本文的研究内容 本文的主要研究内容是针对决策树分类模型的不足进行改进，首先本文对文本分类 的重要概念、过程、技术进行阐述，对网页分类中所涉及的特征降维方法、文本抽取规 则进行了研究。总结了文本分类中的各种分类技术：b a y e s ( 贝叶斯) 、s v m 法即支持向 量机( s u p p o r tv e c t o rm a c h i n e ) 法、粗糙集、遗传算法、神经网络、模糊逻辑、k n n 法( k - n e a r e s tn e i g h b o r ) 等网页分类算法，并对每种技术都做出分析和评价：之后， 比较分析、重点研究了决策树分类方法及其研究进展，并对其优缺点进行了分析；提出 了一种基于模式聚合和c h i 值原理改进的文本降维方法，有效地降低文本维数并可提高 分类精度；同时针对决策树的分类算法c 4 5 进行了研究并提出了改进，改进后的算法 解决了决策树原有的过度拟合、空枝等现象；在随后的决策树剪枝环节中分析了基础误 差剪枝方法的优缺点，据此提出了新的决策树剪枝方法，更加有效地减少了决策树的形 成规模、提高了剪枝效率，增强了决策树的健壮性；最后基于对决策树分类过程中多个 环节的改进形成了新的决策树的文本分类规则获取方法，可获得分类精度较高且易于理 解的文本分类规则。 1 4 论文的组织结构 本文主要由六部分组成： 第一章介绍了文本分类技术的研究现状和研究背景。 第二章阐述了文本分类的一般过程，总结了文本分类中的各种分类技术，并对每种 技术都做出分析和评价，着重研究了决策树分类算法。 第三章对分类中所涉及的特征降维方法、分类算法、决策树剪枝、文本抽取规则进 行了研究，提出了基于模式聚合和c h i 值原理改进的文本降维方法，有效地降低文本维 数并可提高分类精度；改进了决策树常用的分类算法c 4 5 ，减少了建树时间，提高了决 ， 策树的健壮性；设计了新的决策树剪枝方法，提升了剪枝的效率与准确性；根据对决策 树分类几处关键环节的改进，提出的基于模式聚合和决策树的文本分类规则获取方法。 第四章对决策树分类环节的几处改进进行了测试，并比较、分析了测试结果。 最后一章对本文工作做出了总结，并对今后工作做出了展望。 一4 一 东北大学硕士学位论文第2 章文本分类概述 第2 章文本分类概述 本章首先介绍了文本分类的概念、过程；其次，对网页分类中所涉及的特征降维 方法、文本抽取规则进行了研究；阐述了文本分类中的各种分类技术：b a y e s ( 贝叶斯) 、 s v m 法即支持向量机( s u p p o r tv e c t o rm a c h i n e ) 法、粗糙集、遗传算法、神经网络、 模糊逻辑、k n n 法( k - n e a r e s tn e i g h b o r ) 等网页分类算法，并对每种技术都做出分 析和评价，重点研究了决策树分类方法，并对其优缺点进行了分析；据此在下一章中 提出了针对分析结果的改进文本降维方法、分类算法、剪枝方法与文本分类规则的获 取。 2 1 文本分类过程 文本自动分类可以分为训练过程和分类过程啪3 。训练过程可以看作是在己知文档类 别的情况下，统计不同类别内的词的分布，即在预先定义的类别集合c ( c = 矗，c 。，c 。) ) 和词项集合t ( t = p l ，叫一t 。) ) 的幂集之间建立一种加权映 射关系，形成一种向量表示，相应的分类器的分类过程，可以看作在已知一篇文档内所 包含词项分布的情况下，和训练中形成的每个类别向量表示进行对比，来确定该文档与 类别的隶属关系。文本分类的训练阶段和分类阶段主要包括以下几个方面： ( 1 ) 定义类别集合c = c l ，c 。，c 。 ，这些类别可以是层次式的，也可以是并列 式的。 ( 2 ) 给出训练文档集合s = ，是，s 。) ，每个训练文档s ，被标上所属的类别标志 c i 。 ( 3 ) 统计s 中所有文档的特征矢量v ( s ，) ，确定代表c 中每个类别的特征矢量v ( c f ) 。 ( 4 ) 对于测试文档集合t = p l d 。，d ，) 中的每个待分类以，计算其特征矢量v ( 攻) 与每个v ( o ) ( d c ) 之间的相似度s i r e ( 以，研) ； ( 5 ) 选取相似度最大的一个类别作为以的类别。在计算s i m ( 以，c i ) 时，最常用 的方法是考虑两个特征向量之间的夹角余弦，即： s i m ( d t ，c f ) = v ( a t ) 矿( q ) ( 矿( 以) 矿( q ) ) ( 2 i ) 在训练过程中，训练集实例经过中文分词和特征选取处理后被表示成向量形式。该 特征向量集用来描述类别模式；在分类过程中，一个待分类的中文网页经过中文分词并 一5 一 东北大学硕士学位论文第2 章文本分类概述 表示成向量后，应用分类算法同训练过程得到的类别模式逐一比较，得到候选类别列表， 然后同训练过程中得到的每个类别的阈值相比较，保留大于阈值的类别，并作为网页分 类的分类结果。 图2 1 文本分类过程 f i g2 1t e x tc l a s s i f i c a t i o np r o c e s s 2 2 文本分类的关键技术 为了实现中文网页的自动分类，通常需要关注训练分类器使用的训练样本集、特 征选取算法、分类算法、阈值策略、分类系统的性能评价值指标等方面的问题n 引。下 面将分别介绍。 2 2 1 特征选取 实现文本自动分类的基本困难之一是特征项空间的维数过高。所谓“特征项”，在 中文文本中主要指分词处理后得到的词汇，而特征项的维数则对应不同词汇的个数。 数量过大的特征项一方面导致分类算法的代价过高，另一方面导致无法准确地提取文 档的类别信息，造成分类效果不佳。因此，需要在不牺牲分类质量的前提下尽可能地 降低特征项空间的维数。”1 。“特征选取”的任务就是要将信息量小，“不重要”的词汇 从特征项空间中删除，从而减少特征项的个数，它是文本自动分类系统中的一个关键 步骤。 一6 一 东北大学硕士学位论文第2 章文本分类概述 为便于后面的描述，这罩简要给出特征选取的般过程。给定训练文档集合 d o c s = p i ，一，以 ，t e r m s = ，。，t 2 ，乙 为对d o c s 中的文档做分词后得到的词汇 全集，用 m 表示集合 1 ，2 ，m ) 。所谓“特征选取”可以看成是确定从t e r m s 到 m 的一个1 - 1 映射，即f - s e l e c t i o n ：t e r m s - m 然后根据计算丌销的考虑，取一个 i m ，认为t e r m s 中那些函数值不小于i 的词汇为“选取的特征项”作t e r m s s 。在 完成了特征选取后，分类就是基于t e r m s s ，即以其中的元素为基础，用一个向量来表 达每一个文档。分类的过程就是按照某种算法来比较待分类文档的表示向量和训练集 文档的表示向量，取最相近者所处于的类为待分类文档的类。 人们已经研究了多种特征选取方法，如：文档频率( d o c u m e n t f r e q u e n c y ，f ) 、信 息增益( i n f o r m a t i o n g a i n ，i g ) 、互信息( m u t u a l i n f o r m a t i o n ，m 1 ) 、开方拟和检验 ( x z - t e s t ，c h i ) 、术语强度( t e r m s t r e n g t h ，t s ) 等。针对英文纯文本比较研究了上 述五种经典特征选取方法的优劣啪1 。实验结果表明：c h i 和i g 方法的效果最佳：d f 方法的性能同i g 和c h i 的性能大体相当，而且d f 方法还具有实现简单、算法复杂度 低等优点；t s 方法性能一般：m 1 方法的性能最差。下面对其中几个典型的特征选取算 法做一下简单地介绍刳： d f 文档频率 d f 表示在训练集中包含某个特征项t 的文档数。这种衡量特征项重要程度方法基 于这样一个假设：d f 较小的特征项对分类结果的影响较小。这种方法优先取d f 较大 的特征项，而d f 较小的特征项将被剔除。即特征项按照d f 值排序。不过要注意，这 种策略不符合被广泛接受的信息检索理论：高频词没有低频词对文档特征贡献大。d f 是最简单的特征项选取方法，而且该方法的计算复杂度低，能够胜任大规模的分类任 务。 i n f o r m a t i o n g a i n ( i g ) 信息增益 i g 是m a c h i n e l e o i n g 领域中常用的衡量特征项重要程度的指标，d t r e e 算法中， 为每个内部结点选取最能区分这个结点所表示的训练集文档中属于某个特定的类的文 档和不属于这个类的文档的特征项使用的就是这个指标。 卡方拟合检验( c h i ) 使用m l 衡量特征项的重要程度时，只考虑到了j 下相关对特征项重要程度的影响， 其实如果t 和c 反相关，就说明含有特征项t 的文档不属于c 的概率要大一些，这对 一7 一 东北大学硕士学位论文 第2 章文本分类概述 于判断一篇文档是否不属于c 也是很有指导意义的。 定义x 2 ( f ，c ) = n ( 口d c 6 ) 2 “( 口+ c ) ( 6 + d ) ( a + 6 ) ( c + d ) ) 衡量t 对于c 的 重要程度，当t 和c 无关时，x 2 ( t ，c ) = o ；c h i 和m l 的另一个重要的区别是c h i 在 不同的特征项之间是可以比较的，而m l 不行。 可以用两种方法将特征项t 和各个类分别求出的x 2 ( f ，c ) 综合起来衡量t 的重要程 度： x 2 a v g ( t ) = p ( c 1 ) x 2 ( f ，g ) + p ( c m ) x 2 ( f ，巳) ： x 2m a x ( t ) = m a x ( x 2 ( f ，e ) ) ( i = 1 ，m ) ；( 2 2 ) 选用那种方法更好和具体的应用有关。c h i 算法的计算复杂度和f j i f 两种方法一样， 都是0 ( v m ) ，其中v 表示特征项的数目，m 表示类的数目。 2 2 2 阈值策略 对于一篇待分类文档，应用m 元分类算法通常得到多个类别。一般情况下都要求 从这些候选类别中选择部分类别为该文档的最终分类结果。这个过使用的方法通常被 称为阈值策略。下面简单介绍三个比较常见的阂值策略啪1 。 位置截尾法( r c u t ) 假设分类系统预先定义的类别数为m 。整数k 大于l 并且小于m 。对于每一个待分 类的文档d ，分类系统都返回一个长为m 的候选类列表，取候选类列表的前k 项( 按 类和文档的相似度排序) ，这篇文档就被认为属于这k 个类。这种阈值策略就被称为位 置截尾法。r c u t 方法的优点是实现非常简单，能够胜任在线分类工作。但它存在严重 的缺陷：假设待分类的文档数目为1 1 ，候选类列表的每个位置都对应m 个候选类。即 使k 变化1 ，每篇文档的类关系都要发生变化。因此，无法平滑地调整分类系统的性 能。 比例截尾法( p c u t ) p c u t 算法的基本思想是控制分入各个类的文档数，使它们保持训练集中各个类文 档数的比例关系。这种算法最大的问题是过分依赖于这种比例关系，而没有考虑类和 文档的相似度以及类在候选类列表中的位置。可以看到，p c u t 算法是以类别为中心的。 同r c u t 算法相比，p c u t 算法的系统性能比较平滑，但是不能实现在线分类。 最优截尾法( s c u t ) 一8 一 东北大学硕士学位论丈 第2 章文本分类概述 同p c u t 算法一样，s c u t 算法也是以类别为中心。假设待分类的文档数目为n ，预 先定义的类别数为i n 。系统首先计算出每篇待分类文档的候选类列表，然后生成每个 类的候选文档列表( 按类和文档的相似度排序) 。对于候选类列表里的每一个类，如果 这篇文档和这个类的相似度大于这个类的最优截尾相似度，那么这篇文档就属于这个 类。否则，这篇文档就不属于这个类，其中，每各类的最优截尾相似度是这样预先取 得的：将训练集分成两部分，其中一部分仍然作为训练集，另一部分作为测试集，在 这个测试集下对于这个类的分类性能，调整截尾相似度，使得系统的性能达到最优， 此时截尾相似度的值就是这个类的最优截尾相似度。s c u t 算法性能比较优异，但是不 能很好地处理那些稀有类别( 就是比较少见的类别) 。 2 3 文本分类方法概述 文本分类方法主要包括基于传统技术的决策树、k 最近邻( k n n ) 【1 7 】、关联规则、 支持向量机( s v m ) 【”1 、基于数据库的算法、贝叶斯等分类算法和基于软计算的神经 网络、 r 糙集、模糊逻辑和遗传算法。其中，基于软计算的方法通过协同工作提供一 种灵活的数据处理能力，其目标是实现对不精确、不确定、部分信息的处理能力和近 似推理能力，以求能方便、稳健、低代价地逼近人类的分析判断能力。模糊逻辑提供 处理由于模糊而不是随机产生的不精确、不确定性的算法，粗糙集则处理由于不可分 辨关系导致的不确定性，神经网络用于模式分类与聚类，而遗传算法则用于优化和搜 索f 9 l o 2 3 1 基于关联规则的分类算法 关联规则挖掘是当前数据挖掘中一个重要而又活跃的研究领域。关联规则挖掘就 是从大量的数掘中挖掘出有价值描述数据项之间相互联系的有关知识。近年来，已开 始将关联挖掘方法应用到分类方法中。基于关联规则的分类方法，称为关联分类【1 6 1 。 基于关联规则( c b a ：c l a s s i f i c a t i o nb a s e do n a s s o c i a t i o nr u l e ) 的分类算法分两个步骤 构造分类器。第一步利用标准关联规则挖掘算法挖掘出有关的关联规则，即右部为类 别属性值的类别关联规则( c l a s s i f i c a t i o na s s o c i a t i o nr u l e s ：c a r ) ；第二步从已发现的 c a r 中选择高优先度的规则来覆盖训练集，也就是说，如果有多条关联规则的左部相 同，而右部为不同的类，则选择具有最高置信度的规则作为可能规则。c b a 算法主要 是通过发现训练集中的关联规则来构造分类别2 。关联规则的发现的经典算法是 一9 一 东北大学硕士学位论文 第2 章文本分类概述 a p f i o f i 算法。此算法的优点是其分类准确度较高，主要缺点是当