模糊聚类综述

模糊聚类综述摘要：本文首先对模糊聚类进行了概述，然后论述了模糊据类分析法，最后从四个方面综述模糊聚类的研究进展，并论述了其在模式识别及图像处理中的应用。关键词：模糊聚类，模糊相似矩阵，图像处理聚类分析是一种数据划分或分组处理的重要手段和方法。其操作的目的在于将特征空间中一组没有类别标记的矢量按某种相似性准则划分到若干个子集中，使得每个子集代表整个样本集的某个或者某些特征和性质。从这个意义上讲，聚类又称为无监督的分类。传统的聚类分析把每个样本严格地划分到某一类，属于硬划分的范畴。实际上，样本并没有严格的属性，它们在性态和类属方面存在着中介性。随着模糊集理论的提出，硬聚类被推广为模糊聚类。在模糊聚类中，每个样本不再仅属于某一类，而是以一定的隶属度分属于每一类。换句话说，通过模糊聚类分析，得到了样本属于各个类别的不确定性程度，即建立起了样本对于类别的不确定性的描述，这样就能更准确地反映现实世界。1.模糊聚类分析法聚类分析是对事物按一定要求进行分类的数学方法。实际的分类问题常伴有模糊性，因此，聚类问题用模糊数学的方法解决更确切。在实际的模糊聚类问题中，主要有用模糊等价关系进行的聚类分析和基于模糊拟序关系的聚类分析。其中，前者较为常用。1.1聚类分析的步骤步骤一：标定。设X：12,,nXXX为被分类对象全体，每一对象ix由一组数据12,,iiimxxx表征。建立x上的模糊相似关系R，R可表示为模糊相似矩阵R＝ijnnr，其中ix与jx的相似度ijr可根据实际情况，从下列方法中选择一种来规定。1)数量积：，其中M为一适当正数，满足M1max()mikjkijkxx.2)夹角余弦：12211mikjkkijmmikjkkkxxrxx3）相关系数：12211mikijkjkijmmikijkjkkxxxxrxxxx，其中ix＝11mikkxm，jx＝11mjkkxm。其它还有：最大最小法，算术平均最小法，几何平均最小法，绝对值指数法等。以上各种方法，究竟选择哪一种，根据实际问题的特点进行选择。步骤二:聚类(画聚类图)。用上述方法建立起来的模糊关系R，一般只具有自反性与对称性，不满足传递性。一般需求模糊矩阵R的传递闭包t(R)(包含R的最小的模糊传递矩阵)，使其具有传递性，再进行分类，求聚类图。最后，确定最佳阈值λ。聚类图给出各k值的分类，形成一种动态聚类，便于全面了解样本的聚类。最后根据实际需要合理选择某阈值λ，在适当阈值上进行截取，便可得到所需分类。1.2聚类的方法方法一：传递闭包法。步骤如下：(1)从传递矩阵R出发，利用平方法，依次计算2488RRRR直至首次出现kRkR＝kR，可以证明kR就是R的传递闭包t(R)。(2)R＝t(R)为模糊等价矩阵，取λ从1取到0，依次截得等价关系R，它们各自将X分类。由于121212(,)(,)ijijRRxxRxxR，这就是说对于1R，ix，jx属于同一类，则对于2R，ix，jx也属于同一类。因而由1R所得的分类是由2R所得分类的加细。这样当λ从1取到0时，所得分类逐步归并，可形成一个聚类图。方法二：直接聚类法。即建立模糊相似矩阵R后，不需求其传递闭包，直接从R出发，可求得聚类图。其步骤如下：(1)取1＝1(最大值)，求每个ix的相似类1ijijxxr将满足1ijr的ix与jx放在一类，构成相似类。由于R不满足传递性，不同的相似类可能有公共元素，此时将有公共元素的相似类归并。可以证明：关于R的相似类可归并为关于R的等价类。于是可得关于传递闭包R对应于1＝1的等价类。(2)取2等于次大值。从R中找出所有ijr＝2，将上述对应于1＝1的等价类中1iRx与1jRx归并。可以证明：通过对高阈值1的等价类(关于1R的归并，可直接得到对应低阈值2的等价类(关于2R)，归并原则是，若ijr＝2，将1iRx与1jRx合并，于是可得R对应于2的等价类。(3)取3等于第三大值。从R中找出所有ijr＝3，将对应于2的R的等价类中2iRx与2jRx。归并，将所有这种情况归并后，可得R的对应于3的等价类。(4)依此类推，直至归并至X成为一类。方法三：聚类分析的最大树法。(1)先画出被分类的元素集，从矩阵R中按ijr从大到小的顺序依次连边，标上权重，若在某一步会出现回路，便不画那一步。直至所有元素有路相通为止，这样就得到一棵最大树T。(2)取定阈值，在T中砍去权重小于的边，便可将元素分类，互相连通的元素归为同类。可以证明：T中去掉小于的边，将T分裂成若干树12,,,mTTT，则iT(i＝1，2，…，m)的顶点集对应R的等价类。2．在Ruspini和Bezdek等学者的努力下，模糊聚类逐步成为聚类分析研究的主流。八十年代后，其研究主要集中在：(1)模糊聚类新方法研究；(2)模糊聚类算法的实现途径；(3)聚类有效性研究；(4)聚类的实际应用等四个方面。以下就这四个方面综述模糊聚类的研究进展，并指出进一步研究的主要方向。2.1模糊聚类新方法研究进展第一个系统地研究模糊聚类的是Ruspini。1969年他定义了数据集模糊划分的概念。同时，Zadeh，Tarmura等也提出基于相似关系和模糊关系的聚类方法。但由于该类方法不适于大数据集，这方面的工作已经开展的很少了。为解决模糊聚类问题人们作了各种尝试；比如借助图论、数据集的凸分解、动态规划以及基于难以辨别关系等技术。然而由于种种原因，这些方法均不能奏效。实际中受到普遍欢迎的是基于目标函数的聚类方法，它具有设计简单、解决问题的范围广，最终可以归结为优化问题等优点。因此随着计算机的发展，该方法成为模糊聚类分析的主要手段。基于目标函数的模糊聚类方法首先由Ruspini提出，但真正有效的算法---模糊c-均值算法却是由Dunn给出的。Bezdek又将其进一步扩展，建立起模糊聚类理论。从此，该类模糊聚类蓬勃发展起来，目前已形成庞大的体系。2.2聚类算法实现途径的研究进展基于目标函数的模糊聚类实际上是一个非线形规划问题。因此也必然存在对初始化敏感、容易陷入局部极值点、求解过程缓慢等局限。为此，人们在算法实现的途径方面进行着不懈的努力，借助各种技术寻求快速最优聚类的新方法。现有聚类目标函数优化方法大致可以分为基于梯度、神经网络和进化计算三种途径2.3聚类有效性研究进展对于给定的数据集，如果己知有聚类结构，则需要用算法来确定这个结构。而大多数聚类算法需要事先给定数据集的聚类数，如果聚类数选取的不合适，会使划分结果与数据集的真正结构不相符，从而导致分类失败。关于数据集的最佳聚类数确定问题属于聚类有效性范畴。2.4模糊聚类的应用模糊聚类理论的发展推动了它在生产实践中的应用。由于模糊聚类的强大功能，使得它已经在众多的领域获得令人瞩目的成功应用。而且随着理论的不断发展和完善，必将发挥更大的作用。鉴于模糊聚类与模式识别的天然联系，使得它在识别领域首先获得了最为广泛的应用；其次，在图像处理中经常需要处理无监督的分类问题，因此理所当然的成为重要的分析工具；此外，在通讯系统中的信道均衡、矢量量化编码中的码书设计、时间序列的预测、RBF神经网络的训练、参数估计、医学诊断、气候分类、食品分类、水质分析等领域中也发挥着重大的作用。以下我们主要从模式识别和图像处理等方面综括模糊聚类的应用。2.4.1模糊聚类在模式识别中的应用在模式识别中，两个最主要的分支为有监督的分类和无监督分类两个方面，其中无监督分类与聚类分析相对应。在没有训练样本的情况下，模糊聚类可根据数据集的内在结构通过机器学习自动划分特征空间，达到自动分类的目的。特征维数很大的情况下，不但耗时，而且分类效果也不一定好，甚至会造成“维数灾难”。Bezdek等人提出用模糊聚类进行特征优选，在分类效果影响不大的条件下大大压缩了布尔特征维数。如何对一般非布尔变量的特征进行优选将是一个很有意义的研究课题。Hough变换在线条检测中获得了广泛的应用，但峰值检测问题一致困绕着Hough变换的实际应用，Jolion等人提出基于模糊聚类的峰值检测方法，使得Houg变换不用人为干预，从而可以自动实现。在一些具体的应用方面，模糊聚类也获得了广泛应用。比如，Chan，Zhang和吴佑寿等人分别用模糊聚类做汉字字符识别的预分类，得到了较好的分类效果；Huang等在语音识别应用模糊聚类也获得成功；Huang等提出用模糊聚类进行雷达回波库的建立和分类；Bezdek等还利用模糊聚类提取分类规则，用以设计基于If—Then规则的分类器，实验结果均证明了该方法的有效性；同时Antonio等用模糊聚类进行系统辨识，获得了优于神经网络方法的结果；此外，在不变性模式识别、物体检测等领域也同样获得了成功的应用。2.4.2模糊聚类在图像处理中的应用图像处理是计算机视觉的重要组成部分，由于人视觉的模糊性使图像处理适合模糊处理，同时训练样本图像的匮乏又要求无监督处理分析，而模糊聚类正好满足这两方面的要求，于是模糊聚类在图像处理中发挥着不可替代的作用。模糊聚类在图像处理中最为广泛的应用为图像分割。由于图像分割问题可以等效为图像灰度的无监督分类，因此早在1979年Coleman和Andrews就提出用聚类算法进行图像分割，此后，随着模糊聚类理论的发展，人们又结合塔型结构、小波分析等一些新技术，提出了多种基于模糊聚类的灰度图像分割新方法，并且在纹理图像分割、彩色图像分割、序列图像分割、遥感图像分割等方面获得了很大的进展。另外，基于模糊聚类的方法在边缘检测、图像增强、图像压缩、曲线拟合等众多方面的研究也取得了丰硕的成果。参考文献1.张弢，纪德云。模糊聚类分析法。沈阳大学学报2.谢维信，高新波，裴继红。模糊聚类理论发展及其应用。中国体视学与图像分析3.李希灿，解明东。模糊聚类与模糊识别理论模型研究。模糊系统与数学