* 最大マージンクラスタリング (maximum margin clustering) [#c90d0d17]
//ここには %項目の説明を書いてください．よろしければ署名しておいてください．
マージン最大化に基づく教師ありの手法と同じ枠組みでクラスタリングをする手法．
教師ありの場合は，正例と負例の間のマージンを最大化する．これを教師なしにするために，\(N\) 個の事例に，正と負の全ての可能なラベル割り当てを考える．各割り当てでマージンを最大化し，これらの中でマージンを最大化する場合に対応するラベルの割り当てをクラスタリングの結果とする．
ただし，全データが同じラベルだと，マージンは無限大となるが意味はないので，正負クラスの大きさの差に制限を設ける．
さらに，データを事前に中心化しておき，識別面のオフセットは 0 とする．
これらの条件を満たす問題を考えると，次の凸整数計画問題として定式化できる．
\[\min_{M\in\{-1,+1\}^{N\times N}} \max_{\boldsymbol{\lambda}} 2 \boldsymbol{\lambda}^\top\mathbf{e}-\langle K\circ\boldsymbol{\lambda}\boldsymbol{\lambda}^\top,M\rangle\]
subject to
- \(0\le\boldsymbol{\lambda}\le C\)
- L1: \(m_{ii}=1;\; m_{ij}=m_{ji};\; m_{ik}\ge m_{ij}+m_{jk}-1;\;\forall {ijk}\)
- L2: \(m_{jk}\ge -m_{ij}-m_{ik}-1;\;\forall {ijk}\)
- L4: \(-\ell\le\sum_i m_{ij}\le\ell;\;\forall j\)
ただし，\(\mathbf{y}\) をラベル \(\{-1,+1\}\) の割り当てベクトルとして，行列 \(M=\mathbf{y}\mathbf{y}^\top\)，\(\circ\) は行列の要素ごとの積，\(\mathbf{e}\) は1ベクトル，\(K\) はグラム行列，\(C\) と \(\ell\) はパラメータ．
凸整数計画問題は離散最適化の中では解きやすい方だが，実用的にはまだ計算は大変．そこで，\(M\) が整数である制約をはずし次の半正定値計画問題に変換する．
\[\min_{M,\delta,\boldsymbol{\mu},\boldsymbol{\nu}}\delta\]
subject to L1, L2, L3, \(\boldsymbol{\mu}\ge0\)，\(\boldsymbol{\nu}\ge0\)，\(M\)は半正定値，\(\left[\begin{array}{cc}M\circ K&\mathbf{e}+\boldsymbol{\mu}-\boldsymbol{\nu}\\ (\mathbf{e}+\boldsymbol{\mu}-\boldsymbol{\nu})^\top&\delta-2C\boldsymbol{\nu}^\top\mathbf{e}\end{array}\right]\succeq 0\)
このときの解の行列を \(M^\ast\) とし，その最大固有値を \(\lambda_1\)，それに対応する固有ベクトルを \(\mathbf{v}_1\) とする．そして実数に緩和した割り当てベクトルは \(\mathbf{y}=\sqrt{\lambda_1}\boldsymbol{v}_1\) となる．
> -- しましま
** 関連項目 [#i450ce4c]
//英語や同義語のあとに，#brで区切って関連する項目をリストしてください．
-[[maximum margin clustering]]
#br
-[[SVM]]
-[[クラスタリング]]
-[[半正定値計画]]
-[[整数計画]]
#br
-[[検索:最大マージンクラスタリング MMC]]
** リンク集 [#cf91d268]
//関連するWWW資源があればリンクしてください．
-[[最大マージンクラスタリング>http://hillbig.cocolog-nifty.com/do/2008/12/post-0772.html]] @ DO++
** 関連文献 [#daacb6c1]
//この%項目%に関連する書籍や論文を紹介してください．
-基本文献~
L.Xu, J.Neufeld, B.Larson, and D.Schuurmans, "Maximum Margin Clustering", NIPS17 (2005)~
[[GoogleScholarAll:Maximum Margin Clustering]]
![[PukiWiki]](image/ibisforest.png "[PukiWiki]")
