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

整体框图

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


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

基于划分

K-means

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


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

  • 选定初始的k个类别中心,$\mu_1,\mu_2,\cdots,\mu_k$
  • 对于每个样本,将其标记为距离类别中心最近的类别:
  • 将每个类别中心更新为隶属于该类别的所有样本的均值
  • 重复最后两步,直到类别中心的变化小于某阈值


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$最小化1

还记得我们前面一直强调的通俗版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近邻的点才算)。


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

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

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

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


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

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