Грокаем алгоритмы

Если вычислить среднее арифметическое их оценок, вы получите 4,2. Такой метод прогнозирования называется регрессией. У алгоритма k ближайших соседей есть два основных применения: классификация и регрессия:

• классификация = распределение по категориям;

• регресия = прогнозирование ответа (в числовом выражении).

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

• погода по шкале от 1 до 5 (1 = плохая, 5 = отличная);

• праздник или выходной? (1, если сегодня праздник или выходной, 0 в противном случае);

• проходят ли сегодня спортивные игры? (1 = да, 0 = нет).

И вы знаете, сколько буханок хлеба было продано в прошлом при разных сочетаниях признаков.

Сегодня выходной и хорошая погода. Сколько буханок вы продадите на основании только что приведенных данных? Используем алгоритм k ближайших соседей для k = 4. Сначала определим четырех ближайших соседей для этой точки.

Ниже перечислены расстояния. Точки A, B, D и E являются ближайшими.

Вычисляя среднее арифметическое продаж в эти дни, вы получаете 218,75. Значит, именно столько буханок нужно выпекать на сегодня!

Близость косинусов

До сих пор мы использовали формулу расстояния для вычисления степени сходства двух пользователей. Но является ли эта формула лучшей? На практике также часто применяется метрика близости косинусов. Допустим, два пользователя похожи, но один из них более консервативен в своих оценках. Обоим пользователям понравился фильм Манмохана Десаи «Амар Акбар Антони». Пол поставил фильму оценку 5 звезд, но Роуэн оценил его только в 4 звезды. Если использовать формулу расстояния, эти два пользователя могут не оказаться соседями, несмотря на сходство вкусов.

Метрика близости косинусов не измеряет расстояние между двумя векторами. Вместо этого она сравнивает углы двух векторов и в целом лучше подходит для подобных случаев. Тема метрики близости косинусов выходит за рамки этой книги, но вам стоит самостоятельно поискать информацию о ней, если вы будете применять алгоритм k ближайших соседей!

Выбор признаков

Чтобы подобрать рекомендации, вы предлагаете пользователям ставить оценки категориям фильмов. А если бы вы вместо этого предлагали им ставить оценки картинкам с котами? Наверное, вам бы удалось найти пользователей, которые ставили похожие оценки этим картинкам. Однако у вас получилась бы самая плохая рекомендательная система в мире, потому что эти «признаки» не имеют никакого отношения к их вкусам в области кино!

Или представьте, что вы предлагаете пользователям оценить фильмы для формирования рекомендаций — но только «Историю игрушек», «Историю игрушек-2» и «Историю игрушек-3». Эти оценки ничего не скажут вам о вкусах пользователей.

Когда вы работаете с алгоритмом k ближайших соседей, очень важно правильно выбрать признаки для сравнения. Под правильным выбором признаков следует понимать:

• признаки, напрямую связанные с фильмами, которые вы пытаетесь рекомендовать;

• признаки, не содержащие смещения (например, если предлагать пользователям оценивать только комедии, вы не получите никакой информации об их отношении к боевикам).

Как вы думаете, оценки хорошо подходят для рекомендации фильмов? Возможно, я поставил «Прослушке» более высокую оценку, чем «Охотникам за недвижимостью», но на самом деле я провел больше времени за просмотром «Охотников». Как улучшить рекомендательную систему Netflix?

Возвращаясь к примеру с пекарней: сможете ли вы придумать два хороших и два плохих признака, которые можно было бы выбрать для прогнозирования объема выпечки? Возможно, нужно выпечь побольше хлеба после рекламы в газете. Или увеличить объем производства по понедельникам.

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

Упражнения

10.3 У сервиса Netflix миллионы пользователей. В приведенном ранее примере рекомендательная система строилась для пяти ближайших соседей. Пять — это слишком мало? Слишком много?

Знакомство с машинным обучением

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

OCR

Сокращение OCR означает «Optical Character Recognition», то есть «оптическое распознавание текста». Иначе говоря, вы берете фотографию страницы текста, а компьютер автоматически преобразует изображение в текст. Google использует OCR для оцифровки книг. Как работает OCR? Для примера возьмем следующую цифру:

Как автоматически определить, что это за цифра? Можно воспользоваться алгоритмом k ближайших соседей:

1. Переберите изображения цифр и извлеките признаки.