rastudylife

機械学習や統計についての勉強ログ

はじパタからみる識別規則2(距離編)

前回のエントリーでは識別規則が確率に基づいたケースについて学習した.
www.rastudylife.site

今回は識別規則を距離という観点から勉強する.



はじパタ第5章内容

  • 近傍法(NN法)

入力データxと一番ユークリッド距離の近い学習データx_j^{(i)}のクラスに識別する.
NN法の識別規則:識別クラス=arg 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)}) > t の時にリジェクト)tはどの学習データとも距離が大きい時にリジェクトするためのしきい値
各学習データの支配領域は隣接する学習データと等距離にある境界までであり,その境界をボロノイ境界といい,支配領域をボロノイ領域という
隣接する学習データのペアx_i,x_jの中心である平均ベクトル\overline{x}=x_i+x_jを通り,直交する超平面 (\overline{x}-x)^{T}n=0がボロノイ境界である.(n=x_i - x_j
近傍法は学習データの数が大きくなるほど誤り率は低くなる.

  • k最近傍法(kNN法)

最近傍のk個の学習データの多く所属するクラスを識別クラスとする.
kNN法の識別規則:識別クラス=j \{k_j\}=max\{k_1...k_K\}のとき)
\{k_i,...,k_j\}=max\{k_1...k_K\}のときはリジェクト)
kNNの誤り率とベイズ誤り率の関係:\frac{1}{2}\epsilon^* \leq \epsilon_{2NN} \leq \epsilon_{4NN} \leq .... \leq \epsilon^{*} \leq .... \epsilon_{3NN} \leq \epsilon_{1NN} \leq 2\epsilon^{*}
ただし,この関係が成り立つのは漸近仮定(lim_{N \to \infty}   \tau_N \Rightarrow d(x, x_{1NN}) \to 0)が成り立つ時.
次元が大きくデータが一様分布しているときは漸近仮定は成り立たない.
kNN法はデータの次元が多い時に計算量が多く大変.誤って識別されたデータを全て削除する誤り削除型kNNや,識別に寄与しないデータを学習データから削除する圧縮型kNN,学習データと入力データの距離計算を効率的に行う分枝限定法,近似最近傍探索といった,kNN法の欠点を補う方法がある.

漸近仮定がよく理解できなかった.要復習.