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

Ответ 1

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

Вам может быть интересен алгоритм Приблизительный ближайший соседний (ANN). Идея заключается в том, что вы позволяете алгоритму возвращать достаточно близкие соседи (возможно, не к ближайшему соседу); при этом вы уменьшаете сложность. Вы упомянули kd-дерево; это один из примеров. Но, как вы сказали, kd-tree работает плохо в высоких размерах. Фактически, все современные методы индексирования (основанные на пространственном разделении) делятся на линейный поиск достаточно больших размеров [1] [2] [3].

Среди недавно предложенных алгоритмов ANN, возможно, наиболее популярным является Локально-Чувствительное Хеширование (LSH), которое отображает набор точек в высокоразмерное пространство в множество ящиков, т.е. хэш-таблицу [1] [3]. Но в отличие от традиционных хэшей чувствительный к местности хэш помещает соседние точки в один и тот же ящик.

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

Во-вторых, существует строгая теория, которая поддерживает ее производительность. Можно показать, что время запроса сублинейно в размере базы данных, то есть быстрее, чем линейный поиск. Насколько быстрее зависит от того, сколько аппроксимаций мы можем терпеть.

Наконец, LSH совместим с любой нормой Lp для 0 < p <= 2. Поэтому, чтобы ответить на ваш первый вопрос, вы можете использовать LSH с евклидовой метрикой расстояния, или вы можете использовать ее с метрикой расстояния Манхэттена (L1). Существуют также варианты для расстояния Хэмминга и косинуса.

Достойный обзор был написан Малкольмом Слейни и Майклом Кейси для журнала обработки сигналов IEEE в 2008 году [4].

LSH применяется, казалось бы, везде. Вы можете попробовать.

[1] Datar, Indyk, Immorlica, Mirrokni, "Локально-чувствительная схема хеширования на основе p-стабильных распределений", 2004 г.

[2] Вебер, Шек, Блотт, "Количественный анализ и исследование эффективности методов поиска сходства в высокоразмерных пространствах", 1998.

[3] Gionis, Indyk, Motwani, "Поиск подобия в высоких измерениях с помощью хэширования", 1999.

[4] Слейни, Кейси, "Чувствительное к местоположению хэширование для поиска ближайших соседей", 2008 г.

Ответ 2

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

Во-первых, количество функций (столбцов) в наборе данных не является фактором при выборе метрики расстояния для использования в kNN. Есть довольно много опубликованных исследований, направленных именно на этот вопрос, и обычные основы для сравнения:

• лежащая в основе статистика распространение ваших данных;

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

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

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

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

X_new = (X_old - mu) / sigma

II. Структура данных

Если вас беспокоит производительность структуры kd-дерева, A Voronoi Tessellation представляет собой концептуально простой контейнер, но это значительно улучшит производительность и масштабирует лучше, чем kd-деревья.
< бр /" >

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

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

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

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

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

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

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

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

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

Самый простой метод взвешивания - это просто умножение каждого соседа на весовой коэффициент, который равен только 1/(dist * K), или наоборот от расстояния от этого соседа до тестового экземпляра, часто умножаемого на некоторую эмпирически полученную константу, К. Я не поклонник этой техники, потому что она часто превосходит ближайших соседей (и одновременно под весом более отдаленных); значимость этого заключается в том, что данное предсказание может быть почти полностью зависимо от одного соседа, что, в свою очередь, увеличивает чувствительность алгоритма к шуму.

A должна лучше взвешивать функцию, которая, по существу, избегает этого ограничения, это gaussian function, которая в python выглядит следующим образом:

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

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

Ответ 3

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

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

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

Ответ 4

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

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

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

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

Ответ 5

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

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

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

• Современные подходы LSH, такие как Razenshteyn.
• Лес RKD: Лес рандомизированных kd деревьев (RKD), как описано в FLANN, или в более недавнем подходе я был частью kd-GeRaF.
• LOPQ, который обозначает локально оптимизированное квантование продукта, как описано здесь. Он очень похож на новый подход Babenko + Lemptitsky .

Вы также можете проверить мои ответы:

• Два набора точек с высокой точностью: найдите ближайшего соседа в другом наборе
• Сравнение времени выполнения запросов Nearest Neighbor в разных структурах данных
• Реализация PCL kd-tree чрезвычайно медленная

Ответ 6

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

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

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

Ответ 7

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

Ответ 8

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

Ответ 9

KD Деревья отлично работают на 21 размер, если вы рано уходите, после просмотра 5% всех очков. FLANN делает это (и другие ускорения) для соответствия 128-мерным SIFT-векторам. (К сожалению, FLANN делает только евклидову метрику, и быстрый и надежный scipy.spatial.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

Ответ 10

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

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

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

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

Ответ 11

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

Ответ 12

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

Ответ 13

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

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

• Значение k можно найти эмпирически. Вы можете попробовать разные значения и проверить полученные кривые ROC или некоторые другие меры прецизионности/повтора, чтобы найти приемлемое значение.

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

Ответ 14

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

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

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