（计算机应用技术专业论文）支持向量机在web文本分类优化中的应用.pdf

摘要 随着w e b 作为互联网上最重要的应用之一，它提供了便捷的文档发布和信 息的获取，并且各地的信息资源聚集在互联网上，成为生活中不可缺少的一部 分。根据官方资料的显示，在互联网上已经有过亿的w e b 文档，面对如此大的 海量信息，w e b 用户往往无从下手快速获得自己所需的信息，所以迫切需要一 种方法能够快速定位到有用信息上。由于这种需求者越来越多，关于w e b 数据 挖掘技术便产生了。而现阶段的w e b 数据挖掘主要建立在信息检索、数据挖掘 以及知识管理上，通过对大量的w e b 文档进行分析来获得隐含的知识和模式， 从而使得人们更好的进行信息搜索。 随着w e b 数据挖掘技术的发展，如今的文本分类技术能够改善文本信息杂 乱状况，可以降低查询时间，提高搜索质量，快速有效地获取文本信息。因此 文本自动分类技术越来越受到人们的关注。基于机器学习的文本自动分类已经 取得了很好的效果，提出了多种分类算法，如k 最近邻算法、朴素贝叶斯算法、 决策树算法和支持向量机等。 本文主要阐述了w e b 数据挖掘中文本分类技术，给出了w e b 文本分类的处 理过程：文本预处理，特征降维，文本特征的表示方法等，探讨了支持向量机 ( s v m ) 分类算法在文本分类中的应用。重点研究了与贝叶斯中的最小误差率 相结合的支持向量机来构造的一个多分类w e b 文本分类模型以及它的具体构造 过程。经过实验证明，在确保分类器性能的条件下，选取训练数据样本进行训 练，它的实验结果比传统的支持向量机分类器精度有所提高，具有较高的运行 效率。 关键词：w e b 数据挖掘，文本分类技术，贝叶斯最小误差率，支持向量机 ( s v m ) a b s t r a c t a sw e bi so n eo ft h em o s ti m p o r t a n ta p p l i c a t i o n so nt h ei n t e m e t ，w h i c h p r o v i d e sc o n v e n i e n c et od o c u m e n tr e l e a s i n ga n di n f o r m a t i o na c c e s s ，i n f o r m a t i o n r e s o u r c e se v e r y w h e r eg a t h e r e do nt h ei n t e r n e th a sb e c o m ei n d i s p e n s a b l ei no u rl i v e s a c c o r d i n gt oo f f i c i a ld a t a ，t h ei n t e r n e th a sm o r et h a n1 0 0m i l l i o n so fw e b d o c u m e n t s i nt h ef a c eo fs u c hal a r g em a s so fi n f o r m a t i o n ，w e bu s e r sa r eo f t e nd i f f i c u l tt oc h o o s e w h a tt h ei n f o r m a t i o nt h e yn e e d ，s ot h e ya r eu r g e n tt of i n daw a yt oq u i c k l yl o c a t et h e u s e f u li n f o r m a t i o n b e c a u s eo ft h eu s e r s d e m a n di si n c r e a s i n g , d a t am i n i n g t e c h n o l o g yo nw e be m e r g e d b u ta tt h i ss t a g e ，w e bd a t am i n i n gi sm a i n l yb u i l to n i n f o r m a t i o nr e t r i e v a l ，d a t am i n i n ga n dk n o w l e d g em a n a g e m e n t t h r o u g ha n a l y s i so fa l a r g en u m b e ro fw e b d o c u m e n t st oo b t a i nt h eh i d d e nk n o w l e d g ea n dp a t t e r n s ，p e o p l e w i l lm a k eb e t t e ri n f o r m a t i o nr e t r i e v a l w i t ht h e d e v e l o p m e n t o fw e bd a t a m i n i n gt e c h n o l o g y , t o d a y s t e x t c a t e g o r i z a t i o nt e c h n o l o g yc a l li m p r o v et h es t a t u so ft e x tm e s s a g ed i s o r d e ra n dr e d u c e t h eq u e r yt i m e ，i m p r o v es e a r c hq u a l i t y , a n dg e ta c c e s st ot e x tm e s s a g ef a s ta n d e f f i c i e n t l y t h e r e f o r e ，a u t o m a t i ct e c h n i q u e so ft e x tc a t e g o r i z a t i o no b t a i nm o r ea n d m o r ea t t e n t i o n 。t e x tc a t e g o r i z a t i o nb a s e do nm a c h i n el e a r n i n gh a sb e e na c h i e v e dv e r y s a t i s f y i n gr e s u l t s al o to fc l a s s i f i c a t i o na l g o r i t h m sa r ep r o p o s e d ，s u c ha st h ek n n a l g o r i t h m ，n a i v eb a y e sa l g o r i t h m ，d e c i s i o n t r e e a l g o r i t h ma n ds u p p o r t v e c t o r m a c h i n e s 、 t h i sp a p e rm a i n l yd e s c r i b e st h a tw e bd a t am i n i n gc h i n e s et e x tc a t e g o r i z a t i o n t e c h n o l o g i e sa n ds h o w st h ep r o c e s s i n go fw e b t e x tc a t e g o r i z a t i o ni nd e t a i l s ：t e x t p r e p r o c e s s i n g , f e a t u r ed i m e n s i o nr e d u c t i o n ，p r e s e n t a t i o nm e t h o do ft e x tf e a t u r e s ， p r o b e s i n t ot h ea p p l i c a t i o no fs u p p o r tv e c t o rm a c h i n e ( s v m ) c a t e g o r i z a t i o n a l g o r i t l u ni nt e x tc a t e g o r i z a t i o n ，a n df o c u s e s o ns u p p o r tv e c t o rm a c h i n ei nt h e c o m b i n a t i o nw i t hm i n i m i z i n gb a y e se r r o r sr a t et oc o n s t r u c tam u l t i - c a t e g o r ym o d e l o fw e bt e x tc a t e g o r i z a t i o na n di t sc o n c r e t ec o n s t r u c t i o np r o c e s s e x p e r i m e n t ss h o w , u n d e rt h ec o n d i t i o no fe n s u r i n gt h ep e r f o r m a n c eo ft h ec l a s s i f i e r , s e l e c t i n gt h e t r a i n i n gd a t as a m p l e s f o rt r a i n i n g ，i t se x p e r i m e n t a lr e s u l t sc a l la c h i e v eb e t t e rp r e c i s i o n i i c o m p a r i n gw i t ht r a d i t i o n a ls v ma l g o r i t h m ，a n dh a sah i g h e rr u n n i n ge f f i c i e n c y k e yw o r d s ：w e bd a t am i n i n g ，t e x tc a t e g o r i z a t i o nt e c h n o l o g y , m i n i m i z i n g b a y e se r r o r sr a t e ，s u p p o r tv e c t o rm a c h i n e ( s v m ) m 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名：瑾望 日期：迎! ：丛 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：短导师( 签名) ：上至墨日期垫生：垄 武汉理工大学硕：t 学位论文 第1 章绪论 本章为开篇，主要介绍文本分类的产生背景，定义以及发展现状、未来趋 势等。同时，也给出了课题研究的意义，研究的内容和方法，为整篇文章展开 的内容和整个文章的结构提供了整体的框架。 1 1研究背景和意义 1 1 1 研究背景 2 0 世纪以来，随着科学技术的发展，信息和信息技术已经成为社会中必不 可少的东西。信息化的普及和万维网的迅速发展使得其成为世界上规模最大的 公共数据源。总结下，它们应具有以下特点i l j ： ( 1 )数据信息开始以电子文档的形式储存，每天的数据量都在急剧增加。 这些数据的主题广泛而且内容丰富，用户可以在网上找到所需的内容。 但)万维网的信息是异构的，因为网络公司的用户名不同，很多表示相同 或相近的内容可能会用完全不同的格式来表示。 ( 3 )万维网上存在着大量的噪声和垃圾，譬如：广告，导航链接等。对于 这些无用的噪声应该过滤掉，把有用的信息得以保留。还存在一点，就是因为 万维网它本身没有限制上网人员的身份，使得任何用户都可以在不同的网站发 表自己的言论。因此，存在着大量质量低，漏洞多，甚至带有些有误导性的 信息。 ( 4 ) 万维网也具有动态性，网上的信息不断更新。对于专门做搜索引擎等 这一类的工作来说，必须跟踪和监测这些变化。 ( 5 ) 在海量的网页中，现在的搜索引擎仅仅将得到的网页直接呈现在用户 面前，并不进行整理分类。使得用户将无法快速得到与自己相关的信息，无法 为用户提供满意的服务。 那么如果对原始的文档不加以科学的组织和管理，这些特征使得无法快速 便捷的使用这些海量信息，以至于在查找的过程中往往会消耗的大量的时间和 网络资源，降低了学习和工作效率。这将直接或间接的造成社会、经济的损失。 武汉理工大学硕士学位论文 因此如何提高信息的利用率、如何获取数据信息进行科学的管理是一个不可回 避的问题。这就使有效的挖掘有用信息和知识的任务变得非常有趣，并富有挑 战性。而本文研究的正是数据挖掘中最常用的挖掘技术一部分：文本分类。 1 1 2 研究意义 在当今社会，因为数据信息过载的复杂背景下，设计人员为了能用更加智 能，快捷的查询系统来满足用户的需求，便产生了文本分类技术。因此文本分 类具有广泛的商业和发展前景。 这种技术是处理大规模文本的关键，现在很多信息检索也都把文本分类作 为核心，由于它的信息检索的速度跟文本分类的技术有很大的关系。所以至今 为止，有很多技术人员研究文本分类的改进方法，也提出了很多改进算法【2 l ，譬 如：基于1 - a 1 的兼类文本分类算法、基于1 - a r 的兼类文本分类算法、贝叶斯 方法、贝叶斯网络、决策树方法、k 邻近方法等。 本文主要以统计学为基础对文本分类进行改进。那么怎么样才能从准确分 类的文档里挖掘出一些有效分类呢? 关键所在就是分类器的设计。因此分类器 的设计具有极其重要的研究意义。 1 2国内外研究现状 关于文本分类的技术，国外主要研究这种技术的单位有c m u 、斯坦福等， 国内主要研究的单位也有很多，譬如：东北大学、上海复旦大学、哈尔滨工业 大学、中科院计算所、t r s 等，但是我国所研究的主要是将国外的方法引进来 应用到中文文本分类技术上。 至今为止，回顾文本自动分类在国外的历程，可分为三个发展阶段【3 j ： 第一阶段( 1 9 5 0 1 9 6 4 ) 主要进行的是自动分类可行性研究：h p l u h n 首先 提出了词频统计思想，后来又把这种思想应用到了文本分类技术中。1 9 6 0 年， m a r o n 又将贝叶斯定理应用到文本分类中，这种方法的可行性高，从而推动了文 本分类技术的发展。 第二阶段( 1 9 6 5 1 9 7 4 ) 进行自动分类的试验研究：主要是由知识工程师和 技术人员手工编写分类规则，然后再将相应的文档分到他们所划分的类别体系 中。这种做法不仅耗费了大量的时间，而且很受人为因素的影响，这些技术人 员的知识结构会影响到最终的分类效果。 2 武汉理工大学硕士学位论文 第三阶段( 1 9 7 5 至今) 进行实用化阶段：出现了由知识工程方法过渡到了 基于机器学习的文本分类方法，使得它至今仍是主流技术。本方法无需知识工 程师的参与，而是通过机器学习得到的分类器，然后这种分类器再通过自学推 导出新的学习规则。现在这种方法并在邮件分类、电子会议、信息过滤等方面 取得较为广泛的应用。其中，国外较为成功的系统有麻省理工学院( m r r ) 为白 宫开发的邮件分类系统，卡内基集团为路透社开发的c o n s t r u e 系统【4 l 等。 而国内的文本分类研究工作起步比较晚，始于2 0 世纪8 0 年代初期。大体 经历了可行性探讨、辅助性分类系统、自动化分类系统三个阶段。1 9 8 1 年，侯 汉青教授曾介绍过国外的一些文本分类的情况。但是总体来说，中文文本分类 还处于在试验研究阶段，正确的分类率约为6 0 9 0 ，但是现在已经逐渐向商 业化的软件应用方面靠拢，在短短2 0 年里已经尝试开发了一批关于中文的自动 分类系统。例如，中科院计算机所的谭松波博士研究的d r a p 文本自动分类系 统、清华大学吴军、王作英等人研制的自动分类系统、山西大学刘正瑛等人开 发的金融自动分类系统、上海交大的西风文本自动分类系统等。 由于中文文本的表示比较复杂而且测试的标准不能统一，所以如何找到合 理的方法并且在实践中逐步改善它的算法，提高它的性能成为中文文本分类算 法的当务之急。 1 3文本分类的应用领域 随着互联网的诞生，信息已经在世晃范围内得以共享，但是人们希望用一 种有序且有效的方式来寻找信息的需求，因此出现了文本分类几乎应用于与信 息管理相关联的各个领域： ( 1 ) 信息处理【4 l 】 信息处理技术是一门与语言学、计算机科学、心理学、数学、控制论、信 息论、声学、自动化技术等多种学科相联系的边缘交叉性学科。随着科学技术 的发展，信息处理技术已存在于社会生活的各个方面。为了让它能满足各国的 信息基础建设对信息处理应用需求，怎样将文本分类计数应用于信息处理领域 已经成为研究的一个重要问题。 信息处理是用计算机根据不同用户的需要来制定出不同的要求，然后对口 语和书面语进行转换、传输、存贮、分析等加工的科学。现阶段它主要研究的 方向是词语的词汇，语法，语义等方面的自动处理问题。 3 武汉理工大学硕士学位论文 现在，国内出现了很多研究情报检索的单位，他们主要研究的是怎样才能 建立中文情报的检索语言，因为中文词的意思很多，而词的分类直接影响到情 报检索的效率，所以很多技术人员一直在这方面改进，使得情报检索变得更加 实用化。 ( 2 ) 文献归类 文献归类是指根据文献内容和形式的异同，再按照一定的体系来确定所属 ，的类目，然后分门别类的把它们收藏起来。因此对文献归类工作来说，是一项 十分细致而带有一定学术性质的工作。 文献的归类法有很多种，其中最常见的有：等级分类法，标题分类法， 组面分类法( 或叫冒号分类法) ，二进位分类法，十进位分类法，字顺分类法， 自然分类法，人工分类法，主题分类法等。 一般来说，现阶段，很多网站( 譬如淘宝网、新浪网等) 有些还是采用 的人工分类方法，这样既消耗了大量的人力，物力，又不便于及时的更新信息。 为了便于文献检索，文献归类方法必须做到科学合理，使得用户查找的效率更 加高，出现了文本自动分类技术。目前在谷歌，百度等搜索引擎网站、新浪， 网易等门户网站上都研究文献自动归类方法，这将大大的提高分类的效率和网 站信息的更新速度。 ( 3 ) 信息过滤 信息过滤技术作为面向i n t e r n e t 的个性化主动信息服务的一个重要中间环 节，近年来在信息的处理体系中应用越来越广泛。 信息过滤是应用于处理大规模内容的一种典型过程，它是对陆续到达的信 息数据流中寻找用户所需的信息，然后将无用信息进行过滤操作，那些符合用户 需求的信息将得以保留。在这个过程中，要预先知道用户的需求和输入进去的 信息数据流。信息过滤系统会按照用户的需求和用户的兴趣来构造一种用户模 板，只将信息数据流中符合需求和兴趣的信息显示出来，以便用户能够方便使 用，而且用户可以多次修改自己的需求，从而更好的满足用户的需求。 但是面对w e b 动态，实时的海量信息，传统的过滤技术难以适应这种动态 的环境。因此现在大量研究机构的技术人员在总结w e b 这种系统存在的两大问 题上( 相关文档获取和自适应学习) ，为了充分利用信息过滤灵活、动态、实时 的特点，改进基于信息过滤技术的相关文档获取方法，来满足了w e b 系统的时效 性要求，使得系统的整体性能能够进一步得到提高。 ( 4 ) 语言文字处理 4 武汉理工大学硕士学位论文 在这里所说的语言文字处理技术，就是语言学理论与计算机技术所结合的 产物。 当今世界，存在上几千种语言，但是并没有人能够掌握所有语言。因此在 搜索信息时，必须选择自己会的语言。在这种情况下，不得不在语言文字上进 行分类。以中文来说，必须要建立上下文关联的句法结构和语义描述方法来实 现对自然语言的词法、句法和语义的信息符号化和处理机制，从而解决了自然语 言处理过程中的歧义问题，并且以此为理论基础研制了一种方法，即：以拼音为 录入手段，以词为单位的进行整句，整段输入。这种方法具有较高智能的文字处理 系统，使录入方式更接近于自然语言。 现在语言文字处理的主要用法就是以某个国家的特征语言的词和短语作为 聚类对象，然后再分类系统的大范围的语料库里，利用文本分类的特征提取方 法进行词语的领域聚类，利用获得的领域知识来对文本分类和主题进行分析。 以上所涉及到得只是文本分类技术应用的几个主要领域。此外，文本分类 技术还在电子政务、数据挖掘、知识本体等许多方面都有用到，由此可以看出 文本分类技术在各个领域的重要性和广泛性。可以说文本分类技术是一切文档 管理的基础。因此，在各个机构和网络上在线文档的急速增长的情况下，文本 分类技术的研究是一个重要的课题。 1 4 本文的主要研究内容 由于传统的文本分类无法适应网络的自学习能力，本文对文本分类技术进 行了改进，用到了支持向量机。它不仅有扎实的理论基础，而且在许多应用领 域比其他的算法都要准确，可以认为支持向量机在解决文本分类问题上是比较 准确的算法。因此它较广泛的应用于网页的分类领域。但是支持向量机有一定 的局限性，他不能应用于多类问题中，只能用于二类分类中。所以只能把多类 问题转换成二类问题。因此在本文中又用到了最小误差率的方法。如何将最小 误差方法和支持向量机相结合，这些将是本文研究的主要工作之一。 本文研究的主要内容有以下几点： ( 1 )介绍了文本分类的原理和分类的步骤，如：文本信息的预处理，文本 特征表示法等。 ( 2 ) 介绍了支持向量机的基本知识，核心思想，支持向量机进行文本分类 的优点，在文本分类中所存在的问题并总结了一些改进方法。以及支持向量机 5 武汉理工大学硕士学位论文 在文本分类中的应用。 ( 3 ) 介绍了最小误差率方法的原理，如何用最小误差率法解决多类问题转 成二类问题，以及用它的优点和存在的问题。 ( 4 )由于支持向量机只支持两类分类，所以在用支持向量机之前需要用最 小误差率方法来转换，如何用最小误差率方法与支持向量机的结合是本章的关 键问题。 ( 5 ) 利用改进的支持向量机与传统支持向量机算法对文本分类技术进行 分类实验，将实验结果进行对比，来查看它们的准确率。 1 5本章小结 本章讨论了该论文的研究背景、意义以及国内外对文本分类技术研究的现 状。比较详细的阐述了设计开发文本分类系统的现实意义和发展前景，介绍了 一些文本分类技术的主要应用领域，为以后的研究奠定了理论基础。 6 武汉理工大学硕士学位论文 第2 章文本分类技术的概述 2 1中文分词技术 2 1 1 中文分词的思想 任何一门语言都是由词法、句法和语义构成的自然语言，而中文与英文相 区别的是：英文它是由一个个的字母构成，而中文由偏旁部首构成，比较复杂， 需要使用一些分词算法。 如果是英文，只需要剔除一下几点： 1 、只要依次从文档中剔除掉英文词虚词，即：“t h e ”，“a n ，“o f 等，这个 过程比较简单。 2 、剔除单词的前后缀。具体的步骤主要是将同词根的单词映射到一个特征 词属性，这样可以大大地减少特征词的个数。 而中文分词需要把单个汉字切分成一个个的词，这种算法主要有三大类1 5 l ： 基于字符串匹配的分词方法、基于理解的分词方法和基于统计规则的分词方法， 具体用法如下： 图2 - 1 中文分词技术的发展 基于字符串匹配的分词方法，这种方法比较机械，它是按照一定的策略将 等待分析的汉字串与机器词典中的词条相匹配。如果词典中存在这个汉字串， 则匹配成功，成为一个词，否则匹配失败。这种方法如果按照不同的扫描方向， 又可分为正向和逆向匹配：如果按照长度优先的方法来说，又可分为最长匹配 和最短匹配；如果按照与词性标注是否能结合的方法来说，又可分为单纯分词 7 武汉理工大学硕士学位论文 方法和分词与标注相结合的一体化法。最常用的几种机械分词方法有：正向最 大匹配法( 判断的方向是自左向右) 、逆向最大匹配法( 判断的方向是自右向 左) 、最少切分( 使每一句中切出的词数最小) 。根据汉语的特点( 单字成词) ， 一般来说，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。但 是这些精度还是比较低的，在实际的应用中，只把基于字符串匹配的分词方法 当作一种初分手段，还需要用一些其它的信息来提高它的切分精度。随着科技 的发展，出现了一种特征扫描方式，它的原理主要是将待分析的汉字串中识别 或切分出一些带有明显特征的词，然后用这些词作为断点，将原来的汉字串分 为较小的串再进行分词，从而减少了匹配的错误率。还有一种是将分词和词类 标记结合起来，通过利用丰富的词类信息对分词的决策提供帮助，并在标注的 过程中不停的进行检验分词的结果，从而更一步的提高了切分的精度。 基于理解的分词方法，它实际上就是应用了人工智能罩的专家系统进行的 自动分词，是近些年关于中文分词研究的热点问题之一。这种方法的原理是让 计算机模拟人脑对词，句子的理解，来达到识别的效果。基本的思想是在分词 的过程中进行词法、句法、语义、语法，从而处理有歧义的地方。它包括了三 个部分：分词子系统、句法语义子系统、总控部分。通常是在总控的协作下， 分词子系统和句法语义系统来判断分词的歧义。这种分词方法它的切分精度很 高，但是必须依靠大量的语言信息和知识来支撑。而汉语的语言知识很复杂， 也比较笼统，难以将各种语言信息直接组织成机器可读取的形式，所以目前应 用基于理解的分词方法还比较少，还属于研究的初级阶段。 基于统计规则的分词方法，这种方法跟语料库有关。语料库的信息的多少 直接影响到此方法的应用。这种分词法首先要建立数学的统计模型，通过已训 练好的语料库计算成为参数值，应用到分词程序的这种统计模型中。从形式上 来看，词是稳定的字与字之间的组合，因此在语料库中，如果相邻的字同时出 现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率就 能够较好的反映成词的可信度。本方法的具体原理是输入语料库的每一个汉语 串，对它们进行切分，再把切分后的所有结果列出来，然后对每种结果可反映 出语言特征的数据来分别计算出它们的概率，之后再选取它们之间的最大值。 这种概率的计算方法必须依赖于所建立的语言模型。这种方法的优点就是，所 需的一切数据均由机器从生语料中自动获得，无须人工介入，并且能有效地排 除歧义，识别未登陆词，解决了机械匹配分词算法的局限。但是也有一定的局 限性，比如：抽出的一些高频词里并不是常用字组( “之一”等) ，没什么用处， 8 武汉理工大学硕士学位论文 导致对常用词的识别精度差，空间的利用率低，花费的时间多。还有一种情况 下，( 即：在文本进行分词后变成词集，但是词集中仍存在着很多词几乎也不携 带任何信息，比如介词，副词等等，还有一些词在语库中存在频率高但在每篇 文档中出现的概率差不多相等。) 对分类来说也没什么意义，可以把它们剔除掉， 其结果就会缩小了词集的范围，提高了分类的精度。 2 1 2 常用的中文分词系统 s c w s ：h i g h t m a n 所开发的一套基于词频词典的机械中文分词引擎，它能 将一整段的汉字基本正确的切分成词。它所采用的是采集的词频词典，并辅以 一定的专有名称、人名、地名、数字年代等规则识别来达到基本分词，经过小 范围测试后，大概准确率在9 0 9 5 之间，已经能够基本满足一些小型搜索 引擎、关键字提取等场合运用。4 5 k b 左右的文本切词时问是0 0 2 6 秒，大概是 1 5 m b 文本秒，支持p h p 4 和p h p5 。 i c t c l a s ：是最早的中文开源分词项目之一，也是至今为止比较成功的系 统之一。i c t c l a s 在国内9 7 3 专家组组织的评测中活动获得了第一名，在第一 届国际中文处理研究机构s i g h a n 组织的评测中都获得了多项第一名。 i c t c l a s 3 0 分词速度单机9 9 6 k b s ，分词精度9 8 4 5 ，它还具备一套完整的 a p i 接口，a p i 不超过2 0 0 k b ，各种词典数据压缩后不到3 m i c t c l a s 全部采 用c c + + 编写，支持l i n u x 、f r c c b s d 及w i n d o w s 系列操作系统，支持c c + + 、 c 撑、d e l p h i 、j a v a 等主流的开发语言。 h t i p c w s ：是一款基于哪协议的开源中文分词系统，目前仅支持 l i n u x 系统。h t r p c w s 使用“i c t c l a s3 02 0 0 9 共享版中文分词算法”的a p i 进行分词处理，得出分词结果。h t r p c w s 将取代之i j 的p h p c w s 中文分词 扩展。 c c c e d i c t ：一个中文词典开源项目，提供一份以汉语拼音为中文辅助的 汉英辞典，截至2 0 0 9 年2 月8 日，已收录8 2 7 1 2 个单词。其词典可以用于中文 分词使用，而且不存在版权问题。c h r o m e 中文版就是使用的这个词典进行中文 分词的。 因为中科院的i c t c l a s 分词系统具有较高的准确率和分词速度，所以在本 文中采用了这个分词系统来对文本进行分词处理。 9 武汉理工大学硕士学位论文 2 2文本分类的原理 文本分类【5 - 7 l 是当今信息处理领域的一个研究热点，它是以文本归档为目标， 把大量的文献集映射到预先定义好的文本属性类中。而它的任务是将超文本文 件根据内容分为预先定义的几个类别。如今很多领域都有这种问题，包括邮件 过滤、网页搜索、办公自动化、主题索引和新闻故事的分类等。 基于机器学习的文本分类大都由训练和分类两个部分组成【8 1 4 】，基本思想是 将训练集、矢量集与文档矢量集三者相比较。在训练阶段，从训练文本学习到 得的分类知识，来建立一个分类器，训练集是为了建立模型，这种模型是由被 分析的文本构成，每一个为一个样本。模型的学习在被告知每个训练样本属于 哪个类的指导下进行，并采用分类规则、判定树或数学公式等方面的形式给出 学习的方法，然后将己知的类标号与测试样本的学习模型类进行预测比较，再 对学习模型进行准确率的测试评估。在分类的阶段中，需要根据分类器将输入 文本分到最可能的类别中。具体的文本分类的系统模型如图： 1 0 武汉理工大学硕士学位论文 2 2 1w e b 文本分类 图2 - 2 文本分类系统的模型 w e b 文本分类【1 5 弓i a t 自然语言技术，在对w e b 文本信息进行抽取和发现 所需的隐含信息中，通常采用分类、关联规则、序列等方法。但是w e b 文本大 部分是以h t m l 的网页格式形成的，具有一定的结构化。而这种结构化数据通 武汉理工大学硕士学位论文 常是从后台数据库里获取数据记录，按照一定的模板被展示在网页上的，所以 在提取这些有用的数据时需要用到网页预处理。 2 2 2 常用的文本分类技术 朴素贝叶斯分类【3 1 ，3 9 】：它是一种在概率产生模型上进行推导的。假设这个 模型中每一个文档是由一个参数化概率分布( 由一些隐藏参数决定) 生成的。 训练数据是用来估计这些参数，然后再根据贝叶斯准则把这些参数计算后验概 率从而进行分类。这种分类技术的学习效率很高，它只需要对训练的数据进行 一次扫描就可以得出所有的概率，但是它所做的大多数假设都与实际情况不符， 而且在考虑单词在文档中出现的次数时，这种分类技术不是很准确。 k 最邻近方法【2 4 】：是一种惰性学习方法，它需要从训练数据中学习模型， 而学习的过程仅仅在测试样例需要分类时才发生的。这种算法最关键的是相似 度函数，这需要根据不同的应用领域和数据特点选择。但是k 近邻在分类的时 候会花费大量的时间( 尤其是在训练数据集和测试数据很大的时候) ，主要因为 在没有建立好模型时，每个测试样例都在分类时与所有的样例比较。在需要人 类理解的模型时，它不能适用，因为它不能给出一个可以理解的模型。 决策树1 3 5 ，3 7 】：这种是分类算法中最广泛应用的一种技术，这种树有两个类 型的节点( 决策节点和叶子节点) ，决策节点包含针对数据实例某个属性的一些 测试，而叶子节点则代表一个类标。具体的原理是，递归的把训练数据分隔成 不相交的子集，随着决策树的增长，样例就会被不停的递归分隔。这种算法的 分类精准度与其他算法相比效率非常的高效。但是这种算法是一个不回溯的算 法。一旦一个节点创建之后，无论发生了什么，它都不能被修改。 遗传算法1 3 9 l ：是把每个分类器都表示为一个二进制位串，也就是所谓的染 色体。每个分类器根据它的分类任务的完成情况进行计分，然后按照染色体的 得分进行排序，并根据高低顺序对部分的染色体进行复制、交叉、变异等遗传 运算得到的染色体的下一代。重复循环上述的过程直到某个分类器超过了某个 预定的得分门限值。注意的一点是，从每一代进化到下一代所获得的平均性能 改良还是要依赖于每一代中个体间得分的差异程度的大小。 支持向量机i 恤1 4 j ：是当前最流行的算法之一，它不仅具有扎实的理论基础， 而且在很多领域中的应用比其他算法更准确，尤其是在处理高维数据方面。它 是一个线性学习系统，用最大边距决策边界来分割正例和负例，通常这样的问 1 2 武汉理工大学硕士学位论文 题会用一个二次优化问题来刻画，非线性的决策边界可以用原始数据向更高维 的特征空间变换得到。但是支持向量机算法仍存在很多局限。文本在第三章将 会详细介绍支持向量机的分类技术。 当然当前还有很多的分类技术如后向传播分类、线性最小二乘法、模糊集 等，在这就不一一介绍了。 2 3文本信息的预处理 文本信息的预处理实质上就是为了能够进行细粒度w e b 信息分析和数据挖 掘，对网页上文档中一些无关的信息过滤掉，譬如：导航链接、广告、版权声 明等，保留在应用中所需要的有用信息。这里，在一个网站中对网页分类有用 的信息主要是文本题目和文本正文。其他的都可以称之为噪音，可以被过滤掉。 在保留文本题目和文本正文时应该把它们设为纯本文的格式。这样可以提高分 类的精度。因此在给出文本中每个属性( 单词) 的值之前，需要对文本集进行 预处理 1 提取文本的标题，在网页中，文本的标题都比较明显，一般在 和 之间的内容是文本的标题。譬如：“文本分类语料库自动创建系统的研究 与实现”就可以直接提取“文本分类语料库自动创建系统的研究与实现”。如果存 在某些标记的信息，譬如x h t m l 标志( 可扩展超文本标记语言) 的文本信息： ，要把这些标记剔除，因为它们不 带有任何信息。 2 提取文本正文， 和 之间的信息就是正文，但是由于网页 上的文档都是由h t m l ( 超文本标记语言) 标记的，所以剔除于本文无关的内 容是比较困难的，只能先通过提取的字符流后，定义好与文本主题无关的h t m l 的标记，再把无关内容剔除掉。譬如：“ ， 等等。这样 对网页的分类提供了方便。 2 4 特征降维方法 在实际应用中有很多多类问题，遇到包含高达1 1 3 0 个( 甚至更多) 特征问 题时计算量令人惊叹，尤其当这些特征是一些二值变量的时候。这样为了避免 一些问题，就产生了特征维数。因此特征维数对分类精度有一定的影响，而且 武汉理工大学硕士学位论文 对于设计分类器时的计算复杂度也有影响。 维数灾难在应用中存在很大的问题，因而出现了很多降维的算法，而这些 算法的共性就是提供了一个函数映射过程，可以对任何一个特征向量求得在低 维空间上的对应点。比较经典的算法有主成分分析和因子分析，它们都是通过 线性组合特征来达到降维的目的。下面就详细介绍下这两种算法。 主成分分析是在低维空间上找到最能反映原始数据方差的一种表示方法。 具体的思想是：首先计算出d 维均值向量和一个大小为d d 的协方差矩阵，其 次再计算出这个矩阵的本征值和本征向量，每个本征向量都对应一个本征值。 接着选出对应最大k 个本征值的本征向量作为主成分方向。通常所对应的最大 本征向量只有很少的几个，这意味着k 是取决于数据本身的子空间的内在维数， 而剩下的d k 维往往由噪声引起。 因子分析它是主成分分析的进一步发展，在低维空间上找到最能体现原始 数据之间相关性的一种表示方法。具体思想是：用较少个数的公共因子的线性 函数和特定因子之和来表示原来观测的每个变量，以便可以达到合理地解释存 在于原始变量间的相关性和简化变量的个数，根据因子得分对变量或者样品进 行分类。 而经过上一节的预处理之后，特征矢量的维数仍然很高，需要在尽量不损 失分类信息的情况下生成一个低维的特征矢量。当前有两种方法：一是从原有 的特征词集合中挑出最有效的一些特征构成新的特征矢量，这个过程叫特征选 择；二是将高维特征矢量映射( 一般为线性映射) 到低维空间，这个过程叫特 征提取。本文中主要用到的是特征选择。 2 5文本特征表示形式 2 5 1 向量空间模型 文本是非结构数据，要想让计算机来识别文本的类别，首先就要将文本进 行结构化处理。当前比较经典的文本特征表示模型主要三种：布尔模型、向量 空间模型、概率模型。 在对文本分类的过程中通常采用的是向量空间模型，它的原理是在向量空 间罩，每一个轴标识一个词项，文档的坐标轴的方向由两个量来决定，然后将 每个文档都映射为由一组规范化的正交词条矢量张成的空间的一个点。下面介 1 4 武汉理工大学硕七学位论文 绍需要用到的概念f 4 3 i ： 1 、文档：指的就是文章。 2 、项：就是所谓的特征项，指的是文章中的一些词或短语。而文本分类主 要是根据特征项来的。 3 、项的权重：权重表示在评价过程中，被评价对象的不同侧面重要程度的 定量分配，对各评价因子在总体评价中的作用进行区别对待。具体的思想是： 在文档应用中。假设一个系统包含有m 个文档、n 个不同的项，可令d i - - ( t l ，t 2 ，t n ) ( 1 ，i 一1 。j 注明一点就是需要求出此空间中 的线性超平面( w 宰x ) + b = 0 ，从而可以导出在原始的空间上划分的超曲面和决策 函数值，用图形可以形象的表示为： 武汉理工大学硕士学位论文 通过核函数妒o 的变换变成下图： 图3 - 3 用核函数变换的过程 非线性的支持向量机分三层结构，是一个多输入、单输出的学习机器，如 图3 4 所示，其中毛，x 2 ，屯，是输入的数据样本，七( ，x ) ，k ( x 2 ，x ) 。相当于 是样本x 和支持向量机在空间里的内积。a ，( i 一1 ，2 ，n ) 就是拉格朗日的待定 因子，最后的f ( x ) 就是决策函数。这张图形象的形容了非线性支持向量机的 逻辑框架。 武汉理工大学硕士学位论文 叠“ j r 2黾 图3 4 非线性s v m 的结构图 它的执行过程简单的说就是把输入数据样本映射到高维空间里，然后在这 个高维空间使用线性分类器来完成这个分类。当在特征空间中构造出最优函数 是，训练算法进行空间中的内积运算，而这种内积运算是可以从原始空间中的 函数来实施的。因此在非线性分类中引出了一种核函数，如果他满足m e r c e r 条 件的时候，它就对应这个变化空间中的内积。因此在求解最优化函数时就不需 要计算非线性函数，只需要计算满足m e r c e r 条件的核函数1 2 0 , 2 2 2 9 , 4 4 1 。 3 3 3 支持向量机的训练 支持向量机的训练通常分两步走，第一步是将输入数据映射到高维空间的 非线性函数中去( 映射后的空间维数可能很高，但是受到所采集数据的语料库 资源的限制) 。第二步是将有约束的权向量长度极小化问题转化成无约束能力的 拉格朗日因子问题。构造出的函数需找到极小权向量，使这个函数