相関クラスタリング

クラスタリングとは、類似性または非類似性に基づいてデータポイントをグループに分割する問題です。相関クラスタリングは、事前にクラスター数を指定する必要なく、ペアワイズの類似性および非類似性情報に基づいてオブジェクトのセットをクラスターに分割するクラスタリングフレームワークです。^{[ 1 ]}

機械学習において、相関クラスタリング（クラスタ編集とも呼ばれる）は、オブジェクト間のペアワイズ類似性または非類似性の関係が既知である設定を考慮します。標準的な定式化では、入力は重み付けされていない完全グラフとしてモデル化されます。${\displaystyle G=(V,E)}$各エッジには、${\displaystyle +}$または${\displaystyle -}$（つまり、グラフは符号付きグラフであり、対応する端点が類似しているか類似していないかを示します。）

目標はクラスタリング（つまり、${\displaystyle V}$相関クラスタリングでは、クラスターの数を選択する必要はありません。これは、一致の数（同じクラスターに端点がある正のエッジと、異なるクラスターに端点がある負のエッジの合計）を最大化するか、不一致の数（端点が離れている正のエッジと、端点が同じクラスターにある負のエッジの合計）を最小化します。k -meansなどの他のクラスタリング方法とは異なり、相関クラスタリングではクラスターの数を選択する必要があります。${\displaystyle k}$あらかじめ。

不一致がゼロのクラスタリングを見つけることが常に可能とは限りません。たとえば、 2 つの正のエッジと 1 つの負のエッジを含む三角形グラフを考えてみましょう。この場合、すべてのクラスタリングで少なくとも 1 つの不一致が発生します。このような構成は、文献では「悪い三角形」と呼ばれています。^{[ 2 ]}

計算の観点から見ると、相関クラスタリング目的を最適化することは困難です。この問題（決定版）はNP完全です。^{[ 3 ]} その後の多くの研究により、完全グラフや一般グラフ、重みなしグラフや重み付きグラフなど、さまざまな仮定の下で、最小化と最大化の両方の目的に対して相関クラスタリングの近似アルゴリズムが開発されました。この問題は基本的な組み合わせ最適化問題の1つと考えられており、それに対処するために多くのアルゴリズム的手法が開発されています。

この問題は複数の分野で幅広く研究されてきた。初期の相関クラスタリング研究に関する包括的な文献レビューは、WahidとHassiniによって提供されている。^{[ 4 ]}

させて${\displaystyle G=(V,E)}$ノードを持つグラフである${\displaystyle V}$エッジ${\displaystyle E}$クラスター化${\displaystyle G}$ノード集合の分割である${\displaystyle \Pi =\{\pi _{1},\dots ,\pi _{k}\}}$と${\displaystyle V=\pi _{1}\cup \dots \cup \pi _{k}}$そして${\displaystyle \pi _{i}\cap \pi _{j}=\emptyset }$のために${\displaystyle i\neq j}$特定のクラスタリングの場合${\displaystyle \Pi }$、 させて${\displaystyle \delta (\Pi )=\{\{u,v\}\in E\mid \{u,v\}\not \subseteq \pi \;\forall \pi \in \Pi \}}$エッジのサブセットを表す${\displaystyle G}$そのエンドポイントはクラスタリングの異なるサブセットにある${\displaystyle \Pi }$さあ、${\displaystyle w\colon E\to \mathbb {R} _{\geq 0}}$をグラフの各エッジに非負の重みを割り当てる関数とし、${\displaystyle E=E^{+}\cup E^{-}}$エッジを魅力的な (${\displaystyle E^{+}}$）そして嫌悪感を抱かせる（${\displaystyle E^{-}}$) エッジ。つまり、エッジは符号付きです。

最小不一致相関クラスタリング問題は、以下の最適化問題である。 $${\displaystyle {\begin{aligned}&{\underset {\Pi }{\operatorname {minimize} }}&&\sum _{e\in E^{+}\cap \delta (\Pi )}w_{e}+\sum _{e\in E^{-}\setminus \delta (\Pi )}w_{e}\;.\end{aligned}}}$$ ここでは、セット${\displaystyle E^{+}\cap \delta (\Pi )}$クラスタリングに関して異なるコンポーネントに端点を持つ魅力的なエッジが含まれています${\displaystyle \Pi }$そしてセット${\displaystyle E^{-}\setminus \delta (\Pi )}$クラスタリングに関して同じコンポーネントに端点を持つ反発エッジを含む${\displaystyle \Pi }$これら2つのセットには、クラスタリングと一致しないすべてのエッジが含まれています。${\displaystyle \Pi }$。

最小不一致相関クラスタリング問題と同様に、最大一致相関クラスタリング問題は次のように定義される。 $${\displaystyle {\begin{aligned}&{\underset {\Pi }{\operatorname {maximize} }}&&\sum _{e\in E^{+}\setminus \delta (\Pi )}w_{e}+\sum _{e\in E^{-}\cap \delta (\Pi )}w_{e}\;.\end{aligned}}}$$ ここでは、セット${\displaystyle E^{+}\setminus \delta (\Pi )}$クラスタリングに関して同じコンポーネントに端点を持つ魅力的なエッジが含まれています${\displaystyle \Pi }$そしてセット${\displaystyle E^{-}\cap \delta (\Pi )}$クラスタリングに関して異なるコンポーネントに端点を持つ反発エッジを含む${\displaystyle \Pi }$これら2つのセットには、クラスタリングと一致するすべてのエッジが含まれています。${\displaystyle \Pi }$。

相関クラスタリング問題を非負のエッジ重みとエッジを吸引エッジと反発エッジに分割するという観点から定式化する代わりに、エッジの集合を明示的に分割することなく、正と負のエッジコストの観点から定式化することもできます。与えられた重みに対して、${\displaystyle w\colon E\to \mathbb {R} _{\geq 0}}$そして与えられた分割${\displaystyle E=E^{+}\cup E^{-}}$エッジを吸引エッジと反発エッジに分類すると、エッジコストは次のように定義できます。 $${\displaystyle {\begin{aligned}c_{e}={\begin{cases}\;\;w_{e}&{\text{if }}e\in E^{+}\\-w_{e}&{\text{if }}e\in E^{-}\end{cases}}\end{aligned}}}$$ すべての人々のために${\displaystyle e\in E}$。

端点が異なるクラスターに属する辺は切断されていると言われる。${\displaystyle \delta (\Pi )}$切断されるすべてのエッジは、しばしばマルチカット^{[ 5 ]}と呼ばれます。${\displaystyle G}$。

最小コストマルチカット問題はクラスタリングを見つける問題です${\displaystyle \Pi }$の${\displaystyle G}$異なるクラスターに属する端点を持つエッジのコストの合計が最小となるようにする。 $${\displaystyle {\begin{aligned}&{\underset {\Pi }{\operatorname {minimize} }}&&\sum _{e\in \delta (\Pi )}c_{e}\;.\end{aligned}}}$$

最小コスト多重カット問題と同様に、重み付きグラフゲームにおける連合構造生成^{[ 6 ]}は、カットされないエッジのコストの合計が最大となるクラスタリングを見つける問題である。 $${\displaystyle {\begin{aligned}&{\underset {\Pi }{\operatorname {maximize} }}&&\sum _{e\in E\setminus \delta (\Pi )}c_{e}\;.\end{aligned}}}$$ この定式化はクリーク分割問題としても知られています。^{[ 7 ]}

上記で定式化した4つの問題はすべて同等であることが示せる。つまり、4つの目的のいずれかに関して最適なクラスタリングは、4つの目的すべてに関して最適であるということである。

グラフが不一致ゼロのクラスタリングを許容する場合、すべての負のエッジを削除し、残りのグラフの連結成分を計算すると、最適なクラスタリングが得られます。このようなクラスタリングが存在するための必要十分条件は、デイビスによって与えられました。グラフ内のどのサイクルにも、ちょうど1つの負のエッジが含まれていてはなりません。^{[ 8 ]}

Bansal ら^{[ 9 ]}は NP 完全性の証明について議論し、この設定でクラスタを見つけるための定数係数近似アルゴリズムと多項式時間近似スキームの両方を提示しています。Ailon ら^{[ 10 ] は}、同じ問題に対してランダム化 3近似アルゴリズムを提案しています。

CCピボット（G=(V,E + ,E − )） ランダムなピボット i ∈ Vを選択する セット${\displaystyle C=\{i\}}$、V'=Ø すべてのj ∈ V、j ≠ iに対して; もし(i,j) ∈ E +ならば Cにjを加える それ以外の場合（(i,j) ∈ E − の場合） jをV'に加える G' を V' によって誘導される部分グラフとする。 クラスタリングC、CC-Pivot(G')を返します

著者らは、上記のアルゴリズムが相関クラスタリングのための3近似アルゴリズムであることを示している。この問題に対して現在知られている最良の多項式時間近似アルゴリズムは、Chawla、Makarychev、Schramm、およびYaroslavtsevによって示されているように、線形計画を丸めることで約2.06の近似値を達成する。^{[ 11 ]}

カルピンスキーとシュディ^{[ 12 ]}は、完全グラフと固定数のクラスタに対して、その問題に対する多項式時間近似スキーム（PTAS）の存在を証明した。

2011年、BagonとGalun ^{[ 13 ]}は 、相関クラスタリング関数の最適化が、よく知られている離散最適化手法と密接に関連していることを示した。彼らの研究では、相関クラスタリング関数が基となるクラスタ数を推定できるようにする、基となる暗黙的モデルの確率的分析が提案された。この分析によると、関数は、クラスタ数に関係なく、すべての可能な分割に対して一様な事前分布を仮定している。したがって、クラスタ数に対する非一様な事前分布が現れる。

本研究では、要素数に応じて適切にスケーリングする複数の離散最適化アルゴリズムを提案する（実験では10万を超える変数での結果が示されている）。BagonとGalunの研究では、いくつかのアプリケーションにおいて、基となるクラスタ数の復元の有効性も評価している。

相関クラスタリングは、高次元空間における特徴ベクトルの属性間の相関関係が存在すると仮定し、クラスタリングプロセスを導く別のタスクにも関連しています。これらの相関関係はクラスターごとに異なる可能性があるため、全体的な相関除去によってこれを従来の（無相関の）クラスタリングに還元することはできません。

属性のサブセット間の相関により、クラスターの空間的な形状が異なります。したがって、クラスターオブジェクト間の類似性は、局所的な相関パターンを考慮して定義されます。この概念に基づいて、上記の概念と同時に^{[ 14 ]で用語が導入されました。このタイプの相関クラスタリングのさまざまな方法は[ 15 ]で議論されており、さまざまなタイプのクラスタリングとの関係は[ 16 ]}で議論されています。高次元データのクラスタリングも参照してください。

相関クラスタリング（この定義による）は、バイクラスタリングと密接に関連していることが示されています。バイクラスタリングと同様に、その目的は、いくつかの属性において相関関係を共有するオブジェクトのグループを特定することです。ここでいう相関関係は、通常、個々のクラスタに特有のものです。

• Pythonでの実装