物以类聚，人以群分。
聚类(cluster)是最常见的无监督机器学习算法，通过样本属性间的某种距离度量，将数据集分成相似结构的子集。

模型分类

1. 划分聚类(Partitioning Clustering)
   假设数据本身有确定的类别(簇)个数，某条数据确定地属于某簇，学习的目的就是划分每个簇的具体样本子集，比如K-Means、K-Means++、Mini Batch K-Means，是最常见的聚类方法。
2. 基于模型的聚类(Model-Based Clustering)
   假设数据由隐藏分布生成，通过模型学习这个隐藏的分布，比如高斯混合模型GMM(Gaussian Mixture Models)。
3. 层次聚类(Hierarchical Clustering)
   完整的聚类结果是一棵树，叶子节点为单个样本，根节点为所有样本。每个节点代表一个簇。可以根据实际需求，从上而下或从下而上，选择聚成若干簇。
4. 基于密度的聚类(Density-Based Clustering)
   假设聚类结构能通过样本分布的紧密程度确定。通常情况下，密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇以达到最终的聚类结果。 (摘自周志华《机器学习》)，比如DBSCAN、OPTICS等。
5. 谱聚类(Spectral Clustering)等

各模型大致效果及时间复杂度总览图如下，注意观察样本簇的形状：

scikit-learn Clustering文档

K-Means

K-Means是聚类的代名词，非常简单、常见和重要。

1. 选择聚类簇的个数k
2. 随机生成k个簇的质心
3. 为每个样本选择欧拉距离最近的质心
4. 为每个簇，平均样本，更新质心
5. 重复3、4，直至收敛(样本对应簇及簇的质心不再变)，一般根据迭代次数或质心位置变化来控制迭代次数
6. K-Means采用欧拉距离作为相似度度量，所以K-Means适合簇是凸集，不适合不规则的图形。

Andrew Ng CS229

Andrew Ng CS229 K-Means学习过程示意图

 K-Means++

K-Means初始质心是随机的，初始的质心有可能使最终的聚类结果局部最优。
K-Means++在K-Means的基础上，优化了初始质心的位置，尽量保证各个簇的质心，保持较远的距离。

1. 均匀随机选择一个样本作为质心
2. 以样本离所有质心最近的距离作为度量，距离越近，抽样概率越低，尽可能选择距离已确定质心的簇较远的样本作为新增簇的质心
3. 重复2，直至k个质心全部选择完成

David Arthur and Sergei Vassilvitskii

Mini-batch K-Means

1. 每轮随机mini-batch个样本更新质心
2. 以单个样本为单位，采用梯度的形式，更新质心的位置；其中每个样本的贡献除了取决于与质心的距离，还与曾经随机到该簇的样本总数有关，数量越多，更新越谨慎，变化越稳定。
3. mini-batch K-Means是K-Means的一个工程简化版本，试验表明，mini-batch K-Means性能稍微差一些，但该算法速度更快，尤其数据海量时，还是很有必要的。

D. Sculley Web-Scale K-Means Clustering

Gaussian mixture models

假设每个样本都由某个高斯分布产生，高斯分布的个数代表聚类簇的大小。

1. 选定簇的个数k
2. 初始化每个簇的高斯分布参数
3. E-step：估计样本属于某个簇的期望
4. 根据每个簇最新的样本，更新其分布参数
5. 重复3、4，直至收敛

Andrew Ng CS229

根据高斯模型的形式，可以知道，K-Means方法优化的距离和高斯模型本身差个协方差Σ；
可以理解成K-Means是GMM的特例，K-Means假设的是每个高斯分布的协方差相等，可以通过下图感受下：

Hierarchical clustering

以自下而上聚类为例：

1. 每一个单独是一个簇
2. 合并距离最近相似度最高的两个簇为新簇，并删除旧的子簇
3. 重复2，直至满足聚类簇的个数k

示意图如下：

scikit-learn Hierarchical Clustering文档

重点在于，两个簇之间的距离度量方式，属于多对多的相似度估计。
常见的分为四种：

1. Ward：两簇合并之后的方差。
2. 全链接(complete linkage)：两簇之间所有样本间的最大距离。
3. 均链接(Average linkage)：两簇之间所有样本间的平均距离。
4. 单链接(Single linkage)：两簇之间所有样本间的最小距离。

Ward类似于K-Means，适合欧拉距离，后面三种的距离可以任意定义。

DBSCAN

在给定半径的邻域范围和领域节点数约束下，寻找核心样本，核心样本间并可以进行同簇传递，直至找到非核心样本。
如图：点B、点C可通过中间密度传递连接，而点位于整个密度环外，密度不可到达，不属于该簇。

ERICH SCHUBERT DBSCAN Revisited, Revisited

学习过程如下，：

周志华 机器学习

黑点为非核心样本，大圆圈为核心样本。

scikit-learn DBSCAN文档

评价

聚类算法最大的问题就是很难统一评价，有两个大的方向：

1. 簇间距离越大越好，不同簇尽量分离。
2. 簇内距离越小越好，簇内尽量聚合。

周志华 机器学习

总结

聚类最终的效果是根据现有数据属性，为数据增加一个簇类别的标签，本质是一个学习新特征的过程。
这种数据的内在结构信息，可以用于分类本身；也可以当作特征工程，为监督学习下游任务提供更多特征；或者应用于数据预处理，筛选有用数据，降低后续模型训练复杂度。

聚类过程相对比较简单，结果相对比较宽泛，但这是一种很接近人类的学习方式，对数据集无标签的要求，意味着其更大的普适性。

不同模型侧重点不同，实际使用中，需要根据数据量及数据本身分布，在性能和时间之间折中。