Python 无监督学习实用指南：1~5（4）

Python 无监督学习实用指南：1~5（3）https://developer.aliyun.com/article/1426882

对于ε < 7，该值为空。 这样的结果归因于该算法产生的大量群集和噪声样本。 由于样本分布在不同的区域，因此小的扰动不会改变分配。 对于7 < ε < 17，我们观察到一个正斜率达到最大值，大约对应于ε = 12.5，然后负斜率达到最终值 0。在这种情况下，聚类变得越来越大，并且包含了越来越多的样本。 但是，当ε仍然太小时，密度可达性链容易被小扰动破坏（也就是说，样本可以克服球的边界，因此将其排除在群集外）。 结果，在施加加性噪声之后，通常将样本分配给不同的群集。 当ε = 12.5时，此现象达到最大值，然后开始变得不太明显。

实际上，当ε足够大时，球的并集能够包裹整个群集，从而为小扰动留出足够的自由空间。 当然，在取决于数据集的阈值之后，将仅产生单个群集，并且，如果噪声不太强，则任何扰动版本将产生相同的分配。 在我们的特定情况下，ε = 25确保了高稳定性，这也可以通过 t-SNE 图得到证实。 一般而言，此方法可用于所有算法和几何形状，但建议您在决定如何创建受干扰的版本之前，先对X进行全面分析。 实际上，错误的决定会损害结果，产生较大/较小的不稳定性，并不表示表现不好/良好。 特别是，当聚类具有不同的方差时（例如，在高斯混合中），加性噪声项对某些样本的影响可以忽略不计，而它可以完全改变其余样本的结构。 在这些情况下，此方法比其他方法要弱，并且应使用方差很小（通常小于最小聚类（协）方差）的高斯噪声进行二次采样。 另一方面，使用基于密度的算法进行二次采样显然会非常危险，因为由于可达性的丧失，小型群集可能会成为一组孤立的噪声点。 我邀请读者也使用 K 均值测试此方法，以找到最佳的群集数（通常与最小不稳定性相关）。

K 中心点

在上一章中，我们显示了当群集的几何形状为凸形时，K 均值通常是一个不错的选择。 但是，该算法有两个主要局限性：度量始终为欧几里得，并且对异常值的鲁棒性不强。 第一个元素是显而易见的，而第二个元素是质心性质的直接结果。 实际上，K 均值选择质心作为不属于数据集的实际均值。 因此，当聚类具有一些离群值时，均值会受到影响并朝着它们成比例地移动。 下图显示了一个示例，其中一些异常值的存在迫使质心到达密集区域之外的位置：

质心选择（左）和中心点选择（右）的示例

K 中心点的提出（在《基于 L1 范数和相关方法的统计数据分析》中），最初是为了缓解对异常值的缺乏鲁棒性的问题（在原始论文中，该算法仅设计用于曼哈顿度量标准），但后来设计了不同版本，以允许使用任何度量标准 （尤其是任意的闵可夫斯基指标）。 与 K 均值的主要区别在于质心的选择，在这种情况下，质心是始终属于数据集的示例性样本（称为中心点）。 该算法本身与标准 K 均值非常相似，并且替代了中心点的定义μ[i] = x[i] ∈X分配给聚类C[i]的所有其他样本的平均或总距离），然后将样本重新分配给具有最接近中心点的聚类。

容易理解的是，离群值不再具有较高的权重，因为与标准质心相反，离群值被选择为质心的可能性接近于零。 另一方面，当群集由无法归类为离群值的较远样本包围的密集斑点组成时，K 中心点表现较差。 在这种情况下，该算法会错误地分配这些样本，因为它无法生成可以捕获它们的虚拟球（请注意，半径是由质心/质心的相互位置隐式定义的）。 因此，尽管 K 均值可以将质心移动到非密集区域以捕获远点，但当密集的斑点包含许多点时，K 中心点不太可能以这种方式表现。

此外，K 中心点趋向于聚集高度重叠的斑点，斑点的密度具有两个峰值，而 K 均值通常根据手段的位置将整个区域分为两部分。 如果凸几何的假设成立，则通常会接受此行为，但是在其他情况下这可能是一个限制（我们将在示例中展示这种效果）。

最后一个基本差异是公制距离。 由于没有限制，所以 K 型药物或多或少具有攻击性。 正如我们在第 2 章，“聚类基本原理”中讨论的那样，最长的距离由曼哈顿度量标准提供（以相同的方式评估每个组件），而当p增加（以通用的闵可夫斯基度量），组件之间的最大差异成为主导。 K 均值基于最常见的权衡（欧几里德距离），但是在某些特殊情况下，较大的p可以带来更好的表现（比较p = 1与p > 1）。 例如，如果c[1] = (0, 0)，c[2] = (2, 1)和x = (0.55, 1.25)，曼哈顿距离d[1](x, c[1])和d[1](x, c[2])分别为 1.8 和 1.7，而欧几里得距离为 1.37 和 1.47。 因此，在p = 1的情况下，该点被分配给第二个群集，而在p = 2的情况下，该点被分配给第一个群集。

通常，预测正确的p值并不容易，但始终可以使用轮廓和调整后的 Rand 得分等方法测试几种配置，并选择产生更好分割效果的方法（即 ，最大内聚和分离度或更高的调整后的 Rand 得分）。 在我们的示例中，我们将生成一个也包含基本事实的数据集，因此我们可以使用后一个选项轻松评估表现。 因此，我们将使用函数make_blobs生成1000样本，这些样本在由[-5.0, 5.0] 界定的框中分成8个 blob，如下所示：

from sklearn.datasets import make_blobs
nb_samples = 1000
nb_clusters = 8
X, Y = make_blobs(n_samples=nb_samples, n_features=2, centers=nb_clusters, 
                  cluster_std=1.2, center_box=[-5.0, 5.0], random_state=1000)

结果数据集呈现出一些强烈的重叠（如最终图所示），因此我们不希望使用对称方法获得高级结果，但是我们有兴趣比较 K 均值和 K 均值的赋值 。

让我们开始评估由 K 均值达到的调整后的兰德分数，如下：

from sklearn.cluster import KMeans
from sklearn.metrics import adjusted_rand_score
km = KMeans(n_clusters=nb_clusters, random_state=1000)
C_km = km.fit_predict(X)
print('Adjusted Rand score K-Means: {}'.format(adjusted_rand_score(Y, C_km)))

前一个块的输出如下：

Adjusted Rand score K-Means: 0.4589907163792297

这个值足以理解 K 均值在进行错误分配，尤其是在重叠区域中。 由于使用这种方法很难对数据集进行聚类，因此我们并不将这一结果视为真实的指标，而只是将其视为可以与 K 中心点得分进行比较的度量。 现在，我们使用带有p = 7的 Minkowski 度量来实现此算法（邀请读者更改此值并检查结果），如下所示：

import numpy as np
C = np.random.randint(0, nb_clusters, size=(X.shape[0], ), dtype=np.int32)
mu_idxs = np.zeros(shape=(nb_clusters, X.shape[1]))
metric = 'minkowski'
p = 7
tolerance = 0.001
mu_copy = np.ones_like(mu_idxs)

数组C包含分配，而mu_idxs则包含中心点。 由于存储整个中心点所需的空间量通常很小，因此我们首选此方法，而不是仅存储索引。 优化算法为，如下所示：

import numpy as np
from scipy.spatial.distance import pdist, cdist, squareform
from sklearn.metrics import adjusted_rand_score
while np.linalg.norm(mu_idxs - mu_copy) > tolerance:
    for i in range(nb_clusters):
        Di = squareform(pdist(X[C==i], metric=metric, p=p))
        SDi = np.sum(Di, axis=1)
        mu_copy[i] = mu_idxs[i].copy()
        idx = np.argmin(SDi)
        mu_idxs[i] = X[C==i][idx].copy()
    C = np.argmin(cdist(X, mu_idxs, metric=metric, p=p), axis=1)
print('Adjusted Rand score K-Medoids: {}'.format(adjusted_rand_score(Y, C)))

行为非常简单。 在每次迭代中，我们都计算出属于一个群集的所有元素之间的成对距离（这实际上是最昂贵的部分），然后选择使总和最小的中心点。 循环后，我们通过最小化它们与类固醇的距离来分配样本。 重复该操作，直到类固醇的范数变化变得小于预定阈值为止。 调整后的 Rand 得分为，如下所示：

Adjusted Rand score K-Medoids: 0.4761670824763849

最终调整后的 Rand 分数受算法随机初始化的影响（因此，运行代码时，先前的结果可能会略有变化）。 在实际应用中，我建议根据最大迭代次数和较小的公差采用双重停止标准。

因此，即使没有解决重叠问题，其表现也比 K 均值稍好。 下面的屏幕快照显示了地面真相，K 均值和 K 质素结果：

真实情况（左），K 均值（中心）和 K 中心点（右）

如您所见，基本事实包含两个非常难以聚类的重叠区域。 在此特定示例中，我们对解决此问题不感兴趣，而是对展示两种方法的不同行为感兴趣。 如果考虑前两个 Blob（左上角），则 K 均值将整个区域分为两部分，而 K 均值将所有元素分配给同一群集。 在不知道基本事实的情况下，后一个结果可能比第一个更连贯。 实际上，观察第一张图，可能会发现密度差并不足以完全证明分裂的合理性（但是，在某些情况下这是合理的）。 由于该区域非常密集且与邻近区域分开，因此单个群集很可能是预期的结果。 此外，几乎不可能根据差异来区分样本（错误地分配了靠近分离线的大多数样本），因此，K 中心点的攻击性比 K 均值少，并且显示出更好的权衡性。 相反，两个算法几乎以相同的方式管理第二个重叠区域（右下）。 这是由于以下事实：K 均值将质心放置在非常接近某些实际样本的位置。 在这两种情况下，算法需要在 0 和 4 之间创建几乎水平的间隔，因为否则无法分割区域。 这种行为是所有基于标准球的方法所共有的，在这种特殊情况下，这是极其复杂的几何体的正常结果（许多相邻点具有不同的标签）。 因此，我们可以通过说 K 中心点对异常值更健壮，并通过避免不必要的分离而有时比 K 均值更好地表现出结论。 另一方面，在非常密集的区域中没有异常值时，这两种算法（尤其是采用相同度量时）是等效的。 作为练习，我邀请读者使用其他指标（包括余弦距离）并比较结果。

在线聚类

有时，数据集太大而无法容纳在内存中，或者样本通过通道流式传输并在不同的时间步长接收。 在这种情况下，不能使用前面讨论的算法，因为自第一步以来，它们就假定要访问整个数据集。 由于这个原因，已经提出了一些在线替代方案，并且当前它们已在许多现实生活中实现。

小批量 K 均值

该算法是标准 K 均值的扩展，但是，由于不能对所有样本都计算质心，因此有必要包括一个额外的步骤，当现有聚类不再有效时，该步骤负责重新分配样本。 特别是，小批量 K 均值代替了计算均值的方法，可以处理流平均值。 收到批量后，该算法将计算部分均值并确定质心的位置。 但是，并非所有集群都具有相同数量的分配，因此算法必须决定是等待还是重新分配样本。

通过考虑效率非常低的流处理过程，可以立即理解该概念，该过程开始发送属于半空间的所有样本，并且仅包括属于互补半空间的几个点。 由于群集的数量是固定的，因此该算法将开始优化质心，同时仅考虑一个子区域。 假设质心已放置在球的中心，该球围绕着属于互补子空间的几个样本。 如果越来越多的批量继续向密集区域添加点，则算法可以合理地决定丢弃孤立的质心并重新分配样本。 但是，如果进程开始发送属于互补半空间的点，则该算法必须准备好将它们分配给最合适的聚类（也就是说，它必须将其他质心放置在空白区域中）。

该方法通常基于称为重分配比α的参数。 当 α较小时，该算法将等待更长的时间才能重新分配样本，而较大的值会加快此过程。 当然，我们要避免两种极端情况。 换句话说，我们需要避免过于静态的算法在做出决定之前需要大量样本，同时又需要避免过于快速变化的算法来在每次批量后重新分配样本。 通常，第一种情况产生的次优解决方案具有较低的计算成本，而后一种情况可能变得非常类似于每次批量后重新应用于流数据集的标准 K 均值。 考虑到通常与实时过程有关的这种情况，我们通常对需要高计算成本的极其精确的解决方案不感兴趣，而对在收集新数据时得到改进的良好近似值不感兴趣。

但是，必须考虑每个单个上下文来评估重新分配比率的选择，包括合理地预定义流传输过程（例如，它是纯随机的吗？样本是否独立？某些样本在特定时间内是否更频繁） -帧？）。 同样，必须群集的数据量（即批量大小，这是一个非常重要的因素），当然还有可以配置的硬件。 通常，有可能证明小批 K 均值产生的结果可与标准 K 均值相媲美，并且批大小不是太小时具有较低的内存需求和较高的计算复杂性（但这通常不是可控的超参数，因为它取决于外部资源），并相应地选择重新分配比率。

相反，如果从真实数据生成过程中对批量进行均匀采样，则重新分配比率将成为次要参数，并且其影响会更低。 实际上，在这些情况下，批量大小通常是获得良好结果的主要影响因素。 如果足够大，该算法可立即确定质心的最可能位置，并且后续批量无法显着更改此配置（因此减少了对连续重新分配的需求）。 当然，在在线情况下，很难确定数据生成过程的结构，因此通常只能假设一批（如果不是太小）包含每个独特区域的足够代表。 数据科学家的主要任务是通过收集足够的样本以执行完整的 K 均值并将表现与小批量版本进行比较来验证该假设。 观察到批量量较小的最终结果（具有相同的重新分配比率）更好的方案也就不足为奇了。 通过考虑该算法不会立即重新分配样本可以理解这种现象。 因此，有时，较大的批量可能导致错误的配置，但是该配置具有更多的代表，因此重新分配的可能性较低（也就是说，算法更快但准确率更低）。 相反，在相同情况下，由于频繁的重新分配（具有更精确的最终配置），较小的批量可能会迫使算法执行更多的迭代。 由于定义通用的经验法则并不容易，因此一般建议是在做出决定之前检查不同的值。

CF 树

该算法（其名称代表使用层次结构的平衡迭代归约和聚类）具有比小批量 K 均值稍微复杂的动态特性，最后一部分采用了一种方法（层次聚类） 我们将在第 4 章，“层次结构聚类”中进行介绍。 然而，出于我们的目的，最重要的部分涉及数据准备阶段，该阶段基于称为群集特征树的特定树结构（CF 树）。 给定数据集X，树的每个节点都由三个元素的元组组成：

特征元素分别是属于一个节点的样本数，所有样本的总和以及平方范数的总和。 做出此选择的原因将立即清楚，但让我们现在将注意力集中在树的结构上，以及在尝试平衡高度时如何插入新元素。 在下图中，有一个 CF 树的通用表示形式，其中所有终端节点都是必须合并的实际子集群，以获得所需数量的集群：

具有二元分区的简单 CF-Tree 的示例

在上图中，点代表指向子节点的指针。 因此，每个非终端节点都与指向其所有子节点的指针(CF[i], p[i])一起存储，而终端节点是纯 CF。 为了讨论插入策略，必须考虑另外两个元素。 第一个称为分支因子B，而第二个称为阈值T。 此外，每个非终端节点最多可以包含B个元组。 通过减少存储的数据量和计算数量，设计了此策略，以最大程度地提高仅依赖于主内存的流处理过程的性能。

现在考虑需要插入的新样本x[i]。 很容易理解CF[j]的质心(n[j], a[j], b[j])只是μ[j] = a[j]/n[j]； 因此，x[i]沿着树传播，因为它到达了末端 CF（子集群），在此处距离d(x[i], μ[j])是最小值。 到那时，CF 会逐步更新：

但是，如果没有控制权，则树很容易变得不平衡，从而导致表现损失。 因此，该算法执行一个附加步骤。 一旦确定了 CF，就计算更新后的半径r[j]，以及是否r[j] > T并且 CF 的数量大于分支因子，分配新的块并且原始的 CF 保持不变。 由于这个新块几乎完全是空的（x[i]除外），BIRCH 会执行一个附加步骤来检查所有子集群之间的差异（此概念在第 4 章中会更清楚 ， “实用的层次聚类”；但是，读者可以考虑属于两个不同子类的点之间的平均距离）。 最不相似的一对分为两部分，其中之一移到新块中。 这样的选择确保了子群集的高度紧凑性，并加快了最终步骤。 实际上，实际聚类阶段中涉及的算法需要合并子聚类，直到总数减少到所需值为止。 因此，如果先前已将总不相似性最小化，则更容易执行此操作，因为段可以立即识别为连续并合并。 在本章中将不详细讨论此阶段，但不难想象。 将所有终端 CF 依次合并到较大的块中，直到确定单个群集为止（即使当数量与所需群集数目匹配时也可以停止该过程）。 因此，与小批量 K 均值相反，此方法可以轻松管理大量群集n[c]，而当n[c]很小时效果不佳。 实际上，正如我们在示例中将要看到的那样，其准确率通常比使用小批量 K 均值所能达到的精度低，并且其最佳用法要求准确选择分支因子和阈值。 由于此算法的主要目的是在在线情况下工作，因此B和T在处理了某些批量后可能会失效（而小批量 K 均值通常可以在几次迭代后纠正群集），产生次优的结果。 因此，BIRCH 的主要用例是需要非常细粒度细分的在线过程，而在所有其他情况下，通常最好选择小批量 K 均值作为初始选项。

小批量 K 均值和 BIRCH 的比较

在此示例中，我们想将这两种算法的表现与包含 2,000 个样本的二维数据集进行比较，该样本分为8个 blob（出于分析目的，我们也使用了基本事实），如下所示 ：

from sklearn.datasets import make_blobs
nb_clusters = 8
nb_samples = 2000
X, Y = make_blobs(n_samples=nb_samples, n_features=2, centers=nb_clusters,
                  cluster_std=0.25, center_box=[-1.5, 1.5], shuffle=True, random_state=100)

下面的屏幕快照显示了数据集（已被改组以除去流传输过程中的任何相互关系）：

二维数据集，用于比较小批量 K 均值和 BIRCH

在执行在线聚类之前，评估标准 K 均值的调整后的兰德得分非常有用，如下所示：

from sklearn.cluster import KMeans
km = KMeans(n_clusters=nb_clusters, random_state=1000)
Y_pred_km = km.fit_predict(X)
print('Adjusted Rand score: {}'.format(adjusted_rand_score(Y, Y_pred_km)))

前一个块的输出为，如下所示：

Adjusted Rand score: 0.8232109771787882

考虑到数据集的结构（没有凹面），我们可以合理地假设此值代表在线过程的基准。 现在，我们可以实例化类MiniBatchKMeans和Birch，其参数分别等于reassignment_ratio=0.001，threshold=0.2和branching_factor=350。 这些值是经过研究后选择的，但我邀请读者重复使用不同配置的示例，比较结果。 在这两种情况下，我们都假设批量大小等于50样本，如下所示：

from sklearn.cluster import MiniBatchKMeans, Birch
batch_size = 50
mbkm = MiniBatchKMeans(n_clusters=nb_clusters, batch_size=batch_size, reassignment_ratio=0.001, random_state=1000)
birch = Birch(n_clusters=nb_clusters, threshold=0.2, branching_factor=350)

该示例的目标是现在采用方法partial_fit()逐步训练两个模型，并考虑到每个步骤之前处理的全部数据，评估调整后的兰德得分，如下所示：

from sklearn.metrics import adjusted_rand_score
scores_mbkm = []
scores_birch = []
for i in range(0, nb_samples, batch_size):
    X_batch, Y_batch = X[i:i+batch_size], Y[i:i+batch_size]
    mbkm.partial_fit(X_batch)
    birch.partial_fit(X_batch)
    scores_mbkm.append(adjusted_rand_score(Y[:i+batch_size], mbkm.predict(X[:i+batch_size])))
    scores_birch.append(adjusted_rand_score(Y[:i+batch_size], birch.predict(X[:i+batch_size])))
print('Adjusted Rand score Mini-Batch K-Means: {}'.format(adjusted_rand_score(Y, Y_pred_mbkm)))
print('Adjusted Rand score BIRCH: {}'.format(adjusted_rand_score(Y, Y_pred_birch)))

前一个代码片段的输出包含整个数据集的调整后的 Rand 分数：

Adjusted Rand score Mini-Batch K-Means: 0.814244790452388
Adjusted Rand score BIRCH: 0.767304858161472

不出所料，当处理完所有样本后，小批量 K 均值几乎达到基准，而 BIRCH 表现稍差。 为了更好地理解行为，让我们考虑将增量分数作为批量函数的图表，如下图所示：

调整后的兰德评分增量作为批次（样本数量）的函数

如您所见，小批量 K 均值很快就达到最大值，所有随后的振荡都是由于重新分配。 相反，BIRCH 的表现总是较差，且呈负趋势。 出现这种差异的主要原因是由于策略不同。 实际上，小批量 K 均值可以在几次批量后纠正质心的初始猜测，并且重新分配不会显着改变配置。 另一方面，BIRCH 执行的合并数受样本数影响。

刚开始时，表现不是很相似，因为 CF 树中的子群集的数量不是很大（因此，聚合更多相干），但是经过几批之后，BIRCH 必须聚合越来越多的子群集来获得所需的最终群集数。 这种情况以及越来越多的流样本数量驱使算法重新排列树，这常常导致稳定性的损失。 此外，数据集有一些重叠，可以通过对称方法更轻松地进行管理（实际上，即使分配错误，质心在这种情况下也可以到达其最终位置），而采用分层方法（例如 BIRCH 所采用的方法更能够找到所有子区域，但是在合并具有最小间距甚至更糟的重叠的子类时，更容易出错。 但是，此示例确认，通常首选小批量 K 均值作为首选，并且仅在表现不符合预期时（应谨慎选择其参数）才应选择 BIRCH。 我邀请读者使用更多所需的群集（例如nb_clusters=20和center_box=[-10.5, 10.5]）重复该示例。 可能会看到在这种情况下（保持所有其他参数不变），由小批量 K 均值执行的重新分配如何以较差的最终调整后的 Rand 分数减慢了收敛速度，而 BIRCH 立即达到了最佳值（几乎相等） 到通过标准 K 均值获得的结果），并且不再受样本数量的影响。

总结

在本章中，我们介绍了一些最重要的聚类算法，这些算法可用于解决非凸问题。 频谱聚类是一种非常流行的技术，它可以将数据集投影到一个新的空间上，在该空间上，凹形几何形状变为凸形，而标准算法（例如 K 均值）可以轻松地对数据进行分段。

相反，均值漂移和 DBSCAN 分析数据集的密度并尝试对其进行拆分，以使所有密集区域和连通区域合并在一起以构成聚类。 特别是，DBSCAN 在非常不规则的情况下非常有效，因为它基于连接的本地最近邻集，直到分离度超过预定义的阈值为止。 这样，该算法可以解决许多特定的聚类问题，唯一的缺点是，它还会产生无法自动分配给现有聚类的一组噪声点。 在基于旷工的数据集的示例中，我们展示了如何选择超参数，以便以最少的噪声点和可接受的轮廓或 Calinski-Harabasz 分数获得所需数量的聚类。

在最后一部分中，我们分析了 K 中心点作为 K 均值的替代方法，它对于异常值也更可靠。 该算法不能用于解决非凸问题，但是它有时比 K 均值更有效，因为它没有选择实际的均值作为质心，而是仅依赖于数据集，并且聚类中心（称为中心点）是示例性样本。 而且，该算法不严格地局限于欧几里得度量，因此，它可以充分利用替代距离函数的潜力。 最后一个主题涉及两种在线聚类算法（小批量 K 均值和 BIRCH），当数据集太大而无法放入内存或长时间流传输数据时，可以使用这些算法。

在下一章中，我们将分析一个非常重要的聚类算法系列，它们可以输出完整的层次结构，从而使我们能够观察到完整的聚合过程，并选择最有用和最一致的最终配置。

问题

1. 半月形的数据集是凸群集吗？
2. 二维数据集由两个半月组成。 第二个完全包含在第一个的凹腔中。 哪种内核可以轻松地将两个群集分离（使用谱群集）？
3. 应用ε = 1.0的 DBSCAN 算法后，我们发现噪点太多。 对于ε = 0.1，我们应该期待什么？
4. K 中心点基于欧几里得度量。 它是否正确？
5. DBSCAN 对数据集的几何非常敏感。 它是否正确？
6. 数据集包含 10,000,000 个样本，可以使用 K 均值在大型计算机上轻松进行聚类。 相反，我们可以使用更小的机器和小批量的 K 均值吗？
7. 群集的标准差等于 1.0。 施加噪声N(0, 0.005)后，80% 的原始分配被更改。 我们可以说这样的集群配置通常是稳定的吗？

进一步阅读

• Normalized Cuts and Image Segmentation, J. Shi and J. Malik, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 22, 08/2000
• A Tutorial on Spectral Clustering, Von Luxburg U., 2007
• Functions and Graphs Vol. 2, Gelfand I. M., Glagoleva E. G., Shnol E. E., The MIT Press, 1969
• On Estimation of a Probability Density Function and Mode, Parzen E., The Annals of Mathematical Statistics, 33, 1962
• Application of a neuro fuzzy network in prediction of absenteeism at work, Martiniano A., Ferreira R. P., Sassi R. J., Affonso C., in Information Systems and Technologies (CISTI), 7th Iberian Conference on (pp. 1-4). IEEE, 2012
• A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise, Ester M., Kriegel H. P., Sander J., Xu X., Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, Portland, OR, AAAI Press, 1996
• Machine Learning Algorithms, Second Edition, Bonaccorso G., Packt Publishing, 2018
• Cluster stability: an overview,Von Luxburg U., arXiv 1007:1075v1, 2010
• Clustering by means of Medoids, Kaufman L., Rousseeuw P.J., in Statistical Data Analysis Based on the L1–Norm and Related Methods, North-Holland, 1987

四、实用的层次聚类

在本章中，我们将讨论层次聚类的概念，层次聚类是一种强大而广泛的技术，用于生成完整的聚类配置层次，从与数据集等效的单个群集（除法）开始，或者等于样本数量（凝聚法）的多个群集。 当需要立即分析整个分组过程以了解例如如何将较小的群集合并为较大的群集时，此方法特别有用。

特别是，我们将讨论以下主题：

• 层次聚类策略（分裂式和凝聚式）
• 距离度量和链接方法
• 树状图及其解释
• 凝聚聚类
• 作为一种表现指标的 Cophenetic 相关性
• 连通性约束

技术要求

本章中提供的代码要求以下内容：

• Python3.5+（强烈建议使用 Anaconda 发行版）
• 库：

• SciPy 0.19+
• NumPy 1.10+
• Scikit-Learn 0.20+
• Pandas 0.22+
• Matplotlib 2.0+
• Seaborn 0.9+

数据集可以从 UCI 机器学习存储库中获得。 可以从这里下载 CSV 文件，除了添加列名外，不需要任何预处理。 ，这将在加载阶段发生。

可以在 GitHub 存储库上找到示例。

层次聚类

在前面的章节中，我们分析了聚类算法，其中 ， 输出是基于预定义数量的聚类或参数集结果和精确的基础几何结构的单个分割。 另一方面，层次聚类生成一系列聚类配置，这些聚类配置可以排列在树的结构中。 具体来说，让我们假设有一个数据集X，其中包含n个样本：

凝聚方法是通过将每个样本分配到一个集群C[i]开始的，然后通过在每个步骤合并两个集群直到单个最终集群（对应于X）已产生：

在前面的示例中，群集C[i]和C[j]合并为C[k]； 因此，我们在第二步中获得n-1个群集。 该过程继续进行，直到剩下的两个群集合并为一个包含整个数据集的单个块。 相反，分裂方法（由 Kaufman 和 Roussew 最初提出，使用 DIANA 算法）在相反的方向上操作，从X开始，最后每个群集包含单个样本：

在这两种情况下，结果都是层次结构的形式，其中每个级别都是通过在上一个级别上执行合并或拆分操作来获得的。 复杂度是这两种方法之间的主要区别，因为分裂聚类的复杂度更高。 实际上，合并/拆分决定是通过考虑所有可能的组合并通过选择最合适的组合（根据特定标准）来做出的。 例如，在比较第一步时，很明显（在团聚的情况下）找到最合适的几个样本要比考虑所有可能的组合（在X中， 分裂情形），这需要指数级的复杂性。

由于最终结果几乎相同，而除法算法的计算复杂度要高得多，因此，一般而言，没有特别的理由偏爱这种方法。 因此，在本书中，我们将仅讨论凝聚聚类（假设所有概念都可立即应用于除法算法）。 我鼓励您始终考虑整个层次结构，即使需要大多数实现（例如 scikit-learn）来指定所需的集群数量。 实际上，在实际的应用中，最好是在达到目标后停止该过程，而不是计算整个树。 但是，此步骤是分析阶段的重要组成部分（尤其是在没有很好定义群集数的情况下），我们将演示如何可视化树并针对每个特定问题做出最合理的决策。

凝聚聚类

从其他算法中可以看出，为了执行聚合，我们需要先定义一个距离度量，该度量代表样本之间的不相似性。 我们已经分析了其中许多，但在这种情况下，开始考虑通用闵可夫斯基距离（用p参数化）会有所帮助：

两个特定情况对应于p = 2和p = 1。 在前一种情况下，当p = 2时，我们获得标准欧几里德距离（等于L[2]范数）：

当p = 1时，我们获得曼哈顿或城市街区距离（等于L[1]范数 ）：

这些距离之间的主要差异在第 2 章，“聚类基础知识”中进行了讨论。 在本章中，介绍余弦距离很有用，这不是一个合适的距离度量（从数学角度来看），但是当样本之间的区分必须仅取决于他们形成的角度时，这将非常有帮助：

余弦距离的应用非常特殊（例如自然语言处理（NLP）），因此，这不是一个常见的选择。 但是，我建议您使用一些样本向量（例如(0, 1), (1, 0)和(0.5, 0.5)，因为它可以解决许多现实生活中的问题（例如，在 word2vec 中，可以通过检查它们的余弦相似度来轻松评估两个单词的相似度）。一旦定义了距离度量，定义邻接矩阵，P：

P是对称的，所有对角元素均为空。 因此，某些应用（例如 SciPy 的pdist函数）会产生一个压缩矩阵P[c]，这是一个仅包含矩阵上三角部分的向量P[c]的第ij元素对应于d(x[i], x[j])。

下一步是定义合并策略，在这种情况下，该策略称为链接。 链接方法的目标是找出必须在层次结构的每个级别合并为单个群集的群集。 因此，它必须与代表群集的通用样本集一起使用。 在这种情况下，假设我们正在分析几个群集(c[a], c[b])，并且我们需要找到哪个索引a或b对应于将要合并的对。

单一和完整的联系

最简单的方法称为单个和完整链接，它们的定义如下：

单链接方法选择包含最接近的样本对的样本对（每个样本属于不同的群集）。 下图显示了此过程，其中选择了C1和C2进行合并：

单链接的例子。 选择C[1]和C[2]来合并

这种方法的主要缺点是可能同时具有很小的群集和很大的群集。 正如我们将在下一部分中看到的那样，单个链接可以使离群值保持隔离，直到存在非常高的相异度级别为止。 为了避免或减轻该问题，可以使用平均值和沃德方法。

相反，完全链接定义为：

这种链接方法的目的是使属于合并群集的最远样本之间的距离最小。 在下图中，有一个完整链接的示例，其中已选择C[1]和C[3]：

完全链接的示例。 选择C[1]和C[3]进行合并

该算法选择C[1]和C[3]为了增加内部凝聚力。 实际上，很容易理解，考虑所有可能的组合，完全链接会导致群集密度最大化。 在上图所示的示例中，如果所需的群集数为两个，则合并C[1]和C[2]或C[2]和C[3]会产生具有较小内聚的最终构型，这通常是不希望的结果。

平均链接

另一种常见的方法称为平均链接（或非加权组平均法（UPGMA））。 定义如下：

这个想法与完全链接非常相似，但是在这种情况下，考虑每个群集的平均值，并且目标是考虑所有可能的对(c[a], c[b])。 下图显示了平均链接的示例：

平均链接的示例。 选择C[1]和C[2]进行合并。 突出显示的点是平均值。

平均链接在生物信息学应用（定义层次聚类的主要环境）中特别有用。 对其属性的数学解释是不平凡的，我鼓励您查看原始论文（《一种评估系统关系的统计方法》），以获取更多详细信息。

Ward 链接

我们要讨论的最后一种方法称为 Ward 链接（以其作者命名，最初是在《用于优化目标函数的分层分组过程》中提出的。 它基于欧几里得距离，其正式定义如下：

在每个级别上，都要考虑所有聚类，并选择其中两个聚类，以最小化平方距离的总和。 该过程本身与平均链接没有太大不同，并且有可能证明合并过程会导致集群方差的减少（即，增加其内部凝聚力）。 而且，沃德的联系倾向于产生包含大约相同数量样本的群集（也就是说，与单联系相比，沃德的方法避免了小群集和非常大的群集的存在，如下一节所述）。 Ward 的链接是一种流行的默认选择，但是，为了在每种特定情况下做出正确的选择，有必要引入树状图的概念。

分析树状图

树状图是一种树数据结构，它使我们能够表示由凝聚算法或分裂算法产生的整个聚类层次结构。 想法是将样本放置在x轴上，而相异度放置在y轴上。 每当两个聚类合并时，树状图就会显示与其发生的相异程度相对应的连接。 因此，在聚集情况下，树状图始终以所有被视为群集的样本开始，然后向上移动（方向完全是常规的），直到定义了一个群集。

出于教学目的，最好显示与非常小的数据集X相对应的树状图，但是我们将要讨论的所有概念都可以应用于任何情况。 但是，对于较大的数据集，通常需要应用一些截断法以更紧凑的形式可视化整个结构。

让我们考虑一个小的数据集X，它由4高斯分布生成的12二维样本组成，平均向量的范围为(01, 1) × (-1, 1)：

from sklearn.datasets import make_blobs
nb_samples = 12
nb_centers = 4
X, Y = make_blobs(n_samples=nb_samples, n_features=2, center_box=[-1, 1], centers=nb_centers, random_state=1000)

数据集（带有标签）显示在以下屏幕截图中：

用于树状图分析的数据集

为了生成树状图（使用 SciPy），我们首先需要创建一个链接矩阵。 在这种情况下，我们选择了具有 Ward 链接的欧几里德度量标准（但是，与往常一样，我建议您使用不同的配置执行分析）：

from scipy.spatial.distance import pdist
from scipy.cluster.hierarchy import linkage
dm = pdist(X, metric='euclidean')
Z = linkage(dm, method='ward')

dm数组是一个压缩的成对距离矩阵，而Z是通过沃德方法生成的链接矩阵（linkage()函数需要method参数，该参数除其他外接受single，complete，average和ward）。 此时，我们可以生成并绘制树状图（dendrogram() 函数可以使用默认或提供的 Matplotlib axis对象自动绘制图）：

import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import dendrogram
fig, ax = plt.subplots(figsize=(12, 8))
d = dendrogram(Z, show_leaf_counts=True, leaf_font_size=14, ax=ax)
ax.set_xlabel('Samples', fontsize=14)
ax.set_yticks(np.arange(0, 6, 0.25))
plt.show()

该图显示在以下屏幕截图中：

应用于数据集的对应 Ward 链接的树状图

如前面的屏幕快照中所述，x轴表示旨在最大程度降低交叉连接风险的样本，而y轴表示相异程度。 现在让我们从底部开始分析图。 初始状态对应于被视为独立聚类的所有样本（因此相异性为空）。 向上移动，我们开始观察第一次合并。 特别地，当相异度约为 0.35 时，样本 1 和 3 被合并。

当样本 0 和 9 也合并时，第二步发生的差异略小于 0.5。 创建单个群集时，该过程一直持续到相异度约为 5.25。 现在，当相差等于 1.25 时，水平剖析树状图。 查看基础连接，我们发现聚类结构为：{6}, {7, 5, 8}, {0, 9, 4, 10}, {11}, {2 , 1, 3}。

因此，我们有五个聚类，其中两个由一个样本组成。 样本 6 和 11 是最后合并的样本，这并不奇怪。 实际上，它们之间的距离比其他所有区域都远。 在以下屏幕截图中，显示了四个不同的级别（只有包含多个样本的聚类用圆圈标记）：

通过在不同级别切割树状图而生成的群集（沃德链接）

易于理解，聚集从选择最相似的群集/样本开始，然后通过添加最近邻，直到到达树的根为止。 在我们的情况下，在相异度等于 2.0 的情况下，已检测到三个定义明确的群集。 左一个也保留在下一个剪切中，而右两个（显然更靠近）被选择合并以生成单个群集。 该过程本身很简单，不需要特别的解释。 但是，有两个重要的考虑因素。

第一个是树状图结构本身固有的。 与其他方法相反，层次聚类允许观察整个聚类树，当需要通过增加不相似度来显示流程如何演变时，此功能非常有用。 例如，产品推荐器应用无法提供有关代表用户的所需群集数量的任何信息，但是执行管理层可能会对理解合并过程的结构和演变方式感兴趣。

实际上，观察群集是如何合并的可以深入了解底层的几何，还可以发现哪些群集可能被视为较大群集的一部分。 在我们的示例中，在级别 0.5 处，我们有一个小的群集{1, 3}。 问题是“可以通过增加不相似性将哪些样本添加到该群集中？” 可以立即用{2}回答。 当然，在这种情况下，这是一个微不足道的问题，可以通过查看数据图来解决，但是对于高维数据集，如果没有树状图的支持，它可能会变得更加困难。

树状图的第二个优点是可以比较不同链接方法的行为。 使用 Ward 的方法，第一次合并发生的相异度很低，但是五个群集和三个群集之间存在较大的差距。 这是几何形状和合并策略的结果。 例如，如果我们使用单个链接（本质上非常不同）会发生什么？ 以下屏幕快照显示了相应的树状图：

与应用于数据集的单个链接相对应的树状图

结论是，树状图是不对称的，并且群集通常与单个样本或小的附聚物合并。 从右侧开始，我们可以看到样本{11}和{6}合并得很晚。 此外，当必须生成最终的单个群集时，样本{6}（可能是异常值）被合并。 通过以下屏幕快照可以更好地理解该过程：

通过在不同级别切割树状图而生成的群集（单链接）

从屏幕快照中可以看到，虽然 Ward 的方法生成包含所有样本的两个聚类，但单个链接通过将潜在异常值保持在外部来聚集级别 1.0 上的最大块。 因此，树状图还允许定义聚合语义，这在心理学和社会学方面非常有用。 尽管 Ward 的链接与其他对称算法非常相似，但单个链接具有逐步显示的方式，显示了对逐步构建的聚类的潜在偏好，从而避免了相异性方面的巨大差距。

最后，有趣的是，尽管 Ward 的链接通过在级别 3.0 处切断树状图产生了潜在的最佳群集数（三个），但单个链接从未达到这样的配置（因为群集{6}仅在最后一步中合并。 该效果与最大分离和最大内聚的双重原理紧密相关。 沃德的联系往往会很快找到最具凝聚力和最独立的集群。 当相异性差距超过预定义的阈值时（当然，当达到所需的群集数时），它可以切割树状图，而其他链接则需要不同的方法，有时会产生不希望的最终配置。

考虑到问题的性质，我始终鼓励您测试所有链接方法的行为，并为某些示例场景（例如，根据教育水平，居住地， 和收入）。 这是提高认识并提高提供流程语义解释的能力的最佳方法（这是任何聚类过程的基本目标）。

作为表现指标的 Cophenetic 相关性

可以使用前面各章中介绍的任何方法来评估层次集群表现。 但是，在这种特定情况下，可以采用特定措施（不需要基本事实）。 给定一个近似矩阵P和一个链接L，几个样本x[i]和x[j] ∈ X始终分配给特定层次级别的同一群集。 当然，重要的是要记住，在团聚的情况下，我们从n个不同的群集开始，最后以一个等于X的单个群集结束。 此外，由于两个合并的群集成为一个群集，因此属于一个群集的两个样本将始终继续属于同一扩充的群集，直到该过程结束。

考虑到上一节中显示的第一个树状图，样本{1}和{3}立即合并； 然后添加样本{2}，然后添加{11}。 此时，整个群集将与另一个块合并（包含样本{0}, {9}, {4}, {10}）。 在最后一级，将剩余的样本合并以形成单个最终群集。 因此，命名相似度DL[0]，DL[1]，…和DL[k]，样本{1}和{3}在DL[1]处开始属于同一群集。 例如，在DL[6]的同一群集中发现{2}和{1}。

此时，我们可以将DL[ij]定义为x[i]和x[j]首次属于同一群集，并且将以下n×n对称矩阵作为CP：

换句话说，CP[ij]元素是观察同一群集中x[i]和x[j]所需的最小差异。 可以证明CP[ij]是x[i]和x[j]之间的距离度量; 因此，CP与P类似，并且具有与邻近矩阵相同的属性（例如，所有对角元素为空）。 特别是，我们对它们的相关性感兴趣（在-1和1范围内标准化）。 这样的值（Cophenetic 系数（CPC）表示P和CP之间的一致性程度，并且可以很容易地计算出， 如以下等式所示。

由于P和CP均为n×n对称矩阵且对角元素为空，因此可以仅考虑下三角部分（不包括对角线，表示为Tril(·)），包含n (n-1) / 2值。 因此，平均值如下：

标准化平方和值如下：

因此，归一化的同位相关仅等于以下内容：

前面的方程式基于以下假设：如果x[i]，x[j]和x[p]的距离，例如d(x[i], x[j]) < d(x[i], x[p])，可以合理预期x[i]和x[j]在x[i]和x[p]之前合并在同一群集中（即，对应于x[i]和x[j]的合并的差异程度低于x[i]和x[p]的合并）。 因此，CPC → 1表示链接生成了一个最佳层次结构，该层次结构反映了基础几何结构。 另一方面，CPC → -1表示完全不同意，并且潜在的聚类结果与几何形状不一致。 毋庸置疑，给定一个问题，我们的目标是找到一个最大化CPC的指标和链接。

考虑到第 3 章，“高级聚类”中描述的示例，我们可以使用 SciPy 函数cophenet计算与不同链接（假设欧几里得距离）相对应的同位矩阵和 CPC 。 此函数需要将链接矩阵作为第一个参数，将接近度矩阵作为第二个参数，并返回同义矩阵和 CPC（dm变量是先前计算出的压缩接近度矩阵）：

from scipy.cluster.hierarchy import linkage, cophenet
cpc, cp = cophenet(linkage(dm, method='ward'), dm)
print('CPC Ward\'s linkage: {:.3f}'.format(cpc))
cpc, cp = cophenet(linkage(dm, method='single'), dm)
print('CPC Single linkage: {:.3f}'.format(cpc))
cpc, cp = cophenet(linkage(dm, method='complete'), dm)
print('CPC Complete linkage: {:.3f}'.format(cpc))
cpc, cp = cophenet(linkage(dm, method='average'), dm)
print('CPC Average linkage: {:.3f}'.format(cpc))

此代码段的输出如下所示：

CPC Ward's linkage: 0.775
CPC Single linkage: 0.771
CPC Complete linkage: 0.779
CPC Average linkage: 0.794

这些值非常接近，表明所有链接都产生了很好的结果（即使由于两个异常值的存在它们并不是最优的）。 但是，如果需要选择一种方法，则平均链接是最准确的方法，如果没有特殊原因，则应优先使用其他链接。

同类关系是层次聚类特有的评估指标，通常可提供可靠的结果。 但是，当几何形状更复杂时，CPC 值可能会产生误导并导致次佳配置。 因此，我总是建议也使用其他指标（例如，轮廓分数或调整后的 Rand 分数），以便仔细检查表现并做出最合适的选择。

水厂数据集上的凝聚聚类

现在，让我们考虑一个更大的数据集上的更详细的问题（在本章开头的“技术要求”部分中提供了下载说明），其中包含 527 个样本，其中有 38 个化学和物理变量描述了水处理厂的状态。 正如同一作者（ Bejar，Cortes 和 Poch）所述，该域的结构较差，需要仔细分析。 同时，我们的目标是使用不可知论的方法找到最佳的聚类。 换句话说，我们将不考虑语义标记过程（需要领域专家），而仅考虑数据集的几何结构以及通过聚集算法发现的关系。

下载后，可以使用 Pandas 加载 CSV 文件（称为water-treatment.data）（当然，必须更改项目才能指向文件的确切位置）。 第一列是与特定工厂相关的索引，而所有其他值都是数字，可以转换为float64。 缺少的值用'?' 字符表示，并且由于我们没有其他信息，因此将每个属性的均值设置为：

import pandas as pd
data_path = '<DATA_PATH>/water-treatment.data'
df = pd.read_csv(data_path, header=None, index_col=0, na_values='?').astype(np.float64)
df.fillna(df.mean(), inplace=True)

由于单个变量的大小存在很大差异（我邀请读者使用 DataFrame 上的describe函数检查此语句），因此最好在范围(-1, 1)内对其进行标准化，以保持原始差异：

from sklearn.preprocessing import StandardScaler
ss = StandardScaler(with_std=False)
sdf = ss.fit_transform(df)

在这一点上，像往常一样，我们可以使用 t-SNE 算法将数据集投影到二维空间上：

from sklearn.manifold import TSNE
tsne = TSNE(n_components=2, perplexity=10, random_state=1000)
data_tsne = tsne.fit_transform(sdf)
df_tsne = pd.DataFrame(data_tsne, columns=['x', 'y'], index=df.index)
dff = pd.concat([df, df_tsne], axis=1)

生成的绘图显示在以下屏幕截图中：

水处理厂数据集的 t-SNE 图

该图显示了潜在的非凸几何形状，其中有许多小的小岛（密集区域），这些小岛由空白空间隔开。 但是，如果没有任何域信息，则很难确定哪些斑点可以被视为同一群集的一部分。 我们可以决定施加的唯一伪约束（考虑到所有工厂都以相似的方式运行）是具有中等或较小的最终群集数。 因此，假设欧氏距离并使用 scikit-learn AgglomerativeClustering类，我们可以计算所有链接以及4，6，8和 10集群数：

import numpy as np
from sklearn.cluster import AgglomerativeClustering
from sklearn.metrics import silhouette_score
from scipy.spatial.distance import pdist
from scipy.cluster.hierarchy import linkage, cophenet
nb_clusters = [4, 6, 8, 10]
linkages = ['single', 'complete', 'ward', 'average']
cpcs = np.zeros(shape=(len(linkages), len(nb_clusters)))
silhouette_scores = np.zeros(shape=(len(linkages), len(nb_clusters)))
for i, l in enumerate(linkages):
    for j, nbc in enumerate(nb_clusters): 
        dm = pdist(sdf, metric='minkowski', p=2)
        Z = linkage(dm, method=l)
        cpc, _ = cophenet(Z, dm)
        cpcs[i, j] = cpc
        ag = AgglomerativeClustering(n_clusters=nbc, affinity='euclidean', linkage=l)
        Y_pred = ag.fit_predict(sdf)
        sls = silhouette_score(sdf, Y_pred, random_state=1000)
        silhouette_scores[i, j] = sls

相应的图显示在以下屏幕截图中：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-E5Hxkl3W-1681652575118)(https://gitcode.net/apachecn/apachecn-dl-zh/-/raw/master/docs/handson-unsup-learn-py/img/22e87346-d2f3-4423-b75b-c700146d7550.png)]

不同数量的群集和四种链接方法的同位相关（左）和轮廓分数（右）

首先要考虑的一点是，对于完全和平均链接而言，同义相关可以合理地接受，而对于单个链接而言，它太低了。 考虑到轮廓分数，通过单联动和四个群集可实现最大值（约 0.6）。 该结果表明，即使分层算法产生了次优的配置，也可以用中等或高水平的内部凝聚力分离四个区域。

如上一节所述，同位相关有时可能会引起误解，在这种情况下，我们可以得出结论，如果潜在群集的理论数目为 4，则使用单连接是最佳选择。 但是，所有其他图均显示对应于完整链接的最大值（单个图的最小值）。 因此，第一个要回答的问题是：我们是否甚至需要集群？ 在此示例中，我们假设许多工厂以非常标准的方式运行（差异由许多样本共享），但是也可能存在某些特定情况（不适当的离群值）表现出截然不同的行为。

这种假设在许多情况下都是现实的，并且可能是由于创新或实验过程，资源不足，测量过程中的内部问题等导致的。 领域专家可以确认或拒绝我们的假设，但是，由于这是一个通用示例，我们可以决定保留八个具有完全链接的聚类（轮廓分数约为 0.5）。 该值表示存在重叠，但是考虑到数据集的维数和非凸性，在许多实际情况下可以接受。

在这一点上，我们还可以分析截断为 80 片叶子的树状图（可以通过设置trucate_mode='lastp' 参数和p=80来实现），以避免间隔太小且难以区分 （但是，您可以删除此约束并提高分辨率）：

具有欧几里德度量标准和完全链接的水处理厂数据集的树状图

如我们所见，集聚过程不是均匀的。 在过程开始时，相异度的增加非常缓慢，但是在对应于大约 10,000 的值之后，跃变变大。 查看 t-SNE 图，可以理解非凸性的影响对非常大的聚类具有更强的影响，因为密度降低并且隐含地差异增大。 显而易见，很少数量的群集（例如 1、2 或 3）的特征是内部差异非常大，凝聚力非常低。

此外，树状图显示在大约 17,000 的水平上有两个主要的不均匀聚集，因此我们可以推断出粗粒度分析突出显示了主要行为的存在（从顶部观察图），以及由少量的工厂产生的次要行为。 特别是，较小的组非常稳定，因为它将以大约 50,000 的相异度级别合并到最终的单个群集中。 因此，我们应该期待伪异常值的存在，这些伪异常值被分组为更多的孤立区域（t-SNE 图也证实了这一点）。

切割级别在 4,000÷6,000（对应于大约八个群集）的范围内，较大的块比较小的块更密集。 换句话说，离群值群集将包含比其他群集少得多的样本。 这不足为奇，因为，如在专门针对树状图的“分析树状图”部分中所讨论的那样，最远的群集通常在完全链接中合并得很晚。

至此，我们终于可以执行聚类并检查结果了。 Scikit-learn 的实现不会计算整个树状图，而是会在达到所需群集数时停止该过程（除非compute_full_tree 参数不是True）：

import pandas as pd
from sklearn.cluster import AgglomerativeClustering
ag = AgglomerativeClustering(n_clusters=8, affinity='euclidean', linkage='complete')
Y_pred = ag.fit_predict(sdf)
df_pred = pd.Series(Y_pred, name='Cluster', index=df.index)
pdff = pd.concat([dff, df_pred], axis=1)

最终图显示在以下屏幕截图中：

水处理厂数据集的聚类结果（八个群集）

Python 无监督学习实用指南：1~5（5）https://developer.aliyun.com/article/1426885