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

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

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

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

Шпаргалка

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

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

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

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

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

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

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

В этой главе

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

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

Деревья

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

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

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

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

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

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

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

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

Видите, как дерево перекошено вправо? Эффективность такого дерева оставляет желать лучшего, потому что это дерево не сбалансировано. Существуют специальные бинарные деревья поиска, способные к самобалансировке (как, например, красно-черные деревья).

Где же используются бинарные деревья поиска? B-деревья, особая разновидность бинарных деревьев, обычно используются для хранения информации в базах данных.

Если вас интересуют базы данных или более сложные структуры данных, поищите информацию по следующим темам:

• в-деревья;

• красно-черные деревья;

• кучи;

• скошенные (splay) деревья.

Инвертированные индексы

Перед вами сильно упрощенное объяснение того, как работает поисковая система. Допустим, имеются три веб-страницы с простым содержимым.

Построим хеш-таблицу для этого содержимого.

Ключами хеш-таблицы являются слова, а значения указывают, на каких страницах встречается каждое слово. Теперь предположим, что пользователь ищет слово hi. Посмотрим, на каких страницах это слово встречается.

Ага, слово встречается на страницах А и B. Выведем эти страницы в результатах поиска. Или предположим, что пользователь ищет слово there. Вы знаете, что это слово встречается на страницах A и C. Несложно, верно? Это очень полезная структура данных: хеш-таблица, связывающая слова с местами, в которых эти слова встречаются. Такая структура данных, называемая инвертированным индексом, часто используется для построения поисковых систем. Если вас интересует область поиска, эта тема станет хорошей отправной точкой для дальнейшего изучения.

Преобразование Фурье

Преобразование Фурье — действительно выдающийся алгоритм: великолепный, элегантный и имеющий миллион практических применений. Лучшая аналогия для преобразования Фурье приводится на сайте Better Explained (отличный веб-сайт, на котором просто объясняется математическая теория): если у вас есть коктейль, преобразование Фурье сообщает, из каких