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

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

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

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

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

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

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

Как цветок становится точкой

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

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

Как цветок становится точкой

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

Как цветок становится точкой

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

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

Как цветок становится точкой

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

Как цветок становится точкой

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

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

Обсудим

Как цветок становится точкой

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

  1. Влево и вверх
  2. Вправо и вниз
  3. Вправо и вверх
  4. В то же место: вид ещё неизвестен
Ближайшие соседи: чей это цветок?8

Один сосед даёт один ответ

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

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

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

Пояснение

Один сосед даёт один ответ

Известные примеры называют обучающими. У этого метода обучение в простейшем варианте означает сохранить их признаки вместе с видами. При новом запросе он заново ищет соседей.

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

Один сосед даёт один ответ

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

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

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

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

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

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

№ записи Длина ласта, мм Известный вид
1 181 Adelie — Адели
153 211 Gentoo — папуанский
277 192 Chinstrap — антарктический
Ближайшие соседи: чей это цветок?13

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

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

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

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

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

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

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

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

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

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

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

Дадим соседям проголосовать

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

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

Дадим соседям проголосовать

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

Дадим соседям проголосовать

Перед экспериментом предположите: обязательно ли пять соседей выберут тот же вид, что один? На карте уже стоит учебная точка: длина 4 см, ширина 2,2 см. Сначала посмотрите на ближайшего, назовите вид и проверьте подсчёт. Затем выберите пять соседей. Кнопка «Следующий голос» позволяет открывать их по одному; рядом меняются счёт и текущий лидер.

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

Один сосед: первый прогноз

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

Кто ближе к вашему цветку?
Ближайшие соседи: чей это цветок?20

Пять соседей: большинство меняет прогноз

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

Кто ближе к вашему цветку?
Ближайшие соседи: чей это цветок?21

Цветок № 120: три соседа, обе длины в сантиметрах

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

Кто ближе к вашему цветку?
Ближайшие соседи: чей это цветок?22

Тот же цветок: длина в миллиметрах, ширина в сантиметрах

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

Кто ближе к вашему цветку?
Ближайшие соседи: чей это цветок?23

Эксперимент

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

Начните с одного соседа, затем выберите пять. Двигайте измерения ползунками. Для проверки масштаба установите цветок № 120 и три соседа; сравните оба варианта единиц. Карта содержит 120 обучающих ирисов; 30 отложены и не голосуют.
Ближайшие соседи: чей это цветок?24

Дадим соседям проголосовать

Один сосед выбирает virginica, пять выбирают versicolor. Первую точку мы придумали, поэтому правильный вид неизвестен: здесь наблюдаем смену решения. Цветок № 120 ниже позволит проверить прогноз по настоящей метке.

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

Обсудим

Дадим соседям проголосовать

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

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

Почему миллиметры меняют ответ

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

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

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

Вопрос для обсуждения

Почему миллиметры меняют ответ

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

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

Почему миллиметры меняют ответ

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

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

Обсудим

Почему миллиметры меняют ответ

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

  1. У цветка изменился настоящий вид
  2. Стало больше обучающих цветов
  3. Различия по этой оси получили больший вес
  4. Миллиметры всегда точнее сантиметров
Ближайшие соседи: чей это цветок?30

Почему миллиметры меняют ответ

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

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

Профи

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

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

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

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

Профи · Python

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

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

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

Экзамен на незнакомом цветке

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

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

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

Экзамен на незнакомом цветке

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

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

Экзамен на незнакомом цветке

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

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

Экзамен на незнакомом цветке

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

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

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

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

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

Один голос: все решения единогласны

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

Соседи согласны. А ответ верен?
Ближайшие соседи: чей это цветок?39

Пять голосов: большинство тоже может ошибиться

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

Соседи согласны. А ответ верен?
Ближайшие соседи: чей это цветок?40

Эксперимент

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

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

Обсудим

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

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

  1. Достаточно ли яркие цвета на карте
  2. Не выбирает ли каждый цветок самого себя
  3. Не слишком ли короткие названия видов
  4. Все ли измерения записаны целыми числами
Ближайшие соседи: чей это цветок?42

Эпик

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

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

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

Эпик · Решение

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

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

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

Следующий способ

Дерево решений задаёт последовательность вопросов о признаках. Вместо списка соседей мы сможем проследить путь от первого вопроса до ответа.

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

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

  • Механизм: найти ближайшие известные примеры и посчитать голоса.
  • Настройки: число соседей и масштаб признаков способны изменить решение.
  • Проверка: новый цветок не должен подсказывать собственный вид.
Ближайшие соседи: чей это цветок?46

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

  • Для новой учебной точки с длиной лепестка 4 см и шириной 2,2 см сравните прогнозы по одному и пяти ближайшим соседям. В таблице даны пять ближайших известных цветов, от самого близкого к самому дальнему. Каждый выбранный сосед даёт один голос за свой вид. Запишите голоса и объясните смену решения.
Ближайшие соседи: чей это цветок?47

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

№Длина, смШирина, смВид
1074,51,7virginica
624,21,5versicolor
864,51,6versicolor
524,51,5versicolor
674,51,5versicolor
Ближайшие соседи: чей это цветок?48

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

  • Цветок № 120: длина лепестка 5 см, ширина 1,5 см. При сантиметрах по обеим осям выбраны соседи № 53, 73, 134. Если длину перевести в миллиметры, оставив ширину в сантиметрах, выбраны № 78, 147, 114. По таблице сравните прогнозы трёх соседей и объясните изменение.
Ближайшие соседи: чей это цветок?49

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

№Длина, смШирина, смВид
534,91,5versicolor
734,91,5versicolor
1345,11,5virginica
7851,7versicolor
14751,9virginica
11452virginica
Ближайшие соседи: чей это цветок?50

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

  • Со звёздочкой: придумайте пять известных точек двух классов и одну новую так, чтобы прогноз менялся при переходе от одного соседа к трём.
Ближайшие соседи: чей это цветок?51

Источники

  • 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; длина и ширина лепестка — третий и четвёртый столбцы. Каждая пятая строка исключена из обучения.