大数据的聚类层次化缩放
大数据聚类层次缩放
学习如何使用递归凝聚聚类（RAC）来对大型数据集进行层次聚类
导言
凝聚聚类是数据科学中最好的聚类工具之一，但传统的实现无法适用于大型数据集。
在本文中，我将带您了解一些凝聚聚类的背景知识，介绍基于2021年谷歌研究的递归凝聚聚类（RAC），以及RAC++和scikit-learn的AgglomerativeClustering之间的运行时比较，最后简要解释RAC背后的理论。
凝聚聚类的背景
在数据科学中，对无标签数据进行聚类经常非常有用。从搜索引擎结果的分组，到基因型分类，到银行异常检测，聚类是数据科学家工具包中必不可少的一部分。
凝聚聚类是数据科学中最流行的聚类方法之一，并且有很好的原因，它：
✅ 使用简单，几乎不需要参数调整✅ 创建有意义的分类法✅ 在高维数据上表现良好✅ 不需要事先知道聚类的数量✅ 每次创建相同的聚类
相比之下，基于分区的方法（如K-Means）需要数据科学家猜测聚类的数量，非常流行的基于密度的方法DBSCAN需要一些关于密度计算半径（epsilon）和最小邻居数的参数，而高斯混合模型对底层聚类数据分布做出了强大的假设。
对于凝聚聚类，您只需要指定一个距离度量。
在高层次上，凝聚聚类遵循以下算法：
确定所有聚类对之间的聚类距离（每个聚类起始时都是一个单点）合并距离最近的两个聚类重复
结果是一个美丽的树状图，可以根据领域专业知识进行分割。
在生物学和自然语言处理等领域，簇（细胞、基因或单词）自然遵循层次关系。因此，凝聚聚类可以更自然和数据驱动地选择最终的聚类截断点。
下图是著名的Iris数据集的示例凝聚聚类。
那么为什么不在每个无监督分类问题中都使用凝聚聚类呢？
❌ 随着数据集的增大，凝聚聚类的运行时间变得非常糟糕。
不幸的是，传统的凝聚聚类无法扩展。运行时间复杂度为O(n³)或O(n²log(n))（如果使用最小堆实现）。更糟糕的是，凝聚聚类在单核上顺序运行，无法利用计算资源进行扩展。
在自然语言处理领域，凝聚聚类是表现最好的…对于小型数据集。
递归凝聚聚类（RAC）
递归凝聚聚类（RAC）是谷歌提出的一种方法，将传统凝聚聚类的优势扩展到更大的数据集。
RAC降低了运行时复杂度，同时并行化操作以利用多核架构。尽管进行了这些优化，当数据完全连接时，RAC产生与传统凝聚聚类完全相同的结果（见下文）。
注意：完全连接的数据意味着可以计算任意两点之间的距离。非完全连接的数据集具有连接约束（通常以链接矩阵的形式提供），其中一些点被认为是断开的。
即使在具有连接约束的情况下（数据不完全连接），RAC和凝聚聚类仍然通常是相同的，就像上面第二个瑞士卷数据集的示例中所示。
然而，当可能的聚类非常少时，可能会出现较大的差异。噪声月亮数据集就是一个很好的例子:
RAC++在比scikit-learn更大的数据集上具有可扩展性
我们可以将RAC++（互递归聚类的实现）与其对应的scikit-learn中的凝聚聚类进行比较。
让我们生成一些具有25个维度的示例数据，并测试使用racplusplus.rac对不同大小的数据集进行凝聚聚类所需的时间，与使用sklearn.cluster.AgglomerativeClustering进行比较，数据集的大小从1,000到64,000个点不等。
注意：我使用连接矩阵来限制内存消耗。
import numpy as npimport racplusplusfrom sklearn.cluster import AgglomerativeClusteringimport timepoints = [1000, 2000, 4000, 6000, 10000, 14000, 18000, 22000, 26000, 32000, 64000]for point_no in points: X = np.random.random((point_no, 25)) distance_threshold = .17 knn = kneighbors_graph(X, 30, include_self=False) # Matrix must be symmetric - done internally in scikit-learn symmetric = knn + knn.T start = time.time() model = AgglomerativeClustering( linkage="average", connectivity=knn, n_clusters=None, distance_threshold=distance_threshold, metric='cosine' )sklearn_times.append(time.time() - start)start = time.time()rac_labels = racplusplus.rac( X, distance_threshold, symmetric, batch_size=1000, no_cores=8, metric="cosine" )rac_times.append(time.time() - start)下面是每个数据集大小的运行时间结果的图形表示：
如我们所见，RAC++和传统的凝聚聚类在运行时间上存在显著差异。
在略过30k个点时，RAC++快了约100倍！更重要的是，scikit-learn的凝聚聚类在大约35,000个点时达到了时间限制，而RAC++在达到合理的时间限制之前可以扩展到数十万个点。
RAC++可以扩展到高维数据
我们还可以比较RAC++与其传统对应物在高维数据上的扩展能力。
生成聚类与维度之间的时间对比（3000个点）
对于3000个点，我们可以看到传统的凝聚式聚类更快，但它的时间复杂度是线性的，而 RAC++ 几乎是恒定的。在自然语言处理领域，使用768或1536维的嵌入已经成为常态，因此根据需求调整维度尤为重要。
RAC++ 有更好的运行时间
Google 的研究人员证明 RAC 的运行时间为 O(nk)，其中 k 是连接约束，n 是点的数量 —— 是一个线性运行时间。然而，这不包括初始距离矩阵的计算，其时间复杂度为 O(n²) —— 是一个二次运行时间。
我们的结果，使用恒定的30个邻居连接约束，确实证实了一个二次运行时间：
+ — — — — — — -+ — — — — — +| 数据点 | 秒 |+ - - - - - - -+ - - - - - +| 2000 | 0.051 || 4000 | 0.125 || 6000 | 0.245 || 10000 | 0.560 || 14000 | 1.013 || 18000 | 1.842 || 22000 | 2.800 || 26000 | 3.687 || 32000 | 5.590 || 64000 | 22.499 |+ - - - - - - -+ - - - - - +数据点翻倍需要4倍的时间增加。
二次运行时间限制了 RAC++ 在数据集变得非常大时的性能表现，不过，这个运行时间已经比传统的 O(n³) 或优化后的小顶堆 O(n²log(n)) 运行时间有了很大的改进。
注意：RAC++ 的开发人员正在努力将距离矩阵作为参数传递，这将使 RAC++ 的运行时间变为线性。
RAC 的工作原理
RAC++ 为什么如此快速？我们可以将其基本算法简化为以下几个步骤：
将聚类配对为互相最近邻合并聚类对更新最近邻
请注意，这与传统的凝聚式聚类算法的唯一区别在于，我们确保将互相最近邻配对在一起。这就是 Reciprocal Agglomerative Clustering (RAC) 的名字的由来。正如你将看到的，这种互相配对使我们能够并行化凝聚式聚类中最耗时的步骤。
将聚类配对为互相最近邻
首先，我们循环遍历以找到具有互相最近邻的聚类，也就是它们彼此之间的最近邻（请记住，距离可能是有方向的！）。
合并聚类对
RAC 是可并行化的，因为互相最近邻的合并顺序无关紧要，只要链接方法是可归约的。
链接方法是根据每个聚类中包含的点之间的成对距离确定两个聚类之间的距离的函数。可归约的链接方法保证在合并后，新的聚类不会比任何其他聚类更接近。
幸运的是，最流行的四种连接方法是可简化的：
- 单链接 – 最小距离
- 平均链接 – 距离的平均值
- 完全链接 – 最大距离
- 沃德链接 – 最小化方差
由于我们知道我们确定的互补对是彼此的最近邻，而且我们知道可简化的连接合并永远不会使新合并的聚类更接近另一个聚类，因此我们可以一次性安全地合并所有互补的最近邻对。每个最近邻对可以放入可用的线程中，根据连接方法进行合并。
我们能够同时合并互补的最近邻是很棒的，因为合并聚类是计算上最昂贵的步骤！
更新最近邻
使用可简化的连接，在合并后更新最近邻的顺序也无关紧要。因此，通过巧妙的设计，我们也可以并行更新相关的邻居。
结论
通过几个测试数据集，我们已经证明RAC++在完全连接的数据集上产生与传统的聚合聚类（即sklearn）完全相同的结果，并且运行时间更好。通过理解可简化的连接度量和基本的并行编程，我们可以理解使RAC++速度更快的逻辑。
要完全理解（并证明）RAC++所采用的算法是基于哪项开放源码的Google研究，请查看原始的Google研究。
未来
Porter Hunley开始构建RAC++，以通过精调的BERT嵌入为临床术语终点创建分类法。每个医学嵌入都有768个维度，经过他尝试的众多聚类算法中，只有聚合聚类给出了好的结果。
所有其他的高规模聚类方法都需要降低维度才能得到任何有意义的结果。可惜的是，没有绝对可靠的降维方法 – 您将始终丢失信息。
在发现Google关于RAC的研究后，Porter决定构建一个自定义的开源聚类实现，以支持他的临床术语聚类研究。Porter领导了开发工作，我与他一起开发了部分RAC，尤其是将C++实现包装在Python中，优化运行时间并打包软件以进行分发。
RAC++使得许多使用传统聚合聚类速度太慢的聚类应用成为可能，并且最终将可扩展到数百万个数据点。
虽然RAC++已经可以用于聚类大型数据集，但还有改进空间… RAC++仍在开发中 – 请贡献！
贡献作者：
- Porter Hunley，Daceflow.ai的高级软件工程师：github
- Daniel Frees，斯坦福大学的MS统计与数据科学学生，IBM的数据科学家：github
GitHub – porterehunley/RACplusplus：可递归聚合的高性能实现…
