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

Классификация документов — одна из задач информационного поиска, заключающаяся в отнесении документа к одной из нескольких категорий на основании содержания документа. Является одной из задач документной лингвистики.

Классификация может осуществляться полностью вручную, либо автоматически с помощью созданного вручную набора правил, либо автоматически с применением методов машинного обучения.

Следует отличать классификацию текстов от кластеризации, в последнем случае тексты также группируются по некоторым критериям, но заранее заданные категории отсутствуют.

Подходы к классификации текстов

Существует три подхода к задаче классификации текстов.

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

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

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

Постановка задачи

Имеется множество категорий (классов, меток) C = { c 1 , . . . , c | C | } {displaystyle {mathfrak {C}}={c_{1},...,c_{left|{mathfrak {C}} ight|}}} .

Имеется множество документов D = { d 1 , . . . , d | D | } {displaystyle {mathfrak {D}}={d_{1},...,d_{left|{mathfrak {D}} ight|}}} .

Неизвестная целевая функция Φ : C × D → { 0 , 1 } {displaystyle Phi colon {mathfrak {C}} imes {mathfrak {D}} ightarrow {0,1}} .

Необходимо построить классификатор Φ ′ {displaystyle Phi ^{prime }} , максимально близкий к Φ {displaystyle Phi } .

Имеется некоторая начальная коллекция размеченных документов R ⊂ C × D {displaystyle {mathfrak {R}}subset {mathfrak {C}} imes {mathfrak {D}}} , для которых известны значения Φ {displaystyle Phi } . Обычно её делят на «обучающую» и «проверочную» части. Первая используется для обучения классификатора, вторая — для независимой проверки качества его работы.

Классификатор может выдавать точный ответ Φ ′ : C × D → { 0 , 1 } {displaystyle Phi ^{prime }colon {mathfrak {C}} imes {mathfrak {D}} ightarrow {0,1}} или степень подобия Φ ′ : C × D → [ 0 , 1 ] {displaystyle Phi ^{prime }colon {mathfrak {C}} imes {mathfrak {D}} ightarrow [0,1]} .

Этапы обработки

Индексация документов Построение некоторой числовой модели текста, например в виде многомерного вектора слов и их веса в документе. Уменьшение размерности модели. Построение и обучение классификатора Могут использоваться различные методы машинного обучения: решающие деревья, наивный байесовский классификатор, нейронные сети, метод опорных векторов и др. Оценка качества классификации Можно оценивать по критериям полноты, точности, сравнивать классификаторы по специальным тестовым наборам.

Обучающие методы

Наивная байесовская модель

Наивная байесовская модель является вероятностным методом обучения. Вероятность того, что документ d попадёт в класс c записывается как P ( c | d ) {displaystyle P(c|d)} . Поскольку цель классификации - найти самый подходящий класс для данного документа, то в наивной байесовской классификации задача состоит в нахождении наиболее вероятного класса cm

c m = argmax c ∈ C P ( c | d ) {displaystyle c_{m}={underset {cin C}{operatorname {argmax} }},P(c|d)}

Вычислить значение этой вероятности напрямую невозможно, поскольку для этого нужно, чтобы обучающее множество содержало все (или почти все) возможные комбинации классов и документов. Однако, используя формулу Байеса, можно переписать выражение для P ( c | d ) {displaystyle P(c|d)}

c m = argmax c ∈ C P ( d | c ) P ( c ) P ( d ) = argmax c ∈ C P ( d | c ) P ( c ) {displaystyle c_{m}={underset {cin C}{operatorname {argmax} }},{frac {P(d|c)P(c)}{P(d)}}={underset {cin C}{operatorname {argmax} }},P(d|c)P(c)}

где знаменатель P ( d ) {displaystyle P(d)} опущен, так как не зависит от c и, следовательно, не влияет на нахождение максимума; P(c) - вероятность того, что встретится класс c, независимо от рассматриваемого документа; P(d|c) - вероятность встретить документ d среди документов класса c.

Используя обучающее множество, вероятность P(c) можно оценить как

P ^ ( c ) = N c N {displaystyle {hat {P}}(c)={frac {N_{c}}{N}}}

где N c {displaystyle N_{c}} - количество документов в классе c, N - общее количество документов в обучающем множестве. Здесь использован другой знак для вероятности, поскольку с помощью обучающего множества можно лишь оценить вероятность, но не найти её точное значение.

Чтобы оценить вероятность P ( d | c ) = P ( t 1 , t 2 , . . . , t n d | c ) {displaystyle P(d|c)=P(t_{1},t_{2},...,t_{n_{d}}|c)} , где t k {displaystyle t_{k}} - терм из документа d, n d {displaystyle n_{d}} - общее количество термов в документе (включая повторения), необходимо ввести упрощающие предположения (1) о условной независимости термов и (2) о независимости позиций термов. Другими словами, мы пренебрегаем, во-первых, тем фактом, что в тексте на естественном языке появление одного слова часто тесно связано с появлением других слов (например, вероятнее, что слово интеграл встретится в одном тексте со словом уравнение, чем со словом бактерия), и, во-вторых, что вероятность встретить одно и то же слово различна для разных позиций в тексте. Именно из-за этих грубых упрощений рассматриваемая модель естественного языка называется наивной (тем не менее она является достаточно эффективной в задаче классификации). Итак, в свете сделанных предположений, используя правило умножения вероятностей независимых событий, можно записать

P ( d | c ) = P ( t 1 , t 2 , . . . , t n d | c ) = P ( t 1 | c ) P ( t 2 | c ) . . . P ( t n d | c ) = ∏ k = 1 n d P ( t k | c ) {displaystyle P(d|c)=P(t_{1},t_{2},...,t_{n_{d}}|c)=P(t_{1}|c)P(t_{2}|c)...P(t_{n_{d}}|c)=prod _{k=1}^{n_{d}}P(t_{k}|c)}

Оценка вероятностей P ( t | c ) {displaystyle P(t|c)} с помощью обучающего множества будет

P ^ ( t | c ) = T c t T c {displaystyle {hat {P}}(t|c)={frac {T_{ct}}{T_{c}}}}

где T c t {displaystyle T_{ct}} - количество вхождений терма t во всех документах класса c (и на любых позициях - здесь существенно используется второе упрощающее предположение, иначе пришлось бы вычислить эти вероятности для каждой позиции в документе, что невозможно сделать достаточно точно из-за разреженности обучающих данных - трудно ожидать, чтобы каждый терм встретился в каждой позиции достаточное количество раз); T c {displaystyle T_{c}} - общее количество термов в документах класса c. При подсчёте учитываются все повторные вхождения.

После того, как классификатор "обучен", то есть найдены величины P ^ ( c ) {displaystyle {hat {P}}(c)} и P ^ ( t | c ) {displaystyle {hat {P}}(t|c)} , можно отыскать класс документа

c m = argmax c ∈ C P ^ ( d | c ) P ^ ( c ) = argmax c ∈ C P ^ ( c ) ∏ k = 1 n d P ^ ( t k | c ) {displaystyle c_{m}={underset {cin C}{operatorname {argmax} }},{hat {P}}(d|c){hat {P}}(c)={underset {cin C}{operatorname {argmax} }}{hat {P}}(c)prod _{k=1}^{n_{d}}{hat {P}}(t_{k}|c)}

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

c m = argmax c ∈ C [ log ⁡ P ^ ( c ) + ∑ k = 1 n d log ⁡ P ^ ( t k | c ) ] {displaystyle c_{m}={underset {cin C}{operatorname {argmax} }}[log {hat {P}}(c)+sum _{k=1}^{n_{d}}log {hat {P}}(t_{k}|c)]}

Эта формула имеет простую интерпретацию. Шансы классифицировать документ часто встречающимся классом выше, и слагаемое log ⁡ P ^ ( c ) {displaystyle log {hat {P}}(c)} вносит в общую сумму соответствующий вклад. Величины же log ⁡ P ^ ( t | c ) {displaystyle log {hat {P}}(t|c)} тем больше, чем важнее терм t для идентификации класса c, и, соответственно, тем весомее их вклад в общую сумму.

Применение

• фильтрация спама
• составление интернет-каталогов
• подбор контекстной рекламы
• в системах документооборота
• автоматическое реферирование (составление аннотаций)
• снятие неоднозначности при автоматическом переводе текстов
• ограничение области поиска в поисковых системах
• определение кодировки и языка текста