Eigenvalue Sensitive Feature Selection - 甲斐性なしのブログ

クラスタリングや分類などを行う際、なるべく冗長となる特徴量は取り除いてから
行った方が精度や実行時間の観点で有効だとされています。
この「冗長となる特徴量を取り除く」方法は特徴選択と呼ばれ、
これまでに多数の手法が提案されています。
ということで今回は、新たな特徴選択手法を提案している論文

Yi Jiang , Jiangtao Ren
Eigenvalue Sensitive Feature Selection (ICML2011)

を読んでみました（以下、この論文の提案手法をESFSとします）。

具体的な方針としては、ある特徴を変化させた（取り除いた）とき、
Laplacian Eigenmaps（Belkinらによって提案されたグラフラプラシアンを利用した次元削減手法。以下、LE）
の結果にどれだけ影響を及ぼすか計ろうというものです。
例えば $i$ 番目の特徴の変化が、LEの結果に多大な影響を及ぼすようなら、
その特徴は重要な特徴であり、
その逆に、あまり変化を与えないならば、その特徴は冗長な特徴 -> 取り除いてOK
という考え方です。

細かいことは置いておいて、早速、ESFSのアルゴリズムを。

と、その前に・・・

1つのサンプルの特徴ベクトルを ${\bf x}=(x_1 , x_2 , \cdots , x_K)^T$ と表します。
従って、その次元数は $K$ です。
サンプルは今、 $n$ 個あるとします。

すいません。
今度こそ、本当にアルゴリズムです。

1．各特徴に重み ${\bf w}=(w_1 , w_2 , \cdots , w_K)^T$ をかけたときの、
類似度行列を $S({\bf w})$ を以下のようにします。

$\displaystyle S({\bf w})_{ij} = \exp\left(-\frac{\sum_{t=1}^{K}(w_t({x}^i_t - {x}^j_t))^2}{2\sigma^2}\right)$

実際、アルゴリズム上では ${\bf w}=(1,1,\cdots,1)^T$ のときの $S({\bf w})$ が必要になります。
つまり、ここではLE等でおなじみの「普通の」類似度行列 $S$ を計算しておきます。

2．一般化固有値問題 $L({\bf w}){\bf q}({\bf w})_r=\lambda_r({\bf w})D({\bf w}){\bf q}({\bf w})_r$ を解きます。
$D({\bf w})$ は、 $D({\bf w})_{ii} = \sum_{j}S({\bf w})_{ij}$ となる要素を持つ対角行列、
$L({\bf w})$ は、 $L({\bf w})=D({\bf w})-S({\bf w})$ です。
これまた全変数が ${\bf w}$ の関数となっていますが（ $S$ が ${\bf w}$ の関数であるため）、
実装上は、 ${\bf w}$ は考える必要ありません。
従って、ここまではLEとほぼ同じ操作を行うことになります。

3．各特徴のeigenvalue sensitive criterion（EVSC）を求めます。
このEVSCが、各特徴のLEの結果に与える影響、
つまり、特徴の重要度となります。
式の導出過程等の解説は論文の方に譲って、
ここでは、最終的な計算式のみ記述します。

$\displaystyle {\rm EVSC}(t)=\sum_{r=1}^n\|\frac{\partial \lambda({\bf w})_r}{\partial w_t}|{\bf w}=\bf{1}\|$

$\displaystyle \frac{\partial \lambda({\bf w})_r}{\partial w_t}=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}g(i,j,t)(q({\bf w})_{ri}-q({\bf w})_{rj})^2$
$\displaystyle \hspace{5em} - \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}g(i,j,t)(\lambda({\bf w})_r(q({\bf w})_{ri}^2+q({\bf w})_{rj}^2))$

$g(i,j,t)=-w_t\frac{(x_t^i - x_t^j)^2}{\sigma^2}S({\bf w})_{ij}$

ここで、 $q({\bf w})_{ri}$ は固有ベクトル ${\bf q}({\bf w})_{r}$ の $i$ 番目の要素を表します。
ちょっとだけ解説すると、 $t$ 番目の特徴量の重み $w_t$ を $1 \rightarrow 0$ へ変化させ、
それ以外の重みは $w_i=1 (i \neq t)$ と固定した場合の $\lambda({\bf w})_r$ の変化率は、
$\|\frac{\partial \lambda({\bf w})_r}{\partial w_t}|{\bf w}=\bf{1}\|$ で近似されます。
従って、全固有値についてその変化率を計算し合計すれば、
$t$ 番目の特徴の重要度が分かるという寸法です。
正直、この辺りの理解が微妙で、ちょっと納得できていない部分があるんですが・・・

何はともあれ、あとはEVSC値が高い特徴のみ残し、低い特徴は取り除けばOK。

実装して適当な疑似データ作って遊んでみました。
疑似データは、3次元のガウス分布 $N_1({\bf \mu}_1 = (2 , -1 , 0)^T , {\bf I})$ に従うサンプル100個、
ガウス分布 $N_2({\bf \mu}_2 = (-2 , 1 , 0)^T , {\bf I})$ に従うサンプル100個の計200個のデータです。

こんな感じ

やってみると、算出されるEVSC値には結構差が出ます。
1つ目の特徴が最も大きく、2つ目の特徴に比べ3倍くらいの値、
3つ目の特徴のスコアが最も小さく、2つ目の特徴に比べ1/3くらいの値になります。
そのため、上位2つの特徴のみ使用するとなった場合、
3つ目の特徴量が取り除かれることになります。
クラスタリング等を考慮すると、それっぽい結果なので、
うまくいっているんじゃないかなと思います。
満足満足。

とはいえ、特徴選択手法は疑似データでやっても、ちょっと面白みに欠けるかなと。
個人的には、特徴選択は実データで行って、
「この特徴とこの特徴の組み合わせが残るのかぁ、意外だな〜」などと、
発見する使い方が面白いと思います。

あと、python（+numpy、scipyモジュール）で実装したんですが、
馬鹿正直に上記の式をfor文使いまくって実装すると、やっぱりかなり遅いです。
高速化のためには、for文で計算している部分を行列計算になおすなど、
繰り返し構文をなるべく使わない工夫が必要になります。
実際にどのように実装したかは、気が向いたら書こうと思います。