一种分布式的模糊聚类方法

阎俊梅

（山西大同大学数学与计算机科学学院，山西大同 037009）

一种分布式的模糊聚类方法

阎俊梅

（山西大同大学数学与计算机科学学院，山西大同 037009）

由于FCM算法中的初始值需要随机的设定，这种随机性不能保证每次都能达到全局最优，也就是说如果初始聚类中心的设置具有全局的特点，那么聚类的结果才能达到全局最优。因此主要针对模糊c-均值（FCM）聚类算法对初始值很敏感，而且容易陷入局部最优解的这一特点，提出了一种分布式的模糊聚类方法。首先用分治法得到模糊聚类的全局的聚类中心值，然后再用FCM进行聚类，从而克服FCM算法对初始值敏感和容易陷入局部最优解的缺陷，达到全局最优。经仿真实验证明结果是很理想的。

聚类分析；分治方法；大数据集

聚类分析［1］就是通过无监督训练将样本按相似性分类，把相似性大的样本归为一类，占据特征空间的一个局部区域，而每个局部区域的聚类中心又起着相应类型的代表的作用。聚类［2］可以采用不同的算法过程，但归结起来大致可分为3类方法：系统聚类、逐步分解和判别聚类。

系统聚类和逐步分解，都是一种局部的考虑，在实现过程中均没有考虑保持群体的全局分布特性；判别聚类［3］虽然当聚类中心的选取符合全局分布特性时也会产生很好的结果，但是由于这种选取的随机性，不可能每次都能选到符合全局分布特性［4］的聚类中心点。因此，我们需要寻找一种考虑保持群体全局分布特征的方法，而寻找具有全局分布［5］特征的聚类中心点就是一条很好的捷径。鉴于此，提出了一种分布式的聚类方法从而得到全局的聚类中心值。

1 分布式聚类方法的基本思想

将大数据集随机分成若干个子集，再对每个子集利用硬k-均值或者是FCM算法［6］进行聚类，且每个子集的聚类中心数的设置与原来用FCM算法聚类时设置的聚类中心数一样。计算每两个子集之间的距离矩阵，然后局部合并，即每一子集的每一个类应该与另一个子集的哪一个类相合并，最后进行全局合并。由全局合并的结果计算初始的全局聚类中心值，然后再用FCM算法进行聚类。

1.1 距离矩阵的建立

距离矩阵存放的是任何两个子集之间的欧氏距离，距离矩阵中的每一维存放的是一个子集中的一个类的聚类中心与另一子集中的一个类的聚类中心的欧氏距离。

如果在每个子集中有C类，那么一个距离矩阵的维数为C×C。如果一共有N个子集，那么一共有个距离矩阵。

例表1为A子集与B子集之间的距离矩阵：A子集和B子集分别有3类，在距离矩阵中的每一行代表A子集中所有类，每一列代表B子集中所有类。

其中A1，A2，A3分别代表A子集的第一类，第二类，第三类；B1，B2，B3分别代表B子集的第一类，第二类，第三类。

那么AiBj代表A的第i类的距离中心与B的第j类的距离中心之间的欧氏距离。

如A2B3代表A子集的第2类与B子集的第3类的聚类中心的欧氏距离。

表1 A，B子集之间的距离矩阵

1.2 局部矩阵的建立

根据一个距离矩阵得到两个子集之间的相应关系。即第一个子集的某一个类应该与第二个子集的哪一个类相合并。

因为由一个距离矩阵可得到一个局部矩阵，所以如果一共有N个子集，那么局部矩阵的个数为，即与距离矩阵的个数相同。

局部矩阵的建立过程：

1）首先遍历一个距离矩阵的所有维，找到欧氏距离值最小的一个，记下它的行数和列数，并存在局部矩阵中。

2）在距离矩阵中除去已经找到的那个维，然后继续搜索其他所有的维，然后再找到值最小的一个维。

3）同理直到把局部矩阵所有的维填满为止。

1.3 全局矩阵的建立

假如一共有3个子集S1，S2，S3，且每个子集有3类。得到的局部矩阵如表2和表3所示。其中S1中的第二类和S2中的第二类为一类；S1中的第一类与S2中的第一类为一类；S1中的第三类与S2中的第三类为一类。S2中的第三类与S3中的第一类为一类；S2中的第一类与S3中的第三类为一类；S2中的第二类与S3中的第二类为一类。以S2为中介来进一步建立S1、S2与S3之间的关系。

表2 S1，S2子集之间的局部矩阵

表3 S2，S3子集之间的局部矩阵

那么根据局部矩阵可得到的全局矩阵为表4所示：

表4 由表2和表3的局部矩阵得到的全局矩阵

表4表明子集S1的第二类、子集S2的第二类以及子集S3的第二类合并为一类；子集S1的第一类、子集S2的第一类以及子集S3的第三类合并为一类；子集S1的第三类、子集S2的第三类以及子集S3的第一类合并为一类。

2 基于分治法的初始化算法

1）把数据随机分成M个子集。

2）对每个子集用FCM算法或者是C-均值聚类算法去聚类。

3）按照1.1建立距离矩阵。

4）按照1.2建立局部矩阵。

5）按照1.3建立全局矩阵。

6）对全局矩阵利用加权算术平均数来计算全局的聚类中心。

以图4表示的全局矩阵为例来说明聚类中心的计算过程：

如果S1中的第二类有L1个数据，聚类中心为（x1，y1）；S2中第二类有L2个数据，聚类中心为（x2，y2）；S3中第二类有L3个数据，聚类中心为（x3，y3）。那么由这几个类组成的类的全局聚类中心为：

（L1×（x1，y1）+L2×（x2，y2）+L3×（x3，y3））/（L1+L2+L3）

同理可以得到另外两个全局聚类中心点。

7）利用模糊c-均值进行聚类。

通过上述算法得出的聚类中心点的初始坐标.将其代入到FCM算法中进行聚类。

3 仿真实验

从不同的起始群体出发，多次运用分治法，然后将找到的最优的初始值代入到FCM算法继续进行聚类分析。

经过统计分析，分类结果中有80％比单一使用FCM算法的分类结果要好。

图1是其中的一次基于分治法的初始化方法的聚类结果，聚类结果比较清晰，效果较好。且速度比直接用FCM算法聚类快。

图1 基于分治法的初始化方法聚类效果

4 实验结论

通过对基于分治法的初始化方法进行数据仿真实验，我们可以看出该聚类方法找到了保持全局特性的聚类中心初值，而将其与FCM算法结合起来进行处理，克服了FCM算法对初始值敏感和容易陷入局部最优解的缺陷，从而得到了理想的结果。通过实验表明，利用基于分治法的初始化方法进行模糊聚类分析寻找到的空间聚类中心保持了很好的全局分布特性，使聚类效果更加理想。

［1］郑岩，黄蓉怀，站晓苏.基于遗传算法的动态模糊聚类［J］.北京邮电大学学报，2005，28（1）：23-27.

［2］Hoppner F.Speeding up fuzzy c-Means：using a hierarchical data organization to control the precision of membership calculation［J］.Fuzzy Sets and Systems，2002，128（3）：30-50.

［3］张莉，周伟达，焦李成.核聚类算法［J］.计算机学报，2002，25（6）：587-590.

［4］董云影，张运杰，畅春玲.改进的遗传模糊聚类算法［J］.模糊系统与数学，2005，5（10）：12-15.

［5］韩璞，张欣，王兵，等.基于神经网络的交互式炉膛火焰图像识别［J］.中国电机工程学报，2008，28（20）：19-25.

［6］李培强，李欣然.模糊神经网络负荷模型的内插外推能力［J］.高电压技术，2008，34（6）：82-85.

〔编辑 高海〕

A Distributed Fuzzy Clustering Method

YAN Jun-mei
（School of Mathematics and Computer Science，Shanxi Datong University，Datong Shanxi，037009）

The initial values in FCM algorithm are setted randomly，so it can not ensure to get to globle optimization.That is，if the initial clustering center values are globle，the clustering results can get to globle optimization.So this paper proposes a distributed fuzzy clustering method.Firstly get the globle clustering center values of FCM using distributed method，then cluster the datas using the globle clustering center values in FCM.So it can overcome the sensitive of FCM algorithm to initial values and the fault of easily to get local optimization，and get to globle optimization.Experimental results show the method has exact clustering result.

clustering analysis；distributed method；large data set

TP18

A

1674-0874（2011）01-0003-02

2010-10-20

国家科技部高新技术计划资助项目［2005EJ000017］；河北省科技研究与发展计划资助项目［02547015D］；河北省普通高等学校博士科研资助基金［B2002118］

阎俊梅（1981-），女，山西天镇人，硕士，助教，研究方向：数据挖掘。