（计算机应用技术专业论文）基于最大margin的决策树归纳研究.pdf

摘要 摘要 决策树归纳学习算法是机器学习中最重要的算法之一。目前通常采用启发式方 法来构建决策树，因此探索各种启发式算法成了决策树研究的一个焦点。基于最大 m a r g i n 的决策树归纳是一种新的分类方法，它以支持向量机反问题作为启发式来构 建决策树。该方法有着很好的泛化能力，但是时汹复杂度却很高。本文在降低基于 最大m a r g i n 的决策树归纳算法的时间复杂度方面做了相关的研究。 为了提高基于最大m a r g i n 的决策树归纳学习算法的性能，本文在其基础上提出 了两种新的算法。一个是基于最大m a r g i n 的决策树的并行算法。此并行算法采用消 息传递接口( m p i ) 实现，主要并行点是支持向量机反问题的求解。另一个是多项 式级时间复杂度的支持向量机反问题求解算法。该方法首先对数据进行聚类，然后 利用类间间隔矩阵寻找最优划分。实验结果表明，这两种算法都缩短了支持向量机 反问题的求解时间，提高了基于最大m a r g i n 的决策树的构建速度。 关键词支持向量机；最大m a r g i m 决策树；并行化；类i 日j 间隔矩阵 a b s t r a c t a b s t r a c t i n d u c t i o no fd e c i s i o nt r e ei so n eo ft h em o s ti m p o r t a n tm a c h i n el e a r n i n ga l g o r i t h m s e x p l o r i n gh e u r i s t i ca l g o r i t h m sb e c o m e saf o c u sb e c a u s eh e u r i s t i ca l g o r i t h m sa r eu s u a l l y e m p l o y e dt oc o n s t r u c td e c i s i o nt r e e t h ei n d u c t i o no fd e c i s i o nt r e eb a s e do n t h el a r g e s t m a r g i n ，a l s o n a m e dl a r g e m a r g i n d e c i s i o nt r e ei n d u c t i o n ( l m d t i ) ，i san e w c l a s s i f i c a t i o nt e c h n i q u ei nw h i c ht h el a r g em a r g i nb e t w e e nt w oc l a s s e si su s e d a s h e u r i s t i ci n f o r m a t i o nf o rt h ed e c i s i o nt r e eg e n e r a t i o n i th a sg o o dg e n e r a l i z a t i o n ，b u t v e r yl a r g et i m ec o m p l e x i t y m o t i v a t e db yr e d u c i n gt h et i m ec o m p l e x i t yo fl m d t i ，s o m e r e s e a r c h e sh a v eb e e nd o n ei nt h i sp a p e r i no r d e rt oi m p r o v et h ee f f i c i e n c yo fl m d t i ，w ep r o p o s et w on e wm e t h o d sb a s e d o nl m d t i t h ef i r s to n ei st h ep a r a l l e la l g o r i t h mo fl m d t i ，w h i c hp a r a l l e l ys o l v e st h e i n v e r s ep r o b l e mo fs v mw i t hm e s s a g ep a s s i n gi n t e r f a c e ( m p i ) t h eo t h e ri san e w a l g o r i t h mf o rs o l v i n gt h ei n v e r s ep r o b l e mo fs v m i th a sp o l y n o m i a lt i m ec o m p l e x i t y ， a n dg e t st h eo p t i m a lp a r t i t i o nu s i n gm a r g i nm a t r i xa f t e rc l u s t e r i n g e x p e r i m e n t a lr e s u l t s s h o wt h a t ，b o t hm e t h o d sp r e s e n t e de n o r m o u s l yi m p r o v et h ea l g o r i t h mi nt i m ec o m p l e x i t y ， a n da tt h es a m et i m e ，t h es p e e do fc o n s t r u c t i n gt h el a r g em a r g i nd e c i s i o nt r e eb e c o m e s m u c hf a s t e r k e y w o r d ss u p p o r tv e c t o rm a c h i n e ；t h el a r g e s tm a r g i n ；d e c i s i o nt r e e ；p a r a l l e l i z a t i o n ； m a r g i nm a t r i x 河北大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谫 的地方外，论文中不包含 其他人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教育机构的学 位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示了致谢。 作者签名：兰盏整日期：丝塑年上月主!只 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。学校 可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 本学位论文属于 l 、保密口，在年月同解密后适用本授权声明。 2 、不保密t y 。 ( 请在以上相应方格内打“”) 作者签名：兰! 丕整日期： 幽年上月芏一r 导师签名： 保护知识产权声明 本人为申请河北大学学位所提交的题目为( 基于最大m a r g i n 的决策树归纳研 究) 的学位论文，是我个人在导师( 王熙照教授和翟俊海副教授) 指导并与导师合 作下取得的研究成果，研究工作及取得的研究成果是在河北大学所提供的研究经费 及导师的研究经费资助下完成的。本人完全了解并严格遵守中华人民共和固为保护 知识产权所制定的各项法律、行政法规以及河北大学的相关规定。 本人声明如下：本论文的成果归河北大学所有，未经征得指导教师和河北大学 的书面同意和授权，本人保证不以任何形式公开和传播科研成果和科研工作内容。 如果违反本声明，本人愿意承担相应法律责任。 声明人：一兰i 鍪鳖 作者签名： 导师签名： 日期：幽年上月上r 目期：幽年上月卫f t 第1 章绪论 1 1 研究背景与意义 第1 章绪论 决策树归纳是归纳学习中最实用且最重要的学习和推理方法之一，算法的早期版本 可以追溯到二十世纪六十年代。决策树归纳学习算法不需要相关领域知识，归纳学习与 分类识别的操作处理速度都相当快。同时决策树还是分析消耗、进行促销、破产分析、 评估信用风险、发现交叉销售机会和欺诈行为的有力工具。采用决策树归纳算法，不仅 样本集的训练时间短，精度高，而且还可以将数掘规则可视化。因此决策树在知识发现 系统中应用较为广泛。 由于构造最优的决策树已经被证明是n p 难问题i 】，所以典型的决策树学习算法都是 在完全假设空间中的自项向下的贪心搜索，各种搜索算法的区别在于所采用的启发式策 略不同。比较流行的启发式算法有q u i n l a n 提出f i 0 i d 3 算法f 2 】，它倾向于选择能使当前信 息熵下降最快的属性：b r e i m a n 等人提出的c a r t 算法f 3 】它倾向于选择能使不纯度( 由 g i n i 索引函数定义) 下降最快的属性；d em a n t a r a s 提出了一种基于距离的度量方法1 4 】， 它选择的属性所对应的划分是与样例集合最完美划分距离最近的。其中，选用最小信息 熵作为启发式信息的i d 3 算法是决策树中最典型的代表，这种方法生成的决策树规模小 且计算复杂度低。 统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ) 主要研究小样本情况下机器学习的规律 1 5 1 ，它建立在一套坚实的理论基础之上，为解决有限样本学习问题提供了一个统一的框 架。vv a p n i k 等人从六、七十年代开始致力于这方面研究1 6 1 ，到九十年代中期，随着统 计学习理论的不断发展和成熟，在这一理论基础上发展了一种新的学习方法支持向 量机f 7 ) ( s u p p o r t v e c t o rm a c h i n e ) 。该方法已初步表现出许多优子已有方法的性能，尤其是 较强的泛化能力。支持向量机在各方面的出色表现，已使其成为一种强有力的学习方法， 尤其在随类分类问题方面，s v m 被普遍认为是最佳的解决工具。该方法已经广泛应用于 分类、回归及信号处理等领域。 河北人学，j ：学硕士学位论文 根据统计学习理论，s v m 分类洲隔越大，泛化能力越强。考虑到这一关系，基于最 大m a r g i n 的决策树归纳学习采用最大间隔作为启发式信息来构造决策树【8 】。该方法通过 求解s v m 反问题来得到一个具有最大间隔的划分，以此来分裂节点，构造决策树。其意 义在于：( 1 ) 从原始数据中生成高质量的决策树，最大限度地提高决策树对新观察样例的 预测准确性；( 2 ) 它将两种重要的归纳方法互补地结合在一起。 基于最大m a r g i n l 拘决策树归纳学习需要求解支持向量机反问题，因此时间效率成了 该方法的最大问题。本文以统计学习理论和支持向量机为基础，针对基于最大m a r g i n 的 决策树归纳学习算法时间复杂度较高的问题，主要从提高反问题的求解速度方面进行研 究，提出了基于最大m a r g i n 决策树的并行算法和一种新的s v m 反问题求解算法。实验结 果表明新提出的这两种方法都明显缩短了s v m 反问题的求解时间，加快了决策树的构建 速度。因此基于最大m a r g i n l 拘决策树归纳学习可以得到更广泛的应用。 1 2 国内外研究现状 基于最大m a r g i n 的决策树学习以支持向量机反问题作为启发式来构建决策树。该 方法涉及决策树、支持向量机和支持向量机反闯题三个方面的内容。下面分别进行叙述。 1 2 1 决策树 决策树归纳学习算法由于实现简单，算法效率高，归纳能力好而逐渐成为了应用最 广泛的归纳推理算法之一。该算法在最初是一种逼近目标函数的方法，它通过一定的策 略，根据训练数据在目标函数集中逼近目标函数1 2 】。在该算法的发展过程中，为了处理 属性是实值连续型数据的样本，模糊集理论被引入到数据归纳和分类中来，出现了模糊 决策树，如基于f u z z y l d 3 启发式算法和基于m i n a m b i g u i t y 启发式算法的模糊决策树1 9 】， 使决策树理论得到了推广。在这种方法中，学习到的函数被表示为棵树结构，然后再 被表示成多个i f t h e n 规则以提高可读性，最后根据学习到的规则对未知样例进行预 测。 决策树一般采用自顶向下( t o p d o w n ) 的方法构建：在树的构建过程中，所采 用的启发式或者说扩展属性的选取标准是建树的关键。根据启发式选取的不同，目前决 第1 章绪论 策树算法可分为2 大类l j o j ：基于信息论的方法和基于最小g i n i 指标的方法。前者对应的 算法有：i d 3 、c 4 5 ，后者对应于的算法有：c a r t 、s p r i n t 和s l i p 。目前关于决策树 启发式的研究仍是决策树研究领域的热点【1 1 , 1 2 j 。 1 2 2 支持向量机 统计学习理论是支持向量机的理论基础，它建立在一套坚实的理论基础之上，为解 决有限样本学习问题提供了一个统一的框架。它将很多现有方法纳入其中并化为已用。 早在2 0 世纪6 0 年代，作为s v m 奠基人的v a p n i k 就开始了统计学习理论的研究1 6 j 。1 9 7 1 年，v a p n i k 和c h e r v o n e n k i s 共同提出了s v m 中的一个重要理论一- - v c 维理论。1 9 8 2 年，v a p n i k 进一步提出了结构风险最小化原理【l 引。1 9 9 2 年，b o s e r 、g u y o n 和v v a p n i k 提出了最优边界分类器【i4 1 ，此分类器被认为是支持向量机的最初原型。1 9 9 5 年，v a p n i k 正式提出统计学习理论，并较好地解决了线性不可分问题，奠定了s v m 的理论基础1 7 j 。 求解s v m 问题的实质是针对支持向量机的凸二次规划问题进行求解。一般来说，经 典的牛顿方法、共轭梯度、原对偶内点方法等均可以用于求解s v m 。但是，它们的求解 效率很低并且不适用于样本规模很大的情况。因此针对s v m 问题本身的特点，许多新的 求解算法被提出。1 9 9 2 年，b o s e r 等人提出块算法【1 4 1 ，后来又被称为不完全的分解算法。 它的基本思想是：删除矩阵中对应- 于l a g r a n g e 乘数为零的行和列不会对最终结果产生影 响。1 9 9 7 年，b o s e r 等人又提出分解的算法，又称为固定工作集的方法或“o s u n a ”算法 j s a6 1 。它把整个问题分解成固定样本数的子问题，即使支持向量的个数超过工作样本集 的大小，也不改变工作样本集的规模。j o a c h i m s 等人采用启发式的工作集构造策略，显 著加快了分解算法的收敛。他的改进算法得到广泛应用，称为s v m l i g h t 算法i l7 1 。p l a t t 等人于1 9 9 8 年提出s v m 的快速求解算法1 1 8 j 一一序贯最小最优化( s m o ，s e q u e n t i a l m i n i m a lo p t i m i z a t i o n ) 。他将工作集的规模减小为两个样本，使得每一步迭代的予问题的 最优解可以解析地给出。k e e r t h i 等人对s m o 算法的收敛性进行了严格证明，同时对s m o 算法提出了重大改进，通过不断寻找最大违反对替代了s m o 的内外循环，显著加快了算 法的收敛速率i q 】。l i n 在改进的s m o 算法基础上丌发出实用的l i b s v m i 具包删。2 0 0 4 年，b o 】e y 等人提出用聚类的方法训练s v m 【2 l 】。该方法酋先采用一种基于划分的聚类方 法【2 2 ，然后把划分成的每一个簇作为一个点来训练s v m 。 河北人学1 ：学硕十学位论文 s v m 原本只解决两类分类问题，由于实际应用的需要，很多学者又= 玎始t s v m 解 决多类问题的研究。主要的解决方法包括v a p n i k 提出的_ 对多的方法【7 1 ，k r e s s e l 等人提 出的一对一的方法【2 3 】，p l a t t 提出的决策导向循环图( d a g s ) 方法f 2 4 1 。h s u 等人对这些算法 进行了实验对比 2 5 】。此外还有2 0 0 7 年，t i b s h i r a l l i 提出的l a 略em a r g i nt r e e s 算法1 2 6 1 。该算 法将s v m 作为决策树节点的划分标准，用二叉决策树解决多类分类问题。 1 2 3 支持向量机反问题 王熙照教授于2 0 0 5 年提出了支持向量机反问题【2 7 1 ，它是一种无导师学习方法。就是 如何将一个样例集合分为两部分，才能使这两部分之间的间隔最大。间隔就是支持向量 到分割超平面的距离。 王熙照教授于2 0 0 5 年在支持向量机反问题提出的同时，还提出用遗传算法来对反问 题进行求解，并给出了具体算法1 27 1 。文中给出了部分仿真实验和i r i s 数据库中第二类和 第三类数据的实验，结果显示该算法可以得到近似最优划分，但是时间复杂度比较高。 王熙照教授等人2 0 0 6 年又考虑从聚类的角度来求解s v m 反问题( 2 引，提出s v m 反问 题的k m e a n s 聚类求解算法。该方法首先将样本进行聚类，然后把聚成的类作为一个整 体，划分时不再拆丌，这使得划分次数大大减少。然后使用穷举所有可能划分的方法来 求解。当聚成的类别数较少时，算法效率较高。 王熙照教授等人2 0 0 6 年将反问题作为决策树的启发式来生成决策树，提出基于最大 m a r g i n 启发式的决策树归纳【8 】。文中指出用反问题作为启发式能提升决策树的泛化能力。 1 3 本文主要研究内容 本文在深入分析了基于最大m a r g i n l 拘决策树归纳学习的基础上，发现反问题求解是 基于最大m a r g i n 启发式决策树构建的瓶颈。因此在反问题求解算法的并行化和寻求新的 反问题求解方法两方面做了进一步的研究。 首先提出了基于最大m a r g i n 启发式决策树的并行算法。采用并行算法求解反问题， 从而使反问题的求解时间大大减少，加快了基于最大m a r g i n 启发式决策树的构建。此并 行程序是基于m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 丌发的。m p i 并不是一个新的编程语言， 它只是个可用于c ，c + + 和f o r t r a n 的函数库。m p i 使得一个串行算法可以很容易的 4 第l 章绪论 改成并行算法，从丽可以在多处理器上运行以提高性能。该算法还采用了s p m d ( s i n g l e p r o g r a mm u l t i p l ed a t a ) 模式，就是不同处理器运行相同的程序，但是处理不同的数据。 此方法在实际数据库上进行了实验测试，结果显示，该并行算法大大缩短了决策树的构 建时间。 然后又提出了种多项式时间复杂度的反问题求解方法。此方法是借鉴m a r g i nt r e e 中2 6 1 的数据划分策略，使得反问题的求解可以在多项式时间复杂度内完成。该方法从多 类问题的类间最大间隔出发，利用类间间隔矩阵，然后通过单连接或全连接方法求得一 个近似的最优解。我们分析了新算法的时间复杂度，并对单连接、全连接和基于聚类的 反问题求解算法之间的时间消耗进行了实验对比，实验结果表明新的求解方法比原来只 采用聚类的方法要有效的多。 1 4 本文组织 具体章节结构安排如下： 第1 章绪论。主要叙述了课题的背景、意义以及与本文相关的国内外研究状况。 第2 章支持向量机及其反问题。介绍了支持向量机的理论基础、基本问题及其典 型求解算法s m o ；对支持向量机反问题及两种求解算法，即遗传算法和基于聚类的s v m 反问题求解算法进行了描述。 第3 章基于最大m a r g i n 的决策树归纳及其并行算法。对基于最大m a r g i n 的决策 树归纳进行了详细介绍，然后给出了其并行算法。 第4 章新的支持向量机反问题求解算法。提出了一种新的反问题求解算法，并对 该算法的时问复杂度进行了分析，给出了算法实现过程，并与聚类求解支持向量机算法 进行了对比。 第5 章总结与展望。 河北人学i ：学硕+ 学位论文 2 1 支持向量机 第2 章支持向量机及其反问题 支持向量机( s v m s u p p o r t v e c t o rm a c h i n e ) 是在统计学习理论基础上发展起来的一 种新的机器学习方法。设输入模式集 一) cr ”由两类点组成，如果t 属于第一类，则标 记为1 ，属于第二类，则标记为一l 。从中取大小为，的样本作为训练集( 一，z ) ，：l ，2 ，。 学习的目标是构造一个判别函数，将两类模式尽可能正确地区分开来。下面分线性可分、 近似线性可分和线性不可分三种情况进行讨论。 2 1 1 线性可分情形 定义2 一l ：如果存在分割超平面( 0 2 幸x ) + 6 = 0 ，使得 ( 0 2 书) + 6 l ， - - i ( 2 1 ) ( 奉五) + 6 一l ，y j = 一l 成立，则称训练集是线性可分的。可把不等式( 2 - 1 ) 合并写成： 只【( 幸) + 6 】之i ，= l ，2 ，( 2 2 对一个固定的超平面，参数，b ) 不是唯一确定的，商是相差一个常数因子。因此 总能够找到一对，6 ) ，使( 2 2 ) 式中至少有一个以等式成立，为此只需令 ( t ，只) ) 到 该超平面的最小距离等于1 j | 8 。这样的表示方式称为这个超平面关于 ( ，只) ) 的标准表 示。本文中我们约定，以后出现的超平面均采用标准表示。 定义2 - 2 ；若训练集到该超平面的最小距离最大，则称分离超平面是最优的。 根据定义2 2 及上面对定义2 1 的阐述，书工) + 6 = 0 是最优的当且仅当( ，b ) 是 下面优化问题的解： min批2(2-3) s ，只 ( & ) 幸一) + 6 】2 l ，f = 1 ，2 ， 第2 章支持向量机及其反闯题 这是一个二次规划i 、u j 题，且有唯一的极小点，用l a g r a n g e 乘子法把( 2 - 3 ) 式化成其 对偶形式： 一善a ，一圭善a , a y , y j ( x , ，)浯4 ) j f y , a ，= o ，a ，o ，i = 1 ，2 ， ， ( 2 - 3 ) 式中的- z y l a ，。 ，t l 若a ， o ，称相应的为支持向量。于是最优超平面方程为a ， ( 薯木x ) + 6 = o ，判 e s v 别函数为 ， y = s g n - a ，只( 木x ) + 6 】 i = l ( 2 - 5 ) 解决线性可分问题，并由( 2 4 ) 式的最优化问题构造的分类器( 2 - 5 ) 式称为线性 硬问隔支持向量分类机。 一般来说，在实际问题中支持向量仅占训练样本的- - 4 部分( 如图2 1 中虚线上的 + 号和0 号) ，这样( 2 5 ) 式中被加项就减小了许多。下图中厂伍) 就是最优超 平面，m a r g i n 就是最大间隔。 图2 一l 两类分类问题最优超平面示意图 2 1 2 近似线性可分情形 若训练集是线性不可分的，但是又接近线性可分，这样的情况一般称为近似线性可 分。为了解决这种情况，引入非负向量善，又称为松弛变量，来软化对分类问隔的要求。 河北人学1 ：学硕士学位论文 与式( 2 - 3 ) 相对应的优化问题变为： m i n 劲| 1 2 + c i 专 j f 只【( 木葺) + 刎1 一善 ：2 - 6 ) 考。0 ，i = 1 ，2 ， 这里的约束是软化后的约束，专可以看作训练样本关于分离超平面的偏差，喜为0 向量时问题变为线性可分的情形。c 是一个大于0 的常数，称为惩罚系数，用来控制样 本偏差与机器泛化能力之间的平衡。 用l a g r a n g e 乘子法把式( 2 - 6 ) 化成其对偶形式： m a x a ，一去a ，口，只乃( 誓宰一) 4 1 。t 。 ( 2 7 ) 只， 只a ，= o ，o o ，称相应的誓为支持向量。判别函数为 ， y = s g n 【a ，只( 一幸x ) + 6 】 ，= l ( 2 - 8 ) 解决近似线性可分问题( 即引入松驰变量考可以使问题变为线性可分) ，并由( 2 6 ) 式的最优化问题构造的分类器( 2 8 ) 式称为线性软间隔支持向量分类机。 2 1 3 线性不可分情形 超平面的分类能力毕霓有限，为此引入非线性映射及最优超平面，即特征空i 司中的 超平面。主要思想是：作非线性映射( x ) ：尺”专f ，f 是高维内积空间，称为特征空间， 砂( x ) 称为特征映射；然后在f 中构造最优超平面。则判别函数形式为： 厂( 工) = s g n ( ：，a t y ，( 咖( 一) 幸( x ) ) + 6 ) ，其中的参数a 可以通过解决二次优化： m i n 主弘叫州( 砷悱一 ( 2 - 9 ) “，y = o ，o o 的样本点为支持向量。不难看出，为了求特征空间q 。的超平面， 不必知道毋( x ) 的确切表达式，只要知道输入x ，z 计算内积( 妒( x ) 木( 三) ) 就够了，即： ( ( x ) 幸庐( z ) ) = k ( x ，z ) ，这个事实对于构造支持向量机有重要意义。当特征空间的维数很 大( 实际情况常常如此) 甚至是无穷维时，直接计算内积其复杂度非常高，实际不可行。 而上述事实指出：高维空间中内积运算，可以转化为低维输入空间上一个简单的函数运 算。 我们称函数k ( x ，z ) 为核函数，相应的判别函数为： y = s g n z a ，y , k ( x ，x ) + 6 】 ( 2 一l o ) 解决在特征空问中线性可分问题( 即引入非线性映射使问题在特征空间变为线性可 分) ，并由( 2 - 9 ) 式的最优化问题构造的分类器( 2 - 1 0 ) 式称为非线性硬间隔支持向量 分类机。 支持向量机由训练集和核函数完全刻画，这样在实际问题中，常常是直接给出核函 数，而不是直接给出映射妒( x ) 。所以如何构造、选择核函数是个重要问题。常用的核函 数k ( t ，j ) 有三种： 多项式核函数：k ( 一，x ) = 【( 车工) + 1 r ，d 为自然数。 径向基函数核函数：尺( 如石) ：e x p 一生二# ，o - 00 仃。 神经网络核函数：k ( x ，) = s i g m o i d ( u ( x t ) 一6 ) ，z , 艿为常数。 由于采用某一种映射方法，映射到特征空间后，也不定就恰好线性可分。于是一 方面，像非线性硬间隔分类机那样，引进从输入空间到特征空间的非线性映射；另一方 面，像线性软间隔分类机那样，通过引进松弛变量考而放松约束，这样便可以得到一般 更常用的非线性软间隔支持向量分类机。这时原始问题为： m i n i 1 ( w w ) + c ；：。专 舅t 只【( w ) + 6 】2 1 一专 ，= l ， ( 2 1 1 ) 毒，0 ，= 1 ， 其中c 0 。 设核函数为k ( x ，x ) ，则原问题( 2 。1 1 ) 的对偶问题为： 河北人学l = 学硕士学位论文 朋a x 怖) = 一圭：, j = l a p t j y , y j 地，_ ) y j = o ， c a 0 ， i = 1 ， ( 2 1 2 ) 相应的判别函数为： y = s g n a ，只k ( 薯，x ) + 6 】 ( 2 1 3 ) 工e j v 由( 2 1 2 ) 式的最优化问题构造的分类器( 2 1 3 ) 式称为非线性软i 司隔支持向量分 类机。这也是实际中使用最多的支持向量机。图2 - 2 给出了一个示例。 决策函数可以表示为：厂( x ) = s g n ( ：。a 七( 一，x ) + 6 ) ，并且可以得到下面的决策 规则： 将待测样本x 输入决策函数y = s g n ( ：。口 尼( ，z ) + 6 ) ，若y o ，则x 归为正类； 若y 0 ，则工归为负类。 x = ( 一x 2 输出( 玖簧规则) ： y _ - y s g n ( ：- 1 西旌七( 五，力+ 6 + )s g n 【厶 啦旌七【而，砷+ 6 ) 权 戡哟- 呸y j 石j 7 基于个支持向最而，而一，毛 的爿e 线性变换 一) 输入向镊石一( 一，石2 ，) 图2 - 2 非线性软间隔支持向量机示意图 实验表明，支持向量机有以下特点： 结构简单，易于理解。 性能优良，泛化能力好。 优化问题有唯一的极小点。 第2 章支持向量机及其反问题 适合处理高维数据，可避免维数灾难。 更换核k ，可以得到各种不同的超平面。 支持向量机不仅用于模式识别，而且还被应用于回归估计，函数逼近等领域。 2 2 支持向量机求解 通过上一节的介绍，支持向量机的训练可以转化成为线性约束下的一个凸二次规划 形式。即： m a x 形( a ) = e i = i a i - - 去：j = 。a i c t j y , y j k ( x , ，一) “，只= o ， ( 2 1 4 ) c 芝口，0 ，i = 1 ， 这样的凸二次规划没有局部最小，并且可以有效求解。实践中训练集很大时直接使 用传统的二次规划求解方法就会遇到障碍，因此利用特征空间的隐式映射、优化问题的 凸性和解的稀疏性，一些特定的，更高效的支持向量机算法被提出。 2 2 1 常用求解方法 最简单的启发式为块方法【1 4 1 。它的基本思想是：删除矩阵中对应于l a g r a n g e 乘数 为零的行和列不会对最终结果产生影响。因此去掉对应于非支持向量即l a g r a n g e 乘子 为零的训练点，而只对支持向量计算相应的l a g r a n g e 乘子。所谓“块 就是在训练过 程中训练集中的一个子集，而块方法最终就是找到由所有支持向量组成的子集。但是， 在训练过程结束以前支持向量是未知的。因此，块算法的目标就是通过某种迭代方式逐 步排除非支持向量。 分解的方法又称为固定工作集的方法 1 5 a 6 】。这个思想最早由o s u n a 等人提出【1 5 】，也 称为“分解算法”或“o s u n a 算法”。一般地，如果问题不是稀疏的或者问题规模很大， 支持向量的活动集仍然会很大，以至于不能在优化模块中处理，此时可以使用分解的方 法。它把整个问题分解成为固定样本数的子问题，工作样本集的大小固定在算法速度可 以容忍的限度内。迭代过程中只是将剩余样本中部分“情况最糟的样本与工作样本集 中的样本进行等量交换，即使支持向量的个数超过工作样本集的大小，也不改变工作样 1 1 河北人学- 1 ：学硕十掌位论文 曼! ! 曼! ! 詈! ! ! ! 兰! 喜! ! ! 暑皇鼍! 皂皇! ! 曼! ! ! ! ! ! ! i i i i m 1 1 曼苎曼! ! ! ! ! 詈! ! ! ! ! 詈! 詈! 寡鼍! ! ! ! ! 詈! ! 曼 本集的规模。在这个算法中，首先建立一个工作集，保持其大小不变，在解决每个二次 规划子问题时，先从工作集中去掉一个样本，并加入一个不满足k k t 条件的样本，再 进行优化。 在分解算法的基础上，p l a t t 等人提出的序贯最小优化( s m o ，s e q u e n t i a lm i n i m a l o p t i m i z a t i o n ) 算法【| 8 】将工作集的规模减小为两个样本，使得每一步迭代的子问题的最优 解可以解析地给出。他设计了内外两层嵌套循环启发式地选择进入工作集的两个样本， 加快了算法的收敛速度。这也是我们解决s v m 反问题时采用的求解方法，下面进行更 详细的介绍。 2 2 2 序贯最小优化算法( s m o ) 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 ) - 算i 去1 1 8 】是1 9 9 8 年微软研究院的j o h nc p l a t t 提出的。s m o 是一种简单的算法，它可以快速地解决s v m 的q r , 问题，而不需要额外 的矩阵存储，也根本不需要数值化q p 。s m o 将整个q p 问题分解成多个q p 子问题， 利用o s u n a 定理确保其收敛性。 这种算法将工作样本集的规模减到了最小两个样本。之所以需要两个样本是因 为等式线性约束的存在使得同时至少有两个l a g r a n g e 乘数发生变化。由于子问题的优化 只涉及两个变量，而且应用等式约束可以将其中一个变量用另一个变量线性表示出来， 所以迭代过程中每一步的子问题的最优解可以直接用解析的方法求出来，无需使用数值 分析中的二次规划软件包，提高了子问题的求解速度。此外，p l a t t 还设计了一个两层嵌 套循环分别选择进入工作样本集的两个样本，外层循环选择第一个样本，内层循环选择 第二个样本。外层循环首先在整个样本空间循环一遍，决定哪些样本违反了k k t 条件。、 如果找到了不满足k k t 条件的样本，则选择它作为工作集的第一个样本。然后根据第 二个启发式规则选择第二个样本。最后用解析的方法快速的对选定的样本进行优化。为 了加快算法的运行速度，外层循环不总是检查所有训练样本，而是每次在所有样本上循 环一遍以后，只在l a g r a n g e 乘数大于零和小于c 的样本上进行循环，直到所有l a g r a n g e 乘数大于零和小于c 的样本都满足了最优化所应该满足的k k t 条件，然后再在整个样 本空问循环一遍。这样，外层循环是交替地在整个样本空间和l a g r a n g e 乘数大于零且小 于c 的样本上进行。内层循环选择第二个进入工作集的样本，选择的原则是使目标函数 第2 苹交持向鹫机及其反问题 接近最优点的速度达到最快。这种启发式的样本选择策略大大加快了算法的收敛速度。 标准样本集的实验结果证明，s m o 表现出在速度方面的良好性能。 在文献 1 9 】中，s s k e e r t h i 等人对p l a t t 的s m o 进行了重大改进，即在判别最优条 件时用两个阂值代替一个阂值，从而使算法更加合理和快速。并通过实际数据库的对比， 证明确实比传统s m o 算法速度快。 改进后的s m o 算法的a 选择和更新过程如下： ( 1 ) 首先选择两个要更新的a 。和a ：。 把训练样例分为五个集合 i o 兰 f ：0 ( 2 15 ) 其中只三w r t 一只，对应的就是要选择的口，和a ：。 ( 2 ) 找到a 以后，就按下式更新口 a 罗：a 产一巫衄( 2 - 1 6 ) l l 计算口，的上界h 和下界l ，如果h = l ，更新失败 矿h m a x m a r g i n m a x m a r g i n4 - - m a r g i n ( x ) = f ( x ) e n di f s c + + e n dw h i l e 设置当前：1 了点的划分函数为f ( x ) 根据厂。( x ) 把当前：1 了点中的样本分为e x a m p l e 和e x a m p l e + e x a m p l e = x lx e x a m p l e ，a n d f ( 工) 0 ) e x a m p l e + = xlx e x a m p l e ，a n d f ( x ) 0 在当前讧点。卜增加左分支。然后在这个分支卜增j j n - f 树l m d t i ( e x a m p l e ) 在当前掺点卜增加右分支，然后在这个分支。卜增加子树l m d t i ( e x a m p l e + ) 返同当前 7 点 第3 章基丁最人m a r g i n 的决策树归纳及其并行算法 3 1 3 算法分析 现在我们分析一下基于最大m a r g i n 启发式决策树算法的时间复杂度。为了分析简 单，我们现在只考虑一个节点的分裂。设当前要分裂的节点中包含的样本数为r l 。一个 节点的分裂分为三个步骤：第一步是聚类。最近邻聚类的时间复杂度是d ( 砌2 ) f 2 9 】；第二 步是s v m 反问题求解，使用s m o 算法训练一个s v m 的时间是c n 7 3 0 1 ，也就是说时间 复杂度是o ( n 7 ) ，文献( 2 4 】指出y 的值一般取2 。而s v m 反问题需要执行s m o 算法2 “1 一1 次，所以s v m 反问题的时间复杂度是0 ( 2 扣九2 ) ：最后一步是用得到的超平面分割当前 节点中的数据，它的时间复杂度是o ( n ) 。因此，经过这三个步骤，完成次节点分裂的 时间复杂度是这三步的和，即d ( 砌2 ) + 0 ( 2 卜n 2 ) + 0 ( ) ，结果为0 ( 2 卜1 玎2 ) 。我们可以看 出s v m 反问题在节点分裂中的时问复杂度最高。 下面给出实验数据来说明一下样本数和聚类数对基于最大m a r g i n 决策树归纳算法 训练时间的影响。实验中采用u c i 中的i r i s 、w i n e 、g l a s s 、i o n o s p h e r e 和p i m a 五个数 据库进行测试，每个数据库对应的样本个数分别为1 5 0 、1 7 8 、2 1 4 、3 5 1 和7 6 8 ，选用其 中7 0 的样例训练。从下表中可以看出，随着样本数和聚类数k 的增加，训练时i 可都会 明显增多。 表3 - 2 样本数对基丁最人m a r g i n 决策树归纳算法训练时间( s ) a o 影响k = 5 数据库样本数 串行时间( s