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