（计算机应用技术专业论文）分类分析的研究与实现—利用svm构造决策规则分类器.pdf

华北电力人学硕士学位论文摘要 摘要 支持向量机( s v m ) 作为基于统计学习理论的- 4 + 机器学习方法，具有良好的 分类性能。可理解的分类模式对人类专家是非常重要的，然而s v m 的分类模式却不为 人类专家所理解。本文介绍了四种具有归纳偏置的布尔核函数，我们利用这四种核函 数构造出一种新颖的决策规则分类器d r c b k 。实验表明，本文提出的d r c b k 在 文本分类领域和非文本分类领域都具有优秀的分类性能。 d r c b k 的一个不足之处就是产生的规则集比较大。本文给出了一个有效的解 决途径，提出了加权s v m 法线规则集筛选算法。实验表明，使用该算法后，d r c b k 的规则集得到很大程度的压缩，同时，分类性能亦有所提高。 关键词：数据挖掘，s v m ，布尔核函数 a b s t r a c t a sak i n do fm a c h i n el e a r n i n g a l g o r i t h mw h i c hi s b a s e do nt h es t a t i s t i c s l e a r n i n g t h e o r e t i c s ，t h es u p p o r tv e c t o rm a c h i n e ( s v m ) h a se x c e l l e n tc l a s s i f i c a t i o np e r f o r m a n c e u n d e r s t a n d a b l ec l a s s i f i c a t i o nm o d e l i sv e r yi m p o r t a n tf o rh u m a n e x p e r t s h o w e v e r ，c u r r e n t l y ， t h ec l a s s i f i c a t i o nm o d e lf o rs v mc l a s s i f i e r sj sn o n u n d e r s t a n d a b l eb yh u m a n e x p e r t s i nt h i s p a p e r w ei n t r o d u c e f o u rb o o l e a nk e r n e l s u s i n gt 1 1 ef o u rk e r n e lf u n c t i o n sw h i c hw e i n t r o d u c e w eb u i l dan o v e l t yd e c i s i o nr u l ec l a s s i f i e rn a m e da sd r c 丑殷e x p e r i m e n tr e s u l t s s h o wt h a t ，f o rb o t ht e x tc l a s s i f i c a t i o na n dn o n t e x tc l a s s i f i c a t i o n ，d r c - b kh a se x c e l l e n t c l a s s i f i c a t i o np e r f o r m a n c e i ti sad i s a d v a n t a g et h a td r c b kw i l lp r o d u c eal a r g es i z eo fr u l es e t i nt h i sp a p e r ， w ea l s op r e s e n taw e i g h t e ds v mn o r m a lr u l es e l e c t i o na l g o r i t h m w h i c he m c a c i o u s t y r e s o l v e st h i sp r o b l e m e x p e r i m e n tr e s u l t ss h o wt h a t ，a f t e ra p p l i e dw i t ht h i s a l g o r i t h m ， t h es i z eo fr u l es e tf o rd r c b ki s g r e a t l yr e d u c e d ，a tt h es a m et i m e ，c l a s s i f i c a t i o n p e r f o r m a n c eo f d r c b ki si m p r o v e dal i t t l e c u ik e b i n ( c o m p u t e r a p p l i e dt e c h n o l o g y ) d r i e c t e db y p r o f h a nf e n g d i r e c t e db yp r o f l iz h a n h a i k e yw o r d s ：d a t a m i n i n g ，s v m ，b o o l e a n k e r n e lf u n c t i o n 声明 本人郑重声明：此处所提交的硕士学位论文分类分析的研究与实现一 利用s v m 构造决策规则分类器，是本人在华北电力大学攻读硕士学位期间， 在导师指导下进行的研究工作和取得的研究成果。据本人所知，除了文中特 别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得华北电力大学或其他教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 学位论文作者签名 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学 校有权保管、并向有关部门送交学位论文的原件与复印件；学校可以采用 影印、缩印或其它复制手段复制并保存学位论文；学校可允许学位论文被 查阅或借阅：学校可以学术交流为目的，复制赠送和交换学位论文；同意 学校可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：糊 导师签名：鍪扭 日期：! ! ：羔! f日期：2 1 1 - 堇二! ：l 华北电力人学硕十学位论文 第一章引言 随着计算机技术的发展，计算机对数据的存储、管理能力迅速增长，促进了商 业和政府事务的信息化，产生了大量的数据，特别是因特网兴起后，因特网上的信 息更是按指数级增长。 大量数据的出现，造成了“数据丰富，但信息贫乏”的情况。丰富的数据要求 强有力的数据分析工具对其进行分析，数据挖掘技术应运而生。分类是数据挖掘的 主要内容之一，而专门针对文本进行分类的文本分类则更是数据挖掘领域的研究热 点问题。文本分类是信息检索中的一个重要领域，近年来在文本检索，搜索引擎， 信息过滤等方面得到了广泛的应用。本文所作研究主要针对文本分类，为了研究本 文提出的分类器的可扩展性，对非文本分类也有所涉及。 1 1 数据挖掘 数据挖掘( d a t am i n i n g ，d m ) 就是从存放在数据库、数据仓库或其它信息库 中的大量数据中挖掘有用知识的过程“j 。许多人认为数据挖掘就是知识发现 ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e k d d ) ，也有人认为数据挖掘只是数据库中知识 发现过程的一个基本步骤。 数据挖掘融合了数据库、人工智能、机器学习、统计学等多个领域的理论和技 术，能够对将来的趋势和行为进行预测，从而很好地支持人们的决策。 数据挖掘的任务一般可以分为两类：描述和预测。描述性挖掘的任务是找到 能刻画数据的一般特性的模式，包括聚类分析，关联分析等。预测性挖掘的任务是 在当前数据的基础上进行总结和推断，以进行预测，包括分类分析，回归分析等。 在机器学习领域，有时也将描述性挖掘称为无监督学习，将预测性挖掘称为有监督 学习。 ( 1 ) 分类分析 设有一个数据库和一组具有不同特征的类别( 标记) ，该数据库中的每一个记录 都赋予一个类别的标记，这样的数据库称为示例数据库或训练集。分类分析就是通 过分析示例数据库中的数掘，为每个类别做出准确的描述或建立分析模型或挖掘出 分类规则，然后用这个分类规则对其它数据库中的记录进行分类。目前已有多种分 类分析模型得到应用，其中几种典型模型是线性回归模型、决策树模型、决策规则 模型和神经网络模型。 ( 2 1 关联分析 1 华北电力犬学硕士学位论文 关联分析，即利用关联规则进行数据挖掘。在数据挖掘研究领域，对于关联分 析的研究开展得比较深入，人们提出了多种关联规则的挖掘算法，如a p r i o r i 、 s t e m 、a i s 、d h p 等算法。关联分析的目的是挖掘隐藏在数据间的相互关系。 ( 3 ) 聚类分析 与分类分析不同，聚类分析输入的是一组未分类记录，并且这些记录应分成几 类事先也不知道。聚类分析就是通过分析数据库中的记录数据，根据一定的分类规 则，合理地划分记录集合，确定每个记录所在类别。它所采用的分类规则是由聚类 分析工具决定的。聚类分析的方法很多，其中包括系统聚类法、分解法、加入法、 动念聚类法、模糊聚类法、运筹方法等。采用不同的聚类方法，对于相同的记录集 台可能有不同的划分结果。 f 4 ) 回归分析 在分类分析中，预测的结果是离散的，在回归分析中，预测的结果是连续的( 数 字的) ，它用属性的历史数据预测其未来趋势。在简单情况下，可以用标准的统计 方法，如线性回归等来进行回归分析。但是，现实应用中往往是非线性问题，如股 票的涨跌，产量预测等，预测受到许多因素的影响。回归分析的目的就是准确的预 测这总趋势。有些技术可以用于分类分析，也可以用于回归分析，如支持向量机 ( s u p p o r tv e c t o rm a c h i n e ，s v m ) 1 2 】【2 2 2 6 1 。 1 2 文本分类 文本分类就是要建立一个分类模型，然后利用这个模型将未知类别的文本文档 分类到个或多个预定义的类别中1 3 】。自动文本分类的历史可以追溯到上个世纪6 0 年代，但直到上个世纪9 0 年代早期，各种电子文档的大量出现，它才成为研究的 热点。 典型的文本分类是一个两步的过程。第一步利用训练数据集建立一个分类模型， 这一步的关键技术是提取有效特征，以及用这些特征来建立模型；第二步是用已建 立的模型对未知类别的文档分类。 早先的文本分类是基于知识工程的方法，这种方法需要人工来构造分类器，既 费时又费力，所以在2 0 世纪9 0 年代出现了基于机器学习的方法来构造分类器。现 在已经提出了许多机器学习的方法用来构造文本分类器。当前用于文本分类的主要 技术有：概率统计方法【4 “ ，决策树( d e c i s i o nt r e e ，d t ) 1 7 】【8 1 ，决策规则( d e c i s i o n r u l e ) 9 1 1 1 ，回归模型( r e g r e s s i o nm o d e l ) t 12 1 ，神经网络( n e u r a in e t w o r k ，n n ) j 3 】，k 最 近邻居( k n e a r e s tn e i g h b o r ，k - n n ) ”，支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 等。 其中s v m ，k n n 是性能比较优秀的分类器。 近年来出现了将关联规则用于文本分类的分类器( l b 1 4 1 ，a r c b c 1 5 1 1 6 1 ) ，称 2 华北电力大学硕士学位论文 作关联分类器( a s s o c i a t i v ec l a s s i f i e r ) 。关联分类器最初出现于非文本分类领域， 1 9 9 8 年b l i u 等人提出了种将关联规则用于分类的框架”1 ，并实现了用关联规则 进行分类的c b a 分类器。其后又有人相继提出了c m a r 18 1 ，c a e p l l 9 分类器。 自从六十年代开始研究文本分类以来，人们已经将文本分类的相关技术应用到 了很多领域，主要应用有： ( 1 ) 电子邮件分类 主要应用于垃圾邮件的自动辨识、过滤，以及对用户的电子邮件进行分类。 比如：每天发给政府机关的电子邮件，由分类系统辨认出其类别，再转发给税 收、环保、家居、教育等相关部门的负责人进行处理。 f 2 1 电子会议 电子会议是一种新兴的会议方式，与会者通过网络举行会议。会议进行中 可以产生大量的意见和建议，由分类系统对这些信息进行分类和组织，以做成 会议结论。 ( 3 ) 文本信息过滤 针对不同的用户，制定其阅读兴趣。根据不同的阅读兴趣，对信息进行过 滤，剔除不符合用户阅读兴趣的信息。 ( 4 ) 为信息检索服务 信息检索系统必须管理大量的数据，其文本信息库是相当庞大的。文本分 类系统的目的是对文本进行有序的组织，把相似的或相关的文本组织在一起。 它作为知识的组织工具，为信息检索提供了更高效的搜索策略和更准确的查询 结果。 文本分类的应用很多，这里不再一一赘述。 1 ，3 问题的提出 分类分析是数据挖掘的重要问题，其目的是将样品自动的分类到几个预先定义 的类别中去。目前，比较典型的用于分类分析的分类算法包括：贝叶斯、决策树、 神经网络、支持向量机、决策规则等。 其中，s v m 是种基于结构化风险理论的分类器，具有优秀的分类性能。s v m 包括线性s v m 和非线性s v m 。s v m 的分类模式可以看成是问题领域各个属性值 权重的线性和，但人类专家无法获得更细节的知识；使用r b f ，s i g m o i d 核函数 时，s v m 的分类模式是无法理解的。而在门诊信息分类等应用中，可理解的分类 模式对人类专家来说是非常有用的：一方面，人类专家可以从分类模式中学习到知 识；另一方面，人类专家可以将自己的知识体现到分类模式中，从而进一步提高分 类器的准确度i l ”。 3 华北电力人学硕士学位论文 我们在 2 1 中提出几种布尔核函数，可以用于s v m 进行分类分析。使用布尔核 函数，可以将输入空间中的每维看作一个布尔文字，这样，高维特征空间中的每 一维就可以看作输入空间中若干布尔文字的合取范式。可以将重要的合取范式挖掘 出来作为分类规则。这些分类规则是由若干布尔文字组成的，便于人类专家理解。 本文中，我们在s v m ( 使用我们提出的布尔核函数) 构造的超平面上挖掘分类规 则，构造出具有如下特点的分类器d r c b k ( d e c i s i o nr u l ec l a s s i f i e rb a s e do n b o o l e a nk e r n e l ) ： ( 1 ) 基于结构化风险理论，具有较高的准确度 ( 2 ) 分类模式可以为人类专家所理解 同时，针对d r c b k 产生的规则集比较大的问题，我们提出了一种规则集筛选算法 一加权s v m 法线规则集筛选算法，d r c b k 采用该算法后，规则集大小可明显的 减少，分类性能也稍有提高，有效的消除了噪声。 本文的研究工作得到了国家自然科学基金的部分资助。 基金名：对象关系技术对o l a p 支持的研究基金号：6 0 0 7 3 0 5 5 1 4 本文的组织结构 本文的其余部分组织如下： 第二章，介绍了文本分类中的一些基本概念及主要的分类技术和评价标准； 第三章，对本文中d r c b k 使用的四种布尔核函数做了简单的介绍，然后详细 论述了我们提出的d r c b k 的设计流程； 第四章，讨论了特征筛选算法，针对d r c b k 的规则集较大的不足，提出了一 种有效筛选规则集的规则集筛选算法一加权s v m 法线规则集筛选算法： 第五章，给出了d r c b k 的分类实验结果以及利用加权s v m 法线规则集筛选 算法改进后的d r c b k 的分类实验结果，同时对这些实验结果进行了分析、评 价； 第六章，对本文做了总结并展望了将来的工作。 4 华北电力人学硕十学位论文 第二章文本分类 本章主要讲述文本分类的一些基本概念。2 1 节给出了文本分类的定义；2 2 节 讨论在文本分类中如何表示个文档；2 3 节介绍了当前用于文本分类的一些主要 技术，详细介绍了本文中使用的s v m ；2 , 4 节对文本分类器的评价标准作了简单介 绍。 2 1 文本分类的定义 简单地讲，文本分类就是运用机器学习( m a c h i n el e a r n i n g ，m l ) 、知识工程 ( k n o w l e d g ee n g i n e e r i n g ，k e ) 或其它方法来建立一个分类模型，然后利用这个模 型将未知类别的文本文档分类到一个或多个预定义的类别中。【3 】给出了文本分类的 形式化定义。 文本分类就是将一个二元组 d c 映射到一个布尔值的任务。其中d 是我们所讨论的文档的集合，c = c l ，c ：，) 是预先定义的类别的集合。如果将二 元组 映射为值t ( t r u e ) ，则认为文档t 属于类别c j ，否则认为文档嘭不属 于类别c 。 更形式化地说，假设有个未知的目标函数面：d c _ r ，f ，这个函数能够将任 意一个文本准确地分类。文本分类就是要找到一个函数o ：d c 呻 r ，毋使得它的 结果能够尽可能地与西接近。 根据应用的需要可以给文本分类加以不同的约束。例如我们可能需要这样一个 分类器，对给定的整数k ，每个文档d d 需要分类到c 中的七个不同的类别中。k = 1 时，即一个文档只能分给一个类别，这样的分类我们称为单类别分类，而如果个 文档可以分给c 中的任意个类别，这样的分类称为轰类别分类。单类别分类的一个 特例就是二值分类，即对任意一个文档d ，d 要么属于类别c ，要么不属于类别c ， ( 这时属于类别f 的补集巧) 。 从理论的观点来看，二值分类( 同时也是单类别分类) 比多类别分类更为通用。 这是因为一个二值分类的算法也可以用于多类别分类，只需将类别集 5 华北电力人学硕十学位论文 c = c 。，c ：，c 上的多文档分类问题转变为l c l 个独立的在类别集b ，e ) 上的二值 分类问题。但是这样做的前提条件是c 中的各个类别必须是随机独立的，即对c 中 的任意两个类别c 和c ”，o ( d ，c 1 ) 的值不依赖于面( d ，c ”) 的值，反之亦然。然而反 过来一个多类别分类的算法不能够用于二值分类和单类别分类。这是因为，给定一 个待分类文档d ，多类别分类算法可能将其分类到k 1 个类别中，很难从这k 个类 别中选择个最合适的类别来用于单类别分类。另外多类别分类可能根本就没有将 d 分类到任何类别中，这时也很难从类别集合c 中选择一个类别分给d 使其适用于 单类别分类。 在本文中，我们将类别集c = 码，c ：，q 。 上的分类问题看作是l c i 个独立的二值 分类问题，为c 中的每一个类别c ，( i = 1 , 2 ，l c j ) 构造二值分类器m ，：d 斗 7 1 ，乃。 2 2 文档的表示 原始的文本不能够被分类器构造算法和分类器直接处理，所以需要将文本进行 某种处理，以分类器构造算法和分类器能够处理的形式表示出来。在文本分类领域， 一个文档d j 通常由一个带权重的特征向量来表示，即 2 其中，f 是特征集，0 s u ，1 表示特征以在多大程度上代表了文档砖的语义。 对这种表示方法，有两个问题需要考虑： ( 1 ) 如何表示一个特征； ( 2 ) 如何计算特征的权重。 对第个问题来说，通常的做法是用一个单词来表示一个特征。这种表示方法 称为单词集( s e to f w o r d s ) 方法或单词包( b a go f w o r d s ) 方法( 具体地讲，如果权重只 能取0 和i ，则称为单词集方法否则称为单词包1 3 ) 。另外也有人用词组( p h r a s e ) 作为特征。用词组作为特征时，有两种定义一个词组的方法：一种是根据语法信息， 即在语法上有一定联系的多个单词认为是一个词组；另外一种是根据统计信息，即 认为多个频繁地同时出现的单词序列或单词集合是词组。 对第二个问题，权重一般在0 到1 之间取s 值。一种特例就是布尔权重，即w k i = 1 表示特征五在文档巧中出现，而= 0 表示特征五在文档屿中朱出现。使用布尔权 重还是非布尔权重取决于分类器学习算法。使用非布尔权重时，如何来决定w i ，的 值有很多种方法。通常使用驴矽函数。特征五对于文档西的驴矽定义为： t r l t f i d f ( f ，哆) 。4 ( 五，t ) 1 0 9 # ir 1 ( r ，i 。j ( 21 ) 6 华北电力大学硕士学位论文 其中，群( 五，j ，) 表示特征五在文档巧中出现的次数， n ( 五) 表示特征五的文档 频率( d o c u m e n t f r e q u e n c y ) ，即训练集t r 中包含特征五的文档数，i n l 表示训练文 档集中包含的文档数。由公式( 2 1 ) 可以看出，这个定义体现了以下两点： ( 1 ) 某个特征在一个文档中出现的次数越多，它就越能代表这个文档的内容； ( 2 ) 包含某个特征的文档数越多，这个特征就越不具有分类的能力。 需要注意的是这个公式只考虑了特征在文档中出现的次数，并未考虑特征在文 档中出现的位置，顺序，及句法等信息。 为了使权重落在【o ，1 的区间范围内，并且为了使文档以相同长度的向量来表示， 需要将所珊得到的结果进行规范化处理，通常用余弦规范化： m ： 丝丝! 丝：鱼! ( 2 2 )m= ；= = = = = = = = = = = = = ! = = = = = = = f z z ) ：( 驴( 工，嘭) ) 2 2 3 分类技术 在2 0 世纪8 0 年代，文本分类系统主要是基于知识工程( k n o w l e d g ee n g i n e e r i n g ， k e ) 的方法的，这种方法需要由人类专家来手工构造分类模型。到2 0 世纪9 0 年代 早期，机器学习( m a c h i n el e a r n i n g ，m l ) 方法渐渐流行起来并至少在研究领域占 据了主导地位。 现在，大多数的文本分类器是基于机器学习方法的。当前用于文本分类的主要 技术有：概率统计方法，决策树，决策规则，回归模型，神经网络，k 最近邻居， 支持向量机等。其中s v m ，k 一最近邻居是性能比较优秀的分类器。本文中，主要研 究的是s v m ，下一节我们将简要的介绍一下s v m 。 2 4s v m s v m 是一种基于统计学习理论的机器学习算法。它产生于模式识别问题，s v m 作为统计学习理论所提出的一种可以直接付诸实践的机器学习方法，体现了s r m 归纳原则的基本思想，在应用中优于其它学习算法，获得了巨大的成功。本节首先 介绍统计学习理论和s r m 原则，然后对s v m 进行系统的介绍。 2 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 7 1 是v a p n i k 等人在7 0 年代末提出 并在9 0 年代逐渐完善的一种针对小样本的机器学习理论。它的核心问题是寻找 种归纳原则以实现最小化风险泛函，从而实现最佳的推广能力。 7 华北电力人学硕士学位论文 以往机器学习理论的核心是经验风险最小化原则( e r m ) 。如果以大量的样本 进行训练，并且能找到一个相当逼近这些样本的函数，那么它可望对工作样本作出 较准确的预测。这反映了大样本统计学对渐进特性的依赖。6 0 年代的很多学者认 为使学习机器具有好的推广能力的唯一因素就是使它在训练集上的误差最小，因此 e r m 原则似乎是不证自明的。但事实上，如果学习机器能力( c a p a c i t y ) 过强，能 够无误差地适应任意的训练样本( 过适应现象) ，就会导致科学哲学中不可证伪的 情况。这是因为它所采用的函数集过于复杂，对任何i j t l 练样本都保持高精度的辨识 能力，这本身就蕴含着对工作样本所作预测的不可靠性。v a p n i k 提出了v c 维的概 念来标志函数集的复杂程度( 迄今为之还没有人提出更好的概念来标志这种复杂 性) ，并用这个概念给出了与分布无关的学习机器推广能力的界，有关v c 维的详 细论述请参阅 2 7 4 6 。也就是说，按e r m 原则构造的学习机器在给定的样本数量 下实际风险将会在这个界的范围内。这个界由两部分构成：经验风险和置信范围( 以 v c 维为参数) 。学习机器能力过强( v c 维很大) ，虽然能取得小的经验风险，但 簧信范围会很大；v c 维太小又会导致大的经验风险。一个好的归纳原则必须在二 者之间作出权衡。 结构风险最小化原则( s r m ) 正是这样- - * 0 归纳原则。该原则首先定义了一种 函数集的嵌套结构： s tcs 2c cs nc 这些函数集的v c 维从小到大排列，这样函数集的v c 维就成为了可控参数。对一 个给定的训练集，s r m 原则在使风险上界最小的子集s k 中选择使经验风险最小的 函数。 s r m 原则定义了在对给定数据的逼近精度和逼近函数的复杂性之间的种折 衷。 s r m 的一般原则可以用不同的方法实现。在实际的算法中，神经网络是通过 选择一个适当构造的机器来保持固定的置信范围并最小化经验风险：支持向量机是 保持经验风险固定并最小化置信范围。 2 4 2 线性s v m 为了使本文表达清晰、一致，本文中使用的符号含义都遵循表2 1 所示 表2 1 本文符号约定 l符号意义 l x向量j 华北电力大学硕士学位论文 x j向量x 的第i 个分量 一 x j矩阵的第i 个列向量 一 x ：一i 向量贾，的第，个分量 y数值y 对于由d 个样品构成的训练数据集 贾，m ，i = 1 ，2 ，d ，j ，月”表示一 个样品；y ， + l ，一1 表示该样品所属的类别；儿= + 1 时，称置为正例样品，y ，= 一l 时，称牙为负例样品。 线性s v m 基本思想可用图2 1 的两维情况说明。图中，o * n x 代表两类样本，h 为 分类线，h 。、h 2 分别为过各类中离分类线最近的样本且平行于分类线的直线，它 们之间的距离叫做分类间隔( m a r g i n ) 。所谓最优分类超平面就是要求分类线不但 能将两类正确分开( 训练错误率为o ) ，而且使分类间隔最大，此时h l ，h 2 上的训练 样本点就称为支持向量( 2 8 1 。样品x 所在的空间称为输入空间，线性支持向量机通过 在输入空间中构造最优超平面c 阿，彳) + b ：0 来分隔正例、负例样品数据，这里“ ” 表示向量之间的内积；r 一，b r ，使得： y 。k ，x ，) + 6 j 一1 0 i = 1 , 2 ，d( 23 ) 图2 1 线性支持向量机 可以证明，在输入空间中使去9 矽0 2 最小的分类面就是最优分类面f 2 8 l 。求解这个 问题是通过拉格朗日( l a g r a n g e ) 优化法将该问题转换成其对偶问题，也就是转化成 在约束： d y j t 2 i = 0 f = 1 , 2 ，d ( 2 4 ) 1 = 1 下求解： 9 华北电力大学硕士学位论文 q ( a ) = a r g ，a x 窆q 一告主窆口一y , y j ( 2 , ，置) ( 2 5 ) “ ，= 1i = i 瞄为原问题中每个约束条件( 2 4 ) 对应的l a g r a n g e 乘子。这是一个不等式约束下 二次函数寻优的问题，存在唯一解。容易证明，解中将只有一部分( 通常是少部分) 口不为零，对应的样本就是支持向量。解上述问题后得到的最优分类函数是： 厂( z ) = s g n ( q y ，( 置，) + 6 ) ( 2 6 ) 其中：式中的求和实际上只对支持向量进行。b 是分类阈值，可以用任一个支持向 量( 满足公式2 4 中的等号) 求得，或通过两类中任意一对支持向量取中值求得。 b = y ，一刚，( 贾，贾，) 要求0 。( 2 7 ) 这旱，s g n 0 是符号函数。 2 4 3 非线性s v m 通过非线性变换( n o n l i n e a rm a p p i n g ) 可以将输入空间的向量变换成另一个高 维的空间中的向量，该空间称为特征空间。特征空间比输入空间具有更高的维度。 圈2 2 非线性支持向量机 非线性s v m 通过非线性变换矿将输入空洲的向量转换成高维特征空间中的向 量( 如图2 2 ) ，并在特征空间中构造最优超平面： ( w ，尹( 别+ b = 0( 2 ，8 ) 来分隔正例、负例样品数据。这里，是高维特征空间中的向量，b r ，“( ，) ” 表示计算向量之间的内积。使得： y 。，妒( 牙，) ) + h i + 鼻一1 - 0 # ，o f = 1 ，2 ，d ( 2 9 ) 1 0 华北电力人学硕士学位论文 可以证明，在特征空间中使 i i 矿0 2 + c f 量善j 最小的分类面就是最优分类面【2 8 j ， i = 1 其中c 0 是个常数。同线性s v m 类似，求解这个问题也是通过拉格朗日( l a g r a n g e ) 优化法将该问题转换成其对偶问题，也就是转化成在约束： y ，= 0 0 吼c i = 1 ，2 ，d( 2 1 0 ) 下求解： q ( a ) = a r g m a x 兰q 一丢兰兰o t y i y j ( ( j ，) ，妒( 牙脚 ( 2 1 1 ) 求解后，可以得到最优分类函数为： 厂( ) = s g n ( a , y ，( 妒( 贾，) ，( 工) ) + 6 ) ( 2 1 2 ) 其中： 6 = y ，一妻口，儿( 妒( 尼) ，矿( 置) ) 要求吒o( 2 1 3 ) 以上公式中，在计算超平面和分类函数时，需要明确给出在特征空间中计算向 量内积的函数。在高维特征空间中计算向量点积的函数，称为核函数。只要明确给 出了核函数，并不需要显示的给出从输入空间到特征空间的非线性变换，就可以 在特征空间计算向量的内积。 2 5 分类器评价标准 相对于文本搜索系统来说，文本分类器的性能评价更多的是经验性的，而不是 分析性的【3 】。这是因为要分析性地评价一个系统，比如证明一个系统的正确性和完 备性，必须能够对这个系统所要解决的问题给出一个形式化的表述，然而由于文本 分类的主观性( 比如一个文本是否属于某一类别带有很大的主观性，两个不同的专 家可能将其归类到不同的类别中) ，在本质上不能给出一个形式化的表达，所以要 分析性地对分类器进行评价( 比如证明这个分类器是正确的) 是不可能的。 要对一个文本分类器进行性能测试，有两种方法：h a n d o u t 方法和k 折交叉验 证法，这两种方法都要将原始文档集分割为训练文档集和测试文档集。对性能评价 的主要指标有查全率( r e c a l l ) 和查对率( p r e c i s i o n ) ，另外有综合这两种指标的b e p 和凡。下面详细介绍这些测试方法和评价标准。 华北电力r 人学硕士学位论文 2 5 1 训练集和测试集 机器学习方法中，首先通过观察一个预先被正确分类的文档集的特征自动建立 一个分类器。这些文档集中的文档是由些领域专家手工分类的。然后对一个未知 类别的文档，根据其是否包含这些特征来对其分类。用机器学习的术语来讲，分类 问题是一个有监督学习( s u p e r v i s e d l e a r n i n g ) 的过程，因为学习过程是在关于类别 和属于这些类别的调练实例的知识的监督之下进行的。 基于机器学习的文本分类方法依赖于一个初始文档集q = d id ：，) c d ，其 中的文档已经被预先分类到有i c l 个类别的集合c = c l ，c ：，c 。) 中。就是说对于函 数面：d c 一 7 ，f ) ，所有的值对 q c 的值都是已知的。如果 西( d ，q ) = t ，那么称文档d j 是类别c ，的一个正例文档，如果西( d ，q ) = f ，则称文 档d ，是类别c ，的一个负例文档。简单地酷属于类别c ，的文档就是c 。的正例文档，不 属于c 的文档就是它的负例文档。 在研究领域，当一个分类器中建立起来后。就要对其进行性能评价。在这种情 况下，在建立分类器之前就应该将原始的文档集分为两部分，这两部分不一定要包 含相同数目的文档。 一部分称为训练验证集( t r a i n i n ga n dv a l i d a t i o ns e t ) ，丁y = d l ，d 2 ，d l i ) 。类别 集c = c 。，c ：，c 。| ) 上的分类器。就是通过观察这个集合中的文档的特征建立起来 的。 另外一部分称为测试集( t e s ts e t ) ，t e = d 1 7 ，叫d q ，这个集合用来测试分类 器的性能。每个文档d ，t e 输入给分类器，然后将分类器的分类结果中( d ，c ，) 与领 域专家的结果西( d ，c ) 相比较。根据比较结果来计算分类性能度量标准的值，以此 来评价分类器的性能。 测试集死中的文档不能参与分类器的归纳构造过程。如果不满足这个条件，实 验结果是不可信的，性能评价的结果也就不具有任何科学意义。在实际的应用领域， 在评价过分类器的性能之后，可以在整个原始文档集上重新训练这个分类器，以提 升分类器的性能。在这种情况下，前面对分类器性能的评价可能要差于分类器的实 际性能，因为最终的分类器是在更多的数据上进行训练的。 以上这种方法称作h a n d o u t 方法。还有一种叫k 折( 轮) 交叉验证( k - f o l dc r o s s v a l i d a t i o n ) 的方法【舶。在k 折交叉验证法中，原始文档集被分为k 个不相交的集合 n ，死：，扎k ，然后以丁= q t e ，为训练集，以t e ，为测试集反复运用训练测试法， 建立k 个不同的分类器中，o ，中。最后评价分类器的性能时，首先计算各个分类 1 2 华北电力大学硕士学位论文 器的性能，然后以某种方法得到k 个分类器性能的平均值，就是最终的分类器m 的 性能。 2 5 2 查全率和查对率 在文本分类研究领域，般使用查全率( r e c a l l ) 和查对率( p r e c i s i o n ) 来衡量分类 器的性能。 我们来看看表2 。2 。在表2 2 中，配表示测试文档集中本来属于类别c ，而且被分 类器分类到类别c ，的文档数，川表示测试文档集中本来不属于类别c ，但被分类器错 误分类到类别c ，的文档数，刷，表示本来应该属于类别q 但被分类器分类到别的类 别的文档数，而州，表示本来不属于类别c ，而且也没有被分类器分类到类别c 。的文 档数。 表2 2 人类专家识别 类别c 正例负例 分类器识f 例t p if p i 别负例 f n it n i 根据表2 2 ，分类器在类别上的查全率( r e c a l l ) 定义如下： r e c a f ：亲 ( 2 1 4 ) 。t p + f n ? 1 而在类别c ，上的查对率( p r e c i s i o n ) 定义如下 胁c 嘲：未 ( 2 1 5 ) j t p + f p 、。 由以上的定义可以看出，查全率就是一个文档d 应该属于类别c ，而分类器也 确实将其分到类别t 的概率，查对率就是随机文档d 被分类器分类到类别c 。而且这 个决策正确的概率。用逻辑学的术语来讲，查全率考查的是分类器的完备性 ( c o m p l e t e n e s s ) ，而查对率考查的是分类的正确性( s o u n d n e s s ) 。 以上的定义都是针对某个类别c ，的，所以这些指标只能代表局部意义。而为 了在全局意义上来评价分类器，就必须考虑所有的类别，有两种方法来综合所有类 别的查全率和查对率，即宏平均( m a c r oa v e r a g i n g ) 和微平均( m i c r o a v e r a g i n g ) 。 表2 3 l类别集人类专家识别 lc = 弛，c 2 。，q c i 正例负例 1 3 华北电力人学硕士学位论文 j c jl c j 正例 t p = 邛即= 川 分类器识 别 旧 i t f 负例 f n = f n it n = 烈 参考表2 3 ，查全率和查对率在所有类别上的微平均可以定义如下： 胁胁洲= 一t p = 蒜z i c i 宏平均定义如下 2 5 3b e p 和f m i c a v g p r e c i s i o nt p 一2 邛 即+ 即2 ( 础+ 川) m a c a v g 一，= 骅 坳叫v g _ p r e c i s i o n ：娑, = 1v r 警e c l s l o i q i ( 2 1 7 ) ( 2 1 8 ) ( 2 1 9 ) 事实上，前一节所介绍的查全率和查对率不是独立的。比如某一个分类器将所 有的测试文档都分类到类别c ，如果单纯地考虑查全率，这个分类器的性能将很完 美，因为这时候其查全率： r e 刊= 磊= 蒜= 署_ 1(220)0 j t p j f n j1 p j 七t p j j 即，查全率是1 0 0 ，这显然是不合理的，因为这时候查对率可能很低。所以需要 有一种综合考虑查全率和查对率的方法来对分类器进行评价。现在已经提出了不少 这样的方法，比如e l e v e n - p o i n ta v e r a g ep r e c i s i o n ，b r e a k e v e np o i n t ，兄f u n c t i o n 等。 常用的有b e p ( b r e a k e v e np o i n t ) 和b 函数。下面介绍这两种方法。 b e p 就是使得查全率和查对率取得相等值的点( 3 1 。严格地来讲，b e p 的计算是 比较复杂的，为了便于计算，通常都采用查全率和查对率的算术平均值来代替b e p 的值，即对某一个类别c ，我们定义 砸只：r e c a l l _ + - p r e c i s i o n s( 2 2 1 ) 同样对于b e p 有宏平均和微平均两种全局化方法。分别定义如下： y “1b e 尸 m a c a v g b e p = 鱼爷 ( 2 2 2 ) 华北电力大学硕士学何论文 脚鲥增一b e p ：些型掣 ( 2 2 3 ) 兀函数由v a nr i j s b e r g e n 在1 9 7 9 年首先提出使用，综合考虑了查全率和查对率 两种指标，f p 定义为： f p ：( f l 了2 + i 1 ) r e c a l l * p re c i s i o n ( 2 2 4 ) 口。p r e c i s i o n + r e c a l l 其中o 卢+ 。可以看作是对查全率和查对率的相关度。当= o 时，0 就与查对率 ( p r e c i s i o n ) 一致，而当= + o 。时，f p 与查全率( r e c a l l ) 一致。即取值越大越 强调查全率( r e c a l l ) 的重要性，而取值越小越强调查对率( p r e c i s i o n ) 的重要 性。一般情况下，平衡这两个指标，耿= 1 ， 为常用的e 。对于类别c ，其e ，定义为： 耻畿糍 使它们的重要程度相同，这时凡就 ( 2 2 5 ) n f 4 对- 7f 有宏平均和微平均两种全局化的方法，定义如下： m a c a v g 辟骅 2 6 ， 2 5 4 准确率( a c c u r a c y ) 前几节介绍的评价标准主要针对文本分类，对于非文本分类而言，主要采用准 确率( a c c u r a c y ) 来评价分类器的性能。为了表述方便，我们参看2 5 2 节的表2 3 ， 对准确率做如下的形式化定义： a c c u r a c y ： ! 型 ( 2 2 7 ) 2 t p + f p + f n + t n l z z ，j 其中，t p + f p + f n + t n 表示测试集中总的测试文档数，t p + t n 表示分类器正确识别 的测试文档数。a c c r u a c y 比较直观的描述了分类器分类性能的一个评价标准，显然， a c c r u a c y 越大，则表明我们的分类器的分类性能越好，反之，则越差。 2 6 小结 本章主要内容包括： 文本分类的概念，用形式化的方法给出了文本分类的定义，即文本分类就是一 个映射关系：o ：d x c 斗 t ，f ) 。文本分类的主要p f 壬务就是将一些末知类别的文本 文档自动分类到预先定义好的类别中。 1 5 华北电力人学硕七学俯论文 在文本分类鞭域，一个文本文搭表示蠹一令姆禚商艇，可以鼹穗短程交毯中魄 出现与否，以及出现的次数等来描述一个文本。 警蓠嗣予文本分类静主要技零嘉委时颠、抉蘸鼹( d e c i s i o nt r e e ) 、耱经勰络 ( n e u r a l n e t w o r k ) 、最近邻居( k 羽e a r e s t n e i g h b o r ) 和支持向爨机( s v m ) 等。支 替患量辊愚一黎菲露蕊凳蘸分类器，在文本鬻饕文率领域蠹戆努黉往黪帮是菲常蕊 秀的。本文主要的工作都炼针对s v m 所做的，因此，我们在本章还详细