分枝限定法と計算回数の推定に基づく k 近隣識別法の高速化

大町 真一郎  阿曽 弘具  

誌名
電子情報通信学会論文誌 D   Vol.J82-D2   No.4   pp.641-649
発行日: 1999/04/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1923
論文種別: 特集論文 (パターン認識のための学習-基礎と応用-論文小特集)
専門分野: 
キーワード: 
パターン認識,  最近隣法,  k 近隣法,  分枝限定法,  文字認識,  

本文: PDF(293.3KB)>>
論文を購入




あらまし: 
最近隣法あるいは k 近隣法は,パターン認識における代表的なノンパラメトリックな識別手法である. アルゴリズムが簡単であり, 訓練データが十分に存在する場合誤り率がベイズエラーの2倍以下に抑えられる等の 好ましい性質を備えている. しかし,訓練データ数と特徴ベクトルの次元数に比例する計算量を必要とするため, 訓練データ数や特徴ベクトルの次元数が大きい場合には膨大な計算量を必要とする. 本論文では,k 近隣法による識別を高速化することを目的とし, 分枝限定法に基づくアルゴリズムを提案する. また,探索木の構築法として, 計算量の推定を行いながら探索木を構築していくことで計算量が最小となるような学習法を提案する. 文字認識における特徴量を用いた2カテゴリー識別問題に適用した結果, 最近隣法の場合,すべての訓練データとの距離計算を行う手法と比較して6.4倍, 従来の分枝限定法に基づく手法と比較しても3.7倍程度の高速化が実現できることが確認された.