（计算机应用技术专业论文）基于语义中心的knn文本分类算法研究.pdf

硕士论文基于语义中心的k n n 文本分类算法研究 摘要 本文主要研究了文本分类和聚类的相关算法，分析了其中的若干关键技术和难 点。首先，介绍了基于向量空间模型的文本表示方式和相应的特征权重计算方法，并 对几种较好的特征选择方法进行了对比分析；然后，着重剖析了两种性能优秀的分类 算法：k n n 和s v m ，并从理论和实验上对两者进行了对比，分析了各自的优劣，并 最终选择了较稳定的k n n 算法应用于实际的系统。 为克服k n n 算法分类速度较慢的缺陷，本文提出了使用语义中心代替k n n 算 法中样本实例的方法；语义中心的构造采用了文本聚类的方法实现，其中对适合文本 聚类的最近邻聚类算法的整个流程和细节问题作了详细的阐述，并使用了动态调整相 关参数的方法来优化聚类质量；特别是针对聚类初始中心点的确定，本文对已有的算 法进行改进，并给出了详细的算法流程等。 最后，本文针对不同规模的语料，对上述算法进行了实验验证，结果表明采用基 于语义中心的k n n 分类算法，在保证分类准确率的情况下，系统分类速度大大提高。 关键词：文本分类，文本聚类，特征选择、聚类中心初始化、k 近邻算法、 语义中心 硕士论文 基于语义中心的k n n 文本分类算法研究 a b s t r a c t 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 ei nt h i s p 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 dp r o b l e m s ，a 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 ，v e c t o rs p a c em o d e la n dm e t h o d so f t e r mw e i g h tc o m p u t i n ga r ei n t r o d u c e d ，a n dw e c o m p a r es e v e r a lg o o dm e t h o d so ff e a t u r es e l e c t i o n t h e n ，w es e l e c t i v e l ya n a l y s et w o c l a s s i f i c a t i o na l g o r i t h m s ：s v ma n dk n n ，w h o s ep e r f o r m a n c e sa r eb e t t e rt h a no t h e r s o u r e x p e r i m e n t so nt h i st w om e t h o d ss h o wt h a tt h es t a b i l i t yo fk n n i sb e t t e rt h a nt h a to fs v m ， s ow ep i c ki ti n t oo u rr e a ls y s t e m a sk n ni saa l g o r i t h mb a s e do ns a m p l ei n s t a n c e s ，t h es l o ws p e e do fc l a s s i f y i n gi sa b i gp r o b l e m w ep r o p o s ea ni d e at 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 e m a n t i c c e n t e r st oo v e r c o m et h i sp r o b l e m t e x tc l u s t e r i n gi su s e dt oc o n s t r u c tt h es e m a n t i cc e n t e r s a n dw ee x p a t i a t et h en e a r e s tn e i g h b o u rc l u s t e r i n ga l g o r i t h ma n di t ss p e c i f i cp r o b l e m s a n d s o m em e a n so ft u n i n gp a r a m e t e r sd y n a m i c l ya r eu s e dt oo p t i m i z et h ec l u s t e r i n gq u a l i t y f o rt h ep r o b l e mo fi n i t i a l c l u s t e r i n gc e n t r i o d s ，w ei m p r o v ea ne x i s t i n ga l g o r i t h ma n d p r e s e n td e t a i l so f t h ec o r r e s p o n d i n ga l g o r i t h mf l o w f i n a l l y , o u re x p e r i m e n t se v a l u a t et h ea b o v ea l g o r i t h m s o ns e v e r a ld i f f e r e n t s i z e d a t a s e t sa n dt h er e s u l t ss h o wt h a to u rk n nc 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 ns e m a n t i c c e n t e r sg r e a t l yi m p r o v et h ec l a s s i f y i n gs p e e dw 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 t c a t e g o r i z a t i o n ，t e x tc l u s t e r i n g ，f e a t u r es e l e c t i o n ， c l u s t e r i n gc e n t r o i d si n i t i a l i z a t i o n ，k - n e a r e s tn e i g h b o r , s e m a n t i cc e n t e r 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名： 汐刃年6 月刀日 i i 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：魏篷 渺7 年歹月矽日 硕士论文基于语义中心的k n n 文本分类算法研究 1 绪论 互联网经过十几年发展已经成为一个巨大的全球化信息空间，它容纳了海量的各 种信息，包括文本、图像、音频、视频信息等，例如，当今最大的搜索引擎g o o g l e 已抓取的网页已达2 5 0 亿以上【“，然而这也仅仅是当前全球网页的一小部分。由于互 联网上拥有的信息资源呈无限、无序、庞杂的特征，增加了人们获取有效信息的难度； 再者，当今信息产生的速度远远超过人们对信息的利用能力，使得人们在日益膨胀的 信息面前无法快速地查找到所需的信息，从而造成了时间、资金和精力的巨大浪费。 因此，如何充分掌握和利用现有的信息资源已成为一个重要而迫切的问题。 由于i n t e r n e t 上数据大多是缺乏结构化的文本数据，如网页文本等，自然让人们 想到运用数据挖掘中的文本挖掘技术来提高在i n t e m e t 上检索信息、利用信息的效率。 文本挖掘( t e x tm i n i n g ) 是以半结构( 如w e b 网页) 或者无结构( 如纯文本) 的自然语言文 本为对象的数据挖掘1 2 1 。它是从大规模文本数据集中发现重要的、潜在有用的信息的 过程。分类聚类是当前文本挖掘中最实用的技术，如很多企业使用的邮件自动分类过 滤系统就是利用文本分类技术根据邮件主题和正文进行自动归类处理；又如，对搜索 引擎抓取的文档进行自动分类，就可以让用户清晰地得到其感兴趣的相关结果，去除 主题不相关的内容，从而弥补当前搜索引擎检索结果质量差的缺点：聚类技术可用来 聚合用户感兴趣的新闻等信息，另外，聚类算法已应用到生物医学领域中人类基因的 研究上【3 】。 由此可见，对海量网络信息的有效处理和综合利用离不开文本挖掘技术，当前文 本自动分类和聚类技术的应用己大大节约了人力和财力，避免了人工处理带来的周期 长、费用高和效率低等诸多缺陷。在信息时代的今天，互联网的普及和网络资源的急 剧膨胀更是给文本挖掘等深层次语言处理技术提供了现实需求和广阔的应用前景。 1 1 基本概念 在文本挖掘相关算法的理论研究中，分类聚类是目前最具有实用价值的一项技 术，进一步的研究这项技术对改进当前的机器学习技术和文本自动分类的质量，都有 重要意义。 1 1 1 文本分类的定义 文本分类( t e x tc a t e g o r i z a t i o n ) 是指在给定的分类模型下，将用自然语言表示的文 本，根据其内容，自动地确定该文本所属的一个或多个类别1 4 1 。文本分类问题可以形 式化定义如下f 5 】【6 1 ： 硕士论文基于语义中心的k n n 文本分类算法研究 设c = c 1 ，c 2 ，) ( m 2 ) 为预设定的类别集合，d = d l ，以，以) 为已有类 别信息的所有n 个文本，彳= ( ) 。( = o ，1 ) ) 是一个聊x 玎的矩阵，= 1 表示 文本d ，属于类别c ，反之不属于。假设文本和类别间存在一个未知的映射函数： f ：d c 哼 o ，l ( 1 1 ) 且文本集d 中的部分文本d = 面，以，4 ) p 刀) 已由专家分好了对应的类 别，即矩阵彳中的子矩阵a i ) 。，的值已确定。文本分类就是要找到函数： f ：d c 专 o ，1 ) ，使得该函数尽量逼近未知的函数式( 1 1 ) 。要找的函数厂就称为 一个分类器，其中d = 西，以，4 ) o ”) 就：e 可i i 练集，4 。= ，。，为专家对训练 集人工分类的结果。 从数学角度来看，文本分类就是一个映射过程，它将未标明类别的文本映射到已 有的类别中，该映射可以是一对一或一对多的映射，因为一篇文本可以同多个类别相 关联【7 】。分类实际上也是一种知识学习和知识应用的过程，它的特点是分类器根据已 经掌握的每个类中若干样本的数据信息( 如上面的矩阵a = 概 。) ，总结出分类的 规律性而建立判别公式和判别规则，这是知识学习的过程；然后在遇到新文本时，根 据总结出的判别规则，确定新文本相关的类别，这是知识应用的过程。 1 1 2 文本聚类的定义 聚类是一种无监督的机器学习方法( u n s u p e r v i s e d l e a r n i n g ) 。该问题描述如下：给 定一个文档数据集x ，以及文档样本之间的相似度d ，从数据集x 中找出聚团c t ， c ：，g ( 称c j 为簇( c l u s t e r ) 或类k 是预定义的簇数) ，要求满足：同一个簇g 中的 样本彼此之间很相似；属于不同簇的样本间的相似性很小或不相似。 实质上聚类和分类都是分类的方法：聚类是一种无监督的分类方法，而分类是有 监督的分类方法。它们的不同之处在于，聚类没有预先定义好的主题类别，它的目标 是将没有任何类别信息的文档集合分成若干个簇。 目前聚类技术已应用于许多方面，包括模式识别、数据压缩、图像处理、声音处 理、市场分析以及w e b 内容聚合等。 1 2 文本分类和聚类的发展和现状 文本分类的理论研究可以追朔至l j 2 0 世纪6 0 年代初【卯，其发展过程大致可以划分为 三个阶段州： 第一阶段是2 0 世纪8 0 年代前。在这一时期，模式识别和信息检索相继发展成为 - f l 学科。m a o n 和k u l m s 提出概率标j ( p r o b a b i i s t i ci n d e x i n g ) 模型，并应用于信息 检索( i n f o r m a t i o nr e t r i e v a l ) 中；1 9 6 2 年，r o s e n b l a t t 设计了感知机( p e r c e p t r o n ) ，通过 具有阅值的神经元处理二分类问题；g e r a l ds a l t o n 提出了向量空间模型( v e c t o rs p a c e m o d e l ，v s m ) 用于对文本进行描述。这一阶段主要是集中在对分类理论的研究，并主 2 硕士论文基于语义中心的k n n 文本分类算法研究 要是用于信息检索。 第二阶段是2 0 世纪8 0 年代。这一阶段主要是采用传统的知识工程( k n o w l e d g e e n g i n e e r i n g ) 技术，根据专家提供的知识形成规则，手工建立分类器，这实际上是专 家系统，h a y e s 等的c o n s t r u e 系引8 】是典型的代表。这一时期，信息检索技术逐 渐成熟应用，为文本分类提供了许多技术支持，最著名的r 系统是s a l t o n 的s m a r t 系统1 9 1 。但手工建立分类器的缺点有：一是依赖于专家；二是面向领域，一旦应用领 域变化，需要重新生成规则；三是分类器建设周期长，工作量大，分类质量难以保证。 第三阶段是2 0 世纪9 0 年代以后。互联网技术的发展，对文本分类提出了迫切要 求。在这一时期，文本分类的主要特点是采用统计机器学习方法，自动建立分类器。 基于机器学习的文本分类方法克服了以前手工建立分类器的缺点，使得文本分类具有 了真正的实用价值，其主要特点有：一是分类知识来源于机器对训练集的自动学习， 不再依赖于领域专家：二是学习和分类过程不需要人工干预，分类效率和准确率得以 提高。目前所说的文本分类主要是指第三阶段的基于机器学习的文本分类。因此，文 本分类的研究严格来说只有十几年的历史。在开始时期，研究的重点是将机器学习、 信息检索等相关领域中的成果应用到文本分类中；随着研究的深入，文本分类问题被 进一步细化，研究人员对各个子问题进行深入研究，例如：分类方法，特征降维，性 能评价，大小样本学习，分类性能推广，语言知识利用等，试图在对文本内容更多理 解的基础上，提高文本分类的效果。 国外在文本分类以及相关的信息检索、信息抽取等领域开展的比较早，研究也已 比较深入和完整，取得了不少令人注目的研究成果，并产生了一些实用的分类系统。 其中比较成功的有麻省理工学院( m i d 为白宫开发的邮件分类系统、卡内基集团为路 透社开发的c o n s t r u e 系统等。相关文本分类算法的研究也很多，最著名的是y i m i n g y a n g 在标准的r e u t e r s 2 1 5 7 8 数据集上对神经网络( n e u r a ln e t ，n n e t ) 、支持向量机 ( s u p p o r t v e c t o r m a c h i n e ，s v m ) 、简单贝叶斯( n a i v e b a y e s ，n b ) 、k 近邻( k n e a r e s t n e i g h b o r ，k n n ) 和线性最d - - 乘法拟合( l i n e a r l e a s ts q u a r e sf i t ，l l s f ) 等五种代 表性分类算法的性能进行了对比【1 0 i l l 】，在准确率、召回率、f 1 ( 分别在宏平均、微平 均下测试) 等评测指标下，利用假设检验的方法证明了s v m 与k n n 方法在综合性能 上高于l l s f 、n n e t 与n b 。总的来说，在对英文文本分类方面，近年来基于机器学 习的文本自动分类算法都取得了很好的效果，以k n n 和s v m 较好。 国内方面，各大院校和研究所也有很多对中文文本分类的研究，黄萱菁等进行了 汉语语料自动分类的研究，取得了一定的效果【1 2 1 。但由于国内缺乏统一的中文语料和 评价标准，很难对这些研究作出严格的比较。目前，国内比较成熟且已商业化应用的 分类系统有i b m 的深思智能分类系统和t r s 信息技术有限公司的t r s 中文知识管理软 件( c l ( m ) 等，两者的核心都是采用s v m 和k n n 算法，据各自的官方数据，t r s 的c k m 硕士论文基于语义中心的k n n 文本分类算法研究 分类系统的总体准确率( 8 6 9 0 ) 要优于i b m 的分类系统( 8 5 ) 。 尽管文本自动分类技术已经比较成熟，但仍存在的问题有： 分类标准存在缺陷：如中图法中的两个类别：文学和艺术非常相近，有时人工 分类都不能准确地确定一篇文章应归为哪个类别较好。 语料不充分：很多自动分类的研究实验所用的训练样本数都大于测试样本数， 这样才取得了8 0 甚至9 0 以上的准确率；但是在实际使用中，往往训练样本是很少 的，而待分类的样本则是海量的，因此我们要尽量使用较多的测试样本来做实验。 臼自动分类技术本身的问题：很多研究者提出的较好的分类算法往往是参数非常 复杂，而且训练参数需要很多的时间，因而这种实验效果很好的分类算法往往投入到 实际应用后不能保证其效果。 聚类算法的在国外的研究同样早在2 0 世纪6 0 年代就开始了，但是受当时各方面 条件的限制并没有大的发展，直到2 0 世纪9 0 年代才得到了重视，并取得重大的突破， 包括k - m e a n s 、c l a r a n s 、e m 、b i r t h 、d b s c a n 、c l l q u e 等【“1 在内的一批新 的聚类算法被陆续提出，目前仍旧是一个非常热点的问题。与国外相比，国内对中文 文本聚类的研究起步比较晚，目前主要有中科院计算所的b 东波和中国科技大学的姜 宁等人。 文本聚类算法大致分为划分聚类、层次聚类、基于密度的聚类、基于模型的聚类 和基于网格的聚类算法等几大类。虽然聚类已经广泛应用于模式识别、数据挖掘、 w e b 文档分类等许多领域中，并取得了可喜成绩，但在理论与方法上，它们都还不 很完善，各种算法多少都存在着不足，如基于划分聚类算法的初始中心点的问题【j 卯， 聚类结果很难达到最优解等。 目前，文本聚类研究主要面临如下方面的问题：( 1 ) 可伸缩性：许多聚类算法在 小量数据集上工作的很好，但许多实际应用中常有百万个数据对象，必然要求聚类算 法具有高度的可伸缩性；( 2 ) 高维问题：即由于文本特征词数目众多而造成处理效率 严重降低；( 3 ) 如何有效地检测和处理噪声和异常数据；( 4 ) 用于各种类型数据的聚类 算法的效果如何评价等；这些方面也是当前聚类算法研究的热点问题。 1 3 研究工作背景 本课题来源于网络海量信息分类与多语翻译系统这一项目，该项目是华建机器翻 译有限责任公司受中国信息安全产品测评认证中心的委托开发的一套支持多语分类 与翻译、面向海量网络信息、智能化的信息收集和管理软件。该系统主要功能是将用 户感兴趣的内容，如某些突发性新闻或某一网站上的信息，通过指定相关内容的关键 字或网址等，系统自动地从互联网下载符合条件的网页；然后系统对这些信息进行自 动聚类和分类处理，并可对多语言网页进行实时翻译，节省了在信息获取和整理上的 4 硕士论文 基于语义中心的i a m 文本分类算法研究 人力和时间，方便用户将时间和精力放在更重要的信息决策上。 在本系统中，分类聚类是主要功能模块之一。其中聚类是用于建立和优化系统的 分类模型，以便提高分类的速度等；分类功能则是将下载的网页等网络文本信息，根 据其内容自动地分到其相关的类中。因此聚类效果的好坏将很大程度的影响到自动分 类的准确率和速度，而用户一般能够接受的分类准确率要在8 0 以上，所以本课题主 要研究如何最大程度地提高聚类的效果和分类的准确性，同时还要兼顾分类聚类的速 度，达到商业应用的水平。 1 4 论文的主要研究内容 本文主要针对网络海量信息分类与多语翻译系统这一项目的需要，研究设计并实 现其中分类模块所需的分类聚类算法。因此，根据当前各种算法的优劣和实际项目中 的分类要求，我们比较并选择较好的分类聚类算法来提高分类模块的性能。其中有以 下问题需要着重研究解决： ( 1 ) k n n 分类算法中参数k 和相似度阈值的确定：参数k 是k n n 算法中的近邻 数，即最相似文档的数目，k 的大小限制了可用来比较的文档数；相似度阈值是用来 划分两篇文档是否可以属于同一类的约束条件，相似度大于阈值的文档才可以归为同 一类。在使用k n n 算法的分类模型构造过程中，需要训练相似度阈值和k 值。 ( 2 ) k - m e a n s 等聚类算法中簇数k 的确定：包括k m e a n s 在内的大多数聚类算法， 均需用户事先给定聚类个数k ，而聚类结果对k 值大小比较敏感，就目前的算法研 究状况来说，如何选择合适的k 值本身就是一个难题。在本项目的实际应用中，我 们是使用聚类算法针对训练集中每个类进行语义的划分，语义划分的多少直接影响到 分类处理的效率；因此k 的确定要根据分类准确率和速度的需要来做调整。 ( 3 ) k - m e a n s 等聚类算法的初始点选择问题：经典的方法一般是随机选择k 个点 或直接取前k 个点作为初始中心，但这样都只能达到局部最优解；不少研究者提出 了其它较好的初始化方法：有的是针对随机选择的初始中心，然后采用多次运行 k m ( 嘧n s 算法的方法，比较每次的结果，取较好的那次聚类结果作为最优解；另外还 有样本子集作中心、层次聚类法结果作为初始中心等方法，但这些方法一般速度慢参 数设置复杂等，无法满足实际的需要。我们拟从中选取并改进合适的算法，以尽量取 得最优解。 ( 4 ) k - m e a n s 等算法中如何减小孤立点数据的影响：孤立点数据对聚类中心位置的 影响很大，会使聚类中心偏离其真正的位置，从而影响到聚类的质量。v i l l e 等【1 6 j 提 出了一种如何移除孤立点的方法；我们将考虑k 近邻聚类算法加阈值的方法来减小 孤立点数据的影响。 ( 5 ) 聚类质量的评价，如何尽量达到全局最优解：由于聚类初始点的选择和孤立点 s 硕士论文基于语义中心的k n n 文本分类算法研究 数据的影响，k - m e a n s 算法很难达到全局最优解，一般只能近似地接近最优解，我们 结合实际的应用，采用基于簇内文档对相似度和( s p s ) 和纯度的评价方法来对聚类的 质量进行评估，选择具有最大s p s 和纯度值的聚类结果作为较优解。 ( 6 ) 权衡算法的速度和准确率：由于本课题是根据实际项目中的分类模块的需要 来拟定的，因此，我们要兼顾算法的速度和准确率两个方面：首先一定要使准确率满 足用户要求，一般分类的准确率至少要达到8 0 以上；其次，速度上也要满足用户的 使用感受，这一点主要通过基于聚类算法的分类模型语义中心的构造来优化。 ( 7 ) 文本的特征选择：特征选择是一个在分类聚类中都要解决的一个关键问题， 对于样本文档，可能有成千上万的特征，但并非所有特征都是有用的。选择哪些特征 将是一个很关键的问题，这个问题一般要通过特征选择算法加以解决。常用的特征选 择方法有文档频率、互信息、信息增益、矿统计量等。其中文档频率实现起来最简 单，而据文献【2 l 中提到应用较多、效果最好是信息增益法。我们将根据实验对比来选 择较优的特征选择方法。 1 5 论文结构和安排 本文主要探讨了文本分类聚类的若干技术和在实际项目中的应用，主要内容安排 如下： 第一章绪论，主要介绍了文本分类聚类的相关概念和研究现状，本文研究的项目 背景和以及论文的主要安排。 第二章描述了文本表示和特征选择的相关问题，详细介绍了空间向量模型和几种 经典的特征选择函数等。 第三章探讨了文本分类的算法，主要阐述比较了最近邻和支持向量机分类算法， 并对分类性能评价方法进行了介绍。 第四章阐述了文本聚类的算法和聚类质量的评价标准，并对聚类算法中初始化中 心点问题进行了比较分析，并作了适当的改进；另外具体阐述了如何在本系统中使用 k 近邻聚类算法来对分类模型进行语义划分的方法，并对其中算法流程作了相应的优 化和改进等。 第五章是实验系统结构、测试数据和实验设计，以及相应的实验结果和分析。 第六章对本文研究工作进行总结，以及对今后的研究工作的展望。 6 硕士论文基于语义中心的k n n 文本分类算法研究 2 文本表示和特征选择 本章将介绍文本表示模型、文本间的相似度计算和我们实验中实际使用的几种主 要的特征选择算法。 2 1 文本表示模型 计算机并不具有人类的智能，我们人在阅读文章后，根据自身的理解能力可以产 生对文章内容的模糊认识，这种认识是对文本语义的理解。而根据当前的计算机技术 的研究水平，机器还不可能“读懂”人能够理解的自然文本，从根本上说，它只认识 0 和l ，所以必须将文本转换为计算机可以识别的形式。计算机的发展离不开数学， 因此，要想让计算机“读懂”文本，必须能够找到用于文本表示的数学模型。 随着信息检索技术的发展，逐渐发展起来的几种文本检索模型主要有：布尔模型 ( b o o l e a nm o d e l ) 、向量空间模型f v e c t o rs p a c em o d e l ，简称v s m ) 、概率模型 ( p r o b a b i l i s t i cm o d e l ) 等，这些模型从不同角度使用不同的方法处理特征加权、类别 学习和相似计算等问题，而向量空间模型是最有效的文本表示模型【9 】。 2 1 1 向量空间模型 向量空间模型是由o e r a r ds a l t o n 在上世纪6 0 年代提出的，它用项频率一逆文档 频率t f i d f ( t e r m - f r e q u e n c yi n v e r s e d o c u m e n t - f r e q u e n c y ) 将文档转化为向量形式， 用倒排文档进行索引，再通过相关度的计算，从而使用户得到一个清晰的检索结果。 在成功应用于s m a r t 文本检索系统【9 】后( s y s t e mf o rt h em a n i p u h t i o na n dr e t r i e v a lo f t e x t ) ，这一系统理论框架到现在仍然是信息检索技术研究的基础，也是应用的最多 最成熟的模型。 一个向量空间是由一组线性无关的基本向量组成，向量维数与向量空间维数一 致，并可以通过向量空间进行描述。下面介绍一下文档向量空间相关基本概念【_ 巩 ( 1 ) 特征：指出现在文档中并能表示该文档特点的基本语言单位( 如英文等西 方语言中的单词，汉语、日语等语言中的字和词、词组) ；在信息检索中，特征就相 当于检索词。向量空间模型中一般取词作为特征，也有研究者使用汉字、概念等作为 特征构造向量模型的1 1 2 】；这样文档d 就可以由该文档中的所有特征来表示：d = m ，t 2 。u ，其中，t k 是文档d 中第七个特征词，摊表示文档d 中词的个数，这样自 然语言形式的文本文档就可以在向量空间中完全由特征来表示。 ( 2 ) 文档：向量空间中的文档就是指计算机中存储的文本文件或文件中的一个片 段( 如文件中的标题、摘要、正文等) ( 3 ) 特征项权重w k ：指特征项“能够代表文档d 能力的大小，它体现了该特征 7 硕士论文基于语义中心的k n n 文本分类算法研究 项在文档d 中的重要程度。这样文档d 就可以由一个玎元的特征向量来表示，即表 示为d w 2 , ，0 ，其中w 1 ，w 2 , ，w 。分别代表文档d 特征项“红，如的特征项 权重。 向量空间模型将每一个不同的词条都看成是特征空间中独立的一维，将每一个文 档看作为特征空间中的一个向量d 伽, w ，w 。 我们举个例子可以清晰地说明向量空间模型的构成【l 刀： 以下分别是三篇文档的内容： f e a t u r es e l e c t i o nf o rt e x tc l u s t e r i n g t e x tc l u s t e r i n ga n dt e x tc a t e g o r i z a t i o n f e a t u r ee x t r a o f ta n df e a t u r es e l e c t i o nf o rt e x tm i n i n g 去掉连词介词f o r 、a n d 两个停用词后，得到7 个单词作为特征： f e a t u r es e l e c t i o nt e x tc l u s t e r i n gc a t e g o r i z a t i o ne x t r a c t i o nm i n i n g 则上述每个单词在向量空间中对应一维，这三篇文档构成的数据集的特征空间为 7 维；设依次将上面每个单词标为w l , w 2 ，w 7 ，下面就为每个文档建立相应的文档向 量。其主要做法就是为文本向量的每一维计算相应的值，这个值代表了这个单词与这 个文本之间的相关程度。下面使用最简单的计算方法：对于某一个文本向量的某一维， 如果这一维所对应的单词出现在这个文本中，那么这一维对对应的值就是l ，否则为0 ( 也可以使用该单词的出现的次数一词频来表示) 。如下所示： w lw 2w 3w 4w 5w 6 w 7 得到相应的文档向量 文档1 ：1l1l0 0 0 d i 文档2 ：0 011100 d 2 文档3 ：1 110011d 3 由于一个文档中所包含的单词远远小于整个数据集所有的单词量，所以一个文档 向量在大多数的维度上的值都为0 ，如上面的文档2 中有四个维度值为0 。这种情况 下，如果采用线性表存储则需要耗费大量空间来存储无用的o ，所以在实际应用中， 更多是采用链表来存储文本向量：链表的每一项对应这个文本向量中不为0 的维度， 它至少包括两项内容，一是维度的索引值，另一项是相应的值。如，上面的文档2 用链表存储的表示方式为：d 2 ，表示单词w 3 ，w 4 ，w 5 出现在该文档中； 另外两个文档向量的这种表示方法为d 1 和d 3 。当然，其中的维度值1 可以使用更好的词频等权重值表示方式来代替 相似度s 的计算： 相似度指两个文档内容相关程度的大小，当文档以向量来表示时，可以使用文档 向量间的语义距离来衡量。两个向量间的相似度或者距离的计算有多种方法，比如曼 哈顿距离、欧几里德距离、向量内积和余弦相似度等，但对于文档向量来说，一般使 8 硕士论文基于语义中心的k n n 文本分类算法研究 用内积或夹角0 的余弦来计算，两者夹角越小说明相似度越高( 见图2 1 ) 。 。 图2 iv s m 及相似度s ( 0 1 d 2 ) ，j 使用余弦相似度计算两个向量相似度的公式如下i _ 7 】： 月 s ( 日，d 2 ) = w l 。w 2 l 或者 ( 2 1 ) k = l 她圳让躺2 啬蠢 2 2 文本预处理 2 2 1 字符编码转换 首先，由于我们系统的特色就是要处理多种语言，要处理多种语言的文本就必须 使用u n i c o d e 字符集来分析。虽然我们实验用的分类语料都是中文文本，但其中很多 夹杂着英文、希腊字符、日文等其它语言的字符、单词等，所以我们要把所有文本字 符转化为u n i c o d e 编码统一处理。 2 - 2 2 中文文本分词 英文文本处理中不会有分词的概念，因为英文本身是由一个个最基本的单词构成 的( 对于变形的单词只需要进行词干抽取( s t e m m i n g ) h i 口- ) ，自然文本中就已经使用空 格等隔开。但中文是以字为基本的书写单位，词语之间没有明显的区分标记，因此， 中文词语分析是中文信息处理的基础与关键。而中文词语分析一般包括3 个过程：预 处理过程的词语切分，切分排歧与未登录词识别、词性标注等【l 戤。对于文本分类而言， 分词只需要词语切分的结果即可，不需要进行词性标注。 9 m 坳 m 一 饥脚 ， 档 一一， n 文 一一项謦 预 ， 特 引姚 硕士论文基于语义中心的k n n 文本分类算法研究 由于分词的结果是后续特征选择和分类过程的处理对象，词语切分结果的准确性 与包容性( 即必须涵盖正确结果) ，直接影响到最后分类的准确率、召回率。因此选 择较好的分词模块是非常重要的，我们系统中采用的是华建机器翻译公司自主开发的 分词模块，经过在多个系统中应用证明其分词效果是非常好的。 2 2 3 停用词过滤 停用词表中主要有数字，西方语言中的字母，还有大量的中英日俄等语言的常用 词，这些词一般都是虚词、量词等，它们几乎出现在所有类别中的文档中，因而不具 有任何类别信息，不能作为特征使用。而且，不仅这些停用词对分类没有任何帮助， 反而会降低分类的准确率：我们在实验中发现不使用停用词过滤时小样本分类的准确 率只有6 0 多，而使用停用词表对文本词过滤后分类的准确率达到7 0 多。 文本经过分词，去除停用词后，就可以建立起文档的向量空间模型，统计每篇文 档中的词频，文档频率等信息，以便用于后面的权重计算和特征选择。 2 3 特征权重计算 由式( 2 2 ) 可以看出，文本间的相似度大小很大程度上取决于两个文档的每个特征 项的权重的大小，因此每个特征的权重大小的设置能否最大程度地反映原文本的内 容，会对文本间相似度计算产生很大的影响。 下面是几种常用的权重形计算方法【撺】【4 】，其中。表示文档总数，m 表示特征总 数，矿为特征频数，矽为相应特征的文档频数：i d f 为逆文档频率( i n v e r s ed o c u m e n t f r e q u e n c y ) ：它是特征在文本集中出现的频繁程度的量化，用特征t 出现文档个数的 倒数表示，一般的简单计算式是：i d f = 1 0 甙 0 d f ) ，取对数值是为了使其对 0 不 敏感。d f 表示特征的信息熵大小，根据香农的信息论，如果特征的文档频数越高， 那么该特征所包含的信息熵就越少；反之如果特征的出现集中在少数的文档中，即特 征的文档频率较低，则该特征的信息熵就越大。 ( 1 ) 布尔权重( b o o l e a nw e i g h t ) ： ( 2 ) t f i d f 型权重： 矾：f 1t f 0 ”。【0t f = 0 ( 2 3 ) t f ：w = t f j 即仅使用特征频数t f 的值来直接作为特征权重： 圆t f + i d f ，考虑文档频率的作用：w = t f + l o g ( n a d f ) ( 2 4 ) 0 t f c ：是对上面t f * i d f 的进行文档长度规范化，即 w = 1 0 硕士论文基于语义中心的k n n 文本分类算法研究 l t c ：该式中将仃并取对数值是为了降低各个特征的频数大小相差太大而对权 重计算的影响。 形= ( 2 6 ) ( 3 ) 熵( e n t r o p y ) 权重：熵权重来源于信息论，其中矿表示在文档，中的出现的频 率，式中对矿取对数作用同l t c 。 一 1品 形- 1 。甙矿“) + i ：i 万缶可v j1 0 烈等) 】) ( 2 7 ) 其中，t f i d f 型权重是当前研究者用的最多的权重计算方式。在我们的实验中就 使用了t f i d f 型的权重，具体计算方法见2 4 节相似度的计算。 2 4 文本间的相似度计算 下面具体介绍下在我们的分类系统中如何计算文本间的相似度。首先我们对训 练集中的所有文档进行扫描，完成统计所有词的词频、文档频率的统计，其中包括每 个词在各个类别中出现的词频和文档频率，然后使用2 5 节介绍的特征选择方法，从 所有词中选择出较优的特征词。对每个特征词，我们使用下面的算式来计算硒及 矿： 厂 磷= ( i o 双希“o ) ， ( 2 8 ) 豫 斫，= i 旦 ( 2 9 ) l i 其中虬表示训练集中的文档数，d 为该特征i 在训练集中的文档频率，加上1 0 是为了防止对数值为负数时导致i d f 小于0 ；t f ，表示特征i 在文档j 中出现的频率， ，表示文档j 的长度。这里我们将词频的值除以文, j 档长度作为参与计算的词频值矿， 是为了将词频值都归一化到【o ，1 】之间，这样就避免了有些特征词的词频过大或过小对 后面权重计算的不良影响。 接着，我们使用公式( 2 5 ) 来计算特征i 的权重值，即： 得： 形= ( 2 1 0 ) 并采用余弦相似度来计算待分类文档和训练集中文档间的相似度值，由式( 2 2 ) 可 硕士论文基于语义中心的k n n 文本分类算法研究 洲弼卜网d c 。d 2 南 亿1 0 ) 呢：毒望坠 善( 兀蝌 ( 2 1 1 ) 其中的矿，是特征i 在待分类文档以中的词频，它同样也要使用式( 2 9 ) 来计算。 式( 2 1 0 ) 就是我们在实际分类系统中使用的文本间相似度的计算式。 2 5 文本特征选择 特征选择是一个在分类聚类中都要解决的一个关键问题，对于样本文档，可能有 成千上万的特征，但并非所有特征都是有用的。选择哪些特征将是一个很关键的问题， 这个问题一般要通过特征选择算法加以解决。特征选择就是从特征集 t = t l ，t 2 ，) 中选择一个真子集t i 乇，f 2 ，) ( s j ) 。其中：j 为原始 特征集的大小，j 为选择后的特征集大小。选择的依据是特征对分类作用的大小，通 常用一个统计量来度量。针对各种规模的数据集，目前还没有很好的方法确定应该选 取多少个特征比较适宜，一般做法是根据测试结果来调整特征选取的个数。 目前，已经有很多研究者在这方面进行了大量工作，其中c m u ( 卡内基梅隆大学) 的 y a n gy t m i n g i 2 0 】教授和s t a n f o r d 大学的m e c h r a ns a h a m i 2 1 l 的研究较具代表性和总结 性。常用的特征选择方法有文档频率( d f - - d o c u m e n tf r e q u e n c y ) 、互信息( m i m u t u a l i n f o r m a t i o n ) 、信息增益( i g i n f o r m a t i o n6 a i n ) 、统计量等。 特征选择有两种方式：全局选择和局部选择。全局选择指在整个类型集上从原始 特征集中进行特征选择，选择后得到的特征对于各类型都是一致的刚。局部选择是指 以类别为单位对原始特征集进行选择，选择后各类别具有不同的特征集阎。一些研究 的分类结果表明，采用局部特征选择的分类效果要优于全局特征选择 2 3 1 。但是全局 特征选择能够从总体上控制特征集的大小，有利于对特征选择问题进行深入的研究， 由此我们实验中采取全局选择方式。 2 5 1 特征选择对分类的作用 文本分类的最大困难之一就是特征空间的高维性，因此，对特征空间进行降维( 特 1 2 硕士论文 基于语义中心的k n n 文本分类算法研究 征选择) 是很有必要的：减小文本的特征向量维数，保留有区分能力的特征。已取得的 研究成果表明，特征选择可以带来几方面的好处1 2 4 】：一是减小问题处理的规模，提 高分类效率；二是好的特征选择方法可以删除噪声词等特征，使文本之间的相似度更 为准确，即提高语义上相关文本之间的相似度，同时降低语义上不相关文本之间的相 似度，提高自动分类的效率；三是通过降维可以生成一个更紧凑、各维之间更独立的 特征空间，提高分类器的推广能力。 所以，特征选择结果的直接关系到后面分类器性能的好坏，当在测试中发现分类 器的效果较差时，不仅需要调整分类器的参数，更要考虑使用的特征选择方法是否合 适。 2 5 2 特征选择的几种方法 用于特征选择的统计量有：特征频率( 词频) ，文档频率，特征熵，互信息，信 息增益，c h i - s q u a r e ，相关系数，简化c h i ，特征强度脚垮。这些统计量从不同的角度 度量特征对分类所起的作用，每种方法都有自己的优缺点，没有公认的最优方法，需 要针对具体系统进行具体对比来确定最好的方法。 在下面对各统计量的解释中，使用概率p 在文本空间上进行计算。首先我们假设 以下是训练集文本扫描后参数，用于导出计算统计量的具体算式。其中，针对一个特 征t 和某一个类c ，有： c ：训练集中类别个数； n d o e ： 文档总数：n d o et ：训练集中含特征t 的文档总数； n d o ec ：类c 中的文档数n d o ect ：类c 中含特征t 的文档数； n t e r m ：训练集中总的特征数，包括每个特征词重复的次数； n t e r m _ t ：特征t 在训练集中出现的总次数： n t e r m _ c ：类c 中的所有特征出现的次数之和，包括各个特征重复的次数； n t e r mct ：类c 中特征t 出现的次数，包括重复的次数； 则可以得到如下概率值： 特征t 在总特征中的概率：pc = n t e r mc n t e m a ；及反概率：pnc = i pc ；