スペクトルクラスタリング

スペクトルクラスタリングは、質量-ばねシステムの分割と関連していることがよく知られています。このシステムでは、各質量がデータポイントに関連付けられ、各ばねの剛性は、ばねシステムのように、関連する2つのデータポイントの類似性を表すエッジの重みに対応します。具体的には、古典的な文献^{[ 1 ]}では、質量-ばねシステムの横方向振動モードを記述する固有値問題は、次のように定義されるグラフ・ラプラシアン行列の固有値問題とまったく同じであると説明されています。

${\displaystyle L:=DA}$、

どこ${\displaystyle D}$は対角行列です

${\displaystyle D_{ii}=\sum _{j}A_{ij},}$

Aは隣接行列である。

質量-ばね系においてばねによって密接に連結された質量は、低周波振動モードでは平衡位置から一緒に動くため、グラフ・ラプラシアンの最小固有値に対応する固有ベクトルの成分を用いて、質量を意味のある形でクラスタリングすることができます。例えば、図示された2次元ばね系において、すべてのばねと質量が同一であると仮定すると、システムが揺らされたときに、システムの右側にある最も緩く連結された質量が、他の質量とは反対方向に最大の振幅で動くと直感的に予想されます。そして、この予想は、最小固有値、すなわち最小振動周波数に対応するグラフ・ラプラシアンの固有ベクトルの成分を分析することで確認できます。

正規化の目的は、ラプラシアン行列の対角成分をすべて単位にし、それに合わせて非対角成分もスケーリングすることです。重み付きグラフでは、頂点の次数は、接続されている辺の数が少なくても重みが大きい場合もあれば、接続されている辺の数が多くても重みが単位である場合もあり得ます。

一般的な正規化スペクトルクラスタリング手法として、Jianbo ShiとJitendra Malikによって導入された正規化カットアルゴリズム（Shi-Malikアルゴリズム）^{[ 2 ]}があり、これは画像セグメンテーションによく用いられます。このアルゴリズムは、点を2つのセットに分割します。${\displaystyle (B_{1},B_{2})}$固有ベクトルに基づく${\displaystyle v}$対称正規化ラプラシアンの2番目に小さい固有値に対応する。

${\displaystyle L^{\text{norm}}:=ID^{-1/2}AD^{-1/2}.}$

ベクトル${\displaystyle v}$また、これは対称的に正規化された隣接行列の 2番目に大きい固有値に対応する固有ベクトルでもある。${\displaystyle D^{-1/2}AD^{-1/2}.}$

ランダムウォーク（または左）正規化ラプラシアンは次のように定義される。

${\displaystyle L^{\text{rw}}:=D^{-1}L=ID^{-1}A}$

また、スペクトルクラスタリングにも使用できます。数学的に同等のアルゴリズム^{[ 3 ]}は、固有ベクトルを取得します。${\displaystyle u}$ランダムウォーク正規化隣接行列の最大固有値に対応する${\displaystyle P=D^{-1}A}$。

固有ベクトル${\displaystyle v}$対称的に正規化されたラプラシアンと固有ベクトル${\displaystyle u}$左正規化ラプラシアンの値は恒等式によって関連付けられる。${\displaystyle D^{-1/2}v=u.}$

知っていること${\displaystyle n}$-による-${\displaystyle k}$マトリックス${\displaystyle V}$選択された固有ベクトルのマッピング（スペクトル埋め込みと呼ばれる）により、元の${\displaystyle n}$データポイントは${\displaystyle k}$行を使用した次元ベクトル空間${\displaystyle V}$分析は、クラスタリングベクトルにまで縮小されます。${\displaystyle k}$構成要素は、さまざまな方法で作成できます。

最も単純なケースでは${\displaystyle k=1}$選択された単一の固有ベクトル${\displaystyle v}$フィードラーベクトルと呼ばれる は、2番目に小さい固有値に対応します。 の成分を使用すると${\displaystyle v,}$成分が${\displaystyle v}$セット内で正の値をとる${\displaystyle B_{+}}$そして残りは${\displaystyle B_{-}}$これにより、グラフが二分割され、データポイントに2つのラベルが付けられます。この符号ベースのアプローチは、質量-ばねモデルによるスペクトルクラスタリングの直感的な説明に従います。フィードラーベクトルが低周波振動モードで${\displaystyle v}$これは、相互に強く結びついた質量を持つデータポイントが一方向に移動するクラスターと、残りの質量を持つデータポイントが反対方向に移動するクラスターがそれぞれ存在することを意味します。このアルゴリズムは、サブセットを同様の方法で繰り返し分割することで、階層的クラスタリングにも使用できます。

一般的に${\displaystyle k>1}$任意のベクトルクラスタリング手法を使用できます。たとえば、DBSCANなどです。

グラフ ラプラシアンは隣接行列から構築することができ、また一般的には隣接行列から構築されます。構築は行列フリー、つまりグラフ ラプラシアンの行列を明示的に形成せず、AOも使用せずに実行できます。また、メモリ使用量を増やすことなく隣接行列の代わりに実行することもできます。いずれの場合も、グラフ ラプラシアンの構築コストは基本的に隣接行列の構築コストによって決まります。${\displaystyle n}$-による-${\displaystyle n}$グラフ隣接行列。

さらに、正規化ラプラシアンは、正規化隣接行列とまったく同じ固有ベクトルを持ちますが、固有値の順序が逆になります。したがって、正規化ラプラシアンの最小固有値に対応する固有ベクトルを計算する代わりに、ラプラシアン行列について言及することなく、正規化隣接行列の最大固有値に対応する固有ベクトルを計算すれば等価です。

RBFカーネルなどを用いたグラフ隣接行列の素朴な構成では、行列が密になるため、${\displaystyle n^{2}}$記憶と${\displaystyle n^{2}}$AO は、${\displaystyle n^{2}}$行列のエントリ。Nystrom法^{[ 6 ]}は類似度行列を近似するために使用できますが、近似行列は要素ごとに正ではないため^{[ 7 ]}、距離ベースの類似度として解釈することはできません。

グラフ隣接行列を疎行列として構築するアルゴリズムは、通常、最近傍探索に基づいています。これは、与えられたデータポイントの近傍を推定またはサンプリングして最近傍を見つけ、隣接行列の非ゼロ要素を、隣接点のペアのみを比較することによって計算します。選択された最近傍の数が非ゼロ要素の数を決定し、多くの場合、メモリ使用量を抑えるために固定されます。${\displaystyle n}$-による-${\displaystyle n}$グラフ隣接行列は${\displaystyle O(n)}$、 のみ${\displaystyle O(n)}$計算するには、連続した算術演算が必要です。${\displaystyle O(n)}$非ゼロのエントリがあり、計算は簡単に並列実行できる。

計算コスト${\displaystyle n}$-による-${\displaystyle k}$（と${\displaystyle k\ll n}$) グラフの選択された固有ベクトルの行列 ラプラシアンは通常、${\displaystyle n}$-による-${\displaystyle n}$グラフ・ラプラシアン行列をベクトルで表すと、グラフ・ラプラシアン行列が密行列か疎行列かによってコストが大きく変わります。密行列の場合、コストは次のようになります。${\displaystyle O(n^{2})}$文献で非常によく引用されるコスト${\displaystyle O(n^{3})}$選択から生まれる${\displaystyle k=n}$そして、例えば階層的スペクトルクラスタリングでは明らかに誤解を招く。${\displaystyle k=1}$フィードラーベクトルによって決定される。

まばらなケースでは${\displaystyle n}$-による-${\displaystyle n}$ラプラシアン行列をグラフ化${\displaystyle O(n)}$非ゼロのエントリ、行列ベクトル積のコスト、したがって計算のコスト${\displaystyle n}$-による-${\displaystyle k}$と${\displaystyle k\ll n}$選択された固有ベクトルの行列は${\displaystyle O(n)}$メモリフットプリントもわずか${\displaystyle O(n)}$どちらもクラスタリングの複雑さの最適な下限値である。${\displaystyle n}$データポイント。さらに、 LOBPCGのような行列フリーの固有値ソルバーは、分散メモリを備えた複数のGPUなど上で効率的に並列実行でき、スペクトルクラスタリングで有名な高品質のクラスタだけでなく、最高のパフォーマンスも実現します。^{[ 8 ]}

スペクトルクラスタリングは、特にクラスタの割り当て方法において、 k-meansアルゴリズムと密接に関連しています。スペクトルクラスタリングはグラフベース、k-meansは重心ベースという、初期定式化における根本的な違いはあるものの、カーネル法の観点からスペクトルクラスタリングを考察すると、両者の関連性が明らかになります。

特に、重み付きカーネルk平均法は、両者をつなぐ重要な理論的架け橋となります。カーネルk平均法は、標準k平均法の一般化であり、カーネル関数によってデータが暗黙的に高次元の特徴空間にマッピングされ、その空間でクラスタリングが実行されます。スペクトルクラスタリング、特に正規化バージョンは、入力データ（またはグラフノード）をグラフラプラシアンの固有ベクトルによって定義される低次元空間にマッピングすることで、同様の操作を実行します。これらの固有ベクトルは、正規化カットまたはその他のグラフ分割目的の緩和の解に対応します。

数学的には、スペクトルクラスタリングによって最小化される目的関数は、この変換された空間における重み付きカーネルk平均法の目的関数と等価であることが示されます。これは、^{[ 16 ]}などの研究で正式に確立されており、正規化されたカットは、正規化されたラプラシアンの固有ベクトル行列の行に適用される重み付きカーネルk平均法と等価であることが示されています。

この等価性により、スペクトルクラスタリングは、グラフ・ラプラシアンによって定義される固有空間においてカーネルk平均法を実行するものと見なすことができます。この理論的洞察は実際的な意味合いを持ちます。スペクトルクラスタリングにおける最終的なクラスタリングステップでは、通常、ラプラシアンの最初のk個の固有ベクトルによって形成される行列の行に対して標準的なk平均法アルゴリズムを実行します。これらの行は、各データポイントまたはノードを低次元空間に埋め込むものと考えることができ、その空間ではクラスタがより明確に分離されるため、k平均法による検出が容易になります。

さらに、この共通の目的関数を直接最適化するためのマルチレベル手法が開発されています。これらの手法は、グラフを反復的に粗くして問題のサイズを縮小し、粗いグラフ上で問題を解決し、その後、より細かいグラフ上で解を洗練していくことで機能します。これにより、スペクトル埋め込みによって保持されるグローバル構造を捉えつつ、大規模な問題に対してより効率的な最適化が可能になります。^{[ 17 ]}

スペクトルクラスタリングは、特にスペクトル法が グラフの接続されたグラフコンポーネントを識別するために使用される特殊なケースにおいて、 DBSCAN （ノイズのあるアプリケーションの密度ベースの空間クラスタリング）とも概念的に関連しています。相互接続エッジのないノードのサブセットを識別することが目的であるこの自明なケースでは、スペクトル法はDBSCANと同様に、接続性に基づくクラスタリングアプローチに実質的に還元されます。^{[ 18 ]}

DBSCANは、入力空間内の密度連結領域を特定することで動作します。密度連結領域とは、指定された半径（ε）内の隣接点のシーケンスを介して互いに到達可能であり、かつ最小点数（minPts）を含む点の集合です。このアルゴリズムは、任意の形状のクラスタを検出し、事前にクラスタ数を指定する必要なくノイズを除去することに優れています。

スペクトルクラスタリングにおいて、類似度グラフがハード接続基準（すなわち、2つのノードが閾値距離内にあるかどうかに基づく二値隣接）を用いて構築され、ラプラシアンに正規化が適用されない場合、結果として得られるグラフ・ラプラシアンの固有構造は、グラフの非連結成分を直接明らかにします。これは、DBSCANが密度連結成分を分離する能力を反映しています。正規化されていないラプラシアンのゼロ次固有ベクトルはこれらの成分に対応し、連結領域ごとに1つの固有ベクトルが存在します。

この関連性は、スペクトルクラスタリングをソフトパーティションの最適化（正規化カットの最小化など）ではなく、正確な連結成分の識別に使用する場合に最も顕著になります。これは、「密度ベース」クラスタリングの最も極端な形態に相当し、直接的または推移的に接続されたノードのみがグループ化されます。したがって、この領域におけるスペクトルクラスタリングは、特に疎グラフやε近傍グラフの構築において、 DBSCANのスペクトル版のように動作します。

DBSCANは密度推定値を用いてデータ空間で直接処理を行うのに対し、スペクトルクラスタリングはデータを固有空間に変換し、そこでグローバルな構造と接続性が強調される。どちらの手法も本質的にはノンパラメトリックであり、凸型のクラスタ形状を仮定しないため、概念的な整合性がさらに高まる。