（通信与信息系统专业论文）基于聚类算法的knn文本分类系统研究与实现.pdf

摘要 随着社会的进步和i n t e r n e t 高速发展，如何快速准确地获取自己所需的信息已经成 为目前我们迫切需要解决的问题之一。文本分类和聚类是信息处理的重要技术，因而也 成为了目前研究的热点。本文主要研究了文本分类和聚类的相关算法，分析了其中的相 关技术以及难点。 首先，介绍了文本分类中所涉及的主要技术：文本表示、特征选择与抽取、分类算 法和分类性能的评测。其次，着重剖析了k n n 文本分类算法，指出其优点及不足。为了 克服k n n 分类器速度慢的缺陷，提出采用文本聚类对训练集样本库进行合并，将若干样 本合并为少量样本中心来减少计算量。再次，介绍了几种常见的文本聚类算法。对基于 划分的分类算法：k m e a n s 和k - m e d o i d s 进行了深入的分析与研究，发现k m e a n s 等基于 划分的聚类算法对聚类初始点选择十分敏感。应用较多的随机选取聚类初始点的方法虽 然简单，但是聚类结果很不稳定，时f h j 开销大。针对这一点，本文提出了基于文档相似 度的初始化聚类中心点算法，随后通过实验验证了其优越性，并采用这种基于文档相似 度的k m e a n s 聚类算法对训练集样本库进行合并。最后，本文设计并初步实现了一个基 于聚类算法的快速k n n 文本分类系统，通过实验验证了采用文本聚类对训练集样本库进 行合并，将若干样本合并为少量样本中心，可以在保证分类准确率的情况下，大幅提高 k n n 文本分类器速度。 关键词：文本分类特征选择 k n ns v m 文本聚类 k m e a n sk - m e d o i d s 聚类初始中心点 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 fs o c i e t ya n di n t e r n e t ，t h e r ei sa nu r g e n tn e e d o fo u r p r o b l e m st h a ti sh o w t oo b t a i nn e c e s s a r yi n f o r m a t i o na c c u r a t e l y a n dt e x tc a t e g o r i z a t i o na n d t e x tc l u s t e r i n ga st h ef o u n d a t i o no fi n f o r m a t i o np r o c e s s i n gi sb e c o m i n gm o r ep o p u l a r r e s e a r c h e so nt h ea l g o r i t h m so ft e x tc a t e g o r i z a t i o na n dt e x tc l u s t e r i n ga r ed o n ea n dp r o b l e m s i nt h i sp a p e r w ea n a l y s es o m ec r i t i c a lt e c h n o l o g i e sa n dm a k es o m ei m p r o v e m e n t s f i r s t l y , w e d i s c u s sd e e p l yt h e k e yt e c h n i q u e o ft e x tc a t e g o r i z a t i o n ，i n c l u d i n gt e x t p r e t r e a t m e m ，i n f o r m a t i o nr e t r i e v a lm o d e l ，f e a t u r es e l e c t i o n ，c l a s s i f y m e t h o d sa n dr e s u l t e v a l u a t i o na n de x p e r i m e n t st e s t s e c o n d l y , w ef o c u so na n a l y s i n gk n n a n dp o i n to u ti t s s t r e n g t h sa n dw e a k n e s s e s a sk n n i saa l g o r i t h mo ns a m p l ei n s t a n c e s ，w ep r o p o s ea ni d e a t h a td o c u m e n ts a m p l e sa r er e p l a c e db yl e s ss a m p l ec e n t e r st oo v e r c o m et h i sp r o b l e m s t h i r d l y ， w es t u d ys o m ec o m m o nt e x tc l u s t e r i n gm e t h o d s ，a n dd e e p l yd i s c u s sk - m e a n sa n dk - m e d o i d s a n df o u n ds e n s i t i v i n gt ot h ec l u s t e r i n gi n i t i a lp o i n ti nk - m e a n sa n ds oo n t h em e t h o do f s e l e c t i n gi n i t i a lc l u s t e r i n gc e n t r i o d sr a n d o m l yi ss i m p l e ，b u tc l u s t e r i n g r e s u l tu n s t a b l e ，a n d t a k i n gal o to ft i m e f o rt h i s ，t h i sp a p e rp r e s e n t si n i t i a lc l u s t e r i n gc e n t r i o d sa l g o r i t h m b a s e do n t e x ts i m i l a r i t y , a n dt h e nt h i sa l g o r i t h mi sp r o v e dt h a ti ti sb e t t e rt h a ns e l e c t i n gi n i t i a lc l u s t e r i n g c e n t r i o d sr a n d o m l y w ew i l lu s ek - m e a n sb a s e do nt e x ts i m i l a r i t yt oc o m b i n et h et r a i n i n g s a m p l e sf o rm a k i n gt h ek n nf a s t e r f i n a l l y , w e d e s i g n a n df i n i s ho n e 鼢州t e x t c a t e g o r i z a t i o ns y s t e mb a s e dc l u s t e r i n ga l g o r i t h m s t h e nw ed os o m ee x p e r i m e n t sw h i c h p r o v eo u rm e t h o di st r u e ，t h ec l a s s i f i c a t i o nr a t eo fk n n sc a nb eg r e a t l yi m p r o v e db y c l a s s i f i c a t i o n u s i n gc l u s t e r i n gt oc o m b i n et h et r a i n i n gs a m p l e sw i t hh i g hp r e c i s i o n k e y w o r d s ：t e x tc a t e g o r i z a t i o n f e a t u r es e l e c t i o nk n ns v m t e x tc l u s t e r i n g k m e a n sk m e d o i d s i n i t i a lc l u s t e r i n gc e n t r i o d s u 海南大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取 得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写 过的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律结果由本人承担。 论文作者签名：虹摊 日期：勋卵年月q - 日 学位论文版权使用授权说明 本人完全了解海南大学关于收集、保存、使用学位论文的规定，即：学校有权保留并向 国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权海南大 学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。本人在导师指导下完成的论文成果，知识产权归属海 南大学。 保密论文在解密后遵守此规定。 本人已经认真阅读“c a l l s 高校学位论文全文数据库发布章程”，同意将本人的学位论 文提交“c a l l s 高校学位论文全文数据库”中全文发布，并可按“章程”中规定享受相关 权益。回童途塞握銮丘进压；旦：l ：生；旦二生；旦二生蕉查。 论文作者签名：豆懒 日期：砰年石月午日 导师签名： 日期：砌 1 引言 1 1 信息检索定义 信息检索【1 儿2 i ( i n f o r m a t i o nr e t r i e v a l ) 将信息按一定的方式组织和存储起 来，并根据用户的需要找出有关信息的过程。处理的对象是非结构化数据，例如 文本数据、网页、多媒体数据等。目前最主要的处理对象是互联网。信息检索领 域一般用查全率和查准率对检索效果进行量化评价。 1 2 文本挖掘定义 文本挖掘【3 】( t e x tm i n i n g ) 是数据挖掘( d a t am i n i n g ) 的一个分支，它是把文本 型信息源作为分析的对象，利用定量计算和定性分析的方法，从中寻找信息的结构、模 型、模式等各种隐含的知识，这种知识对用户而言是新颖的，具有潜在价值。因此，文 本挖掘技术的出现为文本信息的整理、分析、挖掘提供了有效手段。文本挖掘过程1 4 l 一般包括文本准备、特征标引、特征集缩减、知识模式的提取、知识模式的评价、知识 模式的输出等过程。如图卜1 所示。 图卜1 文本挖掘的一股过程 1 3 研究背景及现状 随着科学技术的飞速发展，i n t e r n e t 得到了广泛的普及。一方面，它为信息发布 者提供了极大的自由：你可以很容易地向全世界发布你的思想及言论，以你最钟爱的方 式文本、声音或者图像；然而另一方面，这种快速、无序的增长对于信息的使用者 来说却意味着混乱：很多信息变得稀奇古怪、突然消失或者杂乱无章。那么，如何让这 本没有主编的，因而有些杂乱无章的百科全书为我们服务呢? 如何在纷繁复杂的 i n t e r n e t 信息与人们快速准确获取全面信息的渴求之间架设一座桥梁呢? 信息检索因 此而受到大家的关注。 信息检索领域是与数据库平行发展的，且已有许多年的研究历史。然而，随着文 本信息的迅猛增加，传统的信息检索技术己无法满足实际的需要，由于常常存在文档都 包含有用信息，但只有一小部分是与特定用户需求密切相关的情况。不清楚文档的内容， 就很难形成有效的查询。文本挖掘可以完成不同文档的比较，以及文档重要性和相关性 排列，或者找出多文档的模式及趋势。 目前研究和应用最多的文本挖掘技术是文本分类和聚类。事实上，聚类也是一种 分类。信息检索的重要基础是文本分类技术。长期以来，对于文本分类的研究已经很多， 分类算法一直是文本分类中的研究热点。国内当前流行的文本分类算法有k 近邻法( k n n ) i 5 - u l ，朴素贝叶斯法( n b ) 5 - 1 0 ，线性最小平分拟合法( l l s f ) ，神经网络法( n n e t ) ，支 持向量机法( s v m ) 5 - i 0 1 等，其中k n n 、n b 和s v m 的分类效果相对较好，成为近几年人们 研究的热点。本文研究的主要是k n n 分类算法。 k n n 法是c o v e r 和h a r t 于1 9 6 8 年提出，并在过去4 0 年里在模式识别中广泛的被研 究。k n n 是一种基于实例学习、非参数的分类技术，简单易行，并且分类效果良好，对 不同数据集都有很好的可操作性，被广泛的应用于基于统计的机器学习中。人们对k n n 分类算法展开了广泛的研究。香港中文大学的w a il a m 等人将k n n 方法和线性分类器结 合，取得了较好效果，在召回率接近9 0 时准确率超过8 0 1 2 j 。w l o d z i s l a wd u c h 提出 了通过选取特征对加权k n n 的研究【1 3 】。文献 1 4 提出了一种基于近邻搜索的快速k 一近 邻分类算法一超球搜索法。该方法通过对特征空间的预组织，使分类得以在以待分样本 为中心的超球内进行。超球半径由零开始逐渐增大至超球内包含k 个以上模式样本为止。 这一方法有效地缩小了算法搜索范围，同时预组织和预分类简单明了，无需复杂的训练， 不存在收敛性问题。文献 1 5 研究了回归函数k n 一近邻估计的渐进性质，得到了回归函 数的k n 近邻估计的渐进正态性和它的b o o t s t r a p 统计量的相合性。文献 1 6 为近邻算 法建立一个有效的搜索树，提高了查询速率。文献 1 7 提出了一种迭代近邻法，用以解 决k n n 算法在小样本库的环境下分类效果不佳的问题，在无法得到足够的定类样本时， 通过检索的方法将待分样本的局部主题特征放大，进而得到足够定类的相似样本。文献 1 8 分析了传统的近邻文本分类方法技术以及w e b 文本的特点，充分利用了w e b 文本的 结构信息进行特征词加权，以类轴向量为核心构建分类器。文献 1 9 提出了加权k 近邻 的方法，对训练集x 内的每一个样本点，给定一个临界半径，对一个待识别样本，比较 其与训练集中每个样本点的加权距离。文献 2 0 针对欧几里德空间的k 近邻，给出了其 在可重构网孔机器上( r m e s h ) 的并行算法。文献 2 1 2 2 谈到k n n 分类算法计算复杂性 的优化和分析。国内外对减少k n n 算法的计算量以提高k n n 分类效率的研究主要有两个 方向：一种是通过快速搜索算法，在尽量短的时间内找到测试样本的最近邻；另一种是 删除原来的训练样本集中的某些样本，并将剩下的样本作为新的训练样本，从而达到减 少训练样本集的目的。 本文主要采用聚类算法，通过设置合适的聚类簇数k 来合并训练样本库，减少k n n 分类器计算量，在保证分类准确度的前提下，大幅提高分类速度。 1 4 本文的主要工作 ( 1 ) 介绍了文本分类涉及到的关键技术，包括文本表示模型、特征权重计算方法、 特征选择与抽取、分类算法和分类效果的评测，并进行了深入的研究与分析。 2 ( 2 ) 着重剖析了k n n 文本分类算法，指出其优点及不足。为了克服k n n 分类器速度 慢的缺陷，提出采用聚类算法对训练集样本库进行合并，将若干样本合并为少量样本中 心来减少计算量。随后设置实验：对几种较好的特征选择方法进行比较分析；训练k n n 分类器的分类参数；比较k n n 与s v m 两种优秀算法的分类性能。 ( 3 ) 介绍了聚类算法，特别是对基于划分的分类算法：k - m e a n s 和k - m e d o i d s 进行 了深入的分析与研究，并且根据k - m e a n s 对聚类初始中心点十分敏感的问题，对聚类初 始点选择方法进行优化，提出一种基于文档相似度的聚类初始中心点算法，并通过实验 证明了它优于普遍采用的随机选取聚类初始中心点的方法。最后采用基于文档相似度 k - m e a n s 算法来实现将对训练样本集的合并。 ( 4 ) 初步设计实现了基于聚类的快速k n n 文本分类器，并通过实验来验证，基本实 现了在保证分类准确率的基础上大幅提高分类器分类速度。 1 5 本文组织结构 第一章：引言。介绍了本课题涉及的相关领域信息检索及文本挖掘，并分析了课题 研究的背景与现状，最后给出了本文的主要研究工作以及本文的整体结构。 第二章：文本分类。首先介绍了文本分类的定义以及文本分类过程。而后针对文本 分类中的相关技术：文本表示、特征选择与抽取、文本分类常用算法、分类效果的评测 进行了详细的研究。 第三章：k n n 分类算法。首先介绍了基于实例的分类算法，其次详细分析了k n n 文 本分类算法的实现思想与优缺点，针对k n n 分类速度慢这一缺点，提出采用聚类算法来 对训练集样本库进行样本合并，以减少k n n 分类器的计算量，提高分类器速度。最后通 过实验来对k n n 文本分类算法进行性能测试及参数训练，并与另外一种优秀的分类算法 s v m 算法进行了性能比较，得出在分类大量数据时，k n n 文本分类算法是一种更加稳定 的分类算法。 第四章：文本聚类。本章主要对文本聚类及其过程、文本聚类算法( 特别是基于划 分的聚类算法) 、文本聚类的评估做了详细的研究，发现k m e a n s 等基于划分的聚类算 法对聚类初始点选择十分敏感，通常采用的随机选取聚类初始点的方法虽然简单，但是 结果很不稳定，并且时间开销大。针对这一点，本文提出了基于文档相似度的初始化聚 类中心点算法，并且通过实验验证了其优越性。最后采用这种基于文档相似度的k - m e a n s 聚类算法来对我们的样本库进行合并。 第五章：基于聚类算法的快速k n n 文本分类系统的设计与实现。详细介绍了系统的 总体设计以及模块功能，并通过实验验证：本系统基本实现了在保证分类准确率的基础 上大幅提高分类器分类速度的目标。 2 文本分类 2 1 文本分类定义 文本分类【5 - 1 0 l 就是按照事先给定的分类体系和训练样例( 标注好类别信息的文本) ， 将文本分到某个或者某几个类别中。从数学的角度而言。分类的实质是一个映射过程， 它将为标明类别的文本映射到已有的类别中，该映射可以是一对一的映射，也可以是一 对多的映射。文献 2 3 给出了文本分类的形式化定义。文本分类就是将一个二元组( d i ，c i ) d c 映射到一个布尔值的任务。该映射用数学公式( 2 一1 ) 表示如下： ：dxc 一 t ，f ( 2 1 ) 式中卜有待分类的文本的集合，d = ( d l , d 2 ，d 。) ； c 给定分类体系下所有预先定义的类别的集合，c = ( c 1 ，c 2 ，c 。) ； 中判别公式和判别规则，根据已掌握的每类若干样本的数据信息而总结出分 类的规律性而建立； d 可以是无限集合，而c 必须是有限集合。如果将二元组( d i ，c i ) 映射值为t ( t u r e ) ， 则认为文档d ；属于类别c ，否则认为文档d ；不属于类别c ，。 文本分类是一种有监督、有指导的分类方法。它的流程图如图2 1 所示。 图2 - 1 文本分类流程图 4 2 2 文本表示 计算机不具有人类的智能，不能像人一样根据自身理解能力对文章产生模糊认识。 因此在文本分类之前，首先应将文本转换为易被计算机理解的形式，然后通过具体的文 本分类对文本类别进行划分。 文本的表示既要能使其方便计算机的处理，又要能够有效表达文本内容。大量研究 表明向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 是一种适合于大规模语料的文本表示模 型。 2 2 1 向量空间模型 向量空间模型【2 4 】【2 5 1 是由g e r a r ds a l t o n 和m c g ill 于二十世纪六十年代提出的，并 在著名的s m a r t 系统中实现。向量空间模型定义如下： 给定一个文本文档d = d ( ( t l ，w 1 ) ，( t 2 ，w 2 ) ，( ，n ，w n ) ) ，项可以在文档的不同位置重 复出现，为了简化分析，通常不考虑项气在文档中出现的先后次序并要求项气互异，这 时可以把t l , t 2 ，t n 看成一个n 维的坐标系，而w l ，w 2 ，w n 为相应的坐标值，这样 d = ( w l ，w 2 ，w n ) 可以被看成n 维空间中的一个向量，称d = ( w 1 ，w 2 ，w n ) 为文本d 的向 量表示，如图2 2 所示。 2 2 ，w2 l i ) 图2 2 向量空间模型 向量空间模型是目前广泛使用的文本表示模型，具有如下优点： ( 1 ) 提高了自然语言文档的可计算性和可操作性，文档内容被形式化到多维空间 中的一个点，通过向量形式给出，将文档以向量的形式定义到了实数域中； ( 2 ) 为词引进权值，通过调节词对应权值的大小来反映词与所在文档的相关程度， 部分地克服了传统布尔模型的缺陷； ( 3 ) 匹配通过计算文档之间的相似度，使属性相似的文档尽量聚拢在一起，以提 高匹配效率。 ( 4 ) 满足用户需求多样化以及匹配手段多样化的需要。用户可以根据需求特点选 择一组可供使用的匹配手段。 但该模型也存在一些缺点，主要表现为：向量空间的维数往往很高，导致计算量大， 影响系统速度；向量中的特征权值较难确定。 对于这些缺点，人们在研究基于词的相似性的向量空间检索。如s k m 旺格等人在 1 9 8 5 年提出用一组经过挑选的正交基向量来表示词向量，词间关系可直接由其向量表 示，给出较为精确的计算，这种模型称为广义向量空间模型。 2 2 2 特征项权重的计算 在向量空间模型中，常通过特征项的权重综合反映该特征项对标识文本内容的贡献 度和文本之间的区分能力。由于各特征项在不同文本中的出现频率满足一定的统计规 律，因此可根据特征项的频率特性来分配特征项的权重。 根据香农信息学理论，如果特征项在所有文本中出现的频率越高，那么它所包含的 信息熵就越少；如果特征项的出现较为集中，只在少量文本中有较高的出现频率，那么 它就会拥有较高的信息熵。特征项权重分配大致满足两条原则：一是正比于特征项在文 本中的出现频率；二是反比于样本文本集中出现该特征项的文本频率。 目前，常用的特征项权重的计算方法【2 6 】【2 7 1 有：布尔函数、词频权重、t f i d f 函数、 熵函数等。 1 布尔权重 布尔权重( b o o l e a nw e i g h t i n g ) 是最简单的一种加权方法，特征词出现的次数大于 0 ，则权重赋为l 。特征词出现的次数为0 ，则权重赋为0 ：其表达公式如2 1 。 w i ：! ) ( t 瑚? ( 2 - 1 ) 1 1 ( t f o ) 。 其中w i 为特征项i 的权重，t f 为特征项i 出现的次数。 从布尔函数公式不难看出，布尔函数具有权重大小与频率无关的特性，不能体现特 征项的区分性。 2 词频权重 使用文档中特征词的频率做权重，可以提高文本分类的查全率，但对准确率不好， 其公式如式( 2 2 ) ，其中t 为特征词i 出现的次数。 形f - t f f ( 2 - 2 ) 这种方法比较简单，因为有些词出现的频率虽然非常高，但是没有什么代表性， 这样使一些噪音词的权重比较高，从而降低了分类的准确率。 6 3t f i d f 权重 t f i d f ( t f i d fw e i g h t i n g ) 是在文本处理领域中使用最广泛的数值权重计算方法。它 的指导思想是：在一个文本中出现次数很多的单词，在另一个同类文本中出现次数也会 很多，反之亦然。该方法是根据特征词的重要性与特征词的文档内频数成正比，与训练 文档中出现该词条的文档频数成反比的原理构造的。该t f i d f 方法基于的思想和构造的 统计量都很简单，但是，在实用中却表现了很好的性能。权重函数为： 形玻= 矿i d f 止 ( 2 3 ) 其中t i c k ( t e r mf r e q u e n c y ) 表示项t k 在文本d i 中的文档内出现的频率， i d f t k ( h i v e r s e d o c u m e n t f r e q u e n c y ) 表示项t k 的反文档频率，是反映t k 在一个文档集中按文 档统计出现的频繁程度的指标。它们有多种计算方法，目前较为常用的公式为： ， 形腑= 吮1 0 9 ( 二二- + ，) ( 2 4 ) 仇 其中t 爪表示项k 在文本d i 中出现的次数，n 表示全部训练集的文本数，n k 表示训 练文本中出现t k 的文本频数，的取值需要根据实验来确定，一般取o 0 1 。 ， 考虑到文本长度对权重的影响，还应该对项权重公式做归一化处理，将各项权重规 范到 o ，l 】之间： 形i k 。 吮1 。g ( 望+ o 0 1 ) 1 k ( 2 5 ) 由上述公式计算出的权重，往往有少数项的值远远大于其它项。权值过高的个别项 在分类过程中往往会抑制其它项的作用，因此在计算权重时，应对统计出的词频做适当 的均衡处理。经过词频均衡处理的权重计算公式如下： 形雎= ( 2 6 ) t f i d f 公式是一种经验公式，并没有坚实的理论基础。但是，多年的实验表明，上 述公式是文本处理中的一个有效工具。事实上，这一公式不仅在信息检索中得到了成功 应用，它对于其他文本处理领域，如信息分发、信息过滤和文本分类也有很好的借鉴意 义。因此，我们在实验中也运用了t f i d f 权重。 4 熵权重 熵权重( e n t r o p yw e i g h t i n g ) 是在信息理论的基础上提出来的。它是最复杂的权重 计算方法，也被证明是最有效的方法。在熵权重计算方法中，一个特征的权重由下式给 7 出： 耻地c 川功川礼g 吉善 鲁l o g c 锄 像7 ， 其中，f j 表示特征i 在文档d j 中出现的频数，n 是语料中所有文档的数目，n 。是特征 在所有文档中出现的总次数，l 。g 吉善 鲁l 。g ( 鲁) 是特征i 的平均熵。当该特征在所 有的文档是均匀分布时，这个值为一1 ，若特征只在一篇文档中出现，则其值为o 。 2 3 文本的特征选择与特征抽取 由于文本数据的半结构化甚至无结构化的特点，使得用特征向量对文档进行表示的 时候，特征向量通常会达到几万维甚至于几十万维。这样高维的特征空间对于分类算法 来说是庞大的，对于分类也未必是有益的。因此，寻求一种有效的特征降维方式来降低 特征空间维数，提高分类精度是目前文本分类研究重点之一。 特征选择和特征抽取是特征降维中的主要方法。目前国际上对文本特征提取多数通 过采用某种评估函数，计算特征属性的权重，然后对所有的特征按照其权重大小进行排 序，选取权重在一定数目或某个值范围内的特征项集合作为文本的特征子集。常用的评 估函数有文档频率、信息增益、互信息、f 统计量、期望交叉熵等。下面主要对特征选 择几种常见的评价函数1 2 8 , 2 9 进行分析。 2 3 1 文档频率 某个特征的文档频率( d o c u m e n tf r e q u e n c y ，o f ) 是指在文档集中含有该特征的文档 数目。 采用d f 作为特征选择方法，基于如下基本假设：o f 值低于某个阈值的词条是低频 词，它们不含或含有较少的类别信息。将这样的词条从原始特征空间中除去，不但能够 降低特征空间的维数，而且还有可能提高分类的精度。文档频率是最简单的特征选择方 法，由于其相对于训练语料规模具有线性的计算复杂度，它能够很容易被用于大规模语 料统计。 但在信息检索研究中通常却认为d f 值低词条相对于d f 值高的词条具有较多的信息 量，不应该将它们完全移除。不同的应用对d f 值的认识不同，因此应根据具体情况来 选择该方法。d f 在实际应用中常常被作为评价其他评价函数的标准。 2 3 2 信息增益 香农在其提出的信息论中定义了信息量( i n f o r m a ti o n ) 和熵( e n t r o p y ) ： e n t r o p y = - ip 】= l o g2 ( p ) i n f o r m a t i o n = - l 0 9 2 ( p o ( 2 - 8 ) 从公式( 3 1 5 ) 中可以看出，熵实际上是系统信息量的加权平均，即系统的平均信息 量。信息增益( i n f o r m a t i o ng a i n ，i g ) 评估的原理就取自信息论。 在文本分类中，信息增益定义某特征项为整个分类所能提供的信息量( 不考虑任何 特征的熵和考虑该特征后的熵的差值) ，是一个基于熵的评估方法。根据训练数据，计 算出各个特征项的信息增益，按照信息增益从大到小排序，剔除信息增益很小的特征。 计算公式如下： 螂m 善p ( 喇。g 黜蝴莩p ( c ki 万) l o g 等( 2 9 ) 式中t j 表示特征项，p ( t j ) 表示特征项如出现的频率，p ( g ) 表示第g 类文本出现的 概率，尸( gl 南) 表示特征项方出现时属于g 类的条件概率。 从信息论角度出发，i g 方法的本质即用各个特征的取值情况来划分学习样本空间， 根据所获信息增益的多寡，来选择相应的特征。特征项的信息增益值越大，对分类越重 要。信息增益的不足之处在于它考虑了词未发生的情况。虽然某个词不出现可能对判断 文本类别也有贡献，但实验证明【3 0 1 ，这种贡献往往小于考虑词不出现情况所带来的干扰， 特别是在类分布和特征值分布是高度不平衡的情况下，绝大多数类都是负类，绝大多数 特征都是“不出现”的，此时信息增益大的特征主要是信息增益公式中后一部分( 代表 单词不出现情况) 大，而非前一部分( 代表单词出现情况) 大，信息增益的效果就会大大 降低了。 2 3 3 互信息 互信息( m u t u a li n f o r m a t i o n ，m i ) 是机器学习领域经常使用的一种特征相关性判别 准则，它表示联合概率分布同边缘概率分布乘积之间的相对熵。对于类别c k 与特定词条 南的互信息计算公式如下 m i c 力，c t ，= - 。g 了耋黼= - 。g 等 c 2 。， m i ( t j ，c k ) 表示词匀和类别c k 的互信息量，体现了它们的共现程度。p ( t j ) 表示词岛在 训练文本集合中出现的概率，p ( t j ic k ) 表示在类别c k 的文本中词巧的出现概率。m i ( t j ，c k ) 越大，说明词t j 和类别c k 的共现程度越大，词t j 包含的类别c k 信息越多。词毛关于所有 类的平均互信息可以由下式求得： 且 m i ( t j ) = p ( c k ) m i ( t j ，c o 2 1 1 1 在实际中，互信息有一个很大的缺点就是它非常容易受一个特征边缘概率的影响。 换句话说，如果两个特征具有相同的条件概率，那么出现次数少的特征会比出现次数多 9 的特征得到更高的m i 值。所以相比于信息增益和聂统计，互信息更看重那些出现次数 较少的特征。然而对于文本分类而言，出现次数较多的单词比出现次数较少的单词具有 更大的作用。因此互信息在文本分类上所表现出来的性能比较差，与信息增益和z ，统 计相去甚远。 2 3 4x2 统计量 使用m i 衡量特征词的重要程度时，只考虑到了正相关对特征词重要程度的影响。 然而如果特征词t j 和类别c k 反相关，就说明含有特征词t j 的文本不属于类别c k 的概率大 一些，这对于判断一篇文本是否不属于类别c k 也是很有指导意义的。# 统计量 ( c h i s q u a r e ，c h i ) 同时考虑了词存在与不存在时的情况。计算公式如下： z 2 ( 务，g ) = 酉西币n 历x ( a 两d - 石c b 丽) 2 面面 2 - 1 2 ) 对于多类问题，可以分别计算特征词匀对于每个类别的c h i 值，再用公式( 2 - 1 3 ) 计 算词t j 对于整个语料的c h i 值，分别进行检验。也可以将词对于各个类别的平均权重c h i 值作为该特征词条对于所有类别的c h i 值，计算公式见( 2 - 1 4 ) z j ( t o = 鼙z 2 ( 巧，c t ) ( 2 - 1 3 ) a 、b 、c 、d 均表示文本数量，如表2 - 1 所示，n = a + b + c + d 。 表2 - 1 描述表 ( 2 1 4 ) c k 类文档集合非c k 类文档集合 t j 出现情况 ab t j 不出现情况 c d f 统计量比较了词条对一个类别的贡献和对其余类别的贡献，以及词条和其它词条 对分类的影响。当特征项t j 和类别c k 之间完全独立的时候，a d b c = 0 ，f 统计量的值 为o ；若a d b c 0 ，说明t j 与c k 正相关，即词条出现说明某个类别也可能出现；反 之，若a d b c 0 的特征项t j 作为特征值。 2 3 5 期望交叉熵 期望交叉熵( e x p e c t e dc r o s se n t r o p y ，e c e ) 是特征选择中常用的一种方法。在信 息论中，熵是用来度量系统所含的信息量或者系统有序程度的值。熵越大，系统包含的 信息量就越大，系统的有序程度就越低。交叉熵表示两个分布函数所包含的信息的差异 程度。分布函数的差异越大，交叉熵的值就越大；分布函数的差异越小，交叉熵的值就 l o 、- 、 g 2 z、， q j p 县乙h = 、， 2 嘴z 越小；当两个分布函数相等时，交叉熵的值等于0 。期望交叉熵计算公式如下： 跏( t j m 兰k = lp c k ) i o g 黜 ( 2 _ 1 5 ) 该方法反映了文本类别出现的概率分布和在出现了某个特征项的条件下文本类别 的概率分布之间的距离，特征项的e c e ( t j ) 值越大，其对文本类别分布的影响也越大。 期望交叉嫡与信息增益唯一不同之处在于没有考虑特征不出现的情况。实验表明， 用期望交叉嫡优于信息增益。因为虽然某特征不出现也可能对判断文本类别有贡献，但 这种贡献往往远小于考虑特征不出现情况所带来的干扰。特别是在类分布和特征值分布 是高度不平衡的情况下，绝大多数类都是负类，绝大多数特征都是“不出现的，此时 信息增益的效果就大大降低。 根据具体的情况，应该当选用一种最佳的特征选择方法。在本实验中采取了的做法 是，选择一个评价函数来对特征集的每个特征进行评估，并按照所得评估分对其所有特 征进行排序，然后选取预定数目的最佳特征做为特征选择的结果。 2 4 常用的文本分类算法 分类算法是文本分类的核心。目前存在着多种分类算法，例如r o c c h i o s 分类算法 【3 1 1 、朴素贝叶斯分类算法【3 2 1 【3 3 】、支持向量机分类算法【3 4 】、k n n 分类算法【35 1 、决策树分 类算法吲和神经网络分类算法【3 6 1 等等。本节主要介绍r o c c h i o s 分类算法、朴素贝叶斯 分类算法、支持向量机分类算法，在下一章中将详细介绍k n n 分类算法。 2 4 1r o c c h i o s 分类算法 r o c c h i o s 分类算法由h u l l 在1 9 9 4 年提出，从那以后，r o c c h i o s 算法得到了广泛 的应用。该算法是基于向量空间模型和最小距离的算法，其最大的特色是具有良好的反 馈性能，能够根据其公式对分类的向量空间进行修正。 计算步骤如下：将文本表示为向量空间中的高维向量，按照训练集中正例的向量赋 予正权值，反例的向量赋予负权值，相加平均以计算每一类别的中心。对于属于测试集 的文本，计算它到每一个类别中心的相似度，将此文本归类于与其相似度最大的类别。 r o c c h i o s 模型分类器的学习基本上都是源于平均权重，具体算法描述如下： ( 1 ) 求类中心，对于类c i ，其类中心向量c 的计算公式为： 巧= 吉荟万 c 2 ， 其中，n 为类c i 中文档的数目，d j 为类c i 中第j 个文档的向量。 ( 2 ) 对待分类文本d i 进行分类，其类标签l a b l e i 按照下式计算： c l a s s ，) = a r g m a x s i m ( d j ，g ) ( 2 1 7 ) 其中，相似度s i m ( d j ，c ) 的计算通常采用余弦相似度，即两个向量的点积除以两个向量 长度的乘积。 一d c 8 i m ( 嘭，e ) 2 褊 q 。1 由此算法过程可见，如果对于那些类间距离比较大而类内距离比较小的类别， r o c c h i o s 分类算法可以取得比较好的分类精度，但对于类内距离比较大的情况，则该分 类算法可能会把大部分文本漏掉，因为这些文本的类中心将落在聚类的外面。 r o e c h i o s 算法的突出优点是容易实现，计算( 训练和分类) 特别简单，它通常用来 实现衡量分类系统性能的基准系统，而实用的分类系统很少采用这种算法解决具体的分 类问题。 2 4 2 朴素贝叶斯分类算法 朴素贝叶斯分类( n a i v eb a y e s ) 3 2 】【3 3 】( 简称n b ) 基于贝叶斯定理，可以用来预测类 成员关系的可能性，给出文本属于某特定类别的概率。分类时根据预测结果将该样本分 到概率最高的类别中去即可。其基本观点是：假设在给定的文本类语境下，文本的特征 词是相互独立的，在实际应用中，这一假定以指数级降低了其复杂性。 设d 为一任意文本，它属于文档类c = c l ，c 2 c m 中的某一类c i 。根据n b 分类法 有： 鹏协d 警( 2 - 1 9 ) 对文本d 进行分类，就是按照公式( 2 - 1 6 ) 计算所有文本类在给定d 情况下的概率， 概率值最大的那个类就是文本d 所属的类，即： p ( c ld ) = m a x p ( c , ) p ( dc ，) ) ，f = 1 ，2 m ( 2 2 0 ) 显然，根据假设，文本特征词互相独立，则p ( gld ) 可以用公式( 2 - 1 8 ) 估算： m p ( gd ) = p ( c f ) 兀p ( d ie ) ( 2 2 1 ) p ( g ) 可以用公式( 2 1 9 ) 估算： p ( 驴等 p ( d j lc j ) 可以用公式( 2 2 0 ) 估算： 1 2 ( 2 - 2 2 ) p ( d 肥) ：单 2 3 ) m + 帆 其中n j , 表示特征j 在训练类别c i 的文本出现的次数，n i 表示类别i 包含的训练文本数， i 表示特征项数，d j 表示特征j 。 朴素贝叶斯分类器一般具有以下特点： ( 1 ) 面对孤立的噪声点，朴素贝叶斯分类器是健壮的。因为在从数据中估计条件 概率时，这些点被平均。通过在建模和分类时盘略样例，朴素贝叶斯分类器也可以处理 属性值遗漏问题。 ( 2 ) 面对无关属性，该分类器是健壮的。如果x i 是无关属性，那么p ( x d y ) 几乎 成了均匀分布。x i 的类条件概率不会对总的后验概率的计算产生影响。 ( 3 ) 相关属性可能会降低朴素贝叶斯分类器的性能，因为对这些属性，条件独立 的假设已不成立。 在理论上，一般用朴素贝叶斯分类算法做其它方法的比较标准。 2 4 3 支持向量机分类算法 支持向量机【3 4 】( s u p p o r tv e c t o rm a c h i n e ，s v m ) 已经成为一种倍受关注的分类技术。 这种技术具有坚实的统计学理论基础，并在许多实际应用( 如手写数字的识别、文本分 类等) 中展示了大有可为的实践效用。此外，s v m 可以很好地应用于高位数据，避免了 维灾难问题。这种方法具有一个独特的特点，它使用训练实例的一个子集来表示决策边 界，该子集称作支持向量( s u p p o r tv e c t o r ) 。 支持向量机分类算法思想，是从训练样本中寻找能够确定一个最优超平面的支持 向量。假设有大小为m 的训练样本集众 ( x ，y 。) ，( x ：，y ：) ，( x 。，y ) ) ，如果它是一 个二分类任务，分类标识为y ；= 1 ( i - l ，2 ，m ) ，那么，这个任务的决策函数可以表示 为： f ( x ) = s i g n ( w e k + b ) ( 2 2 4 ) 那么，支持向量及需要解决下面的一个优化问题： m i 州n ( 1w t w - i - c 善毒) ( 2 - 2 5 ) 并且上述公式满足条件： y i ( w 1 ( x i ) + b ) l 一点 点0 ( 2 2 6 ) 在这里，训练向量x i 通过函数被映射到高维空间中，然后支持向量机将在这个高维空 间中寻找一个带有最大间隔的线性可分超平面。可以使用拉格朗日优化方法将最优分类 面问题转化为一个对偶最优化问题： w ( a ) 2 一i 1m q 吒y i y j ( x i ) t ( x j ) ( 2 - 2 7 ) l = 1 - i ，i = i k ( x i ，x j ) = ( x i ) t ( x j ) ，称之为核函数，常用的函数有： ( 1 ) 线性函数k ( x i ，x ) = x i x ( 2 ) 多项式函数k ( x i ，x ) = ( x i x + 1 ) 4 ( 3 )径向基函数k ( x i , x ) = e x p ( 掣) ( 4 ) 多层感知器函数k ( x i ，x ) = t a