局所性鋭敏型ハッシュ
(Locality sensitive hashing から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/06/30 09:46 UTC 版)
局所性鋭敏型ハッシュ（英: locality sensitive hashing）とは高次元のデータを確率的な処理によって次元圧縮するための手法である。ハッシュの基本的な考え方は類似したデータが高確率で同じバケットに入るようにデータを整理するというものである。多くの場合においてこのバケットの数は入力されるデータサンプルの数よりもずっと小さくなる。
定義
局所性鋭敏型ハッシュを行うためのパラメータの集合をLSH族(Locality Sensitive Hashing Family)と呼ぶ。LSH族は距離空間
と閾値
、近似因子
によって定義される。LSH族[1][2]は2点
について次の2つの性質、
ならば
となる確率は
以上である。
ならばとなる確率は
以下である。
を満たす関数
により与えられる族であり，
は
から一様乱数にしたがって選択される。このとき
は2点
の距離を表す関数であり、
となるよう設計する。このような族は
に鋭敏であるという。
これに準ずる定義として、領域
における類似度関数
によるものがある[3]。局所性鋭敏型ハッシュの性質は、ハッシュ関数の集合
と確率分布
により与えられる。あるハッシュ関数は集合から確率分布により選ばれるが、とは領域に存在する2点
について、
を満たすような確率分布である。
手法
ハミング距離に基づく標本化
LSH族を構築するためのもっとも単純な手法はハミング距離に基づくものである。これは
次元のベクトル
に対して適応できる。この手法は次元のベクトルについて
番目の座標値をハッシュ値として与えるような族により定義され、とは例えば
のように与えられる。ここでからを任意に選ぶということは、入力点から任意にビットを選択するということに他ならない。この時、族は次の性質を持つ。
-
,
安定分布に基づく手法
ハッシュ関数
を次元のベクトル
を整数の集合に移すような関数であると定義する[4]。ハッシュ関数は2つの乱数によって定義される。ここで
とは安定分布から独立に選ばれる乱数であり、
とは
から一様に選ばれる実乱数である。およびが選ばれたとき、ハッシュ関数
は
のように与えられる。
この他にもデータをより適切に対応させるハッシュ関数が提案されている[5]。例えばk-平均法に基づくハッシュ関数などは大域的最適解を与えることが保証されていないものの実用的なハッシュ関数として知られている。
参考文献
- ^ Gionis, A.; Indyk, P., Motwani, R. (1999). , "Similarity Search in High Dimensions via Hashing". Proceedings of the 25th Very Large Database (VLDB) Conference.
- ^ Indyk, Piotr.; Motwani, Rajeev. (1998). , "Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.". Proceedings of 30th Symposium on Theory of Computing.
- ^ Charikar, Moses S.. (2002). "Similarity Estimation Techniques from Rounding Algorithms". Proceedings of the 34th Annual ACM Symposium on Theory of Computing 2002: (ACM 1–58113–495–9/02/0005)…. doi:10.1145/509907.509965. Retrieved 2007-12-21.
- ^ Datar, M.; Immorlica, N., Indyk, P., Mirrokni, V.S. (2004). "Locality-Sensitive Hashing Scheme Based on p-Stable Distributions". Proceedings of the Symposium on Computational Geometry.
- ^ Pauleve, L.; Jegou, H., Amsaleg, L. (2010). "Locality sensitive hashing: A comparison of hash function types and querying mechanisms". Pattern recognition Letters.
関連項目
- Locality sensitive hashingのページへのリンク
