有学者按照机器学习发生场景的不同，将机器学习划分为三种范式，它们分别是有监督学习、无监督学习与强化学习。有监督学习指的是用来训练模型的数据是带有标签的，训练过程可简单概括为根据“数据带有的标签”与“模型产生的输出”之间的误差来调整模型的参数。无监督学习则适用于无标签的数据集，它往往通过对训练集进行记忆，尝试查找出数据中隐含的规律，比如，根据数据的相似度对它们进行划分。强化学习同样是针对无标签的数据集，但在强化我们会有一个reward函数，来判断我们的动作是否合理。本系列文章的二到七篇着重介绍了有一些有监督学习的算法，上一篇中也对强化学习进行了简单的概括，本篇文章将介绍最为常见的无监督学习算法—聚类。

目录

一、什么是聚类？

二、一些常见的聚类算法

一、什么是聚类

“聚类”一词最早应该出自《战国策》中的“方以类聚，物以群分”，这句话的意思是“同类的东西常聚在一起，志同道合的人相聚成群，反之就分开”。将这句话中所发现的规律应用到我们的机器学习中对无标签的数据进行处理，也即假设相似度高的输入数据往往属于同一类别，便是“聚类”的核心思想。

形式化地说，假定样本集

包含m个无标记样本，每个样本

是一个n维特征向量，则聚类算法将样本集D划分为k个不相交的簇

,其中

,且

.相应地，我们用

表示样本

的“簇标记”，即

.于是，聚类的结果可用包含m个元素的簇标记向量

表示。

二、一些常见的聚类算法

一般来说，聚类方法可分为四种：

  • 基于位置的聚类 k-means、k-modes、k-medians
  • 层次聚类 agglomerative、birch
  • 基于密度的聚类 DDBSCAN
  • 基于模型的聚类 GMM、基于神经网络的算法

针对以上的四种方法，接下来各举一个算法进行介绍

1、K-means

算法步骤

（1） 确定聚类个数K

（2） 选定K个D维向量作为初始类中心

（3） 对每个样本计算与聚类中心的距离，选择最近的作为该样本所属的类

（4） 在同一类内部，重新计算聚类中心，不断迭代，直到收敛

优点：

速度快，计算简便；适合发现球形聚类，可发现离群点

缺点：

我们必须事先给出聚类的组数；对初始聚类中心敏感；对异常值免疫能力差；对谱聚类或特征映射效果不好。

2、Agglomerative

算法步骤

（1）计算所有个体和个体之间的距离，找到离得最近的两个样本聚成一类

（2）将上面的小群体看做一个新的个体，再与剩下的个体，计算所有个体与个体之间的距离，找离得最近的两个个体聚成一类，以此类推

（3）重复上述步骤，直至聚成一类

对该过程比较直观的理解可参考下图

优点：

不需要确定K值，可根据你的主观划分，决定分成几类。

缺点：

虽然解决了层次聚类中Kmeans的问题，但计算量特别大。与Kmeans相比两者的区别，除了计算速度，还有kmeans只产出一个聚类结果和层次聚类可根据你的聚类程度不同有不同的结果。

3、DBSCAN

算法步骤

（1） 首先确定半径r和minPoints。随机选择一个没有被访问过的数据点，以这个点为中心，计算以r为半径的圆内包含的点的数量是否大于或等于minPoints，如果大于或等于minPoints则该点被标记为central point，反之则会被标记为noise point。

（2） 重复1的步骤，如果一个noise point存在于某个central point为半径的圆内，则这个点被标记为边缘点，反之仍为noise point。重复步骤1，直到所有的点都被访问过。

优点：

不需要知道簇的数量

缺点：

需要确定距离r和minPoints

4、GMM

GMM即混合高斯模型，属于软聚类，每个样本可以属于多个类，有概率分布。使用高斯混合模型（GMM）做聚类首先假设数据点是呈高斯分布的，相对应K-Means假设数据点是圆形的，高斯分布（椭圆形）给出了更多的可能性。我们有两个参数来描述簇的形状：均值和标准差。所以这些簇可以采取任何形状的椭圆形，因为在x，y方向上都有标准差。因此，每个高斯分布被分配给单个簇。

所以要用GMM做聚类首先应该找到数据集的均值和标准差，我们将采用一个叫做最大期望(EM)的优化算法。

算法步骤：

1. 选择簇的数量（与K-Means类似）并随机初始化每个簇的高斯分布参数（均值和方差）。也可以先观察数据给出一个相对精确的均值和方差。

2. 给定每个簇的高斯分布，计算每个数据点属于每个簇的概率。一个点越靠近高斯分布的中心就越可能属于该簇。

3. 基于这些概率我们计算高斯分布参数使得数据点的概率最大化，可以使用数据点概率的加权来计算这些新的参数，权重就是数据点属于该簇的概率。

4. 重复迭代2和3直到在迭代中的变化不大。

优点：

可理解、速度快

缺点：

初始化敏感、需要手工指定k（高斯分布）的个数、不适合非凸分布数据集（基于密度的聚类和核方法可以处理）

参考文献

1、《机器学习》，周志华

2、聚类算法，fionaplanet，cnblogs.com/fionacai/p/

3、常见的六大聚类算法，诗蕊，blog.csdn.net/Katherine