locality sensitive hashing(LSH)
LSH[0][6]とは、ハッシュ関数を使ってデータを次元圧縮をしたり、データ同士の比較を高速で行えるようにするための手法である。使用するハッシュ関数の代表例は、下記の安定分布とハミング距離、Jaccard指数がある。ハミング距離を使って、データの比較する例は[6]がわかりやすい。
安定分布
[1][2]によると、確率変数が独立同時分布(i.i.d)Xに従う時、
が元のi.i.dと同一の分布である場合、Xは安定分布であるという。なお[3]では条件式が別形式で記載されているが、
となり、XからサンプルSを取り出した時にの係数とを変化させれば上式と同様のことが言える。
安定分布の中の代表格が、ガウス分布やコーシー分布である。
ハミング距離[4]
2つの変数a, bがある時、
で求める。例えばa = [1, 0, 0, 1]、b = [1, 1, 0, 0]とすると、ハミング距離は(0+1+0+1)=2となる。
Jaccard指数[5]
a={abc, def, ghi}, b={abc, efg, hij}とすると、(1つ重複する要素があるため)かつなので、となる。