文献の詳細
言語 | 日本語 |
---|---|
著者 | 大町 真一郎, 阿曽 弘具 |
論文名 | 分枝限定法と計算回数の推定に基づくk近隣識別法の高速化 |
論文誌名 | 電子情報通信学会論文誌D-II |
Vol. | J82-D-II |
No. | 4 |
ページ | pp.641-649 |
年月 | 1999年4月 |
要約 | 最近隣法あるいはk近隣法は,パターン認識における代表的な ノンパラメトリックな識別手法である. アルゴリズムが簡単であり,訓練データが十分に存在する場合 誤り率がベイズエラーの2倍以下に抑えられる等の好ましい性質を備えている. しかし,訓練データ数と特徴ベクトルの次元数に比例する計算量を必要とするため, 訓練データ数や特徴ベクトルの次元数が大きい場合には膨大な計算量を必要とする. 本論文では,k近隣法による識別を高速化することを目的とし, 分枝限定法に基づくアルゴリズムを提案する. また,探索木の構築法として,計算量の推定を行ないながら探索木を 構築していくことで計算量が最小となるような学習法を提案する. 文字認識における特徴量を用いた2カテゴリー識別問題に適用した結果, 最近隣法の場合,すべての訓練データとの距離計算を行なう手法と比較して6.4倍, 従来の分枝限定法に基づく手法と比較しても3.7倍程度の高速化が実現できる ことが確認された. |
@Article {大町1999, author = {大町 真一郎 and 阿曽 弘具}, title = {分枝限定法と計算回数の推定に基づくk近隣識別法の高速化}, journal = {電子情報通信学会論文誌D-II}, year = {1999}, month = apr, volume = {J82-D-II}, number = {4}, pages = {641--649} }