（计算机应用技术专业论文）基于支持向量机的文本分类研究(1).pdf

哈尔滨 ：稃大学硕十学何论文 摘要 文本分类是基于内容的信息自动分类的核心技术，它是由计算机自动判 别文本分类的过程。文本分类具有文本向量稀疏性大、维数高、特征之间有 较大的相关性的特点。正是由于文本分类有样本多，噪音多等特点，支持向 量机在分类时候速度慢，分类的准确度不高。 本文针对以上问题，研究分析了文本分类器的特征提取和选择及改进支 持向量机的方法的关键技术。给出基于概率类别的特征选择的一种新方法， 该方法解决了文本的传统特征选择并不按类别计算统计值，而是选出的是那 些全局意义上的“强类别意义”的词，而这些词可能有着多类的指示意义的 缺点。在文本模型表示部分，采用了向量空间模型，结合特征选择来计算权 重。在支持向量机的改进分类算法中，采用聚类算法对先i j 的样本点做处理， 增加选中支持向量的准确度，加快了分类速度，提高了分类效果。 关键词：数据挖掘；文本分类；特征选择；向量空间模型；支持向量机 哈尔滨r ：稗人学硕十学位论文 a b s t r a c t t e x tc l a s s f i c a t i o ni st h ek e yt e c h n o l o g yo fi n f o r m a t i o na u t o c l a s s f i c a t i o n b a s e do nc o n t e n t i ti st h ep r o c e s st h a tt e x tc a t e g o r i e sa r ec l a s s i f i e da u t o m a t i c a l l y b yc o m p u t e r t h e r ea r em a n yf e a t u r e sa b o u tt e x tc l a s s f i c a t i o n ：w i d es p a r eo ft e x t v e c t o r , h i g hd i m e n s i o n ，c o m p a r a t i v e l yr e l a t i o na m o n gf e a t u r e s a st h e r ea r em o r e t e x tc a t e g o r i e s ，s a m p l e s ，n o i s e s ，t h ec l a s s f i e ri ss l o w e di ns p e e d ，n o tw e l li nt h e r e s u l t s t h ee x t r a c t i o na n ds e l e c t i o no ff e a t u r ea n dt h ec r i t i c a lt e c h i n q u eo fi m p r o v e d s u p p o r tv e c t o rm a c h i n ea r er e s e a r c h e di n t h i st h e s i s i nf e a t u r es e l e c t i o n ，n e w f e a t u r es e l e c t i o nm e t h o dw h i c hi sb a s e dc l a s s i c a t i o ni s p r o p s e d i nc l a s s i c a l f e a t u r es e l e c t i o nm e t h o d ，t h es t a t i s t i cd a t aa r en o t c o m p u t e da c c o r d i n g t o c a t e g o r i e s t h eg l o b a lm e a n i n gw o r d sa r es e l e c t e d h o w e v e r , t h ed i s a d v a n t a g ei s s o l v e di nt h en e wm e t h o d i nt e x tm o d e lr e p r e n t a t i o n ，v e c t o rs p a c em o d e la r eu s e d f e a t u r es e l e c t i o ni sa l s ou s e df o rd e c i d i n gt h e w e i g h t i nt h ei m p r o v e ds u p p o r t v e c t o rm a c h i n ec l a s s f i e dm e t h o d ，c l u s t e rm e t h o di su s e df o rh a n d l i n gt h es a m p l e p o i n tf i r s t l y ，a c c e r l a t e dt h es p e e do fc l a s s i f c a t i o n ，i m p r o v e dt h er e s u l t s k e y w o r d s ：d a t am i n i n g ；t e x tc l a s s f i c a t i o n ；f e a t u r es e l e c t i o n ；v e c t o rs p a c em o d e l ： s u p p o r tv e c t o rm a c h i n e 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ： 日期：铆8 年f 月c 9 - o 日 哈尔滨。翠人学硕十学位论文 第1 章绪论 1 1 课题的研究背景及意义 随着信息时代的来临，为了从海量的信息中迅速查找需要的信息，就需 要对信息进行分类。传统的做法是对信息进行人工分类，并加以组织和整理， 为人们提供一种相对有效的信息获取手段。但是，这种传统的人工分类的做 法存在着许多弊端：一是耗费大量的人力，物力和精力；二是存在分类结果一 致性不高的问题。这就要求我们探索文本自动分类的有效方法，提高分类效 率。只有这样才能保证检索的查全率和查准率都得到提高m ，。 文本自动分类是信息检索技术和人工智能技术相结合的研究领域，是进 行基于内容的自动信息管理的核心技术协n 。文本自动分类是根据一些己经分 配好类别标签( 这些类别标签预先定义好) 的训练文档集合，来对新文档分配 类标签，其目的就是对文本集进行合理处理和组织，使得这些文本能够按照 类别区分丌来。 文本分类的目标是在分析文本内容的基础上，给文本分配一个或多个比 较合适的类别，从而提高文本检索等应用的处理效率。另外，文本分类可以 应用到垃圾邮件的判定，新闻出版按照栏目分类。在文本分类的基础上，可以 更好地进行信息的检索和信息的个性化服务。自动文本分类对大量用自然 语言写成的文本按照预先定义的主题类别进行自动分类，它是人工智能技术 和信息获取技术相结合的研究领域，是进行基于内容的自动信息管理的核心 技术。它是机器学习的重要应用，现有机器学习方法共同的重要理论基础之 一是统计学。传统统计学研究的是样本数目趋于无穷大时的渐近理论，但在 实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习方法在实 际中的表现却可能不尽人意。 v a p n i k 等人从二十世纪六、七十年代开始致力于统计学习理论( s t a t i s t i c a l l e a r n i n g t h e o r y , s l t ) 的研究，随着其理论的不断发展和成熟，也由于神经网 哈尔滨。i ：科人学硕十学何论文 络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广泛 的重视。支持向量机( s u p p o r tv e c t o rm a c h i n e s ，s v m s ) 是二十世纪九十年代中 期在统计学习理论基础上发展起来的一种新型机器学习方法。支持向量机采 用结构风险最小化准贝j j ( s 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 ) ：) j i 练学习机器，其 主要优点是将学习问题归结为一个凸二次规划问题。从理论上说，得到的将 是全局最优解，解决了在神经网络方法中无法避免的局部极值问题，通过非 线性变换将数据映射到高维特征空间，使数据在高维空间中可以用线性判别 函数分类，巧妙地解决了维数问题，算法复杂度与样本维数无关。支持向量 机建立在严格的理论基础之上，较好地解决了非线性、高维数、局部极小点 等问题，成为继神经网络研究之后机器学习领域新的研究热点。 1 2 国内外研究现状 国外文本自动分类研究开始于2 0 世纪5 0 年代术，h ek u h n 在这一领 域进行了丌创性的研究，他首先将词频统计的思想用于文本分类中。1 9 6 0 年 m o 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 a l ”。19 6 2 年博科( h b o r k ) 等人提出了利用因子分析法进行文献的自动分类。其后许多学者在这一领域 进行了卓有成效的研究。国外的自动分类研究大体上可以分为三个阶段：第 一阶段( 1 9 5 8 年1 9 6 4 年) 主要进行自动分类的可行性研究；第二阶段( 1 9 6 5 年 1 9 7 4 年) ，自动分类的实验研究；第三阶段( 1 9 7 4 年至今) ，自动分类的实用 化阶段。己在邮件分类、电子会议、信息过滤等方面取得了较为广泛的应用， 其中较为成功的系统有麻省理工学院为白宫开发的邮件分类系统、卡内基集 团为路透社开发的c o n s t r u e 系统等m ，。 国外当前流行的文本分类方法有r o c c h i o 法及其变异方法、k 近邻法、 决策树、朴素贝叶斯、贝叶斯网络、支持向量机等方法。这些方法在英文以 及欧洲语种文本自动分类上有广泛的研究，而且很多研究表明k n n 和s v m 是英文文本分类的最好方法。国外很多研究人员对英文文本分类领域的各个 问题都有相当深入的研究，对几种流行的方法进行了大量的对比研究。 1 9 8 2 年，v a p n i k 提出了具有划时代意义的结构风险最小化原理，堪称支 2 哈尔滨i - f it 人学硕十学何论文 持向量机算法的基石：1 9 9 2 年，b o s e r 和v a p n i k 提出了最优边界分类器；1 9 9 5 年，c o m e s ，v a p n i k 等完整地提出了支持向量机分类器；1 9 9 7 年，v a p n i k 、 g o o d i s h 和s m o l a 介绍了基于支持向量机方法的回归算法和信号处理算法。 自此之后，支持向量机算法的优良性质和潜在的应用价值吸引了国内外 众多学者的注意：如s m o l a 分析了正则化算子同支持向量机的关系，指出支 持向量机就是最小化f 则风险的正则化网络，证明了正则化算子的格林函数 是合适的支持向量核，这个核具有等价的正则化属性，而且用正则化的观点 分析了当前所使用的支持向量机核函数；w i l l i a m s o n 等对于核函数的泛化误 差给出了一个更紧的界。随着支持向量机理论上的深入研究，出现了许多变 形支持向量机：如s c h o l k o p f 对分类和回归问题提出的v s v m 算法；s u y k e n s 提出的最小二乘支持向量机；m a n g a s a r i a n 等人提出的广义支持向量机”“。 近几年，支持向量机实现了有效的机器学习方法。目前，s v m 算法在模 式识别、回归估计、概率密度函数估计等方面都有应用。例如，在模式识别 方面，对于手写数字识别、语音识别、人脸图像识别、文章分类等问题，s v m 算法在精度上已经超过传统的学习算法或与之不相上下。 国内自动分类研究起步较晚，始于2 0 世纪8 0 年代初期。国内的研究者 在英文文本分类研究的基础上采取相应策略，结合中文文本的特定知识，然 后应用于中文之上，继而形成中文文本自动分类研究体系。到目前为止，我 国陆续研制出一批计算机辅助分类系统和自动分类系统。例如中国科学院、 清华大学、北京大学、北京信息工程学院、上海交通大学、复旦大学、东北 大学、山西大学、同济大学、南京大学、浙江大学以及西安电子科技大学等 单位都有相应的研究成果，也研制出了不少的实验系统。这其中有基于人工 智能技术的分类系统，有基于统计学技术的分类系统，还有基于模糊技术的 分类系统，近几年基于统计知识的分类方法占主流，也不乏有基于规则的分 类方法。 国内许多学者也对支持向量机的推广和发展作出了许多贡献，如张学工 在文中介绍了统计学习理论与支持向量机，并于2 0 0 0 年翻译出版了v a p n i k 的 ：许建华，张学工2 0 0 4 年翻 译出版了v a p n i k ；邓乃扬、f f i 英杰出版了 ；李国正，王猛等翻译了c r i s t i a n i n i 等的 3 哈尔滨+ l ：稃人学硕+ 学位论文 ( ( a ni n t r o d u c t i o nt os u p p o r tv e c t o rm a c h i n e sa n do t h e rk e r n e l - b a s e dl e a r n i n g m e t h o d ) ) ；张铃研究了支持向量机理论与神经网络规划算法的关系；卢增祥、 李衍达提出了交互支持向量机学习算法；f r 盛丰、黄厚宽研究了回归型支持 向量机简化算法；张文生、王珠等提出了在支持向量机中引入后验概率的方 法以及基于邻域原理计算海量数据的支持向量机算法：孙剑，郑南宁等提出 了一种改进的s m o 算法；周水生，周利华等提出了训练支持向量机的低维 n e w t o n 算法；李建民，张拔等提出了序贯最小优化的改进算法；郭崇慧、孙 建涛等提出了广义支持向量机优化问题的极大嫡方法。国内外学者的积极研 究极大地推进了支持向量机的快速发展。目前，支持向量机方法应用于模式 分类，工业控制等诸多领域。 1 3 研究中存在的问题 支持向量机从被广泛重视到现在只有几年的时间，其中还存在很多尚未 解决或尚未充分解决的问题，需要进一步完善和改进以适应实际应用的需要。 面对文本分类具有类别和样本数目多、噪音多等特点，支持向量机在应用过 程中存在以下问题： ( 1 ) 文本分类的训练集提供的信息可能存在大量的无效特征或冗余特 征，这极大地影响了分类器对该数据集的学习，使得分类器精度、速度和可 理解性下降。所以，需要特征选择可以去除冗余特征及无效特征，使得数据 集比较纯净，特征的选择变得非常重要。 ( 2 ) 一般情况下，文本分类问题的样本数目越多，支持向量机的分类速 度越慢。对于训练样本数目多的分类问题，支持向量机的分类速度过慢，这 一点限制了支持向量机的应用，成为支持向量机方法进入大规模实用化阶段 的瓶颈。 1 4 研究内容及论文结构 本文针对研究中所存在问题，研究分析了文本分类器的特征选择及改进 支持向量机的方法的关键技术。 4 哈尔滨+ i ：稃人学硕十学位论文 ( 1 ) 在特征选择部分，结合基于文档频率，熵，信息增益以及互信息等 几种不同的特征选择方法，通过比较与综合，提出在本文的系统中特征选择 的一种新方法。 目前本文进行该项研究的着眼点主要放在选择优化特征集合所需要的两 个主要步骤上。确定关键的变量，即优化的特征子集。首先必须确定进行搜 索所需要的策略；其次，必须确定一些评价准则，根据这些准则来评价所选 择的特征子集的好坏程度。 ( 2 ) 在支持向量机的改进分类算法中，采用聚类算法对先前的样本点结合 支持向量机做处理，增加选中支持向量的准确度，提高分类效果。 标准支持向量机的数学模型是一个二次规划问题，有许多传统的解法如 积极集法、对偶方法、内点算法等，但大规模样本会占用大量的内存，计算 时间也很长。所以，关于支持向量机训练算法的研究一直是支持向量机研究 的重要内容，已经出现了一些比较有效的训练算法和实用软件。由于标准支 持向量机的数学模型是一个二次规划问题，使得对于大规模样本问题，它的 训练速度较慢。总体来说，本文的研究主要从解决支持向量机训练速度慢的 问题：在分解、分块算法之前，通过数据聚类的数据预处理等方法减少训练 样本集的规模，提高支持向量机的训练速度。 本文的具体组织安排如下： 第1 章简要介绍了国内外文本分类技术的研究现状和支持向量机在文本 分类中存在的主要问题。 第2 章论述了文本分类中的关键技术和文本表示模型。 第3 章是对基于向量空间模型的文本特征选择作了详细介绍，提出基于 概率类别的特征选择的新方法，这是本文的创新点和主要贡献之一。 第4 章是对基于统计学习理论的支持向量机算法作了详细介绍，提出基 于聚类的约简支持向量机算法，这也是本文的重要创新点。 第5 章结合改进的算法设计了一个文本的实验分类系统，取得了较好的 分类效果，在一定程度上解决了基于s v m 的大规模文本分类的瓶颈问题。 哈尔滨+ 1 j 科人学硕十学何论文 第2 章相关技术 一个完整的文本分类过程主要包括以下几部分：首先是预处理，根据采 用的分类模型将文档集表示成易于计算机处理的形式；其次是特征提取以及 权重计算，选择合适的特征，给每个特征赋予一定的权重表示文档中各特征 的重要性；再次是根据预处理后的训练集学习建模，构建出分类器。其中关 键技术是分词技术、特征选择、赋权以及分类器构造。本章介绍了分类中涉 及的技术，并分析各个方法的优缺点。 2 。1 分词技术 自动分词是针对中文的一种自然语言处理技术，中文同英文等西方语言 的主要不同点是，句子中各个词条间没有固有的分隔，为了对文本信息进行 分类、索引等处理，首先需要对中文文本进行词条切分( 简称分词) 。中文文 本的分词处理就是指在中文文本中连续的能够代表语义单元的词之问加入分 隔符，将中文文本中连续的汉字流形式转化为离散单词流形式的过程。自动 分词技术是各种中文信息处理技术的基础，也是中西文之间研究，文本自动 分类的主要差异所在，中文文本i t 动分类要在自动分词的基础上进行，对中 文文本进行分词的过程也是文本特征集的确定过程。 从现阶段的实际情况来看，英文已经跨越了分词这一步，也就是说在词 的利用上已经先我们一步，并且已经展现了良好的应用前景，无论是信息检 索还是主题分析的研究都要强于中文，究其根本原因就是中文要通过分词这 道难关，只有攻破了这道难关，我们才有希望赶上并超过英文在信息领域的 发展，所以中文分词对我们来说意义重大，可以说直接影 l i l ! f i 使用中文的每 个人的方方面面。 如果中文信息不采用分词技术，那么整理的结果就过于粗糙，而导致资 源的不可用n 1 。例如：“制造业和服务业是两个不同的行业”和“我们出口日本 的和服比去年有所增长”中都有“和服”，而被当作同一类来处理，结果足检索 6 哈尔滨i ：科人学硕十。孚：何论文 “和服”的相关信息，会将他们都检索到，在信息量少的情况下，似乎还能够 忍受，如果是海量信息，这样的结果就会令人讨厌了。通过引入分词技术， 就可以使机器对海量信息的整理更准确更合理，在“制造业和服务业是两个不 同的行业”中“和服”不会被当做一个词来处理，那么检索“和服”当然不会将它 检索到，使得分类结果更准确，效率也会大幅度的提高。 2 1 1 汉语自动分词的难点 汉语文本是大字符集上的连续字符串，把字符串分隔成词串，就是自动 分词系统需要做的工作。在过去的2 0 多年里，汉语自动分词工作虽然也取 得了很大成绩，但无论按照人的智力标准，还是同实用的需求相比较，差距 还很大。通过研究分析，汉语自动分词过程中的主要困难有以下几个方面。 1 分词规范的问题 在汉语中什么是词，到现在并无公认的定义。甚至有人提出，在汉语中 没有词只有短语。汉语自动分词的首要任务是确定分词规范。书面汉语是字 的序列，词之间没有间隔标记，使得词的界定缺乏自然标准，而分词结果是 否f 确需要有一个通用、权威的分词标准来衡量。分词标准的问题实际上是 汉语词与语素、词与词组的界定问题，这是汉语语法的一个基本、长期的问 题。 2 分词算法中存在的问题 ( 1 ) 歧义切分。所谓歧义就是指对一个句子( 或一个字符串) ，若仅根 据句子中的字的字面意义理解，可以有多种理解方式。对汉语切分会产生切 分歧义。歧义切分是影响分词系统切分正确率的重要因素，也是分词阶段最 困难的问题之一。典型的歧义有交集型歧义和组合型歧义。所谓交集型歧义 就是指字符a b c ( a 、b 、c 为汉字符串) 中，若存在a b ，b c 同时为词， 则称此切分为交集型歧义切分。例如字段“美国会”，既可以理解为“美国”， “会”，又可以理解为“美”，“国会”，这属于交集型歧义字段。如果在 字段a b 中，a ，b ，a b 分别都是词表中的词，则称a b 为组合歧义字段。 7 哈尔滨t 稃人学硕十学何论文 i i 例如“十分”，“马上”，“你好”等都是组合型歧义字段。切分歧义是基 于字典的分词算法无法避免的问题。目前使用的解决歧义的策略主要有： 基于规则，即利用语法语义知识进行歧义切分。基于统计，即利用基于统 计的分词方法自动排歧的特点，采用词频、马尔可夫模型等语料库统计知识 进行歧义切分。基于规则与基于统计相结合。 ( 2 ) 未登录词识别。汉语分词问题中的歧义切分固然困难，但是未登录 词问题可能比上述分词的问题更严重。许多分词算法都是在完备词表的假设 下设计的，其实这一假设并不成立。汉语和其它自然语言一样，它的实词部 分永远是一个开放集，因为社会上的新词不断涌现，而且专有名词虽然不新， 但不可能尽收，如人名、地名、机构名、译名等等。未登录词引入的分词错 误远远超过歧义切分字段引发的错误，因此近年来这个问题己成为自动分词 研究的焦点。 ( 3 ) 分词与理解的先后。即使汉语有了一个公认的词表，计算机分词仍 然面临知识短缺的大问题。从作者自身的体验来看，人在阅读汉语文章时， 大体上是先理解后分词，或至少是边理解边分词。而计算机无法像人在阅读 汉语文章时那样边理解边分词，而只能是先分词后理解，因为计算机理解文 本的f j 提是识别出词、获得词的各项信息。这就是逻辑上的两难：分词要以 理解为自 提，而理解又是以分词为前提。由于计算机只能在对输入文本尚无 理解的条件下进行分词，所以任何分词系统都不可能企求百分之百的切分f 确率。总之，汉语自动分词是中文信息处理的“瓶颈”问题，它的最终解决 依赖于汉语的分词算法、句法结构、语义等语言知识的深入系统的研究，依 赖于对语言与思维的本质的揭示。同时，在很大程度上还依赖于神经网络、 专家系统、知识发现等人工智能技术的研究进展。 2 1 2 汉语分词方法 自2 0 世纪8 0 年代初期，出现了许多分词方法。分词算法的优劣直接影 响切分的准确性，同时在切分阶段必须解决两大难点：歧义现象排除和新词 8 哈尔滨l ：科人学硕十学位论文 识别。对于汉语分词算法研究，自订人做了很多工作，己经给出了许多经典的 算法。概括起来这些算法大致可以分成基于规则的方法，基于统计的方法， 以及两者结合的方法。根据有无分词词典分为有词典分词和无词典分词。 1 基于规则的方法 基于规则的方法一般都需要事先有人工建立好的分词词典和分词规则 库。最基本的基于规则的分词算法是字符串匹配法。这种方法，按扫描方向 可以分为正向扫描、逆向扫描两种；按匹配原则可分为最大匹配和最小匹配。 主要有j 下向最大匹配法、逆向最大匹配法、双向匹配法、逐词遍历匹配法、 设立切分标志法、正向最佳匹配法和逆向最佳匹配法等于如果分词词典规模 小，覆盖程度有限，则会影响分词的正确率。以j 下向最大匹配为例，其算法 如下：在计算机中存放一个已知的词表，从被切分的语料中，按正方向顺序 截取一个定长的字符串，这个字符串的长度，叫做最大词长。把这个具有最 大词长的字符串与词表中的词相匹配，若匹配成功，则可确定这个字符串为 词，计算机程序的指针向后移动匹配成功串长度个字符，继续进行匹配；否 则，则把该字符串长度减一，再与词表中的词进行匹配，直至成功为止。 ( 1 ) f 向最大匹配法。这是最早提出的自动分词方法，由苏联学者在六 十年代研究汉俄机器翻译时提出，它的基本思想是先取一句话的前六个字查 词典，若不是一个词，则删除六个字中的最后一个，然后再查词典，这样一 直查下去直到找到一词为止，对句子剩余部分重复此工作，直到把所有词分 出为止。所谓最大匹配，就是尽可能地用最长的词来匹配句中的汉字符串， 例如，“社会主义”和“社会”都是词，但当我们在句中遇到“社会主义 这个汉字符串时，就用“社会主义”这个词去匹配它，使得切分出来的词尽 可能长，切出来的词的数量尽可能少。 从待切分语料中按f 向取长度为m a x l e n 的字符串s t r ，令 l e n = m e x l e n ； 把s t r 与d 中的词相匹配； 9 哈尔滨1 ：程人学硕+ 学位论文 若匹配成功，则认为该字符串为词，指向待切分语料的指针向前移 l e n 个汉字，返回到； 若匹配不成功，如果l e n 1 ，则把l e n 减1 ，从待切分语料中取 长度为l e n 的字符串s t r ，返回到。否则，得到长度为1 的单字 词，指向待切分语料的指针向前移动1 个汉字，返回到。 m m 法的的原理简单，易于实现，时间复杂度也比较低。但是，最大词长 的长度比较难于确定，如果定得太长，则匹配时花费的时间就多，算法的时 间复杂度明显提高，如果定得太短，则不能切分长度超过它的词，导致切分 正确率的降低。据统计表明，m m 方法的错误切分率为1 1 6 9 。所以，该方 法一般不单独使用，而是作为一种基本的方法和其它方法配合使用。 ( 2 ) 逆向最大匹配法。这种方法和正向最大匹配法思想一样，不同之处 在于它是从句子的最后六个字丌始切分，每次匹配不成功时，去掉汉字符串 前面的一个字。反向最大匹配法对交集型歧义字段处理精度比f 向最大匹配 法略高。这两种方法思想明了，易于机器实现。但由于试图利用相对稳定的 词表来代替灵活多变、充满活力的词汇，把词表作为判词的唯一标准，因而 具有很大主观性和局限性。另外m m ，r m m 实际否认了“词中含词”这一语 言现象。因而出错率高，拒分现象严重，而且这两种方法的时间复杂度很高。 r m m 方法的原理同m m 法基本相同，只不过扫描方向为从右到左。该方法一 般也不单独使用，提出r m m 方法的意义更在于同m m 方法进行结合运用，即 双向匹配法对字符串进行更准确的切分。 ( 3 ) 双向匹配法。这种方法基本原理是分别用删法和r m m 法进行正向 和逆向的扫描和初步的切分，并将用m m 法初步切分的结果与用r m m 法初步 切分的结果进行比较，如果两种结果一致，则判定切分正确；如果两种结果 不一致，则判定为疑点，采用其它手段选取一种切分。它的侧重点是放在检 错和纠错上，该方法对于正、逆向的扫描结果一致但实际切分不f 确的字段 ( 如“结合成分子时”) 仍然不能正确处理。由于要做双向扫描，时间复杂 1 0 哈尔滨r ：w - 火学硕十学位论文 度增加。而且，其分词词库必须同时支持正、逆两种顺序的检索，词库的结 构比一般的分词词库要复杂得多。 双向匹配法克服了脚方法的一些缺点。例如，使用双向匹配法对“负 责任的态度”进行切分时分别使用的m m 方法和r m m 方法得到的两个切分结 果是负责任的态度 和“负责任的态度”，这是切分系统将会 进一步的排歧，从而得到最终的正确结果。 ( 4 ) 最佳匹配法。最佳匹配法( 包括正向和反向) 实际上可以归并到正 向最大匹配法和反向最大匹配法，因为它与上述两类方法的区别仅仅是对词 典中的词序作了适当的调整( 按词频排序) ，以求缩短对分词词典的检索时 间，以降低分词时间复杂度，加快分词速度。最佳匹配法的原理是：在词库 中按词的出现频率大小排列词条，高频率的词排在前，低频率的词排在后， 从而缩短分词词库的检索时间，达到最佳效果，降低分词的时间复杂度，加 快分词速度。0 m 法只是预先处理分词词库的排列顺序，它虽然降低了分词的 时间复杂度，但是并没有提高分词精度。实际上，这是对分词词典的一种预 加工，也不是纯粹意义上的一种分词方法。 2 基于统计的分词方法 从形式上看，词是稳定的字的组合，所以在上下文中，相邻的字同时出 现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率 能够较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合频度 进行统计，计算它们的互现信息。定义两个字的互现信息，计算两个汉字x ， y 的相邻共现概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密 程度高于某一个阀值时，便可认为此字组可能构成了一个词。这种方法只需 对语料中的字组频度进行统计，不需要切分词典，因而又叫做无词典分词方 法或统计取词方法。 3 基于词典的分词方法 哈尔滨一l i 科人学硕十学何论文 这一类型的分词方法最早是由苏联专家在5 0 年代木提出的，因为它们 都是使用机器词典作为分词依据的，故称为基于词典的分词，又叫做机械分 词方法。基本思想是基于字符串匹配的机械分词：按照一定的策略将待分析 的汉字符串与一个“充分大的 机器词典中的词条进行匹配，若在词典中找 到某个字符串，则匹配成功( 识别出一个词) 。按照扫描方向的不同，串匹 配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况， 可以分为最大( 最长) 匹配和最小( 最短) 匹配；按照是否与词性标注过程 相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。还可 以将上述各种方法相互组合。例如，可以将正向最大匹配方法和逆向最大匹 配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配 和逆向最小匹配一般很少使用。由于自然语言的复杂性，该类分词算法会出 现分词歧义( 即对同一段汉字符串分词会出现不同的划分结果) ，需要利用 各种语言信息进行歧义校正。因此，基于词典的分词方法的模式为：机械分 词+ 歧义校正。 2 1 3 分词系统的性能评价 汉语自动分词系统的总目标是建立个开放的，具有较高通用性和实用 性的现代书面汉语自动分词系统。评价一个分词系统的性能优劣主要看两个 方面：分词精度和分词速度。分词精度也称分词准确率，是分词系统性能的 核心指标。评价汉语自动分词的性能主要有如下三个指标：口和。其中， 口指的是分词的准确率；指的是分词的召回率；用公式可形式化为如下所 示。 准确率口= 正确的切分结果数所有的切分结果数x1 0 0 召回率= j 下确的切分结果数标准答案中的切分结果数x1 0 0 分词速度是分词系统性能的另外一个重要指标。影响分词速度的主要因 素是分词词典的组织结构。分词词典的查询速度依赖于词典的组织结构。由 1 2 哈尔滨。l ：稃人学硕十学位论文 于自动分词需要的各类知识都要从分词词典中获取，系统在进行分词处理时 需要频繁查询分词词典，分词词典的查询速度将直接影响分词系统的速度。 在不同的应用中，对分词系统性能的要求侧重点各有不同。 2 2 文本表示模型 因为文本是一种非结构化的数据，计算机无法对文本直接进行处理，因 此，文本自动分类系统首先要做的就是把文本表示成一种结构化数据。自从 文本检索和信息检索概念首次被提出以后，出现了许多文本表示模型，具有 代表性的有布尔模型( b o o l e a nm o d e l ) 、向量空间模型( v e c t o rs p a c em o d e l ) 、 概率模型( p r o b a b i l i s t i cm o d e l ) 等。这些模型从不同角度出发，使用不同的方 法处理特征加权、类别学习和相似度计算等问题。 2 2 1 布尔逻辑模型 布尔逻辑模型( b o o l e a nl o g i c a lm o d e l ) 也称为完全匹配模型，是一种相 对简单的文本表示模型。在分类时，它以文档中是否包含关键词来作为耿舍 的标准。 利用布尔逻辑模型进行文本分类，就是给定一系列的具有二值逻辑的特 征变量。这些变量是从文档中抽取出来的，用来描述文档的特征。通过布尔 操作符把表示文档信息的特征变量构成布尔表达式，此即为一查询。基于布 尔逻辑模型的文本分类技术特点是实现容易、用户操作方便、易接受，而且 查全率比较好。早期的文献检索系统大都采用了布尔模型。布尔模型大体上 可以分为两类：经典的伟尔模型与扩展的布尔模型。 经典的布尔模型建立于集合论与布尔代数的基础之上，主要应用于信息 检索中。在这种模型中，每篇文档表示成文档中出现的特征的集合，也可以 表示为特征空间上的一个向量，向量中每个分量权重为0 或者1 。经典布尔 模型中查询与文档的相关性只能是0 或者1 ，满足查询q u e r y 中的所有逻辑表 达式的文档被判定相关，不满足的被判定为不相关。经典布尔模型通常只能 用于信息检索中计算用户查询与文档的相关性，而无法利用该模型计算两个 13 哈尔滨i ：稃大学硕十学侮论文 义档史深层面的相似度，无法在更多的文本处理应用中使用，其查询结果非 真即假，限制性过强会导致漏判，。在经典布尔模型的基础上，研究人员重 新定义了a n d 与o r 操作符，使相关性可以成为 0 ，l 】之间的数。这便是通 常所说的扩展布尔模型。到目前为止，学者们已经提出了众多扩展布尔模型， 其中p n o r m 模型具有相对更优秀的性能。 2 2 2 向量空间模型 向量空间模型v s m ( v e c t o rs p a c em o d e l ) 是由s a l t o n 教授最早在上 1 9 6 8 年提出的，它使用向量表示文本，把分类过程简化为空间向量的运算。 向量空间模型最早成功应用于信息检索领域，有较好的计算性和可操作性， v s m 一直以来都是信息检索领域最为经典的计算模型。后来又在文本分类 领域得到了广泛的运用，并成功应用于著名的s m a r t 系统中。该模型现已 成为最简便、最高效的文本表示模型之一。 向量空间模型的假设是：一份文档所属的类别仅与某些特定的词或词组 在该文档中出现的频数有关，而与这些单词或词组在该文档中出现的位置或 顺序无关，每篇文本和查询都包含一些用特征项表达的揭示其内容的独立属 性，而每个属性都可以看成是向量空问的一个维数，则文本和查询就可以表 示为这些属性的集合，从而忽略了文本的结构中段落、句子及词语之间的复 杂关系。这样，文本和查询可以分别用空间的一个向量表示，文本与查询之 间的相似度可以用向量间的距离来衡量。相似度的计算方法有很多种，常用 的方法有内积、d i c e 系数、j a c c a r d 系数和余弦系数汪川。最常用的是余弦系 数法，即用两个向量之间的夹角余弦来表示文本与查询问的相似度。央角越 小，说明文本和查询之间的相似度越大。 向量空间的模型可以描述为 假设文档集d = 谚) ，idl = s ( 1dl 表示集合d 中元素的个数) ，特征项 集t = t j ) ，i ti = m 。 定义特征项f ，在文档d ，中的权重w ，为如下所示。 w 2 t f , d l ，i i s ，i j m 1 4 ( 2 1 ) 哈尔滨i ：稗人学硕十学何论文 向量空间模型把文档之间的相关度定义为它们之间的某种相似度。它认 为一篇文档与用户查询越相似，就认为此文档与用户查询越相关。v s m 把文 档表示成高维词空间的一个向量。向量中的每一维表示对应的词在文档中的 权重。相似度的度量采用夹角余弦，也就是通常所说的余弦距离。在此基础 上，建立文档的向量空间模型，把文档z 表示为m 维的向量( w ，w ， w 朋) ，在m 维欧氏空间中对于两个m 维向量d i = ( w l ，w 2 ，w ，册) 和d j = ( w w ，w ) 对应的夹角余弦为 一兰。，雁2善20s k = lk = l= 耥u i i 弘2 ， c 9 = 、= 揣 ( 2 - 2 y 七= j i - i “ 2 2 3 概率检索模型 在向量空问模型中，假设文档向量空间的基是相互正交的，没有考虑检 索词间的相互关系。并且控制向量操作的参数，如文档相似系数，并没有在 模型中规定，具有一定任意性。概率模型包括了检索词间的依赖关系以及主 要参数，如检索词权重计算，查询与文档相似度计算由模型自身决定。 r o b e r t s o n 提出了基于检索词和文档相关关系的概率检索模型，概率方法基 于两个主要的参数，文档的相关概率p r ( r e l ) 和不相关概率p r ( n o r e l ) ， 以及两个系数a 1 和a 2 。a 1 表示由于检索不相关的文档造成的损失，a 2 表 示错过检索相关文档所造成的损失。因为检索不相关的文档产生的损失为a 1 木 卜p r ( n o n r e l ) ，错过相关文档所造成的损失为a 2 * 1 - p r ( r e l ) ，因此 应该检索的文档应符合下式 a 2 木p r ( r e l ) a l * p r ( n o n r e l ) ( 2 - 3 ) g ：坠! 1 2 堕 ( 2 - 4 4 ) o = = - _ 一 l，j 。 1 一p r ( r e l ) a 2 吡g 篙舶g 器 5 ， 其中p r ( r e l ) 和p r ( n o r e l ) 为相关及不相关的先验概率，用p r ( x ir e l ) 和p r ( x in o n r e l ) 来表示后验概率。对于文本分类来讲，由于具有学习过程， 哈尔滨i ：科人学硕十学何论文 p r ( x ，i r e l ) 和p r ( x ，i n o r e l ) 可以通过学习获的”。 2 2 4 潜在语义索引 1 9 9 0 年，s c o t td e e r w e s t e r 提出了潜在语义索引( l a t e ns e m a n t i c i n d e x i n g ，l s i ) 的方法，并将它用在信息检索上，取得了很好的效果。潜在 语义索引又称潜在语义分析( l a t e ns e m a n t i c a n a l y s i s ，l s a ) ，是为了改善向 量空间模型的效果而提出的。潜在语义索引的基础是特征文本矩阵。将该矩 阵进行奇异值分解以得到潜在的语义结构模型。在这个降维的模型中，项与 项之间、文本与项之间、文本与文本之间的相似度都可以通过在这子空间中 所对应的向量间的内积或央角余弦来获得近似值。通过降维，将基本相似的 文本映射在同一个因子空间内，这也解决了以前所提到的关于不可靠的数据 现象。在文本处理过程中，特征和文本之间存在的概念关系是错综复杂的， 存在局部层次关系和意义的非线性交叉，更为复杂的关系经常通过增加维数 来获得最佳的近似，但过大或过小的维数都是应该避免的。关于潜在语义索 引的模型表示理论及奇异值的分解过程，本文将不再赘述【川。 2 3 特征选择技术 特征选择是文本分类中的一个重要环节。由于文本特征集的数量非常庞 大，一般的学习算法无法对其进行类别学习，使得进行特征子集的抽取变得 十分必要。特征选择可以从两个方而提高系统性能：一是分类速度，通过特 征选择，可以大大减少特征集合中的特征数，降低文本向量的特征维数，从 而提高了系统的运行速度。二是准确率，通过适当的特征选择，可以把那些 类别区分性强的特征挑出来，而把那些信息量少、类别特征小的特征项删除 掉。这样做，表面上看文本向量中的特征项少了，有些文本信息丢失了。但 实际上留下的特征项都具有比较强的类别区分能力的，能更好的突出类别的 特性，同时去除了各类别之间的共性。因此小但不会降低系统准确性，反而 会使系统精度提高旧，。 1 6 哈尔滨i ：科人学硕+ 学位论文 2 3 1 特征选择的定义 特征选择就是为了筛选出那些对于分类来说最相关的特征，去掉冗余的 和无效的特征。特征选择在原有的特征集合中选择一个子集，让分类器在所 选择的特征上进行分类。一个合适、有效的特征选择算法可以在数据预处理 阶段去掉数据中的冗余、有噪声的部分的同时，降低特征的维数，减少建立 模型的训练时间，提高分类器正确率。在有的文献中，特征选择被称为属性 选择( a t t r i b u t es e l e c t i o n ) 或变量选择( v a r i a b l es e l e c t i o n ) 。变量选择是 指对特定的输出选定具有最大预测能力的输入变量问题，而特征选择是指选 定一个最优的特征子集，这个特征子集是从输入变量中构造出来的。本论文 将采取大多数文献和学者对于特征选择的理解，约定特征选择是指在输入特 征集中挑选一个对目标概念最相关的特征子集的过程，而特征提取是指在输 入特征空间上做一个变换得到新的特征空间，在这个空间中选取一定的特征 来作为对模式的描述。两者的区别在于有没有在特征空间上进行变换。同时， 对于属性选择和变量选择，本文认为就是指特征选择。 2 3 2 特征选择的分类 依据评判准则和特征选择策略将特征选择分为很多种，其中特征选择搜 索策略分为：启发式搜索策略、完全搜索策略和随机搜索策略；特征选择评 判准则分为：距离度量、信息度量、相关度量、一致性度量和分类错误率度 量。根据特征选择框架，得到特征选择算法是由“特征子集生成”、“特征子 集评价”、“停止条件”和“结果验证 四个部分组成的，其中“特征子集生 成”决定了主要的搜索策略，它和“特征子集评价”中评价准则的确立是特 征选择算法中起决定作用的两个问题。 根据样本中是否含有类别信息，特