局所性保存射影 (Locality Preserving Projection, LPP)とラプラス固有写像 (Laplacian Eigenmap)

次元削減手法の局所性保存射影とラプラス固有写像について.これらは局所性を保存する,という特性がある.局所性とはデータの局所的な構造のことで,例えばクラスタ構造なんかがそれに当たる.PCAも含めて,これらは全て固有値問題を解くことで解を求める.この二つの手法は密接に関係している.整理のためのポスト.

局所性保存射影V \in \mathbb{R}^{d \times k}は,データ\{x_i\}_{i=1}^n, \ x_i \in \mathcal{X} \subseteq \mathbb{R}^d, \ \forall i=1,\ldots,nとその類似度行列Wを入力とし,以下の一般化固有値問題の解である.

XLX^Tv=\lambda XDX^Tv

ここで,X=[x_1|\cdots|x_n], \ D=diag(\sum_{j=1}^n W_{1j}, \ldots, \sum_{j=1}^n W_{nj}), \ L=D-Wである.これをカーネル化することを考える.X\Phi=[\phi(x_1)|\cdots|\phi(x_n)]で置き換えて,

\Phi L \Phi^Tv=\lambda \Phi D \Phi^Tv

を得る.例のごとく,v=\Phi \alphaと置くと,

KLK\alpha=\lambda KDK\alpha

を得て,これがカーネルLPP.さらに,\beta=K\alphaとおくと,

L\beta=\lambda D\beta

となり,これがラプラス固有写像.

カーネルLPPで得られた射影行列V=[v_1 | \cdots | v_k]=\Phi [\alpha_1|\cdots|\alpha_k]=\Phi Aを用いて,データXは,V^T \Phi = A^TKと埋め込まれる.ちなみに,ラプラス固有写像の解はB=[\beta_1 | \cdots | \beta_k]=KAであり,B^TはカーネルLPPでサンプルを射影した結果に一致する!つまり,データにカーネルLPPを施したもの=ラプラス固有写像の解,である.

カーネルLPPによって,元のデータはある特徴空間へ射影される.ラプラス固有写像はその結果をダイレクトに求める.ラプラス固有写像は局所性,例えばクラスタ構造を保存するので,クラスタリングの前処理に適しているとされている.ラプラス固有写像を施した後にK-Meansなどのクラスタリングをする手法はスペクトラルクラスタリングと呼ばれ,ものすごく研究されている.

以上自分用メモ.

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中