（模式识别与智能系统专业论文）最小生成树平滑支持向量机聚类算法研究及其应用.pdf

摘要 支持向量机( s u p p o r tv e c t o rm a c h i n e s ，s v m ) 是在统计学习理论基础上发展 起来的一种新的模式识别方法，近年来在其理论研究和算法实现方面取得了突破 性进展。s v m 聚类方法是一种新的聚类算法，它利用核函数，通过映射把输入空 间的样本点映射到高维特征空间中进行处理。其方法在性能上比经典算法有较大 的改进，但传统s v m 算法随着数据集的增加其时间复杂度呈指数级增加，如何减 少该算法的时间复杂度从而应用于实际数据挖掘问题，正是现在研究的热点。本 f j 文针对支持向量机的聚类方法进行了研究，提出了最小生成树平滑支持向量机的 算法。本文所做的工作主要是： 首先，通过支持向量求解算法的分析，结合聚类的特性，提出了将平滑技术 引入聚类支持向量点求解的改进算法。该方法通过加入惩罚函数，将有约束的二 次优化问题转变为无约束的优化问题，从而利用传统方法进行求解，算法在有效 地保持求解支持向量精度的同时，大大提高算法的性能，节省了存储空间，使求 解过程的时间复杂度大为减少。实验验证了该算法能够进一步降低优化时间。 其次，对支持向量机聚类的标识方法和最小生成树聚类进行了研究，提出将 最小生成树应用于聚类标识的方法。该方法通过分析高维聚类数据分布特征改进 了距离表达方法，更加合理地体现了特征空间内点的相似程度，使各类样本之间 差别增大，增加了聚类的可靠性。此外，最小生成树的聚类标识大大减少了算法 的时间度，实验结果表明该算法与其它方法相比，过程更加简单，所用时间更少。 再次，将以上两种算法结合，提出了一种新的聚类算法m s t - s s v c ，通过实 验对算法参数做出了分析，与传统算法及支持向量机改进算法的比较表明该算法 大大简化了时间复杂度，同时精度基本不变，使得支持向量机聚类算法对实际大 数据集的处理成为可能。 。 最后，首次将该方法应用于社会养老保险个人调查数据的聚类分析中，取得 了一些有意义的结果，表明利用该算法应用于数据挖掘是可行的。 关键词：聚类；平滑支持向量机；最小生成树 。本文获国家社科基金项目“农村社会养老保障制度的基础框架研究”( 批准号：0 5 b s h 0 4 9 ) 支持。 a b s t r a c t s u p p o r tv e c t o rm a c h i n e s ( s v m ) i san e wm e t h o d o l o g yf o rp a t t e r nr e c o g n i t i o n ， w h i c hi sb a s e do ns t a t i s t i cl e a r n i n gt h e o r y r e c e n t l yi t st h e o r e t i c a lr e s e a r c ha n d a l g o r i t h mh a v eag r e a t e s td e v e l o p m e n t s u p p o r tv e c t o rc l u s t e r i n g ( s v c ) i san o v e l c l u s t e r i n gm e t h o d ，w h i c hm a p st h es a m p l e sf r o mi n p u ts p a c et oh i g hd i m e n s i o n f e a t u r es p a c ev i ak e r n e lf u n c t i o n s a l t h o u g hi t sp e r f o r m a n c eh a sb e e ni m p r o v e d c o m p a r e dw i t ho t h e ra l g o r i t h m s ，t h et i m ec o m p l e x i t yo fc o n v e n t i o n a ls v mi n c r e a s e s e x p o n e n t i a l l yw h i l et h ed a t a s e ti n c r e a s i n g s oi t i st h ef o c u do fr e s e a r c ht od e c r e a s e t h et i m ec o m p l e x i t ys oa st ou s ei ta sd a t am i n i n gt 0 0 1 t h i sp a p e rr e s e a r c h e st h e m e t h o d o l o g yo fs v c ，a n dp u t sf o r w a r dan o v e ls v c ：m i n i m u ms p a n n i n gt r e e s s m o o t h i n gs u p p o r tv e c t o rm a c h i n e t h em a i nw o r k so ft h i sp a p e r a r e ： f i r s t ，t h r o u g ha n a l y s i so ft h ea l g o r i t h mf o rs e a r c h i n gs u p p o r tv e c t o ra n dt h e f e a t u r eo fc l u s t e r i n g ，a ni m p r o v e da l g o r i t h mi s b r o u g h tf o r w a r dw h i c hc o n t a i n st h e s m o o t h i n gm e t h o df o rs e a r c h i n gs u p p o r tv e c t o r t h i sa l g o r i t h mc h a n g e st h er e s t r i c t e d q u a d r a t i co p t i m i z a t i o nt on o n r e s t r i c t e do p t i m i z a t i o ns ot h a ti t c a nb es o l v e db y c o n v e n t i o n a lm e t h o d s i tc o u l di m p r o v et h ep e r f o r m a n c eg r e a t l y ，s a v es t o r a g es p a c e a n dd e c r e a s et h et i m ec o m p l e x i t yw h i l et h ep r e c i s i o no fs u p p o r tv e c t o ri s k e p t e f f i c i e n t l y t h ee x p e r i m e n tp r o v e st h a tt h ea l g o r i t h mw o u l dr e d u c et h eo p t i m i z a t i o n t i m ef u r t h e r s e c o n d ，t h i sp a p e rr e s e a r c h e st h el a b e lm e t h o do fs v ca n dm i n i m u ms p a n n i n g t r e e s ( m s t ) c l u s t e r i n g ，p u t sf o r w a r dal a b e lm e t h o db a s e do nm s t i ta m e l i o r a t e st h e d i s t a n c ee x p r e s s i n gv i aa n a l y z i n gt h ed i s t r i b u t i o nf e a t u r eo fh i g hd i m e n s i o nd a t a t h e r e s e m b l a n c e sa m o n gp o i n t si nf e a t u r es p a c ea r ew e l ld e m o n s t r a t e ds ot h a tt h e d i s c r i m i n a t i o no fs a m p l e si sm a g n i f i e d ，a n dr e l i a b i l i t yo fc l u s t e r i n gc a na l s ob e a u g m e n t e d m o r e o v e r , t h i sa l g o r i t h md e c r e a s e st h et i m ec o m p l e x i t yg r e a t l y t h e e x p e r i m e n t sr e s u l t sd e m o n s t r a t et h a ti ti ss i m p l e ra n dn e e d sl e s st i m et h a no t h e r a l g o r i t h m s t h i r d ，c o m b i n i n gt h e s et w oa l g o r i t h m s ，w ep u tf o r w a r dan o v e lc l u s t e r i n g a l g o r i t h mc a l l e dm s t - s s v c i tr e d u c e st i m ec o m p l e x i t yg r e a t l ya n dk e e p sp r e c i s i o n v i aa n a l y z i n gi t sp a r a m e t e r s ，s ot h a ti ti sp o s s i b l et oc o p ew i t hh u g ed a t as e tu s i n g s v c f i n a l l y ，m s t - s s v ci su s e di nt h ec l u s t e r i n go fs o c i a lp e n s i o ni n s u r a n c es u r v e y d a t a ，a n dw ec a no b t a i ns o m er e a s o n a b l er e s u l t s k e y w o r d ：c l u s t e r i n g ；s m o o t hs u p p o r t v e c t o rm a c h i n e ；m i n i m u ms p a n n i n gt r e e s 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成 果。本人在论文写作中参考的其他个人或集体的研究成果，均在 文中以明确方式标明。本人依法享有和承担由此论文产生的权利 和责任。 声明人( 签名) ：耿氏 2 c b 7 年7 月3 日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦 门大学有权保留并向国家主管部门或其指定机构送交论文的纸 质版和电子版，有权将学位论文用于非赢利目的的少量复制并允 许论文进入学校图书馆被查阅，有权将学位论文的内容编入有关 数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密 的学位论文在解密后适用本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密沁) ( 请在以上相应括号内打“4 ) 作者签 导师签 日期：o o tg7 月s 日 日期：7 年7 月弓日 引言 引言 支持向量机( s u p p o r t v e c t o r m a c h i n e s ，s v m ) 【1 】是数据挖掘中的一项新技术， 是在统计学习理论基础上发展起来的一种新的模式识别方法，受到日益广泛的重 视。近年来在其理论研究和算法实现方面取得了突破性进展，开始成为机器学习 中一个独立的子领域，并对机器学习理论和技术的发展有重大的推动作用。支持 向量机与其它传统方法比较具有很强的学习能力和泛化能力，能够较好地解决小 样本、高维、非线性等问题，可以有效地进行分类、聚类、回归、密度估计等。 目前，支持向量机已经成功的应用于复杂数据挖掘、时间序列分析、文本自动分 类、生物基因识别等诸多方面。【2 1 s v m 聚类方法是一种新的聚类算法【3 】，它利用核函数，通过映射把输入空 间的样本点映射到高维特征空间中进行处理。其方法在性能上比经典算法有较大 的改进。灵活的非线性映射可以较好地分辨、提取和放大有用的特征，能处理任 意形状的聚类并且无须事先指定聚类数目，因此适合非线性复杂数据的探索性挖 掘。但传统s v m 聚类算法随着数据集的增加其时间复杂度呈指数级增加，如何 减少该算法的时间复杂度从而应用于实际数据挖掘问题，正是现在研究的热点。 传统s v m 聚类算法首先是搜索数据集中的支持向量点，即求解s v m 。标准 的求解过程需要求解费时的二次规划问题，其求解策略是采用迭代，迭代过程中 的每一步都涉及到核函数矩阵运算。当聚类数据集较大时，核函数矩阵运算占用 大量空间和时间，且迭代过程中的误差积累使得精度迅速下降，因此很难胜任海 量样本的数据挖掘问题。y u h j y el e e 等人【4 】提出了将平滑支持向量机( s m o o t h s u p p o r tv e c t o rm a c h i n es s v m ) 用于回归的算法( s s v r ) ，通过加入平滑函数，将 二次规划问题变为光滑无约束的最优化问题，实验证明利用s s v m 求解支持向 量点可以简化运算步骤，在求解精度不变的条件下大大节省运算时问和空间。本 文通过对平滑函数的研究将上述思想用于聚类算法中支持向量点的求解，提出了 平滑技术的求解算法，进一步提高支持向量机聚类算法的性能。 其次是特征空间聚类标识的选取。特征空间的超球体只能针对一个类分割， 最小生成树平滑支持向量机聚类算法研究及其应用 因此需要聚类标识。j a e w o o k l e e 等人【5 】运用邻近图( p r o x i m i t yg r a p h ) 法，减少了需 计算的连接边缘数目，取得了较好的效果，但该算法可能会丢失一些有用的连接 信息，因而导致错误的聚类结果，同时算法仅使用了输入数据空间e u c l i d e a n 距 离，对于性质不同的数据无法使各样本在特征空间内体现出较大的差别性，降低 了聚类的可靠性。本文在该算法的基础上提出特征空间内基于最小生成树的聚类 标识算法以提高计算的速度，减少聚类的错误率。 综合以上改进，论文提出了基于最小生成树的平滑支持向量机( m s t - s s v c ) 通过对标准数据库和一些经典问题的数据集的试验，结果表明，采用改进后的支 持向量机聚类算法训练时间短，学习效果好，在保持原有精度的前提下提高了对 大规模数据聚类的速度，是实现海量数据挖掘聚类的一种可行的方法。 本文的研究背景是国家社科基金项目的子课题全国农村社会养老保险 个人微观调查数据的分析挖掘。该项目对全国1 2 个省的农村居民进行问卷式调 查，旨在为探索建立有条件地方，有条件人群的农村社会养老保险提供可靠、详 实、科学的决策依据。项目开展两年来，积累了大量的个人调查数据，迫切需要 寻找一种数据自动识别挖掘的方法，对不同参保意愿下不同属性的人群做出探索 性聚类分析，由于问卷数据具有高维和非线性的特点，利用传统聚类方法如 k m e a n s 、层次聚类、s o m 、模糊聚类等无法取得较好的效果，满足实际需求。 本文首次尝试将m s t - s s v c 模型应用于该问题，得出了不同人群属性与参保意 愿的参考性结论，结果较为合理。 论文通过模型分析、改进和算法的具体实施，将支持向量机的聚类算法用于 数据挖掘，为支持向量机聚类算法的应用做出了有益的探索，实验过程以m a t l a b 和s q l 为开发工具，最终设计并实现了关于m s t - s s v c 的通用模块，并运用于 农村社会养老保险数据的聚类分析，其结果有一定的直观意义和合理性。 2 第一章绪论 1 1 数据挖掘技术 第一章绪论帚一早殖化 随着现代信息技术的发展，人们每天都要面对海量的数据。大量的数据在给 人们带来方便的同时也带来了一系列问题，对数据知识的贫乏造成正确运用数据 的困难，如何解决从海量数据中获取有价值的知识成了迫切需要解决的问题。 数据挖掘是多门学科和多种技术相结合的产物，也是一个非常年轻而又活跃 的研究领域，在各行各业的决策支持活动中扮演越来越重要的角色。数据挖掘的 目的，是把人工智能、机器学习、神经网络、统计学、模式识别与数据库等技术 结合起来，由计算机自动从已有海量数据中发现未知的、具有潜在应用价值的信 息或模式，使用这些模式和关系可以进行预测，寻找数据间潜在的关联因而数 据挖掘被认为是解决当今海量数据但知识贫乏矛盾的一种有效方法。 1 1 1 数据挖掘的概念 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随 机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用 的信息和知识的过程【6 】。与数据挖掘相近的同义词有数据融合、数据分析和决策 支持等。这个定义包括好几层含义：数据源必须是真实的、大量的、含噪声的； 发现的是用户感兴趣的知识；发现的知识要可接受、可理解、可运用；并不要求 发现放之四海皆准的知识，仅支持特定的发现问题。 数据挖掘中的知识是指概念、规则、模式、规律和约束等。而数据是形成知 识的源泉，好像从矿石中采矿或淘金一样。原始数据可以是结构化的，如关系数 据库中的数据；也可以是半结构化的，如文本、图形和图像数据；甚至是分布在 网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以 是演绎的，也可以是归纳的。发现的知识可以被用于信息管理，查询优化，决策 支持和过程控制等，还可以用于数据自身的维护。因此，数据挖掘是- i q 交叉学 3 最小生成树平滑支持向量机聚类算法研究及其应用 科，它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提 供决策支持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、 人工智能技术、数理统计、可视化技术、并行计算等方面的学者和工程技术人员， 投身到数据挖掘这一新兴的研究领域，形成新的技术热点。 本文通过对数据挖掘中的支持向量机聚类算法的研究，将该算法实际应用于 农村保险调查数据，得到了一些有意义的结论以供决策参考。 1 1 2 数据挖掘的分类 数据挖掘系统利用的技术越多，得出的结果的精确性就越高。原因很简单， 对于某一个技术不适应的问题，其它方法可能奏效，这主要取决于问题的类型以 及数据的类型和规模。 数据挖掘涉及的学科领域和方法很多，有多种分类方法，根据挖掘的任务主 要分为聚类分析、分类分析( 包括二分类和多分类问题) 、关联分析、偏差分析、 统计预测等，其中聚类分析是本文研究的重点。 1 聚类分析 聚类分析也称群分析或者点群分析，它是研究多要素事务分类问题的数量方 法。其基本原理是，根据样本自身的属性，用数学的方法按照某些相似性或差异 性指标，定量地确定样本之间的亲疏关系，并按这种亲疏关系程度对样本进行聚 类，聚类增强了人们对客观现实的认识，是概念描述和偏差分析的先决条件。 聚类也可以起到分类的作用，但它和大多数分类方法不同，大多数分类方法 都是演绎的，即人们事先确定某种事物分类的准则或各类别的标准，分类的过程 就是比较分类的要素与各类别标准，然后将各要素划归于各类别中。确定事物的 分类准则或各类别的标准或多或少带有主观的色彩。而聚类分析是归纳的，不需 要事先确定分类的准则，甚至连分成几类也不知道。它通过一些计算来把观测进 行合理的分类，使得同一类的观测比较接近，不同类的观测相差较多。 确定事物的聚类技术主要包括传统的模式识别方法和数学分类学。聚类以往 广泛使用的方法有k 均值，神经网络等，而今新兴起的支持向量机方法是 v a p n i k1 7 1 等人根据统计学习理论提出的一种新的机器学 - 3 方法，是数据挖掘领域 的一个重要分枝。 4 第章绪论 通常的聚类方法对于非线性分类问题的处理具有一定的局限性。而支持向量 机个重要的优点就是可以处理非线性聚类的情况，其从原始空间中抽取特征， 将原始空间中的样本映射为高维特征空间中的一个向量，以解决原始空间中非线 性问题【8 】o 对于支持向量机的具体理论和算法，将在第二章给出。 2 分类 分类是数据挖掘中的一个重要的目标和任务，目前的研究主要集中在应用 中。分类技术是一种有监督的学习，b p i j i l 练样本数据集中的每个数据都已经进行 了正确的类别标识，通过学习建立数据与类标识之间的对应知识，从而可以预测 未来数据的归类。分类的目的是通过学习获得学习模型( 称作分类器) ，该模型可 以把数据映射到给定的类别中的某一个类别。分类的一个主要作用就是预测，即 利用学习得到的分类模型能够对未来数据进行类别预测，结果是离散的类别值。 传统的分类器构造方法有统计方法、机器学习方法、神经网格方法等等。 3 关联规则 关联规则是数据挖掘中最活跃的研究方法之一，关联规则挖掘是寻找给定数 据集中项之间的联系，挖掘出的关联规则必须满足用户规定的最小支持度，它表 示了一组项目关联在一起需要满足的最低联系程度。关联规则挖掘最为著名的算 法是a g r a w a l 等提出的a p r i o r i 9 1 0 1 及其改进算法。 4 偏差分析 偏差分析也称为孤立点分析，可以在众多的数据、对象或模式中发现与多数 数据、对象或模式有显著差异的、异常的或不一致的数据、对象或模式，从数据 中检测这些偏差很有意义。偏差包括很多潜在的知识，如分类中的反常实例、不 满足规则的特例、观测结果与模型预测值的偏差、量值随时间的变化等。偏差检 测的基本方法是，寻找观测结果与参照值之间有意义的差别。其分析方法可以分 为三类，统计学方法，偏于距离的方法和基于偏移的方法。 5 概念描述 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。概 念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述 不同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中所有对象的 5 最小生成树平滑支持向量机聚类算法研究及其应用 共性。生成区别性描述的方法很多，如决策树方法、遗传算法等。 6 统计预测 统计预测是通过以往数据的分析，找到规律，来预计未来的趋势。常用方法 有时间序列，回归分析等。 1 2 聚类算法 1 2 1 聚类的概念 聚类作为数据挖掘技术的主要方法之一，是一种重要的数据分析技术，它搜 索并识别一个有限的种类集合或簇集合，从而描述数据。聚类分析与分类有所不 同，聚类的目标是在没有任何先验知识的前提下，根据数据的相似性将数据聚合 成不同的簇( 或类) ，使得相同簇中的元素尽可能相似，不同簇中的元素差别尽可 能大，因此又被称为非监督分类( u n s u p e r v i s e dc l a s s i f i c a t i o n ) 。其已经受到了越 来越多关注。原因在于： 1 在很多实际应用中，由于缺少形成模式类过程的知识，或者由于实际工 作中的困难，收集并标志大型样本集是很费时费力的工作，所以我们也往往只能 用没有类别标签的样本集进行工作。另一方面，存在很多应用，待分类模式的性 质会随着时间发生缓慢的变化。如果这种性质的变化能在无监督的情况下捕捉 到，分类器的性能就会大幅度提升。 2 在一个广义的数据挖掘过程中，聚类分析往往是被作为最初的步骤，用 于对数据分布和聚合特性的初步了解，以在此基础上进行其他数据挖掘操作。 聚类分析作为统计学的一个分支，已经被广泛研究了许多年。而且，聚类分 析也已经广泛地应用到诸多领域中，包括模式识别、数据分析、图像处理以及市 场研究【1 1 1 。通过聚类，人们能够识别密集的和稀疏的区域，因而发现全局的分布 模式，以及数据属性之间的有趣的相互关系。在商务上，聚类能帮助市场分析人 员从客户基本信息库中发现不同的客户群，并且用购买模式来刻画不同的客户群 的特征。在生物学上，聚类能用于推导植物和动物的分类，对基因进行分类，获 得对种群中固有结构的认识。聚类在地球观测数据库中相似地区的确定，汽车保 险单持有者的分组，及根据房屋的类型、价值和地理位置对一个城市中房屋的分 6 第一章绪论 组上也可以发挥作用。 聚类分析作为数据挖掘系统中的一个模块，既可以作为一个单独的工具以发 现数据库中数据分布的深层信息，也可以作为其他数据挖掘分析算法的一个预处 理步骤。 因此聚类分析已成为数据挖掘领域中的一个非常活跃的研究课题，虽然经过 几十年的发展，它已经较为成熟，但仍还有许多值得研究发展的地方。鉴于以上 的认识。本文对支持向量机的聚类算法进行了相关研究，并将该算法用于农村社 会养老保险数据调查的数据挖掘中，取得了较为合理的结果。 1 2 2 聚类算法的分类 许多聚类算法都是为特定的领域设计的，都有各自的特点和应用范围，因而 任何聚类算法都不可能在每个标准上都优越于其它算法。传统的聚类算法主要分 为基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法及基于 模型的方法。本节对这些算法进行了概述，对它们的性能在以下几个方面进行了 比较分析。 1 分层聚类算法 分层聚类算法通过建立系统树图进行分类，每个叶结点对应一个样本，每个 树结点对应某一种分类，聚类根据用户的要求在不同层次进行。分层聚类算法又 可分成凝聚算法( 自底向上) 和分裂算法( 自项向下) 。凝聚算法首先将每个样本 看成一个类，然后根据相应条件将其与最近邻样本融合为另一类，如此迭代进行， 直到所有的样本合并成为一个大类；分裂算法则与之相反，首先将所有的样本看 成为一个类，然后挑选距离较远的样本进行分裂，迭代进行直到所有的类仅包含 一个样本。这类算法的特点是：灵活性大，可在不同层次进行分类，但算法终止需 要预先设定一个终止条件，同时算法缺少鲁棒性，对噪音与边界数据比较敏感， 大多数的h c 算法的计算复杂度为o ( n 21 ，类数据必须以超球型进行分布。 2 分割聚类算法 分割聚类算法是应用最广的聚类算法，通常通过将数据样本划分为多个块， 然后再针对某种评价指标对块内数据进行调整，将不适合在某块内的数据归属到 其他块中。通过连续迭代完成聚类的过程。经典的算法有： 7 最小生成树平滑支持向量机聚类算法研究及其应用 ( 1 ) k 平均( k m e a n s ) 方法 该方法首先由m a c q u e e n 提出【1 2 1 ，在数据挖掘领域中得到了广泛的应用。在 k - m e a n s 方法中，每个类用该类中对象的平均值来表示( 故此得名) 。下面给出 了k m e a n s 过程的概述。 输入：聚类个数k ，以及包含n 个数据对象的数据库。 输出：满足方差最小标准的k 个聚类。 第一步：以n 个数据对象的任意k 个对象作为初始簇中心； 第二步：循环下述流程3 到4 ，直到每个聚类不再发生变化为止； 第三步：根据每个簇中对象的均值( 中心对象) ，计算每个对象与这些中心对 象的距离，并根据最小距离重新对相应对象进行划分； 第四步：重新计算每个( 有变化) 簇的均值。 这个算法尝试找出使平方误差函数值最小的k 个划分。当结果是密集的，而 簇与簇之间区别明显时，它的效果较好。对处理大数据集，该算法是相对可伸缩 的和高效率的，因为它的复杂度是o ( k n t ) ，其中，n 是所有对象的数目，k 是簇 的数目，t 是迭代的次数。通常地，k n ，且t o 3 7 时，这个界限肯定是松驰的。当v c 维无穷 大时，这个界限就不再成立。 为了构造适合于对小样本学习的归纳学习原理，可以通过控制学习机器的泛 化能力来达到此目的。对于o l ( z ，w ) b ，w e 人( 人为抽象参数集合) 二完全有 界非负函数，至少1 一r l 的概率满足以下不等式： 地限+ 昏乎 7 其中，对于无界函数集合，q ： - 3 机器的范化能力的界限是： 1 9 最小生成树平滑支持向量机聚类算法研究及其应用 郴端 a ( p ) = ( 2 8 ) ( 2 9 ) 其中，：2 1 n n - l n 7 7 z 运用以上的公式可以控制基于固定数目的经验样本之上的风险函数的最小 化的过程。控制最小化过程有几种方法：一是最小化经验风险，根据上面的公式 可以看出，风险的上界随着经验风险的值的减少而减少；二是最小化式( 2 5 ) 中右边的第二项，将样本的数目与v c 维作为控制变量。后者适合于样本数较小 的情况。 关于两类分类问题，s l t 指出：在有限训练数据下，学习机器的v c 维越大， 基于支持向量机的在经验风险最小的情况下，函数集的置信范围很大，导致真实 风险与经验风险之间可能的差别很大，学习机器的推广能力仍然很差。所以在机 器学习过程中，不但要使经验风险最小，同时也要使得v c 维尽量小，才能对未 来数据具有较好的推广性。s l t 提出一种策略，称为结构风险最小化( s t r u c t u r a l r i s km i n i m i z a t i o n ，s r m ) 准则( 如图2 1 ) 。 蘸聂予纂t 墨c 焉c 焉v c 维： f ； j s j 0 妒( 。) 一n 0 2 尺2 + 乞 岛o ( 2 1 2 ) ( 2 1 3 ) ( 2 1 4 ) 其中c 是惩罚系数。c 的值越大，越不允许超出球的噪声点的出现。 为了解决上述问题引入l a g r a n g e 乘式有： l 划一驰2 + 岛一i i ( _ ) 一口m 一乞”c 彭( 2 1 5 ) 其中屈 - 0 ，鸬o 为l a g r a n g e 乘子，c 是常数，c 毒为惩罚项 对拉格朗e t 函数中的a ，r ，孝分别求一阶偏倒数，并令其等于0 得到： 最小生成树平滑支持向量机聚类算法研究及其应用 磊o l = 2 尺一2 确= 。j 属= 1 詈= 屈( 吣) 一口) = o j a = 屈吣) 嚣一屈w c 一。j 层- c 一肛 ( 2 1 6 ) ( 2 1 7 ) ( 2 1 8 ) 由k t t 定理司知条件，最优解满足： 乞以= o( 2 1 9 ) ( r 2 + 酬( _ 一口) 1 1 2 ) 屏= 0f ( 2 2 0 ) 根据式( 2 1 6 ) 、( 2 1 7 ) 、( 2 1 8 ) 化简参数只剩下属，f 转化为对偶形式，有： m a x w = ( _ ) 2 局一屈屏m ( 玉) ( 勺) ( 2 2 1 ) ji 。j 满足下列条件： 屏= 1 ( 2 2 2 ) j 0 ，c j = 1 ，2 ，3 n ( 2 2 3 ) 定义满足m e r c e r 条件的核函数： k ( 再，_ ) = 西( 薯) ( _ ) 式中“”表示内积。常用的高斯核函数为： k ( 玉，_ ) = e x p ( 一日忱一五1 1 2 ) 则：w = zk ( x ，t ) 历一层层k ( ，x j ) i i j 根据( 2 2 2 ) 、( 2 2 3 ) 、( 2 2 5 ) 式( 2 2 1 ) 变为 ( 2 2 4 ) ( 2 2 5 ) ( 2 2 6 ) m a x w = 1 - z 层g k ( x i ，工，) ( 2 2 7 ) f ， 即m i n 7 = 层层k ( 五，_ ) i ，歹 s t ：o 尼c j = l ，2 ，3 n 从而解出屏。 对于每一个点，定义它到特征空间超球体球心的距离为 ( 2 2 8 ) ( 2 2 9 ) r 2 ( z ) = m x ) 一口0 2 ( 2 3 0 ) 将式( 2 2 4 ) 代入式( 2 2 7 ) r 2 ( x ) = k ( x ，x ) - 2 f l j k ( x i ，工) + 屈岛k ( 鼍，工j )( 2 3 1 ) jt ，j 分析一下k ，i t 条件的( 2 1 9 ) ( 2 2 0 ) 式可知，若一个样本点对应的松弛变量 专 o 和l a g r a n g e 乘子屈 o ，则表示它是落在特征空间中的超球的外面。由式 第二章支持向量机及其聚类算法 ( 2 1 9 ) 可知这样的点对应的，= o ，代入到( 2 1 8 ) 中，对应的层= c 。这种点 称为b o u n d e ds u p p o r tv e c t o r ( b s v ) 。当某个点对应的色满足o 岛 1 ，使各聚 类团包含一些位于边界曲线旁边的数据点，即聚类团表示为集合： x lr ( x ) 2 r ) ( 2 3 3 ) 2 3 3 特征空间类簇的标识 通过支持向量机只是得到了包含数据点的超球体和各个点在特征空间内到 超球球心的距离，还没有具体区分到底哪些点属于哪些簇，因此需要进行聚类标 识。 经典算法的聚类标识的思想基于如果两个输入点属于同一个簇，那么在高维 空间中，这两个点的连接线上的所有点都不会位于球外，文献2 9 1 中根据这个思想， 构造一个邻接矩阵a ： 冬= 三嚣僦徽蛐前黼掣鲰( 2 3 钔 要解析地分析条件r ( y ) r + 非常困难，实际中，如果在连接线上取1 0 - 2 0 个 采样点，只要他们都满足条件，即可认为r ( y ) r + 成立，然后找出由邻接矩阵a 表示的图中的连通部分( c o n n e c t e dc o m p o n e n t ) ，一个连通部分就表示一个聚类，对 于那些只有一个元素的连通部分，标记为噪声。 最小生成树平滑支持向量机聚类算法研究及其应用 2 3 4 聚类核函数的选取 在现实世界中，许多复杂问题超出了线性学习机器的能力。核函数3 0 1 给出了 一种解决途径，即将数据映射到高维特征空间来增加线性学习机器的能力。由上 述内容的讨论可知，在训练分类器的过程中，训练样本数据不会独立出现，而总 是成对样本数据的内积形式出现。这就使得通过核函数实现样本数据的内积运算 成为可能。 核函数是s v m 的一个重要的构成模块，实现了从线性可分的最优分类超平 面到非线性可分的支持向量机的关键。引入核函数，使得构造决策函数时，是在 输入空间进行，不需要作非线性变换向高维特征空间转化，计算复杂度没有增加， 避免了可能导致的维数灾难问题。核函数方法的一个重要特点是学习算法和理论 可以很大程度上同应用领域的特性分开，这种特性可以在设计核函数时加以考 虑，也就是在s v m 的应用中如何选择合适的核函数。但目前对于如何选择合适 的核函数，缺乏理论依据。目前常用的核函数主要有三种：多项式核函数、径向 基核函数( r a d i a lb a s ef u n c t i o n ，r b f ) 和s i g m o i d 核函数。 多项式核函数： t o ( x , ) = _ ) + 1 d ( 2 3 2 ) 。径向基函数： 足( x , x j ) _ e x p 卜学 ( 2 3 3 ) s i g m o i d 核函数： k ( 工，x j ) = t a n h ( v ( x x j ) + c ) ( 2 3 4 ) k e e r t h i 等人3 1 1 证明了线性核函数和多项式核函数是r b f 核函数的特殊情 况，这就是在缺乏足够先验知识进行选取核函数时更常选用r b f 核函数的原因。 t a x 和d u i n 在文献2 8 1 中指出多项式核函数不能严格服从一个类别边界面的情况， 因此在支持向量机聚类中选取了宽度参数为q ( q = ) 的r b f 核函数。 2 3 5 支持向量机聚类算法的分析 支持向量机算法是从全局的角度先获取所有可能聚簇的边界点再进行归类， 第二章支持向量机及其聚类算法 由于将数据集从输入空间映射至特征空间，因此s v c 聚类算法可以较好的解决 非线性复杂数据的聚类问题，这也是本文研究该算法的原因。在文献【3 l 】中还讨论 了在极端情况下( 即所有样本点都是孤立点时) 与基于p a r z e n 窗 3 1 1 概率密度估 计的聚类方法之间的关系。但从上述算法描述也可以看出s v c 的聚类算法的时 间复杂度是相当大的，其主要瓶颈集中在两方面：计算l a g r a n g e 乘子的二次型 问题和聚类标识的计算。前者可以采用一般的s v m 计算方法诸如 s m o ( s e q u e n t i a lo p t i m i z a t i o n ) ，但当数据集规模增大时s m o 算法的循环次数迅 速增加，计算速度下降。后者的原始算法需要检查所有数据项对的连接，时间复 杂性为o ( n 2 m 1 ，其中，l 为数据项数量，l 为常数，代表各边的采样点数目( 通 常介于l o 到2 0 之间) ，因此原始算法的实用性太差。 鉴于此，本文对原始算法作出改进，提出了基于邻接图的平滑支持向量机 ( m s t - s s v c ) ，该算法在计算l a g r a n g e 乘子的二次型问题时，将平滑函数引入 支持向量点的求解，使得原问题变为无约束的二次规划问题，可以利用传统的优 化法进行求解，大大简化了时间的复杂度，使用高维距离来代替输入空间的权重， 运用特征空间的最小生成树进行聚类标识，改进后的算法时间耗费大大减少，从 而使支持向量机的聚类算法可以处理大规模数据集。本文第三、四章将集中介绍 该算法的具体思路。 最小生成树平滑支持向量机聚类算法研究及其应用 第三章基于平滑技术聚类支持向量点的计算方法 支持向量机的求解等价于在线性约束条件下的一个凸二次规划问题。最小化 多变量的可微函数尤其是凸函数的问题已经过广泛的研究，多数标准方法都可以 直接应用到s v m 的求解中。但是，对于大规模样本数据集上训练s v m 时，标 准的求解方法遇到障碍。这是因为传统的二次规划优化算法进行矩阵的所有行和 列操作，对于支持向量机训练问题，矩阵的维数就是样本数据的个数。优化过程 要计算存储核函数矩阵，在样本数据较大时，势必需要很大的内存，这使得在处 理海量样本数据情况下，不可能将矩阵整个保存在内存中，增加了虚拟内存页替 换的频率。同时，s v m 的二次规划问题的寻优过程中矩阵运算占用了算法时间 的主要部分。因此，在大规模训练样本的情况下，s v m 的训练速度必然很慢， 阻碍了s v m 在许多问题中的应用。 近年来，针对这个问题提出了许多算法，这些算法主要两种：一种为分解策 略，即将原问题分解为一系列规模较小的子问题，通过循环解决子问题进而得到 原问题的解。根据分解策略、分解后子问题的大小以及子问题的求解策略的不同， 现有的分解策略算法可以分为三种块算法、分解算法以及序贯最小优化算 法。b o s e r 3 2 1 等人提出了块算法( c h u n k i n ga l g o r i t h m ) ，o s u n a 3 3 1 等人提出分解算法， 成为解决上述问题的一类有效方法。在分解算法的基础上，p l a t t 3 4 1 提出了序贯最 小优化算法( 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 ) 。另一种策略是把上述问题转 化为一个或一系列无约束最优化问题，如y u h j y el e e 3 5 1 等人提出s s v m 的概念， 通过惩罚因子和平滑函数的引入，使带约束的凸二次规划求解变为无约束问题， 可以使用一般的n e w t o n 法或其改进算法进行求解。和第一种策略相比，该方法 在降低计算复杂性上有较强的优势，适合大规模数据的