FCM聚类算法介绍

FCM 聚类算法介绍 FCM 聚类算法是基于划分的聚类算法，它的思想就是使得被划分到同一簇的对象之间相似度最大，而不同簇之间的相似度最小。模糊 C 均值算法是普通 C 均值算法的改进，普通 C 均值算法对于数据的划分是硬性的，而 FCM 则是一种柔性的模糊划分。 在介绍 FCM 具体算法之前，我们先介绍一些模糊集合的基本知识。模糊集基本知识首先说明隶属度函数的概念。隶属度函数是表示一个对象 x 隶属于集合 A 的程度的函数，通常记做 μA(x)，其自变量范围是所有可能属于集合 A 的对象（即集合 A 所在空间中的所有点），取值范围是[0,1]，即 0<=μA(x)<=1。μA(x)=1 表示 x 完全隶属于集合 A，相当于传统集合概念上的 x∈A。 模糊集合的概念是指定义在空间 X={x}上的隶属度函数，或者叫定义在论域 X={x}上的模糊子集。对于有限个对象 x1，x2，……，xn，模糊集合可以表示为： 有了模糊集合的概念，一个元素隶属于模糊集合就不是硬性的了，在聚类的问题中，可以把聚类生成的簇看成模糊集合，因此，每个样本点隶属于簇的隶属度就是 [0，1]区间里面的值。 K 均值聚类算法（HCM）是一种常用的聚类算法，它的核心思想是把 n 个向量 xj（1,2…,n）分为 c 个组 Gi(i=1,2,…,c)，并求每组的聚类中心，使得非相似性（或距离）指标的价值函数（或目标函数）达到最小。 价值函数可定义为： 这里是组 i 内的价值函数。这样 Ji 的值依赖于 Gi 的几何特性和 ci 的位置。一般来说，可用一个通用距离函数 d(xk,ci)代替组 I 中的向量 xk，则相应的总价值函数可表示为： 为简单起见，这里用欧几里德距离作为向量的非相似性指标，且总的价值函数表示为（6.2）式。划分过的组一般用一个 c×n 的二维隶属矩阵 U 来定义。如果第 j 个数据点 xj 属于组 i，则 U 中的元素 uij 为 1；否则，该元素取 0。 一旦确定聚类中心 ci，可导出如下使式（6.2）最小 uij： 重申一点，如果 ci 是 xj 的最近的聚类中心，那么 xj 属于组 i。由于一个给定数据只能属于一个组，所以隶属矩阵 U 具有如下性质： 且 另一方面，如果固定 uij 则使（6.2）式最小的最佳聚类中心就是组 I 中所有向量的均值： 这里|Gi|是 Gi 的规模或。 为便于批模式运行，这里给出数据集 xi（1，2…，n）的 K 均值算法；该算法重复使用下列步骤，确定聚类中心 ci 和隶属矩阵 U： 步骤 1：初始化聚类中心 ci,i=1,…,c。典型的做法是从所有数据点中任取 c 个点。 步骤 2：用式（6.4）确定隶属矩阵 U。 步骤 3：根据式（6.2）计算价值函数。如果它小于某个确定的阀值，或它相对上次价值函数质的改变量小于某个阀值，则算法停止。 步骤 4：根据式（6.5）修正聚类中心。返回步骤 2。 该算法本身是迭代的，且不能确保它收敛于最优解。K 均值算法的性能依赖于聚类中心的初始位置。所以，为了使它可取，要么用一些前端方法求好的初始聚类中心；要么每次用不同的初始聚类中心，将该算法运行多次。 此外，上述算法仅仅是一种具有代表性的方法；我们还可以先初始化一个任意的隶属矩阵，然后再执行迭代过程。K 均值算法也可以在线方式运行。这时，通过时间平均，导出相应的聚类中心和相应的组。即对于给定的数据点 x，该算法求最近的聚类中心 ci，并用下面公式进行修正： 这种在线公式本质上嵌入了许多非监督学习神经元网络的学习法则。 模糊 C 均值聚类（FCM）是一种基于模糊划分的聚类算法， FCm 把 n 个向量 xi（i=1,2,…,n）分为 c 个模糊组，并求每组的聚类中心，使得非相似性指标的价值函数达到最小。FCM 与 HCM 的主要区别在于 FCM 用模糊划分，使得每个给定数据点用值在 0，1 间的隶属度来确定其属于各个组的程度。 与引入模糊划分相适应，隶属矩阵 U 允许有取值在 0，1 间的元素。不过，加上归一化规定，隶属矩阵 U 满足下面的公式： FCM 算法的主要步骤如下： 步骤 1：初始化聚类中心 ci,i=1,…,c。 步骤 2：用式（6.4）确定隶属矩阵 U。 步骤 3：根据式（6.2）计算价值函数。如果它小于某个确定的阀值，或它相对上次价值函数质的改变量小于某个阀值，则算法停止。 步骤 4：根据式（6.5）修正聚类中心。返回步骤 2。 FCM 算法的性能依赖于聚类中心的初始位置。所以，为了使它可取，要么用一些前端方法求好的初始聚类中心；要么每次用不同的初始聚类中心，将该算法运行多次。此外，上述算法仅仅是一种具有代表性的方法；我们还可以先初始化一个任意的隶属矩阵，然后再执行迭代过程。 FCM 算法也可以在线方式运行。这时，通过时间平均，导出相应的聚类中心和相应的组。即对于给定的数据点 x，该算法求最近的聚类中心 ci，并用下面公式进行修正： 这种在线公式本质上嵌入了许多非监督学习神经元网络的学习法则。 FCM 聚类算法是一种基于模糊划分的聚类算法，它可以柔性地对数据进行划分，且可以在线方式运行。FCM 算法的主要优点是可以处理不确定性和噪声数据，且可以在线方式运行。但是，FCM 算法的性能依赖于聚类中心的初始位置，需要选择合适的初始聚类中心以确保算法的收敛性。