| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > HEngine и KNN |
| Автор: mrgloom 25.2.2014, 17:24 |
| появилась такая статья http://habrahabr.ru/post/211264/ но там используются бинарные векторы, а что если у нас есть обычные численные векторы и мы хотим осуществить поиск ближайшего соседа? Т.е. как преобразовать из численного вектора в бинарный? варианты: 1. на основании набора векторов, по каждой ячейке(числовой позиции например вектор vec={2 3 7} 3 позиции) вычислять среднее или медиану и соответственно если больше то 1, если меньше то 0. 2. кластеризовать вектора, взять k центров и смотреть расстояние до центров, если меньше dist то 1, если больше то 0 (соответственно тут мы получим сокращение размерности). непонятно правда как выбирать k и dist, в предельных случаях будем иметь пустой или очень разреженный вектор или всё в единицах ,а можно сначала заполнить новые вектора длины k расстояниями dist и сделать как в пункте 1. п.с. это похоже получается хэш-функция? но если так делать, то уже точное соответствие не найдешь, т.к. идёт потеря информации. п.с. как раз еще есть http://en.wikipedia.org/wiki/Nearest_neighbor_search#Locality_sensitive_hashing есть так же развитой проект http://www.cs.ubc.ca/research/flann/ , но он так же Approximate Nearest Neighbors. |
| Автор: Mirkes 4.3.2014, 15:45 |
| Довольно забавный подход. Первый вопрос - какая у Вас задача. Исходя из задачи выбирают расстояние. KNN необычайно чувствителен к выбору расстояния. Расстояние Хеминга пригодно только для качественных (категорийных) работ. В простейшем варианте - для бинарных данных. Если Вы работаете с действительными числами, то используйте другие расстояния - квадрат Эвклидова, расстояние Минковского, Манхеттенское и т.д и т.п. Их сотни описаны в литературе. Но увидев один метод подсчета чего-то очень быстро сводить свою задачу к этому чему-то несколько странно. |
| Автор: mrgloom 4.3.2014, 17:26 |
| что значит качественных (категорийных) ? У меня есть набор векторов интов, типа vec={12,1,2,4,23} (только большей размерности примерно 1к) Я использую стандартно евклидово расстояние(l2 distance). выше я предлагал свести вектор интов к бинарному вектору(по идее будет потеря информации). п.с. да я не силён в матане простанства, нормы и т.д. |
| Автор: Mirkes 5.3.2014, 21:47 | ||
Это значит имеет несколько (мало) различных значений. Типичные примеры: пол, образование в анкете (среднее, среднее специальное, высшее). При преобразовании векторов из целых к бинарным может происходить потеря информации, а может не происходить. Сформулируйте задачу, что вы делаете с этими многомерными векторами? |
| Автор: mrgloom 6.3.2014, 10:21 |
| решаю задачу нахождения ближайшего соседа http://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm |
| Автор: Mirkes 6.3.2014, 14:22 |
| Я хорошо знаю задачу нахождения ближайшего соседа и http://www.math.le.ac.uk/people/ag153/homepage/KNN/KNN3.html Однако 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 Кроме того, Вы так и не сформулировали задачу  Зачем Вам ближайшие соседи? Или это просто самоцель? |
| Автор: mrgloom 6.3.2014, 15:18 | ||||||
задача: поиск похожих объектов в базе, типа http://en.wikipedia.org/wiki/Content-based_image_retrieval
изначально, да.
оно может обновляться, но не по 1 точке, а групами точек, я так понимаю, просто при очередном добавлении придётся перестраивать индекс.
http://en.wikipedia.org/wiki/Curse_of_dimensionality что то такое читал |
| Автор: Mirkes 6.3.2014, 16:48 | ||
Вот с таким я не работал, так что посоветовать ничего не могу. Насчет проклятия размерности - с ним очень даже можно бороться путем уменьшения пространства признаков (dimension reduction, feature selection). Однако все эти методы сильно зависят от конкретной задачи (набора признаков) и потребуют большого числа экспериментов для определения нужного поднабора признаков. Желаю удачи. |
