（应用数学专业论文）支持向量机与k均值聚类融合算法研究.pdf

摘要 内容摘要：本文在介绍了支持向量机和k 一均值聚类算法的基本理论 的基础上，对支持向量机和k 均值聚类算法的融合算法进行了研 究，详细介绍了改进算法的理论知识，并通过实验验证了算法的有 效性。 支持向量机是在统计学习理论基础上发展出来的一种新的、非 常有效的机器学习方法，它集优化、核、最佳推广能力等特点于一 身，较好地解决了以往困扰很多学习方法的小样本、非线性、过学 习、高维数、局部极小点等实际问题。尽管支持向量机有着其它机 器学习方法无法比拟的优势，但也有其自身局限性。针对其对噪声 和野点敏感的问题，我们提出了基于模糊隶属度的支持向量机去噪 方法，在线性规划下的一类分类支持向量机中引入模糊隶属度，剔 除样本中的噪声和野点，并在多种数据集上验证了算法的有效性。 k 一均值算法是解决聚类问题的一种简洁、快速的经典算法。如 果样本是密集的，并且类与类之间是线性可分的，它的效果最好： 但是如果类与类之间是线性不可分的，它的聚类效果就很不理想。 针对这个问题，我们提出了基于支持向量机的k 一均值聚类算法， 将一类分类支持向量机引入k 一均值聚类算法之中。文中在人工数 据集( d e l t as e t ) 和u c i 数据集( i r i sd a t a ) 上分别进行了实验，实验证 明，此算法与其它算法相比，聚类精度明显提高。而且线性规划下 的支持向量机比引用二次规划下的支持向量机，不仅提高了聚类精 度，而且极大的降低了算法的复杂性。 关键词：支持向量机；一类分类；线性规划；隶属度；k 均值 i a b s t r a c t c o n t e n t ：i nt h i sp a p e r ，w er e s e a r c hf u s i o na l g o r i t h m so fs u p p o r tv e c - t o rm a c h i n ea n dk m e a n sc l u s t e r i n ga l g o r i t h m ，o nt h eb a s i so ft h e f o u n d a t i o n a lt h e o r i e so fs u p p o r tv e c t o rm a c h i n ea n dk - m e a n sc l u s - t e r i n ga l g o r i t h m ，i n t r o d u c et h et h e o r e t i c a lk n o w l e d g eo fi m p r o v i n g a l g o r i t h m sc a r e f u l l y , a n dv e r i f yt h ee f f e c t i v e n e s so ft h ea l g o r i t h m sb y e x p e r i m e n t s u p p o r tv e c t o rm a c h i n e ( s v m ) i san e wa n dv e r ye f f e c t i v em e t h o d o fm a c h i n el e a r n i n gd e v e l o p e do ns t a t i s t i c a ll e a r n i n gt h e o r y , w h i c h c o n c l u d e so p t i m i z a t i o n ，k e r n e la n dt h ea b i l i t yo ft h eb e s tp r o m o t i n g a n ds oo n i ts o l v e sm a n yp r a c t i c a lp r o b l e m sw h i c ht r o u b l e dm a n y l e a r n i n gm e t h o d si nt h ep a s t ，s u c h 嬲s m a l ls a m p l e ，n o n - l i n e a r ，o v e r - s t u d y , h i g h - d i m e n s i o na n dl o c a lm i n i m u mp o i n t c o m p a r e dw i t ht h e o t h e rm a c h i n el e a r n i n gm e t h o d s ，t h es u p p o r tv e c t o rm a c h i n eh a si n - c o m p a r a b l ea d v a n t a g e si nm a n ya s p e c t s ，b u ti ta l s oh a si t so w nl i m - i t a t i o u s f o rt h es e n s i t i v ep r o b l e mt on o i s e sa n do u t l i e r s ，w eh a v e p r o p o s e daa p p r o a c ho fr e m o v i n gn o i s e sa n do u t l i e r sf o rs v mb a s e d o nf u z z ym e m b e r s h i pw h i c ha d d sf u z z ym e m b e r s h i pi no n e - c l a s ss v m u n d e rl i n e a rp r o g r a m m i n g ，a n dv e r i f yt h ee f f e c t i v e n e s so ft h ea l g o r i t h m i na v a r i e t yo fd a t as e t s k m e a n sc l u s t e r i n ga l g o r i t h mi sas i m p l e ，f a s ta n dc l a s s i c a la l g o - r i t h mt os o l v et h ep r o b l e mo fc l u s t e r i n g i ft h es a m p l e sa r ei n t e n s i v e 支持向量机与k 均值聚类融合算法研究 a n dl i n e a ra m o n gt h ec a t e g o r i e s ，i ti st h eb e s tm e t h o d ，b u ti ft h e ya r e n o n - l i n e a r ，t h ec l u s t e r i n ge f f e c ti s n tp e r f e c t a g m n s tt h i sp r o b l e m ， w eh a v ep r o p o s e dk m e a n sc l u s t e r i n ga l g o r i t h mb a s e do ns v m ，w h i c h a d d so n c l a s ss v mi nk m e a n sc l u s t e r i n ga l g o r i t h m i nt h i sp a p e r w e c o n d u c t se x p e r i m e n t sr e s p e c t i v e l yo nas y n t h e t i cd a t as e t ( d e l t as e t ) a n dau c id a t as e t ( i r i sd a t a ) ，t h e yp r o v et h a ti t sc l u s t e r i n ga c c u r a c y i m p r o v e do b v i o u s l yc o m p a r e dw i t ho t h e ra l g o r i t h m s c o m p a r e dw i t h s v mu n d e rq u a d r a t i cp r o g r a m m i n g ，s v mu n d e rl i n e a rp r o g r a m m i n g d o e s n to n l yi m p r o v et h ea c c u r a c yo fc l u s t e r i n g ，b u ta l s or e d u c et h e c o m p l e x i t yo ft h ea l g o r i t h mg r e a t l y k e yw o r d s ：s v m ；o n e - c l a s s ；l i n e a rp r o g r a m m i n g ；m e m b e m h i p ；k - 1 1 1 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果论文中除特别 加以标注和致谢的地方外，不包含其他人和其他机构已经撰写或发表过的研究成果，其他同 志的研究成果对本人的启示和所提供的帮助，均已在论文中做出了明确的声明并表示谢意 学位论文作者签名： e t 期：锣口9 嗽o 学位论文版权使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有权 保留并向国家有关部门或机构送交复印件和磁盘，允许论文被查阅和借阅本人授权辽宁师 范大学，可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或其他复制手段保存、汇编学位论文保密的论文在解密后使用本授权书 学位论文作者签名：张 指导教师签名：乏川气屉 日 期：枷p 纵。 支持向量机与k 一均值聚类融合算法研究 支持向量机与k 一均值聚类融合算法研究 1 绪论 1 1论文研究的背景及意义 由于数据库技术引发了海量数据，人们想用数据管理系统存储数据，用 机器学习的方法分析数据、挖掘海量数据背后的知识，由此数据挖掘( d a t a m i n i n g ) 产生了。概括的讲数据挖掘的任务是从大型数据库或数据仓库中提取人 们感兴趣的、事先未知的、有用的或潜在有用的信息1 1 1 。 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 1 1 是数据挖掘中的一项新技 术，是借助于最优化方法解决机器学习问题的新工具。它最初于2 0 世纪9 0 年代 中期由v a p n i k 提出，近年来在其理论研究和算法实现方面都取得了突破性进 展，开始成为克服“维数灾难”和“过学习”等传统困难的有力手段。其理论 基础是专门研究小样本情况下机器学习规律的统计学习理论1 2 ，3 】。该理论采用结 构风险最小化原则，在最小化样本点误差的同时，缩小模型复杂度，即减小模 型泛化误差的上界，从而提高模型的泛化能力。 支持向量机使用最大间隔因子来控制学习机器的训练过程，使其只选择 具有最大分类间隔的分类超平面，又叫最优超平面f 在不可分情况下，又引入 松弛因子来控制经验风险) ，从而使其在满足分类要求的情况下，又具有最高 的推广能力。寻找最优超平面的过程最终转化为二次型优化问题( q u a d r a t i c p r o g r a m m i n g ，q p ) ，从理论上说，得到的是全局最优解。在处理非线性分类 问题上，与传统的学习机器不同的是支持向量机是将输入空间映射到高维的特 征空间，仍然使用大间隔因子在高维特征空间中寻找最大间隔超平面。事实 上，高维特征空间中的超平面对应着输入空间中的非线性分类面。实际中，支 持向量机的优化过程并没有真正在高维特征空间中进行，而是通过一些具有特 殊性质的核函数【4 - - 1 0 ，将高维特征空间中的内积运算转化为原始空间中核函数 的运算，从而巧妙地避免了在高维特征空间中处理问题的困难。为了进一步降 低算法的复杂性，一些基于线性规划的支持向量机算法被提出，实验表明线性 规划支持向量机在保持较好的推广能力的前提下，算法复杂度大大降低。 尽管支持向量机在很多方面都有着其它机器学习方法无法比拟的优势，但 任何方法都不是万能的，它也有着自身的局限性。针对传统支持向量机对于噪 支持向量机与k 均值聚类融合算法研究 声和野点敏感的问题，本文对传统支持向量机进行了改进，引入模糊隶属度， 剔除样本中存在的噪声或野值样本，而且，在确定样本的隶属度时，不仅要考 虑样本所在类中心之问的距离，还考虑了类中样本之问的紧密度。 聚类是数据挖掘中的一种重要技术，是分析数据并从中发现有用信息的一 种有效手段。基于“物以类聚”的朴素思想，它将数据对象分组成为若干个类 或簇，使得在同一个类中的对象之间具有较高的相似度，而不同类中的对象差 别很大，通过聚类，人们能够识别密集和稀疏的区域，发现全局的分布模式以 及数据属性之间有趣的相互关系。聚类分析在客户分类、基因识别、w 、唧文 本分类、空间数据处理、卫星照片分析、医疗图象自动检测等领域有着广泛的 应用，而其本身的研究也是一个蓬勃发展的领域，数据挖掘、统计学、机器学 习、空间数据库技术、生物学和市场学的发展推动着聚类分析研究的进展，使 它己成为数据挖掘研究中的一个非常活跃的研究课题。与其它数据挖掘方法不 同，在进行聚类分析前用户一般并不知道数据集的特征。因此，从某种角度 看，聚类分析是一种无监督的学习过程，是基于观察的学习而不是基于实例的 学习。作为统计的一个分支，聚类分析己经被广泛地研究了许多年，主要集中 在基于距离的聚类分析。基于k 一均值，k 一中心点和其它一些方法的聚类分析工 具己经被加入到许多统计分析软件包或系统中，如s p l u s ，s p s s ，以及s a s 。 k - 均值属于聚类分析中一种基本的划分方法，常采用误差平方和准则函数 作为聚类准则。主要优点是算法简单、快速而且能有效地处理大数据集。然而 这种算法依赖于初始值的选择以及数据的输入顺序。此外，由于运用误差平方 和准则函数测度聚类效果，如果各类的形状和大小差别很大，则不能达到一个 好的聚类效果。 因此，本文针对k 一均值聚类算法中存在的问题也进行了改进，其中结合了 支持向量机一类分类算法，提高了算法的泛化能力，并采用线性规划算法，不 仅聚类精度有所提高，而且极大的降低了算法的复杂性，并具有一定的实际应 用价值。 1 2 本文的研究内容及组织结构 1 2 1 研究内容 本文阐述了数据挖掘中支持向量机和k 一均值聚类算法的主要理论。在此基 础上，着重对支持向量机和k 一均值算法进行了改进，对两种算法的融合算法进 2 支持向量机与k 均值聚类融合算法研究 行了研究。 针对支持向量机对噪声和野点敏感的问题，我们提出了基于模糊隶属度的 支持向量机去噪方法，在线性规划下的一类分类支持向量机中引入模糊隶属度 剔除噪声和野点，并在多种数据集上进行实验，通过实验验证了算法的有效 性。 在传统的k 均值聚类方法中，引入了线性规划下的支持向量机，提出了一 个改进的k 一均值聚类算法，即基于支持向量机的k 一均值聚类算法。应用基于 支持向量机的k 均值聚类算法分别在人工数据集( d e l t as e t ) 和u c i 数据集( i r i s d a t a ) 上进行实验，结果表明此算法对线性不可分的数据聚类精度更高，泛化能 力强，且节省了大量的时间。 1 2 2 组织结构 本论文共分四章，具体组织结构如下： 第一章是绪论，介绍了本论文研究的背景及意义。第二章详细介绍了支持 向量机算法的基础理论，由二次规划下的一类分类支持向量机算法推导出了线 性规划下的一类分类支持向量机算法，并且提出了基于模糊隶属度的支持向量 机去噪方法，介绍了算法的主要理论、实现步骤以及通过实验验证了算法的可 行性和有效性。第三章主要介绍了聚类方法中的k - 均值聚类算法的基础理论， 阐述了k 一均值方法的优缺点，并且针对k 一均值中存在的问题，阐述了现存的各 种解决方法。在此基础上，提出了一种基于支持向量机的k 一均值聚类方法，其 中介绍了这种算法的主要思想和实现步骤，并通过实验证明了算法的有效性。 第四章是对全文的总结与展望。 3 支持向量机与k 一均值聚类融合算法研究 2 支持向量机理论 2 1基于二次规划的支持向量机分类 支持向量机【i i 】是统计学习理论中最实用的部分，其核心思想是将结构风险 最小化原则引入其中。 支持向量机是从线性可分情况下的最优分类超平面发展而来的，其本质是 在训练样本中找出构造最优分类超平面的支持向量。在数学上归结为一个求解 具有不等式约束条件的二次规划问题。 假定训练样本集( 玩，玑) ，i = 1 ，z ，由二类组成，如果奶形属于第一 类，则标记为正慨= 1 ) ；如果x i 舻属于第二类，则标记为负( 玑= 一1 ) 。学 习的目标是构造一个决策函数，将测试数据尽可能正确的分类。针对训练样本 集为线性或非线性两种情况进行讨论。 2 1 1 线性可分 如果存在分类超平面 z ) + b = 0( 2 1 ) 使得： ( 鼢) + b 1 ，y i = 1 ( u 甄) + b 一1 ，y i = 一1 ，i = 1 ，2 ，j( 2 2 ) 则称训练集是线性可分的，其中z ) 表示向量u 形与z 形的内积。上述 两式中的z 舻，b 形都进行了规范化，使每类样本集中与分类超平面距离 最近的数据点满足( 2 2 ) 的等式要求。对于式( 2 2 ) ，可写成如下形式 犰( ( u 黾) + b ) 1 ，i = 1 ，2 ，z( 2 3 ) 由统计学习理论知，如果训练样本集没有被超平面错误分开，并且距离超 平面最近的样本数据与超平面之间的距离最大，则该超平面为最优超平面，由 此得到的决策函数 ，( z ) = s 夕礼( ( c d z ) + b )( 2 4 ) 4 支持向量机与k 一均值聚类融合算法研究 其推广能力最优，其中s 妒( ) 为符号函数。最优超平面的求解需要最大化南， 即最小化 i iu1 1 2 。归结为如下的二次规划问题 m i n 扣u1 1 2 约束为 鼽( ( u 也) + b ) 1 ，i = 1 ，2 ，l 我们采用l a g r a n g e 优化方法。为此必须找到l a 口a n g e 函数 三( u ，6 ，口) = 钏u1 1 2 一q t ( 弘( ( “，饿) + 6 ) 一1 ) 的鞍点。式中q t 0 为l a g r a n g e 乘子。 函数( 2 7 ) 式中的最小值必须满足条件 掣：u 一壹姚戤o钆 一芦。一。“ 。 丁o l ( w , b , a ) = 壹舭= oa u白挪1 。 将式( 2 8 ) 代入式( 2 7 ) 并考虑式( 2 9 ) ，我们得到 ( 2 5 ) ( 2 6 ) ( 2 7 ) ( 2 8 ) ( 2 9 ) q ( n ) = 啦一吉q a j y t y j ( x i 巧) ( 2 1 0 ) i = 1 。i j - - 1 这里，我们已经将符号从三( u ，b ，o ) 改成q ( q ) ，以反映出最后的转换。 q ( q ) 的表达式( 2 1 0 ) 称之为l a g r a n g e 对偶目标函数，在约束条件： 0 ，i = 1 ，2 ，j 5 ( 2 1 1 ) ( 2 1 2 ) 甄吼 犰 ；：l i | u 到得此由 0 = 玑 q 。甜 o = 玑 q 。汹 支持向量机与k 一均值聚类融合算法研究 下对啦求解函数q ( q ) 的最大值，所得到的解啦只有一部分( 通常是少部分) 不为 零，对应的样本就是支持向量。 应该注意的是最优化问题的目标函数 ) = i - - - - 1q t 一去荟啪砒吲 j = l 与向量z 的维数无关，但是与两个向量的内积有关。这一事实将允许我们随后在 高维空间( 甚至在无限维f 拘h i l b e r t 空问) 中构造分类超平面。 2 1 2 线性不可分 1 核方法 为了解决线性不可分问题，我们采用一个非线性变换西0 ) 把输入变量z 影射 到一个高维特征空间日，然后在这一特征空间( 可能为无限大的) 中构造一个最 优分类超平面，并得到分类器的决策函数。因此，在非线性情况，分类超平面 为 ( u 圣( z ) ) + b = 0( 2 1 3 ) 决策函数为 f ( x ) = s 夕礼( ( u 西( z ) ) + 6 )( 2 1 4 ) 由式( 2 1 0 ) , - p a 看出，对于在特征空间日中构造最优分类超平面，我们并不 需要以显式来表示特征空间。我们仅仅需要计算特征空间中的向量之间的内 积。 假定，我们将输入向量z 册映射到一个h i l b e r t 空间，即 圣1 ( z ) ，圣2 ( z ) ，圣。( z ) 根据h i l b e r t s c h m i d t 理论，h i l b e r t 空间中的内积有一个等价表达式： ( 1 ，九2 ) = q h i ( x 1 ) 吃( z 2 ) 甘k ( x l ，z 2 ) ，o l i 0 ( 2 1 5 ) i = 1 式口p k ( z l ，z 2 ) 为满足m e r c e r 定理的对称函数，称之为核函数。目前常用的核函 数有1 0 多种，其中流行的核函数是： d 次多项式： k ( x ，甄) = ( 1 + x 乜) d( 2 1 6 ) 高斯径向基函数：g ( x ，戤) = e x p ( 一i iz 一瓤1 1 2 盯2 )( 2 1 7 ) 6 支持向量机与k 一均值聚类融合算法研究 神经网络核函数：k ( x ，戤) = t a n h1 ( z 觑) + 忱( 2 1 8 ) 核方法的基本思想是：椭h m e r c e r 条件的任何核函数k ( z ，既) ，存在 个特征空间( 圣1 ( z ) ，圣2 ( z ) ，垂。( z ) ，) ，在这一空间中这个核函数生成内积。 也就是说式( 2 1 5 ) 的左端绝对一致的收敛于函数k ( x ，x i ) ，即 k ( x ，x i ) = ：a l h t ( x ) h t ( x i )( 2 1 9 ) 1 = 1 由此可见，样本空间的内积运算已替换成核，事实上，运算是在样本空间进行 的，而不是在高维特征空间进行的，这就是核技巧的思想。 核方法的优点：由于输入空间的核函数实际上是特征空间内积的等价。因 此，在实际计算中，我们不必关心非线性映射圣( z ) 的具体形式，只需要选定核 函数g ( x ，兢) 就行。核函数比较简单，而映射函数可能很复杂，而且维数很高。 因此，引入核方法才能克服“维数灾难”问题。 2 算法实现 根据核方法思想，对于非线性分类，首先采用一个非线性映射圣( z ) 把数据 影射到一个高维特征空间，然后在高维特征空间中进行线性分类，映回到原空 间后就成了输入空间中的非线性分类。为了避免高维空间中的复杂计算，支持 向量机采用一个核函数k ( x ，y ) 代替高维空间中的内积运算( 圣( z ) 圣( 矽) ) 。 另外，考虑到可能存在一些样本不能被分离超平面正确分类，采用松弛变 量解决这个问题，于是优化问题为： 1 。 r a u ，6 i ，n 互l 约束为 玑( ( u 圣( 黾) ) + b ) 1 一已，i = 1 ，2 ，z 已0 ，i = 1 ，2 ，z 其中，c 为一正常数。式( 2 2 0 ) 中第一项使样本到超平面的距离尽量大， 高泛化能力；第二项则使分类误差尽量小。 引入拉格朗日函数 l ：互1 怕胪+ c 壶已一壹叫洲u 州硝) + 6 ) 一1 + 已) 一壹m 已 其中，q t ，m 0 ，i = 1 ，f 7 ( 2 2 0 )& 。汹 c+ 2 叫锄限 埘 勉 勉 厩 勉 q 炯 5 支持向量机与k 一均值聚类融合算法研究 函数l 的极值应满足条件 o 伽l = o , 旦l = 。，瓦0 0b l = 。 伽 一 1 弛一 。 于是得到 u = y i a t 圣( ) ( 2 2 4 ) ( 2 2 5 ) ( 2 2 6 ) c q 一已= 0 ，i = 1 ，f ( 2 2 7 ) 将( 2 2 5 ) 一( 2 2 7 ) 代入式( 2 2 3 ) 中，得到优化问题的对偶形式为： f 1l m a x 啦一吉a i a j y i y j k ( x t , 巧) ( 2 2 8 ) i = li = 1j = l 约束为 ，q t 犰= 0 ( 2 2 9 ) i = l 0 q c ，i = 1 ，f ( 2 3 0 ) 一般情况下，该优化问题解的特点是大部分啦将为零，其中不为零的q ；所 对应的样本为支持向量( s u p p o r tv e c t o r ，s v ) 。 根据k k t 条件，在鞍点有 a t ( 玑( ( u 圣( 戤) ) + b ) 一l + 已) = 0 ，i = 1 ，z ( 2 3 1 ) ( c 一口i ) & = 0 ，i = 1 ，f( 2 3 2 ) 于是可得b 的计算式如下： l 玑( a j y j k ( x j ，毛) + 6 ) 一1 = o ，q ( o ，c ) ( 2 3 3 ) j = l 因此，可以通过任意一个支持向量求出6 的值。为了稳定起见，也可以用所 有的支持向量求出6 的值，然后取平均。 最后得到决策函数为： 8 ( 2 3 4 ) o l i 玑 口 ，汹 6+zzk 玑 q ，谢 n 9 s = z ，j 支持向量机与k 一均值聚类融合算法研究 2 1 3 一类分类 设定一个正类样本点集为【祝，i = 1 ，z ) ，瓤r d 用一个非线性映射将样 本点映射到高维特征空间。一类支持向量机( 1 s v m ) 的目的就是要在高维空间 中找一个超平面，使之以尽可能大的距离p 将尽可能多的样本从原点分离开，即 估计一个函数f ( x ) = p 圣( z ) ) 当一个样本z 满足厶( z ) p 时，它被确定为属于 该类。为了获得“，和p 的值，并根据结构风险最小化原则，将问题归结为下面的 优化： ( 2 3 5 ) ( u 垂( 兢) ) p 一毛，& 0 ，i = l ，f( 2 3 6 ) 其中，；i iu1 1 2 为规划项，参数c 对误差项和规划项做出折中。将优化问题化为 对偶形式： m i n 专啦k ( 双，) ( 2 3 7 ) 。i = lj = l 约束为 0 q t c ，i = 1 ，z( 2 3 8 ) 解出口值后，可得决策函数： 决策超平面为： ( 2 3 9 ) ( 2 4 0 ) ( 2 4 1 ) 2 2基于线性规划的支持向量机分类 支持向量机中参数的数量在分类情况下等于训练样本的个数，在回归情况 下是训练样本个数的二倍。当数据量很大时，其计算的时间和空间复杂度均很 大。若能将支持向量机算法归结为线性规划来求解无疑会大大减少计算量，于 是一些线性规划下的支持向量机方法被提出。最初的支持向量机分类算法是通 9 已 。僦 c+ p 一 酽 u 1 2 洫差| 为束约 l = 口 ；斟 zzkq 。汹 = z ，j p l l 圣zk口 。汹 支持向量机与k - 均值聚类融合算法研究 过最大化分类间隔得到的，而其中的距离度量采用的是由l 2 范数导出的欧氏距 离。若用l 1 和l 范数代替其中的l 2 范数将得到基于线性规划的支持向量机算 法。线性规划的支持向量机算法仍然具有很好的性能，而且计算复杂度大大减 少。 若优化问题( 2 3 5 ) d p 的规划项采用l o 。范数，并且核函数取高斯核函数，可 以得到其等价的线性优化问题： 。 l m i n - p + c 已 i = 1 ( 2 4 2 ) 约束为 ( u 圣( z i ) ) p 一& ，& 0 ，i = 1 ，j( 2 4 3 ) 0ui l l = 1( 2 4 4 ) z 可以直接采用核展开式eo q k ( z j ，兢) 代替优化i h - i 题( 2 4 2 ) c p 的不等式约束 项p 圣( 戤) ) ，于是可得到下面的线性规划形式： f r a i n - p + c 矗 ( 2 4 5 ) = 1 约束为 a j k ( x ，) p 一劬= 1 ，z ( 2 4 6 ) j = l f o l i = 1 ( 2 4 7 ) i = 1 啦，& 0 ，i = 1 ，z ( 2 4 8 ) 解这个线性规划可以获得q 和p 的值，于是得到一个决策函数： z ，( z ) = 啦k ( x i ，z ) ( 2 4 9 ) i = 1 根据优化问题的意义，对于大部分训练样本将满足， ) p ，参数c 的意义 就是控制满足条件厂( z ) p 的样本数量，较大的参数c 值将使所有的样本满足条 件。得到的决策超平面为： f q t k ( x 舻) = p ( 2 5 0 ) i = 1 1 0 支持向量机与k 一均值聚类融合算法研究 该决策超平面映回到原空间后，就成为包含训练样本的紧致区域。对于区域内 的任意样本z ，满足，( z ) p ，而对于区域外的任意样本y 将满足，( ) p 。实际 应用中，核函数中的参数盯2 的取值越小，获得原空间中包含训练样本的区域越 紧致，这就说明参数o r 2 将决定分类的精度。 2 3基于模糊隶属度的支持向量机去噪方法 尽管在很多方面支持向量机都具有其它学习方法无法比拟的优势，但是它 不是万能的，也有其自身的局限性，例如对噪声或野值反应灵敏，从而使其容 噪性差，因此，提高支持向量机的抗噪性成为了一个值得研究的课题。 由于支持向量机在构造最优分类超平面时，所有的样本所起的作用相同， 这样，当样本中含有一定的噪声或野值样本时，考虑这些噪声或野值样本所产 生的分类面往往不是真正的最优分类超平面。针对这种情况，l i n 等学者提出 了模糊支持向量机( f u z z ys u p p o r tv e c t o rm a c h i n e ，f s v m ) a 2 - x s ，对不同样本 采用不同的权重系数，使得在构造目标函数时，对噪声或野值赋予较小的权 值，以削弱其影响。在f s v m 中，必须能够客观准确地反映系统中样本存在的 不确定性。一般的f s v m 都是基于样本到类中心之间的距离来度量其隶属度的 大小，然而，在依据样本到类中心之间距离的角度确定样本的隶属度时，有时 并不能将噪声或野值样本从有效的样本中区分出来，导致将噪声或野值样本与 有效样本赋予相同的隶属度。针对这个问题，文献 1 6 】中提出了一种基于样本之 间紧密度的模糊支持向量机方法，在确定样本的隶属度时，不仅要考虑样本所 在类中心之间的距离，还要考虑类中样本之间的紧密度。 支持向量机的本质是在训练样本中找出构造最优分类超平面的支持向量， 而样本中存在的噪声或野值样本常常在分类面附近，从而影响了支持向量对构 造分类面的作用，本章提出的方法就是利用模糊隶属度剔除样本中存在的噪声 或野值样本，在构造最优分类超平面时，不考虑权重系数小的噪声或野值样 本。在确定隶属度的训练中，采用的是线性规划一类分类方法，实验证明了本 文提出的方法在提高s v m 的抗噪能力方面的有效性，而且在处理大量数据时， 线性规划要比二次规划节省很多时间。 2 3 1 构造隶属度函数 在确定样本的隶属度时，不仪要考虑样本与所在类中心的距离，还要考虑 1 1 支持向量机与k 一均值聚类融合算法研究 样本之间的紧密度。样本之间的紧密度可以通过样本远离原点的程度来度量。 所以，样本的隶属度要根据样本远离原点的最大距离p 来确定。对分布在区域 内、外的样本，分别采用两种不同的计算方式计算各自的隶属度。隶属度计算 公式为： l l0 6 宰i p ( 鼢) ： l 卜水l + 0 以) ) ，( 觑) p ( 2 5 1 ) ，( 甄) p 其中p 为样本离原点的最大距离，( 忍) 为样本x t 的决策函数，其计算式为 f f ( x j ) = a i k ( x i ，巧) ，j = 1 ，f ( 2 5 2 ) i = 1 由( 2 5 1 ) 定义的隶属度p ( 兢) 可以看出：样本离原点越远，则该样本属于该 类的隶属度就越大，同时也考虑了样本位于类内位置的影响，位于类区域内的 样本隶属度都大于0 5 ；而位于类区域外的样本隶属度都小于0 5 ，由于噪声和 野值样本一般都位于类区域外，所以其隶属度都小于o 5 。由此，设置一个小 于0 5 的阀值就可以将噪声和野值样本从样本集中剔除，留下的都是对构建最优 分类超平面有益的样本。 2 3 2实现步骤 1 分别对正、负类样本进行线性规划下的一类分类，由此分别产生正、负 决策面a i k ( z i ，x ) = n ，2 ，及决策函数 ，2 ( z ) = e 毗k ( 貌，z ) ； 2 由p 1 ，2 和 ，2 ( z ) 确定各个样本的隶属度p ( z ) ； 3 设定阀值入，将p ( z ) 入的噪声样本从原样本中剔除，从而产生新样本 集； 4 采用去噪后的样本训练支持向量机。 2 3 3 实验分析 本实验先采用了4 0 0 个随机产生的两类二维样本，2 0 0 个正类样本和2 0 0 个 负类样本，并分别在正、负类样本中随机加入了1 0 的噪声作为训练样本， 如图2 1 所示。采用2 2 0 个测试样本，在测试样本中同样也随机加入了1 0 的 噪声。分别采用传统支持向量机和本文提出的基于模糊技术去噪声的方法 1 2 垂、 、一、 一，垄f 卜一h h 支持向量机与k 均值聚类融合算法研究 图2 1 ：带噪声样本 进行实验，c 和口分别取1 2 和3 0 ，a = 0 3 ，传统的支持向量机样本正确识别率 为8 3 6 4 ，本文的方法样本正确识别率为8 7 7 3 。又采用相似随机样本，但只 在分类面附近加入噪声，分别用两种方法训练，c 和伊分别取3 0 和5 0 ，a = 0 3 ， 传统的支持向量机正确识别率分别为7 9 2 ，本文的方法正确识别率为8 4 5 1 。 分别采用b a n a n a ，h e a r t ，b r e a s t c a n c e r 数据进行实验，在原始数据中分别 加入1 0 的噪声，再用上述两种方法分别进行实验。实验结果显示，样本的正 确识别率均有所提高，实验结果如表2 1 所示。而对不加噪声的样本用两种方法 分别进行实验，结果并没有太大差异。 表2 1 本文方法与s v m 方法的正确识别率之比较 方法 b a n a n ah e a r tb r e a s t c a n c e r s v m8 4 6 8 8 0 0 0 7 7 1 本章方法 8 6 2 9 8 5 0 1 7 9 5 2 对于不同的数据，阀值入要采用不同的值，一般情况取0 3 a 0 4 。通过 1 3 支持向量机与k 均值聚类融合算法研究 训练调整a 值，a 值太大会把正常样本点去掉，入值太小对噪声起不到作用。实 验证明，去除含有“异常”信息的噪声样本对构建最优分类超平面是有益的， 本文提出的方法在提高支持向量机的抗噪能力方面效果非常明显，应用也非常 广泛。 2 3 4实验总结 传统的支持向量机在处理无噪声的样本时，学习能力和泛化能力都非常 强，但当样本中存在噪声或野值样本时，噪声或野值样本影响了支持向量对构 造分类面的作用，使产生的分类面偏离了最优分类超平面。本文运用模糊隶属 度去除样本中存在的噪声或野值样本，减小其对分类面的影响。在确定隶属度 时，不仅考虑样本与所在类的距离，而且还考虑了样本之间的紧密度，对不同 的样本采用不同的公式计算其隶属度。再者，应用线性规划大大节省了计算时 间。通过对比实验，证明本文提出的方法与传统的支持向量机相比，样本的正 确识别率更高，改善了支持向量机对噪声敏感的问题，增强了支持向量机的抗 噪能力。 1 4 支持向量机与k 一均值聚类融合算法研究 3k 均值聚类算法 3 1划分聚类算法概述 划分聚类也叫分割聚类。给定一个含有t t 个对象或元组的数据库，一个划分 方法，通过优化一个评价函数构建数据的k 个划分，每个划分表示一个聚类，并 且k t t 。也就是说，它将数据划分为k 个组，同时满足如下的要求： 1 每个组至少包括一个对象； 2 每个对象必须属于且只属于一个组。 但是在某些模糊划分技术中第二个要求可以放宽。一个好的划分准则是：在 同一个类中对象之间尽可能“接近或相关，而不同类中的对象之间尽可能 “远离”或不同。 为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实际 上，绝大多数应用采用了以下两个比较流行的启发式方法：1 k 均值算法，在 该算法中，每个簇用其中对象的平均值来表示。2 k 一中心点算法，在该算法 中，每个簇用接近聚类中心的一个对象来表示。这些启发式聚类方法对在中小 规模的数据库中发现球状簇很适用。为了对大规模的数据集进行聚类，以及处 理复杂形状的聚类，基于划分的方法需要进一步地扩展。 划分算法典型地采用两阶段反复循环过程：1 指定聚类，即指定一个数据 对象到某一个聚类，使得它与这个聚类中心的距离比它与其它聚类中心的距离 要近；2 修改聚类中心。算法的结束条件是不再有数据被重新分配。可以选 择一个反映聚类效果的目标函数，当函数达到最优解时满足终止标准。这一 类算法中，有的算法在对每一个数据对象的每一次指定后就修改一次聚类中 心( 如s o m 方法) ，有的算法当对所有的数据对象都指定完后才修改一次聚类中 心( 如k 一均值，l b g 方法) ，所以对这一类方法来说，存在两个基本问题，即： 如何计算距离和如何修改聚类中心。在计算距离时，对数值属性主要的方法是 采用明考夫斯基距离中的欧氏距离，而对符号属性则可以采用海明距离。 在数据规模比较小以及数据对象维数较低的情况下，传统的划分聚类算法 可以将数据全部读入到内存进行计算，而随着数据量地增加，需要和磁盘进行 多次数据交换，花费大量的i o 时间；又由于划分聚类算法通常需要大量的距 离计算( 数据对象之间以及它们与聚类中心之间的) ，从而导致运行时问开销较 大，效率较低。这直接限制了它们在一些相关领域中的实用性。如何对以惊人 1 5 支持向量机与k 一均值聚类融合算法研究 速度增长的数据量进行聚类，如何提高算法的执行效率以及可扩展性就成为了 许多算法需要解决的问题1 1 7 】。 3 2聚类分析中数据类型 数据分析中的数据类型主要有两类。假设对一个数据集进行聚类分析，该 数据集包含n 个对象，这些对象可以是人、树木、文件等等。基于内存的聚类算 法通常采用以下两种数据结构1 1 8 ： 1 数据矩阵 数据矩阵是一个对象一一属性结构，它其实是一张关系表，每列代表对象 的一个属性，每行表示一个数据对象。具有m 个属性的n 个对象( 例如：树木对 象可以利用m 个属性来描述，属性如：高度、种类等) 可以表示为一个几x 仇矩 阵来表示： a l t o a n m ( 3 1 ) 2 差异矩阵 差异矩阵存储n 个对象两两之间的相异性。它是一个对象一一对象结构，其 表现形式是一个nx n f f r 矩阵，其中的每一个元素d ( t 歹) 表示对象i 和对象歹之间的 垫_ ：。卜 2 ， 通常情况下，d ( i ，歹) 是一个非负数，当对象i 和对象j 彼此“接近”时， 该数据就越接近0 值：该数据值越大，就表示对象i 和对象7 越不相似。由于 有d ( i ，j ) = d ( j ，i ) ，且d ( i ，i ) = 0 ，因此，此矩阵可表示成下三角行列式的形式。 通常，数据矩阵又可称为双模式( t w o - m o d e ) 矩阵，差异矩阵则又可称为单 模式( o n e - m o d e ) 矩阵。因为数据矩阵的行和列分别表示不同的实体，而差异矩 阵的行和列则表示的是同一实体。许多聚类算法都是基于差异矩阵进行聚类分 1 6 一 一 l ，1 m ； o 磊& m o m 邢m ，。一 示表r r如 。 度异相 支持向量机与k 一均值聚类融合算法研究 析的。如果数据是以数据矩阵的形式给出的，就要先将其转换为差异矩阵，才 能利用聚类算法对其进行处理。 3 3聚类分析中相似度度量方法 1 区间标度变量 区问标度变量是一个粗略线性标度的连续变量。典型的例子包括重量和高 度，经度和纬度，以及大气温度。 选用的度量单位将直接影响聚类分析的结果。一般而言，选用的单位越 小，变量可能的值域就越大，这样对聚类结果的影响就越大。因此为了避免聚 类结果对单位选择的依赖，数据应当标准化。标准化处理后，对象间的相异度 是基于距离来计算的。最常用的距离度量方法是欧氏距离，它的定义为： d ( x i ，协) = 、ix i l 一协11 2 + lx i 2 一y i 21 2 + + ix i l y j m1 2 ( 3 3 ) 这里戤= ( x i l ，x i 2 ，x i 竹) 的劬= ( 协1 ，y j 2 ，协n ) 和是两个仇维的数据对象。 在使用欧氏距离时要特别注意样本诸测量值的选取，应是能有效反映类别属性 的特征。 另外，两个著名的度量方法是曼哈顿距离： d ( 戤，协) = x i l 一协1i + ix i 2 一协2i + + i 兢1 一协mi( 3 4 ) 明考夫斯基距离： d ( x i , 协) = 舡孓i 再瓦i 万i 可而 ( 3 5 ) 从明考夫斯基距离可以看出：当口= 1 时，它表示曼哈顿距离，当q = 2 时， 它表示欧氏距离。 2