包含と排除による k 最近隣法の高速化  [in Japanese] Acceleration of the κ-nearest neighbor method using inclusion and exclusion  [in Japanese]

Search this Article

Author(s)

    • 工藤 峰一 KUDO Mineichi
    • 北海道大学大学院工学研究科 Division of Systems and Information Engineering, Graduate School of Engineering

Abstract

著者らは以前、κ最近隣法の高速化として、探索を途中において終端できる条件を示し、分枝限定法においてその条件を組み込む方式を提案した。本研究では、同様の条件が、たとえ終端はできない場合でも、解集合の限定(包含)に利用できることを示す。また、対称的に、解となり得ない集合を排除するための条件を示す。また、これらの包含および排除条件により自然に導かれるアルゴリズムを述べ、その有効性を確認する。

The termination conditions were previously derived by us to stop the search procedure for finding the κ-nearest neighbors and a branch and bound algorithm equipped with these conditions was proposed. In this study, we examine under which conditions we can limit our search space even when such terminations cannot be applied. Indeed, an inclusion condition to narrow the search space and an exclusion condition to exclude some samples from the search are described. With some experiments, we confirm the validity of these conditions.

Journal

  • Technical report of IEICE. PRMU

    Technical report of IEICE. PRMU 103(295), 91-95, 2003-09-08

    The Institute of Electronics, Information and Communication Engineers

References:  10

Cited by:  1

Codes

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