1、聚类简介

西瓜书上对于聚类的说明很详细：

总结下来，聚类的关键词有几个：无监督、划分不相交的簇、寻找数据内在结构、其它任务前驱过程。

2、性能度量

将一组无标记的数据划分成多个不相交的簇有多种分法，我们如何度量一种划分方式是好的还是不好的呢？我们需要确定某种性能度量指标作为优化目标，以便我们找到“最优”的聚类。（这里的最优是对于我们选定的性能度量指标而言的，这个指标反映了我们对于模型的偏好）

直观来讲，什么样的聚类结果是好的呢？我们希望得到的聚类结果是同一簇的样本尽可能相似，不同簇的样本尽可能不同。即“簇内相似度”大、“簇间相似度”小。

聚类的性能指标可以分为两大类：外部指标和内部指标。所谓外部指标，就是我们先得到一个“参考模型”（比如专家给定的划分模型），将聚类结果与之进行比较，从而得到外部指标。内部指标则直接考察聚类结果而不借助任何参考模型。

西瓜书上列出了常用的几种外部指标和内部指标。外部指标有：

可以看到以上指标虽然形式上不同，但都度量了聚类结果和参考模型间的相似性大小。因此我们希望以上指标都是越大越好。

内部指标有：

可以看到内部指标一般要借助距离来定义。因为距离在某种程度上代表了样本之间相似度的大小（两个样本距离越小，相似度越大），关于距离的定义有多种（下节说明）。

3、距离度量

上一节我们已经看到，关于距离的定义对于内部指标的设定至关重要。

最常用的距离度量就是闵科夫斯基距离，其特例包括欧氏距离和曼哈顿距离：

另外我们需要注意属性或特征是否是有序的，只有有序属性才能应用上述距离，无序的属性则需要其它的距离形式：

最后我们需要注意，虽然我们的相似度度量通常是基于距离度量，但是相似度度量通常并不满足直递性，西瓜书上的图形象地说明了这一点：

4、原型聚类

原型聚类也称为“基于原型的聚类”，此类算法假设聚类结构能通过一组原型刻画。通常情况下，算法先对原型初始化，然后迭代求解。

西瓜书上列举了三种原型聚类方法。其中k-means算法已经很熟悉了，它是简洁且强大的算法的代表之一，思路非常简单，但效果通常很好。

学习向量量化法（Learning Vector Quantization，LVQ）我是第一次见，相比其它聚类算法，LVQ比较特别的地方在于假设样本带有类别标记，学习过程中需要利用这些监督信息来辅助聚类。

算法流程如下：

LVQ的核心想法是找K个向量来代表这K类数据的模式。最简单的方法就是我对每类求均值，这是个很好的想法，但是如果每个类中都有若干离群点，那就可能会导致均值不能很好的代表那类数据的输入模式。怎么做呢？可以采用投票机制！

LVQ所做的是，从D中随机选取样本，观察此样本和距离其最近的原型向量对应的类，若此样本和原型向量对应的类相同，我们就让这个原型向量向此样本的方向靠拢；若此样本和原型向量对应的类不同，我们就让这个原型向量向此样本的方向远离。这个过程其实就相当于一种投票，每个样本都给距离其最近的原型向量投赞成（吸引）票，给其它原型向量投反对（排斥）票。

第三种原型聚类算法是高斯混合聚类，其算法流程如下：

实际上，上述过程的3~5对应EM算法的E step，6~10对应EM算法的M step。关于EM算法收敛性证明的学习记录于https://www.jianshu.com/p/a215ae3c1bd8

下面我们直观地理解一下高斯混合聚类的思想：

高斯混合聚类方法采用概率模型（高斯分布）对原型进行刻画，簇划分由原型的后验概率（属于各个类的概率）确定。

当我们假设混合高斯模型是有 $K$ 个高斯模型线性组合而成的，则我们就假定了模型最后将数据分为 $K$ 个簇。因为我们假设数据由高斯混合模型生成，所以我们可以把数据的生成过程分为两部分：各个模型的线性系数表示各个高斯混合成分的先验概率，我们依据此先验概率对各个成分进行选择；选择了成分后，我们依据此成分对应的分布来生成数据。