24 December 2009

Тоби Сегаран «Программируем коллективный разум»

Professional literatureReading room
Знаете, люблю я книжки про всякие интересные алгоритмы, и вот недавно попалась еще одна такая книжка.

Книга «Программируем коллективный разум» в основном посвящена алгоритмам классификации и кластеризации, хотя есть главы, посвященные другим темам вроде создания собственного поисковика, генетическим алгоритмам и генетическому программированию. Почти все описанные алгоритмы применяются в духе Web 2.0, используя анализ поведения пользователей на разных сайтах, которые предоставляют свой API. Но что особенно приятно удивило, так это то, что все примеры написаны на языке Python.


Вот какие алгоритмы описываются в книге:


  • Коллаборативная фильтрация. Или, говоря человечески языком, алгоритмы, которые могут рекомендовать вам какие-то покупки, сайты или музыку в зависимости от оценок, которые вы поставили другим подобным вещам. По таким алгоритмам работает навязывание покупок в интернет-магазинах или подбор музыки на last.fm. В конце главы приводится пример, который будет рекомендовать вам ссылки из сервиса del.icio.us.
  • Алгоритмы группировки (кластеризации). Создаваемый пример анализирует RSS-каналы блогов и пытается их автоматически разделить на группы в виде дерева в зависимости от частоты слов, которые попадаются в блоге. Заодно Сегаран рассказывает как можно сделать так, чтобы названия блогов расположились на плоскости кучками в зависимости от их близости в плане рассматриваемых тем.
  • Отдельная глава посвящена построению поисковиков – созданию паука и, самое главное, рассматриваются алгоритмы ранжирования ссылок, в том числе и с учетом ссылок страниц друг на друга, создавая, таким образом, аналог Google PageRank. Еще интересно, что в этой же главе есть пример, где для выдачи наиболее релевантных ссылок используется нейронная сеть, которая обучается по мере того как пользователь щелкает на понравившиеся ему ссылки.


  • Еще одна глава посвящена методам оптимизации. Здесь, в принципе, ничего особенного нет, коротко описаны алгоритмы случайного поиска, спуска с горы, отжига и генетический алгоритм. В качестве вебдванольного примера выступает поиск авиарейсов для довольно специфической задачи с помощью API сайта Kayak. Но в этой главе меня больше заинтересовали алгоритмы расселения студентов в общаге, чтобы удовлетворить как можно большее количество людей, и рисование связей между людьми таким образом, чтобы линии, обозначающие связи, не пересекались.
  • Рассматриваются алгоритмы сортировки на примере фильтрации спама. Приводится Байесовский алгоритм, который обычно первым приходит на ум при решении подобной задачи, и его модификация – метод Фишера. В качестве примера приводится работа с сайтом Akismet.
  • Рассказывается про алгоритмы построения деревьев решений, а в конце главы приводится пример, который с сайта Zillow загружает данные о ценах на недвижимость, а затем строит дерево решений, которое показывает какие параметры домов каким образом влияют на цену, а при желании можно спрогнозировать какая будет цена у дома с заданными параметрами.
  • Одна глава посвящена числовым прогнозам. Здесь рассмотрен алгоритм k ближайших соседей и взвешенный алгоритм k ближайших соседей. Пример в конце главы пытается угадать наиболее вероятную цену на товары на аукционе eBay по указанным параметрам.
  • Отдельная глава посвящена таким алгоритмам классификации как машина опорных векторов и ядерные методы. К сожалению, самое интересное – метод опорных векторов почти не рассмотрен. Точнее, буквально на пальцах рассказано что он делает, но не то как он это делает, а в примере используется библиотека http://www.csie.ntu.edu.tw/~cjlin/libsvm/, где этот алгоритм уже запрограммирован. В конце главы приводится пример подбора пар с использование API сайта Facebook.
  • Отдельная глава посвящена выявлению независимых признаков по массивам данных, но здесь я, если честно, не особо понял что делают описываемые алгоритмы.
  • И последняя глава посвящена генетическому программированию – разновидности генетических алгоритмов, когда между собой за место под солнцем (в оперативной памяти) конкурируют классы, моделирующие разные программы, которые между собой скрещиваются и мутируют.

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


Из недостатков можно отметить, что хотелось бы все-таки про некоторые описанные алгоритмы почитать более подробно, но как отправная точка книга вполне подойдет.



Эта запись у меня в блоге

Tags:книгиweb 2.0алгоритмы
Hubs: Professional literature Reading room
+61
4.1k 156
Comments 29