機械学習・Pythonお勉強（k最近傍法を例にして　理論編）

はじめに

　以下の記事の続き。

abcxyzonetwothree.hatenablog.com

　今回は理論編と実践編を分けて書く。理由は、理論編では数式が多く登場するが、Markdown方式で書くと、おそらくその記号のバッティングで書けない数式が出てくる。したがって、理論編ではMarkdown方式ではない形で記事を書く。理論といっても大したものではないが。

　一方で、Markdown方式だとコードに色が簡単について良いし、何と言っても書きやすい。したがって、実践編ではMarkdown方式で書く。

k最近傍法とは

　k最近傍法とはあるデータが与えられた際にそのデータと全ての学習データとの距離を計算し、最もその距離が近いk個の学習データが属するクラスによってその与えられたデータの所属クラスを決定する方法である。なお、k個の学習データの所属するクラスが互いに異なる場合は多数決によって決定する。なお、『はじめてのパターン認識』にはその距離はユークリッド距離で計算すると明記されている。

　なお、ある閾値tを設定しておきその閾値tよりも、データと最もそのデータに近い学習データとの距離が大きければ判断を保留する（リジェクトする）事も可能である。またk ≧ 2の時、そのk個の学習データの所属するクラスが異なり、多数決によって投票数がタイになった場合にもリジェクトする事も可能である。あるいは、タイになった時はランダムにどちらかのクラスに分類することも可能である。

　一般的には学習データが増えればその識別性能も向上する。

k最近傍法とベイズ誤り率

　k最近傍法とベイズ誤り率との間には密接な関連が存在する。ここで、ベイズ誤り率について復習をしておく。

　ベイズ識別規則に従えば、事後確率が大きい方にデータ $x$ を分類する。すなわち、 $P(C_1 | x)$ と $P(C_2 | x)$ を比較する。ただし、これらの確率は観測されないのでベイズの定理から以下の式を比較する。それらは、 $\frac{P(x | C_1)P(C_1)}{P(x)}$ と $\frac{P(x | C_2)P(C_2)}{P(x)}$ である。ただし、 $P(x)$ は分母に共通して現れるのでこれは考慮しなくて良い。したがって、 $P(x | C_1)P(C_1)$ と $P(x | C_2)P(C_2)$ を比較することになる。

　ここで、本当はデータ $x$ が所属するクラスが $C_1$ にも関わらず、誤って $C_2$ に分類してしまう確率あるいはその逆の期待値である。まず、その確率（条件付きベイズ誤り率）は事後確率の小さい方となるので、以下のように表現できる。

$\epsilon(x) = min(P(C_1 | x), P(C_2 | x))$

　その期待値（ベイズ誤り率）は期待値の定義から以下の通りである。

$\epsilon^* = \int \epsilon(x) P(x) dx$

この時、以下の関係が成立する事が知られている（証明は『はじめてのパターン認識』を確認されたい）。

$\frac{1}{2} \epsilon^* ≦ \epsilon_{2NN} ≦ \epsilon_{4NN} ≦ ... ≦ \epsilon^* ≦ ... ≦ \epsilon_{3NN} ≦ \epsilon_{1NN} ≦ 2\epsilon*$

　ここで、例えば\epsilon_{2NN}とはkNN法の誤り率においてk = 2の場合の誤り率を意味する。よって、概してkが偶数の時の誤り率は奇数の時の誤り率と比べて小さい傾向にあり、特にその界はベイズの誤り率によって決まっている。

k最近傍法における工夫

　k最近傍法は学習データとの距離を逐一求めなければならないため処理が重い。そこでいくつかの改善手法が提案されている。それらは、誤り削除型kNN、圧縮型kNN、分岐限定法、近似最近傍探索である。

誤り削除型kNN

　誤り削除型kNNは誤って識別されたデータを削除してしまうことを考える。おそらくこの削除の仕方はいくつか考えられる。その1つとして以下のような方法が考えられる。まず、学習データを2つに分けておき、一方で学習させ片方でそれを評価する。この評価するデータには正解が存在するため、どのデータが誤って分類されているかがわかる。例えば、データセット $D$ を $D_1$ と $D_2$ とに分けておく。 $D_1$ によって学習させ、 $D_2$ によってテストする。そうすると、 $D_1$ によって分類された $D_2$ の中で誤分類されたデータが出てくる。それらを削除する。削除後のデータを $D_{2edit}$ とする。この $D_{2edit}$ を新たな学習データとして学習させる。これを繰り返しても良い。このようにすれば、削除後のデータ数はどんどん減っていくため計算量が節約される。

圧縮型kNN

　これは識別に寄与しないデータを削除してしまう事を考える。境界付近のデータは識別する上で重要な役割を果たすが、それ以外のデータはkNN最近傍法においては関係がない。すなわち、明らかにクラスAに属しているデータを削除しておき、クラスAかクラスBか微妙なデータのみを用いる方法である。それではどのようにその削除する基準を決定するのか。1つの方法として条件付きベイズ誤り率を用いる方法がある。すなわち、識別に寄与しないデータは、そのデータを削除しても条件付きベイズ誤り率を増加させないデータと考える。ここで、条件付きベイズ誤り率は以下の通りであった。

$\epsilon = min(P(C_1 | x), P(C_2 | x))$

　この値が削除後のデータと削除前のデータで同じかそれ以下になるようにして、試行錯誤しながら削除するデータを探す。

分岐限定法

これはまず階層構造のあるクラスタリング分析によって学習データをクラスタリングする。

abcxyzonetwothree.hatenablog.com

　これによってできたクラスターを階層構造の上から $S_1, S_2, S_3, ... , S_c$ とする。もちろん、この階層構造内では同率の階層であるクラスターも存在するので、全てに上下関係があるわけではない。ここで、クラスが未知のテストデータのクラスを分類する事を考える。まず階層構造内の上から、各クラスターに属するデータの平均ベクトルと比較しながら、階層構造内の最も下位にあるクラスターまで下がっていく。トーナメント表の上から下まで各クラスターの平均ベクトルを基準としながら下がっていくイメージである。次に、階層構造内の一番下位のクラスターの中で最も距離が近いデータとの距離を計算する。仮に、この距離を $d(x, x_i)$ としておこう。続いて、トーナメント表を1つ戻り、平均ベクトルを基準とした時に2番目に近かった階層構造内の同率最下位のクラスターとの平均ベクトルとの距離を計算する。仮に、この距離を $d(x, m_c):$ としておこう。さらに、このクラスターの平均ベクトルから最も遠いデータとの距離を $d$ としておこう。この時、以下が成立していれば最初のクラスター（平均ベクトルを基準としてトーナメント表を下がっていった時の最下層にあるクラスター）を分類されるべきクラスとする。

$d(x, m_c) ＞ d(x, x_i) + d$

近似最近傍探索

　これはその名の通り「最近傍」のデータを探すのではなくある一定の近さなら良しとする「近似最近」のデータを探す方法である。ここである入力データ $q$ を考える。入力データ $q$ と「最近傍」のデータを $x^*$ 、「近似最近傍」のデータを $x$ とすると以下を満たす $x$ を探す。

$d(q, x) ≦ (1 + \epsilon)d(q + x^*)$

　なお、 $\epsilon$ は正なのでこれは以下と同値である。

$\frac{d(q, x)}{(1 + \epsilon)} ≦ d(q + x^*)$

　つまり、「最近傍」のデータよりも $1+\epsilon$ 倍までを許容する。この $\epsilon$ の値は試行錯誤で決定する。

　それでは、どのようにして「近似最近傍」のデータを上記の条件下で探すのか。ここではまず、2分木の決定木分析によってデータを分類しておく。なお、決定木分析については改めて論じたい。クラスを推定したい入力データ $x$ と（決定木分析によって決定された）同一領域内に属しているデータとの距離を算出する。この距離を $d(x, a)$ としておこう。ここで、以下を計算する。