局所性鋭敏型ハッシュとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > ウィキペディア小見出し辞書 > 局所性鋭敏型ハッシュの意味・解説 

局所性鋭敏型ハッシュ

出典: フリー百科事典『ウィキペディア(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-平均法に基づくハッシュ関数などは大域的最適解を与えることが保証されていないものの実用的なハッシュ関数として知られている。

参考文献

  1. ^ Gionis, A.; Indyk, P., Motwani, R. (1999). , "Similarity Search in High Dimensions via Hashing". Proceedings of the 25th Very Large Database (VLDB) Conference. 
  2. ^ Indyk, Piotr.; Motwani, Rajeev. (1998). , "Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.". Proceedings of 30th Symposium on Theory of Computing. 
  3. ^ 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. 
  4. ^ 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. 
  5. ^ Pauleve, L.; Jegou, H., Amsaleg, L. (2010). "Locality sensitive hashing: A comparison of hash function types and querying mechanisms". Pattern recognition Letters. 

関連項目


局所性鋭敏型ハッシュ

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/05/13 07:55 UTC 版)

最近傍探索」の記事における「局所性鋭敏型ハッシュ」の解説

局所性鋭敏型ハッシュ(LSH)は、距離空間内の各点距離空間操作を施すことで、グループ分けする技法である。ある距離尺度互いに近い点は同じグループになる確率高くなる

※この「局所性鋭敏型ハッシュ」の解説は、「最近傍探索」の解説の一部です。
「局所性鋭敏型ハッシュ」を含む「最近傍探索」の記事については、「最近傍探索」の概要を参照ください。

ウィキペディア小見出し辞書の「局所性鋭敏型ハッシュ」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「局所性鋭敏型ハッシュ」の関連用語

局所性鋭敏型ハッシュのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



局所性鋭敏型ハッシュのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの局所性鋭敏型ハッシュ (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの最近傍探索 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS