ML Данные и машинное обучение Алгоритм
k ближайших соседей
Также: k-nearest neighbours · k-NN · kNN · метод ближайшего соседа · nearest neighbour classifier
Какой это район Алматы, если карты границ нет, а у соседних перекрёстков район подписан? Спросить k ближайших и взять ответ большинства. Самый простой метод машинного обучения: он ничего не учит, а только помнит. Почему он работает, сколько соседей спрашивать и почему в пространстве из сотни признаков соседей не остаётся.
Вы стоите на перекрёстке в Алматы и хотите знать, в каком вы районе. Если есть карта с границами районов, это задача о точке в многоугольнике. А если карты нет, зато про тысячи других перекрёстков известно, к какому району они относятся? Тогда можно спросить у соседей: найти k ближайших перекрёстков с известным районом и поверить большинству. Ниже — настоящие 7445 перекрёстков центра города. Про половину район «известен», вторая половина — экзамен, на котором видно, где голосование ошибается.
Заливка — что ответили бы соседи в каждой точке карты, чёрные линии — настоящие границы. При пяти соседях и 3722 известных перекрёстках голосование право на 97,5 % экзамена, и все его ошибки — кольца — жмутся к границам: там соседи и правда из разных районов. Теперь нажмите «испортить 20 % подписей»: каждому пятому известному перекрёстку достаётся случайный район. С k = 1 карта покрывается пятнами, а с k = 9 почти не меняется. А при k = 51 исчезает маленький Наурызбайский район на юго-западе карты: из двадцати его перекрёстков на экзамене соседи не узнали ни одного.
Идея
Близкие примеры, скорее всего, относятся к одному классу. Чтобы ответить на вопрос о новой точке, найдите k самых близких к ней известных примеров и выберите ответ, который среди них встречается чаще всех.
Обучения в обычном смысле здесь нет: метод только запоминает примеры, а вся работа происходит в момент вопроса. Поэтому его называют ленивым. Три решения, которые надо принять, — что считать расстоянием, сколько брать соседей и как разбивать ничьи. Здесь расстояние — обычное, по прямой на карте; соседей с равным расстоянием упорядочиваем по номеру, а при равенстве голосов побеждает метка самого близкого из претендентов. Без таких правил один и тот же метод на одних данных может отвечать по-разному.
Вот как ответ зависит от k на семи перекрёстках, отсортированных по удалённости от точки вопроса: ближайший — Медеуский, следующие два — Алмалинские, дальше снова Медеуский и три Бостандыкских.
k = 1: Medeu 1 -> Medeu k = 2: Almaly 1, Medeu 1 -> Medeu k = 3: Almaly 2, Medeu 1 -> Almaly k = 4: Almaly 2, Medeu 2 -> Medeu k = 5: Almaly 2, Bostandyk 1, Medeu 2 -> Medeu k = 6: Almaly 2, Bostandyk 2, Medeu 2 -> Medeu k = 7: Almaly 2, Bostandyk 3, Medeu 2 -> Bostandyk
При k = 2 и k = 4 голоса делятся поровну, и решает ближайший. Поэтому для двух классов k часто берут нечётным — тогда ничьих не бывает.
Почему это работает
Насколько хорош такой простой метод? Есть точный ответ для случая, когда примеров очень много.
Пусть известных примеров становится всё больше, а вероятность каждого класса плавно зависит от положения точки. Тогда ошибка правила одного ближайшего соседа стремится к числу, которое не больше удвоенной ошибки наилучшего возможного правила.
Набросок для двух классов. Пусть в точке x класс 1 встречается с вероятностью p, класс 0 — с вероятностью 1 − p. Наилучшее правило, которое знает p, отвечает самым вероятным классом и ошибается с вероятностью min(p, 1 − p). Когда примеров много, ближайший сосед лежит почти в самой точке x, и его класс — независимый жребий с той же вероятностью p. Ошибка — когда жребии разошлись: p(1 − p) + (1 − p)p = 2p(1 − p). А это не больше 2·min(p, 1 − p), потому что второй множитель, max(p, 1 − p), не больше единицы. Усреднив по всем точкам, получаем то же неравенство для полной ошибки.
В бесконечно большой выборке, говорят Ковер и Харт, половина всей информации о классе точки содержится в её ближайшем соседе. Если же брать не одного соседа, а k, и растить k вместе с числом примеров, но медленнее (k → ∞, k/n → 0), ошибка стремится к наилучшей возможной — это доказал Чарльз Стоун в 1977 году.
Обе теоремы говорят о бесконечно большом числе примеров. На конечных данных — а других не бывает — всё решает, сколько соседей брать и что считать близостью.
Сколько соседей спрашивать
Листинг ниже повторяет опыт сцены: делит перекрёстки пополам одним и тем же генератором, голосует при разных k и считает долю верных ответов на экзамене — с честными подписями и с испорченными:
k clean labels 20% spoiled 1 98.3% 82.0% 3 97.6% 91.6% 5 97.5% 96.2% 9 97.5% 97.4% 15 97.2% 97.3% 25 96.9% 97.1% 51 95.5% 95.9%
С честными подписями лучше всех один сосед: районы — сплошные куски города, и ближайший перекрёсток почти всегда в том же районе, что и вы. Каждый лишний сосед только добавляет шанс, что голосовать придут жители соседнего района. С испорченными подписями всё наоборот: один сосед повторяет за случайной ошибкой, и из каждых пяти ответов один неверный. Девять соседей перекрикивают одну-две ошибки, и точность почти та же, что без порчи.
А слишком много соседей вредит в обоих случаях. Голосование размывает границы, и хуже всего маленьким районам: у Наурызбайского района на этой карте всего 41 перекрёсток, и при k = 51 его жителей перекрикивают соседи.
Nauryzbay, the smallest district here: 20 exam crossroads, right at k = 1: 18, right at k = 9: 18, right at k = 51: 0
Это общий закон машинного обучения в самом наглядном виде. Маленькое k слишком доверяет каждому примеру вместе с его случайными ошибками, большое k огрубляет картину и теряет мелкие детали; лучшее — где-то посередине, и где именно, зависит от данных. Поэтому k не угадывают, а проверяют: откладывают часть известных примеров и смотрят, какое k отвечает на них лучше, или по очереди убирают каждый пример и спрашивают о нём остальных. Второй способ — во второй задаче статьи.
Код
Сам метод — десяток строк. Ближайших выбирает heapq.nsmallest: куча из k элементов, без сортировки всех расстояний.
Опыт с Алматы: 7445 перекрёстков с районами — тех, что лежат внутри границ районов из OpenStreetMap, — перемешаны и поделены пополам. На Python расстояния до всех известных перекрёстков считает NumPy сразу пачками по пятьсот вопросов; на Go — обычный цикл, который держит k лучших в коротком упорядоченном списке.
Сколько это стоит
Запомнить примеры — O(n·d) памяти и никакой работы. Зато каждый вопрос в простейшем виде сравнивает точку со всеми n примерами, по O(d) на сравнение, и выбирает k лучших: кучей это O(n log k), а алгоритмом быстрого выбора — O(n) в среднем. В сцене это 3722 расстояния на каждый вопрос и почти пятнадцать миллионов на один экзамен.
Ускорить вопрос можно, если не смотреть на далёкие точки вовсе. При малом числе признаков это делает k-d дерево: в статье о нём ближайший из 45 тысяч городов мира находится за пару десятков сравнений. Но в сотнях измерений дерево перестаёт отсекать, и там ищут уже не точных соседей, а «достаточно близких» — графами вроде HNSW, хешированием, похожим на MinHash и LSH. Так устроен векторный поиск, которым находят похожие тексты и картинки.
Проклятие размерности
Всё сказанное держится на том, что «близко» значит «похоже». В пространстве из многих признаков это перестаёт быть правдой. Проверим на тех же перекрёстках: к двум настоящим координатам добавим признаки, которые ничего не говорят о районе, — случайные числа того же размаха, что и город.
useless features right (k = 5) nearest/farthest
0 96.4% 0.011
1 87.6% 0.041
2 83.6% 0.079
5 65.4% 0.186
10 52.0% 0.308
20 36.4% 0.440
50 28.6% 0.602
100 26.0% 0.700
Два настоящих признака тонут в шуме. Одного случайного признака хватает, чтобы ошибок стало втрое больше, при десяти голосование угадывает лишь половину, при сотне — немногим лучше, чем если всегда называть самый большой район. Правый столбец объясняет, почему: отношение расстояний до ближайшего и до самого дальнего из тысячи известных. В двух измерениях ближайший в сто раз ближе дальнего, в ста двух — лишь на треть. Когда все примеры почти одинаково далеки, слово «ближайший» теряет смысл.
Это и есть проклятие размерности. Чтобы примеры лежали так же плотно, как на плоскости, их в многомерном пространстве нужно экспоненциально больше, а случайные расстояния складываются из множества слагаемых и потому почти одинаковы.
Но настоящие данные — не случайные точки. Рукописные цифры из открытого набора UCI — это 256 пикселей, и всё же соседи у них есть: базовый курс в главе о машинном обучении угадывает цифры голосованием соседей примерно в 98 % случаев. Листинг сравнивает три облака по 256 чисел:
digits nearest/farthest 0.346 pixels shuffled between digits nearest/farthest 0.752 random pixels nearest/farthest 0.803
Во втором облаке те же пиксели, только перемешанные между цифрами: в каждой точке картинки та же доля чернил, но штрихи больше не складываются в цифры. И расстояния сразу выравниваются почти как у случайного шума. Цифры занимают в своём пространстве узкую область: восьмёрку можно наклонить, утолщить, сдвинуть, но вариантов куда меньше, чем картинок из 256 пикселей. Соседи работают ровно настолько, насколько признаки отражают эту структуру. Отсюда практические правила: выбрасывать признаки, которые ничего не говорят о задаче, и приводить остальные к одному масштабу — иначе признак, измеренный в метрах, перекричит признак, измеренный в штуках.
История
Правило ближайшего соседа предложили Эвелин Фикс и Джозеф Ходжес в 1951 году, в техническом отчёте о правилах различения. Они показали, что при росте числа примеров такие правила различения приближаются к наилучшему. Сам отчёт напечатали в журнале только в 1989 году, вместе с комментарием о его месте в истории статистики. Оценку «не хуже вдвое» из раздела о том, почему метод работает, доказали Томас Ковер и Питер Харт в 1967 году в статье «Классификация по ближайшему соседу».
Задачи
Первая задача — метод со всеми правилами ничьих на настоящих перекрёстках. Во второй нужно выбрать k для землетрясений: спросить о каждом все остальные — дорого, если для каждого k начинать заново.
Район по соседям Сколько соседей спросить о глубинеДанные: Границы районов Алматы © участники OpenStreetMap, ODbL Дороги Алматы © участники OpenStreetMap, ODbL Рукописные цифры: E. Alpaydin, C. Kaynak, UCI ML Repository, CC BY 4.0 Землетрясения: каталог USGS, общественное достояние