python - 需要一个合适的数据结构或索引，以便根据 3d 点和重要性因素快速查找用户

Question

我有大量与重要性因素配对的 3d 点。

每个用户都有六分。例如:查理有 6 个点:(22,44,55) 是他的第一个点，重要性因子为 3，(10,0,0) 是他的第二个向量，重要性因子为 2.8，一直到他的第六点是 (100,300,200)，重要性因子为 0.4。

我想做的是找到与查理最相似的人，而不是遍历所有其他人。基本上为每个用户最小化此功能(即，将该用户的正确六个点与查理匹配):

pythagoras(point, point2) * max(importance_factor, importance_factor2) * (abs(importance_factor - importance_factor2) + 1)

然后通过选择成本最低的用户来找到与查理最相似的用户。我现在已经以愚蠢的方式编写了代码(通过执行大量循环)，但我正在寻找一种方法来正确处理存在多个点和重要性因素的事实。

我开始研究空间索引，但我认为它们不会起作用，因为我有多个点，但也许我可以将这些点展开到更高维度的点中？所以我可以在 18 维中有 1 个点，而不是 3 个维度中的 6 个点？仍然无法处理重要性因素，但总比没有好。

不幸的是，我不能在这里使用向量和余弦，因为 (1,1,1) 和 (400,400,400) 是非常相反的事物。

有什么想法吗？

Answer 1

既然你还没有得到任何答案，我想我至少会贡献一些想法。我使用了 python k-d 树模块来快速搜索最近邻点:
http://code.google.com/p/python-kdtree/downloads/detail?name=kdtree.py
只要它们的大小相同，它就可以采用任意点长度。

我不确定你想如何应用“重要性”的权重，但这里只是关于如何使用 kdtree 模块至少让最接近的“人”到给定的每个点的头脑 Storm 人设:

import numpy
from kdtree import KDTree
from itertools import chain

class PersonPoint(object):

    def __init__(self, person, point, factor):
        self.person = person 
        self.point = point 
        self.factor = factor 

    def __repr__(self):
        return '<%s: %s, %0.2f>' % (self.person, 
            ['%0.2f' % p for p in self.point], self.factor) 

    def __iter__(self):
        return self.point

    def __len__(self):
        return len(self.point)

    def __getitem__(self, i):
        return self.point[i]


people = {}
for name in ('bill', 'john', 'mary', 'jenny', 'phil', 'george'):
    factors = numpy.random.rand(6)
    points = numpy.random.rand(6, 3).tolist()
    people[name] = [PersonPoint(name, p, f) for p,f in zip(points, factors)]

bill_points = people['bill']
others = list(chain(*[people[name] for name in people if name != 'bill']))

tree = KDTree.construct_from_data(others)

for point in bill_points:
    # t=1 means only return the 1 closest.
    # You could set it higher to return more.
    print point, "=>", tree.query(point, t=1)[0]

结果:

<bill: ['0.22', '0.64', '0.14'], 0.07> => 
    <phil: ['0.23', '0.54', '0.11'], 0.90>

<bill: ['0.31', '0.87', '0.16'], 0.88> => 
    <phil: ['0.36', '0.80', '0.14'], 0.40>

<bill: ['0.34', '0.64', '0.25'], 0.65> => 
    <jenny: ['0.29', '0.77', '0.28'], 0.40>

<bill: ['0.24', '0.90', '0.23'], 0.53> => 
    <jenny: ['0.29', '0.77', '0.28'], 0.40>

<bill: ['0.50', '0.69', '0.06'], 0.68> => 
    <phil: ['0.36', '0.80', '0.14'], 0.40>

<bill: ['0.13', '0.67', '0.93'], 0.54> => 
    <jenny: ['0.05', '0.62', '0.94'], 0.84>

我想出了这个结果，你可以看看最频繁匹配的“人”，或者再考虑权重。或者，也许您可​​以汇总结果中的重要因素，然后选择评分最高的因素。那样的话，如果 mary 只匹配一次但有 10 个因子，而 phil 有 3 个匹配但总计只有 5 个，mary 可能更相关？

我知道您有更强大的功能来创建索引，但它需要遍历集合中的每个点。