появилась такая статья HEngine

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


варианты:
1. на основании набора векторов, по каждой ячейке(числовой позиции например вектор vec={2 3 7} 3 позиции) вычислять среднее или медиану и соответственно если больше то 1, если меньше то 0.
2. кластеризовать вектора, взять k центров и смотреть расстояние до центров, если меньше dist то 1, если больше то 0 (соответственно тут мы получим сокращение размерности). непонятно правда как выбирать k и dist, в предельных случаях будем иметь пустой или очень разреженный вектор или всё в единицах ,а можно сначала заполнить новые вектора длины k расстояниями dist и сделать как в пункте 1.

п.с. это похоже получается хэш-функция?

но если так делать, то уже точное соответствие не найдешь, т.к. идёт потеря информации.


п.с. как раз еще есть LSH 


есть так же развитой проект FLANN , но он так же Approximate Nearest Neighbors.


Это сообщение отредактировал(а) mrgloom - 25.2.2014, 17:26

Довольно забавный подход. Первый вопрос - какая у Вас задача.
Исходя из задачи выбирают расстояние. KNN необычайно чувствителен к выбору расстояния. Расстояние Хеминга пригодно только для качественных (категорийных) работ. В простейшем варианте - для бинарных данных. Если Вы работаете с действительными числами, то используйте другие расстояния - квадрат Эвклидова, расстояние Минковского, Манхеттенское и т.д и т.п. Их сотни описаны в литературе.
Но увидев один метод подсчета чего-то очень быстро сводить свою задачу к этому чему-то несколько странно. 

что значит качественных (категорийных) ?

У меня есть набор векторов интов, типа vec={12,1,2,4,23}  (только большей  размерности примерно 1к)
Я использую стандартно евклидово расстояние(l2 distance).

выше я предлагал свести вектор интов к бинарному вектору(по идее будет потеря информации).

п.с. да я не силён в матане простанства, нормы и т.д.


Это сообщение отредактировал(а) mrgloom - 4.3.2014, 17:28

Это значит имеет несколько (мало) различных значений. Типичные примеры: пол, образование в анкете (среднее, среднее специальное, высшее).

При преобразовании векторов из целых к бинарным может происходить потеря информации, а может не происходить.

Сформулируйте задачу, что вы делаете с этими многомерными векторами?

решаю задачу нахождения ближайшего соседа
http://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm

Я хорошо знаю задачу нахождения ближайшего соседа и KNN
Однако KNN это инструмент и не более. А какова задача?

Поясняю. Пусть у нас МНОГО точек и нам нужно находить ближайших соседей для новых точек. В этом случае применяются специальные методы индексации точек для быстрого поиска соседей. Если множество базовых точек регулярно обновляется, это уже другая задача.

Теперь по поводу 1000 мерных векторов. Есть хорошая статья о применимости KNN в этой ситуации: Beyer, K.; Goldstein, J.; Ramakrishnan, R.; Shaft, U. (1999). "When is “Nearest Neighbor” Meaningful?". Proc. 7th International Conference on Database Theory - ICDT'99. LNCS 1540: 217–235. doi:10.1007/3-540-49257-7_15. ISBN 978-3-540-65452-0

Кроме того, Вы так и не сформулировали задачу  
Зачем Вам ближайшие соседи?
Или это  просто самоцель?

задача: поиск похожих объектов в базе, типа CBIR


изначально, да.


оно может обновляться, но не по 1 точке, а групами точек, я так понимаю, просто при очередном добавлении придётся перестраивать индекс.



http://en.wikipedia.org/wiki/Curse_of_dimensionality
что то такое читал

Вот с таким я не работал, так что посоветовать ничего не могу.

Насчет проклятия размерности - с ним очень даже можно бороться путем уменьшения пространства признаков (dimension reduction, feature selection).

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

Желаю удачи.