（计算机软件与理论专业论文）基于支持向量机的文本分类问题研究.pdf

中文摘要 摘要 文本自动分类是基于内容的信息自动分类的核心技术，它是由计算机自动判 别文本类别的过程。文本分类问题具有文本向量稀疏性大、维数高、特征之间具 有较大的相关性的特点，因此，支持向量机非常适合于文本分类问题，在文本分 类中具有很大的应用潜力。同时，文本分类也给支持向量机提出了许多富有挑战 性的课题。例如，文本分类具有类别和样本数目多、噪音多等特点，支持向量机 用于文本分类时存在训练和分类速度较慢等缺点。 本文从降低文本分类过程中文本向量数目的角度出发，来加快训练支持向量 机分类的速度。采用密度聚类的方法提取原始样本中对分类起决定性作用的样本 作为新的训练集进行分类器训练。这些起决定性作用的样本点就是分布在边界上 的点，这些点在s v m 理论罩被称为支持向量。本文的目的就是尽可能的将这些点 从原始文本向量集中提取出来。 如果将常见的密度聚类算法直接拿来使用，效果并不好，因为它们的时| 日j 复 杂度太高，导致整体的分类训练过程效率比较低。本文采用一种改进的密度聚类 算法，该算法融合了层次聚类算法c u r e 的特点，既保留密度聚类算法对边缘点 比较敏感的特性，又降低了算法的时间复杂度。同时，本文通过大量的试验得出 了针对文本分类样本的高维性特点，在对其进行密度聚类时仞始参数的动态设置 方法，从而在一定程度上解决了以前只能通过人工估算束确定参数值时效率低下， 实际应用效果不佳的弊端。 关键词：支持向量机：文本分类；密度聚类 英文摘要 s t u d yo nt e x tc l a s s i f i c a t i o nb a s e d o ns v m a b s t r a c t t e x ta u t o c l a s s i f i c a t i o ni st h ec o r et 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 i f i c a t i o n b a s e uo nc o n t e x 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 yb y u s i n gc 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 i 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 g f e a t u r e s s os v mi sv e r ys u i t a b l e a n dp o t e n t i a lf o rr e s o l v i n gt e x tc l a s s i f i c a t i o n m e a n w h i l e ，t h e r ea r el o t so ft a s k st h a ta r e f u l lo fc h a l l e n g i n gb yr e s o l v i n gt e x tc l a s s i f i c a t i o nu s i n gs v m f o re x a m p l e t h e r ea r e t o om a n yc a t e g o r i e s ，s a m p l e s ，n o i s e s ，a n dc l a s s i f i e rs p e e di ss l o wb yu s i n gs v m t h i sp a p e rs p e e d su pt h ec l a s s i f i c a t i o np r o c e s sb yd e c l i n i n gt h en u m b e ro ft e x t v e c t o r s t h i st h e s i sc h o o s e st h ed e c i s i v es a m p l e sf r o mt h eo r i g i n a ls e tb yu s i n gd e n s i t y c l u s t e r i n ga l g o r i t h m ，t h e ni t r i s e st h ed e c i s i v es a m p l e sa sn e w t r a i n i n gs e tt ot r a i nt h e s v mc l a s s i f i e r t h e s es a m p l e sa r ea l w a y st h ep o i n t st h a td i s t r i b u t ea r o u n de d g e ，w h i c h a r ec a l l e ds u p p o r tv e c t o ri ns v m t h et a r g e ti st of i n do u tt h es a m p l e sf r o mt h e o r i g i n a ls e t 。 i t sn o tag o o dw a yf o rm a k i n gu s eo ft h ec o m m o nd e n s i t yc l u s t e r i n ga l g o r i t h m d i r e c t l y ，b e c a u s et h e i rt i m ec o m p l e x i t yi sv e r yh i g h ，t h i sw i l lc a u s et h et o t a lc l a s s i f y i n g p r o g r e s se f f i c i e n c yv e r yl o w s ot h i s a r t i c l e u s e sa l li m p r o v e dd e n s i t yc l u s t e r i n g a i g o r i t h m ，t h i sa l g o r i t h mm i x e sf c a t u r e so fh i e r a c h i c a lc l u s t e r i n ga l g o r i t h mc u r e i t n o to n l yr e t a i n st h ef e a t u r et h a ti ss e n s i t i v et oe d g ep o i n t ，b u ta l s od e c l i n e st h et i m e c o m p l e x i t yo fd e n s i t yc l u s t e r i n gp r o g r e s s a tt h es a m et i m e ，i td o e sl o t so fe x p e r i m e n t s t of i n do u tam e t h o dt h a tc a nd y n a m i c a l l ys e tt h ei n i t i a lp a r a m e t e r st h a tw i l lb eu s e di n t h ec l u s t e r i n gp r o g r e s s t h ew a yi sm o r ee f f i c a c i o u st h a nt h eo l do n et h a tm u s ts e t p a r a m e t e r sm a n u a l l y k e yw o r d s ：s v m ；t e x tc l a s s i f i c a t i o n ：d e n s i t yc l u s t e r i n g 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文 ：基王塞缱回量扭麴塞奎筮羞间星丛峦：。除论文中已经 注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明 确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表 或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名： 弋f 为净；月一日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位 论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或 扫描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于：保密口 不保密( 请在以上方框内打“”) 论文作者签名： 缸导师签名：渗盏烈 隰砷年岁月伊 基于支持向量机的文本分类问题研究 第1 章绪论 1 1 问题的提出及意义 随着信息时代的来临，为了从海量的信息中迅速查找需要的信息，就需要对 信息进行分类。传统的做法是对信息进行人工分类，并加以组织和整理，为人们 提供一种相对有效的信息获取手段。但是，这种传统的人工分类的做法存在着许 多弊端：一是耗费大量的人力，物力和精力；二是存在分类结果一致性不高的问 题。这就要求我们探索文本自动分类的有效方法，提高分类效率。只有这样才能 保证检索的查全率和查准率都得到提高。 面对如此复杂的问题，分类技术在信息检索、信息过滤、数据挖掘等方面起 着至关重要的作用。而网上的大部分信息以文本的形式存在，因此，文本自动分 类就成为信息处理领域的一个重要的研究课题。 文本自动分类是信息检索技术和人工智能技术相结合的研究领域，是进行基 于内容的自动信息管理的核心技术。文本自动分类是根据一些已经分配好类别标 签( 这些类别标签预先定义好) 的训练文档集合，来对新文档分配类标签，其目的 就是对文本集进行合理处理和组织，使得这些文本能够按照类别区分开来。作为 知识的组织工具，它为信息检索提供了更高效的搜索策略和更准确的查询结果。 其中，高效性在于用户可以首先确定查询的可能类别，以减小需进一步匹配的文 本数量；有效性在于相似的文本很可能与相同的查询相关。这样使得检索的查全 率和查准率都得到了提高。 文本分类的目标是在分析文本内容的基础上，给文本分配一个或多个比较合 适的类别，从而提高文本检索等应用的处理效率。另外，文本分类可以应用到垃圾 邮件的判定；新闻出版按照栏目分类，类别 政治，体育，军事，) ；词性标注， 类别 名词，动词，形容词，) ；词义排歧，类别 词义1 ，词义2 ，) ，文本检 索，文本过滤以及主题发现与跟踪等。从s p r i n g e rl i n k 全文电子期刊与i e l ( i e e ， i e e e ) 数据库中，可以看到最近的期刊与国际会议论文，有大量的关于文本分类的 文章，说明随着大量网上电子信息的出现，文本分类仍是人们研究的热点。 第1 章绪论 1 2 研究背景及现状 国外自动分类的研究起步较早，始于1 9 5 0 年代末。1 9 5 7 年，i b m 公司的 h p l u h n 在这一领域进行了开创性地研究，他首先将词频统计的思想用于文本分 类中。1 9 6 0 年m a r o n 在j o u r n a lo f a s m 上发表了有关自动分类的第一篇论文0 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 2 年博科( h b o r k o ) 等人提出了利用因子分析法进行文献的 自动分类。其后许多学者在这一领域进行了卓有成效地研究。国外的文本分类经 历了可行性基础研究和实验性开创研究，目前已经进入到实际性商业应用，在信 息检索、电子会议、网络安全，机器翻译等方面都得到了广泛地应用。 文本分类的发展历史大致可分为两个阶段，从6 0 年代起步至8 0 年代末主要 是以专家人工构建的知识工程技术为支撑，分类系统包含专家定义的一系列逻辑 规则，依据这些规则可以把新给定的文本归类为某种或几种特定类别，典型的代 表系统有麻省理工学院( m i t ) 为白宫开发的邮件分类系统、卡内基集团为路透社开 发的c o n s t r u e 系统等。第二阶段从9 0 年代开始，随着互联网技术的快速发展，文 本自动分类的研究也进入了一个新的阶段，各种方法相继得到了发展i t , 2 】，包括机 器学习技术为主的信息分类技术逐渐取代了基于知识工程的方法，成为文本自动 分类研究的主要形式，如n a v i eb a y e s ，d e c i s i o nt r e e ，神经网络等等。1 9 9 8 年 d o r t m u n d 大学的j o a c h i m s 3 1 探讨了用支持向量机方法进行文本分类，取得了很好 的效果。此外，些学者还采用 b o o s t i n g 4 j 方法来探讨提高分类处理的方法。这类 分类算法通常是从预先分类正确的训练文本集合中学习到类别的特征判别信息， 再通过测试文本集合对分类器性能进行测试。目前，这种方法所达到的分类性能 已经不亚于人工分类。典型的代表系统有g o o g l e 公司的搜索引擎和i b m 公司的文 本智能挖掘机等。 国内自动分类研究起步较晚，始于2 0 世纪8 0 年代初期。1 9 8 1 年侯汗清对计 算机在文献分类工作中的应用作了探讨，并介绍了国外在计算机管理分类表、计 算机分类检索、计算机自动分类、计算机编制分类表等方面的概况。此后，国内 的研究者在英文文本分类研究的基础上采取相应策略，结合中文文本的特定知识， 基于支持向量机的文本分类问题研究 然后应用于中文之上，继而形成中文文本自动分类研究体系。到目前为止，我国 陆续研制出一批计算机辅助分类系统和自动分类系统。这其中有基于人工智能技 术的分类系统，有基于统计技术的分类系统，还有基于模糊技术的分类系统，近 几年来基于统计知识的分类方法占主流，也不乏有基于规则的分类方法。国内的 清华大学，上海交大，哈工大，中国科学院等科研院所在文本分类领域作了很多 的研究，在中文文本自动分类镢域中已经取得了令人瞩目的研究成果，其中一些 已经被成功地推广和应用，典型地代表系统有北大天网和百度搜索等。 1 3 本文的研究工作 支持向量机从被广泛重视到现在只有几年的时间，其中还存在很多尚未解决 或尚未充分解决的问题，需要进一步完善和改进以适应实际应用的需要。面对文 本分类等具有类别和样本数目多、噪音多等特点的应用，支持向量机在应用过程 中存在以下问题： ( 1 ) 支持向量机是针对二分类问题提出的，当用于多分类伺题时必须将其推 广。对于类别数目较多的分类问题，目前仍缺乏有效的支持向量机多分类方法。 在文本分类应用中，多分类问题非常普遍，支持向量机多分类方法的研究具有很 大的实用价值，是支持向量机研究中的重要内容。 ( 2 ) 标准支持向量机对所有样本采用相同的错分惩罚，对噪音敏感，分类时 倾向于样本数目较多的类别；并且，对于需要求解二次规划问题的支持向量机模 型，当样本数目较多时，其训练速度较慢。如何进一步改进和完善支持向量机模 型及其训练算法，是支持向量机研究中的热点问题。 ( 3 ) 一般情况下，文本分类问题的样本数目越多，支持向量机的分类速度越 慢。对于训练样本数目多的分类问题，支持向量机的分类速度过慢，这一点限制 了支持向量机的应用，成为支持向量机方法进入大规模实用化阶段的瓶颈。 本文从缩减原始文档训练集的规模，提高支持向量机的分类速度方面入手， 考虑到支持向量( s u p p o r tv e c t o r ) 在支持向量机( s u p p o r tv e c t o rm a c h i n e ) 分类中的 重要作用，采用改进的密度聚类的方法对原始的文档向量集进行简约处理，提取 第1 章绪论 训练集中的边缘点，也就是支持向量。利用简约后的训练集进行s w 分类器的训 练，这样可以减少训练的时间代价。 本文的工作主要包含以下几个方面： 第一章：介绍了文本自动分类的意义及目前的研究现状。 第二章：从文本分类任务的特点，文档的表示模型，文档特征选择方法等方 面介绍了文本分类技术。 第三章：支持向量机背景理论及其实现算法的综述，概要介绍了支持向量机 的背景理论一一统计学习理论。 第四章：讨论了为何选取密度聚类算法应用到我们的系统中；详细介绍了利 用密度聚类方法对原始的文本向量集进行聚类处理并提取边缘点集作为新的训练 集提供给s v m 进行分类的方法，并提出了用一种改进的密度聚类算法提取边缘点 的；对改进的密度聚类算法的两个初始参数密度半径、密度阈值的设置作了分析 研究，提出了在高维数据环境下动态调整参数值的方法。一 第五章：介绍了采用基于密度聚类的提取边缘点的s v m 分类方法的具体实现过 程及对分类结果进行分析。 最后，对已做的工作进行总结，并对以后的工作进行展望。 基于支持向量机的文本分类问题研究 第2 章文本分类技术 文本分类技术是数值分类学和信息处理技术相结合的研究领域。在最初的分 类学中，人们往往通过经验和专业知识对事物进行定性分析，很少使用数学工具。 随着信息的不断增长，信息之间的关系也日益复杂，从而导致分类程度越来越细， 分类规模也越来越大，这时仅仅依靠定性分析将无法满足要求，于是人们在分类 过程中引入数学工具，使用统计、人工智能等各种方法处理信息，从而形成了数 值分类学( n u m e r i c a l t a x o n o m y ) ，大大推动了信息处理技术的前进步伐。 2 1 文本分类任务的特点 简单地讲，文本分类( t e x tc a t e g o r i z a t i o n ，t c ) 的任务是：在给定的分类体系 下，根据文本的内容或属性，将大量的文本归到一个或多个类别中。从数学角度 来看，文本分类是一个映射的过程，它将未表明类别的文本映射到已有的类别中， 该映射可以是一对一映射，也可以是一对多的映射，因为通常一篇文本可以同多 个类别相关联。用数学公式表示如下： ，：a b 其中：a 2 ( d 1 ，d ：，d 。)b 一( c 1 ，c 2 ，c 。) ( 2 1 ) 即：a 为所有待分类的文本的集合；b 为给定分类体系下，所有类别的集合。 4 可以为无限集合，而b 必须为有限集合。 文本分类的映射规则，是文本分类系统的关键，它是系统根据训练集的样本 信息总结出的分类规律，来建立判别公式和判别规则；遇到新文本后，根据总结 出的文本分类的映射规则，确定该文本相关的类别。 文本分类实际上是一个模式分类任务，所以许多模式分类的算法可以应用到 文本分类中。但是，文本分类同时又是模式分类和自然语言处理的一个交叉学科， 是和文档的语义紧密相关的，所以与普通的模式分类任务相比有许多独特之处【5 1 。 ( 1 ) 高维特征空间 在文档特征提取的时候，有大量的候选特征。如果使用词语作为文档特征， 即使一个1 0 0 0 篇左右的训练文档集，一般也会产生上万的候选特征。 第2 章文本分类技术 ( 2 ) 特征语义相关 一种避免“高维灾难”的解决方法是，假设大部分特征空间之间是相互独立 的，使用特征选择方法选取那些彼此无关的特征提取出来，作为能够代表文档特 征的依据。但是非常不幸，文本分类中很少特征之间是彼此无关的。个好的分 类器应该将尽可能多的特征结合起来，而特征选择会导致信息的损失。 ( 3 ) 特征存在多义和同义现象 文本分类中一般使用词、短语、n g r a m 项等作为表征文档语义的文档特征。 但是，这些特征往往无法清晰地表达一种含义。一个特征可能有多种含义，即多 义现象，如：“教授”这个特征即可以表示一种职称的含义，也可以代表一种传 授知识的含义。同时，许多相同的含义又可以用不同的特征来描述，即同义现象， 如：“计算机”和“电脑”这两个特征都表示相同的含义。 ( 4 ) 特征分布稀疏 根据z i p f 法则，如果我们在一个大型语料库中统计一种语言中每个单词类型 出现的次数，然后依据出现频度列出单词表，我们能够探查单词频度，和它在表 中位次r 的关系为： 三( 2 2 ) - 例如，排位为第5 0 位的单词的频率厂近似等于嘉，排位为第1 5 0 位的单词的 频率厂近似等于击。这意味着排列第5 0 位最常见的单词的出现频度是第1 5 0 位 单词出现频度的3 倍。文档特征空间的维数是非常高的，而能够作为文档特征的 往往是那些在语料库出现频度适中的词。对于一篇不是很长的文档来说，特征空 间中多数特征词的出现频率都为0 ，导致了文档向量中多数特征的值都为0 ，特征 的分布非常稀疏。 ( 5 ) 基本线性可分 基于支持向量机的文本分类问题研究 文本分类中，大部分类别之间不存在双螺旋结构，基本线性可分。所以一些 复杂的、在其它模式分类任务中应用很成功的方法，在文本分类中未必会取得很 好的效果f 6 1 。 2 2 文档表示模型 文本分类是一种面向语义的操作。实际上，即便是属于同一语义类别的文档， 它们的用词、长短和风格也会大相径庭。这就涉及到一个怎样表示文档才能体现 出它的内涵的问题。这一问题包括两个方面：用于表征文档语义的特征和这些特 征的组织方式。 2 2 1 文档特征 从一篇文档的语法层次来看，它是由词、短语、句子和段落所构成的。所以， 这些要素都可以作为文档的特征。但是，随着这些要素所处的语法层次增高，组 合出的特征会呈指数增长，所以基于句子和段落层次的特征在文本分类中比较少 见。常用的文档特征有词、短语和n g r a m 项。 ( 1 ) 词语 给定一篇文档，最直观的方法就是使用词和短语作为表征文档语义的特征。 对于英文来说，不存在分词的问题，因为词语之间已经使用空格格开。但是，英 语存在词形的变化，如：名词的单复数、动词的时态变化、词的前缀和后缀变化 等，所以会有一个词干抽取的过程( s t e m m i n g ) 同。对于中文来说，需要借助于词典 和使用专门的分词技术。 ( 2 ) n g r a m 项 对于中文来说，n g r a m 项一般由相邻字构成。例如：从“中国人民”中提取 2 - g r a m 项，可以得到“中国”、“国人”、“人民”三个2 - g r a m 项。对于英文 来说，n g r a m 项既可以由相邻单词构成，也可以由相邻字母构成。例如：从 “r e p u b l i c o f c h i n a ”中提取2 - g m m 项，以单词的方式可以得到“r e p u b l i c o f ”、 “o fc h i n a ”两个2 - g r a m 项；以字母的方式可以得到“r e ”、“e p ”、“p u ” “n a ”共1 6 个2 - g r a m 项【8 】o 第2 章文本分类技术 n g r a m 项的提取相对要容易得多。但是，n g r a m 项的语义显然没有真正的 词那么明显。而且，随着n 的增长，n g r a m 项的数目会呈指数增长，使算法的时 间和空间消耗大大增加，所以n 的取值一般不宜过大。 2 2 2 文档表示 从本质上讲，文本是一个由众多字符构成的字符串，无法被学习算法直接用 于训练或分类。要将机器学习技术运用于文分分类问题，首先需要将作为训练和 分类对象的文档，转化为学习算法易于处理的向量形式吼 现在文本分类技术的前提假设是特征和文档类别概念密切相关。在这一假设 下，通常有两种文档表示模型，即向量空问模型和布尔模型。 s a l t o n 提出的向量模型( v e c t o rs p a c em o d e l ，简称v s m ) i t o 】最早成功应用于信 息检索领域，后来又在文本分类领域得到了广泛地运用。向量空i b j 模型的一个基 本假设是，一份文档所属的类别仅与某些特定的单词或词组在该文档中出现的频 数有关，而与这些单词或词组在该文档中出现的位置或顺序无关。也就是说，如 果将构成文本的各种语义单位( 如单词、词组) 统称为“词项”，以及词项在文本 中出现的频数称为“词频”，那么一份文档中蕴涵的各个词项的词频信息足以用 来对其进行正确的分类。事实上，这一假设对于文本分类而言是恰当地，而对于 其它方面的文本分类，如流派、作者等识别问题就不那么可靠了。 v s m 是由一组规范化的正交词条矢量组成的向量空间，每一个文档映射到向量 空间的一个点，向量间的距离表示文档之问的相似度。通过这种模型可以将给定 的文档以向量的形式表示在v s m 中，从而将文档之问的相似性这一抽象的问题转 化为具体的空间的点与点的距离问题，通过计算出任意两个向量之间的近似程度， 从而来反映所对应的文档问的相似性。 在v s m 中，主要涉及到以下几个概念： ( 1 ) 文档( d o c u m e n t ) ：指一篇文章。 ( 2 ) 项( t e r m ) ：也称为索引项或特征项，一般指文档中的词或短语。给文档 分类主要是依据特征项。即一些特殊的项，可以起到代表文档的作用。 基于支持向量机的文本分类问题研究 ( 3 ) 项的权重( t e r m w e i g h t ) ：假设一个系统包含有r n 个文档、n 个不同的项， 则d 。一( t 1 , f 2 ，t 。x 1 i m ) ，表示一个文档；给定其中的项t t ( 1 ks _ ，1 ) 赋值，记 为m ，表示它在文档中的重要程度，通常称为项f 。的权重。 ( 4 ) 向量空间模型：由( 3 ) 得到一个含值的文档表示，记作： d 。一( t w 1 ，t 2 w 2 ，f 。w n ) 。由于t 。，f ：，t 。互不相同，可以把它们看作是n 维欧氏空 间的n 个坐标，把( m ，h ，：，w n ) 看作是n 维欧氏空间的向量。这样，称 d l 一( f 。，f ：，t 。) 为文档d l 的向量表示。t 。为特征项词条，彬为对应坐标值，即特 征词条权值。 布尔模型可以看作是向量模型的一种特例，根据特征是否在文档中出现，特 征的权值只能取1 或0 。许多时候，使用二值特征的分类效果并不比考虑特征频率 的差。 决策树方法、关联规则方法和b o o s t i n g 方法就是基于布尔模型；而k n n 法、 s v m 方法、l l s f 是基于向量模型。b a y e s 推理网分类方法，则是考虑了文档中词 之1 1 日j 的依赖关系。 2 3 _ 文档特征选择方法 在文本分类中对文本进行分词后，文本就变为词集，但是词集中有很多虚词 在文章中仅起到结构作用，不表示实际意义，比如介词，副词等，另外还有一些 词在整个语料中出现频率高而在每篇文档中出现概率大致相等，对文本分类来说 作用不大，我们把这些词合称为停用词。对于这些词，应该从特征集中去掉。停 用词的选取对词集的大小、分类的准确率都有影响。 停用词的选择原则：第一，删除停用词后，分类准确率应不降；第二，删除 停用词后能够达到粗降维的目的。 从文档中提取的特征数量很大，特别是训练文档库比较大的时候。有些特征 对文档分类的作用可能并不大。因此，我们有必要对提取到的文档特征进行筛选， 选出那些最能代表类别概念的特征。这一过程就是特征选择。 特征选择的具体步骤为： 第2 章文本分类技术 ( 1 ) 从训练文档库中提取所有特征项，构成文档特征集f ： ( 2 ) 对集合f 中的每一项用下列某一种方法进行打分。譬如，选用信息增量 方法，则对f 中的任意n - g r a m 项，求i g ( d 。当f 中的所有项都打分完成后，按 分值由高到低进行排序； ( 3 ) 假设需要选取n 个文档分类属性，则从f l 中的选取分值高的n 个项，构 成最终的分类属性集f s 。f s 将用于文档分类的训练与测试。 下面给出几种文档属性选择方法，目的是通过测试比较，找到比较好的文档 属性选择方法。这些方法，基本上是基于信息论和统计分析。 2 3 i 信息增量( in f o r m a t i 0 1 3g a i n ) 信息增量表示文档中包含某一个特征值时文档类的平均信息量。它定义为某 一特征在文档中出现前后的信息熵之差。假定c 为文档类变量，c 为文档类的集合， d 为文档，为特征。对于特征，其信息增量记为m ( ) ，计算公式如下： i g ( f ) - h ( o h ( c l ，) = 罗p ( c ) l 0 9 0 ( c ) ) + p ( ，) p ( c i ：) l o g ( p ( c i ，) + p ( 7 ) p ( c l f ) l o g ( p ( c 1 7 ) 怒篾 2 荟厂) l o 甙篇) + p ( c 7 ) l o g 踹) ) ( 2 3 ) 在只考虑单个类的时候，则有： 础黼批甙羞鬟静嘶 7 ) 1 0 甙焉黯) ( 2 t ) 2 3 2 互信息( m u t u a ii n f o r m a t i o n ) 互信息是用于表征两个变量间相关性的。对于文档类别c 和特征，其互信息 记为m l ( c ，) ，计算公式如下： m l ( c ，) - 1 0 9 篇 ( 2 5 ) 显然，当，独立于c 时，m l ( c ，) 为0 。 基于支持向量机的文本分类问题研究 2 ，3 3z 2 统计 z 2 统计也是用于表征两个变量间的相关性，但它比互信息更强，因为它同时 考虑了特征存在与不存在时的情况。对于文档类别c 和特征厂，其z 2 统计的计算 公式如下： 舭，) i 丝篙舞铲 c z e ， 当c 与厂相互独立时，z 2 ( c ，) 为0 。和互信息类似，取平均值： 盔( ，) i 荟p ( 2 7 ) 2 3 4 交叉熵( c r o s se n t r o p y ) 交叉熵和信息增量相似，不同之处在于信息增量中同时考虑了特征在文本中 发生与不发生时的两种情况，而交叉熵只考虑特征在文本中发生一种情况。对于 特征，其交叉熵记为c e ( ) ，计算公式如下： c e ( c ，) 2 荟北，) l 船) ( 2 8 ) 在只考虑单个类的时候，则有：+ c e ( c ，) 叫c ，) l o g ( 焉器) ( 2 9 ) 2 4 特征词权重 不同的特征项对文档的重要程度和区分度的影响是不同的，因此系统在对文 本进行形式化处理的时候，需要对特征项进行加权，下面对常用的加权函数迸行 详细介绍。 ( i ) 布尔权重 布尔权重是最简单的一种加权方法，如果特征词出现次数为0 ，则其权重为0 ， 如果特征词出现次数大于0 ，则其权重为i 。公式如下： 岭飚： ( 2 t o ) 第2 章文本分类技术 其中w t 。表示特征词f 在文档j 中的权重，矾表示特征词f 在文档j 中出现的 次数。 ( 2 ) 词频权重 该方法将特征词的频次作为权重。公式如下： w t 。- 珥， ( 2 1 1 ) ( 3 ) t f - i d f 权重 该方法基于以下两点原因：一是特征词i 在文档，中出现次数越多越重要，权 重和z 成正比；二是文档集中含有特征词i 的文档数d e 越大越不重要，权重和 d f , 成反比。公式如下： w t 。，- 矾l o g ( n d f , ) ( 2 1 2 ) 该式表明，若特征词f 在所有文档中均出现，即d 互一n ，n w t 。- 0 ，也就是 说，虽然特征词i 出现次数多，但它的分布比较均匀，说明它没有区分类别的能力。 ( 4 ) 信息熵权重 咿崦c t f o + 1 0 ) * 【1 + 击荛隆s c 剐 眨 埭z e 嗍击薹 器，咯，卜特鳓的熵或不确珧 当分布极度均匀：熵等于1 ，说明它没有区分类别的能力。只在一个文档中出现： 熵等于0 ，说明它的区分类别的能力最大。 2 5 文本分类性能评估指标 因为文本分类从根本上来说是一个映射过程，所以评估文本分类系统的标志 是映射的准确度和映射的速度。映射的速度取决于映射规则的复杂程度，而评估 映射准确程度的参照物是通过专家思考判断后对文本的分类结果( 这里假设人工 分类完全正确并且排除个人思维差异的因素) ，与人工分类结果越相近，分类的准 确程度就越高，这里隐含了评估文本分类系统的两个指标：准确率和查全率。 基于支持向量机的文本分类问题研究 准确率是所有判断的文本中与人工分类结果吻合的文本所占比率。 查全率是人工分类结果应有的文本中分类系统吻合的文本所占的比率。 准确率和查全率反映了分类质量的两个不同方面，两者必须综合考虑，不可 偏废，因此，存在一种新的评估指标，1 值。 以上三个数学公式分表如下： 准确率。肥c 括如n ，= 萎嚣募燃 c z t ， 查全率( ，e f f ) 一坌毒要筹 ( 2 1 5 ) f 1 。姿氅慧 ( 2 1 6 ) 查全率+ 准确率 一 另外有微平均和宏平均两种计算准确率、查全率和f 1 值的方法。 微平均：计算每一类的准确率、查全率和f 1 值。 宏平均：计算全部类的准确率、查全率和f 1 值。 2 6 常用的文本分类方法 国内外当前流行的文本分类方法有k 邻近法( i c j c n ) 1 1 1 , 1 2 1 、朴素贝叶斯( n a i v e b a y e s ) 方法1 1 3 , 1 4 1 、最大熵模型1 1 5 1 、线性最小平方拟合( l l s f ) 【1 6 1 、决策树方法1 切、 神经网络方法1 1 8 】、遗传算法1 1 9 1 、支持向量机( s v m ) 方法【捌以及概念推理网法1 2 1 l 等。其中k n n 、n b 和s v m 由于分类效果比较好成为近几年人们研究的热点。通 过【2 2 】的实验结果得知，在采用了文档形和词频形两种概率估计方法，利用查准率、 查全率以及f 1 值评价了分类器的性能，实验结果显示在两种概率估计模型下s v m 都是进行文本分类最好的一种方法。 第3 章支持向量机与统计学习理论 第3 章支持向量机与统计学习理论 3 撕l ：r ( s u p p o r tv e c t o rm a c h i n e ) 2 3 , z 4 1 是九十年代出现的一种新的分类方 法，已初步表现出很多优于已有方法的性能。利用支持向量机训练得到的分类器 具有很好的推广能力，即使训练样本很少，分类器的预测准确率也会很高。支持 向量机是建立在统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ) 1 2 5 】基础之上的。统计学 习理论是一种专门研究有限样本情况下机器学习规律的理论，它建立在一套较坚 实的理论基础之上，为解决有限样本学习问题提供了一个统一的框架；它能将很 多现有方法纳入其中，有望帮助解决许多原来难以解决的闽题( 比如神经网络结构 选择问题、局部极小点问题等) 。 3 1 机器学习的基本方法 3 1 1 学习问题的一般表示 统计学习理论的创始人v v a p n i k 认为，机器学习的目的是根据给定的训练样 本求对某系统输入输出之间依赖关系的估计，使它能够对未知输出作出尽可能准 确地预测。可以一般地表示为：变量y 与x 存在一定的未知依赖关系，即遵循某一 未知的联合概率f & ，y ) ( x 和y 之间的确定性关系可以看作是其特例) ，机器学习问 题就是根据n 个独立同分布观测样本 0 。，y 。l b ：，y ：l ，仁。，y 。) ( 3 1 ) 在一组函数 ， ，w ) 1 w 中求一个最优的函数，b ，) 对依赖关系进行估计，使 期望风险 g ( w ) - 仁( _ ) ，( x ，w ) ) d p ，y ) ( 3 2 ) 最小。其中， ，仁，w ) ) 称作预测函数集，w 为函数的广义参数。 厂0 ，) 可以表示 任何函数集。工( y ，i ( x ，w ) ) 是用，扛，w 。) 对) 进行预测而造成的损失，不同的学习问 题有不同形式的损失函数。预测函数也称作学习函数、学习模型或学习机器【硐。 基于支持向量机的文本分类问题研究 v a p n i k 认为有三类基本的机器学习问题，即模式识别、函数逼近和概率密度 估计。对模式识别问题，输出y 是类别标号，两类情况下) ，一佃，1 或伍一1 ) ，预测函 数称作指示函数，损失函数可以定义为 如旭m 船耄兹： 。， 使风险最小就是b a y e s 决策中使错误率最小。在函数逼近问题中，y 是连续变 量( 这里假设为单值函数) ，损失函数定义为 l ( y ，0 ，w ) ) 一一l o g p ( x ，w ) ( 3 4 ) 3 1 2 经验风险最小化 在上面的问题表述中，学习的目标在于使期望风险最小化，但是，由于我们 可以利用的信息只有样本( 3 1 ) ，( 3 2 ) 式的期望风险根本无法计算，因此传统的 学习方法中采用了所谓经验风险最小化( e m p i r i c a l r i s k m i n i m i z a t i o n ，e r m ) 准则， 即用样本定义经验风险 r 。( w ) - 昙耋眠雕删 ( 3 5 ) 作为对( 3 2 ) 式的估计，设计学习算法使它最小化。对损失函数( 3 3 ) ，经验 风险就是训练样本错误率：对( 3 4 ) 式的损失函数，经验风险就是平方训练误差； 而采用( 3 5 ) 式损失函数的e r m 准则就等价于最大似然方法。 事实上，用经验风险最小化准则代替期望风险最小化并没有经过充分地理论 论证，只是直观上合理的想当然做法，但这种思想却在多年的机器学习研究中占 据了主要地位。人们多年来将大部分注意力集中到如何更好地最小化经验风险上。 而实际上，即使可以假定当n 趋向于无穷大时( 3 5 ) 式趋近于( 3 2 ) 式，在很多问题 中的样本数目也离无穷大相去甚远。其实，下面我们会讨论到，在有限样本下经 验风险最小化准则得到的结果并不一定能使真实风险也较小。 第3 章支持向阜机与统计学习理论 3 1 3 复杂性与推广能力 经验风险最小化原则希望通过最小化训练误差来实现最小化测试误差的目 的，在早期的神经网络研究中，人们总是把注意力集中在如何使尺( 口) 更小，但 很| 夹发现，一味追求训练误差并不总能达到好的预测效果。实际情况是，只要学 】矶器足够复杂，训练时间足够长，则训练误差可以任意减小。最极端的情况是， 学习机器“记住”所有训练样本，则训练误差为零，但实际上这种学习机器几乎 不具有泛化能力。在某些情况下，训练误差过小反而可能会导致泛化能力下降。 经验风险( 或训练误差) 对学习机器的性能有一定的影响，但不起决定作用。 执行经验风险最小化原则( 即最小化训练误差) ，并不总能提高学习机器的泛化性 能。复杂度较高的学习机器，往往具有较低的经验风险。因此，经验风险最小化 碾则的结果，将使学习机器变得越来越复杂。学习机器的复杂度对其性能有较大 影响，泛化性能好的学习机器应该具有与实验面对的问题相对应的复杂度。 3 2 统计学习理论 32 v c 维 为了研究机器学习过程一致收敛的速度和推广性，统计学习理论中定义了一 系刊有关函数集学习性能的指标，其中最为重要的是v c 维( v a p n i k c h e r v o n e n k i s d i m e n s i o n ) 。模式识别方法中v c 维的直观定义是：对一个指示函数集。如果存在 h 个样本能够被函数集中的函数按所有可能的2 种形式分开，则称函数集能够把h 个洋本打散，函数集的v c 维就是它能打散的最大样本数目h 。若对任何数目的样 夺都有函数能将它们打散，则函数的v c 维是无穷大。有界函数的v c 维可以通过 用定的阈值将它转化成指示函数来定义。 v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂( 容量越大) 。 遗憾地是，目前尚没有通用的关于任意函数集v c 维计算的理论，只对一些特殊的 函敛知道其v c 维。比如在 维实数空间中线性分类器和线性实函数的v c 维是 ，l + 1 。对于一些比较复杂的学习机器( 如神经网络) ，其v c 维除了与函数集( 神经 网结构) 有关外，还受学习算法等的影响，其确定更加困难。对于给定的学习函数 基丁= 支持向量机的文本分类问题研究 集，如何( 用理论或实验的方法) 计算其v c 维是当前统计学习理论中有待研究的一 个问题。 v a p n i k 提出了v c 维的概念柬标志函数集的复杂程度，并用这今概念给出了 与分饰无关的学习机器推广能力的界。这个界由两部分构成：经验风险和置信范 围( 以v c 维为参数) 。学习机器能力过强( v c 维很大) ，虽然能取得小的经验风险， 但置信范围会很大；v c 维太小又会导致大的经验风险。一个好的归纳原则必须在 两者之间作出权衡。 结构风险最小化原则( s t r u c t u r a lr i s km i n i m i z a i t o n ，s r m ) 1 2 8 】正是这样一种归 纳原则。s r m 原则定义了在对给定数据的逼近精度和逼近函数的复杂性之问的一 种折衷。 3 2 2 结构风险最小化 由于经验风险最小化原则在样本有限时是不合理的，我们需要同时最小化经 验风险和置信范围。其实，在传统方法中，选择学习模型和算法的过程就是调整 置信范围的过程，如果模型比较适合现有的训练样本( 相当于值适当) ，则可以 取得比较好的效果。但因为缺乏理论指导，这种选择只能依赖先验知识和经验， 造成了如神经网络等方法对使用者经验的过分依赖。统计学习理论提出了一