（计算机应用技术专业论文）基于模糊支持向量机的多类文本分类方法研究.pdf

硕士学位论文 摘要 针对文本分类具有类别和样本数目多、噪音多、各类别样本数目不均衡等特 点，将模糊支持向量机方法用于多类文本分类中，提出一种基于模糊支持向量机 与决策树的文本分类器的构建方法。该方法是在考虑了样本与类中心之间距离关 系的同时，根据传统支持向量机中包含支持向量且平行于分类面的平面构建切球， 以此来确定类中各个样本之间的关系，由样本点与球的位置关系计算其隶属度， 合理地区分有效样本、噪音和孤立点样本，并将该方法与二叉决策树方法相结合， 实现多类文本分类。 重点对模糊支持向量机中隶属度函数的确定方法进行深入的分析与研究，针 对目前模糊支持向量机方法中，一般使用样本与类中心之间的距离关系构建隶属 度函数的不足，提出了一种改进的有效地反映样本不确定性的隶属度确定方法一 一基于双超球的隶属度函数。该方法通过样本的类中心与传统支持向量机的分类 面构建两个超球，根据样本点与这两个超球的位置关系计算其隶属度，并且将隶 属度与样本到类中心的距离之间表示成非线性关系。 最后，通过在r u t e r s 一2 15 7 8 文档集上的实验，证明了这两种方法能切实有 效的解决文本分类问题，与传统支持向量机方法和基于样本与类中心点的线性距 离的隶属度函数模糊支持向量机分类方法相比，基于模糊支持向量机与决策树的 文本分类器能够有效区分有效样本和噪音、孤立点样本，有较好的分类效果。在 使用的三种隶属度函数中，基于双超球的模糊支持向量机方法抗噪性能最好，分 类性能最强。 关键词：文本分类；多类分类：模糊支持向量机；隶属度；超球 基于模糊支持向量机的多类文本分类方法研究 a b s t r a c t r e l a t i v et ot h et e x tc l a s s i f i c a t i o ni sc h a r a c t e r i z e dw i t hah i g hn u m b e ro fc l a s s e s a n dt r a i n i n ge x a m p l e sa sw e l la st o om a n yn o i s e sf u z z ys u p p o r tv e c t o rm a c h i n e m e t h o dh a sb e e na p p l i e dt om u l t i c l a s st e x tc l a s s i f i c a t i o i lo n ec o n s t r u c t i o na p p r o a c h o ft e x tc l a s s i f i e rb a s e do nf u z z ys u p p o r tv e c t o rm a c h i n ea n dd e c i s i o nt r e ei sp r o p o s e d t h er e l a t i o n s h i po ft h es a m p l ea n di t sc l u s t e rc e n t e ri sc o n s i d e r e da n dc o m b i n i n gt h e t a n g e n ts p h e r ec o n s t r u c t e db yt h eh y p e r p l a n ew h i c h c o n t a i n st h es u p p o nv e c t o r sa n d p a r a l l e l st h ec l a s s i f i c a t i o nh y p e r p l a n ei nt r a d i t i o n a ls u p p o r tv e c t o rm a c h i n e ，s ot o f u r t h e rd e t e r m i n et h er e l a t i o no fa l ls a m p l e si nt h ec l a s s t h em e m b e r s h i po fo n e s a m p l et oac l a s sc a nb ec o m p u t e db yt h el o c a t i o no ft h es a m p l ei nt h es p h e r e ，s ot h e e f 伍c i e n ts a n l p l e s ，n o i s e sa n do u t l i e r sc a nb ed i s t i n g u i s h e dr a t i o n a l l y i n t e g r a t i n gt h e d e c i s i o nt r e em e t h o d ，t h ec l a s s i 丘c a t i o no fm u l t i c l a s s e si sr e a l i z e d t h em a i nr e s e a r c hi s s u eo ft h i sp a p e ri st h ed e t e r m i n a t i o no ff u z z ym e m b e r s h i pi n f u z z ys u p p o r tv e c t o rm a c h i n e r e l a t i v et o t h ef u z z ym e m b e r s h i pa saf u n c t i o no f d i s t a n c eb e t w e e nt h ep o i n ta n di t sc l a s sc e n t e rf o rs o m ec u r r e n tf u z z ys u p p o r tv e c t o r m a c h i n e s ，an e wa n dm o r ee f f e c t i v ef u z z ym e m b e r s h i pa saf u n c t i o no f t w os p h e r e si s p r o p o s e df 0 rt h em e a s u r e m e n to ft h ei n a c c u r a c yo fs a m p l e s t h er e l a t i o n s h i po f t h e s a m p l ea n di t sc l u s t e rc e n t e ri sc o n s i d e r e da n dc o m b i n i n gt w os p h e r e sc o n s t r u c t e db y t h ec l u s t e rc e n t e ra n dt h ec l a s s i f i c a t i o nh y p e r p l a n ei nt r a d i t i o n a ls u p p o nv e c t o r m a c h i n e ， s ot of u r t h e rd e t e r m i n et h er e l a t i o no fa l ls a m p l e si nt h e c l a s s t h e m e m b e r s h i po fo n es a m p l et oac l a s sc a n b ec o m p u t e db yt h el o c a t i o no ft h es a m p l ei n t h es p h e r e s f i n a l ly ，t h et e s t so nr u t e r s 215 7 8c o r p u ss h o wt h a tt h e b o t hm e t h o d sc a n e f ! f i c i e n t l ya n de f f e c t i v e l ys o l v et h et e x tc l a s s i f i c a t i o np r o b l e m s 。c o m p a r e dw i t ht h e t r a d i t i o n a ls u p p o r tv e c t o rm a c h i n em e t h o d sa n dt h ef u z z ys u p p o r tv e c t o rm a c h i n e s b a s e do nt h ed i s t a n c eo fas a m p l ea n di t sc l u s t e rc e n t e t h ea p p r o a c hb a s e do nf h z z y s u p p o r tv e c t o rm a c h i n ea n dd e c i s i o nt r e ec a nd i s t i n g u i s ht h ee f f i c i e n ts a m p l e s ，n o i s e s a n do u t l i e r sm o r ge f f e c t i v e l y ，a n dh a sp r e f e r a b l ec l a s s m c a t i o ne f 诧c t t h ef u z z y s u p p o r tv e c t o rm a c h i n eb a s e do nt h et w os p h e r e si sm o r er o b u s tt h a nt h et r a d i t i o n a l s u p p o r tv e c t o rm a c h i n e ，a n df u z z ys u p p o nv e c t o rm a c h i n e st a k e nb yo t h e rt w of u z z y m e m b e r s h i p s k e yw o r d s ：t e x tc i a s s i f i c a t i o n ；m u l t i c l a s sc l a s s i f i c a t i o n ；f u z z ys u p p o r tv e c t o r m a c h i n e ；f l l z z ym e m b e r s h i p s ；s p h e r e i i 硕十学位论文 插图索引 图2 1 文本分类流程图5 图2 2 文本的向量空间模型及文本间的相似度6 图2 3 两维线性可分情况1 3 图2 4 支持向量机示意图13 图3 1 不可分区域2 0 图4 1 构造切球的示意图2 6 图4 2f s v m 决策树2 7 图5 1 构造切球的示意图3 3 1 1 1 基于模糊支持向量机的多类文本分类方法研究 表2 1 表4 1 表4 2 表5 1 附表索引 二值分类列联表17 使用线性核函数时六种多类分类方法的凡值比较( ) 2 9 使用多项式核函数时六种多类分类方法的只值比较( ) ，2 9 四种分类方法的几值比较( ) 3 4 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名： 碣洋 ， 1 日期：2 d d 7 年乡月7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学 校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保 存和汇编本学位论文。同时授权中国科学技术信息研究所将本学位论文收 录到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。 作者签名：竭半 导师签名：多础每一 日期：20 0 7 年 日期：k 7 年 石月日 具9b l 硕士学位论文 也就说用什么方法建立从文档特征到文档类别的映射关系，这是文本分类的 核心问题。 5 性能评估模型 即如何评估分类方法和系统的性能或者说分类结果。真正反映文本分类内在 特征的性能评估模型可以作为改进和完善分类系统的目标函数。在文本分类中， 到底使用什么评价参数取决于具体的分类问题。单标注分类问题( 一个测试文档 只属于一个类) 和多标注分类问题( 一个测试文档可以属于多个类) 所使用的评 估参数是不一样的。目前使用比较多的分类性能评估指标为查全率和查准率，这 是来源于信息检索中的两个术语。 图2 1 为文本分类主要步骤的示意图。 文本表示 训练过程 l 一- - - 一1 分类过程 图2 1 文本分类流程图 2 2 文本预处理 在对文本表示之前，需要对文本进行预处理【2 4 1 ，主要包括以下几个内容： 1 去掉一些标记信息，这主要针对网页文件，例如：h t m l 中的t a g 。 2 去除停用词( s t o pw o r d ) ，般这种词不携带任何信息，如中文中的“的 、 “啊”，英文中的“t h e ”，“a ”。 3 词根还原( w o r ds t e m m i n g ) ，该步骤主要用在英文文本分类中，将同词根 的单词映射到一个特征词属性，可以大大减少特征词的个数。 2 3 文本表示 基于模糊支持向量机的多类文本分类方法研究 文本分类器及其构造系统无法直接处理文本文档，因此，构造文本分类器的 首要任务就是将文本文档性质( 文本特征) 定量地表示出来，首先要将文本的有用 信息输入计算机中，为此应对文本进行科学的抽象，建立它的数学模型，从而将 实际的文本文档映射成文本分类器及其构造系统可以处理的数据。用简单而准确 的方法将文档表示成计算机能够处理的形式是进行文本分类的基础。 目前，在信息处理方向上，文本的表示主要采用向量空间模型( v e c t o rs p a c e m o d e ) 。s a l t o n 等在2 0 世纪的6 0 年代提出了向量空间模型并将它成功应用于很多系 统中，比较著名的有s m a r t 系统( s y s t e mf o rt h em a n i p u l a t i o na n dr e t r i e v a lo f t e x t ) 。目前，空间向量模型及其相关技术，如特征项选择、加权策略、相关反馈 等，在文本分类、信息检索和搜索引擎等很多领域都得到了广泛应用，并取得了 较好效果【25 1 。在这种模型中，每一对象模型化为空间中的点，两对象间的差异由 多维空间中两点间的距离表示。 向量空间模型的基本思想是以向量来表示文本： 给定一个自然文本d ( ，；乞，；l ；t ，w ；l 乙) ，由于词f ，在文本中既可以重复 出现又可有先后次序的出现，分析起来相当困难。目前的文本自动分类都不考虑f ， 在文本中的先后顺序，而只要求t 互异。此时我们把 ，f ：，l ，l ，乙看成是一个，2 维 的坐标系，而w 1 ，w 2 ，l ，w ，l ，为对应的坐标值。所以d ( ，m ；乞，w 2 ；l ；r ，w ；l 乙) 被看作是刀维空间中的一个向量( 如图2 2 中的d 1 ，d ，) 。我们称 d ( ，w ；乞，啦；l ；t ，；l 毛) 为文本d 的向量表示或向量空间模型。 两个文本d 1 和d ，之间的相关程度可以用它们之间的相似度来度量。当文本被 表示成向量空间模型时，我们就可以借助向量之间的某种距离来表示文档间的相 似度。夹角余弦是常用的相似度计算方法。 夹角余弦计算公式如下： s f 聊( q ，岛) = c o s p = w l ，w 2 ， ，= 1 ，l ，。) 图2 2 文本的向量空间模型及文本间的相似度 6 ( 2 1 ) 硕士学位论文 向量空间模型有效地解决了非结构化文本数据的处理问题，提高了文本处理 的速度和效率，把对文本的操作转变为对特征向量的操作。 文档向量中每一维对应于文档中的个特征，它的权值为该向量维对应的特 征在文档库中的权值，不同的特征项对文档的重要程度和区分度的影响是不同的， 因此系统在对文本进行形式化处理的时候，需要对特征项进行加权，一般采用 t f i d f 方法计算。该方法基于以下两点原因：一是特征词f 在文档，中出现词数越多 越重要，权重和弘，成正比；二是文档集中含有特征词f 的文档数啦越大越不重要， 权重和啦成反比。公式如下： 耽，= 珥，幸l o g ( 嬲) ( 2 2 ) 该式表明，若特征词! 在所有文档中均出现，即耻= ，则耽。= 0 ，也就是 说，虽然特征词f 出现次数多，但它的分布比较均匀，说明它没有区分类别的能力。 考虑到文档长度的影响，对上面公式进行归一化： 珥，幸1 0 9 ( d f ) 为了降低玩的作用将式( 2 3 ) 调整为： 2 4 特征选择 l o g ( 巩+ 1 o ) 宰1 0 9 ( d f ) ( 2 3 ) ( 2 4 ) 实现文本自动分类的基本困难之一是特征项空间的维数过高。数量过大的特 征项一方面导致分类算法的代价过高，另一方面导致无法准确地提取文档的类别 信息，造成分类效果不佳。因此，需要在不牺牲分类质量的前提下尽可能地降低 特征项空间的维数。特征选择的任务就是要将信窟、量缩小，“不重要”的词汇从特 征项空间中删除，除去特征集中不能较好表示有效信息的特征，从而减少特征项 的个数，以提高分类准确度和减少计算复杂度。它是文本自动分类系统中的一个 关键步骤。 近年来在文本自动分类中使用较多的特征抽取方法包括文档频率d f ( d o c u m e n tf r e q u e n c y ) 、信息增益i g ( i n f o r m a t i o ng a i n ) 、互信息m i ( m u t u a l i n f o r m a t i o n ) 和z 2 统计量c h i ( c h i s q u a r es t a t i s t i c ) 等【2 6 - 2 8 1 。这些方法的基本思想都 是对每一个特征即词条，计算它的某种统计的度量值，然后设定一个阈值丁，把度 量值小于丁的那些特征过滤掉，剩下的即认为是有效特征。 下面对这些典型的特征选择算法做一下简单地介绍。 7 基于模糊支持向帚机的多类文本分类方法研究 2 4 1 基于文档频率的特征选择d f 一个特征的文档频率是指在文档集中含有该特征的文档数目。采用d f 作为特 征选择，基于如下基本假设：d f 值低于某个阈值的词条是低频词，它们不含或含 有较少的类别信息。将这样的词条从原始特征空间中除去，不但能够降低特征空 间的维数，而且还有可能提高分类的精度。文档频率是最简单的特征抽取技术， 由于其相对于训练语料规模具有线性的计算复杂度，它能够很容易被用于大规模 语料统计。而在信息检索研究中通常却认为d f 值低的词条相对于d f 值高的词条具 有较多的信息量，不应该将它们完全移除。不同的应用将对d f 值的认识不同，因 此应根据具体情况来选择该方法。 2 4 2 基于信息增益的特征选择i g 信息增量表示文档中包含某一特征值时文档类的平均信息量，在机器学习领 域被广泛使用。它定义为某一特征在文档中出现前后的信息嫡之差。假设q ，巳，气 为尼个类别，特征w 的i g 计算公式为： 佑( 叻= - 尸( 巳) 1 0 9 尸( 巳) + 尸( 尸( 巳i 计l o g 尸( 巳i + 尸( 访) p ( 巳l 回l o g p ( c ，l 劝( 2 5 ) 其中，p ( c ) 为属于类c ，的文档在总集合中的比例，p ( w ) 为出现特征w 的文档 在总集合中的比例。另外，尸( c ，1w ) 为包含特征w 的文档在类c ，中的比例。尸( c f | 访) 为不出现特征w 的文档在类c 中的比例。i g 算法的计算复杂度为d ( 剧) 。 i g 方法需要对训练集中的每个特征进行统计，同时将小于阈值的特征删除。 这种缩减维数的算法能够充分利用特征在不同文档和类别中的分布情况。 2 4 3 基于互信息的特征选择m i 互信息是用于表征两个变量间相关性的，在统计语言模型中被广泛采用，m i 越大，共现程度越大。使用以下公式计算某个特征项f 与类别c 之间的相关性： m l o g 两 ( 2 6 ) 其中，彳为，和c 同时出现的次数；b 为，出现而c 没有出现的次数；c 为c 出现而f 没有出现的次数。为所有文档数。如果f 和c 不相关，则，( f ，c ) 值为0 。如果有，z 个 类，那么对于每个，都会有聊个值，取它们的平均，就能得到特征选取所需的一个 线性序列。闩z 均值大的特征优先被选取。互信息算法的计算复杂度也为0 ( 剧) 。 2 4 4 基于z ：统计量的特征选择c h i z 2 统计也是用于表征两个变量间的相关性，但它比互信息更强，因为它同时 考虑了特征存在与不存在时的情况。z 2 统计方法度量词条，和文档类别c 之间的相 关程度，并假设，和c 之间符合具有一阶自由度的z 2 分布。词条，对于某类的z 2 统计 8 硕士学位论文 值越高，它与该类之间的相关性越大，携带的类别信息也较多，独立性也越小。 令，彳，b ，c 的含义同上述2 5 - 3 ，d 是既不属于c 也不包含f 的文档频数。若a d o 是一个常数，它控制对错分样本惩 罚的程度。广义最优分类面的对偶问题与线性可分情况下几乎完全相同，只是条 件口f o ，f = 1 ，l ，玎变为0 口，c ，f = 1 ，l ，船。 2 支持向量机 对非线性问题，可以通过非线性变换转化为某个高维空间中的线性问题，在 变换空间求最优分类面。这种变换可能比较复杂，因此这种思路在一般情况下不 易实现。但是注意到，在上面的对偶问题中，不论是寻优函数( 2 2 8 ) 还是分类函 数( 2 2 9 ) 都只涉及训练样本之间的内积运算( 薯x ，) ，这样，在高维空间实际上只 需进行内积运算，而这种内积运算是可以用原空间中的函数实现的，我们甚至没 有必要知道变换的形式。根据泛函的有关理论，只要一种核函数k ( 誓，x ，) 满足 m e r c e r 条件，它就对应某一变换空间中的内积。 因此，在最优分类面中采用适当的内积函数k ( x ，x ，) 就可以实现某一非线性变 换后的线性分类，而计算复杂度却没有增加，此时目标函数( 2 2 8 ) 变为 q ( 口) = 口，一去q 口，只乃k ( 薯_ ) ( 2 - 3 1 ) ，= 1 ，= l 而相应的分类函数也变为： 厂( x ) = s g n 口m k ( x ) + 6 ) ( 2 3 2 ) 1 4 硕十学位论文 概括地说，支持向量机就是首先通过用内积函数定义的非线性变换将输入空 间变换到一个高维空间，在这个空间中求( 广义) 最优分类面。s v m 分类函数形 式上类似于一个神经网络，输出是中间节点的线性组合，每个中间节点对应一个 支持向量，如图2 4 所示。 、 z 3 图2 4 支持向量机不意图 3 核函数 s v m 中不同的内积核函数将形成不同的算法，目前研究最多的核函数主要有 三类： 一是多项式核函数：k ( x ，置) = 【( x 一) + 1 】9 ，所得到的是g 阶多项式分类器； 1 2 二是径向基函数( r b f ) k ( x ，誓) ：e x p 一单) ，所得分类器与传统r b f 方 盯 法的重要区别是，这里每个基函数中心对应一个支持向量，它们及输出权值都是 由算法自动确定的； 三是采用s i g m o i d 函数作为内积，即定( x ，一) = t a n h ( v ( x 誓) + c ) 。 这时s v m 实现的就是包含一个隐层的多层感知器，隐层节点数是由算法自动 确定的，而且算法不存在困扰神经网络方法的局部极小点问题。 s v m 问题可以通过二次线性规划技术来计算。可以通过在s v m 中引入软分类 边界( s o f tm a r g i n ) 或者将原来的数据空间映射到更高维空间的方法将解决线性可 分情况推广到解决线性不可分的情况。 2 6 实验评测数据集 文本分类实验中，语料库的选择至关重要，选择的原则是国内外使用广泛、 权威标准和规范。这样使得我们的实验结果和国内外同行的实验结果具有可比性， 同时也便于认真细致地分析实验数据，分析算法的优劣。英文语料库己经有受到 国内外认可和广泛使用的路透社语料库( r e u t e r s 一2 1 5 7 8 ，r c v l 和r c v 2 ) ，t r e c 文档集和2 0n e w s g r o u p 等文档集。 基于模糊支持向量机的多类文本分类方法研究 实验中我们选用r e u t e r s 2 15 7 8 语料库进行实验分析和性能比较。 r e u t e r s 2 1 5 7 8 是d a v i dl e w i s 从1 9 8 7 年英国路透社新闻专线公开发表的数据中编 辑的，在文本分类研究领域是一个使用非常广泛、公认权威的语料库，国内外已 有许多研究人员公布了基于此语料库的实验结果。r e u t e r s 2 15 7 8 语料库可以从网 上免费下载 2 1 1 。r e u t e r - 2 1 5 7 8 由路透社的2 1 5 7 8 篇新闻文章构成，这些文档都是 关于经济的新闻稿，共分为5 个大类：即t o p i c s 、o r g a n i z a t i o n s 、e x c h a n g e s 、p l a c e s 和p e o p l e ，而每个大类又分为多个子类。在总共1 3 5 个类别中，最常用的也是最 大的1o 个类别共包含9 9 8 0 个样本，这样得到的样本子集通常称为 r e u t e r s 一215 7 8 t o p l0 。 为了方便实验的设计和算法性能的比较，有研究者将r e u t e r s 2 1 5 7 8 作了几种 切分，在以往进行的众多文本分类实验中，该数据集可以按照以下三种主要方式： “m o d l e w i s ”，“m o d a p t e ”和“m o d h a y e s ”分解成训练样本集和测试样本集，其 中以m o d a p t e 分解方式最为常见。本文中，我们的实验都是基于m o d a p t e 切分， 通过移除其中的多类别文档，选择r e u t e r s 2 1 5 7 8 t o p l o 中的6 个类别构造子数据 集。t 2 7 评测指标 文本分类中一个很重要的问题就是对分类的结果进行评价。不同的分类算法 选取的评估指标不同，下面将介绍一些常用的评估指标【2 0 】： 1 领域独立性 现有文本分类技术基本上是基于特征词信息，这使得文本分类需要借助于词 典和使用专门的分词技术。一方面，不同领域的词典在词的选择上各有侧重，而 编撰通用的面向不同领域的词典是很困难的，也不现实。因此，研究无须词典支 持、领域独立的文本分类系统无疑具有重要价值，这使得文本分类系统成为真正 意义上的通用系统。 2 时间无关性 语言是一个开放系统，随着时间的变化，语言和语言中的词也在不断变化。 新的词和表达会不断涌现，而有些已经存在的词和表达会慢慢被淘汰，消失于文 档之中。这意味着词典是随时间变化的。依赖于词典的文档分类系统，必须定期 对词典进行更新。 3 可扩展性 每一个文本分类系统都是建立在某一具体的文本分类方法基础之上。只要人 们还在不断探索和研究，更准确、更高效的文本属性选择和文本分类新方法会不 断出现；另一方面，文本分类作为一个机器学习过程，它也是开放的，应当能够 不断对新的实例进行学习，以改善它的对新环境的预测能力。因此，一个文本分 1 6 硕士学位论文 类系统应该具备功能和性能上的可扩展性，这就要求文本分类系统建立在模块化、 可扩展的体系结构基础之上。 4 空间和时间代价 算法的空间和时间代价是分两个阶段来考虑的，一些算法的训练时间是线性 的，但是分类时间是非线性的，如j j n n ；一些训练时间是非线性的，分类时间是 线性的，如最大熵模型和s v m ；还有一些训练时间和分类时间都是线性的，如n a i v e b a y e s ；一般来说，在训练阶段，高昂的空间和时间代价是可以忍受的；但是，分 类阶段则不然。 上述这些指标没法定量测量，所以文本分类一般不是使用这些指标，而使用 信息检索中的查全率和查准率这些指标来衡量系统的性能。文本分类应用可以归 纳为如下两类，对于这两类应用它们查全率和查准率的计算公式亦有所不同。 1 单类赋值( s i n g l ec a t e g o r ya s s i g n m e n t ) ：存在多个文档类，但每个文档只属于 其中的一个类，分类结果是给每个文档赋予一个文档类标号。 2 多类排序( m u f t i c a t e g o r yr a n k i n g ) ：存在多个文档类，且每个文档可以属于其 中的多个类。分类结果是给每个文档所属的类打分并排序。排在最前面的类，说 明该文档属于该类的可能性最大。 2 7 1 单类赋值 文本分类中普遍使用的性能评估指标有查全率( r e c a l l ，简记为尸) 、查准率 ( p r e c i s i o n ，简记为p ) 。对于文档类中的每一个类别，使用列联表( c o n t i n g e n c y t a b l e ) 来计算查全率和查准率。表2 1 为一个列联表示例。 表2 1 二值分类列联表7 这时，r 和p 分别定义为：r ：旦p ：三 a+c：d+bo 1 宏平均和微平均( m a c r o - a v e r a g i n ga n dm i c r o - a v e r a g i n g ) 用列联表只能评价单个类的分类性能，如果要对分类的整体性能进行评价， 通常使用宏平均( m a c r o a v e r a g i n g ) 和微平均( m i c r o - a v e r a g i n g ) 。宏平均是先对 每个类统计八p 值，然后对所有的类求，j 、p 的平均值；微平均是先建立一个全 局列联表，然后根据这个全局列联表进行计算，、矽的值。显然，宏平均是对类的 平均，所以容易受小类的影响，而微平均则是对文档的平均，容易受到大类的影 向。 2 平衡点( b r e a k e v e np o i n t ) 1 7 基于模糊支持向量机的多类文本分类方法研究 对于分类系统来说，厂和p 值是互相影响的。提高，会引起p 的减小，反之亦然。 因此，为了更全面地反映分类系统的性能，一种做法是选取r 和p 相等时的值来表 征系统性能，这个值叫做平衡点( b i e a k e v e np o i n t ，简称b e p ) 值。当然，有时 通过测试可能得不到r 和p 相等的值。这时取最接近的，和p 值的平均值作为b e p 值， 称为插值b e p 。 3 f 值( f m e a s u r e ) 另一种常用的将查全率和查准率结合起来的性能评价方法是f 测量，其计算公 式为： 只：鲤掣迦 ( 2 3 3 ) b 1p 七r 其中，是一个用来调节查全率和查准率权重的参数。一般取值为l ，这时 公式( 2 3 3 ) 转化为： 曩= 2 甲( ，+ p ) ( 2 3 4 ) 显然，b e p 是互的特殊形式，因为当，= p 时，有e = 彪p 。 2 7 2 多类排序 对于这类问题，首先应给定一个门限值，以确立文档和类之间的所属关系。 对每一个输入的测试文档，都会返回一个排序后的文档类列表。这时，两个指标 分别定义为： 找到的该文档所属的正确类别数目 ， 判断为该文档所属类的类别数目 找到的该文档所属的正确类别数目 该文档所属的所有类别数目 整个分类器的评估应该是对所有测试文档的这两个指标的统计平均。通常使 用的统计平均为1 l 点插值平均查准率( i n t e r p o l a t e d1 l p o i n ta v e r a g ep r e c i s i o n ) 。 2 8 本章小结 本章详细讲述了文本分类系统。从文本分类的定义、分类过程、分类算法、 评测数据集、评测指标等各个方面进行了研究。总的来说，文本分类理论及技术 研究正逐步走向成熟。其应用也已经深入到众多的领域，在各行业的应用越来越 广泛；并以其显著的经济效益推动着其应用的迅速普及，同时又以强大的市场需 求刺激着其理论及技术研究的不断发展，将统计学理论应用于文本分类，将会对 文本分类产生很大影响。 1 8 硕士学位论文 第3 章模糊支持向量机 3 1 模糊集的基本概念 模糊数学是一门应用极为广泛的数学学科。尤其是近十多年来，它与信息科 学紧密结合，模糊智能系统、模糊神经网络等模糊系统纷纷出现【36 1 。我们先讲一 下模糊集合【3 7 3 9 】的基本概念。 在论域u 上，元素材【，与经典集合a 之间的关系是：要么“么；要么”萑么， 二者必居其一，且仅居其一。经典集合是用于表述非此即彼的清晰概念，用特征 函数表示就是： x 砌卜1 艇么 ( 3 1 ) x 。( 掰) = ( 3 1 ) “ l o “仨么 在属于和不属于之间不存在中间状态，1 9 6 5 年美国计算机与控制论专家扎德 推广了用特征函数表示经典集合的方法，用隶属函数表示模糊( f u z z y ) 集合，把值 域 o ，1 ) 推广为区间 0 ，1 。 定义：给定论域x 上的一个模糊子集a ，是指由该论域上的一个映射： ：x _ 【0 ，1 】，x a 心( x ) ( 3 2 ) 所表征的集合。对于任意的x x ，都有一个实数心 ) 【0 ，1 】与之对应，则称心( x ) 为x 对集合a 的隶属度，而映射。称为a 的隶属函数。 为了与经典集合区别，模糊集合a 记为身，隶属度。( x ) 记为瓤) ，隶属函数 。记为搿。 当瓤) ：l 时，则x 完全属于模糊集碧；当瓤) = o 时，则x 完全不属于模糊集学； 脓) 越接近1 ，x 属于学的程度就越大。因此，隶属函数实质上是特征函数的一般 化，而模糊集是经典集合的一般化。 3 2 模糊支持向量机 支持向量机由于其完备的理论基础和出色的性能曰益受到广泛重视，该方法 已成为机器学习界的研究热点，并在很多领域都得到了成功的应用。但是作为一 种新兴的技术，s v m 还存在着以下两方面问题：一方面，如何将两类问题的解决 办法有效地推广至多类问题。目前，已经有一些卓有成效的方法，这些方法的基 本思想多数是把多类分类问题划分为多个两类分类问题，通过某种方式组合这些 两类分类器来解决多类分类问题，如“一对一 ( o n e v e r s u s o n e ) 、一对多 ( o n e v e r s u s r e s t ) 以及决策树等方法( 将在第四章进行详细描述) ；另一方面， 1 9 基于模糊支持向帚机的多类文本分类方法研究 在实际问题中，存在可能不完全属于某一类别的样本点以及一些被噪音影响而对 分类没有意义的样本点，而标准支持向量机等同对待所有训练样本，因此对那些 混杂在另一类中噪音、孤立点样本非常敏感，降低了分类器的泛化能力。针对这 种情况，近几年提出了模糊支持向量机( f s v m ) 【1 2 1 4 1 7 】方法，作为对传统的支持 向量机的一种改进与完善。模糊支持向量机的概念主要有下列两种。 3 2 1 第一种模糊支持向量方法 一种思想是由日本学者t a k u g a 与s h i g e o 于2 0 0 1 年和2 0 0 2 年提出的【1 2 1 3 1 。 此方法主要是针对一对多组合与一对一组合支持向量机存在决策盲区而提出的。 这两种思想在多类分类问题上都有一个共同的缺点一一存在不可分区域，即 对于训练好的分类函数，可能对一个待分数据无法进行分类。 举例说明，以一对一组合进行多类分类，在样本中单独取出第f 类和第，类 1 f ，尼，考虑这样一个两类分类问题，易得分类函数： 口，= 嵋g ( x ) + 6 ， ( 3 3 ) 定义d 。= 一口，对于给定数据x 进行分类，定义x 对第i 类的归属度： 七 皿( x ) = s 咖 岛( 跏 f = 1 ，2 ，3 ，七 ( 3 4 ) ，= l 计算出k 个口后，将x 分入归属度最大的一类，即分入： a r g 磐峰口( x ) ( 3 5 ) i ；1 膏 图3 1 不司分区域 如图3 1 ，箭头所示方向为各分类函数为1 的方向，如果给定一个x 在阴影部 分内，则： d 1 ( x ) = s 忉 d 1 2 ( x ) + s 酬q 3 ( x ) 】= 一l + 1 = 0 ( 3 6 ) d 2 ( x ) = s 忉 d 2 l ( x ) 】+ s 酬d 2 3 ( x ) = 1 1 = o ( 3 7 ) d 3 ( x ) = j 柳【d 3 l ( x ) + j 酬d 3 2 ( x ) 】= 一1 + 1 = 0 ( 3 8 ) 从而d l ( x ) = d 2 ( x ) = d 3 ( x ) = o ，无法对数据x 进行分类，图中的阴影部分即为 2 0 硕士学位论文 不可分区域。 为了避免产生不可分区域，我们引入模糊隶属度函数，定义： i l p ，1 ( ，) = q一1 或 o ，则模糊隶属度t 可定义如下： 1 1 一掣， d ( 一) 又 驴 。，凳，( 南卜m ( 4 7 ) 其中，d ( 一) 是样本点一到球心艺的距离，计算公式为d ( 誓) = 忱一k 忆r 为类 半径，计算公式为r = 毋a x | l 艺一虬净1 ，2 ，l ，嚣。从式( 4 。7 ) 可以看出，位于球 内的样本，隶属度最小值为1 一，且离球心越近，该样本属于该样本集的隶属 度越大；而位于球外的样本，其隶属度最大值不超过1 一二，且离球越远，该样 本属于该样本集的隶属度越小。 4 2 2 f s v m 决策树文本分类器实现多类分类基本思想 如果存在一个足类可分的问题，那么任意两类之间都是两两可分的。基于这 点，本文将f s v m 两类分类器与二叉决策树的拓扑结构结合起来，构成树形结构 的多类分类器。根据二叉树性质：对任何一棵二叉树，如果其叶子结点个数为m ， 度为2 的结点个数为2 ，则有o = 1 + 1 。 如图4 2 所示，椭圆形表示f s v m 分类器结点，数字代表类别号，二叉决策 树的拓扑结构上必定为完全二叉树，每一类别对应一个叶子结点，非叶子结点即 为分类器结点。首先将f s v m l 作为二叉树的根节点，将属于第l 类的测试样本决 策出来，将不属于第l 类的样本通过f s v m 2 进行分类，直到f s v m 霓1 将第| j 类 图4 2f s v m 决策树 2 7 基于模糊支持向量机的多类文本分类方法研究 对于尼类问题，当所有训练结束时，得到珏1 个两类分类器： z ( x ) = w x + 匆 ：窆哆只k ( t ，x ) + 6 f - 1 ，2 ，h 4 剐 j = l 对于新给的测试样本x 被分入： c 缸船( x ) = a r g m a ) 【 石( x ) ，五( x ) ，五一l ( x ) ( 4 9 ) 4 2 3 算法的具体步骤 整个算法的思想步骤可简单描述如下： s t e p l 训练传统的s v m 分类器，得到初始支持向量，并用其来构成决策分 类面； s t e p 2 根据4 2 1 节中介绍的方法，由传统s v m 中得到的分类面及超平面 m ，求出隶属度函数s ； s t e p 3 确定模糊训练集：( ，m ，s 1 ) ，( 屯，y 2 ，是) ，( ，以，) ； s t e p 4 训练模糊训练点，构造最优分类函数。对于七类训练样本，训练七- 1 个f s v m 分类器； s t e p 5 对样本进行分类。 4 3 实验结果及分析 在实验中我们使用通用的文本分类标准测试集r e u t e r 2 1 5 7 8 ，该文本集材料 来自路透社1 9 8 7 年的英语新闻文本，经过路透社人工处理和分类，分成1 3 5 类， 总共包含2 15 7 8 篇文档，其中训练集有9 6 0 3 篇文档，测试集有3 2 9 9 篇文档。本 文实验基于m o d a p t e 切分，通过移除其中的多类别文档，选择r e u t e r s 2 1 5 7 8 t o p l o 中的6 个类别构造子数据集。 文本用向量空间模型表示，用t f i d f 方法进行特征加权。对不同分类方法的 比较，使用z 2 统计量对分词结果进行特征提取。 我们使用并修改了标准的l i b s v m 软件包f 4 3 1 ，以适应本文的方法。l i b s v m 是 一款简单、易用、高效的用于s v m 分类和回归的软件，可以在网上免费下载。