K-NN法

核関数に基づく方法では、領域 $R$ の体積 $V$ を固定して、データから $K$ を決定するが、K-NN法では、逆に $K$ を固定して、$V$ を決定することによ り密度分布を推定する。点 $\mbox{\boldmath$x$}$ を中心とする超球を考え、その超球内に ちょうど $K$ 個のデータ点が含まれるまで超球の半径を大きくして行く。ちょ うど $K$ 個のデータ点が含まれるようになった超球の体積を $V(\mbox{\boldmath$x$})$ と すると、密度分布は式(28)から、

$$\tilde{p}(\mbox{\boldmath$x$}) = \frac{K}{N V(\mbox{\boldmath$x$})}$$ (35)

のように推定できる。

K-NN法では、超球に含まれるデータ点の個数 $K$ を大きくすると、推定され る密度分布は次第に滑らかになる。核関数に基づく方法の場合と同様に、滑ら かさを大きくしすぎると、バイアスが大きくなり良い推定結果が得られなくな り、滑らかさが不十分な場合には、密度分布が個々の学習データに強く依存す るようになり、推定結果の分散が大きくなってしまう。ここでも、滑らかさの パラメータを適切な値に決めることが重要となる。

パターン認識において確率密度分布を推定するのは、識別(classifier)を構成 するためであるが、K-NN法を利用して各クラスの条件付き確率密度分布 $p(\mbox{\boldmath$x$}\vert C_k)$ を推定すると、以下のような簡単な識別器が構成できる。

今、学習データとして、クラス $C_k$ から $N_k$ 個の特徴ベクトルが得られ たとする。また、全学習データ数は $N=\sum_{k=1}^L N_k$ とする。点 $\mbox{\boldmath$x$}$ を中心とする超球を考え、その中にちょうど $K$ 個の学習データを 含むまで超球の半径を大きくして行った時の超球の体積を $V(\mbox{\boldmath$x$})$ とす る。また、その超球内には、クラス $C_k$ のデータが $K_k$ 個含まれている とする。この時、クラス $C_ｋ$ の条件付確率密度関数は、

$$\tilde{p}(\mbox{\boldmath$x$}\vert C_k) = \frac{K_k}{N_k V(\mbox{\boldmath$x$})}$$ (36)

のように推定できる。同様に、 $\mbox{\boldmath$x$}$ の確率密度関数は、

$$\tilde{p}(\mbox{\boldmath$x$}) = \frac{K}{N V(\mbox{\boldmath$x$})}$$ (37)

となる。また、事前確率は、

$$\tilde{P}(C_k) = \frac{N_k}{N}$$ (38)

のように推定できるので、Bayes の定理より、事後確率は、

$$\tilde{P}(C_k\vert\mbox{\boldmath$x$}) = \frac{\tilde{P}(C... ...}\vert C_k)}{\tilde{p}(\mbox{\boldmath$x$})} = \frac{K_k}{K}$$ (39)

となる。従って、誤り確率を最小とするような識別のためには、この値が最大 となるクラスに識別すればよい。このような識別方法は、K-NN識別規則(K-NN classification rule)と呼ばれている。