模糊C均值聚类简述

模糊C均值聚类简述

By:Yang Liu
1.什么是模糊C均值聚类
模糊c-均值聚类算法 fuzzy c-means algorithm (FCMA)或称（ FCM）。通过优化目标函数得到每个样本点对所有类中心的隶属度，从而决定样本点的类属以达到自动对样本数据进行分类的目的。无监督机器学习的主要技术之一。
2.模糊C均值聚类涉及的数学方法——拉格朗日乘数法
设给定二元函数z=ƒ(x,y)和附加条件φ(x,y)=0，为寻找z=ƒ(x,y)在附加条件下的极值点，先做拉格朗日函数 $F(x,y,\lambda ) = f(x,y) + \lambda \varphi (x,y)$F(x,y,λ)=f(x,y)+λφ(x,y)，其中λ为参数。
令F(x,y,λ)对x和y和λ的一阶偏导数等于零，即
F’(x)=ƒ’x(x,y)+λφ’x(x,y)=0
F’(y)=ƒ’y(x,y)+λφ’y(x,y)=0
F’(λ)=φ(x,y)=0
由上述方程组解出x,y及λ，如此求得的(x,y)，就是函数z=ƒ(x,y)在附加条件φ(x,y)=0下的可能极值点。
若这样的点只有一个，由实际问题可直接确定此即所求的点。
3.模糊C均值聚类的过程简述
隶属度函数是表示一个对象x隶属于集合A的程度的函数，其自变量范围是所有可能属于集合A的对象，取值范围是[0,1]。用$u$u表示。
模糊C均值聚类，需要两个参数一个是聚类数目，另一个是一个控制算法的柔性的参数。
算法的输出是聚类中心点向量和一个模糊划分矩阵，这个矩阵表示的是每个样本点属于每个类的隶属度。根据这个划分矩阵按照模糊集合中的最大隶属原则就能够确定每个样本点归为哪个类，聚类中心表示的是每个类的平均特征，可以认为是这个类的代表点。
步骤1：用值在0，1间的随机数初始化隶属矩阵U，使其满足约束条件
步骤2：计算c个聚类中心ci，i=1,…,c。
步骤3：计算价值函数。如果它小于某个确定的阀值，或它相对上次价值函数值的改变量小于某个阀值，则算法停止。
步骤4：计算新的U矩阵。返回步骤2。

4.数学推导过程
此时要求的就是价值函数的最小值；进而变成求在隶属度函数的和为1的条件下，价值函数最小的条件极值问题。
价值函数J:$J = \sum\limits_{i = 1}^c {\sum\limits_{j = 1}^n {u_{ij}^m{d_{ij}}} }$J=i=1∑c​j=1∑n​uijm​dij​ 其中c表示分成了几簇，n表示n个样本，d表示样本到对应样本中心的距离，u表示隶属度函数。
条件极值的条件是:${u_i} = 1$ui​=1。
构造拉格朗日函数:$J = \sum\limits_{i = 1}^c {\sum\limits_{j = 1}^n {u_{ij}^m{d_{ij}}} } + \sum\limits_{j = 1}^n {{\lambda _j}(\sum\limits_{i = 1}^c {{u_{ij}} - 1} )}$J=i=1∑c​j=1∑n​uijm​dij​+j=1∑n​λj​(i=1∑c​uij​−1)
对变量u和c求导；
对c求导有：$\frac{{\partial J}}{{\partial {c_k}}} = \sum\limits_{i = 1}^c {\sum\limits_{j = 1}^n {\frac{{\partial u_{ij}^m{d_{ij}}}}{{\partial {c_k}}} - \frac{{\partial \sum\limits_{j = 1}^n {{\lambda _j}(\sum\limits_{i = 1}^c {{u_{ij}} - 1} )} }}{{\partial {c_k}}}} }$∂ck​∂J​=i=1∑c​j=1∑n​∂ck​∂uijm​dij​​−∂ck​∂j=1∑n​λj​(i=1∑c​uij​−1)​
其中$\frac{{\partial \sum\limits_{j = 1}^n {{\lambda _j}(\sum\limits_{i = 1}^c {{u_{ij}} - 1} )} }}{{\partial {c_k}}} = 0$∂ck​∂j=1∑n​λj​(i=1∑c​uij​−1)​=0

则有$\frac{{\partial J}}{{\partial {c_k}}} = \sum\limits_{i = 1}^c {\sum\limits_{j = 1}^n {\frac{{\partial u_{ij}^m{d_{ij}}}}{{\partial {c_k}}} = } } \sum\limits_{i = 1}^c {\sum\limits_{j = 1}^n {u_{ij}^m\frac{{\partial {d_{ij}}}}{{\partial {c_k}}} = } } u_{kj}^m\sum\limits_{j = 1}^n {\frac{{\partial {d_{ij}}}}{{\partial {c_k}}} = } 0$∂ck​∂J​=i=1∑c​j=1∑n​∂ck​∂uijm​dij​​=i=1∑c​j=1∑n​uijm​∂ck​∂dij​​=ukjm​j=1∑n​∂ck​∂dij​​=0
由于d是c和x的距离，且倒数最后为0，则非零的系数可以去掉。
最后变成关于c和x的等式，有$\sum\limits_{j = 1}^n {u_k^m{c_k}} - \sum\limits_{j = 1}^n {u_k^m{x_j}} = 0$j=1∑n​ukm​ck​−j=1∑n​ukm​xj​=0,
最终得到${c_k} = \frac{{\sum\limits_{j = 1}^n {u_{kj}^m{x_j}} }}{{\sum\limits_{j = 1}^n {u_{kj}^m} }}$ck​=j=1∑n​ukjm​j=1∑n​ukjm​xj​​。
对隶属函数u进行求导：$\frac{{\partial J}}{{\partial {u_{ij}}}} = \sum\limits_{j = 1}^n {\sum\limits_{i = 1}^c {mu_{ij}^{m - 1}{d_{ij}} + \sum\limits_{j = 1}^n {c{\lambda _j}} } } = \sum\limits_{j = 1}^n {(\sum\limits_{i = 1}^c {mu_{ij}^{m - 1}{d_{ij}}} + c{\lambda _j}) = 0}$∂uij​∂J​=j=1∑n​i=1∑c​muijm−1​dij​+j=1∑n​cλj​=j=1∑n​(i=1∑c​muijm−1​dij​+cλj​)=0
有$\sum\limits_{i = 1}^c {mu_{ij}^{m - 1}{d_{ij}}} + c{\lambda _j} = \sum\limits_{i = 1}^c {(mu_{ij}^{m - 1}{d_{ij}}} + {\lambda _j}) = 0$i=1∑c​muijm−1​dij​+cλj​=i=1∑c​(muijm−1​dij​+λj​)=0因为上式中括号函数大于等于零，
所以$mu_{ij}^{m - 1}{d_{ij}} + {\lambda _j} = 0$muijm−1​dij​+λj​=0
得${u_{ij}} = {(\frac{{ - {\lambda _j}}}{{m{d_{ij}}}})^{\frac{1}{{m - 1}}}}$uij​=(mdij​−λj​​)m−11​
由于$\sum\limits_{k = 1}^c {{u_{kj}} = 1}$k=1∑c​ukj​=1
可得$\sum\limits_{k = 1}^c {{{(\frac{{ - {\lambda _j}}}{{m{d_{kj}}}})}^{\frac{1}{{m - 1}}}}} = 1$k=1∑c​(mdkj​−λj​​)m−11​=1
进而有${(\frac{{ - {\lambda _i}}}{m})^{\frac{1}{{m - 1}}}} = \frac{1}{{\sum\limits_{k = 1}^c {{{(\frac{1}{{{d_{kj}}}})}^{\frac{1}{{m - 1}}}}} }}$(m−λi​​)m−11​=k=1∑c​(dkj​1​)m−11​1​
最终可得${u_{ij}} = \frac{1}{{\sum\limits_{k = 1}^c {{{(\frac{{{d_{ij}}}}{{{d_{kj}}}})}^{\frac{1}{{m - 1}}}}} }}$uij​=k=1∑c​(dkj​dij​​)m−11​1​.
参考文献：
（1）https://wenku.baidu.com/view/ee968c00eff9aef8941e06a2.html
（2）https://blog.****.net/shaoyu_hlq/article/details/56488204
（3）https://www.cnblogs.com/wxl845235800/p/11046248.html