分枝限定法と計算回数の推定に基づくk近隣識別法の高速化 (<小特集>パターン認識のための学習 : 基礎と応用)

スポンサーリンク

概要

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

著者

関連論文

もっと見る

スポンサーリンク