PCA(Principal Component Analysis)とLPP(Locality Preserving Projection)をPythonで実装

こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。

今回は教師なし線形次元削減の手法であるPrincipal Component Analysis(PCA)とLocality Preserving Projection(LPP)について書きます。最後にはPythonでの実装を載せて実験します。

### 教師なし線形次元削減

教師ラベルなしで、データの次元を落とす手法です。

データの次元を落としたいという状況はよくあります。
機械学習のモデルに入力するデータの次元が大きすぎると性能に響きます。次元の呪いとか言われたりします。

他にも、例えばDeepなモデルを学習したあとの潜在表現を取り出して可視化したい、という場合にも次元削減が使えます。

一般にDeepなモデルで得られる潜在表現は次元が2とかではなくもう少し高次元なので、人間の目では見ることができませんが、今回紹介するPCAなどを使って2次元や3次元に圧縮することで可視化が可能になります。

### PCA

教師なし線形次元削減の手法としてPCAは割と有名だと思います。
自分も今回勉強する前からPCAは知っていました。

PCAでは、データを分散が大きい方向を新たな軸としてデータを変換します。

いろんな値を取るような方向は情報が大きいよね、という気持ちです。
逆にどのデータも同じような値しか取らないような軸はあってもデータを表現するのに役立たないので、そういう軸は使いたくないですね。

アルゴリズムとしては

1. データから分散共分散行列をつくる
2. 固有値分解する
3. 固有値が大きい順に固有ベクトルを$m$個とってきて並べる
4. 3で作った行列$T$がPCAを行う線形変換の行列

$T$をデータにかければ低次元$m$の表現が得られます。

今回は自分で実装しますが、PCAはscikit learnにもあるので手軽に使えます。

### LPP

PCAでは単純にデータの中で広がりのある方向の軸を見つけてきてその軸で測る、ということをやっていました。

PCAの弱点として、

「もともとのデータのクラスター構造を壊してしまうことがある」

ということがあります。

これに対処するために、類似度行列$W$というものを考えます。

類似度行列の各成分$W_{i,i'}$はデータ$x_i$と$x_{i'}$が近いかどうかを表します。

線形変換$T$を次のlossを最小にするように学習します。

$$
\sum_{i,i'=1}^n W_{i,i'}||Tx_{i}-Tx_{i'}||^2
$$

似ているデータは近くにmappingしようね、という気持ちが現れています。

単純にこれをminimizeすると$T$が零行列になってしまうので、縮退を防ぐような制約のもと、最適化します。
簡単のため$X$は平均を0にしたものを考えます。

詳しい計算は省きますが、ラグランジュ未定乗数法を使うと以下の一般化固有値問題に帰着できます。

$$
(XLX^T)v = \lambda (XDX^T)v
$$

$D$は類似度行列$W$の次数行列、$L$はラプラシアン($L=D-W$)です。

これをといて、固有値を昇順に並べたものに対応する一般化固有値ベクトルを$m$個並べたものがLPPを行う線形変換$T$です。

手順のまとめとしては

1. データからW,D,Lを計算する
2. 一般化固有値問題$(XLX^T)v = \lambda (XDX^T)v$を解く
3. 固有値が小さい順に一般化固有ベクトルを$m$個とってきて並べる
4. 3で作った行列$T$がLPPを行う線形変換の行列

です。

### 実装

PCAとLPPをPythonで実装しました。

```python
class PCA:
    """Pricipal Component Analysis"""

def __init__(self, n_components):
        self.n_components = n_components

def fit(self, X):
        self.mean_ = np.mean(X, axis=0)
        self.cov_ = self.get_covariance(X)
        eig_val, eig_vec = np.linalg.eig(self.cov_)
        eig_vec = np.array(eig_vec).T
        index = np.argsort(-eig_val)
        eig_vec = eig_vec[index]
        self.components_ = eig_vec[:self.n_components, :]
        return self.components_

def transform(self, X):
        return self.components_ @ X

def get_covariance(self, X):
        z = X - self.mean_
        return np.cov(z[:, 0], z[:, 1], bias=1)

```

```python
import numpy as np
import math
from scipy.linalg import eigh

class LPP:
    """Locality Preserving Projection."""

def __init__(self, n_components, h=1 / np.sqrt(2)):
        self.n_components = n_components
        self.h = h

def fit(self, X):
        X = X - np.mean(X, axis=0)
        W = self.create_similarity_matrix(X)
        D = self.get_degree_matrix(W)
        L = D - W
        A = X.T @ L @ X
        B = X.T @ D @ X
        eig_val, eig_vec = eigh(A, B)
        index = np.argsort(eig_val)
        eig_vec = eig_vec[index]
        components = []
        for vec in eig_vec:  # normalize
            normalized_vec = vec / np.linalg.norm(vec)
            components.append(normalized_vec)
        self.components_ = np.array(components[:self.n_components])
        return self.components_

def gaussian_kernel(self, x_i, x_j):
        """kernel function"""
        return math.e**(-np.dot(x_i - x_j, x_i - x_j) / (2 * self.h**2))

def get_degree_matrix(self, W):
        return np.diag([sum(W[i]) for i in range(len(W))])

def create_similarity_matrix(self, X):
        """create Similarity matrix

:param X: data matrix (data_nX,feature_n)
        """
        W = []
        for x_i in X:
            K_i = []
            for x_j in X:
                K_i.append(self.gaussian_kernel(x_i, x_j))
            W.append(K_i)
        return np.array(W)

```

固有値問題や一般化固有値問題の部分はnumpyやscipyを使っていますが、この時にかえって来る固有値はsortされているとは限らないらしいので、自分でsortします。

PCAは降順sortですが、numpyのargsortはdefaultで昇順でoptionもないので、マイナスをつけてargsortに渡しています。

また、numpyとscipyのsolverで固有ベクトルの並ぶ方向が違っていました。

`numpy.linalg.eig`では固有ベクトルが列ベクトルになっていて、`scipy.linalg.eigh`では行ベクトルと成っていたので、PCAでは転置しています。

### 実験

クラスター構造があるものとないものの二種類の人工データを生成しました。

生成したデータはこちら。

これらに対してPCAとLPPを試してみます。

まずPCAから。図中の直線は第一固有ベクトルの方向です。次元削減した後の一番目の軸、と思ってください。

クラスター構造のあるなしに関わらず、広がりの大きいx1方向を第一固有ベクトルとしてとっていることがわかります。クラスター構造を考慮していないというPCAの弱点があったという話だったので、この結果は妥当です。

次に、LPPを実行してみると、次のようになります。

クラスター構造がない場合はPCAと似ていますが、クラスター構造がある場合のLPPは広がりの大きいx1方向ではなくクラスターが存在するx2方向を新しい軸としてとってきていることがわかります。

### まとめ

教師なし線形次元削減の手法としてPCAとLPPを簡単にまとめて、pythonで実装して人工データを用いて実験をしました。

結果、クラスター構造を考慮しないPCAと比較して、LPPがクラスターの存在する方向にデータを射影していることがわかりました。

PCAはscikit learnにあるので簡単に試すことができるので、気になった方は試してみるといいと思います。

ありがとうございました。

このブログを検索

ぐぐりらにっき

PCA(Principal Component Analysis)とLPP(Locality Preserving Projection)をPythonで実装

コメント

コメントを投稿

PCA(Principal Component Analysis)とLPP(Locality Preserving Projection)をPythonで実装

この記事をシェアする

コメント

コメントを投稿