查询阶段 对于每一个hash函数Hi(∗) 计算查询元素q的hash值Hi(q) 将集合T中Hi(∗)所对应的分组方式下hash值为Hi(q)的分组添加到该次查询的候选集合中。然后 在该候选集合内使用简单的最近邻搜索方法寻找最相似的k个元素。

以上改进使得集合中元素与查询元素q的t个hash值中 只要任意一个相等 那么该集合元素就会被加入到候选集中。那么 相似度为s的元素的召回率为

在执行效率上 预处理阶段由于需要计算t个hash函数的值 所以执行时间上升为t倍。查询阶段 如果单纯考虑候选集合大小对执行效率的影响 在最坏的情况下 t个hash值获得的列表均不相同 候选集集合大小的期望值为t∗m2b 查询速度下降至1t 与简单近邻搜索相比查询速度提升为2bt倍。

下图是召回率公式p(s) 1−(1−(1−arccos(s)π)b)t在不同的b和t取值下的s-p曲线。我们通过这些曲线来分析这里引入参数t的意义。4条蓝色的线以及最右边红色的线表示当t取值为1 相当于没有引入t 而b的取值从1变化到5的过程 从图中可以看出随着b的增大 不同相似度下的召回率都下降的非常厉害 特别的 当相似度接近1时曲线的斜率很大 也就说在高相似度的区域 召回率对相似度的变化非常敏感。10条红色的线从右到左表示b的取值为5不变 t的取值从1到10的过程 从图中可以看出 随着t的增大 曲线的形状发生了变化 高相似度区域的召回率变得下降的非常平缓 而最陡峭的地方渐渐的被移动到相对较低的相似度区域。因此 从以上曲线的变化特点可以看出 引入适当的参数t使得高相似度区域在一段较大的范围内仍然能够保持很高的召回率从而满足实际应用的需求。

根据以上分析 H(*)函数的参数b越大查询效率越高 但是召回率越低 参数t越大查询效率越低但是召回率越高。因此选择适当参数b和t来折中查询效率与召回率之间的矛盾是应用好随机投影法的关键。下面提供一种在实际应用中选取b和t的参考方法。

根据实际应用的需要确定一对(s,p) 表示相似度大于等于s的元素 召回率的最低要求为p。然后将召回率公式表示成b-t之间的函数关系t log1−(1−acos(s)pi)b(1−p)。根据(s,p)的取值 画出b-t的关系曲线。如s 0.8,p 0.95时的b-t曲线如下图所示。考虑具体应用中的实际情况 在该曲线上选取一组使得执行效率可以达到最优的(b,t)组合。

在最近邻文本搜索中 一般待检索的文本或查询文本 都已被解析成一系列带有权重的关键词 然后通过余弦相似度公式计算两个文本之间的相似度。这种应用场景下的最近邻搜索与以上所提到的最近邻搜索问题相比存在以下两个特点

对于第一个特点 我们需要选取一个包含n个关键词的关键词集合 在进行文本相似度计算时只考虑属于该集合的关键词。也就是说 每一个文本都视为是一个n维度的向量 关键词权重体现为对应维度的值。该关键词集合可以有很多种生成办法 比如可以是网站上具有一定搜索频率的关键词集合 总的来说该关键词集合应当能够涵盖所有有意义并且具有一定使用频率的关键词。通常n的取值会比较大 如几十万到几百万 由于在使用随机投影算法时 每一个生成的随机向量维度都为n 这种情况下需要特别考虑利用这些高维随机向量对执行效率造成的影响 在确定b、t参数时需要考虑到这方面的影响。

对于第二个特点 由于向量元素各维度值都非负 那么这些元素在高维空间中只会出现在特定的区域中。比如当n为3时 只会出现在第一象限中。一个直观的感觉是在生成随机向量的时候 会不会生成大量的无用切割平面 与第一个象限空间不相交 使得所有元素都位于切割平面的同侧 。这些切割平面对应的H(*)函数hash值中的二进制位恒定为1或者0 对于提高算法执行速度没有帮助。以下说明这种担心是没有必要的

切割平面与第一象限空间不相交等价于其法向量的每一个维度值都有相同的符号 都为正或者负 否则总能在第一象限空间中找到两个向量与法向量的乘积符号不同 也就是在切割平面的两侧。那么 随机生成的n维向量所有维度值都同号的概率为12n−1 当n的取值很大时 该概率可以忽略不计。

[1] P. Indyk and R. Motwani. Approximate Nearest Neighbor:Towards Removing the Curse 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

后记

        然而最后 我使用了还是随机投影的方法 这个是正确率和速度的权衡