聚类分析(cluster analysis),也称为数据分割(data segmentation),有多种不同的目的。所有的目的都可以理解为是将一个集合中的对象汇聚或分割到不同的子集或“簇”(cluster)中,从而使每个簇中的那些对象彼此更接近、不同簇中的对象的差异更大。可以用一组度量(特征变量)来描述一个对象,或者也可以用这对象与其他对象之间的关系来描述。此外,有时我们的目的是让簇可以形成一个自然的层级结构。这就需要依次地再对簇本身进行分组,从而使得在每一个层级上同一组内的簇彼此更相似,而不同组之间簇的差异更大。
聚类分析也可用于构建一些描述性的统计量,来明确数据是否是由一些性质存在显著差别的不同子集组成的。为实现这个目标,我们就需要一个可以描述不同簇内的对象差异程度的评估指标。
不论聚类分析的目的是什么,其核心的概念是被聚类的对象个体之间的相似(或不相似)程度的度量。某个聚类方法对对象的分组是依赖于它所用到的相似性定义的。这个定义只能取决于具体问题。这在某种程度上与预测问题(监督学习)中损失函数或成本函数的函数选取有相似之处。一个不准确的预测所带来的成本定义并不是从数据样本中得出的(而是依赖具体的问题和其他领域的知识)。

图 14.4 展示了通过常用的 K 均值算法分成了三个组的模拟数据。在这个例子中,有两个簇并没有很好地被分开;因此“分割”比“聚类”是对这个算法中这部分过程的一个更准确的描述。K 均值聚类从对三个簇中心的猜测值开始,然后交替进行以下两个步骤,直到收敛:
- 为每个数据点,确定与之(按欧式距离)最接近的簇中心,并将其纳入到这个簇。
- 用簇中所有的点的坐标平均值来更新每一个簇的中心。
我们会在后面介绍更多关于 K 均值聚类的细节,包括如何选择簇的数量的问题(这个例子中是三个)。K 均值聚类是一个自上而下的过程,而我们将介绍的其他方法是自下而上的。所有聚类方法的基础是对两个对象之间的距离或差异性测量的选择。在介绍不同的聚类算法之前,我们先探讨下距离的测度。
14.3.1 相似矩阵
有时候数据是直接以对象彼此之间的相似性(proximity / alikeness / affinity)的形式表达的。这些数据可以是 相似性,也可以是 差异性。例如在社会科学的实验中,会请被试评估一个对象与另一个对象不同的确定程度。然后可以对这些评估的样本集做平均,计算出“差异性”。这种类型的数据可以表达为一个
大部分算法都假定输入的是一个 差异矩阵(dissimilarity matrix),其所有元素是非负的,对角元素为零
14.3.2 基于属性的差异度量
通常我们的数据是对变量(也称为 属性,attribute)
目前最常用的选择是平方距离:
不过也有其他可能的选择,不同的选择会产生可能不同的结果。而对非数量的属性(例如分类数据),平方距离可能不再适用。此外,有时会希望对属性给予不同的权重,而不是像在 14.20 中那样都是相同的权重。
这里先根据属性类型的不同介绍几个其他的距离定义:
-
数值变量(quantitative variable)
这类变量或属性的测量值是在连续的实数域上。自然地会将它们之间的“误差”定义为它们之间绝对差值的一个单调递增函数: 除了平方误差损失 之外,另一个常见的选择是单位函数(即绝对误差)。平方误差对大的差异比对小的差异的重视程度更高。另外在聚类算法中也可使用相关性: 其中 。需要注意这里是对变量(维度)的平均,而不是对观测样本的平均。若已将观测样本进行了标准化处理,那么: 因此,基于相关性(相似性度量)的聚类也就等价于基于平方距离(差异性度量)的聚类。 -
有序变量(ordinal variable)
这个类型的变量通常是连续的整数,而且它的取值是在一个有序集合中。例如,学习成绩(A、B、C、D、F),偏好程度(厌恶、反感、一般、喜欢、极好)。排序数据也是一个特殊的有序变量。有序变量的误差测度定义,一般会按照其原始取值的排序,用下式代替其 个原始取值: 然后在这个取值尺度上将它们按照数值变量的方式处理。 -
分类变量(catgorical variable)
对于无序的分类变量(unordered categorical,nominal),取值两两之间的差异度必须显式地直接定义出来。若变量有 个不同的可能取值,这些差异度可以表达为一个对称的 矩阵,满足 、 、 。最常用的选择是 ,不过也可以用不相等的损失值来区别对待不同的误差。
14.3.3 对象的差异性
接下来我们将
其中
必须要指出的是将每个变量的权重
其中第
因此,第
其中的数值变量就作为了坐标轴。这里的式 14.25 就变成了:
其中的
如果目的是发掘出数据中的天然组群,某些属性可能比其他属性携带了更多的分组趋势。应该给对群组分割更有价值的变量在定义对象相似性中分配更高的影响因子。而在这里给所有的属性分配相同的影响因子会将群组变得模糊不清,以至于聚类算法无法发现这些群组。[图 14.5] 展示了一个例子。
![**图 14.5**:模拟数据。左图中,在原始数据中使用 K 均值聚类($K=2$)。两个颜色标记了不同的簇。右图中,在聚类之前先将特征变量标准化。这等价于使用了特征权重 $1/[2\cdot\operatorname{var}(X_j)]$。标准化操作使两个完全分割的群组变得难以区分。需要注意两个图中的水平和垂直坐标使用了相同的单位(右图未对标准化进行还原)。](https://public.guansong.wang/eslii/ch14/eslii_fig_14_05.png)
虽然对个体属性差异性
最后一点,观测样本中通常在一个或多个属性上有缺失值。在式 14.24 的差异性计算中最常用的缺失值处理方法,是在计算样本
14.3.4 聚类算法
聚类分析的目的是将观测样本划分到若干个组(group)或簇(cluster)中,使得同一个簇中的两两差异性一般要小于不同簇中的差异性。聚类算法可分成三个不同的类型:组合算法、混合模型、和众数搜索。
组合算法(combinatorial algorithm) 不需要直接参照一个底层的概率模型,而直接对观测样本进行操作。混合模型(mixture modeling) 则假设数据来自一个概率密度函数所描述的某个总体样本的独立同分布(i.i.d.)抽样。这个密度函数是由许多成分密度函数混合而成的一个参数化的模型;每一个成分密度函数代表了一个簇。然后使用最大似然或相应的贝叶斯方法在数据上拟合这个模型。众数搜索(mode seeking),或“凸块搜索”(bump hunting),从非参数方法的角度试图直接估计出概率密度函数不同的众数。按最近的众数点划分的观测点就组成了相应的众数点处的簇。
第 6.8 节介绍了混合模型。第 9.3 节和第 14.2.5 节中的 PRIM 算法,是众数搜索或凸块搜索中的一种。接下来将介绍组合算法。
14.3.5 组合算法
最常见的聚类算法是直接将每个观测样本分配到一个组或簇中,而不需要考虑这个数据背后的概率模型。将每个观测点用整数
一个方法就是直接地指定一个量化的损失函数,然后通过某个组合最优化算法对其进行最小化。既然聚类的目标是将接近的点分配到同一个簇中,那么损失函数(或能量函数)自然的形式是:
这个准则函数描绘了同一个簇中的观测样本点彼此接近的程度。有时它被称作为“簇内分散度”(within cluster point scatter),因为分散度可分解为:
或者写为:
其中
当分配到不同簇中的观测样本点之间的距离较远时,这个分散度一般会比较大。因此可见:
对
组合最优化的聚类分析从原理上很简单。只需要在
例如,
这些可行的最优策略是基于重复的贪心下降(greedy descent)。首先指定一个初始化的分配规则。然后在每一次迭代步骤中,对簇的分配规则进行改动,使得准则函数的取值较之前有所提升。这个类型的聚类算法在每次迭代中修改簇分配规则的方法上有所区别。当在某次迭代中对分配规则的改动无法得到提升时,算法终止并将当前的分配规则作为它最终的解。由于在每一次迭代中的观测点和簇的分配规则是基于上一次迭代结果的微小变动,所以在所有可能的分配规则(式 14.30)中只有很小的一部分会被考虑到。然而,这些算法收敛到的局部最优可能与全局最优的差距很大。
14.3.6 K 均值
K 均值(K-means) 算法是最常用的迭代下降聚类方法之一。它适用于所有变量都是数值变量并且使用欧式距离的平方作为差异性度量的场景中。
请注意也可以通过重新定义
则式 14.28 的簇内分散度可写为:
其中的
这个最小化问题为:
上式可通过一个迭代下降算法求解。对任意的观测点集合
因此我们可以通过对一个扩大的最优化问题求解而得到
这可以用算法 14.1 中给出的交替最优化过程进行最小化。
算法 14.1 K 均值聚类
- 给定一个簇分配规则
,对总的簇内方差 14.44 进行最小化,则 的解为当前簇内的均值(见式 14.32)。 - 给定一组当前的均值
,式 14.33 的最小化解即为将每个观测样本点分配给距离(当前)簇均值最近的簇: - 迭代进行步骤 1 和步骤 2,直到分配规则不再改变。
步骤 1 和步骤 2 都会降低准则 14.33 的值,所以可保证过程的收敛。不过这个结果有可能是一个次优的局部最小化解。Hartigan and Wong (1979) 的算法更进一步地保证了最终结果中不存在可使目标函数继续降低的变更单个观测点所属簇的操作。此外,使用者可以随机生成多个初始化均值来启动算法,然后在其中选择目标函数值最小的一个解。
图 14.6 展示了在图 14.4 的数据上 K 均值的一些迭代结果。其中的圆圈代表着簇中心点。直线划分出了观测点的区域,每个区域代表着距离每个中心点最近的观测点。这个分割图被称作 沃罗诺伊图(Voronoi tessellation)1。在 20 次迭代后,计算过程达成了收敛。
 中模拟数据上 K 均值聚类算法的逐次迭代。](https://public.guansong.wang/eslii/ch14/eslii_fig_14_06.png)
14.3.7 高斯混合与 K 均值软聚类
K 均值聚类计算过程与估计某个特定高斯混合模型使用的 EM 算法有紧密的联系。(参考第 6.8 节和第 8.5.1 节)。EM 算法中的期望(E)步骤基于在每个混合成分分布下的相对密度为每个数据点分配“责任值”(responsibility),而后在最大化(M)步骤基于这些责任值重新计算成分密度函数的参数。假设我们指定了有

14.3.8 示例:人类肿瘤微阵列数据
我们在第一章中介绍过的人类肿瘤微阵列(microarray)数据上应用 K 均值聚类。这是一个高维空间聚类问题。
数据为一个 breast
(乳腺癌)、melanoma
(黑色素癌)、等等;在聚类中我们不会使用这些标签,而是在过后检查各个标签落入到哪个类别中。
我们对

Cluster | Breast | CNS | Colon | K562 | Leukemia | MCF7 |
---|---|---|---|---|---|---|
1 | 3 | 5 | 0 | 0 | 0 | 0 |
2 | 2 | 0 | 0 | 2 | 6 | 2 |
3 | 2 | 0 | 7 | 0 | 0 | 0 |
Cluster | Melanoma | NSCLC | Ovarian | Prostate | Renal | Unknown |
---|---|---|---|---|---|---|
1 | 1 | 7 | 6 | 2 | 9 | 1 |
2 | 7 | 2 | 0 | 0 | 0 | 0 |
3 | 0 | 0 | 0 | 0 | 0 | 0 |
表 14.2:人类肿瘤数据:K 均值聚类的三个簇中的每个类型癌症样本的个数。
可见聚类方法成功地将同一类癌症的样本归在同一组中。实际上第二个簇中的两个乳腺癌样本在之后被发现是误诊,是发生了转移的黑色素癌。不过在这个应用中 K 均值聚类也有不足之处。首先,它没有给出簇内对象的一个线性排序,我们只是简单地按字母顺序列举出来。其次,当改变簇的数量
14.3.9 向量量化
K 均值聚类算法在看似并不相关的图片和信号压缩领域也是一个关键的工具,特别是在向量量化(vector quantization,VQ)问题中(Gersho and Gray, 1992)。图 14.92 的左图为著名统计学家罗纳德·费希尔爵士(Sir Ronald Fisher)的一张数字化照片。其中包含了

这里的 VQ 版本首先将图片分解成很多小方块,在这个例子中是
为了描述近似后的图片,我们需要为每个块记录它的近似值在码书中位置。每个块需要
为什么 VQ 图片压缩可以奏效?其原因是对于一般的日常图片,比如照片,很多块是一样的。在这个例子中,有很多几乎为纯白色的块,而且类似地也有很多不同灰度的纯灰色块。这些信息只需要每种保留一个块,以及指向这种块的像素指针。
由于被近似的图片是原图的质量降级版本,上面介绍的也被称作有损(lossy)压缩。通常可以用均方误差(mean squared error)测量这个降级(degradation)或失真(distortion)。在这个例子中,
上文中说在码书中识别
14.3.10 K 中心点
如上所述,K 均值算法适用于以欧式距离平方
K 均值算法中仅在以下用到了欧式距离平方假设:最小化步骤的式 14.32;式 14.33 中的簇中心向量
算法 14.2 K 中心点聚类
- 给定一个簇分配规则
,找出每个簇中距离同簇中其他点的总距离最小的观测点: 则 为当前步骤的簇中心估计。 - 给定一组当前的簇中心
,将每个观测点分配至(当前步骤)距离它最近的簇中心,从而使总误差最小化: - 迭代进行步骤(1)和步骤(2),直到分配规则不再改变。
在每个临时的簇
所需要的计算量和之前一样与
用式 14.37 替换式 14.35 后(算法 14.2)就成为了求解下面这个最小化问题的一个特定的启发式搜索策略(heuristic search strategy)。
Kaufman and Rousseeuw (1990) 提出了另一个直接求解式 14.38 的策略:暂时地用一个非中心点的观测点替换每一个中心
例:国家差异性
BEL | BRA | CHI | CUB | EGY | FRA | IND | ISR | USA | USS | YUG | |
---|---|---|---|---|---|---|---|---|---|---|---|
BRA | 5.58 | ||||||||||
CHI | 7.00 | 6.50 | |||||||||
CUB | 7.08 | 7.00 | 3.83 | ||||||||
EGY | 4.83 | 5.08 | 8.17 | 5.83 | |||||||
FRA | 2.17 | 5.75 | 6.67 | 6.92 | 4.92 | ||||||
IND | 6.42 | 5.00 | 5.58 | 6.00 | 4.67 | 6.42 | |||||
ISR | 3.42 | 5.50 | 6.42 | 6.42 | 5.00 | 3.92 | 6.17 | ||||
USA | 2.50 | 4.92 | 6.25 | 7.33 | 4.50 | 2.25 | 6.33 | 2.75 | |||
USS | 6.08 | 6.67 | 4.25 | 2.67 | 6.00 | 6.17 | 6.17 | 6.92 | 6.17 | ||
YUG | 5.25 | 6.83 | 4.50 | 3.75 | 5.75 | 5.42 | 6.08 | 5.83 | 6.67 | 3.67 | |
ZAI | 4.75 | 3.00 | 6.08 | 6.67 | 5.00 | 5.58 | 4.83 | 6.17 | 5.67 | 6.50 | 6.92 |
表 14.3:一个政治学的调研数据:一些政治学的学生的调查问卷中国家之间两两差异性的得分平均值。
这个示例来自 Kaufman and Rousseeuw (1990),在一项研究中让一些政治学的学生给出 12 个国家的两两差异度:比利时(BEL)、巴西(BRA)、智利(CHI)、古巴(CUB)、埃及(EGY)、法国(FRA)、印度(IND)、以色列(ISR)、美国(USA)、苏联(USS)、南斯拉夫(YUG)、扎伊尔(ZAI)。表 14.3 列出了差异度评分的平均值。在这个差异矩阵上使用 3 中心点聚类。请注意在这里无法使用 K 均值,因为只有距离矩阵而没有原始的观测点。图 14.10 的左图展示了根据 3 中心点聚类进行分块并且重新排列的差异矩阵。右图为二维的多维尺度分析图,其中的颜色标记了三个中心点的聚类结果(关于多维尺度分析请阅读第 14.8 节)。两个图中都可看到三个簇的分隔清晰,但从多维尺度分析图中看“埃及”落在了两个簇中间的位置。

14.3.11 实践问题
应用 K 均值或 K 中心点聚类算法,需要选择簇的个数
簇个数
数据驱动的
这个方法底层的直觉思想如下。如果真实的数据模型中存在
那么可以理解在这个情况下,在
那么就可以通过找到
近期 (Tibshirani et al., 2001b) 提出了 间隙(Gap)统计量。在包含了样本数据的一个长方体中生成均匀分布的数据,然后得出一个
 的模拟数据上的 $\log W_K$ 观测样本取值(绿色)和期望取值(蓝色)。两个曲线都变换为了在一个簇时取值为零。(右图:)间隙曲线,即为 $\log W_K$ 在观测样本取值和期望取值之间的差。间隙统计量对 $K^\*$ 的估计是使间隙统计量在 $K+1$ 的间隙的一个标准差范围内的最小的 $K$ 值。这里的 $K^\*=2$。](https://public.guansong.wang/eslii/ch14/eslii_fig_14_11.png)
图 14.11 展示了在图 14.4 模拟数据上使用了间隙统计量的结果。左图为
这个结果是
14.3.12 层次聚类
K 均值或 K 中心点聚类算法的结果依赖于簇个数的选择和初始化的分配规则配置。与之相反,层次聚类(hierarchical clustering) 方法不需要这些配置。然而它需要指定一个基于两组观测点之间的两两差异性的两个(不相交)组之间的差异性度量。正如它的名称,这些方法可得出层次结构,其中每一级中的簇都是由下一级中的簇合并而来的。在最低一级,每个簇只包含一个观测样本。在最高一级,只有一个包含了所有数据的簇。
层次聚类的策略可分为两个基本的模式:自下而上的 凝聚(agglomerative),和自上而下的 分裂(divisive)。凝聚方法从最底部开始,递归地在每一级选择一对簇将其合并起来。这样在上一个级别中簇的个数就变少了一个。被选择合并的一对簇是所有簇中簇间差异性最小的两个。分裂方法从最顶部开始,递归地在每一级选择一个簇将其分成两个簇。分裂的选择是可以使得到的两个新簇之间的差异性最大。两种模式的层次结构中都会有
层次结构中的每一级都代表了将观测数据划分到不相交簇中的一个特定的数据分组。层次结构的整体就形成了一个这些数据分组的有序序列。至于哪一个级别能最好地表现一个“自然”聚类,也就是在哪个级别上每个组内部的观测点足够相似而不同组之间的观测点相差足够大,则需要使用者自行决定。之前介绍的间隙统计量也可在这里用到。
递归二元分裂/凝聚可以通过一个有根二叉树表现出来。树中的节点代表了分组。根节点代表了整个数据样本集合。
大部分的凝聚方法和一些分裂方法(从下向上观察)具有一个单调的性质。也就是说,被合并的两个簇之间的差异性随着合并级别的增加而单调递增。因此,在绘制二叉树时可以使每个节点的高度与其子节点之间的差异性取值成正比。只包含一个观测点的终节点在图中高度为零。这种类型的图形称之为 树状图(dendrogram)。
树状图以图像的形式提供了一个可解释性很高的对层次聚类的完整描述。这也是层次聚类方法非常流行的主要原因之一。

图 14.12 展示了微阵列数据上使用平均链接的凝聚聚类得到的树状图;本节稍后会更详细介绍关于凝聚聚类和这个示例的内容。若在一个特定的高度水平地将树状图截断,数据就会被分隔成与水平线相交的垂直线所代表的不相交簇。如果当最优组间差异性超过某个阈值点(树状图的高度)后就终止合并的过程,这些就是所得到的簇。
较高一级合并的(组间差异)值会高于该节点下面较低级别合并的值,前者是自然(真实)聚类的备选结果。可见这个过程可以发生在不同的级别上,也就形成了一个聚类的层次结构,即为簇嵌套着簇。
这样的树状图通常被看作是对数据本身的一个图像的概括,而不是对算法结果的一个描述。不过应该小心地看待这种理解方式。首先,不同的层次聚类方法(下文会详述),或者数据中的一些小变更,都可能会得出非常不同的树状图。其次,只有当观测点两两之间的差异性真的存在可被算法捕捉到的层次结构时,这样的概括图才有意义。其实无论数据中是否真的存在这样的层次结构,层次聚类方法都会得出层次结构。
树状图表现出的层次结构是否真的表达了数据本身的结构,可以通过 共表相关系数(cophenetic correlation coefficient) 来做判断。这个系数是输入给算法的
共表差异性是一个约束性很强的差异性度量。首先,观测样本上的
从几何上做个示例,假设数据为一个欧式坐标系统中的点。为了使数据点之间的距离能满足式 14.40,所有的三个点形成的三角形都必须是等腰三角形,而且三角形的底要小于它的腰(Jain and Dubes, 1988)。因此一般一个数据集的差异性度量,尤其是当其中没有太多重复值时,都不太可能与从树状图中得出相应的共表差异性比较相似。所以树状图应该被更多地看作是对应用某个特定的算法后所得出的层次聚类结构的一个描述。
凝聚聚类
凝聚聚类(agglomerative clustering)算法从每个观测点代表一个单元素簇开始。在
令
这也通常被称为 最近邻(nearest-neighbor) 方法。全链接(complete linkage,CL) 凝聚聚类,或 最远邻(furthest-neighbor) 方法,则取其中最远(差异性最大)的一个作为组间差异性:
组平均(group average,GA) 凝聚聚类则使用组中的平均差异性:
其中的

如果数据的差异性
单链接的定义 14.41 只需要两个组中的一个差异性
那么单链接可能会得出直径非常大的簇。
全链接的定义 14.42 则是另一个极端。只有当两个组的并集中所有的观测点都比较相似时,两个组
组平均 14.43 则是单链接和全链接两个极端的折中。它试图让得出的簇既是相对紧致的同时又相对彼此远离。不过它的结果依赖于观测点之间差异性
有观点认为组平均聚类具有统计学上一致性的性质,而单链接和全链接则不具备。假设数据的属性变量为
其中的
例:人类肿瘤微阵列数据(续)
图 14.13 中左图展示了微阵列样本数据上使用了平均链接的凝聚聚类的树状图结果。中图和右图分别为使用了全链接和单链接。平均链接和全链接给出了相似的结果,而单链接得到了不平衡的组、细长的簇。以下讨论聚焦在平均链接聚类上。
和 K 均值聚类一样,层次聚类成功将简单的癌症类型聚类在一起。但它还有其他一些不错的特性。首先,通过在不同高度截断树状图可以得出不同数量的簇,并且这些簇存在嵌套关系。其次,它可以给出关于样本的一些部分排序信息。在图 14.14 中,我们按层次聚类中得出的顺序排列了基因(行)和样本(列)的表达矩阵。

注意若在每次合并时调整树状图中分支的定位,得到的树状图依然与层次聚类的计算过程是一致的。所以为了确定叶节点的排序,必须(在合并时)要添加一个约束。为生成图 14.14 的行排序,我们使用了 S-PLUS 中的默认规则:在每次合并时,更紧凑的簇被排放在左侧(图中旋转后的树状图则为下侧)。所有单个基因的簇是最紧凑的簇,在对两个单个基因簇合并时,按它们的观测点序号排序。在列的排序中也使用了一样的规则。也有其他可能的规则,例如根据基因的多维尺度排序,可参考第 14.8 节。
图 14.14 中双向的重排列得出了一个信息丰富的基因和样本图片。这个图比第一章图 1.3 中的行与列随机排列提供了更多信息。此外,树状图本身也有使用价值,例如生物学家可以从生物过程的角度解释基因聚类。
分裂聚类
分裂聚类(divisive clustering)算法从所有数据集作为一个单独的簇开始,自上而下地在每次迭代中将一个已有的簇分割成两个子簇。这个方法在聚类研究领域中的研究远没有凝聚方法深入和广泛。而它在工程领域中的压缩应用场景上有一些探索(Gersho and Gray, 1992)。在聚类问题中,当目标是聚焦于将数据分割成相对少的簇时,分裂方法比凝聚方法可能存在潜在的优势。
分裂方法可以通过迭代地应用任意一种组合方法来进行分割,例如令
Macnaughton Smith et al. (1965) 提出了一个可以避免这些问题的分裂算法。它首先将所有的观测点放在一个簇
重复这个迭代分割操作,直到所有的簇或者成为单元素簇,或者每个簇内的所有元素彼此间差异性都为零。
本节练习
练习 14.1
Weights for clustering
Show that weighted Euclidean distance
satisfies
where
Thus weighted Euclidean distance based on x is equivalent to unweighted Euclidean distance based on z.
练习 14.2
Consider a mixture model density in p-dimensional feature space,
where
Suppose we have data
- Write down the log-likelihood of the data
- Derive an EM algorithm for computing the maximum likelihood estimates (see Section 8.1).
- Show that if σ has a known value in the mixture model and we take
, then in a sense this EM algorithm coincides with K-means clustering.