ビッグデータのための階層的クラスタリングのスケーリング

ビッグデータの階層的クラスタリングのスケーリング

大規模データセットの階層的クラスタリングにReciprocal Agglomerative Clustering（RAC）を使用する方法を学びましょう

イントロダクション

アグロメラティブクラスタリングは、データサイエンスで最も優れたクラスタリングツールの一つですが、従来の実装は大規模データセットには対応できません。

この記事では、アグロメラティブクラスタリングの背景、Googleの2021年の研究に基づいたReciprocal Agglomerative Clustering（RAC）の紹介、RAC++とscikit-learnのAgglomerativeClusteringのランタイム比較、およびRACの理論の簡単な説明をご紹介します。

アグロメラティブクラスタリングの背景

データサイエンスでは、ラベルのないデータをクラスタリングすることがよくあります。検索エンジンの結果のグルーピングから遺伝子型の分類、銀行の異常検出まで、クラスタリングはデータサイエンティストのツールの重要な一部です。

アグロメラティブクラスタリングは、データサイエンスで最も人気のあるクラスタリング手法の一つであり、その理由は以下の通りです：

• EDIとは何ですか？電子データ交換について
• 「Google CloudとNVIDIAが協力を更に進展させる」
• 「AIと倫理の架け橋：医療実施における包括的な解決策」

✅ パラメータの微調整がほとんど不要で簡単に使用できる✅ 有意義なタクソノミを作成する✅ 高次元データでもうまく機能する✅ クラスタの数を事前に知る必要がない✅ 毎回同じクラスタを作成する

これに対して、K-Meansなどの分割手法ではデータサイエンティストがクラスタの数を推測する必要があり、非常に人気のある密度ベースの手法であるDBSCANでは密度計算半径（イプシロン）と最小近傍サイズに関するいくつかのパラメータが必要であり、ガウス混合モデルはクラスタデータ分布について強い仮定を行います。

アグロメラティブクラスタリングでは、指定する必要があるのは距離計量です。

アグロメラティブクラスタリングは、以下のアルゴリズムに従います：

1. すべてのクラスタのペア間のクラスタ距離を特定する（各クラスタは単一の点から始まる）
2. 最も近い2つのクラスタを結合する
3. 繰り返す

結果は、ドメインの専門知識に基づいて分割できる美しいデンドログラムです。

生物学や自然言語処理などの分野では、クラスタ（細胞、遺伝子、または単語）は自然な階層的関係に従います。したがって、アグロメラティブクラスタリングは最終的なクラスタリングのカットオフをより自然でデータ駆動型に選択することが可能になります。

以下は、有名なアイリスデータセットのサンプルアグロメラティブクラスタリングの例です。

では、なぜアグロメラティブクラスタリングをすべての教師なし分類問題に使用しないのでしょうか？

❌ アグロメラティブクラスタリングは、データセットのサイズが増えるにつれて非常に遅くなります。

残念ながら、従来のアグロメラティブクラスタリングはスケーリングできません。ランタイムの計算量はO(n³)またはO(n²log(n))（最小ヒープを使用して実装した場合）です。さらに悪いことに、アグロメラティブクラスタリングはシーケンシャルに単一のコアで実行され、計算によるスケーリングはできません。

NLPの分野では、アグロメラティブクラスタリングは小規模のデータセットで最も優れたパフォーマンスを発揮します。

Reciprocal Agglomerative Clustering（RAC）

Reciprocal Agglomerative Clustering（RAC）は、Googleが提案した方法であり、従来のアグロメラティブクラスタリングの利点を大規模なデータセットにスケーリングするためのものです。

RACはランタイムの計算量を減らし、また操作を並列化してマルチコアアーキテクチャを活用します。これらの最適化にもかかわらず、データが完全に接続されている場合、RACは従来のアグロメラティブクラスタリングとまったく同じ結果を生み出します（以下参照）。

注意：完全に接続されたデータは、任意の2つのポイント間の距離メトリックを計算することができます。非完全に接続されたデータセットには、接続制約（通常はリンケージ行列の形式で提供される）があり、一部のポイントが切断されたと見なされます。

<img alt="RACは、データが完全に接続されている場合には従来の集合的クラスタリングとまったく同じ結果を生成します！（トップ）さらに、接続制約がある場合でも同様の結果が得られることが多いです（ボトム）。共著者ポーター・ハンリーによる作成されたグラフ。

完全に接続されていないデータ（RACと凝集性クラスタリング）でも、通常は同じ結果になります。上記の2番目のスイスロールデータセットの例でも同様です。

ただし、クラスタの可能性が非常に少ない場合には、大きな不一致が生じる場合があります。ノイズの多い月のデータセットはこれの良い例です。

<img alt="RACとsklearnの間の不一致した結果。共著者ポーター・ハンリーによる作成されたグラフ。

RAC++はscikit-learnよりも大規模なデータセットに対応しています

RAC++（相互結合クラスタリングの実装）とscikit-learnの対応物であるAgglomerativeClusteringを比較することができます。

25次元の例データを生成し、データセットのサイズが1,000から64,000ポイントまで変化した場合に、racplusplus.racとsklearn.cluster.AgglomerativeClusteringを使用して凝集クラスタリングがどれくらい時間がかかるかテストしてみましょう。

注意：メモリ消費を制限するために接続行列を使用しています。

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)  # マトリックスは対称でなければなりません - 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)

以下は、各サイズのデータセットの実行時間結果のグラフです。

<img alt="sklearnとracplusplusを比較した場合、大規模なデータセットではランタイムが大幅に変化します。共著者ポーター・ハンリーによる作成されたグラフ。

見てわかるように、RAC++と従来の凝集クラスタリングの間には実行時間の大きな違いがあります。

30,000ポイントをわずかに超えると、RAC++は約100倍高速です！さらに重要なことに、scikit-learnの凝集クラスタリングは約35,000ポイントで時間制限に達しますが、RAC++は合理的な時間制限に達するまで、何十万ポイントでもスケーリングすることができます。

RAC++は高次元にスケーリングできます

RAC++が高次元データにどれくらいスケーリングするか、従来の対応物と比較することもできます。

3,000ポイントの次元ごとのクラスタ生成にかかる時間

3,000ポイントの場合、伝統的な階層的クラスタリングはより速いですが、線形的にスケーリングします。一方、RAC++はほぼ一定です。NLPの分野では、768次元または1536次元の埋め込みを取り扱うことが一般的になっており、それらの要件に合わせて次元をスケーリングすることが重要です。

RAC++はより優れたランタイムを持っています

Googleの研究者は、RACのランタイムがO(nk)であり、kは接続制約、nはポイントの数であることを証明しました。つまり、線形のランタイムです。ただし、これには初期の距離行列の計算は含まれていません。初期の距離行列の計算はO(n²)であり、つまり、二次のランタイムです。

私たちの結果は、定数の30近傍接続制約でO(n²)のランタイムを確認しています：

+ — — — — — — -+ — — — — — +| データポイント | 秒 |+ - - - - - - -+ - - - - - +| 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++は非常に高速なのでしょうか？基礎となるアルゴリズムをいくつかのステップに簡略化できます：

1. 相互最近傍のクラスタをペアにする
2. ペアのクラスタをマージする
3. 近傍を更新する

このように、伝統的な階層的クラスタリングアルゴリズムとの唯一の違いは、相互最近傍のクラスタをペアにすることです。これがReciprocal Agglomerative Clustering（RAC）という名前の由来です。次に示すように、この相互ペアリングにより、階層的クラスタリングの計算コストが最も高いステップを並列化することが可能になります。

相互最近傍のクラスタをペアにする

まず、相互最近傍のクラスタを見つけるためにループを回します。相互最近傍とは、最も近い隣接点が互いになるクラスタのことです（距離は方向性を持つことを覚えておいてください）。

ペアをマージする

RACは並列化可能です。なぜなら、相互最近傍のクラスタをマージする順序は関係なく、リンケージメソッドが簡約可能であれば良いからです。

リンケージメソッドとは、各クラスタに含まれるポイント間のペアワイズ距離に基づいて、2つのクラスタ間の距離を決定する関数のことです。簡約可能なリンケージメソッドは、マージ後の新しいクラスタが他のどのクラスタよりも近くならないことを保証します。

幸運なことに、最も人気のある4つの連結法は簡約可能です：

• シングルリンケージ — 最小距離
• 平均リンケージ — 距離の平均
• 完全リンケージ — 最大距離
• ワードリンケージ — 分散の最小化

私たちは相互ペアがお互いの最近傍であることを知っており、簡約可能な連結法のマージは新しくマージされたクラスタを他のクラスタに近づけることはありません。したがって、相互の最近傍ペアを一度にすべてマージすることができます。各最近傍ペアは、連結法に従ってマージするための利用可能なスレッドに配置することができます。

相互の最近傍を同時にマージできるという事実は素晴らしいことです。なぜなら、クラスタのマージは計算上最も費用のかかるステップだからです！

最近傍の更新を更新する

簡約可能な連結法では、マージ後に最近傍を更新する順序も重要ではありません。したがって、いくつかの巧妙な設計を行うことで、関連する最近傍を並列で更新することもできます。

結論

いくつかのテストデータセットを使用して、RAC++が完全に接続されたデータセットに対して従来の凝集クラスタリング（つまり、sklearn）とまったく同じ結果を生成することを示しました。さらに、ランタイムもはるかに優れています。簡約可能な連結法のメトリックを理解し、並列プログラミングの基本的な理解を持つことで、RAC++が非常に高速になるロジックを理解することができます。

オープンソースに採用されたアルゴリズムRAC++の詳細な理解（および証明）については、元となったGoogleの研究をご覧ください。

将来

Porter Hunleyは、ファインチューンされたBERT埋め込みを介して生成された臨床用語エンドポイントの分類体系を作成するために、RAC++を構築し始めました。これらの医療埋め込みは768次元であり、彼が試した他のクラスタリングアルゴリズムでは、凝集クラスタリングだけが良い結果を出しました。

他の高スケールのクラスタリング手法では、情報を得るために次元の削減が必要ですが、完全に確実な次元の削減方法はありません。常に情報を失うことになります。

GoogleのRACに関する研究を発見した後、Porterは独自のオープンソースクラスタリング実装を構築し、臨床用語クラスタリングの研究をサポートしました。Porterが開発をリードし、私はRACの一部を共同開発しました。特に、C++実装をPythonでラップし、ランタイムを最適化し、ソフトウェアを配布するためにパッケージ化しました。

RAC++は、従来の凝集クラスタリングでは遅すぎるクラスタリングアプリケーションを可能にし、最終的には数百万のデータポイントにスケーラブルになるでしょう。

RAC++はすでに大規模なデータセットのクラスタリングに使用できますが、改善の余地があります… RAC++はまだ開発中です — 貢献してください！

共著者:

• Porter Hunley、Daceflow.aiのシニアソフトウェアエンジニア：github
• Daniel Frees、スタンフォード大学のMS Stats＆Data Scienceの学生、IBMのデータサイエンティスト：github

GitHub — porterehunley/RACplusplus: Reciprocal Agglomerativeの高性能実装…

We will continue to update VoAGI; if you have any questions or suggestions, please contact us!