Быстрый поиск для вектора словаря к данному вектору. Высокие размеры
Я ищу ответ, который масштабируется, но для моей определенной цели, у меня есть 48-й вектор размера. Это могло быть представлено как массив 48 целых чисел все между 0 и 255.
У меня есть большой словарь этих векторов, приблизительно 25 тысяч из них.
Я должен смочь взять вектор, который может или не может быть в моей базе данных и быстро найти, какой вектор от базы данных является самым близким. Самым близким я имею в виду с точки зрения традиционной формулы расстояния.
Мой код закончится в Python, но это - больше общий вопрос.
Грубая сила является слишком медленной. Мне нужен близкий поиск скорости словаря. У кого-либо есть идея?
2 ответа
Другой метод, который окажется полезным, - хеширование с учетом местоположения: http://en.wikipedia.org/wiki/Locality_sensitive_hashing
Из вашего вопроса не ясно, нужно ли вам - точные- ближайшие соседи. Если вам нравится возвращать вектор, который является приблизительно ближайшим соседом, есть более быстрые решения. См. Здесь ( http://www.cs.umd.edu/~mount/ANN/ )
Я бы предложил реализовать kd-tree , на котором вы можете выполнить поиск ближайшего соседа . В худшем случае время поиска для N точек в k измерениях составляет O (kN ^ (1-1 / k)) , поэтому оно должно масштабироваться сублинейно по N.
Если у меня будет время, я вернусь к этот ответ и дать менее краткое объяснение, чем в Википедии.
Поскольку вы работаете на python, эта запись в кулинарной книге Scipy на kdtrees должна помочь.