サポートベクトルクラスタリング (support vector clustering)

点\(\mathbf{x}_j\)を,高次元の特徴空間に写す関数を \(\phi(\cdot)\),球の中心を \(\mathbf{a}\),球の半径を \(R\),スラック変数を \(\xi_j\)とする.ここで,全ての \(j\) について次の制約を考える \[||\phi(\mathbf{x}_j)-\mathbf{a}||^2\le R^2+\xi_j\] 他の制約も考えて半径 \(R\) を最小化するLagrangianを考える.(\(\mu_j\)と\(\beta_j\)はLagrange乗数) \[L=R^2-\sum_j (R^2+\xi_j-||\phi(\mathbf{x}_j)-\mathbf{a}||^2)\beta_j-\sum\xi_j\mu_j+C\sum\xi_j\] この式から導かれる制約を使って,この式の双対形は次のようになる \[W=\sum_j \phi(\mathbf{x}_j)^2\beta_j-\sum_{i,j}\beta_i\beta_j\phi(\mathbf{x}_i)\cdot\phi(\mathbf{x}_j)\] すると,関数\(\phi(\cdot)\)の内積だけで書けるので,カーネルを使うことができる.最小化はsequential minimal optimization法で計算量が \(O(N^2)\) で解ける.(\(N\)はデータ数)

入力空間で\(\mathbf{x}_i\)と\(\mathbf{x}_j\)を結ぶ線分上の任意の点が,特徴空間中で超球内にあり続ければ,これら二つの点は同じクラスタの要素になる.クラスタ割り当ての計算量は\(O(N^2d)\) で解ける.(\(d\)は入力の次元数)

ガウスカーネルを使うと球の周辺ほど密度の低い部分となるので,点密度の低い部分で分離するようなクラスタリングとなる.

-- しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:12:20 (2493d)