（通信与信息系统专业论文）支持向量机的核方法及其多核聚类算法的研究.pdf

厂 支持向量机的核方法及其多核聚类算法的研究 学位论文完成日期： 指导教师签字： 答辩委员会成员签字： 擎雒 i ； 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含未获得 ( 逵! 翅逡直墓丝置噩缱别直盟的：奎拦豆窒2 或其他教育机构的学位或证书使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 学位论文作者签名：李新 签字日期：) 矿，口年f 月艿日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学技术信息 研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公 众提供信息服务。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：鹰彰 导师签字： 签字日期：加，口年厂月m 旧签字日期：2 口幻年r 月莎日 支持向量机的核方法及其多核聚类算法的研究 摘要 自1 9 9 5 年v a p n i k 等人提出了基于统计学习理论和核技巧的支持向量机算法 以来，基于核的机器学习方法( 即核方法) 取得了迅速的发展，目前已成为机器 学习和人工智能领域的研究热点之一，广泛应用于图像处理、生物信息技术、入 侵检测技术和文本分类等多个领域。进一步研究支持向量机，无论对核方法理论 的完善和发展，还是对核方法在应用领域的进一步拓展，都具有十分重要的意义。 核函数作为实现非线性映射的重要途径是支持向量机得到广泛应用和取得 良好效果的关键所在。本论文的目的就是研究多核函数的性质与构造。研究多核 的意义在于一方面可以扩展提高支持向量机的应用性，进而扩展模式分析、人工 智能和机器学习；另一方面核作为一门独立的学科，刚刚处于发展的初始阶段， 其潜力还远远没有得以完全发掘。 本论文主要创新工作是： 1 针对多数据源或异构数据集，采用单个核函数的效果不是太理想，提出了 鲁棒性更强的多核函数。根据不同的属性选择不同的核函数或者参数不同的核 函数，提高核的学习能力及泛化能力，并证明了新核的合法性； 2 将多核学习引入到模糊聚类分析中，提出了一种多核模糊聚类算法。通 过选取子核函数及其参数构造多核函数，使得输入空间的样本经多核函数映射 后，增大不同类别样本间的差别，提高了核函数的学习能力和泛化能力。克服了 全局核函数学习能力较弱和局部性核函数泛化能力较弱的问题，与单核聚类算法 相比较，提出的算法能更好地实现聚类。 3 支持向量聚类是一个无监督学习模型，聚类效果完全取决于所选取的核函 数。高斯核是支持向量聚类中常用的。但由于高斯核宽度的局限性，决定其核机 器泛化能力较弱，因而提出将泛化性能更好的加权多宽度高斯核引入支持向量聚 类算法，以期达到更好的聚类效果。 关键词：核方法，聚类，多核学习，高斯核，加权多宽度高斯核，支持向量聚类， 核函数，支持向量机 i l r e s e a r c ho fk e r n e lm e t h o d sf o rs u p p o r tv e c t o rm a c h i n e a n dm u l t i p l ek e r n e lc l u s t e r i n ga l g o r i t h m a b s t r a c t s i n c ev a p n i kp r o p o s e dt h es u p p o r tv e c t o rm a c h i n e ( s v m ) b a s e do ns t a t i s t i c a l l e a r n i n gt h e o r ya n dk e r n e lt r i c ki n 19 9 5 ，k e r n e lm e t h o db a s e dm a c h i n el e a r n i n g a l g o r i t h mh a sb e e nd e v e l o p e dr a p i d l y i tb e c o m e so n eo ft h eh o tp o i n t si na c a d e m i c r e s e a r c hn o wa n dh a sb e e nw i d e l yu s e di ni m a g ep r o c e s s i n g ，b i o l o g yi n f o r m a t i o n t e c h n o l o g y , i n t r i s i o nd e t e c t i o na n dt e x tc l a s s i f i c a t i o n ，e t c s oi ti so fg r e a ts i g n i f i c a n c e f o rb o t ht h ed e v e l o p m e n ta n di m p r o v e m e n to fk e m e lt h e o r ya n di t s e x p a n s i o no f a p p l i c a t i o n k e m e lf u n c t i o n ，a so n eo ft h em o s ti m p o r t a n tw a y so fn o n l i n e a rm a p p i n g ，i st h e e s s e n c eo fs u p p o av e c t o rm a c h i n e s 、析t l ls u c hw i d ea p p l i c a t i o n a ni n d e p e n d e n t d i s c i p l i n ec a l l e dk e r n e lm e t h o d sh a sb e e nf o r m e de s p e c i a l l yf o rk e r n e lf u n c t i o n s t h e p u r p o s eo ft h i st h e s i si st or e s e a r c ht h ep r o p e r t i e sa n dc o n s t r u c t i o no fm u l t i p l ek e r n e l f u n c t i o n s r e s e a r c ho fk e r n e lf u n c t i o n sd o e sn o to n l yi m p r o v et h eu s a g eo fs u p p o r t v e c t o rm a c h i n e s ，b u ta l s og i v e ss u p p o r tt oa r t i f i c i a l i n t e l l i g e n c ea n dm a c h i n e l e a r n i n gt h e m s e l v e s t h i sp a p e rh a sm a i n l yd i s c u s s e dt h ef o l l o w i n gp r o b l e m s ： ( 1 ) m u l t i p l ek e r n e l si sp r o p o s e dd u et ol e a r n i n gp r o b l e m si n v o l v em u l t i p l e a n dh e t e r o g e n e o u sd a t as o u r c e s c h o o s i n gd i f f e r e n tp a r a m e t e r so fd i f f e r e n tk e m e l f u n c t i o n so rk e r n e lf u n c t i o na c c o r d i n gt od i f f e r e n tp r o p e r t i e st oi m p r o v el e a r n i n g a b i l i t ya n dg e n e r a l i z a t i o no fk e r n e l ，a n dp r o v et h el e g i t i m a c yo f t h en e wk e r n e l ( 2 ) af u z z yc l u s t e r i n ga l g o r i t h mb a s e do nm u l t i p l ek e r n e l si sp r o p o s e dd u e t o l e a r n i n gp r o b l e m si n v o l v em u l t i p l ea n dh e t e r o g e n e o u sd a t as o u r c e s t h e m e t h o do v e r c o m e sl i m i t a t i o n so ft h ea l g o r i t h mb a s e do ns i n g l ek e r n e la n d i m p r o v e st h el e a r n i n ga n dg e n e r a l i z a t i o np e r f o r m a n c e b yu s i n gm u l t i p l ek e r n e l f u n c t i o n s ，t h eo r i g i n a ld a t ac a nb em a p p e di n t oah i g h d i m e n s i o n a lf e a t u r es p a c e i i i s ot h a tt h ei m p o r t a n tc h a r a c t e r i s t i c so fd a t aa r es h o w nc l e a r e r t h ec l u s t e r i n g e x p e r i m e n t ss h o wt h a tm u l t i p l ek e r n e l sf u z z yc l u s t e r i n ga l g o r i t h mc a nb e h a v e m o r ee f f e c t i v e l yt h a nt h a to fs i n g l ek e r n e l ( 3 ) s u p p o r tv e c t o rc l u s t e r i n gb e l o n g st ou n s u p e r v i s e dl e a m i gm a c h i n em o d e l s a n di t sr e s u l td e p e n d se n t i r e l yo nt h es e l e c t e dk e r n e lf u n c t i o n g a u s s i a nk e m e li s c o m m o n l yu s e di ns u p p o r tv e c t o rc l u s t e r i n g h o w e v e r ，t h el i m i t a t i o n so f t h eg a u s s i a n k e r n e lw i d t h d e t e r m i n e st h eg e n e r a l i z a t i o na b i l i t yo fk e r n e lm a c h i n e t h e r e f o r e p r o p o s es u p p o r t v e c t o rc l u s t e r i n ga l g o r i t h mb a s e do nw e i g h t e dg a u s s i a nk e r n e lw i t l l m u l t i p l ew i d t h s ，w h i c hc a na c h i e v eb e a e rc l u s t e r i n gr e s u l t s k e y w o r d s ：k e r n e lm e t h o d s ，c l u s t e r , m u l t i p l ek e r n e ll e a r n i n g ，g a u s s i a nk e r n e l w e i g h t e dg a u s s i a nk e r n e lw i t hm u l t i p l ew i d t ho v g k m w ) ，s u p p o r tv e c t o r c l u s t e r i n g ( s v c ) ，k e r n e lf u n c t i o n ，s u p p o r tv e c t o rm a c h i n e s ( s v m ) 目录 1 绪论。1 1 1 研究背景1 1 2 核方法研究进展2 1 3 核聚类研究进展5 1 4 本文研究的主要内容。6 2 核聚类理论基础8 2 1 聚类分析8 2 1 1 聚类分析的概念8 2 1 2 聚类相似度度量方法8 2 1 3 常用的几种聚类算法9 2 2 核方法1 1 2 2 1 核方法原理1 2 2 2 2 核方法应用分类1 3 2 3 支持向量机1 4 2 3 1 线性可分支持向量机。1 4 2 3 2 线性不可分支持向量机1 7 2 3 3 非线性支持向量机18 3 核函数2 0 3 1 核函数理论2 0 3 1 1 内积与半正定矩阵2 1 3 1 2m e r c e r 定理2 3 3 2 常用的核函数2 3 3 3 多核的构造2 4 3 3 1 多核的构造原则2 4 3 3 2 多核合法性的证明2 5 4 多核模糊聚类算法2 7 v 4 1 单核存在的问题2 7 4 2 多核函数2 8 4 3 多核模糊聚类算法过程2 9 4 4 仿真实验与分析3 1 4 5 结论3 3 改进支持向量聚类算法。3 4 5 1 核函数选取3 4 5 2 支持向量机训练和聚类标识3 5 5 3 模型选择3 8 5 4 实验分析_ 4 0 总结与展望4 6 6 1 全文总结4 6 6 2 研究展望4 6 考文献4 8 v i 支持向量机的核方法及其多核聚类算法的研究 1 绪论 1 。1 研究背景 随着计算机技术的迅猛发展以及网络的普及，人们有了更多的机会和便捷 的手段接触和获取到大量的信息。大量的信息给人们带来了方便，却也增加了从 中获取有用信息的难度。传统的数据库技术可以高效地实现数据的录入、查询、 统计等功能，但是无法发现数据中存在的关系和规则，无法根据现有的数据预测 未来的发展趋势，缺乏挖掘数据背后隐藏的知识的手段，因此导致了“数据爆炸 但知识贫乏 的现象。而人们又希望能够在对已有的大量数据分析的基础上进行 科学研究、商业决策或企业管理，为了解决传统分析方法的不足，并对大规模数 据进行分析处理，产生了一门新的技术一数据挖掘技术。数据挖掘( d a t am i n i n g ) 就是从大量的不完全的有噪声的模糊的随机的数据中提取和发现隐含在其中的 人们事先不知道的，但又是潜在有用的信息和知识的过程【。数据挖掘作为信息 管理领域中的一项重要技术，目前发展十分迅速。数据挖掘技术己在生物医学、 电信业、金融业、零售业等多个行业中被企业广泛应用于客户关系管理、市场趋 势预测等管理领域，为管理者进行决策提供了更有价值的信息依据。 聚类分析【2 j 是数据挖掘的一项重要功能，它是依据样本间关联的量度标准将 其自动分成几个群组，且使同一群组的样本相似，而属于不同群组的样本相异的 一组方法，一个聚类分析系统的输入是一组样本和一个度量两个样本间的相似度 ( 或相异度) 的标准【3 】。聚类分析的输出是数据集的几个各组( 类) ，这些组构成一 个分区或一个分区结构，同类中的样本比属于不同类的样本彼此具有更高的相似 性。聚类分析的一个附加的结果是对每个类的综合描述，这种结果对于更进一步 深入分析数据集的特性是尤其重要的。聚类方法尤其适合用来探讨样本间的相互 关联关系，从而对一个样本结构做一个初步的评价。人们能够对一维、二维或三 维的样本进行聚类分析，但是大多数现实问题涉及到更高维的聚类。对于人们来 说凭直觉解释高维空间包含的数据是非常困难的。聚类分析的应用非常广泛， 比较典型的应用有：模式识别；在地理信息系统( g i s ) q b ，通过聚类发现特征空 间来建立主题索引；空间数据分析( 检测并解释空间中的簇) ；经济学；图像处理； 支持向量机的核方法及其多核聚类算法的研究 文档分类；通过分析w e b 日志数据来发现相似的访问模式等等。 作为统计学的一个分支，聚类分析己有多年的历史，这些研究主要集中在基 于距离的聚类分析方面，诸如基于k - m e a n s 等聚类分析的方法。在机器学习中， 聚类分析属于一种无监督的学习方法，与监督学习不同，无监督学习不依靠事 先确定的数据类别，以及标有数据类别的学习训练样本集合。正因为如此，聚类 分析又是一种通过观察学习方法( 1 e a r n i n gb yo b s e r v a t i o n ) ，而不是示例学习 ( 1 e a r n i n gb ye x a m p l e ) 。在概念聚类方法中，仅当一组对象可以由一个概念所描述 时，这些对象才能构成一个类。这与基于几何距离表示相似程度并进行聚类的传 统聚类方法有所不同。概念聚类方法主要包括两部分内容：发现适当的类； 根据每个类形成相应的特征描述，这与在分类学习中的方法类似。聚类的过程完 全依赖于样本之间的特征差别。可想而知，由于缺乏输出，聚类问题难度比分类 问题更大。 基于核的机器学习方法或称核方法( k e r n e lm e t h o d ，k m ) 是以支持向量机为 核心算法的一类新的机器学习方法，是统计学习理论与核技术相结合的产物【4 - 5 。 它具有两个显著的特点【6 1 ：首先是在线性与非线性间架设起一座桥梁，其次是通 过巧妙地引入核函数，避免了维数灾难，也没有增加计算复杂度。目前，支持向 量机已成为核机器学习领域内重要的研究内容之一。对支持向量机的深入研究， 无论是对核方法的进一步发展，还是对其在数据处理中的实际应用，都有重要的 意义。目前聚类分析研究的热点集中在设计能够有效、高效地对大数据库进行聚 类分析的方法上。本文将围绕这一思想在以后的章节逐步介绍。本论文就是以支 持向量机为主线，对核方法展开研究工作的。 1 2 核方法研究进展 核理论的研究可以追溯到1 9 0 9 年，m e r c e r 在泛函分析中提出了再生核 ( m e r e e r 核) 和再生核希尔伯特空间。1 9 5 0 年，a r o n s z a j n 等人对其进行了进一 步完善7 1 。1 9 6 4 年，a i z e r m a n 等人将再生核技术用于学习理论的证明【8 1 。1 9 9 5 年，统计学习理论的创始人v a p n i k 等人利用“核技巧 ( k e r n e lt r i c k ) ，即通 过引入核函数代替内积，构建了一种新的核方法一支持向量机。该方法大大提高 了学习性能，掀起了机器学习领域的一场革命，进一步推动了核理论和核机器学 2 支持向量机的核方法及其多核聚类算法的研究 习研究的热潮【9 】。 此后，研究人员相继提出了许多不同的核方法以及针对支持向量机的改进算 法，使得核理论不断地完善，应用领域不断扩大。1 9 9 8 年，s c h o l k o p f 等人对线 性主成分分析( l i n e a rp r i n c i p a lc o m p o n e n ta n a l y s i s ，l p c a ) 方法进行核化，得到 了相应的核主成分分析( k e r n e lp r i n c i p a lc o m p o n e n ta n a l y s i s ，k p c a ) 方法【l o 】。核 典型相关分析( k e r n e lc a n o n i c a lc o r r e l a t i o na n a l y s i s ，k c c a ) 是由a k a h o 于2 0 0 1 年提出的方法，是模式识别中进行特征提取的重要技术【1 1 1 。为了更加有效地解决 处理结构数据问题，充分利用数据间的结构特征，研究人员构造了一种特殊的核 函数即结构化数据核函数，如使用邻域核识别纹理图象【1 2 1 ；使用字符串核和词 序列核进行文本分类【1 3 】；使用边界化核进行蛋白质分类等【1 4 】；j a a k k o l a 等人把 隐马尔可夫模型与根据背景知识所设计的核函数相结合，通过支持向量机，在部 分资料遗漏的情况下，仍可取得比较好的检测效果【1 5 】。另外，核方法通常采用 的是单核学习，即在学习过程中使用一个核函数。近年来，随着对核方法的深入 研究，针对多数据源或异构数据集问题，s o n n e n b u r g 等人提出了多核学习的概 念【1 6 - 1 7 1 。与单核学习相比，多核学习可以提高分类精度，鲁棒性更强。r a t s c h 等人则将多核学习用于生物序列数据的分类，取得了良好的效果【1 8 l 。 虽然支持向量机在一系列的应用中表现出非常优越的性能如支持向量机可 以降低分类面的复杂度，提高分类精度等。但是，支持向量机的研究仍处于初级 阶段，理论研究与实际应用方面都还有许多问题需要加以解决，概括起来主要有 以下几点： 1 核函数的研究 核函数的思想在现实世界中有着广泛的应用。任何一个涉及到点积运算的问 题，都可以通过引入核函数将问题映射到高维空间中去解决。 目前，核函数的研究工作主要集中在两个方面：一是研究已有核函数的参数 如何选取，即核参数选取的优化问题：二是根据实际应用问题提供的数据，构造 新的高效核函数。关于核参数的选择与核函数的构造等问题的研究虽然己经取得 了一些进展，但是仍不能令人满意1 1 9 之1 1 。核参数的选择是能否取得理想的预测结 果的重要因素之一，而目前核参数的选择大多数是靠人工估计，根据经验进行选 择，显然存在一定的随意性和局限性。如何构造与实际应用问题有关的核函数， 支持向量机的核方法及其多核聚类算法的研究 直是s v m 研究的重要课题。 另外，s v m 可直接处理向量数据，但是对于结构数据，如字符串、图像和蛋 质等无法直接输入，如何将结构化数据转换成向量，即构造结构化数据核函数， 后应用到支持向量机等核方法中，仍是一个函待解决的难题。因此，构造适合 结构化数据核函数，设计出高效的核方法也是研究的一个热点。 2 降低支持向量机的计算复杂度 支持向量机的应用受到限制的一个很重要的原因就是需要求解凸二次优化 问题，对于大规模样本的数据集，其计算具有较高的时间和空间复杂度。因此， 如何在不影响分类性能的前提下，降低计算复杂度，提高学习速度，建立高效的 求解支持向量机中的最优化问题算法，成了支持向量机一个很重要的研究方向。 3 增量学习的研究 当训练样本数据过大，无法一次性读入内存或在线学习情况下，训练开始时 无法得到所需要的全部数据时，可以采用支持向量机的增量学习算法 ( i n c r e m e n t a ll e a r n i n g ) 。将训练集分成几个独立的子集，依次在各个子集上作 增量学习，这样不仅可以舍去无用的样本，节省内存空间，缩短训练时间，而且 可以充分地利用以前的学习结果，使得学习结果具有延续性2 2 。2 3 1 。 目前，国内外研究支持向量机增量学习的方法大体上可以分为以下四大类， 即错误驱动法、固定划分法、过间隔法、错误驱动与过间隔结合的方法刚。 4 多核学习的研究 由于实际应用中经常出现的异类数据源，近年来研究人员提出了基于多核学 习( m u l t i p l ek e r n e l ) 的支持向量机以及实现算法。在现实世界中，往往存在大量 的数据是针对多数据源或异构数据集的，采用单个核函数的效果不是太理想。例 如，输入空间是两个向量组成的空间，第一个向量服从高斯分布，而第二个向量 却服从多项式分布。这时，如果仅仅采用一种核函数就显得不足，若用高斯核函 数则无法利用第二个向量进行有效划分，而如果采用多项式核函数则由于第一个 向量的存在会给分类造成影响。因此，如何进一步研究高效的多核学习的方法成 为研究核方法的热点之一。 多核学习有两层含义：一是可以一次针对不同的属性选择参数不同的核函 数，如根据不同的属性可以选择高斯核函数的不同宽度：二是针对不同的属性选 4 支持向量机的核方法及其多核聚类算法的研究 择不同种类的核函数，如根据不同的属性可以在学习过程中同时选择高斯核函数 和多项式核函数。使用多个核函数的组合，即使不知道最优参数，也可以通过调 整权值找到最合适的参数，显然使用多个核函数的组合要比单个核函数的鲁棒性 更强。 1 3 核聚类研究进展 近年来核方法被用在聚类分析中，t a x 将支持向量方法用于数据域描述( 即 一类分类) 中，提出了基于g a u s s 核的s v d d ( s u p p o r tv e c t o rd o m a i nd e s c r i p t i o n ) 算法【2 卯，b e n h e n 提出了一种新的无监督非参数型的聚类算法一支持向量聚类 ( s u p p o r tv e c t o rc l u s t e r i n g ，s v c ) 【2 6 1 。s v c 算法主要分为两个部分：基于支持向量 机训练和聚类标识，其中s v m 训练部分负责新知识模型的训练，包括g a u s s i a n 核宽度系数的优化、h i l b e r t 空间最小包络超球体半径的计算、l a g r a n g e 乘子的计 算以及有界支持向量( b o u n d e ds u p p o r tv e c t o r s ，b s v s ) 与支持向量的选取，再通 过d f s ( d e p t h f i r s ts e a r c h ) 算法根据关联矩阵进行聚类分配。 g i r o l a m 和焦李成等在结合核方法和聚类算法方面也做了开创性工作2 7 。2 剐。 目前已有的聚类算法只能对一些典型分布的样本奏效，比较经典的聚类方法有传 统的k m e a n s 方法、模糊c 均值聚类方法等，这些方法都没有对样本的特征进行 优化，而是直接利用样本的特征进行聚类。因此上述这些方法的有效性很大程度 上取决于样本的分布情况。例如一类样本散布较大，而另一类散布较小的情况， 这些方法效果就比较差：如果样木分布更加混乱，则聚类的结果就会面目全非。 文献 2 7 ，2 8 通过引入核方法把输入空间的数据非线性映射到高维特征空间，增 加了数据点的线性可分概率，即扩大数据类之间的差异，在高维特征空间达到线 性可聚的目的，从而提高聚类的质量。 近年来对核聚类的积极研究，涌现了许多基于核的聚类算法，诸如支持向量 聚类2 6 1 ，模糊核聚类算法【2 9 1 ，并将模糊核聚类算法例推广到分类属性的数据中。 而核聚类的研究为非线性数据的有效处理带来了突破口，也拓宽了本领域的研究 范围。 支持向量机的核方法及其多核聚类算法的研究 1 4 本文研究的主要内容 本论文主要研究多核函数、核函数的构造、和应用新的核函数进行聚类分析。 其中，多核函数，多核函数的构造，多核聚类算法，改进支持向量聚类算法是本 论文的核心创新内容。通过m a t l a b 支持向量聚类实验，并对实验进行分析，进 而获得对多核函数和多核聚类的有效论证。 本论文的主要工作是： 1 针对多数据源或异构数据集，采用单个核函数的效果不是太理想，提出了 鲁棒性更强的多核函数。根据不同的属性选择不同的核函数或者参数不同的核 函数，提高核的学习能力及泛化能力，并证明了新核的合法性； 2 将多核学习引入到模糊聚类分析中，提出了一种多核模糊聚类算法。通 过选取子核函数及其参数构造多核函数，使得输入空间的样本经多核函数映射 后，增大不同类别样本间的差别，提高了核函数的学习能力和泛化能力。克服了 全局核函数学习能力较弱和局部性核函数泛化能力较弱的问题，与单核聚类算法 相比较，提出的算法能更好地实现聚类。 3 支持向量聚类是一个无监督学习模型，聚类效果完全取决于所选取的核函 数。高斯核是支持向量聚类中常用的。但由于高斯核宽度的局限性，决定其核机 器泛化能力较弱，因而提出将泛化性能更好的加权多宽度高斯核引入支持向量聚 类算法，以期达到更好的聚类效果。 本论文内容安排如下： 第一章绪论。简要说明了本论文的课题背景，核方法与核聚类研究进展， 对其难点问题进行了分析，介绍了本文的研究内容，内容安排。 第二章核聚类理论基础。简单介绍了核方法的原理和常用核方法的分类， 聚类分析的理论基础和方法进行了归纳和总结。系统阐述了支持向量机的基本思 想和理论。 第三章核函数。核函数作为实现非线性映射的重要途径是支持向量机得到 广泛应用和取得良好效果的关键所在。本论文的目的就是研究多核函数的性质与 构造。根据不同的属性选择不同的核函数或者参数不同的核函数，提高核的学习 能力及泛化能力，并证明了新核的合法性； 第四章多核模糊聚类算法。针对多数据源或异构数据集的，采用单个核函 6 支持向量机的核方法及其多核聚类算法的研究 数的效果不是太理想。例如，输入空间是两个向量组成的空间，第一个向量服从 高斯分布，而第二个向量却服从多项式分布。这时，如果仅仅采用单一核函数就 显得不足，若用高斯核函数则无法利用第二个向量进行有效划分，而如果采用多 项式核函数则由于第一个向量的存在会给聚类造成影响。本章探讨了将多核学习 引入到聚类，通过选取子核函数及其参数构造多核函数，以期达到较好的聚类效 果 第五章改进支持向量聚类算法。本章探讨了基于加权多宽度高斯核的支持 向量聚类算法，主要分为两部分：基于支持向量机训练和聚类标识。其中s v m 训练部分负责新知识模型的训练，包括核宽度系数的优化、h i l b e r t 空间最小包络 超球体半径的计算、l a g r a n g e 乘子的计算以及新颖数据与支持向量的选取。聚类 标识部分首先生成聚类标识关联矩阵，再通过d f s 算法根据关联矩阵进行聚类 分配。 第六章总结与展望。对全文所作的工作进行概括性总结，展望了核方法的 发展趋势和今后的研究思路。 7 支持向量机的核方法及其多核聚类算法的研究 2 核聚类理论基础 2 1 聚类分析 聚类分析是数据挖掘中一种非常重要的技术和方法，是数据挖掘的主要任务 之一。聚类是把一组个体按照相似性划分成若干个类别，跟平常说的“物以类聚 相似。聚类分析就是使用聚类算法来发现有意义的类，主要依据是把相似的样本 划分为一类，而把差异大的样本区分开来，这样所生成的簇是一组数据对象的集 合，这些对象与同一簇中的对象彼此相似，而与其他簇的对象彼此相异。在应用 中经常把一个簇中的数据对象当成一个整体来对待。 2 1 1 聚类分析的概念 定义2 1 簇( c l u s t e r ) ：一个数据对象的集合。在同一簇中，对象具有相似性， 不同簇中，对象之间是相异的。 定义2 2 聚类分析( c l u s t e r i n ga n a l y s i s ) - 把一个给定的数据对象集合分成不 同的簇，即在空间x 中给定一个有限的取样点集或从数据库中取得有限个例子 的集合。聚类的目标是将数据聚集成类，使得类问的相似性最小，而类内的相似 性尽可能得大。 2 1 2 聚类相似度度量方法 数值的相似度测量方法大多直接或间接依赖于欧几里德距离。常见的基于欧 式距离的聚类算法有分割算法中的k - m e a n s 算法以及分层算法中的b i r c h 算法， c u r e 算法以及基于密度的d b s c a n 算法。首先我们给出几个基本概念： 定义2 3 度量空间：一个度量空间是指一个数据对象集x 和这个数据对多 集合上的距离函数d 构成的二元组( x d ) ，其中距离函数d 是二元函数，并且 满足以下条件： ( 1 ) 非负性：有0 d ( x ，y ) o ，两个单点相似性函数定义为 s i m ( x ，y ) = c ( c + d ( x ，即) ，它也称为相似度。显然它满足非负性：s i m ( x ，y ) 0 和对称性：s i m ( x ，y ) = s i m ( y ，x ) 【3 1 】。 对于p 维样本空间s 中的任意两个数据对象x ，y ，测量对象间的聚类目前常 采用的方法有： ( 1 ) 欧式距离： d ( i ，) = i 薯。一_ ，1 2 + i 薯：一_ ：1 2 + + f 一勃1 2 ( 2 1 ) ( 2 ) 曼哈坦距离： d ( i ，) = i 薯。一砀 + i x i ：- x j ：i + + 1 一勃 ( 2 2 ) ( 3 ) 明考斯基距离： d ( i ，) = ( k 一_ 。h 薯：一对+ + l x , - x j 1 9 ) ( 2 3 ) 其中江( t 。，薯：，) 和，= ( 。，t ：，勃) 是两个p 维的数据对象，q 是一 个正整数。欧氏距离是最常用的方法，曼哈坦距离是另一种常用的方法，而明考 斯基距离将两种距离统一到一种形式中。 有时为了突出一些数据的关键属性对聚类分析的重要作用，常采用加权形式 的距离，以避免某些属性的值过大而屏蔽其它取值较小的属性对数据相似性测量 的影响。 2 1 3 常用的几种聚类算法 为实现数据对象的聚类，人们提出了各种算法，其中最常用的算法有以下几 种： ( 1 ) k m e a n s 算法 k - m e a n s 算法是一种常用的传统聚类算法，首先由m a e q u e n 提出。其聚类思 想是将数据集分成若干子集，即给定一个例子的集合x ，其中包括刀个数据对 象，并要生成数目为k 的簇，需要满足如下的要求： 9 支持向量机的核方法及其多核聚类算法的研究 每个组至少包括一个对象； 每个对象必须属于且只属于一个组。 它以k 为参数，将n 个对象分成k 个簇，以使簇内具有较高的相似度，而簇 间相似度较低，其相似度的计算根据一个簇中对象的平均值来进行。此方法能有 效地处理簇内密集，簇间区别明显的数据的聚类，其时间复杂度为o ( n k t ) ( 其中 f 为迭代次数) ，因此有相对较高的可伸缩性和高效率。但它只能聚类数值型的数 据，并且要求用户事先必须确定参数k ，不适合发现非凸面形状的簇或大小差别 很大的簇，聚类结果与数据的输入顺序也有明显的关系，对于孤立点数据和“噪 声 也是很敏感的【3 2 】。 ( 2 ) 模糊聚类算法 传统的聚类把每个样本严格地划分到某一类，随着模糊集理论的提出，传统 聚类被推广为模糊聚类。在模糊聚类中，每个样本不再仅属于某一类，而是以一 定的隶属度属于每一类，换句话说，通过模糊聚类分析，得到了各样本属于各个 类别的不确定性程度，即建立起了样本对于类别的不确定性的描述，这样就更能 准确地反映现实世界。 基于目标函数的模糊聚类方法首先由r u s p i n i 提出【3 3 1 ，但是真正有效的f c m 算法却是由d u n n 给出的。b e z d e k 将其进一步扩展，建立起了模糊聚类理论 3 4 - 3 5 】。 从此该类模糊聚类蓬勃发展起来，目前已经形成了庞大的理论体系。f c m 算法 把数据集x 划分成为c 个模糊簇，并获得一个最优模糊划分矩阵u + ，该矩阵的 t r , 素u j 【0 ，1 表示模式矢量一隶属于第j 类的程度。f c m 算法可以描述为最小化 目标函数： j ( u ，y ) = n c 甜m 一_ 1 1 2 ( 2 - 4 ) 其中，v ，r p 是聚类中心或第f 类的模式原型，c 是事先确定的簇数，u 必 须满足以下约束： f 叶= 1 ，w j 3 1 ( 2 5 ) 0 y u 。 o 时，以是光滑的，而且当f 一0 时，以专， 因此聚类问题就转变成为使目标函数以最小化的优化问题。计算以关于q 的梯 度，可以得出最优化的条件【3 8 】： 其中 n p ( 薯，c ，) t q = 上l - 一 p ( t ，c ，) i = l ( 2 8 ) pc誓，c，2一k e x p ( 一忙一巳产) 式( 2 8 ) 给出的聚类中心是以指数函数值为系数的数据点的凸组合，它是 一种软聚类格式，并且当f 哼0 时，每一个q 均收敛于各自类的均值，f 值影响 算法的收敛速度，但对算法的精度影响不大。 2 2 核方法 核方法的基本原理、m e r c e r 定理、再生核理论等是研究核方法的基础，系 支持向量机的核方法及其多核聚类算法的研究 统地掌握这些知识对进一步认识和深入地研究核方法具有非常重要的意义。 2 2 i 核方法原理 假设已知某个学习算法是基于准则构造一个分类函数，且在构造过程中只涉 及到样本点之间的点积运算，那么我们就可以通过引入核函数，将样本从向量空 间映射到高维特征空间中，通过构造其相应的核方法来解决。任何核方法的解决 方案都由两部分组成：一个模块和一种学习算法【3 9 1 。模块执行的是映射到高维 特征空间的过程；而学习算法是用来发现该高维空间的线性模式。核方法的实质 就是把数据映射到一个可以发现线性关系的空间，而核就是核方法中的核心转换 模块。 图2 - 1 展示了利用核方法来进行模式分析的几个阶段。数据处理用核构造一 个核矩阵，然后利用模式分析算法( p a 算法) 处理核矩阵，然后得到一个模式 函数，再用这个函数去处理新的数据。从图中也可以看出，核函数是接触原始数 据的第一个环节，从根本上决定了模式函数的稳定性。 斗 a f ( x ) = e ai k ( x i , x ) l斗诊 k 数据核函数核矩阵p a 算法模式函数 图2 - 1 利用核方法进行模式分析的模块化过程 核方法的基本原理是：在非线性可分的情况下，使用一个非线性变换拭) 将输 入模式空间r 中的数据映射到高维特征空间f 中，即r 专，在f 中基于准则 构造新的分类函数，达到线性可分的目的。不必明确知道非线性变换的具体表达 式，只要用核函数k ( x ，y ) = c o ( x ) t p ( y ) 替代内积运算即可，如图2 2 所示。 1 2 支持向量机的核方法及其多核聚类算法的研究 图2 - 2 输入空间到特征空间的映射 通常情况下，变换函数缈( ) 比核函数k ( ) 更为复杂，也就是说简单的核函数 往往对应着“复杂 的映射。因此，核函数的引入可以大大降低非线性变换的计 算量。 根据核方法的基本原理可以看出，设计新的核方法有两个关键问题：一是核 函数，如何选择核函数、设计新的核函数以及相关参数的优化。二是采用何种学 习算法和改进学习算法。采用不同的学习算法可以构成不同的核方法，如将核函 数引入聚类方法可以构成核聚类方法。 2 2 2 核方法应用分类 从学习方式来看，常用的方法大体上可以分为有监督学习和无监督学习两大 类，学习的过程如图2 - 3 所示。有监督学习所处理训练样本的类别是事先己经标 号的，无监督学习所处理训练样本的类别则是未事先标号的。由于核方法的实质 就是将核函数引入到一些模式分类或回归方法中，因此可以将核方法也相应地分 为有监督学习和无监督学习。 无监督学习 有