K-D Decision Treeとその応用 : 最近傍識別器の高速化と省メモリ化(パターン認識基礎, <特集>画像の認識・理解論文)  [in Japanese] K-D Decision Tree : An Accelerated and Memory Efficient Nearest Neighbor Classifier  [in Japanese]

Search this Article

Author(s)

Abstract

本論文では, 入力空間の分割による最近傍識別器の高速化法を提案する. 最近傍識別は(1)最大マージン基準に基づいて識別境界が決定される, (2)ベイズ誤り確率の2倍未満の誤り確率を達成できる, (3)他の識別器のようにkernel関数やbase classifierや確率分布モデルなどの事前知識を必要としない, (4)そのままで多クラスの識別が行える, などの優れた特性をもつ. その一方で, メモリの使用効率が悪い, 識別速度が遅いという問題点がある. 最近傍識別を行う場合, 通常k-d treeのような最近傍探索アルゴリズムを用いて最近傍パターンを探索し, その帰属クラスへの識別が行われる. しかし, 「最近傍探索」は「最近傍識別」を行うために必ず実行しなければならない処理ではない. 我々は, この考えに基づき高速な最近傍識別器k-d decision tree(KDDT)を提案する. このアルゴリズムでは, 入力空間内で二分探索を行い, 必要な場合に限って局所的な最近傍探索を行う. このような方法により, 識別の高速化が実現できる. また, 学習パターンをプロトタイプとして全数記憶せず, Voronoi condensingを行った後のプロトタイプのみを記憶するため, 通常の方法よりも使用メモリを低く抑えることができる. 様々なパターン集合に対して識別速度を実測したところ, 通常の最近傍探索アルゴリズムを用いて識別を行った場合と比べ, 約2〜190倍高速であり, KDDTの有効性を確認した.

Journal

  • The transactions of the Institute of Electronics, Information and Communication Engineers. D-II

    The transactions of the Institute of Electronics, Information and Communication Engineers. D-II J88-D-II(8), 1367-1377, 2005-08-01

    The Institute of Electronics, Information and Communication Engineers

References:  21

Cited by:  3

Codes

  • NII Article ID (NAID)
    10016796339
  • NII NACSIS-CAT ID (NCID)
    AA11340957
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    09151923
  • NDL Article ID
    7438768
  • NDL Source Classification
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No.
    Z16-1853
  • Data Source
    CJP  CJPref  NDL  NII-ELS 
Page Top