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

大连理工大学博士学位论文 摘要 支持向量机作为一种基于统计学习理论的新型机器学习方法，较好地解决了非线 性、高维数、局部极小点等实际问题，是机器学习领域新的研究热点。文本分类是基于 内容的自动信息管理的核心技术。文本向量稀疏性大、维数高、特征之间具有较大的相 关性，支持向量机对于特征相关性和稀疏性不敏感，处理高维数问题具有较大的优势， 因此，支持向量机在文本分类中具有很大的应用潜力。但是，由于文本分类具有类别和 样本数目多等特点，因此，支持向量机用于文本分类时仍有许多尚未完全解决的问题。 例如，增量学习、兼类分类、训练和分类速度较慢等。本文主要针对支持向量机在文本 分类等实际应用中存在的一些问题进行深入研究，主要工作如下： 1 对支持向量机兼类分类算法进行了研究。针对规模较小、类别数较多的兼类样本 集，提出了一种基于1 a - r 方法的兼类分类算法。该算法用1 a - r 方法训练模糊子分类器， 对待分类样本，通过子分类器得到其对应的隶属度向量，依据隶属度向量判定其所属类 别。针对规模较大、类别数较少的兼类样本集，提出了一种基于1 a - 1 方法的兼类分类 算法。该算法用1 a - 1 方法训练模糊子分类器，对于待分类样本，通过子分类器得到其 对应隶属度矩阵，依据隶属度矩阵每行元素和判定该样本所属类别。针对规模较大、类 别数较多的兼类样本集，提出了一种超球支持向量机兼类分类算法。该算法对每一类样 本分别训练球超，通过计算待分类样本到各超球球心的距离确定其类别。实验表明，三 种算法都能有效地实现兼类分类，扩展了支持向量机的分类能力。 2 对支持向量机增量学习算法进行了研究。提出了一种加权类增量学习算法，该算 法是对c i l 算法的改进，通过加入类权值，解决了因两类训练样本不平衡而造成的小类 别分类精度较低的问题。实验证明，与c i l 算法相比，该算法在不降低分类速度的前提 下，提高了小类别的分类精度。同时，提出了一种新的类增量学习算法，该算法利用超 球支持向量机进行分类。增量学习过程中，先对新增类别训练超球，然后对新增样本兼 有的历史类别重新训练超球。在很小的样本集，很小的空间代价下实现类增量学习，同 时保留了历史训练结果。该算法对单号样本和多标号样本都适用，便于改进和扩充。实 验证明，该算法具有较高的训练速度、分类速度和分类精度，增强了支持向量机的学习 能力。 3 对支持向量机快速分类算法进行了研究。在分析了现有支持向量集缩减方法的基 础上，提出了一种支持向量机快速分类算法，该算法是对f c s v m 算法的改进。该算法利 用二分法选取支持向量子集，然后采用变换的方式，用选取的支持向量子集代替全部支 基于支持向量机的文本分类算法研究 持向量进行分类计算。实验结果表明，该算法在不损失分类精度的前提下，进一步缩减 了决策函数中的支持向量，提高了支持向量机的分类速度。 4 对模糊支持向量机训练算法进行了研究。针对大规模训练集，提出了一种利用最 大违反对选择工作集训练模糊支持向量机的算法。在此基础上，又提出了一种利用目标 函数的二阶近似信息选取工作集训练模糊支持向量机的算法。实验表明，两种算法都能 实现模糊支持向量机的快速训练。两种算法相比，第二种算法的训练速度更快，训练样 本集规模越大，效果越明显。 关键词：支持向量机；文本分类；兼类分类；增量学习；超球 大连理工大学博士学位论文 s t u d y o nt e x tc l a s s i f i c a t i o na l g o r i t h m sb a s e do ns v m s a b s t r a o t s u p p o r tv e c t o rm a c h i n e s ( s v m s ) a san e wm a c h i n el e a r n i n gm e t h o db a s e do ns t a t i s t i c a l l e a r n i n gt h e o r y h a v ea t t r a c t e dm o r ea n dm o r ea t t e n t i o na n db e c a m eah o ti s s u ci nt h ef i e l do f m a c h i n el e a r n i n g ，b e c a u s et h e yc a r lw e l lr e s o l v es u c hp r a c t i c a lp r o b l e m sa sn o n l i n e a r i t y ，h i g h d i m e n s i o na n dl o c a lm i n i m a t e x tc a t e g o r i z a t i o ni sak e yt e c h n i q u ei nc o n t e n t b a s e d a u t o m a t i ci n f o r m a t i o nm a n a g e m e n t t e x tv e c t o r sa r eh i g hd i m e n s i o n a la n de x t r e m e l ys p a r s e ， a n dh a v en u m b e r so fr e l e v a n tf e a t u r e s s v m sa r ep a r t i c u l a r l ys u i t e df o rt e x tc a t e g o r i z a t i o n a n dh a v eg r e a tp o t e n t i a li nt e x tc a t e g o r i z a t i o n ，a ss v m sa r en o ts e n s i t i v et or e l e v a n tf e a t u r e s a n ds p a r s ed a t a , a n dh a v ea d v a n t a g e si nd e a l i n g 诵mm 曲d i m e n s i o n a lp r o b l e m s h o w e v e r ， t e x tc a t e g o r i z 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 sa n dt r a i n i n ge x a m p l e s ， t h e r e f o r et h e r ea r es t i l lm a n yo n g o i n gr e s e a r c hi s s u e st os v m si nt e x tc a t e g o r i z a t i o n a p p l i c a t i o n ，s u c ha l si n c r e m e n t a ll e a r n i n g ，m u l t i l a b e lc l a s s i f i c a t i o n ，a n dl o w e rs p e e di n t r a i n i n ga n dc l a s s i f i c a t i o ne t c t h i sp a p e rm a i n l yf o c u s e so nt h ed r a w b a c k so fs v m si nt h e p r a c t i c a la p p l i c a t i o ni n c l u d i n gt e x tc a t e g o r i z a t i o n ，a n dt h em a i n w o r ki sa sf o l l o w s ： 1 m u l t i - l a b e lc l a s s i f i c a t i o na l g o r i t h m sf o rs v m sa r es t u d i e d f o rt h et r a i n i n gs e tw i m m o r es a m p l e sa n df e w e rc l a s s e s ，b a s e do nl a - 1 m e t h o d ，am u l t i l a b e lc a t e g o r i z a t i o n a l g o r i t h mi sp r e s e n t e d t h ea l g o r i t h mu s e sl a 1m e t h o dt ot r a i nf u z z ys u b c l a s s i f i e r s f o rt h e s a m p l et ob ec l a s s i f i e d ，t h es u b c l a s s i f i e r sa r eu s e dt oo b t a i nt h em e m b e r s h i pm a t r i x ，a n dt h e n t h es u mo fe v e r yr o wo fm e m b e r s h i pm a t r i xa r eu s e dt oc o n f i r mt h ec l a s s e st h es a m p l e f o r t h et r a i n i n gs e tw i t hf e w e ts a m p l e sa n dm o r ec l a s s e s b a s e do n1 a 1m e t h o d 。am u l t i 1 a b e l c a t e g o r i z a t i o na l g o r i t h mi sp r e s e n t e d 1 1 1 ea l g o r i t h mu s e s 1 - a - rm e t h o dt ot r a i nf u z z y s u b c l a s s i f i e r s f o rt h es a m p l et ob ec l a s s i f i e d t h es u b c l a s s i f i e r sa r eu s e dt oo b t a i nt h e m e m b e r s h i pv e c t o r a n dt h e nt h em e m b e r s h i pv e c t o ri su s e dt oc o n f i r mt h ec l a s s e so ft h e s a m p l e f o rt h et r a i n i n gs e tw i t hm o r es a m p l e sa n dm o r ec l a s s e s ，b a s e do nh y p e rs p h e r e ，a m u l t i - l a b e l c a t e g o r i z a t i o na l g o r i t h mi sp r e s e n t e d f o re v e r yc l a s s ，t h eh y p e r s p h e r et h a t c o n t a i n sm o s ts a m p l e so ft h ec l a s si st r a i n e d f o rt h es a m p l et ob ec l a s s i f i e d t h ed i s t a n c e s f r o mi tt ot h ec e n t r eo fe v e r yh y p e r s p h e r ea r eu s e dt oc o n f i r mt h e c l a s s e so ft h es a m p l e e x p e r i m e n t a l r e s u l t si n d i c a t et h e a l g o r i t h m sh a v eb e t t e rp e r f o r m a n c e o nm u l t i - l a b e l c l a s s i f i c a t i o n 2 i i l c r e m e n t a ll e a r n i n ga l g o r i t h m sf o rs v m sa r es t u d i e d aw e i g h t e dc l a s si n c r e m e n t a l l e a r n i n ga l g o r i t h mi sp r e s e n t e d ，w h i c hi m p r o v e st h ec l la l g o r i t h m t h ea l g o r i t h ma d d st h e w e i g h so fc l a s st ot r a i n i n gs a m p l e s e x p e r i m e n t a lr e s u l t si n d i c a t et h a t ，c o m p a r ew i t hc i l i i i 基于支持向量机的文本分类算法研究 a l g o r i t h m ，t h em e t h o di n c r e a s e sp r e c i s i o no ft h ec l a s sw i t hf e w e rs a m p l e si nt h ec o n d i t i o nt h a t t h ec l a s s i f i c a t i o ns p e e dd o e sn o td e c r e a s e b e s i d e s ，b a s e do n h y p e rs p h e r es v m s ，an e w c l a s s i n c r e m e n t a ll e a r n i n ga l g o r i t h mi sp r e s e n t e d t h eh y p e r s p h e r e so ft h en e wc l a s s e sa r et r a i n e d 。 a n dt h ep r i m a lh y p e r s p h e r e st l l a tt h e yc l a s s e se x i s ti nn e wi n c r e m e n t a ls a m p l e sa r er e t r a i n e d 1 1 1 ec l a s si n c r e m e n t a ll e a r n i n gi sr e a l i z e di nas m a l lt r a i n i n gs e ta n das m a l lm e m o r y s p a c e t h eh i s t o r yr e s u l t sa r es a v e da tt h es a m et i m e t h ea l g o r i t h mi ss u i t a b l ef o rb o t hs i n g l e 1 a b e l t r a i n i n gs e ta n dm u l t i - l a b e lt r a i n i n gs e t i ti sc o n v e n i e n c et oi m p r o v e m e n ta n de x t e n s i o n e x p e r i m e n t a lr e s u l t si n d i c a t et h a tt h ea l g o r i t h mh a sah i g hp e r f o r m a n c eo nt r a i n i n gs p e e d ， c l a s s i f i c a t i o ns p e e da n dp r e c i s i o n 3 f a s tc l a s s i f i c a t i o na l g o r i t h mf o rs v m si ss t u d i e d s e v e r a l e x i s t i n gm e t h o d so f r e d u c i n gs u p p o r tv e c t o r ss e ta r ea n a l y z e d t h e n ，am e t h o do fr e d u c i n gs u p p o r tv e c t o r ss e ti s p r e s e n t e d ，w h i c hi m p r o v e sf c s v ma l g o r i t h r n t h em e t h o du s e sd i c h o t o m yt os e l e c tas u b s e t o fs u p p o r tv e c t o r s a f t e rt h et r a n s f o r m a t i o no nt h ef u ns e to fs u p p o r tv e c t o r s t h es u b s e to f s u p p o r tv e c t o r si su s e di nc l a s s i f i c a t i o n t h ee x p e r i m e n t a lr e s u l t si n d i c a t et h a t c o m p a r e dw i t h f c s v ma l g o r i t h m ，t h em e t h o dr e d u c e st h en u m b e ro fs u p p o r tv e c t o r st ot h eg r e a t e s tg r a d e a n di n c r e a s e sc l a s s i f i c a t i o ns p e e do fs v m si nt h ec o n d i t i o nt h a tt h ec o r r e c tr a t ed o e sn o t d e c r e a s e 4 f a s tt r a i n i n ga l g o r i t h m sf o rf u z z ys v m sa r es t u d i e d f o rt h e t r a i n i n gs e tw i t ha n u m b e ro fs a m p l e s ，am e t h o do fw o r k i n gs e ts e l e c t i o nu s i n gm a x i m a lv i o l a t i n g p a i rf o r t r a i n i n gf u z z ys v m si sp r o p o s e d b e s i d e s ，am e t h o do fw o r k i n gs e ts e l e c t i o nu s i n gs e c o n d o r d e ri n f o r m a t i o nf o rt r a i n i n gf u z z ys v m si sp r o p o s e d e x p e r i m e n t a lr e s u l t si n d i c a t et h a tt w o m e t h o d sr e a l i z ef a s tt r a i n i n go ff u z z ys v m s o ft h et w ot h el a t t e ri sf a rb e t t e rt h a nt h ef o r m e r e s p e c i a l l yi n t h ec a s eo fl a r g en u m b e ro ft r a i n i n gs a m p l e s k e yw o r d s ：s u p p o r tv e c t o rm a c h i n e s ；t e x tc a t e g o r i z a t i o n ；m u l t i l a b e lc l a s s i f i c a t i o n ； i n c r e m e n t a ll e a r n i n g ；h y p e rs p h e r e i v 独创性说明 作者郑重声明：本博士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 爪乏、c ； 、。 大连理工大学博士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名： 导师签名： 系易，巴 ， 一 l 豸叫 大连理工大学博士学位论文 1 绪论 1 1 研究的背景和意义 随着信息存储技术和通讯技术的迅猛发展，大量的文字信息开始以计算机可读的形 式存在，并且其数量每天都在急剧增加。如何有效地组织和管理这些文本数据，并快速、 准确、全面地从中找到用户所需要的信息就成为当前信息科学和技术领域迫切需要解决 的重要问题。 传统的文本分类工作是由特定领域的专家人工完成的，这种人工分类方法周期长、 费用高、效率低，特别是随着文本信息量的大量增加，人工方法己经很难满足分类的需 求，因此，利用计算机对文本进行自动分类( a u t o m a t i ct e x tc a t e g o r i z a t i o n ，a t c ) 日 益受到重视。 基于数据的机器学习( m a c h i n el e a r n i n g ) 是数据挖掘技术中的重要内容，它研究从 观测数据出发寻找规律，并利用这些规律对未来数据或无法观测的数据进行预测。文本 挖掘是指从文本形式的数据中寻找和发现有用信息的过程，它包括信息的检索与分析、 文本分类、文本信息的评测等基本操作。其中，文本分类( t e x tc a t e g o r i z a t i o n ) 作为 处理和组织大量文本数据的关键技术，可以在较大程度上解决信息杂乱现象的问题，方 便用户准确地定位所需的信息和分流信息。因此，文本分类作为信息过滤、信息检索、 搜索引擎、文本数据库、数字化图书馆等领域的技术基础，有着广泛的应用前景。 现有机器学习方法共同的重要理论基础之一是统计学。传统统计学研究的是样本数 目趋于无穷大时的渐近理论，但在实际问题中，样本数目往往是有限的，因此，一些理 论上很优秀的学习方法在实际中的表现却不尽人意。支持向量机( s u p p o r tv e c t o r m a c h i n e s ，s v m s ) 是二十世纪九十年代中期在统计学习理论基础上发展起来的一种新型 机器学习方法。支持向量机采用结构风险最小化准则( 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 ) 训练学习机器，其主要优点有：专门针对有限样本情况，其目标是得到现有信息下 的最优解而不仅仅是样本数趋于无穷大时的最优值；算法最终将转化成为一个二次型寻 优问题，从理论上说，得到的将是全局最优点，解决了在神经网络方法中无法避免的局 部极值问题：算法将实际问题通过非线性变换转换到高维的特征空间( f e a t u r es p a c e ) ， 在高维空间中构造线性判别函数来实现原空间中的非线性判别函数，特殊性质能保证机 器有较好的推广能力，同时它巧妙地解决了维数问题，其算法复杂度与样本维数无关。 文本向量稀疏性大、维数高、特征之间具有较大的相关性，支持向量机对于特征相 关性和稀疏性不敏感，处理高维数问题具有较大优势，因此，支持向量机非常适用于文 基于支持向量机的文本分类算法研究 本分类问题，并且取得了比其它文本分类算法更好的分类效果。另外，支持向量机的泛 化性能并不依赖全部训练数据，而是该全部数据的一个子集，即支持向量集。由于支持 向量的数目同整个训练数据集数目相比是很小的，因此，支持向量机是增量学习强有力 的工具，在文本分类中具有很大的应用潜力，能够解决文本分类中许多用其它方法难以 解决的问题。但是，支持向量机从提出到现在只有几年的时间，还有很多尚未解决或尚 未充分解决的问题。首先，缺乏有效的用于如兼类文本等多标号问题的分类方法。在实 际应用中，多标号问题非常普遍，用支持向量机对多标号问题分类方法的研究具有很重 要的实用价值。其次，模糊支持向量机在实际应用中非常普遍，但用于如文本分类等训 练规模较大的分类问题，其训练速度较慢。如何选择工作集，减少训练时间，以满足实 际应用的需要，是一个具有重要理论和实际意义的研究课题。再次，对于文本分类问题， 支持向量机中的支持向量较多，分类速度较慢，这一点限制了支持向量机在文本分类中 的应用，是支持向量机进入大规模实用化阶段的瓶颈。如何缩减决策函数中的支持向量， 提高支持向量机的分类速度是支持向量机研究中的重要问题，该问题的研究对于支持向 量机方法在实际应用中的推广具有重要意义。另外，缺乏有效的支持向量机增量学习方 法。在实际应用中，增量学习问题非常普遍，如何充分利用历史学习结果实现样本增量 学习和类增量学习，是支持向量机研究中的重要课题。 总之，文本分类有着广阔的应用前景，可以创造巨大的经济和社会效益。针对支持 向量机在文本分类等实际应用中存在的问题进行深入研究，对于支持向量机方法的完善 和文本分类技术的广泛应用都具有重要意义。 1 2 自动文本分类技术 自动文本分类就是在给定的分类体系下，由计算机系统根据待分类文本的内容自动 确定文本类别( 也称主题) 的过程【l 】。分类体系一般由人工构造，著名的分类体系有 r e u t e r s 分类体系和中图分类体系等。 依据文本所属类别的个数( 即类别标号的个数) ，文本分类问题可区分为单标号 ( s i n g l e l a b e l ) 文本分类和多标号( m u l t i l a b e l ) 文本分类。单标号文本是指只属于一 个类别的文本，单标号文本又称单主题文本。多标号文本是指同时属于两个或两个以上 类别的文本，多标号文本又称多主题文本或兼类文本。 从数学角度来看，文本分类是一个映射过程，它将待分类文本映射到已有的类别中， 该映射可以是一对一映射，也可以是一对多的映射，因为一篇文本可以涉及多个主题。 数学描述如下： 大连理工大学博士学位论文 厂：a 专b 其中，彳为待分类的文本集合，曰为分类体系中的类别集合，厂是映射 规则。 自动文本分类的映射规则厂是系统根据已经掌握的每类若干样本的数据信息，总结 出分类的规律性而建立的判别公式和判别规则。然后在遇到新文本时，根据总结出的判 别规则，确定文本所属的类别。 训练过程 分类过程 训练文本l 预处理广 、l 特征项 选取 上 f 训练文本l 再处理l 图1 1 文本分类流程 f i g 1 1t e x tc a t e g o r i z a t i o np r o c e s s 在实际分类时，首先将文本表示成以词为元素的向量，接着按某种方法进行特征选 取，然后将特征用权值表示。这样就可以对词权值表示的文本向量进行训练，得到决 策模型。分类时，也将待分类文本表示成词权值向量，并用训练得到的模型进行分类， 最终判断其类别。通用的文本分类流程如图1 1 所示。 由自动文本分类的流程可知，文本自动分类主要包括文本预处理、文本的表示、文 本特征的选取、文本分类算法和文本分类的性能评估等。 1 2 1 文本预处理 文本预处理的主要任务是剔除文本中所有与分类任务无关的内容，并将文本转化为 由其包含的基本语义单位组成的表列。 文本预处理的首要工作是分词，分词的关键在于如何选择恰当的基本语义单位。在 西文文本分类研究中，通常将单词作为基本语义单位，并忽略大小写对单词语义的可能 影响。因此，将文本中出现的所有大写字母转换为小写字母形式，把空格、标点符号等 非字母字符作为分隔符，就可以方便地将文本转化为由语义单位( 单词) 组成的表列。 与西文文本相比，中文文本没有类似于空格之类的标示词边界的标志。中文文本自 动分词的任务就是由计算机在中文文本的基本语义单位之间自动加上空格。目前，常见 基于支持向量机的文本分类算法研究 的分词算法可以分成三大类：基于字符串匹配的分词方法、基于理解的分词方法和基于 统计的分词方法乜一1 。 1 2 2 文本表示 人在阅读文章后，根据自身的理解能力和已掌握的知识可以对文章内容产生模糊的 认识。计算机并不具备人类这样的智能，因而它并不能轻易地“读懂 文章。因此，文 本自动分类遇到的基本问题是如何将文本按照计算机可以“理解 的方式进行有效的表 示，从而在这个表示的基础上进行分类。目前文本表示主要是应用g s a l t o n 于1 9 6 9 年提 出的向量空间模型( v e c t o rs p a c em o d e l ，v s m ) “3 。向量空间模型的基本思想是把文本简 化为以特征项的权重为分量的向量表示：( ，w 2 ，) ，其中心为第i 个特征项的权重。 因此，基于向量空间模型的分类中，关键的一步就是如何从文本中提取反映类别的有效 特征。一般可以选择字、词或词组作为文本的特征，根据实验结果，普遍认为选取词作 为特征项要优于字和词组。对于中文文本，因为词与词之间没有明显的切分标志，所以 首先还需要分词处理。 在向量空间模型中，文本集合是使用词文本矩阵a 来表示的，其中每一项表示一 个词在某个文本中的权重： a = ( ) 肘。 ， ( 1 1 ) 这里表示词f 在文本中的权重( w e i g h t i n g ) ，m 为文本集合中出现的词的个数，为 文本集合中文本的总数。 近年来，文本自动分类中使用较多的权重计算方法【5 】包括布尔权重、词频权重、 t f i d f 权重、t f c 权重、l t c 权重和熵权重等。其中，卵枣i d f 权重是在文本处理 领域中使用最广泛的数值权重计算方法。该方法基于以下原因：一是特征f 在文档j f 中 出现次数越多，越重要；二是文档集中含有特征f 的文档数越多越不重要。卵宰d f 方 法基于的思想和构造的统计量都很简单，并且在实际应用中表现了很好的性能。它有多 种计算方法，目前较为常用的为式( 1 2 ) 。 r 嘞= 厶l o g ( 。- o l ) ( 1 2 ) 1 啊 其中，z ，表示词f 在文档中出现的频率，为文本集合中文本的总数，n ，为词f 在文 本集合中出现的总次数。 一4 一 大连理工大学博士学位论文 1 2 3 文本特征提取 将文本表示成特征向量时，原始特征集由出现在文本集中的所有词条组成。无论采 用什么样的文本表示模型，中等规模的文本分类问题所对应的原始特征集通常都高达几 万维、甚至十几万维。因此我们需要进行特征降维，这样做的目的主要有两个：第一， 如果直接在这样一个高维特征空间上进行训练和分类，计算量过大，降维可以提高程序 的执行效率和运行速度；第二，所有词条对文本分类的意义是不同的，一些通用的、各 个类别都普遍存在的词条对分类的贡献小，在某特定类中出现比重大而在其他类中出现 比重小的词条对文本分类的贡献大，降维可以提高分类器的推广能力。 特征降维就是从原始特征集t = 瓴，f 2 ，t ，) 中选择一个真子集t = 7p l ，r p 。) ， 满足见 0 ，称x ，为支持向量：如果口? = c ，称x ，为 边界支持向量：如果0 口? 0 ，称薯为支持向量；如果口? = c ， 界支持向量：如果0 口? - y ，a ，k ( x ，x ) - b 。) ( 3 6 ) 3 3 利用s m o 算法训练模糊支持向量机 3 3 1 停机准则 在介绍利用s m o 算法训练模糊支持向量机之前，先讨论停机准则。 对于对偶问题( 3 5 ) ，它的l a g r a n g e 函数为： 扛三1w r w 一啦一匹+ s 旭一c , ) - p z y 。 其中，4 ，墨，分别为约束0 ，印，y t 口= o 的l 删g e 乘子。 口是d h - - 次规划问题( 3 5 ) 的解的汀条件为，存在l a g r a n g e 乘子万，占，满足： o 口，sc 0 j ，f = l ，2 ，口7 y = 0 ； o a 一p 一y 一万+ s = 0 ，s 0 ，万0 ； s ；缸c - ，) = 0 ，i ：1 纠2 一，8 * t o t = 0 由此可以得到如下停机准则： ( 3 7 ) ( 3 8 ) ( 3 9 ) 基于支持向量机的文本分类算法研究 q s 仅js c j j = 1 , 2 ，l ，y l a2 0 1 0 ) ， i 1 x h = o y j ( y ，k ( x i , x j ) 一) = 1 f0 吩 印j ) ( 3 1 1 ) 扭1 【1( x i 哆= 印， 对偶问题( 3 5 ) 的k k t 条件还可以描述为： 罢：( 鼻一) ”一4 - ! - $ i = 0 ，4 o ，谚q ：0 ，每o ，s ，( 口，一c ，) ：o ，v f ( 3 1 2 ) o 倪j 其中，e = y j k ( x ，x j ) - y ， 最优性条件可以简化为： f 0i f 口，= 0 ( e - p ) y ， = 0 f0 口， c 一， ( 3 1 3 ) b 0 矿= c 0 ， 令 厶= f ff0 口， ) 厶= ，2 = 乞或者f ，j i l o ，e o ，d ， 0 。这对应于f i p 缸) ， 。) ，并且目标函数的最小 值点为d 产l ，d = - 1 。当一y v p ( a ) ， ( 3 3 9 ) 证毕 由此可知，利用最大违反对选择工作集其实质是利用目标函数的一阶近似信息，工 作集选取的时间复杂度为d “) ，选取速度较快。文献 1 0 0 j 给出了算法的收敛性证明。 利用最大违反对选择工作集的模糊支持向量机训练算法描述如下： 步骤l ：取初始点口1 ，令k = 1 ： 步骤2 ：如果口满足