Locality Sensitive Hashによる類似ベクトル検索を試す - Negative/Positive Thinking
はじめに 類似性が高いベクトルのハッシュ値が近い値になるようなハッシュ関数を使って、 類似するものを高速に検索することができるので、それを試してみた。 Locality Sensitive Hash 類似するデータが高確率で近い値になる(Locality-Sensitive)ハッシュ関数のこと 高次元データの次元圧縮を行える (P1,P2,r,cr)-sensitiveなHash族とは、 2つの特徴ベクトルp,qについて(P1>P2) ||p-q||P1 ||p-q||>crならPr[h(p)=h(q)] を満たすハッシュ関数h:R^d->U コサイン類似度に対するLSH 2つのk次元ベクトルu,vについて コサイン類似度: u*v / sqrt(|u|*|v|) d個のk次元のランダムベクトルr_iを考え、ハッシュ関数h_i(u)を h_i(u) = 1 (r*u >=0) h_i(u)
LSH (Locality Sensitive Hashing) を用いた類似インスタンスペアの抽出 - mixi engineer blog
GW 中の長距離移動のために体調が優れない takahi-i です. 今回は巨大なデータをマイニングする一つの技術として LSH (Localtiy Sensitive Hashing) を紹介させていただきます. LSH とは LSH は大量なデータから類似度が高いインスタンスのペアを高速に抽出してくれるアルゴリズムです. ここでインスタンスはデータ集合の一つの要素を表します. たとえば扱うデータが E-コマースサイトの購買ログであれば, インスタンスは各ユーザですし, 画像データ集合であれば, インスタンスは個々の画像データです. LSH の詳しい解説については以下のサイトがあります. Wikipedia のエントリ LSH に関する論文がまとめられているページ 本稿ではE-コマースサイトの購買履歴データを基に LSH の機能について述べてゆきます. 以下のような E-コマースサイトの
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
