Нужна правильная структура данных или индекс для быстрого поиска пользователей на основе трехмерных точек и факторов важности.

У меня есть большое количество 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)

А затем найти пользователя, который больше всего похож на Чарли, выбрав пользователя с наименьшей стоимостью. На данный момент я написал код глупым способом (выполнив множество циклов), но я ищу способ правильно справиться с тем фактом, что существует несколько точек И факторов важности.

Я начал изучать пространственные индексы, но я не думаю, что они будут работать, поскольку у меня есть несколько точек, но, возможно, я мог бы развернуть точки в точку более высокого измерения? То есть вместо 6 точек в 3 измерениях у меня может быть 1 точка в 18 измерениях? Все еще не могу справиться с фактором важности, но это было бы лучше, чем ничего.

К сожалению, я не могу использовать здесь векторы и косинусы, так как (1,1,1) и (400,400,400) — очень противоположные вещи.

Любые идеи?


python optimization math data-structures spatial-index
person zachaysan    schedule 11.05.2012    source источник
comment
Я не эксперт в алгоритмах, но означает ли это, что вам нужно установить какой-то приоритет либо на расстояние, либо на вес, чтобы сузить набор данных? Как говорится, сначала рассмотрите N ближайших, а затем отсортируйте вес? Мне кажется, что для того, чтобы рассмотреть эту функцию, вам нужно будет проверить каждую комбинацию.   -  person jdi    schedule 11.05.2012
comment
Вы можете рассчитать евклидово расстояние от этой точки до других точек. Является ли фактор важности отдельным параметром или это просто вес существующих векторов?   -  person Joel Cornett    schedule 11.05.2012
comment
Просто вес на существующих точках.   -  person zachaysan    schedule 12.05.2012

Ответы (1)


arrow_upward
1
arrow_downward

Поскольку вы еще не получили ответов, я подумал, что могу хотя бы поделиться некоторыми мыслями. Я использовал модуль python kd tree для быстрого поиска ближайших соседних точек:
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, Мэри могла бы быть более релевантной?

Я знаю, что у вас есть более надежная функция для создания индекса, но для этого потребуется просмотреть каждую точку в вашей коллекции.

person jdi    schedule 11.05.2012