基于元素差分的相似向量的搜索
据我所知，有一条线在这里讨论一个类似的问题：
但我的问题略有不同--希望更容易一些。
给定同一维的一组向量，例如，
2、3、5、9
12、9、2、8
45、1、0、1
查询向量1、4、7、2，我想要一个算法，返回2、3、5、9作为最接近的匹配向量，因为它具有最小的元素差和，即(1-2) + (4-3) + (7-5) + (2-9) = -5。
一种方法是预先计算成对的“相似性”，但是计算量很大，因为我将有超过5000个向量，所以比较250,000个。
回答 2
Software Engineering用户
发布于 2017-04-03 14:59:35
对于元素上的差异，曾傑瑞给出了一个很好的解决方案。如果这是你真正想要的，这是一个完美的方法。
然而，我想指出的是，元素间的差异和向量之间的距离之间可能会有一些混淆。如果要计算向量的距离(=要找到最接近查询向量的向量)，则需要重新定义计算：
考虑这两个向量：
- v1：1 4
- v2：4 1
给定查询向量Q 2 4，很明显，v1比v2更接近，尽管差异之和是相同的：
diff(v1, q) = (1-2) + (4-4) = -1+0 = -1
diff(v2, q) = (4-2) + (1-4) = 2-3 = -1你的差分函数的问题是，如果你想知道向量的距离，负的差异应该被视为正的。因此，使用距离函数(=差分的绝对值)，方程如下所示：
dist(v1, q) = abs(1-2) + abs(4-4) = 1+0 = 1
dist(v2, q) = abs(4-2) + abs(1-4) = 2+3 = 5现在我们清楚地看到，v1更接近于q。
同样，这可能不是对最初问题的回答--只是添加一些内容:)
Software Engineering用户
发布于 2017-04-07 23:14:05
我想建议一种用GPGPU计算查询向量和一组向量(m)之间曼哈顿距离的非传统方法。
假设你的向量集定义为S(m，n)。
S (m,n) =
[s_1,1, s_1,2, .... s_1,n
s_2,1, s_1,2, .... s_2,n
.... ....
s_m,1, s_m,2, .... s_m,n]首先，你必须转换你的N维向量(V1，.对于N+1维数向量as (V1，...Vn,1)，可以在O(m)时间内完成。
S'(m,n+1)=
[s_1,1, s_1,2, .... s_1,n ,1
s_2,1, s_1,2, .... s_2,n, 1
.... ....
s_m,1, s_m,2, .... s_m,n ,1]然后，可以使用以下方法将查询向量Q‘= Q1，.，Qn，1周围的集合转换为
TQ(n+1,n+1)=
[1, 0, .... 0, -Q1
0, 1, .... 0, -Q2
.... ....
0, 0, .... 1, -Qn
0, 0, .... 0, 1]
S''(m,n+1)= S'(m,n+1) x TQ(n+1,n+1);可以使用以下矩阵乘法计算曼哈顿距离：
MD(n+1,1)=
[1,
1,
...
1,
0]
S'''(m,1) = S''(m,n+1) x MD(n+1,1)如GPU上的矩阵计算第3.4节所述，所有矩阵乘法都可以在GPU中完成，方法是使用CUDA优化处理
现在，唯一需要做的就是找到min(S‘)及其对应的向量，它可以在O(m)时间内完成。
https://softwareengineering.stackexchange.com/questions/345427
复制相似问题
腾讯云开发者
