《机器学习》笔记-聚类（9）

刘才权

写在最前面

如今机器学习和深度学习如此火热，相信很多像我一样的普通程序猿或者还在大学校园中的同学，一定也想参与其中。不管是出于好奇，还是自身充电，跟上潮流，我觉得都值得试一试。对于自己，经历了一段时间的系统学习（参考《机器学习/深度学习入门资料汇总》），现在计划重新阅读《机器学习》[周志华]和《深度学习》[Goodfellow et al]这两本书，并在阅读的过程中进行记录和总结。这两本是机器学习和深度学习的入门经典。笔记中除了会对书中核心及重点内容进行记录，同时，也会增加自己的理解，包括过程中的疑问，并尽量的和实际的工程应用和现实场景进行结合，使得知识不只是停留在理论层面，而是能够更好的指导实践。记录笔记，一方面，是对自己先前学习过程的总结和补充。 另一方面，相信这个系列学习过程的记录，也能为像我一样入门机器学习和深度学习同学作为学习参考。

章节目录

• 聚类任务
• 性能度量
• 距离计算
• 原型聚类
• 密度聚类
• 层次聚类

（一）聚类任务

在无监督学习中（unsupervised learning）中，训练样本的标记信息是未知的，目标是通过对无标记的训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。此类学习任务中研究最多、应用最广的是“聚类”（clustering）。
聚类试图将数据集中的样本划分为若干通常是不相交的子集，每个子集称为一个“簇”（cluster）。
聚类既能作为一个单独的过程，用于找寻数据内的分布结构，也可作为分类等其他学习任务的前驱过程。

（二）性能度量

聚类性能度量亦称聚类“有效性指标”（validity index）。与监督学习中的性能度量作用相似。对聚类结果，我们需通过某种性能度量来评估其好坏；另一方面，若明确了最终将要使用的性能度量，则可直接将其作为聚类过程的优化目标，从而更好地得到符合要求的聚类结果。
聚类是将样本集D划分为若干不相交的子集，即样本簇。直观上看，我们希望“物以类聚”，即同一簇的样本尽可能彼此相似，不同簇的样本尽可能不同。换言之，聚类结果的“簇内相似度”（intra-cluster similarity）高且“簇间相似度”（inter-cluster similarity）低。
聚类性能度量大致有两类：
* “外部指标”（external index）
将聚类结果与某个“参考模型”（reference model）进行比较；
* “内部指标”（internal index）
直接考察聚类结果而不利用任何参考模型；

常用的聚类性能度量外部指标有：
* Jaccard系数（Jaccard Coefficient，简称 JC）
* FM指数（Fowlkes and Mallows Index，简称FMI）
* Rand指数（Rand Index，简称RI）

常用的聚类性能度量内部指标有：
* DB指数（Davies-Bouldin Index，简称DBI）
* Dunn指数（Dunn Index，简称DI）

（三）距离计算

给定样本xi=（xi1，xi2；...；xin），与xj=（xj1；xj2；...；xjn），最常用的是”闵可夫斯基距离“（Minkowski distance），

p=2时，闵可夫斯基距离即欧氏距离（Euclidean distance），

p=1时，闵可夫斯基距离即曼哈顿距离（Manhattan distance），

上面的距离计算式都是事先定义好的，但在不少现实任务中，有必要基于数据样本来确定合适的距离计算式，这可通过”距离度量学习“（distance metric learning）来实现。

（四）原型聚类

原型聚类亦称”基于原型的聚类“（prototype-based clustering），此类算法假设聚类结构能通过一组原型刻画，在现实聚类任务中极为常用。通常情形下，算法先对原型进行初始化，然后对原型进行迭代更新求解。采用不同的原型表示、不同的求解方式，将产生不同的算法。

1. k均值算法

给定样本集D={x1，x2，...，xm}，”k均值“（k-means）算法针对聚类所得簇划分C={C1，C2，...，Ck}最小化平方误差，

其中，

x是簇Ci的均值向量。直观来看，上面式子在一定程度上刻画了簇内样本围绕簇均值向量的紧密程度，E值越小则簇内样本相似度越高。

2. 学习向量量化

与k均值算法类似，“学习向量量化”（Learning Vector Quantization，简称LVQ）也是试图找到一组原型向量来刻画聚类结构，但与一般的聚类算法不同的是，LVQ假设数据样本带有类别标记，学习过程用样本的这些监督信息来辅助聚类。

3. 高斯混合聚类

与k均值、LVQ用原型向量来刻画聚类结构不同，高斯混合（Mixture-of-Gaussian）聚类采用概率模型来表达聚类原型。

（五）密度聚类

密度聚类亦称“基于密度的聚类”（density-based clustering），此类算法假设聚类结构能通过样本分布的紧密程度确定。通常情况下，密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果。
DBSCAN是一种著名的密度聚类算法。

（六）层次聚类

层次聚类（hierarchical clustering）试图在不同层次对数据集进行划分，从而形成树形的聚类结构。数据集的划分可采用“自底向上”的聚合策略，也可采用“自顶向下”的分拆策略。
AGNES是一种采用自底向上聚合策略的层次聚类算法。