一种混合模糊聚类算法

一种混合模糊聚类算法

【摘要】将传递闭包方法与FCM方法结合，提出一种混合模糊聚类算法，使其不需要预先设定聚类数目，并且能够降低它对初始化的敏感程度，收敛速度更快，且不用人为给定聚类类别数，不容易受初始化的影响。
【关键词】传递闭包-统计量模糊-均值聚类
聚类是按照一定的要求和规律对事物进行分类的过程，它根据研究对象的某些特性，运用数学方法对给定对象进行区分和分类。自Zadeh提出模糊集理论以来，人们开始用模糊的方法来处理聚类问题，并称之为模糊聚类分析。
现有的模糊聚类算法都是以某种准则来评价一个己给定划分的特性的，通常在参数输入、停机条件上存在诸多人为控制因素，这导致了用户在使用聚类方法时需要大量的数据分析领域知识。另外，有些聚类算法只能对某种分布数据聚类效果较好，对其它分布的数据聚类效果则很差。许多聚类算法是根据欧氏距离和Manhattan距离来进行聚类的，基于这类距离的聚类方法一般只能发现具有类似大小和密度的圆形或球状聚类。比如现在比较流行的-Means和模糊-Means聚类算法，既需要提供参数―聚类数目，而且对非球状或椭球型分布的数据集聚类效果不理想。因而需要设计一种好的聚类算法来提高算法的自主性和适应性，减少用户的参与。
一、传递闭包法聚类
（1）建立模糊相似矩阵。设X={x1，x2，…，xn}为被分类对象的全体，设每一对象xi由一组特征数据（xi1，xi2，…，xim）来表征，于是可以得到原始数据矩阵Xnxm=[xij]。
为了使不同量纲的数据也能进行比较，常常需要将原始数据矩阵进行极差化或标准化。这里先将原始数据矩阵统一趋势化，得到无量纲矩阵X'nxm=（x"ij），其中x.ij=|xij-ui0|/iqr（xij）
iqr（xij）表示四分位极差。
按照普通的聚类方法中相似系数确定方法，建立模糊相似矩阵与，xi与xj的相似程度rij可根据实际情况采用相似系数法、距离法以及其它方法。
（2）由相似矩阵求等价矩阵。因为模糊等价矩阵能对论域进行等价的划分，这就能满足聚类分析的需要。然而，通常情况下，由标定过程构造出的模糊关系仅仅能满足自反性和对称性，而不满足传递性，所以生成的只是一个模糊相似矩阵R。为了进行分类，需要根据标定所得模糊矩阵R，求出其传递闭包t（R）。R=t（R）为模糊等价矩阵。
（3）进行聚类。将λ从1依次取到0，依次截得等价关系Rλ，并按Rλ将X分成等价类。
二、利用FCM算法得到最终分类
（1）确定FCM的聚类类别数c。将人从1依次取到0，形成一种动态聚类，便于全面了解样本聚类，然后根据实际需要选择某阈值λ，确定样本一种分类。如何合理选择阈值λ，笔者用F-统计量选择λ最佳值。F值越大，分类越合理，将这时的分类数目作为FCM的聚类类别数c。
（2）FCM算法。Step1：将F-统计值最大的阈值λ对应的分类数目r作为聚类类别数c，2≤c≤n，n是数据个数，给定加权指数m，设定迭代停止阈值ε，初始化聚类中心V（0），设置迭代计数器b=0；
Step2：根据（式1.1）计算或更新划分矩阵U（b）=[μik]；
其中，dik为无量纲矩阵中X.第k个序列到第i类中心vi的欧氏距离。
Step3：根??（式1.2）更新聚类中心V（b+1）：
Step4：如果‖V（b）-V（b+1）‖≤ε，则算法停止并输出划分矩阵U和聚类中心V；否则令b=b+1，转向执行Step2。
若μjk=max{μjk}，则xk∈第j类。
同样，该算法也具有另一种形式，即从初始化模糊划分矩阵开始，先用（式1.2）计算聚类中心矩阵，然后用（式1.1）更新模糊分类矩阵，直到满足停止准则为止。
对比可知，这种混合模糊聚类法比传统FCM方法更切合实际，收敛速度更快，且不用人为给定聚类类别数，不容易受初始化的影响。
三、结论
本文针对经典的模糊C均值聚类算法需要事先确定聚类类数，设定初始聚类中心的缺点，提出改进的FCM算法，即一种混合模糊聚类算法。先利用传递闭包法得到一系列分类，再引入F-统计量，根据F-统计值的大小确定一种分类，以最大的F-统计值对应的一种分类的类数作为FCM聚类的类别数C，以这种分类的聚类中心作为FCM算法的初始聚类中心。此方法能够反映出原始数据的真实特性，真正达到聚类分析的无监督性；同时也降低了由于人为因素造成的不确定性影响，增强了聚类结果的准确性和可信度。
参考文献：
[1]高新波.模翊聚类分析及其英语[M].西安：西安电子科技大学出版社，2004.
[2]王洪春，彭宏.一种基于嫡的聚类算法[J].计算机科学，2007.
[3]路金芳，孙双全，杨建燕，伍化岩.统计学原理[M].河南：黄河水利出版社，2006.
[4]HALKIDIM，VAZIRGIANNISM.Adatasetorientedapproachforclusteringalgorithmselection[C]//Procofthe5thEuropeanConferenceonPrinciplesofDataMiningandKnowledgeDiscov-ery.London：SpringerVerlag，2001.