（计算机应用技术专业论文）基于类间最大间隔理论的多级决策树归纳算法.pdf

摘要 摘要 决策树归纳算法由于其实现简单，归纳能力强而逐渐成为了最常t t j 的机器学习 算法之。但当要处理的问题类别个数增多时，传统的决策树算法由于产生的单一 决策树过于复杂，而出现概括能力降低，预测精度下降的问题。针对该问题，本文提 d j 了一种基于类问最大问隔理论的多级决策树归纳算法，多级决策树的主要思想是 首先把多类别问题转化成正反两类问题来产生第一级的决策树，然后把正子类再细 分为n i 、反两类来产生第二级的决策树，同理把第一级的反子类也细分为f 、反两 类来产生第三级的决策树，在第二级的得到的正反两类重复上面的工作，直到把所 有类别都分歼。本文将最大间隔理论引入到了多级决策树归纳中，以期在每一级划 分正反予类时能得到较优的划分。 本文在闸述算法思想和步骤的基础上，通过与传统的决策树算法进行实验对比， 得到了如下结论：多级决策树算法能够得到条数较少、概括性更强的规则，从而能 够有效提高训练和测试精度。因此，该算法在多类别的分类问题及相关应用领域中 具有明显的优势和潜力。 关键词：多类别分类多级决策树支持向量机最大间隔理论类间问隔矩阵 a b s t r a c t a b s t r a c t d e c i s i o nt r e e ( d t ) a l g o r i t h mh a sa l r e a d yb e e no n eo ft h em o s ti m p o r tm a c h i n e l e a r n i n ga l g o r i t h m sb e c a u s eo fi t ss i m p l ea c c o m p l i s h m e n ta n dh i g hg e n e r a l i z a t i o n a b i l i t y h o w e v e r , w h e nd td e a l sw i t hm u l t i - c l a s s e sp r o b l e m s ，i tw i l lh a v es e v e r a l p r o b l e m s ，s u c ha sl o wg e n e r a l i z a t i o na b i l i t ya n dt e s t i n gp r e c i s i o n ，b e c a u s et h et r e e g e n e r a t e db yd ti ss oc o m p l e x i t y t oc o p ew i t ht h i sp r o b l e m ，t h i sp a p e rp r e s e n t sa m u l t i - s t a g ea l g o r i t h mb a s e do nl a r g e m a r g i nt h e o r y ( l m d t ) t h em a i ni d e ao fl m d t i st h a tf i r s t l yt h em d ta l g o r i t h mc o n v e y st h em u l t i - c l a s sp r o b l e mi n t ot w o c l a s s p r o b l e mb yl a r g em a r g i nl e a r n i n go fs v mh y p e r p l a n e s ，a n dt h e nf o re a c ht w o - c l a s s p r o b l e m ，i tu s e st r a d i t i o n a ld ta l g o r i t h mt og e n e r a t ead e c i s i o nt r e ew h i c hs p l i t s a d a t a s e ti n t ot w os u b s e t sf o rt h ef u r t h e ri n d u c t i o n i nt h i sp a p e r ，w ei n t r o d u c et h el a r g e m a r g i nt h e o r yi n t ot h ei n d u c t i o no fm u l t i - s t a g et og e ts p l i t sw i t hg o o dg e n e r a l i t yi n e a c hs t a g e i nt h i sp a p e r ，w ef i r s ti n t r o d u c et h em a i ni d e aa n dd e t a i lo ft h e l m d ta l g o r i t h m ， a n dt h e nw i t ht h ee x p e r i m e n t a lc o m p a r i s o n ，w ed r a wt h ec o n c l u s i o nt h a tl m d ti s s u p e r i o rt oo t h e ra l g o r i t h ma n dh a sg o o dp e r f o r m a n c e ，b e c a u s ei t n o to n l yc a ng e tr u l e s w i t hh i g hg e n e r a l i z a t i o na b i l i t yb u ta l s oh a sh i g ht r a i n i n ga n dt e s t i n gp r e c i s i o nr a t e k e y w o r d s ：m u l t i - c l a s sc l a s s i f i c a t i o n ；m u l t i s t a g e d e c i s i o nt r e e ；s v m ；l a r g e m a r g i n t h e o r y ；m a r g i nm a t r i x 河北大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包禽其他人已经发表或撰写的研究成果，也不包含为获得河北大学 或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了致谢。 作者签名：一雄一 一日期：上竺l 年月卫同 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印仲和电子版，允许论文被查阅 和借阅。学校可以公析i 论文的全部或部分内容，可以采用影印、缩印或其他 复制手段保存论文。 本学位论文属于 l 、保密口，在年月r 解密后适用本授权声明。 2 、不保密圈。 ( 请在以上相应方格内打“”) 作者签名：豸乜轻， 导师签名：云坦 日期：1 坐2 年 月卫同 日期：羔竺2 年上月 竺一同 第1 章绪论 1 1 决策树算法及研究现状 第l 章绪论 机器学习是一门新兴的科学，一般被定义为一个系统自我改进的过程，机器学习 的核心问题是从历史数据中学习出知识并且根据这些知识对系统进行自我完善而提高 性能，从而更好的为人们决策提供帮助。目前机器学习被成功的应用到很多领域，从学 习超市历史数据来优化配置货物，到自动识别人们的阅读兴趣的智能搜索引擎，雨到能 下深海自动探测和抢险维修的机器人，这个领域的理论和算法有了很大的发展，并且还 会进一步广泛的应用到交通、金融、科技、教育等各个领域。 决策树归纳学习算法由于实现简单，算法效率高，归纳能力好而逐渐成为了应用最 广泛的归纳推理算法之一。该算法的发展之初，是一种逼近离散值目标函数的方法，通 过一定的算法根据训练数据在目标函数集中逼近目标函数。在该算法的发展过程中，为 了处理属性是连续型数据的示例，人们又将模糊集理论引入到数据归纳和分类中来，于 是又l l j 现了模糊决策树，如基于f u z z y l d 3 启发式算法和基于m i n a m b i g u i t y 启发式算 法的模糊决策树，使决策树理论得到了推广。在这种方法中，学习到的函数被表示为一 棵树的结构，进而该结构再被表示成多个i f t h e n 的规则来提高可读性，再根据学习 到的规则对未知样例进行预测。 决策树的建立一般采用自顶向下的构建方法：对于给定k 类训练集： ( _ 。y 1 ) ，( x 2 ，y 2 ) ，( x l ，乃) ，每个样例有，7 7 个属性a = a i ，爿2 ，4 ，) ，且y c ic 2 , ，oo q ) ， 在建树过程中，在每个结点都要根据一定的启发式算法从候选属性中选择一个属性来分 割例子集合。当决策树中某一个分支的结点中的例子中某一类的比例达到一定的阈值 u 寸，陔分支停止生长，生成叶子结点，当决策树所有分支都停止生长时，该算法结束。 每一条从根到l 叶子的路径都可以生成一条规则。 在建树过程中启发式的选择，即每个结点如何选择属性来分割训练集是建树的关 键。根据启发式的不同，目前已经形成了多种决策树算法如：c l s 、i d 3 、c h a i d 、c a r t 、 f a c t 、c 4 5 、g i n i 、s e e 5 、s l i q 、s p r i n t 等。决策树的启发式大体上可以分成两类1 2 j ： 基于信息论的方法和基于最小g i n i 指标的方法。对应于前者的算法有：i d 3 、c 4 5 ，对 河北人学l ：学硕十学位论文 应于后者的有：c a r t 、s p r i n t 和s l i p 。目前关于决策树启发式的研究还是决策树研 究领域的热点，该领域的研究还在继续。 1 2 多级决策树算法的提出 归纳学习分有导师学习和无导师学习两种，这罩所提到的决策树归纳学习属于有导 师学习，即示例学习。决策树归纳学习方法以q u i l a n l 9 8 6 年提出的i d 3 为代表，由于该 算法比较简单，容易实现而且适于处理规模较大的学习问题，现已成为归纳学习的一个 重要方法。但该算法在处理多类问题时由于决策树算法自身的缺陷即分类而界限过于单 一，再加上各类数据问相互干扰而导致归纳能力下降【3 ，4 】，从而该算法不能很好的解决多 类问题。 为了解决该问题，文献 4 】提出一种基于层次分解的决策树( h i d 3 ) 。所谓层次分解 就是把多类别的分类问题按一定的方法转化为两类问题来分层次处理。本文基于此思想 提出了多级决策树算法，经实验证明该算法处理多类问题时分类效果明显，准确率高， 较以前的方法有很大优势。多级决策树算法的主要思想是：首先把多类别问题转化成矿 反两类问题来产生第一级的决策树，然后把f 类再细分为正、反两类来产生第二级的决 策树，同理把第一级的反类也细分为子的f 反两类来产生第三级的决策树，在第二级的 得到的正反两类重复上面的工作，直到把所有类别都分开。 支持向量机理论是在上世纪六十年代以后，在统计学习理论发展的基础上发现的一 种新的学习理论。该算法出现以后，在学习领域表现出了优异的性能，在美国科学杂志 上，支持向量机以及核学习方法被认为是“机器学习领域非常流行的方法和流行的例子， 并且是一个非常令人瞩目的发展方向”。由于支持向量机在机器学习领域表现出了优异 的性能，我们希望将支持向量机的理论引入到多极决策树的算法中，通过二者的结合， 使多极决策树在处理多类问题上性能有一个大的提高。 根据上述思想，本文提出了一种基于类别问最大间隔的多级决策树( m u l t i s t a g e d e c i s i o nt r e eb a s e do nl a r g em a r i nd e c i s i o nt r e e ，l m d t ) 启发式算法，该算法在多级决 策树的每一级根据最大阳j 隔理论将多类问题转化为两类问题并且在每一级建立完整的 决策树。由于在每一级产生明显的分类函数界，算法产生的规则比传统的决策树算法简 洁，概括，并且支持规则的例子更多，从而能获得较满意的训练和测试精度。 第1 章绪论 1 3 本文主要研究内容 最大问隔理论是支持向量机理论的一个重要组成部分，该理论认为大的间隔蕴涵着 好的归纳性能”一l 。文献【7 】希望把最火问隔理论引入到决策树归纳算法中，作为一种新 f f , j j 。j 发式来提高决策树的泛化能力，提出了s v m 的反问题理论。而在多级决策树归纳 算法中，很关键的一步就是需要把多类问题按一定的理论转化成两类问题，所以本文在 s v m 的反问题摧础上，提出了类问最大i 开j 隔，希望在多级决策树的每一级分成的两个 子类具有最大的问隔。本文将最大问隔理论应用到多级决策树归纳算法中，从而获得较 ；【f - f ( , j 泛化能力。 山_ - j 二s v m 的反问题算法的效率比较低，我们刘算法进行了一些改进，引入类j u j 删 隔矩阵，并通过没计合理的算法提高了效率。我们的文章的结构是这样的：我们在第二 章对统计学习理论和支持向量机理论进行了简要的回顾，支持向量机本来是解决两类问 题的归纳学习算法，为了能够使该算法能够解决多类问题，国内外的很多学者对该算法 进行了改进，提出了很多解决多类问题的算法，我们在第二章对其中比较重要的算法进 行了简单的总结。第三章介绍了基于类问最大问隔的多极决策树归纳算法，第四章是实 验、分析和该算法在变压器综合故障诊断巾的应用，最后一章是对全文的总结。 河北人学l ：学硕十学何论文 第2 章基于统计学习理论的多类分类器综述 支持向量机( s v m ) 是在统计学习理论的基础上发展出来的新一代学习算法，该算 法在文本分类、手写识别、图像识别、生物信息学等领域获得了较好的应用。支持向量 机是机器学习领域若干领域的集大成者，并且集成了最大问隔理论、m e r c e r 核、凸二次 规划、稀疏解、和松弛变量等多项技术【8 1 。 本章首先介绍了统计学习理论的发展，然后介绍了该理论的核心支持向量机 ( s v m ) 理论的基本问题，并介绍了处理多类问题的一些重要的算法。 2 1 统计学习理论的发展 传统的归纳问题遵循着“经验j x l 险最小化( e m p i r i c a lr i s km i n i m i z a t i o n ，e r m ) 原 则”1 5 】i1 6 l f 8 1 。为了在测试样本上取得好的推广性，e r m 原则提出了最小化训练误差的 决策原则。七十年代的研究发现e r m 原则的一致性( 对于给定的事件集合，事件概率 序列依最小概率收敛于目标函数集合的最小可能值) 的充要条件和收敛速率取决于学习 及其所实现的函数集的容量。e r m 的原则与分布无关的一致性的充要条件是，学习机 器所实现的函数集具有一个有限的v c 维，并且收敛速率的与分布无关的界取决于v c 维、训练误差大小和观测样本数。而一致收敛速率的界不仅解决了e r m 推理的主要理 论基础，而且促进了归纳推理一种新的理论结构风险最小化( 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 ) 的产生。这种新的理论认为：为了通过控制( 最小化) 训练错误的大小来达到测 试错误的最小界，应该采用v c 维最小的学习机器。这种新的理论发现了学习机器的推 广能力取决于机器所实现的函数集的容量，而容量不同于自由参数的个数，从而使处理 高维数据成为了可能。 2 0 世纪的八十年代，容量控制理论取得了实质性的进展。在学习理论发展新体系的 过程中，f r o s e n b l a t t 在分析模式识别问题时1 5 j ，发现了模式识别这平叶- 需要从经验数据中 估计函数的一般统计问题中要估计的函数属于简单的函数集，并且在分析这些简单的函 数集的过程中，发现了函数集容量的概念，并且容量决定了推广能力。从此，容量控制 成为了新的方法的主要的分析工具之一。 容量控制理论以支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 出现达到高潮，这是 第2 章基丁统计学习理论的多类分类器综述 山v a p n i k 等人提出的一套学习算法，该算法综合考虑了核空间理论，泛化性理论和最 优化理论。根据不同的泛化性界，支持向量机理论启发了不同的算法，比如优化最大间 隔、问隔分布或支持向量的数目。而最早提出的模型是最大叫隔分类器，而关于支持向 量机理论的研究仍是现在分类及归纳理论的热点。下节主要介绍支持向量机理论的基本 问题。 2 2 支持向量机的基本问题 s v m 最初只能解决二类分类问题，s v m 的基本问题拙述如下f 7 j ：设有训练数据 ( x i ，乃) ，( 恐，奶) ，( _ ，乃) ，x r ”，y + 1 ，一1 可以被一个超平而 ( x ) + b = 0( 1 ) 分开。如果这个向量集合被超平面没有错误的分开，并且离超平而最近的向量与超平面 之i u j 的距离是最大的，则我们说这个向量集合被这个最优超平面( 或最大i h j 隔超平面) 分开。如图1 所示。 o 图1 最优分类超平面 我们使用下而的形式；来描述分类超平面： ( x ，) + b l ，y ，= l ( x ，) + b 一1 ，y ，= 一l 并且有紧凑形式： 只 ( ) + b 】1 ，= l ，2 ， 容易验证，将样本点无错误分开的超平面( 1 ) ，其削隔为： 刀，a r gi n = 1 1 1 0 , i i 气 河北人学l ：学硕十学位论文 最优超平面是在线性可分的前提下讨论的，在线性不可分的情况下，可以在条件巾 加入一个松弛变量考，0 ，这时的最优超平面称为广义最优超平面，通过解决如下问题 得到： m i n ( ) = i 1 ( c o ) + c 考， 满足 只【( x ，) + b 】1 一考，i = 1 ，2 ， 其中c 是一个常数。最优超平面可通过解下面对偶问题得到： m a x ；m u m ( a ) = 兰一圭：i = 1y y p t a i ( 誓x ，) l s u b j e c tt 。二i 胪，= o ；c a ， 0 ，i = 1 2 一， 最优分割超平面有如下形式： ( x ) = ：，只a ? ( 一x ) + b o ( 4 ) 事实上，对于大多数实际问题，样本点在原空间巾一般不是线性可分的，所以j j 上 述方法往往得不到好的决策函数( 最优超平面) 。为此，v a p n i k 将支持向量机从原空州 中推广至特征空f n j 。其基本思想如下：支持向量机通过某种事先选择n , 9 1 仁线性映射将输 入向量x 映射到一个高维特征空问z ，在这个高维特征空问中构造最优分类超平而。而 这个非线性的映射称作是核函数： ( 毛z 2 ) = k ( x i ，x 2 ) ( 5 ) 目前常用的核函数有： 1 多项式核函数k ( x j ，恐) = 【( 一) + 1 】f ， 2 高斯核函数m 蚓一p ( _ 哼2 ) 3 s 形核函数k ( x l ，x 2 ) = s ( z ，( 五x 2 ) + c ) 其中，甜为常数，s 为s i g m o i d 函数。 引入核函数后，s v m 所求的最优超平面为： ( x ) = ：只0 f ? k ( 一x ) + 6 0 ( 6 ) 第2 章基丁_ 统计学习理i c - n ；j 多类分类器综述 2 3 基于s v m 的多类分类器 支持向量机的基本问题是解决二类分类问题，目前有很多方法将支持向量机推广至 多类分类，日时比较著名的有1 一博一1s v m 、 1 一凇一，7s v m 、以及d a g s v m ，文献 5 】 1 1 1 详细的介绍了这三种方法，并进行了详细的比较。我们在下面的章节中对支持向量机 的多类分类器进行了简要的总结。 2 3 11 v s n 方法 1 一坩一刀方法是最早提出的用基于s v m 的多类分类器，对于给定的一个七类训练集 ( 。) ，。) ，( x ：，y ：) ，。( _ ，乃) ，x r ”，y 少。j ，：，y k ) 1 1 博一，7 方法构造走个s v m 分类器，对于第，个分类器，把属于第，类的例子看作 是币类，而把其余所有的例子看作是负类，这样就把洲练集转化成了一个新的两类问题， ：j i f 且可以利用s v m 的基本l 、u 】题求解，其所要求解超平面以及与之相对应的对偶问题和 s v m 的基本问题类似。第，s v m 分类器得到的决策函数 ：= ( 0 9 ) k ( x ) 4 - b ( 7 ) 对于所有的七个类别，可以得到七个决策函数： ( c 0 1 ) k ( ) 十6 ( 0 9 ) k ( ) + 6 刘于待测样本x ，将j 代入这后个决策函数得到七个函数值，驭得最大值的决策函数对 应的类别即为该样本的类别，即： c ( x ) - a r g ( m 川a x ( ( w ) k ( x ) + 6 ) ) ( 8 ) 该方法的优点是建立的分类器较少，匹配的速度快。缺点就是对于每一个分类器所 有的样本都参加训练，训练速度较慢。 文献【9 】，【l o 】，【11 中都提到了一种一次性求解的方法，该方法同l v s 一玎一样都是 要得到k 个作用相同的决策函数，所不同的是一次性求解的方法的七个决策函数是通过 求解一个优化问题得到的，因此该方法又被称为完全多类支持向量$ j l ( a 1 1 t o g e t h e r ) 。完全 多类支持向量机所要求解的优化问题可以表示成如下形式： 河北人学i ：学硕十学他论文 满足 r a i no ( c o ) = 去( q ，) + c ? - - i l l = i ，= l ，”l i ( 9 ) j j 妒( 一) + b y , ，”妒( 一) + 匆，+ 2 一考j ( 1 0 ) f o ，i = 1 ，朋 l ，k ) 只 、 该问题实现比较困难，不适于实际问题的应用，所以该方法不常使用。 2 3 2l - v s 1 方法 另外一种比较重要的基于s v m 的支持向量机多类分类的方法是，对于所有的类别 两丽组合，构成一个s v m 分类器。对于有后类的i j l l 练集，共有k ( k 一1 ) 2 中组合方式， 即可以构成k ( k - 0 2 分类器。对于第i 类和第_ ，类构成的分类器，将训练集f | 1 所有属于 第i 类的数据标为萨类，所有属于第类的数据标为负类，从而得到第，类和第j 类的决 策函数： z ，= ( c o “) k ( x ) + 6 ” ( 1 1 ) 对于所有的七个类别，可以得到的k ( k 一1 ) 2 个决策函数为： 彳，：，彳。，z 。t 五，3 ，五， ； z “ 对于待测样本x ，采用的是投票( v o t i n g ) 的方法来确定它的类别：将x 依次代入这 k ( k 一1 ) 2 个决策函数，例如， ，当z ，( x ) 0 ，第i 类的票数增1 ，( x ) 根据式1 4 计锋每一匮性信息增蘸嘲其有最人信息罐稳的属性米扩醚根结点o 根据选定的属性的照将训练集划分成儿个子集j 1 ：检奄若子集符合式( 15 ) 刚生成叶子结点， j l ：拆示该结点的类铡o 若子壤不符合式f j 5 ) ，州递门的凋j | j 该建树过程o 。， 将产，上的决策树转化为一组规刚其中每条规则是根绵点l 出发钠l l l i 予结点的一条路径o 1 i ) 3 力i 去川洲练集建立单一决策树，随着要处理的洲练集所包含的类的个数增多时， i j j 予数和结点数就会增多，单一决策树就会变得复杂。而复杂的树产生的舰则就会过于 适合训练例子，而使预测准确度降低。同时每个规则中所包含的部分属性值对这些训 练例子是无关的l6 1 。【6 提出了一种基于层次分解的多级决策树，目的在于能在每一个层 次都能得到比较简单的树进而得到简单的舰则，从而总体上获得较好的泛化能力。 目萌订，如何提高多类分类的精确性成为了机器学习研究的一个热点，而多级分类由 于其机理简单，效果明显，因此成为了人们普遍采h j 的解决多类分类的一利- 常用的方法。 在本文中；我们希望将多级分类引入到决策树归纳算法中，实现多级决策树算法，使决 策树算法能够很好的解决多类分类问题。 多级分决策树也是一个递归算法，在多级决策树的第一级，首先j j j 一定的标准将多 类问题转化成一个两类问题：对于给定的一个| | 类训练集s ： ( 、儿) 。( x ：，y ：) ，( x ，乃) ，x r ”，y c ，其中c = c ic 2 ，q ) ，将s 根据例子的类别分 河北人学1 ：学硕十学佗论文 割成两个子集s + 和s 一，即将c 中的某几类看作成一个子类c + ，而将其余的几类看成足 另外的子类c 一，将s 中的每一个类别用c + 和c 一标示以后，s 就转化成了一个两类的问 题。s 就可以被分成了两个子集s + ( s 中所有表示为c + 的样例) 和s 一( s 中所有表示为( ” 的样例) ，用传统的决策树归纳算法建立第一级的决策树。建完第一级决策树后，递归 处理s + 和s 一，直到每个子集都包含一个类别为止。 多缴决策树的关键步骤是如何将多类问题转化成两类的问题。对于如图3 所示的多 类问题训练集的空问分析i 图。当用服从该图所示分析i 的数据作为训练集建立第一级决策 树时，有好多种比较合理的划分方法： 1 c + = “，c 2 ，c 4 ) ，c 一= 白，f 5 ，c 6 ) 2 c + = k ，c 2 , 巳) ，c 一= c 4 ，c 5 ，c 6 ) 3 c + = 托，c 3 ，c 4 ，c 5 ，气) ，c 一= c 2 ) 图3 六类问题示意图：c l = c l a s s l ，c 2 - - c l a s s2 , c 3 = c l a s s3 ，c 4 = c l a s s4 ，c 5 = c l a s s5 ， c 6 = c l a s s 6 多级决策树归纳算法首先要解决的问题就是选择将多类问题转化成两类i u j 题的标 准，标准选择不同，转化的结果也不同，就会对后续的归纳结果产尘影响，目前有好多 可以用来作为转化的算法。最大i 、日j 隔理论是支持向量机理论体系的重要部分，其核心的 思想就是最大的问隔蕴涵着比较好的归纳能力，所以本文中，希望将最大问隔理论作为 转化的标准，并且提出比较合理的算法。 3 2 最大间隔理论 最大i 日j 隔理论既是支持向量机理论的基础，又是支持向量机理论重要组成部分。下 面，就对该理论的一些主要内容做一下简要的介绍。 第3 章基丁类问最人问隔的多级决策树 3 2 1v c 维 v c 维是度量目标函数集容量的jf ，a ) ，a 人的v c 维【5 8 9 1 ， 是能够被集合中的函数以f j f 有可能的2 ”柙万式分成网英明同量z ，z h 的最大数目h ( 也就是能够被这个函数集打散的向量的最大数目) 。如果对任意的，7 ，总存在一个 可 以被函数集q ( z ，a ) ，a 人打散，那么函数集的v c 维就是无穷大。 对于实函数集来说，其v c 维的定义如下：设asq ( z ，a ) sb ，a 人，是一个以常数 a 和b 为界的实函数集合( a 可以是一o o ，b 可以+ o 。) ，其指示器集合为 i ( z ，a ，卢) = o ( q ( z ，a ) 一卢) ，a 人，p ( a ，b ) 其中o ( z ) 足阶跃函数 吣，= 0 妻三 则函数集a q ( z ，口) b ，a 人的v c 维定义为其指示器集合的v c 维，其中参数 口人，3 ( 彳，b ) 。 定理3 1 ( v a p n i k 和c h e r v o n e n k i s ) ：令h 是v c 维为d 的假设空间。对在xx - i ，1 ) 上 n ，j 任意概率分嘶jd ，与，个随机样本集s 一致的任意假没空i e i jh 在s 上的概率l _ 6 不 大于： 盯r 。( h ( f ，脚) = 和。g 了2 e l + 1 0 9 昙0 ) 1 )l a) 条件是d ，2 s 。 这一定理显示了对于无限假设集，过拟合的问题是可以避免的，所使h j 的复杂度的 度量矿是v c 维。要保证好的泛化能力，在一致假设情况下训练样本的大小跟这个量呈 线性关系。 v c 理沦为一致假设提供了分析j 无关下的一个泛化性界，对于具有高v c 维的假设 类，存在输入概率分确i 要求学习器增大训练集来获得好的泛化能力。可以看出v c 维刻 画了函数集的学习能力将误差表达为有限的v c d i m ( h ) 的函数。 v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂( 容量越大) 。可是目 d 订尚没有计算任意函数集v c 维计算的理论，只能够 1 。算一些特殊的函数集的v c 维。 河北人学i ：学硕十学何论文 3 2 2 最大间隔理论 最大问隔理论是支持向量机理论的最重要的组成部分，该理论认为大的问隔蕴涵着 好的归纳能力5 , 6 , 7 , 8 1 ，所以构造分类器日j 。总是寻找具有最大的l j 隔的分类面。以下是分类 器问隔的定义f 8 】： 定义3 1 ：样例( 一，只) 对应于超平面( c o ，6 ) 的( 函数的) 间隔是量：) ，= ( ( 一) + 6 ) ， 其中) ， 0 意味着( x ，”) 被f 确分类。超平而 ，6 ) 对应于训练集s 的问隔分布就是i jj l 练 集s 中样例的间隔分布。 推广到任意实值的函数类则有： 定义3 2 ：考虑在输入空问x 上使用一实值函数类f 来分类，阂值为0 。定义样例 ( 一，”) xx - 1 ，1 ) 对应于函数厂f 的问隔是y ，= 只( 一) 其巾7 ， 0 意味着( 一，儿) 被讵 确分类。对应于训练集s 的厂的i 瑚隔分柿是训练集s 中样例的间隔分布。有时将川隔分 布的最小值对应于训练集s 的厂的间隔m ，( 厂) 。如果j 下确分类s ，这个值是正的。而 对应于类f 训练集s 的问隔是在所有厂f 上的最大f h j 隔。 以上为分类器的| 、口j 隔的定义，而大的问隔蕴涵着好的归纳能力是因为分类器的错误 界可以用分类器的1 白j 隔巩( ) 来定义。 定理3 2 1 8 l ：考虑闽值化一个实值的函数空问f 并固定y r + ，对于x x 一l ，1 ) 上的 任意概率分印d ，具有间隔m 、( 厂) y 的假设f f 在，个随机样例s 上的误差以概率 1 6 不大于： p 哪e ( 1 , l , 8 , y ) = 弛( f , 2 1 , 7 2 ) + l 。g 詈) 考虑到宽打散维( v c 维的实数推广) ，定理3 2 可以表示成： 定理3 3 。8 ：考虑在区间 - r ，r 】内阈值化个实值的函数空间f 并固定) ，r + ，对 于x x 一l ，l 上的任意概率分布d ，具有间隔m ( ) ) ，的假设f f 在f 个随机样例s 上 的误差以概率1 6 不大于： 一垆以脚= 弛g 等l o g 等礼g 刳 定理3 3 显示如何用m ，( ) 来界定泛化性误差，这个量可以从训练的结果观察到， 第3 章基丁类问最人问隔的多级决镱树 并且可以得出在小的样本上大的问隔可以产生好的泛化能力。 并且可以进一步得出s v m 的最大i f j j 隔界： 定理3 4 1 8 i ：考虑在内积空问上的阈值化具有单位权重向量的实值线性函数三， 并固定，瓞+ 。在x 一1 ，1 ) 上的任意概率分斫jd ，在以原点为球心，半径为r 的球内， 在1 个随机样例集s 上具有问隔m ( 厂) ) ，的假设厂l 在s 上的误差以概率1 6 不大 于： 踟黔州 研，= 款丁6 4 r 2 崦石e l y 崦等扎g 刳 3 2 3s v m 的反问题理论的提出 s v m 算法是一种基于统计学习理论的算法，该算法遵循结构风险最小化原理 ( s r m ) ，并且该算法比较适合于小样本数据。s v m 算法的出发点是在分类过程中寻找归 纳能力强的日标函数，而在统计学习理论中，归纳能力是用v c 维来度量的。并且根据 1 - l jq 所迷的知以，最大的州隔蕴涵着较好的归纳能) j 1 5 6 8 】。 山于问隔和归纳能力之问存在着一定的关系，文献 7 】提出了s v m 的反问题，反问 题足- 1 1 基于最大问隔学习理论的划分数据集的策略。其重要思想就是每次用最大问隔 的思想寻找原数据集在特征空l - j j ：的两个划分，这种分割策略可以应用到其它的机器学 习方法巾，比如可以代替最大增益方法分割训练集的方法来生成决策树，从而得到的决 策树具有较好的归纳能力。 s v m 的反问题的描述如下： 定义3 3 ：设给定无类别数据集u = “，x 2 ，h j ，其中x 并且，= l ，2 n ， q = 厂1 厂为u 到 一1 ，1 】的一个影射 ，对于一个给定，u 可以分成正负两个子集，则 这个数据集可以用一个最优超平面m a r g i n ( f ) 分开，对于厂q ，存在一个最大问隔将 数据分成两个子集： m a x i m u m f 。o ( m a r g i n ( f ) ) ( 16 ) s v m 的反问题就是穷举数据集中的点所有可能的类别，这种算法的效率非常低。f 7 1 - l _ i 就捉：u 了一种用遗传算法来求解反问题，取得了很好的效果。当然还有很多改进的算 法，比如先聚类再求解，或者采用并行算法求解。 1 7 河北人学l ：学硕十学位论文 3 2 4 类间最大间隔 本文中我们将s v m 的反问题进行了推广，提出了类问最大间隔，并将类问最大i r j 隔 用在了多类分类中，类问最大间隔定义如下： 定义3 4 ：给定所类数据集u = ，x ：，h ，其类别c = c 。，f ：，f 。】且 一xi = l ，2 ，n ，假设q = g ig 为c 到 一1 ，1 ) 的一个影射 ，对于一个给定g ，c 中的 每一个元素都可以重新标定为1 或者1 ，这样c 就可以划分成两个子类g 和e ，并且这 个数据集就被划分成了正负两个集合并且可以用一个最优超平面m a r g i n ( g ) 分开，刘。于 g q 。，存在一个最大问隔： m a x i m u m g n ( m a r g i n ( g ) ) ( 17 ) 将数据分成两个子集u ，和u ：。 m a x i m u m g e f l ( m a r g i n ( g ) ) 就称为类问最大间隔，因为对于一个给定的g ，原数据 集中类别一样的数据分到了相同的子集中。当数据集的类别不是很多时，穷举所有的可 能的效率也不是很低。 3 3 基于类间最大间隔的多级决策树( l m d t ) 多级决策树主要是为了解决决策树处理多类问题性能下降的问题而提出的，自矿面章 节介绍了多级决策树的主要思想：使用一定的标准将多类问题转化成一个两类问题，以 后用传统的决策树归纳算法建立第一级决策树。然后将训练集分成两个子集，再递归处 理两个子集，直到每个子集都包含一个类别为止。 基于类f n j 最大问隔的多级决策树( l m d t ) 主要思想就是将式( 1 7 ) 所提出的类问最大 f n j 隔作为多类问题转化成两类问题的标准，使训练集划分的两个子集有最大的f r j 隔，从 而保证该算法具有很好的泛化能力：即对于给定的一个k 类训练集s ： ( x im ) ，x 2 ，y ：) ，( 一， ) ，x 彤，y c ，其中c = “，c ：，q ) ，用( 1 7 ) 将s 将转化盛一 个两类问题s ，建立第一级决策树后，将s 分成两个子集s + 和s 一，递归处理两个予集， 多级决策树的算法可以表示如下： 第3 章基丁i 类问最人问隔n 勺多级决策埘 算珐2 ： 在所给多类西例子集合尹选定训练祟。 、户 用最大，田膊理论符训联巢转化成一个正负两类问题，用偌统厅争央慕树方珐建立弟一级决震树。 根据上步转化的类别，杼原始训练祟分列成两个亍祟，即在上步尹转化成正类的为一含子集， l 嗲专转 匕为焱类的为另舟一个予集o 递归处理正类子集 递归处理负类子集 丛于类i i j j 最大| 口j 隔的多级决策树算法和2 3 4 , p 提日 的最大间隔s v m 分类器的构造 算法足很相似的，从多类问题转化成两类问题，这两种算法所用的方法相同，在转化成 眄类问题以后，这两个算法的处理方法有所分别。1 j 玎者j j 决策树归纳算法进行处理，后 者继续川s v m 的方法进行处理，由于决策树算法和s v m 算法有差别，这两种算法在不 同数据库上性能有些差别。 对于给定的一个i n 类的数据集，笫一级共有2 ”。一1 种划分方式，因为c 中任个类 别i | i i ；可以标为化类或者负类，其中有一半重复的划分方式，并且当c 中的元素全部划分 成j f 类或负类时是无效的划分，所以共有竺善：2 ，一1 中划分方式。 z 根据上述理论，该算法具有很好的泛化能力，下面的实验也能汪明该算法确实可行。 但是这种算法的效率是非常低的，以u c i 数据库中l e t t e 卜r e c o g n i t i o n 数据为例，该数据共 有2 6 类，则在第一级共需要计算2 ”一1 = 3 3 5 5 4 4 3 1 次类问| 日j 隔，并且在第一级，每一次 求解类1 1 l j 最大问隔都用到了所有的数据，时州耗费特别大，所以改进该算法来提高效率 是很有必要的。 3 4 改进算法 3 4 i 类间矩阵 除了一。l - t 。, 。- l i ，一提出的效率低下问题，该算法在每次划分时倾向于划分出一个类别，从 而会降低该算法的归纳能力。为了克服上述缺点，提高算法的效率，该算法引入了类问 1 9 河北人学i ：学硕十学位论文 l 。日j i ；鬲矢巨l 浑来求角翠： 定义3 5 ：给定露类数据集s = ( x 。，x ：，x ) ，其类别c = ，c ：，f 。】且 一xi = l ，2 七，1 1 1 k ，是所有属于类i 的例子，和所有属于类j 的例子r ，所构成的两类问 题根据( 3 ) 求的的类问的问隔，- ，2 尼，i 其中( u ) k ( ) + 6 j ，为、，和一r ，的最优分类 超平面。则数据集s 的类i n j 间隔矩阵为： m = m i ，2 ，1 7 1 i 1 ，i l l ) ，其中且有i ，= 1 ，七且， m 成立 如果上述假设成立，则m i n ( 矽，i ，m ，m ， ) = ，又由于m m 。，则 m 矿m 矿，m 的每一个元素都大于心，则m i ，m 2 ，m t 肯定都包含m ，i ，m 矿，m “， m 矿m ，2 ，m 。能把c 分成两个子集，则根据算法3 的求解过程m i ，m 2 ，m ，。包含 m 矿m ，2 ，m ， ，则m 。，m ：，m ，肯定能把c 分成两个子集，则根据算法3 求解的最人 f a l n y , lm 与命题矛盾，所以m ，m ：，m 。为最优过程，该过程能够求出最大f u j 隔， 且可以得到和( 1 7 ) 式相似的结果。 3 4 2 综合考虑类间间隔和类内间隔 上节中的算法并不能保证能搜索到最优的结果，即不定能搜索到最大的i 训隔，即 只可以保证搜索到次优的最大的问隔。经过简单的分析可以得到如下的结论，当一个多 第3 章荩丁类问最人问隔f r i 勺多级决策树 类问题划分成两个子类后，子类间的问距肯定大于予类内各类的最大的问隔，即有下式 成立： m a x ( m ( c l ，c 2 ) ，q ，c 2 s + ，c ”。，c i ，c 2 s 一) m i n m ( c i ，f ：) ，f ：s + ，f ：s 一) ( 2 1 ) 山式( 2 1 ) 我们可以得出另外一种改进的算法，可以综合考虑划分成两个子类后子类 内的f u j 距和予类内的类f n j l f i j 。使划分后尽量使类内子类问隔小，使类问i n j 隔大。该算法 首先要借助如下的定义： 定义3 7 ：s 的类内问隔m 。( s ) ：给定的后类的数据集s ，s 对应的类别为c ，其中 c = 岛，( ：，q ) ，s 被分成了两个子集s + 和s 一，s + 的类问距阵m + ，m + 共有，+ 个元 素，s 一的类间距阼m 一，m 一共有厂个元素。则数据s 的类内| 自j 隔心，( s ) 为： fym + + ym m 。( s ) ：j 垡丁声一，m o )( 2 2 )m 。，( s ) = ，+ + ，一 叫v 7 ( 2 2 ) 【，矿( ，_ = o ) 定义3 7 的说明： 1 其中，m + 为s + 的类间距阵m + 各元素的和，m 一