局部敏感哈希LocalitySensitiveHashing（LSH）之随机投影法1. 概述
是由⽂献[1]提出的⼀种⽤于⾼效求解最近邻搜索问题的Hash算法。LSH算法的基本思想是利⽤⼀个hash函数把集合中的元素映射成hash 值，使得相似度越⾼的元素hash值相等的概率也越⾼。LSH算法使⽤的关键是针对某⼀种相似度计算⽅法，找到⼀个具有以上描述特性的hash函数。LSH所要求的hash函数的准确数学定义⽐较复杂，以下给出⼀种通俗的定义⽅式：
⼀般来说在最近邻搜索中，元素间的关系可以⽤相似度或者距离来衡量。如果⽤距离来衡量，那么距离⼀般与相似度之间存在单调递减的关系。以上描述如果使⽤距离来替代相似度需要在单调关系上做适当修改。
根据元素相似度计算⽅式的不同，LSH有许多不同的hash算法。两种⽐较常见的hash算法是随机投影法和min-hash算法。本⽂即将介绍的随机投影法适⽤于集合元素可以表⽰成向量的形式，并且相似度计算是基于向量之间夹⾓的应⽤场景，如余弦相似度。min-hash法在参考⽂献[2]中有相关介绍。
2 随机投影法(Random projection)
假设集合S中的每个元素都是⼀个n维的向量：
，集合中两个元素
对于以上元素集合S的随机投影法hash函数h(*)可以定义为如下：
在n维空间中随机选取⼀个⾮零向量
根据以上定义，假设向量
饥荒韦斯
以上所描述的h(*)函数虽然符合LSH算法的要求，但是实⽤性不⾼。因为该hash函数只产⽣了两个hash值，没有达到hash函数将元素分散到多个分组的⽬的。为了增加不同hash值的个数，可以多次⽣成独⽴的函数h(*)，只有当两个元素的多个h(*)值都相等时才算拥有相同的hash值。根据该思路可以定义如下的hash函数H(*)：
以H(*)为hash函数的话，两个相似度为s的元素具有相同hash值的概率公式为深圳航空公司
3 随机投影法在最近邻搜索中的应⽤
3.1 最近邻搜索
最近邻搜索可以简单的定义为：对于m个元素的集合T，为⼀个待查询元素q找到集合中相似度最⾼的k个元素。
经幡读音最近邻搜索最简单的实现⽅法为：计算q与集合T中每⼀个元素的相似度，使⽤⼀个具有k个元素的⼤顶堆（优先队列）保存相似度计算结果（相似度值为key）。这种实现⽅法每⼀次查询都要遍历整个集合T来计算相似度，当m很⼤并且查询的频率很⾼的时候这种暴⼒搜索的⽅法⽆法满⾜性能要求。
当最近邻搜索的近邻要求并不是那么严格的时候，即允许top k近邻的召回率不⼀定为1（但是越⾼越好），那么可以考虑借助于LSH算法。
歌舞升平的意思
微信怎么切换账号3.2 随机投影法提⾼执⾏速度
这⾥我们介绍当集合T的元素和查询元素q为同维度向量(维度为n)，并且元素相似度计算⽅法为余弦相似度时，使⽤随机投影法来提⾼最近邻搜索的执⾏速度。具体的实现⽅法为：
预处理阶段：使⽤hash函数H(*)计算集合T中所有元素的hash值，将集合T分成⼀个个分组，每个分组内的元素hash值均相等。⽤合适的数据结构保存这些hash值到分组的映射关系（如HashMap）。
查询阶段：计算查询元素q的hash值H(q)，取集合T中所有hash值为H(q)的分组，以该分组内的所有元素作为候选集合，在候选该集合内使⽤简单的最近邻搜索⽅法寻找最相似的k个元素。
该⽅法的执⾏效率取决于H(*)的hash值个数
根据以上分析H(*)中b的取值越⼤算法的执⾏速度的提升越多，并且是指数级别的提升。但是，在这种情况下H(*)函数下的概率公式p(s)，实际上表⽰与查询元素q的相似度为s的元素的召回率。当b的取值越⼤时，top k元素的召回率必然会下降。因此算法执⾏速度的提升需要召回率的下降作为代价。例如：当b等于10时，如果要保证某个元素的召回率不⼩于0.9，那么该元素与查询元素q的相似度必须不⼩于
0.9999998。
加多宝家族3.3 提⾼召回率改进
为了在保证召回率的前提下尽可能提⾼算法的执⾏效率，⼀般可以进⾏如下改进：
预处理阶段：⽣成t个独⽴的hash函数超市开业
查询阶段：对于每⼀个hash函数
以上改进使得集合中元素与查询元素q的t个hash值中，只要任意⼀个相等，那么该集合元素就会被加⼊到候选集中。那么，相似度为s的元素的召回率为
在执⾏效率上，预处理阶段由于需要计算t个hash函数的值，所以执⾏时间上升为t倍。查询阶段，如果单纯考虑候选集合⼤⼩对执⾏效率的影响，在最坏的情况下，t个hash值获得的列表均不相同，候选集集合⼤⼩的期望值为
下图是召回率公式
3.4 参数选取
根据以上分析，H(*)函数的参数b越⼤查询效率越⾼，但是召回率越低；参数t越⼤查询效率越低但是召回率越⾼。因此选择适当参数b和t来折中查询效率与召回率之间的⽭盾是应⽤好随机投影法的关键。下⾯提供⼀种在实际应⽤中选取b和t的参考⽅法。
根据实际应⽤的需要确定⼀对(s,p)，表⽰相似度⼤于等于s的元素，召回率的最低要求为p。然后将召回率公式表⽰成b-t之间的函数关系3.5 关于最近邻⽂本搜索
在最近邻⽂本搜索中，⼀般待检索的⽂本或查询⽂本，都已被解析成⼀系列带有权重的关键词，然后通过余弦相似度公式计算两个⽂本之间的相似度。这种应⽤场景下的最近邻搜索与以上所提到的最近邻搜索问题相⽐存在以下两个特点：
如果把每个⽂本的带权重关键词表都看作是⼀个向量元素的话，每个关键词都是向量的⼀个维度，关
键词权重为该维度的值。理论上可能关键词的个数并不确定（所有单词的组合都可能是⼀个关键词），因此该向量元素的维数实际上是不确定的。
由于关键词权重肯定是⼤于零的，所以向量元素的每⼀个维度的值都是⾮负的。
对于第⼀个特点，我们需要选取⼀个包含n个关键词的关键词集合，在进⾏⽂本相似度计算时只考虑属于该集合的关键词。也就是说，每⼀个⽂本都视为是⼀个n维度的向量，关键词权重体现为对应维度的值。该关键词集合可以有很多种⽣成办法，⽐如可以是⽹站上具有⼀定搜索频率的关键词集合，总的来说该关键词集合应当能够涵盖所有有意义并且具有⼀定使⽤频率的关键词。通常n的取值会⽐较⼤，如⼏⼗万到⼏百万，由于在使⽤随机投影算法时，每⼀个⽣成的随机向量维度都为n，这种情况下需要特别考虑利⽤这些⾼维随机向量对执⾏效率造成的影响，在确定b、t参数时需要考虑到这⽅⾯的影响。
商机需求
对于第⼆个特点，由于向量元素各维度值都⾮负，那么这些元素在⾼维空间中只会出现在特定的区域中。⽐如当n为3时，只会出现在第⼀象限中。⼀个直观的感觉是在⽣成随机向量的时候，会不会⽣成⼤量的⽆⽤切割平⾯（与第⼀个象限空间不相交，使得所有元素都位于切割平⾯的同侧）。这些切割平⾯对应的H(*)函数hash值中的⼆进制位恒定为1或者0，对于提⾼算法执⾏速度没有帮助。以下说明这种担⼼是没有必要的：
切割平⾯与第⼀象限空间不相交等价于其法向量的每⼀个维度值都有相同的符号（都为正或者负），否则总能在第⼀象限空间中找到两个向量与法向量的乘积符号不同，也就是在切割平⾯的两侧。那么，随机⽣成的n维向量所有维度值都同号的概率为
参考⽂献
[1] P. Indyk and R. Motwani. Approximate Nearest Neighbor:Towards Removing the Cur of Dimensionality. In Proc. of the 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 604–613.
[2] Google News Personalization: Scalable Online Collaborative Filtering
