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

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

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

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

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

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

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

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

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

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

Неизвестная целевая функция ${\displaystyle \Phi \colon {\mathfrak {C}}\times {\mathfrak {D}}\rightarrow \{0,1\}}$.

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

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

Классификатор может выдавать точный ответ ${\displaystyle \Phi ^{\prime }\colon {\mathfrak {C}}\times {\mathfrak {D}}\rightarrow \{0,1\}}$ или степень подобия ${\displaystyle \Phi ^{\prime }\colon {\mathfrak {C}}\times {\mathfrak {D}}\rightarrow [0,1]}$.

Индексация документов

Построение некоторой числовой модели текста, например в виде многомерного вектора слов и их веса в документе. Уменьшение размерности модели.

Построение и обучение классификатора

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

Оценка качества классификации

Можно оценивать по критериям полноты, точности, сравнивать классификаторы по специальным тестовым наборам.

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

${\displaystyle c_{m}={\underset {c\in C}{\operatorname {argmax} }}\,P(c|d)}$

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

${\displaystyle c_{m}={\underset {c\in C}{\operatorname {argmax} }}\,{\frac {P(d|c)P(c)}{P(d)}}={\underset {c\in C}{\operatorname {argmax} }}\,P(d|c)P(c)}$

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

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

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

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

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

${\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)}$

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

${\displaystyle {\hat {P}}(t|c)={\frac {T_{ct}}{T_{c}}}}$

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

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

${\displaystyle c_{m}={\underset {c\in C}{\operatorname {argmax} }}\,{\hat {P}}(d|c){\hat {P}}(c)={\underset {c\in C}{\operatorname {argmax} }}{\hat {P}}(c)\prod _{k=1}^{n_{d}}{\hat {P}}(t_{k}|c)}$

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

${\displaystyle c_{m}={\underset {c\in C}{\operatorname {argmax} }}[\log {\hat {P}}(c)+\sum _{k=1}^{n_{d}}\log {\hat {P}}(t_{k}|c)]}$

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

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

• Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze An Introduction to Information Retrieval Архивная копия от 9 декабря 2012 на Wayback Machine Draft. Online edition. Cambridge University Press. — 2009. — 544 p.

• Наивный байесовский классификатор
• Кластеризация
• Кластеризация документов
• Семантическое зеркало

• Лекция № 6 по классификации текстов курса «Современные задачи теоретической информатики Архивная копия от 15 октября 2008 на Wayback Machine» (постановка задачи, построение и обучение классификатора, оценка качества).
• F. Sebastiani. Machine Learning in Automated Text Categorization (PDF). Архивная копия от 28 мая 2016 на Wayback Machine (англ.)
• «Text mining. Классификация текста». Архивная копия от 3 октября 2011 на Wayback Machine Пример классификации документов с использованием программных алгоритмов STATISTICA