Измерение расстояния между векторами

Question

У меня есть набор из 300 000 или около того векторов, которые я бы хотел каким-то образом сравнить, и, учитывая один вектор, я хочу найти ближайший вектор, о котором я подумал о трех методах.

• Простой евклидово расстояние
• косинус сходство
• Используйте ядро ​​(например, гауссовой) вычислить матрицу Грама.
• Рассматривайте вектор как дискретное распределение вероятности (что делает смысл ) и вычисляет некоторую мера дивергенции.

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

Извините за слабый вопрос, но я должен был начать где-то ...

Спасибо!

Answer 1

Ваш вопрос не совсем ясен, вы ищете метрику расстояния между векторами или алгоритм для эффективного поиска ближайшего соседа?

Если ваши векторы просто содержат числовой тип, например, двойные или целые числа, вы можете найти ближайшего соседа эффективно, используя такую ​​структуру, как kd-дерево. (так как вы просто смотрите на точки в d-мерном пространстве). См. http://en.wikipedia.org/wiki/Nearest_neighbor_search, для других методов.

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

Answer 2

Если ваши векторы очень скудные по своей природе и если они бинарные, вы можете использовать расстояние Хэмминга или Хеллингера. Когда размеры вашего вектора велики, избегайте использования Euclidean (см. http://en.wikipedia.org/wiki/Curse_of_dimensionality)

Для обзора измерений расстояния/подобия обратитесь к http://citeseerx.ist.psu.edu/viewdoc/download?rep=rep1&type=pdf&doi=10.1.1.154.8446, хотя документ ограничивает его до пары распределений вероятностей.