k最近傍法(kNN法)

最近傍法近い鋳型にブちこむ k最近傍法近いk個の鋳型の中から一番たくさん入っている鋳型にブちこむ

最近傍法とボロノイ境界

K個のクラス$Ω={C_1,…,C_k}$,$i$番目のクラスの学習データ数$N(i)$, その集合$S_i$

最近傍法(NN法)

入力データ$x$と各学習データの類似度をユークリッド距離で計算する。 学習データのことを鋳型とも呼ぶ。

ユークリッド距離

$d(x,x_j^{(i)}) = ||x-x_j^{(i)}||$

最近傍法の識別規則

$識別クラス = \left\{\begin{matrix} \min_{i} \{\min_{j} d(x,x_j^{(i)})\} & \min_{i,j} d(x,x_j^{(i)}) < t のとき \\\ リジェクト & \min_{i,j} d(x,x_j^{(i)}) \leq t のとき \end{matrix}\right\}$

ボロノイ図

p55 図5.1参照
鋳型●■▲で示される鋳型は隣接する 鋳型と等距離にある境界にある境界で囲まれた領域を持つ。これを ボロノイ領域。また、その境界をボロノイ境界と言う

鋳型の数と識別性能

最近傍法による認識率は学習データ数が多くなれば良くなる。
p58 図5.6参照

kNN法

k最近傍法、投票型kNN法とも呼ばれる。

kNN法の識別規則

$識別クラス = \left\{\begin{matrix} j {k_j} = max{k_1,...,k_K}のとき\\ リジェクト {k_i,...,k_j} = max{k_1,...,k_K}のとき$

得票数が同じ場合はリジェクトとしているが、ランダムにどれかの クラスを識別クラスにするような規則でも良い。

最近傍法とk最近傍法を比較

• k=1最近傍法
  孤立点が現れる

k=11最近傍法
孤立点はなくなりなめらかな境界となる。 kを大きくすると、入力データから離れた鋳型も投票に入るので 識別制度が下がる。

kNN法とベイズ誤り率

kNN法の計算量とその低減法

クラス番号 $i=1,…,K$
鋳型 $j=1,…,M$
データの次元 d
この場合入力データxが与えられた時 $d^2(x,x_j^{i}) = (x-x_j^{i})^T(x-x_j^{i})$ $KMlog(KM)$
多くの時間と記憶容量が必要、 実時間認識には向いていない手法である。

誤り削除型kNN

本来正しい領域にあるデータも誤ってしまうことがあり、 ベイズ誤り率より高い確率で誤りが発生する。これを 避けるためm、正しくないクラスの領域に存在している学習データを削除する。

???????

圧縮型kNN

kNN法はベイズ境界付近のデータが重要で、分布中央のデータはいらん。 したがって、識別に寄与しないデータを学習データから削除して節約をする。

試行錯誤により閾値を決める必要がある。

分岐限定法

近似最近傍探索