需要一個適當的數據結構或索引，以便根據3d點和重要因素進行快速用戶查找

Question

我有大量與重要因素配對的3d點。

每個用戶都有6分。例如：人查理有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個點而不是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模塊來至少獲得最接近每個點的「人」的頭腦風暴特定的人的集合：

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> 

我想，結果，你可以看看最常見的匹配的「人」還是再考慮權重。或者，也許你可以總結結果中的重要因素，然後採取最高評分。這樣，如果瑪麗只匹配一次，但有10個因素，而菲爾有3匹配，但只有5個，瑪麗可能更相關？

我知道你有一個更強大的函數來創建索引，但它需要通過你的集合中的每一個點。