Ближайшие соседи по многомерным данным?

Question

Я задал вопрос несколько дней назад о том, как найти ближайших соседей для данного вектора. Мой вектор теперь 21 измерения, и прежде чем я продолжу дальше, потому что я не из области машинного обучения или математики, я начинаю задавать себе некоторые фундаментальные вопросы:

• Является ли евклидово расстояние хорошей метрикой для поиска ближайших соседей? Если нет, то какие у меня варианты?
• Кроме того, как можно определить правильный порог для определения k-соседей? Можно ли провести анализ, чтобы выяснить это значение?
• Ранее мне предлагалось использовать kd-Trees, но на странице Википедии четко сказано, что для больших размеров kd-Tree почти эквивалентно поиску методом грубой силы. В таком случае, как лучше всего найти ближайших соседей в наборе данных на миллион точек?

Может кто-нибудь уточнить некоторые (или все) из приведенных выше вопросов?

Answer 1

Я думаю, косинус на tf-idf логических функций будет хорошо работать для большинства проблем. Это потому, что его проверенная временем эвристика используется во многих поисковых системах, таких как Lucene. Евклидово расстояние в моем опыте показывает плохие результаты для любых текстовых данных. Выбор различных весовых коэффициентов и k-примеров можно выполнить с помощью обучающих данных и выбора параметров грубой силы.

Answer 2

Многое зависит от того, почему вы хотите знать ближайших соседей. Вы можете взглянуть на алгоритм среднего сдвига http://en.wikipedia.org/wiki/Mean-shift, если вы действительно хотите найти режимы набора данных.

Answer 3

Вы можете попробовать кривую z порядка. Это легко для 3-х измерений.

Answer 4

Является ли евклидово расстояние хорошей метрикой для поиска ближайших соседей? Если нет, какие у меня варианты?

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

Алгоритм кластеризации типа k-средних для подпространственной кластеризации смешанных чисел и категориальные наборы данных