На столе лежит ирис без этикетки. В справочнике есть измерения других цветов и названия их видов. Самое доступное решение: измерить неизвестный цветок и поискать похожие записи. Если у похожего цветка подписан вид, можно предположить такой же у нашего.
Звучит разумно, пока два похожих цветка не оказываются разных видов. Кому верить? Разберём способ, который позволяет проследить каждый голос. Для этого достаточно читать таблицу, сравнивать длины и считать до пяти. Все вычисления на карте выполнит интерактив.
Возьмём два признака: длину лепестка и его ширину. Это две измеримые характеристики одного цветка. В таблице каждая строка описывает отдельный экземпляр. Последний столбец хранит известный вид: эти подписи понадобятся для голосования. У проверочного цветка вид сначала скроем, а после прогноза откроем для сравнения.
| Цветок в исходном файле | Длина, см | Ширина, см | Вид |
|---|---|---|---|
| № 1 | 1,4 | 0,2 | setosa |
| № 51 | 4,7 | 1,4 | versicolor |
| № 101 | 6,0 | 2,5 | 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 голосуют три цветка, даже если в справочнике их сотня. При равных голосах наш интерактив сообщает «ничья». Если расстояния совпали, раньше выбирается строка с меньшим номером: это заранее принятое правило.
Перед экспериментом предположите: обязательно ли пять соседей выберут тот же вид, что один? На карте уже стоит учебная точка: длина 4 см, ширина 2,2 см. Сначала посмотрите на ближайшего, назовите вид и проверьте подсчёт. Затем выберите пять соседей. Кнопка «Следующий голос» позволяет открывать их по одному; рядом меняются счёт и текущий лидер.
Один сосед выбирает virginica, пять выбирают versicolor. Первую точку мы придумали, поэтому правильный вид неизвестен: здесь наблюдаем смену решения. Цветок № 120 ниже позволит проверить прогноз по настоящей метке.
Цветок не меняется, когда длину записывают в миллиметрах. Но число становится в десять раз больше. Если программа сравнивает эти числа как раньше, различия в длине начинают сильнее влиять на выбор соседей.
Представьте два известных цветка относительно нового. У А длина отличается на 0,2 см, ширина на 0,8 см. У Б длина отличается на 0,5 см, ширина совпадает. На карте в сантиметрах Б ближе: до него 0,5 см, до А больше 0,8 см. Теперь запишем только длину в миллиметрах: различия станут 2 и 5. При прежнем способе считать расстояние ближе окажется А.
В интерактиве выберите цветок № 120, три соседа и вариант «длина в мм, ширина в см». Сравните список соседей с исходным. Оси для удобства остаются в сантиметрах; меняется расчёт расстояния. Поэтому выбранные соседи могут выглядеть дальше на прежней картинке.
Масштаб нужно выбрать осмысленно. Часто признаки приводят к сопоставимым диапазонам по обучающим данным. Подходящий способ проверяют на отдельных примерах; универсального масштаба для любых задач нет.
Как вычислить расстояние
Для двух признаков используем евклидово расстояние: 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. Порядок поменялся.
Цель: Получите прогноз versicolor по большинству трёх соседей
Отсортируйте строки по расстоянию, затем возьмите первые три.
Вернитесь к интерактиву в шаге 3. Выберите цветок № 120, три соседа и «Обе длины в сантиметрах». Назовите прогноз, проверьте подсчёт голосов и нажмите «Узнать настоящий вид».
Разбор после проверки
В исходном наборе он подписан virginica, а прогноз при этих настройках — versicolor: вот конкретная ошибка. Другие настройки могут исправить её, но это ещё не повод считать их лучшими для всех цветов.
Мы заранее отложили каждую пятую строку исходного файла: 30 цветов из 150. Среди соседей остаются 120. Если разрешить проверочному цветку голосовать за самого себя, он окажется на нулевом расстоянии. При одном соседе получится пересказ известной метки вместо проверки на новом объекте.
Больше соседей тоже не всегда лучше. Если спросить всех, побеждать начнёт самый частый вид справочника независимо от измерений запроса; при равных количествах будет ничья. А если спросить одного, ответ сильнее зависит от случайной точки. Подходящее число соседей выбирают по результатам проверки.
Может ли большинство ошибиться?
Проверим сразу все 30 отложенных цветов. Для каждого посчитаем голоса за выбранный вид. Например, «4/5» означает, что четыре из пяти соседей поддержали прогноз. На графике такие цветы собраны в один столбик; его высота показывает их количество. При одном соседе все решения единогласны. Значит ли это, что все они верны?
Сколько чужих меток изменят большинство?
Среди семи ближайших соседей пять имеют метку А и два метку Б. Расстояния фиксированы. Какое минимальное число меток нужно заменить, чтобы победил Б? Обобщите для нечётного k и текущего большинства m голосов за А. Докажите минимальность.
Решение
Одна замена А на Б уменьшает отрыв А сразу на два голоса. В примере после одной замены счёт 4:3, после двух 3:4. Минимум две. Для нечётного k нужно оставить у А не более (k-1)/2 голосов: заменить m-(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: исследование классификации по ближайшему соседу.