机器学习-聚类

简介

前面介绍的线性回归，SVM等模型都是基于数据有标签的监督学习方法，本文介绍的聚类方法是属于无标签的无监督学习方法。其他常见的无监督学习还有密度估计，异常检测等。

聚类就是对大量未知标注的数据集，按照数据的内在相似性将数据集划分为多个类别（在聚类算法中称为簇），使类别内的数据相似度高，二类别间的数据相似度低。

相似度

在聚类算法中，大多数算法都是需要计算两个数据点之间的相似度，所以先介绍一下计算相似度的方法。

图1

其中Minkowski距离是所有范式距离的统称，当p=1时是L1距离也叫曼哈顿距离，当p=2时是L2距离也叫欧式距离。而如果两个数据X，Y的均值都为0时，则X和Y的Pearson相关系数就是X和Y的余弦相似度。

下面来介绍一下常见的聚类方法：基于原型聚类的K-means聚类算法以及其衍生算法K-means++，基于密度聚类的DBSCAN聚类算法以及谱聚类。

K-Means聚类：

k-means算法的思想是：通过人工指定k的值确定分类簇的类别数，随机选择k个数据点作为各个簇的中心点，然后通过迭代将一类数据（相似度高的一类数据）划入各个簇中。k-means的优点是容易实现，可以认为确定划分类别的个数。但是算法可能收敛到局部极小值，并且在大规模数据上收敛速度慢。

算法过程：

1）随机选择k个初始类别中心点，μ1，μ2.....μk。

2）对于每个样本计算其与各个中心点的距离，将该样本划入距离最近的一个类别簇中。

3）将所有数据划分完毕后，取每个簇的均值作为各个簇Ci的新中心点。

图2

4）重复2）和3）过程，直到收敛，也就是簇中心点变化小于阈值。

个人代码实现：

图3

需要注意的几个点是：

1）如果簇中包含异常点，在计算簇均值时可能影响结果，如[1,1,1,2,100] 这个簇的均值为21，但是已经距离样本中大多数数据很远了。所以有时在取均值时换一种方法取簇的中位数，这个算法称为K-mediod聚类。

2）初始值敏感，K-means算法不稳定只要是由于初始值随机选择，同样的数据同样的参数不同的初始值的模型训练结果不同，一种解决方案是：随机选取第一个中心点，然后根据第一个中心点到其他数据的距离作为权重去选取第二个中心点，使距离第一个中心点最远的数据点有更大的机率作为第二个中心点，依次类推一个个选择出簇的中心点初始值，这个方法称为K-means++聚类算法。或者使用固定的前k个样本作为中心点的初始值，这样可以固定结果，但是收敛速度却可能变慢。

3）K-means算法适用于近似圆形分布的数据集，一些其他特殊的数据分布很难有好的聚类效果。

DBSCAN聚类：

基于密度聚类的算法思想是：只要样本点的密度大于阈值，就将该样本点加到最近的簇中。

首先介绍几个概念：

1）ε-邻域，指的是在数据集中，所有到xi数据点的距离小于ε的数据点的集合。

2）核心对象，如果样本点xi的ε-邻域中包含的样本个数大于等于指定值m，则该点xi称为核心点。

3）密度直达，样本点xi与它的ε-邻域中的样本点之间称为密度直达。

4）密度可达，样本点xi与它的ε-邻域中样本的ε-邻域中的样本点称为密度可达。

DBSCAN就是将数据集中的密度可达的所有样本点划分为一个簇，某些样本密度可达形成一个簇，另外一些样本点又可以密度可达就又形成另外一个簇。簇内样本点均密度可达，但是簇内的样本点与其他簇的样本点无法可达，最后形成了多个簇类。

算法过程：

1）如果一个点p的ε-邻域包含多于m个样本，则创建一个以p为核心对象的新簇。

2）寻找并合并核心对象直接密度可达的样本点。

3）没有新点可以更新簇时，算法结束。

个人代码实现：

图4

DBSCAN算法不需要指定簇类的个数，它是通过数据分布内在联系形成的簇类，所以样本分布近的样本团就容易分为一个簇。而其他不和任何样本点密度可达的样本点就划分为异常点或者叫做噪音点的类别中。

层次聚类

1）凝聚的层次聚类：AGNES算法

自底向上的策略，将每个样本数据作为一簇，然后合并这些原子簇为越来越大的簇，直到符合要求为止。

2）分裂的层次聚类：DIANA算法

自顶向下的策略，将所有对象作为一个大簇，然后逐步细分为越来越小的簇，有些像决策树。

谱聚类（SC）

方阵作为线性算子，它的所有特征值的全体统称为方阵的谱，其中最大的特征值成为谱半径。

算法过程：

1）计算得到邻接距离矩阵W：将各个样本与各个样本做距离计算，求任意两个样本的距离，这里使用的是高斯距离公式，形成一个N*N的对称阵，其中对角线上的元素全为0（自己与自己的距离），N为样本个数。

2）求对角矩阵D：将各个样本点xi与其他样本点的距离加和，得到该样本点的度（参考图），形成一个对角线上是各个样本点的度，其他元素是0的N阶对角矩阵。

3）求拉普拉斯矩阵L：L = D - W，这是一个对称阵，且L>=0，所以为半正定。

4）对L求特征分解，取前k个特征向量，组成一个N*k的矩阵A，m为样本个数，k为簇个数。

5）使用K-means聚类算法对A矩阵做聚类，得到的聚类结果就是对原数据集的聚类结果。

谱聚类的思想（个人理解）：就是对原数据做降维处理，得到一个N*k的矩阵，并且其中的数据值也经过计算变成0/1形式，再对该矩阵进行K-means聚类时，能够很容易并快速得到较为准确的结果。没有深入了解学习谱聚类，以后有时间敲一下谱聚类的代码，深入了解后再来更新。

总结

各个聚类方法有自己的适用场景，根据数据分布的不同选择合适的聚类方法可以得到良好的结果，下图是我用自己写的代码与sklearn库中的聚类方法做了一个对比：

图5

可以看出DBSCAN很容易将一团数据划为一簇。有兴趣的朋友可以自己写一下代码，做更多的对比实验（个人比较懒），本文如有写错的地方请帮忙指出，共同进步，谢谢!

待更新。。

详细代码可参考GitHub:代码链接

参考书籍:

《机器学习》 周志华  著