乱択データ構造の最新事情 －MinHash と HyperLogLog の最近の進歩－MinHash, b-bit MinHash, HyperLogLog, Odd Sketch, HIP Estimator の解説です．
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を使ったサイトのカテゴリ分類 - Qiita
動機 URLをカテゴリ分けしたいと考えb-Bit MinHashを使ってみました。 具体的には以下のようなことをするためです。 cookieから抽出したサイト閲覧情報を素性としてユーザのCV確率を求める場合、素性ベクトルがかなりスパースになってしまいます。そこで、URL単位でカテゴリに分け、ある程度素性ベクトルの密度を上げたいと考えました。そのために標題について実験をしています。 このブログに書いたこと b-Bit MinHashの概要 参考コード b-Bit MinHashの概要 参考文献 b-Bit Minwise Hashing b-Bit Minwise Hashing in Practice: Large-Scale Batch and Online Learning and Using GPUs for Fast Preprocessing with Simple Hash F
RubyでMinHashを実装してみた。 - タチコマ好きなエンジニアのブログ
SmartNews開発者ブログのb-Bit MinHashによる高速かつ省スペースな類似度判定を見て、おもしろそうだったのでMinHashをRubyで実装してみた。 MurmurHash3の実装はmurmurhash3-rubyを使わせてもらった。 % bundle init % vi Gemfile gem 'murmurhash3' % bundle install で準備完了。 require 'murmurhash3' require 'benchmark' def init_seeds(num) seeds = Array.new num.times do seeds << Random.rand(999999999) end seeds end def calc_minhash(targets, seed) hash_values = Array.new targets.eac
MinHashによる高速な類似検索 - Preferred Networks Research & Development
年が明けてもう一ヶ月経ちましたね．岡野原です． 今日はMinHashと呼ばれる手法を紹介します．これは特徴ベクトルの高速な類似検索に利用することができます(クローラーの文脈だとShingleとして知られている）． 今や世の中のあらゆる種類のデータが，高次元のバイナリベクトルからなる特徴ベクトルで表されて処理されるようになってきました．例えば文書データであれば文書中に出現する単語やキーワードの出現情報を並べた単語空間ベクトル（Bag of Words）で表し，画像データも，SIFTをはじめとした局所特徴量を並べた特徴ベクトル（とそれをSkecth化したもの）として表せます．行動情報や時系列データも特徴量をうまく抽出する．グラフデータもFast subtree kernels[1]と呼ばれる方法で非常に効率的に特徴ベクトルに変換することができ，グラフの特徴をよく捉えることができるのが最近わかっ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://www.jstage.jst.go.jp/article/essfr/7/3/7_256/_pdf
MinHashing: Fast Similarity Search
Jubatusのリアルタイム分散レコメンデーション@TokyoWebmining#17