（计算机应用技术专业论文）模糊聚类分析及其有效性研究.pdf

两南大学硕士学位论文摘要 模糊聚类分析及其有效性研究 计算机应用技术专业硕士研究生：孔攀 指导教师：邓辉文教授 摘要 聚类分析是非监督模式识别的一个重要分支，模糊聚类由于建立起了样本对于类别的不 确定性描述，更能客观地反映现实世界，从而成为聚类分析研究的主流。模糊聚类已经被广 泛应用于模式识别、数据挖掘、图像处理等许多领域。 本文的研究工作主要包括以下两个方面： 1 针对传统模糊核聚类算法没有考虑各维特征对聚类的不同贡献程度，以及易陷入局部 最优等缺点，提出一种改进的模糊核聚类算法。该算法构造了一个简单有效的适应度函数，结 合遗传算法全局搜索的优点，避免算法陷入局部最优。还为各维特征引入一个权系数，并利 用r e l i e f f 算法为特征加权。该算法比传统模糊核聚类算法有较大改进。实验结果表明了其有 效性。 2 提出一个新的模糊聚类有效性指标。该指标能确定由模糊c 均值算法得到的模糊划分 的最优划分和最优聚类数。该指标结合了模糊聚类的紧致性和分离性信息。用类内加权平方 误差和计算紧致性，用类间相似度计算分离性。在3 个人造数据集和3 个著名的真实数据集 上的对比实验证明了该指标的性能优于其它有效性指标。 全文共分五章，各章的内容分别为： 第1 章是引言。介绍了本文的研究背景和意义，指出论文的主要研究内容，并对全文结构 安排进行了简介。 第2 章是相关研究回顾及理论综述。较为详细的介绍了聚类分析以及模糊聚类算法的研究 现状和相关理论。 第3 章重点描述了一种改进的基于核函数的模糊聚类算法，并对算法的聚类效果进行了对 比实验和分析。 第4 章提出一个新的模糊聚类有效性指标( c ) ，并把新指标和现有指标在6 个数据集上进 行了对比实验。 第5 章是全文的结束语，包括对现有工作的总结和对未来工作的展望。 关键词：模式识别模糊聚类聚类有效性 西南大学硕士学位论文 a b s t r a c t r e s e a r c ho nf u z z yc l u s t e r i n g a n a l y s i sa n d i t sv a l i d i t y m a j o r ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g i e s r e s e a r c hd i r e c t i o n ：a r t i f i c i a li n t e l l i g e n c e s u p e r v i s o r ：p r o f d e n gh u i w e n a u t h o r ：k o n gp a n ( 1 1 2 0 0 6 3 2lo o 0 0 6 7 ) a b s t r a c t c l u s t e ra n a l y s i si sa i li m p o r t a n tb r a n c ho fu n s u p e r v i s e dp a r e mr e c o g n i t i o n b e c a u s eo fh a v i n g e s t a b l i s h e dt h es a m p l et h a td e s c r i b e st h eu n c e r t a i n t yo fc a t e g o r i e s ，a n db e i n ga b l et or e f l e c tt h er e a l w o r l dm o r eo b j e c t i v e l y ，f u z z yc l u s t e r i n gh a sb e c o m et h em a i n s t r e a mo fc l u s t e ra n a l y s i ss t u d y f u z z y c l u s t e r i n gh a sb e e nw i d e l yu s e di np a t t e r nr e c o g n i t i o n ，d a t am i n i n g ，i m a g ep r o c e s s i n ga n dm a n y o t h e rf i e l d s t i r ec o n t r i b u t i o no ft h i sp a p e re x i s t si nt w oa s p e c t s ： s i n c et h et r a d i t i o n a lk e r n e lf u z z yc l u s t e r i n ga l g o r i t h md o e sn o tt a k ei n t oa c c o u n to ft h e r e s p e c t i v ec o n t r i b u t i o nm a d eb yd i f f e r e mf e a t u r e s ，a n di ta l s oh a sas h o r t c o m i n go fe a s i l yf a l l i n gi n t o as i t u a t i o no fal o c a lo p t i m u m , a ni m p r o v e dk e r n e lf u z z yc l u s t e r i n ga l g o r i t h mi sp u tf o r w a r d c o m b i n gt h ea d v a n t a g eo ft h ee 乒o b a lo p t i m u mt h a tt h eg e n e t i ca l g o r i t h mt h ei m p r o v e dk e r n e lf u z z y c l u s t e r i n ga l g o r i t h mc o n s t r u c t sas i m p l ea n de f f e c t i v ef i t n e s sf u n c t i o nt h a tc a l la v o i dp l u n g i n gl o c a l o p t i m u m t h i si m p r o v e da l g o r i t h mg i v e se v e r yf e a t u r eaw e i g h t e dc o e f f i c i e n t , i nw h i c ht h er e l i e f f a l g o r i t h mi su s e dt oa s s i g nt h ew e i g h t sf o re v e r yf e a t u r e c o m p a r i n gw i t ht h et r a d i t i o n a la l g o r i t h m , t h i so l l eh a sm a d es o m es i g n i f i c a n tp r o g r e s s e s ，a n dt h ee x p e r i m e n t a lr e s u l th a sp r o v e di t s e f r e c t i 、j = e n e s s an e wc l u s t e rv a l i d i t yi n d e xi sp r o p o s e dt h a td e t e n - n i n e st h eo p t i m a lp a r t i t i o na n do p t i m a l n u m b e ro fc l u s t e r sf o rf u z z yp a r t i t i o n so b t a i n e df r o mt h ef u z z yc - m e a n sa l g o r i t h m t h ep r o p o s e d v a l i d i t yi n d e xc o m b i n e sc o m p a c t n e s sm e a s u r ea n ds e p a r a t i o nm e a s u r eb e t w e e nc l u s t e r s t h e c o m p a c t n e s sm e a s u r ei so b t a i n e db yc o m p u t i n gi n t e r - c l u s t e rw e i g h t e dt h es q u a r eo fe r r o r t h e s e p a r a t i o nm e a s u r ei so b t a i n e db yc o m p u t i n gs i m i l a r i t yb e t w e e nf u z z yc l u s t e r s i n t h et h r e e s y n t h e t i c a ld a t a s e t sa n dt h r e ew e l l - k n o w nr e a ld a t a s e t st h ee x p e r i m e n tp r o v e dt h a tt h ep r o p o s e d i n d e xi ss u p e r i o re f f e c t i v e l yi nc o m p a r i s o nt oo t h e ri n d e x e s f u l lt e x ti sd i v i d e di n t of i v ec h a p t e r s ，e a c hc h a p t e ri sa sf o l l o w s ： i l 两南大学硕士学位论文a b s t r a c t c h a p t e r1 i st h e i n t r o d u c t i o nt h a tg i v e st h er e s e a r c hb a c k g r o u n da n ds i g n i f i c a n c e ，b r i e f l y p r e s e n t i n gt h em a i ns c o p eo ft h i sr e s e a r c ha n di t ss t r u c t u r a la r r a n g e m e n t s c h a p t e r2i st h el i t e r a t u r er e v i e wt h a tl o o k sb a c ka tt h es t a t u sq u oo ft h ec l u s t e ra n a l y s i sa n d f u z z yc l u s t e r i n ga l g o r i t h mr e s e a r c h ，a n dr e l a t e dt h e o r i e s c h a p t e r3f o c u s e so i la ni m p r o v e dk e r n e l - b a s e df u z z yc l u s t e r i n ga l g o r i t h m i ta l s oc o n d u c t sa c o m p a r a t i v ee x p e r i m e n ta n da n a l y s i so nt h ec l u s t e r i n ge f f e c to ft h e a l g o r i t h m c h a p t e r4p r o p o s e san e wv a l i d i t yi n d i c a t o ro ff u z z yc l u s t e r i n g ac o m p a r a t i v es t u d yo ft h en e w i n d i c a t o ra n de x i s t i n gi n d i c a t o ri sa l s oc o n d u c t e di nt h es i xd a t as e t s c h a p t e r5i st h ec o n c l u d i n gp a r to ft h i st h e s i s i tp r e s e n t sas u m m a r yo ft h ec u r r e n tr e s e a r c ha n d i t sp r o s p e e t k e y w o r d s ：p a t t e r nr e c o g n i t i o n ，f u z z yc l u s t e r i n g ，c l u s t e r i n gv a l i d i t y i i i 独创性声明 学位论文题目： 搓塑鐾类佥堑丞基查夔丝叠窒 本人提交的学位论文是在导师指导下进行的研究工作及取得的 研究成果。论文中引用他人已经发表或出版过的研究成果，文中己加 了特别标注。对本研究及学位论文撰写曾做出贡献的老师、朋友、同 仁在文中作了明确说明并表示衷心感谢。 _ l ，上 学位论文作者：孔攀签字日期：7 , - 口。7 年q - 月2f 日 学位论文版权使用授权书 本学位论文作者完全了解西南大学有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅。本人授权西南大学研究生院( 筹) 可以将学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书，本论文：翻不保密， 口保密期限至年月止) 。 学乎论文作者张舢警 签字日期：弘。( 年争月叫日 导师签名： 仍移 签字日期：砂勺年j 月j - j 日 | 西南大学硕士学位论文第1 章引言 1 1 相关研究背景和意义 第1 章引言 模式识别( p a t t e r nr e c o g n i t i o n ) 是2 0 世纪6 0 年代初迅速发展起来的、与高技术的研究开发 有着密切联系的- - i - j 新兴学科【1 】。它所研究的理论和方法在很多科学和技术领域中得到了广 泛的应用，推动了人工智能系统的发展，扩大了计算机应用的领域，在向人类智能逼近这一 永恒的前沿课题中占有一席之地。在高度智能化、自动化的今天，模式识别几乎已经进入人 类生活的各个领域。形象地讲，模式识别是指从待识别的对象中分辨出哪个对象与标本相同 或相似。显然，分类( c l a s s i f i c a t i o n ) 是建立和识别模型的重要基础和手段，因此模式识别与分 类是密切相关的。此外，任何一门学科都要通过分类来建立自己的概念，也要通过分类来发 现和总结规律。这样，做为一种强有力的工具，分类研究具有十分重要的意义。模式识别或 者模式分类可分为有监督的分类和无监督的分类两种类型【2 】。有监督的分类中，已知模式的 类别和某些样本的类别属性，首先用具有类别标记的样本对分类系统进行学习或训练，使该 分类系统能够对这些已知样本进行正确分类，然后用学习好的分类系统对未知的样本进行分 类。这就要求我们对分类的问题有足够的先验知识，而要做到这一点，往往要付出相当大的 代价，有时甚至是不可能的。 无监督的分类又称为聚类分析，就是按照一定的要求和规律对事物进行区分和分类的过 程，在这一过程中没有任何关于分类的先验知识，仅靠事物间的相似性作为类属划分的准则， 使相似的样本尽可能归为一类，而不相似的样本尽量划分到不同的类中。聚类是一个古老的 问题，它伴随着人类社会的产生和发展而不断深化，人类要认识世界就必须区别不同的一事 物并认识事物间的相似性i 传统的聚类分析是一种硬划分，它把每个待辨识的对象严格地划分到某类中，具有“非 此即彼”的性质，因此这种类别划分的界限是分明的【3 】。而实际上大多数对象并没有严格的 属性，它们在性态和类属方面存在着中介性，具有“亦此亦彼”的性质，因此适合进行软划 分。1 9 6 5 年，美国自动控制专家、数学家扎德( l a z a d e h ) 发表了他的论文模糊集( f u z z y s e t s ) ，提出了模糊集理论，把模糊性和数学统一在了一起 4 1 。1 9 6 9 年，r u s p i n i 率先提出了 模糊划分的概念【5 】，以此为起点和基础，模糊聚类理论和方法迅速蓬勃发展起来。模糊集理 论和方法的发展为聚类分析的软划分提供了有力的分析工具，人们开始用模糊的方法来处理 聚类问题，并称之为模糊聚类分析。由于模糊聚类得到了样本属于各个类别的不确定性程度， 表达了样本类属的中介性，即建立起了样本对于类别的不确定性描述，更能客观地反映现实 世界，从而成为聚类分析研究的主流。 虽说聚类分析应用于模式识别的时间不长，但它并非一个新领域，旱已被应用在其他学 西南大学硕士学位论文第1 章引言 科中。d u b e s 和j a i n 关于聚类分析的综述包括了从7 7 份杂志和4 0 本书中摘取出来的2 5 0 条引 文，如此巨大的文献量说明了聚类分析的重要性的交叉学科性，也足以说明它的发展及应用 前景的广阔性【2 】。 同时，国际和国内的学者都对聚类分析研究非常重视，i e e e 的汇刊中 p a t t e r na n a l y s i sa n d m a c h i n ei n t e l l i g e n c e ) ) 、 s y s t e m s ，m a n ，a n dc y b e r n e t i c s ) ) 、 f u z z ys y s t e m s ) ) 、 n e u r a ln e t w o r k s ) ) 、 s i g n a lp r o c e s s i n g ) ) 等杂志中几乎每期都有讨论聚类分析问题的文章。 此外，从1 9 9 2 年开始的由i e e e 和神经网络理事会共同主办的f u z z i e e e 会议，每两年 召开一次，每次至少有3 到4 个专题讨论聚类的模糊聚类分析的最新研究进展和发展现状。 随着理论的发展，模糊聚类已经有效地应用在数据挖掘、模式识别、图像处理、网络入 侵检测、大规模数据分析、决策支持等领域，并取得了满意的效果和可观的效益。其中，最 为成功的是在模式识别、数据挖掘和图像处理三个领域。 1 模糊聚类在模式识别中的应用 模式识别中一个最重要的问题是特征提取，b e z d e k 等人首先提出用模糊聚类进行特征选 优，模糊聚类不但能从原始数据中直接提取特征，还能对已经得到的特征进行优化和降维操 作，以免造成“维数灾难”；b e z d e k 等还利用模糊聚类来进行特征空间划分和模糊规则提取， 以构造基于模糊i f - t h e n 规则的分类器，实验结果证明该方法的有效性；在物体识别或线条 检测中，模糊聚类既可以直接作用于原始数据上，也可以用于变换域中，比如h o u g h 变换一 直受峰值检测的困扰，j o l i o n 提出基于模糊聚类的检测方法，解决了这一难题，使得h o u g h 变换可以自动执行，使用起来方便快捷1 2 。a n t o n i o 等用模糊聚类进行系统辨识，获得了优于 神经网络方法的结果。 此外，在一些具体的识别应用中，模糊聚类也取得了较好的效果，比如z h a n g 和吴佑寿 等人分别用模糊聚类做了汉字字符识别的预分类，得到了较好的分类效果；h u a n g 等在语音识 别中应用模糊聚类也获得了成功。 2 模糊聚类在数据挖掘中的应用 数据挖掘是知识发现过程中的重要步骤，是从大量的、不完全的、有噪声的、模糊的、 随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过 程。发现了的知识可以被用于信息管理、查询优化、决策支持、过程控制等，还可以用于数 据自身的维护。数据挖掘是一个新兴的多学科交叉应用领域，正在各行各业的决策支持活动 中扮演着越来越重要的角色。数据挖掘涉及多学科技术的集成，包括数据库技术、统计学、 机器学习、高性能计算机、模式识别、神经网络、数据可视化、信息检索、图象与信号处理 和空间数据分析【6 】。 数据挖掘对聚类分析的要求：可伸缩性强，能够处理各种级别和各种类型的数据对象： 能够处理空值、未知数据或错误数据等噪声数据；用于决定输入参数的领域知识最小化，聚 类结果对输入的参数很敏感，用户输入的参数直接决定了聚类的质量。 2 西南大学硕士学位论文 第l 章引言 由于现实的数据挖掘过程往往伴随着模糊性，所以用模糊聚类分析会显得更自然、更符 合客观实际。模糊聚类可以做为独立的数据挖掘工具或者作为其他数据挖掘算法( 如特征和分 类) 的预处理步骤。当前，模糊聚类己经成为数据挖掘领域一个非常活跃的研究课题。 在数据挖掘中，模糊聚类分析已经广泛地应用于金融领域，包括金融市场分析和预测、 客户分类、银行担保和信用评估等。利用模糊聚类分析对客户进行分类，阻止产生坏账，防 范金融欺诈，挖掘优质客户。在医药学数据挖掘中，应用较多的是用模糊聚类将中药进行分 类和鉴别。应用模糊聚类的方法还可以对引种品种的生物学特性、原产地的环境因素、气候 条件、土壤结构等各种信息进行处理，预测出异地栽培的产量和适应性，结合品种选育和种 植过程的模糊控制，可缩短异地栽培适应性研究的过程和时间。 3 模糊聚类在图像处理中的应用 图像处理是计算机视觉的重要组成部分。由于人眼视觉的主观性使图像适合用模糊手段 处理，训练样本图像的匮乏又需要无监督分析，而模糊聚类正好满足这两方面的要求，因此 成为图像处理中一个强大的研究分析工具。 模糊聚类在图像处理中最为广泛的应用是图像分割。由于图像分割问题恰好是将图像的 像素集进行分类的问题，于是人们很自然地将聚类分析用于图像分割之中。早在1 9 7 9 年 c o l e m a n 和a n d e r e w s 就提出用聚类算法进行图像分割 7 】。 p r e w i t t 首先提出了图像分割的模糊处理的方法【8 】。此后基于二维直方图 9 】、小波分析 【1 0 、分形分维等一系列新技术，人们又相继提出了多种基于模糊聚类的灰度图像分割新方法， 并且在纹理图像分割、遥感图像分割等方面也获得了很大的进展。此外，基于模糊聚类的方 法在边缘检测方面的研究同样也取得了丰硕的成果。 采用模糊聚类的方法进行图像分割的优点是避免了设定闽值的问题，并且能解决阈值化 分割难以解决的多个分支的分割问题；模糊聚类方法适合于图像中存在不确定性和模糊性的 特点：同时模糊聚类方法是属于无监督的分类方法，聚类过程中不需要任何人工的干预，很 适合于自动分割的应用领域。 由于模糊聚类的强大功能，使得它已经在众多的领域获得令人属目的成功，而且随着理 论的不断发展和完善，必将发挥更大的作用。同时，随着模式识别、数据挖掘和图像处理等 应用领域的发展，对模糊聚类理论又提出了新的要求，因此必须进一步丰富和完善聚类理论， 指导实际应用，使之更好地服务于人类。 1 2 本文的主要研究内容 本文的研究工作主要有以下几个方面： 1 针对传统模糊核聚类算法没有考虑各维特征对聚类的不同贡献程度，以及易陷入局部 最优等缺点，提出一种改进的模糊核聚类算法。该算法构造了一个简单有效的适应度函数，结 合遗传算法全局搜索的优点，避免算法陷入局部最优。还为各维特征引入一个权系数，并利 3 西南大学硕士学位论文 第1 芎引言 用r e l i e t f 算法为特征加权。并对算法的有效性进行了对比实验。 2 针对现有聚类有效性指标的缺点。提出一个新的模糊聚类有效性指标。该指标能确定 由模糊c 均值算法得到的模糊划分的最优划分和最优聚类数。该指标结合了模糊聚类的紧致性 和分离性信息。用类内加权平方误差和计算紧致性，用类间相似度计算分离性。并通过实验， 对新指标和其他有效性指标进行比较。 1 3 本文的结构安排 论文结构安排如下： 第1 章是引言。介绍了本文的研究背景和意义，指出论文的主要研究内容，并对全文结构 安排进行了简介。 第2 章是相关研究回顾及理论综述。较为详细的介绍了聚类分析以及模糊聚类算法的研究 现状和相关理论。 第3 章重点描述了一种改进的基于核函数的模糊聚类算法，并对算法的聚类效果进行了对 比实验和分析。 第4 章提出一个新的模糊聚类有效性指标( c ) ，并把新指标和现有指标在6 个数据集上进 行了对比实验。 第5 章是全文的结束语，包括对现有工作的总结和对未来工作的展望。 西南大学硕士学位论文第2 审相关研究同顾及理论综述 第2 章相关研究回顾及理论综述 本章将主要介绍本文中涉及到的一些基本理论及其研究进展，包括聚类分析、模糊聚类、 模糊c 均值算法等。 2 1 聚类分析 2 1 1 聚类分析概述 聚类分析是多元统计分析中的一种，也是非监督模式识别的一个重要分支。“物以类聚， 人以群分”，聚类是一个古老的问题，它伴随着人类社会的产生和发展而不断深化，人类要认 识世界就必须区别不同的事物并认识事物间的相似性，而每个概念的最初形成无不借助于事 物的聚类分析。因此，聚类分析的研究不仅具有重要的理论意义，也具有重要的工程应用价 值和人文价值。 聚类就是将物理或抽象的对象，按照对象间的相似性进行区分和分类过程。在这一过程 中没有教师的指导，是一种无监督的分类，是将数据集划分为若干组或类的过程，并使得同 一个组内的数据对象具有较高的相似度，而不同组中的数据对象则是不相似的【3 】。相似或不 相似的度量是基于数据对象描述的取值来确定的，通常就是利用距离来进行描述。将一群物 理的或抽象的对象，根据它们之间的相似程度，分为若干组，其中相似的对象构成一组，这 一过程就称为聚类过程。一个聚类，或称为簇( c l u s t e r ) ，就是由彼此相似的一组对象所构成的 集合，不同聚类中对象通常是不相似的。 聚类分析是一种数据划分或分组处理的重要手段和方法，从给定的数据集中搜索数据对 象之间所存在的有价值联系，其操作的目的在于将特征空间中一组没有类别标志的矢量按某 种相似性准则划分到若干个子集中，使得每个子集代表整个、某个或某些特征和性质。 聚类分析已经被广泛应用到许多领域中，包括模式识别、数据挖掘、图像处理以及市场 研究等。在商务上，聚类能够帮助市场分析人员从客户基本库中发现不同的客户群；在生物 学上，聚类用于推导植物和动物的分类，对基因进行分类：聚类也能对w e b 上的文档进行分 类，以发现信息。 2 1 2 聚类分析的数学模型 从数学角度来刻画聚类分析问题，可以得到如下的数学模型。设x = 扛。，x 2 ，矗 是待 聚类分析的对象的全体( 称为论域) ，x 中的每个对象( 称为样本) x 。( 尼= 1 , 2 ，刀) 常用有限个 5 西南大学硕士学位论文第2 章相关研究回顾及理论综述 参数值来刻画，每个参数值刻画五的某个特征。于是对象x i 就伴随着一个向量 p ( x i ) = ( x k l ) x 膏2 ，) ，其中工灯( 歹= 1 , 2 ，s ) 是在第_ ，个特征上的赋值，p ( x i ) 称 为以的特征向量或模式矢量。聚类分析就是分析论域x 中的聆个样本所对应的模式矢量间的 相似性，按照各样本间的亲疏关系把，工2 ，z 。划分成多个不相交的子集置，x 2 ，x 。， 并要求满足下列条件： x lu y 2 ux 。= x ，x fnx ，= 1 f j c 样本扎( 1 k ，1 ) 对子集x f ( 1 f c ) 的隶属关系可用隶属函数表示为 哪。- , g r - 暴之，嚣 其中，隶属函数必须满足条件谊e 。也就是说，要求每一个样本能且只能隶属于某一类， 劂时要求每个子集都是非空的。因此，通常称这样的聚类分析为硬划分。 fi c玎 、 e 2 p 膻卜髓 o ，1 ) 善趾“，v j j ；o 否以 n , v i t 2 。j ) r u s p i r t i 利用模糊集理论把样本的隶属函数盹从 o ，1 ) 二值扩展到【o ，1 】区间，从而把硬 划分推广到模糊划分。在模糊划分中，样本集x 被划分成c 个模糊子集置，舅：，j 。，满足 条件： e ，： 腑l 心 o ，1 ；童心：1 ，v 枷 窆让矗v f l ( 2 - 2 ) l1 i = lk - i j 对于模糊划分，如果放宽概率约束条件t t = 1 ，v k ，则模糊划分演变为可能性划分。显然， 对于可能性划分，每个样本对各个划分子集的隶属度构成的矢量 “t = “舭“2 女，“捩，“政 r 在c 维实空间中单位超立方体内取值，即 e ，= 函，尺。i “诸【o ，1 ，v f ，k 而模糊划分e 的取值范围为c 维空间中过c 个单位基矢量的超平面，即 6 西南大学硕士学位论文第2 章相关研究同顾及理论综述 b = p ，e ，l 喜擅= ，v 尼) 如此，硬划分e 只能在单位超c 立方体的c 个单位基矢量上取值。 e = 讧，ee ii 髓 o ，1 ) 2 1 3 聚类方法的分类 迄今，人们已经提出了各种各样的聚类方法。通常聚类的方法大致可以分为以下几类： 基于划分的方法、基于分层的方法、基于密度的方法、基于网格的方法和基于模型的方法。 2 1 3 1 基于划分的聚类方法 基于划分的方法是最常用的聚类方法类型，本文亦主要是针对此类算法进行讨论。基于 划分的聚类方法也叫做基于目标函数的聚类算法。它一般是通过优化一个评价聚类效果的目 标函数，把目标函数取得极值下的划分作为聚类的结果。这类方法首先把数据集分割成k 个 部分并创建一个初始划分，然后利用循环迭代的重定位技术，通过将对象从一个划分移到另 一个划分来改善划分质量，直到目标函数取得极值。般来说，一个好的评价聚类效果的划 分准则是：在同一个类中的对象之间尽可能的接近或相关，而不同的类中的对象之间尽可能 的远离或不同。当然还有许多其他划分质量的评判准则 1 1 3 。 划分聚类法的效率比较高，但聚类前要预先知道聚类的数目，绝大多数划分方法是基于 数据对象之间的距离进行聚类的，这样的方法只能发现球状的或凸形的聚类，而在发现任意 形状的聚类上遇到了困难，并且初始划分的不同选择对聚类的效率有很大影响，往往可能得 到不同的聚类结果【1 1 】。典型的基于划分的聚类方法包括：k - m e a n s ，k - m e d o i d s ，k - m o d e 等。 ( 1 ) k - m e a n s k - m e a n s 也叫硬c 均值聚类算法。在该算法中，每个簇用该簇中对象的平均值来表示。首 先，随机地选择k 个对象，每个对象初始地代表了一个簇的平均值或中心。对剩余的每个对 象，根据其与各个簇中心的距离将它赋给最近的簇。然后重新计算每个簇的平均值。这个过 程不断重复，直到准则函数收敛。k - m e a n s 算法的缺点是对于脏数据和孤立点很敏感。 ( 2 ) k - m e d o i d s k - m e d o i d s 对k m e a n s 算法的缺点进行了改进。在k m e d o i d s 中，每个簇用接近聚类中 心的一个对象来表示。它首先为每个簇随意选择一个代表对象，剩余的对象根据其与代表对 象的距离分配给最近的一个簇，然后反复地用非代表对象来代替代表对象，以改进聚类的质 量。k m e d o i d s 算法对于脏数据和孤立点不敏感，但计算量要比k - m e a n s 要大，一般只适 合小数据量。 划分聚类法大多为启发聚类方法，为了获得基于划分的聚类分析的全局最优结果就需要 7 西南大学硕：卜学位论文第2 章相关研究回顾及理论综述 穷举所有可能的对象划分。这些启发聚类方法在分析中小规模数据集以发现圆形或球状聚类 时工作得很好，但为了使划分算法能够分析处理大规模数据集或复杂数据类型，就需要对其 进行扩展，如k - m o d e 就是从k - m e a n s 扩展而来以能对目录属性的数据进行聚类。为了使聚 类结果更加符合实际，人们又将k - m e a n s 算法和模糊数学理论相结合，提出了模糊c 均值 ( f c m ) 算法。然而，模糊c 均值聚类算法也存在着许多不足之处，如易于陷入局部最小、对初 始值较敏感及不能处理噪声数据等问题，其寻优能力有待进一步提高。为此，研究者们又陆 续提出了许多改进方法，有的是基于加权的思想，有的是基于遗传算法、克隆选择及人工免 疫等的生物学理论技术上的思想，还有的是基于可能性理论。本文还将在下一节中对此类算 法做具体、重点地阐述。 2 1 3 2 基于分层的聚类方法 分层聚类法是由不同层次的分割聚类组成，层次之间的分割具有嵌套关系，通过将数据 组织成若干组并形成一个相应的树状图来进行聚类。分层聚类方法对给定的数据对象集合进 行层次的分解，根据层次的分解如何形成，可以分为凝聚的和分裂的两种。凝聚的方法，也 称自底向上的方法，一开始将每个对象作为单独的一个组，然后相继的合并相近的对象或组， 直到所有的组合并为一个( 层次的最上层) ，或者达到某个要求的终止条件。分裂的方法，也称 为自项向下的方法，一开始将所有的对象置于一个簇中。在迭代的每一步中，一个簇被分裂 为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件。分层聚类方法 的缺陷在于，一旦一个步骤( 凝聚或分裂) 完成，它就不能被撤销，这个严格规定是有用的，由 于不用担心组合数目的不同选择，计算代价会比较小。 分层聚类法不必事先知道聚类的数目，基于模糊相似关系的模糊聚类就是这种聚类法， 如传递闭包法、最大树法、动态直接聚类法等。基于模糊相似关系的聚类算法对输入数据的 次序不敏感，能够发现任意形状的聚类，但往往计算量大，处理海量数据的聚类时效率较低。 典型的分层聚类法主要有b i r c h ，c u r e 和c h a m e l e o n 等。 ( 1 ) b i r c h b i r c h ( b a l a n c e di t e r a t i v er e d u c i n ga n dc l u s t e r i n gu s i n gh i e r a r c h i e s ) 是一个综合的分层聚 类方法。它引入了两个概念：聚类特征和聚类特征树( c f 树) ，它们用于概括聚类描述。这些 结构辅助聚类方法在大型数据库中取得高的速度和可伸缩性。b i r c h 方法对增量或动态聚类 也非常有效。b i r c h 方法可以动态地对输入数据进行聚类，可以处理数据的噪声，但它一般 只适用于聚类簇是球形的情况( 因为它用了半径或直径的概念来控制聚类的边界) ，而且对输入 数据的次序也比较敏感： ( 2 ) c u r e c u r e ( c l u s t e r i n gu s i n gr e p r e s e n t a t i v e s ) 采用了一种新颖的分层聚类法，该算法选择基于质 心和基于代表对象方法之间的中间策略。它不用单个质心或对象来代表一个簇，而是选择数 一8 一 西南大学硕士学位论文 第2 章相关研究同顾及理论综述 据空间中固定数目的具有代表性的点。c u r e 解决了偏好球形和相似大小的问题，在处理孤立 点上也更加健壮 ( 3 ) c h a m e l e o n c h a m e l e o n 是一个在分层聚类中采用动态模型的聚类算法。在它的聚类过程中，如果两个 簇间的互连性和近似度与簇内部对象间的互连性和近似度高度相关，则合并这两个簇。基于 动态模型的合并过程有利于自然的和同构的聚类的发现，而且只要定义了相似度函数就可应 用于所有类型的数据。 2 1 3 3 基于密度的聚类方法 密度聚类法是利用数据密度函数进行聚类。它根据数据对象周围的密度不断地增长聚类， 主要用于对空间数据的聚类。其主要思想是：只要临近区域的密度( 对象或数据点的数目) 超过 某个给定的值就继续聚类，也就是说对给定类中的每个数据点在一个给定范围的区域中必须 至少包含某个数目的点。该类方法最大的优点是可以发现任意形状的聚类，它的主要缺点是 对用户定义的参数非常敏感，不同的参数值可能对聚类的最终结果产生很大的影响，以至于 导致差别巨大的聚类结果，而且这些参数不好确定，常常带有很大的主观色彩，同时它也不 具有很好的伸缩性，因而算法效率不是很高。典型的基于密度的聚类方法包括d b s c a n 、 o p t i c s 和d e n c u 厄等。 ( 1 ) d b s c a n d b s c a n ( d e n s i t y b a s e ds p a t i a l c l u s t e r i n go fa p p l i c a t i o n sw i t hn o i s e ) 算法将具有足够高密 度的区域划分为簇，并可以在带有“噪声”的空间数据集中发现任意形状的聚类。它定义簇 为密度相连点的最大集合。d b s c a n 的缺点是仍然将选择能产生可接受的聚类结果的参数值 的责任留给了用户。 ( 2 ) d e n c l u e d e n c l u e ( d e n s i t y - b a s e dc l u s t e r i n g ) 算法根据数据点在属性空间中的密度来进行聚类。从 本质上讲，d e n c l u e 是基于密度的聚类算法与基于网格的预处理的结合，它受目标数据的维 度影响较小。 ( 3 ) o p t i c s o p t i c s ( o r d e r i n gp o i n t st oi d e n t i f yt h ec l u s t e r i n gs t r u c t u r e ) 算法没有显式地产生一个数据 集合簇，它为自动和交互的聚类分析计算一个簇次序( c l u s t e ro r d e r i n g ) 。这个次序代表了数据的 基于密度的聚类结构。它包含的信息，等同于从一个宽广的参数设置范围所获得的基于密度 的聚类。 2 1 3 4 基于网格的聚类方法 网格聚类法从对数据对象空间量化的角度出发，利用属性空间的多维网格数据结构，把 数据对象空间量化为有限数目的单元，以形成一个可以进行聚类分析的网格结构。所有的聚 9 西南大学硕士学位论文 第2 荦桐关研究同顾及理论综述 类操作都在这个网格结构( 即量化的空间) 上进行。这种方法聚类的处理时间独立于数据对象的 数目，只与量化空间中每一维的单元数目有关。这类聚类方法有快速的处理速度，对于大型 数据库中的高维数据的聚类非常有效，但网格的粒度与有关参数难于选择，这使得聚类的质 量和精确性往往受到影响。典型的有s t i n g ，c l i q u e ，w a v e c l u s t e r 等方法。 ( 1 ) s t i n g s t i n g ( s t a t i s t i c a li n f o r m a t i o ng r i d ) 是一种基于网格的多分辨率聚类方法，它将空间区域划 分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一 个层次结构：高层的每个单元被划分为多个低一层的单元。关于每个网格单元属性的统计信 息( 例如平均值、最大值和最小值) 被预先计算和存储。 ( 2 ) c l l q u e c l i q u e ( c l u s t e r i n gi nq u e s t ) 是一种基于密度和基于网格的混合聚类方法。c l i q u e 算法 可以自动标识高维空间的子空间，使得在该子空间中数据能够很好地聚类。所有搜索限制在 原始空间的子空间中，而不是引入新的维度，这有利于产生可解释的聚类结果。c l i q u e 对数 据输入顺序不敏感，无需假设任何规范的数据分布。它随输入数据的大小线性地扩展，当数 据维数增加时具有良好的可伸缩性，对于大型数据库中的高维数据的聚类非常有效。但 c l i q u e 算法不能自动去除数据集中的孤立点，需要增加额外的计算步骤去除孤立点，这就增 加了计算复杂性。此外，c l i q u e 算法采用固定划分网格的方法，这很容易破坏密集区域的边 缘，降低最终结果的准确性。 ( 3 ) w a v e c l u s t e r w a v e c l u s t e r 是一种多分辨率的聚类算法，它认为数据是多维信号，首先通过在数据空间 上强加一个多维网格结构来汇总数据，然后采用信号处理技术小波变换来变换原特征空间， 通过在变换后的空间中找到密集区域来识别聚类。w a v e c l u s t e r 可以有效的发现任何形状的聚 类，并可以处理噪声，它还对数据输入顺序不敏感。而且，它还适用于任何数值属性。 2 1 3 5 基于模型的聚类方法 基于模型的方法为每个类假定一个模型，寻找数据对给定模型的最佳拟合。一个基于模 型的算法可以通过构建反映对象空间分布的密度函数来定位聚类。它也基于标准的统计数字 自动决定聚类的数目，考虑“噪声”数据或孤立点，从而产生健壮的聚类方法。基于模型的 方法主要有两类：统计学方法和神经网络方法。 ( 1 ) 统计学方法 概念聚类是机器学习中的一种聚类方法，给出一组未标记的对象，它产生对象的一个分 类模式。概念聚类的绝大多数方法采用了统计学的途径，在决定概念或聚类时使用概率度量。 常用方法包括f i s h e r 提出的c o b w e b 和g e n n a r i 等提出的c l a s s i t 等。c o b w e b 是一种流 行的简单增量概念聚类算法，以一个分类数的形式创建层次聚类。它的输入对象用分类属性 一1 0 西南大学硕士学位论文第2 章相关研究同顾及理论综述 一值对来描述。c l a s s i t 是c o b w e b 的扩展，用以处理连续性数据的增量聚类。 ( 2 ) 神经网络方法 神经网络方法将每个簇描述为一