（计算机应用技术专业论文）基于web的中文文档自动分类的研究与实现.pdf

哈尔溃理t 人学t 学顺l 学位论史 基于w e b 的中文文档自动分类的研究与实现 摘要 因特网上的信息同益丰富，己经成为知识获取的一个重要来源。信息资 源的丰富也使信息的检索有如大海捞针，检索到自己所需要的信息资源效率 不高。对信息进行整理。提高信息检索的效率具有非常重要的意义。本课题 的研究的内容是对中文w e b 文档进行自动整理归类，以提高用户对信息检 索的体验，同时它是搜索引擎、信息过滤、信息检索、文本数据库、数字化 图书馆等领域的核心技术。 文本分类通常是指在给定分类体系的情况下，根据文本的属性( 内容) 自 动确定其所属类别的过程。一般情况下，文本分类需要有训练集的支持。所 谓的训练集是指个文本的集合，由一组已经完成分类( 即给定类别标号) 的 文本组成。而且根据分类体系的设定，每一个类别都应含有一定数量的训练 文本。分类器通过某种学习方法完成训练后才可以用于分类未知文本。文本 分类技术可以为信息的组织管理提供有效的支持，更好的满足信息检索的需 求。该技术的好坏直接影响到搜索效率的高低。 本文主要对文本自动分类中的特征提取以及文本分类算法等几个核心技 术进行了深入的研究。提出了一种结合多线程技术实现的并行开放的文本自 动分类解决方案。将各种文本分类算法集成为一种可选择单一运行，可并行 同时运行的机制。并且可对各算法给出一个开放性的接口进行管理。可添加 新的文本分类算法，也可以删去过时的文本分类算法。特征提取方法也采取 了类似的办法。这样的做法大大提高了文本分类系统的兼容性及准确性。并 且在晟后实现了个完整的文本自动分类系统以检测本论文提出的文本分类 算法的效率。 关键词文本自动分类；特征提取；并行；多线程 竺尘堡型三尘兰：兰竺! ! 兰堡丝三 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 ft h ec h i n e s e d o c u m e n ta u t o m a t i cc a t e g o r i z a t i o nb a s e do nw e b a b s t r a c t a si n f o r m a t i o no ni n t e r n e ti sa v a i l a b l ei na b u n d a n c e i ti sb e c o m i n gav i t a l s o u r c eo fk n o w l e d g eg e t t i n g b u ti n f o r m a t i o ni st o om u c ht ol o o ku pv a l u a b l e o n e e f f i c i e n t l y s oi t i sv e r yi m p o r t a n tt on e a t e nt h ei n f o r m a t i o no ni n t e r n e t t h i s d i s s e r t a t i o nf o c u so nc h i n e s ew e bd o c u m e n ta u t o m a t i cc a t e g o r i z a t i o n ，w h i c hi s t h ec o r et e c h n o l o g yf o ri n t e r n e ts e a r c he n g i n e ，i n f o r m a t i o nf i l t r a t i o n ，i n f o r m a t i o n s e a r c h ，t e x td a t a b a s e ，a n dd i g i t a ll i b r a r y t h et e x tc a t e g o r i z a t i o ni st oc a t e g o r i z et h et e x ta c c o r d i n gt ot h ea t t r i b u t e ( c o n t e n t ) u n d e r t h ec e r t a i n c a t e g o r i z a t i o ns y s t e m g e n e r a l l y , t h e t e x t c a t e g o r i z a t i o ns h o u l db es u p p o r tt h et r a i n i n gs e t t h et r a i n i n gs e ti sa c o l l e c t i o n o ft h et e x t ，w h i c hi sm a d eu po ft e x tc a t e g o r i z e da l r e a d y ( g i v e nc e r t a i nt y p e s y m b 0 1 ) a n de v e r yt y p es h o u l di n c l u d ec e r t a i nn u m b e rt r a i n i n gt e x t ，a c c o r d i n g t ot h ec a t e g o r i z a t i o ns y s t e ms e t t i n g t h et y p es e l e c t o rs h o u l db et r a i n e db ya c e r t a i n s t u d y i n g m e t h o db e f o r eu s e dt os e l e c tu n k n o w nt e x t t h et 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 np r o v i d ef i n es u p p o r tt ot h ei n f o r m a t i o no r g a n i z e r ， a n dc a ns a t i s f yt h ei n f o r m a t i o ns e a r c hb e t t e r t h el e v e lo ft h et e c h n o l o g yw i l l d i r e c t l yi n f l u e n tt h ee f f i c i e n c yo f t h es e a r c h i n g t h ec h a r a c t e r m a t c h i n g a n dd o c u m e n t c a t e g o r i z a t i o n a r i t h m e t i co f d o c u m e n ta u t o m a t i cc a t e g o r i z a t i o na r es t u d i e di n t h i sp a p e r am e t h o di s p r o p o s e d b a s e do nm u l t i t h r e a d i n gt oa c h i e v et h ep a r a l l e lo p e nd o c u m e n t a u t o m a t i c c a t e g o r i z a t i o n s e v e r a l d o c u m e n t c a t e g o r i z a t i o n a r i t h m e t i ca r e i n t e g r a t e di n t oo n e t h a tc a nb er u nb ys i n g l eo rt o g e t h e r a no p e ni n t e r f a c ec a nb e d e s i g n e d f o ra l la r i t h m e t i c ，w h i c hc a na d dn e wd o c u m e n tc a t e g o r i z a t i o n a r i t h m e t i ca n dd e l e t et h eo u t d a t e d t h em e t h o do fc h a r a c t e rm a t c h i n ga l s ou s e s t h es a m eo n e a sar e s u l t ，t h ec o m p a t i b i l i t ya n dv e r a c i t yo ft h ed o c u m e n t c a t e g o r i z a t i o ns y s t e mw i l lb ei m p r o v e dal o t a n da tl a s t ，t h ew h o l ed o c u m e n t i i 竺! ! 篁竺二垒兰：兰竺! ：兰丝尘兰 a u t o m a t i cc a t e g o r i z a t i o ns y s t e mi sd e v e l o p e dt oc h e c kt h em e t h o dp r o p o s e di n t h i sp a p e r k e y w o r d s d o c u m e n ta u t o m a t i cc a t e g o r i z a t i o n ；c h a r a c t e rm a t c h i n g ；p a r a l l e l ； m u l t i t h r e a d i n g i i i 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于w e b 的中文文档自动分 类的研究与实现，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间 独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含 他人己发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均 已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：弘冻焉罗开期：a 即印年弓月1 6 日 哈尔滨理工大学硕士学位论文使用授权书 基于w e b 的中文文档自动分类的研究与实现系本人在哈尔滨理工大学 攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈 尔滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全 了解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关 部门提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学 可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内 容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密口。 ( 请在以上相应方框内打4 ) 作者签名：j 反冻勿只期：如7 年；月，5 只 导师签名：丁铆彳易同期：l 叩年；月侈同 晴尔演理t 人学t 学碗1 学位论文 第1 章绪论 1 1课题来源 本课胚来源于横向项目。 1 2研究的背景和现实意义 随着i n t e r n e t 及其相关技术的飞速发展，互联网上出现了海量的、异质的 w e b 信息资源，在这些庞大的信息资源中，蕴含着具有巨大潜在价值的知识。 人们迫切需要能够从w e b 上快速、有效地发现资源和知识的工具l lj 。于是功能 强大的搜索引擎问世了( 如g o o g l e ，a l t av i s t a 和b a i d u 等) ，这些搜索引擎可以 按照知识的种类进行分门别类建立索引，有效的减轻了人们从海量的信息资源 中寻找有价值信息的负担。但是，由于网络信息的爆炸式增长，搜索引擎的覆 盖率有限，其查全率低；同时，大多数搜索引擎都是基于全文的检索，不能达 到赋词标引的效果，也导致查准率较低。再者，绝大多数搜索引擎智能化水平 低，不能有效地提供个性化用户服务：加之最重要的一点是，搜索引擎的目的 在于定位w e b 上的资源，就w e b 上的知识发现而言，搜索引擎不能够胜任。 为了从海量数据中发现有效、新颖、潜在有用、可最终理解的模式，数据 库领域引入了数据挖掘( d a t am i n i n g ) 。但是，数据挖掘的主要对象是结构化的 数据仓库( d a t aw a r e h o u s e ) ，对于w 曲上的异质、非结构化信息，并不能直接 应用数据挖掘的技术。为了解决这个问题，人们将传统的数据挖掘技术跟w e b 技术相结合形成了现在的w e b 挖掘技术，w e b 挖掘作为一个具有挑战性的新 课题被提了出来，并得到了业界人士的广泛关注。另外研究发现，在海量的 w e b 信息资源中，有8 0 以上的信息是以文本的形式存在的，因此隶属于w e b 内容挖掘的w e b 文本挖掘显得尤为重要口】l ”。 w e b 文本挖掘就是从w e b 文档和w e b 活动中发现、抽取感兴趣的潜在的 有用模式和隐藏的信息的过程。w e b 文本挖掘和通常的平面文本挖掘有类似之 处，但是，w e b 文档中的标记给文档提供了额外的信息，可以借此提高w e b 文本挖掘的性能，w e b 文本挖掘是文本挖掘的主要研究内容。w e b 文本挖掘对 我们充分利用w w w 资源很有帮助，可以使用户比较准确找到需要的资料； 哈尔滨理t 人学t 学硕i 学位论文 同时还可以帮助用户节约搜索时问，提高w e b 文档的利用价值等。w e b 文本 挖掘可以对w e b 文档集合的内容进行总结、分类、聚类、关联分析以及趋势 预测等1 4 1 1 ”。 w e b 文本分类是w e b 文本挖掘的一项重要技术，是指将w e b 文档集合中 每个文档归入一个预先定义的类别之中。这样，用户在浏览w e b 文档时，就 不会因为纵横交错的超链接而“迷路”，而是基于一种主题分类的指导。目 前，y 抽o o 还是基于人工手工来对w e b 上的文档进行分类，这种作法存在弊 端：一是耗费了大量的人力和物力，二是由于个人的主观因素导致分类结果存 在不一致现象：同时大大降低了索引数目，另外由于互联网的飞速发展，w e b 上大量的文本信息急剧增加，这种超出想象的信息增长迫切需要更高效更智能 化的文本分类技术的产生，从而使得分类的j 下确率提高，保证检索结果的查全 率和准确率“。 网络诞生最初的目的是为了发布信息和共享信息，网络从最初的少量研究 机构之白j 的信息共享发展到今天的因特网让全世界信息共享，搜索引擎极大地 方便了人们的知识获取，也开创了新的商业模式，尽管目前主要的搜索引擎如 g o o g l e 、雅虎、百度等都没有向用户收取任何费用，但在将来可能上演e m a i l 收费的路线，以付费的方式向特殊用户提供更为专业的信息检索服务。当前搜 索引擎技术的竞争己经达到了白热化的程度，如g o o g l e 投入了1 0 亿美元在美 国斯坦福大学成立搜索引擎技术研究中心，微软也推出了自己的搜索引擎。显 然其背后的经济价值是不言而喻的1 7 1 1 ”。因此，本课题的研究有着广泛的应用 前景和重要的研究意义。 1 3国内外的研究现状 1 3 1w e b 文本挖掘的研究现状 以w e b 文本为对象的文本挖掘被称为是w e b 文本挖掘。w e b 文本挖掘属 于w e b 内容挖掘的范畴，可以对w e b 上大量文档集合的内容进行文本检索、 概括、分类、聚类、关联分析、趋势预测和网络导航等。 第一，文本检索主要研究对整个文档文本信息的表示、存诸、组织和访 问，即根据用户的检索要求，从数据库中检索出相关的信息资料。目f j 存在三 种检索方法：布尔模型是简单常用的严格匹配模型，如清华大学的中国学术期 刊( 光盘版) 采用就是布尔模；概率模型利用词条1 1 日j 和词条与文档问的概率相关 性进行信息检索，如美国马萨诸塞大学开发的i n q r e r y 文本检索系统；向量 空自j 模型在于将文档信息的匹配问题转化为向量空问中的矢量匹配问题处理， 如美国康乃尔大学基于向量空间模型丌发了s m a r t 文本检索系统。 第二，文本概括是指从w e b 文档中抽取主要的信息，从而形成关于文本 内容的简洁摘要，又称为自动摘要。例如，搜索引擎在向用户返回查询结果 时，通常需要给出文档的摘要，使用户在浏览全文之前可以快速了解文档的主 要内容。目前，绝大部分搜索引擎采用的方法是截取文档中出现检索词频次最 高的几行或者几句话作为摘要，并不考虑检索词位置和匹配长度问题，因此摘 要的效果很差【9 l 。 第三，文本分类是w e b 文本挖掘的一项重要技术，是指将w e b 文档集合 中每个文档归入一个预先定义的类别之中。近年来涌现出了大量的适合于不同 应用的分类算法，如：基于归纳学习的决策树( d t d e c i s i o nt r e e ) 、基于向量空 间模型的k 最近邻( k n n ，kn e a r e s tn e i g h b o r ) 、基于概率模型的朴素贝叶斯 m b ，n a i v eb a y e s ) 、神经网络( n n ，n e u r a ln e t w o r k ) 、基于统计学习理论的支持 向量机( s v m ，s u p p o r tv e c t o rm a c h i n e ) 方法等。 第四，文本聚类与分类的不同之处在于，聚类没有预先定义好的主题类 别，它的目标是将文档集合分成若干个簇，要求同一簇内文档内容的相似度尽 可能地大，而不同簇间的相似度尽可能地小。聚类方法主要有：划分方法、层 次方法、基于密度的方法、基于网格的方法和基于模型的方法等。 第五，关联分析最早被应用于“货篮子”的研究，这罩是指文档之间以及 文档集合中不同词语之f n j 的关联关系，即不同的几个词语出现在同一篇文档中 的概率研究i l o l l ”i 。例如，b r i n 提出了一种从大量文档中发现一对词语出现模式 的算法，并用来在w e b 上寻找作者和书名的出现模式，从而发现了数千本在 a m a z o n 网站上找不到的新书籍。 第六，趋势预测( 也称为分布分析) 是指通过对w e b 文档的分析，得到特定 数据在某个历史时刻的情况或将来的取值趋势。f e l d m a n 等人使用多种分布模 型对路透社的几万多篇新闻进行了挖掘，得到主题、国家、组织、人、股票交 易之间的相对分布，揭示了一些有趣的趋势。还可以通过分析w e b 上出版的 权威性经济文章，对每天的股票市场指数进行预测，取得了良好的效果f 1 2 ”j 。 第七，网络导航：文本挖掘技术可以通过分析用户的网络行为等，帮助用 户更好地寻找有用信息，一个典型的例子是c m u 的w e bw a t c h e r 。这是一个 在线用户向导，可以根据用户的实际点击行为分析用户的兴趣，预测用户将要 选择的链接，从而为用户进行导航1 1 4 i 。 喻尔滨理t 大学t 学硕i 学位论文 1 3 2w e b 文本分类的研究现状 1 3 2 1 文本分类方法的研究现状在w e b 出现之前，人们已经对文本自动分 类问题进行了大量的研究，形成了稳当自动分类技术。随着w e b 上海量的文本 信息的增加，文档自动分类技术的处理对象从普通的文档扩展到了w e b 文本。 很显然，文档自动分类技术也成为w e b 文本分类技术的基础。 国外对于文本自动分类的研究开展较早，5 0 年代未，h p l u h n 在这个领 域进行了开创性的研究，提出了基于词频统计思想的文本自动分类方法。1 9 6 0 年，m a r o n 发表了关于自动分类算法的第一篇论文，随后以k s p a r k gs a l t o n 以及k s j o n e s 等人为代表的众多学者也在这一领域进行了很有成效的研究工 作。目前国外的文本分类研究已经从实验性阶段进入到了实用化阶段，并在邮 件分类，电子会议等方法取得了广泛的应用，其中较为成功的有麻省理工学院 为白宫开发的邮件分类系统和卡内基集团为路透社开发的c o n s t r u e 系统l 【1 6 1 。 国内对于文本自动分类的研究起步较晚，1 9 8 1 年，侯汉清教授对计算机 在文本分类工作中应用作了探讨和阐述。此后，我国陆续研究产生了一些文本 分类系统，其中有具有代表性的有上海交通大学研制的基于神经网络算法的中 文自动分类系统，清华大学的自动分类系统等等。同时在不同的分类算法方面 也展开了广泛的研究和实现，中科院计算所的李晓黎、史忠植等人应用概念推 理网进行文本分类，召回率达到9 4 2 ，准确率达到9 9 4 。中国科技大学的 范众等人在k n n 、贝叶斯和文档相似性研究的基础上提出了一个超文本协调 分类器，正确率接近8 0 9 6 ，它的特点是适当的考虑了h t m l 文本中结构化 信息。复旦大学和富士通研究中心的黄营著、吴立德等人研究了独立语种的文 本分类，并以词汇和类别的互信息量为评分函数，考虑了单分类和多分类，最 好的召回率为8 8 8 7 。上海交通大学的刁倩、王永成等人结合词权重和分类 算法进行分类，基于v s m 的封闭式测试实验中分类诈确率达到9 7 。 目前，一些比较成熟的文本分类算法己经被应用到了w e b 文本分类中， 其中有基于s v m 的向量距离法、贝叶斯分类算法、k n n 分类算法、支持向量 机分类算法、决策树分类算法和神经网络分类算法等等，近些年还出现了基于 粗糙集合理论的文本分类算法和一些结合多种方法的混合分类方法m 1 。 1 3 2 2 分类关键技术的研究现状在对w e b 文本进行分类的过程中，包括几 个关键步骤：文本预处理、分词、权重计算、特征提取、降维技术，这些关键 技术的研究和实现对最终的分类算法都有一定程度上的影响，下面将对分词、 权重计算、特征提取和降维技术的研究现状做简单介绍。 哈尔演理t 人学t 学顾f 。学位论文 1 分词的研究现状语分词是中文文本分类的一个基础环节。汉语不像英 语那样，词与词之间存在明显的分词标记，如空格、换行和标点符号：而汉语 是一种无明显词间间隔的语言，词与词之白j 没有分割标记和界限，因而存在一 个如何分词的问题就是分词技术。 汉语自动分词是机器翻译、文献标引、智能检索、自然语言理解与处理的 基础，也是中文文本分类的一个关键的环节8 i i ”i 。自从8 0 年代初自动分词被 提出以来，有众多的专家和学者为之付出了不懈的努力，涌现了许多成功的汉 语分词系统，主要有北京航空航天大学研制的c d w s 和c w s s 分词系统，分 词速度为2 0 0 字每秒。清华大学黄昌宁、马晏等丌发的s e g 系统，分词速度 为2 5 9 字每秒，正确率为9 9 3 。东北大学姚天顺建立的基于规则的汉语分词 系统；南京大学王启祥等人实现的w s b n 分词系统。中科院计算所研制出的 汉语词法分析系统i c t c l a s 等等。 汉语自动分词系统的实现及效果依赖于分词理论与方法。目前国内分词系 统所采用的或者正在研究的方法基本上分为三类：机械分词、基于理解的分词 和基于统计的分词。 2 权重计算的研究现状文本的基本元素是词、词组和短语，文本经预处 理和分词后，抽取能表示文本的特征项组成文本的特征向量形式， v ( d ) = ( tj ，w l ( d ) ，t 2 ，w 2 ( d ) ，t 。，w 。( d ) ) 其中w i ( d ) 表示对应特征项的权重。特征 项的权重综合反映了该特征项对标识文本内容的贡献度和文本之间的区分能 力。 常用的特征项权重计算函数有以下几种：和尔函数、开根号函数、w i d f 函数、著名的 i t i d f 公式法；其中t f i d f 函数基本思路是使用频率因子t f ( t e r mf r e q u e n c y ) 进行特征项的赋权，同时还要考虑文档集因子i d f ( i n v e r s e d o c u m e n tf r e q u e n c y ) ，体现出查询内容与文档的相关度大小，一般采用使用出 现频率的倒数来计算，i d f = l o g ( n n j ) ，其中n 为文档集合，n j 为查询内容在文 档中出现的次数。作为一种应用比较广泛的权重计算方法t f i d f 公式法， 也存在不足之处，一方面，传统的特征权重算法存在明显的不足。因为t f i d f 是将文档集作为整体来考虑的，特别是其中i d f 的计算，并没有考虑到特 征项在类删和类内的分布情况。如果某一特征项在某个类别大量出现，而在其 它类别出现很少，这样的特征项的分类能力显然是很强的。但这在t f i d f 算 法中是无法体现的。另一方面，同样是集中分御于某一类别的不同特征项，类 内分布相对均匀的特征项的权重应该比分布不均匀的要高，因为如果某一特征 项只在某个类别的一两篇文档中大量出现，而在类内的其它文档中出现得很 哈尔滨理t 人学t 学硕l 。学位论空 少，那么不排除这一两篇文档是该类别中特例的情况，因此这样的特征项不具 备代表性，权重相对较低。对于这种情况，传统的t f i d f 算法也不能很好地 处理。 于是，权重的计算只能视具体情况而定，至今仍没有普遍使用的“最优公 式”，也需要我们在这个方面进行进一步的研究。 3 特征选择的研究现状特征选择就是从特征集t = t i ，t s 中选择一个真 子集t = f t h - - , t s ， ，其中，s 为原始特征集的大小，s 为选择后的特征集大小。 选择的准则是经特征选择后能有效提高文本准确率。选择没有改变原始特征空 间的性质，只是从原始特征空自j 中选择了一部分重要的特征，组成一个新的低 维空间。 文本分类中，用于特征选择的统计量大致有：特征频度，文档频度，特征 熵，交互信息，信息增益，统计总量，特征权，期望交叉熵等。这些统计量从 不同的角度度量特征对分类所起的作用”o l 。 目前，也出来了一些新的特征选择方法，如低损降维方法、频率差方法、 b a y e s 准则法、f l 值准则法和f i s h e r 简便量法等。 1 3 3 需要进一步研究的问题 目前国内对w e b 文本分类的研究还没有到达一个成熟的阶段，其中还存 在许多待解决和研究的问题： 首先，分词是影响文本分类的重要因素之一，分词的速度和准确率与最 终的分类结果密切相关。尤其是w e b 上不断出现新词汇，对分词理论的创新 和词典的构造都提出了较高的要求。 其次，目前还没有发现“最佳”的特征选择方法，针对中文w e b 文本分 类的组织特点，需要结合特定的特征选择，因此在使用不同分类算法时如何选 择最佳的特征选择方法也是我们需要深入研究的问题。 再次，由于中文文本分类起步晚和中文不同于英文的特性，目i j 中文 w 曲文本分类还没有标准的开放的文本测试集，各研究者大多使用自己建立的 文本集进行训练和测试，其分类结果没有可比性，不利于交流和提高。 最后，目i i f 存在多种成熟的文本分类算法，大部分分类系统都是应用某 一种分类算法，分类性能受到制约。针对这些算法的各自的优缺点，我们是否 可以找到更高效的混合分类方法，从而达到扬长避短，也是我们币在和今后研 究工作的重点。 哈尔滨理t 人学t 学颂f 学位论上 1 4 本课题的主要研究内容 目前文本自动分类中的两个关键步骤：特征选择以及文本分类存在着大量 不同的算法。由于w e b 文本的数量巨大，涉及内容的极其广泛造成的极其复 杂性，没有哪个算法能对所有类别的文本得到很好的分类结果。因此，各个特 征选择方法以及分类算法分别在某些领域和某些方面有比较好的效果，而在另 外的些方面及领域又显得不足。为此，本文深入研究了特征选择和文本分类 的一些目前最具代表性的算法，提出了个较好的解决方案。 哈尔滨理t 人学t 学颀1 学位论殳 2 1特征提取 第2 章特征提取及文本分类技术的研究 根据j o h np i e r r e 的理论，用束表示文本的特征理论上应具有如下特点： 第一，数量上尽量少： 第二，出现频率适中； 第三，冗余少； 第四，噪音少； 第五，与其所属类别语义相关； 第六，含义尽量明确。 就w e b 文本来说，先将h t m l 标签按特征进行过滤变成纯文本。因此最 方便采用的特征就是词或短语。作为文本组成的最小单位，选择他们作为特征 具有天然的优势。受自然语言处理技术的局限，也出于实用性的考虑，目i i 相 对成熟的方法均不涉及任何语义处理。只以单个的词或短语作为文本的特征， 并且忽略了他们在文本中出现的顺序( 即结构信息，某种程度上这也是出于实 用性的考虑。) 在多数基于统计的分类模型中。这种文本的表示方法均取得了 良好的效果。以下将对目前主要的特征方法进行介绍口”。 2 1 1i g 特征提取 i g ( i n f o r m a t i o ng a i n ) ，即信息赢取。i g 值代表了特征在训练集上的分布情 况，它通过统计特征在各个类别中的出现次数来计算，公式如下： g ( f ) = 一：p ( c ) 1 0 9 p ( c ，) + p ( ，) ：。e ( qi t ) l o g p , ( c , i f ) + ，、 p 仃) ：p ( 1 7 ) l o g e , ( c , i7 _ ) 其中t 代表特征，e 代表第i 个类别，m 为类别数，p 代表概率i g 值越 高表示该特征在训练集中的类别上分布越集中，i g 方法提取i g 值较高的特 征，其基本思想为分布越集中的特征越重要。 坠尘篁些三垒耋二兰竺! ：兰竺篁兰 2 1 2m i 特征提取 m if m u t u a li n f o r m a t i o n ) ，互信息值，它通过计算机t 和类别c 间的相关性 来完成提取。计算机公式为： m ，c ) = l 。g 瓦p a 而t a c ) 万 ( 2 2 ) 为方便计算，可简化为： m ，c ) l o g 面丽a x 石n 两 ( 2 3 ) 其中n 为训练集中包含的文本总数，a 为t 与c 同时出现的次数，b 为t 出现而c 不出现的次数，c 为c 出现而t 不出现的次数。通过该公式就可以取 得特征与各类别间的互信息值【2 2 i 。为了能取得特征在数掘集上的整体评价，有 以下两种计算方法： k ( f ) = 只( e ) ，( f ，q ) ( 2 - 4 ) ，嘣( f ) = m，q ) ) ()_axl(t 2 - 5 公式( 2 - 4 ) 代表了特征和各类别的平均互信息值，公式( 2 5 ) 则取特征与各类 别互信息值中的最大值。m i 方法提取互信息值较高的特征，其基本思想为与 类别相关性越高的特征越重要。 2 1 3c h i 特征提取 c h i 具有和m i 方法基本相似的思想，同样通过计算特征t 和类别c 阳j 的 依赖程度来完成提取。但二者的计算细节不同，c h i 作了更多地考虑，有种看 法认为c h i 是一种“j 下规化”了的m i 。c h i 的计算公式如下： c h i ( ，= 而蒜筹篙而 ( 2 - s ) 其中n 为训练集中包含的文本总数，a 为t 与c 同时出现的次数，b 为t 出现而c 未出现的次数。c 为c 出现而t 未出现的次数，d 为二者都未出现的 次数。与m i 相同c h i 也有平均值和最大值两种方法来取得特征的整体评 价： 晴尔演理t 人学t 学坷! i 。学位论史 c h i 。x ( t ) = i a e ，) c h i ( t ，e ) ( 2 7 ) ，_ l c h i = 。( f ) = 1 1 1 a x c h l ( t ，q ) ( 2 - 8 ) c h i 方法的基本思想也是与类别关系越紧密的特征重要性越高叫i 。 2 1 4d f 特征提取 d f ( d o c u m e n tf r e q u e n c y ) ，即文档频率，指训练集中包含该特征的文本总 数。所谓文本包含特征是指这个特征在该文本中出现，忽略其在文本中的出现 次数。d f 方法提取d f 值较高的特征，它的目的是去掉在训练集上出现次数 过少的特征，保留出现达到一定次数、具有一定影响力的特征。在各个特征提 取方法中，d f 方法的计算是最简单。 2 2分类方法 文本向量经过降维处理之后。就可以使用这些特征向量束表示文本。文本 分类方法需要一个类别己标识的文本数据集柬训练分类器，然后用训练好的分 类器对未标识类别的文本进行分类。文本分类方法通过构造某种分类模型( 也 称为分类器) ，并以此判断样本所属的类别。分类器的构造方法有许多种，本 文介绍了贝叶斯方法、k 近邻方法、决策树方法、支持向量机方法、神经网络 方法、投票方法、r o c c h i o 方法和s l e e p i n ge x p e r t 方法。 2 2 1 贝叶斯方法 贝时斯方法( b a y e sm e t h o d ，b m ) 在机器学习领域中应用很广泛。贝叶斯方 法分两种：一种是朴素贝叶斯方法州a i v eb a y e sm e t h o d ，n b m 】，它假设每个特 征都独立于其它特征，即特征独立性假设。但是，大部分情况是文本特征之间 的依赖关系是存在的，所以特征独立性假设会影响朴素贝叶斯分类的结果。另 一种是贝叶斯网络分类方法fb a y e s n e tm e t h o d ，b n m ) ，它考虑特征之间的依赖 关系，该方法更能真实地反映文本的情况，但是其计算复杂度比朴素贝叶斯高 得多1 2 4 1 1 2 ”。 哈尔滨理t 人学t 学硕l 学位论文 2 2 2k 近邻方法 k 一近邻方法( k n e a r e s tn e i g h b o r , k - n n ) 是由c o v e r 和h a r t 于1 9 6 8 年提出 的，直至现在仍在很多领域中应用。k 近邻方法是一种基于统计的分类方法， 该方法根据测试文本在训练文本集中与之最相近的k 篇文本的类别来判定它的 类别。 2 2 3 决策树方法 决策树( d e c i s i o nt r e e s ，d t ) 方法是一种常用的分类技术，它是以实例为基 础的归纳学习算法。给定关于某个概念的一系列己知的下例和反例，归纳学习 的任务是从中归纳出一个通用的概念描述。归纳学习能够获得新的概念，创立 新的规则，发现新的理论。它一般的操作是泛化和特化，泛化操作用来扩展假 设的语义信息，使其能够包含更多的丁f 例，应用于更多的情况：特化操作与泛 化操作相反，用于限制概念描述的应用范围。 决策树方法的任务是通过一组无次序、无规则的实例推理出树型的分类规 则。它采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较并根 据不同的属性值判断从该结点向下的分支，在决策树的叶结点得到结论。所以 从根结点到叶结点的一条路径就对应着一条合取规则，整棵决策树就对应着一 组析取表达式规则2 i i7 】【2 ”。 决策树方法的优点是它在学习过程中不需要使用者了解很多背景知识，只 要训练样例能够使用属性一结论式的方式表达出来，就能使用该方法来学习。 典型的决策树方法有c a r t 方法、i d 3 方法和c 4 s 方法。 2 _ 2 3 1c a r t 方法c a r t ( c l a s s i f i c a t i o na n dr e g r e s s i o nt r e e s ) 方法由f r i e d m a n 于1 9 7 7 年提出的，根据一个独立向量函数在每个结点分开训练集向量建立二 叉树。因此首先的任务是决定哪个向量作为最好的分割点，它最好尽可能将同 类子集划分在一起，这就是说最好的分割点应该是最大限度地减少训练集样例 之间的差异。 2 2 3 2i d 3 方法目前普遍应用的差异测试方法是使用“嫡”计算。如q u i n l a n 与】9 7 9 年提出的i d 3 算法，它采用自顶向下贪婪搜索的方法遍历可能的决策 树空间。i d 3 方法基于信息熵理论，选择当前样本集中具有最大信息增益的属 性作为测试属性，并采用划分后样本集的不确定性作为衡量划分好坏的标准。 2 2 3 3c 4 5 方法c 4 5 方法是q u i n l a n 于1 9 9 3 年提出的，是i d 3 方法的后 哈尔演埋t 人学丁学顺i 学位论文 续，对每个结点制造不同数目的分支，也是多决策树方法的基础，在单机的决 策树方法中，它的分类速度是较快，并且精确度也比较高。c 4 5 方法在效率上 有了很大的提高。不仅可以直接处理连续型属性，还允许训练集中出现属性空 缺的样本，并且生成的决策树的分枝也较少。但该算法仍然没有脱离信息熵原 理，因而生成的树仍是多叉树。 2 2 4 支持向量机方法 v a p n i k 等人在2 0 世纪6 0 年代开始研究有限样本情况下的机器学习问题， 到了9 0 年代，逐渐形成了较完善的统计学习理论体系。在统计学习理论的基 础之上发展出了支持向量机方法( s u p p o r tv e c t o rm a c h i n e ，s v m ) 1 2 9 】1 3 0 l 。 对于一个给定的具有有限数量训练样本的学习任务，如何在准确性( 对于 给定训练集) 和机器容量( 机器可无错误地学习任意训练集的能力) 两方面进行折 衷，以得到最佳的推广性能。s v m 采用计算学习理论的结构风险最小化 fs t r u c t u r a lr i s km i n i m i z a t i o n 。s r m ) 原则。其主要思想是在高维空间内寻找将训 练数据分成两类的最佳超平面o s h ( o p t i m a ls e p a r a t i n gh y p e r - p l a n e ，o s h ) ，以 保证最小的分类错误率，在训练集中以支持向量( s u p p o r t v e c t o r , s v ) 为基础。 首先考虑对应图2 1 所示的二维空间上的简单分类问题，讨论函数g ( x ) 是 线性函数g ( x ) = ( w x ) + b 的情况，其中x 是输入向量，w 是法向量，“”代 表两个向量的内积运算符号。分类问题就是要寻找一条合适的直线划分整个二 维平面，即确定法方向w 和截距b 。 图2 - 1 支持向封机原理i 璺| f i g 2 - 1s u p p o av e c t o rp r i n c i p l ec h a r t 能将两类中的点正确分丌的直线很多，如直线l ，假设它的法方向为w ， 不改变法方向，平行地向右上方或左下方推移直线l ，直到碰到某类训练点。 哈；j = 演理t 人学t 学砸i 学位论史 这样就得到了两条极端的直线l 1 和l 2 ，称这两条直线之间的距离为在该法方 向上对应的“间隔”。支持向量机方法从解决线性可分情况的最佳分类面出发 的，其思想就是选取使“间隔”达到最大的那个法方向，相应得到的两条极端 直线就是最佳分类线。如果一个训练集中的矢量能被一个超平面无错误地线性 分割，且距该超平面最近的矢量之间的距离最大，则称该超平面为最佳超平 面。其中对决策面设计起决定作用的点，称为支持向量。使分类“白j 隔”最大 实际上就是对推广能力的控制，这是s v m 的核心思想之一。最小化训练误差 和最大化泛化能力( 推广能力) 就是体现了支持向量机最小化结构风险的思想。 进一步说，对于选定的法方向w ，会有两条极端的直线，选取b 使得要找的直 线为两条极端直线“中间”的那条直线。 对线性可分问题，用直线方程分别来表示这三条直线。由于表示同一条直 线的方程很多，所以先将直线方程规范化，即调整w ，b ，使得两条极端的直线 l l 和l 2 分别表示为： ( w - x ) + 6 = l( r ) + b = - i( 2 9 ) 中间的划分直线为： ( w x ) + 6 = 0 ( 2 1 0 ) 由规范形式的划分直线直接计算可知，相应的两条极端直线的距离为 11 l ，即相隔i n 距为j 乇，这里的1 1w 表示范数。使训练误差达到最小， 1 1 w w | i 或者说使训练错误率为零，这正是体现了s v m 极大化“i u j 隔”的思想，实质 1l 上就是求解的最优化问题m a x 击，或者m i n - ；| f w 2 。 w i | 2 对于非线性问题，可以通过非线性变换转化为某个高维空间的线性问题， 在高维空间求最优分类面。这种变换可能比较复杂，因此不容易实现。 超平面是对两类分类的划分，对于大于两类的多类文本分类，就对每个类 构造一个超平面，将这一个类与其余的类分开。有多少个类就构造多少个超平 面。测试时就看哪个超平面最适合测试样本1 3 1 。 支持向量机的优点在于： 首先，它是专门针对有限样本情况的分类方法，其目标是得到现有信息下 的最优解而不仅仅是样本数趋于无穷大时的最优值，该算法最终将转化成为一 个二次型寻优问题，理论上得到的将是全局最优点，避免了局部极值问题。 其次，该方法将实际问题通过非线性变换转换到高维的特征空间，在高维 特征空间中构造线性判别函数束实现原空间中的非线性判别函数，特殊性质能 阶 j ：i e 理t 人学t 学倾i 学位论史 保证具有良好的推广能力，计算的复杂度不再取决于空间维数，而是取决于样 本数，尤其是样本中的支持向量数，这些特点就可能有效地用于解决高维问 题。 再次，该方法对稀疏数据不敏感，更好的捕捉了数据的内在特征，准确率 较高。支持向量机方法的缺点是参数调整比较困难，分类比较费时。 2 2 5 神经网络方法 神经网络m e u r a ln e t w o r kn n ) 是模仿人脑神经网络的基本组织特性构成的 新型信息处理系统。神经网络通常由输入层、输出层和若干个隐层组成，输入 层的神经元个数等于样本的特征数，输出层就是分类判决层，它的神经元个数 等于样本类数。每个神经元有一个单一的输出，它可以连接到很多其它的神经 元，其输入有多个连接通路，每个连接通路对应一个连接权系数，这些神经元 互连构成自适应、非线性的动态系统口