LSH (Locality Sensitive Hashing) を用いた類似インスタンスペアの抽出 - mixi engineer blog
GW 中の長距離移動のために体調が優れない takahi-i です. 今回は巨大なデータをマイニングする一つの技術として LSH (Localtiy Sensitive Hashing) を紹介させていただきます. LSH とは LSH は大量なデータから類似度が高いインスタンスのペアを高速に抽出してくれるアルゴリズムです. ここでインスタンスはデータ集合の一つの要素を表します. たとえば扱うデータが E-コマースサイトの購買ログであれば, インスタンスは各ユーザですし, 画像データ集合であれば, インスタンスは個々の画像データです. LSH の詳しい解説については以下のサイトがあります. Wikipedia のエントリ LSH に関する論文がまとめられているページ 本稿ではE-コマースサイトの購買履歴データを基に LSH の機能について述べてゆきます. 以下のような E-コマースサイトの
kd-tree Visualization(2) - agwの日記
先日のエントリにて、kd木を紹介しました。前回はアルゴリズム Cに倣って、要素の追加のみでkd木を構築してみました。 繰り返しになりますが、一般的に要素の追加のみでkd木を構築するとバランスの悪い木となることが知られています。先日のエントリで作成したkd木を可視化したものは以下のようなものでした。 同じく、木構造として可視化したものは以下のようなものでした。 さて、では何故均衡の取れない木が構築されてしまうのでしょう? 座標群の初めの点、1番の点を挿入した直後の状態を可視してみましょう。 この可視と先ほどの木構造としての可視を比較すると不均衡な木が構築される理由がより明らかとなります。木構造の可視にて1番の左側にぶら下がっている2番以下の座標群は、この可視では1番によって空間分割された領域の下側、つまり、y座標値がより小さい側に分布しています。 同様に、木構造にて1番の右側にぶら下がってい
Tutorial "Algorithms for Nearest Neighbor Search" by Yury Lifshits
© COPYRIGHT FREE! Slides and TeX sources including pictures are provided for reuse without any restriction. If you like, you can mention that it was taken from tutorial by Yury Lifshits from http://simsearch.yury.name/tutorial.html. But you are not obliged to do this! Relevant reading For lectures 1-2: P. Zezula, G. Amato, V. Dohnal, M. Batko, Similarity Search - The Metric Space Approach, Springe
くさもち研究室生活ブログだったもの LSHまとめ(1)
LSHは近似最近傍探索(Approximate Nearest Neighbor)アルゴリズムの一つ． 近似最近傍探索とは，簡単に言うとクエリqから半径(1+ε)内にある点vを探索すること． つまり，半径(1+ε)の点のうち，どれか1つでも探索できればおｋ． 言葉の意味そのままに最近傍探索(Nearest Neighbor)の条件を少し緩くした探索といえる． （実は，特徴ベクトルの次元がd=2の場合なら，ボロノイ図を使えば近似最近傍探索ができる） LSHはハッシュ関数を用いた確率的探索で近似最近傍探索を解く． そう，実はハッシュ関数を用いるということ以上に確率的探索ということに大きな意味がある．（これが自分にとってはかなりやっかいな問題） LSHでは，クエリqと近傍(半径(1+ε)以内)にある点ではハッシュ値が一致する確率が高く， クエリqと遠い位置にある点ではハッシュ値が一致する確率が低
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Algorithm-LSH-0.00001_01
搭の木公園
しょうこうフェア
