分類アルゴリズムいろいろ （２）

#はじめに
こんにちは、supercellです。復習のために分類アルゴリズムをまとめていきたいと思います。
#目次
1．カーネルSVM
2．決定木
3．ランダムフォレスト
4．k近傍法(KNN)
#1．カーネルSVM
カーネルSVMとは、線形分離不可能なデータを高次元空間へ射影して線形分離できるようにする手法です。
しかし、高次元空間へ射影するとき、かなりの計算量が必要となります。そのため、「カーネルトリック」を用います。

まず、カーネル関数を定義します。

\kappa(x^{(i)},x^{(j)})=\phi(x^{(i)})^T\phi(x^{(j)})\tag{1}

最も使用されているカーネルの一つは、動径基底関数カーネルです。このカーネルはRBFカーネル、ガウスカーネルとも呼ばれます。

\kappa(x^{(i)},x^{(j)})=\exp\Biggl(-\frac{||x^{(i)}-x^{(j)}||^2}{2\sigma^2}\Biggl)\tag{2}

この関数は、次のように簡略化されます。

\kappa(x^{(i)},x^{(j)})=\exp\biggl(-\gamma||x^{(i)}-x^{(j)}||^2\biggl)\tag{3}

$\gamma=\frac{1}{2\sigma^2}$は、ハイパーパラメータです。
「カーネル」は、「類似性を表す関数」と解釈することができます。べき乗部分が0から無限大の値をとるため、カーネル関数の値は0から1までの値に収まります。

以上が、カーネルSVMの簡単な説明となります。

#2.決定木
決定木学習は、得られた結果の意味を解釈したい場合に有効なモデルです。
このモデルでは、一連の質問を学習して、クラスラベルを推測します。特徴量が実数値の場合は、しきい値を設定して、その値を超えるかどうかで推測することになります。
決定木のアルゴリズムでは、情報利得が最大となる特徴量でデータを分割します。情報利得は、分割された集合の要素についてのばらつきの減少を表します。
ばらつきの減少がなくなる（葉が純粋になる）まで、分岐条件（子ノード）を繰り返していきます。

情報利得を最大とするように分割するためには、最適化する目的関数を定義する必要があります。

IG(D_p,f)=I(D_p)-\sum_j\frac{N_j}{N_p}I(D_j)\tag{4}

ここで、$f$は分割を行う特徴量であり、$D_p$は親のデータセット、$D_j$は$j$番目の子ノードのデータセットです。$I$は不純度を数値化したものであり、$N_p$は親ノードのサンプルの総数、$N_j$は$j$番目の子ノードのサンプルの個数です。このように、情報利得は親ノードの不純度と子ノードの不純度の合計の差にすぎません。つまり、子ノードの不純度が低いほど、情報利得は大きくなります。
ほとんどのライブラリでは、組み合わせ探索空間を減らすために、二つの子ノードに分割します。

二分決定木で使用される不純度の分割条件は、ジニ不純度、エントロピー、分類誤差の3つです。
まずは、エントロピーの定義です。

I_H(t)=-\sum_i p(i|t)\log_{2}p(i|t)\tag{5}

$p(i|t)$は、あるノード$t$においてクラス$i$に属するサンプルの割合を表します。
そのため、エントロピーが最大となるのは、各クラスが一様に分布している場合となります。二値分類では、二つのクラスにそれぞれ属する確率が$0.5$であるとき、最大となります。

ジニ不純度は、誤分類の確率を最小化する条件であると解釈できます。

I_G(t)=\sum_i p(i|t)(1-p(i|t))=1-\sum_i p(i|t)^2\tag{6}

エントロピーと同様、ジニ不純度が最大となるのは、クラスが一様に分布しているときです。

分類誤差は、決定木の深さを調整する際に用いられます。

I_E(t)=1-\max{p(i|t)}\tag{7}

分類誤差は、エントロピーやジニ不純度にくらべて、決定木を深くさせるには向いていません。

以上が、決定木の説明となります。

#3.ランダムフォレスト

ランダムフォレストは、複数の決定木を平均化して汎化性能を高めることができるモデルです。
このモデルでは、以下の手順で学習していきます。

1. トレーニングデータから$n$個のサンプルを選ぶ
2. $d$個の特徴量を非復元抽出して、決定木を成長させる。
3. 1、2の手順を$k$回繰り返す。
4. 手順ごとで、多数決でクラスラベルを割り当てる。

ランダムフォレストの利点として、調整するパラメータが少ないことが挙げられます。基本的には、手順を繰り返す$k$の値を調整するだけで済みます。このようなアンサンブルな学習では、個々の値のノイズに強いという特徴があります。そのため、決定木の深さを調整する必要がありません。

抽出する特徴量の個数$d$は最適化が可能です。
scikit-learnでは、デフォルトで$d=\sqrt{m}$と設定されています。ここで、$m$はトレーニングサンプルの特徴量の個数です。

以上がランダムフォレストの説明となります。

#4.k近傍法(KNN)

k近傍法は、今までのアルゴリズムと異なり、クラスを分類させる判別関数を学習しません。
代わりに、トレーニングデータを暗記します。
具体的には、以下の手順で学習します。

1. kの値と距離指標を選択する。
2. 分類したい点に最も近いサンプルをk個選択する。
3. 多数決によってクラスラベルを割り当てる。

このアルゴリズムの利点として、新しいトレーニングデータにすぐに順応することができます。しかし、サンプル数が増加するにつれて、計算量も増えてしまう欠点があります。

うまく学習させるには、、距離指標の選択と、データの標準化が重要となります。
距離指標は、多くの場合、ユークリッド距離が使用されます。

d(x^{(i)},x^{(j)})=\sqrt[p]{\sum_k|x^{(i)}-x^{(j)}|^p}\tag{8}

$p=2$の時に、ユークリッド距離と呼ばれます。この距離では、データを標準化しておくことが重要となります。他にも様々な距離指標があるので、調べて見てください。

#おわりに
様々なアルゴリズムを見てきましたが、数学的な知識を必要とするものが出てきました。(例えば、SVM)この本に合わせて数学も勉強する必要がありますね。

#参考文献
Python機械学習プログラミング