Nutch и Hadoop, первые впечатления

Давно уже собирался как следует посмотреть на Nutch — open-source поисковый движок на Java — сегодня наконец поставил, буду по-тихоньку делиться впечатлениями.

Nutch построен на основе Hadoop — это фреймворк, реализующий идею MapReduce. Расскажу кратко основную идею. Термины map и reduce пришли из функционального программирования, где они означают следующее: reduce это функция типа α -> β, map — функция типа (α -> β) -> [α] -> [β]. То есть map применяет переданную ей первым аргументом функцию reduce к списку элементов типа α и на выходе получается список элементов типа β. Например, если мы определим функцию square x = x ∗ x, вызов map square[1,2,3] вернет [1,4,9]. Если reduce функция без побочных эффектов (то есть она не изменяет ничего за пределами своей области видимости), то применять ее можно одновременно к нескольким элементам входного списка. Гугловый фреймворк MapReduce позволяет прозрачно для программы разносить эти вычисления по многим машинам. Hadoop представляет собой open-source реализацию этой же идеи на Java.

Итак, исходники скачаны, первое, что необходимо сделать — настроить запуск их среды разработки. Как это сделать для Eclipse описано здесь, перескажу вкратце с одним дополнительным шагом для IDEA.

1. При создании нового проекта IDEA найдет все папки с исходниками (их там много).
2. В dependencies надо добавить все *.jar из lib и src/plugin/*/lib. К hadoop-*.jar лучше подключить исходники или (лучше) настроить Hadoop соседним модулем в проекте.
3. Пометить папку conf как source folder. В настройках компилятора в Resource Patterns добавить ?*.txt, если этого не сделать *.txt файлы из conf, не будут видны в рантайме и Nutch работать не будет.
4. В nutch-site.xml (или nutch-defaults.xml) прописать свойство plugin.folders как src/plugin
5. Прописать в defaults VM arguments: -Dhadoop.log.dir=logs -Dhadoop.log.file=hadoop.log

После этого можно попробовать запустить Injector с соответствующими параметрами (см. tutorial), все должно работать.

К сожалению, какая-либо внятная и полная документация по Nutch и Hadoop отсутствует, API также практически не задокументирован, а код не слишком читабелен. Без дебагера разобраться сложно. Плюс эти товарищи повсеместно используют конструкцию, за которую надо просто отрывать руки:

try {
    url = urlNormalizers.normalize(url, URLNormalizers.SCOPE_INJECT);
    url = filters.filter(url);
} catch (Exception e) {
    if (LOG.isWarnEnabled()) { LOG.warn("Skipping " +url+":"+e); 
    url = null;
}

Если произойдет исключение, то мы увидим только его класс, а stacktrace нам не покажут. Нам даже не скажут на какой строчке какого класса оно произошло. Метод warn у логгера (и все остальные тоже) специально перегружены, чтобы корректно обрабатывать такую ситуацию, достаточно вместо плюса поставить запятую — LOG.warn("Skipping " +url+":", e) — и будет выведен нормальный stacktrace, из которого легко понять что происходит.

В целом же, Nutch работает: качает и ищет. В дальнейших планах написать пару плагинов к нему для особого парсинга скачанных страниц, развернуть его на кластере и разобраться с API Hadoop. Обо всем это, естественно, напишу.

Классификация документов

Продолжение серии "Введение в text mining".

С результатами автоматической классификации документов встречались, практически, все, кто пользовался электронной почтой. Спам-фильтры классифицируют входящую почту по двум категориям "спам"/"не спам" с помощью самых разных алгоритмов, начиная от простых decision trees задаваемых пользователем до сложных статистических методов. Далее мы рассмотрим несколько самых распространенных алгоритмов классификации и поймем как можно оценить и сравнить результаты работы этих алгоритмов.

Начнем с формулировки задачи. У нас есть некоторый набор категорий и документы, про которые известно, что они принадлежат одной из категорий. Пример: любой веб-каталог (Яндекс.Каталог, Yahoo Directory и другие), где сайты классифицированы по тематике. Эти документы составляют обучающую выборку для классификатора. Задача заключается в определении (точнее, предсказании с определенной вероятностью) категории для документов не входящих в обучающую выборку.

Очевидный способ классифицировать документ известный под названием алгоритм ближайшего соседа (nearest neighbour, NN) — найти в обучающей выборке наиболее схожий с ним и предположить, что их категории совпадают. В качестве меры похожести обычно используют расстояние или косинус угла между векторами. Самый простой в реализации, этот алгоритм оказывается и самым медленным, он линейно зависит от числа документов в обучающей выборке. На практике обычно используется модификация алгоритма ближайшего соседа — алгоритм k-ближайших соседей (k-nearest neighbours, k-NN). Здесь ищутся k наиболее близких документов из обучающей выборки и в качестве искомой категории выбирается встречающаяся чаще других в найденных документах. Так поступают, чтобы снизить влияние шума в обучающей выборке на результат. Шумом могут быть как просто неправильно классифицированные документы, так и документы, которые содержат много слов характерных для другой категории. Из-за невысоких показателей качества и, в первую очередь, низкой скорости алгоритм k-ближайших соседей редко применяется в промышленных разработках.

Следующий алгоритм, который мы рассмотрим, многие применяли и применяют в повседневной жизни. Создавая правило "always trust e-mails sent from address name@company.com" в почтовом клиенте, мы неявно управляем деревом принятия решений (decision tree), с помощью которого работают многие спам-фильтры. В нелистовых узлах дерева решений содержатся своего рода "вопросы" к документу, в листьях — ответы в виде результирующей категории. "Вопросы" могут задаваться самим пользователем, как в примере выше, так и вычисляться на основе обучающей выборки — в этом случае они обычно имеют вид "присутствуют ли в документе такие слова?" Простота идеи компенсируется сложностью построения такого дерева вопросов из набора документов, если интересно — напишу об этом отдельный пост. Кроме классификации, построенное дерево решений можно использовать для анализа структуры документов и категорий, что может может оказаться ценным само по себе. На практике, деревья решений используют в основном с этой целью, потому что по качеству классификации они сильно проигрывают классификаторам Байеса и линейным моделям, о которых пойдет речь дальше.

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

Здесь xi равно 1, если слово i присутствует в документе x, и 0 в противном случае. Таким образом задача классификации сводится к вычислению весов wi и смещения b для каждой категории и метод Байеса лишь один из многих способов их вычисления, причем не самый лучший. Заметим, что веса (wi,b) образуют гиперплоскость в пространстве слов, по одну сторону от которой лежат документы принадлежащие категории, по другую — не принадлежащие. Очевидно, что существует бесконечно много таких гиперплоскостей разделяющих документы из обучающей выборки. Идея, лежащая в основе метода опорных векторов (support vector machines, SVM), заключается в выборе разделяющей гиперплоскости, которая максимально удалена от всех документов. На данный момент, SVM считается самым точным алгоритмом классификации документов.

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

Представление текстовых данных

Продолжение серии "Введение в text mining".

Перед применением какого-либо алгоритма text mining набор текстовых документов надо преобразовать в более удобный вид. Общепринятым представлением является векторная модель (vector space model). Пусть у нас есть n документов, которые все вместе состоят из m уникальных слов. Каждому документу можно поставить в соответствие вектор d ∈ Rm, такой что di = 1, если слово i содержится в документе, и di = 0 в противном случае. Мы получили самую простую двоичную векторную модель. Как я уже говорил, важным свойством такого представления является разреженность, действительно, m может быть очень большим числом (несколько сотен тысяч), в то время как число единиц в каждом векторе может не превышать нескольких десятков. Это позволяет хранить в памяти не всю матрицу n ∗ m (1 000 000 ∗ 100 000 = 100 000 000 000 бит = 12.5 гигабайт), а лишь очень малую ее часть, обычно около 0.01-0.1%.

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

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

Еще одной техникой препроцессинга, помимо удаления стоп-слов, является стемминг (или лемматизация): выделение значимой части слова. С помощью стемминга слова "телефоны" и "телефона" приведутся к одному слову "телефон", что, помимо улучшения качества работы выбранного алгоритма, еще и значительно сократит словарь (а значит вырастет скорость работы). Хорощий обзор свободно доступных морфологических анализаторов можно найти в статье Губина и Морозова.

Описанная частотная модель, тем не менее, тоже не лишена недостатков. Некоторые слова могут встречаться в почти во всех документах и, соответственно, оказывать малое влияние на принадлежность документа к той или иной категории. Для понижения значимости таких слов используют модель TF∗IDF. TF (term frequency) это отношение числа раз, которое слово t встретилось в документе d, к длину документа. Нормализация длиной документа нужна, чтобы уравнять в правах короткие и длинные (в которых абсолютная встречаемость слов может быть гораздо больше) документы. IDF (inverse document frequency) — это логарифм отношения числа всех документов к числу документов содержащих слово t.
Таким образом, для слов, которые встречаются в большом числе документов IDF будет близок к нулу (если слово встречается во всех документах IDF равен нулю), что помогает выделить важные слова. Коэффициент TF∗IDF равен произведению TF и IDF. TF играет роль повышающего множителя, IDF — понижающего. Соответственно, вместо простой частоты встречаемости элементами векторов-документов будут значения TF∗IDF. Во многих задачах (но не во всех) это позволяет заметно улучшить качество.

Google Translate, Russian

Google запустил бета-версию переводов русский-английский и английский-русский. Качество перевода достаточно высокое, например, вот так выглядит часть предыдущего поста переведенная на английский:

Text mining, in contrast to his elder brother, data mining, a relatively young field of computer science, the most significant results were obtained in the past 10 to 15 years. It seems to me that this is linked primarily to the emergence of a very large number of available each text and the appearance of the volume computing power. For the data mining input are some facilities with a small number of properties, which made certain conclusions. For example, the object could be history, characteristics, the results of tests and examinations, and the findings accordingly diagnosis. The text mining operate with a set of documents, the words of which are the same as properties. The size of such documents can be very large (several thousand words), and the size of the dictionary for all documents can reach several hundreds of thousands of words. Here, it should be noted, an important feature set of documents : if present it in the form of a matrix dokumentslovo (where there is aij 1 ,if the word j contained in document i and 0 otherwise), we see that it is highly razrejennouu structure, the majority of well 0. This enables us to develop effective (memory and speed) algorithms for processing very large volumes of data.

Критерием достижения стопроцентного результата в машинном переводе считается двойной перевод, например, русский-английский-русский:

Текстовая добыча - в отличие от своего старшего брата, добыча данных, что является относительно молодым области применения компьютерной техники,наиболее важные результаты были получены в последние 10-15 лет.Мне кажется, что это прежде всего связано с появлением очень большого числа доступных каждому тексту, а также появлением большого объема вычислительной мощности.За добычу данных материалов некоторые объекты с небольшим числом свойств, что сделало определенные выводы.Например, объект может быть история, характеристики, результаты тестов и экзаменов, а выводы, соответственно, диагноза.Текст горного работать с пакетом документов, словами это те же свойства.Размеры таких документов может быть очень большим (несколько тысяч слов),и размер словарь для всех документов может достигать нескольких сотен тысяч слов.Здесь надо отметить, одной из важных особенностей комплекса документов :Если представить ее в виде матрицы, dokumentslovo (где есть aij 1, если выражение й содержащихся в документе я не 0),Вы видите, что это весьма razrejennouu структуре, а большинство из 0.Это позволяет создавать эффективные (память и скорость) алгоритмы для обработки очень больших объемов информации.

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

Машинный перевод (machine translation) является частью более общей задачи обработки текстов на естественных языках (natural language processing, NLP) и, возможно, наиболее сложной. Среди прочих задач NLP можно выделить распознавание речи, ответы на вопросы, авто-реферирование, проверка правильности текстов. Существует два главных направления в NLP: семантическое (когда мы пытаемся понять семантику слов и предложений) и статистическое (обучение на каком-либо корпусе текстов, для получения различной статистики взаимодействия слов). Статистические методы в NLP пришли из text mining, семантические методы NLP в свою очередь применимы в области извлечения информации (information extraction).

Возращаясь к Google Translate, забавный факт: почему-то заголовок "Text Mining Explained" был переведен (с русского на английский) как "Text Mining Casino".

Что такое text mining

Решил написать небольшую серию постов, некоторое введение в text mining. Что это такое, какие задачи ставятся, как решаются, какие направления сейчас развиваются. Начну с общего обзора.

Text mining, в отличие от своего старшего брата data mining, сравнительно молодая область computer science, большинство значительных результатов было получено в последние 10-15 лет. Как мне кажется, связано это в первую очередь с появлением очень большого количества доступной каждому текстовой информации и появлением соответствующих таким объемам вычислительных мощностей. Для задач data mining входной информацией являются некоторые объекты с небольшим числом свойств, на основании которых делаются определенные выводы. Например, объектом может быть история болезни, свойствами — результаты анализов и осмотров, а выводы, соответственно, диагноз. Системы text mining оперируют с набором документов, слова из которых можно аналогичным образом считать свойствами. При этом размер таких документов может быть очень большим (несколько тысяч слов), а размер общего словаря по всем документам может достигать нескольких сотен тысяч слов. Здесь нужно отметить одно важное свойство набора документов: если представить его в виде матрицы документ-слово (где элемент aij равен 1, если слово j содержится в документе i и 0 в противном случае), мы увидим, что она имеет сильно разреженную структуру, то есть большинство элементов равно 0. Это позволяет создавать эффективные (по памяти и скорости) алгоритмы обработки очень больших объемов данных.

Задачи text mining

1. Классификация (classification). Задача заключается в отнесении документа к одной из нескольких заранее определенных категорий, основываясь на содержании документа. Для построения классификаторов используется обучающая выборка из документов с присвоенными им категориями. Классический пример: классификация писем по категориям спам/не спам. Самые простые классификаторы: метод k ближайших соседей и классификатор Байеса.
2. Кластеризация (clustering) отличается от классификации тем, что мы не знаем какие существуют категории. У нас нет никакой обучающей выборки, есть только документы, которые надо попытаться определенным образом сгруппировать в кластеры (категории). Причем, как правило, неизвестно даже число возможных категорий (хотя его можно более-менее точно оценить. Существует два типа алгоритмов кластеризации: одни работают с заранее определенным числом категорий (например, алгоритм k-средних), другие с неизвестным (например, иерархическая кластеризация). Известные примеры использования кластеризации: Яндекс.Новости и Nigma.
3. Извлечение фактов (fact/information extraction). Название говорит за себя, задача заключается в извлечении из неструктурированного текста информации определенного вида, например пресс-портрета или цитат.

В следующих постах расскажу подробно о каждой из задач.

Text Mining Books

Хочу порекомендовать вам две замечательные книги по text mining.

1. Text Mining: Predictive Methods for Analyzing Unstructured Information (Sholom M. Weiss, Nitin Indurkhya, Tong Zhang, Frederick Damerau). Эта книга — краткое, но в то же время достаточно полное введение в text mining. Подготовка данных, классификация, кластеризация, поиск, извлечение информации — всему нашлось место в книге, причем некоторые алгоритмы описаны очень подробно. Самой интересной мне показалась шестая глава, посвященная статистическим методам в извлечении информации (information extraction). Резюме: специалистам в text mining книга поможет структурировать имеющийся объем знаний, для новичков же она прекрасное введение в область.
2. Survey of Text Mining: Clustering, Classification, and Retrieval (под редакцией Michael W. Berry). Здесь собраны лучшие работы участников Text Mining Workshop проведенного в рамках Second SIAM International Conference on Data Mining (SDM) в 2002-ом году. Наиболее интересные, на мой взгляд: мягкий (soft) алгоритм k-средних с автоматической расстановкой весов отдельным словам, алгоритмы кластеризации PDDP (Principal Direction Divisive Partitioning) и sPDDP( spherical PDDP), Latent Semantic Indexing и Covariance Matrix Analysis (известный также как Principal Component Analysis) и их модификации для лучшей обработки маленьких кластеров. Три перечисленных алгоритма кластеризации (кроме LSI) используют по сути один и тот же метод: нахождение одного или нескольких собственных векторов матрицы ковариантности. Чуть позже напишу об этом подробнее, это действительно очень интересно.
   

Стоит отметить, что 28-апреля 2007-го года в рамках очередной SDM пройдет Text Mining Workshop, лучшие работы с которого будут опубликованы во втором издании Survey of Text Mining. Работы принимаются до 8-го января.