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

. Сначала наивный классификатор Байеса тренируется на данных.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Мы нашли узел Maggie! В целом процедура поиска напоминает бинарный поиск. Поиск элемента в бинарном дереве поиска в среднем выполняется за время O(log n), а в худшем случае — за время O(n). Поиск в отсортированном массиве выполняется за время O(log n) в худшем случае — казалось бы, отсортированный массив эффективнее. Однако бинарное дерево поиска в среднем работает намного быстрее при удалении и вставке элементов.

У бинарных деревьев поиска есть и свои недостатки: во-первых, они не поддерживают произвольный доступ. Вы не сможете потребовать: «Выдайте мне i-й элемент этого дерева». Кроме того, в таблице приведено