局部敏感哈希LSH

参考资料： 简单介绍： http://www.cnblogs.com/maybe2030/p/4953039.html 在茫茫人海中发现相似的你——局部敏感哈希（LSH） : http://www.cnblogs.com/fengfenggirl/p/lsh.html 基本思想 　 局部敏感哈希的基本思想类似于一种空间域转换思想，LSH算法基于一个假设，如果两个文本在原有的数据空间是相似的，那么分别经过哈希函数转换以后的它们也具有很高的相似度；相反，如果它们本身是不相似的，那么经过转换后它们应仍不具有相似性。 文档相似度计算 按照文本处理的术语，我们认为一条微博是一篇文档，度量两篇文档相似度有多种方法，有欧式距离、编辑距离、余弦距离、Jaccard距离，我们这里使用Jaccard距离。这里注意一下，距离和相似度是不同的概念，距离越近相似度应该越高，距离越远相似度应该越低，因此similar = 1-distace。 　　集合S和T的Jaccard相识度 当我们不考虑微博中重复出现的词时，一条微博就可以看成一个集合，集合的元素是一个个的词： s1 = '''从 决心 减肥 的 这 一刻 起 请 做 如下 小 改变 你 做 得 到 么''' s2 = '''从 决心 减肥 的 这 一刻 起 请 做 如下 小 改变''' 　　sim(s1,s2)=11/16=0.69. 文档的Shingling 为了字面上相似的文档，将文档表示成集合最有效的方法是构建文档中的短字符串集合，一个常用的方法时Shingling（不知道翻译成什么，囧），看定义很简单的：文档的k-shingle定义为其中长度为k的子串。对于上面的字符串s2，选择k=2，这s2中的所有2-single组成的集合为: { "从 决心" , "决心 减肥" , "减肥 的" , "的 这" , "这 一刻" , "一刻 起" , "起 请" , "请 做" , "做 如下" , "如下 小" , "小 改变" } 　　k值的选取具有一定的技巧，k越大越能找到真正相似的文档，而k越小就能召回更多的文档，但他们可能相似度不高，比如 k=1，就变成了基本词的比较了 。我这里词作为shingle的基本单位，在英文处理中，是以字母为基本单位，原因在于汉字有上万个，而英文字母只有27个，以汉字为单位将造成shingle集合巨大。 　　遍历所用文档，就得到了shingle全集。 保持相似度矩阵表示 　　1、集合的矩阵表示 　　假设我们有这样4篇文档（分词后）： s1 = "我 减肥" s2= "要" s3 = "他 减肥 成功" s4 = "我 要 减肥" 　　为方便叙述，我们取k=1，这时shingle全集为{我，他，要，减肥，成功}，将文档表示成特征矩阵，行代表shingle元素，列代表文档，只有文档j出现元素i时，矩阵M[i][j]=1，否则M[i][j] = 0. 元素 S1 S2 S3 S4 我 1 0 0 1 他 0 0 1 0 要 0 1 0 1 减肥 1 0 1 1 成功 0 0 1 0 　　实际上，真正计算的过程中矩阵不是这样表示的，因为数据很稀疏。得到矩阵表示后，我们来看最小hash的定义。 最小哈希（min-hashing） 　　最小hash定义为：特征矩阵按行进行一个随机的排列后，第一个列值为1的行的行号。举例说明如下，假设之前的特征矩阵按行进行的一个随机排列如下： 元素 S1 S2 S3 S4 他 0 0 1 0 成功 0 0 1 0 我 1 0 0 1 减肥 1 0 1 1 要 0 1 0 1 　　最小哈希值：h(S1)=3，h(S2)=5，h(S3)=1，h(S4)=2. 　　为什么定义最小hash？事实上，两列的最小hash值就是这两列的Jaccard相似度的一个估计，换句话说，两列最小hash值同等的概率与其相似度相等，即P(h(Si)=h(Sj)) = sim(Si,Sj)。为什么会相等？我们考虑Si和Sj这两列，它们所在的行的所有可能结果可以分成如下三类： 　　（1）A类：两列的值都为1； 　　（2）B类：其中一列的值为0，另一列的值为1； 　　（3）C类：两列的值都为0. 　　特征矩阵相当稀疏，导致大部分的行都属于C类，但只有A、B类行的决定sim(Si,Sj)，假定A类行有a个，B类行有b个，那么sim(si,sj)=a/(a+b)。现在我们只需要证明对矩阵行进行随机排列，两个的最小hash值相等的概率P(h(Si)=h(Sj))=a/(a+b)，如果我们把C类行都删掉，那么第一行不是A类行就是B类行，如果第一行是A类行那么h(Si)=h(Sj)，因此P(h(Si)=h(Sj))=P(删掉C类行后，第一行为A类)=A类行的数目/所有行的数目=a/(a+b)，这就是最小hash的神奇之处。