譯者 | 朱先忠
審校 | 重樓
簡介
層次聚類算法（Agglomerative Clustering）是數(shù)據(jù)科學(xué)中最好的聚類工具之一，但傳統(tǒng)的實現(xiàn)無法擴(kuò)展到大型數(shù)據(jù)集領(lǐng)域。
在這篇文章中，我將帶你了解層次聚類算法的一些背景，基于谷歌2021年的研究介紹交互式層次聚類（RAC）算法、RAC++算法和Scikit Learn的層次聚類算法的運(yùn)行時效果比較，最后將簡要探討一下RAC算法背后的理論支持。
層次聚類算法的背景
在數(shù)據(jù)科學(xué)領(lǐng)域，對未標(biāo)記的數(shù)據(jù)進(jìn)行聚類通常是非常有用的。從搜索引擎結(jié)果的分組到基因型分類，再到銀行異常檢測，聚類已經(jīng)成為數(shù)據(jù)科學(xué)家們的工具包中必不可少的一部分。
層次聚類是數(shù)據(jù)科學(xué)中最流行的聚類方法之一，這是有充分的理由的：
- 易于使用，幾乎不需要參數(shù)調(diào)整
- 創(chuàng)建有意義的分類法
- 適用于高維數(shù)據(jù)
- 不需要事先知道簇的數(shù)量
- 每次創(chuàng)建相同的簇
相比之下，像K-Means這樣的劃分方法則需要數(shù)據(jù)科學(xué)家猜測聚類的數(shù)量，非常流行的基于密度的方法DBSCAN則需要圍繞密度計算半徑（ε）和最小鄰域大小的一些參數(shù)，而高斯混合模型對潛在的聚類數(shù)據(jù)分布做出了強(qiáng)有力的假設(shè)。
對于層次聚類算法，您只需要指定一個距離度量指標(biāo)即可使用。
從高級視角來看，層次聚類遵循以下算法：
- 確定所有簇對之間的簇距離（每個簇從一個點(diǎn)開始）；
- 合并彼此最接近的兩個群集；
- 重復(fù)上述步驟。
結(jié)果是：生成一個美麗的樹狀圖，然后可以根據(jù)領(lǐng)域?qū)I(yè)知識進(jìn)行劃分應(yīng)用。
在生物學(xué)和自然語言處理等領(lǐng)域，（細(xì)胞、基因或單詞的）簇自然遵循等級關(guān)系。因此，層次聚類能夠?qū)崿F(xiàn)對最終聚類截止點(diǎn)的更自然和數(shù)據(jù)驅(qū)動的選擇。
下圖是著名的鳶尾花（Iris）數(shù)據(jù)集的層次聚類結(jié)果示例。
通過萼片長度和萼片寬度對著名的鳶尾花數(shù)據(jù)集進(jìn)行聚類（本圖表由合著作者Porter Hunley制作）
那么，為什么不對每個無監(jiān)督分類問題都使用層次聚類算法呢？答案在于：
隨著數(shù)據(jù)集大小的增加，層次聚類算法的運(yùn)行時間表現(xiàn)得非常糟糕。
另一方面，不幸的是，傳統(tǒng)的層次聚類算法還沒有得到大規(guī)模的應(yīng)用。如果使用最小堆結(jié)構(gòu)實現(xiàn)的話，則運(yùn)行時復(fù)雜度為O（n3）或O（n2log（n））。更糟糕的是，層次聚類算法在單核的CPU上按順序運(yùn)行，無法通過計算進(jìn)行擴(kuò)展。
結(jié)論是：在自然語言處理領(lǐng)域，層次聚類算法是小型數(shù)據(jù)集的最佳表現(xiàn)算法。
交互式層次聚類算法
交互式層次聚類（RAC）算法是谷歌提出的一種方法，旨在將傳統(tǒng)型層次聚類算法的優(yōu)勢擴(kuò)展到更大的數(shù)據(jù)集。
RAC算法降低了運(yùn)行時的復(fù)雜性，同時還將操作并行化以利用多核CPU架構(gòu)。盡管進(jìn)行了這些優(yōu)化，但當(dāng)數(shù)據(jù)完全連接時，RAC產(chǎn)生的結(jié)果與傳統(tǒng)的層次聚類算法卻完全相同（見下文）。
注意：完全連接數(shù)據(jù)意味著，可以計算任何一對點(diǎn)之間的距離度量。非完全連接的數(shù)據(jù)集則具有連接約束（通常以連接矩陣的形式提供），其中一些點(diǎn)被認(rèn)為是斷開的。請參考下面的對比圖示。
當(dāng)數(shù)據(jù)完全連接時，RAC會產(chǎn)生與傳統(tǒng)層次群集完全相同的結(jié)果?。ㄉ蠄D），并且通常在連接約束的情況下繼續(xù)這樣做（下圖）（圖表由合著作者Porter Hunley制作）
即使存在連接限制（未完全連接的數(shù)據(jù)），RAC和層次聚類通常仍然相同，如上面的第二個Swiss Roll數(shù)據(jù)集示例所示。
然而，當(dāng)可能的簇非常少時，可能會出現(xiàn)巨大的差異。這方面，Noisy Moons數(shù)據(jù)集就是一個很好的例子：
RAC算法和Sklearn算法之間的計算結(jié)果表現(xiàn)出不一致性（本圖表由合著作者Porter Hunley制作）
RAC++算法可擴(kuò)展到比Scikit-learn更大的數(shù)據(jù)集
我們可以在Scikit-learn中將RAC++算法（交互式層次聚類的一種實現(xiàn)）算法與其對應(yīng)的層次聚類算法進(jìn)行比較。
現(xiàn)在，不妨讓我們生成一些具有25個維度的示例數(shù)據(jù)，并使用racplusplus.rac與sklearn.cluster.AglognitiveClustering測試層次聚類需要多長時間，應(yīng)用于大小從1000到64000點(diǎn)的數(shù)據(jù)集。
注意：下面代碼中，我使用連接矩陣來限制內(nèi)存消耗。
import numpy as np
import racplusplus
from sklearn.cluster import AgglomerativeClustering
import time
points = [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)
#矩陣必須是對稱的：在Scikit-learn庫的內(nèi)部完成
symmetric = knn + knn.T
start = time.time()
model = AgglomerativeClustering(
linkage="average",
cnotallow=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)以下給出的是每個大小數(shù)據(jù)集的運(yùn)行時結(jié)果圖：
與racplusplus相比，當(dāng)使用sklearn時，大型數(shù)據(jù)集的運(yùn)行時呈爆炸式增長變化趨勢（本圖表由合著作者Porter Hunley制作）
正如我們從上圖中所看到的，RAC++算法和傳統(tǒng)的層次聚類算法在運(yùn)行時有著巨大的差異。
在剛剛超過30k的點(diǎn)上，RAC++算法的速度大約是原來的100倍！更不可能的是，Scikit-learn的層次聚類達(dá)到了約3.5萬個點(diǎn)的時間限制，而RAC++算法在達(dá)到合理的時間限制時可以擴(kuò)展到數(shù)十萬個點(diǎn)。
RAC++算法可以擴(kuò)展到高維度
我們還可以比較RAC++算法在高維數(shù)據(jù)與傳統(tǒng)數(shù)據(jù)之間的縮放情況。
通過RAC++算法和sklearn的數(shù)據(jù)維度擴(kuò)展時間復(fù)雜性（本圖由合著作者Porter Hunley繪制）
上圖展示了生成3000點(diǎn)的聚類與維度所花費(fèi)的時間變化規(guī)律。
對于3000點(diǎn)的數(shù)據(jù)量來說，我們可以看到傳統(tǒng)的層次聚類更快，但它是線性的，而RAC++算法表現(xiàn)得幾乎是恒定的。如今，使用768或1536維嵌入已經(jīng)成為NLP領(lǐng)域的常規(guī)指標(biāo)；因此，縮放維度以滿足這些要求是很重要的。
RAC++算法表現(xiàn)出具有更好的運(yùn)行時性能
谷歌的研究人員證明，RAC算法的運(yùn)行時間為O（nk），其中k表示連接約束，而n代表點(diǎn)的數(shù)量——線性運(yùn)行時間。然而，這不包括初始距離矩陣的計算，即O（n2）——二次運(yùn)行時。
我們的結(jié)果，運(yùn)行恒定的30個鄰連接約束情況下，確實證實了將使用O（n2）復(fù)雜度的運(yùn)行時狀態(tài)：
+ — — — — — — -+ — — — — — +
| Data points | Seconds |
+ - - - - - - -+ - - - - - +
| 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 |
+ - - - - - - -+ - - - - - +將數(shù)據(jù)點(diǎn)增加一倍對應(yīng)于時間的4倍。
二次運(yùn)行時限制了RAC++算法在數(shù)據(jù)集變得真正龐大時的性能，然而，與傳統(tǒng)的O（n3）或最小堆優(yōu)化O（n2log（n））運(yùn)行時相比，該運(yùn)行時已經(jīng)有了很大的改進(jìn)。
注意：RAC++算法的開發(fā)人員正在將距離矩陣作為一個參數(shù)進(jìn)行傳遞，該參數(shù)將為RAC++算法提供線性運(yùn)行時間。
RAC算法的工作原理
為什么RAC++算法更為快速呢？我們可以將底層算法簡化為如下幾個步驟：
- 將簇與交互的最近鄰配對
- 合并成對的簇
- 更新鄰接簇
注意，這與傳統(tǒng)的層次聚類算法之間的唯一區(qū)別是，我們確保將交互最近鄰的簇配對在一起。這就是交互層次聚類（RAC）這個名稱的由來。正如您將看到的，這種交互配對使我們能夠并行化層次聚類中計算成本最高的步驟。
將簇與交互最近鄰配對
首先，我們循環(huán)尋找具有交互最近鄰的簇，這意味著它們的最近鄰是彼此（記住，距離可以是定向的?。?。
識別交互最近鄰簇（本圖由合著作者Porter Hunley繪制）
合并成對的簇
RAC算法是可并行執(zhí)行的，因為只要連接方法是可還原的，交互最近鄰的合并順序無關(guān)緊要。
連接方法是根據(jù)每個聚類中包含的點(diǎn)之間的成對距離來確定兩個聚類之間距離的函數(shù)?？蛇€原連接方法保證新合并的簇在合并后不會更接近任何其他簇。
如果使用可還原連接，則ab_c將不會比ac或bc更接近（此圖由合著作者Porter Hunley繪制）
幸運(yùn)的是，四種最流行的連接方法都是可還原的：
- 單連接——最小距離
- 平均連接——距離的平均值
- 完全連接——最大距離
- 離差平方和法連接——最小方差
4種可還原連接方法的可視化表示（我本人繪制，靈感來自http://www.saedsayad.com/clustering_hierarchical.htm）
由于我們知道我們識別的交互對是彼此的最近鄰居，并且我們知道可還原連接合并永遠(yuǎn)不會使新合并的簇更接近另一個簇，因此我們可以安全地將所有交互最近鄰居對同時合并在一起。每個最近鄰居對可以被放置到一個可用線程中，以便根據(jù)連接方法進(jìn)行合并。
我們可以同時合并交互最近的鄰居，這一事實非常棒，因為合并簇是計算成本最高的步驟！
可視化準(zhǔn)備合并的簇（本圖由合著作者Porter Hunley繪制）
更新最近鄰簇
對于可還原連接，合并后更新最近鄰的順序也無關(guān)緊要。因此，通過一些巧妙的設(shè)計，我們也可以并行地更新相關(guān)的鄰居。
在合并后識別新的最近鄰簇（本圖片由合著作者Porter Hunley繪制）
結(jié)論
通過一些測試數(shù)據(jù)集，我們已經(jīng)表明，對于完全連接的數(shù)據(jù)集，RAC++算法在更好的運(yùn)行時產(chǎn)生與傳統(tǒng)的層次聚類算法（即sklearn中所提供的）完全相同的結(jié)果。通過對可還原連接度量指標(biāo)的解釋和對并行編程支持的基本分析，我們最終理解了使RAC++算法更快的邏輯。
為了更完整地理解（和證明）RAC++算法在開源包中所采用的算法，有興趣的讀者可以查看它所基于的谷歌原始研究成果。
未來的工作
目前，Porter Hunley已經(jīng)開始構(gòu)建RAC++算法，努力為通過微調(diào)BERT嵌入產(chǎn)生的臨床術(shù)語端點(diǎn)創(chuàng)建分類法支持。這些醫(yī)學(xué)嵌入中的每一個都有768個維度，在他嘗試的許多聚類算法中，只有層次聚類算法給出了良好的結(jié)果。
所有其他的高規(guī)模聚類方法都需要降維才能給出任何連貫的結(jié)果。不幸的是，當(dāng)前還不存在一種很有把握的方法用于降低維度——你總是會丟失一些信息。
在發(fā)現(xiàn)谷歌圍繞RAC的研究成果后，波特決定構(gòu)建一個自定義的開源簇實現(xiàn)，以支持他的臨床術(shù)語簇研究。Porter負(fù)責(zé)開發(fā)，我和他共同開發(fā)了RAC算法的一些部分，特別是在python中封裝C++實現(xiàn)，優(yōu)化運(yùn)行時，以及打包軟件以供分發(fā)方面。
總之，RAC++算法支持大量簇應(yīng)用程序，這些應(yīng)用程序使用傳統(tǒng)的層次聚類表現(xiàn)得太慢，最終將擴(kuò)展到數(shù)百萬個數(shù)據(jù)點(diǎn)。
最后，盡管RAC++算法現(xiàn)在已經(jīng)可以用于簇式大型數(shù)據(jù)集，但仍存在不少有待改進(jìn)之處……RAC++算法仍在開發(fā)中！
本文特約作者：
- Porter Hunley，Daceflow.ai高級軟件工程師：他的GitHub代碼倉庫是https://github.com/porterehunley
- Daniel Frees，斯坦福大學(xué)統(tǒng)計與數(shù)據(jù)科學(xué)碩士生，IBM數(shù)據(jù)科學(xué)家：他的github代碼倉庫是https://github.com/danielfrees
注：GitHub——porterehunley/RAPlusplus：交互聚集的高性能實現(xiàn)……
譯者介紹
朱先忠，51CTO社區(qū)編輯，51CTO專家博客、講師，濰坊一所高校計算機(jī)教師，自由編程界老兵一枚。
原文標(biāo)題：Scaling Agglomerative Clustering for Big Data，作者：Daniel Frees
