模糊聚类

引言

前面我们讲了k-means, k-means属于一种硬聚类的方法，也就是说一个样本属于哪个类了后，他就是哪个类别的了，非此即彼，来不得半点马虎。但是现实生活中，哪有这么多的确定的事啊，身不由己经常发生，因此引入了模糊聚类，英文名Fuzzy c-means clustering, 模糊聚类意味着样本不再是刚性的属于某一类别了，而是给出其属于各个类别的概率。因此称之为模糊聚类。

模糊聚类

在k-means算法中我们尝试给每个样本聚到某一个类中，也就是给样本一个标签。在模糊聚类中，对于某一个样本，不再是将其赋予某一个标签，而是一个概率向量，这个向量表示样本分别属于这k个类别的概率。

正常将，我们要将n个样本模糊聚类到c个类中，就是要学习一个隶属度矩阵，矩阵表示的就是n个样本模糊聚类到c个类中的概率。

令：

$$x = \left \{ x_1,x_2,x_3,...,x_n \right \} \qquad$$

表示 $n$ 个样本

$$c = \left \{ c_1,c_2,...,c_k \right \} \qquad$$

表示$k$个类别

那么所谓的隶属度矩阵就如下所示：

$$U= \begin{pmatrix} u_{11} & ... & u_{1k}\\ ...& &... \\ u_{n1} & ... & u_{nk} \end{pmatrix}$$

其中$\sum_{j=1}^k u_{pj} =1 \qquad$ 其中 $p\subset [1,n] \qquad$

也就是说每一个样本，他属于所有类别的概率的和为1。明显这是合理的。

下面我们来推导一下如何学习这个隶属度矩阵。

隶属度矩阵

在任何的机器学习算法中，都有一个核心点，那就是把在数据集上构建机器学习模型的问题转化为最小化代价函数的问题，模糊聚类也是一样的。

首先我们定义下代价函数：

$$J(U,k) = \sum_{i=1}^k \sum_{j=1}^n u_{ij}^m d_{ij}^2 \qquad$$

其中 $d_{ij}^2 = || x_j - c_i ||^2 \qquad$ $v_i$ 表示聚类的中心点 $\qquad m$为模糊系数

我们的目标就是最小化函数$J(U,k)$, 即$min( J(U,k) )$

在约束条件$\sum_{j=1}^k u_{pj} =1$下求极值，自然想到了拉格朗日乘子法。

$$J(U,k) = \sum_{i=1}^k \sum_{j=1}^n u_{ij}^m d_{ij}^2 + \sum_{j=1}^n \lambda_j(\sum_{i=1}^k u_{ij} -1 )$$

求偏导：

$$\frac{\partial J }{\partial u_{ij}} = m u_{ij}^{m-1} d_{ij}^2 + \lambda_j = 0$$

所以$u_{ij}^{m-1} = - \frac{\lambda_j}{m d_{ij}^2}$

所以在$u_{ij} = (- \frac{\lambda_j}{m d_{ij}^2})^{ \frac{1}{m-1}}$函数取极小值。

而将此值带如到函数$\sum_{i=1}^k u_{ip} =1$中，有：

$$\sum_{i=1}^k u_{ip} = \sum_{i=1}^k (-\frac{\lambda_j}{m})^{\frac{1}{m-1}} (\frac{1}{d_{ip}^2})^{\frac{2}{m-1}}= 1$$

所以有：

$$(-\frac{\lambda_j}{m})^{\frac{1}{m-1}} = \frac{1}{\sum_{i=1}^k ({d_{ip}})^{\frac{-2}{m-1}}}$$

将其带入到$u_{qp} = (- \frac{\lambda_j}{m d_{qp}^2})^{ \frac{1}{m-1}}$中，可得

$$u_{qp} = (-\frac{\lambda_j}{m})^{\frac{1}{m-1}} (\frac{1}{d_{qp}^2})^{\frac{1}{m-1}} = \frac{1}{ \sum_{i=1}^k (\frac{d_{qp}}{d_{ip}})^{\frac{2}{m-1}} }$$

这个表示样本到k个类的中心点的距离的和除以样本到第q个分类点的距离的$\frac{2}{m-1}$次方的倒数。

这里我们得到了隶属度矩阵的求解方法，但是这里面需要计算$d_{ij}^2 = || x_j - c_i ||^2 \qquad$ 这里面需要求解$c_i$，因此继续对拉格朗日函数求偏导，有

$$\frac{\partial J }{\partial c_i} = \sum_{j=1}^{n} u_{ij}^m *2* ||x_j-c_i||= 0$$

因此有：

$$c_i = \frac{ \sum_{j=1}^{n} u_{ij}^m x_j }{\sum_{j=1}^{n} u_{ij}^m}$$

因此我们得到了更新聚类中心点和隶属度矩阵的方程，如下所示：

$$u_{qp} = (-\frac{\lambda_j}{m})^{\frac{1}{m-1}} (\frac{1}{d_{qp}^2})^{\frac{1}{m-1}} = \frac{1}{ \sum_{i=1}^k (\frac{d_{qp}}{d_{ip}})^{\frac{2}{m-1}} }$$ $$c_i = \frac{ \sum_{j=1}^{n} u_{ij}^m x_j }{\sum_{j=1}^{n} u_{ij}^m}$$

因此模糊聚类算法如下：

模糊聚类算法步骤

1) 根据给定的聚类类别个数$k$ ，随机初始化隶属度矩阵$U$
2) 计算$c_i$
3) 更新初始化隶属度矩阵$U$
4) 重复上面的步骤，直到满足停止条件为止，停止条件可以是中心点$c_i$不再变化或者初始化隶属度矩阵$U$ 变化很小为止。

实例分析