https://preview.redd.it/di99yw56tksg1.png?width=992&format=png&auto=webp&s=8828c9459dcf8f8541718e4d7a9fae52bfc0b95a

汎用クラスタリングのために、SPORE（Skeleton Propagation Over Recalibrating Expansions）というクラスタリングアルゴリズムを作りました。これは、非凸・凸データ、低次元・高次元のデータのどれにも対応できるよう意図しています。2〜784Dの28個のデータセットでベンチマークし、Pythonパッケージと研究論文を公開しました。

短い要約

SPOREは、密度分散に基づく手法で、任意の幾何形状と次元数における汎用クラスタリングを目的としています。まずknnグラフを構築した後、2つのフェーズがあります。フェーズ1（Expansion）では、BFSを用い、密度分散の制約を継続的に洗練（リファイン）しながら、初期クラスタをそれらの固有のスケールに適応する形で拡張します。狙いは、内側のよくシールドされたスケルトンを捉え、低分離の境界領域には踏み込みすぎないようにすることです。フェーズ2（Small-Cluster Reassignment、別名SCR）は、そうした境界点を取り囲むスケルトンにそれらを統合（マージ）し、隣接するクラスタ境界の間に鋭い線を引くことができます。これは、k-meansの分割が最も近いセントロイド／代表への割り当てを行うのに少し似ています。つまりSPOREは、スケールに適応した形状認識能力を持ち、クラスタ同士が近いときでも鋭い境界を描けるため、多くの密度ベースのクラスタリングアルゴリズムが抱える「マージしてしまうか、断片化してしまうか（merge-or-fragment）」問題に対して強く耐性があります。また、次元数にもかなり頑健で、数百次元まで対応できます。さらに、1000D+のLLM埋め込みに使ってもきれいな結果が得られました（ただし公平のために言うと、LLM埋め込みは高次元であるにもかかわらず、しばしばうまく分離されるように学習されていることが多いです）。

より詳しく

SPOREには3つの主要ステップがあり、そのうち2つは実際のクラスタリングが行われる段階です：

1. knnグラフを構築する。 これは厳密または近似のどちらでも行えます。私はHNSWによる近似をおすすめします（Pythonパッケージがデフォルトとして使っているのがこれです）。いずれでも性能は本質的に同じです。というのも、SPOREは拡張を制約するために、クラスタ内の密度分散についての「概ねの」近似的な感覚があればよいからです。厳密なknnは必須ではありません。近傍の誤差があまり大きくなければ、ほとんどのケースで問題ありません。
2. BFSを実行する。 ここがSPOREという名前の最もふさわしい部分です。生物の胞子のように、特定の点にクラスタを「種まき」し、データのマニフォールド上で外側へ広げていき、マニフォールドがもはや「住みやすくない」状態になるまで成長させます。
   1. 最初に、密度の逆順（降順とは逆で、密度が高い方からではなく“逆の順序”）で点を並べ替えます。
   2. 次に、最も密な点を取り出し、それを中心にBFSを開始します。
   3. BFSの間、近傍距離の平均と標準偏差を追跡し、受け入れた各点ごとにそれを更新します。追加候補を検討するときは、現在の平均と標準偏差を使って、その点の最前線（フロンティア）からの距離のzスコアを計算します。zスコアが（ユーザーが指定した閾値に基づいて）高すぎる場合、その点は棄却されます。やがて、すべての候補点のzスコアが高すぎる状態になります。これは、クラスタが境界に近づいて細ってきていると自然に起こります。
   4. クラスタ1の拡張が終わったら、次に密な点を取り出し、クラスタ2のためにBFSを開始します。
   5. 最後に目標とするのは、各“真の”クラスタの中で少なくともある最小限のコアスケルトンを拡張しきる一方で、境界は断片化したまま残すことです。というのも、境界領域へ成長してしまうと、拡張が隣接クラスタへ漏れ出す原因になり得るからです。スケルトンが無傷で、境界が砕けている状態であれば、次のフェーズにとって理想的な準備が整っています。
      1. 密度分散アプローチの良い副作用の1つは、スケルトンの分離に役立つ「低い距離コントラスト」への頑健性が一定程度あることです。コントラストが低い場合、距離における標準偏差もそれに応じて下がります。そのため、距離のわずかではあるが一貫した差でも何らかの信号として働き、結果として多くの場合においてクラスタの内側スケルトン同士を互いに分離できます。
      2. スケルトンだけが目的ではありません。データセットがすでにうまく分離されているなら、拡張だけで仕事が済む可能性があり、次のフェーズは不要です。
3. Small Cluster Reassignment（SCR）。 スケルトンが同定されると、小さなクラスタの再割り当てがやってきます。別名SCRです。このフェーズは、ローカライズされたK-meansのようなものだと考えています。つまり、点を「最も近いクラスタ代表」によって分割するのです。ただし今回は、代表は「再割り当て対象点」のknn内に存在する、特定クラスタの点です。そして分割アルゴリズムは本質的にknn分類器です。したがって、このフェーズでは、すべての小クラスタ内の点（理想的にはバリア点で構成される）を取り、それらのknnの中で、囲い込み（enclosure）、knnの個数、近さ（nearness）といった特定の幾何学的条件を測るスコアを最大化するクラスタへ再割り当てします。その最大選択によって、鋭い境界を描けるわけです。分離が最小限であっても大丈夫で、重要なのは、再割り当て対象点のknnの中で、右のクラスタが一貫してより強く裏づけられているための点がいくつか存在することです。これはしばしば、たとえ極わずかな差でも、その点へ再割り当て対象点の近さで表れることが多いです。
   1. 別の見方をすると、このフェーズは、より“接続欲が低い（connection-greedyではない）”別モードの再開された拡張フェーズのような働きをします。第1フェーズは形状への適応度が高いアンカーを見つけ、第2フェーズがそれらを外側へ伝播して、第1フェーズ単独では見つけられなかった、より明確な停止点へ到達させます。
4. 簡潔さのためにいくつかの詳細は省略していますが、それが中核です。