数据挖掘 - 放大局部敏感哈希 - 吾爱随笔录

放大局部敏感哈希

数据挖掘机器学习

2021-10-10 07:47:23

我正在尝试构建一个余弦局部敏感哈希，这样我就可以找到候选的相似项目对，而无需比较每个可能的对。我基本上可以正常工作，但是我的数据中的大多数对似乎在 -0.2 到 +0.2 范围内具有余弦相似度，所以我试图将它切得很细，并挑选余弦相似度为 0.1 及以上的东西。

我一直在阅读 Mining Massive Datasets 第 3 章。这涉及通过 Amplifying Locality-Sensitive Family 提高候选对选择的准确性。我想我只是理解数学解释，但我很难看到我是如何实际实现的。

到目前为止我所拥有的如下

我说过 1000 部电影，每部电影都有来自 100 万用户的评分。每部电影由用户分数的稀疏向量表示（行号 = 用户 ID，值 = 用户分数）
我构建了 N 个随机向量。矢量长度与电影矢量的长度（即用户数量）相匹配。向量值为 +1 或 -1。我实际上将这些向量编码为二进制以节省空间，+1 映射到 1，-1 映射到 0
我通过获取电影的点积和 N 个随机向量中的每一个来为每部电影构建草图向量（或者更确切地说，如果我通过水平放置 N 个随机向量并将它们彼此叠加来创建矩阵 R，那么草图对于电影 m 是 R*m)，然后取结果向量中每个元素的符号，所以我以 +1s 和 -1s 的每个电影的草图向量结束，我再次将其编码为二进制。每个向量的长度为 N 位。
接下来，我通过执行以下操作来寻找类似的草图
1. 我将草图矢量分成 r 位的 b 条带
2. 每个 r 位带是一个数字。我将该数字与乐队编号结合起来，并将电影添加到该数字下的哈希桶中。每部电影可以添加到多个存储桶中。
3. 然后我查看每个桶。同一桶中的任何电影都是候选对。

将此与 mmds 的 3.6.3 进行比较，我的 AND 步骤是当我查看 r 位带时 - 如果 r 位具有相同的值，则一对电影通过 AND 步骤。我的 OR 步骤发生在桶中：如果电影都在任何桶中，它们就是候选对。

这本书建议我可以通过添加更多的 AND 和 OR 步骤来“放大”我的结果，但我不知道如何实际做到这一点，因为对进一步层的构造过程的解释是检查成对相等性而不是想出桶号。

谁能帮我理解如何做到这一点？

2个回答

我想我已经解决了一些问题。基本上我正在寻找一种适用于 map/reduce 类型环境的方法，我认为这种方法可以做到。

所以，

假设我有 r 行的 b 条带，我想添加另一个 AND 阶段，比如另一个 c AND。
所以我需要 b * r * c 位的散列而不是 b * r 位
我运行我之前的程序 c 次，每次都在 b * r 位上
如果通过这些过程中的任何一个发现 x 和 y 是候选对，它会发出一个键值对 ((x, y), 1)，其中 ID 的元组 (x,y) 作为键，值 1
在 c 程序结束时，我按键和总和对这些对进行分组
总和等于 c 的任何对 (x,y) 都是 c 轮中每一轮的候选对，整个过程的候选对也是如此。

所以现在我有了一个可行的解决方案，我需要做的就是弄清楚使用这样的 3 个步骤是否真的可以帮助我以更少的整体哈希位或更好的整体性能获得更好的结果......

我本来只想发表评论，但我不能。我一直在寻找一种实用的 LSH 放大处理方法，您所介绍的内容很有意义。据我所知，主要的散列函数是

h (x, v) = {\begin{cases} 0 & if sgn (x \cdot v) < 0 \\ 1 & else \end{cases}

$h(x,v)=\left\{ \begin{array}{ll}0 & \mbox{if }\textrm{sgn}(x\cdot v) < 0\\ 1 & \mbox{else}\end{array} \right.$ 对于一些随机向量

v

$v$ , 在 AND 之后变成

h^{'} (x, i) = (h (x, v_{i + 1}), . . ., h (x, v_{i + r}))

$h'(x,i) = (h(x,v_{i+1}),...,h(x,v_{i+r}))$ ，最后在 OR 之后，

h^{″} (x, j) = f (h^{'} (x, r j), j)

$h''(x,j) =f(h'(x,rj),j)$ 或者

h^{″} (x, y) = {\begin{cases} 1 & if h^{″} (x, j) = h^{″} (y, j) for any j \in [0, b) \\ 0 & else \end{cases}

$h''(x,y) =\left\{ \begin{array}{ll}1 & \mbox{if }h''(x,j) = h''(y,j) \mbox{ for any }j \in [0,b)\\ 0 & \mbox{else}\end{array} \right.$ 现在您可以使用 AND/OR

h^{″} (x, y)

$h''(x,y)$ 正如你所描述的。然后，您将只是根据 AND/OR 逻辑语句选择候选人；你不再是真正的散列了。此时要继续散列，您需要一个映射

\hat{h} : S \to S^{'}

$\hat{h}:S\to S'$ 的箱，使得每个向量只出现一次

S^{'}

$S'$ ，但这样做也可能会引入误报和/或否定。散列的一个想法是最小

h^{″} (x, j)

$h''(x,j)$ 对所有人

j

$j$ （或所有的最小值

j

$j$ 以及所有直接和间接相关的

y

$y$ ）。两者显然都会引入偏见。我可能会尝试其中的一种，但我不确定来自一个随机 AND/OR 的哈希值下一次是否有意义。但考虑到随机分布的均匀

v

$v$ 和大量的复制，也许？

其它你可能感兴趣的问题

上一篇目标函数和输出层激活函数之间的联系有多灵活？下一篇是否有研究检查辍学与其他正则化？