

6 聚类分析

“为了成为一群羊的完美成员，首先必须自己成为一只羊。“ -Albert Einstein

6.1 介绍

许多应用程序都要求将数据点分成直观相似的组。将大量数据点划分为更少数量的组会对总结数据有所帮助并且帮助理解它的各种数据挖掘应用。聚类的非正式和直观的定义如下：

给定一组数据点，将他们分成含有相似的数据点的组。

这是一个非常粗略并直观的定义，因为它没有提到很多制定问题不同方式，例如组的数量，客观的相似性标准。尽管如此，这个简单的描述可以作为许多模型的基础，专门针对不同的应用而定制。 一些这类应用的例子如下：

• *数据汇总：*在最广泛的层面上，可以将聚类问题考虑为数据汇总的一种形式。由于数据挖掘是关于从数据中提取总结信息（或精练信息），聚类过程在许多数据挖掘算法中往往是第一步。实际上，许多应用程序都使用聚类分析的汇总特性，以不同的形式进行。
• 客户分类：*通常需要分析类似客户的群体的共同行为。 这就是*客户分类。一个客户分类应用的例子是协同过滤，其中使用类似顾客群体的陈述或派生偏好在群组内进行产品推荐。
• 社交网络分析：*就网络数据而言，通过链接关系紧密聚集的节点往往是类似的*群体。群体检测问题是社会网络分析上最广泛研究的问题之一，因为从社区群体动态分析中可以获得人类行为的更广泛的理解。
• *与其他数据挖掘问题的关系：*由于它提供的汇总表示，聚类问题对于研究其他数据挖掘问题很有用。例如，聚类通常被用作许多分类和异常值检测模型中的预处理步骤。

对于聚类分析已经开发了多种模型。 这些不同的模型在不同的场景和数据类型中可能会更好。 许多聚类算法遇到的问题是许多特征可能对聚类分析而言是噪声或不具有分析意义。 这些特征需要在聚类过程早期分析中删除。这个问题被称为*特征提取*。 本章也将研究聚类特征提取算法。

在本章和下一章中，聚类研究将局限于更简单的多维数据类型，如数字或离散数据。更复杂的数据类型，例如时间或网络数据，将在后面的章节中进行研究。 这些模型主要的不同点在于数据组内如何定义相似性。在某些情况下，相似性是用适当的距离度量进行明确定义，而在其他情况下，它被使用概率混合模型或基于密度的模型隐式定义。另外，一定聚类分析的场景，如高维或超大规模数据集，姿态特殊挑战。 这些问题将在下一章讨论。

本章安排如下：6.2节中研究特征提取问题。 在6.3节中讨论基于代表算法。在6.4节中讨论分层聚类算法。 在6.5节中讨论基于概率和基于模型的数据聚类方法。在6.6节中介绍基于密度的聚类方法。在6.7节讨论基于图的聚类技术。 6.8节介绍了非负矩阵分解的数据聚类方法。在6.9章节中讨论聚类有效性的问题。 最后，6.10章节是总结。

6.2 聚类的特征提取

特征提取的关键目标是去除影响聚类的噪声。对于无监督的问题，特征提取通常更加困难，例如聚类，外部验证条件（如标签）不适用于特征提取。直观地说，特征提取的问题与确定的一组特征的固有聚类趋势问题密切相关。 特征提取方法确定使潜在聚类趋势最大化的特征子集。 以下有两个主要的用于执行特征提取的模型类别：

1. *过滤模型：*在这种情况下，每个特征都使用基于相似度的标准与分数相关联。 这个标准本质上是一个提供特征去除条件的过滤器，删除不符合要求的分数的数据点。 在某些情况下，这些模型可能会将特征子集的质量量化为组合，而不是单个特征。 这样的模型更强大，因为它们隐含地考虑到了添加一个特征对与其他的增量影响。
2. *包装模型：*在这种情况下，使用聚类算法来评估特征子集的质量。 然后在执行聚类时用它来提炼其中的特征子集。这是一个迭代的方法，好的特征选择取决于聚类，反之亦然。所选功能将会通常至少在某种程度上取决于所使用的特定聚类方法。尽管这可能看起来像是一个缺点，但事实却不同，聚类方法可能对不同的特征集有不同的效果。 所以，这个方法也可以将特征提取优化为特定的聚类技术。另一方面，具体特征的内在信息可能有时候由于特定聚类的影响而不能被这种方法所反映。

过滤和包装模型之间的主要区别是前者纯粹是一个预处理阶段，而后者直接集成到聚类中处理。 在下面的章节中，将会有大量的过滤和包装模型讨论。

6.2.1 过滤模型

在过滤模型中，使用特定标准评估特定特征或特定特征子集对数据集的聚类趋势的影响。 以下将介绍许多常用的标准。

6.2.1.1 术语强度

术语强度适用于诸如文本数据之类的稀疏域。 在这样的领域，它在讨论非零值属性（单词）上存在或不存在，而不是距离上更有意义。而且，使用相似性函数比距离函数更有意义。 在这种方法中，对文档进行采样，但是在一对之间施加了随机顺序。术语强度被定义为相似文件对的分数（相似度大于$β$），其中该术语出现在两者中文件，条件是它出现在第一个文件中。 换句话说，任何一个术语$t$，文件对$(\overline{X},\overline{Y})$被认为非常相似的强度定义如下：

$$\begin{align}术语强度=P(t\in\overline{Y}|t\in\overline{X})\end{align}\tag{6.1}$$

如果需要，术语强度也可以通过离散量化属性转换为二进制值来推广到多维数据。 其他类似的措施使用总体距离和属性距离与模型相关性之间的相关性。

6.2.1.2 预测属性依赖

这种测量的直观动机是相关特征总会比不相关的特征的结果更好。 当属性相关时，其他属性可以用来预测这个属性的值。分类（或回归建模）算法可以用来评估这种预测性。 如果属性是数字，那么可以使用回归建模算法。否则，使用分类算法。属性$i$的量化相关性的总方法如下：

图6.1 聚类数据对距离分布熵的影响

1. 对于除属性$i$之外的所有的属性使用分类算法来预测属性$i$的值，把它作为一个人造类变量。
2. 将分类准确性反映为属性$i$的相关性。

可以使用任何合理的分类算法，因为它的相似性计算和聚类有着天然的联系，所以最近邻分类器很适合采用。分类算法在第10章中进行讨论。

6.2.3.1 熵

这些方法背后的基本思想是在基础距离分布上高度聚集的数据反映了其中的一些聚类特征。 为了说明这一点，图6.1a和b分别显示了两种不同的数据分布。首先第一张描绘了均匀分布的数据，而第二张描绘了两个聚类的数据。在图6.1c和d中，说明了两种成对的点对点距离分布情况。很明显，统一数据的距离分布是以钟形曲线的形式呈现，而聚类数据的排列则有两个不同的峰值分别对应于聚类间分布和聚类内分布。这种峰值的数量通常会随着簇的数量增加而增加。基于熵的方法的目标是量化这个距离分布在特征子集上的“形状”，然后选择与图6.1b的情况更类似行为分布的子集。因此，除了量化基于距离的熵之外，还需有一种系统的方法来搜索适当的特征组合。那么如何量化在属性的特定子集上基于距离的熵呢？

量化熵的一种自然方法是在数据点上直接使用概率分布并使用这些值量化熵。考虑一个$k$维特征子集。第一步是将数据离散化为一组多维网格区域，每个维度使用$\phi$个网格区域。这导致$m=\phi^k$个网格区域，其中索引从1到$m$。$m$的值在所有的值中大致相同，通过选择$\phi=\left \lceil m^\frac{1}{k}\right \rceil$来评估特征子集。 如果$p_i$是网格区域$i$中数据点的分数，则基于概率的熵$E$定义如下：

$<span><span class="MathJax_Preview">\begin{align}E=-\sum_{i=1}^m [p_ilog(p_i)+(1-p_i)log(1-p_i)]\end{align}\tag{6.2}</span><script type="math/tex">\begin{align}E=-\sum_{i=1}^m [p_ilog(p_i)+(1-p_i)log(1-p_i)]\end{align}\tag{6.2}$ $$ \begin{align}E=-\sum_{i=1}^m [p_ilog(p_i)+(1-p_i)log(1-p_i)]\end{align}\tag{6.2} $$ 具有较差聚类行为的均匀分布具有较高的熵，而聚类数据具有较低的熵。 因此，熵度量提供关于聚类特征子集的质量的反馈。

上述量化可以直接使用，但网格区域$i$的概率密度$p_i$有时难以从高维数据准确估计。这个是因为网格区域是多维的，并且它们在高维度越来越稀疏。在变换的维数$k$的特征子集上固定网格区域$m$的数量也很困难，因为$\phi=\left\lceil m^{1/k}\right\rceil$ 的值被四舍五入为整数值。因此，另一种方法是计算数据样本的一维点到点的距离分布的熵。 这与如图6.1所示的分布相同。$p_i$的值代表第$i$个1维离散化的范围的距离分数。 虽然这种方法并没有完全解决高维度的挑战，但是对于适度维度的数据通常是更好的选择。例如，如果熵是在图6.1 $c$和$d$中的直方图上计算的，那么这将会区分两种分布。另一种基于原始距离的启发式逼近法也经常使用。请参阅书目注释。

为了确定熵$E​$最小化的特征子集，尝试了各种各样的搜索策略。例如，从全部特征基开始，使用一种简单的贪婪方法来放弃导致熵最大降低的特征。特征数地反复下降，直到增量减少不显著，或熵增加。 对于这些方法在量化措施或是搜索策略上的改进，将在在书目部分讨论。

6.2.1.4 霍普金斯统计

霍普金斯统计量通常用于衡量数据集的聚类趋势，但它也可以应用于特定属性的子集。 由此产生的措施可以与特征搜索算法一起使用，例如在前一小节讨论的贪婪法。

设$\mathcal{D}$是需要评估聚类趋势的数据集。$r$的样本$S$合成数据点是在数据空间的域中随机生成的。同时，$r$个数据点的样本$R$是从$\mathcal{D}$中选择的。设$\alpha_1\ldots\alpha_r$是在距离样本$R⊆D$中的数据点到原始数据库内$\mathcal{D}$的中最近邻居的距离。同样，让$\beta_1\ldots\beta_r$是合成样本$S$中的数据点到$\mathcal{D}$中最近邻居的距离。然后，霍普金斯统计量$H$定义如下：

$$\begin{align}H=\frac{\sum_{i=1}^r\beta_i} {\sum_{i=1}^r(\alpha_i+\beta_i)}\end{align}\tag{6.3}$$

霍普金斯统计量将在$(0,1)$的范围内。 均匀分布的数据霍普金斯统计值为0.5，因为$\alpha_i$和$\beta_i$的值是相似的。另一方面，对于聚类数据，$\alpha_i$的值通常会比$\beta_i$低的多，这会导致其中霍普金斯统计值接近1。因此，一个很高的霍普金斯值统计量$H$表示高度聚集的数据点。

一种意见是该方法使用随机抽样，因此使用该度量将随不同的随机样本而变化。 如果需要，可以在多个试验中重复随机采样。可以使用统计尾部准确性测试来确定霍普金斯统计量大于0.5的准确度水平。 对于特征选择，可以使用多次试验统计的平均值。这个统计可以是用于评估任何特定子属性的质量以评估聚类该子集的趋势。这个标准可以与贪婪法结合使用来发现相关的特征子集。 贪婪法与讨论的在基于距离的熵方法的情况下类似。

6.2.2 包装模型

包装模型使用内部聚类有效性标准和应用于适当的特征子集的聚类算法。聚类有效性标准是用于评估聚类的质量，并在6.9节中详细讨论。 这个方法是使用具有特征子集的聚类算法，然后用一个聚类有效性标准评估这个聚类的质量。因此，不同特征的子集搜索空间需要探索以确定特征的最佳组合。由于特征子集的搜索空间与维数呈指数关系，可以使用贪婪算法来连续丢弃导致聚类有效性标准最大改进的特征。这种方法的主要缺点是，它对有效性标准的选择很敏感。 正如你将在本章中学到的那样，集群有效性标准还很不完善。 此外，该方法计算复杂。

另一种更简单的方法是在分类算法中使用的，使用特征选择标准来选择单个特征。 在这种情况下，特征被单独评估，而不是统一评估为一个子集。聚类方法人为地创建一组标签$L$，对应于单独的聚类标识符数据点。特征选择标准可以从分类文献中借鉴使用$L$中的标签。这个标准被用来识别最具分歧性的特征：

1. 使用选定特征F的当前子集上的聚类算法来修复数据点的聚类标签$L$。
2. 使用任何监督标准来量化各个特征的质量，服从标签$L$。并根据此量化选择前$k$个特征。

上述框架具有相当大的灵活性，其中不同类型的聚类算法和特征选择标准被用在前述的每一个步中。可以使用各种监督标准，如*基于类别的熵*或$Fisher$评分（参见第10章第10.2节）。$Fisher$分数，在第10章的10.2.1.3节中，迭代地测量任意特定属性的类间变化与类内变化的比率。此外，也可以修改一下第一步对上述迭代。不选择前$k$个特征，前$k$个特征的权重设置为1，其余的部分设置为$α<1$。这里，$α$是用户指定的参数。 在最后一步中，选择前$k$个特征。

算法 $ GenericRepresentative$（数据库：$\mathcal{D}$,代表数：$k$）

开始

**

​ 初始化代表基$S$; 重复

​ 通过使用距离函数$Dist(\cdot ,\cdot)$给$\mathcal{D}$中每个点分配$S$中离其最近的代表创建聚类$(\mathcal{C_1\ldots C_k})$； 对每个使函数$\sum_{\overline{X_i}\in\mathcal{C_j}}Dist(\overline{X_i},\overline{Y_j})$最小的Cj决定一个代表$\overline{Y_j}$重新创建$S$; 直到 收敛；

​ 返回 （$(\mathcal{C_1\ldots C_k})$）；

结束

​

图6.2：具有未指定距离函数的通用代表性算法

包装模型通常与过滤器模型组合以创建更好的混合模型效率。在这种情况下，使用滤波器模型构建候选特征子集。然后，用聚类算法评估每个候选特征子集的质量。评估可以使用聚类有效性标准或使用一个结果聚类标签的分类算法来选择最佳候选特征子集。混合模型比过滤器模型提供更好的准确性，并且比包装模型效率更高。

6.3 基于代表的算法

基于代表的算法是所有聚类算法中最简单的算法，因为它们直接依靠直观的距离（或相似性）概念来聚类数据点。在基于代表的算法，这些簇是一次性创建的，并且于不同的簇中不存在层次关系。这通常是使用一组分区代表来完成的。 分区代表可以根据簇中的数据点的函数（例如均值）来创建或者可以从簇中现有的数据点中选择。这些方法的主要想法是发现数据中高质量的簇，相当于发现一组高质量的代表。代表确定后，可以使用距离函数将数据点分配给他们最近的代表。

通常，假设k表示用户的聚类数量，考虑在$d$维空间中数据集$\mathcal{D}$包含由$\overline{X_1}\ldots\overline{X_n}$表示的$n$个数据点。 目标是确定$k$个代表$\overline{Y_1}\ldots\overline{Y_k}$最小化以下目标函数$O$：

$$\begin{align}O=\sum_{i=1}^n[\operatorname{min}_jDist(\overline{X_i},\overline{Y_i})]\end{align}\tag{6.4}$$

换句话说，不同数据点到他们最近的代表的距离的总和需要最小化。请注意，将数据点分配给代表取决于代表$\overline{Y_1}\ldots\overline{Y_k}$的选择。 在一些代表算法的变化中，例如k-medoid算法，假设代表$\overline{Y_1}\ldots\overline{Y_k}$是来自原始数据库$\mathcal{D}$，但这并不会提供最佳的解。一般来说，本节中的讨论不会自动假定代表从原始数据库D中抽取，除非另有规定。

关于方程式6.4的一个观点是代表$\overline{Y_1}\ldots\overline{Y_k}$和数据点的最优分配事先是未知的，但是他们以循环方式相互依赖。例如，如果最佳代表是已知的，那么最佳分配很容易确定，反之亦然。 这样的优化用候选代表的迭代方法解决问题而候选的分配则用来相互改进。因此，通用 k-representatives方法首先使用初始化 k-representatives直接的启发式的$S$（如从原始数据中随机抽样），然后细化代表和聚类分配，迭代如下：

• （分配步骤）使用函数$Dist（·,·）$距离将每个数据点分配给$S$中最近的代表，并用$\mathcal{C_1}\ldots\mathcal{C_k}$表示相应的簇。
• （优化步骤）确定每个聚类$\mathcal{C_j}$的最佳代表$\overline{Y_j}$，使其类内目标函数$\sum_{\overline{X_i}\in\mathcal{C_j}}[Dist(\overline{X_i},\overline{Y_j})]$最小化。

本章后面会明显看出，这两步骤过程与到期望最大化算法的聚类分析的生成模型的密切相关。局部优化的第二步通过这种两步迭代方法进行简化，因为在方程6.4中的全局优化问题中，它不再依赖未知的数据点分配到集群。 通常，优化的代表可以证明是第$j$个聚类$\mathcal{C_j}$中数据点的一些中心度量，精确的测量取决于距离函数$Dist(\overline{X_i},\overline{Y_j})$的选择。尤其是，对于欧几里德距离和余弦相似函数的情况，可以看出每个集群的最佳集中代表是其均值。但是，不同距离函数可能会导致稍微不同的集中代表类型，并且这导致了这种更广泛的方法的不同变化，例如k-means和k-medians算法。因此， k-representatives方法定义了一系列算法，基本框架的细微变化允许使用不同的距离标准。下面将讨论这些不同的标准。 基于具有未指定距离函数的代表通用框架算法在图6.2示出。这个想法是改善多次迭代的目标函数。通常情况下，在早期的迭代中增加是显著的，但在后面的迭代中会减慢。 当迭代中目标函数的提高小于用户定义的阈值时算法终止。该方法主要计算的瓶颈是需要在所有点代表对之间计算距离的分配步骤。 对于一个大小$n$和维度$d$的迭代，每次迭代的时间复杂度为$O(k·n·d)$。 该算法通常以小的迭代常数结束。

图6.3 具有随机初始化的 k-representatives算法的图示

在图6.3中举例说明 k-representatives算法的内部运作，数据包含三个簇，用$A，B$和$C$表示，假定数据中的算法的输入$k$与聚类数目相同，本例中为3。使用欧几里得距离函数，因此“重新选取代表点”步骤使用该簇的平均值。最初的从数据空间随机选择一组代表（或种子），这可能是一个不好的初始化，其中两个代表接近簇$B$，并且其中一个位于集群$A$和$C$之间的某处。结果，簇$B$最初是由两位代表的“影响范围”分裂开来的，而在集群$A$和$C$中的大多数点在第一个分配步骤中分配给单个代表。这种情况如图6.3a所示。但是，因为每个代表都被分配了来自不同簇的不同数量的数据点，代表漂移进来随后迭代到其中一个独特的簇。例如，代表1稳定地向$A$簇漂移，代表3稳定地向$C$簇漂移。同样时间，代表2成为集群$B$的更好的集中代表。因此，在10次迭代结束时，簇$B$不再在不同的代表之间分裂（图6.3f）。一个有趣的观察是，即使初始化非常差，它只需要10次迭代就可以创建合理的数据的$k$代表方法的聚类。在实践中，这对于 k-representatives的方法来说通常是正确的，对数据点的良好聚类相对较快地收敛。 但是，这是可能的使$k$-均值收敛到次优解，特别是当异常数据点选作该算法的初始代表。在这种情况下，簇中的一个可以包含一个不代表数据集的单例点，或者可能包含两个点合并的簇。 有关实施情况的处理的问题将在下章讨论的。在下面的章节中，将会介绍这个框架的一些特殊情况和变体讨论。$k$代表框架的大多数变体都由在数据点$\overline{X_i}$和代表$\overline{Y_j}$之间的距离函数$Dist(\overline{X_i},\overline{Y_j})$选择， 这些选择中的每一个都会产生不同类型的集群代表。

6.3.1 k-均值算法

在k均值算法中，数据点到他们最近的代表的欧几里德距离的平方和被用来量化聚类的目标函数。因此，我们有： $$ Dist(\overline{X_i},\overline{Y_j})=\lVert\overline{X_i}-\overline{Y_j}\rVert_2^2.\tag{6.5} $$ 在这里,$\lVert\bullet\rVert_p$表示$L_p$范数。 表达式$Dist(\overline{X_i},\overline{Y_j})$可以被看作是最接近的代表数据点的近似平方误差。因此，整体客观最小化不同数据点上的平方误差之和。 这有时也被称为$SSE$。在这种情况下，1可以表明每个“优化”迭代步骤最佳代表$\overline{Y_j}$是群集$\mathcal{C_j}$中数据点的平均值。 因此，图6.2的通用伪代码和k-means之间的唯一区别就是伪代码是距离函数$Dist（·,·）$的具体实例，以及该代表作为其集群的本地均值。

k-means算法的一个有趣变体是使用当地的$Mahalanobis$距离将数据点分配给簇。 这个距离函数在第三章的3.2.1.6节中讨论。 每个聚类$\mathcal{C_j}$都有它自己的$d×d$的协方差矩阵$Σ_j$，可以用它来计算在前一次迭代中分配给该群集的数据点。平方马哈拉诺比斯距离即数据点$\overline{X_i}$与代表$\overline{Y_j}$之间的协方差矩阵$Σ_j$定义为： $$ Dist(\overline{X_i},\overline{Y_j})=(\overline{X_i}-\overline{Y_j})\begin{matrix} \sum_{j}^{{-1}\end{matrix}(\overline{X_i}-\overline{Y_j})}T\tag{6.6} $$ 当椭圆形的类沿着某个确定方向延伸时，使用$Mahalanobis$距离通常是有用的如图6.3所示。 因子$\begin{matrix}\sum_{j}^{-1}\end{matrix}$也提供局部密度归一化，这对于具有不同局部密度的数据集是有帮助的。所得到的算法被称为Mahalanobis k-means算法。当群集具有任意形状时，$k$均值算法效果不佳。 一个例子如图6.4a所示，其中$A$群具有非凸形状。k-means算法将其分解为两部分，并将这些部分中的一个与集群$B$合并。这样的情况在k-means中很常见，因为它偏向于找到球形聚类。即使是Mahalanobis k-means算法在这种情况下在其调节团簇伸长的能力也不能很好地工作。另一方面，Mahalanobis k-means算法可以很好地适应不同的簇密度，如图6.4b所示。 这个是因为$Mahalanobis$方法通过使用群特异性来标准化局部距离协方差矩阵。图6.4b的数据集基于许多密度的算法不能被有效聚类，其旨在发现任意形状的群集（参见6.6节）。 因此，不同的算法适用于不同的应用程序设置。

6.3.2 核K-均值算法

$k$-均值算法可以使用称为内核技巧的方法扩展到发现任意形状的簇。 基本的想法是隐式地转换数据，以便任意形状的簇映射到新空间中的欧几里德簇。 参考到第10章的10.6.4.1节 简要描述核$k-$均值算法。该核$k-$均值算法的主要问题是计算单独的内核矩阵与数据点的数量呈二次关系的复杂度。 这种方法可以有效地发现图6.4a中的任意形状的簇。

算法 通用的中心点算法（数据库：$\mathcal{D}$，代表数：$k$）

开始

​ 初始化从$\mathcal{D}$中选择的代表基$S$;

​ 重复

​ 使用距离函数$Dist(\cdot ,\cdot)$给$\mathcal{D}$中的每个点分配$S$中最近的代表创建聚类（$(\mathcal{C_1\ldots C_k})$）； 决定一对$\overline{X_i}\in\mathcal{D}$和$\overline{Y_j}\in S$来替代最可能提高目标函数的$\overline{Y_j}\in S$和$\overline{X_i}$； 仅在正向提高的情况执行的$\overline{X_i}$和$\overline{Y}$交换； 更新$M$中的新的行列的全部元素； 直到 当前迭代没有提高；

​ 返回 （$(\mathcal{C_1\ldots C_k})$）；

结束

​

图6.5：具有不具体的爬山策略的通用k-medoids算法

6.3.3 k-Medians算法

在$k$-中值算法中，曼哈顿距离被用作目标函数选择。 因此，距离函数$Dist(\overline{X_i},\overline{Y_j})$定义如下 $$ Dist(\overline{X_i},\overline{Y_j})=\lVert\overline{X_i}-\overline{Y_j}\rVert_1.\tag{6.7} $$ 在这种情况下，可以表明最佳代表$\overline{Y_j}$是沿着集群$\mathcal{C_j}$中的每个维度的数据点的中值。 这是因为一条线上分布的一组点的$L_1$距离的最小总和是其中值。 这个结果的证明很简单。中位数的定义可以用来表明这一点，从中位数的任一方向不能严格减少$L_1$距离的和。 这意味着在数据点集合中中位数优化了$L_1$距离的总和。

由于中间值是沿每个维度独立选择的，因此得到的$d$维代表将（通常）不属于原始数据集$\mathcal{D}$。k-medoids方法有时会与从原始数据库$\mathcal{D}$中选择这些代表的k-medoids方法混淆。在这种情况下，通用伪代码之间的唯一区别如图6.2所示，而k-medians方法则是实例化的曼哈顿距离的距离函数，并使用该代表作为该集群的本地中位数（独立地沿每个维度）。k-medians方法选择聚类代表的方式通常比k-means更强大，因为中位数并不像以群集中异常值的存在的平均值那么敏感。

6.3.4 k-Medoids算法

虽然k-medoids算法也使用代表的概念，它的算法结构不同于图6.2的k-representatives算法。 但聚类目标函数与 k-representatives算法具有相同的形式。k-medoids算法的显着特点是代表总是从数据库$\mathcal{D}$中选择，并且这种差别需要改变k代表算法的基本结构。

一个问题是，为什么有时需要从$\mathcal{D}$中选择代表，这有两个原因， 其中一个原因是$k$均值聚类的代表可能会被该集群中的异常值所破坏。在这种情况下，代表是可能的位于该群集大部分数据点不具有代表性的空白区域。这些代表可能会导致不同集群的部分合并，显然是不可取的。 然而，这个问题可以通过小心异常部分解决处理和使用异常值强健的变量，如k-medians算法。第二个原因是计算一组复杂数据类型的数据点的最优中央代表有时很困难。 例如，如果$k$代表聚类算法被应用在一组不同长度的时间序列上，那么应该怎么为这些异构时间序列的功能定义中央代表？在这样的案例中，从原始数据集中选择代表可能会非常有帮助。 只要从每个集群中选择一个代表性对象，该方法将提供合理的高质量的结果。因此，k-medoids算法的一个关键属性是它可以在任何数据类型上虚拟定义，只要有适当的相似性或距离函数即可在数据类型上定义。 因此，k-medoids方法直接关联到到聚类的距离函数设计的问题。

k-medoids方法使用通用的爬山策略，其中的代表集合$S$被初始化为来自原始数据库$\mathcal{D}$的一组点。随后，该集合$S$通过从数据库$\mathcal{D}$中交换集合$S$中的单个点与所选数据点来迭代改进。这种迭代交换可以被看作是一种爬山策略，因为集合$S$隐含地定义了聚类问题的解决方案以及每个交换可以被看作是爬山的一步。 那么交易的标准是什么？何时应该终止？

显然，为了使聚类算法成功，爬山方法至少应该在一定程度上改善问题的目标函数。 几个选择就交易如何进行而言可以这样执行：

1. 可以尝试所有$| S | ·| \mathcal{D} |$ 用$\mathcal{D}$中数据点替换S中的代表的可能性指向，然后选择最好的一个。 但是，这计算非常昂贵，因为每个$| S | ·| \mathcal{D} |$替代品的增量目标函数变化的计算将需要与原始数据库大小成比例的时间。
2. 更简单的解决方案是对于可能的交换使用一组随机选择的$r$对$(\overline{X_i},\overline{Y_j})$，其中从数据库$\mathcal{D}$中选择$\overline{X_i}$，并且从集合$S$中选择$\overline{Y_j}$代表性。这些$r$对中最好的用于交换。

第二个解决方案需要的时间与数据库大小的成$r$倍正比，但通常是这样对于规模适中的数据库实际上可以实施。当目标函数没有改进时，或者如果在之前的迭代中，平均目标函数改进低于用户指定的阈值，那么解决方案就会收敛。k-medoids方法通常比k-means方法慢得多，但在不同的数据类型具有更大的适用性。下一章将介绍$CLARANS$算法，它是k-medoids框架的扩展版本。

实际和实施问题

在所有以代表为基础的算法实施方面出现了一些实际问题，例如k-means,k-medians和k-medoids算法。这些问题涉及初始化标准，群集数目$k$的选择和存在异常值的情况。

最简单的初始化条件是要么从数据空间选择随机地点，或者对原始数据库$\mathcal{D}$进行采样。对原始数据库$\mathcal{D}$进行采样通常优于数据空间采样，因为它会导致更好的统计基础数据的代表。 k-representatives算法对初始化的选择具有鲁棒性，尽管算法有可能创建次优群集。一种可能的解决方案是从$\mathcal{D}$中采样更多的超过所需的数量$k$的数据点，并使用更昂贵的分层聚类方法来创建$k$个稳健的中心。 因为这些中心在数据库$\mathcal{D}$中更具代表性的，这为算法提供了一个更好的初始点。

一个非常简单的方法，似乎工作起来非常好，是选择最初的代表作为$m$个随机选择的用户选择参数$m$的点样本的的中心。这将确保最初的中心不会因为任何特别偏差离群。 此外，虽然所有这些中心代表将大致相等到数据的平均值，它们通常会稍微偏向一个或另一个群集，因为不同样本间的随机变化。k-means的后续迭代将会将这些代表中的每一个与一个聚类联系起来。

异常值的存在通常会对这些算法产生不利影响。在初始化过程选择异常值作为初始中心其中之一的情况下，可能会发生这种情况。尽管在迭代交换期间k-medoids算法通常会丢弃异常值代表，但k-medoids方法可能会陷入单群集或后续迭代中的空群集的问题中。在这种情况下，一种解决方案是添加一个该算法迭代部分中的额外步骤，即丢弃小群集中心，并用数据中随机选择的点替换它们。

聚类数$k$是该方法使用的参数。 第6.9.1.1节集群上的有效性提供了用于选择聚类数$k$的近似方法。 如在 6.9.1.1节所述这种方法不是很完美。自然群集的数量往往使用自动化方法很难确定。 因为天然簇的数量不是先验知道的，有时可能需要使用比关于数据中真正的自然数簇的“猜测”更大的$k$值。这将导致将一些数据簇分成多个代表，但不太可能会有集群被错误地合并。作为 k-representative后处理步骤，可能会基于簇间距离合并一些簇。 一些混合聚集和分区算法包括过程中的合并步骤。在书目注释参考这些算法。

6.4 分层聚类算法

分层算法通常用距离对数据进行聚类。 但是，使用距离函数不是强制性的。许多分层算法使用其他聚类方法，如基于密度或基于图形的方法，作为构建层次结构的子例程。

那么为什么层次聚类方法从以应用为中心的角度来说是有用的?一个主要原因是不同级别的聚类粒度提供了不同应用程序特定的见解。 这提供了可以浏览的用于语义分析的群集的分类。作为一个具体的例子，考虑由著名的开放目录项目$(ODP)$创建的网页的分类2。 在这种情况下，聚类是通过人工志愿者的努力创建的，但它提供了很好的可以用这种方法获得的多粒度见解的理解。图6.6说明了分层组织的一小部分。 在最高级别的网页上被分成诸如艺术，科学，健康等等的主题。在下一级，这个科学的话题成为副题，如生物学和物理学，而健康的话题分为健身和医药等话题。该组织进行手动浏览对用户来说非常方便，尤其是当群集的内容可以用语义上可理解的方式描述时。 在其他情况下，可以通过索引算法使用这种分级组织。此外，这些方法有时也可以用于创建更好的“平坦”群集。 一些凝聚层次方法和分裂方法等，如平分k-means可以提供比分割方法更好的类，例如k-means，虽然计算成本较高。

​ 图6.6 多层次聚类的多粒度见解

​ 有两种类型的分层算法，这取决于簇分层树的构建方式：

1. 自下而上（聚集）方法：各个数据点是连续地聚集成更高级别的集群。 不同方法之间的主要差异是在选择用于决定聚类合并的目标函数。
2. 自上而下（分裂）方法：自上而下的方法用于连续分区数据点指向树状结构。 可以使用平坦的聚类算法用于给定步骤中的分区。 这种方法提供了极大的灵活性在选择树结构中的平衡与每个节点中数据点的数量的平衡之间。例如，分割最重的节点的树木生长战略将导致叶节点在其中具有相似数量的数据点。 另一方面，构建平衡的树木生长战略在每个节点上具有相同数量子节点的树结构将导致叶节点具有不同数量的数据点。

​ 在下面的章节中，将讨论这两种分层方法。

6.4.1 自下而上的聚集方法

在自下而上的方法中，数据点被连续聚集成更高层次的聚类。该算法从各自的数据点开始，并将它们聚集成更高级的聚类。在每次迭代中，选择两个被认为尽可能接近群集。 这些集群被合并并替换为一个新创建的合并集群。 因此，每个合并步骤通过减少一个簇的数量，因此，需要设计一种方法来测量含有的簇多个数据点之间的接近程度，以便它们可以合并。这是计算集群之间的距离的选择，不同方法之间的大部分变化都会出现。

令$n$是$d$维数据库$\mathcal{D}$中的数据点的数量，并且$n_t = n-t$是$t$个聚集后的聚类数量。 对于任何给定的点，该方法在当前数据中簇之间保持一个$n_t×n_t$的距离矩阵$M$.用于计算和维护这个距离矩阵的确切的方法将在后面描述。 在任何给定的迭代算法，距离矩阵中的（非对角）条目最少距离被选择，并且相应的群集被合并。这种合并将需要将距离矩阵更新为更小的$(n_t-1)\times(n_t-1)$矩阵。 维度减少1，因为两个合并群集的行和列需要删除，并且与新创建的群集相对应的新的行和列的距离需要被添加到矩阵中。这对应于数据中新创建的集群。该用于确定这个新创建的行和列的值的算法依赖于合并过程中聚类到聚类的距离计算，接下来再描述。距离矩阵的增量更新过程是更有效的选择，而不是从头开始计算所有距离。 当然，假设足够的内存可用于维护距离矩阵。 如果不是这样，那么距离矩阵需要在每次迭代中完全重新计算，使这种凝聚方法变得不太理想。对于终止，两个合并群集之间的距离可以使用最大阈值，或最小阈值可以用于终止时的集群数目。前者的标准被设计为自动确定数据中簇的自然数目，但具有阈值质量难以直观地预测，需要规范的缺点。 后者的标准具有优势可以直观地解释数据中的聚类数量。自然合并的命令会创建一个层次树状结构来说明这种在不同的聚类之间的关系，这被称为树状图。在图6.8a中有 树状图的一个例子，其中$A，B，C，D，E$和$F$表示的六个数据点上进行连续合并。

算法 聚集合并（数据：$\mathcal{D}$）

开始

​ 用$\mathcal{D}$初始化$n\times n$阶距离矩阵$M$ 重复

​ 使用$M$选择距离最近的聚类$i$和$j$； 合并聚类$i$和$j$； 删$M$中的行/列$i$和$j$并且对与合并的新的聚类建立新的行和列； 更新$M$中的新的行列的全部元素； **直到**满足终止准则；

​ 返回 当前合并的聚类的基；

结束

图6.7 具有未指定合并准则的通用聚集合并算法

图6.8 分层聚类步骤的图解

在图6.7中说明了具有未指定合并标准的通用聚集程序。 被编码的距离在$n_t×n_t$距离矩阵$M$中。这个矩阵提供使用合并标准成对簇距离的计算。稍后将描述合并标准的不同选择。 两个集群的合并对应于矩阵M中的行（列）$i$和$j$需要一些其构成目标之间的距离测量的计算。对于包含$m_i$和$m_j$的两个簇对象分别存在组成对象之间的$m_i·m_j$对距离。例如，在图6.8b中，成分对象之间有$2×4 =8$对距离，由相应的边缘来说明。 两个集群之间的整体距离需要根据这些$m_i·m_j$对来计算。 在下面，将讨论计算距离的不同方式。

6.4.1.1 基于组的统计

以下讨论假定要合并的两个群集的索引是分别由$i$和$j$表示。 在基于组的标准中，两对象组之间的距离被计算为组对象之间的$m_i\cdot m_j$对距离的函数。计算两组目标之间距离的不同方式如下：

1. 最佳（单个）联动：在这种情况下，距离等于在所有$m_i·m_j$对物体之间的最小距离。 这对应于两组之间最接近的一对目标。在执行合并之后，矩阵$M$的成对距离需要更新。 第$i$行和第$j$行被删除并被合并的集群替换一行和一列代表。新行（列）可以使用先前在$M$删除的一对行（列）中的最小值来计算。这是因为其他群集到合并群集的距离是它们在与各个群集的距离的最小值的最佳关联。 对于任何其他聚类$k\neq i，j$，这等于$\operatorname{min} {(M_{ik}，M_{jk})}$（对于行）和$\operatorname{min}(M_{ki}，M_{kj})$（对于列）。然后更新行和列的索引以解释两个集群的删除并用新集群替换它们。最好的联系方式是非常擅长发现任意形状的簇的凝聚方法的实例之一。这是因为数据点在任意形状的聚类中可以连续合并，数据点成对链以小的距离彼此配对。 另一方面，当它由嘈杂的点产生时，这样的链接可能也会不恰当地合并不同的簇。

2. 最差（完整）联动：在这种情况下，两组物体之间的距离为等于两组中所有$m_i\cdot m_j$对象之间的最大距离。这对应于两组中最远的一对。 相应地，矩阵在这种情况下，$M$使用行（列）的最大值进行更新。 对于任何$k\neq i，j$的值，这等于$\operatorname{max} {(M_{ik}，M_{jk})}$（对于行）和$\operatorname{max}(M_{ki}，M_{kj})$（对于列）。最糟糕的联系标准试图使一个簇的直径最大值最小化，定义为由任何一对点之间的最大距离。 这种方法也被称为完整的联动方法。

3. 组平均关联：在这种情况下，两组对象之间的距离为等于组中所有$m_i\cdot m_j$对象之间的平均距离。至于计算$M$中合并聚类的行（列），即使用矩阵$M$第$i$个和第$j$行（列）加权平均值。对于任何$k\neq i，j$的值，这等于$\frac{m_i\cdot M_{ik}+m_j\cdot M_{jk}}{m_i+m_j}$（对于行）和$\frac{m_i\cdot M_{ki}+m_j\cdot M_{kj}}{m_i+m_j}$（对于列）。

4. 最近的中心：在这种情况下，最接近的中心在每次迭代中合并。 这个方法并不可取，但是，因为中心失去了不同集群的相对差异有关信息。例如，这种方法不会歧视在合并不同大小的聚类对之间，只要它们的中心对距离相同。通常情况下，对合并对较大的距离有偏差，因为较大群集的中心在统计上更可能更接近彼此。

5. 基于方差的标准：该标准最大限度地减少了目标函数的变化（如聚类方差）作为合并的结果。 合并由于粒度的损失，总是会导致聚类目标函数值恶化。希望合并目标函数中变化（退化）的簇作为合并的结果是尽可能少的。 为了实现这个目标，第一、二阶矩统计数据与每个群集保持一致。可以将第$i$个群集的平均平方误差$SE_i$计算为簇中的点（零阶矩）数量$m_i$的函数，聚类i中数据点的总和$F_ir$沿着每个维度$r$（一阶矩），以及在集群$i$中平方和的$S_ir$根据每个维度$r$（二阶矩）的数据点有以下关系; $$ SE_i=\sum_{r=1}^{d(S_{ir}/m_i-F}2_{ir}/m^2_i)\tag{6.8} $$ 这种关系可以用方差的基本定义来表示，并被许多聚类算法如$BIRCH$（参见第7章）使用。 因此，对于每个群集，只需要维护这些特定于群集的统计信息。这样的统计很容易保持跨合并，因为在两个集群$i$和$j$合并时统计并且可以被容易地计算为它们的时刻统计量的总和。让$SE_{i∪j}$表示两个集群i和j之间潜在合并的方差。 所以执行集群$i$和$j$合并时的方差变化如下： $$ \Delta SE_{i\cup j}=SE_{i\cup j}-SE_i-SE_j \tag{6.9} $$ 这种变化可以始终显示为正数量。最小方差增加的簇对将因合并而导致被选择为要合并的相关对。 如前所述，$ΔSE_{i∪j}$的成对值的矩阵$M$与时刻统计保持一致。在第$i$个和第$j$个簇合并后，簇$M$的第$i$行和第$j$列将被删除，合并后的簇的新列将添加。$M$中的这个新列的第k行（列）输入$（k = i，j）$与$SE_{i∪j∪k}-SE_{i∪j}-SE_k$是相等的。 这些值是使用群集时刻统计计算的。 在计算新的行和列之后，矩阵$M$的索引会更新以说明其尺寸缩小。

6. 沃德的方法：与其使用方差的变化，也可以使用（无标度）平方误差和作为合并标准。这相当于设置方程式6.8的$RHS$ 至$\begin{matrix}\sum_{r=1}^d(m_iS_ir-F^2_{ir})\end{matrix}$。 令人惊讶的是，这种方法是一个变化的中心法。合并的目标函数是通过乘法获得的（平方）欧式距离与每一对中点的点数谐波平均值之间的欧几里德距离。因为较大的群集受到这个附加因素影响，该方法比中心方法更有效。

各种标准具有不同的优点和缺点。 例如，单曲联系方法能够连续合并紧密相关的点链来发现任意形状的群集。但是，这个属性也可以（不恰当地）合并两个不相关的群集，当链接是由两个群集之间的噪点引起的时。 图 6.9a和b的例子分别说明了单链接聚类的好和坏情况。因此，单连接方法的行为取决于嘈杂的数据点影响和存在。 有趣的是，众所周知的$DBSCAN$算法（参见图 6.6.2）可以看作是单连接方法的一个强有力的变体，它可以找到任意形状的簇。$DBSCAN$算法排除来自聚类合并过程的嘈杂点以避免不需要的链接效应。

图6.9 单连接聚类好的和坏的情况

完整（最坏情况）的连接方法试图最小化群集中的任意一对点之间最大距离。 这种量化可以被视为一种一个簇的直径的近似。 由于其专注于最小化直径，它会尝试创建群集，以便它们都具有相似的直径。但是，如果数据中的一些自然簇比其他簇大，那么这种方法就会打破这个较大的群集。 它也将偏向于创建球形形状的团簇而不管基础数据分布。完整链接方法的另一个问题是它在集群的噪声边缘对数据点太重要，因为重点关注集群中任意一对点之间的最大距离。 组平均，方差，并且$Ward$的方法在距离计算中由于使用多个关联而更加稳健。

凝聚方法需要维护一堆有序的距离来有效地确定矩阵中的最小距离值。初始距离矩阵计算需要$O(n^2\cdot d)$时间，并且维护排序后的堆数据结构在算法的过程中需要$O(n^2·log(n))$时间，因为总共会有$O(n^2)$添加和删除到堆中。因此，整体运行时间为$O(n^2·d + n^2·log(n))$。 距离矩阵所需的空间是$O(n^2)$。 且空间要求对于大型数据集来说尤其成问题。在这种情况下，相似度矩阵M不能增量维护，许多分层方法的时间复杂性将会急剧增加到$O(n^3·d)$。发生这种增加是因为相似性计算集群之间需要明确执行合并。不过，它有可能通过近似合并标准在这种情况下加速算法。在第7章的7.3.3节中讨论的$CURE$方法，提供可扩展的分层方法单链接应用并可以发现任意形状的聚类。 这个通过使用从群集中仔细选择的代表点来实现改进计算单链接标准。

实际考虑

聚集式分层拒了方法生成了一个二叉树集群。 一般来说与自上而下的方法相比使用自下而上的方法更难控制分层树的结构。因此，在特定结构的情况下分类自下而上的方法不太理想。

分层方法存在的一个问题是它们对在合并过程中犯的少数错误都很敏感。例如，如果不正确的合并决定是由于数据集中存在噪声而在某个阶段做出，那么就没有办法撤销它，错误可能会在连续合并中进一步传播。实际上，一些层次聚类的变体，如单连接方法，由于存在少量嘈杂点而合并相邻群集是不太好的。尽管如此，通过处理嘈杂的数据点来减少这些影响的方法也有很多。

从空间和时间效率角度来看，凝聚方法对于更大的数据集可能变得不切实际。 因此，这些方法通常与采样以及其他分区方法相结合来有效地提供高质量的解决方案。

6.4.2 自上而下的分裂方法

尽管自下而上的凝聚方法通常是基于距离的方法，但自上而下分层方法可以被看作是几乎所有的聚类算法都可以看作是一个子程序的通用元算法。由于自上而下的方法，涉及到它的度和不同树枝之间的平衡方面在树的总体结构上可以实现更强的控制。

自顶向下聚类的整体方法使用通用平面聚类算法$\mathcal{A}$作为子程序。 该算法在包含全部数据点的根节点处初始化树。在每次迭代中，当前树的特定节点处的数据集是分成多个节点（集群）。通过改变节点选择的标准，人们可以创建高度平衡的树木或聚类数目平衡的树木。如果算法$\mathcal{A}$是随机的，例如k-means算法（随机种子），可以使用在特定节点对相同算法进行多次试验并选择最佳试验。该图6.10说明了自顶向下分裂策略的通用伪代码。该算法以自顶向下的方式递归地分割节点，直到实现某个高度树或者每个节点包含少于预定数量的数据对象。一个算法A的不同实例可以设计各种各样的算法和增长战略。 请注意，算法$\mathcal{A}$可以是任何的聚类算法，而不仅仅是一个基于距离的算法。

算法：通用的自顶向下集群算法（数据：$\mathcal{D}$，算法：$\mathcal{A}$)

$开始$:

​ 将树$\mathcal{T}$初始化为包含$\mathcal{D}$的根； 重复

​ 根据预定义的准则，选择树$\mathcal{T}$中的叶子节点$L$; 使用算法$\mathcal{A}$将$L$分成$L_1…L_k$; 把$L_1…L_k$作为孩子加入到树$\mathcal{T}$的$L$节点； **直到**满足终止准则；

$结束$

图6.10 通用自顶向下聚类算法

6.4.2.1 平分K-Means

平分$k$-均值算法是一种自顶向下的层次聚类算法，使用2-均值算法将每个节点正好分成两个子节点。将节点分割成两个子节点，使用了几次随机化的拆分试运行，以及使用了拆分对总体聚类目标有最佳影响。这种方法的几种变体使用选择要分割的节点的不同增长策略。 例如，最重的节点可能首先被分割，或者离根距离最小的节点可能被首先分割。这些不同的选择导致平衡聚类权重和树高。

6.5 基于概率模型的算法

本书中讨论的大多数聚类算法都是硬聚类算法，每个数据点被确定性地分配给特定的群集。 基于概率模型算法是软算法，其中每个数据点可以具有非零分配到许多（通常是所有）集群的概率。聚类问题的软解决方案可以通过将数据点分配给相对于集群的方式从而转换为硬解决方案，这样具有最大的分配概率。

基于混合的生成模型的宽泛原则是假设数据是由具有概率分布$\mathcal{G_1}\cdot \mathcal{G_k}$的$k$个分布的混合产生。 每分布$\mathcal{G}_i$表示一个聚类，也被称为混合分量。 每数据点$\overline{X_i}$，其中$i∈{\left\{1\ldots n \right\}}$ ，这个混合模型产生如下：

1. 选择一个先验概率为$α_i=P(\mathcal{G_i})$的混合分量，其中$i∈{\left\{1\ldots k\right\}}$。假设选择了第$r$个。
2. 从$\mathcal{G_r}$产生一个数据点。

该生成模型将由$\mathcal{M}$表示。不同的先验概率$α_i$和不同分布$\mathcal{G_r}$的参数事先是未知的。每个分步$\mathcal{G_i}$通常被假定为高斯分布，尽管每个$\mathcal{G_i}$可以假定任意的（不同的）分布簇。 分布$\mathcal{G_i}$的选择很重要，因为它反映了用户对个人的聚类的形状和分布的先验理解（混合组分）。每种混合成分的分布参数，例如它的均值和方差，需要从数据中估计出来，整体数据具有模型生成的最大可能性。 这已经用期望最大化$(EM)$算法实现了。不同混合成分的参数可以用来描述集群。 例如，每个高斯分量平均值的估计类似于在一个$k$代表性的算法中确定每个聚类中心的平均值。在混合成分的参数估计已经完成之后，相对于数据点到每个混合组分（簇）的后生成（或分配）概率都可以确定。

假定混合分量$\mathcal{G_i}$的概率密度函数表示为$f^i(\cdot)$。 数据点$\overline{X_j}$的概率（密度函数）由模型生成，由不同混合组分的概率密度的加权和给出，其中权重是混合物组分的先验概率$α_i=P(\mathcal{G_i})$： $$ f^{{point}(\overline{X_j}|\mathcal{M})=\sum_{i=1}}k \alpha_i\cdot f^{i(\overline{X_j})\tag{6.10} $$ 然后，对于包含$n$个数据点的数据集$\mathcal{D}$，用$\overline{X_1}\ldots \overline{X_n}$表示，由模型$M$生成的数据集的概率密度是所有特定点的乘积概率密度： $$ f}{data}（\mathcal{D|M}）=\prod_{j=1}^n f^point(\overline{X_j}|\mathcal{M})\tag{6.11} $$ 数据集$\mathcal{D}​$相对于模型$\mathcal{M}​$的对数似然拟合$\mathcal{L(D|M)}​$是对数并且可以（更方便地）表示为在不同的数据点上数值的总和。 对数似然拟合更适合计算。 $$ \mathcal{L(D|M)}=\operatorname{log}(\prod_{j=1}^nf{point}(\overline{X_j}|\mathcal{M}))=\sum_{j=1}^{n\operatorname{log}(\sum_{i=1}}k \alpha_if^i(\overline{X_j})\tag{6.12} $$ 这种对数似然拟合需要最大化以确定模型参数。 显着的观察是如果数据点的概率是从不同的簇生成的是已知，那么对混合每个组分来说确定最优模型参数变得相对容易。同时，不同组件生成的数据点的概率取决于这些最优模型参数。 这种循环性让人联想起在6.3节中优化目标类似的循环分区算法的功能。在那种情况下，数据点的硬分配的聚类信息给每个本地聚类提供了给群集提供了确定最佳群集代表的能力。 在这种情况下，软分配的信息为每一个簇的提供估计最优（最大似然）模型参数的能力。这自然表明了一种迭代$EM$算法，其中模型参数和概率分配从彼此迭代地进行估计。

设$Θ$是一个向量，表示混合模型的所有组件的整个参数集。例如，在高斯混合模型的情况下，$Θ$包含所有组分混合均值，方差，协方差和先验生成概率$α_1\ldots α_k$。然后，$EM$算法从初始的一组$Θ$值开始（可能对应于数据点到混合分量的随机分配），并且继续如下：

1. （$E$步）给定$Θ$中参数的当前值，估计组件$\mathcal{G_i}$的后验概率$P(\mathcal{G_i}|\overline{X_j},Θ)$在生成过程中已经选择的，因为我们已经观察到数据点$\overline{X_j}$。 数量$P(\mathcal{G_i}|\overline{X_j},Θ)$也是我们试图估计的软集群分配概率。 这一步针对每个数据点$\overline{X_j}$和混合组分$\mathcal{G_i}$执行。
2. （$M$步）给定数据点分配给集群的当前概率，请使用最大似然法确定$Θ$中所有参数的值，根据当前分配最大化对数似然拟合。

这两个步骤重复执行以改进最大似然准则。当目标函数没有显着改善时，算法被认为在一定次数的迭代中是收敛的。 $E$步和$M$步的细节现在将继续解释。

$E$步骤使用当前可用的模型参数来计算由混合的每个组分产生数据点$\overline{X_j}$的概率密度。 这个概率密度用于计算通过组件$\mathcal{G_i}$生成数据点$\overline{X_j}$的贝叶斯概率（模型参数固定为当前参数集$Θ$）： $$ P(\mathcal{G_i}|\overline{X_j},\Theta)=\frac{P(\mathcal{G_i})\cdot P(\overline{X_j}|\mathcal{G_i},\Theta)}{\begin{matrix}\sum_{r=1}^k\end{matrix}P(\mathcal{G_r})\cdot P(\overline{X_j}|\mathcal{G_r},\Theta)}=\frac{\alpha_i\cdot f^{{i,\Theta}(\overline{X_j})}{\begin{matrix}\sum_{r=1}}k\end{matrix} \alpha_r\cdot f^{r,\Theta}(\overline{X_j})}\tag{6.13} $$ 正如你将在第10章中学习的那样的分类，6.13节正是这种机制，即贝叶斯分类器将先前未看到的数据点分配给类别（类别）。一个上标$Θ$已被添加到概率密度函数中以表示事实他们被评估为当前模型参数$Θ$。

假设$E$步骤已经提供了“正确的”软分配的情况下，$M$步骤需要优化每个概率分布的参数优化。 至于优化适合度，对应的对数似然拟合的偏导数相对于模型参数需要计算并设置为零。没有这些代数步骤的细节的具体描述，计算出的模型参数的值作为优化的结果在这里描述。

每个$α_i$的值被估计为分配给集群i的点的当前加权分数，其中$P(\mathcal{G_i}|\overline{X_j},\Theta)$的权重与数据点$\overline{X_j}$相关联。 因此，我们有： $$ \alpha_i=P(\mathcal{G_i})=\frac{\begin{matrix}\sum_{j=1}^n \end{matrix}P(\mathcal{G_i}|\overline{X_j},\Theta)} {n}\tag{6.14} $$ 在实践中，为了获得更小的数据集的稳健结果，分子中属于每个聚类的数据点的预期数量增加1，并且分母中点总数的是$n+k$。 因此，估计值如下: $$ \alpha_i=1+\frac{\begin{matrix}\sum_{j=1}^n \end{matrix}P(\mathcal{G_i}|\overline{X_j},\Theta)} {k+n}\tag{6.15} $$ 这种方法也被称为拉普拉斯平滑方法。

为了确定组件$i$的其他参数，处理$P(\mathcal{G_i}|\overline{X_j},\Theta)$的值作为该数据点的权重。 考虑$d$维高斯混合模型，其中第$i$个分量的分布定义如下: $$ f^{i,\Theta}(\overline{X_j})=\frac{1}{\sqrt{|\sum_i|}(2\cdot \pi)^(d/2)}e{-\frac{1}{2}(\overline{X_j}-\mu_i)\sum_i^{-1}(\overline{X_j}-\mu_i))}\tag{6.16} $$ 这里，$\overline{μ_i}$是第$i$个高斯分量的$d$维平均向量，并且$Σ_i$是第i个分量的广义高斯分布的$d×d$协方差矩阵。该符号$|Σ_i|$ 表示协方差矩阵的行列式。注释3可以显示，$\overline{μ_i}$和$Σ_i$的最大似然估计的产生了（概率加权）平均值以及该组件中数据点的协方差矩阵。 这些概率权重来自$E$步骤中的分配概率。有趣的是，这正是在6.3节中马哈拉诺比斯k-均值方法的代表和协方差矩阵是怎样的派生的推导。 唯一的区别是数据点没有加权，因为利用确定性$k$均值算法使用了硬分配的方法。请注意，这个词在高斯分布的指数中是马氏距离的平方。

$E$步骤和$M$步骤可迭代执行以收敛以确定最优参数集$Θ$。 在过程结束时，获得了一个用生成模型描述整个数据集的概率模型。该模型还提供了基于最终执行的的$E$步骤的数据点的软分配概率$P(\mathcal{G_i}|\overline{X_j},\Theta)$。

在实践中，为了最小化估计参数的数量，$Σ_i$的非对角输入往往设置为0.在这种情况下，$Σ_i$的行列式简化为各个维度上的方差的乘积。这相当于在指数中使用$Minkowski$距离的平方。 如果所有对角线输入进一步受限制为相同的值，那么相当于使用欧氏距离，并且所有混合的组件将具有球形团簇。因此，在每个组件的概率分布中，混合组的不同的选择和模型分布复杂性提供了不同灵活程度。

这种两阶段迭代方法类似于基于代表的算法。$E$步可以被看作是基于距离分区的分配步骤的软算法。$M$步骤让人想起优化步骤，其中最佳组件特定根据固定分配学习参数。 距离项在概率分布的指数中提供了概率和基于距离的算法之间的自然联系。 这个连接在下一节讨论。

6.5.1 EM与k-means和其他代表方法的联系

$EM$算法为概率聚类提供了非常灵活的框架，某些特殊情况可被视为基于距离的聚类方法的软版本。作为一个具体的例子，考虑作为模型设置的一部分所有先验生成概率$α_i$都是固定为$1/k$的情况。此外，混合的所有组分在所有方向上具有相同的半径$σ$，并假定第$j$个簇的平均值是$\overline{Y_j}$。 因此，要学习的唯一参数是$σ$和$\overline{Y_1}\ldots \overline{Y_k}$。 在那种情况下，第j个混合物的组分具有以下分布： $$ f^{j,\Theta}(\overline{X_i})=\frac{1}{(\sigma\sqrt{2\cdot \pi})^d}e{-(\frac{\lVert\overline{X_i}-\overline{Y_j}\rVert}{2\sigma^2})}\tag{6.17} $$ 该模型假设所有混合成分具有相同的半径$σ$，每个组件都是球形的。 请注意，分布中的指数是欧几里得距离的缩放平方。$E$步骤和$M$步骤如何与分配和k-means算法的重新集中步骤相比较？

1. （$E$步骤）每个数据点$i$有一个属于群集$j$的概率，它与到每个代表$\overline{Y_j}$的缩放和指数化的欧几里得距离是成比例的。在k-means算法中，通过挑选最好的任何代表$\overline{Y_j}$的欧几里距离是难以完成的。
2. （$M$步骤）中心$\overline{Y_j}$是所有数据点的由分配给集群j的概率定义的权重平均值。 这种硬算法用于k-means中，其中每个数据点分配给一个集群或未分配到群集（即类似于0-1概率）。

当混合分布用更一般形式的高斯分布来定义时，相应的 k-representative算法是$Mahalanobis k$均值算法。值得注意的是，一般高斯分布的指数是马哈拉诺比斯距离。这意味着$EM$算法的特殊情况相当于一个软版本的k-means算法，其中使用指数 k-representative距离定义软$EM$分配概率。

$E$步骤在结构上与分配步骤类似，$M$步骤与 k-representative算法中的优化步骤类似。 许多混合组组分分布可以以$K_1·e^{-K_2·Dist(\overline{X_i,Y_j})}$的形式表示，其中$K_1$和$K_2$通过分配参数来调节。这种指数分布的对数似然直接映射到$M$步目标函数中的加法距离项$Dist(\overline{X_i,Y_j})$，这在结构上与相应的 k-representative的方法的加性优化目标相同。对于许多具有混合概率分布的形式$K_1·e^{-K_2·Dist(\overline{X_i,Y_j})}$的$EM$模型，可以用距离函数$Dist(\overline{X_i,Y_j})$定义相应的$k$代表性算法。

实际考虑

混合建模中的主要的实际考虑因素是定义所需混合组分的灵活性的水平。 例如，当定义每个混合物组分作为广义高斯函数时，它更有效地发现任意形状的群集方向。另一方面，这需要学习更多的参数，如$d×d$协方差矩阵$Σ_j$。 当可用的数据量很小时，这样由于过拟合，这种方法不能很好地工作。过拟合是指这种情况，在真正的生成模型的小样本上学习的参数由于数据内部存在嘈杂的变化，因此不能反映了该模型。 此外，如在k-means算法，$EM$算法可以收敛到局部最优。

在另一个极端，一个可以选择一个球形高斯其中的每个混合分量具有相同的半径，并且还将先验生成概率$α_i$固定为$1/k$。在这种情况下，即使在非常小的数据集上，$EM$模型也可以非常有效地工作，因为算法只需要学习单个参数。 但是，如果不同集群具有不同的形状，大小和方向，即使在一个大的集群上也会很差。一般的经验法则是将模型的复杂性变为可用的数据大小。 更大的数据集允许更复杂的模型。 在某些情况下，分析师可能有有关集群中数据点分布的领域知识。 在这些情况下，最好的选择是根据这一领域知识选择混合组分。

图6.11 不同粒度的任意形状和网格划分的集群

6.6 基于网格和密度的算法

基于距离和概率的方法的一个主要问题是，底层集群的形状已经被底层距离函数或概率分布隐式地定义了。例如，k-means算法隐式地假设集群呈球形。类似地，一个带有广义高斯分布的EM算法假设是椭圆簇。在实践中，这些形状可能很难用距离函数或概率分布暗示的原型形状来建模。要理解这一点，请考虑图6.11a所示的集群。很明显，数据中有两组正弦曲线。然而，在k-means算法中，几乎任何代表的选择都将导致其中一个集群的代表从另一个集群中删除数据点。

基于密度的算法在这种情况下非常有用。这种算法的核心思想是首先识别数据中细粒度的密集区域。它们构成了构建任意形状集群的“构建块”。这些也可以被认为是伪数据点，它们需要被仔细地重新聚集到任意形状的组中。因此，大多数基于密度的方法都可以被认为是两层的层次结构算法。由于第二阶段的构建块比较少，与第一阶段的数据点数量相比，可以使用更详细的分析将它们组合成复杂的形状。这种详细的分析(或后处理)阶段在概念上类似于单链接聚合算法，它通常更适合于从少量(伪)数据点确定任意形状的集群。这个更广泛的原则有许多变体，这取决于所选择的特定类型的构建块。例如，在基于网格的方法中，细粒度的集群是数据空间中的网格状区域。当在密集区域中预先选择的数据点使用单链接方法进行集群时，这种方法称为$DBSCAN$。其他更复杂的基于密度的方法，例如$DENCLUE$，使用了对内核密度估计的梯度上升来创建构建块。

6.6.1 基于网格的算法

在这个方法中，数据被化为同等大小的p个区间，区间有可能是等深的，对于一个$d$维的数据集来说，这种划分会产生$p^d$个数据集，不同间隔尺寸$p=3,25,80$的网格在图6.11$b,c,d$所示。一个密度阈值$\tau$来决定$p^d$个超立方体的稠密度，在大多数真实的数据集中，会产生一个任意形状的集群在由一侧或至少一个角连接在一起的多个密集区域中。因此，如果两个网格区域共享一侧，则称它们相邻连接。这个定义的较弱版本考虑了两个区域如果它们相邻连接共同分享一个共同点。 许多网格聚类算法都使用强定义相邻的连通性，使用侧面而不是角落。总的来说，对于$k$维的数据来说，如果两个$k$维的超立方体至少由$r$维的空间邻接$(r<k)$，那么就可以认为这两个超立方体是邻接的。

​ 这种直接相邻的连接可以推广到间接密度连接在不直接相邻的网格区域之间。 两个网格区域是密度连接，如果一个路径可以从一个网格找到另一个只包含一系列相邻连接的网格区域。 基于网格的聚类的目标是确定由这样的网格单元创建的连接区域。 这很容易确定通过在网格上使用基于图的模型来连接网格区域。 每个密集的网格节点是与图中的节点相关联，并且每条边代表相邻的连接。该图中的连通分量可以通过使用宽度优先或者深度优先来确定在图上遍历，从不同组件中的节点开始。 图6.13展示了从构建块构建任意形状的集群的示例。注意，发现的集群的角是人为做成矩形的，这是基于网格的方法的局限性之一。图6.12讨论了基于网格的方法的通用伪代码。

基于网格（以及大多数其他基于密度）算法的一个理想特性是数据聚类的数量并未事先预先定义，如在k-means算法中。相反，目标是将数据中的自然聚类与相应的数据一起返回形状。 另一方面，需要定义两个不同的参数到网格范围$p$的数量和密度阈值$\tau$。 这些的正确选择参数通常很难并且语义上不直观。 一个不准确的选择可能导致意想不到的后果：

1. 当选择的网格数量范围太小时，如图6.11b所示，来自多个集群的数据将出现在相同的网格区域中。当选择的栅格范围的数量太大时，如图6.11d所示，这将导致许多空网格单元甚至在集群内。 如结果，数据中的自然簇可能被算法断开。 更大由于数量的增加，网格范围的数量也导致计算挑战网格单元的数量。

2. 密度阈值的选择对聚类具有相似的影响。 例如，当密度阈值$\tau$太低时，包括环境噪声在内的所有群集将会被合并成一个大集群。 另一方面，密度过高可以部分或全部错过一个集群。

上面讨论的两个缺点是严重的，尤其是在有重大意义的时候不同局部地区的团簇大小和密度的变化。

算法：通用的网格聚类算法（数据：$\mathcal{D}$，范围：$p$,密度：$τ$)

$开始$:

​ 将数据$\mathcal{D}$的每个维度离散为范围为$p$; 确定密度网格单元的密度水平$τ$; 如果网格是相邻的，则创建它们连接的图; 确定图的连通分量; **返回**每个连接组件中的点作为集群;

$结束$

图6.12 通用的网格聚类算法

图6.13 相邻的网格

实际问题

基于网格的方法不需要指定簇的数量，也可以不要为集群假设任何特定的形状。 但是，这是以牺牲的为代价的必须指定密度参数$\tau$，这在分析中并不总是直观的透视。 网格分辨率的选择也具有挑战性，因为它不清楚它是如何的可能与密度$\tau$有关。

许多基于密度的方法（包括基于网格的方法）面临的主要挑战是他们全局使用单一密度参数$τ$。 但是，底层的集群数据可能具有不同的密度，如图6.14所示。 在这种特殊情况下，如果密度阈值选择过高，则可能错过群集$C$。 在另一方面，如果密度阈值选择太低，则可能人为地合并聚类$A$和$B$。在这种情况下，基于距离的算法（如k-means）可能会更有效比基于密度的方法。 这个问题不是特定于基于网格的方法，而是通常会在所有基于密度的方法中出现。

图6.14 局部分布对基于密度的方法的影响

矩形网格区域的使用与这类方法的近似。 这个近似随着维数的增加而降低，因为高维矩形区域是底层群集的差近似。 此外，基于网格由于网格的数量，方法在高维方面变得在计算上不可行细胞与基础数据维度呈指数增长。

6.6.2 DBSCAN

DBSCAN方法的工作原理与基于网格的方法非常类似。 然而，与基于网格的方法不同，数据点的密度特征用于合并它们成类。 因此，密集区域中的单个数据点根据密度对它们进行分类。数据点的密度由位于半径内的点数决定该点的$Eps$（包括点本身）。 这些球形区域的密度是用于将数据点分类为核心，边界或噪声点。 这些概念被定义如下。

1. 核心点：数据点被定义为核心点，如果它至少包含$\tau$数据点。

2. 边界点：数据点被定义为边界点，如果它包含小于$\tau$点，但它在半径$Eps$内还包含至少一个核心点。

3. 噪点：既不是核心点也不是边界点的数据点被定义为噪点。

**$DBSCAN$**算法(数据：$\mathcal{D}$，半径：$Eps$，密度：$\tau$)：

$开始$:

​ 确定$\mathcal{D}$级核心，边界和噪声点（$Eps$，$τ$）； 创建连接核心点的图形； 如果它们在彼此的$Eps$内； 在图中确定连接的组件； 将每个边界点分配给连接的组件与它最好的连接； $返回$ 将每个连接组件中的返回点作为一个集群

$结束$

图6.15 基本的$DBSCAN$算法

核心点，边界点和噪声点的例子如图6.16所示$τ= 10$。数据点$A$是一个核心点，因为它包含10个数据点被说的半径$Eps$。另一方面，数据点$B$在$Eps$的半径中只包含6个点，但它包含核心点$A$。因此，它是一个边界点。数据点$C$是一个噪声点，因为在$Eps$的半径内只包含4个点，而它不包含任何核心点。核心、边界和噪声点确定后，进行$DBSCAN$聚类算法如下：首先，构建一个连通图核心点，其中每个节点对应于核心点，并且在其之间添加边缘一对核心点，当且仅当它们在彼此的$Eps$距离内。注意该图是在数据点而不是在分区上构建的，如图所示基于网格的算法。此图的所有连接组件都被标识出来。这些对应于在核心点上构建的群集。边界点然后分配给它们具有最高级别的连接。结果组是作为群集报告并且噪声点报告为异常值。基本的$DBSCAN$算法如图6.15所示。值得注意的是，基于图的聚类的第一步是与具有终止标准的单连接凝聚聚类算法相同$Eps$距离，这只适用于核心点。因此，$DBSCAN$算法可被看作是单链连接凝聚聚类算法的增强专门处理边缘（边界）和噪点。这种特殊的治疗可以减少而且不会失去创建任意形状的簇的能力，而是单链接算法的异常敏感的链接特性。例如，在图6.9b的情况下，噪声数据点的桥梁将不会用聚集过程，如果$Eps$和$τ$被适当选择。在这种情况下，$DBSCAN$会尽量发现正确的群集数据中的噪声。

实际问题

$DBSCAN$方法与基于网格的方法非常相似，只是它使用循环方法地区作为构建块。圆形区域的使用通常提供更平滑的轮廓到发现的聚类。尽管如此，在更详细的粒度水平上，这两者方法往往会变得相似。$DBSCAN$的优点和缺点与基于网格的方法相似。 $DBSCAN$方法可以发现任意形状的聚类，并且不要求将聚类数量作为输入参数。与基于网格的方法一样，它容易受到本地聚类密度的变化。例如在6.4b和6.14中$DBSCAN$将不会发现稀疏聚类，或者它可能会合并这两个密集的聚类。在这种情况下，像Mahalanobis k-means这样的算法因为它们能够用局部密度来标准化距离，所以更加有效。另一方面，$DBSCAN$将能够有效地发现图6.4a的聚类，其中用Mahalanobis k-means方法是不可能的。

图6.16 核心、边界和噪声点的例子

$DBSCAN$的主要时间复杂性在于找到不同的邻居数据点在$Eps$的距离内。 对于大小为$n$的数据库，时间复杂度可以是$O（n^2）$在最坏的情况下。 但是，对于一些特殊情况，使用空间索引进行查找最近的邻居可以将其减少到大约$O(n·log(n))$距离的计算。查询性能$O(log(n))$只适用于低维数据，而最近邻的索引工作运行良好。 一般来说，基于网格的方法更高效，因为它们划分空间，而不是选择更复杂的方法来寻找最近邻。

参数$\tau$和$Eps$以直观的方式相互关联，这对于参数设置非常有用。具体而言，在用户已经设定了$\tau$的值之后，$Eps$的值可以通过数据驱动的方式确定。这个想法是使用$Eps$的值可以捕获集群中的大部分数据点作为核心点。这可以实现：对于每个数据点，确定其$\tau$最近邻距离。通常情况下，簇内绝大多数数据点的$\tau$值小于最近邻距离。然而，$\tau$最近邻的值通常会因为少数噪点（或簇边缘处的点）突然增加。因此，关键是识别$\tau-$最近邻距离分布的尾部。统计测试，如$Z$值测试，可用于确定$Eps$的价值$τ-$最近邻距离开始突然增加。 $τ$最近邻的这个值在此截止点处的距离提供$Eps$的合适值。

**$DENCLUE$**算法(数据：$\mathcal{D}$，半径：$Eps$，密度：$\tau$)：

$开始$:

​ 用公式6.20的梯度上升确定$\mathcal{D}$中各数据点的密度吸引子； 创建汇聚到相同密度吸引子的数据点簇; 丢弃的集群密度流动密度小于$τ$和报告为离群点的值;
合并密度吸引子与密度路径至少为$τ$的簇； $返回$ 每个类簇中的点

$结束$

图6.17 基本的$DBSCAN$算法

6.6.3 DENCLUE

$DENCLUE$算法基于核密度估计的稳定统计基础。核密度估计可以用来创建一个光滑的轮廓密度分布。 在核密度估计中，坐标$X$处的密度$f（\overline{X}）$为定义为在数据库$D$中$n$个不同数据点的影响（核）函数$K（·）$的总和

$$ f(\overline{X})=\frac{1}{n}\sum_{i=1}^{n} {K(\overline{X}-\overline{X_i})}.\tag{6.18} $$ 可以使用各种各样的内核函数，而普通的选择是高斯内核。对于$d$维数据集，高斯内核定义如下：

$$ K(\overline{X}-\overline{X_i})=(\frac{1}{h\sqrt{2\pi}})^de{-\frac{\parallel \overline{X}-\overline{X_i} \parallel^2}{2\cdot h^2}}.\tag{6.19} $$ 这个范数$\parallel \overline{X}-\overline{X_i} \parallel$表示这些$d$维数据之间的欧几里得距离点。直观地说，核密度估计的效果是取代每个离散数据指向一个平滑的“凹凸”，一个点的密度就是这些“凹凸”的总和。这导致数据的平滑轮廓，其中数据的随机伪像被抑制，并且获得密度的平滑估计。这里，$h$代表调节估计平滑度的估计带宽。较大的值的带宽$h$可以消除嘈杂的文物，但也可能会失去一些细节分配。在实践中，h的值是以数据驱动的方式启发式选择的。一个举例说明了具有三个天然簇的数据集中的核密度估计在图6.18中。

图6.18 密度阈值较低的密度型剖面。

图6.19 密度阈值较高的密度型剖面。

目标是通过使用与其相交的密度阈值τ来确定聚类光滑的密度分布。示例在图1和图2中示出 6.18和6.19数据点在这个交叉点的每个（任意形状的）连接轮廓中都会属于这个交点相应的群集。位于此范围之外的群集的一些边界数据点轮廓也可能因为数据点与之相关联的方式而被包括使用爬山方法进行聚类。密度阈值的选择将会影响数据中的群集数量。例如，在图6.18中，一个低密度阈值被使用，因此两个不同的集群被合并。因此，该方法只会报告两个集群。在图6.19中，使用了更高的密度阈值，因此采用了该方法将报告三个集群。请注意，如果密度阈值进一步增加，则为1或更多的集群将完全错过。这样一个集群，其峰值密度较低比用户指定的阈值，被认为是一个噪声簇，并没有被报告$DENCLUE$算法。 $DENCLUE$算法使用密度吸引子的概念来划分数据点成群集。这个想法是将密度分布的每个局部峰值视为一个密度吸引子，并将每个数据点与其相关的峰值通过爬山向其相关联相关峰值。通过密度至少为τ的路径连接的不同峰值是然后合并。例如，在图6.18和6.19，每个图都有三个密度吸引子。但是，对于图6.18的密度阈值，只会发现两个簇，因为其中有两个会合并一对峰。

$DENCLUE$算法使用迭代梯度上升方法，其中每个数据点$X∈D$通过使用相对于密度分布的梯度来迭代地更新到$X$。设$X（t）$是第t次迭代中X的更新值。 $X（t）$的值被更新如下：

$$ \overline{X^{(t+1)}=\overline{X}(t)}+\alpha\Delta f(\overline{X^(t)}) \tag{6.20} $$ 这里，$∇f（X（t））$表示核密度的偏导数的d维向量相对于每个坐标，并且$α$是步长。数据点不断使用上述规则更新，直到它们收敛到局部最优值，这将会始终是密度吸引子之一。因此，多个数据点可能会收敛到密度相同的吸引子。这创建了对应于点的隐式聚类不同的密度吸引子（或局部峰值）。计算每个吸引子的密度根据公式6.18。那些吸引力的密度不符合用户指定的阈值$τ$被排除，因为它们被认为是小的“噪声”簇。此外，任何密度吸引子通过密度路径相互连接的一对丛集至少$τ$会被合并。这一步骤解决了多个密度峰值的合并问题如图6.18所示，类似于基于网格的后处理步骤方法和$DBSCAN$。整个$DENCLUE$算法如图6.17所示。

核密度估计的一个优点是梯度值$∇f（X）$可以是使用组成核心密度值的梯度很容易计算：

$$ ∇f(\overline{X})=\frac{1}{n}∇K(\overline{X}-\overline{X_i}) \tag{6.21} $$ 尽管如此，梯度的精确值取决于核函数的选择当数据点数量不同时，不同选择之间的差异往往并不显着很大。 在高斯内核的特定情况下，可以显示梯度起作用由于存在负平方距离，以下特殊形式指数：

$$ ∇K(X - X_i) ∝ (X_i - X)K(X - X_i) \tag{6.22} $$ 这是因为指数函数的导数本身就是它的梯度负平方距离与$（Xi - X）$成正比。 内核的梯度是这两个术语的产物。 请注意，在等式中的比例常数。 6.22是无关紧要的因为它间接包含在梯度上升法的步长$α$中。确定局部最佳值的另一种方式是将梯度$∇f（X）$设置为0作为$f（X）$的最优化条件，并使用其求解方程组一种迭代方法，但是使用与各种数据相对应的不同起点点。 例如，通过设置等式 我们用高斯核函数为6.21通过代入公式 公式中的6.22，6.21：

$$ \sum_{i=1}^{{n}\overline{X}K(\overline{X}-\overline{X_i})=\sum_{i=1}}{n}\overline{X_i}K(\overline{X}-\overline{X_i})\tag{6.23} $$ 这是一个关于X的d坐标的非线性方程组，它将具有对应于不同密度峰值（或局部最优值）的多个解决方案。 这样的系统的方程可以用迭代更新方法和选择的方法进行数值求解起点会产生不同的峰值。 当一个特定的数据点被用作起始点时在迭代中，它总是会达到它的密度吸引子。 因此，我们得到以下修改后的更新规则，而不是梯度提升法:因此，我们得到以下修改后的更新规则，而不是梯度提升法:

$$ \overline{X^{{(t+1)}}=\frac{\sum_{i=1}}{n}\overline{X_i}K(\overline{X^{{(t)}}-\overline{X_i})}{\sum_{i=1}}{n}K(\overline{X^{(t)}}-\overline{X_i})}\tag{6.24} $$ 这个更新规则取代了$Eq$。 6.20收敛速度要快得多。有趣的是，这个更新规则被广泛称为平均移位法。DENCLUE和均值漂移方法之间有着有趣的联系。书目注释包含指向这种优化方法和均值偏移方法的指针。

该方法需要计算每个数据点处的密度，即$O（n）$。因此，总体计算复杂度为$O（n^2）$。这种计算复杂性可以通过观察数据点的密度主要仅受其影响来减少其邻近的数据点，并且远处数据点的影响相对较小用于指数内核，如高斯内核。在这种情况下，数据是离散化的进入网格，并且只根据内部数据点计算点的密度它的网格和紧邻的网格。因为网格可以高效地访问通过使用索引结构，该实现更高效。有趣的是，通过使用$DBSCAN$方法的聚类可以证明$DENCLUE$的特例一个二进制核函数，它在一个点的$Eps$的半径内取值为1，并且否则为0。

实际问题

当时，$DENCLUE$方法可能比其他基于密度的方法更有效数据点的数量相对较少，因此，一个平滑的估计提供了一个更准确地了解密度分布。 $DENCLUE$也能够处理通过使用密度吸引子来以更优雅的方式在簇的边界处数据点从集群边缘吸引相关数据点，即使它们的密度较小比$τ$。如果它们的密度很小，那么将会适当地丢弃一小组嘈杂的数据点吸引子不符合用户指定的密度阈值$τ$。该方法也是共享的其他基于密度算法的许多优点。例如，该方法能够发现任意形状的簇，并且它不需要指定数字的集群。另一方面，正如所有基于密度的方法一样，它需要规范的密度阈值$τ$，这在很多实际应用中很难确定。如上所述早些时候在图6.14的背景下，密度的局部变化可能是一个重大挑战适用于任何基于密度的算法。但是，通过改变密度阈值$τ$是可能的创建一个分层的聚类树状图。例如，两个不同的$τ$值在图6.18和6.19将创建群集的自然分层排列。

6.7 基于图形的算法

基于图形的方法提供了一个通用的元框架，其中几乎任何数据类型可以聚集。 正如在$chap.$2，实际上任何类型的数据都可以被转换用于分析的相似度图。 这种转变是允许隐含的关键通过对相应的转换进行聚类来聚类任何数据类型图形。 这个转变将在下面的讨论中重新讨论。 成对的概念相似性通过使用邻域图来定义。 考虑一组数据对象$\mathcal{O}=\{O_1,...,O_n\}$，在其上可以定义一个邻域图。 请注意这些对象可以是任何类型的，例如时间序列或离散序列。 主要的限制是它应该可以在这些对象上定义一个距离函数。 邻域图构造如下：

1. 为$\mathcal{O}$中的每个对象定义单个节点。这由节点集$N$定义，包含$n$个节点，其中节点$i$对应于对象$O_i$。

2. 如果距离$d（O_i，O_j）$小于特定值，则在Oi和Oj之间存在边门槛？ 更好的方法是计算$O_i$和$K$的最近邻居$O_j$，并且当任一个是另一个的$k-$最近邻时添加边缘。 重量边缘$（i，j）$的$w_{ij}$等于一个核函数之间的距离对象$O_i$和$O_j$，以便更大的权重表示更大的相似性。 一个例子是热内核，它是根据参数$t$定义的：

$$ w_{ij}=e^{{{-d(O_i,O_j)}}2/t^2}\tag{6.25} $$ 对于多维数据，欧几里得距离通常用于实例化$d(O_ i,O_ j)$。

1. (可选步骤)此步骤有助于减少局部密度变化的影响，如图6.14所示。注意，数量$deg(i)=\sum_{i=1}^{n}w_{ir}$可以看作是本地内核密度估计点$O_i$附近的一个代替。每一个边的权重$w_{ij}$通过除以$\sqrt{deg(i)·deg(j)}$进行归一化。这种方法确保了在相似性值与局部密度归一化后进行聚类。这一步并不重要，当算法如归一化的光谱聚类被用于最终聚类节点在邻域图。这是因为光谱聚类方法在覆盖层下执行相似的标准化。

**算法**图元框架（数据：$\mathcal{D}$）

$开始$:

​ 在$\mathcal{D}$上构造邻域图$\mathcal{G}$; 确定$\mathcal{G}$中节点上的集群(社区); 如果它们在彼此的$Eps$内； $返回$ 与节点分区对应的集群;

$结束$

图6.20 通用的基于图的聚类算法

邻域图构建完成后，任何网络集群或社区检测算法（参见第19章第19.3节）可用于聚类中的节点邻里图。节点上的群集可用于映射回群集原始数据对象。谱聚类方法，这是一个特定的实例下面将详细讨论最后一个节点聚类步骤。但是，基于图表的方法应该被视为可以使用任何社区的通用元算法检测算法在最后的节点聚类步骤中。图6.20提供了基于图的聚类的总体元算法。

令$G =（N，A）$为节点集$N$和边集$A$的无向图，即由上述基于邻域的转换创建。对称的$n×n$权重矩阵$W$根据具体的选择定义了相应节点的相似度社区转型，如方程6.25。这个矩阵中的所有条目都被假定为非负值，更高的值表示更大的相似性。如果边之间不存在一对节点，则相应的条目被假定为0.希望嵌入这个图的节点变成了一个$k$维空间，这样就构成了相似的结构数据大约保留用于聚类过程。这个嵌入然后被用于聚类的第二阶段。

首先，让我们讨论将节点映射到一维的更简单的问题空间。对k维情况的推广是相对直接的。我们会例如将N中的节点映射成一组一维实值$y_1...y_n$在一条线上，所以这些点之间的距离反映了节点之间的连通性。它是对于与高权重边缘连接的节点映射到遥远的节点是不理想的点这一行。因此，我们想确定最小化$y_i$的值以下目标函数$O$：

$$ O=\sum_{i=1}^{{n}\sum_{j=1}}{n}w_{ij}*(y_i-y_j)^2\tag{6.26} $$ 这个目标函数在权重成比例的情况下惩罚$y_i$和$y_j$之间的距离去$w_{ij}$。 因此，当$w_{ij}$非常大（更相似的节点）时，数据点$y_i$和$y_j$会在嵌入式领域更可能彼此接近。 目标函数$O$可以根据权重矩阵的拉普拉斯矩阵$L$重写为$W=[w_{ij}]$。

拉普拉斯矩阵$L$被定义为$\Lambda-W$,其中$\Lambda$是一个对角矩阵，满足$\Lambda_{ii}=\sum_{j=1}^{n}w_{ij}$,将嵌入值的$n$维列向量表示为$\overline{y}=(y_1...y_n)^T$。在一些代数化简后，目标函数$O$可以用拉普拉斯矩阵来重写:

$$ O=2\overline{y}^TL\overline{y}\tag{6.27} $$ 拉普拉斯矩阵$L$是半正定的，具有非负特征值，因为平方目标函数$O$的和总是非负的。我们需要合并一个缩放约束，以确保所有$i$的$y_i = 0$的值没有被优化解选中。一个可能的比例约束如下:

$$ \overline{y}^T\Lambda\overline{y}=1\tag{6.28} $$ 约束条件中$Λ$的存在确保嵌入的更好的局部规范化。可以使用约束优化技术,使得$\overline{y}$的最优解是取最小化目标函数$O$等于最小的特征向量$Λ^{−1 }L$，满足关系$Λ^{−1} L\overline{y} =λ\overline{y}$。在这里$λ$是一个特征值。然而，最小的特征特征向量$Λ^{−1 }L$总是等于0，它对应于$\overline{y}$的平凡解向量只与包含1s成正比。这个平凡的特征向量是非信息性的，因为它将每个节点嵌入到直线上的同一点。因此，它可以被丢弃，在分析中不使用。然后第二个最小的特征向量提供了一个更有用的最优解。

该优化公式和相应的解可以推广到寻找最优k维嵌入。这是通过确定特征向量$Λ^{−1 }L$先后增加了特征值。丢弃后第一个微不足道的特征向量$\overline{e_1}$与特征值$\lambda_1=0$，这导致k的一组特征向量$\overline{e_2},\overline{e_3}…\overline{e_{k+1}}$与相应的特征值$λ_2≤λ_3≤…≤λ_{k + 1}$。每个特征向量是一个$n$维向量，并被缩放到单位范数。第$j$个特征向量的第$i$个分量表示第$i$个数据点的第$j$个坐标。因为总共$k$个特征向量选择，这种方法创建一个$n×k$矩阵,对应于一个新的$n$的每个数据点$k$维表示。然后可以将k-means聚类算法应用到转换后的表示中。

为什么转换后的表示比原始数据更适合于现成的k-means算法呢？值得注意的是，在新的嵌入空间中，基于欧几里得k-means自然发现的球状星团可能与原始空间中任意形状的星团对应。正如下一节所讨论的，这种行为是定义相似图和目标函数$O$的方式的直接结果。这也是使用转换到相似图的主要优点之一。例如,如果方法适用于任意形状的簇在图6.11中,相似图将这样一个k - means算法对转换后的数据(或一个社区检测算法相似图)通常会导致正确的原始空间中任意形状的簇。在第19章第19.3.4节中详细讨论了光谱方法的许多变体。

6.7.1 基于图的算法的性质

图6.21 k近邻图在处理不同形状和密度的簇的优点

基于图的算法的一个有趣特性是任意形状的簇可以被发现的方法。这是因为邻域图编码了相关的局部距离（或k个最近邻居），因此诱导邻域图中的社区通过聚集局部密集区域而隐式确定。如在上一节中讨论了基于密度的聚类，即本地聚集密集区域对应于任意形状的簇。例如，在图$6.21a$中，在$k-$最近邻图中，任意形状的集群A中的数据点将密集地相互连接，但不会显著地与集群B中的数据点连接。

基于图的方法也能够更好地适应数据中的局部变化密度（见图6.14），当他们使用k最近邻来构建邻域时而不是绝对距离阈值。这是因为k最近的邻居根据地点内距离的相对比较来选择节点的数据点是大还是小。例如，在图$6.21b$中，尽管如此簇$D$和$E$比稀疏簇$C$中的任何一对数据点彼此更接近，所有三个集群应被视为不同的集群。有趣的是，一个k最近邻图形不会为这些小的值创建太多的这些集群之间的交叉连接$ķ$。因此，尽管密度不同，所有三个集群都可以通过邻域图上的社区检测算法找到。因此，基于图形的方法可以由于其调整能力而提供比诸如DBSCAN等算法更好的结果改变局部密度以及发现任意形状的团簇的能力。k最近邻图算法的这种理想特性不限于使用谱聚类方法在最后阶段。许多其他基于图形的算法也有已被证明以局部敏感的方式发现任意形状的簇。这些可取属性因此被嵌入在k最近邻图表表示中可以概括为其他数据挖掘问题，如异常值分析。请注意共享最近邻近相似函数的局部敏感度（参见3.2.1.8节）第一章。 也是由于相同的原因。许多经典聚类的局部敏感性算法，如k-medoids，自下而上算法和DBSCAN，可以通过改进结合基于图的相似度函数，如共享最近邻法。

另一方面，高计算成本是基于图形的主要缺点算法。把这种方法应用到$n×n$相似矩阵通常是昂贵的。尽管如此，因为相似图很稀疏，所以最近有许多社区检测方法可以利用这种稀疏性来提供更有效的解决方案。

6.8 非负矩阵分解

非负矩阵分解（$NMF$）是一种适合聚类的降维方法。换句话说，它将数据嵌入到一个潜在的空间中更适合集群。这种方法适用于非负和稀疏的数据矩阵。例如，文本应用程序中的$n×d$文档项矩阵始终包含非否定条目。而且，由于大多数词频是零，这个矩阵也很稀疏。 非负矩阵分解为数据表示创建了一个新的基础系统，如在所有降维方法中。然而，与许多其他降维方法相比，$NMF$的一个显着特征是基础系统没有必然包含正交向量。此外，矢量和基础系统的基础在这个系统中的数据记录的坐标是非负的。这个非负面的表示非常易于解释并且非常适合聚类。所以非负面的矩阵分解是服务于对偶的降维方法之一启用数据集群的目的。

考虑$NMF$在文本域中的常见用例，其中$n×d$数据矩阵$D$是文档术语矩阵。换句话说，在词典上定义了$n$个文档大小$d$。 $NMF$将数据转换为简化的$k$维基系统，其中每个基础向量是一个话题。每个这样的基矢量是非负加权的矢量定义该主题的词。每个文档都有一个非负的坐标到每个基矢量。因此，可以确定文档的集群成员资格通过沿$k$个矢量中的任何一个检查文档的最大坐标。这个提供文档最相关的“主题”，因此定义了其集群。执行聚类的另一种方法是应用另一种聚类方法如变换表示上的$k-$均值。因为转换后的表示更好地区分群集，$k-means$方法将更加有效。该每个文件的表达方式作为一种附加和非负的组合底层主题还为这种表示提供了语义解释。这就是为什么矩阵分解的非负性是如此理想的原因。那么如何确定基础系统和坐标系？非负面的矩阵分解方法试图确定最小化的矩阵$U$和$V$以下目标函数：

$$ J=\frac{1}{2}\parallel D-UV^T \parallel^2 \tag{6.29} $$ 在这里，$\parallel ~\parallel^2$表示Frobenius范数（平方），它是所有平方的和矩阵中的元素，U是一个n×k的非负矩阵，V是一个非负的d×k矩阵。 k的值是嵌入的维数。 矩阵U提供了变换后的基础系统中D行的新k维坐标，矩阵V提供了原始词典的基本向量。 特别是，行U为每个n文档和列提供k维坐标的V提供k维基向量。前述优化问题的意义是什么？ 请注意通过最小化J，目标是将文档项矩阵D分解如下：

$$ D ≈ UV ^T\tag{6.30} $$ 对于$D$（文档向量）中的每一行$X_i$，以及$U$的每个$k$维行$Y_i$（经过变换文档向量），上述等式可以被重写如下：

$$ \overline{X_i} ≈ \overline{Y_i}V^T \tag{6.31} $$ 这与任何标准降维方法的形式完全相同，$V$的列提供基础空间和行向量$\overline{Y_i}$代表缩减的坐标。换句话说，文档向量$\overline{X_i}$可以被重写为近似（非负）$k$个基本向量的线性组合。$ k$的值通常比较小因为$V$的列向量发现了潜在的结构数据。 此外，矩阵$U$和$V$的非负性确保文件被表达为关键概念（或集群区域）的非负面组合基于术语的特征空间。

图6.22 非负矩阵分解的一个例子

一个玩具$6×6$文档项矩阵$D$的$NMF$的例子如图6.22所示。行对应于$6$个文档$\overline{X_1}...\overline{ X_6}$和$6$个单词对应的列。矩阵条目对应于文档中的词频。文件${\overline{X_1},\overline{X_2},\overline{X_3}}$与猫有关，文档${\overline{X_5},\overline{X_6}}$与汽车有关，文件X4与两者都有关。因此，数据中有两个自然簇，该矩阵被相应地分解为两个矩阵$U$和$V^T$，其秩$k = 2$。一个近似最优的分解，每个条目四舍五入到最接近的整数，如图6.22所示。请注意，因式分解矩阵中的大部分条目都不会在现实世界中的例子中恰好为0，但其中很多可能接近于0，差不多全部将是非整数值。很明显，$U$的列和行和$V$映射到数据中的汽车或猫群。 $6×2$矩阵$U$提供关于6个词与2个集群的关系的信息，而$6×2$矩阵$V$提供有关6个词到2个集群的对应关系的信息。每文件可以分配给它在$U$上具有最大坐标的群集。

通过分别用$U$和$V$的$k$列$U_i$和$V_i$表示矩阵乘积，可以将秩$k$矩阵分解$UV^T$分解为$k$个分量：

$$ UV^T=\sum_{i=1}{k}\overline{U_i}\overline{V_i}^T\tag{6.32} $$ 每一个$n×d$的矩阵$\overline{U_i}\overline{V_i}^T$都是秩为$rank-1$的矩阵，它对应于数据中的潜在分量。由于非负分解的可解释性，很容易将这些潜在组件映射到集群中。例如，上述示例中分别对应于猫和车的两个潜在分量如图6.23所示。

还有待解释的是如何解决上述针对$J$的优化问题。任何矩阵$Q$的平方范数可以表示为矩阵$QQ^T$的轨迹。因此，目标函数$J$可以表示如下：

$$J=\frac{1}{2}[(D-U^T)(D-U^T)^T]\tag{6.33}$$

$$=\frac{1}{2}[tr(DD^T)-tr(DVU^T)-tr(UV^TD^T)+tr(UV^TVU^T)]\tag{6.34}$$

这是一个关于矩阵$U = [u_{ij}]$和$V = [v_{ij}]$的优化问题。因此，矩阵项$u_{ij}$和$v_{ij}$是优化变量。此外，$u_{ij}≥0$和$v_{ij}≥0$的约束确保矩阵的非负性。这是一个典型的约束非线性优化问题，可以用拉格朗日松弛法来求解，拉格朗日松弛了这些非负约束，并在目标函数中用约束违犯惩罚替换它们。拉格朗日参数是这些新的惩罚项的乘数。让$P_α=[α_{ij}]_{n×k}$和$P_β=[β_{ij}]_{d×k}$是分别是维数相同的非负矩阵是$U$和$V$的元素。此外，请注意，$tr(P_αU^T)$等于$\sum_{i,j}α_{ij}u_{ij}$，$tr(P_βV^T)$等于$\sum_{i,j}β_{ij}v_{ij}$，它们分别对应于对$U$和$V$的非负性约束的拉格朗日惩罚。然后，具有约束惩罚的增广目标函数可表示为: $$ L=J+tr(P_αU^T)+tr(P_βVT)\tag{6.35} $$ 为了优化这个问题，我们计算了$L$对$U$和$V$的偏导数，并将其设为0。基于跟踪的目标函数的矩阵计算结果如下:

$$\frac{∂L}{∂U}=-DV+UV^TV+P_α=0\tag{6.36}$$

$$\frac{∂L}{∂V}=-D^TU+VU^TU+P_β=0\tag{6.37}$$

上述表达式提供了两个约束矩阵。上述$(i,j)$项(两个矩阵)条件分别对应于$L$对$u_{ij}$和$v_{ ij}$的偏导数。这些约束条件分别乘以$u_{ij}$和$v_{ ij}$。通过使用Kuhn-Tucker最优条件$α_{ij}u_{ij}=0$和$β_{ij}v_{ij}$，约束对可以写成:

$$(DV)_{ij}u_{ij}-(UV^TV)_{ij}u_{ij}=0 \forall{i}\in{1…n},\forall{j}\in{1...k} \tag{6.38}$$

$$(D^TU)_{ij}v_{ij}-(VU^TU)_{ij}v_{ij}=0 \forall{i}\in{1…d},\forall{j}\in{1...k} \tag{6.39}$$

这些条件独立于$P_α$和$P_β$，他们根据$U$和$V$的元素提供一个方程组。这类方程组通常用迭代法求解。通过对$u_{ij}$和$v_{ ij}$分别使用乘法更新规则，可以解决这个特定的系统:

$$u_{ij}=\frac{(DV)_{ij}u_{ij}}{(UV^TV)_{ij}} \forall{i}\in{1…n},\forall{j}\in{1...k} \tag{6.40}$$

$$v_{ ij}=\frac{(D^TU)_{ij}v_{ij}}{(VU^TU)_{ij}} \forall{i}\in{1…d},\forall{j}\in{1...k} \tag{6.41}$$

$U$和$V$的条目初始化为(0,1)中的随机值，并执行迭代直到收敛。

关于矩阵分解技术的一个有趣的观察是它也可以用于确定文字群集而不是文档群集。 就像$V$的列一样提供可用于发现文档集群的基础，可以使用列$U$找到与单词集群相对应的基础。 因此，这种方法提供了对维度非常大的空间的补充见解。

图6.23 NMF的矩阵分解

6.8.1 奇异值分解的比较

奇异值分解（参见第2章第2.4.3.2节）是一种矩阵分解方法。$SVD$将数据矩阵分解为三个矩阵而不是两个矩阵。 在这里复制第二章的公式2.12.：

$$D≈ Q_k\sum_{k}P_k^T \tag{6.42}$$

将这种分解与公式6.30的分解进行比较是有益的。 6.30为非负矩阵因式分解。$n×k$矩阵$Q_kΣ_k$类似于非负的$n×k$矩阵$U$。矩阵分解。 $d×k$矩阵$P_k$类似于矩阵中的$d×k$矩阵$V.$因式分解。两种表示都使数据表示的平方误差最小化。该$SVD$和$NMF$之间的主要差异源于相应优化公式中的不同约束。奇异值分解可以被看作是一个矩阵分解目标函数是相同的，但优化公式强加正交性对基础矢量的约束而不是非负的约束。许多其他种类的约束可以用来设计不同形式的矩阵分解。此外，可以改变目标函数进行优化。例如，$PLSA$（参见13.4节）将（缩放）矩阵的非负元素解释为概率并且最大化关于所观察的生成模型的似然估计矩阵元素。矩阵分解的不同变体提供了不同的类型各种应用中的实用程序。

1. $NMF$中的潜在因素对于聚类应用更容易解释，因为没有消极性。例如，在诸如文本聚类的应用程序域中，$U$和$V$中的每个$k$列可以与文档集群和单词相关联集群，分别。非负（转换）坐标的大小反映哪些概念在文档中强烈表达。这种“添加剂部分”$NMF$的表示具有高度的可解释性，特别是在文本等领域这些特征具有语义意义。这在$SVD$中是不可能的变换后的坐标值和基矢量分量可能是负的。这个也是$NMF$转换比$SVD$更有用的原因进行聚类。类似地，非负矩阵分解的概率形式，如$PLSA$，也常用于聚类。比较这一点是有益的图6.22的例子，在末尾有相同矩阵的$SVD$。
2. 与$SVD$不同，$NMF$的$k$个潜伏因子不是彼此正交的。这个是$NMF$的缺点，因为轴系统的正交性允许直观将数据转换解释为轴旋转。项目很容易在标准正交中的样本外数据点（即，不包括在$D$中的数据点）基础体系。此外，转换的数据点之间的距离计算在$SVD$中更有意义。
3. 对任何优化问题添加约束条件（例如非负性）通常会降低找到的解决方案的质量。但是，正交性的增加在$SVD$中，约束不影响无约束矩阵分解公式的理论全局最优值（参见练习13）。因此，$SVD$提供比$NMF$更好的$rank-k$近似值。此外，在实践中更容易以确定$SVD$的全局最优，与完全指定的矩阵的无约束矩阵分解相比。因此，$SVD$提供了其中之一无约束矩阵分解的替代全局最优解，这在计算上容易确定。对于不完整的数据矩阵，$SVD$通常很难实现矩阵分解的许多其他变体。这与评分矩阵不完整的推荐系统有关。有关建议的潜在因素模型的使用在第二部分进行了讨论。因此，$SVD和NMF$具有不同的优点和缺点，并且可能更合适针对不同的应用。

6.9 聚类验证

数据聚类确定后，重要的是要评估其质量。这个问题被称为集群验证。 集群验证通常很难实现数据集，因为问题是以无监督的方式定义的。 因此，没有外部验证标准可用于评估群集。 因此，可以定义许多内部标准来验证聚类的质量。 主要问题在于内部标准是它们可能偏向一种算法或另一种算法，具体取决于如何定义它们。 在某些情况下，外部验证标准可能可用一个测试数据集是综合生成的，因此真实（地面真值）聚类是众所周知。 或者，对于真实的数据集，类标签（如果可用）可用作代理为群集标识符。 在这种情况下，评估更有效。 这样的标准是简称外部验证标准。

6.9.1 内部验证标准

当没有外部标准可用于评估时，使用内部验证标准聚类的质量。 在大多数情况下，用于验证算法质量的标准是直接从目标函数中借用的，而目标函数是通过特定的聚类模型进行优化的。 例如，实际上$k$代表中的任何目标函数，$EM$算法和凝聚方法可用于验证目的。该使用这些标准的问题在比较不同的算法时显而易见方法。 验证标准总是有利于使用$a$的聚类算法类似于其优化的目标函数。 然而，在没有外部验证标准的情况下，这是人们希望达到的最好结果。 这样的标准也可以在使用相同的广泛方法比较两种算法方面是有效的。 通常使用的内部评估标准如下：

1. 到质心的平方距离之和：在这种情况下，不同群集的质心被确定，并且平方和（SSQ）距离被报告为相应的目标函数。 这项措施的较小值表明效果更好集群质量。 与基于密度的方法（如DBSCAN）相比，这种方法显然更适合基于距离的算法，如k-means。SSQ的另一个问题是，绝对距离不会为用户提供有关底层群集质量的有意义的信息。

2. 集群内与集群间距离比：这个测量比SSQ更详细测量。 这个想法是从底层数据中抽取r对数据点。 的这些，让P是属于算法找到的相同群集的一组对。剩余的对由集合Q表示。平均簇间距离和簇内距离定义如下：

$$ Intra = \sum_{(\overline{X_i},\overline{X_j})}dist(\overline{X_i},\overline{X_j})/|P | \tag{6.43} $$

$$ Intra = \sum_{(\overline{X_i},\overline{X_j})}dist(\overline{X_i},\overline{X_j})/|Q | \tag{6.44} $$

然后给出平均簇内距离与簇间距离的比率通过$Intra / Inter$这个度量的小值表示更好的聚类行为。

1. 轮廓系数：设$Davijin$为$\overline{X_i}$内数据点的平均距离$\overline{X_i}$的集群。 数据点$\overline{X_i}$到每个簇中的点的平均距离（除了它自己）也被计算出来，让$Dminout_i$表示这些（平均）距离中的最小值，在其他集群中。那么，第$i$个对象特有的轮廓系数$S_i$如下：

整体轮廓系数是数据点特定系数的平均值。轮廓系数将从范围（-1,1）中绘制。 大正值表示高度分离的聚 类，而负值表示某个水平混合来自不同群集的数据点。 这是因为Dminout我会只有在数据点Xi接近至少另一个数据点的情况下，才比Davgiin少群集比自己的群集。 这个系数的一个优点是绝对的值提供了对群集质量的直观感受。

$$ S_i=\frac{Dmin_i^{out}-Davg_i{in}}{max{Dmin_i^{out},Davg_i{in}}}\tag{6.45} $$

1. 概率测量：在这种情况下，目标是使用混合模型进行估计特定聚类的质量。 每个混合物组分的质心是假定为每个发现的簇的质心，以及其他参数每个组件（例如协方差矩阵）都是从发现的数据中计算出来的使用类似于$EM$算法的$M$步骤的方法进行聚类。 报告测量的总体对数似然性。 这种措施在知道时很有用从特定领域的知识来看，集群应该具有特定的形状通过混合物中每种组分的分布来提示。

内部措施的主要问题是他们严重偏向于特定的聚类算法。例如，基于距离的测量（例如轮廓系数）对于任意形状的聚类将不太适用。考虑聚类的情况在图6.11中。在这种情况下，某些特定点系数可能具有负值为正确的聚类。即使是正确聚类的整体轮廓系数可能不如不正确的$k-$均值聚类，其混合不同的点集群。这是因为图6.11中的簇是不符合的任意形状到距离测量的质量指标。另一方面，如果以密度为基础标准，但它也会偏向于基于密度的算法。专业不同方法与内部标准相对比较的问题在于所有标准试图为善良定义一个“原型”模型。质量衡量经常只告诉我们原型验证模型与用于发现的模型相匹配的程度集群，而不是任何内在的基础集群。这可以查看作为过度拟合的一种形式，这会显着影响这种评估。至少，这是现象会造成评估可靠性的不确定性，从而影响评估的可靠性首先评估的目的。这个问题是无监督的基础数据聚类的本质，对此问题还没有完全令人满意的解决方案。内部验证措施在某些实际情况下确实具有实用性。例如，它们可以用于通过相似类别的算法或不同运行来比较聚类相同的算法。最后，这些措施对集群的数量也很敏感通过算法找到。例如，不能比较两个不同的聚类当由不同算法确定的聚类数目是一个特定标准时不同。细粒度聚类通常与许多优越的值相关联内部质量措施。因此，应谨慎使用这些措施，因为他们倾向于支持特定的算法或者相同的不同设置算法。请记住，聚类是一个无监督的问题，根据定义，意味着在不存在的情况下，没有明确定义的“正确”聚类模型的概念的外部标准。

图6.24 参数调整的有效性度量的拐点。

6.9.1.1 使用内部度量的参数调整

所有的聚类算法使用许多参数作为输入，例如数量簇或密度。尽管内部措施本身存在缺陷，但数量有限可以用这些措施来执行参数调整。这里的想法是，有效性测量的变化可能显示正确的拐点（或“肘”）参数的选择。当然，因为这些措施是有缺陷的，所以这样做应谨慎使用技术。此外，拐点的形状可能会随着所调整的参数的性质和验证而显着变化正在使用的措施。考虑参数为k的k均值聚类的情况tuned是簇的数目$k$。在这种情况下，$SSQ$度量总是会减少与集群的数量有关，尽管它会在变形后以极低的速度降低点。另一方面，对于诸如群内群与群间群的比率等度量距离，措施将减少，直到拐点，然后可能会略微增加。一个这两种变形的例子如图6.24所示。 X轴表示参数被调节（簇的数量），并且$Y$轴说明（相对）值的验证措施。在许多情况下，如果验证模型也不反映数据中聚类的自然形状或用于创建数据的算法模型聚类非常好，这样的转折点可能是误导性的，甚至没有被观察到。但是，如图6.24所示的图可以与视觉结合使用检查数据的散点图和算法分区以确定数据许多情况下正确的聚类数量。这种内部措施的调整技巧应该用作非正式的经验法则，而不是一个严格的标准。

6.9.2 外部验证标准

当关于基础数据中的真实群集的基础真实可用时，使用这样的标准。一般来说，这在大多数实际数据集中是不可能的。但是，合成时数据是从已知基准生成的，因此可以将群集标识符与生成的记录。在实际数据集的情况下，这些目标可以近似在类别标签可用时通过使用类别标签实现。使用的主要风险类标签是这些标签基于该数据集的应用程序特定属性并且可能不会反映基础数据中的自然聚类。尽管如此，这样的标准仍然比内部方法更可取，因为它们通常可以避免一致的偏见评估，当在多个数据集上使用时。在下面的讨论中，术语“类”标签“将互换使用，以指代合成数据中的任一群集标识符设置或分类真实数据集中的标签。其中一个问题是数据中自然簇的数量可能不会反映出来类标签（或集群标识符）的数量。类标签的数量由表示$k_t$表示集群的真实或基础真实数。簇的数量由算法确定的记为$k_d$。在一些设置中，真实群集的数量$k_t$等于算法确定的聚类$k_d$的数量，尽管这通常不是案件。在$k_d = k_t$的情况下，创建混淆矩阵特别有用涉及真实聚类的映射到由算法确定的那些。每排i对应于类别标签（地面实况集群）$i$，并且每对应于算法确定的簇$j$中的点。因此，这个矩阵的第（$i$，$j$）个条目是等于真集群$i$中的数据点的数量，其被映射到算法确定的集群$j$。整个特定行的值总和将始终相同跨越不同的聚类算法，因为它反映了地面真实聚类i的大小数据集。

图6.25 聚类质量好的混淆矩阵。 图6.26聚类质量差的混淆矩阵

当聚类质量很高时，通常可以对行和列进行置换这个混淆矩阵的列，所以只有对角线条目很大。在另一当聚类质量较差时，矩阵中的条目将更多平均分配。图1和图2中示出了混淆矩阵的两个例子。 6.25和6.26，分别。第一个聚类显然比第二个聚类要好得多。混淆矩阵提供了直观的方法来直观地评估聚类。但是，对于较大的混淆矩阵，这可能不是一个实际的解决方案。此外，而对于$k_d\neq k_t​$的情况，也可以创建混淆矩阵，这很困难通过视觉检查评估特定聚类的质量。因此，重要的是设计硬性措施来评估混淆矩阵的整体质量。两个普遍使用的措施是集群纯度和基于等级的基尼指数。让$m_{ij}​$代表映射到（算法确定的）簇$j​$的来自类（地面实况簇）$i​$的数据点的数目。这里，我是从[1，$k_t​$]中抽取的，$j​$是从范围中抽取的[1，$k_d​$]。同样假设真簇中的数据点数量用$N_i​$表示，算法确定的簇$j​$中的数据点的数目由$M_j​$表示。因此，不同群集中数据点的数量可以如下关联：

$$N_i=\sum_{j=1}^{k_d}m_{ij}\tag{6.46}$$

$$M_j=\sum_{i=1}^{k_t}m_{ij}\tag{6.47}$$

高质量的由算法确定的集群$j$应该包含很大程度上的数据点由一个类统治。 因此，对于给定的算法确定的簇$j$，其主导类别中的数据点$P_j$的数量等于值的最大值$m_{ij}$在地面真值簇的不同值上：

$$ P_j=max_im_{ij}\tag{6.48} $$ 高质量聚类会导致$P_j≤M_j$的值，这些值非常接近$M_j$。 然后，整体纯度如下：

$$ Purity=\frac{\sum_{j=1}^{{k_d}P_j}{\sum_{j=1}}{k_d}M_j}\tag{6.49} $$ 纯度的高值是可取的。簇的纯度可以用两种不同的方式计算。上面讨论的方法计算每个算法的纯度 - 确定集群（相对于地面真值集群），然后计算总体纯度以这个为基础。第二种方法可以用来计算每个地面真值聚类的纯度尊重算法确定的聚类。这两种方法不会导致相同的结果结果，特别是当$k_d$和$k_t$的值显着不同时。的意思在这种情况下，也可以使用两个值作为单一度量。第一项措施，根据公式6.49，是最容易直观解释的，因此是最多的流行。 基于纯度的措施的一个主要问题是只能解释集群中的主导标签并忽略剩余点的分布。对于例如，包含主要来自两个类的数据点的群集更好而不是数据点属于许多不同类别的数据库，即使是集群的纯度是一样的。为了解释不同类别之间的差异，基尼系数可能会有所不同使用。这项措施与熵的概念密切相关，它衡量的水平在一行（或一列）条目分布中的不平等（或混淆）混淆矩阵。与纯度测量的情况一样，它可以按行进行计算方法或列方法，并且它将评估为不同的值。这里描述了列式方法。列（算法确定的集群）$j$的基尼指数$G_j$定义如下：

$$ G_j=1-\sum_{i=1}^{{k_t}(\frac{m_{ij}}{M_j})}2\tag{6.50} $$ 当混淆矩阵的列中的条目为时，G j的值将接近于0偏斜，如图6.25的情况。 当条目均匀分布时，值将为接近$1 - 1 / k_t$，这也是该值的上限。 平均基尼系数是这些不同列向值的加权平均值，其中$G_j$的权重是$M_j$：

$$ G_{average}=\frac{\sum_{j=1}^{{k_d}G_j*M_j}{\sum_{j=1}}{k_d}M_j}\tag{6.51} $$ 基尼系数值较低是可取的。 基尼指数的概念密切相关到熵$E_j$（由算法确定的簇j）的概念，其测量相同数据的直观特征：

$$ E_j=-\sum_{i=1}^{k_t}(\frac{m_{ij}}{M_j})*log(\frac{m_{ij}}{M_j})\tag{6.52} $$ 熵的较低值表示较高质量的聚类。 整体熵以与基尼系数相似的方式计算，并使用特定于集群的熵。

$$ E_{average}=\frac{\sum_{j=1}^{{k_d}E_jM_j}{\sum_{j=1}}{k_d}M_j}\tag{6.53} $$ 最后，可以使用成对精确度和成对召回度量来评估质量的聚类。 为了计算这个度量，生成相同算法决定的簇内的所有数据点对。 属于相同的基本群集的对的比例是精度。 为了确定召回，在同一点内的点对对地面真实聚类进行采样，并计算出现在相同算法决定聚类中的分数。 统一的措施是$Fowlkes-Mallows$措施报告精度和召回的几何平均值。

6.9.3 一般结论

虽然群集验证是聚类文献中广泛研究的问题，但大多数用于群集验证的方法相当不完善。 内部措施不完善，因为它们通常偏向于一种算法或另一种算法。 外部措施不完善因为他们使用的类标签可能不会反映数据中的真实群集。即使生成了合成数据，生成方法也会隐含地支持一个算法或其他。 出现这些挑战是因为聚类是一个无监督的问题，并且验证这些算法的质量是非常困难的。 通常，唯一的事情就是这样聚类质量的测量是其满足特定应用目标的能力。

6.10 总结

针对数据聚类问题设计了各种各样的算法，例如基于代表性的方法，分层方法，概率方法，基于密度的方法，基于图的方法和基于矩阵分解的方法。所有方法通常都要求算法指定一些参数，例如簇的数量，密度或矩阵分解的秩。基于代表的方法，和概率方法限制了聚类的形状，但更好地适应不同的聚类密度。另一方面，凝聚和密度为基础的方法更好地调整簇的形状，但不适应簇的密度变化。基于图形方法提供了对不同形状和密度的最佳调整，但通常更多实施起来很昂贵。集群验证的问题是一个非常困难的问题无监督的问题，如集群。虽然外部和内部验证标准可用于聚类，但它们往往偏向于不同的算法，或者可能不准确地反映底层数据中的内部群集。这样的措施应该是谨慎使用。

6.11 书目注释

聚类问题已经在数据挖掘和机器学习文献中被广泛研究。传统书籍[74,284,303]讨论了大部分传统聚类方法。这书介绍了许多经典的算法，例如分割和分割分层算法，非常详细。另一本书[219]讨论了数据聚类的最新方法。数据聚类的优秀调查可以在[285]中找到。最多最近的书[32]在文献中提供了一个非常全面的概述数据聚类算法。提供了关于特征选择方法的详细讨论在[366]中。基于距离的熵度量在[169]中讨论。可以使用从谱聚类和聚类散布矩阵导出的各种有效性度量用于特征选择[262,350,550]。聚类书[32]的第二章提供了详细的内容审查特征选择方法。一个经典的调查[285]提供了对k均值算法的优秀评论。问题在[108]中讨论了改进k-均值类型算法的初始数据点。该解决了在k均值算法中发现正确簇数量的问题在[423]中。代表性算法的其他着名标准包括使用Bregman分歧[79]。本章介绍的三种主要的基于密度的算法是STING [506]，DBSCAN [197]和DENCLUE [267]。出现更快的DENCLUE更新规则在[269]中。更快的更新规则在[148,159]早些时候独立发现均值漂移聚类。在基于网格的算法中，最常见的算法包括WaveCluster [464]和MAFIA [231]。 DBSCAN的增量版本已解决在[198]中。 OPTICS算法[76]基于排序执行基于密度的聚类的数据点。它对分层聚类和可视化也很有用。另一个DBSCAN算法的变化是可以使用的GDBSCAN方法[444]更普遍的数据类型。最着名的基于图的算法之一是Chameleon算法[300]。共享最近邻居算法[195]，本质上是基于图形的算法，并进行调整以及不同数据位置的变化密度。众所周知的自顶向下分层多级聚类算法是METIS算法[301]。一个很好的调查关于谱聚类方法可以在[371]中找到。矩阵分解及其[288,440,456与谱聚类密切相关[185]。 [212]中讨论了图中社区检测的方法。任何这些方法都可以用于图形聚类算法的最后一个阶段。讨论聚类有效性方法在[247,248]中。另外，[32]详细研究了聚类有效性的问题。

6.12 习题

1. 考虑具有10个数据点的1维数据集{1，2，3，...10}。 显示三个当$k = 2$时$k-$均值算法的迭代，并且随机序列被初始化到{1，2}。
2. 用初始种子集{2，9}重复练习1。 如何做出不同的选择种子集影响结果的质量？
3. 编写一个计算机程序来实现k代表性算法。 使用模块化的程序结构，其中的距离函数和质心测定是独立的子程序。 将这些子程序实例化为（i）$k-means$的情况算法，和（ii）k-中值算法。
4. 实现$Mahalanobis k-means$算法。
5. 考虑一维数据集{1...10}。 应用层次聚类方法，使用最小，最大和组平均标准进行合并。显示前六个合并。
6. 编写一个计算机程序来实现分层合并算法单连接合并标准。
7. 编写一个计算机程序来实现EM算法，其中有两个具有相同半径的球形高斯团簇。 下载电离层数据集来自UCI机器学习库[213]。 将算法应用于数据设置（随机选择中心），并在每个中记录高斯的质心迭代。 现在应用练习3中实现的k-means算法，使用相同的算法一组初始种子为高斯质心。 两种算法中的质心如何？比较不同的迭代？
8. 练习7的计算机程序使用一般的高斯分布，而不是球形高斯分布。
9. 考虑一个具有三个自然簇的1维数据集。 第一个集群包含连续的整数{1...5}。 第二个群集包含{8...12}。 第三个群集包含数据点{24,28,32,36,40}。 应用初始中心为1，11和28的kmeans算法。算法是否确定正确的群集？
10. 如果初始中心更改为1，2和3，算法是否发现正确集群？ 这告诉你什么？
11. 使用练习9的数据集来展示分层算法如何敏感局部密度变化。
12. 使用练习9的数据集来展示基于网格的算法如何对本地敏感密度变化。
13. 线性代数的一个基本事实是任何$rank-k$矩阵都有一个奇异值分解，其中$k$个奇异值非零。 使用此结果表明奇异值分解中$rank-k$近似的最小误差与$α$相同无约束矩阵分解，其中基本向量不被约束正交。 假设在两种情况下都使用误差矩阵的$Frobenius$范数来计算近似误差。
14. 假设你从一个数据集构造了一个k近邻相似度图与边缘的重量。 从下面描述自下而上的单链算法相似度图。
15. 假设使用共享最近邻近相似度函数（见第3章）结合$k-medoids$算法从$n$个数据点中发现$k$个簇。用来定义共享最近邻居相似度的最近邻居的数量是米 描述如何以$k$和$n$的形式选择合理的$m$值，如不会导致较差的算法性能。
16. 假设矩阵分解用于近似表示数据矩阵$D$如$D≈D'= UV^T$。 显示一个或多个$U$和$V$的行/列可以是乘以常数因子，以代表$D'= UV^T$中的无限数量不同的方式。 这些解决方案中$U$和$V$的合理选择是什么？
17. 解释每个内部有效性标准是如何偏向其中一种算法的。
18. 假设你生成一个包含任意方向的高斯聚类的合成数据集。 $SSQ$标准如何反映集群的质量？
19. 哪些算法对于练习18中的合成数据生成方法最有效？