机器学习第十五章聚类任务原型聚类

资料参考来源：

清华大学出版社周志华《机器学习》第九章

聚类任务

监督学习的模型我们已经见过了很多，现在让我们引入无监督学习的部分。

我们知道，监督学习中的分类任务会提供我们关于样本的类别标签，然后让我们根据这些已有类别标签的样本的特征训练出一个合适的模型，再用这些模型去读取测试集中样本的特征从而判断测试集中的样本的类别标签。

在无监督学习（unsupervised learning）中也有类似的问题，但不同的是，这个问题中的数据集是不含有类别标签的，这种问题我们就称之为聚类（clustering）问题。

简单的说，再监督学习的分类问题中，我们的训练数据集是这样子的：

但在聚类问题中，它就变成下图这种：

我们可以从图中观察到，尽管左右两部分的数据集的样本标记的颜色是相同的（类别标签是无法区分的），但它们依然有聚在一堆的倾向，这样的在训练数据集中若干个通常是不相交的子集，每一个子集就称为一个簇（cluster）（亦可称“类”）

在聚类问题中，每一个簇都对应着一个潜在的概念，以西瓜为例，某一簇可能表示本地瓜，某一簇表示外地瓜，某一簇表示比较甜的瓜…等等等等，簇对应的概念（或说类别）在训练之初我们是不知道的，对于聚类算法而言，聚类过程仅能在学习过程中自动形成簇结构，而每个簇所对应的概念语义这需要由使用者来赋予。

符号标记

我们还是比较习惯于用符号来规范化我们在聚类问题中用到的一些数学工具，这里我参考的是西瓜书上的符号规范，当然，之后还是可能会穿插一些《统计学习方法》中的符号，我会尽量统一符号的使用…

首先我们规定样本集 $$D=\{x_1,x_2,...,x_m\}$ $包含m各无标记样本
每个样本 $$x_i=\{x_{i1};x_{i2};...;x_{in}\}$ $是一个n维特征向量
聚类算法将样本集D划分为 k 个不相交的簇 $$\{C_l\mid l=1,2,...,k\}$ $，其中 $$C_{l'}\bigcap_{l'≠l}C_l=\emptyset$ $且 $$D=\bigcup^{k}_{l=1}C_l$ $
用 $$λ_j∈\{1,2,...,k\}$ $表示样本 $$x_j$ $的簇标记（cluster label），即 $$x_j∈C_{λ_j}$ $。聚类的结果可以用包含 $$m$ $个元素的簇标记向量 $$λ=(λ_1;λ_2;...;λ_m)$ $表示。

性能度量与距离计算

要实现一个聚类算法，我们需要解决两个基本问题——性能度量和距离计算。

性能度量

又称有效性指标（validity index）。类似于监督学习中的性能度量，对于聚类结果，我们就通过某种性能度量来评估其好坏；另一方面，通过明确最终要使用的性能度量，也可以直接将其作为聚类过程的优化目标，从而更好地得到符合要求的聚类结果。

聚类的目的是将样本集D划分为若干个互不相交的子集，即样本簇。为了评价划分效果，我们给出两个指标：

一个是簇内相似度（intra-cluster similarity），用于表示同一簇内的样本的相似程度，该值越高越好。
一个是簇间相似度（inter-cluster similarity），用于表示不同簇样本的相似程度，该值越低越好。

聚类的性能度量也分为两类：

一类是将聚类结果与某个参考模型（reference model）进行比较，称为外部指标（external index）
一类是直接考查聚类结果，称为内部指标（internal index）

外部指标

对数据集 $$D=\{x_1,...,x_m\}$ $，假定通过聚类给出的簇划分为 $$C=\{C_1,...C_k\}$ $，参考模型给出的簇划分为 $$C^*=\{C_1^*,...C^*_S\}$ $，相应的，令 $$λ$ $与 $$\lambda^*$ $分别表示与 $$C$ $和 $$C^*$ $对应的簇标记向量。我们将样本两两配对考虑，并定义

其中集合 $$SS$ $表示在 $$C$ $中隶属于相同簇且再 $$C^*$ $中也隶属于相同簇的样本对的集合， $$SD$ $表示在 $$C$ $中隶属于相同簇而在 $$C^*$ $中隶属于不同簇的样本对的集合， $$DS,SS$ $以此类推。（ $$SameSame,SameDifferent...$ $）由于每个样本对 $$(x_i,x_j)(i < j)$ $仅能出现在一个集合中，因此有 $$a+b+c+d=\frac{m(m-1)}{2}$ $（此即样本对总数 $$m-1+m-2+...+1+0=m(m-1)/2$ $）

基于上面的定义可以导出常用的聚类性能度量外部指标：

Jaccard 系数（Jaccard Coefficient , JC）

FM 指数（Fowlkes and Mallows Index , FMI）

Rand 指数（Rand Index, RI）

上述性能度量的结果均在 $$[0,1]$ $区间，值越大越好。

内部指标

考虑聚类结果的簇划分为 $$C = \{C_1,...,C_k\}$ $，定义

其中 $$dist(. , .)$ $表示两个样本之间的距离，距离越大则样本的相似度越低； $$μ$ $表示簇 $$C$ $的中心点$$$μ=\frac{1}{

}\sum_{1 ≤ i ≤

}x_i $$ ；因此，$ $avg(C) $$对应于簇$ $C$$$内样本间的平均距离。

其中 $$diam(C)$ $对应于簇 $$C$ $内样本间的最远距离， $$d_{min}(C_i,C_j)$ $对应于簇 $$C_i$ $与簇 $$C_j$ $最近样本间的距离， $$d_{cen}(C_i,C_j)$ $对应于簇 $$C_i$ $与簇 $$C_j$ $中心点间的距离。

基于上式我们又可以导出常用的聚类性能度量的内部指标

DB 指数（Davies-Bouldin Index, DBI）

Dunn 指数（Dunn Index, DI）

DBI的值越小越好，而DI的值越大越好。

距离计算

对函数 $$dist(.,.)$ $，如果它是一个距离度量（distance measure），则满足一些基本性质：

直递性又称“三角不等式”

给定样本 $$x_i=(x_{i1};...;x_{in}),x_j=(x_{j1};...;x_{jn})$ $，最常用的是闵可夫斯基距离（Minkowski distance）

当 $$p ≥ 1$ $时距离度量基本性质满足。 $$p-> \infty$ $时得到切比雪夫距离； $$p=2$ $时得到欧氏距离（Euclidean distance）， $$p=1$ $时得到曼哈顿距离（Manhattan distance）。

一个属性是否有“序”对于距离计算非常重要，能直接在属性值上计算距离，如 $$\{1,2,3\}$ $这样的属性称为有序属性（ordinal attribute），像 $$\{男，女\}$ $这样的就称为无序属性（non-ordinal attribute）。

闵可夫斯基距离可用于有序属性。

对无序属性常用VDM（Value Difference Metric）：

令 $$m_{u,a}$ $表示在属性 $$u$ $上取值 $$a$ $的样本数， $$m_{u,a,i}$ $表示在第 $$i$ $个样本簇中属性 $$u$ $上取值 $$a$ $的样本数， $$k$ $为样本簇数，则属性 $$u$ $上两个离散值 $$a$ $与 $$b$ $的VDM距离为

将闵可夫斯基距离和VDM结合可以处理混合属性。假定有 $$n_c$ $个有序属性、 $$n-n_c$ $个无序属性，不失一般性，令有序属性排列在无序属性之前，有

若样本空间中不同属性的重要性不同，还可以使用加权距离（weighted distance），以加权闵可夫斯基距离为例：

权重 $$w_i ≥ 0(i=1,...,n)$ $表征不同属性的重要性，通常 $$\sum^n_{i=1}w_i=1$ $

我们通常基于某种形式的距离来定义相似度度量（similarity measure），距离越大，相似度越小。然而，用于相似度度量的距离未必一定要满足距离度量的所有基本性质，尤其是直递性。西瓜书中用了这样一个例子说明这个情况，假设属性有 $$\{人，马，人马\}$ $我们要表示“人”和“马”都与“人马”相似，但“人”与“马”却不相似的效果时，距离就不再满足直递性，这样的距离称为非度量距离（non-metric distance）

另外，在不少现实任务中，我们还需要基于数据样本来确定合适的距离算式而不能直接用前面所说的已经定义好的距离计算式，这种情况就需要用到距离度量学习（distance metric learning）

原型聚类

“原型”指样本空间中具有代表性的点，原型聚类（亦称基于原型的聚类（prototype-based clustering）这一类算法假设聚类结构能够通过一组原型刻画，在现实聚类任务中极为常用。

通常来说，算法会先对原型进行初始化，然后对原型进行迭代更新求解。

k均值算法

样本集 $$D=\{x_1,...,x_m\}$ $，k均值(k-means)算法针对聚类所得簇划分 $$C=\{C_1,...,C_k\}$ $最小化平方误差

其中$$$μ_i=\frac{1}{

C_i

}\sum_{x ∈C_i}x $$是簇$ $C_i $$的均值向量。显然，$ $E$$$越小簇内样本相似度越高。

最小化式子（9.24）是一个 NP-hard 问题（NP即非确定性多项式（non-deterministic polynomial，缩写NP），NP-hard问题（例如“旅行推销员问题”）通常被认为是不存在一个有效算法来求最优解，只能寻找该类问题的有效地近似算法）。因此，k均值算法采用贪心策略，通过迭代优化来近似求解上式。

算法流程如下

算法第1行对均值向量初始化；第4-8行对当前簇划分进行迭代更新；第9-16行对当前均值向量迭代更新；第18行则表示，若迭代更新后聚类结果保持不变，则返还当前簇划分结果。

学习向量量化

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

给定样本集 $$D=\{(x_1,y_1),...,(x_m,y_m)\}$ $，样本 $$x_j$ $由n个属性描述的特征向量 $$\{x_{j1},...,x_{jn}\}$ $,并且 $$y_j∈Y$ $是样本 $$x_j$ $的类别标记。LVQ的目的是学得一组n维原型向量 $$\{p_1,...,p_n\}$ $，每个原型向量代表一个聚类簇，簇标记 $$t_i∈Y$ $

LVQ算法流程如下

第1行对原型向量进行初始化，如对第q个簇可从类别标记为 $$t_q$ $的样本中随机选取一个作为原型向量。第2-10行度原型向量进行迭代优化，其中最关键的是第6-10行，即找到离原型向量最近的有标记的样本后更新原型向量的方法。

对样本 $$x_j$ $，若最近的原型向量 $$p_{i*}$ $与 $$x_j$ $的类别标记相同，则令 $$p_{i*}$ $向 $$x_j$ $的方向靠拢，如第7行所示。此时更新后的新原型向量 $$p'$ $与 $$x_j$ $之间的距离为

令学习率 $$\eta∈(0,1)$ $，则原型向量 $$p_{i*}$ $在更新为 $$p'$ $之后更接近 $$x_j$ $。

类似地，若 $$x_j$ $与 $$p_{i*}$ $标记不同，那么更新后的原型向量 $$p'$ $与 $$x_j$ $之间的距离就会增大为

从而使得原型向量更加远离样本 $$x_j$ $。

习得一组原型向量后便可实现对样本空间 $$X$ $的簇的划分，所有的样本都将被划入与其最近的原型向量所代表的簇中，换言之每个原型向量 $$p_i$ $也定义了一个与之相关的一个区域 $$R_i$ $，该区域中的每个样本与该原型向量的距离不大于它与其它原型向量 $$p_{i'}(i' ≠ i)$ $的距离，即有

由此形成了对样本呢空间 $$X$ $的簇划分 $$R=\{R_1,...,R_q\}$ $，改划分称为Voronoi剖分（Voronoi tessellation）

如果我们用原型向量来表示其对应的区域中的所有样本，我们就可以实现数据的有损压缩（lossy compression），这称为向量量化（vector quantization）。

高斯混合聚类

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

多元高斯分布的定义：对n维样本空间中 $$X$ $中的随机向量 $$x$ $，若 $$x$ $服从高斯分布，其概率密度函数维

其中 $$μ$ $是n维均值向量， $$Σ$ $是 $$n$ $x $$n$ $ 的协方差矩阵。由式子（9.28）可以看出，高斯分布完全有均值向量 $$μ$ $和协方差矩阵 $$Σ$ $这两个参数确定。

记高斯分布的概率密度函数为$$$p(x

μ,Σ)$$$，定义高斯混合分布

该分布由k个混合成分组成，每个混合成分对应一个高斯分布。其中 $$μ_i$ $与 $$Σ_i$ $是第 $$i$ $个高斯混合成分的参数，而 $$\alpha_i > 0$ $为相应的混合系数（mixture coefficient）， $$\sum^k_{i=1}\alpha_i=1$ $

假设样本的生成过程由高斯混合分布给出：

根据 $$\alpha_1,...,\alpha_k$ $定义的先验分布选择高斯混合成分，其中 $$\alpha_i$ $为选择第 $$i$ $个混合成分的概率，然后，根据被选择的混合成分的概率密度函数进行采样，从而生成相应的样本。

如果训练集 $$D = \{x_1,...x_m\}$ $由上述过程生成，令随机变量 $$z_j∈\{1,...,k\}$ $表示生成样本 $$x_j$ $的高斯混合成分，且其取值未知。则 $$z_j$ $的先验概率 $$P(z_j=i)$ $对应于 $$\alpha_i(i=1,2,...,k)$ $根据贝叶斯公式， $$z_j$ $的后验分布为

即$$$p_M(z_j=i

x_j) $$给出了样本$ $x_j $$由第$ $i $$个高斯混合成分生成的后验概率，简记为$ $\gamma_{ji}(i=1,…,k)$$$

当高斯混合分布（9.29）已知时，有高斯混合聚类将样本集D划分为 k 个簇 $$C=\{C_1,...C_k\}$ $，每个样本 $$x_j$ $的簇标记 $$\lambda_j$ $如下确定：

接下来我们来求解模型参数 $$\{(\alpha_i,μ_i,Σ_i)1 ≤ i ≤ k\}$ $

给定样本集D，采用极大似然估计，即最大化（对数）似然

对该问题采用EM 算法进行迭代优化求解，关于EM算法我们会在之后的一章进行详细的讨论，这里只进行一个简单的推导。

（我们可以先将EM算法的原理用下面这个例子来理解一下：假设有A和B两个碗，我们需要给两个碗乘同样多的菜，那么最简单的方法就是先给两个碗装好菜，然后观察，若A的菜多便将B的菜放一点到A内，若B的多则取A的一部分放入B，以此类推，知道A和B内的菜差不多一样多。EM算法就是这样，假设我们估计知道A和B两个参数，在开始状态下二者都是未知的，并且知道了A的信息就可以得到B的信息，反过来知道了B也就得到了A。可以考虑首先赋予A某种初值，以此得到B的估计值，然后从B的当前值出发，重新估计A的取值，这个过程一直持续到收敛为止。来源：EM算法百度百科）

若参数 $$\{(\alpha_i,μ_i,Σ_i)1 ≤ i ≤ k\}$ $能使式子（9.32）最大化，由 $$\frac{\delta LL(D)}{\delta μ_i}=0$ $得到

再由式子（9.30）以及$$$γ_{ji}=p_M(z_j=i

x_j)$$$，有

由该式得到各混合成分的均值可由样本加权平均来估计，样本权重是每个样本属于该成分的后验概率。类似地还有 $$\frac{\delta LL(D)}{\delta Σ_i}=0$ $可以得到

然后对于混合系数 $$\alpha_i$ $，除了要最大化 $$LL(D)$ $，还需要满足 $$\alpha_i ≥ 0,\sum^k_{i=1}\alpha_i=1$ $，由此可以用拉格朗日乘数法来解这种有约束条件的最优化问题

考虑 $$LL(D)$ $的拉格朗日形式

将其对 $$\alpha_i$ $求偏导并置零，得到

两边同时乘以 $$\alpha_i$ $再由$$$γ_{ji}=p_M(z_j=i

x_j)$$$与式子（9.30）可得到

$\alpha_i=-\frac{\sum_{j=1}^m\gamma_{ji}}{\lambda}$

对所有混合成分求和有 $$\lambda=-m$ $，因此有

即每个高斯成分的混合系数由样本属于该成分的平均后验概率决定。

这时候我们就可以根据上述推导来获得拟合高斯混合模型的EM算法，在每步迭代中先根据当前参数来计算每个样本属于每个高斯成分的后验概率 $$\gamma_{ji}$ $（E步），再根据上述三个参数表达式（9.34）（9.35）（9.32）更新模型参数$$${(\alpha_i,μ_i,Σ_i)

1 ≤ i ≤ k}$$$（M步）

如下图

第一行初始化也即先给三类参数任意赋值。然后EM算法会根据初始化后的参数逼近实际值。

ZyBlog