机器学习：基础算法（十一）—— 聚类

无监督学习的目标是通过对无标记训练样本的学习来揭示数据的内在规律，应用最广的是聚类(clustering)。聚类的目标是将数据集划分为若干互不相交的子集，每个子集称为“簇”，每个簇对应于一些潜在的“类别”，这些类别事先未知，需要由使用者把握和命名。

聚类既能作为一个单独的过程，也可以作为其他学校任务的前驱过程。

聚类的性能度量

一般原则：簇内相似度尽可能高，簇间相似度尽可能低

聚类性能指标一般有两大类：

1、外部指标：将聚类结果与某个参考模型进行对比，如Rand指数(越大越好)：

$RI=\frac{a+d}{\binom{n}{2}}$

a:在聚类模型和参考模型中都属于同一簇的样本二元组数
b:在聚类模型和参考模型中都属于不同簇的样本二元组数
n:样本数

2、内部指标：直接考察聚类结果，不参考任何外部模型，如DB指数(越小越好)：

$DBI=\frac{1}{k}\sum_{i=1}^{k}\underset{i\neq j}{max}\frac{avg(C_i)+avg(C_j)}{d(\mu_i,\mu_j)}$

k：簇的个数
$avg(C_i)$：簇$C_i$中两两样本的平均距离
$d(\mu_i,\mu_j)$：簇$C_i$与$C_j$中心的距离

距离度量

对$(x_i,x_j)$的距离度量需满足以下基本性质：

非负性：$d(x_i,x_j)\geqslant 0$
同一性：$d(x_i,x_i)=0$
对称性：$d(x_i,x_j)=d(x_j,x_i)$
直递性：$d(x_i,x_j)\leqslant d(x_i,x_k)+d(x_k,x_j)$

对有序特征，通常采用闵可夫斯基距离：

$d_p(x_i,x_j)=(\sum_{k=1}^{d}\left | x_{ik} - x_{jk}\right |^p)^{\frac{1}{p}}$

p=1：曼哈顿距离，街道距离
p=2：欧氏距离，直线距离
$p=\infty $：切比雪夫距离，最大分量差

对无序特征，常采用CDM距离：衡量同一无序属性上两个属性值之间的距离，同一属性上的两个值，在相同簇中样本数比例差别越大，属性值之间的距离越大

$VDM_p(a,b)=\sum_{i=1}^{k}\left | \frac{m_{uai}}{m_{ua}} - \frac{m_{ubi}}{m_{ub}}\right |$

$m_{uai}$：第i个样本簇中属性u上取值为a的样本数
$m_{ua}$：属性u上取值为a的样本数

如果特征中混合了有序特征和无序特征，则可以混合闵可夫斯基距离和VDM距离，假设前k个属性为有序特征，后d-k个属性为无序特征，则：

$d_p(x_i,x_j)=(\sum_{u=1}^{k} \left | x_{iu}-x_{ju} \right |^p+\sum_{u=k+1}^{d} VDM_p(x_{iu},x_{ju}))^{\frac{1}{p}}$

原型聚类

所谓”原型“指的是聚类中心，将所有样本按照某组聚类中心进行划分，最常见的原型聚类是K-Means算法。

原型聚类问题描述：假设有一个数据集{$x1,x_2,…,x_N$}，我们的目标是将数据集划分为K类，并找到聚类类别和聚类中心。聚类类别可以用”1-of-K“表示法来表示，K维向量$z_i$中有且只有一个元素为1，其余元素为0，$z{ik}=1$表示第i个样本属于第k个类别；第k个类别的聚类中心可以用$\mu_k$表示

K-Means算法

为了极大化簇内相似度，极小化簇间相似度，K-Means算法的目标函数被定义为以下”失真度“：

$L(\theta)=\sum_{i=1}^{N}\sum_{k=1}^{K}z_{ik}\left \| x_i-\mu_k \right \|^2$

为找到目标函数的极小值，需考察数据集中所有可能的簇划分，这是一个NP难问题，K-means采用了 EM 算法来求解：

1、明确变量和参数：

（1）观测变量：$X=[x1,x_2,…,x_N]$
（2）隐变量：$Z=[z_ik]{n \times K}$
（3）参数：$\mu=[\mu_1,\mu_2,…,\mu_K]$

2、初始化参数：$\mu^0$，置j=0

3、EM迭代：迭代 E 步和 M 步直至前后两次聚类中心不变，$\mu^j$即为最终的近似最优解

（1）E步：样本分配，基于当前的聚类中心，关于类别隐变量分布，最小化目标函数，只需将样本分配到距其最近的聚类中心所在类别中即可

$z_{ik}=\left\{\begin{matrix} 1 & if\ k=arg\ \underset{j}{min}\left \| x_i-\mu_j \right \|^2\\ 0 & else \end{matrix}\right.$

（2）M步：更新聚类中心。基于当前类别隐变量分布，关于聚类中心参数，最小化目标函数，只需取当前类别内所有样本的均值作为新的聚类中心即可

目标函数对聚类中心偏导为0：

$2\sum_{i=1}^{N}z_{ik}(x_i-\mu_k)=0$

解出新的聚类中心：$n_k$为第k个簇中样本数

$\mu_k^{j+1}=\frac{\sum_{i=1}^{n_k}z_{ik}x_i}{n_k}$

K-Means 过程的可视化：

直接实现 K-Means 算法非常慢，因为在每个E步必须计算每个聚类中心和每个数据点的距离，常用的加速方法：

建立K-D树：详见kd-tree加速K-means
利用距离的三角不等式，避免不必要的计算：如果$2d(x,\mu_i)\leqslant d(\mu_i,\mu_j)$，则$d(x,\mu_i)\leqslant d(x,\mu_j)$，详见运用三角不等式加速Kmeans聚类算法

高斯混合聚类

高斯混合模型的EM算法和K-means算法有很强的相似性，K-means算法对样本数据点的聚类进行了”硬“分配，每个数据点只属于唯一的聚类，而EM算法基于后验概率分布，进行了一个”软“分配。事实上可以将K-means算法看做是高斯混合模型EM算法在方差趋于0的极限情况下的特例。

对于一个特定的数据点x，后验概率（分量贡献度）为：

$\gamma (z_k)=\frac{\pi_k e^{-\frac{\left \| x-\mu_k \right \|^2}{2\sigma }}}{\sum_{j=1}^{K}\pi_j e^{-\frac{\left \| x-\mu_j \right \|^2}{2\sigma }}}$

当$\sigma \rightarrow 0$时，$\left | x-\muj \right |^2$较大的项，$\gamma(z{j})$会趋于0，只有$\left | x-\muj \right |^2$最小的项$\gamma(z{j})$会趋近于1，在这种极限情况下，可以得到对数据点的一个硬分解。

从另外一个角度来看，当高斯混合分布已知时，高斯混合聚类会将样本集划分为k个簇，每个样本会被归入贡献度最高的分量：

$z_k=arg\ \underset{j \in {1,2,...,K}}{max}\gamma (z_{j})$

学习向量量化

学习向量量化(Learning Vector Quantization,LVQ)假设数据样本带有类别标记，学习过程利用这些监督信息来辅助聚类。

LVQ算法：

输入:样本集D={$(x_1,y_1),(x_2,y_2),…,(x_m,y_m)$}，原型向量个数K，各原型向量预设的类别标签{$c_1,c_2,…,c_K$}（可能含有重复），学习率$\eta $
输出：原型向量{$p_1,p_2,…,p_K$}

初始化一组原型向量{$p_1^0,p_2^0,…,p_K^0$}，置s=0
迭代以下过程，直至相邻两次原型向量更新很小或者到达最大迭代次数
1. 从样本中随机选取样本$(x_i,y_i)$
2. 找出与样本$x_i$距离最近的原型向量$p_j^s$，判断样本标签$y_i$与该原型向量的标签$c_j$是否相同
3. 如果相同，将原型向量$p_j^s$朝着样本$x_i$方向靠拢：$p_j^{s+1}=p_j^s+\eta(x_i-p_j^s)$
4. 否则，将原型向量$p_j^s$朝着远离$x_i$的方向移动：$p_j^{s+1}=p_j^s-\eta(x_i-p_j^s)$

层次聚类

层次聚类视图在不同层次上对数据进行划分，形成树形的聚类结构，数据集划分通常可采用”自底向上“的聚合策略，也可采用”自顶向下“的分拆策略。

”自底向上“的层次聚类算法：先将数据集中每个样本看做一个初始聚类簇，然后在每次迭代时将两个距离最近的聚类簇合并，直至达到预设的聚类簇个数。

衡量聚类簇间距离的指标:

最小距离：两个簇间元素间的最短距离
最大距离：两个簇间元素间最长距离
平均距离：两个簇间两两元素间的平均距离

参考

数据科学中必须熟知的5种聚类算法