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

Продолжение серии "Введение в 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. Во многих задачах (но не во всех) это позволяет заметно улучшить качество.

Что такое 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). Название говорит за себя, задача заключается в извлечении из неструктурированного текста информации определенного вида, например пресс-портрета или цитат.

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