你能确认我的问题是对的吗?
您的表表示由 groupId 标识的向量。每个向量的维度都在 100 到 50,000 之间,但维度上没有定义顺序。即从表中的一个向量实际上是一个等价类的代表。
现在,您将两个等价类的相似性定义为等价类的任意两个代表投影到前 30 个维度的子空间的最小欧几里得距离。
投影到二维的示例:
A = <1, 2, 3, 4>
B = <5, 6, 7, 8, 9, 10>
A 表示以下等价类向量。
<1, 2, 3, 4> <2, 1, 2, 3> <3, 1, 2, 4> <4, 1, 2, 3>
<1, 2, 4, 4> <2, 1, 3, 2> <3, 1, 4, 2> <4, 1, 3, 2>
<1, 3, 2, 4> <2, 3, 1, 4> <3, 2, 1, 4> <4, 2, 1, 3>
<1, 3, 4, 2> <2, 3, 4, 1> <3, 2, 4, 1> <4, 2, 3, 1>
<1, 4, 2, 2> <2, 4, 1, 3> <3, 4, 1, 2> <4, 3, 1, 2>
<1, 4, 3, 2> <2, 4, 3, 1> <3, 4, 2, 1> <4, 3, 2, 1>
这个等价类的所有代表到前两个维度的投影产生。
<1, 2> <1, 3> <1, 4>
<2, 1> <2, 3> <2, 4>
<3, 1> <3, 2> <3, 4>
<4, 1> <4, 2> <4, 3>
B 表示具有 720 个元素的等价类。对前两个维度的投影产生 30 个元素。
< 5, 6> < 5, 7> < 5, 8> < 5, 9> < 5, 10>
< 6, 5> < 6, 7> < 6, 8> < 6, 9> < 6, 10>
< 7, 5> < 7, 6> < 7, 8> < 7, 9> < 7, 10>
< 8, 5> < 8, 6> < 8, 7> < 8, 9> < 8, 10>
< 9, 5> < 9, 6> < 9, 7> < 9, 8> < 9, 10>
<10, 5> <10, 6> <10, 7> <10, 8> <10, 9>
所以 A 和 B 的距离是 8 的平方根,因为这是两个向量到投影的最小距离。例如 <3, 4> 和 <5, 6> 产生这个距离。
那么,我对这个问题的理解是否正确?
对于具有 m 个分量的 n 个向量,一个非常简单的算法必须计算 (n - 1) 个距离。对于每个距离,算法将计算 m 的距离!/(米 - 30)!每个向量的投影。因此,对于 100 个维度(您的下限),一个向量有 2.65*10^32 个可能的投影。这需要计算投影之间的大约 7*10^64 距离并找到最小值以找到两个向量的距离。然后重复这个 n 次。
我希望我误解了你或犯了一个错误。否则,这听起来介于真正具有挑战性和不可行之间。
我想到的事情是订购矢量组件并尝试匹配它们。如果可能的话,使用曼哈顿距离可能有助于简化解决方案。