パターン認識ー最近傍識別理論ー担当：和田俊和部屋 A513 Email

パターン認識
ー最近傍識別理論ー
担当：和田俊和
部屋 A513
Email [email protected]
講義資料はhttp://wada1.sys.wakayama-u.ac.jp/PRA/
最も単純な識別方法
ー最近傍識別規則ー
A,B：クラス
ラベル
A
A
A
B
クラスAに属する
B
既知の
パターン
最近傍識別における識別境界
A
A
A
B
B
Voronoi分割
プロトタイプが複数ある場合の
識別境界
A
A
A
B
B
Voronoi Condensing
プロトタイプを少なくしても同じ結果が得られる。
プロトタイプ
Voronoi Condensing によって求めたプロトタイプを
用いても最近傍識別の性能は変わらない。
Voronoi Condensingの実例
Delauneyグラフも灰色の線で表示されている。
Gabriel Editing
さらにプロトタイプを減らす
パターンを直径として持つ超球を考え、この超球内部に
他のパターンが含まれていないときにプロトタイプとする。
Gabriel Condensing の実例
Gabriel Editing の結果は
Voronoi Condensing の結果とよく似ている。
最近傍識別と区分的線形識別関数
gi (x)  max {g i(l ) (x)}
l 1,, Li
d
g ( x)  w   w x j
(l )
i
(l )
i0
i  1,2,  , c
j 1
(l )
ij
誤り確率
• ある
x に対する誤り確率（2クラスの場合）
 P(1 | x)
Pe ( x)  
P(2 | x)
( x  2 )
( x  1 )
• Pe (x)を最小化するには、下記のように判断すれば良い
P(1 | x)  P(2 | x)  x  1

 P(1 | x)  P(2 | x)  x  2
P(1 | x)
P(2 | x)
Bayes誤り確率(要チェック)
• Bayes誤り確率（避けることのできない誤り率）
M
Pe   min [ P (i | x)] p ( x)dx
i 1
  Pe ( x) p ( x)dx
M
Pe ( x)  min [ P( x | i )]
i 1
P(1 | x)
P(2 | x)
最近傍識別器の誤り確率(2クラスの場合)
•
•
•
•
プロトタイプの集合 {x1 , , xn }
入力 xに対する最近傍パターン x' ( x' {x1 , , xn })
誤り確率 PNNerr ( x)  P(1 | x) P(2 | x' )  P(2 | x) P(1 | x' )
全ての x に対する誤り確率
PNNerr   PNNerror ( x) p( x)dx
lim x '  x
• 仮定
n
lim P(i | x' )  P(i | x) が成り立つ。
• したがって
n 
• このことから、
lim PNNerr ( x)  2 P (1 | x) P (2 | x)
n 
 2 P (1 | x){1  P (1 | x)}
 2 Pe ( x){1  Pe ( x)}
最近傍識別器のBayes誤り確率(2クラスの場合)
• Bayes誤り確率と最近傍識別器の誤り確率の比較
PNNerr   {lim PNNerr ( x)} p( x)dx
n 
  2 Pe ( x)(1 Pe ( x)) p( x)dx
PNNerr   2 Pe ( x)(1 Pe ( x)) p( x)dx
  ( Pe ( x)  Pe ( x))(1 Pe ( x)) p ( x)dx
 2 Pe (1  Pe )  2Var ( Pe ( x))
 P e   Pe ( x)(1 2 Pe ( x)) p( x)dx
 2 Pe (1  Pe )
 Pe
• したがって、2クラスの場合
Pe  PNNerr  2 Pe (1  Pe )
• Mクラスの場合の最近傍識別器の誤り確率
Pe  PNNerr
Pe 

 Pe   2  M

M 1

最近傍識別器のBayes誤り確率(2クラスの場合)
• 大量のデータが与えられる場合、全数記憶に基
づく最近傍識別器は漸近的にBayes誤り確率の2
倍未満が達成できる。
最近傍識別器の一般化
k-最近傍識別
• 入力パターン x に対して、最も近い k 個のプロトタイプを
探し、それらに対して割り当てられたクラスラベルのうちで、
最も多いクラスに分類する。
• これは、 x 付近での確率密度を近似計算し、その中で最も
高い確率密度を持つクラスに分類するということを行ってい
ることと等価である。
• この結果、少ないプロトタイプでも前述のBayes誤りの2倍未
満が達成されるようになる。
• 問題点は、Condensingアルゴリズムと併用できないことで
ある。

Download Report