聚类

## k-means

1. 选择初始化的 K 个样本作为初始聚类中心 $c = c_1, c_2,...,c_k$；
2. 针对数据集中每个样本 $x_i$ 计算它到 k 个聚类中心的距离并将其分到距离最小的聚类中心所对应的类中；
3. 针对每个类别 $c_j$，重新计算它的聚类中心（即属于该类的所有样本的质心）；
4. 重复上面 2 3 两步操作，直到达到某个中止条件（迭代次数、最小误差变化等）。

目标函数为：

$$
J(C) = \sum_k^K\sum_i d_{ik}^2
$$

常用的有使 $J(C)$ 最小，其中 $d_{ik}$ 表示第 $i$ 个样本点到第 $k$ 类中心的距离。

## 模糊C均值算法(FCM)

在 k-means 的基础上，用一个隶属程度矩阵 $U = [u_{ik}]$ 来表示每个样本点属于每个类的程度大小，其目标函数：

$$
J(U,C) = \sum_k^K\sum_i u_{ik}^m * d_{ik}^2
$$

其中 $m>1$ 是加权指数，约束条件：$\sum_k^K u_{ik} = 1$，即每个样本点的对不同类的隶属程度加起来等于 1。最优化问题可以用拉格朗日法求解：

$$
u_{ik} = \frac{1}{\sum_j^K(\frac{d_{ik}}{d_{ij}})^{-\frac{2}{m-1}}} \\
C_k = \sum_i\frac{u_{ik}^m}{\sum_i u_{ik}^m}x_i
$$

需要初始化 $U,C$进行迭代。

## 可能性C均值聚类(PCM)

PCM 是 FCM 的一种改进，一个样本点可能同时属于多个类别，约束条件改为：

$$
0<\sum_i^N u_{ik} < N
$$

构造新的目标函数：

$$
J(U,C) = \sum_k^K\sum_i u_{ik}^m * d_{ik}^2 + \sum_k^K\eta_k\sum_i^N(1-u_{ik})^m
$$

这里的 $\eta$ 一般使用 FCM 算法计算得出的 $(U,C)$ 直接计算作为定值，也可以指定一个常数。此时：

$$
u_{ik} = \frac{1}{1+(\frac{d_{ik}^2}{\eta_k})^{\frac{1}{m-1}}} \\
C_k = \frac{\sum_i^N u_{ik}^m x_i}{\sum_i^N u_{ik}^m}
$$

如果使用 $(U,C)$ 计算 $\eta_k$，则：

$$
\eta_k = M\frac{\sum_i^N u_{ik}^m d_{ik}^2}{\sum_i^N u_{ik}^m}
$$

通过不断迭代 $(U,C)$，直到目标函数达到一个稳定状态。

## 可能性模糊C均值聚类(PFCM)

增加了一个特征矩阵 $T$，目标函数：

$$
J(T,U,C) = \sum_k^K\sum_i (a t_{ik}^h+b u_{ik}^m) * d_{ik}^2 + \sum_k^K\eta_k\sum_i^N(1-u_{ik})^m
$$

约束条件：$\sum_k^K t_{ik} = 1$：

$$
t_{ik} = \frac{1}{\sum_j^K(\frac{d_{ik}}{d_{ij}})^{\frac{2}{m-1}}} \\ 
u_{ik} = \frac{1}{1+(b \frac{d_{ik}^2}{\eta_k})^{\frac{1}{m-1}}} \\
C_k = \frac{\sum_i^N (a t_{ik}^h+b u_{ik}^m) x_i}{\sum_i^N (a t_{ik}^h+b u_{ik}^m)}
$$

## 均值漂移

简单来说就是让中心点向更加密集的方向前进：

![](https://blog.qiniu.ctaoist.cn/机器学习/mean_shift_1.png)

1. 随便挑一个**没有访问过的点作为起始点**(初始时所有点都没有被访问)
2. 使用mean-shift思想进行移动, 直到收敛, 把途经的圆圈内的所有点都标记为**已访问**
3. 如果收敛的点与已有的某个中心点过近, 则合并为一个中心点, 反之作为一个独立的中心点
4. 重复1, 2, 3直到所有点都被访问过
5. 得到所有的中心点

## 参考

https://zhuanlan.zhihu.com/p/467766855

https://blog.csdn.net/u014423305/article/details/83006063

- [Fuzzy c-means(FCM)模糊聚类详解及matlab实现](https://www.cnblogs.com/xiaohuahua108/p/6187178.html)
- [Mean Shift算法](https://daolinzhou.github.io/Blog/2020/05/21/mean-shift/)

聚类

最近更新

热门标签

文章目录