转载

局部敏感Hash

1.LSH简介

之前在项目中做数据聚合去重的逻辑的时候简单看过局部敏感Hash(Locality Sensitive Hashing,简称LSH)这个东东。今天整理一下个人的理解。

LSH可以理解为一种衡量文本相似度的算法，特点是散列前的相似点经过哈希之后，也能够在一定程度上相似，并且具有一定的概率保证。其有坚实的理论依据(98年左右理论就提出来了，99年有第一版实现)并且在高维数据空间中表现优异。简单的价格实验场景：

近似检测(Near-duplicate detection): 通常运用在网页去重方面。在搜索中往往会遇到内容相似的重复页面，它们中大多是由于网站之间转载造成的。可以对页面计算LSH，通过查找相等或相近的LSH值找到Near-duplicate。
图像、音频检索: 通常图像、音频文件都比较大，并且比较起来相对麻烦，我们可以事先对其计算LSH，用作信息指纹，这样可以给定一个文件的LSH值，快速找到与其相等或相近的图像和文件。
聚类: 将LSH值作为样本特征，将相同或相近的LSH值的样本合并在一起作为一个类别。
指纹匹配: 一个手指指纹通常由一些细节来表征，通过对比较两个手指指纹的细节的相似度就可以确定两个指纹是否相同或相似。

LSH的发展历史可以参考： http://jacoxu.com/?p=496

2.普通Hash

说到Hash，大家都很熟悉，是一种典型的Key-Value结构，最常见的算法莫过于MD5。其设计思想是使Key集合中的任意关键字能够尽可能均匀的变换到Value空间中，不同的Key对应不同的Value。通过建立Hash的方式我们能够得到O(1)的查找时间性能，其中关键在于选取一个hash function(md5就是一致hash function)。

md5这种hash函数通常情况下，Key值只有轻微变化，Value值也会发生很大地变化。比如下面实验中用到的文本，仅仅是邮箱号少了个.，其md5完全不同：

xiaobaoqiu@xiaobaoqiu:~/temp/md5$ cat 1.dat  xiaobaoqiu@qunar.com xiaobaoqiu@xiaobaoqiu:~/temp/md5$ cat 2.dat  xiaobaoqiu@qunarcom xiaobaoqiu@xiaobaoqiu:~/temp/md5$ md5sum 1.dat  ca201d44a9bb6f8e0ca761cdeb678948  1.dat xiaobaoqiu@xiaobaoqiu:~/temp/md5$ md5sum 2.dat  f585aa440eb3b8bbc46f1184e2944fb9  2.dat

原始文本是极其相似的，但是hash之后这种相似性就丢失了。

3.LSH

局部敏感哈希的最大特点就在于保持数据的相似性。需要注意的是这里说的保持数据的相似度不是说保持100%的相似度，而是保持最大可能的相似度。换个角度来看，可以将LSH理解为数据降维的方法。

数据对应的维度越高，信息量也就越大，相反，如果数据进行了降维，那么毫无疑问数据所反映的信息必然会有损失。哈希函数从本质上来看就是一直在扮演数据降维的角色。

LSH的基本思想是：将原始数据空间中的两个相邻数据点通过相同的映射或投影变换后，这两个数据点在新的数据空间中仍然相邻的概率很大，而不相邻的数据点被映射到同一个桶的概率很小。

参考： https://en.wikipedia.org/wiki/Locality-sensitive_hashing http://www.cnblogs.com/maybe2030/p/4953039.html http://blog.csdn.net/weiyuweizhi/article/details/8921973

正文到此结束