模糊C均值聚类算法

模糊C均值聚类算法：

模糊c均值聚类（FCM），即众所周知的模糊ISODATA，是用隶属度确定每个数据点属于某个聚类的程度的一种聚类算法。1973年，Bezdek提出了该算法，作为早期硬c均值聚类（HCM）方法的一种改进。

FCM把n个向量xi（i=1,2,…,n）分为c个模糊组，并求每组的聚类中心，使得非相似性指标的价值函数达到最小。FCM与HCM的主要区别在于FCM用模糊划分，使得每个给定数据点用值在0，1间的隶属度来确定其属于各个组的程度。与引入模糊划分相适应，隶属矩阵U允许有取值在0，1间的元素。不过，加上归一化规定，一个数据集的隶属度的和总等于1：

ui1cij1,j1,...,n (3.1)

那么，FCM的价值函数（或目标函数）就是：

m2J(U,c1,...,cc)Jiuijdiji1i1jccn， (3.2)

这里uij介于0，1间；ci为模糊组I的聚类中心，dij=||ci-xj||为第I个聚类中心与第j个数据点间的欧几里德距离；且m1,是一个加权指数。

构造如下新的目标函数，可求得使（3.2）式达到最小值的必要条件：

cJ(U,c1,...,cc,1,...,n)J(U,c1,...,cc)j1j(uij1)i1nudj(uij1)mij2iji1jj1i1cnnc (3.3)

这里j，j=1到n，是（3.1）式的n个约束式的拉格朗日乘子。对所有输入参量求导，使式（3.2）达到最小的必要条件为：

ucij1nj1nmijxjumij (3.4)

和

1dijk1dkjc2/(m1)uij (3.5)

由上述两个必要条件，模糊c均值聚类算法是一个简单的迭代过程。在批处理方式运行时，FCM用下列步骤确定聚类中心ci和隶属矩阵U[1]：

步骤1：用值在0，1间的随机数初始化隶属矩阵U，使其满足式（3.1）中的约束条件

步骤2：用式（3.4）计算c个聚类中心ci，i=1,…,c。

步骤3：根据式（3.2）计算价值函数。如果它小于某个确定的阀值，或它相对上次价

值函数值的改变量小于某个阀值，则算法停止。

步骤4：用（3.5）计算新的U矩阵。返回步骤2。

上述算法也可以先初始化聚类中心，然后再执行迭代过程。由于不能确保FCM收敛于一个最优解。算法的性能依赖于初始聚类中心。因此，我们要么用另外的快速算法确定初始聚类中心，要么每次用不同的初始聚类中心启动该算法，多次运行FCM。