* サポートベクトルクラスタリング (support vector clustering) [#i938afc3]

//ここには %項目の説明を書いてください.よろしければ署名しておいてください.

点\(\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\)は入力の次元数)

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

> -- しましま

** 関連項目 [#m366d103]

//英語や同義語のあとに,#brで区切って関連する項目をリストしてください.
-[[support vector clustering]]
#br
-[[クラスタリング]]
-[[SVM]]
-[[凸二次計画]]
#br
-[[検索:サポートベクトルクラスタリング]]

** リンク集 [#w0355117]

//関連するWWW資源があればリンクしてください.

** 関連文献 [#j7da372e]

//この%項目%に関連する書籍や論文を紹介してください.

-基本文献:フルペーパー~
A.Ben-Hur, D.Horn, H.T.Siegelmann, and V.Vapnik "Support Vector Clustering", JMLR, vol.2, pp.125-137 (2001)~
[[GoogleScholarAll:Support Vector Clustering]]
-基本文献:国際会議~
A.Ben-Hur, D.Horn, H.T.Siegelmann, and V.Vapnik "A Support Vector Clustering Method", ICPR2000~
[[GoogleScholarAll:A Support Vector Clustering Method]]
- 同様の手法を同時期に提案~
D.M.J.Tax and R.P.W.Duin "Support Vector Domain Description", Pattern Recognition Letters, vol.20 (1999)~
D.M.J.Tax and R.P.W.Duin "Support Vector Domain Description", Machine Learning, vol.54 (2004)~
[[GoogleScholarAll:Support Vector Domain Description]]

トップ   編集 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS