硕士学位论文-数据挖掘中的模糊聚类分析算法研究.doc

学校代码：10254 密 级： 论文编号： 上海海事大学SHANGHAI MARITIME UNIVERSITY硕士学位论文MASTER DISSERTATION论文题目：数据挖掘中的模糊聚类分析算法研究学科专业：计算机应用技术作者姓名：王 花指导教师：黄晓霞 副教授完成日期：二一年六月论文独创性声明本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其他机构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明并表示了谢意。作者签名： 日期：论文使用授权声明本人同意上海海事大学有关保留、使用学位论文的规定，即：学校有权保留送交论文复印件，允许论文被查阅和借阅；学校可以上网公布论文的全部或部分内容，也可以采用影印、缩印或者其他复印手段保留论文。保密的论文在解密后遵守此规定。作者签名： 导师签名： 日期摘要摘 要随着全球信息持续的增加，数据挖掘技术也应运而生，数据挖掘是一门交叉性学科，其中模糊聚类就是聚类分析与模糊集合理论相结合的产物。为了对数据进行聚类分析，研究者们提出了很多的聚类算法。其中模糊聚类算法（FCM）最具有影响力，由于它引入了模糊集的概念。模糊聚类分析是依据客观事物间的特征,亲疏程度和相似性，通过建立模糊聚类相似关系对客观事物进行分类的方法。相对于硬划分聚类算法而言，它可更好的对事物进行模糊划分，可对孤立点，成员关系等进行更好的处理，在实际生活中得到更好的应用。它最早起源是由于L.A.Zadeh在1965年创立了模糊集合论，随后Bellman和Kalabaff.Zadeh提出了用模糊集来处理聚类问题。在1969年，著名的学者E.H.Ruspin又引入了模糊划分的概念进行模糊聚类分析。第一个系统的表述并研究了模糊聚类。至今越来越多的学者将模糊聚类应用于各个领域，使得模糊聚类在运用于天气预报，气象分析，图像分割，模式识别，生物，医学诊断和化学分析等领域均时均取得了满意的效果和客观的效益。这也使得如何来判定一个模糊聚类算法的有效性成为了大家研究的焦点。本文通过对目前存在的一些主流有效性指标的研究发现其中存在一些不足。并提出了一种新的有效性指标。本文所做的改进与研究工作主要集中在以下几个方面：1. 对两个模糊聚类算法的算例分析比较。根据目前的模糊聚类算法，主要针对直接聚类法中的布尔矩阵法和间接聚类法中的最大树法进行比较研究。在比较中，应用了IRIS典型数据集进行计算。并分析最终结果产生的原因和它们的适用范围。2. 运用标准数据集IRIS，对当前主要的模糊聚类的有效性指标进行仿真实验。从中发现了一些有效性指标的优点和不足。3. 提出一种新的判定模糊聚类有效性指标Vnew。首先简单的介绍了目前主流的模糊有效性指标和一些改进后的有效性指标，对这些主流有效性指标进行研究，发现它们各自的优缺点。基于它们的缺点，本文提出了一种新的判定模糊聚类有效性的指标Vnew。并对新的指标进行了分析证明。证明新指标的稳定性。4. 提出了一种新的判定模糊聚类有效性算法。为了判定新指标的可靠性，本文提出了一种新的判定模糊聚类有效性算法。分别运用四个标准数据集对新算法进行实验仿真，能够有效的验证新指标的可靠性。实验表明，新指标具有较好的可靠性和判定性。关键字：数据挖掘，聚类分析，模糊聚类，聚类有效性ABSTRACTABSTRACTData mining technology has emerged for the continued increase information in global. Data mining is an overlapping subject; one of the data mining methods called fuzzy clustering is combined with fuzzy clustering and fuzzy mathematics. The searcher had proposed many of cluster methods for data classification. And the fuzzy clustering algorithm (FCM) the most influential, because it introduces the concept of fuzzy sets. Fuzzy clustering analysis is based on objective characteristics between things, the extent and closeness of fuzzy clustering similarity relations through the establishment of objective methods to classify things. Compared with the hard partition clustering algorithm, the better things it can be fuzzy partition, and can deal with the isolated point, members of the relationship better, and has a better application in real life. It originated because of L.A. Zadeh founded the fuzzy set theory in 1965, and then Bellman and Kalabaff Zadeh proposed clustering with fuzzy sets to deal with the problem. In 1969, the famous scholar E.H.Ruspin who is the first person described and research the fuzzy clustering has introduced the concept of fuzzy partition clustering analysis. More and more scholars have used the fuzzy clustering in many kinds of fields, makes the fuzzy clustering applied to weather forecasting, weather analysis, image segmentation, pattern recognition, biological, medical diagnostics and chemical analysis and both had satisfaction effectiveness and efficiency objective. This is why more and more researchers make the validity of a fuzzy clustering algorithm become the focus of their study. This article is based on the research of many major existing cluster validity indexes and a lot of advantages and disadvantages were found, and then proposed a new cluster validity index.This articles research work to improve focus on the following aspects:1. Two examples of fuzzy clustering algorithm analysis and comparison .Relation to the current fuzzy clustering algorithm mainly focus on the direct clustering method of Boolean matrix method and indirect method of maximum tree clustering methods comparison. And use the data set iris to compute the each method. At last compared the result and proposed the scope they can use.2. Use of standard data sets IRIS on the current validity of the main indexes of fuzzy clustering simulation. Found some indexes advantages and disadvantages.3. A new validity index Vnewwas given. During the simulation experiment made in the Xie-Beni validity index VXB found that when cn, then VXB (U, V, c) will also tend to 0 while the loss of ability to judge. For this shortcoming presents a new validity index, the index on the basis of the original added a penalty term, can well solve the problem. Demonstrated in this paper a new better determine new indicators and robustness.4. In order to determine the reliability of the new index, this paper gives a new algorithm for determining the effectiveness of fuzzy clustering. It can effectively verify the reliability of new indicators. Each data set using four criteria to test the new algorithm for simulation, can effectively verify the reliability of new indicators. Experiments show that the new index has good reliability and decidability. Improve the robustness of the algorithm.Keywords: Data Mining, Cluster Analysis, Fuzzy Clustering, Cluster validity目录目 录第一章 绪论11.1 研究背景11.2 数据挖掘技术11.3 本文研究工作11.4 论文结构1第二章 聚类分析与模糊聚类12.1 聚类分析12.2 聚类分析与模糊理论的结合12.3 模糊聚类分析的研究方向12.3.1 模糊聚类算法的改进12.3.2 模糊聚类算法的实现途径12.3.3 模糊聚类的应用研究12.3.4 模糊聚类的有效性研究12.4 HCM算法思想和基本步骤12.5 FCM算法思想和基本步骤12.6 本章小结1第三章 模糊聚类算法研究和算例分析比较13.1 引言13.2 模糊理论13.2.1 模糊集合的基本概念及运算13.2.2 模糊截集的概念及其性质13.2.3 模糊关系与模糊矩阵13.2.4 模糊相似矩阵和模糊等价矩阵13.3 模糊聚类算法过程分析13.3.1 模糊聚类的分类13.3.2 模糊聚类的基本步骤13.4 两种模糊聚类算法的算例分析与比较13.4.1 数据集介绍13.4.2 布尔矩阵法13.4.3 最大树法13.4.4 实验结果分析13.5 本章小结1第四章 一种新的判定模糊聚类有效性指标14.1 引言14.2 模糊聚类的有效性指标研究14.2.1 Fukayama-Sugeno提出的有效性指标14.4.2 Partition Coefficient (PC)14.2.3 Classification Entropy(CE)14.2.4 Partition Index(SC) 14.2.5 Separation Index(S)14.2.6 Xie-Beni提出的有效性指标(XB)14.2.7 Bensaid提出的有效性指标14.2.8 S.H.Kwon提出的有效性指14.3 一种新的模糊聚类有效性指标14.4 一种新的判定模糊聚类有效性算法14.5 实验验证与结果分析14.6 本章小结1第五章 结论与展望15.1 本文主要内容总结15.2 进一步工作展望1致 谢1参考文献1攻读硕士学位期间论文发表和参与的科研项目1 第一章 绪论第一章 绪论1.1 研究背景二十世纪末以来，全球信息量以惊人的速度急剧增长。据估计，每二十个月将增加一倍。许多组织机构的IT系统中都收集了大量的数据（信息）。目前的数据库系统虽然可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。为了充分利用现有信息资源，从海量数据中找出隐藏的知识，数据挖掘技术应运而生并显示出强大的生命力。将物理或抽象对象的集合分组成为由类似对象组成的多个类的过程称为聚类(Clustering)1。聚类分析是数据挖掘中应用较为广泛的一种技术。目前，已有很多的学者将聚类分析应用于各种不同的领域。由于数据挖掘是一门多学科交叉技术。因此，在进行聚类分析研究的过程中，总会将聚类分析技术与其他学科进行交叉研究，并得到一些更好的结果。模糊聚类就是聚类分析与模糊集合理论相结合的产物。模糊聚类分析是依据客观事物间的特征,亲疏程度和相似性通过建立模糊聚类相似关系对客观事物进行分类的方法.它最早起源是由于L.A.Zadeh在1965年创立了模糊集合论，随后Bellman和Kalabaff.Zadeh提出了用模糊集来处理聚类问题。在1969年，著名的学者E.H.Ruspin又引入了模糊划分的概念进行模糊聚类分析。第一个系统的表述并研究了模糊聚类。至今越来越多的学者将模糊聚类应用与各个领域，使得模糊聚类在运用于天气预报，气象分析，图像分割，模式识别，生物，医学诊断和化学分析等领域均时均取得了满意的效果和客观的效益。1.2 数据挖掘技术近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高，无数个数据库被用于商业管理、政府办公、科学研究和工程开发等,这一势头仍将持续发展下去。于是，一个新的挑战被提了出来：在这被称之为信息爆炸的时代，信息过量几乎成为人人需要面对的问题。如何才能不被信息的汪洋大海所淹没，从中及时发现有用的知识，提高信息利用率呢？要想使数据真正成为一个公司的资源，只有充分利用它为公司自身的业务决策和战略发展服务才行，否则大量的数据可能成为包袱，甚至成为垃圾。因此,面对“人们被数据淹没，人们却饥饿于知识”的挑战，数据挖掘和知识发现(DMKD)技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。数据挖掘(Data Mining)就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程2。还有很多和这一术语相近似的术语，如从数据库中发现知识(KDD)、数据分析、数据融合(Data Fusion)以及决策支持等。人们把原始数据看作是形成知识的源泉，就像从矿石中采矿一样。原始数据可以是结构化的，如关系型数据库中的数据，也可以是半结构化的，如文本、图形、图像数据，甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现了的知识可以被用于信息管理、查询优化、决策支持、过程控制等，还可以用于数据自身的维护。因此,数据挖掘是一门广义的交叉学科，它汇聚了不同领域的研究者，尤其是数据库、人工智能、数理统计、可视化、并行计算等方面的学者和工程技术人员。特别要指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面向特定数据库的简单检索查询调用，而且要对这些数据进行微观、中观乃至宏观的统计、分析、综合和推理，以指导实际问题的求解，企图发现事件间的相互关联，甚至利用已有的数据对未来的活动进行预测。例如加拿大BC省电话公司要求加拿大Simon Fraser大学KDD研究组，根据其拥有十多年的客户数据，总结、分析并提出新的电话收费和管理办法，制定既有利于公司又有利于客户的优惠政策。美国著名国家篮球队NBA的教练，利用某公司提供的数据挖掘技术，临场决定替换队员，一度在数据库界被传为佳话。这样一来，就把人们对数据的应用，从低层次的末端查询操作，提高到为各级经营决策者提供决策支持。这种需求驱动力 ，比数据库查询更为强大。同时需要指出的是，这里所说的知识发现，不是要求发现放之四海而皆准的真理，也不是要去发现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明。所有发现的知识都是相对的，是有特定前提和约束条件、面向特定领域的，同时还要能够易于被用户理解，最好能用自然语言表达发现结果。因此DMKD的研究成果很讲求实际。1997年第3届KDD国际学术大会上进行的实实在在的数据挖掘工具的竞赛评奖活动，就是一个生动的证明。最近，还有不少DMKD产品用来筛选Internet上的新闻，保护用户不受无聊电子邮件的干扰和商业推销，受到极大的欢迎。随着DMKD研究逐步走向深入，人们越来越清楚地认识到，DMKD的研究主要有3个技术支柱，即数据库、人工智能和数理统计。数据库技术在经过了80年代的辉煌之后，已经在各行各业成为一种数据库文化或时尚，数据库界目前除了关注分布式数据库、面向对象数据库、多媒体数据库、查询优化和并行计算等技术外，已经在开始反思。数据库实质的应用仅仅是查询吗？理论根基最深的关系型数据库本质的技术进步点，就是数据存放和数据使用之间的相互分离。查询是数据库的奴隶，发现才是数据库的主人；数据只为职员服务，不为老板服务。这是很多单位的领导在热心数据库建设后发出的感叹。由于数据库文化的迅速普及，用数据库作为知识源具有坚实的基础；另一方面，对于一个感兴趣的特定领域-客观世界，先用数据库技术将其形式化并组织起来，就会大大提高知识获取起点，以后从中发掘或发现的所有知识都是针对该数据库而言的。因此,在需求的驱动下，很多数据库学者转向对数据仓库和数据挖掘的研究，从对演绎数据库的研究转向对归纳数据库的研究。专家系统曾经是人工智能研究工作者的骄傲。专家系统实质上是一个问题求解系统，目前的主要理论工具是基于谓词演算的机器定理证明技术。领域专家长期以来面向一个特定领域的经验世界，通过人脑的思维活动积累了大量有用信息。在研制一个专家系统时，知识工程师首先要从领域专家那里获取知识，这一过程实质上是归纳过程，是非常复杂的个人到个人之间的交互过程，有很强的个性和随机性。因此，知识获取成为专家系统研究中公认的瓶颈问题。其次，知识工程师在整理表达从领域专家那里获得的知识时，用if-then等类的规则表达，约束性太大，用常规数理逻辑来表达社会现象和人的思维活动局限性太大，也太困难，勉强抽象出来的规则有很强的工艺色彩，差异性极大，知识表示又成为一大难题。此外，即使某个领域的知识通过一定手段获取并表达了，但这样做成的专家系统对常识和百科知识出奇地贫乏，而人类专家的知识是以拥有大量常识为基础的。人工智能学家Feigenbaum估计，一般人拥有的常识存入计算机大约有100万条事实和抽象经验法则，离开常识的专家系统有时会比傻子还傻。例如战场指挥员会根据“在某地发现一只刚死的波斯猫”的情报很快断定敌人高级指挥所的位置，而再好的军事专家系统也难以顾全到如此的信息。以上这3大难题大大限制了专家系统的应用，使得专家系统目前还停留在构造诸如发动机故障论断一类的水平上。人工智能学者开始着手基于案例的推理，尤其是从事机器学习的科学家们，不再满足自己构造的小样本学习模式的象牙塔，开始正视现实生活中大量的、不完全的、有噪声的、模糊的、随机的大数据样本，也走上了数据挖掘的道路。 数理统计是应用数学中最重要、最活跃的学科之一，它在计算机发明之前就诞生了，迄今已有几百年的发展历史。如今相当强大有效的数理统计方法和工具，已成为信息咨询业的基础。信息时代，咨询业更为发达。然而，数理统计和数据库技术结合得并不算快，数据库查询语言SQL中的聚合函数功能极其简单，就是一个证明。咨询业用数据库查询数据还远远不够。一旦人们有了从数据查询到知识发现、从数据演绎到数据归纳的要求，概率论和数理统计就获得了新的生命力，所以才会在DMKD这个结合点上，立即呈现出繁荣景象。一向以数理统计工具和可视化计算闻名的美国SAS公司，领先宣布进入DMKD行列。数据挖掘所能发现的知识有如下几种：广义型知识，反映同类事物共同性质的知识；特征型知识，反映事物各方面的特征知识；差异型知识，反映不同事物之间属性差别的知识；关联型知识，反映事物之间依赖或关联的知识；预测型知识，根据历史的和当前的数据推测未来数据；偏离型知识，揭示事物偏离常规的异常现象。所有这些知识都可以在不同的概念层次上被发现，随着概念树的提升，从微观到中观再到宏观，以满足不同用户、不同层次决策的需要。例如，从一家超市的数据仓库中，可以发现的一条典型关联规则可能是“买面包和黄油的顾客十有八九也买牛奶”，也可能是“买食品的顾客几乎都用信用卡”，这种规则对于商家开发和实施客户化的销售计划和策略是非常有用的。至于发现工具和方法，常用的有分类、聚类、模式识别、可视化、决策树、遗传算法、不确定性处理等。1.3 本文研究工作 本文首先简单介绍了数据挖掘技术和聚类分析。其中重点介绍了模糊聚类，并详细阐述了几种具有代表性的聚类算法和模糊聚类算法。对其中的布尔矩阵法和最大树法进行算例分析比较，通过仿真实验分析这两种算法各自的优缺点。最后针对多种经典的聚类有效性指标，本文提出了一种新的模糊聚类有效性指标，并进行了实验仿真，以分析这种新的模糊聚类有效性性指标的作用效果。本文所作的主要工作总结如下:（1）对两个模糊聚类算法的算例分析比较，根据目前的模糊聚类算法，主要针对直接聚类法中的布尔矩阵法和间接聚类法中的最大树法进行比较研究。在比较中，应用了IRIS典型数据集进行计算。并分析最终结果产生的原因和它们的适用范围。（2）运用标准数据集IRIS，对当前主要的模糊聚类的有效性指标进行仿真实验。从中发现了一些有效性指标的优点和不足。（3） 提出一种新的有效性指标Vnew。在对Xie-Beni提出的有效性指标VXB进行仿真实验中，发现当cn时，VXBU,V,c将也趋向于0而失去了判定能力。针对此缺点提出了一种新的有效性指标，在原来指标的基础上新增了一个惩罚项，能够很好的解决这个问题。并在本文中论证了新指标具有较好的判定性和鲁棒性。（4）提出了一种新的判定模糊聚类有效性算法。为了判定了新指标的可靠性，本文提出了一种新的判定模糊聚类有效性算法。分别运用四个标准数据集对新算法进行实验仿真，实验表明，新指标具有较好的可靠性和判定性。1.4 论文结构本文各部分组织如下：第一章 绪论，描述了本文的研究背景并概述了数据挖掘技术的基本内容，以及本论文所做的工作和创新点。第二章 聚类分析与模糊聚类，首先介绍了聚类分析的基本概念和模糊聚类分析的形成，重点研究分析了模糊聚类分析的四个研究方向。分别是模糊聚类算法的改进、模糊聚类算法的实现途径、模糊聚类的应用研究和模糊聚类的有效性研究。基于聚类分析和模糊聚类分析，最后分别介绍了HCM算法和FCM算法的基本思想和基本步骤。第三章 模糊聚类算法研究和算例分析比较。首先简单的介绍了模糊数学的一些基本概念，如：模糊集，模糊矩阵，模糊关系，模糊相似关系和等价关系等等。本章主要对模糊聚类算法的过程作了详细的研究，从模糊聚类的分类到模糊聚类算法的基本步骤，最后重点对直接聚类法中的最大树法和间接聚类法中的布尔矩阵法进行分析和比较。分别用标准数据集进行计算，分析实验结果。说明这两种方法的适用范围。第四章 提出一种新的判定模糊聚类有效性指标Vnew。首先简单的介绍了目前主流的模糊有效性指标和一些改进后的有效性指标，对这些主流有效性指标进行研究，发现它们各自的优缺点。基于它们的缺点，本文提出了一种新的判定模糊聚类有效性的指标Vnew。并对新的指标进行了分析证明。证明新指标的稳定性和鲁棒性。最后为了验证新指标的可靠性，本文提出一种新的判定模糊聚类有效性算法，通过利用四种标准数据集进行实验仿真，将Vnew与其他指标进行分析比较，验证了有效性的可靠性。第五章 总结与展望，总结了本文算法的不足之处，并指出进一步研究的方向。69第二章 聚类分析与模糊聚类第二章 聚类分析与模糊聚类2.1 聚类分析聚类(Clustering)是一个将数据集划分为若干组(Class)或类(Cluster)的过程，并使得同一个组内的数据对象具有较高的相似度，而不同组中的数据对象则是不相似的1。相似或不相似的度量是基于数据对象描述的取值来确定的。通常就是利用(各对象间)距离来进行描述的。将一群(Set)物理的或抽象的对象，根据它们之间的相似程度，分为若干组(Group)，其中相似的对象构成一组，这一过程就称为聚类过程(Clustering Procession)2,一个聚类(Clustering)也就是由彼此相似的一组对象所构成的集合；不同聚类中对象通常是不相似的。聚类分析就是从给定的数据集中搜索数据对象之间所存在的有价值联系。而在许多应用中，一个聚类中所有对象常常被当作一个对象来进行处理或分析。聚类分析是人类的一个重要内容。早在儿童时期，一个人就是通过不断完善潜意识中的分类模式，来学会识别不同物体，如:猫和狗;动物和植物等。聚类分析己被应用到许多领域，其中包括:模式识别、数据分析、图象处理和市场分析等。通过聚类，人可以辨识出空旷和拥挤的区域，进而发现整个的分布模式，以及数据属性之间所存在有价值的相关联系。聚类分析的典型应用主要有：在商业方面，聚类分析可以帮助市场人员发现顾客群中所存在的不同特征的组群，并可以利用购买模式来描述这些具有不同特征的顾客组群。在生物学方面，聚类分析可以用来获取动物或植物所存在的层次结构(Taxonomies)，可根据基因功能对其进行分类以获得对人群中所固有的结构更深入的了解。聚类还可以从地球观测数据库中帮助识别具有相似的土地使用情况的区域。此外，还可以帮助分类识别互联网上的文档以便进行信息发现。作为数据挖掘的一项功能，聚类分析还可以作为一个单独使用的工具，来帮助分析数据的分布、了解各数据类的特征、确定所感兴趣的数据类以便作进一步分析。当然聚类分析也可以作为其他算法(诸如：分类和定性归纳算法)的预处理步骤。数据聚类分析是一个正在蓬勃发展的领域。聚类分析所涉及的领域包括：数据挖掘、统计学、机器学习、空间数据库技术、生物学和市场学等。由于各应用数据库所包含的数据量越来越大，聚类分析己成为数据挖掘研究中一个非常活跃的研究课题。作为统计学的一个分支，聚类分析已有多年的历史，这些研究主要集中在基于距离的聚类分析方面。许多统计软件包，诸如:S-Plus, SPSS和SAS,都包含基于K-Means、K-Mediods等诸多聚类分析方法。在机器学习中，聚类分析属于一种无(教师)监督的学习方法。与分类学习不同，无(教师)监督学习不依靠事先确定的数据类别，以及标有数据类别的学习训练样本集合。正因为如此，聚类分析又是一种通过观察学习方法(Learning by Observation)，而不是示例学习(Teaming by Example)。在概念聚类方法中，仅当一组对象可以由一个概念所描述时，这些对象方才能构成一个类。这与基于几何距离表示相似程度并进行聚类的传统聚类方法有所不同。概念聚类方法主要包含两部分内容：发现适当的类；根据每个类来形成相应的特征描述，这与在分类学习中的方法类似。聚类分析的基本指导思想是最大程度地实现类中对象相似度最大，类间对象的相似度最小。在数据挖掘中，大多数工作都集中在设计能够有效、高效地对大数据库进行聚类分析的方法上。相关的研究课题包括：聚类方法的可扩展性、复杂形状和复杂数据类型的聚类分析及其有效高效性、高维聚类技术，以及混合数值属性与符号属性数据库中的聚类分析方法等。随着对聚类分析的深入研究，它开始得到了非常广泛的应用。但每个应用都有自己特定的要求，这就要求数据挖掘要对聚类分析提出一些典型的要求。可扩展性、处理不同类型属性的能力、发现任意形状的聚类、需要(由用户)决定的输入参数最少、处理噪声数据的能力、对输入记录顺序不敏感、高维问题、基于约束的聚类、可解释性和可用性等。 目前存在大量的聚类分析方法，很难对它提出一个简单又简洁的分类方法。因为这些类别并不是完全独立存在的，它们可能彼此重叠。总体上来说，目前主要的聚类方法可以划分为以下几类2：如下2-1图所示：模型聚类EMCOBWEBSOM网格聚类STRINGCLIQUE密度聚类DBSCANOPTICS层次聚类BIRCHCUREROCKChameleon划分聚类K-MEANSK-Medoids聚类算法图2-1 聚类算法分类（1）划分方法（Partitioning Methods） 给定一个n个对象或元组的数据库，一个划分方法构建数据的k个划分每个划分表示一个聚簇，并且kn。也就是说，它将数据划分为k个同时满足如下的要求：（I）每个组至少包含一个对象；(II)每个对象必须属于且只属于一个组，同时某些模糊划分技术中第二个要求可以放宽。给定要构建的划分的数目k，划分方法首先创建一个初始划分。然后用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。一个的划分的一般准则是；在同一个类中的对象之间尽可能“接近”或者对不同类中的对象之间尽可能“远离”或不同。还有许多其他划分质量的评准则。为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分际上，绝大多数应用采用了以下两个比较流行的启发式方法，K-Means算法，在该算法中，每个簇用该簇中对象的平均值来表示。K-Medoids算法中，每个簇用接近聚类中心的一个对象来表示。这些启发式聚类方对在中小规模的数据库中发现球状簇很适用。为了对大规模的数据集进行类，以及处理复杂形状的聚类，基于划分的方法需要进一步的扩展。（2）层次方法（Hierarchical Methods）层次的方法对给定数据对象集合进行层次的分解。根据层次的分解如何形成，层次的方法可以分为凝聚的和分裂的。凝聚的方法，也称为自底向上的方法，一开始将每个对象作为单独的一个组，然后相继地合并相近的对象或组，直到所有的组合并为一个(层次的最上层)，或者达到一个终止条件。分裂的方法，也称为自顶向下的方法，一开始将所有的对象置于一个聚类中。在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件。层次方法的缺陷在于，一旦一个步骤(合并或分裂)完成，它就不能被撤消。这个严格规定是有用的，由于不用担心组合数目的不同选择，计算代价会较小。但是，该技术的一个主要问题是它不能更正错误的决定。有两种方法可以改进层次聚类的结果：1) 在每层划分中，仔细分析对象间的“联接”；2) 综合层次凝聚和迭代的重定位方法。首先用自底向上的层次算法，然后用迭代的重定位来改进结果。第一个方法称为BIRCH，它首先用树结构对对象进行层次划分，然后采用其他的聚类算法对聚类结果进行求精。第二个方法称为CURE，它采用固定数目的代表对象来表示每个簇，然后依据一个定义的分数向着聚类中心对它们进行收缩。第三个方法称为ROCK，基于簇的互联性进行合并。第四个方法称为Chameleon，在层次聚类中发现动态模型。（3）基于密度的方法（Density-Based Method）绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发现球状的簇，而对发现任意形状的簇却有困难。随之提出了基于密度的另一类聚类方法，其主要思想是：只要临近区域的密度(对象或数据点的数目)超过某个阀值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法可以用来过滤“噪声”孤立点数据，发现任意形状的聚类。DBSCAN是一个有代表性的基于密度的方法，它根据一个密度阀值来控制簇的增长。OPTICS是另一个基于密度的方法，它为自动的和交互的聚类分析计算一个聚类顺序。（4）基于网格的方面（Grid-Based Methods）基于网格的方法把对象空间量化为有限数目的单元，形成了一个网格结构。所有的聚类操作都在这个网格结构(即量化的空间)上进行。这种方法的主要优点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。代表性的算法有STRING算法和CLIQUE算法。（5）基于模型的方法（Model-Base Methods）基于模型的方法为每个聚类假定了一个模型，寻找数据对给定模型的最佳拟合。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。它也基于标准的统计数字自动决定聚类数目，考虑“噪声”数据或孤立点，从而产生健壮的聚类方法。一些聚类算法集成了多种聚类方法的思想，所以有时将某个给定的算法划分为属于某类聚类方法是困难的。此外，某些应用可能有特定的聚类标准要求综合多个聚类技术。基于模型聚类的方法也很多，其中最大期望化EM算法，概念聚类COBWEB算法和神经网络方法SOM应用都很广泛。2.2 聚类分析与模糊理论的结合不难发现，在现实生活中，很多的时候需要对带有模糊特征的事物进行聚类分析，所以应该采用模糊数学的方法来进行聚类分析，我们称为模糊聚类。最早是由美国的计算机和控制理论专家L.A.Zadeh创立了模糊集合论，它在1995年发表了一篇叫“Fuzzy Sets”的论文3，因为模糊数学便成为一门新的学科并得到迅速的发展。但是首次提出用模糊集来处理聚类问题的人是Bellman, Kalabaff Zadeh。随后于1969年，著名的著名学者E.H.Ruspini引入了模糊划分3的概念，用模糊划分的方法进行模糊聚类分析。并系统的表述和研究了模糊聚类。至今越来越多的学者将模糊聚类应用与各个领域，使得模糊聚类在运用于天气预报，气象分析，图像分割，模式识别，生物，医学诊断和化学分析等领域均时均取得了满意的效果和客观的效益。现在已经提出了很多基于模糊划分的模糊聚类方法，如：最大数法，传递闭包法，基于摄动的模糊聚类方法，模糊C-均值算法，编网法等等。2.3 模糊聚类分析的研究方向自从模糊聚类分析提出到现在，不断地有学者和研究人员对其提出改进，对模糊聚类的分析有很多的方面。其中有4个主要的研究方向5，分别是模糊聚类算法的改进、模糊算法的实现途径、模糊聚类的应用和模糊聚类的有效性研究。其中本文主要研究模糊聚类的有效性研究。2.3.1 模糊聚类算法的改进伴随着模糊数学理论的形成、发展和深化，Ruspini率先提出了模糊划分的概念。同时，Zadeh6, Tamara等也提出基于相似关系和模糊关系的聚类方法，但由于该类方法不适于大数据集，所以这方面的工作已经开展的很少了。为解决模糊聚类问题，人们作了各种尝试，比如借助图论、数据集的凸分解、动态规划以及基于难以辨别关系等技术。然而，由于种种原因，这些方法均不能奏效。实际中受到普遍欢迎的是基于目标函数的聚类方法，也就是说，把聚类归结成一个带约束的非线性规划问题，通过优化求解获得数据集的模糊划分和聚类。该方法设计简单、解决问题的范围广，还可以转化为优化问题而借助经典数学的非线性规划理论求解，并易于在计算机上实现。因此随着计算机的应用和发展，该方法成为模糊聚类分析的主要手段，成为当前的研究热点。基于目标函数(或划分)的模糊聚类方法首先由Ruspini4提出，但真正有效的算法模糊C-均值算法却是由Dunn7给出的。Bezdek8又将其进一步扩展，建立起比较系统的模糊聚类理论。从此，该类模糊聚类方法蓬勃发展起来，目前己形成庞大的体系。由模糊聚类的数学模型可知，对于一组给定的样本集，模糊聚类分析可很容易获得它的一个模糊。划分： U=uij|1ic;1jn。要保证划分的有意义，则需要依据问题的需要定义合适的划分准则，比如常用的相似(异)性准则D()。假定每个模糊子集Xi（1ic）都形成一个模式v,(常被称作聚类原型)，则样本xk与模糊子集Xi的相似性可以通过它与聚类原型v,间的失真度dij=D(xk,vi)来度量，从而确定模糊划分矩阵U。不过聚类原型事先无法得知，需在聚类过程中逐步形成。这样，为了保证聚类的结果能使“物以类聚”，就以极小化的每类样本与该类模式间的失真度构造模糊聚类的目标函数，然后通过优化该目标函数获得样本集的最佳模糊。划分Uu,k和每类的模式P=pi,1ic。常见的模糊聚类目标函数形式如下，为一带约束的非线性函数5：minJm=i=1ck=1nuikmD2xk,pi+,s,t,f(uik)CON (2-1)其中为惩罚相，CON为约束条件，m为加权指数。因此，模糊聚类的目标函数就由参量集U, D(),P, m,X而确定。下面就分别从这五个分量的角度来分别介绍目标函数的演化过程。（1）对模糊划分矩阵U的研究 传统的聚类分析为一种硬划分，uik0,1为样本xk类属的指示函数，类别标记矢量uxk=(u1k,u2k,uck)T为欧氏c空间的基矢量。为了表达模式间的相近的信息，引入了模糊划分的概念。令uik0,1,把标记矢量扩展为欧氏c空间中的超平面i=1cuik=1，故模糊标记也称为概率标记。而概率约束使得隶属度只能用来表示样本在类之间的分享程度，而不能反映其典型性，为此Krishnapuram等提出可能性划分的概念，放松了该约束。这样标记矢量变为除去原点的单位超立方体。为了结合硬聚类和模糊聚类的优点，Selim和Ismail提出了半模糊划分9的概念，只保留划分矩阵中较模糊的元素，其余元素去模糊处理。这样使划分矩阵既具有一定的明晰性，又保持了样本在空间分布的模糊性，从而提高了分类的正确性。后来，文献10又提出了改进型的半模糊划分方法。（2）对相似性准则D()的研究对单一的聚类准则不能解决所有可能的无监督分类问题，因此聚类准则层出不穷。迄今为止，人们已经提出了多种相似性准则，如最大似然准则、最大熵准则、最小体积准则、非计量的准则、模糊测度准则和信息论准则等。不过，实际中最常见和最普遍的还是基于最小类内加权平方误差和准则。经典的类内平方和函数(WGSS)最早被用来定义硬C-均值聚类算法。随着模糊理论的提出，Dunn11首先把它推广到加权的类内平方和函数，后由Bezdek12扩展到加权类内平方和函数的无限族，形成了模糊C-均值类型算法的通用聚类准则。对该准则函数的研究主要集中在相似性或者误差度量D()上，一般用样本与原型模式间的距离表示。而不同距离度量可用来检测不同结构的数据子集，常用的距离函数见表2-l13所示：表2-1 常用的距离函数名称距离函数特点功能Minkowshidpa,b=t=1s|at-bt|p1p对应1p为一族距离测度，可检测从菱形立方体正方形超立方体结构Euclideand2a,b=t=1s|at-bt|212对应p=2的Minkowshi距离，可用以检测特征空间中圆形超球体结构Hammingd1a,b=t=1s|at-bt|对应p=1的Minkowshi距离，可用以检测特征空间中菱形超立方体结构Maximumda,b=maxi=1,.s|at-bt|对应p=的Minkowshi距离，可用以检测特征空间中正方形超立方体结构MahalanobisdAa,b=a-bTAa-b可用来检测特征空间中超椭球结构在聚类分析中，距离函数的选择会对聚类结果产生重要影响，合适的距离函数可以得到的较好的聚类结果，因而值得人们对选择距离函数的重视。（3）对聚类原型C的研究基于目标函数的模糊聚类又称作基于原型的聚类，因为目标函数的构造依赖于原型的定义。对聚类原型的研究是伴随着聚类应用的发展和需求而展开的，最初的聚类分析只应用于特征空间中超球体聚类结构的检测，因此原型为特征空间中的“点”，或者叫聚类中心；为了处理非超球体的聚类结构，Bezdek8提出了新的聚类原型，即过点vRs的r(1rs-1)维线性Crv,si=v+span(si)。基于目标函数的模糊聚类分析对原型有较强的依赖性，因此这就要求一方面必须充分利用先验知识选择合适的原型模式，另一方面必须与距离测度相结合研究，才能构造出合理的相似性度量。（