（管理科学与工程专业论文）基于决策树和k最近邻算法的文本分类研究.pdf

中文摘要 文本分类是文本挖掘的重要内容，是对信息的一种最基本的认知形式。目前 的文本特征降维算法、改进或创造适应文本数据的分类算法、抽取文本分类规则 等方面的研究仍远远不能满足实际的需要。本文主要研究了文本特征空间的降维 问题、利用决策树抽取文本分类规则问题和改进k n n 算法以适应文本分类问题。 本文提出了三种特征降维方法：一种是基于模式聚合和改进z2 统计量的文 本降维方法，有效地降低文本维数并可提高分类精度：种是基于c h i 值原理 和粗糙集理论的属性约减的文本降维方法，据此提出的基于决策树的文本分类规 则获取方法，可获得分类精度较高且易于理解的文本分类规则；第三种是基于神 经网络的特征抽取方法，此方法根据灵敏度将特征进行排序，采用二分法的方式 去掉部分特征，降低了神经网络特征提取的计算量。 本文提出了两种基于模糊决策树的模糊文本分类规则抽取方法。第一种方法 采用分枝合并减少了分类规则，第二种方法提出了一种基于类信息熵和密度分布 函数的数据模糊化方法，降低了数据模糊化的工作量和模糊决策树的规模，减少 了分类规则数量。 本文关于k n n 算法的改进主要做了三个方面的工作： 欧氏距离中的权重求解问题：提出了两种权重求解方法。一种采用灵敏度方 法获得每个文本特征对分类作用的权重，并且在距离公式中又加入了同一特征对 不同文本类的分类作用的权重；第二种是基于c h i s q u a r e 距离理论的权重求解方 法，首先根据s s t r e e 划分的区域查找近似i ( 0 个最近邻，根据k 0 个最近邻和 c h i s q u a r e 距离理论计算权重。这两种方法都可以提高k n n 算法的分类精度。 提高k 个最近邻查找速度：提出了一种快速查找精确k 个最近邻的算法 t f k n n ，预先建立s s r t r e e ，s s r - t r e e 的每个非叶子结点的孩子按照其距父结 点中心点的距离排序。根据这棵树进行k 个最近邻的查找，只需在满足一定条 件内的部分样本中查找k 个最近邻，从而减小了查找范围，大大降低了相似度 计算量。 裁减样本库：提出了一种k n n 算法中的训练样本库的裁减维护方法，首先 采用c u r e 算法对训练样本库进行聚类，获得每个聚类的代表样本组成新的训 练样本集合，然后用t a b u 算法对此样本集合进行进一步维护。此算法不仅极大 缩减样本库裁减的工作量，且使k n n 算法的分类速度和分类精度都得到了提高。 关键词：文本分类决策树k n n 算法模糊逻辑粗糙集理论神经网络 a b s t r a c t t e x tc a t e g o r i z a t i o ni so n eo ft h em o s ti m p o r t a n ti s s u e so ft e x tm i n i n g ，w h i c hi s t h o u l g h ta sab a s i cc o g n i t i o n a lf o r m t h er e s e a r c h e so nt h em e t h o d so ff e a t u r e d 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 dt 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 nh a v e n o ts a t i s f i e dt h ea c t u a la p p l i c a t i o n ss of a r i nt h i sp a p e r , t h et e x tf e a t u r ed i m e n s i o n s r e d u c t i o na n dt 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 nu s i n gd e c i s i o nt r e ea r ei n v e s t i g a t e d ， a n ds o m en e wk n n a l g o r i t h m sa r er e p r e s e n t e df o rt e x tc a t e g o r i z a t i o n i nt h i sp a p e r , t h r e em e t h o d sf o rt e x tf e a t u r ed i m e n s i o n sr e d u c t i o na r ep r e s e n t e d ： t h ef i r s tm e t h o dr e d u c e st h ed i m e n s i o n sb a s e do np a t t e r na g g r e g a t i o nt h e o r ya n da l l i m p r o v e dz 2s t a t i s t i c ，a n dt h e nt h e b 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 ni sa c q u i r e d ；t h e s e c o n dm e t h o dr e d u c e st h ed i m e n s i o n sb a s e do nt h ec h iv a l u ea n dr o u g hs e t , a n d t h e nt 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 do nd e c i s i o nt r e et h a ta r eu n d e r s t o o d e a s i l ya n d h a v eb e a e r a c c u r a c yo fc a t e g o r i z a t i o n ；t h et h i r d o n er e d u c e st h e d i m e n s i o n sb a s e do ut h en e u r a ln e t w o r kt h e o r y , r a n k e df e a t u r e su s i n gas e n s i t i v i v y m e t h o da n ds e l e c t st h ef e a t u r e su s i n gd i c h o t o m ym e t h o d ，t h e nt h en u m b e ro ft h e d i m e n s i o n si sr e d u c e dw h i c ha v o i d sh u g ec o m p u t a t i o no f n e u r a ln e t w o r k t w om e t h o d sf o rt e x tc a t e g o r i z a t i o nf u z z yr u l ee x t r a c t i o na r ep r e s e n t e db a s e do n f u z z yd e c i s i o nt r e e t h ef i r s tm e t h o dp r e s e n t saf u z z yd e c i s i o nl a - e ew i t hm e r g i n g s o m eb r a n c h e s ，t h e nt h en u m b e ro fc a t e g o r i z a t i o nr u l ei sr e d u c e dl a r g e l yb e c a u s eo f m e r g i n gs o m eb r a n c h e s ；i nt h es e c o n dm e t h o d ，an c wm e t h o df o rc o n s t r u c t i n g m e m b e r s h i pf u n c t i o n si sp r e s e n t e d ，w h i c hr e d u c e st h et i m eo fd a t af u z z i f i c a t i o n l a r g e l y , r e d u c e s t h en u m b e ro fr u l e sa n di n c r e a s e s c a t e g o r i z a t i o na c c u r a c y c o n s e q u e n t l y i nt h i sp a p e r ，t h r e em e t h o d sa r ep r e s e n t e dt oi m p r o v et h ek n n a l g o r i t h m ： a c q u i r ew e i g h t so fe u c l i dd i s t a n c ef o r m u l a ：t w om e t h o d sa r ep r e s e n t e d f i r s t l y , w e i g h t so fe v e r yf e a t u r ea r ea c q u i r e db a s e do nas e n s i t i v i t ym e t h o d t h e nt h em e t h o d c o n s i d e r st h ed i f f e r e n tf u n o t i o n so ft h es a m ef e a t u r eo nd i f f e r e n tc l a s s e si ne u c l i d d i s t a n c ef o r m u l a t h eo t h e rm e t h o di sb a s e do nc h i s q u a r ed i s t a n c et h e o r y f i r s t , k o a p p r o x i m a t en e a r e s tn e i g h b o r sa r ea c q u i r e db a s e do ns st r e e t h e nw e i g h t sa r e c o m p u t e db a s e do nk 0a p p r o x i m a t en e a r e s tn e i 【g h b o r sa n dc h i - s q u a r ed i s t a n c et h e o r y b o t hm e t h o d sc a ni m p r o v et h ea c c u r a c yo f k n n a l g o r i t h m q u i c k e nt h es p e e do fs e a r c h i n gk n e a r e s tn e i g h b o r s ：am e t h o di sp r e s e n t e dt o s e a r c ht h ee x a c tkn e a r e s tn e i g h b o r sq u i c k l y f i r s t , as s rt r e ef o rs e a r c h i n gkn e a r e s t n e i g b b o r si s c r e a t e d i nt h es s rt r e e ，c h i l d r e na r a n k e db a s e do nt h ed i s t a n c e b e t w e e ni t s e l fa n dt h ee e n t r i o do ft h e i rd a 化n t t h ea p p r o a c hn e e dn o ts e a r c hk n e a r e s tn e i g h b o r si na l ls a m p l e sb a s e do nt h et r e e t h e r e f o r e ，t h es e a r c h i n gs c o p ei s r e d u c e d ，s u b s e q u e n t l yt h et i m eo f s i m i l a r i t yc o m p u t i n gi sd e c r e a s e dl a r g e l y , p r u n et r a i n i n gs a m p l e s ：am e t h o di sp r e s e n t e dt op r u n et r a i n i n gs a m p l e sf o rk n n a l g o r i t h m f i r s t , r e p r e s e n t a t i v es a m p l e ss e to ft r a i n i n gs e t sa a c q u i r e db a s e do n c r u ec l u s t e r i n ga l g o r i t h m t h er e p r e s e n t a t i v es a m p l e ss e ti st a k e na st h ei n i t i a ls e t o ft a b ua l g o r i t h mt of u r t h e rm a i n t a i n ，t h em e t h o do n l yc o n s i d e r st h es a m p l e sa t d i f f e r e n tc l a s s e sb o r d e r sw h e ns a m p l e sa r ei n s e r ti n t on e w t r a i n i n gs e t t h ew o r ko f p r u n i n ga n dm a i n t e n a n c et r a i n i n gs a m p l e ss e ti sd e c r e a s e dl a r g e l y b o t hs a t i s f i e d s p e e da n da c c u r a c yo f c l a s s i f i c a t i o nc a l lb ea c q u i r e d k e yw o r d s ：t e x tc a t e g o r i z a t i o n ，d e c i s i o n 慨k n na l g o r i t h m ，f u z z yl o g i c 。 r o u g h s e tt h e o r y ，n e u r a ln e t w o r k m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨盗盘堂或其他教育机构的学位或证 书而使用过的材料。与我同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：王随签字日期：如o f 年厂月91 9 学位论文版权使用授权书 本学位论文作者完全了解苤鲞盘堂有关保留、使用学位论文的规定。 特授权叁叠盘茔可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：土必要 签字日期：l 口口厂年6 月9 日 导师签名： 签字日期： 天津大学博士学位论文 第一章绪论 第一章绪论 本章首先介绍了选题的研究背景和意义；然后对文本挖掘的重要概念、过程、 技术进行阐述，总结了文本挖掘中的各种分类技术，并对每种技术都做出分析和 评价；之后，重点研究了决策树分类方法和k n n 分类方法及其研究进展，并对 其优缺点进行了分析；最后指出了本论文的主要工作和创新点。 1 1 选题的研究背景和意义 近年来，人们利用信息技术生产和搜集数据的能力大幅度提高，无数个数据 库被用于商业管理、政府办公、科学研究和工程开发等。这样的形势在发展延伸， 于是新的挑战摆在了世人面前：在信息爆炸的时代，信息过量几乎成为人人需要 面对的问题。如何才能不被信息的汪洋大海所淹没，从中及时发现有用的知识， 提高信息利用率呢? 面对“人们被数据淹没，人们却饥饿于知识”的挑战，数据 挖掘技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。 数据挖掘( d a t am i n i n g ) 起源于2 0 世纪9 0 年代中期，是一个年轻又活跃的 研究领域，是多门学科和多门技术相结合的产物。数据挖掘就是从大量的、不完 全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道 的、但又是潜在有用的信息和知识( 如规则、规律、模式、约束等) 的过程。发 现和利用隐藏在数据集背后知识的数据挖掘成为新兴研究方向，成为知识发现过 程中的核心和关键步骤【i 翔。在现实世界中，知识不仅以传统数据库中的结构化 数据的形式出现，而且以诸如书籍、研究论文，新闻文章、w e b 页面及电子邮件 等各种各样的形式出现。由于在这些非结构化的数据源中也存在着大量的知识， 因此也应该在这些数据源上进行数据挖掘，提取感兴趣的、潜在的有用模式和隐 藏的信息，这项工作就是文本挖掘。文本挖掘是从大量文本中发现新的知识，进 行文本处理的研究领域。文本挖掘已经成为了数据挖掘中的一个日益流行的重要 研究课题。 文本挖掘通过分析文本提取出对特定需求有用的信息f 3 】，是一种智能化的工 具。它能够抽取出的有价值知识，可用来更好地组织信息，它能够使人们免于陷 入信息的汪洋之中，从大量冗余的信息中迅速发现对自己有用的信息，还在一定 天津大学博士学位论文第一章绪论 程度上揭示信息与信息之间的关联，产生出用户以前未曾意识到的有用信息。而 传统的信息检索软件所查询的信息可能仅仅从字面上符合查询要求，并不是人们 真正需要的信息。文本挖掘技术能够根据用户的实际需要挖掘相关联，有价值、 以及用户以前未曾注意的有用信息。 国际上也提出了多项文本挖掘计划，以期对网上“堆积如山”的巨大的信息 矿床进行有效的过滤、开发与综合利用，把信息变成能够方便利用的知识和财富。 n i s t 和d a r p a 组织的t r e c 会议是国际上文本挖掘领域的著名评测会议，从 1 9 9 2 年起每年召开一次。1 9 9 1 - 1 9 9 8 年，d a r p a 资助了t i p s t e r 文本计划， 主要着跟于三项基础技术的评测：文档检测、信息提取、摘要。由此可见，对海 量网络信息的有效处理和深层次综合利用离不开文本挖掘技术，文本挖掘将成为 人们应对信息时代挑战的强大利器之一【4 】。 文本挖掘中最基本的两项工作就是分类和聚类，几乎在所有文本挖掘的应用 领域都离不开文本的分类和聚类。文本分类是文本挖掘的一个重要内容，是指按 照预先定义的主题类别，为文档集合中的每个文档确定一个类别1 5 。通过自动文 本系统把文档进行归类，可以帮助人们更好地寻找需要的信息和知识。在人们看 来，分类是对信息的种最基本的认知形式。传统的文献分类研究有着丰富的研 究成果和相当的实用水平。但随着文本信息的快速增长，特别是i n t e r n e t 上在线 文本信息的激增，文本自动分类已经成为处理和组织大量文档数据的关键技术。 现在，文本分类正在各个领域得到广泛的应用。但是，随着信息量日趋丰富，人 们对于内容搜索的准确率、查全率等方面的要求会越来越高，因而对文本分类技 术需求大为增加，如何构造一个有效的文本分类系统仍然是文本挖掘的一个主要 研究方向。 文本挖掘【6 1 作为特殊的数据挖掘，其分类技术也有着其特殊性，既需要充 分利用数据挖掘本身的原理和技术，又要为适应文本数据本身具备的主观性、不 精确性、不确定性等特点进行特殊的研究。大量的高维数据是文本数据最重要的 特点，由此带来计算瓶颈问题会使分类方法失去其实用价值。并且由于文本数据 的特殊结构，造成文本分类技术中很难象数据挖掘那样抽取出易于理解的分类规 则。现有的特征降维算法、改进或创造适应文本数据的分类算法、抽取文本分类 规则等课题的研究仍远远不能满足实际的需要。因而无论在理论上，还是实践环 节上，这些研究都存在巨大的发展余地。 决策树分类模型之所以被广泛使用，因为决策树的分类原理简单易懂，易于 生成可以理解的规则：基于决策树的分类模型建立速度快，计算量相对来说不是 很大；决策树分类模型还可以清晰地显示哪些属性比较重要。因而可以利用决策 天津大学博士学位论文 第一章绪论 树的特点研究文本规则抽取。决策树用于文本挖掘也存在一些问题，当特征维数 过高、类别过多，错误可能就会增加得比较快，另外直接使用词频表示文本分类 规则，离散化的好坏直接影响分类规则的精度并且规则容易出现过于拟合现象。 为了使其适用于文本分类规则抽取，就需针对其缺点进行规刚抽取的优化。 k n n 方法思路非常简单直观，易于实现；不需要产生额外的数据来描述规 则，它的规则本身就是数据( 样本) ；它允许训练样本库存在噪音；在类别决策 时只与极少量的相邻样本有关，可以较好地避免样本数量的不平衡问题。但同时 k n n 也存在分类过程中相似度计算量过大、对样本库过于依赖和相似度的度量 函数不适用等问题。为了使其适用于文本分类，就需针对其缺点对k n n 分类算 法进行改进。 1 2 文本挖掘概述 文本挖掘是数据挖掘的一个分支，是以文本型信息源作为挖掘对象，利用定 量计算和定性分析的办法，从中寻找信息的结构、模型、模式等隐含的具有潜在 价值的新知识的过程。由于文本类型数据的快速增长，文本挖掘的重要性也日益 增加。 文本挖掘是利用智能算法，如神经网络、基于案例的推理、可能性推理等， 并结合文字处理技术，分析大量的非结构化文本源( 如文档、电子表格、客户电 子邮件、问题查询、网页等) ，抽取或标记关键字概念，文字间的关系，并按照 内容对文档进行分类，获取有用的知识和信息。文本挖掘的早期研究是信息检索， 包括了基于关键字检索和全文检索，而现在的文本挖掘则是分析和发现大量非结 构化文本中的关系。 文本挖掘具有广泛的应用前景，它不仅可以用于企业的有决策需求的业务部 门，也可以用于提供综合信息服务的网站。从企业角度来看，在当今社会任何一 个企业都不能只关注企业内部的情况，必然要关心竞争对手、合作伙伴、市场变 化等企业外部环境，而i n t e r n e t 网络是获取这些信息的最好途径。文本挖掘便可 帮助企业员t ( 尤其是需要实时有效信息的决策部门) 获取最新的、来自世界范 围的、自己所感兴趣的文档信息，并在此基础上进行分析和进一步的利用。具体 说来，文本挖掘的应用可以概括成电子邮件管理、文档管理、在客户自动问答系 统中的应用、市场研究和情报收集等方面的应用。 天津大学博士学位论文第一章绪论 1 2 1 文本数据的特点 文本挖掘是以文本型信息源作为挖掘对象，文本信息是半结构化和非结构化 的数据。这些文本信息有着自己的特殊性，因而造成了文本挖掘的困难。 文本数据的特点可以从七个方面来描述i s ： ( 1 ) 半结构化或者无结构化 文本数据是半结构化或者无结构的数据。比如h n n l 文本是半结构化的数据， 而f r e et e x t 是无结构化的数据，它们具有很强的非线性的特征，很难用传统模型 来描述，也就不能采用传统的方法进行处理。 ( 2 ) 高维数据 文本数据是高维数据，这是文本数据最重要的特点。文本特征向量的维数一 般都可以高达上万维，一般的数据挖掘、数据检索的方法由于计算量过大或代价 高昂而失去可行性。因而特征空间的降维也成为文本挖掘的一个关键。 ( 3 ) 大数据量 文本数据通常具有很大数据量，即使一般用于文本检索的文本库也会有至少 数千个文本样本，对这些文本进行处理的工作量是非常庞大的。因而文本处理必 须是自动化或者半自动化，手工方法不可行。 ( 4 ) 时变数据 文本数据由于会随着时间不断增加数据量，这些数据不只带来数据量的变 化，同时也加入新的信息。因此，文本处理方法应该可以处理随时间变化的文本， 即随时间变化可以更新原有文本和接纳新的文本，具备学习能力( 尤其是无监督 学习) ；要求具备长期记忆能力、短期记忆能力，详细模式记忆和粗略模式记忆 等多种记忆功能。 ( 5 ) 语义性 文本数据具有语义性特点，比如文本检索本身是语义检索，由于一词多义、 多词一义，在时间和空间上的上下文相关等情况。文本检索本身就具有内在相关、 非确定性、非精确性等特点，传统的严格关键词布尔检索方法难于适应具有上述 特点的文本检索，因而有必要在检索词表示、文本表示、匹配算法等各方面进行 语义性扩充。 ( 6 ) 无标签 文本数据是无标签数据，一般需要进行处理后才可以进行分类、检索等相关 操作。 ( 7 ) 分布式 文本数据类型多样、来源多样，这使得文本收集之后，处理前一般都需要预 天津大学博士学位论文第一章绪论 处理操作，比如：对于h t r n l 类型的文本文件，一般的预处理步骤为去除h t m l 的 语法标签。 文本数据这样的特点就造成一般的数据挖掘的方法在文本挖掘中的不可行。 文本挖掘中莹须研究解决文本表示方法、有效的特征空间的降维方法、改变现有 方法以适应高计算量、高资源消耗的文本处理特点，并且算法应具有很强的学习 能力和鲁棒性。文本挖掘是多学科交叉的研究课题，包括数据挖掘、机器学习、 统计学、自然语言处理、信息抽取、可视化技术、数据库技术等。 1 2 2 文本挖掘的功能 文本挖掘可以对文本数据的内容进行总结、分类、聚类、关联分析、分布分 析以及趋势预测等【9 ，1 们。文本挖掘的功能主要包括： ( 1 ) 文本总结 文本总结是指从文档中抽取关键信息，用简洁的形式对文档内容进行摘要或 解释。文本总结在有些场合十分有用，例如，搜索引擎在向用户返回查询结果时， 通常需要给出文档的摘要。 ( 2 ) 文本分类 文本分类是指按照预先定义的主题类别，为文档集合的每个文档确定一个类 别。用户不但能够方便地浏览文档，而且可以通过限制搜索范围来使文档的查找 更为容易。利用文本分类技术可以对大量文档进行快速、有效的自动分类。 ( 3 ) 文本聚类 文本聚类的目标是将文档集合分成若干个簇，要求同一簇内文档内容的相似 度尽可能地大，而不同簇间的相似度尽可能地小。可以利用文本聚类技术将搜索 引擎的检索结果划分为若干个簇，用户只需要考虑那些相关的簇，大大缩小了所 需要浏览的内容。 ( 4 ) 关联分析 关联分析是指从文档集合中找出不同词语之间的关系。b r i n 提出了一种从大 量文档中发现一对词语出现模式的算法f “j ，并用来在w e b 上寻找作者和书名的 出现模式，从而发现了数千本在a m a z o n 网站上找不到的新书籍。 ( 5 ) 分布分析 分布分析是指通过对文档的分析，得到特定数据在某个历史时刻的分布情 况。如f e l d m a n 等人使用多种分布模型对路透社的两万多篇新闻进行了挖掘，得 到主题、国家、组织、人、股票交易之间的相对分布【1 2 】。 ( 6 ) 趋势预测 天津大学博士学位论文第一章绪论 趋势预测是指通过对文档的分析，得到特定数据将来的取值趋势。如 w u t h r i c h 等人通过分析w e b 上出版的权威性经济文章，对每天的股票市场指数 进行预测，取得了良好的效果【1 3 】。 1 2 3 文本挖掘的过程 尽管文本挖掘的过程与领域信息密切相关，但总体上，其过程如图1 - l 所示， 一般经过特征提取箱；征表示、特征选择、模式获取和结果评价四个阶段。 ( 1 ) 特征提取 寺征表示 要从文本中提取适当的特征，将文本表示成计算机能够理解的数字形式。 文档集合 图1 1 文本挖掘的过程 有用模式 ( 2 ) 特征选择 在目前所采用的文档表示方法中，存在的一个共同的不合人意的地方，这就 是文档特征向量具有惊人的维数，使得特征子集的选取成为文本挖掘过程中必不 可少的一个环节。 ( 3 ) 模式获取 模式获取即采用各种文本挖掘方法发现隐藏的知识模式，以满足用户评价标 准的模式最终输出，成为指导人们实践的有用知识。 ( 4 ) 结果评价 最后对获取的知识模型进行质量评价。若评价结果满足一定的要求，则存储 该知识模式：否则就返回到以前的某个环节，分析改进后进行新一轮的挖掘工作。 为了客观地评价文本挖掘的效果，人们提出了很多评测方法，比较常用的有准确 率( p - p r e c i s i o n ) 、召回率( r r e c a l l ) 和f 。- m e a s u r e 等。 1 2 4 文本挖掘面临的课题 在许多其它领域中提出的数据挖掘算法主要针对结构化数据，而文本数据是 半结构化或无结构化数据。并且现在文本挖掘要处理的文本集合可能非常巨大。 因而，文本挖掘面临许多新的研究课题，最主要的有： 天津大学博士学位论文 第一章绪论 ( 1 ) 文本的表示 文本挖掘处理的是自然语言表示的文本，缺乏计算机可理解的语义，需要把 文本表示为计算机可读的一种中间形式。目前。虽然自然语言处理领域的研究己 取得很大进展，但还没有一种能够完全表示文本语义的中间形式。对于不同的挖 掘目的，也需要使用不同复杂度的中间表示形式。对于细粒度的，领域特定的知 识发现任务，需要进行语义分析，以得到足够丰富的表示，抓住文本中对象或概 念之间的关系。但是语义分析计算量大，如何使计算机更快地进行语言分析并对 于大文本集合具有可扩展性是一个挑战性的问题 ( 2 ) 特征空间降维问题 通常的向量空间文本表示法中，维数很容易达到成千上万维。过高的文本空 间维数会导致挖掘所需要的空间异常增大，时间代价也非常高昂，而且现有的挖 掘算法很多属于非增量算法，要求一次性将数据读入内存进行处理，过高的维数 势必限制挖掘算法的实际应用。因此降维问题始终是文本挖掘的一个关键问题。 ( 3 ) 文本相似性度量问题 在各类文本挖掘和检索技术中，一般使用欧氏距离来计算文本向量之间、检 索词向量之间、检索词向量和文本向量之间的相似程度。欧氏距离是距离空间中 最典型的距离衡量方法，但这种经典方法却不适应于文本向量之间距离的度量。 文本特征空间是个非常复杂的空间结构，其中既有代表最细化概念的点，也有代 表上层概念的平面，甚至是超平面或者超曲面，而各个坐标之间也并不是平等的， 对于概念之间的语义联系莛着不同程度的作用。而经典的欧氏距离应用的前提条 件是每个坐标对于计算欧氏距离起着相同的作用，很明显欧氏距离并不适合计算 文本向量之间的距离，按照欧氏距离进行计算会导致空间形状的扭曲和变形，仿 照多元统计分析的方法，可以采用旋转和标准化的方法建立一正定二次型作为欧 氏距离的变形量度，但是对于大样本和高维空间，其计算量是非常庞大的。( 内 积或者余弦计算同样存在类似的问题) 。因而各维特征权重的获取算法研究或新 的相似性度量标准也是文本挖掘领域的重要研究方向。 ( 4 ) 大规模文本集合 i n t e r a c t 的发展，电子商务和数字图书馆的兴起和广泛应用，永久存储设备 价格的不断降低，所有这些都使得各公司各机构储存的文本信息的规模越来越 大，电子文本库中文本数量达几十万，几百万之多。对如此之大的文本集合进行 处理，必须有快速高效的文本挖掘算法才能与之相适应。 ( 5 ) 模式的理解和可视化显示 在许多应用中，发现的模式的可理解性对于用户来说是很重要的，提高可理 天津大学博士学位论文第一章绪论 解性的解决方法通常包括以图形方式显示结果，提供相对少量的规则，或者生成 自然语言以及利用可视化技术等，以提供更友好的用户界面。而目前的文本挖掘 系统主要针对有经验的专家，一般人很难使用。抽取出易于理解的模式也是文本 挖掘中的一个难题。 ( 6 ) 一词多义和多词一义问题 克服多词一义问题，目前主要采用同义词字典，但同义词词典的建立、维护 代价甚高，并且涉及多语种问题：对一词多义问题尚缺乏有效的解决手段；另一 方面一词多义和多词一义是不可分离的，不解决一词多义也很难解决多词一义。 ( 7 ) 跨语言问题 数据挖掘算法是以数据库中的结构化数据作为输入的，是语言独立的，而文 本挖掘是以自然语言的文本作为输入的，依赖于自然语言。由于自然语言的多样 性，各种语言各有其特点，在一种语言中有效的文本挖掘功能却很可能不适用于 其他语言。待处理的文本集合中可能存在多种语言写成的文本。因此，文本挖掘 功能要考虑到能够在多种语言之间进行语义转换，这需要一个语言模型及系统的 方法，这将构成跨语言文本挖掘的重要部分。 ( 8 ) 算法的选择 面对多种多样的文本挖掘算法，各种算法各有其特点，如何从中选择一种适 合于具体应用的算法是一个尚待研究的问题。 ( 9 ) 领域知识集成 当前的文本挖掘系统大都未采用领域知识，领域知识很有用，可以提高文本 分析效率，有助于取得更紧凑的表示形式等。因此，需要考虑把领域知识集成到 文本挖掘系统中。 o 毋中文文本分词技术 在印欧语系语言中，词与词之间有空格作为固定的分隔符，因此容易进行分 词。而在中文中，词与词之间没有分隔符，一个句子是由一串连续的汉字组成， 加之汉语中的词具有不同的长度，相同的字可出现在许多不同的词中，还有许多 词是由单个字组成，这使得中文分词是一项很难的工作，需要快速有效的技术。 1 3 文本分类的主要技术 1 3 1 文本表示模型 文本挖掘处理的是自然语言表示的文本，是无结构或半结构化数据，缺乏计 天津大学博士学位论文第一章绪论 算机可理解的语义。在进行文本挖掘之前，需要对文本进行预处理、特征提取， 从而把文本表示为计算机可读的一种中间形式。 表示文本的第一步是要从文本数据中提取能表示该文本的特征。要表示好文 本，就要寻找最有代表性的文本特征。文本的特征应该不仅能够对文本进行充分 表示，并且要反映出文本在特征空间中的分布，具有较为明显的统计规律，还要 注意文本映射到特征空间的计算复杂度不太大。 文本挖掘中常用的文本特征有字、词或短语等。概念也可以作为特征，“电 脑”和“计算机”具有同义关系，在计算文档的相似度之前，可以将两个词映射 到同一个概念类，从而增加匹配的准确度。但是概念的判断和处理相对复杂，自 然语言中存在同义、近义、从属和关联等各种关系。如何很好地划分概念特征、 确定概念类，以及概念类的数量都是需要通过反复尝试和改进来解决的问题。 在实际应用中，到底选择何种特征来表示文本需要结合处理速度、精度要求、 存储空间等方面的具体要求来决定。常见的文本表示模型有向量空间模型、概率 模型和语言模型等。 经典的文本表示模型是向量空间模型( v s i f - v e c t o rs p a c em o d e l ) ，由 s a l t o n 等人于6 0 年代末提出，并成功地应用于著名的s m a r t 文本检索系统“”。 向量空阀模型对文本进行简化表示，认为特征之间是相互独立的而忽略其依赖 性，将文档内容用它所包含的特征词来表示。除了向量空间模型之外，s t e p h e n r o b e r t s o n 和s p a r kj o n e s 等人提出的概率模型也得到了人们的广泛认可。该 模型综合考虑了词频、文档频率和文档长度等因素，把文档和用户兴趣( 查询) 按照一定的概率关系融合，形成了著名的o k a p i 公式“”。该模型在信息检索领 域取碍了成功。 目前文本分类中，绝大部分仍然采用经典的向量空间模型。向量空间模型表 示文本通常包括分词，取词根，去掉功能词，统计词频，选择特征，生成频数向 量，赋权，规范化等步骤。向量空间模型中，文本空间被看作是由组正交词条 向量所张成的空间，每一个词条称为一个特征项，每一个文本d 则表示为空间内 的一个向量或者空间点，一般表示为： d = ( w ( t j ) ，w ( t 2 ) ，w ( 0 ) ) ( 卜1 ) 其中f ，为文本空间的词条，肌为文本空间的维数，特征表示中的w ( ) 是函数， 其基本功能是计算词条f 。在文本向量中的权重，函数的自变量是词条在文本中的 出现频率和在整个文本集中出现的频率，可以认为函数w ( 由2 部分组成： w ( ) = l g _ ，) c ( o ( 1 - 2 ) 第一部分为局部权值l ( 力，表示第i 个词在第，篇文本中的权重，第二部分 天津大学博士学位论文第一章绪论 为全局权值c ( 力，其为第f 个词在整个文本集中的权重。设t 乇和北表示第f 个词 在第_ ，篇文本中出现的频度和在整个文本集中出现的频度，行为文本集文本总 数，常见的局部权值公式l ( i ，j ) 有： 词频法； 布尔函数法； 平方根法： 对数词频法 l o g ( t f i j + n 常见的全局权值公式c ( o 有： n o r m a l 法： i d f 法： e n 仃o p y 法： l o g ：( 争+ l ，f i f 0 ，l o g ( d 熹，) ，一莩苜 j 1 。e v ， 1 3 2 文本特征空间的降维 ( 1 - 3 ) ( 1 - 4 ) ( 卜5 ) 0 - 6 ) ( 1 - 7 ) ( 1 - 8 ) ( 1 - 9 ) 文本降维算法成为文本挖掘研究的主要趋势之一。自然语言文本集中往往包 含大量的词汇。如果把这些词都作为特征，将带来一系列问题。首先是特征空间 维数过高，给计算带来了巨大压力：占用存储空间大、处理速度慢。其次是这些 词中实际上有很大一部分是冗余的，对挖掘作用不大。由此可知，如果用全部特 征进行文本分类，不仅计算量庞大，且分类精度也难以保证。因此特征降维处理 是非常重要的。从文本特征中选出最有代表性的特征部分，以降低特征空间的维 数，从而达到降低计算复杂度和提高分类准确率的目的。最后得到的文本特征应 该最大可能地反映文本的内容。以下是些现有的文本降维方法。 1 基于评估函数的方法 基于评估函数的特征集缩减算法1 6 j 般使用特征独立性假设以简化特征选 择。通常是通过在训练数据集上的统计来计算每一特征的某种指标值，根据指标 o 0 = 吒吒 如，o ，、l ， 天津大学博士学位论文 第一章绪论 值的高低决定是否保留相应的字或词，或者对相应特征加权，从两实现特征选择。 基于评估函数的特征抽取处理的般步骤是：用某种评估函数独立地对每个特征 计算，然后把特征按计算结果进行排序，选择事先确定的数目或者超过闽值的若 干特征目前提取特征项的方法主要有7 种：互信息”6 1 、信息增型、词频法【1 6 1 、 c h i 概率统计【l6 1 、期望交叉熵“7 】、几率比1 1 刁和文本证据权”。 假定词条t 、类q ( i = 1 ，2 ，) ，定义p ( f ) 为f 在整个库中出现的概率， p ( t ) 表示t 不出现的概率，p ( c ，) 为q 类的出现概率，p ( c j i t ) 为t 出现时属于q 类 的条件概率，p ( q l f ) 为f 不出现时属于q 类的条件概率，t f ( t ) 为f 在文本集中出 现的次数，p u s 表示正例集情况，n e g 表示负例集情况。则各个评估函数的计算方 法为： 互信息： 加( r ) = 喜北) l o g ( 等 ( 1 - 1 0 ) 期望交叉熵： c t ( f ) ：加) 善j 删，) 1 0 9 ( 雩挣0 - 1 1 ) 词频： i f ( t ) ( 1 1 2 ) 信息增益： l g ( r ) = p ( r ) 喜p ( q 旧l o g 5 鼍乎) + p ( - ) 喜p 幻l _ ) l o g ( 2 j 若p ( 1 1 3 ) 文本证据权： 叫惦加，善烈q 斗o g 高咎别 ( 1 - 1 4 ) 几率比： 。r t ( ，) = l o g 而p ( ti 面p o s ) 而( 1 - p 丽( t n e g ) ) 、 c h i 概率统计：c h i 的主要思想是认为词条与类别之间符合z2 分布，词条 的z2 统计表示词条对某个类别的贡献大小。其使用方法及其改进将在3 1 节中详 细介绍。 2 潜在语义索引 潜在语义索引( l a t e n ts e m a n t i ci n d e x ：l s i ) 是s t d u m a i s 在1 9 9 8 年提出 的，也称为隐含语义分析( l a t e n ts e m a n t i c a n a l y s i s ) f 1 8 1 。l s i 试图剥用概念标引 代替关键词标引，从语义相关的角度为文本选择标引词，而不考虑标引词是否在 文本中出现，其通过奇异值分解( s i n g u l a r v a l u e d e c o m p o s i t i o n ：s v d ) 将词频矩 阵转化为维数极大减小的奇异矩阵，用转换后的文本向量进行文本挖掘处理。转 换后的新词颓矩阵在最小平方意义上最接近原来的词频矩阵。 天津大学博士学位论文第一章绪论 l s i 方法假定在文本库中存在隐含的关于词的使用的语义结构，这种语义在 定程度上被文本中词的语义和形式上的多样性所掩盖，比如词条之间的非正交 情况，同义词和多义词、上下文背景相关等。l s 方法利用统计方法形成词条一 文本矩阵，并进行奇异值分解，选取奇异值中最大的前k 个奇异值及其对应的奇 异向量构成一个新矩阵来近似表示原词条一文本矩阵。新矩阵以语义结构表示词 和文本，将词和文本映射在同一个k 维向量空间，不仅可以分析原有的词与词、 文本与文本之间的关系，也可以分析词与文本之间的关系。l s i 在一定程度上消 减了原矩阵中语义关系的模糊度，更加有利于信息表示和处理，并且通过选择奇 异值中最大的前k 个奇