I. Метрика расстояния
Во-первых, количество объектов (столбцов) в наборе данных не является фактором при выборе метрики расстояния для использования в kNN. Есть довольно много опубликованных исследований, направленных именно на этот вопрос, и обычные основы для сравнения:
базовый статистический
распространение ваших данных;
связь между функциями
которые составляют ваши данные (являются ли они
независимый - то есть, что делает
ковариационная матрица выглядит так); и
координатное пространство, из которого ваш
данные получены.
Если у вас нет предварительных знаний о распределении (ях), из которого были взяты ваши данные, по крайней мере одно (хорошо документированное и тщательное) исследование приходит к выводу, что евклидово расстояние - лучший выбор.
Евклидова метрика, используемая в мегамасштабных системах веб-рекомендаций, а также в современных научных исследованиях. Расстояния, рассчитанные евклидовым значением, имеют интуитивное значение, а вычислительные масштабы - т.е. евклидово расстояние вычисляется одинаково, независимо от того, находятся ли эти две точки в двух измерениях или в пространстве двадцати двух измерений.
Это провалилось для меня всего несколько раз, в каждом из этих случаев евклидово расстояние не удавалось, потому что базовая (декартова) система координат была плохим выбором. И вы обычно узнаете это, потому что, например, длины пути (расстояния) больше не являются аддитивными - например, когда метрическое пространство является шахматной доской, манхэттенское расстояние лучше, чем евклидово, аналогично, когда метрическое пространство является Землей, а ваши расстояния транс -континентальные рейсы, метрика расстояния, подходящая для полярной системы координат, является хорошей идеей (например, от Лондона до Вены - 2,5 часа, от Вены до Санкт-Петербурга - еще 3 часа, более или менее в том же направлении, но от Лондона до Санкт-Петербурга Петербург не 5,5 часов, а чуть более 3 часов.
Но кроме тех случаев, когда ваши данные принадлежат не декартовой системе координат, выбор метрики расстояния обычно не является существенным. (Смотрите это сообщение в блоге от студента CS, сравнивая несколько метрик расстояния, изучая их влияние на классификатор kNN - квадраты хи дают лучшие результаты, но различия не велики; более полное исследование находится в академическая статья, Сравнительное исследование функций расстояния для ближайших соседей - Махаланобис (по существу евклидово, нормализованное для учета ковариации измерений) был лучшим в этом исследовании.
Одно важное условие: чтобы расчеты расстояния были значимыми, вы должны изменить масштаб ваших данных - редко можно построить модель kNN для генерации точных прогнозов без делая это. Например, если вы строите модель kNN для прогнозирования спортивных результатов, а вашими переменными ожидания являются рост (см), вес (кг), жировые отложения (%) и пульс покоя (ударов в минуту), тогда типичная точка данных может выглядеть примерно так: [180.4, 66.1, 11.3, 71]. Очевидно, что при расчете расстояния будет доминировать рост, а вклад% жира в организме будет практически незначительным. Иными словами, если вместо этого данные были представлены по-другому, так что вес тела был в граммах, а не в килограммах, тогда исходное значение 86,1 было бы 86,100, что сильно повлияло бы на ваши результаты, а это именно то, что вы делаете. не хочу Вероятно, наиболее распространенным методом масштабирования является вычитание среднего значения и деление на стандартное отклонение (среднее значение и относительное значение sd рассчитываются отдельно для каждого столбца или функции в этом наборе данных; X относится к отдельной записи / ячейке в строке данных):
X_new = (X_old - mu) / sigma
II. Структура данных
Если вас беспокоит производительность структуры дерева kd, A Тесселяция Вороного является концептуально простым контейнером, но он значительно улучшит производительность и масштабируется лучше, чем kd-Trees.
Это не самый распространенный способ сохранения данных обучения kNN, хотя применение VT для этой цели, а также вытекающие из этого преимущества производительности хорошо документированы (см., Например, Отчет Microsoft Research ). Практическая значимость этого заключается в том, что, если вы используете «основной» язык (например, в TIOBE Index ), то вы должны найти библиотеку для выполнения VT. Я знаю, что в Python и R есть несколько вариантов для каждого языка (например, пакет voronoi для R доступен на CRAN )
Использование VT для kNN работает так:
Из ваших данных случайным образом выберите w точек - это ваши центры Вороного. Ячейка Вороного охватывает все соседние точки, которые являются ближайшими к каждому центру. Представьте, что вы назначаете разные цвета для каждого из центров Вороного, чтобы каждая точка, назначенная данному центру, окрашивалась в этот цвет. Пока у вас есть достаточная плотность, выполнение этого будет хорошо показывать границы каждого центра Вороного (как границы, которые разделяют два цвета.
Как выбрать центры Вороного? Я использую два ортогональных руководства. После случайного выбора точек w, рассчитайте VT для ваших тренировочных данных. Затем проверьте количество точек данных, назначенных каждому центру Вороного - эти значения должны быть примерно одинаковыми (с учетом равномерной плотности точек по всему пространству данных). В двух измерениях это приведет к VT с тайлами одинакового размера. Это первое правило, вот второе. Выберите w с помощью итерации - запустите алгоритм kNN с параметром w в качестве переменного параметра и измерьте производительность (время, необходимое для возврата прогноза путем запроса VT).
Итак, представьте, что у вас есть миллион точек данных ..... Если бы точки были сохранены в обычной 2D-структуре данных или в kd-дереве, вы бы выполнили в среднем пару миллионов вычислений расстояния для каждой новые точки данных, чью переменную ответа вы хотите предсказать. Конечно, эти расчеты выполняются на одном наборе данных. С помощью V / T поиск ближайшего соседа выполняется в два этапа один за другим по двум различным группам данных - сначала по центрам Вороного, затем, как только ближайший центр найден, точки внутри ячейки, соответствующие этот центр ищется, чтобы найти фактического ближайшего соседа (путем последовательных вычислений расстояния). В совокупности эти два поиска выполняются намного быстрее, чем один поиск методом "грубой силы". Это легко увидеть: предположим, что для 1М точек данных вы выбираете 250 центров Вороного, чтобы тесселяровать пространство данных. В среднем каждая ячейка Вороного будет иметь 4000 точек данных. Таким образом, вместо выполнения в среднем 500 000 вычислений расстояния (грубой силы), вы выполняете намного меньше, в среднем всего 125 + 2000.
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), или обратное расстояние от этого соседа до тестового экземпляра, часто умноженное на некоторую эмпирически выведенную константу,К. Я не фанат этой техники, потому что она часто перевешивает ближайших соседей (и, соответственно, перевешивает более отдаленных);значение этого в том, что данный прогноз может почти полностью зависеть от одного соседа, что, в свою очередь, увеличивает чувствительность алгоритма к шуму.
Должна лучше взвешивать функцию, которая существенно избегает этого ограничения. Гауссовская функция , которая в python выглядит следующим образом:
def weight_gauss(dist, sig=2.0) :
return math.e**(-dist**2/(2*sig**2))
Чтобы вычислить прогнозируемое значение, используя ваш код kNN, вы должны определить n ближайших соседей к даннымУкажите точку, ответную переменную которой вы хотите предсказать («тестовый экземпляр»), затем вызовите функцию weight_gauss, один раз для каждого из n соседей, передавая расстояние между каждым соседом контрольной точки. Эта функция будет возвращать вес для каждого соседа, который затем используется в качестве коэффициента этого соседа в средневзвешенном расчете.