最大マージンクラスタリング

これらのキーワードがハイライトされています：最適化 optimization

最大マージンクラスタリング (maximum margin clustering)†

マージン最大化に基づく教師ありの手法と同じ枠組みでクラスタリングをする手法．

教師ありの場合は，正例と負例の間のマージンを最大化する．これを教師なしにするために，\(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\) となる．