![[PukiWiki]](image/ibisforest.png "[PukiWiki]")
点\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は入力の次元数)
ガウスカーネルを使うと球の周辺ほど密度の低い部分となるので，点密度の低い部分で分離するようなクラスタリングとなる．
-- しましま
