WPR-8

パターン認識
ー最近傍識別理論ー
担当：和田俊和
部屋 A513
Email [email protected]
講義資料はhttp://wada1.sys.wakayama-u.ac.jp/PR/
最も単純な識別方法
ー最近傍識別規則ー
A-E：クラス
ラベル
C
A
B
D
クラスBに属する
E
標準パターン
（プロトタイプ）
最近傍識別における識別境界
C
A
B
D
E
Voronoi分割
プロトタイプが複数ある場合の
識別境界
A
A
A
B
B
大量のデータが与えられる場合、全数
記憶に基づく最近傍識別器は漸近的に
Bayes誤りの2倍未満が達成できる。
Voronoi Condensing (Editing)
プロトタイプを少なくしても同じ結果が得られる。
プロトタイプ
Voronoi Condensing によって求めたプロトタイプを
用いても最近傍識別の性能は変わらない。
Voronoi Condensingの実例
Delauneyグラフも灰色の線で表示されている。
Gabriel Condensing (Editing)
さらにプロトタイプを減らす
パターンを直径として持つ超球を考え、この超球内部に
他のパターンが含まれていないときにプロトタイプとする。
Gabriel Condensing の実例
Gabriel Condensing の結果は
Voronoi Condensing の結果とよく似ている。
プロトタイプ
パターンが近接している部
分ではほとんど同じ識別面
が得られる。
Gabriel Condensing の結果は
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(i | x)]
i 1
P(1 | x)
P(2 | x)
最近傍識別器のBayes誤り確率(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

最近傍識別器の一般化
k-最近傍識別
• 入力パターン x に対して、最も近い k 個のプロトタイプを
探し、それらに対して割り当てられたクラスラベルのうちで、
最も多いクラスに分類する。
• これは、 x 付近での確率密度を近似計算し、その中で最も
高い確率密度を持つクラスに分類するということを行ってい
ることと等価である。
• この結果、少ないプロトタイプでも前述のBayes誤りの2倍未
満が達成されるようになる。
• 問題点は、Condensingアルゴリズムと併用できないことで
ある。

Download Report