Ближайшие соседи: чей это цветок?

Уровень курса

← К урокам·Урок 2.2·45 мин

У цветка потерялась этикетка. Рядом есть измерения знакомых ирисов. Можно ли восстановить вид по похожим соседям?

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

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

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

Цветок в исходном файле Длина, см Ширина, см Вид
№ 1 1,4 0,2 setosa
№ 51 4,7 1,4 versicolor
№ 101 6,0 2,5 virginica

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

Ширина лепестка, см 01234567 0123 Длина лепестка, см № 1 · setosa № 51 · versicolor № 101 · virginica
Каждая строка превращается в одну точку. Положение кодирует два измерения; значок показывает известный вид. Масштаб одинаков: один сантиметр по обеим осям занимает одну клетку.

Карта сохраняет только выбранные измерения. Запах, цвет и место, где рос ирис, в этот пример не попали. Два цветка могут оказаться рядом на карте, хотя выглядят по-разному. Сходство всегда относится к тем признакам, которые мы решили сравнивать.

На карте цветов длина лепестка растёт вправо, ширина — вверх. У нового цветка лепесток длиннее, но уже, чем у отмеченного. Куда относительно отмеченной точки поставить новую?

Теперь добавим неизвестный цветок. Найдём ближайшую точку справочника и возьмём её вид как прогноз. Метод ближайшего соседа (nearest neighbor) использует близость как правило: похожие измерения могут означать одинаковый вид.

В простом примере известны только длины: у цветка А лепесток 4 см, у цветка Б — 6 см. У нашего 4,4 см. До А разница 0,4 см, до Б — 1,6 см. Ближе А. Если есть ещё ширина, сравниваем расстояние на плоскости; можно представить линейку между точками. Формула для работы с картой не нужна.

Такое правило иногда ошибается. У ближайшего цветка могли неверно записать вид. Или это редкий экземпляр на границе двух групп. Тогда один неудачный пример определит весь ответ.

Тот же способ на пингвинах

Попробуем перенести правило на настоящие измерения Palmer Penguins. Для маленького справочника специально выберем всего три птицы из полного набора. Сравнивать будем один признак — длину ласта: чем меньше разница в миллиметрах, тем ближе сосед.

№ записи Длина ласта, мм Известный вид
1 181 Adelie — Адели
153 211 Gentoo — папуанский
277 192 Chinstrap — антарктический

У проверочной птицы № 3 ласт длиной 195 мм. Её самой в справочнике нет. Кто ближе: птица с ластом 181, 211 или 192 мм? Назовите прогноз, затем откройте настоящий вид.

Какого пингвина мы узнали?

Разницы равны 14, 16 и 3 мм. Ближе всего запись № 277, поэтому прогноз — Chinstrap. Но в исходном файле проверочная птица № 3 относится к Adelie. Расчёт выполнен правильно, а прогноз ошибочен: виды могут иметь похожие размеры, и наш справочник очень мал. Добавление других измерений и примеров стоит проверить, но оно не обещает безошибочного ответа.

Мы не строили лучший определитель пингвинов: три записи выбраны для разбора одного решения. Полный CSV позволяет проверить измерения и найти другие примеры.

Посмотрим, что произойдёт, если спросить несколько соседей.

Берём три ближайшие точки. Две подписаны versicolor, одна virginica. Каждый цветок получает один голос, поэтому прогноз будет versicolor. Число выбранных соседей принято обозначать буквой k; название k-NN означает «k ближайших соседей». При k = 3 голосуют три цветка, даже если в справочнике их сотня. При равных голосах наш интерактив сообщает «ничья». Если расстояния совпали, раньше выбирается строка с меньшим номером: это заранее принятое правило.

versicolor1 голосversicolor1 голосvirginica1 голосПрогноз: versicolor, 2 голоса из 3
Из трёх ближайших примеров два голосуют за versicolor. Более далёкие точки в этом решении не участвуют.

На карте отмечен придуманный цветок с лепестком 4 × 2,2 см. Вот его ближайшие соседи из справочника в порядке удаления: № 107 — virginica, № 62 — versicolor, № 86 — versicolor, № 52 — versicolor, № 67 — versicolor. Запишите, какой вид победит при одном, трёх и пяти голосующих. На каком из этих переходов сменится лидер?

Кто ближе к вашему цветку?

Выберите число соседей и открывайте их по одному кнопкой «Следующий голос». На карте 120 обучающих ирисов. Ещё 30 отложены для проверки и не голосуют.

Сверить три прогноза

При одном соседе побеждает virginica (1:0). Следующие два голоса за versicolor меняют лидера (2:1). Ещё два голоса укрепляют его преимущество (4:1). Настоящий вид придуманного цветка неизвестен. Проверить правильность прогноза можно будет на цветке № 120, для которого есть метка.

Теперь фильтр ищет соседей для нового SMS. В этом учебном примере пять похожих сообщений уже расположены от ближайшего к самому далёкому. Их метки по порядку: обычное, спам, обычное, спам, спам. Каждый из выбранных соседей даёт один голос. В какую папку фильтр отправит новое SMS при k = 1, затем при k = 3 и при k = 5?

Среди семи ближайших цветков {{n}} относятся к versicolor, остальные к virginica. Сколько голосов получит virginica?

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

Представьте два известных цветка относительно нового. У А длина отличается на 0,2 см, ширина на 0,8 см. У Б длина отличается на 0,5 см, ширина совпадает. На карте в сантиметрах Б ближе: до него 0,5 см, до А больше 0,8 см. Теперь запишем только длину в миллиметрах: различия станут 2 и 5. При прежнем способе считать расстояние ближе окажется А.

В интерактиве выберите цветок № 120, три соседа и вариант «длина в мм, ширина в см». Сравните список соседей с исходным. Оси для удобства остаются в сантиметрах; меняется расчёт расстояния. Поэтому выбранные соседи могут выглядеть дальше на прежней картинке.

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

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

Профи

Как вычислить расстояние

Для двух признаков используем евклидово расстояние: d=(a1−b1)2+(a2−b2)2d=\sqrt{(a_1-b_1)^2+(a_2-b_2)^2}. Буквы aa и bb обозначают два цветка, индексы 1 и 2 — длину и ширину. Для сортировки можно сравнивать квадраты расстояний: квадратный корень сохраняет порядок неотрицательных чисел.

Для А из примера квадрат расстояния равен 0,22+0,82=0,680{,}2^2+0{,}8^2=0{,}68, для Б — 0,52=0,250{,}5^2=0{,}25. После перевода длины: 22+0,82=4,642^2+0{,}8^2=4{,}64 и 52=255^2=25. Порядок поменялся.

Выберите трёх ближайших

Цель: Получите прогноз versicolor по большинству трёх соседей

Вернитесь к интерактиву в шаге 3. Выберите цветок № 120, три соседа и «Обе длины в сантиметрах». Назовите прогноз, проверьте подсчёт голосов и нажмите «Узнать настоящий вид».

Разбор после проверки

В исходном наборе он подписан virginica, а прогноз при этих настройках — versicolor: вот конкретная ошибка. Другие настройки могут исправить её, но это ещё не повод считать их лучшими для всех цветов.

Мы заранее отложили каждую пятую строку исходного файла: 30 цветов из 150. Среди соседей остаются 120. Если разрешить проверочному цветку голосовать за самого себя, он окажется на нулевом расстоянии. При одном соседе получится пересказ известной метки вместо проверки на новом объекте.

Больше соседей тоже не всегда лучше. Если спросить всех, побеждать начнёт самый частый вид справочника независимо от измерений запроса; при равных количествах будет ничья. А если спросить одного, ответ сильнее зависит от случайной точки. Подходящее число соседей выбирают по результатам проверки.

Может ли большинство ошибиться?

Проверим сразу все 30 отложенных цветов. Для каждого посчитаем голоса за выбранный вид. Например, «4/5» означает, что четыре из пяти соседей поддержали прогноз. На графике такие цветы собраны в один столбик; его высота показывает их количество. При одном соседе все решения единогласны. Значит ли это, что все они верны?

Соседи согласны. А ответ верен?

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

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

Эпик

Сколько чужих меток изменят большинство?

Среди семи ближайших соседей пять имеют метку А и два метку Б. Расстояния фиксированы. Какое минимальное число меток нужно заменить, чтобы победил Б? Обобщите для нечётного k и текущего большинства m голосов за А. Докажите минимальность.

Решение

Одна замена А на Б уменьшает отрыв А сразу на два голоса. В примере после одной замены счёт 4:3, после двух 3:4. Минимум две. Для нечётного k нужно оставить у А не более (k−1)/2(k-1)/2 голосов: заменить m−(k−1)/2m-(k-1)/2. Меньшее число оставляет А строго больше половины голосов. Это рассуждение предполагает два класса и неизменный состав соседей; для трёх классов условия победы другие.

Механизм:

найти ближайшие известные примеры и посчитать голоса.

Настройки:

число соседей и масштаб признаков способны изменить решение.

Проверка:

новый цветок не должен подсказывать собственный вид.

Домашняя работа

Источники

  • Palmer Penguins: описание измерений — данные Kristen Gorman и Palmer Station LTER, CC0; справочник из записей 1, 153, 277 и проверочная запись 3 файла penguins.csv.
  • Iris, UCI: источник измерений, описание признаков, CC BY 4.0.
  • IDS Skoltech: прогнозы kNN: источник идеи сравнения голосов с настоящими ответами.
  • Файлы Iris: используется bezdekIris.data, номера строк отсчитываются от 1; длина и ширина лепестка — третий и четвёртый столбцы. Каждая пятая строка исключена из обучения.
  • Методы ближайших соседей, scikit-learn: алгоритм, голосование, выбор расстояния.
  • Cover и Hart, 1967: исследование классификации по ближайшему соседу.

Повторить эту тему