2020年03月14日阅读 7

经典机器学习系列之【聚类分析】

在《战国策·齐策三》中有这么一句话：“物以类聚，人以群分”，用于比喻同类的东西常聚在一起，志同道合的人相聚成群，反之就分开。而所谓的科学，不过是把我们日常的生活经验，大自然的规律用数学的语言描述出来罢了。在机器学习中也有这么一类算法，聚类算法，借鉴的就是“物以类聚，人以群分”的思想。

想想人在生活中是如何做到“聚类”的。我们通常会跟自己很像的人在一起玩，比如同龄人、有共同爱好的人，相同的社会观、价值观等等。但往往自己并不知道自己是属于哪一类，也就是说你是没有标签的，而当别人告诉你，或者暗示你，你可能就知道，哦自己属于这一类。在这个聚类问题中有一个很关键的因素就是如何评价其他人与你像与不像。

那在机器学习中聚类算法又是如何做到这样一件事情的呢？之前我们有说分类问题，他的样本空间由 $(X,Y)$ 构成， $X$ 称之为特征， $Y$ 为标签，其为离散值，如果是连续值，则为回归问题。

当我们所能拿到的数据只有 $X$ ,而没有 $Y$ 的时候，对数据的划分问题我们称之为聚类问题，本质是在揭示数据的内在性质及规律。聚类分析的目标是：使得簇内数据之间具有高的相似性；不同簇数据之间具有高的差异性。簇指的是聚类分析划分的类别。这里一个很重要的问题就是如何来度量数据间的相似性？

相似性度量的方法有很多，之前文章有总结12种常见的数据相似性的度量标准：经典机器学习系列之【相似性度量】。

基于不同的学习策略，聚类方法的分类一般可以分为以下几类：

划分方法
层次方法
基于密度方法
基于网格方法
基于模型方法

我们依次来对其进行讨论：

划分方法

在划分方法中，对于给定 $n$ 个对象数据集 $D$ ，以及簇的数目 $k$ (也就是划分的类别数)，划分算法将对象组织为 $k$ 个划分( $k \leq n$ )。划分的基本原则是在簇内的相似度高(intra-cluster similarity)，簇间相似度低(inter-cluster similarity)。经典的方法有：K-means及其变种、K-中心点、CLARA、CLARANS等。

K-means

k-means算法，也被称为k-平均或k-均值，是一种广泛使用的聚类算法，或者成为其它聚类算法的基础，算法的步骤描述如下所示：

假定输入样本为 $S=X_{1}，X_{2}，\cdots X_{m}$ ，则算法步骤为：

选择初始的 $k$ 个类别中心 $\mu_{1}$ ， $\mu_{2}$ ， $\cdots$ ， $\mu_{k}$
对于每个样本 $X_{i}$ ，将其标记为距离类别中心最近的类别，即：

\text{label}_{i} =\text{argmin}_{1 \leq j \leq k}||X_{i}-\mu_{i}||

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

\mu_{j}=\frac{1}{|c_{j}|}\sum_{i \in c_{j}}x_{i}

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

k-means公式化理解

记 $K$ 个簇中心为 $\mu_{1}$ ， $\mu_{2}$ ， $\cdots$ ， $\mu_{k}$ ，每个簇的样本数目为 $N_{1}$ ， $N_{2}$ ， $\cdots$ ， $N_{k}$ 。使用平方误差作为目标函数：

J(\mu_{1},\mu_{2} \cdots,\mu_{k})=\frac{1}{2}\sum_{j=1}^{K}\sum_{i=1}^{N_{j}}(x_{i}-\mu_{j})^{2}

按照凸优化的思想想取其最小值，求其关于 $\mu_{1},\mu_{2},\cdots,\mu_{k}$ 的偏导，并令其等于0。有：

\frac{\partial J}{\partial \mu_{j}}=-\sum_{i=1}^{N_{j}}(x_{i}-\mu_{j})=0

可以推出：

\mu_{j}=\frac{1}{N_{j}}\sum_{i=1}^{N_{j}}x_{i}

如果度量标准取的不是欧式距离，比如余弦距离，那对其均方误差求偏导数是又可能会导致其结果发生振荡的。

K-Means变种

K-Mediods聚类(K中值距离)

K-Means将簇中所有点的均值作为新质心，若簇中含有异常点，将导致均值偏离严重。以一维数据为例：

举个例子：数组【1，2，3，4，100】的均值为22，显然距离“大多数”数据【1，2，3，4】比较远，如果改成数组中位数3，在该实例中更为稳妥。这种聚类方式即 $\text{k-Mediods}$ 聚类(K中值距离)。

K-Means算法对于初值的选择是会比较敏感的，想想一下极端情况，如果刚好卡在数各个数据簇中心的某个死角，完事划分完了，但不是正确的划分(相当于找到了数据的漏洞)，因此在实际过程中我们往往选择比较远的点作为初值。

那实际操作过程中是如何来找到这些比较远的样本点呢？一般的做法如下：随机选择一个样本 $X_{1}$ ，然后计算其他样本与它的距离，然后选择与他距离最远的距离(或则与距离成正比的一个概率)作为下一个初始点样本 $X_{2}$ ，依据需要划分成几类簇而依次进行下去，这个效果往往会比随机选择的初始点要好一点点，在sklearn里面，这个选初值的方法就是k-mean++，并且sklearn里面默认会计算10次，取结果较好的那一次返回。

k-means算法会对数据是混合高斯分布的这样一种数据有比较好的效果。将数据旋转之后效果往往不好，对于方差不相等的数据效果也不会很好

二分k-means

为了改进K-means算法，我们还有别的思路，比如二分k-means。

如果k-means聚类完成之后，发现某两类的均值很接近，方差又很小，那么这两类其实是可以归为同一簇，如果划分类别数不变的话，其它的簇就得拆开来一簇(方差大的那一簇)。可以看作是用初始的k-means做基本的划分之后，再来优化这个聚类的过程。

Mini-batch k-Means算法

如果我们不是对所有样本求均值，而是对其中一个batch样本点求均值的话，能够使得k-means算法加速(少算了很多样本点)。

k-means算法优缺点对比

优点：

是解决聚类问题的一种经典算法，简单、快速。它的时间复杂度为 $O(t\cdot n\cdot k)$ ，其中 $t$ 为迭代次数， $n$ 为样本数， $k$ 为所需划分簇的数目。
对处理大数据集，该算法保持可伸缩性和高效性。
当簇近似为高斯分布时，它的效果较好。

缺点：

在簇的平均值可被定义的情况下才能使用，可能不适用于某些应用。
必须实现给出k(要生成的簇的数目)，而且对初值敏感，对于不同的初始值，可能会导致不同结果。
不适用于发现非凸形状的簇或者大小差别很大的簇。
因为求取的是均值，所以其对噪声和孤立点数据敏感。其可作为其它算法的基础，如谱聚类。

层次方法

层次聚类也是一种从生活中能够直观理解的一种聚类思想，比如说人，可以分为美国人、中国人，再划分一下中国人，又可以分为北京人、上海人，这就很明显的具有层次性的感觉。

层次聚类方法大体思想是：对给定数据集进行层次的分解，直到某种条件满足为止。会将数据对象建立一颗聚类树。依据建树的方法可以分为两类：

自底向上的策略，把小的类别逐渐合并为大的类别，这种方法称为凝聚。具体做法：首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。典型的算法有AGNES算法。
自顶向下的策略，把大的类别逐渐分裂为小的类别，这种方法称为分裂。具体做法：采用自顶向下的策略，首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。典型算法有DIANA算法。

在AGNES算法方法中，我们需要去衡量簇间距离的度量方法，看看这两个簇是否能合并。定义簇间距离度量的方法主要有以下四种：

最小距离：两个集合中最近两个样本的距离(最近邻聚类算法)。这种方法在簇跟簇之间合并的时候容易形成链状结构。

$d_{min}(C_{i},C_{j})=min_{p\in C_{i},p^{'}\in C_{j}}|p-p^{'}|$

最大距离：两个集合中最远的两个样本的距离。这种方法在存在异常值的时候就不是很稳定。

$d_{max}(C_{i},C_{j})=max_{p\in C_{i},p^{'}\in C_{j}}|p-p^{'}|$

平均距离：两个集合样本间两两距离的平均值。

$d_{avg}(C_{i},C_{j})=\frac{1}{n_{i}n_{j}}\sum_{p\in C,p^{'}\in C_{j}}|p-p^{'}|$

$n_{i}$ 是簇 $C_{i}$ 中对象个数， $n_{j}$ 是簇 $C_{j}$ 中对象个数。

均值距离：

$d_{mean}(C_{i},C_{j})=|m_{i}-m_{j}|$

$m_{i}$ 是簇 $C_{i}$ 的均值。

方差：使得簇内距离平方和最小，簇间平方和最大。

在层次聚类算法的实际应用中，聚类通常终止于某个预先设定的条件，比如簇的数目达到某个预定的值，或者每个簇的直径都在某个阈值之内。

除此之外呢，还有一些方法，比如BRICH方法、ROCK方法和Chameleon方法。

基于密度方法

密度聚类方法的指导思想是：只要样本点的密度大于某阈值，则将该样本添加到最近的簇中。

这类算法能克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类，且对噪声数据不敏感。但计算密度单元的计算复杂度大，需要建立空间索引来降低计算量。

基于密度的方法将簇看作数据空间中被低密度区域分割开的稠密的对象区域，有时也将这种低密度区域看作噪声。

经典的方法有：DBSCAN、OPTICS、DENCLUE等。

DBSCAN算法

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法。与上文说的划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有“噪声”的数据中发现任意形状的聚类。

在开始描述这个算法之前，我们需要定义一些名词概念：

$\epsilon$ 领域：给定对象半径 $\epsilon$ 内的领域称为该对象的 $\epsilon$ 领域。

核心对象：如果对象的 $\epsilon$ 领域至少包含最小数目 $Minpts$ 的对象，则称该对象为核心对象。

直接密度可达(密度直达)：给定一个对象集合 $D$ ，如果 $p$ 在 $q$ 的 $\epsilon$ 领域内，而 $q$ 是一个核心对象，则称对象 $p$ 从对象 $q$ 出发是直接密度可达的。换句话说，如果知道了对象 $p$ 从对象 $q$ 出发是直接密度可达的，那么 $q$ 就是一个核心对象，至于 $p$ 是不是核心对象就不清楚了。

密度可达：如果存在一个对象链 $p_{1}$ , $p_{2}$ , $\cdots$ , $p_{n}$ ,对 $p_{i}\in D$ ,( $1 \leq i \leq n$ ), $p_{i+1}$ 是从 $p_{i}$ 关于 $\epsilon$ 和 $MinPts$ 直接密度可达的，则对象 $p$ 是从对象 $q$ 关于 $\epsilon$ 和 $Minpts$ 密度可达的。密度可达是直接密度可达的传递闭包，它是非对称的，只有核心对象之间互相密度可达(反过来的话，那个点可能不是核心对象)。

密度相连：如果对象集合 $D$ 中存在一个对象 $o$ ，使得对象 $p$ 和 $q$ 是从 $o$ 关于 $\epsilon$ 和 $Minpts$ 密度可达的，那么对象 $p$ 和 $q$ 是关于 $\epsilon$ 和 $Minpts$ 密度相连的。密度相连则是一种对称的关系。

从下图可以很容易看出理解上述定义，图中 $Minpts=5$ ，红色的点都是核心对象，因为其 $\epsilon$ 领域至少有5个样本。黑色的样本是非核心对象。所有核心对象密度直达的样本在以红色核心对象为中心的超球体内，如果不在超球体内，则不能密度直达。图中用绿色箭头连起来的核心对象组成了密度可达的样本序列。在这些密度可达的样本序列的 $\epsilon$ 领域内所有的样本互相都是密度相连的。

簇：一个基于密度的簇是最大的密度相连对象的集合(密度相连的点样本所形成的集合)。不包含在任何簇中的对象被认为是噪声。

算法流程：

检查数据集中的每个点的 $\epsilon$ 领域。

如果点的 $\epsilon$ 领域包含的点多于 $Minpt$ 个，则创建一个以这个点为核心对象的新簇；迭代聚集从这些核心对象直接密度可达的对象。

当没有新的点可以添加到任何簇时，聚类过程结束。

算法评价：

计算复杂度为 $O(n^{2})$ ，在使用空间索引的数据库中计算复杂度可降为 $O(nlogn)$ 。在参数 $\epsilon$ 和 $Minpts$ 设置恰当的情况下，DBSCAN算法可有效地找到任意形状的簇；

但是这个算法对参数非常敏感；

真实的高维数据具有非常倾斜的分布，全局密度参数不能刻画其内在的聚类结构。

基于网格方法

它采用一个多分辨率的网格数据结构，将空间量化为有限数目的单元，这些单元形成了网络结构，所有的聚类操作都在网格上进行。

特点：直接聚类的对象是空间，而不是数据对象。

优点：处理速度快

经典方法：STING和WaveCluster等。

基于模型方法

试图优化给定的数据和某些数学模型之间的拟合，即假设数据是根据潜在的概率分布生成的；

基于模型的方法试图找到其背后的模型，并使用其概率分布特征进行聚类。

经典方法：期望最大化方法、概念聚类、基于神经网络等。

评价聚类算法好坏标准

当我们设计了一个聚类算法，聚类算法好坏的评价指标是什么呢？这个问题称之为聚类性能度量，亦称聚类“有效性指标”(validity index)。若明确了最终将要使用的性能度量，则可直接将其作为聚类过程的优化目标，从而更好地得到符合要求的聚类结果。

聚类性能度量大致有两类。一类是将聚类结果与某个“参考模型”进行比较，称为“外部指标 ”(external index)；另一类是直接考察聚类结果而不利用任何参考模型，称为“内部指标”(internal index)。

外部指标

将样本两两配对，然后确定4个值：

a为在参考模型中属于同一个类且在聚类结果中属于同一个簇的样本对的数量。
b为在参考模型中不在同一个类且在聚类结果中属于同一个簇的样本对的数量。
c为在参考模型中属于同一个类且在聚类结果中不在同一个簇的样本对的数量。
d为在参考模型中不在同一个类且在聚类结果中不在同一个簇的样本对的数量。

基于上述的这四个度量值，可以确定以下的聚类性能度量外部指标：

Jaccard系数(Jaccard Coefficient)（JC）：

FM指数(Fowlkes and Mallows Index)（FMI）

FMI=\sqrt{\frac{a}{a+b}\times \frac{a}{a+c}}

Rand指数(Rand Index)（RI）

其中 $m$ 为样本总数量。

上述性能度量的结果均在 $[0,1]$ 区间，值越大越好。这个评价标准还有一个进阶版本调整兰德系数(ARI(Adjusted Rand Index))，与这个类似的还有一个调整互信息(AMI，Adjusted Mutual Information) ，内部使用信息熵。就不展开说了，感兴趣的可以查阅相关资料。