聚类算法总结(1)

来公司实习已经一个多月了，做的事情主要根据聚类相关，趁着有空，来一发总结。

整体框图

主要总结下各类算法的思想，以及优缺点，不要太在意细节。

聚类就是对大量未标注的数据集，按数据的内在相似性将数据集划分为多个类别，使得类别内的数据相似性尽可能大，而各类别间的数据相似性尽可能小。

基于划分

K-means

基本思想： K-means算法首先随机地选择个对象，每个对象初始地代表一个簇的平均值或中心。对剩余的每个对象根据其与各个簇中心的距离（之前的各种距离的定义，在这里派上了用场，可以根据实际需求来选择不同的距离定义），将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数函数收敛（准则函数常常使用最小均方误差）。

假定输入样本为 $S = x_1,x_2,\cdots,x_m$

选定初始的k个类别中心，$\mu_1,\mu_2,\cdots,\mu_k$
对于每个样本，将其标记为距离类别中心最近的类别:

$\text{label}_i = \underset{1 \le j \le k}{\arg \min}||x_i-\mu_j||$

将每个类别中心更新为隶属于该类别的所有样本的均值

$\mu_j = \frac{1}{|c_j|}\sum_{i \in C_j} x_i$

重复最后两步，直到类别中心的变化小于某阈值

K-means 和 EM

K-means也被称为hard EM（GMM为soft EM），整体思想与EM是相通的。

下面我们来解释一下，它俩是如何联系到一起的。

我们一开始不知道每个样例$x^{(i)}$对应隐含变量也就是最佳类别$c^{(i)}$。最开始可以随便指定一个$c^{(i)}$给它，然后为了让$P(x,y)$最大（这里是要让$J$最小），我们求出在给定$c$情况下，$J$最小时的$\mu$（前面提到的其他未知参数），然而此时发现，可以有更好的$c^{(i)}$（质心与样例$x^{(i)}$距离最小的类别）指定给样例$x^{(i)}$，那么$c^{(i)}$得到重新调整，上述过程就开始重复了，直到没有更好的$c^{(i)}$指定。这样从K-means里我们可以看出它其实就是EM的体现，E步是确定隐含类别变量$c^{(i)}$，M步更新其他参数$\mu$来使$J$最小化¹。

还记得我们前面一直强调的通俗版EM解说吗？

简版：猜（E-step）,反思（M-step）,重复；
啰嗦版：你知道一些东西（观察的到的数据），你不知道一些东西（隐藏变量），你很好奇，想知道点那些不了解的东西。怎么办呢？
你根据一些假设（parameter）先猜（E-step），把那些不知道的东西都猜出来，假装你全都知道了;
然后有了这些猜出来的数据，你反思一下，更新一下你的假设（parameter）,
让你观察到的数据更加可能(Maximize likelihood; M-step);
然后再猜，再反思，最后，你就得到了一个可以解释整个数据的假设了。

K-means优缺点

优点

简单，易于实现
当结果簇是密集的，效果较好

缺点

k值选择
对初值敏感，对于不同的初始值，可能会导致不同结果(K-means++)
不适合于发现非凸形状的簇或者大小差别很大的簇
对躁声和孤立点数据敏感（异常点检测）

谱聚类

指导思想：谱聚类(Spectral Clustering)是一种基于图论的聚类方法，将带权无向图划分为两个或两个以上的最优子图，使子图内部尽量相似，而子图间距离尽量距离较远。

首先我们需要根据数据建立Graph，Graph的每一个节点对应一个数据点，边的权重用于表示数据之间的相似度（高斯距离），我们通常采用mutual K-nearest-neighbor graph（也就是说只有我是你的n近邻，你也必须是我的n近邻的点才算）。

剩下就变为求解下面优化问题：

$\min cut(A_1,\cdots,A_k) = \frac{1}{2}\sum_{i=1}^{k} W(A_i,\bar{A}_i)$

上面的式子表示的是进行分割时去掉的边的权值总和，但是这样做往往不能得到最佳划分，它只是一味的考虑被切掉边的权重，没有考虑到划分之后各类别本身的特性，容易得到一些孤立点团簇。

为了能够让每个类都有合理的大小，又提出了RadioCut和NCut:

$\begin{align*} RadioCut(A_1,\cdots,A_k) & = \frac{1}{2}\sum_{i=1}^{k}\frac{W(A_i,\bar{A}_i)}{\|A_i\|} \\ NCut(A_1,\cdots,A_k) & = \frac{1}{2}\sum_{i=1}^{k}\frac{W(A_i,\bar{A}_i)}{vol(A_i)} \end{align*}$

其中，$|A_i|$表示$A_i$中包含的顶点数目，$vol(A)=\sum_{i \in A}W_{ij}$，这两个指标都是对团簇大小的一种衡量。

然后呢，要解决这种NP-hard的优化问题，就得提到拉普拉斯矩阵，这里有机会我们在回来解说。

用拉普拉斯矩阵一些性质转换之后，整个聚类过程可以总结为：

K-means聚类算法 ↩