Адитья Бхаргава – Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих (страница 27)

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

Допустим, вы пытаетесь угадать оценку Приянки для фильма «Идеальный голос». Как этот фильм оценили Джастин, Джей-Си, Джозеф, Ланс и Крис?

Если вычислить среднее арифметическое их оценок, вы получите 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. Переберите изображения цифр и извлеките признаки.

2. Получив новое изображение, извлеките признаки и проверьте ближайших соседей.

По сути это та же задача, что и задача классификации апельсинов и грейпфрутов. В общем случае алгоритмы OCR основаны на выделении линий, точек и кривых.

Затем при получении нового символа из него можно извлечь те же признаки.

Извлечение признаков в OCR происходит намного сложнее, чем в примере с фруктами. Однако важно понимать, что даже сложные технологии строятся на основе простых идей (таких, как алгоритм k ближайших соседей). Те же принципы могут использоваться для распознавания речи или распо­знавания лиц. Когда вы отправляете фотографию на Facebook, иногда сайту хватает сообразительности для автоматической пометки людей на фото. Да это машинное обучение в действии!

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

Построение спам-фильтра

Спам-фильтры используют другой простой алгоритм, называемый наив­ным классификатором Байеса. Сначала наивный классификатор Байеса тренируется на данных.

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

Например, наивный классификатор Байеса может использоваться для классификации фруктов: есть большой и красный фрукт. Какова вероятность того, что он окажется грейпфрутом? Это простой, но весьма эффективный алгоритм — из тех, что нам нравятся больше всего!

Прогнозы на биржевых торгах

Есть одна задача, в которой трудно добиться успеха машинным обучением: точно спрогнозировать курсы акций на бирже. Как выбрать хорошие признаки? Предположим, вы говорите, что если курс акций рос вчера, то он будет расти и сегодня. Хороший это признак или нет? Или, предположим, вы утверждаете, что курс всегда снижается в мае. Сработает или нет? Не существует гарантированного способа прогнозировать будущее на основании прошлых данных. Прогнозирование будущего — сложное дело, а при таком количестве переменных оно становится почти невозможным.

Шпаргалка

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

• Алгоритм k ближайших соседей применяется для классификации и регрессии. В нем используется проверка k ближайших соседей.

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

• Регрессия = прогнозирование результата (например, в виде числа).

• «Извлечением признаков» называется преобразование элемента (например, фрукта или пользователя) в список чисел, которые могут использоваться для сравнения.

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

11. Что дальше?

В этой главе

• Приводится краткий обзор 10 алгоритмов, которые не рассматривались в книге. Вы узнаете, для чего нужны эти алгоритмы.

• Я порекомендую книги, которые стоит читать дальше в зависимости от того, какие темы представляют интерес для вас.

Деревья

Вернемся к примеру с бинарным поиском. Когда пользователь вводит свое имя на сайте Facebook, сайт должен проверить содержимое большого массива, чтобы узнать, существует ли пользователь с таким именем. Мы выяснили, что для нахождения значения в массиве быстрее всего воспользоваться бинарным поиском. Однако здесь возникает проблема: каждый раз, когда на сайте регистрируется новый пользователь, придется заново сортировать массив, потому что бинарный поиск работает только с отсортированными массивами. Насколько удобнее было бы вставить пользователя в правильную ячейку массива, чтобы потом его не пришлось сортировать заново! Именно эта идея заложена в основу структуры данных бинарного дерева поиска.