Introducing Similarity Search at Flickr | code.flickr.com
At Flickr, we understand that the value in our image corpus is only unlocked when our members can find photos and photographers that inspire them, so we strive to enable the discovery and appreciation of new photos. To further that effort, today we are introducing similarity search on Flickr. If you hover over a photo on a search result page, you will reveal a “…” button that exposes a menu that g
MinHash - Wikipedia
In computer science and data mining, MinHash (or the min-wise independent permutations locality sensitive hashing scheme) is a technique for quickly estimating how similar two sets are. The scheme was invented by Andrei Broder (1997),[1] and initially used in the AltaVista search engine to detect duplicate web pages and eliminate them from search results.[2] It has also been applied in large-scale
Rubyでb-Bit MinHashを実装してみた。 - タチコマ好きなエンジニアのブログ
昨日に引き続き、SmartNews開発者ブログの「b-Bit MinHashによる高速かつ省スペースな類似度判定」を参考に、Rubyでb-Bit MinHashを実装してみた。 ビット数は1、ハッシュ関数の個数は128で計算させている。 ただし、1ビット値は最初から50％の確率で衝突するので、単に一致した回数をkで割っただけでは、真のJaccard係数が0の場合でも0.5くらいの推定値が出てきてしまいます。 とのことなので、一致数をハッシュ関数の個数で割った値から0.5を引いて2倍したものを表示させてみた。（calc_jaccardのコメントを外すと表示される） だいたい0.4に近い値が出るので多分合っているはず。 ベンチマーク的にはMinHashと大差がなかったけれど、popcountの処理をきちんと実装すれば速くなるかもしれない。 ソースコード require 'murmurhash3
b-Bit MinHashによる高速かつ省スペースな類似度判定 - SmartNews Engineering Blog
ゴクロの浜本です。ネットカフェでコードを書くのが好きです。 前回のエントリーでも触れられていますが、SmartNewsはホットな話題をユーザにお届けするために、常時、膨大な数のツイートおよびURLをクロールしています。こうして収集した記事に対し、様々な分析が施されますが、その中でも重要な処理の1つに、記事の類似度判定があります。内容の似通った記事をインデックスから発見し、グループ化する処理です。 毎秒、大量の新着記事が到着することから、この類似度判定は高速に実行する必要があります。また、インデックスを全てメモリに載せているので、類似度判定を実現する際の空間効率も要求されます。 今回は、SmartNewsが高速かつ省スペースな類似度判定のために使用しているb-Bit MinHashと呼ばれる手法を紹介します。2年前に、PFIの岡野原さんが非常に分かりやすい解説記事を書かれており、本エントリー
局所性鋭敏型ハッシュ - Wikipedia
局所性鋭敏型ハッシュ（きょくしょせいえいびんがたハッシュ、英語: locality sensitive hashing）とは高次元のデータを確率的な処理によって次元圧縮するための手法である。ハッシュの基本的な考え方は類似したデータが高確率で同じバケットに入るようにデータを整理するというものである。多くの場合においてこのバケットの数は入力されるデータサンプルの数よりもずっと小さくなる。 定義[編集] 局所性鋭敏型ハッシュを行うためのパラメータの集合をLSH族(Locality Sensitive Hashing Family)と呼ぶ。LSH族は距離空間と閾値、近似因子によって定義される。LSH族[1][2]は2点について次の2つの性質、 ならばとなる確率は以上である。 ならばとなる確率は以下である。 を満たす関数により与えられる族であり，はから一様乱数にしたがって選択される。このときは2点の
Bhattacharyya distance - Wikipedia
In statistics, the Bhattacharyya distance is a quantity which represents a notion of similarity between two probability distributions.[1] It is closely related to the Bhattacharyya coefficient, which is a measure of the amount of overlap between two statistical samples or populations. It is not a metric, despite being named a "distance", since it does not obey the triangle inequality. History[edit
tfidf、LSI、LDAの違いについて調べてみた
tfidf、LSI、LDAの意味、違いを調べるために、それぞれの形式のコーパスの中身を調べてみた。そのメモ。 前回のおさらい 前回の記事では、もっとも基本的なコーパスの中身を確認してみました。その結果、「コーパスとは、文章集合をベクトル空間に変換したもの」いうことが分かりました。 今回は、基本的なコーパス以外の複数のコーパス、特に、tfidf、LSI、LDAで用いるコーパスについて、基本的なコーパスとは何が違うのかを調べます。その結果分かったコーパスの違いから、各モデルの違いを理解することを目標とします。 gensimに実装されたtfidfのコーパスの中身を見てみました 今回は、「Topics and Transformations」を参考に進めていきます。 >>> import logging >>> logging.basicConfig(format='%(asctime)s : %
Integrating BM25 & BM25F into Lucene1
Integrating BM25 & BM25F into Lucene Joaquín Pérez-Iglesias Introduction This document describes the BM25 and BM25F implementation using the Lucene Java Framework. The implementation described here can be downloaded from http://nlp.uned.es/~jperezi/Lucene-BM25/jar/models.jar. Both models have stood out at TREC by their performance and are considered as state-of-the-art in the IR community. BM25 i
TF-IDF - Negative/Positive Thinking
TF-IDFについて いくつかの文書が与えられたとき、文書中の単語の重みを決める手法の一つ。 TF(Term Frequency, 文書中の単語出現頻度) 「よくでてくる単語はその文書の主題を表しやすい」 ある文書dに単語tがでてきた個数をtf(t,d)と定める tfの定義として、個数nをそのまま用いてしまうと文書サイズが大きいほどnも大きくなってしまうことがある。 なので、文書中のすべての単語数で割って正規化したものをtfとして定義するのがいいかも。 IDF(Inverse Document Frequency, 単語が出現する文書数の逆数) 「どんな文書にもよくでてくる単語は、あんまり重要じゃない」 単語tがでてくる文書数をdf(t)とし、全文書数をNとしたとき、以下の式で決まる TF-IDF 上記の2つを組み合わせたもの。 ある文書dに出現する単語tの重みを以下のように定義。 Oka
コサイン類似度
コサイン類似度について 概要 コサイン類似度とは、ベクトル空間モデルにおいて、文書同士を比較する際に用いられる類似度計算手法。 コサイン類似度は、そのまま、ベクトル同士の成す角度の近さを表現するため、三角関数の普通のコサインの通り、1に近ければ類似しており、0に近ければ似ていないことになる。 だいたいは、tf-idfの値で計算を用いて計算される場合が多いと思います。 コサイン類似度計算式 以下の式で計算できる。 正規化された単位ベクトルについての計算は、以下で可能。 計算例 正規化後の値 ターム 文書1 文書2 文書3
tf-idf - Wikipedia
情報検索の分野において、tf–idf (または、 TF*IDF、TFIDF、TF–IDF、Tf–idf)は、term frequency–inverse document frequencyの略であり、コーパスや収集された文書群において、ある単語がいかに重要なのかを反映させることを意図した統計量（数値）である[1]。また、tf-idfは情報検索や、テキストマイニング、ユーザーモデリング（英語版）における重み係数（英語版）にもよく用いられる。ある単語のtf-idfの値は文書内におけるその単語の出現回数に比例して増加し、また、その単語を含むコーパス内の文書数によってその増加が相殺される。この性質は、一般にいくつかの単語はより出現しやすいという事実をうまく調整することに役立っている。今日、tf-idfはもっとも有名な語の重みづけ(term-weighting)手法である。2015年に行われた研究
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
乱択データ構造の最新事情 －MinHash と HyperLogLog の最近の進歩－