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

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

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

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

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

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

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

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

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

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

Имеется множество категорий (классов, меток) <math>\mathfrak{C}=\{c_1,...,c_{\left|\mathfrak{C}\right|}\}</math>.

Имеется множество документов <math>\mathfrak{D}= \{ d_1, ... , d_{ \left| \mathfrak{D} \right| } \}</math>.

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

Необходимо построить классификатор <math> \Phi^\prime </math>, максимально близкий к <math>\Phi</math>.

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

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

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

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

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

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

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

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

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

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

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

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

<math>c_m = \underset{c \in C}{\operatorname{argmax}} \, P(c|d)</math>

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

<math>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)</math>

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

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

<math>\hat{P}(c) = \frac{N_c}{N}</math>

где <math>N_c</math> - количество документов в классе c, N - общее количество документов в обучающем множестве. Здесь использован другой знак для вероятности, поскольку с помощью обучающего множества можно лишь оценить вероятность, но не найти её точное значение.

Чтобы оценить вероятность <math>P(d|c) = P(t_1, t_2, ..., t_{n_d}|c)</math>, где <math>t_k</math> - терм из документа d, <math>n_d</math> - общее количество термов в документе (включая повторения), необходимо ввести упрощающие предположения (1) о условной независимости термов и (2) о независимости позиций термов. Другими словами, мы пренебрегаем, во-первых, тем фактом, что в тексте на естественном языке появление одного слова часто тесно связано с появлением других слов (например, вероятнее, что слово интеграл встретится в одном тексте со словом уравнение, чем со словом бактерия), и, во-вторых, что вероятность встретить одно и то же слово различна для разных позиций в тексте. Именно из-за этих грубых упрощений рассматриваемая модель естественного языка называется наивной (тем не менее она является достаточно эффективной в задаче классификации). Итак, в свете сделанных предположений, используя правило умножения вероятностей независимых событий, можно записать

<math>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)</math>

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

<math>\hat{P}(t|c) = \frac{T_{ct}}{T_c}</math>

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

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

<math>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)</math>

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

<math>c_m = \underset{c \in C}{\operatorname{argmax}} [\log\hat{P}(c) + \sum_{k=1}^{n_d} \log\hat{P}(t_k|c)]</math>

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

Применение

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

Литература

• Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze [www.informationretrieval.org/ An Introduction to Information Retrieval] Draft. Online edition. Cambridge University Press. - 2009. - 544 p.

См. также

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

Ссылки

• Лекция № 6 по классификации текстов курса «[yury.name/modern.html Современные задачи теоретической информатики]» (постановка задачи, построение и обучение классификатора, оценка качества).
• [nmis.isti.cnr.it/sebastiani/Publications/ACMCS02.pdf F. Sebastiani. Machine Learning in Automated Text Categorization (PDF).]  (англ.)
• [statosphere.ru/blog/135-text-mining1.html "Text mining. Классификация текста".] Пример классификации документов с использованием программных алгоритмов STATISTICA

Отрывок, характеризующий Классификация документов

Князь Николай Андреевич оглядел Анатоля. – Молодец, молодец! – сказал он, – ну, поди поцелуй, – и он подставил ему щеку.
Анатоль поцеловал старика и любопытно и совершенно спокойно смотрел на него, ожидая, скоро ли произойдет от него обещанное отцом чудацкое.
Князь Николай Андреевич сел на свое обычное место в угол дивана, подвинул к себе кресло для князя Василья, указал на него и стал расспрашивать о политических делах и новостях. Он слушал как будто со вниманием рассказ князя Василья, но беспрестанно взглядывал на княжну Марью.
– Так уж из Потсдама пишут? – повторил он последние слова князя Василья и вдруг, встав, подошел к дочери.
– Это ты для гостей так убралась, а? – сказал он. – Хороша, очень хороша. Ты при гостях причесана по новому, а я при гостях тебе говорю, что вперед не смей ты переодеваться без моего спроса.
– Это я, mon pиre, [батюшка,] виновата, – краснея, заступилась маленькая княгиня.
– Вам полная воля с, – сказал князь Николай Андреевич, расшаркиваясь перед невесткой, – а ей уродовать себя нечего – и так дурна.
И он опять сел на место, не обращая более внимания на до слез доведенную дочь.
– Напротив, эта прическа очень идет княжне, – сказал князь Василий.
– Ну, батюшка, молодой князь, как его зовут? – сказал князь Николай Андреевич, обращаясь к Анатолию, – поди сюда, поговорим, познакомимся.
«Вот когда начинается потеха», подумал Анатоль и с улыбкой подсел к старому князю.
– Ну, вот что: вы, мой милый, говорят, за границей воспитывались. Не так, как нас с твоим отцом дьячок грамоте учил. Скажите мне, мой милый, вы теперь служите в конной гвардии? – спросил старик, близко и пристально глядя на Анатоля.
– Нет, я перешел в армию, – отвечал Анатоль, едва удерживаясь от смеха.
– А! хорошее дело. Что ж, хотите, мой милый, послужить царю и отечеству? Время военное. Такому молодцу служить надо, служить надо. Что ж, во фронте?
– Нет, князь. Полк наш выступил. А я числюсь. При чем я числюсь, папа? – обратился Анатоль со смехом к отцу.
– Славно служит, славно. При чем я числюсь! Ха ха ха! – засмеялся князь Николай Андреевич.
И Анатоль засмеялся еще громче. Вдруг князь Николай Андреевич нахмурился.
– Ну, ступай, – сказал он Анатолю.
Анатоль с улыбкой подошел опять к дамам.
– Ведь ты их там за границей воспитывал, князь Василий? А? – обратился старый князь к князю Василью.
– Я делал, что мог; и я вам скажу, что тамошнее воспитание гораздо лучше нашего.
– Да, нынче всё другое, всё по новому. Молодец малый! молодец! Ну, пойдем ко мне.
Он взял князя Василья под руку и повел в кабинет.
Князь Василий, оставшись один на один с князем, тотчас же объявил ему о своем желании и надеждах.
– Что ж ты думаешь, – сердито сказал старый князь, – что я ее держу, не могу расстаться? Вообразят себе! – проговорил он сердито. – Мне хоть завтра! Только скажу тебе, что я своего зятя знать хочу лучше. Ты знаешь мои правила: всё открыто! Я завтра при тебе спрошу: хочет она, тогда пусть он поживет. Пускай поживет, я посмотрю. – Князь фыркнул.
– Пускай выходит, мне всё равно, – закричал он тем пронзительным голосом, которым он кричал при прощаньи с сыном.
– Я вам прямо скажу, – сказал князь Василий тоном хитрого человека, убедившегося в ненужности хитрить перед проницательностью собеседника. – Вы ведь насквозь людей видите. Анатоль не гений, но честный, добрый малый, прекрасный сын и родной.
– Ну, ну, хорошо, увидим.
Как оно всегда бывает для одиноких женщин, долго проживших без мужского общества, при появлении Анатоля все три женщины в доме князя Николая Андреевича одинаково почувствовали, что жизнь их была не жизнью до этого времени. Сила мыслить, чувствовать, наблюдать мгновенно удесятерилась во всех их, и как будто до сих пор происходившая во мраке, их жизнь вдруг осветилась новым, полным значения светом.
Княжна Марья вовсе не думала и не помнила о своем лице и прическе. Красивое, открытое лицо человека, который, может быть, будет ее мужем, поглощало всё ее внимание. Он ей казался добр, храбр, решителен, мужествен и великодушен. Она была убеждена в этом. Тысячи мечтаний о будущей семейной жизни беспрестанно возникали в ее воображении. Она отгоняла и старалась скрыть их.
«Но не слишком ли я холодна с ним? – думала княжна Марья. – Я стараюсь сдерживать себя, потому что в глубине души чувствую себя к нему уже слишком близкою; но ведь он не знает всего того, что я о нем думаю, и может вообразить себе, что он мне неприятен».
И княжна Марья старалась и не умела быть любезной с новым гостем. «La pauvre fille! Elle est diablement laide», [Бедная девушка, она дьявольски дурна собою,] думал про нее Анатоль.
M lle Bourienne, взведенная тоже приездом Анатоля на высокую степень возбуждения, думала в другом роде. Конечно, красивая молодая девушка без определенного положения в свете, без родных и друзей и даже родины не думала посвятить свою жизнь услугам князю Николаю Андреевичу, чтению ему книг и дружбе к княжне Марье. M lle Bourienne давно ждала того русского князя, который сразу сумеет оценить ее превосходство над русскими, дурными, дурно одетыми, неловкими княжнами, влюбится в нее и увезет ее; и вот этот русский князь, наконец, приехал. У m lle Bourienne была история, слышанная ею от тетки, доконченная ею самой, которую она любила повторять в своем воображении. Это была история о том, как соблазненной девушке представлялась ее бедная мать, sa pauvre mere, и упрекала ее за то, что она без брака отдалась мужчине. M lle Bourienne часто трогалась до слез, в воображении своем рассказывая ему , соблазнителю, эту историю. Теперь этот он , настоящий русский князь, явился. Он увезет ее, потом явится ma pauvre mere, и он женится на ней. Так складывалась в голове m lle Bourienne вся ее будущая история, в самое то время как она разговаривала с ним о Париже. Не расчеты руководили m lle Bourienne (она даже ни минуты не обдумывала того, что ей делать), но всё это уже давно было готово в ней и теперь только сгруппировалось около появившегося Анатоля, которому она желала и старалась, как можно больше, нравиться.
Маленькая княгиня, как старая полковая лошадь, услыхав звук трубы, бессознательно и забывая свое положение, готовилась к привычному галопу кокетства, без всякой задней мысли или борьбы, а с наивным, легкомысленным весельем.
Несмотря на то, что Анатоль в женском обществе ставил себя обыкновенно в положение человека, которому надоедала беготня за ним женщин, он чувствовал тщеславное удовольствие, видя свое влияние на этих трех женщин. Кроме того он начинал испытывать к хорошенькой и вызывающей Bourienne то страстное, зверское чувство, которое на него находило с чрезвычайной быстротой и побуждало его к самым грубым и смелым поступкам.
Общество после чаю перешло в диванную, и княжну попросили поиграть на клавикордах. Анатоль облокотился перед ней подле m lle Bourienne, и глаза его, смеясь и радуясь, смотрели на княжну Марью. Княжна Марья с мучительным и радостным волнением чувствовала на себе его взгляд. Любимая соната переносила ее в самый задушевно поэтический мир, а чувствуемый на себе взгляд придавал этому миру еще большую поэтичность. Взгляд же Анатоля, хотя и был устремлен на нее, относился не к ней, а к движениям ножки m lle Bourienne, которую он в это время трогал своею ногою под фортепиано. M lle Bourienne смотрела тоже на княжну, и в ее прекрасных глазах было тоже новое для княжны Марьи выражение испуганной радости и надежды.
«Как она меня любит! – думала княжна Марья. – Как я счастлива теперь и как могу быть счастлива с таким другом и таким мужем! Неужели мужем?» думала она, не смея взглянуть на его лицо, чувствуя всё тот же взгляд, устремленный на себя.
Ввечеру, когда после ужина стали расходиться, Анатоль поцеловал руку княжны. Она сама не знала, как у ней достало смелости, но она прямо взглянула на приблизившееся к ее близоруким глазам прекрасное лицо. После княжны он подошел к руке m lle Bourienne (это было неприлично, но он делал всё так уверенно и просто), и m lle Bourienne вспыхнула и испуганно взглянула на княжну.
«Quelle delicatesse» [Какая деликатность,] – подумала княжна. – Неужели Ame (так звали m lle Bourienne) думает, что я могу ревновать ее и не ценить ее чистую нежность и преданность ко мне. – Она подошла к m lle Bourienne и крепко ее поцеловала. Анатоль подошел к руке маленькой княгини.
– Non, non, non! Quand votre pere m'ecrira, que vous vous conduisez bien, je vous donnerai ma main a baiser. Pas avant. [Нет, нет, нет! Когда отец ваш напишет мне, что вы себя ведете хорошо, тогда я дам вам поцеловать руку. Не прежде.] – И, подняв пальчик и улыбаясь, она вышла из комнаты.


Все разошлись, и, кроме Анатоля, который заснул тотчас же, как лег на постель, никто долго не спал эту ночь.
«Неужели он мой муж, именно этот чужой, красивый, добрый мужчина; главное – добрый», думала княжна Марья, и страх, который почти никогда не приходил к ней, нашел на нее. Она боялась оглянуться; ей чудилось, что кто то стоит тут за ширмами, в темном углу. И этот кто то был он – дьявол, и он – этот мужчина с белым лбом, черными бровями и румяным ртом.