Грокаем а Иллюстрированное пособие для программистов и любопытствующих

МАЛЫМ


БОЛЬШОМ


ой мыслительный процесс выглядит примерно так: у меня в мозге суще­ствует некое подобие графика.
А=М1ЕЛЬС.ИН
Г=ГРЕМПФРУТ
К
ЗАГАДОЧНЫМ
ФРУКТ
3
МАЛЫМ
■ БОЛЬШОМ

ак правило, крупные и красные фрукты оказываются грейпфрутами. Этот фрукт большой и красный, поэтому, скорее всего, это грейпфрут. Но что, если вам попадется фрукт вроде такого?
К
2
О


ul
со
ГГ


Г
Г
Г
Г Г


Г
г


/


LU
*


РАЗМЕР


■»

ак классифицировать этот фрукт? Один из способов — рассмотреть со­седей этой точки. Возьмем ее трех ближайших соседей.
МАЛЫ* ■ ■ ■ БОЛЬШОЙ
Среди соседей больше апельсинов, чем грейпфрутов. Следовательно, этот фрукт, скорее всего, является апельсином. Поздравляем: вы только что применили алгоритм k ближайших соседей для классификации! В целом алгоритм работает по довольно простому принципу.

Г г ^г ? А ‘ А ^А	Г Г ^г -* / А ^Л	г г ^г —у • / :о: А ' ' А ^А
1. ЬЫ ПОЛУЧАЕТЕ	1. ЬЫ ПРОвЕРЯЕТЕ ЕГО	3. СРЕДИ СОСЕДЕЙ АПЕЛЬСИНОв
Н06ЫЙ ФРУКТ ДЛЯ	3 БЛИЖАЙШИХ СОСЕДЕЙ	БОЛЬШЕ, ЧЕМ ГРЕЙПФРУТОв,
КЛАССИФИКАЦИИ		ПОЭТОМУ ФРУКТ, СКОРЕЕ 6СЕГ0,
		ЯвЛЯЕТСЯ АПЕЛЬСИНОМ

Алгоритм к ближайших соседей прост, но полезен! Если вы пытаетесь выполнить классификацию чего-либо, сначала попробуйте применить алгоритм к ближайших соседей. Рассмотрим более реалистичный пример.

Построение рекомендательной системы
Представьте, что вы работаете на сайте Netflix и хотите построить систему, которая будет рекомендовать фильмы для ваших пользователей. На высо­ком уровне эта задача похожа на задачу с грейпфрутами!
Информация о каждом пользователе наносится на график.

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

У Джастина, Джей-Си, Джозефа, Ланса и Криса похожие вкусы. Значит, те фильмы, которые нравятся им, с большой вероятностью понравятся и Приянке!
После того как у вас появится такая диаграмма, построить рекоменда­тельную систему будет несложно. Если Джастину нравится какой-нибудь фильм, порекомендуйте этот фильм Приянке.
ВАМ МОЖЕТ ПОНРАВИТЬСЯ

ПРЕВОСХОДНО
г. ЕМУ ПОНРАВИЛСЯ ФИЛЬМ

‘ >^{1 1}.
. «

1. ДЖАСТИН
СМОТРИТ ФИЛЬМ


Л3. РЕКОМЕНДУЕМ ЭТОТ ФИЛЬМ ПРИЯНКЕ
Однако в картине не хватает одного важного фрагмента. Вы оценивали, на­сколько близки вкусы двух пользователей на графике. Но как определить, насколько они близки?
Извлечение признаков
В примере с грейпфрутами мы сравнивали фрукты на основании их размера и цвета кожуры. Размер и цвет — признаки, по которым ведется сравнение. Теперь предположим, что у вас есть три фрукта. Вы можете извлечь из них информацию, то есть провести извлечение признаков.

ЦВЕТ: Z I 5

СДанные трех фруктов наносятся на график.

С
%

АВ
РАЗМЕР

Из диаграммы хорошо видно, что фрукты А и В похожи. Давайте измерим степень их сходства. Для вычисления расстояния между двумя точками применяется формула Пифагора.
С У-уД
Например, расстояние между А и В вычисляется так:
= лГо~7Т --JT 1
Расстояние между А и В равно 1. Другие расстояния вычисляются анало­гично.
С

вФормула расстояния подтверждает то, что мы видим: между фруктами А и В есть сходство.

Д

опустим, вместо фруктов вы сравниваете пользователей Netflix. Пользо­вателей нужно будет как-то нанести на график. Следовательно, каждого пользователя нужно будет преобразовать в координаты — так же, как это было сделано для фруктов.
Когда вы сможете нанести пользователей на график, вы также сможете из­мерить расстояние между ними.
Начнем с преобразования пользователей в набор чисел. Когда пользователь регистрируется на Netflix, предложите ему оценить несколько категорий
фильмов: нравятся они лично ему или нет. Таким образом у вас появляется набор оценок для каждого пользователя!

	ПРИЯНКА
КОМЕДИЯ	3
БОЕВИК	л-
ДРАМА	4-
УЖАСЫ	1
МЕЛОДРАМА	4

П

риянка и Джастин обожают мелодрамы и терпеть не могут ужасы. Мор- феусу нравятся боевики, но он не любит мелодрамы (хороший боевик не должен прерываться слащавой романтической сценой). Помните, как в за­даче об апельсинах и грейпфрутах каждый фрукт представлялся двумя чис­лами? Здесь каждый пользователь представляется набором из пяти чисел.

- + (з,+,4,1,4-)
Математик скажет, что вместо вычисления расстояния в двух измерениях вы теперь вычисляете расстояние в пяти измерениях. Тем не менее формула расстояния остается неизменной.
Просто на этот раз используется набор из пяти чисел вместо двух.
Формула расстояния универсальна: даже если вы используете набор из миллиона чисел, расстояние вычисляется по той же формуле. Естественно спросить: какой смысл передает метрика расстояния с пятью числами? Она сообщает, насколько близки между собой эти наборы из пяти чисел.

= 2
Это расстояние между Приянкой и Джастином.

Вкусы Приянки и Джастина похожи. А насколько различаются вкусы Приянки и Морфеуса? Вычислите расстояние между ними, прежде чем продолжить чтение.
Сколько у вас получилось? Приянка и Морфеус находятся на расстоянии 24. По этому расстоянию можно понять, что у Приянки больше общего с Джастином, чем с Морфеусом.
Прекрасно! Теперь порекомендовать фильм Приянке будет несложно: если Джастину понравился какой-то фильм, мы рекомендуем его Приянке, и на­оборот. Вы только что построили систему, рекомендующую фильмы.
Если вы являетесь пользователем Netflix, то Netflix постоянно напоминает вам: «Пожалуйста, оценивайте больше фильмов. Чем больше фильмов вы оцените, тем точнее будут наши рекомендации». Теперь вы знаете почему: чем больше фильмов вы оцениваете, тем точнее Netflix определяет, с какими пользователями у вас общие вкусы.
Упражнения

1. 
   В примере с Netflix сходство между двумя пользователями оцени­валось по формуле расстояния. Но не все пользователи оценивают фильмы одинаково. Допустим, есть два пользователя, Йоги и Пинки, вкусы которых совпадают. Но Йоги ставит 5 баллов любому фильму, который ему понравился, а Пинки более разборчива и ставит «пятер­ки» только самым лучшим фильмам. Вроде бы вкусы одинаковые, но по метрике расстояния они не являются соседями. Как учесть разли­чия в стратегиях выставления оценок?
   
2. 
   Предположим, Netflix определяет группу «авторитетов». Скажем, Квентин Тарантино и Уэс Андерсон относятся к числу авторитетов Netflix, поэтому их оценки оказывают более сильное влияние, чем оценки рядовых пользователей. Как изменить систему рекомендаций, чтобы она учитывала повышенную ценность оценок авторитетов?
   

Регрессия
А теперь предположим, что просто порекомендовать фильм недостаточно: вы хотите спрогнозировать, какую оценку Приянка поставит фильму. Возь­мите 5 пользователей, находящихся вблизи от нее.



Кстати, я уже не в первый раз говорю о «ближайших пяти». В числе «5» нет ничего особенного: с таким же успехом можно взять 2 ближайших пользова­телей, 10 или 10 000. Поэтому- го алгоритм и называется «алгоритмом к бли­жайших пользователей», а не «алгоритмом 5 ближайших пользователей»!
Допустим, вы пытаетесь угадать оценку Приянки для фильма «Идеальный голос». Как этот фильм оценили Джастин, Джей-Си, Джозеф, Ланс и Крис?

ДЖАСТИН :	s: