物以类聚，人以群分。

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

模型分类划分聚类(Partitioning Clustering)

假设数据本身有确定的类别(簇)个数，某条数据确定地属于某簇，学习的目的就是划分每个簇的具体样本子集，比如K-Means、K-Means++、Mini Batch K-Means，是最常见的聚类方法。基于模型的聚类(Model-Based Clustering)

假设数据由隐藏分布生成，通过模型学习这个隐藏的分布，比如高斯混合模型GMM(Gaussian Mixture Models)。层次聚类(Hierarchical Clustering)

完整的聚类结果是一棵树，叶子节点为单个样本，根节点为所有样本。每个节点代表一个簇。

可以根据实际需求，从上而下或从下而上，选择聚成若干簇。基于密度的聚类(Density-Based Clustering)

假设聚类结构能通过样本分布的紧密程度确定。通常情况下，密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇以达到最终的聚类结果。 (摘自周志华《机器学习》)，比如DBSCAN、OPTICS等。 谱聚类(Spectral Clustering)等

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

scikit-learn Clustering文档

K-Means

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

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

Andrew Ng CS229

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

K-Means++

K-Means初始质心是随机的，初始的质心有可能使最终的聚类结果局部最优。

K-Means++在K-Means的基础上，优化了初始质心的位置，尽量保证各个簇的质心，保持较远的距离。

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

David Arthur and Sergei Vassilvitskii

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

D. Sculley Web-Scale K-Means Clustering

Gaussian mixture models

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

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

Andrew Ng CS229

根据高斯模型的形式，可以知道，K-Means方法优化的距离和高斯模型本身差个协方差Σ；

可以理解成K-Means是GMM的特例，K-Means假设的是每个高斯分布的协方差相等，可以通过下图感受下：

Hierarchical clustering

以自下而上聚类为例：

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

示意图如下：

scikit-learn Hierarchical Clustering文档

重点在于，两个簇之间的距离度量方式，属于多对多的相似度估计。

常见的分为四种：

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

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

DBSCAN

在给定半径的邻域范围和领域节点数约束下，寻找核心样本，核心样本间并可以进行同簇传递，直至找到非核心样本。

如图：点B、点C可通过中间密度传递连接，而点位于整个密度环外，密度不可到达，不属于该簇。

ERICH SCHUBERT DBSCAN Revisited, Revisited

学习过程如下，：

周志华 机器学习

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

scikit-learn DBSCAN文档

评价

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

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

周志华 机器学习

总结

聚类最终的效果是根据现有数据属性，为数据增加一个簇类别的标签，本质是一个学习新特征的过程。

这种数据的内在结构信息，可以用于分类本身；也可以当作特征工程，为监督学习下游任务提供更多特征；或者应用于数据预处理，筛选有用数据，降低后续模型训练复杂度。

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

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