Высококачественный поиск ближайшего соседа и хеширование чувствительности местности

Question

Вот основная проблема.У меня есть очень большая база данных (25 000 или около того) из 48 векторов, каждый из которых заполнен значениями в диапазоне от 0 до 255.Специфика не так важна, но я полагаю, что это может помочь создать контекст.

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

Я написал хеш-функцию, как лучше всего описано в статье в разделе "Стабильные распределения"Можно.Вот код:

def lsh(vector, mean, stdev, r = 1.0, a = None, b = None):
 if not a:
  a = [normalvariate(mean, stdev) for i in range(48)]
 if not b:
  b = uniform(0, r)
 hashVal = (sum([a[i]*vectorA[i] for i in range(48)]) + b)/r
 return hashVal

Функция хеширования "работает", по крайней мере, некоторые.Если я упорядочу список точек по хэш-значению и вычислю среднее расстояние между точкой и ее соседом в списке, среднее расстояние составит около 400, по сравнению со средним расстоянием около 530 для любых двух случайно выбранных точек.

Мои самые большие вопросы:

A: Любые предложения о том, где я могу прочитать больше об этом.Мой поиск не дал много результатов.

B: Метод предполагает вывод целочисленного значения (а моего нет).И затем вы должны попытаться найти совпадения для этого целочисленного значения, а совпадение означает вероятного ближайшего соседа.Я понимаю, что должен вычислить некоторый набор таблиц значений хеш-функции для всех моих точек, а затем проверить упомянутые таблицы на наличие совпадений хэшей, но значения, которые я возвращаю, не кажутся достаточно хорошими, чтобы в итоге я получилспички на всех.С моей стороны требуется дополнительное тестирование.

C: Инструкции о том, как создавать хеш-функции на основе других методов хеширования?

Answer 1

Вот два ответа:

B : на странице Википедии указано, что math.floor() следует использовать для hashVal: так вы получаете целые числа.* C : если вы хотите использовать метод Хэмминга, вы можете реализовать его довольно просто: каждая хеш-функция Хемминга просто определяется координатой (между 0 и 47) и числом бит (между 0 и 7).Вы можете получить значение целого числа в данном бите b с помощью:

bool(i & 2**b)

Answer 2

Maby, это немного не по теме, но вы можете попробовать использовать PCA http://en.wikipedia.org/wiki/Principal_component_analysis для уменьшения размерности набора данных. Должно быть много модулей PCA, разработанных для numPy (например: http://folk.uio.no/henninri/pca_module/). Метод довольно прост, и с готовыми к использованию модулями это будет несложно.

По сути, это сокращает количество измерений (вы должны иметь возможность указать желаемое число), максимизируя дисперсию в пределах заданного количества измерений.