Верховный алгоритм

Как поведал Стивен Джонсон в книге The Ghost Map, алгоритм ближайшего соседа может спасать жизни. В 1854 году Лондон поразила вспышка холеры. В некоторых частях города от нее умер каждый восьмой житель. Господствовавшая тогда теория, что холера вызвана якобы плохим воздухом, не помогла предотвратить распространение эпидемии. Но Джон Сноу, физик, скептически относившийся к этой теории, придумал кое-что получше. Он отметил на карте Лондона все известные случаи холеры и разделил карту на области, расположенные ближе всего к общественным водокачкам. Эврика! Оказалось, что почти все смерти приходились на «агломерацию» конкретного водозабора, расположенного на Брод-стрит в районе Сохо. Сделав вывод, что вода там заражена, Сноу убедил местные власти выключить насос, и эпидемия сошла на нет. Из этого случая родилась эпидемиология, а еще это пример первого успешного применения алгоритма ближайшего соседа — почти за столетие до его официального открытия.

В алгоритме ближайшего соседа каждая точка данных — это маленький классификатор, предсказывающий класс для всех примеров запросов, на которые она правильно отвечает. Это как армия муравьев: отдельные солдаты сами по себе делают немного, но вместе способны сдвигать горы. Если груз слишком тяжел для одного муравья, он зовет соседей. Метод k-ближайших соседей действует в том же духе: тестовый пример классифицируется путем нахождения k-ближайших соседей, которые после этого голосуют. Если ближайшее изображение к только что загруженному — это лицо, но следующие два ближайших — нет, третий ближайший сосед решает, что загруженная картинка все же не лицо. Алгоритм ближайшего соседа подвержен переобучению: если точке данных присвоен неправильный класс, он распространится на всю свою агломерацию. Алгоритм k-ближайших соседей более устойчив, потому что ошибается только тогда, когда большинство из k-ближайших соседей зашумлены. Но за это приходится платить более замутненным зрением: из-за голосования размываются мелкие детали границы. Когда k идет вверх, дисперсия уменьшается, но увеличивается смещенность.

Брать k-ближайших соседей вместо одного — это еще не все. Интуиция подсказывает, что примеры, ближе всего расположенные к тесто­вому, должны быть важнее. Это ведет нас к взвешенному алго­ритму k-ближайших соседей. В 1994 году группа ученых из Миннесот­ского университета и Массачусетского технологического института построила рекомендательную систему на основе, по их словам, «обманчиво простой идеи»: люди, которые соглашались на что-то в прошлом, с большей вероятностью согласятся на это и в будущем. Эта мысль вела прямиком к системам коллаборативной фильтрации, которые имеются на всех уважающих себя сайтах электронной торговли. Представьте, что вы, как Netflix, собрали базу данных, где каждый пользователь присваивает просмотренным фильмам рейтинг от одной до пяти звезд. Вы хотите определить, понравится ли вашему пользователю по имени Кен фильм «Гравитация», поэтому ищете пользователей, оценки которых лучше всего коррелируют с оценками Кена. Если все они присвоили «Гравитации» высокий рейтинг, вероятно, так поступит и Кен, и этот фильм можно ему посоветовать. Если, однако, у них нет единого мнения в отношении «Гравитации», все равно нужно как-то выйти из положения, и в данном случае пригодится список пользователей, упорядоченный по их корреляции с Кеном. Если Ли коррелирует с Кеном сильнее, чем Мег, его оценки должны считаться, соответственно, более важными. Спрогнозированная оценка Кена будет таким образом средней взвешенной оценок его соседей, где вес каждого соседа — это его коэффициент корреляции с Кеном.

Однако есть интересный момент. Представьте, что у Ли и Кена очень схожие вкусы, но, когда Кен дает фильму пять звездочек, Ли всегда выставляет три, когда Кен дает три, Ли — только одну и так далее. Нам хотелось бы использовать оценки Ли для прогнозирования оценок Кена, но, если сделать это «в лоб», мы всегда будем отклоняться на две звездочки. Вместо этого нужно предсказать, насколько рейтинги Кена будут выше или ниже его средней, основываясь на таком же показателе для Ли. Теперь видно, что Кен всегда на две звездочки выше своей средней, когда Ли на две звездочки выше своей, и наш прогноз будет попадать в точку.

Кстати говоря, для коллаборативной фильтрации явные оценки не обязательны. Если Кен заказал фильм на Netflix, это значит, что он ожидает, что фильм ему понравится. Так что «оценкой» может быть просто «заказал / не заказал», и два пользователя будут похожи, если они заказывают много одинаковых фильмов. Даже простой клик на что-то косвенно показывает интерес пользователя. Алгоритм ближайшего соседа работает во всех этих случаях. Сегодня для того, чтобы давать рекомендации посетителям сайта, используются все виды алгоритмов, но взвешенный k-ближайший сосед был первым, нашедшим широкое применение в этой области, и его до сих пор сложно победить.