文献

J-GLOBAL ID：201002255758866999   整理番号：10A0122603

高次元でのおそらく正しいk-最近傍探索

Probably correct k-nearest neighbor search in high dimensions

著者 (3件)： TOYAMA Jun (Div. of Computer Sci., Graduate School of Information Sci. and Technol., Hokkaido Univ., Sapporo 060-0814, JPN) ,  KUDO Mineichi (Div. of Computer Sci., Graduate School of Information Sci. and Technol., Hokkaido Univ., Sapporo 060-0814, JPN) ,  IMAI Hideyuki (Div. of Computer Sci., Graduate School of Information Sci. and Technol., Hokkaido Univ., Sapporo 060-0814, JPN)
資料名： Pattern Recognition  (Pattern Recognition)
巻： 43  号： 4  ページ： 1361-1372  発行年： 2010年04月 
JST資料番号： D0611A  ISSN： 0031-3203  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： Euclid距離を用いたk-最近傍探索(k-NN)のための新しい方法について述べた。次元が高いときには,多くの洗練されたアルゴリズムが,力ずくのアルゴリズムを打ち負かせないことは良く知られている。ここでは,探索時間を大幅に低減するために,k-最近傍の正しい集合を高い確率で求める,おそらく正しい方法を提案した。低次元で,記憶したデータから推定したk番最近傍の周辺分布を利用した(実験的百分率法)。周辺分布の基本的性質を解析し,部分距離探索の確率的変形である実装したアルゴリズムの利点を示した。その問い合わせ時間はデータサイズnに準線形であり,任意の固定次元mに対してO(mnδ)で,nについてδ=o(1)でδ≦1である。Copyright 2010 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.

シソーラス用語： 問題 ,  *近傍探索法 ,  距離 ,  高次元 ,  計算量
準シソーラス用語： Euclid距離 ,  *最近傍問題 ,  探索時間

分類 (1件)： 人工知能  (JE08000Z)

タイトルに関連する用語 (2件)： 高次元 ,  近傍探索