в обобщении на любую размерность смотреть исходники реализации knn

У тебя именно список точек? Тогда наверно хранить кластерами. Т.е. кластер с некоторыми координатами хранит точки не далее r от себя. В кластер могут входить подкластеры и т.д. Всю эту байду логично запихать в корневой кластер с координатами 0,0. Тогда поиск будет идти так: берём список ближайших кластеров, выбираем ближайшие подкластеры... и так пока не упрёмся в точки. Дальше только выбирать список.

2D-дерево поиска: §9.4.1. class TwoDTree{}.

Если точек много, твое дерево будет терабайты занимать. Лучше кластеризуй. А для поиска выбираешь все точки из кластера и сортируешь

// deja vu? я уже на ЛОРе кому-то на такой же вопрос то же самое отвечал.

Нужно все точки, или заранее известен максимальный радиус круга в котором они есть?

Заранее известен. На самом деле, если изучить тему с BSP-tree, то там не будут важны никакие радиусы/пределы - просто сразу получаешь ближайшую точку, а дальше по указателям от неё самые близкие... Чё-то такое в голове крутится.

а дальше по указателям от неё самые близкие...

Это неправильно. Правильно выбросить эту точку и повторить.

BSP-tree в многомерном пространстве - это k-d tree.

А сколько будет точек, как они распределены по области и какие требования к скорости поиска? Потому что «быстрейший» алгоритм, это несерьезно...

а ещё лучше если позволяет религия взять библиотеку для своего языка реализующую knn :)

ну почитать хотя бы википедию http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm

Кстати, странно: поверхностный гуглеж выдал кучу реализаций KNN для всяких пытонов и R, но ни одной для С! Что за нафиг?

Если я правильно понял, то knn не решает поставленную задачу, а зависит от ее решения (необходимо иметь возможность для произвольной точки выбрать k ближайших). Что-то при беглом просмотре http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm я не заметил как искать эти k ближайших соседей.

P.S. Решение исходной задачи можно применить при реализации knn, но не всякое решение задачи поиска k ближайших соседей может быть использовано при эффективном решении исходной задачи.

1) я не вижу никакой разнице в формулировке топика и задачи knn

2) http://en.wikipedia.org/wiki/Closest_pair_of_points_problem как ссылка с основной страницы

внутри R решения например algorithm=c(«VR», «brute», «kd_tree», «cover_tree») и я почему то уверен что там внутри си :)

Cname <- switch(algorithm, cover_tree = "get_KNNX_cover", 
        kd_tree = "get_KNNX_kd", VR = "get_KNNX_VR", CR = "get_KNNX_CR", 
        brute = "get_KNNX_brute")
    knnres <- .C(Cname, t(data), t(query), as.integer(k), d, 
        n, m, nn.index = integer(m * k), nn.dist = double(m * 
            k), DUP = FALSE)

я не вижу никакой разнице в формулировке топика и задачи knn

Это прискорбно.

Буду премного благодарен за ссылочку на сишный код. У самого такие задачи периодически всплывают. Пока что, правда, общего решения не нужно было, но, думаю, что если будет общее, то будет намного проще в дальшейшем. Конечно, зависит еще и от производительности: если общее решение будет на порядок дольше работать, чем велосипед, то предпочтение отдается велосипеду.

А если попробовать сделать так?

1. Все исходные точки заключены внутри большого квадрата.

2. Разбиваем этот квадрат на 4 квадратика меньшего размера.

3. Каждый получившийся квадратик снова разбиваем на 4 равных части.

4. Рекурсивно повторяем разбиение плоскости и строим «квадродерево» (т.н. Quadtree). В листьях этого дерева сохраняем наборы наиболее близких друг ко другу точек, либо отдельные точки.

5. Встаем внутри исходного большого квадрата в любую точку и начинаем поиск по квадро-дереву, в какой ветке эта точка могла бы находиться. В конце концов в процессе поиска дойдем до листочка дерева, в котором хранятся точки наиболее близкие к данной.

6. Если от найденного листочка подниматься обратно к «вершине» дерева, то в этих ветках будут точки, которые расположены все дальше и дальше от той, на которую мы «встали» на 5-м шаге.

Разбиение квадратной части плоскости в «квадродерево» сходно с разбиением кубической части пространства в разреженное воксельное октодерево - Sparse Voxel Octree (сокращенно S.V.O.), которое применяется в компьютерной графике.

google://Sparse Voxel Octree

я не вижу никакой разнице в формулировке топика и задачи knn

Как можно не видить разницы между двумя совершенно разными задачами?

kNN, если верить википедии, — решает задачу поиска значения в некоторой точке функции, заданной значенями на некотором конечном множестве точек, причем эта функция принимает значения из конечного множества. То есть поиск k ближайщих точек для kNN — вспомогательная задача.

В топике же спрашивается о перечислении точек в порядке удаления от заданной. Причем в условии не сказано о том, что число перечисляемых точек ограничено, то есть перечислить надо все точки. Это первое отличие от вспомогательной задачи kNN.

Второе отличие заключается в том, что в задаче в топике требуется установить линейный порядок над множеством точек, а во вспомогательной задаче kNN, этот порядок хоть и предпологается, но нет необходимости в его полном построении. То есть, как я говорил ранее, умея решать subj мы можем получить k ближайших соседей (достаточно просто выполнять алгоритм перечисления точек в порядке удаленности до тех пор, пока не найдем нужное количество точек), но если у нас есть возможность получить множество k ближайших точек, то я вижу только один способ как это использовать. Сначала построим следующую последовательность множеств: ø, f(x,1), f(x,2), …, f(x,N), где x — заданная точка, N — количество точек в исходном множестве, f(x, k) — множество k ближайших соседей точки x. Затем найдём разницу между соседними множествами последовательности. Эти разности будут состоять из точек в нужном порядке. Как видим, решение задачи ТС через вспомогательную задачу kNN стало сложнее.

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

• количество точек в ответе
• отсутствие порядка

http://en.wikipedia.org/wiki/Closest_pair_of_points_problem как ссылка с основной страницы

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

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

Ну почему же. Если есть ОЧЕНЬ МНОГО памяти и можно потратить уйму ОЧЕНЬ МНОГО на предвычисление, то можно находить порядок за O(log N). Под порядком имеется ввиду массив номеров точек исходного множества в требуемом порядке.

хватит пурген нести :)

«Встаю в любую координату 2D-плоскости и получаю список точек в порядке удалённости от текущей.» (С)

именно это и возвращает практически реализация knn.

а это называется: «нести пурген, находясь на воздушном шаре» :)

скачать с http://cran.r-project.org/web/packages/FNN/

Еще раз. Не возвращает, а использует.

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

А теперь выясняется, что для поиска k ближайших соседей используются струкуры данных cover-tree и kd-tree. И что есть kNN search и kNN classificationо. В википедии говорится про второй.

Практическая реализация knn в случае k = N должна мгновенно вернуть полный список точек, не делая ничего более.

можно находить порядок за O(log N). Под порядком имеется ввиду массив номеров точек исходного множества в требуемом порядке

Формирование «массива номеров точек исходного множества в требуемом порядке» уже как минимум O(N), как тогда O(log N) получается?

Для одномерного случая, например, разбиваем отрезок, которому принадлежат все точки на подобласти, где сохраняется порядок расстояний:

[0, 1, 3]

[0.0, 0.5] 1 2 3
[0.5, 1.5] 2 1 3
[1.5, 2.0] 2 3 1
[2.0, 3.0] 3 2 1

Точек перехода будет число инверсий от 1..n до n..1, то есть n(n-1)/2.

Для любой точки binary search'ом по множеству в log(n(n-1)/2 +1) находим какому подотрезку она принадлежит, это эквиалентно log(n). Возвращаем уже сгенерированную перестановку.

Возвращаем уже сгенерированную перестановку.

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

R^2 будет поделена n(n-1) прямой (равноотстоящие от каждой пары точек) на максимальное количество из (n(n-1))(n(n-1)+1)/2 ~ n^4 подобластей. Можно сделать какой-нибудь двухкратный binary search по паре координат, при этом второй массив с интервалами, будет выбран в зависимости от первого результата (при этом он тоже должен быть предвычислен) и тоже получить log(n). Правда сколько это всё потребует памяти мне страшно.

приветствуем пролетающих на воздушном шареTM! приветствуем и машем, машем, машем...

На этапе предвычисления. А он, по моим подсчетам, будет ОЧЕНЬ ДОЛГИМ, порядка O(N^10 log N).

именно это я и имел в виду.

Строим диаграмму Вороного, запоминаем все связи, а затем по заданной точке рекурсивно сканируем соседние ячейки? Да уж, памяти очень много надо будет...

Количество прямых m=n(n-1)/2 (так как нам не важен порядок в паре точек).

Количество областей q = 1 + m(m+1)/2.

Но с порядком ты не ошибся.

Не совсем диаграмму Вороного. В ДВ для области инвариантом является точка, а здесь инвариантом будет — порядок точек по удаленности. Т.е. Области в ДВ придется дробить.

Тогда с этим и МГУшный кластер не справится, если точек будет, скажем, миллион!

по заданной точке рекурсивно сканируем соседние ячейки

А зачем? В точках в соседних ячейках ДВ точно будет другой порядок. Надо по точке находить ячейку.

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

Надо по точке находить ячейку

Либо все ячейки перебирать придется, либо как-то кластеризовать для оптимизации поиска.

Лучше все-таки вначале кластеризовать точки и запомнить связи между соседними кластерами. Хотя бы точек по 10 в кластер — уже быстрей будет.

• находим перебором кластер, содержащий искомую точку
• рекурсивно сканируем связи, перебирая все точки в каждом кластере, формируем массив точек
• сортируем массив по r от заданной точки

Миллион?

Да он бы и для 10000 ещё не вышел из этапа предвычислений, если бы начал работать в момент образования вселенной.

Кластеризовать точки или области?

Ты предлагаешь кластеризовать точки при каждом запросе? Или по какому критерию ты предлагаешь проводить кластеризацию?

Точки кластеризовать. Один раз: в самом начале. Кластеризацию проще всего было бы сделать по равномерной сетке (прямоугольной). Но вроде бы уже должно быть полным-полно готовых алгоритмов для этой задачи. Правда, я что-то не нашел ничего.

Вот, кстати, дельная статейка по поводу k-means