（运筹学与控制论专业论文）数据挖掘中若干数学模型与算法研究.pdf

大连理工大学硕士学位论文 摘要 近年来，由于计算机和信息技术的快速发展，人们需要花费昂贵的代价收集、存储 和处理海量的数据。如何“去粗取精”，从j t i 发现有用的信息。已经成为一个迫切需要 解决的问题。数据挖掘技术在这种背景下应运而生。数据挖掘的定义就是：在数据库中 发现有用的、潜在的、最终可理解的模式的非平凡过程。它是一门内容广泛的交叉学 科，涉及机器学习、数学规划、数理统计、神经网络、数据库、模式识别、粗糙集、模 糊数学等相关技术。 数学规划是运筹学一个重要分支，在机器学习、网络问题、博弈理论与经济学、工 程机械学等领域有着广泛而重要的应用，是国际上最活跃的运筹学研究领域之一。现 在，数学规划得到极大的发展，和其他学科结合形成新的研究领域，并不断在新的领域 找到应用。数学规划和数据挖掘技术的结合已使大规模和高复杂性的问题的解决成为可 能。数学规划在特征提取、聚类和回归等方面有很重要的应用，而这些都是数据挖掘亟 待解决的问题。 本文主要致力于支持向量机、近似支持向量机的学习算法研究，特征提取的数学模 型与算法的改进及其应用，聚类分析算法的收敛性证明。 支持向量机是数学规划在数据挖掘领域的一个重要应用。支持向量机是v a p n i k 等 人根据统计学习理论提出的一利嘶的机器学习方法，其本质是数学规划中的二次规划。 如何准确、快速求解二次规划是支持向量机研究的基本问题，而这些问题的解决与数学 规划中的优化理论密切相关。本文研究了支持向量机与近似支持向量机的在线学习算 法，并将支持向量机增量学习算法应用于蛋白质二级结构预测，取得了很好的结果。 特征提取指的是意识到存在无关而多余的特征并要剔除它们，同时对两个集合进行 区分。现存模型在区分高维数据( 例如脑科学中几十万维的数据) 时需要的时间和空间 代价很高，因此需要对有用的特征进行提取。本文对已有支持向量机的特征提取方法进 行了改进。最后将本文的方法应用于一个经典的著作权分析问题一砌pd i s p u t e d f e d e r a l i s t 凡槲，一通过与已有机器学习结果不同的特征得到了与经典著作权分析方法相 同的结论。 聚类分析也是数据挖掘中比较常用的方法，它是一种无监督的学习方法。本文给出 了一种k - m e a n s 聚类分析算法的收敛性证明，为算法的使用提供可靠的理论保证。 数据挖 | f 中若干数学模1 4 与算法研究 本文的意义在于：改进数据挖掘中若干数学模型和算法，提高了它们对现实数据的 适应性；尝试将这些方法应用于新的领域，拓宽了它们的使用范围；给出了一种聚类算 法的收敛性证明，为算法提供可靠的理论保证。 关键词：数据挖掘；数学规划：支持向量机：在线学习；增量学习；特征提取 聚类分析 i i 大连理工大学硕士学位论文 a b s t r a c t i nr e c e n ty e a r s ，w i t ht h ed e v e l o p m e n to fc o m p u t e ra n di n f o r m a t i o n a lt e c h n o l o g y ，p e o p l e n e e de x p e n dr i c hp r i c et oc o l l e c t , s t o r ea n dp r o c e s sm a g n a n i m i t yo fd a t a i ti sa ni m m i n e n t p r o b l e m t os o l v eh o wt oe x t r a c td i s t i l l a t ef r o md r a f ta n df i n du s e f u li n f o r m a t i o n d a t am i n i n g t e c h n o l o g yc o m e si n t ob e i n gi nt h i sb a c k g r o u n d t h ed e f i n i t i o no fk d d i st h i s ：t h es e a r c hf o r u s e f u l ，p o t e n t i a la n du n d e r s t a n d a b l en o n - t r i v i a lp r o c e s sp a t t e r n sf r o m s e t so fd a t a i ti n v o l v ea l o to fi n t e r c m s s s u b j e c t s a n d t e c h n o l o g i e s s u c ha sm a c h m e l e a r n i n g , m a t h e m a t i c a l p r o g r a m m i n g ，s t a t i s t i c s ，n e u r a ln e t w o r k , d a t a b a s e ，p a t t e r nr e c o g n i t i o n ，r o u g hs e t , f u z z y m a t h e m a t i c sa n ds oo n m a t h e m a t i c a lp r o g r a m m i n gi sa l li m p o r t a n tb r a n c ho fo p e r a t i o n a lr e s e a r c h i th a v ea n i m p o r t a n te x t e n s i v ea p p l i c a t i o nt oa r e a s o fm a c h i n el e a r n i n g , n e t w o r k sp r o b l e m ，g a m et h e o r y ， e c o n o m i c s m e c h a n i c sa n di t st h em o s ta d v a n c e da 嘲o fo p e r a t i o n a lr e s e a r c h n o w a d a y s ， m a t h e m a t i c a lp r o g r a m m i n gm a k e sg r e a tp r o g r e s s ，c o n j u r ew i t ho t h e rs u b j e c t st op r o d u c en e w s t u d y a r e a sa n df i n dn e wa p p l i c a t i o ni nn e wa r e a s t h ec o n j u r a t i o n o fm a t h e m a t i c a l p r o g r a m m i n g a n dd a t am i n i n gm a k e si tp o s s i b l et os o l v el a r g e - s c a l ea n d c o m p l i c a t e dp r o b l e m s m a t h e m a t i c a lp r o g r a m m i n gi si m p o r t a n ti nf e a t u r es e l e c t i o n ，c l u s t e r i n ga n dr e g r e s s i o n ，a n d t h e s ea r et h e p r o b l e m s ，w h i c h a r es o l v e di m m i n e n t l y t h i sp a p e r sm a i nw o r k si st h a t ：l e a r n i n ga l g o r i t h ms t u d i e so fs u p p o r tv e c t o rm a c h i n e ， m a t h e m a t i c a lm o d e la n da p p l i c a t i o na b o u tf e a t u r es e l e c t i o n ，c o n v e r g e n c ea n a l y s i so f c l u s t e r i n g a l g o r i t h m s u p p o r tv e c t o rm a c h i n e i sa ni m p o r t a n te x a m p l et h a tm a t h e m a t i c a lp r o g r a m m i n ga p p l i e s i nd a t am i n i n g s u p p o r tv e c t o rm a c h i n ei san e wm a c h i n el e a r n i l l gm e t h o d ，w h i c h i sb r o u g h to u t a c c o r d i n gt os t a t i s t i cl e a r n i n gb yv a p n i k t h e e s s e n c eo f s u p p o r tv e c t o rm a c h i n e i sq u a d r a t i c p r o g r a m m i n g i t i sb a s i cp r o b l e mh o wt os o l v eq u a d r a t i cp r o g r a m m i n ga c c u r a t e l ya n dq u i c k l y ， a n dt h e s ep r o b l e m sh a v ec l o s ec o n n e c t i o nw i t ho p t i m a lt h e o r yi nm a t h e m a t i c a lp r o g r a m m i n g h e r e ，a u t h o rs t u d i e so n - l i n el e a m i n go fs u p p o r tv e c t o rm a c h i n ea n dp r o x i m a ls u p p o r tv e c t o r m a c h i n e ，t h e na p p l i e ss u p p o r tv e c t o rm a c h i n et op r o t e i ns e c o n d a r ys t r u c t u r ep r e d i c t i o n ，a n d r e s u l ti sv e r yw e l l f e a t u r es e l e c t i o ni st h i s ：w h i l ek n o w i n gs u p e r f l u o u sf e a t u r ea n dw a n t i n gt od e l e t et h e m ， w ew o u l dd i s t i n g u i s ht w od a t as e t s e x i s t i n gm o d e l sn e e dt o om u c h t i m ea n d s p a c et op r o c e s s h i g h - d i m e n s i o nd a t a ( f o re x a m p l e , d a t a i nb r a i ns c i e n c e ，w h i c hw i l lb et h o u s a n d so f d i m e n s i o n s ) t h i sp a p e rm a k e s a p r o g r e s si nf e a t u r es e l e c t i o nv i as u p p o a v e c t o rm a c h i n e a t i i i - 数据挖掘中若干数学模型与算法研究 l a s t ，i ti sa p p l i e dt ot h ed i s p u t e d f e d e r a l i s tp a p e r s a l t h o u g hf e a t u r ev e c t o r s , w h i c h a r er e f i n e d b yd i f f e r e n tm l r l s ，a r c h ts a m e ，w e d r a wt h ei d e n t i c a lc o n c l u s i o n s c l u s t e ra n a l y s i si sa l s ot h em e t h o d ，w h i c hi s f r e q u e n t l yu s e di n d a t am i n i n g i ti sa n m e t h o do f u n s u p e r v i s e dl e a r n i n g t h ep a p e r g i v e sc o n v e r g e n c ea n a l y s i so f k - m e a n sa l g o r i t h m ， w h i c h p r e s e n t sc r e d i b l et h e o r yg u a r a n t e e t ou s e a l g o d t h m t h es e n s eo f t h ep a p e rl i e si n ：m a k ep r o g r e s ss o m em a t h e m a t i c a lm o d e la n da l g o r i t h mi n d a t am i n i n g ，t h e nm a k et h em e t h o d sf i tt or e a ld a t a ；t r yt oa p p l yt h em e t h o d st on e wa r e a s ，s o t h a te n l a r g et h e i ra p p l i c a t i o nr a n g e ；p r e s e n tc o n v e r g e n c ea n a l y s i so fa l g o r i t h m ，w h i c hp r e s e n t s c r e d i b l et h e o r yg u a r a n t e ef o r a l g o r i t h m k e y w o r d s ：d a t a m i n i n g ；m a t h e m a t i c a lp r o g r a m m i n g ；s u p p o r t v e c t o rm a c h i n e o n - l i n el e a r n i n g ：i n c r e m e n t a ll e a r n i n g ：f e a t u r es e l e c t i o n ；c l u s t e ra n a l y s i s i v 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名：日期：星q q 墨二墨二墨q 大连理工大学硕士学位论文 引言 数据挖掘( d a t am i n i n g 简称d m ) 一词首次出现在1 9 8 9 年8 月举行的第l1 届国际联合人 工智能学术会议上。迄今为止，由美国人工智能协会主办的d m 国际研讨会已经召开了 7 次，规模由原来的专题讨论会发展到国际学术大会，研究重点也逐渐从发现方法转向 系统应用，并且注重多利t 学科之问的相互渗透。其它内容的专题会议也把数据挖掘列为 议题之一，成为当前计算机科学界的一大热点。经过十几年的研究和实践，数据挖掘技 术已经吸收了许多学科的最新研究成果而形成独具特色的研究分支。从1 2 前的现状看， 数据挖掘的研究仍然处于广泛研究和探索阶段。一批具有挑战性和前瞻性的问题被提 出，吸引越来越多的研究者。数据挖掘的概念从二十世纪八十年代被提出后，其经济价 值已经显现出来。数据挖掘之所以吸引专家学者的研究兴趣和引起商业厂家的广泛关 注，主要在于大型数据库系统的广泛使用和把数据转换成有用知识的迫切需要。 1 2 前，数学规划已经成功地应用于许多数据挖掘问题。例如，数学规划的思想在解 决特征提取、聚类、分类等问题已经显示了它们的影响力。从数值的角度说，数学规划 方法，尤其是线性和二次规划方法是可靠的、有效的，它们在过去的几十年中得到极大的 提高。通用的软件，例如c p l e x ( 1 9 9 2 ) ，它能执行下面提到的所有算法。但是这些适应性 很强的算法对于特定的问题却表现出很多缺陷，例如时间和空问复杂度高。对于特定问 题，需要使用具有针对性的算法，以提高运算的速度和准确率。 本文通过模型表示、模型评价和算法的具体实施，将数学规划，尤其是优化技术应 用于数据挖掘，提高了数据挖掘的效率、速度和可靠性，使得数据挖掘技术能够更好的 适合现实世界处理数据的需要，这是本文的主要目的之一。故本文的研究内容有极大的 社会效益和经济效益。作者希望从理论上提供特征分析、分类、聚类等重要的数据挖掘 模型和算法，并将其应用于实践，同时运用计算机编程的知识对其进行验证，为研究提 供可靠的依据。 数据挖掘中若干数学摸型与算法研究 1 数据挖掘技术简介 1 1 数据挖掘技术的发展 数据挖掘( d a t am i n i n g ) 是从大量的、不完全的、有噪声的、模糊的、随机的数据中 提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程【l j 。还有 很多和这术语相近似的术语，如从数据库r p 发现知识( k d d ) 、数据分析、数据融合 ( d a t af u s i o n ) 及决策支持等。人们把原始数据看作是形成知识的源泉，就像从矿石巾 采矿一样。原始数据可以是结构化的，如关系型数据库中的数据，也可以是半结构化 的，如文本、图形、图像数据，甚至是分布在网络上的异构型数据。发现知识的方法可 以是数学的，也可以是非数学的：可以是演绎的，也可以是归纳的。发现了的知识可以 被用于信息管理、查询优化、决策支持、过程控制等，还可以用于数据库自身的维护。 因此，数据挖掘是一门广义的交叉学科，它汇聚了不同领域的研究者，尤其是数据库、 人工智能、数理统计、数学规划、可视化、并行计算等方面的学者和工程技术人员。我 们主要关注数据挖掘的数学规划方法。 当前，许多领域大量不同的问题可以作为数学规划问题被公式化并有效地得到解 决，例如，运筹研究1 2 3 、神经网络问题吣】、博弈理论与经济学m 、工程机械学i s , 9 1 。1 8 世纪伟大的数学家e u l e r 说：“任何宇宙中发生的事件都包含某种极大或极小。”通过 数学规划解决数据挖掘问题成为近几年来新兴的研究领域【l ”。 本文主要以统计学习和神经网络理论为基础，以数学规划为手段，对数据挖掘中的 支持向量机方法和聚类分析方法进行研究。 1 2 统计学习理论简介 支持向量机学习方法研究是本文的主要工作之一，它建立在统计学习理论基础之 上，因此这里首先对统计学习理论作一介绍。统计学习理论就是研究小样本估计和预测 的理论【“，最具有指导性的结果是推广的界，与此相关的一个核心概念是v c 维。 1 2 1v c 维 学习系统的容量对其泛化能力有重要影响【l “射。低容量学习系统只需要较小的 训练集，高容量学习系统则需要较大的训练集。但其所获的解将优于前者。对给定 训练集来说，高容量学习系统的训练集误差和测试集误差之间的差别将大于低容量 学习系统。v a p n i k 指出，对学习系统米说，训练集误差与测试集误差之间的差别是 训练集规模的函数，该函数可以由学习系统的v c 维表征。换言之，v c 维表征了学 习系统的容量。 2 一 大连理工大学硕士学位论文 a n t h o n y 1 9 1 将v c 维定义为：设助一个从h 维向量集艇 o ，1 ) 的函数族，则确v c 维为础q 子集e 的最大元素数，其中蜀茴足：对于任意s 点，总存在函誊耽f ，使得当x s t 对f s ( x ) = 1 ，x 盛池e e 时f s ( x ) = 0 。 v c 维可作为函数族f 复杂度的度量，它是一个自然数，其值有可能为无穷大，它 表示无论以何种组合方式出现均可被函数族f 正确划分为两类的向量个数的最大值。对 于实函数族，可定义相应的指示函数族，该指示函数族的v c 维即为原实函数族的v c 维。 为便于讨论，我们针对典型的二元模式识别问题进行分析。设给定训练集为 0 l ， ) 幢，曲，( “蚰) ，其中蕾r “，y 0 ，1 ) 。显然，x i 是一个，t 维输入向量，y 为 二值期望输出。再假设训练样本与测试样本均满足样本空问的实际概率分布p ( x ， 力。 对基于统计的学习方法来说，学习系统可以由一族二值函数( 触，毗口a ) 表 征，其中参数羽以唯一确定函数a ) ，人为撕有可能的取值集合。因此，( 肛，叻，口 a 的v c 维也表征了该学习系统的复杂度，即学习系统的最大学习能力，我们称 其为该学习系统的v c 维。学习的目的就是通过选择一个参数口+ ，使得学习系统的 输出- ，阮口与期望输出y 之问的误差概率最小化，即出错率最小化。出错率也称为 期望风险( e x p e c t e dr i s k ) ，如式l 所示： 趟a ) = 仁i y 一，( x ，口_ d p ( x ，) ( 1 ) 。 其中尸似力为样本空间的实际概率分布。由于m ，力通常是未知的，因此无法直 接计算r ( 功。但是，对给定的训练集，其经验风险( e m p i r i c a lr i s k ) r 。d 却是确 定的，如式2 所示： ( a ) = 去- f ( x ，a ) i ( 2 ) 1 = 1 其中国，帅为训练样本，为训练集中样本数，即训练集规模。由数理统计中的大数 定理可知，随着训练集规模的扩大，r 。d 曲将逐渐收敛于r ( 谚。 1 2 2 推广的界 基于统计的学习方法大多建立在经验风险最小化原则( p r i n c i p l eo fe m p i r i c a lr i s k m i n i m i z a t i o n ) 基础上，其思想就是利用经验风险忍唧( 来代替期望风险r ( 回，用使 忌一a ) 最d , o c j a x , 啪来近似使刖碑最4 , 0 t ! g x , 嘞。这类方法有一个非常凝本的假设，即 如果乜“收敛于尉曲，那么心“印的最小值将收敛于甄回的最小值。v a p n i k 与 3 一 数据挖掘中若干数学模型与算法研究 c h e r v o n e n k i s ”1 证明，该假设成立的充要条件_ 足函数族( 肛，回，口人) 的v c 维为有限 值。 v a p n i k 还证明，期望风险胄( 国满足一个上界，即任取，黼足o 一 r 0 的样本称为支持向量。由 ( 1 ) ( 2 ) 的约束条件和k k t 互补条件可知支持向量就是满足茧= 1 一y l ( w 一r ) 且 毒0 的向量。以图1 中圆圈所代表的样本为例，就是与本类数据在平面w x = r 一1 异 侧的圆圈样本。特别要说明的是分类间隔上的向量也是支持向量，它们对应的 l a g r a n g e 乘子o a i c ( 其余的支持向量对应的l a g r a n g e 乘子口j = c ) 。当口，取定 对得到 ”2 己f - 1 n 却 此时r 可以通过任意支持向量求得，这时广义最优线性分类器( 也称为决策函数) 是 ，( x ) = s g n 扣，一r ) = s g n 莲：。a ，y x 一，j ( 4 ) 也就是图1 中的w z = r ，其余两个超平面w x = ，l 我们把它们叫做分隔超平 面。 除了上述的标准模型外，还有- - 1 3 1 , t p 标准的支持向量机模型应用也十分广澍孤3 7 1 。 卜= ：舞2 ，麓叫2n i s f y i ( j ，一，) + f ，l fe l ， 【 f i 0 fe l ，2 ，) 该模型利用f r 躯代替原来的置信范围f l w 虻，使用2 一范数平方的训练误差来代替 卜范数的训练误差。这样得到了一个对分类结果影响很小的强凸的目标函数d 8 】，任何算 法在该目标函数上通常具有比标准模型更快的收敛速度。 图1 支持向量机与支持向量图2 增量过程和支持向量集的变化 f i g 1s u p p o r tv e c t o rm a c h i n ea n d f i g 2p r o c e s s i n go fi n c r e m e n t a ll e a r n i n g s u p p o r tv e c t sa n dt h ec h a n g eo ft h es e to fs u p p o r tv e c t o r s 1 0 ， 大连理r 大学硕十学位论文 2 1 2 处理约束约化的一种光滑化方法 这里介绍一种处理支持向量机问题的光滑化方法，本章的数值实验就是采用这种方 法，该方法是基于非标准的支持向量机模型，为了便于讨论将非标准的支持向量机写作 如下形式： m i n y y + ( w l w 2 ) s t d ( aw e ，) + y 0( 6 ) _ y 0 其中y 是所有数据点的分类错误组成的列向量；a 是所有数据点组成的矩阵a 的 行向量就是数据点；d 是对角矩阵，d 。= 1 代表a 中对应行向量所在的类别。 当w ，y 是( 6 ) 的解时有 y = ( e d ( a w p r ) ) + ( 7 ) 这罩 ix ，x 0 ( x ) + = 1o ：x o( 9 ) 从而，( 6 ) 转化为下面目标函数光滑且无约束条件的优化问题 m i n n ( w , 沪池扣p d ( 名w 一哪，国峥圭( w 。w 十三i r 2 ) ( 1 。) 传统的优化方法能够容易地求解这个问题。 2 2 数据预处理的核函数方法 为了提高分类的准确度，可以引进核函数，其核心思想是将样本x 映射到某个高维 特征空间h ，也就是做变换庐：x 卜矿( x ) = 幼( x ) ，矽：( x ) ，矽。( x ) ) ，而在高维特征空间 h 中训练样本的像有较好的分离性。此时模型( 2 3 和( 4 ) 转化为 数据挖掘中若干数学模型与算法研究 m a x 圭圆一；圭圭只y ，庐) 妒)m a x 圆一；只y ，庐b ) 妒k ) i = l i = l j = l s z 0 s c i e 1 2n ( 1 1 ) e a , y , = o ，：s g n 舻一r ) ：s 酬圭必州毫) 一， ( 1 2 ) 从上面两式可以看到寻优函数和分类函数只涉及训练样本之间的内积，而不必知道 变换的具体形式。根据泛函理论，只要一种核函数世k ，y j 满足m e r c e r 条件：对任意 给定函数g ( o 当k 2 g 妞有限时，足k ，只j 就对应某一空间的内积。而相应的寻优函 数和分类函数也变为 m “壹口一寻杰壹口口，置& ，x ，) ( - 。) ，( x ) ：s g n 杰d ，y f i & ，x ，) 一r ( 1 4 ) 当前常用的核函数有三种，分别是多项式核函数x 仁力= & y + l f ，径向基函 数k ，舡一y i ) = e x p 一卜一y 1 2 ，仃2 ，多层感知机k g ，y ) = t a n l l ( x 7 y 一。) 。由于篇幅 关系，不再累述。 下面县专橹向量棚的结构示意图，可以帮助理解支持向。量机的学习过程 z 2z i 图2支持向量机结构示意图 1 2 大连理工大学硕士学位论文 2 3 支持向量机的训练算法 由于s v m 方法较好的理论基础和它在一些领域的应用中表现出来的优秀的推广性 能，近年来，许多关于s v m 方法的研究，包括算法本身的改进和算法的实际应用，都陆 续提了出来。尽管s v m 算法的性能在许多实际问题的应中得到了验证，但是算法在 计算上存在着一些问题，包括训练算法速度慢、算法复杂而难以实现以及检测阶段运算 量大等等。 传统利用标准二次型优化技术解决对偶问题的方法可能是训练算法慢的主要原因： 首先，s v m 方法需要计算和存储核函数矩阵，当样本点数目较大时，需要很大的内 存，例如，当样本点数目超过4 0 0 0 时，存储核函数矩阵需要多达1 2 8 兆内存；其次， s v m 在二次型寻优过程中要进行大量的矩阵运算，多数情况下。寻优算法是占f h 算法 时间的主要部分。 s v m 方法的训练运算速度是限制它的应用的主要方面，近年来人们针对方法本身 的特点提出了许多算法来解决对偶寻优问题。大多数算法的一个共同的思想就是循环迭 代：将原问题分解成为若干子问题，按照某种迭代策略，通过反复求解子问题，最终使 结果收敛到原睡题的最优解。根据子问题的划分和迭代策略的不同，又可以大致分为两 类。 第一类是“块算法”( c h u n k i n ga l g o r i t h m ) 。“块算法”基于的是这样一个事 实，即去掉l a g r a n g e 乘子等于零的训练样本不会影响原问题的解。对于给定的训练样 本集，如果其中的支持向量是已知的，寻优算法可以排除非支持向量，只需对支持向量 计算权值( 即l a g r a n g e 乘子) 即可。实际上支持向量是未知的，因此“块算法”的目 标就是通过某种迭代方式逐步排除非支持向量。具体的作法是，选择一部分样本构成工 作样本集进行训练，剔除其中的非支持向量，并用训练结果对剩余样本进行检验，将不 符合训练结果( 一般是指违反k k t 条件) 的样本( 或其中的一部分) 与本次结果的支 持向量合并成为一个新的工作样本集，然后重新训练。如此重复下去直到获得最优结 果。 当支持向量的数目远远小于训练样本数目时，“块算法”显然能够大大提高运算速 度。然而，如果支持向量的数目本身就比较多，随着算法迭代次数的增多，工作样本集 也会越来越大，算法依旧会变得十分复杂。因此第二类方法把问题分解成为同定样本数 的子问题：工作样本集的大小固定在算法速度可以容忍的限度内，迭代过程中只是将剩 余样本中部分“情况最糟的样本”与工作样本集中的样本进行等量交换，即使支持向量 1 3 数据挖掘中若干数学模型与算法研究 的个数超过工作样本集的大小，也不改变工作样本集的规模，而只对支持向量- i - - 的一部 分进行优化。 同定工作样本集的方法和块算法的主要区别在于：块算法的日标函数中仅包含当前 工作样本集中的样本，而固定工作样本集方法的优化变量虽然仅包含工作样本，其目标 函数却包含整个训练样本集，即工作样本集之外的样本f l j l a g r a n g e 乘子阎定为前一次 迭代的结果，而不是像块算法中那样设为0 。而且固定工作样本集方法还涉及到一个确 定换出样本的问题( 因为换出的样本可能是支持向量) 。这样，这一类算法的关键就在 十找到一种合适的迭代策略使得算法最终能收敛并且较快地收敛到最优结果。 最i f y j o h nc p l a t t 在提出s m o ( s e q u e n t i a lm i n i m a lo p t i m i z a t i o n 或s m o ) 算法。将 工作样本集的规模减到最小两个样本。之所以需要两个样本是因为等式线性约束的 存在使得同时至少有两个l a g r a n g e 乘子发生变化。由于只有两个变量，而且应用等式 约束可以将其中一个用另一个表示出来，所以迭代过程中每一步的子问题的最优解可以 直接j 1 j 解析的方法求出米。这样，算法避开了复杂的数值求解优化问题的过程；此外， p l a i t 还设计了一个两层嵌套循环分别选择进入工作样本集的样本，这种启发式策略太 大加快了算法的收敛速度。标准样本集的实验结果证明，s m o 表现出在速度方面的良好 性能。 子问题的规模和迭代的次数是一对矛盾，s m o 将工作样本集的规模减少到2 ，一个 直接的后果就是迭代次数的增加。所以s m o 实际上是将求解子问题的耗费转嫁到迭代 上，然后在迭代上寻求快速算法。但是，s m o 迭代策略的思想是可以用到其他迭代算 法中，可见s m o 还有改进的余地。 s m o 在实际应用中取得了较好的效果，但它也存在着一些问题。s m o 算法每次 迭代都要更新闽值，但是该值有可能是无法确定的( 例如不存在0 a i c 的样本，尽 管这种情况很少出现) ，这时s m o 采用的方法是确定出b 的上下界然后取平均值；另 外，每一次迭代过程。| i 的阈值仅取决于上次迭代结果的两个变量的最优值，用这个6 值 判断样本是否满足迭代结果，这就可能存在某些达到最优值的样本却不满足k _ k t 条件 的情况，从而影响了该算法的效率。 解决算法速度问题的另一个途径是采用序列优化的思想。这种方法主要目的是研究 当出现新的单个样本时，它与原有样本集或其子集，或是原有样本集训练结果的关系， 铡如，它的加入对原有样本集的支持向量集有什么样的影响，怎样迅速地确定它对新的 分类器函数的贡献等等。 2 4 支持向量机的增量学习 1 4 大连理工大学硕士学位论文 增量学习技术( i n c r e m e n t a ll e a r n i n gt e c h n i q u e ) 是一种得到广泛应用的智能化数据 挖掘与知识发现技术。其思想是：当样本逐步积累时，学习精度也要随之提高。与传统 的学习技术相比，增量学习技术不但可以舍去无用样本，减少存储数据所占用的空间， 而且可以充分利用历史学习的结果，显著节省后继训练时间。一种机器学习方法是否具 有良好的增量学习功能已经成为评价其性能优劣的重要标准之一。经典的支持向量机理 论与增量式学习并不具备直接的相容性。但是支持向量机训练所得的支持向量能够完全 反映分类超平面的信息，而支持向量通常只占训练样本很小的一部分，这对支持向量机 增量学习算法的构建具有重要的意义【3 9 】。 2 4 1 支持向量性质分析 为了论述方便，本节只对两阶段情况进行讨论，多阶段的情况只是将其进行简单推 广。设h 为历史样本集，也称作旧样本集，i 是增量样本集，也称作新样本集。为了得 到h u i 的分类超平面，最直接的方法就是对它们中的所有样本进行学习，这种方法是 支持向量机的经典学习方法。如前面所述，该方法会增加运算时间和存储空间。 经典的学习方法忽视了支持向量机的一个重要性质：支持向量机训练所得的决策函 数仅与支持向量有关，既支持向量机在全体样本上训练和在支持向量集上训练得到的决 策函数相同。历史训练的结果在经典的支持向量机学习方法完全不起作用，这使得训练 速度很低。本文在充分分析支持向量特征和增量过程的基础上提出了一种新的支持向量 机增量学习算法。 支持向量虽然在样本集r 1 1 占很小的一部分，但却完全反映了最优分类器的特征。增 量学习的主要任务就是利用历史训练结果，尽量避免样本的重复训练，得到比较准确的 分类结果，并且训练规模不能太大，这面临下面几个问题： 1 ) 什么样的新增样本可能影响学习能力和泛化能力? 2 ) 新增样本如何改变原来的分类器? 新增样本在增量学习中的地位是否相同? 3 ) 支持向量可以代表样本集本身么? 4 ) 增量后原样本集的中的支持向量如何变化? 5 ) 什么样的向量可能成为最终训练结果的支持向量? 在原样本集h 中支持向量集s v 完全代表了历史样本的学习能力和泛化能力，它们 在增量学习后成为支持向量的概率是相当大的，在增量样本集i 中错分向量a s v 对分 量结果的影响最大，这些样本很可能成为支持向量。还有与最优分类器临近的，即使被 正确分类的样本也有可能成为支持向量，这些向量处于问隔平面和最优超平面之问，记 为e s v ，它们主要影响支持向量机的泛化能力。当然，其它的样本也可能成为支持向 一1 5 一 数据挖掘中若干数学模弛与算法研究 量，但概率要比上述向量小得多。因此在新增样本- 】优先考虑这两种样本。这里除去 a s v 和e s v 的样本记为n s v 。 现在考虑增量过程，每次增量可以看成三个阶段，首先加入n s v 样本，它们对最 优分类超平面和分类间隔超平面的位置完全没有影响。再加入e s v 样本，这些样本是 被正确分类的样本，但是它们的加入使得最优分类超平面两侧的区域更加“拥挤”，从 而使得支持向量机的泛化能力减弱，降低了预测的准确率。最后加入a s v 样本，它们 的加入将使得最优线性分类器有很大改变。以上分析表明这两种样本成为增量学习的支 持向量的概率是非常大的，因此可以使用s v u a s v u e s v 代替h u i 进行训练。 在样本的统计性质比较好时，即历史样本与增量样本具有相似的分布，使用 s vu a s vue s v 进行训练得到最优分类超平面与原来的分类超平面近似，只是间隔超 平面的距离有所减小，s v u a s v u e s v 之外的向量成为支持向量概率很小。但是，好 的统计性质在实际的数据库中有时是不能保证的，尤其是样本较少时。此时，历史样本 和增量样本分布并不相似，甚至分布差异( c o n c e p td r i f t 或c o n c e p tc l m n g e ) 十分显著。 这时如图2 所示最优线性分类器起了很大的变化。在历史样本集中的一部分非支持向量 变成支持向量，同时一部分支持向量退化为普通向量；在增量样本集中，一部分n s v 样本变成了支持向量，从而影响支持向量机的学习和泛化。在这种情况下，剩余的未被 学习的样本有必要被重新考虑，可以将s v u a s v u e s v 作为历史样本集，剩下的作为 增量样本集重新进行训练。当然，这个过程可以继续下去，但那样增加运算的复杂度， 并且一般地，二次训练加上下面的权值调整规则，已经能够得到很好的结果。 在上面提到的学习中，使用支持向量代表历史样本集进行训练是不合理的，因为支 持向量毕竟只代表分类超平面，不能代表样本集本身，用数目较少的支持向量来代替样 本集会使得样本集对分类的影响降低。因此，根据 4 0 中的思想需要给历史样本集的支 持向量所犯的错误加权，同时，在约束条件中最优分类超平面的法向量和阈值也要加 权，也就是把它们扩大一个倍数。这表明样本越多，由于犯错误而受到的惩罚就越重， 分类超平面之间的距离越小( 法向量和阈值同时扩大不会影响超平面的位置) 。权值取 万， 其中，五= 0 样本总数训练所使用的样本0 使用五作为权值是因为( 5 ) 式的目标函数使用的置信范围和训练误差是平方的形 式。增量样本集也要按照这个方法进行加权。在初始状态，增量信息是完全未知的，使 用加权方法得到更好的训练和测试结果，但泛化能力会受到影响。经过第一步学习得到 1 6 大连理工大学硕士学位论文 的分类器已经能近似反映最优分类器的特征，第二步学习只是对上一步得到的分类器进 行调整，此时不再使用加权过程，避免泛化能力减弱。 2 4 2 增量学习算法 在上面分析的基础上，我们给出本文的支持向量机增量学习算法。 算法： 在历史样本集h 上训练，得到初始的分类器厶。 从增量样本集i 中分离出a s v 和e s v ，若错分样本集a s v = o 则停止训练，输 出分类器工；否则，在s v u a s v u e s v 上进行加权训练，得到其上的分类器z 。 再将- ，；赋值给 ，s v u a s v u e s v 作为历史样本集h ，其余作为增量样本集 l ，重复和( 无加权过程) ，得到分离器 ，它就是最终的增量学习结果。 2 4 3 数值实验 基于上面的研究，本文在8 1 2 4 2 2 的m u s h d a t a l 4 i 】数据集上进行模拟实验，随机选 取其中2 7 2 4 个做测试集，2 7 0 0 个作为初始训练集，其余的平均分成五组，依次作为增 量训练样本集进行增量模拟实验。从图3 可以看出，本文的增量学习算法在不明显降低 测试精度的前提下显著减少了训练时间。( 本文使用y j l e e 和o l m a n g a s a r i a n 的 s s v m 算法【4 2 】进行训练，该算法运算速度较快，并使用 4 3 的r e d u c e ds v m 方法将核空 间的维数降低到2 0 0 0 维，采用r b f 核函数，选取正则化参数c = 1 0 ，核参数 y ：0 0 5 ) 。 一1 7 一 数据挖掘中若干数学模型与算法研究 ( b ) ( 横轴表示增量样本，纵轴分别表示测试精度( ) 和训练时间( s ) ，一代表经典学 习，一代表增量学习) ( e t ) 测试精度的比较( b ) 训练时问的比较 图3 两种学习方法关于测试精度和训练时间的比较 f i g 3c o m p a r i s o no f t w ol e a r n i n g m e t h o d so n t e s t i n ga c c u r a c ya n dt r a i n i n gt i m e