Как найти ближайшие 2 точки в 100-мерном пространстве с 500 000 точек?

У меня есть база данных с 500 000 точек в 100-мерном пространстве, и я хочу найти ближайшие 2 точки. Как это сделать?

Обновление: пространство евклидово, извините. И спасибо за все ответы. Кстати, это не домашнее задание.


performance algorithm pca nearest-neighbor approximate-nn-searching
person louzer    schedule 10.10.2010    source источник
comment
Ради интереса, откуда вы взяли 100-мерное пространство?   -  person Will A    schedule 10.10.2010
comment
вопрос лишен ясности. это математический вопрос?   -  person Sarmaad    schedule 10.10.2010
comment
@Sarmaad В вопросе может не хватать многих вещей, но в нем есть ясность: прочитав 1 предложение, я полностью понимаю проблему. (хотя тип пространства не упоминается, по умолчанию обычно предполагается евклидово)   -  person Nikita Rybak    schedule 10.10.2010
comment
по теме: stackoverflow.com/q/2486093 Помните, что подход KDTree в вашем случае требует ~ 5 дней вычислений.   -  person jfs    schedule 11.10.2010
comment
какую производительность вы ищете?   -  person Unreason    schedule 11.10.2010
comment
@ J.F.Sebastian: я собираюсь найти приблизительное решение k-NN. Используя библиотеку ANN, предложенную @dalle ниже. Но я планирую сначала уменьшить размеры до 20, используя PCA, согласно предложениям @Hasan Khan.   -  person louzer    schedule 11.10.2010
comment
@Unreason: производительность, которую я ищу, - это то, что может работать в течение недели или около того.   -  person louzer    schedule 11.10.2010
comment
@louzer, ну, если вы переборщите, вам понадобится 500 000 * 499 999/2 сравнений, что составляет 1,25e11 сравнений, каждое из которых требует 400 операций с плавающей запятой, что приводит к 5e13. В один день у вас есть около 86400 секунд, поэтому вам потребуется 5,8e8 FLOPS, и я думаю, что современные процессоры примерно соответствуют этому уровню. С некоторыми циклами, потраченными на другие вещи, я думаю, вы могли бы переборщить с этим за неделю.   -  person Unreason    schedule 11.10.2010
comment
@louzer: вот подход грубой силы с использованием KDTree и многопроцессорной обработки ideone.com/Z7uSc (вы можете проверить его на своем решении за небольшое количество баллов)   -  person jfs    schedule 11.10.2010
comment
@ J.F.Sebastian, ты должен поставить это как ответ ...   -  person Unreason    schedule 12.10.2010
comment
@Will, я получил 104-мерное пространство, когда изобразил все белки в соответствии с определенными функциональными и структурными параметрами. Я смог получить очень небольшой набор данных только с ближайшими эволюционными родственниками, решив задачу k-NN. Я провел классификацию этих родственников, чтобы получить сигнатуры высокой точности и высокой полноты, общие для всех белков с определенными свойствами.   -  person louzer    schedule 06.12.2010

Ответы (5)


arrow_upward
6
arrow_downward

Вы можете попробовать библиотеку ANN, но она дает надежные результаты только до 20 измерений. .

person dalle    schedule 10.10.2010
comment
Спасибо. ANN — это именно то, что я искал. Надеюсь, он может хранить все в оперативной памяти. - person louzer; 11.10.2010
comment
ИНС проста в использовании, но следует отметить, что это приблизительная реализация ближайшего соседа, поэтому ее правильность не гарантируется. - person chuck taylor; 12.10.2010

arrow_upward
17
arrow_downward

В Введение в алгоритмы есть глава, посвященная поиску двух ближайших точек в двумерном пространстве в O( n*logn) время. Вы можете ознакомиться с ним в книгах Google. На самом деле, я предлагаю это всем, потому что то, как они применяют технику «разделяй и властвуй» к этой проблеме, очень простое, элегантное и впечатляющее.

Хотя его нельзя распространить непосредственно на вашу проблему (поскольку константа 7 будет заменена на 2^101 - 1), для большинства наборов данных это должно подойти. Итак, если у вас достаточно случайный ввод, это даст вам O(n*logn*m) сложность, где n — количество точек, а m — количество измерений.

редактировать
Это все при условии, что у вас есть евклидово пространство. То есть длина вектора v равна sqrt(v0^2 + v1^2 + v2^2 + ...). Однако, если вы можете выбрать метрику, могут быть и другие варианты оптимизации алгоритма.

person Nikita Rybak    schedule 10.10.2010

arrow_upward
7
arrow_downward

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

http://en.wikipedia.org/wiki/Kd-tree

P.S. Веселая проблема!

person Stefan Mai    schedule 10.10.2010

arrow_upward
6
arrow_downward

Запустите PCA для ваших данных, чтобы преобразовать векторы из 100 измерений в, скажем, 20 измерений. Затем создайте дерево K-ближайших соседей (KD-Tree) и получите двух ближайших соседей на основе евклидова расстояния.

Вообще если нет. размеров очень велики, тогда вам нужно либо использовать подход грубой силы (параллельный + распределенный/уменьшение карты), либо подход, основанный на кластеризации.

person Muhammad Hasan Khan    schedule 10.10.2010
comment
Спасибо. Я уменьшаю размеры в соответствии с вашими предложениями. - person louzer; 11.10.2010
comment
Если вы запускаете PCA 100 -> 20 измерений, обязательно проверьте долю дисперсии, сумму (20 собственных значений) / сумму (все). - person denis; 01.02.2011

arrow_upward
4
arrow_downward

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

http://en.wikipedia.org/wiki/Kd-дерево.

Мой друг работал над своей кандидатской диссертацией много лет назад, когда столкнулся с похожей проблемой. Его работа была порядка 1 миллиона точек в 10 измерениях. Мы создали библиотеку kd-tree, чтобы решить эту проблему. Возможно, мы сможем раскопать код, если вы захотите связаться с нами в автономном режиме.

Вот его опубликованная статья: http://www.elec.qmul.ac.uk/people/josh/documents/ReissSelbieSandler-WIAMIS2003.pdf

person selbie    schedule 10.10.2010
comment
Насколько я помню, kdtrees позволяет легко найти ближайшего соседа к заданной точке за время O(log n). Есть ли оптимизация для поиска ближайшей пары точек менее чем за O (n log n)? - person rampion; 10.10.2010
comment
-1, также согласно википедии kD-tree эффективны, если N ›› 2^k (где k — размерность и N количество точек; в данном случае 2^100 ›› 5e5 и ответ полностью вводит в заблуждение) - person Unreason; 12.10.2010
comment
10д не 100д. Даже если точки данных лежат примерно в 10-мерной плоскости в 100d, kd-дерево не может работать (имхо): подумайте о kd-дереве глубиной 100 с. - person denis; 01.02.2011