（计算机应用技术专业论文）一种改进的离群模糊核聚类算法.pdf

摘要一般说来，离群点是远离其他数据点的数据，但很可能包含着极其重要的信息。对离群点进行识别是相当重要的，它不但能够提高分析的质量，而且能够发现和研究离群点。本文对算法如何初始化参数进行了比较研究，提出用类心作为初始化参数并说明了其优点。针对聚类目标函数的选择，本文提出了一种全新的聚类目标函数采用核空间类心的距离，即类心的核距离作为聚类的目标函数，并给出了该目标函数的推导过程。通过对本文算法和现有算法目标函数搜索空间的比较， 导出文中算法的目标函数是较优的。本文还对算法的空间复杂度和时间复杂度进行了分析，说明本文算法在时间复杂度上比现有算法小。通过对仿真数据和真实数据的实验，测试了算法的可行性和有效性。首先，针对不同的数据集选取了不同的核函数进行了实验，并针对不同聚类目标函数进行了对比分析；其次，结合算法如何初始化参数的分析，对不同初始点对算法灵敏度的影响进行了比较实验；最后，本文对权重常量和权重指数的变化对聚类结果的影响进行了分析，给出了理论上的解释，并结合隶属度和权重系数的图进行了验证。实验结果表明改进算法能在保持聚类效果的前提下，很大程度的提高算法的收敛速度，大大减少算法整体的运行时间。关键词：离群模糊核函数核距离聚类分析a b s t r a c to u t h e r sa r ed a t av a l u e st h a tl i ea w a yf r o mt h eg e n e r a lc l u s t e r so fo t h e rd a t av a l u e s i tm a yb et h a ta no u t l i e ri m p l i e st h em o s ti m p o r t a n tf e a t u r eo fad a t a s e t t h e i ri d e n t i f i c a t i o ni si m p o r t a n tn o to n l yf o ri m p r o v i n gt h ea n a l y s i sb u ta l s of o ri n d i c a t i n ga n o m a l i e sw h i c hm a yr e q u i r ef u r t h e ri n v e s t i g a t i o n i nt h i sp a p e r , ac o m p a r i s o no fi n i t i a l i z i n gp r o t o t y p eva n dm e m b e r s h i pd e g r e eui sm a d e ，w h i c hs h o w st h a ti n i t i a l i z i n gv h a sm a n ya d v a n t a g e so v e rt h o s ea v a i l a b l e w ei n t r o d u c ean e wo b j e c t i v ef u n c t i o nf o rf u z z yc l u s t e r i n g ，w h i c hu s e svk e r n e l d i s t a n c ea st h ef u n c t i o n ，a n dt h ed e r i v a t i o np r o c e d u r eo ft h ef u n c t i o ni sa l s os h o w ni nt h ep a p e r ac o m p a r i s o nb e t w e e nt h ep a p e r sa n dt h ea v a i l a b l em e t h o ds h o w st h a tt h en e wo b j e c t i v ef u n c t i o nh a st h ea d v a n t a g e so fl e s ss e a r c hs p a c e i ti sa l s os h o w nt h a to u rm e t h o dh a sl e s st i m ec o m p l e x i t yt h a nt h ea v a i l a b l e t h es i m u l a t i o n sd e m o n s t r a t et h ef e a s i b i l i t ya n ds p e e d yo ft h ep r o p o s e dm e t h o d f i r s t l y ，e x p e r i m e n t so fd i f f e r e n td a t a s e t sb ya p p l y i n gd i f f e r e n tk e r n e lf u n c t i o na n do b j e c t i v ef u n c t i o na r em a d e s e c o n d l y ,e x p e r i m e n t s o f i n i t i a l i z i n gd i f f e r e n t v a r e m a d e f i n a l l y , f i g u r e so f m e m b e r s h i p d e g r e e u a n d o u t l i e rw e i g h t i n gf a c t o rw a r es h o w n o u rm e t h o dc a ng r e a t l yi n c r e a s et h ec o n v e r g e n c es p e e da n dd e c r e a s et h ea l g o r i t h m sp i d s s i n gt i m eu n d e rt h eg o o dc l u s t e r i n gr e s u l ti sk e p t k e y w o r d s ：o u t l i e r ，f u z z y ，k e r n e lf u n c t i o n ，k e r n e ld i s t a n c e ，c l u s t e r i n ga n a l y s i s创新性声明y8 5 s s 6g本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签名：叠。亟逮i日期垫! ! ：三：兰关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在解密后遵守此规定)本人签名：垒整亟导师签名：邋臼期迦! ! ：鲨日期怂! ：丝第一章绪论第一章绪论1 1 研究背景对于离群问题的定义，很多学者对于不同问题提出了不同的定义( h a w k i n s ，1 9 8 0 1 】；b e c k m a n & c o o k ，1 9 8 3 2 】：b a r n e t t l e w i s ，1 9 8 7 3 】；t a b a c h n i c k f i d e l l ，1 9 9 6 1 4 ) ，但其内在含义是一致的，即离群点是在收集数据的过程中由于误操作或者异常情况，从而出现了一些不符合正常特征的数据点。对于这些离群点，如果是由于误操作而得到的，则要剔除掉，从而提高样本数据的质量；如果是由于出现了新规律而导致离群点的产生，则应该对这些点加以重点的分析。由于离群点在整个数据集中只占很小的一部分，在以前的数据处理中，常常会把离群点当作小概率事件而不加以处理分析，从而造成了很大的损失。从知识发现的角度来讲，小概率事件通常要比一般事件更能引起人们研究的兴趣。离散点的识别有着众多的应用，包括侦察信用卡的信用欺骗，发现电子经济犯罪活动，视频监视，药物研究，天气预报，职业运动员的成绩统计分析，以及发现那些未知的天体和罕见的天文现象等【5 】。1 2 离群模糊聚类算法的发展概况近几年，对于离群点的发现越来越引起人们的关注。很多学者提出了不同的发现离群点的方法。总的说来，目前主要有两类发现离群点的方法：主观发现法和客观发现法。在主观方法中，用户直接把自己的知识融入定义参数的过程中，如“非常远”、“低密度”等，从这一点来说，主观发现方法对于不同的用户可能会导致不同的结果，并且其可扩展性也比较差【6 1 ，而且这种主观发现的方法只适用于一些小数据集，对于大数据集来说，将是一个非常耗时的过程。在客观发现的方法中，算法将根据数据点的分布情况，自动地发现一些离群点。文献7 1 给出了一种基于图形方法的客观发现方法，这种方法通过构建一个b o xp l o t 来描述数据样本的分布情况。实际上，已经有学者开始把模糊聚类算法应用于发现离群点的过程中，并取得了很好的结果1 8 1 ，该算法是基于f c m 模糊聚类算法，通过对每一个样本分配一个动态的权值，从而最终通过权值发现离群点，该算法对于线性可分的数据集能取得较好的效果。现实生活中常常会出现一些线性不可分但非线性可分的数据集，对于这种数据集，文献【8 】的算法将不能很好地聚类并发现相应的2一种改进的离群模糊核聚类算法离群点。文献【9 】提出了一种新的离群模糊核聚类算法，通过m e r c e r 核函数，首先把数据样本空间映射到特征空间，对特征空间的每一个向量分配一个动态的权值，并在f c m 模糊聚类的基础上得到一个新的包括向量权值的目标函数，在特征空间内，通过对该新目标函数的优化，最终得到了各个数据点的权值，从而根据这个权值发现数据样本中的离群点。然而文献【8 】和【9 】都是在f c m 的基础上演化出的算法，算法的过程中有很多可以进行完善和提高，比如算法初始化参数的选择，聚类目标函数的选择等等。1 3 研究内容和章节安排作者在他人先期研究离群模糊核聚类的基础上，对其基本原理、运行行为及其特性进行了较深入的研究，分析了离群模糊核聚类算法中存在的问题，从多个角度和方面进行研究和探讨，提出了一种改进的离群模糊核聚类算法。本文的工作主要有以下几个方面：( 1 ) 本文对算法如何选择初始化参数进行了比较研究，提出采用类心作为离群模糊核聚类算法的初始化参数；( 2 ) 提出了一种全新的聚类目标函数采用核空间的类心的距离，即类心的核距离作为聚类的目标函数，该方法能很大的提高算法的收敛速度，从而大大减少算法整体的运行时间；( 3 ) 对仿真数据和真实数据进行了实验，并对实验结果从图像和数据统计上给出了多方面的分析。具体的章节安排如下：第一章简单介绍了离群问题的研究背景以及离群模糊聚类算法的发展概况；第二章介绍了模糊算法的基础知识，重点讲述了模糊理论技术：第三章对现有离群算法进行了概况讲述，引出离群模糊核聚类算法；第四章在现有离群模糊核聚类算法的基础上，提出了一种改进的离群模糊核聚类算法，并对算法的性能进行了分析：第五章用仿真数据和真实数据对算法进行了实验，分析了选取不同的核函数以及初始点对聚类结果的影响，并分析了弘矽图。实验从图像和统计数据上给出了多方面的比较分析。实验结果表明了该算法的有效性和快速性；第六章总结本论文的主要研究成果及意义，同时也指出了研究工作中存在的不足和进一步的解决思路。本课题的研究工作在国家自然科学基金( n o 6 0 3 7 1 0 4 4 ) 和国家留学回国人员科研基金资助的支持下完成。第二章模糊算法基础知识第二章模糊算法基础知识2 1 模糊理论综述2 1 1 模糊理论定义模糊理论是一个充满争议的领域，主要原因之一是人们对模糊这两个字的误解。模糊理论并非“模糊的理论”，而是研究模糊现象，利用模糊信息的精确理论。与其他适用性理论一样，模糊系统理论所追求的目标是为解决各种实际问题提供更加有效的思路与方法。归纳一下，模糊系统理论具有以下特点【”1 ：( 1 ) 强调充分利用各种所能获得的信息，包括数据信息，模型信息，语言信息等。( 2 ) 将各种信息融为一体，在一个统一的数学框架下进行研究。( 3 ) 强调实用性与理论完备性相结合，以实用性为先导。( 4 ) 应用对象不局限于某个特定的领域，而广泛适用于工程、经济、金融、管理、社会等各个领域。2 1 2 研究模糊系统的目的“模糊”( f u z z y ) 一词的含义为“朦胧的，模糊的；不精确的；不合乎逻辑的，不明白的。”实际上，模糊系统是一个被精确定义的系统，尽管模糊系统理论描述的现象可能是模糊的，但理论本身却是精确的【1 1 l 。在文献 1 1 1 ，认为研究模糊系统理论的原因有两类：( 1 ) 现实世界太复杂以至于无法做到精确描述，所以为了得到一个合理的且可跟踪的模型就必须引入近似性( 即模糊性) 概念。( 2 ) 随着向信息时代的迈进，人类知识变得日益重要。我们需要一种理论，能系统的描述人类知识并将其同其它信息( 如数学模型和感官测量) 一起嵌入到工程系统中。第一类原因虽然正确，但它并未概括出模糊系统理论独一无二的性质。实际上，几乎工程中的所有理论都是以一种近似的方法来描述现实世界的。举例来说，大多数实际系统都是非线性的，但我们却对线性系统的研究作了大量的努力。一个好的工程理论应该是精确的，应既能概括出现实世界的关键性质，又便于用数学分析的方法跟踪研究。在此方面，模糊系统理论同其他工程理论是没有区别的。d一种改进的离群模糊核聚类算法第二类原因，描述了模糊系统理论的独有特征并证明了它是作为工程学中的一一个独立分支而存在的。根据一般性原则，一个好的工程理论应该能够有效利用所有可得的信息。对于大多数实际系统来说，有两个重要的信息来源：一个是要用自然语言描述系统性能的专家；另一个是传感器提供的测量数据和根据自然法则推导出来的数学模型。因此，一项重要的任务就是怎样将这两类信息整合到系统设计中去。实现这种整合的关键在于怎样将人的知识整合到同传感器测量结果及数学模型类似的“框架”中。换句话说，关键问题在于怎样把一个人类知识库转换成一个数学公式，这种转换就是由模糊系统来完成。2 2 模糊理论技术模糊数学为模糊系统与模糊控制的发展提供了起点和基本语言。模糊数学本身就是一个巨大的领域，其原理是由用模糊集合的概念取代经典数学理论中的集合概念而发展来的。按照这种方式，所有的经典数学分支都可以被“模糊化”，于是诞生了模糊测度理论、模糊拓扑、模糊算术和模糊分析等等分支。因此，下面将介绍模糊数学中有关模糊系统的一些概念和原理。2 2 1 经典集合定义一个论域正它为有相同特性对象的集合，域盖内的元素称为膏。x 域中的元素性质可以是离散的、可数整数或实轴上有连续取值的量。各种域的元素可列举如下：计算机c p u 的时钟频率；电机的工作电流；1 1 0 间的整数。由j 域内某些元素的集合所构成的清晰集合a 和口有下列定义：x x z 属于x上e a x 属翻x 琏彳一z 不属于对石域上的集合爿和占有：爿c 嚣一a 完全包含于b ( 如果x c a 贝, t k b )爿c b 一4 包含于曰或等价于ba = b 一4 曰和丑4把不包含任何元素的集合定义为空集妒，把域内所有元素的集合定义为全集。空集对应于不可能发生的事情，全集对应于必然发生的事情。盖的所有可能子集合第二章模糊算法基础知识所构成的一个特殊集合称为幂集e ( x 1 。2 2 2 模糊集合在经典或清晰集合中，域内元素在给定集合中有隶属度与无隶属度之间的变化是突变的和容易定义的( 称为“清晰”) 。对含有模糊集合的论域中元素来说，这种变化是渐变的。不同隶属度之间的变化可认为遵循了模糊集合边界的不确定性和模糊性的事实。因此，此集合中的域内元素的隶属度可由描述不确定性和模糊性的函数来度量。模糊集合是一个有着不同隶属度的元素的集合。这与经典或清晰集合的概念正相反，因为清晰集合是不可能有非全隶属度的元素的( 即其隶属度为1 ) 。一个模糊集合中元素可以是同一域内另一个模糊集合的元素，因为其隶属度可为非全隶属度取值。用函数论的形式将模糊集合的元素映射到一个“隶属度值”域内。定义2 1 论域u 上的模糊集合是用隶属函数心 ) 来表征的，以 ) 的取值范围是【o 1 】。因此，模糊集合是经典集合的一种推广，它允许隶属度函数在区间【0 ，1 】内任意取值。换句话说，经典集合的隶属度函数值允许取两个值0 或1 ，而模糊集合的隶属度函数则是区间【o ，1 】上的一个函数。由定义可以看出，模糊集合一点都不模糊，它只是一个带有隶属度函数的集合。c ，上的模糊集合一可以表示为一组元素与其隶属度值的有序对的集合，即a = o ，。 ) ) i 石u )( 2 1 )当u 连续时如( 月= u ) 。a 一般可以表示为a = 阻。0 ) i x( 2 - 2 )矗这里的符号j 并不表示积分，而是表示u 上隶属度函数为p 。o ) 的所有点工的集合。当u 取离散值时，爿一般可以表示为：彳；p 。( x ) x( 2 3 )1 口_这里的符号并不表示求和，两是表示u 上隶属度函数为卢。) 的所有点爿的集合【1 2 l 。2 2 3 模糊逻辑基本概念在各种不同的情况下都能够产生模糊信息和模糊数据。首先，它可能依赖于不精确的现实数据。比方说一个感觉数据可能是一个程度，而不是一个确定的值。6一种改进的离群模期核聚类算法其次，主观判断也可能产生模糊信息。打个比方，一个关于房屋不动产的数据库信息可能要包括对于公立学校质量的描述，社区的安全，以及对于房屋价格的正确评估等等。用精确值来表示这类信息常常很难确定诸如差、一般、好、优这些定性描述的平滑界限。因此，找到一个能够表示和操纵模糊信息的数据模式是一件很重要的事情。第三，用户也许正是对这些模糊信息感兴趣。比方说，对于一个大四的学生来说，找一个具有好的研究生工程课程和低生活费的大学是他们所感兴趣的。前面提到的“好”和“低”是不精确的。我们用定界限的方法来查询，“每年生活费低于x 元将把那些生活费稍稍高于工的，而且研究生工程课程非常好的大学排除在外。换句话说，用精确的查询条件进行不精确查询很可能会丢失一些用户要得到的有用信息。在目前的信息社会，社会科学，尤其是经济科学，要求数学提供表达形式，而在其中，模糊概念的数学表达形式是必不可少的，但是传统的集合论在模糊概念面前却软弱无力。1 9 6 5 年扎德( l 丸z a d e h ) 提出了模糊集合理论来处理这种模糊性。模糊概念是用相应的模糊集来刻画的。模糊集是对普通集合的扩充，可用其隶属函数来刻画。对于模糊集合及其隶属函数，扎德给出如下定义：定义：设u 是绘定论域，p ，是把任意“e u 映像为【o ，1 】上的某个值的函数，即脚：u 一【0 ，1 】“一卢，以)则称弘，为定义在( ，上的一个隶属函数，由p ，q ) ( 对所有球，) 所构成的集合，称为u 上的一个模糊集，称为“对f 的隶属度。我们可以看出，模糊集f 完全是由隶属函数弘，来刻画的，弘，把u 中的每一个元素u 都映像为【0 ，1 】上的一个值蜥0 ) 。卢，m ) 的值表示“隶属于f 的程度，其值越大，表示隶属于，的程度就越高。当p ， ) 仅取0 和1 两个值时，模糊集f就退化为一个普通集合。一般来说，一个非空的论域可以对应多个不同的模糊集：而一个空的论域只能对应一个空的模糊集。但是，一个模糊集与其隶属函数之间却是一一对应关系，即一个模糊集只能由一个隶属函数来刻画，一个隶属函数也只能刻画一个模糊集。2 2 4 模糊集合基本运算对应于普通集合的并、交、补运算，模糊集合也有类似的运算，在介绍模糊集合的这三个运算之前，首先将给出包含概念的定义，无论是普通集合还是模糊集合中，它都起到重要的作用。定义：设4 、8 为u 上的两个模糊集，若对于任意h u ，有第二章模糊算法基础知识7成立，定义：成立，定义：1 2 ) 1 2 口0 )则称4 包含曰，记为爿b 。设爿、b 为u 上的两个模糊集，若对于任意“e u ，有1 2 。0 ) = 1 2 。o )则称爿等于口，记为a = 口。设彳、b 为u 上的两个模糊集，c 为模糊集合4 、口的并集，即c ；爿u b 或c = 爿0 r b那么c 定义为1 2 c ) 一m a x ( 1 2 。0 ) ，肛口0 ) ) = 肛 ) v1 2 口 )定义：设a 、b 为u 上的两个模糊集，c 为模糊集合彳、丑的交集，即c - a n b 或c 刊a n d b那么c 定义为1 2 c 0 ) - m i n ( p 0 ) ，1 2 口以) ) ；1 2 j ) a1 2 口0 )定义：设a 为u 上的模糊集合，a 为一的补集，记为爿( - a ，n o t a )2 2 + 5 模糊知识表示和模糊推理传统的分析技术本质上不能处理人文系统，它的行为受人类判断、感知和情绪影响很大。这就是所谓“不兼容原则”的体现。“当系统复杂性提高，在一定阀值范围内，我们对其行为做出精确而有效判断的能力降低，在此阀值范围之外，精确性和有效性几乎是相互排斥的两个特性”。作为对人类思想建模的另一种方法，模糊逻辑使用了语言变量的概念，指的是用自然语言中的词或句子表示的变量。模糊逻辑是通过模糊谓词、模糊量词、模糊概率、模糊可能性、模糊真值、模糊修饰等对命题的模糊性进行描述的。模糊i f - t h e n 规则( 也称为模糊规则、模糊隐含或模糊条件句) 形为i f xi s at h e n yi s b其中一和曰分别是论域石和】，上的模糊集合定义的语言值，工、y 为变量，表示对象。通常，称“z 是爿”为前件或前提，“y 是b ”为后件或结论。条件部分可以是多个“x ；是4 ”的逻辑组合，此时，诸隶属函数之间的运算按照模糊集的运算进行。这个表达式描述的是变量x ，y 之间的关系。模糊i f - t h e n 规则可以定义为乘积空间x x y 上的二元模糊关系，设彳，四分别为论域z ，l ，上两个模糊集，则：r 。= f o 1 2 。o ) ) v ( 1 2 。o ) 1 2 。( y ) ) ( x ，y )j 1 7定义：，是u 上的模糊集合的全体，设a e f ( u 、，任取z s o , q ，记a 。= 恤e u l 爿 ) 苫a )一种改进的离群模糊核聚类算法称彳，为爿的a 截集，其中一称为阀值或置信水平。传统二值逻辑中基本的推理规则是假言推理，按照假言推理我们可以从爿的真实性和隐含关系4 一口推得命题b 的真实性。当a 接近于a ，b 接近于b ，爿、b 、a 、b 都是适当论域的模糊集合时，这一推理过程称为近似推理和模糊推理，也称为广义假言推理。定义：设a ，a ，b 和f 分别是x ，石和y 上的模糊集合，模糊隐含a 一曰表示为x x y 上的模糊关系r ，则由“z 是a ”和模糊规则“如果x 是a 则y 是曰”导出的模糊集合曰定义为t 口( y ) 一m a x ：r a i n # o ) ，0 ，_ ) ，) 】一v ；【芦a i o ) a z r ，y ) 】或等价地b t ；a o b ，4 o r 爿f o 一曰1也就是说若x 上的一个模糊集合，且4 可以和a 匹配，则可以推出y 是，且是y 上的一个模糊集。这种模式下，模糊知识i f x i s at h e n y i s b表示在a 和曰之间存在确定的因果关系r ，那么，当已知模糊事实f 可以和b 匹配时，则可以通过a 和r 的合成得到f 。2 3 本章小结本章首先介绍了模糊理论的定义，提出了研究模糊系统的目的，其次对模糊数学原理，模糊集合的概念进行了说明。模糊数学为模糊系统与模糊控制的发展提供了起点和基本语言，为解决各种实际问题提供更加有效的思路与方法。模糊数学已经越来越受到人们的重视，也发挥羞越来越大的作用。第三章离群数据聚类算法9第三章离群数据聚类算法3 1 离群模糊聚类算法令x 一仁，z ：，h ) 为模式空间r 9 中的一个有限数据集，以为该模式空问中的一个模式矢量。该个p 维数据表示成的一个n x p 的数据矩阵x ，模糊聚类算法把数据集x 划分成c 个模糊类，并获得一个最优模糊划分矩阵u 。该矩阵的元素“。e 0 , 1 】表示模式矢量以隶属于第i 类的程度。b e z d e k 提出的f c m 算法是分别关于u ，v 最小化目标函数，可表示为i ，( u ，矿) = 善荟“d & 2( 3 - 1 )其中矿一 ，v ：，v 。) ，q r ( 1 5 is c ) 是聚类中心或第i 类的模式原型。c 是事先确定的类别数目，m * ) 是模糊加权指数，对聚类的模糊程度有重要的调节作用：d * 一恢一划是数据点 到类心q 的距离，即用鼍和q 的欧式距离丸( k ，巧)来作距离测度。模糊c 一均值算法对( 3 一1 ) 式做极小化优化。b e z d e k 给出的f c m 算法通过目标函数j ，y ) 极小化的必要条件之间的迭代收敛到一个局部极小点或鞍点【2 7 】，得到的一个模糊c 划分u 。为避免出现平凡解，u 必须满足下面的约束：善“* t 1 ，v t 和o 善“* ，则t = t + l ，转4 ；否则算法终止。4 4 算法的空间复杂度从算法使用的存贮空间分析，本文算法需要的存贮空间有：初始化的类心v o个样本点置，样本到类心的核距离q ，隶属度u ，权重系数缈以及目标函数g工“一、lj，玩一鲰一。蚤；瞳第四章改进的算法及算法性能分析b | j ：s = o w 0 ) + o ( x ) + o ( q ) + o ( 叻+ o ( 叻+ o ( g )= 璺匾四+ o ( p ) + o ( n o + o ( n o + 0 0 v ) + q 固其中，是样本数目，p 是样本的维数，c 是样本的类数。比较文献【9 】给出的算法的存贮空间为：s = o ( 的+ o ( q ) + 0 ( t o + o ( 矸，+ o ( j )= 0 吒+ o ( n c o + 0 ( c ) + o ( ) + ! q ( n 。从加下划线的部分可以看出，本文提出的算法要比文献【9 】的算法使用较多的存贮空间，但这对于现今的计算机来说已经不是很大的问题。较多的存贮空问换来的是本文算法在时间复杂度上的极大降低。4 5 算法的时间复杂度从4 _ 3 节算法的步骤可以看出，本文算法的时间复杂度为：t = 0 k q ) + 0 ( u ) + o ( v o + 0 ( 6 3= o ( t i n n ) + o ( i c n n ) + o ( t i c n n n ) + q ( 互i 幽其中，乃是本文算法总的迭代次数，是样本数目，c 是样本的类数。比较3 2 节文献【9 】给出的算法的时间复杂度为：t = 0 ( q ) + 0 ( 叻+ o ( 叨+ 0 = 0 ( z 州奶+ o ( t 2 c n n 聊+ o ( t 2 c n 聊+ g 曼鲤噬殴其中，乃是文献【9 】的算法总的迭代次数。加下划线的部分分别是本文算法及文献【9 】的算法的目标函数的时间复杂度，从中我们可以容易看出本文算法的优点：i 、本文的目标函数的时间复杂度明显比文献【9 】的目标函数的时间复杂度来的优，其时间复杂度是o ( z 训聊，而文献【9 】的时间复杂度是o ( t 2 c n n n ) 。2 、本文算法的整体运行时间乃要比文献【9 】的算法的整体运行时间乃小，即瓦c 疋，这可以从本文第五章的实验得到验证。3 、当样本点的数目嘶艮大时，算法的优势将更加明显。所以，本文提出的以类心的核距离为目标函数的方法可以的提高算法收敛的速度，从而大大减少算法整体运行的时间。4 6 本章小结本章在现有离群模糊核聚类算法的基础上，通过对初始化参数的选择和聚类目标函数的选择的分析，提出了一种改进的离群模糊核聚类算法。本文就如何初一种改进的离群模糊核聚类算法始化算法参数进行了比较研究，表明用类心作为算法的初始化的有效性。并提出了一种新的聚类目标函数采用核空间的类心的距离，即类心的核距离作为聚类的目标函数，该方法能很大的提高算法的收敛速度，从而大大减少算法整体的运行时间。算法通过m e r c e r 核把原来的数据空间映射到特征空间，并为特征空间的每个向量分配一个动态权值，在特征空间内的得到一个全新的聚类目标函数，通过对该目标函数的优化，最终得到了各个数据的权值，根据权值的大小标识出样本集中的离群点。改进的算法在时间复杂度上明显要比文献【9 】的算法来优，能大大的提高算法的效率。第五章实验与结果分析第五章实验与结果分析为了测试本文提出的改进算法的性能，分别用三种方法对线性可分、线性不可分以及商维的数据样本集进行测试。算法一、改进的算法，以类心作为初始化，以g 作为目标函数；算法二、改进的算法，以类心作为初始化，以j 作为目标函数；算法曼、文献【9 】的算法，以隶属度作为初始化，以，作为目标函数。经过实验统计比较可以看出改进的模糊核聚类算法对这三种数据样本集都能取得令人满意的结果。5 1 不同核函数的比较分析核方法的基本思想就是用非线性变换) 把输入模式空间月映射到一个高维特征空间月e ，用核函数代替内积运算。针对不同的数据集，算法要选取不同的核函数。本节对如何选取核函数进行讨论分析，核函数分别为高斯核函数k e x p ( 一i i x y f r 0 2 ) 以及多项式核函数置= ( x y + 6 ) 。本节中算法的初始化方法如下：1 、文献f 9 1 的算法使m a t l a b 中的函数m i l f e m 对隶属度进行初始化；2 、改进的算法选取样本集的前c 个样本点对类心进行初始化。5 1 1 对仿真数据的聚类实验1 ：采用了一个线性可分的样本集，数据分布如图5 1 所示。该样本集由手动生成，共含有1 0 0 个样本，分为两类，第一类5 5 个样本，第二类4 5 个样本，每个样本2维。一、采用商斯核函数算法一：参数选取为m = 2 ，q = 0 1 ，c = 2 w = 2 0 0 ，口2 - 3 ，f - 1 0 - 4 。随机做1 0 0 次实验，其中一次实验结果见图5 2 。其中一次实验结果见图5 2 。一种改进的离群模糊核聚类算法图5 1 一个线性可分的数据样本集图5 2 聚类效果以及根据等权线发现离群点的结果翻图5 1 3 显示了隶属度的曲线图，图中红色曲线是代表“。的曲线，即样本点以属于第1 类的程度；绿色曲线是代表n ：。的曲线，即样本点赡属于第2 类的程度。图5 4 显示了算法目标函数收敛的门限的变化以及算法的迭代次数。图5 3 隶属度的曲线圈图5 4 门限判断和迭代次数算法三：参数选取为m - - - - 2 ，q = 0 1 ，c = 2 ，w = 2 0 0 ，仃2t3 ，s 一1 0 4 。随机做1 0 0 次实验，其中一次实验结果见图5 5 。图5 6 显示了算法目标函数收敛的门限的变化以及算法的迭代次数。w h - m t n 啪图5 5 聚类效果以及根据等权线图5 6 门限判断和迭代次数发现离群点的结果图三种算法进行统计结果比较：第五章实验与结果分析2 l表5 1 实验1 高斯核函数统计结果比较二、采用多项式核函数算法一：参数选取为m = 2 ，d = 2 ，b = l ，q = l ，c = 2 ，w = 2 0 0 ，一1 0 。4 。随机做1 0 次实验，其中一次实验结果见图5 7 。图5 8 显示了隶属度的曲线图，图中红色曲线是代表“2 七的曲线，绿色曲线是代表u ，。的曲线。2 l r 咭一、占f 1 弓一一0 i *_ 11。一力1 0 0图5 7 采用多项式核函数的聚类结果图5 8 隶属度的曲线图从图5 8 可以看出，对于实验1 中给出的线性可分的数据集，应采用高斯核函数，不适合采用多项式核函数。实验2 ：采用了一个线性不可分的样本集，数据分布如图5 9 所示。该样本集由手动生成，共含有3 5 0 个样本，分为两类，第一类1 4 6 个样本，第二类2 0 4 个样本，每个样本2 维。一、采用多项式核函数算法一：参数选取为m = 2 ，d = 2 ，b = l ，q = l ，c = 2 ，w = 4 0 0 ，g ：1 0 。随机做1 0 0 次实验，其中一次实验结果见图5 1 0 。一种改进的离群模糊核聚类算法图5 9 一个线性不可分的数据样本集d6o 一15 50 0 5152 75x图5 1 0 聚类效果以及根据等权线发现离群点的结果圈图5 1 1 显示j 隶属度的曲线图，图中红色曲线是代表的曲线，即样本点t 属于第l 类的程度：绿色曲线是代表h ：。的曲线，即样本点属于第2 类的程度。图5 1 2 显示了算法目标函数收敛的门限的变化以及算法的迭代次数。m 州呻脚t n h - t 嗍一”图5 1 l 隶属度的曲线图图5 1 2 门限判断和迭代次数算法三：参数选取为m = 2 ，d = 2 ，厶= 1 ，q = l ，c = 2 ，w = 4 0 0 ，- 1 0 - 4 。随机做1 0 0 次实验，其中一次实验结果见图5 1 3 。图5 1 4 显示了隶属度的曲线图，图中红色曲线是代表“。的曲线，绿色曲线是代表l 。的曲线。图5 1 3 聚类效果以及根据等权线发现离群点的结果图三种算法进行统计结果比较；图5 1 4 隶属度的曲线图蓊一、甘，_一，：0、一一馁一第五章实验与结果分析表5 2 实验2 采用多项式核函数统计结果比较二、采用高斯核函数算法一：参数选取为m = 2 ，q = l ，c = 2 ，w = 4 0 0 ，仃2 = 1 5 ，- 1 0 。4 。随机做1 0 次实验。其中一次实验结果见图5 1 5 。图5 1 6 显示了隶属度的曲线图，图中红色曲线是代表“，。的曲线，绿色曲线是代表h ：。的曲线。寻” 。j ；i ，。图5 1 5 采用高斯核函数的聚类结果图5 1 6 隶属度的曲线图算法三：参数选取为m = 2 ，q = l ，c = 2 ，w = 4 0 0 ，口2 1 5 ，一1 0 r 4 。随机做1 0 次实验，其中一次实验结果见图5 1 7 。图5 1 8 显示了隶属度的曲线图，图中红色曲线是代表：。的曲线，绿色曲线是代表“。的曲线。图5 1 7 聚类效果以及根据等权线图5 1 8 隶属度的曲线图发现离群点的结果图一种改进的离群模糊核聚类算法三种算法进行统计结果比较表5 3 实验2 采用商斯核函数统计结果比较所以。对于实验2 中给出的线性不可分的数据集，可以采用高斯核函数，也可以采用多项式核函数，但采用线性核函数在时间复杂度上比采用高斯核函数优。5 1 2 对真实世界中的数据聚类实验3 ：好的聚类算法还要能对离维的、真实世界中的数据进行聚类。作为一个例子，我们对真实世界中相对简单的而且在分类实验中人们经常用到的四维i r i s 数据进行了聚类。i r i s 数据是提取三种不同类别花的花瓣和花萼的特征所构成的特征向量。共含1 5 0 个样本，分为三类，每类各5 0 个样本，每个样本4 维( 第一维是花萼的长度，第二维是花萼的宽度，第三维是花瓣的长度，第四维是花瓣的宽度) 。图5 1 9 显示了该数据样本集的分布( 根据数据的前两维画出) 。一、采用高斯核函数算法一：参数选取为m = 2 ，q = l ，c = 3 ，w = 2 0 0 ，盯2 3 ，- 1 0 。随机做1 0 0 次实验，其中一次实验结果见图5 2 0 ，图中的数字和箭头标明的点是聚类错误的g ! c ( 1 1 个) 。- _ _ m _ _ _ - - - - ，x图5 1 9i r is 数据集憎+ 。o 、。：0 ：南图5 2 0 聚类效果以及聚类错误点的结果图第五章实验与结果分析图5 2 1 显示了隶属度的曲线图，图中红色曲线是代表“。的曲线，即样本点以属于第l 类的程度；绿色曲线是代表h ：。的曲线，即样本点砟属于第2 类的程度；蓝色曲线是代表“。的曲线，即样本点也属于第3 类的程度。图5 2 2 , 显a 示了算法目标函数收敛的门限的变化以及算法的迭代次数。_ b h * _。! 仁三j 二一- - 一1。二j4和1 wr 一一一“：b 盈，j 查。型图5 2 1 隶属度的曲线圈图5 2 2 门限判断和迭代次数算法三：参数选取为掰= 2 ，q = l ，c = 3 ，w = 2 0 0 ，a 2 3 ，。1 0 。随机做1 0 0 次实验，其中一次实验结果见图5 2 3 ，图中的数字和箭头标明的点是聚类错误的点( 1 2 个) 。图5 2 4 显示了算法目标函数收敛的门限的变化以及算法的迭代次数。一：竺竺竺竺，一。 lj。f 1m 1lj* i1卜i ：一f 护 ：图5 2 3 聚类效果以及图5 2 4 门限判断和迭代次数聚类错误点的结果图三种算法进行统计结果比较：表5 4 实验3 采用高斯核函数统计结果比较二、采用多项式核函数p、nv鼍一种改进的离群模糊核聚类算法参数选取为m = 2 ，d = 2 ，6 = 1 ，验，其中一次实验结果见图5 2 5 。图5 2 6 显示了隶属度的曲线图，代表“。的曲线。w b b45 iq = l ，c = 2 ，w = 2 0 0 ，s = 1 0 。4 。随机做1 0 次实图中红色曲线是代表“：。的曲线，绿色曲线是1 一05l一一。 一；，；南a ! f 虱酬6 l 二三：益澎剖图5 2 5 采用多项式核函数的聚类结果图5 2 6 隶属度的曲线图从图5 2 5 、5 2 6 可以看出，对于实验3 中给出的i r i s 数据集，应采用高斯核函数，不适合采用多项式核函数。算法对核函数的选取较为敏感，不同的数据集应采用相应的核函数，但如何正确的选取核函数，文中还只是采用试探的方法，核函数优选的方法有待探讨和研究。以上的三个实验可以说明，本文提出的改进算法比参考文献的算法在迭代次数和运行时间方面都来的优，是一种有效的聚类方法。从表5 1 、5 2 、5 3 、5 4 我们可以看出，文献【9 】的算法的迭代次数出现了波动，造成了算法在运行时间上也有很大的波动，这是因为它是以隶属度u 作为初始化参数，如果，初始化的好的话，迭代的次数和运行时间就小，反之就大。改进的算法是取样本点的前c 个点作为样本空间的初始化类心，所以比较稳定，很少产生迭代次数和运行时间的波动。下面我们就对算法初始类心的选择作一下探讨，说明改进算法的有效性。5 2 初始点的选取对算法灵敏度的分析实验4 ：本文4 1 节已经对初始化参数选择的问题进行了探讨，指出以类心作为初始化参数的明显优势，下面我们给出三种初始化类心参数的方法对实验3 中的i r i s 数据进行测试，然后对这三种方法进行比较，分析算法对初始点选取的灵敏度。三种初始化类心参数的方法如下：1 、选取样本的前三个点；第而章实验与结果分析2 、利用m a t l a b 的f c m 算法得到的三个类心；3 、任意选取样本的三个点；其中，利用m a t l a b 的f c m 聚类算法得到的三个类心为：阼【5 j d 0 3 63 4 0 31 4 8 50 2 5 1 5 4 ；6 7 7 4 93 0 5 2 45 6 4 6 72 0 5 3 5 ；5 8 8 92 7 6 1 24 3 6 41 3 9 7 3 ； ；任意选取样本的三个点为：怍【4 8 0 0 03 0 0 0 01 4 0 0 00 1 0 0 0 ；5 7 0 0 02 8 0 0 04 5 0 0 01 3 0 0 0 ；7 3 0 0 02 ，9 0 0 06 3 0 0 01 8 0 0 0 ；1 ；算法采用高斯核函数，参数选取为m = 2 ，q = l ，c = 3 ，w = 2 0 0 ，仃2 ：3 ，s ；1 0 _ 4 。三种初始化的类心如图5 2 7 、5 2 8 、5 2 9 所示，其中初始点用黑色+ 表示。- “h 一- e 啪t - - h 一氍姗图5 2 7 选取前三个样本煮4 5s 5657l 5x图5 2 8f c m 算法得到的三个类心x图5 2 9 任意选取样本中的三个点随机做1 0 次实验，比较结果如下：表5 5 实验4 初始点的选取对算法灵敏度的比较| i 一一一oo一种改进的离群模糊核聚类算法任意选取样本中的三个点1 1 484 1 2 5 0从表5 5 可以明显看出，采用本文的方法，可以利用现有各种聚类算法得到的结果，用得到的类心作为算法的初始化类心，能大大提高算法的速度，减少算法的迭代次数和算法运行的时间。5 3u - 图分析根据改进的离群模糊核聚类算法，我们得到了样本隶属度u 和离散权值w o离群模糊核聚类算法的目标是对普通数据样本分配一个小权值w k ( 就大) ，而坼一般地，离群点将远离任何一个类中心，从而分配一个大权值m ( 就小) 。权域重常量w 和权重指数q 在聚类过程中起到重要的作用。我们可以借助，_ 矿图对参数w 和q 进行分析，研究w 、q 值的变化对聚类结果的影响。对w 、q 的分析如下：一、权重常量w 的变化对聚类结果的影响f 妻”级r从式( 4 1 2 ) ，即w k = j 旦r w ，并结合式( 4 4 ) ( 4 - 1 3 ) 可以很显然看羹f 弘”级r出，样本点以的权重系数m 是权重常量w 的增函数。二、权重指数q 的变化对聚类结果的影响从式( 4 1 2 ) 也可以显然看出：当q m 时，每个数据样本的权重值将趋近于导，也就是说，权重对于所有的样本都有相同的影响；当4 0 时，权重影响将达到最大：非离散点获得更小的权重，离散点获得更大的权熏。所以，权熏常量w 和权重指数霉可以控制聚类结果中样本点的权重系数，专家可以通过设定w 、4 的值来有效的控制离散点的数量和分布，针对感兴趣数据点进行分析研究。为了说明和简化问题，我们采用实验1 的线性可分的数据集，该数据集的样本分布如图5 1 所示。实验采用高斯核函数，参数按照指定的选取。画出隶属度u 。和的图，图中点的标号为样本点的序号。通过卜讳徊我们能比较直观的看出权重常量w 以及权重指数q 对权重系数m 的影响，并对上面的分析进行验证。5 3 1 权重常量w 的变化对结果的影响1 、当w = 1 5 0 时：( c = 2 ，q = 1 ，盯2 = 3 ，肌= 2 )第五章实验与结果分析图5 3 0 当w = 1 5 0 时的u - w 图2 、当w = 2 0 0 时：( c = 2 ，q = 1 ，盯