Introductory guide to Information Retrieval using kNN and KDTree

Article(2000 words)

www.analyticsvidhya.com

 

 

Introduction

筆者は,大好きなクリケット選手についての記事をウェブ上で50個ほど読んでいた際に,今読んでいる記事に基づいて次の記事が提示されていることに気付いた.これは偶然だろうか?いや,そうではない.この背景には「情報探索」という技術が使われている.

この記事では,情報探索の基礎と情報探索を実行するための2つの一般的なアルゴリズムであるkNNとKDTreeを扱う.この記事を読み終わるまでに,あなたは自分自身の情報探索システムを作れるようになっているでしょう.

 

What is Information Retrieval?

ユーザがデータベースにアクセスし,関連する知識や文書を抽出するのを支援するために,情報探索が使用されます.

情報探索システムの主な目標は,「関連情報,  またはユーザの情報ニーズを満たす文書を見つける」ことです.

 

KNN for Information Retrieval

多くのデータサイエンティストたちが情報探索のために使う最も一般的なアルゴリズムの1つがKNNです.K Nearest Neighbour (KNN)は,クエリとデータセットの各点との間の距離を計算し,最も近いK個の対象を見つける,最もシンプルなアルゴリズムの1つです.

NN法を使うときは,クエリとすべての点に対して比較して,最も近い点を見つけます.

数千ものクエリがあり,毎回クエリの点とすべての点とを比較する状況を想像してみてください.計算量が非常に多くなると思いませんか?データ点が多くなればなるほど,計算量も増えていきます.

そのため,数百万,数千ものクエリをもつデータセットの場合,KNNは非常に計算量が多くなります.同様のアプローチを用いた,時間効率が良いKNNに代わる方法はないのでしょうか?

KD Treeは,決定木とKNNを組み合わせて最近傍点を計算するアルゴリズムの1つです.

 

Improvement over KNN : KD Trees for Information Retrieval

KD Treeは,データを効率的に表現するためのデータ構造です.特に,特定の状況に基づいたデータセットを整理し,分割するのに役立ちます.

 

f:id:tom0930:20180302205920p:plain

⇡3次元のKDTree.根セル(白)をまず2つの部分セルに分割(赤)し,それぞれをさらに2つに分割(緑)している.最後に4つのセルそれぞれを2つに分割(青)している.それ以上の分割はされていないので,最終的にできた8つのセルを葉セルと呼ぶ.黄色の球は木の頂点を表している.kd木 - Wikipedia

 

f:id:tom0930:20180302173213g:plain

 

 

Intuitive Explanation of KD Trees

※KD Treeの詳しいアルゴリズムが書いてあるが省略

 

Advantages and Disadvantages of KD Trees

Advantages of KD Trees

  • あるクエリがあるときに最初にするべきことは,葉ノードまで降りていくということです.最悪の場合,Nノードまで降りていく必要があります(Nはデータ点の数).途中で何も取り除くことができないとき.
  • 最小の計算量はO(logN)である.もし何も取り除くことができない場合の計算量はO(N)になる.
  • 多くの場合は,効率と時間が大幅に向上する.

Disadvantages of KD Tree

  • 次元が増えるにつれてKDTreeを使用した最近傍探索の効率性の点で性能が低下する傾向がある.これは,高次元では最近傍の半径が多くの異なる区間を横切るため,多くの区間を取り除くことができないためである.

 

Words 

  • co-incidence 偶然の一致,同時発生
  • computationally 計算的に
  • intensive 激しい
  • organize data データを整理する
  • suppose 仮定する
  • traverse 登る(ここでは,ひとつ上のノードを探しに行く)
  • prune 取り除く
  • intersect 横切る