— Пап, смотри! Это мидия или рапана? Она наполовину в песке, и я не понимаю.
— Тогда давай спросим у её соседей.
— У ракушки есть соседи?
— У чего угодно есть соседи, если правильно нарисовать.
Папа взял палочку и начертил на мокром песке две оси. В рюкзаке у него, как всегда, нашлась рулетка.
— Измеряй всё, что мы сегодня собрали: длину и ширину. А я буду рисовать.
Ракушки на песке
За полчаса на песке появилась картинка, очень похожая на ту, что ты видел в главе 15. По горизонтали — длина ракушки, по вертикали — ширина. Каждая ракушка — одна точка. Мидии папа отмечал кружочками, рапаны — крестиками.
И снова точки не разбросаны как попало. Мидии — длинные и узкие — собрались внизу справа. Рапаны — пошире — вверху слева. Два лагеря, каждый в своём углу.
Числа, которыми мы описываем предмет (здесь — длина и ширина), называются признаками. А подпись «мидия» или «рапана» — это метка, или класс. Задача отнести новый предмет к одному из классов — «мидия или рапана», «спам или нет», «кот или пёс» — называется classification (классификация).
Шесть ракушек — те же, что в программе из рубрики «Под капотом». Попробуй k = 5: ответ изменится.
Теперь новая ракушка. Вероника измеряет её — и на песке появляется знак вопроса. Что дальше? Папа обводит вокруг него круг, чтобы в него попали три ближайшие точки. Две из них — мидии, одна — рапана. Голосование: два против одного. Значит, скорее всего, мидия.
Вот и весь метод. Он называется k-nearest neighbors, kNN (метод k ближайших соседей): найди k ближайших знакомых примеров и посмотри, каких среди них больше. Здесь k = 3.
Сколько соседей спрашивать?
Число k выбираем мы сами, и от него многое зависит. Если k = 1, решает один-единственный ближайший сосед. А вдруг это была ошибка: рапану измерили криво или записали не в тот лагерь? Тогда и ответ будет неверным.
Если же взять k слишком большим — скажем, все сорок ракушек, — голосовать будет весь пляж, и победит класс, которого просто больше. Поэтому k ищут посередине. А когда классов два, берут нечётное k — чтобы голоса не разделились пополам.
— Пап, а метод долго учится?
— Вообще не учится. Он просто помнит все ракушки. И думает, только когда ты приносишь новую.
Это правда. В главе 15 мы «сжимали» все точки в одну линию, а дальше пользовались только ею. kNN ничего не сжимает: он держит в памяти все примеры и каждый раз сравнивает новый с каждым. Для сорока ракушек — пустяк, для миллиарда фотографий — очень медленно.
Метод описали в 1951 году американские статистики Эвелин Фикс и Джозеф Ходжес — в отчёте для школы авиационной медицины ВВС США. Теперь его изучает первым чуть ли не каждый, кто берётся за машинное обучение.
— Значит, мидия, — сказала Вероника и наконец вытащила ракушку из песка. Ракушка была длинная, узкая и тёмная.
— Соседи не соврали, — улыбнулся папа.
— На этот раз. Потому что я их хорошо измерила.
