局部敏感哈希(Locality-Sensitive Hashing, LSH)方法介绍
局部敏感哈希(Locality-Sensitive Hashing, LSH)方法介绍
本文主要介绍一种用于海量高维数据的近似最近邻快速查找技术——局部敏感哈希(Locality-Sensitive Hashing, LSH)，内容包括了LSH的原理、LSH哈希函数集、以及LSH的一些参考资料。
一、局部敏感哈希LSH
在很多应用领域中，我们面对和需要处理的数据往往是海量并且具有很高的维度，怎样快速地从海量的高维数据集合中找到与某个数据最相似（距离最近）的一个数据或多个数据成为了一个难点和问题。如果是低维的小数据集，我们通过线性查找（Linear Search）就可以容易解决，但如果是对一个海量的高维数据集采用线性查找匹配的话，会非常耗时，因此，为了解决该问题，我们需要采用一些类似索引的技术来加快查找过程，通常这类技术称为最近邻查找（Nearest Neighbor,AN），例如K-d tree；或近似最近邻查找（Approximate Nearest Neighbor, ANN），例如K-d tree with BBF, Randomized Kd-trees, Hierarchical K-means Tree。而LSH是ANN中的一类方法。
局部敏感哈希示意图（from: Piotr Indyk）
二、LSH的应用
LSH的应用场景很多，凡是需要进行大量数据之间的相似度（或距离）计算的地方都可以使用LSH来加快查找匹配速度，下面列举一些应用：
（1）查找网络上的重复网页
互联网上由于各式各样的原因（例如转载、抄袭等）会存在很多重复的网页，因此为了提高搜索引擎的检索质量或避免重复建立索引，需要查找出重复的网页，以便进行一些处理。其大致的过程如下：将互联网的文档用一个集合或词袋向量来表征，然后通过一些hash运算来判断两篇文档之间的相似度，常用的有minhash+LSH、simhash。
（2）查找相似新闻网页或文章
与查找重复网页类似，可以通过hash的方法来判断两篇新闻网页或文章是否相似，只不过在表达新闻网页或文章时利用了它们的特点来建立表征该文档的集合。
（3）图像检索
在图像检索领域，每张图片可以由一个或多个特征向量来表达，为了检索出与查询图片相似的图片集合，我们可以对图片数据库中的所有特征向量建立LSH索引，然后通过查找LSH索引来加快检索速度。目前图像检索技术在最近几年得到了较大的发展，有兴趣的读者可以查看基于内容的图像检索引擎的相关介绍。
（4）音乐检索
对于一段音乐或音频信息，我们提取其音频指纹（Audio Fingerprint）来表征该音频片段，采用音频指纹的好处在于其能够保持对音频发生的一些改变的鲁棒性，例如压缩，不同的歌手录制的同一条歌曲等。为了快速检索到与查询音频或歌曲相似的歌曲，我们可以对数据库中的所有歌曲的音频指纹建立LSH索引，然后通过该索引来加快检索速度。
（5）指纹匹配
一个手指指纹通常由一些细节来表征，通过对比较两个手指指纹的细节的相似度就可以确定两个指纹是否相同或相似。类似于图片和音乐检索，我们可以对这些细节特征建立LSH索引，加快指纹的匹配速度。
相关参考资料
Website:
[1] http://people.csail.mit.edu/indyk/ （LSH原作者）
[2] http://www.mit.edu/~andoni/LSH/ (E2LSH)
Paper:
[1] Approximate nearest neighbor: towards removing the curse of dimensionality
[2] Similarity search in high dimensions via hashing
[3] Locality-sensitive hashing scheme based on p-stable distributions
[4] MultiProbe LSH Efficient Indexing for HighDimensional Similarity Search
[5] Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions
Tutorial:
[1] Locality-Sensitive Hashing for Finding Nearest Neighbors
[2] Approximate Proximity Problems in High Dimensions via Locality-Sensitive Hashing
[3] Similarity Search in High Dimensions
Book:
[1] Mining of Massive Datasets
[2] Nearest Neighbor Methods in Learning and Vision: Theory and Practice
Cdoe:
[1] http://sourceforge.net/projects/lshkit/?source=directory[2] http://tarsos.0110.be/releases/TarsosLSH/TarsosLSH-0.5/TarsosLSH-0.5-Readme.html
[3] http://www.cse.ohio-state.edu/~kulis/klsh/klsh.htm
[4] http://code.google.com/p/likelike/
[5] https://github.com/yahoo/Optimal-LSH
[6] OpenCV LSH（分别位于legacy module和flann module中）
声明：
作者：icvpr | blog.csdn.net/icvpr
