Yasuo Tabeiの日記

Min-Max類似度を使ったSketchSortの実装 (SketchSort-MinMax)を公開しました

21:56 |

SketchSortとは全ペアー類似度検索(与えられたデータセットからすべての類似するデータペアーを発見する問題)を高速に解くためのソフトウェアーで、以前に論文とソフトウェアーを公開しました。

論文: Yasuo Tabei, Takeaki Uno, Masashi Sugiyama, Koji Tsuda: Single Versus Multiple Sorting in All Pairs Similarity Search, The 2nd Asian Conference on Machine Learning (ACML), Tokyo, Japan, 2010.

ソフトウェアー: https://code.google.com/archive/p/sketchsort

ブロブ記事: http://d.hatena.ne.jp/tb_yasu/20100911/1284207891

以前のこれらのバージョンでは、コサイン類似度、Jaccard(Tanimoto)類似度、ユーグリッド距離を類似度の尺度としてつかっていました。

今回の新しいバージョンではMinMax類似度を類似度の尺度として用いています。 ではなぜ今SketchSortなのかといいますと、今携わっているプロジェクトで全ペアー類似度検索を解く場面がありまして、類似度としてはminmax類似度を使いたいという要望がありました。SketchSortでは内部でデータのランダムプロジェクションを行っているのですが、ちょうど今年のKDD'17でMin-Max類似度用のランダムプロジェクションを提案した論文が発表され、MinMax類似度を用いたSketchSortを実現できることがわかったので実装を行いました。因みにMinMax類似度のためのランダムプロジェクションはgeneralized consistent weighted samplingと呼ばれ、手法を解説した論文は以下となります。ご興味がある方は読んでみてください

Ping Li: Linearized GMM Kernels and Normalized Random Fourier Features, KDD'17

http://www.kdd.org/kdd2017/papers/view/linearized-gmm-kernels-and-normalized-random-fourier-features

MinMax類似度を用いたSketchSort-minmaxはgithubからダウンロードできます。

https://github.com/tb-yasu/sketchsort-minmax