模糊C均值（FCM）算法更新公式推导

模糊C均值（FCM）算法更新公式推导

目标函数

FCM的目标函数为：

$$J_m=\sum _{i=1}^n\sum _{j=1}^k{u}_{ij}^m\Vert x_i-c_j{\Vert }^2$$

其中：

• $x_i$ 是数据点，$i=1,2,\dots ,n$。
• $c_j$ 是第 $j$ 个簇的中心，$j=1,2,\dots ,k$。
• $u_{ij}$ 是数据点 $x_i$ 属于第 $j$ 个簇的隶属度。
• $m$ 是模糊度参数，通常 $m>1$。

更新公式推导过程

1. 定义目标函数

$$J_m=\sum _{i=1}^n\sum _{j=1}^k{u}_{ij}^m\Vert x_i-c_j{\Vert }^2$$

2. 引入约束条件

$$\sum _{j=1}^k{u}_{ij}=1\forall i$$

使用拉格朗日乘数法，引入拉格朗日乘子 ${\lambda }_i$，构造拉格朗日函数：

$$\mathcal{L}=\sum _{i=1}^n\sum _{j=1}^k{u}_{ij}^m\Vert x_i-c_j{\Vert }^2+\sum _{i=1}^n{\lambda }_i\left(\sum _{j=1}^k{u}_{ij}-1\right)$$

3. 对 $u_{ij}$ 求偏导数并设为零

对拉格朗日函数 $\mathcal{L}$ 求 $u_{ij}$ 的偏导数并设为零：

$$\frac{\partial \mathcal{L}}{\partial u_{ij}}=m{u}_{ij}^{m-1}\Vert x_i-c_j{\Vert }^2+{\lambda }_i=0$$

解这个方程得到：

$$u_{ij}^{m-1}=-\frac{{\lambda }_i}{m\Vert x_i-c_j{\Vert }^2}$$

为了保证 (u_{ij}) 非负，设 ${\lambda }_i=-m\zeta$，则：

$$u_{ij}^{m-1}=\frac{\zeta }{\Vert x_i-c_j{\Vert }^2}$$
即：

$$u_{ij}={\left(\frac{\zeta }{\Vert x_i-c_j{\Vert }^2}\right)}^{\frac{1}{m-1}}$$

4. 求解拉格朗日乘子 $\zeta$

利用约束条件 ${\sum }_{j=1}^k{u}_{ij}=1$：

$$\sum _{j=1}^k{\left(\frac{\zeta }{\Vert x_i-c_j{\Vert }^2}\right)}^{\frac{1}{m-1}}=1$$

解这个方程得到：

$$\zeta ={\left(\sum _{j=1}^k{\left(\frac{1}{\Vert x_i-c_j{\Vert }^2}\right)}^{\frac{1}{m-1}}\right)}^{1-m}$$

代入 $u_{ij}$ 的表达式，得到隶属度更新公式：

$$u_{ij}=\frac{1}{{\sum }_{l=1}^k{\left(\frac{\Vert x_i-c_j\Vert }{\Vert x_i-c_l\Vert }\right)}^{\frac{2}{m-1}}}$$

5. 对簇中心 $c_j$ 求偏导数并设为零

对目标函数 $J_m$ 对 $c_j$ 求偏导数并设为零：

$$\frac{\partial J_m}{\partial c_j}=\sum _{i=1}^n{u}_{ij}^m(c_j-x_i)=0$$

解这个方程得到：

$$\sum _{i=1}^n{u}_{ij}^m{c}_j=\sum _{i=1}^n{u}_{ij}^m{x}_i$$

$$c_j=\frac{{\sum }_{i=1}^n{u}_{ij}^m{x}_i}{{\sum }_{i=1}^n{u}_{ij}^m}$$

总结

通过上述推导过程，我们得到了FCM算法的更新公式：

• 隶属度更新公式：

$$u_{ij}=\frac{1}{{\sum }_{l=1}^k{\left(\frac{\Vert x_i-c_j\Vert }{\Vert x_i-c_l\Vert }\right)}^{\frac{2}{m-1}}}$$

• 簇中心更新公式：

$$c_j=\frac{{\sum }_{i=1}^n{u}_{ij}^m{x}_i}{{\sum }_{i=1}^n{u}_{ij}^m}$$

这些公式在每次迭代中交替更新，直到目标函数收敛。