（计算机应用技术专业论文）knn算法的改进及其在文本分类中的应用.pdf

摘要 摘要 随着互联网的快速发展，网络上的文本信息急剧增长，如何从庞大的信息库中提取 有用的信息已变得越来越重要，这有赖于数据挖掘中的文本挖掘技术。文本分类技术是 文本挖掘的关键技术之一，因此，对文本分类的研究具有重要的意义。 k n n 以简单和高鲁棒性而被广泛应用于机器学习和数据挖掘领域，被证实是向量空 间模型( v s m ) 下最好的文本分类方法之一。然而k n n 算法有其固有的缺点，当训练样本 集过大或特征过多时，k n n 算法的效率会明显下降。 针对k n n 算法的不足，本文提出了一种改进的k n n 文本分类算法一p k n n ，该算法基 于投影寻踪理论和i d i s t a n c e 索引结构，能够通过对一维投影距离的搜索快速获得与待 分类样本最近的小样本库，然后通过计算与小样本库内文本的相似度即可获得最近的k 个样本，而无须与整个训练样本库的文本进行计算，因而在保证分类精度的同时明显提 高了计算的效率。 本文首先介绍了文本分类技术的概况和研究现状，然后系统介绍了文本预处理技 术，在对k n n 算法研究的基础上，提出了改进的p k n n 算法。在此基础上，实现了一个 中文文本分类系统，该系统由训练模块、分类模块、评价模块组成，能够对文本进行去 停用词、特征选择、加权、分类等功能。该系统可以实现不同特征选择算法之间、p k n n 和i ( n n 之间分类性能的对比。 最后通过实验验证了p k n n 算法的效率和准确性。 关键词：文本分类、k n n 、特征选择、降维、投影 a b s t r a c t 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 ft h ei n t e m e t ，t e x ti n f o r m a t i o ng r e a t l yi n c r e a s e s ，a n dh o wt o g e tu s e f u li n f o r m a t i o ni sb e c o m i n gm o r ea n d m o r ei m p o r t a n t ，t e x tm i n i n gc a nh e l pt og a i ni t t e x tc l a s s i f i c a t i o ni st h ek e yt e c h n o l o g yo ft e x tm i n i n g ，s or e s e a r c ho nt e x tc l a s s i f i c a t i o ni s e x t r e m e l yi m p o r t a n t k n ni sw i d e l yu s e di nm a c h i n el e a r n i n ga n dd a t am i n i n go w i n gt oi t ss i m p l e n e s sa n d r o b u s t n e s s ，a n dh a sb e e np r o v e dt ob et h eb e s tm e t h o di nv e c t o rs p a c em o d e l s h o w e v e r , k n nh a sas h o r t a g e ：t h ec l a s s i f i c a t i o ne f f i c i e n c yw i l lf a l lw h e nt h et r a i n i n gs a m p l es e t sa n d a t t r i b u t e si n c r e a s e a i m i n ga tt h es h o r t a g eo fk n n ，t h i sa r t i c l ep r e s e n t sa ni m p r o v e dk n na l g o r i t h mn a m e d p k n n ，w h i c hb a s e so np r o j e c t i o np u r s u i tt h e o r ya n di d i s t a n c ei n d e xs t r u c t u r e ，t h ep k n n c a np i c k su pn e a r e s tt r a i n i n gs a m p l es e t sb ys e a r c h i n gs i n g l ed i m e n s i o n a lp r o j e c t i o nd i s t a n c e ， t h e ng e t st h en e a r e s tk n e i g h b o r sb yc a l c u l a t i n gt h es i m i l a r i t yb e t w e e nt h et e s ts e ta n dt h e s e l e c t e dt r a i n i n gs e t s b e c a u s et h es e l e c t e dt r a i n i n gs e t sa r ef a rl e s st h a nt h ew h o l et r a i n i n g s e t s ，s ot h ep k n nc a ni m p r o v ee f f i c i e n c yo fc l a s s i f i c a t i o n t h i sa r t i c l ef i r s t l yi n t r o d u c e sg e n e r a ls i t u a t i o na n dr e s e a r c ho ft e x tc l a s s i f i c a t i o n ，t h e n ， a n a l y s i si nv e r yd e t a i lt h ep r e p r o c e s s i n go ft e x tc l a s s i f i c a t i o n a f t e rf u r t h e rr e s e a r c ho nk n n ， a ni m p r o v e dp k n na l g o r i t h mi sp r e s e n t e d ，a n dac h i n e s et e x tc l a s s i f i c a t i o ns y s t e mi s d e s i g n e db a s e so nt h ep k n nt h e o r y ，t h es y s t e mh a st r a i n i n gm o d u l e 、c l a s s i f i c a t i o nm o d u l e a n de v a l u a t i o nm o d u l e ，t h ef u n c t i o n so ft h es y s t e ma r ea sf o l l o w s ：r e m o v i n gs t o pw o r d sf r o m t e x t s ，f e a t u r e ss e l e c t i o n ，c o m p u t i n gw e i g h to ff e a t u r e s ，c l a s s i f i c a t i o n ，a n ds oo n t h es y s t e m h a st w of e a t t i r es e l e c t i o nm e t h o d sa n dt w oc l a s s i f i c a t i o nm e t h o d st oc h o s e f i n a l l y , s o m ee x p e r i m e n t sd e s i g n e dt ov a l i d a t et h ee f f i c i e n c ya n dp r e c i s i o no fp k n n k e y w o r d s ：t e x tc l a s s i f i c a t i o n ，f e a t u r es e l e c t i o n ，k - n e a r e s tn e i g h b o r s ，d i m e n s i o n a l i t y r e d u c t i o n ，p r o j e c t i o np u r s u i t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 签 名：3 二扯日 期：j 埠二l 名征 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名：导师签名： 日 期： 第一章绪论 第一章绪论 1 1 课题研究背景及意义 随着信息技术的发展和互联网的普及，文本的信息量急剧增加，中国互联网络信息 中心( c n n i c ) 2 0 0 8 年发布信息显示，目前，中国的网页总数为8 4 7 亿个，年增长率达到 8 9 4 ，网页总字节数达到1 9 8 ，3 4 8 g b ，这些信息大部分是非结构化或半结构化的信息， 其中包含了很多有价值的内容，信息就是财富、知识、生产力，如何从庞大的信息库中 提取有用的信息成为当今研究的热点。 文本挖掘( t e x tm i n i n g ) 为从大量文本数据中提取有用的信息提供了用力的工具， 文本挖掘是指从大量文本数据中抽取事先未知的、可理解的、最终可用的信息或知识的 过程。直观地说，当数据挖掘的对象完全由文本数据类型组成时，这个过程就称为文本 挖掘。文本挖掘中最基本的两项工作就是分类和聚类，几乎在所有文本挖掘的应用领域 都离不开文本的分类和聚类。 文本分类是文本挖掘的一个重要内容，是指按照预先定义的主题类别，为文档集合 中的每个文档确定一个类别。通过自动文本分类系统把文档进行归类，可以帮助人们更 好地寻找需要的信息和知识。传统的文献分类研究有着丰富的研究成果和相当的实用水 平。但随着文本信息的快速增长，特别是i n t e r n e t 上在线文本信息的激增，文本自动 分类已经成为组织和处理大量文本数据的关键技术。 现在，文本分类正在各个领域得到广泛的应用。但随着信息量日趋丰富，人们对于 内容搜索的准确率、查全率等方面的要求会越来越高，对文本分类技术需求大为增加， 因此对文本分类技术进行深入研究具有重要的意义。 文本分类是信息过滤，搜索引擎、数字化图书馆的关键技术之一，具有广阔的应用 前景。 ( 1 ) 信息过滤：i n t e r n e t 的高速发展使其成为世界上最丰富的信息资源，已成为人 类获得信息的最主要的途径之一。随着互联网的不断发展，“垃圾信息 的泛滥问题也 变得日益突出。2 0 0 9 年5 月，计算机安全厂商赛门铁克( s y m a n t e c ) 发布的报告显示，在 所有电子邮件中，垃圾邮件的比例已经达到9 0 4 ，调查显示，美国垃圾邮件每年造成 经济损失7 0 0 亿美元，中国互联网协会反垃圾邮件中心2 0 0 7 年公布统计结果显示，我 国网民收到的垃圾邮件总量接近7 0 0 亿封，给我国造成了1 8 8 4 亿元的巨额损失。怎样 阻止垃圾信息在网上传播；怎样保护企业机密、个人隐私不被泄露；怎样从海量的网络 资源中，挖掘具有宝贵有使用价值的信息；怎样在获取所需信息的同时，过滤掉无用的 信息，已成为当今网络安全技术领域的研究热点，文本分类技术作为信息过滤的基础技 术，必将会得到很大的发展。 ( 2 ) 搜索引擎：随着网络的普及，搜索引擎在人我们生活中起的作用越来越大，已 经成为获取知识、解决问题的一个重要的途径。搜索引擎获取网页依靠网页抓取程序 ( s p i d e r ) ，s p i d e r 顺着网页中的超链接，连续地抓取网页。这些通过关键字抓取的网页 江南大学硕士学位论文 涉及各个领域，而且信息量非常巨大，但用户所需的仅是某一类的相关信息，怎样准确、 高效地返回用户所需的网页，成为搜索引擎设计的关键，而文本分类技术可以对s p i d e r 抓取的网页进行分类，大大提高了信息检索的效率和准确性。 ( 3 ) 数字图书馆：数字图书馆( d i g i t a ll i b r a r y ) 是一个新兴的研究领域，是指用 数字技术处理和存储各种文献的图书馆，涉及了数据仓库、数据挖掘、互联网、多媒 体等多个技术领域，实质上是一种多媒体制作的分布式信息系统。数字图书馆存储了海 量的图书资料，采用自动文本分类技术可以提高图书的检索速度，提供个性化的检索服 务。 1 2 国内外研究现状乜儿羽 自动文本分类的研究始于2 0 世纪5 0 年代末，到目前，文本自动分类在国外经历了 三个发展阶段： 第一阶段( 1 9 5 8 1 9 6 4 ) ：主要进行文本自动分类的可行性研究，在此期间，i b m 公 司的h p l u h n 在这一领域进行了开创性的研究，提出了采用词频统计提取摘要的思想 h 1 。1 9 6 0 年，m a r o n 在j o u r n a lo fa s m 上发表了关于文本自动分类的第一篇论文o n r 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 5 1 9 7 4 ) ：进行文本自动分类的实验研究，1 9 7 1 年，r o c c h i o 提出了 在通过用户的反馈来修正权重向量，来构成简单的线性分类器。m a r kv a nu d e n 、m u n 等给出了其他的一些修改权重的方法。 第三阶段( 1 9 7 5 至今) ：自动分类进入实用化阶段，1 9 7 9 年，v a nr i j s b e r g e n 对信息检索领域的研究做了系统的总结，提出的信息检索的一些概念，如向量空间模型 ( v e c t o rs p a c em o d e l ) 和评估标准，如准确率( p r e c i s i o n ) 、召回率( r e c a l l ) ，后来被 陆续地引入文本分类中。 1 9 9 2 年l e w i s 发表了他的博士论文r e p r e s e n t a t i o na n dl e a r n i n gi ni n f o r m a t i o n r e t r i e v a l ，文中系统地介绍了文本分类系统实现方法的各个细节，并且在自己建立的 数据集r e u t e r s 2 2 1 7 3 上进行了测试。这篇博士论文成为文本分类领域的经典之作。后 来的研究者在特征降维和分类器的设计方面作了大量的工作。y i m i n gy a n g 对各种特征 选择方法，包括信息增益( i n f o r m a t i o ng a i n ) 、互信息( m u t u a li n f o r m a t i o n ) 、x 2 统计 量等，从实验上进行了分析和比较嵋1 。 她在1 9 9 7 年还对文献上报告的几乎所有的文本 分类方法进行了一次总结，在公开数据集r e u t e r s 2 1 5 7 8 和o h s u m e d 上比较了各个分类 器的性能，对后来的研究起到了重要的参考作用。 1 9 9 5 年，v i p n i k 提出了基于统计理论的支持向量机( s u p p o r tv e c t o rm a c h i n e ) 方 法阳1 ，基本思想是寻找最优的高维分类超平面。支持向量机以成熟的小样本统计理论作 为理论基础，因而在机器学习领域受到广泛的重视。t h o r s t e nj o a c h i m s 第一次将线性 核函数的支持矢量机用于文本分类，与传统的算法相比，支持向量机在分类性能上有了 非常大的提高，并且在不同的数据集上显示了算法的鲁棒性。至今，支持向量机的理论 和应用仍是研究的热点。 2 第一章绪论 在支持向量机出现的同时，1 9 9 5 年及其后，以y o a v f r e u n d 和r o b e r t e s c h a p i r e 发表的关于a d a b o o s t 的论文为标志，机器学习算法的研究出现了另一个高峰。r o b e r t e s c h a p i r e 从理论和试验上给出a d a b o o s t 算法框架的合理性。其后的研究者在这个框 架下给出了许多的类似的b o o s t i n g 算法比较有代表性的有r e a la d a b o o s t ，g e n t l e b o o s t ，l o g i t b o o s t 等。这些b o o s t i n g 算法己被应用到文本分类的研究中，并且取得 和支持向量机一样好的效果。 到2 0 上世纪九十年代，随着网络信息的骤增，大规模的文本分类和检索成为研究 的重点。由于人工智能技术的不断成熟，研究者开始把专家系统技术引入到文本自动分 类领域。专家系统是一种在某特定领域以人类专家的水平去解决该领域问题的计算机程 序，一般由知识库和推理机两大基础部分组成。文本分类系统首先通过在预先分类好的 文本集上训练，建立一个判别规则或分类器，从而对未知类别的新样本进行自动归类。 大量的实验结果表明它的分类精度比得上专家手工分类的结果，并且它的学习不需要专 家干预，能适用于任何领域的学习，使得它成为目前文本分类的主流方法。 国内对文本分类研究比较晚，1 9 8 1 年，侯汉清教授首先探讨和介绍了国外文本分 类的研究情况口1 ，从计算机管理分类表、计算机分类检索、计算机自动分类、机编分类 表等四个方面介绍了国外的发展概况。随后，国内很多学者在这方面进行了比较深入的 研究。 1 9 8 6 年，上海交大电脑应用技术研究所的朱兰娟、王永成等开发的中文科技文献 ( 计算机类) 实验性分类系统。1 9 9 5 年，清华大学电子工程系的吴军研制的汉语语料自 动分类系统，以语料相关系数作为分类依据，以字频、词频及常用搭配为补充，采用停 用词表排除非特征词，进行人工指导分类。1 9 9 8 年，东北大学的计算机系的张月杰、 姚天顺研制的新闻语料汉语文本自动分类模型，通过计算预定义类别和文本特征项之 间相关性来进行自动分类。1 9 9 9 年，邹涛、王继成等开发的中文技术文本分类系统c t d s ( c h i n e s et e c h n i c a ld o c u m e n tc l a s s i f i c a t i o ns y s t e m ) 采用了向量空间模型和基于统 计的特征词提取技术，能够根据文本的具体内容将其分配到一个或多个类别。 相比于英文文本分类，中文文本分类的一个重要的差别在于预处理阶段：中文文 本的读取需要分词，不像英文文本的单词那样有空格来区分。从简单的查词典的方法， 到后来的基于统计语言模型的分词方法，中文分词的技术已趋于成熟。比较有影响力的 当属中国科学院计算所开发的汉语词法分析系统i c t c l a s ，现已公开发布供中文文本分 类的研究使用。 长期以来，没有专门的适合中文文本分类研究的数据集，研究者们大都采用英文语 料库( 如路透社的r e u t e r s 2 1 5 7 8 数据集) ，这使得分类算法难以比较。现在采用较多的 中文测试集有：北京大学建立的人民日报语料库、清华大学建立的现代汉语语料库、复 旦大学李荣陆博士整理的语料库、中科院谭松波博士制作的t a n c o r p v l 0 语料库等。其 实一旦经过预处理将中文文本变成了样本矢量的数据矩阵，那么随后的文本分类过程和 英文文本分类相同，也就是随后的文本分类过程独立于语种。因此，当前的中文文本分 类主要集中在如何利用中文本身的一些特征来更好地表示文本样本。 江南大学硕士学位论文 1 3 本文所做的工作 本文系统而全面的介绍了文本分类的研究现状，研究了文本分类的相关技术，并给 出了一种改进的k n n 文本分类方法，最后设计了一个文本分类系统，并在此系统上进行 了相关实验，具体工作如下： ( 1 ) 理论的研究 文本分类是一个系统的论体系，本文对文本分类的预处理、训练、分类、结果评价 等各个阶段的知识体系进行了系统研究。 文本的预处理主要包括文本分词、去停用词等工作，常用的文本分词方法有：基于 字符串匹配的分词方法、基于理解的分词方法、基于统计的分词方法；去停用词需要有 完善的停用词词典才能达到好的去停用词效果。 训练阶段的主要理论包括：特征选择、特征权重计算，常用的特征选择方法有：文 档频率( d f ) 、互信息( m i ) 、信息增益( i g ) 、x 2 统计( c h i ) ；特征权重有四种计算方法： 布尔权重、t f 权重、i d f 权重、t f i d f 权重，其中t f i d f 权重的加权效果最好。 分类阶段常用的分类算法包括：贝叶斯、支持向量机、关联规则、k n n 、决策树分 类算法、神经网络等，其中以支持向量机和k n n 的分类效果最好。使用最多的文本相似 度计算方法有：欧氏距离、基于向量夹角的余弦等，在文本分类领域，基于向量夹角的 余弦计算相似度的分类效果要好于欧氏距离。 文本分类效果的评价方法有很多，常用的有准确率、召回率、f 1 值三个指标，包括 对分类效果总体评价指标：宏准确率、宏召回率、宏f 1 和对各类分类效果局部评价的 指标：微准确率、微召回率、微f l 值。 ( 2 ) 算法的改进 传统的k n n 算法具有分类精度高、结构简单的优点，但也存在不足：分类时间过长、 每次分类都需训练。针对k n n 算法的缺点，本文提出了一种改进的k n n 分类算法，该算 法基于投影寻踪理论和i d i s t a n c e 降维理论，能够在保证分类精度的同时获得更高的分 类效率。 ( 3 ) 系统的实现 本文在前面理论的基础上，实现了一个文本分类系统，该系统采用c # 语言编写，分 为训练、分类、评价三个模块。实现了两种特征选择方法：文档频率( d f ) 和x 2 统计( c h i ) ； 实现了两种文本分类方法：k n n 和p k n n 。该系统可以对特征选择的维数、k 值等参数进 行随意设置。 训练模块可以对训练文本完成分词、去停用词、特征选择、特征加权、标识训练文 本为向量等操作。 分类模块可以对测试文本完成分词、去停用词、特征加权、标识测试文本为向量、 文本相似度计算等操作。 评价模块可以对分类的结果统计准确率、召回率、f 1 值。 ( 4 ) 相关的实验 在本文实现的文本分类系统的基础上，设计了四个对照试验，分别为：c h i 和d f 4 第一章绪论 分类效果的对照实验；特征维数对分类性能的影响；k 值选取对分类性能的影响；p k n n 和k n n 分类效率、分类准确率对照试验，并对实验结果进行了分析评价。 1 4 本文的组织结构 本文分六章，各章节安排如下： 第一章：分析了当前研究的背景，给出了课题研究的意义，在总结国内外研究现状 的基础上，提出本文的研究方向。 第二章：研究了文本分类所需的关键技术，包括：文本表示方法、中文分词技术、 特征选择方法、特征权重计算等。 第三章：研究文本分类的方法，主要有：朴素贝叶斯算法、k n n ( k 近邻) 分类算法、 支持向量机( v s m ) 、神经网络算法、决策树分类算法，最后给出这几种分类算法的分类 效果的比较研究。 第四章：在k n n 算法的基础上，提出了一种改进的k n n 分类算法一p k n n ，并通过实 验简单对比p k n n 和k n n 算法的效率。 第五章：在前面几章的理论基础上，设计了一个文本分类系统，并详细介绍了该系 统的结构、功能和设计中遇到的问题、及解决方法。 第六章：在第五章实现的系统基础上进行试验，通过设计的几组实验，寻找最适合 k n n 和p k n n 分类的各项参数，深入对比了p k n n 和k n n 算法的效率和准确性。 第七章：总结全文，指出当前研究已取得的成果和存在的不足，并给出未来的研究 方向。 江南大学硕士学位论文 第二章文本分类关键技术研究 文本分类是一项系统的工程，所涉及的技术很多，按流程可以将文本分类分为：文 本预处理阶段、训练阶段、分类阶段、评价四个阶段，其中预处理阶段要文本处理成计 算机能识别的格式，首先对文本进行分词处理，中文文本和英文文本组织形式不同，中 文文本的分词过程比英文分词要复杂得多。分词后文本的特征词非常多，而我们需要的 只是少数有使用价值的特征词，因此分词后的文本要进行特征选择，并将特征选择后的 特征项加权，最后将文本表示成向量空间模型( v s m ) 呻1 ，经过预处理后的文本才能进行分 类。分类算法是文本分类的核心技术，文本分类的方法很多，本章主要介绍有代表性的 几种算法。评估阶段是对文本分类的效果进行评价，常用的指标有：准确率、召回率、 以及综合这两个指标的评价方法一f 1 值等。 2 1 文本表示方法 我们处在一个计算机技术在飞速发展的时代，但计算机还只是一个工具，不能代替 人脑的思维，虽然i b m 制造的超级计算机“深蓝 打败了国际象棋大师卡斯帕罗夫， 但那是因为“深蓝存贮了几乎世界上所有的棋谱，归根到底是人的智慧。同样，在 文本分类领域，计算机还没有达到能直接“读懂”文本的水平，从原理上分析，即使现 在最强大的处理器，读取的也只是o 1 代码，因此要想让计算机处理文本，需要对文本 进行特定的转化。 经过半个世纪的发展，在文本处理领域，研究者提出了一些文本表示模型，主要有： 布尔模型、向量空间模型、概率检索模型、n - g r a m 1 模型等，其中使用最广、效果最好 的是向量空间模型。 2 0 世纪6 0 年代，s a l t o ng 等人提出了向量空间模型，并成功应用于s m a r t 文本检 索系统，其基本思想是：将文本表征成由特征项( 词) 构成的向量空间中的一个点， 仍，彤，服，列，其中形为第j 个特征项的权重，然后通过计算空间两点之间的相 似度来表示两个文本的相关程度，相似度计算一般采用欧氏距离或向量夹角的余弦值。 向量空间模型在实际使用中取得了很好的效果，常用的文本分类算法中，支持向量机、 k 近邻、和n b 都是基于向量空间模型的，向量空间模型包括下面几个概念： 特征项：指出现在文档中并能表示文档特点的基本语言单位，一般可以选择字、词 或词组作为特征项。实验结果显示，选取词作为特征项要优于字和词组，对于一篇含有n 个特征项的文本，可以表示为d 以，t 2 , t s , ，其中1 7 是“的特征项，七尼 特征权重：特征权重是指特征项在文档中的重要程度，对于含有1 1 个特征的文本 d 阮t 2 , t 3 , ，设某一特征项的权重为形，则d 可以表示成刀维向量空间中的一个 抵量d ( ( t l 。w 1 ) 。( t 2 谤2 ) ( t l 骊0 ( t n 碡n ) ) o 文本相似度：文本的相似度表示两个文本的内容相关程度，在向量空间模型中，常 用向量夹角的余弦和欧氏距离表示文本的相似度。 6 第二章文本分类关键技术研究 ( 1 ) 向量夹角的余弦 设文档a 在v s m 空间中的向量形式为a “，x z , ，彬，文档b 在v s m 空间中向量形 式为b 仂，儿，则a ，b 文本的向量夹角的余弦可表示为： c o s ( 1 7 ，6 ) = 疗 x ，y 。 f = l ( 2 1 ) 两个向量夹角的余弦值越大，表示这两个向量相似度越高。 ( 2 ) 欧氏距离 欧式距离是通过空间向量点间的距离表示文本的相关程度，具体形式为： 一 d ( x ，y ) = ( t y ，) 2 ( 2 2 ) yi = i 其中，a ，伍是样本x 和y 的欧式距离，脚是样本属性总数，两个向量点之间的欧 氏距离越小，表示两个向量相似度越高。 在文本分类领域，使用向量夹角余弦计算文本相似度的效果，要好于欧式距离。 2 2 中文分词技术嗍1 1 1 词是文本中最小的具有意义的语言成分，是构造向量空间模型的基础，文本分词的 效果直接影响到文本分类的结果。 在文本的组织上，中文与以英语为代表的欧美语言有着很大的不同，在西方语言中， 词与词是使用空格隔开的，因此不需要进行分词处理，而在中文文本中，字、词是连在 一起的，一个语句就是一连串的字、词组合，词与词之间没有明显界限，因此，分词的 难度较大。常用的分词算法主要有：基于词典的分词方法、基于理解的分词方法、基于 统计的分词方法。 1 、基于词典的分词方法 基于词典的分词方法又叫做机械分词方法，它是按照一定的策略将待切分的字符 串与词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功( 即识别出一个 词) 。按照扫描方向的不同，基于词典的分词方法可以分为正向匹配和逆向匹配；按照 不同长度优先匹配的情况，可以分为最大匹配和最小匹配；按照是否与词性标注过程相 结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法，常用的几种基于词 典分词方法如下：正向最大匹配法( 由左到右的方向) 、逆向最大匹配法( 由右到左的方 向) 、逐词遍历法。 在实际应用中，常常将上述方法结合起来。例如，可以将正向最大匹配方法和逆向 最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆 向最小匹配一般很少使用。般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧 义现象也较少。 7 江南大学硕士学位论文 再一种方法是改进扫描方式，称为特征扫描或标志切分，优先在待分析字符串中识 别和切分出一些带有明显特征的词，以这些词作为断点，可将原字符串分为较小的串再 来进行机械分词，从而减少匹配的错误率。还有一种方法是将分词和词类标注结合起来， 利用丰富的词类信息对分词决策提供帮助，并且在标注过程中又反过来对分词结果进行 检验、调整，从而极大地提高切分的准确率。目前实用的自动分词系统基本上都是以采 用机械分词为主，辅以少量的词法、语法和语义信息的分词系统。该方法的优点是易于 实现，但精度较低，远远不能满足实际的需要。实际使用的分词系统，都是把机械分词 作为一种初分手段，再利用各种其它的语言信息来进一步提高切分的准确率。 2 、基于理解的分词方法 又称人工智能分词法，这种分词方法是通过让计算机模拟人对句子的理解，达到识 别词的效果。其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语 义信息来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控部 分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对 分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语 言知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可 直接读取的形式，因此目前基于理解的分词系统还处在试验阶段。 3 、基于统计的分词方法 基于统计的分词算法的思想是：找出输入字符串的所有可能的切分结果，对每种切 分结果利用能够反映语言特征的统计数据计算它的出现概率，然后从结果中选取概率最 大的一种。 词是稳定的字的组合，因此在上下文中，如果相邻的字共现的次数越多，就越有可 能构成一个词。因此字与字相邻出现的频率或概率能够较好的反映成词的可信度。通过 对语料中相邻共现的各个字的组合频度进行统计，计算它们的互现信息。互现信息体现 了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认为此字组可能 构成了一个词。这种方法只需对语料中的字组频度进行统计，不需要切分词典，因而又 叫做无词典分词法或统计取词方法。 但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是词的常用字 组，并且对常用词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部 基本的分词词典进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计和 串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结 合上下文识别生词、自动消除歧义的优点。 对于任何一个成熟的中文分词系统来说，不可能单独依靠某一种算法来实现，需要 综合不同的算法来处理不同的问题。 2 3 停用词处理技术 经过分词处理的文本，并不是所有的特征都对构造向量空间模型和分类有帮助，相 反，将对文本分类没有帮助的词作为特征项，会对分类的精度造成很大的影响，特别对 第二章文本分类关键技术研究 于使用文档频率( d f ) 进行特征选择的分类方法，影响更大。另外，去停用词可以很大程 度上减小特征项的数量，对文本降维具有很大帮助，所以在构造向量空间模型前，要对 分类无帮助的词进行尽可能彻底的清理。 停用词主要是指文本中存在的助词、副词、连词、代词、介词、叹词、量词、数词 等。例如： 助词中的“的，得，地，吧，呢；副词中的“非常，很，十分，都 ；连词 中的“和，及，或者，又，既 ；代词词中的“我，你，他，大家”；介词中的“把， 从，为了，对于 ；叹词中的“啊，喂，哎呀”；量词中的“只，辆，棵，斤，次 ； 数词中的“一，二，第一，第二，一倍 。 可以看出，在文本中这些词在不同文本中的词频和在同一文本中的词频是非常大 的，如果不除去，会对特征选取造成很大的影响。 去停用词在技术上实现并不复杂，只需建立一个停用词词典，将在分词后每个词与 停用词词典内的词条进行匹配，如果匹配成功，则将该词去掉。值得注意的是，汉语的 词语非常丰富，停用词词典不可能一次构建完善，这需要我们在平时的研究中进行积累， 一个有效的方法是：使用一个容量较大的测试文本库，对这个文本库中的词的词频进行 统计，然后输出到文本，排在词序列最前面的词往往是对文本分类无帮助的词，具体的 分辨需要我们人为判断决定，然后我们将这些对分类无助的特征词添加到停用词词典 中。 对词频进行统计的技术涉及到2 4 节中的文档频率( d f ) 技术 2 4 特征选择方法1 2 1 n 3 1 在经过文本分类系统的分词、去停用词处理后，文本的特征维数仍然很高，这里所 指的特征维数是指要构造v s m 空间的所有文本的特征之和，一个文本集合很可能包含十 几万个特征词，而每篇文本包含的特征词却很少，这样构造的向量空间模型是一个高维 的稀疏矩阵，会对分类算法的时间复杂度和空间复杂度造成很大的影响。实验显示，当 向量空间的特征维度达到一定值时就可以实现很高的分类性能，随着特征维度的增加， 分类性能反而会下降。因此，必须对特征项进行有效的筛选。 常用的文本特征选择方法有：文档频率( d f ) 、信息增益( i g ) 、互信息( m i ) 、x 2 统计 量( c h i ) 、期望交叉熵等，这些方法的基本思想都是对每一个特征( 在这里是中文词) ， 计算某种统计度量值，然后设定一个阈值t ，把度量值小于t 的那些特征过滤掉，剩下 的即认为是有效特征。 2 4 1 文档频率 词条的文档频率( d o c u m e n tf r e q u e n c y ) 是指在训练语料中出现该词条的文档数。基 于文档频率抽取特征词的思想是：d f 值低于某个阈值的词条是低频词，它们不含或含有 较少的类别信息。将这样的词条从原始特征空间中移除，不但能够降低特征空间的维数， 而且还有可能提高分类的精度。d f 高于某个阈值的词为中、高频词，这些词被认为对分 类的影响较大，应该保留。 9 江南大学硕士学位论文 文档频率是最简单的特征抽取技术，由于其具有相对于训练语料规模的线性计算复 杂度，它能够容易地被用于大规模语料统计。但是在信息抽取研究中却通常认为d f 值 低的词条相对于d f 值高的词条具有较多的信息量，应该将它们完全移除。实验证明：在 英文环境中，当i g 和c h i 等统计方法的计算的复杂度太高时，d f 可以代替它们被使用。 2 4 2 互信息 互信息( m u t u a li n f o r m a t i o n ) 在统计语言模型中被广泛采用。如果用a 表示包含词 条t 且属于类别c 的文档频数，曰为包含于但是不属于c 的文档频数，f 表示属于c 但 是不包含方的文档频数，表示语料中文档总数，芒和c 的互信息可由下式计算： m i ( t , c ) l o g 两而a xn ( 2 3 ) 如果f 和c 无关( 即p 以= p 俐x p 俐) ，亿值自然为零。为了将互信息应 用于多个类别，与c h i 统计的处理类似，由下式计算芒对于c 的互信息： m i ( t ) = m a x 7 ：li ( t , c i m a x ) ( 2 4 ) = l 其中历为类别数，将低于特定阈值的词条从原始特征空间中移除，降低特征空间的 维数，保留高于阈值的词条。 2 4 3 信息增益 信息增益( i n f o r m a t i o ng a i n ) 表示文档包含某一特征时文档类的平均信息量，定义 为某一特征在文档中出现前后的信息熵之差。假定c 为文本类变量，f 为文本类的集合， d 为文本，为特征。对于特征，其信息增益记为i g ( f ) ，计算公式如下： i g ( f ) = ( c ) 一h ( ci 力 = 一p ( c ) l o g ( p ( c ) ) + p ( 厂) p ( c if ) l o g ( p ( c f ) ) + p ( 7 ) p ( vl7 ) l o g ( p ( c7 ) ) 2 驴c 舢g ( 怒m - ) l o g ( 揣) ) ( 2 5 ) 只考虑单个类的时候有： g ( c , 舻w ) l o g ( 揣m 厕l o g ( 嵩舄 ( 2 6 ) 2 4 4x 2 统计( c h i ) c h i 统计方法度量词条手和文档类别c 之间的相关程度，并假设t 和c 之间符合具 有一阶自由度的x ? 分布。词条对于某类的x 2 统计值越高，它与该类之间的相关性越大， 携带的类别信息也较多。令表示训练语料中的文档总数，c 为某一特定类别，芒表示 特定的词条，彳表示属于c 类且包含芒的文档频数，曰表示不属于c 类但包含芒的文档 频数，f 表示属于c 类但不包含芒的文档频数，刃是既不属于c 也不包含芒的文档频数。 i o 第二章文本分类关键技术研究 则芒对于c 的c h i 值由下式计算： x 2 ( f ，c ) = 面丽n i x ( a 丽d - 而c d ) j 2 i 而 ( 2 7 ) 对于多类问题，分别计算芒对于每个类别的c h i 值，可以用下面的两种标准计算t 对整个训练集的c h i 值： x 一2 ( f ) = m a x j 竺lx 2 ( ，q ) ( 2 8 ) x 嘴2 ( f ) = ：。l p ( c j ) x 2 ( f ，q ) ( 2 9 ) 其中皿为类别数。从原始特征空间中移除低于特定阈值的词条，保留高于该阈值的 词条作为文档表示的特征。 2 5 特征权重计算方法n 铂 2 5 1 布尔权重 布尔权重也被称作均权，布尔权重是最简单的一种赋权方法，这种方法将所有特征 同等看待，既不突出又不抑制任何一个特征。特征项的权值或者等于1 ，或者等于0 ， 计算公式为： 彬= 器品二： 亿 其中w i 为特征项i 的权重，t f 为特征项i 出现的次数。这种方法的缺点是无法体 现一个词在文本中的重要程度。 2 5 2t f 权重 t f 权重( t e r mf r e q u e n c y ) 又称词频权重，或称特征项频率。不同类别的文档，在特 征项的出现频率上有很大差异，因此特征项频率信息是文本分类的重要参考之一，一般 较大的特征项在该类文档中具有较高的权重。它的计算公式为： 既= 巩= 第k 个特征词在第j 篇文本中出现的次数 ( 2 1 1 ) 实际应用中各类别文本的长度很难一致，各类文本包含的字数、词数可能差别会很 大，这对词频会造成直接影响，因此通常对词频作归一化处理。另外，如果特征选择后 的特征项中含有较多的非名词( 如代词、数词、连词) ，而这些词出现的概率非常高，如 果使用t f 权重加权，会赋值给这些词较高的权重，这势必对分类结果产生不利影响， 因此，t f 权重对去停用词的效果具有较强依赖性。 2 5 3i d f 权重 i d f 权重( i n v e r s ed o c u m e n tf r e q u e n c y 反比文档频率) ：i d f 越大，此特征项在文 档中的的分布越集中，说明它在区分该文档内容属性方面的能力越强。反文档频率是特 征项在文档集分布情况的量化。该方法以出现特征词的文本数为参数构建的函数代表特 江南大学硕士学位论文 征项的权重。这体现了信息论中集中度的思想，具有一定的合理性，但忽略了分散度和 频度两个因素，因此具有片面性，公式如下： w 。k = l 0 9 2c 南川靠糕器， 亿 2 5 4t f i d f 权重 t f i d f ( t e r mf r e q u e n c y i n v e r s ed o c u m e n tf r e q u e n c y ) 是由是由s a l t o n 在1 9 8 8 年 提出的，t f i d f 权重综合考虑了t f 权重和i f d 权重的优点和不足，是目前加权效果最好 的权重计算方法，广泛应用于文本处理领域。其基本思想是：如果特征项以在一类文档 的出现的次数越多，而在整个文档集中出现的频率越