（运筹学与控制论专业论文）数学规划在数据挖掘和机器学习中的应用.pdf

摘要 本文从机器学习领域中的两类分类问题出发，对于线性可分和线性不可分 的情况分别给出了直观的几何解释，并根据几何解释和数学规划中的对偶理论， 给出了线性分类器的数学规划表述。对于线性可分离情况，求两个样本集合的 最大间隔等价于求包含各自数据点的凸包的最小距离，并借助简约凸包的概念， 将这一结论推广到线性不可分离的情况。借助“最大间隔分类器“的理念，引入 了“支持向量机”的概念，并在下文中对支持向量机以及它和数学规划之间的 关系进行了较详细的阐述。 支持向量机( s u p p o r tv e c t o rm a c h i n e ，简称s v m ) 是在九千年代初期 由v a p n i k 及其合作者引入到机器学习领域中来的，之后受到了广泛地关注，在 数据分类、回归、奇异点分析、聚类问题、主成分分析等方面得到了应用，在 近几年得到了广泛地发展，现已成为机器学习和数据挖掘领域的标准工具。 支持向量机是机器学习领域中若干标准技术的集大成者。它集成了最大超平 面、m e r c e r 核、凸二次规划、稀疏解和松弛变量等多项技术，在若干挑战性的 应用中，获得了目前为止最好的性能。它在泛化性能和误差估计等方面得到了 统计学习理论强有力地支持，这是先前的传统统计方法和人工神经网络等所不 可企及的。文中在介绍了s v m 的同时渗透着核方法的理念，并突出强调核方法 在s v m 中的奠基性作用。核方法的引入，将s v m 的理念拓展到非线性分类器的 领域当中，即只需通过一次映射，将样本空间映射到一个特征空间，使得在特征 空间中我们可以将问题视为一个新的寻求线性分类器的过程，而映射是通过选 择合适的核函数来实现。接下来，做为两类分类问题的简单扩展，较为简单地 介绍了一下用s v m 解决多类分类问题的方法和思路。 在接下来的章节中，进一步阐述了数学规划和最优化理论在数据挖掘和机 器学习中的两个经典问题中的应用：特征选取和聚类。文中把特征选取和聚类 都表述成了一个数学规划问题，以便借助最优化领域中的成熟的算法使这两个 问题得以较好地解决( 目前在线性规划和二次规划中都有很好的算法) 。对于 前者，我们将特征选取和分类两个任务同时进行，得到的分类器很好地兼顾了 特征选取，使得分类器有较好的泛化能力。我们将其表述成一个数学规划问题， 但是在未经处理的时候，该非线性问题最多只能转化一个非线性整数规划问题， i i 数学规划在数据挖掘和机器学习中的应用 这在实际中是难以处理的，我们通过一些近似或者精确地转化步骤，最终可以 得到一个近似最优解，且最终问题是线性规划问题。目前，线性规划以其成熟 的理论体系和算法( 单纯形法和内点法) 备受青睐，它求解准确，算法稳健，在 大规模问题上表现出了良好的可扩展性( s c a l a b i l i t y ) ，近些年也涌现出了很多 性能优异的线性规划求解软件。该章最后，通过修改前述两类分类问题的支持 向量机中的相关度量，将问题转化为求解两个线性规划问题，并通过初步的理 论分析，可以看出在规模较大的问题上，这两个线性规划问题得到最优解可以 为原问题提供良好的近似解，从实际工程应用的角度来看，这也是一种较好的 思路。 最后，给出了总结和一点展望。 关键词：线性分类器支持向量机最大间隔数学规划核函数线性规划 第一章引言 从数据中学习的问题在历史上已经被很多哲学家研究过，并称之为“归 纳推理”。人工智能领域的研究者从一开始就考虑了学习的问题。a l a n t u r i n g 1 在1 9 5 0 年指出了学习器的思想，以反驳“机器只会做我们指挥他做 的事情”的论断。数年之后f r a n kr o s e n b l a t t 的感知器【2 】是最初开发出来的学习 器之一。对学习问题进行建模，使其成为适当假设空间中的搜索问题，这也成 为主流人工智能方法的特点。 学习算法的发展成为人工智能的一个重要的子领域，最终形成了机器学 习这样个独立的学科领域，是现代智能技术中一个非常活跃的领域。在历史 上，对机器学习有过很多不同的说法，目前大家比较公认的说法是s i m o n 对学 习的阐述m ：“如果一个系统能够通过执行某种过程而改变它的性能，这就是学 习”。s i m o n 对学习的说明是对机器学习一个一般性概括，可以说是一种理念。 这种说法包括三个要点：( 一) 、学习是一个过程；( 二) 、学习是对一个系统而言 的；( 三) 、学习可以改变系统的性能。过程、系统和性能改变是学习的三个要 点。对计算机科学而言，人们更关心对不同系统实现机器学习的过程，以及改 变性能的效果。简单地说，我们可以将机器学习理解为一种优化过程。 基于数据的机器学习就是研究如何从一些观测数据( 样本) 出发得到目前 尚不能通过原理分析得到的规律或者内在因素，即基于观测设计优化过程，然 后利用这些规律去分析客观对象，对未来数据或无法观测的数据进行预测和分 析。它的主要任务是：对于种未知的依赖关系，以观测为基础对它进行估计。 现实世界中存在大量我们还无法准确认识但却可以进行观测的事物，因此这种 机器学习在从现代科学、技术到社会、经济等各领域中都发挥着十分重要的作 用。 线性分类器的理论可以追溯n 2 0 世纪3 0 年代，那时f i s h e r 4 提出了一个 通过超平面分类多元数据的程序。检验线性关系的高效算法在2 0 世纪5 0 年代 和6 0 年代就已经被使用了，它们的计算行为和统计行为在和h 中有很好的描 述。在2 0 世纪8 0 年代中期，模式分析( 识别) 领域经历了一场非线性革命，几乎 同时引入了后向传播神经网络和决策树同、【7 1 。虽然这些方法建立在简单 的启发式算法的基础上，缺乏坚实的理论基础，但是它们第一次朝非线性模式 2 数学规划在数据挖掘和机器学习中的应用 的高效并且可靠的检测方向踏出了重要的一步。 把核函数用做特征空间的内积的思想，通过a i z e y l n a l l n 、b r a v e r m a n 和r o z o e n e r s 关 于势函数方法的研究，于1 9 6 4 年被引入到机器学习领域中。但是直到2 0 世纪9 0 年 代，b o s e r 和v a p n i k j 把它和最大间隔( m a x i m u mm a r g i n ) 超平面结合起来之 后，这种思想的潜在价值才开始被充分理解，并导致了支持向量机( s 讧) 的产 生。基于核的学习方法对于非线性模式分析来说颇有一种柳暗花明的感觉，使 我们可以基于成熟的线性算法理论来处理非线性关系，较为合理地将线性算法 拓展到非线性领域中去，使得非线性模式分析算法和与之对应的线性算法一样 高效且有理论依据。局部极小化和不完全统计分析这两个缺点是神经网络和决 策树中的典型弊病，在这里可以被巧妙地避开。 在机器学习中，如果观测数据是输入输出配对的。就被称作为监督学 习( s u p e r v i s e dl e a r n i n g ) 。输入输出对反映了从输入到输出的映射关系，从输 入到输出所蕴含的函数称为目标学习函数，学习算法得到的对目标学习函数 的估计就被称作为学习问题的解。解是基于数据从一个特定的假设空间( 函 数空间) 中选取的，而假设空间包含了全部从输入空间到输出区域的映射，学 习算法的泛化能力是我们选取合适的假设空间的主要考虑因素之一。泛化性 能( g e n e r a l i z a t i o na b i l i t y ) 是机器学习关心的焦点问题之一。对于监督学习而 言，学习的目标就是提高泛化能力，而对于一般学习问题而言，则需要识别出 统计上稳定的模式，稳定的关系是对生成数据的数据源的内在性质的一种体现， 并不是某个特定数据集的偶然特征。传统的机器学习方法都是基于经验风险最 小化原则，对泛化性能缺乏必要的分析和控制，存在“过拟合”的问题。在有限 样本的情况下，学习精度和泛化能力之间的矛盾似乎是不可调和的，采用复杂 的学习机器容易使学习误差更小，但却往往丧失了泛化能力。控制过拟合问题 的一个方法是限制学习模型的复杂程度，或者可以说是假设空间的“容量”。举 一个直观的例子，我们在多项式拟合的过程中，用高次函数拟合的准确性( 基于 目前的样本集合而言) 往往比低次函数更好，但高次函数却往往容易散失泛化 性能，也就是说对于其他的样本集合表现出来的准确性较差( 体现出过度拟合 的迹象) 。其基本的原因是由于高次函数相对于低次函数而言更加“复杂”，那 我们就应该控制拟合的曲线的复杂性，直观地，通过控制曲线的次数或者曲率 等来实现。 对于假设空间的容量的相关研究始于v a p n i k 和c h e r v o n e n k i s 等人，他们设 第一章引言 3 计出一种叫做v c 维数的空间容量衡量尺度。v c 维的理论可以很好地用来分析 学习系统的性能，通过把它和模式分析算法的可调参数联系起来，从而有可能 直接控制过度拟合数据的风险。机器学习实际应用中的许多学习启发和原理都 是以被v c 理论所解释。基于v c 维数的统计学习理论，在v a p n i k 的两本统计学 习理论的著作中有广泛描述1 、【11 1 。v c 维数的计算太过复杂，所以又有了后 来的基于c o v e r i n gn u m b e r 和r a d e m a c h e rc o m p l e x i t y 的复杂度分析f 1 3 1 、f 1 2 】。 二十世纪九十年代以来随着统计学习理论自身的不断发展和成熟产生了支 持向量机方法( s u p p o r tv e c t o rm a c h i n e ) ，它是体现结构风险最小化思想的一 种具体方法。支持向量机最初产生于模式识别问题中的两类分类问题，并被推 广到函数估计、回归、新颖检测f 2 1 等其他学习问题。支持向量机具有几何性和 对偶性，它的推导过程以及由其得到的最优超平面都体现出潜在的几何直观感。 支持向量机是一个线性学习机，但是基于核方法，非线性问题可以通过核函数 技术被转化为线性问题来解决，所以支持向量机的适用面是相当广泛的。 支持向量机方法是建立在统计学习理论的v c 维理论和结构风险最小原 理( s r m ) 基础上的。根据有限的样本信息，在模型的复杂性( 即对特定训练样 本的学习精度) 和学习能力( 即无错误地识别样本的能力) 之间寻求最佳折衷，以 期获得最好的推广能力。支持向量机集优化、核方法、统计学习理论等优点于 一身。其主要特点有： 1 支持向量机专门针对小样本情况，其目标是得到现有信息下的最优解而不 仅仅是样本数趋于无穷大时的最优值。它有坚实的数学和理论基础。 2 支持向量机算法最终将转化成为一个二次型寻优问题。从理论上说，得到 的解将是全局最优解，解决了在神经网络方法中无法避免的局部极值问 题。 3 支持向量机巧妙地解决了维数问题，其算法复杂度与样本维数无关。在支 持向量机方法中，只要选取不同的核函数，就可以实现多项式逼近、径向 基函数( r b f ) 方法、多层感知器网络等许多现有学习算法。支持向量机非 常适合于处理非线性问题。 4 由于结构风险最小化原则的应用，支持向量机具有非常好的推广能力( 泛 化能力) 。 4数学规划在数据挖掘和机器学习中的应用 数学规划( 最优化方法) 是应用数学中的一个重要分支，它包括多个方面 的内容，目前应用面最广的当属凸优化领域】。它起源于2 0 世纪4 0 年代，在五 六十年代有着迅猛的发展，到了7 0 年代其理论逐步完善，如求解无约束最优化 问题的变尺度法，求解约束问题的罚函数法等。在8 0 年代末到九十年代初，由于 实际工程应用的需要和计算机的迅猛发展，在求解大规模的优化问题方面有了 较为广泛的研究，研究方向朝着实用型方法转变，强调算法与实际应用相结合， 解决相应的实际工程问题。由于很多实际问题可以被描述成最优化问题，所以 在最优化问题求解引擎( s o l v e r ) 方面有着很大的市场需求，由此也产生了不少 优秀且相对成熟的软件 3 印用以求解线性和非线性规划等问题，而这也反过来 刺激了最优化理论和方法在工程中的更为广泛的应用。 最优化方法在机器学习领域的系统使用，至少要追溯到m a n g 蠲a r i a n 的开创 性努力似j 】。许多不同的作者独立提出基于l a g r a n g e 乘子理论的用于数据分类或 者其他任务的算法，现在这种方法已经是机器学习领域方法中不可或缺的一部 分。 支持向量机和其他一些机器学习方法( 如b o o s t i n g 等) 都是和最优化理论 紧密结合在一起的，很多机器学习和数据挖掘领域里面的问题( 分类、特征选 取、约束聚类等) 都可以最终表述成一个最优化闯题，然后借助最优化的理论 和算法得到较好的解决。支持向量机方法的建模、推导和最终的计算方法无不 渗透了数学规划的思想，没有最优化的对偶理论，也就不可能有核方法在模式 识别领域如此广泛的应用。 第二章最优化理论 2 1 数学规划问题的表述 数学规划( m a t h e m a t i c a lp r o g r a m m i n g ) ，简单地说，就是在某些约束条件下 求目标函数的最优值，其数学表达式为： r a i n ，( z ) s t g ( x ) 0 h ( x ) = 0 ( 2 1 ) ( 2 2 ) ( 2 3 ) 其中z 形，：形_ 兄1 ，g ：形_ 胛，h ：舻_ 尉。 如果，g 和h 都为线性函数，则称2 1 2 3 为线性规划问题；否则为非线性规 划问题。线性规划问题是最简单、也是应用最广泛的数学规划问题，其基本形 式可以表示为： m i n，z s t a $ o ( 2 4 ) ( 2 5 ) ( 2 6 ) ( 2 7 ) ( 2 8 ) 当目标函数，为二次函数，而g ，危为线性函数的时候，则称为二次规划问题， 二次规划问题可以表述为： 1 m i n f ( x ) = 妻霉r 月t + ，z ( 2 9 ) 二 s t a r x b ( 2 1 0 ) 若日是半正定矩阵，则称2 9 - 2 1 0 为凸二次规划问题。若日是正定对称阵， 则称2 9 - 2 1 0 为严格凸二次规划问题。对于一般情况，如果，( z ) ，吼( $ ) ( i = 6数学规划在数据挖掘和机器学习中的应用 1 ，2 ，m ) 都是凸函数，则称 r a i n f ( x ) s t 玑p ) 00 = 1 ，m ) 为凸规划问题。， ( 2 1 1 ) ( 2 1 2 ) 2 2约束最优化问题的最优性条件 定义2 1 对于约束曩优化问题2 1 2 & 记其可行域为 d = z l g c z ) o ，h ( x ) = o ) ， 若对于矿d ，存在e o 使得 - 3 x d 臣l l z z l ise r i c ，总有 f ( x ) f ( x + ) ， 则称矿为数学规划问题2 1 2 蹦局部解，或简称矿为最优解若当。d - g - o f ( x ) ， 则称矿为约束问题的严格局部最优解 定理2 1 ( g a r o a h 胁 m 她c k 绽理煅优化问题2 1 2 3 中，( z ) ，夕( z ) ，危( 茁) 具有 连续的一阶偏导数，若矿是该问题的局部最优解，则存在常数”和矿，使得： v 。l ( z ，a ，矿) = v f ( x + ) + v g ( x ) a + + v h ( x ) 矿= 0 ， ( 2 1 3 ) 9 ( 矿) 0 ( 2 1 4 ) h ( x ) = 0( 2 1 5 ) ”0( 2 1 6 ) a + 勺( z + ) = 0( 2 1 7 ) 其中1 i ，g ( z ) 。f p 。”，v h ( x ) r “。，工( z ，a ，卢) 为三哪，w e 函数 工( z ，a ，p ) = ，( z ) + a t g ( x ) + ， ( z ) 该定理为最优化问题2 1 2 3 局部最优解的一阶必要性条件。 定理2 2 设凸规划问题2 1 1 2 j 2 中，( z ) ，g ( z ) ， ( z ) 具有连续的一阶偏导数， 则矿是该问题全局最优解的充分盛要条件悬存在 和矿使得2 1 3 - 2 成立 第二章最优化理论 7 2 3 最优化问题的对偶理论 定义2 2 对于凸规划问题2 j j 2 j 幺称规划问题 m a xl ( z ，入) s t v ；l ( z ，a ) = 0 a 0 ( 2 1 8 ) ( 2 1 9 ) ( 2 2 0 ) 为该问题的骱j ，e 对偶问题，称2 j j 幺j 2 为原始问题其中l ( z ，a ) 为k 9 m 舶9 e 函 数，即 l ( x ，a ) = ，( z ) 4 - a t 9 ( 茁) 定理2 。3 c w o l f e 对偶定理煅矿是凸规划问题2 1 1 2 1 2 的最优解，且正则性 假定成立，则存在”，使得( ；：) 为对偶问题2 1 8 - 2 e o 的最优解，粕- f ( x + ) = l ( x + ，”) 定理2 4 傅对偶定理j 若y 是原始问题目标函数，( z ) 对于所有可行解z 的值的 下确解，而 是对偶问题的目标函数l ( z ，a ) 对于所有可行解g ) 的值的上确界， 则y 芝t ， 弱对偶定理告诉我们，如果原始问题无有界解，则对偶问题不可行；同样， 对偶问题无有界解，则原始问题不可行。 先考虑严格凸二次规划问题2 9 - 2 1 0 ( 日为正定) 的对偶问题 m 馘地a ) = 尹1 胁+ 如+ f ( z 一6 ) s , t v 。l ( z ，a ) = h x + c + a a = 0 a 0 ( 2 2 1 ) ( 2 2 2 ) ( 2 2 3 ) 由约束条件2 2 2 得到z = 一h _ 1 ( c + a a ) ，代入到目标函数2 2 1 d o 得到 三= 一j 1 妒a t i t 。1 a a 一( a t h - 1 _ c + 功飘一；朋以b 因此，对偶问题可写成 m i n ；f ( a r 胪a ) a + ( a t h - - 1 c + 6 ) ? a ( 2 2 4 ) s t a 0( 2 2 5 ) 8数学规恕l 在数据挖掘和机器学习中的应用 称2 2 4 - 2 2 5 为严格凸规划问题2 9 2 1 0 的对偶问题。 对偶问题2 2 4 2 2 5 只有非负约束，它的形式要t b 原始问题2 2 4 2 2 5 要简单， 因此根据w d l 硒c 于偶定理，我们可以通过求解对偶问题得到原始问题的最优解， 即为如下定理。 定理2 5 如果原始问题2 9 - 2 1 0 有可行解，则z + 是原始问题的最优解的充分必 要条件是：”是对偶问题2 彩一2 2 5 的最优解，且矿= 一日。( a a + + c ) ，且”即 是原始问题的如胛r w 辣子 第三章支持向量机的数学规划表示 3 1 线性分类 两类问题的分类通常用一个实值函数，：r n 一 - 1 ，+ 1 ，按照这样的方式 操作：当，( z ) o 时，输入z = ( x l ，) 赋予正类( + 1 ) ，否则赋予负类( - 1 ) 。 考虑当，( z ) ，z x 是线性函数的情况，函数通常可以写为： ，o ) = w i x t + 6 i = l = ( t o ，z ) + b 这里，b ) pxr 是控制函数的参数，( z ) 是输入空间中的一张超平面，而决 策规则l 自s g n ( f ( x ) ) 给出( 按照惯例s g n ( o ) = 1 ) 。 上述为一个线性分类器，线性函数最容易理解并且应用最简单。传统统计 学和经典神经网络文献已经阐述了许多利用线性函数区分两类事件的方法，以 及利用线性函数插值的方法。 这类分类器的几何解释为，式细，z ) + b = o 定义的超平面是维数为n 一1 的 仿射子空间，它将空间分成两个部分，这两个部分对应输入中的两类。 统计学家和神经网络的研究者经常使用这种称为线性判别平面或感知机的 简单分类器。线性判别平面的理论是f i s h e r 在1 9 3 6 年发展起来的，而神经网络的 研究者是在2 0 世纪6 哞代早期开始研究感知机的，主要的工作由r o s e n b l a t t 完 成。其中将脚和6 称为权重向量和偏置，这是从神经网络文献中拿来。 定义3 1 用x 表示输入空间，y 表示输入域通常x 酗，对于两类问 题，y = - 1 ，1 ) ；对于多类问题，y = 1 ，2 ，m ) ；对于回归问题，y r 。 训练集是训练样例的集合，训练样例也称为训练数据通常表示为：s = ( z 1 ，玑) ，( 锄，鼽) ，( xxy ) 2 其中，f 是样例数目z i 指样例，执是它们的标 记 我们先考虑两类问题，标示集合y = - 1 ，1 ) 。类另y 的值将训练集s 划分成 两个部分：a = 瓤k x ，y i = 1 ) ，8 = 甄陬x ，鼽= - 1 。我们试图用一个 1 0数学规划在数据挖掘和机器学习中的应用 线性分类器( 超平面 = ，y ) 在输入空间中分离a 和b ，其中w 是平面的法 向量，平面到原点的e u c l i d e 距离为拣。令集合a 中的m 个点的坐标由m n 阶 表示，集合召中的k 个点的坐标由七xn 阶矩阵b 表示，每一行代表一个样本。如 果存在t 瘌，y 使得：a w e , 7 和b w 一 啦 l = 啦 ；：l 甄啦 。筒 ，【 | iz 日 数学规划在数据挖掘和机器学习中的应用 2 c - m a r g i n 问题 对于线性可分离问题，我们从另个角度来构造超平面。构造两个平行 的超平面，使得同类样本点分别位于这两个平面的一边，两个超平面之间不 含样本点。直观地认为，尽量使这样的两个超平面之间的距离最大即为最优 的判别策略，然后取位于两平行超平面中问的平面做为分离超平面，这样的 方式是最为稳健的。假设这两个超平面分别为x t w = 和z t 铆= p ，样本集 合一4 中的任何点都满足x t w o t ，且有数据点使等号严格成立，即位于该平面 之上；样本集合b 中的任何点都满足z t 伽p ，且有数据点使等号严格成立则 两个支持超平面之间的距离为陋一j 臼) h w l l ，然后最大化距离的目标通过最小 化j j 叫j j 和一陋一卢) 来达到。这样最大化两个支持超平面之间距离的数学问题就 可以写成如下最优化问题： 珊；删2 一( a 一卢) s , g a 铆一a e 0 - b w + 口e 0 ( 3 4 ) ( 3 5 ) ( 3 6 ) 解该二次规划问题得到最优解为峦，- ，万，最优分离超平面位于两个支持超 平面的中间，即为： 一 砌= 字 3 g h 仰问题和g - m a r g i n f o - 题之间的关系 我们已经从两个不同的角度来对数据进行划分，g - m a r g i n 方法是求凸包之 间的最近距离，g - m a r g i n 方法是求两个支持超平面之间的最大距离。如何评价 这两种方法的优劣呢，它们之间是否存在着关系呢? 考虑c m a r g i n f 司题3 4 3 6 的l a g r a u g e 踩i 数： l ( 叫，a ，卢，u ，t ，) = 去i l 伽1 1 2 一( d 一卢) u r ( a w o r e ) 一矿( 一b w + 伽) ( 3 7 ) 由k k t 条件得到： v 。l = 一a t u + b t = 0 ( 3 8 ) 砜工= 一1 + e t , u = 0 ( 3 9 ) v a l = 1 一，口= 0( 3 1 0 ) 第三章 支持向量机的教学规划表示 其中“0 ，口20 是问题3 4 - 3 6 的l a g r a n g e 乘子。将3 8 - 3 1 0 代入3 7 ，消 去w ，q ，p 得到c - m a r g i n f 题3 垂3 6 的w o l f e 对偶问题： m a x i i a t u b 1 1 2 2 i a t u b r v i i u ，v 一一 2 s t e t u = 1 ，t 0 e t ? 3 = 1 ，移0 ( 3 1 1 ) ( 3 1 2 ) ( 3 1 3 ) 它完全等价于问题3 1 - 3 3 因此，c - m a r g i n f 习题的对偶是d h 讪闯题根据 数学规划的对偶理论，这两种方法是完全等价的，即得到如下定理。 定理3 2 c - m a r g i n 问题只4 一奠疗的骱驰对偶问题即为c - h u l l f * - i 题3 i s 3 。 4 问题的支持向量机表述 在c - m a r g i n f ：a 题3 4 - 3 6 中对参量 1 1 1 、n 、p 同时进行倍数变换是不影响问题的 最优解的，所以根据表述需要，我们令a 一卢= 2 ，又令，y = o t 一1 ，则有p = 7 1 ， 得到如下的分离问题： 扣| 2 a w 一( ，y + 1 ) e 0 一b + ( ，y 一1 ) e 0 令优化问题3 1 4 - 3 1 6 中的，y = 一b ，写成如下等价形式： m i l l ；i l w l l 2 8 t 帕+ 1 ， i f y i = 1 + 6 - 1 ，i f 执= - 1 上面的问题可改写成以下的二次规划问题： 曾扣2 s t 挑( + 6 ) 1( i = 1 ，哟 下面给出支持向量机的定义： ( 3 1 4 ) ( 3 1 5 ) ( 3 1 6 ) ( 3 1 7 ) ( 3 1 8 ) ( 3 1 9 ) ( 3 2 0 ) ( 3 2 1 ) 1 4数学规划在数据挖掘和机器学习中的应用 定义3 3 如果数据点使不等式约束3 2 1 式中的等号成立，则称相应的置为支持 f r ( s u p p o r tv e c t o r ) ，称对应的超平面 + 6 = + 1 和 + 6 = 一1 为 支持超平面用最大化支持超平面的距离来得到线性分类器的方法称为支持向 量机方法 规划3 2 0 - 3 2 1 的含义就是求解两个最大距离的支持超平面，等价于d m a r g i n 方法，所以从几何直观的认识上来看，该方法是稳健( r o b u s t ) 的，即对 任一个样本点稍微做一点改变，对样本分类判别的准确度的影响并不显著。 现考虑二次规划问题3 2 0 - 3 2 1 的最优性条件。问题3 2 0 - 3 2 1 的l a g r a n g e 函 数为： 上( 础，b ，8 ) = ；i f w l l 2 一啦( 弘( + 6 ) 一1 ) ( 3 2 2 ) “ i = 1 其中的啦( i = 1 ，n ) 为对应约束的l a g r a n g e 乘子，d j p 为这些乘子组 成的向量。 根据k k t 条件，得到如下的最优性条件： v 。l ( t j ，b ，a ) = 叫一a i y i x i 嘉跏6 ，加一妻啦瓠 执( l + 6 ) =0 =0 1 ，t = 1 ，n 0 ，i = 1 ，r 一，n 啦( 执( + 6 ) 一1 ) = 0 ，i 一1 ，n ( 3 2 3 ) ( 3 2 4 ) ( 3 2 5 ) ( 3 2 6 ) ( 3 2 7 ) 设- 5 ，西为规划问题3 2 0 - 3 2 1 的k k t 点，则当面 0 的时候，由式3 2 7 - 知， 式3 2 5 中的等式成立，即茁；位于支持超平面上，该数据点即为支持向量。 由式3 2 3 和式3 2 4 得到： w = y a i x i = 1 ( 3 2 8 ) ( 3 2 9 )啦 玑 。：l = 0 第三章支持向量机的数学规划表示 将式3 2 8 和3 2 9 代入到l a g r a i l g e 函数3 2 2 中，得到： 1 n l ( 叫，6 ，o ) = ； 一芝二啦队( + 6 ) 一1 1 ( 3 3 0 ) 一讧=l n 11 一、 2 2l 弘协 一 j ：l 鼽协口 + 啦 ( 3 3 1 ) 2 - 一鼽协口 + 2 _ 一啦 p 1 ) i j = l i = l 馆 一 竹 = 0 一百i 弘协啦 ( 3 3 2 ) i = i 。i j = 1 考虑规划问题3 ，2 0 - 3 2 1 的w 6 对偶，得到如下二次规划问题： 警阶) 2 ；旷；盖娜耶妒 s t 躺= 0 啦0t = 1 ，n ( 3 3 3 ) ( 3 3 4 ) ( 3 3 5 ) 有前面的推导可知，规划问题3 2 0 - 3 2 1 等价于c - m a r g i n f , 3 题3 4 - 3 6 ，而g m a r g i n f 可题的对偶问题是c - h u l l 问题3 1 3 3 ，所以二次规划问题3 3 3 - 3 3 5 本质 上是等价于c h u l l 问题3 1 3 3 的，前面已经给出了该问题的几何解释。 原规划问题3 2 0 - 3 2 1 中的b 的值一直没有出现在对偶问题中。根据最大间隔 的几何意义，显然有1 6 = n l i 耳( 坩，双) ，- i b + = m 旺( 伽，墨) ，所以我们得 到6 = 一 【亲璺( 舢。，以) + 器璺( ( 叫+ ，瓤) ) 】 根据k k t 互补条件，我们知道最优解中对直l a g r a n g e 乘子a ： o 的数据点 一定位于支持超平面上，其它所有的点对应的l 8 鲫l g e 乘子霹都为零。因此在 权重向量w 的表达式中，只有这些点包括在内，这也是它们被称为支持向量的原 因。 这样的优化超平面就可以在对偶表示中用参数子集来表示： ， ，o ，扩) = 弘西 + 矿 ( 3 3 6 ) i = l = ：挑n ： + 矿 ( 3 3 7 ) 1 6 数学规划在数据挖掘和机器学习中的应用 其中s v 表示支持向量的集合。 与每个点相关的l a g r a n g e 乘子成为对偶变量，并赋予了它们一个直观的解 释，而且定量给出了每个训练点在所得解中的重要性。不是支持向量的点没有 影响，在未退化的情况下，这些点的轻微扰动不影响解的准确性。 另外，由k k t 互补条件可以知道，对于j s v ，有： 由此得到： y j f ( x j ，0 l * ，6 ) = 协( 玑0 l 。* + 6 幸) = 1 ， i e s v n = 鼽珊西噶 i j = l = q ；协y ii j e s v i e s v = 哆( 1 - y j b ) j e s v = 叼 j e s v ( 3 3 8 ) ( 3 3 9 ) ( 3 4 0 ) ( 3 4 1 ) = 嵋 ( 3 4 2 ) j = l 因此，有以下结论成立： 定理3 3 考虑一个线性可分的训练样本集：5 = 扛1 ，玑) ，( ，) ) ，假定参 数d 是对偶优化问题只路只巧的最优解，则权重向量伽= w 霹如实现了几何 i = 1 间隔为：7 = 赤= ( o ：) - 1 7 2 的最大间隔超平面 3 1 2 线性不可分离情况 最大间隔分类器是一个重要的概念，是分析和构造更加复杂的支持向量机 的起点，但它在许多现实世界的问题中不能使用：如果数据有噪声，样本空闻一 般不能线性分开。最大间隔分类器的主要问题是，它总是完美地产生一个没有 训练误差的一致假设，这在线性不可分离的情况下是行不通的。如果我们在上 述相关规划的约束条件中加入相应的松弛变量，改成软间隔约束，就可以将最 大间隔分类器的思想推广到线性不可分离的情况。 第三章 支持向量机的数学规划表示 1 7 同线性可分离的情况一样，我们也从考查问题的直观几何意义入手，然后 借此推导出线性不可分离的支持向量机表述。 1 r d h u u 问题 我们在c - h u l l 问题中考虑了两类数据凸包之间的距离，但是常常也会遇到 两个凸包不可分离的情况，此时，两类数据集合的凸包的交是非空的，数据是线 性不可分离的。如采按照原来的思想来分离凸包是不可行的，幸运的是，大多数 情况下还是能够进行线性划分的，因为往往一类集合的绝大多数点并不在另 个集合的凸包中。如果能够限制一下边缘点的影响，还能回到用凸包来分析问 题的观点上来。依赖于像间隔这样的量使得系统易落入少数点所控制的危险境 况，而在真实数据中，噪声总是存在的，这会导致算法出现问题。所以我们希望 任何一个点对于问题求解的影响都不会很大，更准确地说，希望其最优解至少 基于数据集合中的k 个点，而不像线性可分的情况下那样，其最优解只由s v 集 合中的少数样本点决定( 如3 ，4 5 3 4 9 所示) 。这个目的可以通过称为简约凸包的 概念来完成。由限制凸组合中乘子的上界来构造简约凸包。 定义3 4 设s = ) 各1c 形为数据点集，d 1 为预先给定的常数，则称集合 nn r h ( s ) 垒 芝二啦翰i 芝二啦= 1 ，0 a i d ，t = 1 ，n 仁：1= 1 为s 的简约凸包 对于数据集合4 中点的简约凸包可以表示成： t i c = a t u ，e t t = 1 ，0 u d e ，d 1 ) ， 数据集合召中点的简约凸包可以写成： d l d = b t v ，e t v = l ，0 移d e ，d 1 ) ( 3 4 3 ) ( 3 。4 4 ) 如果d = 丢，1 k 0 为一个固定的常数，用于平衡惩罚项在目标函数中的作用力度。 类似于定理3 2 的证明，对于线性不可分离的情况，有如下定理成立： 定理3 4 r c - m a r g i n f l 题3 4 毋，5 嘲f ，e 对偶是r d 涧题，4 5 3 彳z 在问题3 5 1 3 5 4 中令1 = 一b ，将相应的惩罚项f ，叩统一记为 ，得到如下等 价形式的二次规划问题： m 毗i n 。扣1 2 + 嘻 s t 鼽( ( t ，z ) + b ) + 6 1 ，i = 1 ，n 矗20 ，i = 1 ，n ( 3 ，5 5 ) ( 3 5 6 ) ( 3 5 7 ) 有前面的论述可知，该问题与r c - m a r g i n f 习题3 4 8 3 5 0 是等价的。因此，问 题3 5 5 - 3 5 7 的几何意义是：求支持超平面的最大间隔，同时允许个别点不满足 约束条件，但破坏约束的点要予以惩罚。这里采用的是2 。模惩罚，其中c 是惩罚 系数，由于问题3 5 1 3 5 4 和r c - m a r g i n 问题之间有倍数变换，所以该规划中的g 与r d m a r 舀n 问题中的d 满足：c = i 茬= 号善 设锄，扩为二次规划问题3 5 5 - 3 5 7 的最优解，则相应的支持超平面为( + ，z ) + b = 1 和伽，z ) + b = 一1 。当数据点满足y , c ( w ，缸) + b ) o 的时候，则该数据点 被错误地划分为另一类。 3 支持向量机的表述 现在，我们来考查规划问题3 5 5 - 3 5 7 的最优性条件，该问题的l a g r a n g e 函数 为： 工( 加，6 ，f ，。，p ) ：；i i i ：+ c 妻6 一 1 一啦( 鼽( ( 叫，瓤) + 6 ) 一1 + 6 ) 一心矗( 3 5 s ) i = l 其中( a ，p ) 是相应的l a 留a n g e 乘子。根据k k t 条件，得到如下的最优性条 数学规划在数据挖掘和机器学习中的应用 v 。l ( w ，b ，口，p ) = t ，一啦弘z = 0 未洳 ，萨一啦挑= o 毫l ( 加，f ，口，p ) = g 一啦一胁= o ， 弘( + 6 ) + 6 1 ， a t ( 鼽( + 一1 + 6 ) = 0 ， 地靠= 0 ， 啦0 ，& 0 ，地0 ， ( 3 5 9 ) ( 3 6 0 ) ( 3 6 1 ) ( 3 6 2 ) ( 3 6 3 ) ( 3 6 4 ) ( 3 。6 5 ) 设，玩，o t ，p ) 是数学规划问题3 5 5 - 3 5 7 的最优解，即满足k k t 条件3 5 9 - 3 ，6 5 。 现就约束条件3 5 6 的l a 舒a n g e 乘子啦的最优值的取值进行分情况讨论： 1 当啦= o 时，由条件3 6 1 和3 6 4 知，斑= c 一啦= g 袁= 0 ，再由3 6 2 式碍 到玑( + 6 ) 1 ，即对应的数据点瓤有正确的分类。 2 当0 毗。弘锨= o 0 啦 c ，i = 1 ，n ( 3 6 6 ) ( 3 6 7 ) ( 3 6 8 ) n