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

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

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

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

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

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

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

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

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

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

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

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

Шпаргалка

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

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

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

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

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

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

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

В этой главе

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

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

Деревья

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

Бинарное дерево поиска выглядит так:

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

Предположим, вы ищете узел Maggie. Поиск начинается с корневого узла.

Строка Maggie идет после David, поэтому идем направо.