（模式识别与智能系统专业论文）基于支持向量机的文本分类方法研究.pdf

摘要 随着计算机技术和w w w 的飞速发展，互联网上的电子文档信息急 剧增加。面对如此浩瀚的信息，人们迫切需要寻找一条能够快速、准 确获得所需信息的途径。而文本分类作为信息过滤、信息检索、搜索 引擎、文本数据库、数字化图书馆等领域的技术基础，有着广泛的应 用前景，因此也就成为人们研究的热点问题。 本文从文本的向量模型表示，特征选择和分类器训练这三个步骤 较系统地研究了文本自动分类。 ( 1 ) 讨论了文本表示的整个过程分词，建立停用词表，特 征选择，权重计算，生成向量空间。针对停用词对分类的影响，建立 了适合文本分类的停用词表，使向量维数得到初步降低；对现有特征 选择方法进行了介绍和对比，构造了一种适合支持向量机的特征选择 函数基于类内频率的特征选择函数。 ( 2 ) 介绍了当前性能较好的三种文本分类方法：朴素贝叶斯、 k n n 法和支持向量机法，对它们进行了对比研究，实验结果表明支持 向量机是当前分类结果较稳定，精度较高，性能较好的方法。 ( 3 ) 结合粗糙集和支持向量机的优点，提出了基于粗糙集与支 持向量机融合的文本分类方法，利用粗糙集的约简可以降低向量的维 数，从而缩短了支持向量机的训l 练时间。 ( 4 ) 实现了一个实用性较强的文本分类实验系统，利用该系统 可以进行特征选择、权重计算研究，也可以直接对不同的语料进行训 练和测试。 ( 5 ) 对文本分类未来研究进行了展望。 关键词：文本分类；特征选择；粗糙集；支持向量机 a b s t r a c t w i t ht h ed e v e l o p m e n ta tf u l l s p e e do ft h et e c h n o l o g y o ft h e c o m p u t e ra n dw w w j t h ee l e c t r o n i cf i l ei n f o h n a t i o no ni m e m e ti n c r e a s e s s h a 叩l y i nt h ef a c eo fs ov a s ti n f b m a t i o n ，p e o p l eu r g e n t i yn e e dt ol o o k f o raw a yt h a tc a no b t a i nn e c e s s a r yi n f o m a t i o nf l e e t l ya n da c c u r a t e l y a n dt e x tc a t e g o r i z a t i o na sm et e c h l l o l o 西c a lf o u n d a t i o ni su s e di ns u c h f i e l d sa si n f b m a t i o nf l l t e r i n g ，i n f b h n a t i o nr e t r i e v a l ，s e a r c he n g i n e ，t e x t d a t a b a s e ，d i g i t i z e d1 i b r a r ye t c t h e r ea r ee x t e n s i v ea p p l c a t i o np r o s p e c t s ， s oi tb e c o m e st h eh o tp r o b l e m t h i sp 印e rs t u d ys y s t e m a t i c a l l yt e x ta u t o m a t i cc a t e g o r i z a t i o n 矗o m m r e ew a v si n c l u d i n gv e c t o rm o d e lr e p r e s e n t a t i o n ，f e a t u r es e l e c t i o na n d c l a s s m e rt r a i n i n g ( 1 ) t h ew h o l ep r o c e s so f t e x tr e p r e s e m a t i o nw e r ed i s c u s s e d w o r d s e g m e n t a t i o n ，b u i l d i n gs t o p w o r d sl i s t ， f e a t u r e s e l e c t i o n ，w e i g h t c o m p u t a t i o na 1 1 dg e n e r a t i n gv e c t o rs p a c e a i m a tt h ei n f l u e n c eo fs t o p w o r d s ，al i s t ，w h i c hi sf i tf o rt e x tc a t e g o r i z a t i o n ，i ss e tu pa n dm a k e st h e v e c t o rd i m e n s i o nr e d u c e t h ee x i s t i n 2m e m o d so ff e a t u r es e l e c t i o nw e r ei m r o d u c e da n d c o m d a r e da n dak i n do ff e a t u r es e l e c t i o nm n c t i o nw h i c hi ss u i t a b l ef o r s v mw a sc o n s t m c t e d f 宅a m r es e l e c t i o nf u n c t i o nb a s e do nf r e q u e n c yi n k i n d f 2 ) t h r e eb e t t e rm e t h o d so ft e x tc a t e g o r i z a t i o n n a i v eb a y e s ， k 卜ma n ds v mw e r ei n t r o d u c e da n dc o m p a r e d a t p r e s e n t ： t h e e x d e r i m e n t a lr e s u l ti n d i c a t e st h a ts v mi sab e t t e rm e t l l o dw i t hr e l a t i v e l y s t a b m z a t i o n ，h i 曲p r e c i s i o na n d b 毗e rp e r f o 玎n a n c e ( 3 ) c o m b i n e da d v a n t a g e so fr o u 曲 s e t sa n ds v m ， at e x t c a t e g o r i z a t i o nm e t h o db a s e do nr o u g hs e t sa n ds v mw e r ep r o p o s e d t h i sm e t h o dc a nc u td o w nv e c t o rd i m e n s i o na n dr e d u c et h et r a i n i n gt i m e o fs v mb yu s i n gr o u g hs e t sr e d u c t i o n ( 4 ) o n eu s e m lt e x tc a t e g o r i z a t i o ne x p e r i m e n t a ls y s t e mw a sc a r r i e d o u t b yu s i n gt h i ss y s t e m ，f e a t u r es e l e c t i o na n dw e i g h tc o m p u t a t i o nc a n b es t u d i e d ，t l a i n e da n dt e s t e df o rd i f r e r e n tl a n g u a g em a t e r i a l sd i r e c t l y ( 5 ) t h er e s e a r c h e so nt e x tc a t e g o r i z a t i o ni nf u t u r ew e r ep r o s p e c t e d k e y w o r d s ：t e x tc a t e g o r i z a t i o n ；f e a t u r es e l e c t i o n ；r o u g hs e t s ；s v m i i 第1 章引言 第1 章引言 1 1 问题提出及意义 随着计算机技术的飞速发展以及i n t e r n e t 的普及与应用，互联网上的电子文 档信息急剧增加。如何从大量的信息中快速、准确地检索到所需的信息资料，是人 们普遍关心的问题，也是计算机工作者急需解决的问题。面对如此复杂的问题，分 类技术在信息检索、信息过滤、数据挖掘等方面起着至关重要的作用。而网上的大 部分信息以文本的形式存在，于是文本自动分类技术就成为网上信息检索和信息过 滤的关键。另外，文本分类可以应用到垃圾邮件的判定( s p a n lo rn o ts p a m ) ，类别 s p 砌，n o t s p 锄) ；新闻出版按照栏目分类，类别 政治，体育，军事 ；词性标注， 类别 名词，动词，形容词) ；词义排歧，类别 词义1 ，词义2 ) ，文本检索，文 本过滤以及主题发现与跟踪等。而从s p r i n g e rl i l l k 全文电子期刊与i e l ( i e e ，i e e e ) 数据库中，可以看到最近的期刊与国际会议论文，有大量的关于文本分类的文章， 说明随着大量的网上的电子信息，文本分类仍是人们研究的热点。 面对网上的海量信息，传统的做法是对网上信息进行人工分类，并加以组织和 整理，为人们提供一种相对有效的信息获取手段。但是，这种传统的人工分类的做 法存在着许多弊端：一是耗费大量的人力，物力和精力；二是存在分类结果一致性 不高的问题。这就要求我们探索计算机自动进行文本分类的有效方法，使得分类的 正确率提高。只有这样才能保证检索的查全率和准确率都得到提高。 文本自动分类是人：【智能技术和信息检索技术相结合的研究领域，是进行基于 内容的自动信息管理的核心技术。文本分类是指根据一些已经分配好类标签( 这些 类标签预先定义好) 的训练文档集合，来对新文档分配类标签，其目的就是对文本 集进行合理处理和组织，使得这些文本能够按照类别区分开来。作为知识的组织工 具，它为信息检索提供了更高效的搜索策略和更准确的查询结果，其中，高效性在 于用户可以首先确定查询的可能类别，以减小需进一步匹配的文本数量：有效性在 于相似的文本很可能与相同的查询相关，这样使得检索的查全率和准确率都得到了 提高。 文本分类作为信息过滤、信息检索、搜索引擎、文本数据库、数字化图书馆等 领域等技术的基础研究，有着广泛的应用前景。 基于支持向量机的义本分类方法研究 1 2 国内外研究现状 国外自动分类研究开始于1 9 5 0 年代末，h p l u h n 在这一领域进行了开创性的 研究，他首先将词频统计的思想用于文本分类中。1 9 6 0 年m a r o n 在j o u r n a lo fa s m 上发表了有关自动分类的第一篇论文“o nr e l e v a n e e ，p r 。b a b i t i cin d e x i n ga n d i n f 。r m a t i o nf e t n r a l ”。1 9 6 2 年博科( h b o r k o ) 等人提出了利用因子分析法进行 文献的自动分类。其后许多学者在这一领域进行了卓有成效的研究。国外的自动分 类研究大体上可以分为三个阶段：第一阶段( 1 9 5 8 年1 9 6 4 年) 主要进行自动分类的 可行性研究：第二阶段( 1 9 6 5 年一1 9 7 4 年) ，自动分类的实验研究：第三阶段( 1 9 7 5 年一 至今) ，自动分类的实用化阶段。现已在邮件分类、电子会议、信息 过滤等方面取得了较为广泛的应用，其中较为成功的系统有麻省理工学院( m i t ) 为 白宫丌发的邮件分类系统、卡内基集团为路透社丌发的c o n s t r u e 系统等。 国内自动分类研究起步较晚“，始于2 0 世纪8 0 年代初期。1 9 8 1 年侯汉清对 计算机在文献分类工作中的应用作了探讨，并介绍了国外在计算机管理分类表、计 算机分类检索、计算机自动分类、计算机编制分类表等方面的概况。此后，困内的 研究者在英文文本分类研究的基础上采取相应策略，结合中文文本的特定知识，然 后应用于中文之上，继而形成中文文本自动分类研究体系。到目前为止，我国陆续 研制出一批计算机辅助分类系统和自动分类系统。例如中国科学院、清华大学、北 京大学、北京信息工程学院、上海交通大学、复旦大学、东北大学、山西大学、同 济大学、南京大学、浙江大学以及西安电子科技大学等单位都有相应的研究成果， 也研制出了不少的实验系统。这其中有基于人工智能技术的分类系统，有基于统计 学技术的分类系统，还有基于模糊技术的分类系统，近几年基于统计知识的分类方 法占主流，也不乏有基于规则的分类方法。 国外当前流行的文本分类方法有k 近邻法( k n n ) ”3 、决策树”1 、朴素贝叶斯( n b ) 、支持向量机( s v m ) 、神经网络( n n e t ) ”。1 、线性最小平方拟合( l l s f ) 法1 、 最大熵模型“、回归模型、遗传算法1 等方法。这些方法在英文文本自动分 类上有广泛的研究，而且很多研究表明k n n 和s v m 是英文文本分类的最好方法。国 外很多研究人员对英文文本分类领域的各个问题都有相当深入的研究，对几种流行 的方法进行了大量的对比研究。y i m i n gy a n ga n dx i nl i u “5 1 对s v m 、k n n 、l l s f 、 n n e t 和n b 这5 种方法进行了专门的比较研究。 国内当前流行的文本分类方法有k 近邻法( k n n ) ”6 “1 、朴素贝叶斯( n a i v e 第1 章0 i 吉 b a y e s ) 方法“们”、最大熵模型驯、线性最小平方拟合( l l s f ) ：州、决策树方法：、 神经网络方法“、遗传算法3 、支持向量机( s v m ) 方法哺：以及概念推理网法1 等等。其中k n n 、n b 和s v m 由于分类效果比较好成为近几年人们研究的热点。文本 分类过程由文本的表示、特征选择和分类器训练组成。分类算法只是其中的一个环 节，另外两个环节也非常重要。现在人们普遍采用向量空问模型表示文本，常见的 加权方法有：布尔权重、词频权重、t f i d f 权重和信息熵权重等。常见的特征选择 方法有：文档频率、特征词和类别的互信息、特征词的x 2 统计、信息增益等。 1 3 本文研究工作 鉴于以上对文本分类的分析，本文主要从以下几方面进行研究： ( 1 ) 讨论了文本表示的整个过程分词，去停用词，特征选择，权重计算， 生成向量空间。其中对停用词对分类的影响进行了研究，使得向量维数得到初步降 低；对现有特征选择方法进行了介绍和对比，构造了一种适合支持向量机的特征选 择函数基于类内频率的特征选择函数： ( 2 ) 介绍了当前常用的三种分类方法：朴素贝叶斯、k n n 法和支持向量机法，对 它们进行了对比研究，实验结果表明支持向量机是当前分类效果最好的方法； ( 3 ) 结合粗糙集和支持向量机的优点，提出了基于粗糙集的支持向量机文本分 类方法，该方法可以降低向量的维数，从而缩短了支持向量机的训练时间； ( 4 ) 最后实现了文本分类系统，利用该系统可以进行特征选择、权重计算研究， 也可以直接对不同的语料进行训练和测试。 1 4 本文的组织 本文以后各章的具体组织结构如下： 第2 章从特征词的表示，特征选择，向量空间模型三方面介绍了文本的表示； 第3 章对常用的三种文本分类方法作了介绍，通过对比实验和分析，得出支持 向量机是这三种方法中分类性能最好的一种分类器： 第4 章介绍了粗集理论以及基于粗集的文本分类算法，分析了浚方法的优缺点， 最后将粗集的优点和支持向量机的优点相结合提出了基于粗糙集的支持向量机文 本分类方法； 第5 章是文本分类系统的设计和实现； 第6 章对本文的研究工作进行了总结，对未来的研究进行了展望。 基于支持向量村【的文本分类方7 三研究 第2 章中文文本表示 文本分类大致可分为三个步骤：文本的向量模型表示，文本特征选择和分类器 训练。 2 1 向量空间模型( v s m ) 向量空间模型( v e c t o rs p a c em o d e 卜简称v s m ) 是由s a lt 。n 等人在六十年 代末到七十年代初期提出的模型，近年来应用较多且效果好。v s m 是由一组规范化 f 交词条矢量所组成的向量空问，每一个文档映射向量空间的一个点，向量间的距 离表示文档之间的相似度。通过这种模型可以将给定的文档以向量的形式表示在 v s m 中，从而将文档之间的相似性这一抽象的问题转化为具体的空间的点与点的距 离问题，通过计算出任意两个向量之间的近似程度，从而来反映所对应的文档间的 相似性。 在v s m 中，主要涉及到以下几个概念： ( 1 ) 文档( d o c u m e n t ) ：指一篇文章。 ( 2 ) 项( t e r m ) ：也称为索引项或特征项，一般指文档中的词或短语。给文档分类 主要是依据特征项，即一些特殊的项，可以起到代表文档的作用。 ( 3 ) 项的权重( t e r mw e i g h t ) ：假设一个系统包含有m 个文档、n 个不同的项，则 d ，= ( f ，2 ，f 。) ( 1 瞧m ) ，表示一个文档：给其中的项，女( 1 女h ) 赋值，记为w 。， 表示它在文档中的重要程度，通常称为项f 。的权重。 ( 4 ) 向量空间模型：由( 3 ) 得到一个含值的文档表示，记 作：d ，= ( ，1 w 1 ，f 2 w 2 ，。w 。) 。由于f l ，f 2 ，。互不相同，可以把它们看作是n 维欧氏 窄间的n 个坐标，把( w ，w ：，w j 看作是n 维欧氏空间的向量。这样，称 p = ( ，w l ，：w ：，r 。w ，) 为文档d ，的向量表示。，为特征项词条，w ，为对应坐标值， 即特征词条权值。 22 文本特征词的表示 通过计算机对文本进行分类，首先要把文本表示成计算机能处理的数据形式。 在文本分类中最常见的是对文本进行分词，这样文本就变为词集，而将全部词集作 为文本分类的特征，构成文本词汇的数量是相当大的，可以达到几万个，因此需要 对词集进行相应的压缩以获得对分类有用的特征，这样做的目的主要有两个：第一， 第2 章文本表示 为了提高分类程序的效率；第二，为了提高分类的精度，由于不同的词汇对文本分 类的意义是不同的，一些是通用的、各个类别都普遍存在的词汇对分类的贡献小， 在某特定类中出现比重大而在其他类中出现比重小的词汇对文本分类的贡献大，因 此，对于每一类，应去除那些表现力不强的词汇，筛选出针对该类的特征项集合。 2 21 停用词对文本分类的影响 在文本分类中对文本进行分词后，文本就变为词集，但是词集中有很多虚词在 文章中仅起到结构作用，不表示实际意义，比如介词，副词等等，另外还有一些词 在整个语料中出现频率高而在每篇文档中出现概率大致相等，对分类来说作用不大 我们把这些词合称为停用词。对于这些词，应该从特征集中去掉。停用词的选取对 词集的大小、分类的准确率都有影响。 停用词的选择原则：第一删除停用词后，分类准确率应不降；第二，删除停 用词后能够达到粗降维的目的。 停用词表的生成过程： ( 1 ) 计算词频，人工从高频词中将我们认为对分类贡献不大的的词选出，如： “的”、“在”、“是”、“不”、“否则”等1 8 0 个词，作为停用词，放入停用 词表； ( 2 ) 将代词表、副词表、介词表、连词表和助词表加入，经过反复实验比较分析， 最后将代词和连词扩充进停用词表。 ( 3 ) 通过( 2 ) ，得到停用词表中一共由1 4 3 2 个词组成。 在实验中，我们从特征集维数缩减率和分类准确率两方面进行了衡量。去停用 词前的分类准确率是9 7 ，去掉由( 1 ) 得到的停用词后的分类准确率为9 7 5 6 1 ，然 后加入代词和连词后分类准确率不变，但特征集中的特征减少了，之后又分别继续 加入副词表、介词表和助词表后特征集中的特征同样也减少了，但分类准确率都有 所降低。这说明由( 1 ) 得到的停用词表中的词对分类有负面影响，而代词和连词对 分类不起作用，把两者结合形成了进行文本分类所用的停用词表。另外，去停用词 丽特征集中有1 0 8 6 9 个词，去后有8 2 2 5 个词，维数缩减了2 4 3 。通过以上分析可 以得出，去除停用词确实能够起到粗降维和提高分类精度的作用。 2 2 2 特征词的权重 不同的特征项对文档的重要程度和区分度的影响是不同的，因此系统在对文本 基于支持向量机的文本分类方法研究 进行形式化处理的时候，需要对特征项进行加权，f 面对常用的加权函数进行详细 介绍。 ( 1 ) 布尔权重 布尔权重是最简单的一种加权方法，如果特征词出现次数为0 ，则其权重为0 ， 如果特征词出现词数大于0 ，则其权重为l 。公式如下： 啥牌笺 c z t ， 其中w t 。表示特征词f 在文档，中的权重，矾表示特征词j 在文档j 中出现次数。 ( 2 ) 词频权重 该方法将特征词的频次作为权重。公式如下： 耽。= r ( 22 ) t fi d f 权重 该方法基于以下两点原因：一是特征词f 在文档j 中出现词数越多越重要，权重 和甄成正比；二是文档集中含有特征词f 的文档数d f 越大越不重要，权重和班 成反比。公式如下： 耽。= 7 一，+ i o g ( d f )( 2 3 ) 该式表明，若特征词f 在所有文档中均出现，即d f = j ，则耽。= o ，也就是 说，虽然特征词f 出现次数多，但它的分布比较均匀，说明它没有区分类别的能力。 对上面进行归一化： ： 姜些丝丝! i ( 2 4 ) “，一# o = = = = = = = = = = = = = 一 l l 。 z + l o g ( d 吒) 2 、。 为了降低，f 的作用将式( 2 4 ) 调整为： ：毒些坠竺丝黑 ( 2 5 ) “ 1 0 9 ( r + 1 o ) + l o g ( d 吒) 2 、 其中a r 表示全部训练文档的总数，d f 表示在文档集合中出现特征词i 的文档数目。 ( 4 ) 信息熵权重 第2 章文本表示 “。扎峨“矿 击善c 矗崦c 和 亿s ， 上北6 ) 中的击喜 每l o g ( 称为特蹴的熵或者平均不靛陛。 当分布极度均匀：熵等于一1 ，说明它没有区分类别的能力。只在一个文档中出现： 熵等于o ，随明它的区分类别的能力最大。 23 特征选择 在中文文本分类中，文本集经过分词后变成词集，然后经过去掉停用词粗降维 得到特征集。但是特征集仍然是个高维的特征空间，对于所有的分类算法来说维数 都太大。因此，我们面临寻求一种有效的特征抽取方法。以降低特征空间的维数，提 高分类的效率和精度。 特征选择的目的是除去特征集中不能较好表示有效信息的特征，以提高分类准 确度和减少计算复杂度。常见的特征选择方法仲83 ”3 有以下4 种：文档频率、 信息增益( i g ) 、互信息( m i ) 、z 2 统计量( c h i ) 等。这些方法的基本思想都是对每一 个特征即词条，计算它的某种统计的度量值，然后设定一个阈值t ，把度量值小于t 的那些特征过滤掉，剩下的即认为是有效特征。 2 3 1 文档频率 一个特征的文档频率( d o c u m e n tf r e q u e n c y ) 是指在文档集中含有该特征的文档 数目。采用d f 作为特征选择，基于如下基本假设：d f 值低于某个闽值的词条是低 频词，它们不含或含有较少的类别信息。将这样的词条从原始特征空间中除去，不但 能够降低特征空间的维数，而且还有可能提高分类的精度。文档频率是最简单的特 征抽取技术，由于其相对于训练语料规模具有线性的计算复杂度，它能够很容易被 用于大规模语料统计。而在信息检索研究中通常却认为d f 值低的词条相对于d f 值 高的词条具有较多的信息量，不应该将它们完全移除。不同的应用将对d f 值的认识 不同，因此应具体情况来选择该方法。 2 3 2 信息增益 信息增益( i n f o m a t i o ng a i n ) 在机器学习领域被广泛使用。对于词条f 和文档类 别c 用i g 考察文档类别f 中出现和不出现词条，的文档频数来衡量词条，对于文 档类别c 的信息增益。我们采用如下的定义式： 媾r 支持向量机的文本分类方法例宄 g a i n ( t ) = 一：p ( c ，) l o g ，( c ，) + p ( f ) ：p ( c ，f ) l o g p ( c ，j f ) r 97 、 i + p ( r ) ! 尸( c ，f ) l 。g 尸( c ，f ) 其中p ( c ，) 表示f ，类文档在语料中出现的概率，p ( f ) 表示语料中包含词条f 的文档的 概率，p ( c 。r ) 表示文档包含词条，时属于c ，类的条件概率，p ( f ) 表示语料中不包含 词条，的文档的概率，p ( c 。 ) 表示文档不包含词条f 时属于c 的条件概率，m 表示类 别数。 实验中叫以对语料中出现的每个词条计算其信息增益值，从原始特征空间中移 除低于特定闽值的词条，保留高于阈值的词条作为表示文档的特征。当然，信息增益 方法也有缺点：当r 仅出现在一个类中时，即使，在这个类中均匀分布，g a i n 的值也 很小，但这时r 对该类具有很强的代表性。 2 33 互信息 互信息( m 咖a 1i n f o m a t i o n ) 在统计语言模型中被广泛采用，m i 越大，共现程 度越大。如果用爿表示包含词条，且属于类别c 的文档频数，b 为包含，但是不属于 c 的文档频数，c 表示属于c 但是不包含f 的文档频数，j v 表示语料中文档总数，和 c 的互信息可由下式计算： 坤，沪岘揣扎s 等一l o s 揣 s ， 如果f 和c 无关( 即p ( ，c ) = p ( f ) p ( c ) ) ，( ，c ) 值自然为零。为了将互信息应用 于多个类别，与z2 统计的处理类似，由下式计算，对于c 的互信息： 。( f ) 2 翟：p ( c 。) 坤，c ) ( 2 9 ) 其中m 为类别数。将低于特定阈值的词条从原始特征空阃中移除，降低特征空间的 维数，保留高于阈值的词条。另一种方法是公式，将词条对于各个类别的平均，。( f ) 值作为它对所有类别的。( f ) 值，但是它的表现不如( 29 ) 式，平均，。( f ) 值的计算 见下式： ，。( ，) = j d ( f ( ，c ，) ( 2 1 0 ) 2 3 4 z2 统计 z2 统计方法度量词条，和文档类别。之间的相关程度，并假设r 和c 之间符合具 有一阶自由度的z 2 分布。词条f 对于某类的z2 统计值越高，它与该类之间的相关性 第2 章文奉表示 越大，携带的类别信息也较多，独立性也越小。令j v ，4 ，b ，c 的含义同上述2 3 3 ，d 是既不属于c 也不包含f 的文档频数。若4 d 0 是一个常数，它控制对错分样本惩罚的程度。广义最优分类面的对偶问题 基于支持向量机的文本分类方法研究 与线性可分情况下几乎完全相同，只是条件口，o ，一1 ，”变为 0 d ，玉c ，f = 1 ，h ( 3 1 9 ) 33 2 支持向量机 剥于维空间中的线性函数，其v c 维为+ l ，但根据式( 3 1 3 ) 的结论，在 爿的约束下其v c 维可能大大减小，即使在十分高维的空间中也可以得到较小 v c 维的函数集，以保证有较好的推广性。同时我们看到，通过把原问题转化为对偶 问题，计算的复杂度不再取决于空间维数，而是取决于样本数，尤其是样本中的支 持向量数。这些特点使有效地对付高维问题成为可能。 对菲线性问题，可以通过非线性变换转化为某个高维空间中的线性问题，在变 换空间求最优分类而。这种变换可能比较复杂，因此这种思路在一般情况下不易实 现。但是注意到，在上面的对偶问题中，不论是寻优函数( 3 1 6 ) 还是分类函数( 3 1 7 ) 都只涉及训练样本之间的内积运算( t x ，) ，这样，在高维空问实际上只需进行内 积运算，而这种内积运算是可以用原空间中的函数实现的，我们甚至没有必要知道 变换的形式。根据泛函的有关理论，只要一种核函数k ( x ，x ，) 满足m e r c e r 条件，它 就对应某一变换空间中的内积。 因此，在最优分类面中采用适当的内积函数世( 置，x ) 就可以实现某一非线性变 换后的线性分类，而计算复杂度却没有增加，此时目标函数( 3 1 6 ) 变为 q ( a ) = 窆q 一去兰蚂彬，k ( 即x ，) ( 3 2 0 ) l = 】f ，= i 而相应的分类函数也变为 厂( 班= s g n ( n j 只世( 一- x ) + 6 ) | = l ( 3 2 1 ) 这就是支持向量机。 概括地浇，支持向量机就是首先通过用内积函数定义的非线性变换将输入空间 变换到一个高维空间，在这个空间中求( 广义) 最优分类面。s v m 分类函数形式上类 似于一个神经网络，输出是中问节点的线性组合，每个中间节点对应个支持向量 如图3 3 所示 第3 章文本分类方法对比研究 ， 图3 3 支持向量机示意图 3 3 3 核函数 s v m 中不同的内积核函数将形成不同的算法 类，一是多项式核函数 k ( x ，工，) = ( z x ，) + l 】。 目前研究最多的核函数主要有三 所得到的是9 阶多项式分类器：二是径向基函数( r b f ) i 工一工i 2 k ( x ，一) = e x p 卜了卫一) 矿。 ( 3 2 2 ) ( 3 2 3 ) 所得分类器与传统r b f 方法的重要区别是，这里每个基函数中心对应一个支持向量， 它们及输出权值都是由算法自动确定的。也可以采用s i 鲫o i d 函数作为内积，即 石( 工，x ：) = t a l l h ( v ( x 茁，) + c ) ( 3 2 4 ) 这时s v m 实现的就是包含一个隐层的多层感知器，隐层节点数是由算法自动 确定的，而且算法不存在困扰神经网络方法的局部极小点问题。 s v m 问题可以通过二次线性规划技术来计算。可以通过在s v m 中引入软分类边 界( s o f tm a r g i n ) 或者将原来的数据空间映射到更高维空间( 该空间中的新特征包含 原空间中特征的交互作用，该新空间中线性可分) 的方法将解决线性可分情况推广 到解决线性不可分的情况。 3 3 4 实现技术 支持向量分类的关键是解得d ，f _ l ，2 ，h ，但是实践中训练集很大是直接使用 茎主兰堑塑苎垫些兰查坌耋查鲨! 堕王一 标准技术的障碍，因为仅仅存储系数矩阵就需要一个随样本大小二二次增长的内存空 间，即使样本只有几于个，内存空间电要超出上百兆字节。 基于以上原因，下面我们介绍序贯最小优化算法( s m o ) ： s m o 算法是将分解算法思想推向极致得出的，而每次迭代仅优化两个点的最小 子集。这项技术的威力在于两个数据点的优化问题可咀获得解析解，从而不需要将 二次规划优化算法作为算法一部分。 对条件y 。d ，= o 需要在迭代中实现，意味着每步能优化的乘子最小个数为2 无论何时一个乘子被更新，至少需要调整另 每步s m 0 选择两个元素e 和a 。共同优化- 个元素参数的最有值，并更新相应的口向量。 个点的乘子的优化可以获得解析解。 个乘子来保持条件成立。 在其他参数固定的前提下，找到这两 这两个点的选择是启发式的，而这两 s m 算法的伪码和软件包可以在网站! 型：! 业q ! ! ! 二! ! ! ! ! ! ：盟! 上获得。 34 实验结果与分析 从w w w y a h o o c o f r 【c n 上随机下载有关汽车、房地产、经济、计算机和环境j 类将近7 0 0 篇文本选出3 0 0 篇文章作为本实验的语料，随机地选2 0 0 篇作为训练集， 剩下的1 0 0 篇作为测试集。为了测试分类器的各项性能，我们以信息增益为特征选 择函数，先计算每个特征的信息增益值，对它们从大到小排序，取前3 0 0 0 个词作 为最终的特征词，然后利用t f i d f 公式计算权重，最后选用不同的分类器进行训 练和测试。在进行概率估计时，我们分别采用了词频型和文档型概率估计方法。词 频型即当文档中出现该词时用出现次数计算概率，否则为o ；文档型即当文档中出 现该词时用1 计算概率，否则为0 。基于两种概率估计方法的三种分类方法比较情 况见表3 1 和表3 2 。 从表3 1 不难看出，汽车类、环境类和经济类s v m 法的f 值高于n a i v eb a y e s 和k n n 法，房地产类n a i v eb a y e s 的f 。值高于s v m 法和k n n 法，其原因是由于语料 的各个类别间有交叉，但平均性能s v m 的f ，值高于其他两种方法，n a i v eb a y e s 的 f 。值高于k n n 法。从表3 2 可以看出，房地产类、汽车类、经济类和计算机类的f 值高都高于其他两种，经济类、环境类和计算机类k n n 法的f 。值高于n a i v eb a y e s ， 总体看以文档型作为概率估计方法s v m 的f 。值高于k n n ，而k n n 的f 。值高于n a i v e b a y e s 。由于n a i v eb a y e s 更依赖特征词的频次的统计，所以以词频型作为概率估 ， 第3 章义奉分类方法对比研究 计方法时n a i v eb a y e s 的各项性能要高于k n n ，而以文档型作为概率估计方法时则 不然。综上分析，我们可以得出以下结论： 表3 1 词频型的分类方法对比表 n a i v eb a y e s ( )k n n 法( )s v m ( ) 查准率查全率 f 、值 查准率商全率f 值商准率查全率 r 值 瞎鲍产 9 0 9 11 0 09 5 2 3 97 91 6 79 5 8 63 6 4 9 04 7 69 59 2 6 8 3 汽车 1 0 09 59 7 4 3 68 01 0 08 8 8 8 99 5 2 3 81 0 09 7 5 6 1 环境 8 2 6 19 58 83 7 38 9 4 7 48 58 7 1 89 4 7 3 79 09 2 3 0 8 经济 9 3 3 37 0 7 9 9 9 99 3 3 3 3 7 0 8 0 9 4 7 3 79 09 2 3 0 8 计算机 9 5 2 41 0 09 75 6 29 41 1 88 08 6 4 8 79 59 59 5 平均性能 9 2 4 1 89 29 2 2 0 98 68 68 6 9 49 49 4 表3 2 文档型的分类方法对比表 n a j v eb a y e s ( )k n n 法( ) s v m ( ) 查准率查全率f 值查准率查全率f 。值查准率查全率f 。值 房地产 8 63 69 59 0 4 7 49 09 0 9 1 0 08 5 2 3 88 6 9 5 71 0 09 3 0 2 4 汽车 1 0 0 9 59 7 4 3 6 7 4 0 7 41 0 08 5 1 0 61 0 01 0 01 0 0 环境 8 2 3 57 07 5 6 7 49 4 1 1 8 8 08 6 4 8 7 8 8 8 8 98 08 42 1 1 经济 9 2 3 16 07 2 7 2 89 4 1 1 88 08 64 8 78 9 4 7 4 8 58 7 1 8 计算机 6 8 9 71 0 08 1 6 3 69 4 1 1 8 8 08 6 4 8 79 59 59 5 平均性能 8 5 9 9 88 48 4 9 8 78 88 88 8 9 29 29 2 不管概率估计方法是采取词频型还是文档型，支持向量机方法的查准率、查全 率和f 。值都高于朴素贝叶斯方法和k n n 方法，这说明支持向量机是进行文本分类的 较好的方法，因此本文选用支持向量机作为分类器。 但是在文本分类中，向量的维数少则几千维多则几万维，每一维是一个特征词， 于是导致支持向量机有如下缺点： 2 3 摧于支持向量机的文本分类方法研究 ( 1 ) 输入量太大，分类过程中的计算量也相应会很大，训练时间就要长： ( 2 ) 在如此多的特征中不能确定数据中哪些特征是冗余的，哪些是有用的，哪些 作用大，哪些作用小； ( 3 ) 特征向量的维数很难确定。 3 5 本章小结 本章对朴素贝叶斯、k n n 法和支持向量机三种国内外研究较多、分类性能较好 的分类方法进行了对比研究，并做了对比实验。实验中采用了文档型和词频型两种 概率估计方法，利用查准率、查全率以及f 1 值评价了分类器的性能，实验结果显示 在两种概率估计模型下s v m 都是进行文本分类最好的一种方法。最后分析了支持 向量机在文本分类中存在的缺点。 第4 章基于粗糙集与支持向量机融合技术的文本分类方法 第4 章基于粗糙集与支持向量机融合技术的文本分类方法 4 1 粗糙集理论 粗糙集( r 。u g hs e t s ) 理论j “州是波兰数学家p a w l a k 于1 9 8 2 年提出的一种 数据分析理论，该理论是一种新型的处理模糊和不确定知识的数学工具。该理论从 提出以来已经在数据的决策与分析、模式识别、机器学习与知识发现等方面得到成 功应用，现已成为一种从海量数据中挖掘潜在的、有利用价值的信息( 有用知识) 的有效工具。其主要思想是在保持分类能力不变的前提下，通过知识约简，导出问 题的决策或分类规则。其最大特点是：不需要提供问题所需处理的数据集合之外的 任何先验信息，且基本思想清晰、便于操作。 4 1 1 粗糙集的基本概念 ( 1 ) 知识与不可区分关系 假设u 是人们感兴趣的对象组成的集合，称为论域。任何子集爿u ，称为u 中 的一个概念或范畴。u 中的任何概念族称为关于u 的抽象知识，简称知识。设r 为 论域u 上的一个等价关系，u r 为r 的所有等价类构成的集合。一个知识库就是一 个关系系统丘= ( u ，r ) ，其中v 是论域，r 是u 上的一族等价关系。 不可区分关系是指对象由属性集p 表示时，在论域u 上的等价关系。若属性集 p r ，对象x ，j ，u ，对于每个q p ，当且仅当厂( x ，q ) = ( y ，q ) 时，x 和y 是不 可区分的，即有 加d ( p ) = ( z ，l ，) u ：v q p ，( ，q ) = ，( y ，q ) ) a 加d 口) 的等价类称为知识p 的基本概念或基本范畴。 不可区分关系的概念是粗糙集理论的基石，它揭示出论域知识的颗粒状结构 ( 2 ) 决策表、约简与核 在粗集理论中，为了处理智能数据，需要进行知识的表达。知识表达系统的基 本成分是研究对象的集合，关于这些对象的知识是通过指定对象的基本特征( 属性) 和它们的特征值( 属性值) 来描述的。一个知识表达系统s 可以表达为 s = 其中： u ：对象的非空有限集合，称为论域； 爿：属性的非空有限集合； 基于支持向量机的文本分类方法研究 = u 圪：圪是属性a 的值域； d ：( ，爿一矿是一个信息函数，它为每个对象的每个属性赋予一个信息值 即v 口爿，互u ，厂( x ，以) 圪。 知识表达系统也称为信息系统。信息系统的数据以关系表的形式表示。关系表 的行对应要研究的对象，列对应对象的属性，对象的信息是通过指定对象的各属性 值来表达。 设s = 为知识表达系统，爿= c u d ，c n d = ，c 称为条件属性集 d 称为决策属性集。具有条件属性和决策属性的知识表达系统称为决策表。 知识库中的知识( 属性) 并不是同等重要的，甚至其中某些知识是冗余的，所 以需对其进行简约。所谓决策表的属性约简，就是在保持知识库分类能力不变的条 件下，删除其中不相关或不重要的知识。 下面介绍约简和核的概念。 设u 是一个论域，p 是定义在u 上的一个等价关系簇，r p 。如果 加d ( 尸 r ) = 加d ( 尸) ，则称关系r 在p 中是绝对不必要的( 多余的) ；否则，称r 在 p 中是绝对必要的。 绝对不必要的关系在知识库中是多余的，如果将它们从知识库中去掉，不会改 变该知识库的分类能力。相反，若知识库中去掉一个绝对必要的关系，则一定改变 知识库的分类能力。 设u 是一个论域，p 是定义在u 上的一个等价关系簇，r p 。如果每个关系 月，在p 中都是绝对必要的，则称关系簇p 是独立的；否则，称尸是相互依赖的。 对于相互依赖的关系簇来说，其中包含有冗余关系，可以对其约简：而对于独 立的关系簇，去掉其中任何一个关系都将破坏知识库的分类能力。 设u 是一个论域，p 是定义在u 上的一个等价关系簇，尸中所有绝对必要关系 组成的集合称为关系簇p 的绝对核