rambo

聚类(三)Fuzzy c-means

经典k-均值聚类算法的每一步迭代中,每一个样本点都被认为是完全属于某一类别。我们可以放松这个条件,假定每个样本x_{j}模糊“隶属”于某一类的。

硬聚类把每个待识别的对象严格的划分某类中,具有非此即彼的性质;模糊聚类建立了样本对类别的不确定描述,更能客观的反应客观世界,从而成为聚类分析的主流。

  • 隶属度函数是表示一个对象x隶属于集合A的程度的函数,通常记做\mu_{A}(x),其自变量范围是所有可能属于集合A的对象(即集合A所在空间中的所有点),取值范围是[0,1],即0\leq\mu_{A}(x)\leq 1
  • μA(x)=1表示x完全隶属于集合A,相当于传统集合概念上的x∈A。

对下述目标函数最小化:J_{m}=\sum_{i=1}^{N}\sum_{j=1}^{C}u_{ij}^{m}\lVert x_{i}-c_{j}\rVert^{2},1\leqm<\infty

其中,m\in[1,\infty]是一个加权指数,u_{ij}x_{i}在类j中的隶属度,x_{i}为第i个d维观测数据,c_{j}为聚类中心。

构造拉格朗日方程:QQ截图20150911001003

\lambda_{i}(i=1,2,...,n)是拉格朗日乘子。

求导,求极值。模糊划分(Fuzzy Partion)通过下列两式的更新迭代来使得上述目标函数达到极小:

QQ截图20150911001425

归一化规定: 一个样本(数据集)的隶属度的和等于1,\sum_{j=1}^{c}\mu_{ij}=1,?? i=1,...,n

image027时迭代终止,0<\epsilon<1k为迭代次数。该过程收敛到J_{m}的一个局部极小值或鞍点(saddle point)。

算法流程:

  • 用值在0~1间的随机数初始化隶属矩阵U;(也可以先初始化聚类中心,然后再执行迭代过程)
  • 计算c个聚类中心c_{j},j=1,?,c
  • 计算目标函数,如果它小于某个确定的阈值,或它相对上次值的改变量小于某个阈值,则算法停止;
  • 计算新的U矩阵,返回步骤2。

QQ截图20150910235137

如上所述,数据属于某个类是由隶属度函数确定的,这正是该算法的模糊行为的体现。在该算法中用一个由0和1之间元素组成的矩阵表达对象与类别的隶属关系。

例1、一个一维的例子来说,给定一个特定数据集,分布如下图:

image031

图中可以很容易分辨出两类数据,分别表示为‘A’ and ‘B’. 利用前述的k-means 算法,每个数据关联一个特定的质心,隶属度函数如下所示:

image033

用FCM 算法,同一个数据并不单独属于一个分类,而是可以出现在中间。在这个例子中,隶属函数变得更加平滑,表明每个数据可能属于几个分类。

image035

上图中,红色点表示的数据更可能属于类别B,而不是A, ‘m’ 的值0.2表明了数据对A的隶属程度。引入一个矩阵,其元素取自隶属函数:

QQ截图20150911003219

矩阵的行数和列数取决于数据和类别的个数,确切的说,行数表示数据个数,列数表示类别个数,矩阵元素表示为 \mu_{ij}。上面的例子中,我们考虑了k-means (a) and FCM (b) 的例子,可以看出在第一个例子(a) 中的稀疏总是二值,表明每个数据只能属于一个分类,其他属性表示如下:

QQ截图20150911003450

例2、20个数据点和3个聚类中心。m=2

image046

当迭代终止条件image048,迭代步数为8。

image049

\epsilon=0.01,迭代步数为37。

image051

FCM特点:

  • 不能确保FCM收敛于一个最优解,算法的性能依赖于初始聚类中心。因此,要么用另外的快速算法确定初始聚类中心,要么每次用不同的初始聚类中心,多次启动FCM算法;
  • Bezdek引入了加权指数m,是从硬聚类准则函数到软聚类目标函数的推广;
  • m又称为平滑因子,控制着模式在模糊类间的分享程度,最佳的m的选取目前还缺乏理论,尽管存在一些经验值或经验范围,但没有面向问题的优选方法,也缺少参数m的有效性评价准则;
  • 加权指数m控制着聚类的模糊性。m越接近于1,聚类越趋向于突变(crisp),m越大,结果越模糊、相对更易于反映空间的渐变性,但过大的m值将导致类别间的重叠太多,聚类结构不清晰,因此对m的选取需要在模糊度与清晰的聚类结构间进行权衡。一般m的有效值在1~30之间,部分文献建议1.5~2.5(于剑,2003;高新波,2004)。在研究中可选择多个m对结果进行比较,以选择合适的m。
  • 尽管模糊聚类是一种无监督的分类,但现在的聚类算法却需要应用聚类原型的先验条件,否则算法会产生误导;
  • 模糊聚类目标是非凸的,计算过程是迭代爬山,容易陷入局部极值点,得不到最优解;大数据量下算法耗时也是一大难题;
  • 算法是针对特征空间中的点集设计的,对于特殊类型的数据,比如在样本每维特征的赋值不是一个数,而是一个区间、集合和模糊数时,无法直接处理。

参考资料:

1)http://home.deib.polimi.it/matteucc/Clustering/tutorial_html/cmeans.html

2)Duda,《模式分类》 第10章

3)J. C. Dunn (1973): "A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters", Journal of Cybernetics 3: 32-57

4)J. C. Bezdek (1981): "Pattern Recognition with Fuzzy Objective Function Algoritms", Plenum Press, New York

5)Tariq Rashid: “Clustering”   http://www.cs.bris.ac.uk/home/tr1690/documentation/fuzzy_clustering_initial_report/node11.html

6)Hans-Joachim Mucha and Hizir Sofyan: “Nonhierarchical Clustering”     http://www.quantlet.com/mdstat/scripts/xag/html/xaghtmlframe149.html