【西瓜书】第九章聚类

本文是周志华老师《机器学习》第九章聚类的学习笔记。　　

近来做毕业设计，要在parameter server框架下实现各类机器学习算法，准备从聚类(k-means)做起。之前在法国和coursera学的也有些淡忘了，(coursera的聚类笔记也较为浅显)因此翻出西瓜书再来看看巩固一下。

聚类任务

首先明确一下什么是聚类任务，它是无监督学习的一种（常见其他无监督学习还有密度估计和异常检测），也是应用范围最广的一类学习任务。

聚类任务试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个簇(cluster)，需要说明的是，簇所对应的概念语义对聚类算法而言是未知的。
形式化地说，样本集 $D={x_1,x_2,…,x_m}$ 包含m个无标记样本，每个样本$x_i=(x_i1,x_i2,…,x_in)$是一个n维特征向量，则聚类算法将样本集D划分为k个不相交的簇${C_l | l=1,2,…,k}$

性能度量

明确了任务之后，当然我们也需要一个指标来度量咱们的任务干的如何，但是和监督学习不同，这里的性能不太能直观地看出来。
我们凭直觉来看，我们肯定希望同一簇的样本彼此尽可能相似，而不同簇的样本尽量不同，也就是簇内相似度高而簇间相似度低。
聚类任务的性能度量一般分为两类：

将聚类结果和某个参考模型比较（例如某领域专家的划分），又称外部指标
不考虑参考模型的内部指标

首先来讲第一类度量指标，我们令：

$a=|SS|,b=|SD|,c=|DS|,d=|DD|$

这里的S指same，D指different，我们对样本集中的样本两两考虑(设为$i,j$)，如果i和j在聚类划分和参考模型中都属于同一簇，那么样本对$(i,j)$就属于$SS$集合；如果它们在聚类划分中属于同一簇，而在参考模型中属于不同簇，那么该样本对就属于$SD$集合；$DS,DD$集合也同理，同时对于m个样本$a+b+c+d=m(m-1)/2$那么我们就能得到以下外部指标：

Jaccard系数 $JC=\frac{a}{a+b+c}$
FMI $FMI=\sqrt{\frac{a}{a+b} \times \frac{a}{a+c}}$
Rand指数 $RI=\frac{2(a+d)}{m(m-1)}$
显然，这里指标都是越大越好。

然后就是第二类指标了，这里主要有DB指数。

$DB=\frac{1}{k}\sum^k_{i=1}max(\frac{avg(C_i)+avg(C_j)}{d_{cen}(\mu_i,\mu_j)})$

这里$avg(C)$ 表示簇C内样本间的平均距离，$\mui$ 表示样本i对应簇的中心点，$d{cen}(C_i,C_j)$ 对应于簇$C_i$ 和簇$C_j$ 中心点之间的距离。

距离计算

针对不同的问题，距离计算也有诸多算法。但是任意距离度量都需要满足：

非负性$dist(x_i,x_j) >= 0$
同一性$dist(x_i,x_j)=0$ 当且仅当$i=j$
对称性$dist(x_i,x_j)=dist(x_j,x_i)$
直递性$dist(x_i,x_j)\le dist(x_i,x_k)+dist(x_k,x_j)$

最常用的距离应该是闵可夫斯基距离：

$dist_{mk}(x_i,x_j)=(\sum_{u=1}^n|x_{iu}-x_{ju}|^p)^{\frac{1}{p}}$

当 $p=2$，该距离就是我们熟悉的欧式距离，而$p=1$ 时，则为曼哈顿距离。
注意，这里闵可夫斯基距离既可以用于连续距离，也可以用于离散距离，但是用于离散距离的前提是它是有序距离 ,举例来说我们有1，2，3这几个离散值，1和2距离近，相比之下1和3距离就远；但是无序距离 例如飞机，大炮，坦克这类就无法用闵氏距离刻画，这时我们采用VDM来处理(详细见书p200)。
西瓜书中没有提及的一种重要的距离叫做余弦距离，

$dist_{cos}(x_i,x_j)=\frac{\sum_{k=1}^nx_{ik}x_{ik}}{\sqrt{\sum_{k=1}^nx_{ik}^2}\sqrt{\sum_{k=1}^nx_{jk}^2}}$

欧氏距离（以及其他闵可夫斯基距离）更多的衡量个体间的绝对差异，更加适用于比如各类金融指标，用户行为数据等等，而余弦距离大家可以发现更多衡量方向/维度上的差异，从几何上来看，它衡量了几何相似性，且对坐标系的旋转/放大/缩小的变换保持不变，在处理用户兴趣数据，文章相似度等方面可能表现更好。
此外常用的还有马氏距离，定义为$D^2=(x-\mu)^T\Sigma^{-1}(x-\mu)$ ,它能够排除样本之间的相关性，但是协方差矩阵在实际应用中难以计算。

最后再多提一句，我们之前提到距离度量需要满足一定的性质（非负同一对称直递），但是有时候我们用于相似度度量的距离不一定要满足这些性质（比如上面的余弦距离就不满足直递性以及为了让K-means算法更好解决非凸簇形结构的Bregrman距离不满足对称性和直递性），西瓜书中有个有趣的例子，人与半人马，马和半人马都是相似的，但是人和马显然不太相似，这就不太符合直递性了。
实际聚类时需要根据数据样本来选择适当的距离（以及加权等调整）。

聚类算法

因为不存在一个绝对客观的标准，因此聚类算法非常多，主要可以分为原型聚类，密度聚类和层次聚类，这里主要记一下应用最为广泛的原型聚类里的K-means算法。

Kmeans

K-means算法针对给定样本集，对划分的簇最小化平方误差：

$E=\sum_{i=1}^k\sum_{x\in C_i}||x-\mu_i||_2^2$

这里$\mu_i$ 是簇$C_i$ 的均值向量，可以看出E越小，簇内样本相似度越高。
这里如何最小化E呢，k-means使用了贪心的策略迭代优化来求近似解。具体的算法如下图：
k-means k-means
这里看出算法分为两部分，一部分是算每个点和每个簇中心的距离，并将点加入到最近的那个簇中，第二部分是计算每个簇的新中心 ，算法的边界条件可以是所有样本的分类都不再改变，但是实际应用中常常是设置一个最大迭代次数或者最小误差作为停止的阈值。

Kmeans比较适合簇数已知的情况，且初始化簇中心会对算法结果造成很大影响，可以启发式地搜索k的取值，寻求拐点，但并不总是有效的。有很多种方法尝试更好的完成初始化，除了随机选择之外，还有按照经验选，按照密度选（计算每个样本一定空间内的样本数作为密度，选密度最大的作为第一个初始簇中心，离他一定距离之外选择此外最大密度作为第二个，以此类推）。

除了这种确定的Kmeans，还有一种模糊Kmeans算法。(这部分内容来自《Pattern Classification》)传统的Kmeans，元素的归属都是属于确定集合（脆集合）即元素只有属于或者不属于某集合；模糊Kmeans使用的是模糊集合，即元素以一定概率属于某集合。这更符合NLP和常识性的知识。
我们设样本集为${x_i}$，聚类中心$m_j$, 第$i$个样本对第$j$ 的隶属度函数为$\mu_{j}(x_i)$.
那么我们定义损失函数：

$J_f=\sum_{j=1}^c\sum_{i=1}^n[\mu_j(x_i)]^b\|x_i-m_j\|^2$

那么不同的隶属度定义，就能得到不同的模糊聚类方法，但是总体来说还是和Kmeans算法一样符合EM算法的框架,初始化后交替更新$m,\mu$ 。

$m_j=\frac{\sum_{j=1}^n[\mu_j(x_i)]^bx_i}{\sum_{i=1}^n[\mu_j(x_i)]^b}$ $\mu_j(x_i)=\frac{(1/\|x_i-m_j\|^2)^{1/(b-1)}}{\sum_{p=1}^k(1/\|x_i-m_p\|^2)^{1/(b-1)}}$

参数服务器版本Kmeans

在参数服务器框架上实现kmeans的改造也很简单，服务器端只需要存储所有簇中心的坐标，而工作节点上存储各自样本的向量及其聚类标号。每轮迭代时，工作节点先拉取最新的簇中心坐标，然后对每个样本计算其各自的聚类，然后在工作节点上各自计算各个簇的暂存中心，接着推送各个簇的簇标号，暂存中心以及簇中样本个数，服务器端接收到这些数据后，计算每个簇真正的中心。