Прочитал книгу Х. Марманиса и Д. Бабенко «Алгоритмы интеллектуального интернета». Как видно из названия, эта книга посвящена алгоритмам, которые применяются на сайтах для того, чтобы сделать сайт чуть более дружественным пользователю, хотя эти же алгоритмы можно применять и для оффлайновых приложений.

Все рассмотренные в книге алгоритмы можно отнести к области Data Mining, то есть к извлечению каких-то новых сведений из уже имеющихся данных (иногда достаточно больших). Основные темы книги — это поиск, выработка рекомендаций, кластеризация и классификация.

В разделе про поиск описывается алгоритм PageRank, который был представлен на конференции в 1998 году Сергеем Брином и Ларри Пейджем. Конечно, с того времени в алгоритме, используемым Google, многое поменялось, но в целом суть осталась той же — чем больше ссылок на странице, тем более релевантной она считается. Этот алгоритм показывает, как можно учитывать ссылки между страницами для того, чтобы определить, какой из них отдать предпочтение при поиске.

Для поиска по данным в примерах используется библиотека Lucene, которая использует свой алгоритм подсчета релевантности страниц. В книге описаны способы объединения нескольких алгоритмов подсчета веса страниц с тем, чтобы улучшить поисковую выдачу.

Для дальнейшего улучшения поиска авторы используют алгоритм Байеса. Обычно этот алгоритм описывается на примере фильтрации спама (в книге такой пример тоже будет), но сначала авторы его используют для того, чтобы рассчитать вероятность того, что данная ссылка заинтересует пользователя, зная, на какие ссылки он кликал до этого и при каких поисковых запросах. После этого авторы объединяют все три способа фильтрации результатов поиска.

Удовлетворившись результатами поиска страниц в интернете, авторы рассказывают о том, как можно улучшить поиск по файлам PDF и Word, где нет явных ссылок между файлами. Для этого авторы для каждого файла вводят понятие DocRank (по аналогии с PageRank), который в данном случае зависит от частоты появления ключевых слов в файлах. Т.к. поиск осуществляется по локальным файлам, то проблема спама и накрутки ключевых слов с помощью черной поисковой оптимизации не особо актуальна. Разумеется, для поиска по файлам в интернете этот алгоритм должен быть модифицирован.

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

Следующая глава книги посвящена алгоритмам выработки рекомендаций. Вы, наверное, видели, что когда вы покупаете или просматриваете товар в интернет-магазине, то на той же странице вам предлагают посмотреть похожие товары. Это как раз и работают эти алгоритмы. В книге рассматриваются два основных принципа выработки предложений. Один из них работает по сходству товаров (если кто-то покупал несколько товаров, то скорее всего они как-то взаимосвязаны) и по сходству пользователей (если Васе нравится примерно те же музыкальные группы, что и Пете, то Васе можно предложить послушать песни, которые нравятся Пете). Именно для выработки предложений крупные интернет-компании, такие как Google и Facebook, собирают о вас как можно больше сведений. Многим это не нравится, но с другой стороны так меньше вероятность, что у вас на экране в качестве рекламы (почему-то еще не все пользуются банерорезалками) будут маячить китайская чесалка для спины на $0.99, если, конечно, вы не интересуетесь китайскими чесалками.

Еще одна глава посвящена вопросам кластеризации или объединению похожих предметов в группы. В качестве примера в книге рассматривается случай, когда нужно проанализировать множество пользователей сайта SourceForge.net, разбить их на группы и посмотреть, по каким критериям пользователи одной группы похожи друг на друга. Затем полученные группы можно использовать, например, для рекомендаций пользователей друг другу. В книге используются разные алгоритмы кластеризации (алгоритмы на основе связей между данными, алгоритм на основе минимального остовного дерева, алгоритм k-средних, а также алгоритмы ROCK и DBSCAN, который создает группы на основе плотностей точек в многомерном пространстве параметров).

После кластеризации в книге рассказывается про алгоритмы классификации. В начале этой главы перечисляются множество алгоритмов, которые применяются для этой цели со ссылками на статьи, где про них можно почитать. Более подробно говорится об алгоритмах Байеса (везде используется наивный байесовский алгоритм, когда считается, что выборки данных, по которым происходит обучение и классификация статистически независимы), нейронные сети (куда уж без них, если говорят о распознавании) и деревья решений (decision tree).

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

Завершив рассмотрение работы отдельных алгоритмов классификации, авторы рассказывают о том, как можно объединить несколько таких алгоритмов для повышения качества их работы, какие есть статистические способы сравнения алгоритмов, чтобы понять, есть ли смысл объединять разные алгоритмы, или они дают статистически одинаковые результаты. Для этого используются тест Макнемара, тест на разность пропорций, Q-тест Кохрана и F-тест. Некоторые из этих тестов предназначены для сравнения двух алгоритмов, некоторые для трех и более. Также приводятся алгоритмы Bagging и Boosting для объединения результатов классификации, полученных с помощью разных алгоритмов (или для использования одного и того же алгоритма, обученного на разных данных).

Это основные алгоритмы, которые рассматриваются в книге, но кроме них авторы приводят множество ссылок на другие алгоритмы, только перечисляя их, и говоря о том, какие у них преимущества и недостатки.

Это, что касается содержания книги, а теперь про форму того, как все это описано. Для книги авторы написали множество законченных программ на языке Java и собрали данные, на которых все описываемые алгоритмы можно испытывать. Но, к сожалению, большая часть книги посвящена не столько описанию самих алгоритмов, сколько описанию реализаций этих алгоритмов авторами. Теория алгоритмов описана довольно скудно, как работают некоторые из используемых алгоритмов становится понятно только после просмотра программы. Создается ощущение, что читаешь не книгу про алгоритмы, а книгу про использование библиотеки, в которую эти алгоритмы заложены. С одной стороны, благодаря этому можно брать и использовать исходники авторов в своих программах (если вы пишите на Java), а с другой — читать такую книжку не очень интересно. Но, надо сказать, что с точки зрения объектно-ориентированного программирования, программы авторов спроектированы довольно хорошо — где надо используются абстрактные классы, стараясь поглубже скрыть от пользователя реализации алгоритмов, ради которых, казалось бы написана книга.

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

В результате книжку почитать можно, если вы готовы немного повозиться с предлагаемыми программами, но только будьте готовы, что большую часть книги займет описание исходников, а не алгоритмов. Из-за этого книга Тоби Сегарана «Программируем коллективный разум» мне нравится больше.

PS. Вы можете подписаться на новости сайта через RSS, Группу Вконтакте или Канал в Telegram.