探索方法の学習による識別の高速化

識別方法の一つに、最近隣識別法と呼ばれる方法があります。これは、クラスごとに確率分布を考えるのではなく、すべての収集データ（サンプル）と観測された未知パターンとの距離を計算し、距離の最も近いサンプルのクラスであると認識する方法です。例えば右図では、未知パターンはクラス「あ」のサンプルと最も近いので、「あ」と認識されることになります。
この方法はデータの分布を正規分布と仮定する必要がないためどのようなデータに対しても適用できますが、すべてのサンプルとの距離を計算する必要があるため、認識する際の計算量が膨大なものになります。

これを改善するために、あらかじめサンプルを分類しておき、比較する必要ないサンプルとの距離計算を省略することで識別を高速に行う手法を開発しました。データにもよりますが、高次元の特徴を用いた場合に特に改善の効果が大きく、6倍程度の高速化が実現できました。

関連文献

• 分枝限定法と計算回数の推定に基づくk近隣識別法の高速化
  電子情報通信学会論文誌D-II, vol.J82-D-II, no.4, pp.641-649, April 1999
  大町真一郎, 阿曽弘具