模糊聚类分析算法研究.doc

摘要聚类就是按照事物间的相似性进行区分和分类的过程，在这一过程中没有教师指导，因此是一种无监督的分类。聚类分析则是用数学方法研究和处理所给定对象的分类。传统的聚类分析是一种硬划分，它把每个待辨识的对象严格地划分到某个类中，具有非此即彼的性质，因此这种分类的类别界限是分明的。而实际上大多数对象并没有严格的属性，它们在性态和类属方面存在着中介性，适合进行软划分。Zadeh提出的模糊集理论为这种软划分提供了有力的分析工具，人们开始用模糊的方法来处理聚类问题，并称之为模糊聚类分析。模糊聚类分析算法的一般包括三个步骤:第一步:数据标准化;第二步:建立模糊相似矩阵;第三步:聚类。本文对模糊聚类分析中的两种算法进行了重点研究。最后利用matlab实现了一个模糊聚类算法，并用实例加以验证。关键词：模糊集合，模糊聚类分析，模糊等价矩阵，传递闭包AbstractThis paper will illustrate “clustering analysis” thoroughly. Cluster is a process that assorts things by their similarity. There is no adviser in this process, so it is a non-supervised classification. “Clustering analysis” research and process assort things by mathematical means. Traditional Clustering analysis assorts things strictly: therefore the limit of the classification is very clearly. But in fact most of the things have no obvious attribute by each: their limit is vague, as a result soft classification is a better way to process them. Professor Zadeh introduced the theory of fuzzy sets, which offer a powerful means to solve the problem. People begin to use fuzzy way to deal with clustering problem, and call it “fuzzy clustering analysis”.“Fuzzy clustering analysis” contains three steps. The first is data standardization; the second is to establish fuzzy similar matrix; the third is clustering. This paper will research two arithmetic of the Fuzzy clustering analysis. Finally, the paper will accomplish Fuzzy clustering analysis program by matlab. It is significant to use data to validate it. Key words: fuzzy set, fuzzy clustering analysis, fuzzy equivalent matrix, transitive closure目录第1章 引言11.1研究背景11.2本文的研究对象与工作31.3本文的内容组织3第2章 模糊聚类分析综述42.1模糊集合的基本概念42.2 模糊集合的表示法42.3 模糊集的运算及性质52.4 模糊集的分解定理62.5 模糊矩阵72.6 模糊聚类分析算法综述14第3章 基于模糊等价矩阵的模糊聚类分析193.1基于模糊等价矩阵的模糊聚类分析的主要步骤193.2 基于模糊等价矩阵的模糊聚类分析方法的评价27第4章 基于目标函数的模糊ISODATA聚类分析304.1 模糊ISODATA聚类分析方法304.2 聚类效果的检验324.3 模糊ISODATA算法的改进33第5章 模糊聚类分析算法的实例实现345.1 求模糊相似矩阵355.2 计算的传递闭包355.3 计算截矩阵36结束语37参考文献40致谢42外文资料原文43外文资料译文46第1章 引言1.1研究背景聚类是人类最基本的一项认识活动，人类要认识世界就必须区别不同的事物并认识事物间的区别与联系，并且是伴随着人类的产生和发展而不断深化的一个问题。所谓聚类，它是一种研究分类的多元分析方法，就是按照事物的某些属性，将事物分成多个类或簇，所以又称为簇分析、群分析，它的做法是使得在同一类中的事物相似性尽可能的大，不同类别间的事物相似性尽可能的小。聚类分析则是指用数学的方法研究和处理给定对象的分类。“人以群分，物以类聚”，聚类是一个古老的问题，它伴随着人类社会的产生和发展而不断深化，人类要认识世界就必须区别不同的事物并认识事物间的相似性。经典分类学往往是从单因素或有限的几个因素出发，凭经验和专业知识对事物分类.这种分类具有非此即彼的特性，同一事物归属且仅归属所划定类别中的一类，因此这种分类的类别界限是分明的，所以这种分类又被称为硬分类。随着人们认识的深入，发现这种分类越来越不适用于对具有含义模糊的事物进行分类。如把人按身高分为“个子高的人”，“个子矮的人”，“身材中等的人”。如何判别特定的一个人的类别便产生了经典分类学解决不了的难题。而这类问题适合进行软分类，模糊数学的产生就为软分类提供了数学基础，由此产生了模糊聚类分析。我们把应用普通数学方法进行分类的聚类方法称为普通聚类分析，而把应用模糊数学方法进行分析的聚类分析称为模糊聚类分析。由于模糊聚类得到了样本属于各个类别的不确定性程度，表达了样本类属的中介性，即建立起了样本对于类别的不确定性的描述，能更客观地反映现实世界，从而成为聚类分析研究的主流。在现实生活中，人们往往会使用一些意思清楚而又不准确的语言来描述这个世界，比如“这座山很高”，“今天天气很热”等，对于有着丰富经验和常识的人来说，理解这些是很容易的，但让计算机去分析这些带有模糊性的信息就很困难了，例如，我们能很容易地根据别人描述的特征找到一个东西，但让计算机去做则很困难，因为以往的计算机技术大都是基于经典数学的，经典数学能很好地处理精确信息，但对含义不明确的信息就显得无能为力了，而这种信息在日常生活中被大量使用.美国控制学专家LA.Zadeh教授充分认识到了这一矛盾，提出了模栈数学的核心思想，就是用数学的手段来模仿人的思维，建立对复杂事务进行模糊度量、模糊识别、模糊推理、模糊控制和模糊决策的本领，由此产生了模糊数学。最早是由 Rsupah将模糊理论应用于聚类分析，于是出现了数据对象聚类归属模糊化，即每个数据对象并非一定要绝对的归属于某个聚类，而可以按照某一归属系数不同程度的分别属于不同的聚类。模糊聚类分析的实质就是根据研究对象本身的属性构造模糊知阵，在此基础上根据一定的隶属度来确定其分类关系。比较典型的有:基于相似性关系和模糊关系的方法(包括聚合法和分裂法)，基于模糊等价关系的传递闭包方法，基于模糊图论的最大树方法，动态直接聚类法、人工神经网络模糊聚类法以及基于数据集的凸分解、动态规划和难以辨识关系等方法。模糊聚类理论的发展推动了它在生产实践中的应用。由于模糊聚类的强大功能，使得这种技术己经在很多的领域获得了成功的应用。而且随着模糊聚类理论的不断发展和完善，必将发挥更大的作用。由于模糊聚类与模式识别的有着自然联系，使得它在识别领域首先获得了最为广泛的应用;其次，在图像处理中经常需要处理无监督的分类问题，因此理所当然的成为重要的分析工具，图像处理是计算机视觉的重要组成部分，由于人眼视觉的主观性使图像比较适合用模糊手段处理，同时训练样本图像的缺乏又需要无监督分析，而模糊聚类正好满足这两方而的要求，因此成为图像处理中一个强大的研究分析工具。模糊聚类在图像处理中最为广泛的应用为图像分割，由于图象分割问题可以等效为象素的无监督分类，因此早在1979年Coleman和Andrews就提出用聚类算法进行图像分割，此后基于二维直方图、塔型结构、小波分析、分形分维等一系列新技术，人们又相继提出了多种基于模糊聚类的灰度图像分割的新方法，并且在纹理图像分割、彩色图像分割、序列图像分割、遥感图像分割等方而也获得了很大的进展。基于模糊聚类的方法在边缘检测、图像增强、图像压缩、曲线拟合等众多方而的研究同样一也取得了丰硕的成果。现在数据挖掘技术是当今数据库系统研究和应用领域的热点问题，聚类分析是数据挖掘中非常重要的研究领域和应用技术之一，由于人们有待处理的问题越来越多，因此要求数据库处理的数据种类也越来越多，这其中就有含义不明确的模糊数据，所以将模糊信息处理技术加入到聚类分析中，便可以有助于数据挖掘技术的发展。此外，在通讯系统中的信道均衡、矢量量化编码中的码书设计、时间序列的预测，神经网络的训练、参数估计、医学诊断、气候分类、食品分类、水质分析等领域中模糊聚类分析也发挥着重大的作用。例如，在对耕作土壤进行分类时，红壤、黄壤和棕壤之间的界限不是很清晰，那么介于两者之间的土壤归属问题，用模糊聚类分析来处理更加合理。各种形式的聚类分析方法以及广阔的应用领域为聚类分析研究提供了宽广的舞台。同时，在聚类分析中加入模糊理论，可以使现有的聚类分析方法更加符合复杂的实际情况，模糊聚类分析方法也在各个领域有着更好的应用前景。1.2本文的研究对象与工作本文通过阐述模糊集合知识，引出模糊数学中一个重要的研究领域，即模糊聚类分析，综述了当前常见模糊聚类分析的原理及方法，并对模糊聚类分析中两种重要的方法即基于模糊等价矩阵的模糊聚类分析法和ISODATA法进行了重点研究，之后给出改进算法。最后使用Matlab语言实现一个模糊聚类分析程序。1.3本文的内容组织 本文的内容一共分为五章。第一章为“引言”，介绍模糊聚类分析的背景意义、研究现状和发展情况，本文的研究对象与工作概述及内容组织。第二章为“模糊聚类分析综述”，先介绍模糊集合的基本概念，然后阐述模糊集合的基本运算方法，给出分解定理，它是联系模糊集合与经典集合的桥梁。接着介绍了几种当前较为常见的模糊聚类分析方法的主要思路。第三章为“基于模糊等价矩阵的模糊聚类分析”，说明模糊聚类分析是如何通过模糊矩阵的变化来实现的，以及模糊聚类分析的步骤和能实现分类的各种方法。第四章为“基于目标函数的模糊ISODATA聚类分析”，介绍了ISODATA算法的主要思路，给出了一些改进的思路。第五章为“模糊聚类分析算法的实例实现”，用Matlab语言实现了一个模糊聚类分析程序。最后为“结束语”，是对全文的总结与展望。第2章 模糊聚类分析综述2.1模糊集合的基本概念人们所熟悉的经典集(为了与模糊集相区别，故称之为经典集)论要求：对论域中的任何元素，或者属于某一集合，或者不属于这个集合，两者必居其一且仅居其一。然而在现实世界中，有许多概念都是很模糊的，比如说“天气好”、“水温很低”、“个子很高”等都是模糊的概念。这样就使得经典集合论对于这样的概念显得力不从心了，因为模糊概念很难简单地用“属于”或“不属于”来表示，而只能通过属于的程度来描述。换句话说，就是论域中的元素符合某一概念的程度不能仅仅用0或1来表示，而需要借助于介于0到1之间的实数来表示。：论域上的“模糊集合”定义为：或者其中或者称为“隶属函数”，它满足： ：，这里称为“隶属空间”，最常见的隶属空间为。隶属函数用于刻画元素对模糊集合的隶属程度，即“隶属度”。所以模糊集合的每个元素都能明确地表现出的隶属等级。的值越大，的隶属程度就越高。比如，=1时，说明完全属于,而=0时，说明不属于，而值介于0和1之间时，说明隶属于的程度也介于“属于”与“不属于”之间是模糊的。由定义可以看出，模糊集合是由隶属函数唯一确定的，以后可以把模糊集合与隶属函数看成是等同的，另外，隶属程度的思想是模糊数学的基本思想。当的值域为集合时，模糊集合就是经典集合，可见经典集合是模糊集合的特殊情形。上的所有模糊集合组成的集合称为的模糊幂集，记为。2.2 模糊集合的表示法对于模糊集合，可以有各种不同的表示方法：(2) 序偶表示法 序偶表示法又称为向量表示法，它的形式为：（2）符号法：这种表示法适合用于任何种类的论域，特别是论域为无限集合的模糊集合的描述。设论域为，为上的一个模糊集合，则可以记为：这里的积分符号仅仅是一种表示，而并不意味着是进行积分运算。（3）符号法：这种表示法适合用于论域为有限集合或可列集合的模糊集合的描述。设论域为，为上的一个模糊集合，则可以记为：式中“”和“”只是一种记号，不是通常意义下的分数线与求和，只是表示上的元素与其隶属度的对应关系的一个总括。2.3 模糊集的运算及性质2.3.1定义:设,，若对于任意的，有，则称包含，记为,如果且，则称与相等，记为.:设,定义并：对于任意的,的隶属函数为 ，交：对于任意的,的隶属函数为 ，补：对于任意的,称为的补集，也称为余集，其隶属函数为2.3.2模糊集运算的性质 幂等律：, 交换律：, 结合律：, 吸收律：, 分配律：, 零-壹律：,;, 复原律： 对偶律：，值得注意的是，与经典集合交、并和补运算性质不同的是，在这里互补律不再成立，这一事实表明模糊集合不再具有“非此即彼”的特点，这正是模糊性带来的特征。2.4 模糊集的分解定理2.4.1 截集：设为论域中的模糊集合，定义的“截集”为集合实数称为“阈值”或“置信水平”。：设为模糊集合，则下面的等式成立,：令为模糊集合，且，则. 这个定理从理论上回答了“值越小，包含的元素越多”的问题。这种让由大到小取值，而所含的元素由少到多的过程，实际上是一种分类过程。值取得越大，包含的元素越少，分出的类就越多，分类就越细；反之亦然，这是以后模糊聚类分析的基础。2.4.2 分解定理模糊集合的截集是经典集合，那么能否用经典集合来表示模糊集合呢？下面介绍的分解定理就可以解决这个问题。为了叙述分解定理，首先引入一种新运算，即：数与模糊集合的乘积。(3) 数与模糊集合的乘积 ：设，,规定，其隶属函数为，并称为数与模糊集合的乘积。可见是一个模糊集合。 数与模糊集合的乘积运算的性质： 2. ：设,则 推论2.1：设,则 推论2.2：设，对任意的，则 分解定理是模糊数学的重要定理之一，由分解定理可知各数积项的最终计算是取最大值，所以只需计算各区间中上界与其相应截集的数积。2.5 模糊矩阵2.5.1 模糊矩阵的概念当论域为有限集合时，对于普通二元关系分的描述常常采用关系矩阵的方法，与此类似，对于有限论域上的二元模糊关系，也常常采用模糊矩阵描述.(4) 模糊矩阵的定义如果与都是有限集，则到的模糊关系的隶属函数值可用一个矩阵表示。设，是到的一个模糊关系，令 ，若其所有元素满足则称矩阵为模糊矩阵。显然，布尔矩阵式模糊矩阵的特例。在有限论域中，普通关系与布尔矩阵具有一一对应的关系，与此同时，在模糊数学中，有限论域中的模糊关系与模糊矩阵之间也具有一一对应的关系。设，均为阶模糊矩阵，则(5) 当且仅当时，“等于”，记为=当且仅当时，“包含”，记为定义与的“并运算”为定义与的“交运算”为定义补运算为2.5.2 模糊矩阵的运算及其性质一模糊矩阵之间的关系设，记，则相等：，包含：，二模糊矩阵的并，交，补运算模糊矩阵的并，交，补运算具有与模糊集合性质相同的性质（交换律，结合律，分配律等）设记，则 并： 交： 补： 模糊矩阵的并，交，补运算的性质：设，,，则有 幂等律：, 交换律：, 结合律：， 吸收律：,(6) 分配律：,(7) 零-壹律：,;, 复原律： 对偶律：，下面是包含性质：设，,，则有 , 三：模糊矩阵的合成运算模糊矩阵的合成运算相当于矩阵的乘法运算。1. 定义设，称模糊矩阵为与的合成，其中，即。 合成运算不满足交换律：即，和普通矩阵乘法一样，只有模糊矩阵的列数等于模糊矩阵的行数时，合成运算才有意义。2. 模糊方阵的幂设 ，模糊方阵的幂定义为合成“”运算的性质： 结合律： 分配律：下面是包含性质四：模糊矩阵的转置模糊矩阵的转置定义与线性代数中矩阵的转置定义是相同的。设，称为的转置矩阵，其中，。模糊矩阵的转置具有以下性质： 五 模糊矩阵的截矩阵 设，对于任意的，称为模糊矩阵的截矩阵，其中 当时，；当时，显然，截矩阵为布尔矩阵。 截矩阵的性质：任意 ; 2.5.3 模糊矩阵的基本定理 定义2.1：设，若模糊矩阵满足（的主对角元素），则称为自反矩阵。 定义2.2：设，若模糊矩阵满足()，则称为对称矩阵。 定义2.3：设，若模糊矩阵满足（），则称为模糊传递矩阵。 定义2.4：设，满足 ,总有，则称为的传递闭包，记为,即。这个定义的意思是指包含而且被任何包含的传递矩阵所包含的传递矩阵，称为的传递闭包。或者是包含的最小的模糊传递矩阵的传递闭包。显然，的传递闭包满足 （传递性） （最小性）定理2.1：设为自反矩阵，则定理2.2：设，传递闭包定理2.3：设，则传递闭包2.5.4 模糊关系由于普通关系都是二值的，因此换句话说，对于任意两个元素，在它们之间要么存在关系，要么不存在关系，两者必居其一且仅居其一。这种关系适合于描述“模糊确定”的关系。但是，在实际中，有不少关系是很难简单地用“是”或“否”来衡量的，而必须引入一定的量来表示两元素具有这种关系的程度。例如，正常人的身高与体重之间是有一定关系的。譬如对于一个身高170cm高的健康人来说，一般不能断定他的体重大约是多少，而只能根据正常人身高与体重的关系表来估计他的体重大约是多少。又如，正方形的四条边是等长的，但是在日常生活中，我们判断一个四边形物体的形状通常并不是总用尺子去度量它的四条边后才得出它是否为正方形的结论的，当四条边的长度在一定范围内有差异时，很可能不同的人会得出不同的结论。另外，“远远小于”、“非常大”等都是些“不清晰”的关系。这类需要有描述关系程度的量来补充描述的关系就是模糊关系，而其中的关系程度通过隶属函数来表示。与模糊子集是经典集合的推广一样，模糊关系是普通关系的推广。例如师生关系是普通关系，而两人之间的彼此“熟悉”程度的关系就是模糊关系。一 模糊关系的定义，运算及性质1. 模糊关系的定义设论域，称的一个模糊子集为从到的模糊关系，记为：其隶属函数为映射：并称隶属函数为关于模糊关系的相关程度。对于任意的隶属函数事实上表示了之间存在关系的程度。2. 模糊关系的运算由于模糊关系的笛卡尔乘积集合中的模糊集合，所以模糊集合运算的定义和性质也完全适用于模糊关系。设均为集合到的模糊关系，则对于任意的有以下运算：与的“并运算”记为，隶属函数定义为：与的“交运算”记为，隶属函数定义为：与的“补运算”记为，隶属函数定义为：“包含于”，记为，其隶属函数满足下式：与“相等”，记为，即且，其隶属函数满足：与的“代数和”，记为，其隶属函数满足：与的“代数积”，记为，其隶属函数满足：的“逆关系” 设为集到的模糊关系，则的“逆关系”是集合到的模糊关系。它们的隶属函数之间有关系式： 3. 模糊关系的性质为任意一个模糊关系，为零模糊关系，为全称模糊关系。 同一律： 零律： 若,则 若,则二 模糊关系的合成1. 模糊关系合成的定义设有三个论域，是到的模糊关系，是到的模糊关系，则和的合成是到的一个模糊关系，其隶属函数为：若，则当论域为有限时，模糊关系的合成转化为模糊矩阵的合成。设为有限论域。则与的合成为：其中2. 模糊关系合成的性质 结合律： 分配律：,3. 模糊等价关系由于在论域上的普通等价关系可以确定的一个划分（即的一个分类）。同样模糊等价关系也可以用于分类。定义2.5 若模糊关系满足： 自反性： 对称性： 传递性：则称是上的一个模糊等价关系，其中隶属函数表示的相关程度。三 模糊等价矩阵当论域,为单位阵，若满足： 自反性： 对称性： 传递性：则称为模糊等价矩阵。模糊等价矩阵的性质：定理2.4：是模糊等价矩阵，是等价的布尔矩阵。此定理的重要性在于将模糊等价矩阵转化为等价的模糊布尔矩阵有限论域上的普通等价关系，而等价关系式可以分类的，因此，当在上变动时，由得到不同的分类。这些分类之间的联系则由下面一个定理给出。定理2.5：设是模糊等价矩阵，则对，且，所决定的分类中的一个类是决定的分类中的某个类的子类。定理2.5表明，当时，所决定的分类是决定的分类的加细。因此，当由1变到0时，则分类由细变粗，可以形成一个动态聚类图，称之为模糊分类。四 模糊相似矩阵及其性质定义2.6：若模糊关系满足 自反性： 对称性：则称为上的模糊相似关系，其中隶属度表示的相似程度。当为有限论域时，模糊相似关系可以用模糊相似矩阵来表示。定义2.7：当论域,为单位阵，若满足： 自反性： 对称性：则称为模糊相似矩阵。模糊相似矩阵的性质定理2.5：设是模糊相似矩阵，则对任意的（自然数），也是模糊相似矩阵。定理2.6：设是模糊相似矩阵，则存在一个最小自然数，使得传递闭包，对于一切大于的自然数，恒有。此时，为模糊等价矩阵。定理2.6表明，通过求传递闭包，可以将模糊相似矩阵改造成模糊等价矩阵，它具有传递性，同时又保留了自反性和对称性。下面介绍一种实用的，简洁的方法，即所谓平方法，用它来求传递闭包。从模糊相似矩阵出发，一次求平方：当第一次出现时（表明具有传递性），就是所求的传递闭包。2.6 模糊聚类分析算法综述目前存在大量的聚类算法，算法的选择取决于数据的类型、聚类的目的和应用。大体上，主要的聚类算法可以划分为如下几类:2.6.1 基于分层的聚类法分层聚类法是由不同层次的分割聚类组成，层次之间的分割具有嵌套关系。分层聚类方法对给定的数据对象集合进行层次的分解，根据层次的分解如何形成，可以分为凝聚的和分裂的两种。凝聚的方法，也称自底向上的方法，一开始将每个对象作为单独的一个组，然后相继的合并相近的对象或组，直到所有的组合并为一个(层次的最上层)，或者达到某个要求的终止条件。分裂的方法，也称为自顶向下的方法，一开始将所有的对象置于一个簇中。在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件。分层聚类法不必事先知道聚类的数目，基于模糊相似关系的模糊聚类就是这种聚类法，如传递闭包法、最大树法、动态直接聚类法等，另外典型的这类方法还包括BIRCH, CURE和CHAMELEON等。在这些方法中，基于模糊相似关系的聚类算法对输入数据的次序不敏感，能够发现任意形状的聚类，但往往计算量大，处理海量数据的聚类时效率较低;BIRCH方法可以动态地对输入数据进行聚类，可以处理数据的噪声，但它一般只适用于聚类簇是球形的情况(因为它用了半径或直径的概念来控制聚类的边界)，而且对输入数据的次序也比较敏感;CURE方法解决了偏好球形和相似大小的问题，在处理孤立点上也更加健壮.2.6.2 基于分割的聚类法分割法也称为划分方法，它一般是通过优化一个评价聚类效果的目标函数，把目标函数取得极值下的划分作为聚类的结果。这类方法首先把数据集分割成K个部分并创建一个初始划分，然后利用循环迭代的重定位技术，通过将对象从一个划分移到另一个划分来改善划分质量，直到目标函数取得极值。一般来说，一个好的评价聚类效果的划分准则是:在同一个类中的对象之间尽可能的接近或相关，而不同的类中的对象之间尽可能的远离或不同。当然还有许多其他划分质量的评判准则。典型的分割聚类方法包括:K-Means, K-Mode, CLARANS等。分割聚类法的效率比较高，但聚类前要预先知道聚类的数目，绝大多数分割方法是基于数据对象之间的距离进行聚类的，这样的方法只能发现球状的或凸形的聚类，而在发现任意形状的聚类上遇到了困难，并且初始划分的不同选择对聚类的效率有很大影响，往往可能得到不同的聚类结果。分割聚类法大多为启发聚类方法，为了获得基于划分的聚类分析的全局最优结果就需要穷举所有可能的对象划分。这些启发聚类方法在分析中小规模数据集以发现圆形或球状聚类时工作得很好，但为了使划分算法能够分析处理大规模数据集或复杂数据类型，就需要对其进行扩展，如K-Mode就是从K-Means扩展而来以能对目录属性的数据进行聚类。为了使聚类结果更加符合实际，人们又将K-Means算法(硬C一均值聚类算法)和模糊数学理论相结合，提出了模糊C-均值(FCM)算法。然而，模糊C一均值聚类算法也存在着许多不足之处，如易于陷入局部最小、对初始值较敏感及不能处理噪声数据等问题，其寻优能力有待进一步提高。为此，研究者们又陆续提出了许多改进方法，有的是基于加权的思想，有的是基于遗传算法、克隆选择及人工免疫等的生物学理论技术上的思想，还有的是基于可能性理论.2.6.3 基于密度的聚类法为了发现任意形状的聚类结果，提出了基于密度的聚类方法(density-based method)。这类方法将簇看作是数据空间中被低密度区域分割开的高密对象区域。它的主要思想是:只要临近区域的密度(对象或数据点的数目)超过某个闽值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法可以用来过滤“噪声”孤立点数据，发现任意形状的簇。DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是个基于密度的聚类算法。该算法将具有足够高密度的区域划分为簇，并可以在带有“噪声”的空间数据集中发现任意形状的聚类。它定义簇为密度相连点的最大集合。DBSCAN的缺点是仍然将选择能产生可接受的聚类结果的参数值的责任留给了用户。OPTICS(Ordering Points to Identify the Clustering Structure)没有显式地产生一个数据集合簇，它为自动和交互的聚类分析计算一个簇次序(cluster- ordering)。这个次序代表了数据的基于密度的聚类结构。它包含的信息，等同于从一个宽广的参数设置范围所获得的基于密度的聚类。DENCLIUE(Density-based Clustering)是一个基于一组密度分布函数的聚类算法。该算法主要基于下面的想法Li)每个数据点的影响可以用一个数学函数来形式化地模拟，它描述了一个数据点在邻域内的影响，被称为影响函数(influence- function); ( ii)数据空NJ的整体密度可以被模型化为所有数据点的影响函数的总和;(iii)然后聚类可以通过确定密度吸引点(density- attractor)来得到，这里的密度吸引点是全局密度函数的局部最大。2.6.4 基于网格的聚类法基于网格的方法(grid-based method)把对象空间量化为有限数目的单元，形成了一个网格结构。所有的聚类操作都在这个网格结构(即量化的空间)上进行。这种方法的主要优点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。STING(Statistical Information Grid)是一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构:高层的每个单元被划分为多个低一层的单元。关于每个网格单元属性的统计信息(例如平均值、最大值和最小值)被预先计算和存储。统计参数的使用可以按照以下自顶向下的基于网格的方法。WaveCluster是一种多分辨率的聚类算法，它首先通过在数据空间上强加一个多维网格结构来汇总数据，然后采用小波变换来变换原特征空间，在变换后的空间中找到密集区域。2.6.5 基于约束的聚类法聚类技术的发展为地理数据分析等实际应用提供了许多有用的工具，但是绝大多数聚类算法不能直接解决存在现实约束的聚类问题。为了使得空间聚类对现实问题更实用，一些研究者还对聚类算法做了这方面的研究，提出了带约束条件的聚类算法。带约束条件的聚类是指特定的领域知识以“约束”的形式表达，并嵌入到聚类过程中的方法。因为利用了领域知识，使得聚类算法获得更多的启发式信息，从而减少了其搜索过程中的“盲目性”，提高了其效率和聚类质量。COP-Kmeans算法和CCL聚类算法是两种具有代表性的基于约束条件的聚类方法。这类约束聚类方法存在的主要问题是对数据的输入顺序都比较敏感。输入顺序不同，产生的符合条件的聚类结果也有所不同。2.6.6 基于模型的聚类法基于模型的方法为每个类假定一个模型，寻找数据对给定模型的最佳拟合。一个基于模型的算法可以通过构建反映对象空间分布的密度函数来定位聚类。基于模型的方法主要有两类:统计学方法和神经网络方法。(1) 统计学方法常用方法包括Fisher提出的COBWEB和Germari等提出的CLASSIT等。概念聚类的绝大多数方法采用了统计学的途径，在决定概念或聚类时使用概率度量。COBWEB就属此类算法，它是一种流行的简单增量概念聚类算法，以一个分类数的形式创建层次聚类。它的输入对象用分类属性一值对来描述。CLASSIT是COBWEB的扩展，用以处理连续性数据的增量聚类。(2) 神经网络方法竞争学习 (Competitive Leaming)采用若干个单元的层次结构，它们以一种“胜者为王(winner-take-all)”的方式对系统当前处理的对象进行竟争。学习矢量量化 (英文简称LUQ)方法是由Kohonen提出的。这是一种自适应数据聚类方法，它基于对具有期望类别信息数据的训练。尽管是一个有监督训练方法，然而LUQ采用了无监督数据聚类技术，对数据集进行预处理，可获得聚类中心。自组织特征映射(英文简称SOFM)，也由Kohonen提出，以其所具有的诸如拓朴结构保持、概率分布保持及无导师学习等特征，广泛应用于聚类分析之中。传统的SOFM网络存在着许多不足，如网络结构固定、训练时间长等缺点。为此，人们提出了多种在训练过程中动态确定网络形状和单元数目的解决方案.除上述六大类方法以外，在各种文献中还存在着大量的聚类方法。如基于遗传算法的聚类方法、模糊聚类方法、处理高维数据的聚类方法、处理大规模数据的聚类方法、处理动态数据的聚类方法以及将基本聚类方法与各种新技术相结合的聚类方法等。所有的聚类方法都具有各自的特点。有些以方法简单、执行效率高见长(如K-Means)，有些对任意形状、大小的类识别能力强(如CUBN)，有些能很好的过滤噪声数据(如DBSCAN)，但这些方法都有各自的局限性，如K-Means方法只能识别大小近似的球形类，CUBN. DBSCAN的时间复杂度都为O()。另外，很多聚类方法对输入参数十分敏感(如FCM算法)，而且参数很难确定，这加重了用户的负担。因此，尽管己存在众多的聚类方法，人们仍在致力于研究聚类能力强、执行效率高、参数设置简单的聚类方法。第3章 基于模糊等价矩阵的模糊聚类分析所谓聚类分析就是根据事物间的不同特征，亲疏程度和相似性等关系，对它们进行分类的一种数学方法，其数学基础是数理统计中的多元分析。由于在现实世界中，事物间的关系其界限往往是不分明的，即为模糊关系，故利用模糊数学方法来进行聚类分析会显得更自然，更符合客观实际，这就是模糊聚类分析具有很强生命力之所在。模糊等价矩阵动态聚类分析法是基于模糊等价矩阵聚类的，它的特点是分类数不定，根据不同要求对事物进行动态聚类。本章主要介绍的就是该方法的基本原理及主要步骤以及几种常用的聚类方法。3.1基于模糊等价矩阵的模糊聚类分析的主要步骤我们知道，一个合适的分类应当具备下列3个条件：自反性：即任何一个对象必需和自己在同一类；对称性：即若对象与对象同类，则与也应同类；传递性：即若对象与对象同类，而与对象同类，则与同类也应同类。满足上述3个条件的关系即为一个等价关系。因此，模糊聚类分析是根据模糊等价关系来进行的。其主要步骤如下：设被分类对象的集合为，每一个对象有个特性指标（反应对象特征的主要指标），即可由如下维特性指标向量来表示，其中表示第个对象的第个特性指标，则个对象的所有特性指标构成一个矩阵，记作称为的特性指标矩阵。3.1.1 数据规格化由于个特性指标的量纲和数量级不一定相同，故在运算过程中可能突出某数量级特别大的特性指标对分类的作用，而降低甚至排除了某些数量级很小的特性指标的作用，致使对各特性指标的分类缺乏一个统一的尺度。为了消除特性指标单位的差别和特性指标数量级不同的影响，必须对各指标值施行数据规格化的处理，从而使每一个指标值统一于某种共同的数值特性范围。下面介绍几种常用的数据规格化的方法。第二， 数据标准化对特性指标矩阵的第列，计算然后作变换易见，施行变换后的每个指标的平均值，而方差 均值规格化对特性指标矩阵的第列，计算，然后作变换， 中心规格化对特性指标矩阵的第列，计算，然后做变换， 最大值规格化对特性指标矩阵的第列，计算然后做变换， 极差规格化对特性指标矩阵的第列，计算及然后作变换， 对数规格化作变换，3.1.2 构造模糊相似矩阵设数据均以规格化，下面用多元分析的方法来确定对象和之间的相似程度： 从而构造出一个对象与对象之间的模糊相似矩阵下面介绍几种确定的常用方法。1. 相似系数法 数量积法