Имам база данни с 500 000 точки в 100-измерно пространство и искам да намеря най-близките 2 точки. Как го правя?
Актуализация: Пространството е евклидово, съжалявам. И благодаря за всички отговори. BTW това не е домашна работа.
Как да намерим най-близките 2 точки в 100-измерно пространство с 500 000 точки?
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)
Можете да опитате ANN библиотека, но това дава надеждни резултати само до 20 измерения .
person
dalle
schedule
10.10.2010
Благодаря. ANN е точно това, което търсих. Надяваме се, че може да побере всичко в RAM.
- person louzer; 11.10.2010
ANN е лесен за използване, но трябва да се отбележи, че това е приблизително изпълнение на най-близкия съсед, така че не е гарантирано, че е правилно.
- person chuck taylor; 12.10.2010
Има глава в Въведение в алгоритмите, посветена на намирането на две най-близки точки в двумерното пространство в O( n*logn) време. Можете да го разгледате в google books. Всъщност го предлагам на всички, тъй като начинът, по който прилагат техниката "разделяй и владей" към този проблем, е много прост, елегантен и впечатляващ.
Въпреки че не може да се разшири директно към вашия проблем (тъй като константата 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
Използвайте kd дърво. Разглеждате проблем с най-близкия съсед и има силно оптимизирани структури от данни за справяне с този точен клас проблеми.
http://en.wikipedia.org/wiki/Kd-tree
P.S. Забавен проблем!
person
Stefan Mai
schedule
10.10.2010
Изпълнете PCA на вашите данни, за да конвертирате вектори от 100 измерения в 20 измерения. След това създайте K-най-близко съседно дърво (KD-Tree) и вземете най-близките 2 съседи въз основа на евклидово разстояние.
Като цяло, ако не. на измеренията са много големи, тогава трябва да използвате подход с груба сила (паралелно + разпределено/намаляване на картата) или подход, базиран на клъстериране.
person
Muhammad Hasan Khan
schedule
10.10.2010
Благодаря. Намалявам размерите според вашите предложения.
- person louzer; 11.10.2010
Ако стартирате PCA 100 -› 20 измерения, не забравяйте да проверите частта от дисперсията, sum( 20 eigenvalues ) / sum(all).
- person denis; 01.02.2011
Използвайте структурата от данни, известна като KD-TREE. Ще трябва да разпределите много памет, но може да откриете една или две оптимизации по пътя въз основа на вашите данни.
http://en.wikipedia.org/wiki/Kd-tree.
Мой приятел работеше върху докторската си теза преди години, когато срещна подобен проблем. Работата му беше от порядъка на 1 милион точки в 10 измерения. Създадохме kd-дърво библиотека, за да го решим. Може да успеем да изкопаем кода, ако искате да се свържете с нас офлайн.
Ето неговата публикувана статия: http://www.elec.qmul.ac.uk/people/josh/documents/ReissSelbieSandler-WIAMIS2003.pdf
person
selbie
schedule
10.10.2010
kdtrees улесняват намирането на най-близкия съсед до дадена точка за O(log n) време, доколкото си спомням. Има ли оптимизация за намиране на най-близката двойка точки за по-малко от O(n log n)?
- person rampion; 10.10.2010
-1, също според wikipedia kD-дървото е ефективно, ако N ›› 2^k (където k е размери и N брой точки; в този случай 2^100 ›› 5e5 и отговорът е напълно подвеждащ)
- person Unreason; 12.10.2010
10d не е 100d. Дори ако точките от данни лежат приблизително в 10-d равнина в 100d, kd-дървото не може да работи (imho): помислете за kd-дърво с дълбочина 100 s.
- person denis; 01.02.2011
