局所性鋭敏型ハッシュ

局所性鋭敏型ハッシュ（きょくしょせいえいびんがたハッシュ、）とは高次元のデータを確率的な処理によって次元圧縮するための手法である。ハッシュの基本的な考え方は類似したデータが高確率で同じバケットに入るようにデータを整理するというものである。多くの場合においてこのバケットの数は入力されるデータサンプルの数よりもずっと小さくなる。
定義.
局所性鋭敏型ハッシュを行うためのパラメータの集合をLSH族(Locality Sensitive Hashing Family)と呼ぶ。LSH族は距離空間formula_1と閾値formula_2、近似因子formula_3によって定義される。LSH族は2点formula_4について次の2つの性質、
を満たす関数formula_11により与えられる族であり，formula_12はformula_13から一様乱数にしたがって選択される。このときformula_14は2点formula_15の距離を表す関数であり、formula_16となるよう設計する。このような族formula_13はformula_18に鋭敏であるという。
これに準ずる定義として、領域formula_19における類似度関数formula_20によるものがある。局所性鋭敏型ハッシュの性質は、ハッシュ関数の集合formula_21と確率分布formula_22により与えられる。あるハッシュ関数formula_12は集合formula_21から確率分布formula_22により選ばれるが、formula_22とは領域formula_19に存在する2点formula_28について、
を満たすような確率分布である。
手法.
ハミング距離に基づく標本化.
LSH族を構築するためのもっとも単純な手法はハミング距離に基づくものである。これはformula_30次元のベクトルformula_31に対して適応できる。この手法はformula_30次元のベクトルについてformula_33番目の座標値をハッシュ値として与えるような族formula_13により定義され、formula_13とは例えばformula_36のように与えられる。ここでformula_13からformula_12を任意に選ぶということは、入力点から任意にビットを選択するということに他ならない。この時、族は次の性質を持つ。
安定分布に基づく手法.
ハッシュ関数formula_41をformula_30次元のベクトルformula_43を整数の集合に移すような関数であると定義する。ハッシュ関数formula_12は2つの乱数formula_28によって定義される。ここでformula_46とは安定分布から独立に選ばれる乱数であり、formula_47とはformula_48から一様に選ばれる実乱数である。formula_46およびformula_47が選ばれたとき、ハッシュ関数formula_51は
のように与えられる。
この他にもデータをより適切に対応させるハッシュ関数が提案されている。例えばk-平均法に基づくハッシュ関数などは大域的最適解を与えることが保証されていないものの実用的なハッシュ関数として知られている。