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

I. Метрика Расстояния

• базовые статистические распространение ваших данных;

• связь между функциями которые содержат ваши данные (являются они независимый-т. е. то, что делает ковариационная матрица выглядит так); и

• координатное пространство, из которого ваш данные были получены.

Если у вас нет предварительных знаний о распределении(Ях), из которых были отобраны ваши данные, по крайней мере один (хорошо документированный и тщательный) исследование делает вывод, что евклидово расстояние является лучшим выбором.

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

это не удалось для меня только несколько раз, каждый из этих случаев евклидово расстояние не удалось, потому что базовая (декартова) система координат была плохим выбором. А вы обычно узнаете это, потому что, например, длины пути (расстояния) больше не являются аддитивными-например, когда метрическое пространство является шахматной доской, расстояние Манхэттена лучше, чем Евклидово, точно так же, когда метрическое пространство является землей, а ваши расстояния-трансконтинентальными полетами, метрика расстояния, подходящая для полярной системы координат, является хорошей идеей (например, Лондон до Вены составляет 2,5 часа, Вена до Санкт-Петербурга-еще 3 часа, более или менее в том же направлении, но Лондон до Санкт-Петербурга не 5,5 часов, а компания HRS.)

но кроме тех случаев, когда ваши данные принадлежат в декартовой системе координат, выбор метрику расстояния, как правило, не материальные. (См. блоге от студента CS, сравнивая несколько метрик расстояния, изучая их влияние на классификатор kNN--Chi square дают лучшие результаты, но различия невелики; более полное исследование находится в академической статье,сравнительное исследование функций расстояния для ближайших Соседи--Махаланобис (по существу евклидов нормированный для учета размерности ковариации) был лучшим в этом исследовании.

одно важное условие: чтобы вычисления метрики расстояния были значимыми, вы должны повторно масштабировать ваши данные -- редко можно построить модель kNN для получения точных прогнозов, не делая этого. Например, если вы строите модель kNN для прогнозирования спортивных результатов, а ваши переменные ожидания рост (см), Вес (кг), жировые отложения ( % ) и пульс покоя (удары в минуту), то типичная точка данных может выглядеть примерно так: [ 180.4, 66.1, 11.3, 71 ]. Очевидно, что в расчете расстояния будет преобладать высота, в то время как вклад bodyfat % будет почти незначительным. Другими словами, если бы вместо этого данные сообщались по-другому, так что вес тела был в граммах, а не в килограммах, то первоначальное значение 86,1 было бы 86 100, что оказало бы большое влияние на ваш результаты, которые именно то, что вы не хотите. Вероятно, наиболее распространенным методом масштабирования является вычитание среднего и деление на стандартное отклонение (среднее и sd относятся к вычисленным отдельно для каждого столбца или функции в этом наборе данных; X относится к отдельной записи / ячейке в строке данных):

X_new = (X_old - mu) / sigma

второй. Структуры Данных

Если вас беспокоит производительность структуры KD-tree, a Вороного Тесселяции - это концептуально простой контейнер, но это значительно улучшит производительность и масштабирование лучше, чем KD-деревья.

это не самый распространенный способ сохранения данных обучения kNN, хотя применение VT для этой цели, а также вытекающие из этого преимущества производительности, хорошо документированы (см., например, this Microsoft Research report). Практическая значимость этого заключается в том, что при условии, что вы используете "основной" язык (например, в индекс TIOBE) тогда вы должны найти библиотеку для выполнения VT. Я знаю, что в Python и R, есть несколько вариантов для каждого языка (например,вороного пакет для R доступен на сайте CRAN)

использование VT для kNN работает следующим образом::

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

Как выбрать центры Вороного? Я использую два ортогональных направления. После случайного выбора точек w вычислите VT для ваших данных обучения. Затем проверьте количество точек данных, назначенных каждому центру Вороного--эти значения должны быть примерно одинаковыми (учитывая равномерную плотность точек в вашем пространстве данных). В двух измерениях это вызвало бы VT с плитками того же размера.Это первое правило, второе. Выберите w путем итерации--запустите алгоритм kNN с параметром W в качестве переменной и измерьте производительность (время, необходимое для возврата прогноза путем запроса VT).

Итак, представьте, что у вас есть один миллион точек данных..... Если точки были сохранены в обычной двумерной структуре данных, или kd-tree, вы бы выполнили в среднем пару миллионов вычислений расстояния для каждого новые точки данных, переменную отклика которых вы хотите предсказать. Конечно, эти вычисления выполняются на одном наборе данных. При V/T поиск ближайших соседей выполняется в два этапа один за другим, против двух разных популяций данных-сначала против центров Вороного, затем, как только ближайший центр найден, точки внутри ячейки, соответствующие этому центру, являются поиск, чтобы найти фактического ближайшего соседа (путем последовательных вычислений расстояния) в сочетании, эти два поиска намного быстрее, чем один поиск грубой силы. Это легко увидеть: для 1M точек данных предположим, что вы выбрали 250 центров Вороного для тесселирования вашего пространства данных. В среднем, каждая ячейка Вороного будет иметь 4000 точек данных. Поэтому вместо того, чтобы выполнять в среднем 500 000 вычислений расстояния (грубая сила), вы выполняете гораздо меньше, в среднем всего 125 + 2,000.

раздел III. Расчет результат (переменная прогнозируемый ответ)

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

в/р/т первый компонент, вы можете определить самое лучшее значение n при решении задачи оптимизации (очень похоже на оптимизацию по методу наименьших квадратов). Это теория; на практике большинство людей просто используют n=3. В любом случае, просто запустить алгоритм kNN над набором тестовых экземпляров (для вычисления прогнозируемых значений) для n=1, n=2, n=3 и т. д. и сюжет ошибки как функцию от N. Если вы просто хотите правдоподобного значения для n, чтобы начать снова, просто использовать N = 3.

второй компонент заключается в том, как взвешивать вклад каждого из соседи (при условии n > 1).

должна лучше весовая функция, которая существенно избегает этого ограничения является гауссовой функции, который в Python, выглядит так:

def weight_gauss(dist, sig=2.0) :
    return math.e**(-dist**2/(2*sig**2))

чтобы вычислить прогнозируемое значение с помощью кода kNN, вы должны определить n ближайших соседей к точке данных, переменную отклика которой вы хотите предсказать ('test экземпляр'), затем вызовите функцию weight_gauss, один раз для каждого из N соседей, передавая расстояние между каждым соседом тестовой точки.Эта функция возвращает вес для каждого соседа, который затем используется в качестве коэффициента этого соседа в вычислении средневзвешенного значения.

с чем вы столкнулись, называется проклятие размерности. Иногда полезно запустить такой алгоритм, как PCA или ICA чтобы убедиться, что вам действительно нужны все 21 измерения и, возможно, найти линейное преобразование, которое позволит вам использовать менее 21 С примерно одинаковым качеством результата.

обновление: Я столкнулся с ними в книге под названием Biomedical Signal Processing by Rangayyan (надеюсь, я помню это правильно). ICA-это не тривиальный метод, но он был разработан исследователями в Финляндии, и я думаю, что код Matlab для него общедоступен для загрузки. PCA является более широко используемым методом, и я считаю, что вы должны быть в состоянии найти его R или другую программную реализацию. PCA выполняется путем итерационного решения линейных уравнений. Я сделал это слишком давно, чтобы помнить как. = )

идея заключается в том, что вы разбиваете свои сигналы на независимые собственные векторы (дискретные собственные функции, действительно) и их собственные значения, 21 в вашем случае. Каждое собственное значение показывает размер вклада, который каждая собственная функция обеспечивает для каждого из ваших измерений. Если собственное значение является крошечным, вы можете очень точно представлять сигналы, не используя его соответствующую собственную функцию вообще, и именно так вы избавляетесь от измерения.

чтобы ответить на ваши вопросы по одному:

• нет, евклидово расстояние является плохой метрикой в многомерном пространстве. В основном в высоких измерениях существует небольшая разница между ближайшим и самым дальним соседом.
• много статей / исследований есть в данных с высоким измерением, но большинство материалов требует много математической софистики.
• дерево KD плохо для больших размерных данных ... избегайте его всеми средствами

здесь хорошая бумага, чтобы вы начали в правильном направлении. "когда в ближайшем соседе значимо?"by Beyer et all.

Я работаю с текстовыми данными размеров 20K и выше. Если вам нужен совет, связанный с текстом, я мог бы помочь вам.

лучшие ответы хороши, но старые, поэтому я хотел бы добавить ответить на 2016.

---

приблизительный поиск ближайших соседей (ANNS), что в пользу некоторой точности, ускоряет процесс. Вы получаете хорошее приближение из точного NN, с хорошей пригодностью.

---

горячие темы, которые могут быть достойны:

1. современные подходы LSH, например Razenshteyn ' s.
2. лес РКД: лес(Ы) рандомизированных K-d деревьев (RKD), как описано в ФЛАННА, или в более позднем подходе я был частью,кд-GeRaF.
3. LOPQ что означает локально оптимизированный продукт Квантование, как описано здесь. Он очень похож на новый Бабенко+Лемптицкий подход.

---

вы также можете проверить мои соответствующие ответы:

1. два набора высокомерных точек: найдите ближайшего соседа в другом наборе
2. сравнение времени выполнения запросов ближайших соседей по различным структурам данных
3. PCL KD-tree реализация крайне медленная

косинусное сходство является распространенным способом сравнения векторов высокой размерности. Обратите внимание, что поскольку это сходство, а не расстояние, вы хотите максимизировать его, а не минимизировать. Вы также можете использовать доменный способ сравнения данных, например, если ваши данные были последовательностями ДНК, вы можете использовать сходство последовательностей, которое учитывает вероятности мутаций и т. д.

число ближайших соседей для использования варьируется в зависимости от типа данных, сколько шума и т. д. Там нет общих правил, вы просто должны найти то, что лучше всего работает для ваших конкретных данных и проблемы, пытаясь все значения в диапазоне. Люди интуитивно понимают, что чем больше данных, тем меньше соседей вам нужно. В гипотетической ситуации, когда у вас есть все данные, вам нужно только посмотреть на одного ближайшего соседа для классификации.

метод k ближайших соседей, как известно, является вычислительно дорогим. Это одна из главных причин, почему люди обращаются для других алгоритмов, таких как поддержка векторных машин.

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

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

но кроме того, KD-деревья хорошо работают только с нормами Lp для всех, кого я знаю, и есть эффект концентрации расстояния, который заставляет алгоритмы на основе расстояния ухудшаться с увеличением размерность.

для получения дополнительной информации вы можете прочитать о проклятии размерности и различных его вариантах (есть более одной стороны!)

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

iDistance, вероятно, лучше всего подходит для точного извлечения knn в многомерных данных. Вы можете просмотреть его как приблизительную тессалацию Вороного.

деревья KD отлично работают для 21 измерения, если вы выходите рано, после просмотра скажем 5% от всех точек. ФЛАННА делает это (и другие ускорения) чтобы соответствовать 128-тусклым векторам просеивания. (К сожалению, ФЛАНН делает только евклидову метрику, и быстрый и твердый scipy.пространственный.cKDTree делает только метрики Lp; они могут быть или не быть достаточными для код данные.) Здесь, конечно, есть компромисс между скоростью и точностью.

(если бы вы могли описать ваш Ndata, Nquery, распределение данных , это может помочь людям попробовать аналогичные данные.)

добавлено 26 апреля, время выполнения для cKDTree с отсечкой на моем старом mac ppc, чтобы дать очень приблизительное представление о целесообразности:

kdstats.py p=2 dim=21 N=1000000 nask=1000 nnear=2 cutoff=1000 eps=0 leafsize=10 clustype=uniformp
14 sec to build KDtree of 1000000 points
kdtree: 1000 queries looked at av 0.1 % of the 1000000 points, 0.31 % of 188315 boxes; better 0.0042 0.014 0.1 %
3.5 sec to query 1000 points
distances to 2 nearest: av 0.131  max 0.253

kdstats.py p=2 dim=21 N=1000000 nask=1000 nnear=2 cutoff=5000 eps=0 leafsize=10 clustype=uniformp
14 sec to build KDtree of 1000000 points
kdtree: 1000 queries looked at av 0.48 % of the 1000000 points, 1.1 % of 188315 boxes; better 0.0071 0.026 0.5 %
15 sec to query 1000 points
distances to 2 nearest: av 0.131  max 0.245

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

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

Я испытал ту же проблему и могу сказать следующее.

1. Евклидово расстояние является хорошей метрикой расстояния, однако это вычислительно дороже, чем расстояние Манхэттен, и иногда дает немного более плохие результаты, таким образом, я бы выбрал позже.

2. значение k можно найти эмпирически. Вы можете попробовать разные значения и проверить полученный Roc-кривых или какой-то другой измерение точности / отозвания для того чтобы найти приемлемое значение.

3. Как евклидовы, так и манхэттенские расстояния уважают треугольника неравенство, таким образом, вы можете использовать их в метрических деревьев. Действительно, производительность KD-деревьев сильно ухудшается, когда данные имеют более 10 измерений (я сам испытал эту проблему). Я нашел VP-деревья будет лучшим вариантом.

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

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

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