（计算机应用技术专业论文）基于改进词语权重的文本分类方法研究.pdf

独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得东北师范大学或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意。 学位论文作者签名：客聋日期：2 型堡：2学位论文作者签名：公聱日期：2 型堡：2 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和磁盘，允许论 文被查阅和借阅。本人授权东北师范大学可以将学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：进指导教师签名：翘 日 期：2 1 2 2 1 ：7 日期：兰! ：臣：! z 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 摘要 信息科技飞速发展的今天，互联网技术也得到了迅猛发展，电子文档的数量呈现了 指数级增长，海量信息为用户提供方便的同时，也给用户获取有用信息带来了不便。如 何有效地帮助用户查找、组织和管理这些信息，并且快速、准确地找到用户所需的有用 信息已成为当今研究的重要课题。正是在这样的背景之下，基于机器学习的文本分类方 法逐渐成为一个日益重要的研究领域。 文本分类是信息检索与数据挖掘领域的研究热点与核心技术，近年来得到了广泛的 关注和快速的发展。文本分类系统能够在给定的分类模型下，根据文本的内容对文本进 行分类，从而更好地帮助人们组织和挖掘文本信息，因此成为信息处理领域最重要的研 究方向之一，具有较大的发展潜力。文本分类具有很大的实用价值，它在信息检索和信 息过滤等方面有着广泛的应用，极大地提高了信息的使用效率。 本文研究的重点是通过改进传统的词语权重计算方法来提高文本分类精度。在对传 统的基于词语权重的文本分类方法作了深入研究的基础上，改进传统的词语加权方法一 t l i d f 方法，得到一种新的词语加权方法。传统的词语加权方法只考虑f f ( 词频) 、i d f ( 反 文档频率) 两方面，并且简单地认为低频词比高频词重要，所以，往往把稀有词赋予较 高的权值，但在实际当中，稀有词几乎不能作为文本的特征来表示文本。为了弥补这个 缺点，本文提出了新的计算词语权重的方法，来提高分类的效率和精度。并通过实验验 证了该方法的可行性和高效性。 实验表明，本文提出的改进词语权重的计算方法，在数据集r e u t e r s 2 1 5 7 8 上使用 k n n 分类器分类的效果，要优于传统词语权重计算方法使用k n n 分类器分类的效果。 实验结果证明，从评估函数精确率、召回率、只函数三方面来看，改进的词语权重计算 方法的分类效果要好于传统的词语权重计算方法的分类效果。 关键词：文本分类；t l i d f ：词语权重；k 近邻分类器 a b s t r a c t i n f o r m a t i o nt e c h n o l o g yb o o m i n gd e v e l o p m e n t a lt o d a y , i n t e r n e tt e c h n o l o g yh a sa l s o b e e nd e v e l o p i n gr a p i d l y t h en u m b e ro fe l e c t r o n i cd o c u m e n t sp r e s e n t se x p o n e n t i a lg r o w t h v a s ta m o u n t so fi n f o r m a t i o np r o v i d e su s e r sw i t hc o n v e n i e n c e ，b u ti tc a u s e si n c o n v e n i e n c ef o r u s e r st oo b t a i nu s e f u li n f o r m a t i o n h o wt os e a r c h ，o r g a n i z ea n dm a n a g ei n f o r m a t i o ne f f e c t i v e l yf o ru s e r sa n ds e a r c ho u t u s e f u li n f o r m a t i o nf o ru s e r sq u i c k l ya n da c c u r a t e l yh a v eb e c o m eav e r yi m p o r t a n ti s s u ea t p r e s e n t i nt h i sb a c k g r o u n d ，t e x tc l a s s i f i c a t i o nb a s e do nm a c h i n el e a r n i n gi sb e c o m i n ga l l i m p o r t a n tr e s e a r c hf i e l di n c r e a s i n g l y t h e r eh a v eb e e ne x t e n s i v es t u d i e sa n dr a p i dp r o g r e s s e si nt e x tc a t e g o r i z a t i o n ，w h i c hi s o n eo ft h eh o t s p o t sa n dk e yt e c h n i q u e si nt h ed a t am i n i n ga n di n f o r m a t i o nr e t r i e v a lf i e l da n d i th a sw i t n e s s e dab o o m i n gi n t e r e s ti nt h er e c e n td e c a d e s t e x tc a t e g o r i z a t i o ns y s t e m sc a l l c l a s s i f yt e x t sa c c o r d i n gt ot h et e x tc o n t e n t si nag i v e nc l a s s i f i c a t i o nm o d e l ，i no r d e rt ob e t t e r h e l pu s e r so r g a n i z ea n dm i n et e x ti n f o r m a t i o n ，t h e r e f o r e ，i ti sb e c o m i n go n eo ft h em o s t i m p o r t a n tr e s e a r c ha s p e c ti ni n f o r m a t i o np r o c e s s i n gf i e l d ，a n dh a sv e r yg r e a td e v e l o p m e n t a l p o t e n t i a l t e x tc l a s s i f i c a t i o nh a sg r e a tp r a c t i c a lv a l u e ，i th a sa ne x t e n s i v ea p p l i c a t i o n si nt h e i n f o r m a t i o nr e t r i e v a la n di n f o r m a t i o nf i l t e r i n g , a n di n c r e a s e si n f o r m a t i o ne f f i c i e n c yg r e a t l y i nt h i st h e s i s ，t h ef o c u so fr e s e a r c hi si m p r o v i n gt h ea c c u r a c yo ft e x tc a t e g o r i z a t i o nb y i m p r o v i n gt h et r a d i t i o n a lt e r mw e i g h t i n gm e t h o d s h a v i n gt h o r o u g h l yr e s e a r c h e dt h ee x i s t i n g t r a d i t i o n a lt e x tc l a s s i f i c a t i o nb a s e do nt e r mw e i g h t i n gm e t h o d s ，w ei m p r o v eat r a d i t i o n a lt e r m w e i g h t i n gm e t h o d - - t f - i d fm e t h o d ，a n do b t a i nan e wt e r mw e i g h t i n gm e t h o d t r a d i t i o n a l a l g o r i t h mo ft e r mw e i g h t i n go n l yc o n s i d e r sa b o u ti f ( t e r mf r e q u e n c y ) ，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 ) a n ds oo n ，a n dt h i sa p p r o a c hs i m p l yt h i n k sl o wf r e q u e n c yt e r m sa r ei m p o r t a n t ， l l i g hf r e q u e n c yt e r m s a r eu n i m p o r t a n t ，s oi t d e s i g n sh i g h e rw e i g h t st o t h er a r et e r m s f r e q u e n t l y t oc o m p e n s a t ef o rt h i sd e f i c i e n c y , w ep r e s e n tan e w t e r mw e i g h t i n ga p p r o a c ht o i m p r o v et h ee f f i c i e n c ya n da c c u r a c yo fc l a s s i f i c a t i o n a n dt h ee x p e r i m e n t a lr e s u l t sp r o v e t h a t t h en e w a p p r o a c hc a ni m p r o v et h ef e a s i b i l i t ya n de f f i c i e n c y t h ee x p e r i m e n t a lr e s u l t sp r o v et h a tt h ei m p r o v e dt e r mw e i g h t i n ga p p r o a c ha r es u p e r i o r t ot h et r a d i t i o n a lt e r mw e i g h t i n gm e t h o du s i n gk n nc l a s s i f i e rt oc l a s s i f yo v e rw i d e l y u s e d b e n c h m a r kd a t as e tr e u t e r s 一2 1 5 7 8f r o mp r e c i s i o n 、r e c a l la n df lf u n c t i o n k e yw o r d s ：t e x tc l a s s i f i c a t i o n ；t f - i d f ；t e r mw e i g h t i n g ；k n n i i i 目录 摘要ii a bstr a c t iii 第一章引言1 1 1 研究背景及意义j 1 1 2 国内外研究历史及现状2 1 3 本文的主要工作3 1 4 论文结构3 第二章文本分类的关键技术4 2 1 文本分类过程4 2 2 文本预处理5 2 3 常用文本表示方法5 2 3 1 布尔模型( b o o l e a nm o d e l ) 5 2 3 2 概率模型( p r o b a b i l i s t i cm o d e l ) 5 2 3 3 向量空间模型( v e c t o rs p a c em o d e l ) 6 2 4 常用特征选择方法7 2 4 1 文档频率( d f ) 7 2 4 2 信息增益( i g ) j 8 2 4 3 互信息( m i ) 8 2 4 4x 2 统计量( c h i ) 8 2 5 常用分类方法9 2 5 1 朴素贝叶斯( n b ) 9 2 5 2k 近邻( k n n ) 9 2 5 3 支持向量机( s v m ) 1 0 2 5 4 人工神经网络( a n n ) 1 l 2 5 5 决策树( d t ) 1 2 2 6 性能评价指标1 2 2 7 小结1 3 第三章词语权重计算方法的改进15 3 1 常用词语权重计算方法1 5 3 1 1 布尔权重1 5 3 1 2 词频权重( t f ) 1 5 3 1 3i d f 权重1 6 3 1 4t f i d f 权重1 6 3 2 传统方法的不足1 7 3 3 改进的方法1 7 3 4 分类器的设计1 9 3 5 小结1 9 第四章实验结果及分析2 1 4 1 实验介绍2 l 4 1 1 数据集2 1 4 1 2 参数设定2 l 4 2 实验结果2 2 4 3 分析与讨论2 3 4 4 小结2 4 第五章总结和展望2 5 5 1 总结2 5 5 2 进一步工作2 5 参考文献2 7 致谢3 0 在学期间公开发表论文情况3l v 东北师范大学硕士学位论文 1 1 研究背景及意义 第一章引言 2 0 世纪9 0 年代以来，互联网作为一个开放的信息空间，得到了快速的发展，互联 网信息呈现爆炸式增长，而网络资源中的大部分以文本形式存在的信息越来越多，呈现 指数级增长，原因是文本数据占用网络资源少，不像声音、图像等占用大量的内存空间， 而且容易上传和下载。面对丰富的网络信息，一方面为用户带来前所未有的便捷，另一 方面也给用户获取有用信息带来了不便。如何有效地帮助用户查找、组织和管理这些信 息，并且快速、准确地找到用户所需的有用信息已成为当今研究的重要课题。搜索引擎 的出现在一定程度上为用户提供了适当的帮助和支持，但是搜索结果庞大，还是不利于 用户找到所需要的信息。在这样的背景之下，基于机器学习( m a c h i n el e a r n i n g ) 的文本 分类( t e x tc l a s s i f i c a t i o 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 g ) 领域的研究热 点与核心技术，近年来得到了广泛关注和快速发展。特别是在线信息资源的逐渐增加， 文本分类显得越来越重要。最初的文本分类是依靠人工方法进行的，通过手工劳动对文 本进行分类，这样既费时又费力，当信息呈现指数级增长时，人工分类已经不能满足用 户的需求，趋于瘫痪。文本自动分类能较好地解决大量文本分类问题，在信息检索、自 然语言处理、信息过滤等领域都有着广泛的应用，具有极大的实用价值。 文本分类是指按照预先定义的主题类别，根据文本内容把文档划分到和它相关的类 别中去。通过文本自动分类系统把文档分到属于它自己的类别当中，这样可以帮助人们 更快更好地找到所需要的信息。随着信息量的增加，人们对信息的查准率、查全率的要 求也逐渐增加，这样对文本分类的需求也就越来越大，因此对文本自动分类技术的深入 研究具有重要意义。文本分类最大的特点就是特征空间的高维性，我们的研究目的就是 寻求一种有效的特征选择方法，降低特征空间的维数，提高分类精度。所以文本分类的 关键技术就是对高维的特征空间进行降维，而特征选择是进行降维的关键技术，特征选 择的好与坏会直接影响分类结果，而特征词权重的计算方法又是特征选择的关键技术， 对于词语权重的计算方法越来越受到学术界的关注，是文本分类重要的研究方向之一。 东北师范大学硕士学位论文 1 2 国内外研究历史及现状 国外对文本分类技术的开创性研究始于2 0 世纪5 0 年代。1 9 5 8 年1 9 6 4 年，主要是 对文本分类技术进行可行性研究。5 0 年代末，由美国i b m 公司的h e l u h n 在这一领域 作了开创性的研究，他首先将词频统计的思想应用在文本分类中1 1 l 。1 9 6 0 年，m a r o n 在 j o u r n a lo fa s m 上发表了关于文本自动分类算法的第一篇论文o nr e l e v a n c e ， p r o b a b i l i s t i ci n d e x i n ga n di n f o r m a t i o nr e t r i e v a l ) ) 。1 9 6 2 年，h b o r k o 等人提出利用因子分 析法进行文本的自动分类。其后k s p a r c k 、g s a l t o n 等许多学者在这一领域进行了卓有 成效的研究工作，其中，基于词频统计分析思想一直处于领导地位，应用比较广泛。2 0 世纪6 0 年代至8 0 年代末，文本分类技术进入到实验性研究。主要是以知识工程技术为 主的文本自动分类方法研究，使用人工的方法来构建分类器，这样既耗费人力物力，又 容易出现人为错误，所以在实际当中很少单独使用这个方法。在这一阶段，s a l t o n 等人 提出的向量空间模型( v s m ) 表示法【1 4 】，成为后来广泛采用的文本表示方法。2 0 世纪9 0 年代以后，特别是互联网技术的迅猛发展，分类技术发生了翻天覆地的变化，这一阶段 主要是以机器学习占主导地位的自动分类技术。出现了许多经典的分类模型和算法，如 k 近邻、朴素贝叶斯、神经网络、决策树方法等等，1 9 9 5 年，v a p n i k 提出了著名的支 持向量机( s v m ) 方法【3 1 ，与传统的方法相比，它在分类性能上有了很大的提高，一度成 为研究热点。到目前为止，国外的文本自动分类研究已经进入到了实用化阶段，并在邮 件分类、电子会议等方面取得了比较广泛的应用1 4 j ，1 9 9 7 年，德国d o r t m u n d 大学的 t o r s t e nj o a c h i m s 等人研究了基于向量空间模型的自动分类系统，美国斯坦福大学的 d a p h n ek o l e 等人提出基于很少语料词汇的层次自动分类方法。1 9 9 8 年，美国的卡内吉 梅隆大学的y i m i n gy a n g 等人将决策树应用于文本在线自动分类中。随后，还有麻省理 工学院为白宫开发的邮件分类系统、卡内基集团为路透社开发的c o n s t l l l e 【5j 系统。 国内对文本分类技术的研究，与国外相比，起步较晚，开始于2 0 世纪8 0 年代。中 文文本分类与英文文本分类之间有一定的差异，主要的差别就是在预处理阶段，不管是 中文还是英文文本，都需要分词，不像英文文本分词用空格来区分那样简单，中文文本 是以词或词组作为最小特征来分词的，因此，中文文本分词有一定的难度，目前已经形 成了多种典型的分词系统。另外，句法分析和语义分析方面也有所不同。所以，中文文 本分类不能照搬照抄国外的研究成果，只能是在英文文本分类的基础上，结合中文文本 分类的特点，形成针对中文文本的分类系统。1 9 8 1 年，侯汉清1 6 j 教授首先从计算机管理 分类表、计算机分类检索、计算机自动分类、机编分类表等四个方面对国外文本分类技 术的发展概况进行阐述和介绍。此后，国内很多学者在这方面都进行了深入的研究，并 且取得了突出的成就。1 9 8 6 年，上海交大开发了针对中文科技文献实验性分类系统。1 9 9 5 年，清华大学研制了针对汉语语料自动分类系统 7 1 。1 9 9 8 年，东北大学研制成功了汉语 新闻语料文本自动分类系统【引。此外，中国科学院、复旦大学、哈尔滨工业大学等一些 大学的著名学者在该领域也做出了突出贡献。 2 东北师范大学硕士学位论文 1 3 本文的主要工作 本文对国内外基于词语权重的英文文本分类方法进行了深入地研究。对文本分类的 文本预处理、文本表示方法、特征选择方法、分类器的设计与实现以及性能评价等各个 模块进行系统地研究与探讨，本文将改进词语权重的计算方法作为主要工作，通过对传 统的基于词语权重的计算方法的研究，发现传统的词语权重计算方法t f - i d f 方法在计算 特征词权重的时候，经常会把较高的权重赋给那些在少量文本中出现的稀有词，针对这 个缺点，本文提出一种改进的计算文本特征词权重的方法，并对其进行了实验分析。实 验结果比较令人满意。 1 4 论文结构 本文各章节具体安排如下： 第一章：引言。主要介绍文本分类的研究背景及意义、国内外对文本分类的研究历 史及现状，并给出论文的主要研究内容和组织结构。 第二章：文本分类的关键技术。主要介绍文本分类的一般过程，文本预处理、文本 表示方法，常用特征选择方法，常用的分类方法以及评估方法。 第三章：词语权重计算方法的改进。主要介绍常用的词语权重计算方法以及传统方 法的缺点，针对缺点对原有方法进行改进。 第四章：实验结果及分析。在前一章理论的基础上进行试验，通过设计几组实验对 比，对实验结果进行分析。 第五章：总结与展望。主要对本文工作进行总结和对未来工作提出展望。 3 东北师范大学硕士学位论文 2 1 文本分类过程 第二章文本分类的关键技术 通常，网络中的大部分信息是以文本或超文本形式存在的，我们平时接触的具有一 定内容的一段文字就可以成为文本。文本分类( t e x tc l a s s i f i c a t i o n ) 9 】【1 0 】是指按照预先定义 的主题类别c ，为文档集合d 中的每个文档确定一个类别g 。从数学的角度来讲，文本 分类指的是映射的过程【9 1 ，这个映射可以是一对一的映射，也可以是一对多的映射，通 常，一篇文档可以属于一个或几个类别。设这个映射设为亭，数学公式表示如下： 孝：d _ c其中：d = 九如”；磊，) ，c = q g ，c ：) 其中，d 为文档集合，c 为类别集合，文档集合d 可以是无限集合，类别集合c 是有限集合。 文本分类的一般过型1 6 1 包括：文本预处理、文本表示、特征选择、分类方法的选择 和性能评价五个部分。文本分类系统各个模块的功能如图2 1 所示： 将待分类文本处理成统一格式 把规范化的文本分解成最小处理单元 把能代表文本内容的特征提取出来 选择合适的分类器，对文本进行分类 对分类结果好坏的评价 类系统各个模块的功能 4 东北师范大学硕士学位论文 2 2 文本预处理 文本预处理是将不规范的文本信息转换成计算机能够处理的文字信息，是将非结构 化的文本转换成计算机能够处理的结构化形式。文本预处理过程主要是规范文档格式， 把原始文档处理成统一格式，以方便于后续工作。一般情况下，文本预处理的结果会直 接影响文本分类的精度，是文本分类中关键因素之一。文本预处理阶段的主要工作【1 1 】( 本 文指英文语料) 包括：词根还原、去停用词、去标点符号、去标记信息等工作。 2 3 常用文本表示方法 在对文档进行分类之前，必须把文档表示成计算机可以处理的形式。目前，常用的 文本表示模型主要有三种【1 2 】：布尔模型( b 0 0 l e 柚m o d e l ) 、概率模型( p r o b a b i l i s t i cm o d e l ) 、 向量空间模型( v e c t o rs p a c em o d e l ，简称v s m ) 。因为文本分类是基于信息检索发展起来 的，所以，信息检索中的很多方法都适用于文本分类中。这几种文本表示方法也是从信 息检索领域借鉴过来的。 2 3 1 布尔模型( b o o l e a nm o d e l ) 布尔模型( b o o l e a nm o d e l ) 是最简单、最严格的匹配模型。最早应用于信息检索模型。 它是用布尔表达式和用户的查询信息进行匹配，以文本中是否包含所查询的关键词来表 示文档内容。布尔模型定义了一个二元变量集合来表示文档，对于一篇文档来说，如果 包含所查询的关键词，其对应变量的值为1 ；否则，其对应的变量的值就为0 。在文本 检索时，根据用户提交的检索条件是否满足文档表示中的逻辑关系，分为相关和不相关 两种状态。 2 0 世纪六七十年代，布尔模型取得了较大的发展，在这期间出现了很多基于布尔模 型的商用检索系统，如d i a l 0 0 , s t a i r s 等。许多搜索引擎也采用布尔检索模型，如 y a h o o 。其主要特点是：方法简单，容易理解，检索速度快。同时它也存在着一定的缺 陷，就它的匹配策略来讲，缺乏对文本相关性排序，有一定的局限性。 2 3 2 概率模型( p r o b a b i l i s t i cm o d e l ) 概率模型( p r o b a b i l i s t i cm o d e l ) 是基于贝叶斯理论而被提出来的。信息检索中的概率 模型的基本思想是：给定一个用户的查询q 和集合中的文档函用概率模型来估计用户查 询串g 与文档盔的相关概率，并按照计算结果进行排序。此模型试图估计用户找到其感 兴趣的文本盔的概率，模型假设这个相关概率只依赖于查询和文本表示。 概率模型的一般公式为p ( r i q , 田，其中，p 表示文档d 与用户查询串q 被用户判断为 相关的概率。该模型假设存在一个所有文档的集合，这种概率只取决于文档和查询串。 5 东北师范大学硕士学位论文 并且文档对查询串的相关性与文档集合中的其它文档是独立的。 概率模型的优点是：理论上，文档可以按照其相关概率的大小进行排序。缺点是： 需要把文档集分为相关和不相关两个集合，通常情况下是很难做到的。只采用简单的二 元变量形式，没有考虑到特征词在文档中出现的频率等信息，并且这种模型处理问题过 于简单。 2 3 。3 向量空间模型( v e c t o rs p a c em o d e l ) 向量空间模型( v e c t o rs p a c em o d e l ) 刈是由g s a l t o n 等人在2 0 世纪6 0 年代末提出来 的。是较早应用于信息检索领域的经典计算模型，并且成功应用于著名的s m a r t 系统， 后来在文本分类、信息检索等许多领域也得到了广泛的应用。这个模型已经成为最简单、 效果最好的文本表示之一，所以，本文也使用这个方法对文档进行向量化。 向量空间模型的思想是用特征向量来表示文本内容，特征词作为特征向量，对于英 文语料，特征词就是单独的一个词，而对于中文语料，特征词可以是字、词或是短语， 这主要依靠分词系统。在向量空间模型中，文档盔被看作由一组特征词纯匕，如) 组成的n 维向量空间，其中，每个如都是不同的，相互独立的。文档西是以特征词的权 重为分量的向量表示，即石= “f ，j w 暂) ，其中七表示特征词集合的长度，聊表示第 ，篇文档中第f 个特征词的权重，通常o = 脚= 1 。这样，相关度的计算就转化为对空间向 量的计算，大大降低了计算的复杂性。 对于文本分类来说，计算文档之间彼此相关程度就是计算两个向量的相似度 ( s i m i l a r i t y ) ，用s i m 仇呦来表示文档d i 和西之间的相似度。常用的相似度计算方法是基 于距离相似度的方法，包括欧式距离( e u c l i d e a nd i s t a n c e ) 、向量内积( i n n e rp r o d u c t ) 、夹 角余弦( c o s i n e ) 等，其公式如下： ( 1 ) 欧式距离计算公式，如公式( 2 1 ) 所示： 一 s i m ( d d ) 一o ( c l 州d ) 一、( 岷一) 2 o ks 刀)( 2 1 ) 其中，w k 表示文档磊的特征词玖的权重，吼表示文档d j 的特征词改的权重，n 是 特征词的总数，也是特征空间的维数。 ( 2 ) 向量内积计算公式，如公式( 2 2 ) 所示： s 拥( ) 2 。荟。w 庐( 1 k s n )( 2 2 ) ( 3 ) 夹角余弦计算公式，如公式( 2 3 ) 所示： s i m ( d i ，d ) 一c o s o ； 一 荟 6 ( 1sks ，1 )( 2 3 ) 东北师范大学硕士学位论文 使用余弦夹角计算相似度的公式，得到的结果是在o 和1 之间的数，值越大说明两 篇文档越相似。本文使用夹角余弦来计算文档之间的相似度。 在向量空间中，文本之间的夹角如图2 2 所示： 图2 2文本相似度的夹角余弦表示 2 4 常用特征选择方法 特征选择是文本分类中的一个重要步骤。待分类的文本经过词根还原、去停用词等 文本预处理之后，文本集的特征数也可能是十几万或几十万个特征词，但是每一篇文档 包含的特征词却很少，这样，构造出来的向量空间模型就是一个稀疏的高维矩阵。对于 任何分类算法来说，计算开销太大，也会影响算法的时间和空间的复杂度。特征集中的 一部分特征词很可能是噪音词，对文本分类的结果贡献不大，甚至对分类结果还会有影 响。寻找一种有效的特征降维方法，降低特征空间维数，最终提高分类精度和效率。常 用的文本特征选择方法有【1 4 】【1 5 】：文档频率( d f ) 、信息增益( i g ) 、互信息( m i ) 、x 2 统计量 ( c h i ) 等。 2 4 i文档频率( d d 文档频率( d o c u m e n tf r e q u e n c y ) 指在某一文档集中，出现某个特征词的文档数。它 是最简单、最常用的特征选择方法。它的基本思想是：当特征词的文档频率低于某个阈 值时，就认为这个特征词含有较少的类别信息，对分类结果影响较小，有可能还会影响 分类效果；当特征词的文档频率高于某个阈值时，包含较多的信息量，对分类结果影响 比较大。这样，低于这个阈值的特征词就从特征空间中移除，也不会对分类结果造成很 大影响，保留高于阈值的特征词，这样既能降低空间维数，又能减少分类器的计算复杂 度，有助于提高分类性能。文档频率计算简单，由于文档频率具有相对于训练文档规模 的线性计算复杂度，它能够容易地用于大规模文档集特征选择中。它的缺点是没有考虑 到移除文档频率低的特征词，可能会影响分类结果的准确性，这些词可能也会含有较多 的分类信息。 7 东北师范大学硕士学位论文 2 4 2 信息增益( i g ) 信息增益( i n f o r m a t i o ng a i n ) 是引用数学中熵的概念，是一种基于熵的理论的评估方 法。信息增益方法在机器学习领域广泛使用。它是通过计算某个特征词是否出现对类别 的信息增益。它的计算公式如公式( 2 4 ) 所示： 6 ( t ) = 一善尸 ) l 。g p ( c f ) + 尸) 善p ( q i f ) 1 。g 尸( c fi f ) + p ( t ) 荟e ( qi t ) l 。g e ( c , l i ) ( 2 4 ) 其中，p ( q ) 表示类别q 的概率，p o ) 表示包含特征词t 的文档数在整个文档集中的概率， p o ) 表示不包含特征词f 的文档的概率，讹i t ) 表示包含特征词t 且属于类别q 的条件 概率，p ( qi t ) 表示不包含特征词t 属于类别c f 的条件概率，m 表示类别总数。g 的值 越大就表示特征词t 所含的信息量越多，特征词对类别的贡献量按i g 排序。 2 4 3 互信息( m i ) 互信息( m u t u a li n f o r m a t i o n ) 被广泛应用于统计语言模型中。在统计学中，互信息用 于表征两个向量的相关性。在文本分类中，主要体现了特征词和类别之间的相关度，计 算公式如公式( 2 5 ) 所示： 挑咖茎嵩 ( 2 5 ) 在实际运算中，这些概率可以使用特征词在文档中的频率进行相似计算。它的缺点 是受临界特征的概率影响比较大，当特征词的p a l c r ) 值相等时，文档中稀有词的m i 值 比较高，所以，互信息方法比较侧重稀有词。 2 4 4x 2 统计量( c h d x 2 统计- 量( c h i - s q u a r es t a t i s t i c ) 方法与互信息( m i ) 方法类似。该方法也是度量特征词 和类别之间的相关性。计算公式如公式( 2 6 ) 所示： 肌) = 逖鬻等嚣酱巡 ( 2 6 ) 其中，p ( t ，c f ) 表示包含特征词t 且属于类别c i 的概率，p o ，q ) 表示不包含特征词t 且属于类别c f 的概率，p o ，q ) 表示包含特征词t 且不属于类别c f 的概率，p o ，q ) 表示不 包含特征词t 且不属于类别q 的概率。x 2 统计量的值越大，相关性越大。 相关实验表明【1 5 】f 砌】：i g 是最有效的方法之一，d f 的效果比i g 稍差，而m i 的效 果却相对较差。因为i g 的效果较好，所以，本文使用i g 方法进行特征选择。 东北师范大学硕士学位论文 2 5 常用分类方法 目前，常用的经典的分类算法都是基于机器学习方法的，很多研究者从不同的角度 提出很多有效的分类算法。这些分类方法大致上可以分成三类：( 1 ) 基于统计的方法，如 朴素贝叶斯( n a i v eb a y e s ) 方法、k 近邻( 1 心呻方法、支持向量机( s v m ) 方法；( 2 ) 基于连 接的方法，如人工神经网络( a n n ) 方法；( 3 ) 基于规则的方法，如决策树( d e c i s i o nt r e e ) 。 本节将简单介绍这几种分类方法。 2 5 1 朴素贝叶斯( n b ) 朴素贝叶斯( n a i v eb a y e s ) 2 9 1 1 7 j 9 】是利用概率统计进行分类的算法，它是一种简单有 效的分类方法。朴素贝叶斯方法成立的前提是假设各个属性之间相互独立，是不相关的。 这样就大大减少了分类器的计算开销，但是这样也可能会影响分类结果。如果一个数据 集满足这个类条件独立性假设，则有较高的分类效果，否则分类效果较低。贝叶斯定理， 是用来预测文档属于某个类别的概率。根据预测结果将文档分到概率最高的类别中去。 假设d 为任意文档，文档d 用其含有的特征词来表示，即d = e z ，匕功，k 为文档 的特征词数，毛表示文档d 中的第j 个特征词，由此得到下式： i p 似i c j ) 一p 瓴，乞，气) = ilp l c j ) ( 2 7 ) 其中，p 瓴l c ，) 表示分类器预测特征词t i 在类别勺的文档中发生的概率。 根据贝叶斯定理： 盹协d 警 ( 2 8 ) 由于p ( a ) 对所有类来说都是常数，所以公式( 2 8 ) 可以转换为： p ( c fi d ) p ( c ) p ( di c f ) ( 2 9 ) 由公式( 2 7 ) 和公式( 2 9 ) - i 得到如下公式： p ( c ji d ) 尸( c j ) 兀p c ，) ( 2 1 0 ) 贝叶斯方法容易使用，且只需要扫描一次训练数据。但数据的属性之间通常不是独 立的，要通过忽略属性间的关系，取关系不大的子集进行计算。 尽管这个方法给出的独立性假设在实际当中是不成立的，但是朴素贝叶斯方法的分 类效率还是很高的，所以在很多领域都得到了广泛的应用。 2 5 2k 近邻f k n i 町 k 近邻f 2 0 - 2 1 】( 简称k n n ，k - n e a r e s tn e i g h b o r ) 分类算法最早由c o v e rh a n 提出来的， 已有四十多年的发展历史。k n n 是著名的模式识别系统学方法之一，它是一种基于实 9 东北师范大学硕士学位论文 例的分类方法。 它的基本思想是：对于一篇待测文档，首先考虑的是，计算训练文档集与该待测文 档的相似度，根据文本相似度找出与该待测文档最相似( 也是距离最近) 的k 篇文档， 然后根据这k 篇文档所属的类别判定新文档所属的类别。当k = i 时，就变成里最近邻 ( n m 方法，就是找出与待测文档距离最近的一篇文档，根据这篇文档的类别，对新文档 进行归类。k 值的确定通常都是预先定义一个值，然后再根据实验反复对k 值进行调整。 k 值的选择过大过小都会影响到分类结果，所以对k 值的选择要慎重。 算法步骤如下： ( 1 ) 把预处理之后的文档向量化，使用向量来表示文档； ( 2 ) 对于一篇新的待分类文档，按照特征词的特点进行分词，把新文档表示成向量 形式； ( 3 ) 使用相似度计算公式，如公式( 2 3 ) 所示，计算并挑选出训练集中与该文档最相 似的k 篇文档； ( 4 ) 在与该文档最相似的k 篇文档中，计算每一类的权重； ( 5 ) 比较每一类的权值，将新文档分到权值最大的类别中。 许多实验都表明，k n n 分类算法简单有效，操作容易，在众多领域广泛应用。k n n 算法的缺点是，每一篇待测文档都与训练集中的每一篇文档进行相似性计算，当训练规 模较大时，算法的计算开销过大，所以，k n n 算法适用于训练规模较小的情况。 2 5 0 支持向量机( s v m ) 支持向量机【2 2 - 2 3 l ( s u p p o av e c t o rm a c h i n e ) ：是1 9 9 5 年由v a p n i k 3 】提出来的。它用于解 决两类模式问题【4 2 1 。它是一种基于统计学习理论的机器学习方法，广泛应用于文本分类、 图像处理、生物信息学等领域。由于其良好的性能，支持向量机已经成为近年来学术界 的研究热点之一。j o c h i m s 最早将s v m 方法应用于文本分类中【4 3 1 。 支持向量机是建立在统计学理论中的v c 维理论和结构风险最小化原则之上，它主 要是针对两类分类问题，把训练集映射到高维空间，其目的是对于输入空间中线性不可 分的情况映射到高维空间后转换成线性可分的情况，然后在高维空间中寻找一个最优超 平面作为两类的分界，用来保证最小的分类错误率。支持向量机能较好地解决高维、非 线性、小样本等问题。它的优点是不依赖维数，只依赖样本个数。 如果已知一个训练集为：a 2 ) ，纯，y o ，x e r a ，) ， + 1 ，- 1 ) ，n 为输入空间的 维数，在线性可分的情况下，会被存在一个超平面把这两类样本分开。这个超平面可记 为： w * x + b = o ( 2 1 1 ) 且如下分类： 当w * x + b = o 时，姐= + 1 ； 当w * x 柏 o 时，y f - 1 1 0 东北师范大学硕士学位论文 w 是超平面的法线方向。 如果训练数据能准确地被划分开，则每类数据与超平面距离最近的向量与超平面之 间的距离最大称这个平面为最优超平面，如图( 2 3 ) 所示： 支持向量 y - 。 图2 3 两类问题的分类超平面 支持向量机要解决的关键问题是，首先，找到一个非线性映射，把输入空间中线性 不可分的情况转换到高维空间线性可分的情况。其次，确定最优超平面，最大限度地把 两类数据分开。支持向量机的详细介绍请参考其它文酬矧【徜】。 许多研究表明，支持向量机已经能够处理多类分类问题，在分