Skip to content
検索結果に戻る

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

提唱者
Ng, A. Y.; Jordan, M. I.; Weiss, Y.
年
2002
種類
Graph-based clustering (spectral method)

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

スペクトラルクラスタリングは、2002年にNg、Jordan、Weissによって形式化されたグラフベースの教師なし学習アルゴリズムであり、k-meansを適用する前に、類似性グラフのラプラシアンから派生した低次元固有空間にデータ点をマッピングします。このスペクトル埋め込みにより、ユークリッド距離ベースの方法では一貫して分離できない、リング、クレセント、インターリーブされたスパイラルなどの任意の形状のクラスタを回復することが可能になります。

手法の背後にある直感

標準的なk-meansは直線距離によって空間を分割するため、凸状でほぼ球形の塊しか見つけることができません。スペクトラルクラスタリングは、まずデータをネットワークとして考え、各点をノードとし、ノード間のエッジは2つの点の類似性を反映する重みを持つことで、これを回避します。クラスタは、内部で密に接続されているが、それ以外とは緩く接続されているネットワーク領域に対応します。グラフのラプラシアン行列は、この接続構造をエンコードし、その最小固有ベクトルは、データが互いに絡み合っていても、よく分離されたクラスタが互いに離れるようにデータを引き伸ばす滑らかな座標系のように機能します。その新しい座標系での単純なk-meansステップは、それらをきれいに分離します。

歴史学

スペクトラルクラスタリングの理論的基盤は、グラフ接続性と代数的接続性固有値に関するフィードラーの1973年の研究にまで遡ります。ShiとMalik(2000)は、画像セグメンテーションのための正規化カット基準を通じて、このアプローチをコンピュータビジョンに導入しました。Ng、Jordan、Weiss(2002)は、NIPSで、現在最も一般的に引用されているクリーンで汎用的なアルゴリズムを、その方法がいつ、なぜ機能するのかを説明する摂動理論的分析とともに発表しました。Von Luxburgの2007年のStatistics and Computingのチュートリアルは、競合する定式化を統一し、ラプラシアン正規化の役割を明確にし、実務者にとって標準的な参照となりました。スペクトラルクラスタリングは現在、機械学習カリキュラムの中心的な位置を占めており、スケーラブルな近似、ロバストなカーネル、グラフや多様体への拡張に関する進行中の作業により、活発な研究トピックであり続けています。

使うべき場面

スペクトラルクラスタリングは、クラスタが非凸、非線形分離不可能、またはユークリッドパーティション法では検出できない細い橋で接続されている場合に適しています。一般的な例としては、リング状のクラスタ、インターリーブされたスパイラル、画像セグメントなどがあります。ペアごとの類似性を意味のある方法で計算できる場合(生のフィーチャのカーネルから、または事前に提供された親和性行列から)、およびクラスタ数kが既知であるか、固有ギャップヒューリスティックから推定できる場合に適切です。この方法は、クラスタ形状に関する分布上の仮定を必要としません。実用上の制限には、点の数に対する二次メモリ(完全な親和性行列の場合)と固有値分解に対する立方時間があり、標準的な定式化は、約10,000点を超える場合は高価になります。近似法(Nystrom、疎グラフ、ランダム化SVD)は、その範囲をより大きなデータセットに拡張します。

限界と注意点

  • 完全なn×n親和性行列の構築には、固有値分解にO(n^2)のメモリとO(n^3)の時間が必要であり、ナイーブなアルゴリズムは大規模データセットでは実行不可能になります。
  • 結果は、カーネル帯域幅σの選択とグラフ構築戦略に敏感です。不適切な選択は、クラスタをマージまたはフラグメントする可能性があります。
  • スペクトル埋め込みにおけるk-meansの初期化はランダム性を導入します。異なる実行では異なるパーティションが得られる可能性があります。
  • 慎重なカーネル選択なしでは、非常に高次元の特徴空間にうまくスケーリングしません。
  • クラスタラベルのみを提供します。生成モデルを提供せず、新しい点に対する自然なサンプル外拡張も提供しません。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • k-meansやガウス混合モデルを打ち負かす、非凸および非線形分離不可能な構成を含む、任意の形状のクラスタを検出します。
  • ユークリッド距離だけでなく、任意のペアごとの類似性行列で動作できるため、グラフ、文字列、その他の構造化データに適用できます。
  • 固有ギャップヒューリスティックは、クラスタ数kを選択するための、原理に基づいたデータ駆動型のガイドを提供します。
  • グラフ接続性と代数的接続性固有値に関するフィードラーの1973年の研究にまで遡る豊かなスペクトルグラフ理論に基づいています。
  • 標準的な線形代数ライブラリを使用して、概念的にシンプルで簡単に実装できます。

応用

  • 画像セグメンテーション:ピクセルレベルの特徴類似性を使用して、知覚的に一貫した領域にピクセルまたはスーパーピクセルを分割すること。
  • 特徴ベクトルではなくペアごとの接続性が構造を定義する、ソーシャルネットワークおよびバイオネットワークにおけるコミュニティ検出。
  • バイオインフォマティクス:発現プロファイルの類似性によって遺伝子またはタンパク質をグループ化すること。この場合、発現クラスタは遺伝子空間ではめったに凸になりません。
  • 自然言語処理:意味的類似性カーネルを使用したドキュメントまたは文のクラスタリング。
  • コンピュータビジョン:クラスタ境界が不規則なモーションセグメンテーションおよび点群パーティショニング。
  • 探索的データ分析:確認的手法を適用する前に、明白でないクラスタ構造を明らかにすること。

使い方

使い方

1

データからペアごとの類似性(親和性)行列Wを構築します。最も一般的な選択肢はガウス(RBF)カーネルであり、近くのペアに高い重みを割り当て、遠いペアにはゼロに近い重みを割り当てます。帯域幅パラメータσは、距離とともに類似性がどれだけ速く減衰するかを制御します。その選択は非常に重要です。あるいは、大規模データセットの疎な表現のためにk最近傍グラフを使用することもできます。

数式
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)
2

次数行列Dは、i番目のエントリがWのi番目の行の合計である対角行列です。WとDから正規化された(対称)グラフラプラシアンL_symが形成されます。この行列は、類似性グラフの完全な接続構造を捉え、その固有値スペクトルは、データがいくつの自然なクラスタを含んでいるか、そしてそれらがどれだけきれいに分離されているかを示します。

数式
L_{\mathrm{sym}} = D^{-1/2}(D - W)D^{-1/2} = I - D^{-1/2}W D^{-1/2}
3

L_symのk個の最小固有値に対応するk個の固有ベクトルを計算します。これらの固有ベクトルは、埋め込み行列Uの列を形成し、Uはデータ点ごとに1行を持ちます。このk次元スペクトル空間では、元の特徴空間で互いに入り組んでいても、同じクラスタに属する点は互いに引き寄せられます。

数式
L_{\mathrm{sym}}\, u = \lambda u \quad \Rightarrow \quad U = [u_1,\, u_2,\, \ldots,\, u_k]
4

Uの各行をユークリッドノルムで割ることで、埋め込まれた点を単位超球に投影します。Ng、Jordan、Weissによって導入されたこの正規化は、固有ベクトル間の偽のスケール差を除去し、後続のk-meansステップが大きさではなく埋め込みの角度構造に焦点を当てることを保証します。

数式
T_{ij} = U_{ij} \Big/ \left(\sum_{j'} U_{ij'}^2\right)^{1/2}
5

正規化された埋め込み行列Tの行に標準的なk-meansクラスタリングを適用します。スペクトル埋め込みはすでにクラスタの幾何学的構造を解きほぐしているため、k-meansは非凸クラスタ形状でも意味のあるパーティションを見つけます。クラスタラベルは、元のデータ点にマッピングされます。

よくある落とし穴

  • 原理に基づいた交差検証や自己調整なしにσを選択すること。帯域幅が小さすぎるとグラフが切断され、大きすぎると異なるクラスタがマージされます。
  • k-meansの前に親和性行列の行を正規化しないこと(Ngらによる行正規化ステップは安定性のために不可欠です)。
  • 固有ギャップを無視すること:固有値スペクトルを調べずに固定のkを使用すると、クラスタの過小または過剰セグメンテーションにつながることがよくあります。
  • 近似または疎なバリアントに切り替えることなく、数万点のデータセットに完全なアルゴリズムを適用すること。
  • 正規化されていない(L = D - W)ラプラシアンと正規化された(L_sym、L_rw)ラプラシアンを混同すること。これらはクラスタ割り当てを大幅に変更する可能性があります。

よくある質問

クラスタ数kをどのように選択しますか?

固有ギャップヒューリスティックが標準的なガイダンスです。昇順で正規化ラプラシアンの固有値を計算し、連続する固有値間の最大のギャップを探します。このギャップが発生するインデックスが、自然なクラスタ数を示唆します。固有ギャップが曖昧な場合は、安定性ベースのアプローチ(複数のkの値に対してアルゴリズムを実行し、摂動全体でのクラスタ割り当てを比較する)が役立ちます。

ガウスカーネル帯域幅σをどのように設定すべきですか?

一般的なヒューリスティックは、データセット内のペアごとの距離の中央値、または各点にローカル帯域幅を割り当てる最近傍自己調整スキーム(Zelnik-Manor & Perona、2004)です。実際には、σは、結果の親和性グラフの接続性を検査することによって検証されるべきです。各点は少なくとも数個の高重み近傍を持つべきであり、グラフは孤立したコンポーネントにフラグメントされるべきではありません。

行正規化ステップはなぜ必要ですか?

ラプラシアンの固有ベクトルは、スケールが大きく異なる場合があります。埋め込み行列の各行を単位長に正規化しないと、k-meansステップは大きな大きさを持つ固有ベクトルによって支配され、情報量が多いが小さい大きさのコンポーネントを無視する可能性があります。Ng、Jordan、Weissによって導入された行正規化は、すべての点を単位球にマッピングするため、k-meansは大きさではなく埋め込みの角度幾何学的構造に応答します。

スペクトラルクラスタリングは非常に大きなデータセットを処理できますか?

ナイーブな形式ではできません。O(n^2)のメモリとO(n^3)の固有値分解時間が必要です。nが大きい場合、標準的な解決策には、完全な親和性行列の代わりに疎なk最近傍グラフを構築すること、サブサンプルから固有ベクトルを推定するためにNystrom近似を使用すること、またはランダム化SVDを適用することが含まれます。これらの近似法は、コストの fraction でほとんどの精度を回復します。

関連する手法

参考文献

  1. Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002). On Spectral Clustering: Analysis and an Algorithm. Advances in Neural Information Processing Systems, 14, 849–856.

    出版物の文献を開く
    コピーしました。
  2. von Luxburg, U. (2007). A Tutorial on Spectral Clustering. Statistics and Computing, 17, 395–416.

    DOI 文献を開く
    コピーしました。
  3. Shi, J., & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905.

    DOI 文献を開く
    コピーしました。