Szybkie wyszukiwanie wektora słownikowego dla danego wektora. Wysokie wymiary

Question

Szukam odpowiedzi, która skaluje, ale dla mojego konkretnego celu, mam wektor 48-wymiarowy. Może to być reprezentowane jako tablica składająca się z 48 liczb całkowitych od 0 do 255.

Mam duży słownik tych wektorów, w przybliżeniu 25 tysięcy z nich.

Potrzebuję być w stanie wziąć wektor, który może ale nie musi być w mojej bazie danych, i szybko znaleźć który wektor z bazy danych jest najbliżej. Najbliższy, mam na myśli w kategoriach tradycyjnej formuły dystansowej.

Mój kod skończy się pytonem, ale jest to bardziej ogólne pytanie.

Brute Force jest zbyt wolny. Potrzebuję wyszukiwania w pobliżu słownika. Ktoś ma pomysł?

Answer 1

Inną techniką, że okażą się przydatne jest lokalizacja wrażliwy mieszania: http://en.wikipedia.org/wiki/Locality_sensitive_hashing

Nie jest jasne, z pytaniem, czy trzeba -exact- najbliższych sąsiadów. Jeśli jesteś zadowolony z powrotu wektora, który jest w przybliżeniu najbliższym sąsiadem, istnieją szybsze rozwiązania. Zobacz tutaj (http://www.cs.umd.edu/~mount/ANN/)

Answer 2

Proponuję zastosować kd-tree, w którym można wykonać Nearest neighbour search. Najgorzej wyszukiwany czas dla N punktów w wymiarach k to O(k.N^(1-1/k)), więc powinien skalować podnajmująco w N.

Jeśli będę mieć czas, powrócę do tej odpowiedzi i udzielę mniej lapidarnego wyjaśnienia, że ​​Wikipedia.

Ponieważ pracujesz w Pythonie, pomocna powinna być książka kucharska Scipy pod numerem kdtrees.