Question

聚类（Clustering）

Answer 1

首先我们先来认识一下什么是聚类任务。
聚类是“无监督学习（unsupervised learning）”中重要的一种。其目标是：通过对无标记的训练样本学习，来揭示数据内在的性质以及规律，为进一步的数据分析做基础。聚类的结果是一个个的簇（Cluster）。所以来说，聚类通常作为其他学习算法的先导，比如在分类问题中，常常先做聚类，基于聚类的不同簇来进行分类模型的训练。
我们先来认识一下聚类算法涉及到两个基本问题：性能度量 & 距离计算。后面我们再具体讲解聚类的经典算法。

由于聚类算法是无监督式学习，不依赖于样本的真实标记。所以聚类并不能像监督学习例如分类那样，通过计算对错（精确度/错误率）来评价学习器的好坏或者作为学习器的优化目标。一般来说，聚类有两类性能度量指标：外部指标和内部指标

所谓外部，是将聚类结果与某个参考模型的结果进行比较， 以参考模型的输出作为标准，来评价聚类的好坏。 假设聚类给出的结果为 λ，参考模型给出的结果是λ*，则我们将样本进行两两配对，定义：

内部指标不依赖任何外部模型，直接对聚类的结果进行评估。直观来说： 簇内高内聚，簇间低耦合 。定义：

我们从小学的距离都是欧氏距离。这里介绍几种其他的距离度量方法：

这里对于无需属性我们用闵可夫斯基距离就不能做，需要用VDM距离进行计算，对于离散属性的两个取值a和b，定义：

所以在计算两个样本的距离时候，将两种距离混合在一起进行计算：

原型聚类即“基于原型的聚类（prototype-based clustering）”，原型指的是样本空间中具有代表性的点（类似于K-Means 选取的中心点）。通常情况下来说，算法现对原型进行初始化，然后对原型进行迭代更新求解。而不同的初始化形式和不同的求解方法，最终会得到不同的算法。常见的 K-Means 便是基于簇中心来实现聚类；混合高斯聚类则是基于簇分布来实现聚类。下面我们具体看一下几种算聚类算法：

K-Means 聚类的思想十分简单， 首先随机指定类中心，根据样本与类中心的远近划分类簇；然后重新计算类中心，迭代直至收敛。 实际上，迭代的过程是通过计算得到的。其根本的优化目标是平方误差函数E：

其中 u_i 是簇 C_i 的均值向量。直观上来看，上式刻画了簇内样本围绕簇均值向量（可以理解为簇中心）的紧密程度，E值越小，则簇内样本的相似度越高。
具体的算法流程如下：

书上还给出了基于具体西瓜样本集的计算过程说明。可以看一下。

LVQ 也是基于原型的聚类算法，与K-Means 不同的是， LVQ使用样本的真实类标记来辅助聚类 。首先，LVQ根据样本的类标记，从各类中分别随机选出一个样本作为该类簇的原型，从而形成了一个 原型特征向量组 ，接着从样本集中随机挑选一个样本，计算其与原型向量组中每个向量的距离，并选取距离最小的向量所在的类簇作为该样本的划分结果，再与真实类标比较：

可以看到，K-Means 和 LVQ 都是以类中心作为原型指导聚类，而高斯混合聚类则采用 高斯分布 来描述原型。现在假设每个类簇中的样本都服从一个多维高斯分布，那么空间中的样本可以看做由K个多维高斯分布混合而成。
多维高斯的概密为：

密度聚类是基于密度的聚类，它从个样本分布的角度来考察样本之间的 可连接性 ，并基于可连接性（密度可达）不断拓展疆域（类簇）。最著名的就是DBSCAN（Density-Based Spatial Clustering of Applications with Noise），首先我们需要明白以下概念：

层次聚类试图在不同层次对数据集进行划分，从而形成属性的聚类结构。
这里介绍一种“自底向上”结合策略的 AGNES（AGglomerative NESting）算法。假设有N个待聚类的样本，AGNES算法的基本步骤如下：

可以看出其中最关键的一步就是 计算两个类簇的相似度 ，这里有几种度量方法：
（1）单链接（singal-linkage）：取类间最小距离