Анализ методов автоматической классификации документов

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Тольяттинский государственный университет»

Курсовая работа Тема Анализ методов автоматической классификации документов Студент Сидякин Антон Валерьевич г. Тольятти

2012 г.

• Ведение
• 1. Постановка задачи
• 2. Общие подходы к решению задачи классификации
• 3. Индексация документа
• 3.1 Построение вектора терминов и уменьшение его размерности
• 3.2 Расчет весов терминов
• 4. Методы построения классификаторов
• 4.1 Метод Rocchio
• 4.2 Метод вероятностной классификации (метод Байеса)
• 4.3 Метод разрешающих деревьев (деревья решений)
• 4.4 Правила принятия решений
• 4.5 Модели регрессии
• 4.6 Искусственные нейронные сети
• 4.7 Классификаторы на основе примеров. Метод k ближайших соседей
• 5. Оценка качества классификации
• 5.1 Оценка автоматической классификации в традициях информационного поиска
• 5.2 Оценка автоматической классификации с точки зрения особенностей реализации
• Заключение
• Список литературы
• автоматическая классификация документ поиск

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

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

В задачи курсовой работы входит:

· Рассмотрение подходов к индексации документов

· Рассмотрение подходов к построению классификаторов

· Рассмотрение подходов к оценке работы классификаторов

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

Классификация документов (классификация текстов, text categorization, text classification или topic spotting) является одной из основных задач информационного поиска.

В общем случае задача формулируется так:

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

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

Неизвестная целевая функция, где Т и F это «истина» (если текст принадлежит категории) и «ложь» (если текст не принадлежит категории) соответственно, является решением данной задачи.

Документ, для которого необходимо разрешить задачу классификации, договоримся называть обрабатываемым документом.

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

· При ранжированной классификации область значений функции лежит в отрезке В данном случае, функция на входе получает документ и возвращает значение статуса категоризации (categorization status value), т. е число от нуля до единицы, которое говорит о степени принадлежности документа к опрделенной категории. Таким образом, документы ранжируются в соответствии с их значением функции, а классификатор принимает решение о присвоении документу данной категории при анализе условия.

· При точной классификации область значений функции представлена двумя элементами {0,1} или {F, T} (где Т или 1 это «истина», т. е. текст принадлежит категории, а F или 0 это «ложь», т. е. текст не принадлежит категории)

или В данном случае, функция на входе получает документ и дает точный ответ, принадлежит ли текст данной категории или нет.

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

· Категории называются пересекающимися, если документ может принадлежать одновременно нескольким категориям. Категории называются непересекающимися, если документ не может принадлежать одновременно нескольким категориям.

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

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

К бинарной классификации можно свести все остальные: для каждой категории определяем, принадлежит ли данный документ к данной категории или к ее дополнению. В этом случае мы гарантируем, что документ в итоге будет отнесен не более чем к одной категории. Есть два различных способа использования классификатора документов для решения двух различных подзадач[2]:

· DPC — document-pivoted categorization. Данный тип подзадач встречается наиболее часто и состоит в том, что для данного документа требуется найти все категории, в которые он может попасть. Типичный пример — сортировка электронных писем или новостей.

· CPC — category-pivoted categorization. В этом случае для данной категории требуется найти все документы которые к данной категории относятся. Данная задача возникает например тогда, когда в множество, для которого уже была проведена классификация документов, добавляется одна или несколько новых категорий и требуется заново перераспределить документы между новым множеством категорий.

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

2. Общие подходы к решению задачи классификации

Зарождение теории автоматической классификации текстов датируется началом 60-х гг. ХХ в. За прошедшее время заметно изменился подход к анализу и решению проблемы, что произошло во многом благодаря появлению значительно более мощного аппаратного обеспечения и возросшего интереса к применению данных идей в реальных системах. На сегодняшний день можно выделить два основных подхода к автоматической классификации документов[3]:

1. До конца 80-х гг. самым популярным подходом к классификации текстов являлся метод инженерии знаний (knowledge engineering), заключающихся в определении человеком-специалистом набора правил, по которым осуществляется классификация. При условии, что правила составлены грамотно, этот метод является более точным, нежели второй (см. ниже), а результаты обработки легко поддаются интерпретированию (легко выяснить, почему для данного текста была выбрана именно такая-то рубрика). Однако, он имеет существенный недостаток — создание и поддержание правил в актуальном состоянии требует постоянной работы специалиста, знакомого с той предметной областью, для которой пишется данный классификатор.

2. В 90-х гг. на смену этому подходу пришел подход, называемый машинным обучением (machine learning), в соответствии с которым набор правил или, более обще, критерий принятия решения текстового классификатора, вычисляется автоматически из обучающих данных.

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

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

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

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

· - обучающее множество текстов (training set)

· - проверочное множество текстов (validation set)

· - Тестовое множество текстов (test set)

Процесс обучения классификатора делится, соответственно, на три фазы: Фаза машинного обучения классификатора

· Фаза проверки и настройки классификатора

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

В общем случае можно выделить три основные фазы решения задачи классификации документов:

1. Индексация (построение индекса) документа

2. Построение классификатора

3. Оценка качества классификации Индексацией называется процесс приведения документов к единому формату, удобному для дальнейшей обработки. Зачастую приходится иметь дело с большими объемами информации, поэтому из индекса документа стараются выкидывать все лишнее. Так, некоторые слова (предлоги, союзы и т. п.) могут очень часто встречаться в документах, но не нести никакой смысловой нагрузки.

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

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

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

Текстовые документы в исходном виде не подходят для интерпретации классификатором или алгоритмом построения классификатора. Поэтому необходимо применение процедуры индексации, которая переводит текст в удобное, для работы классификатора, представление. Очевидно, что для индексации обучающих и тестовых документов должен применяться один и тот же метод индексации.

Фаза индексации имеет огромное значение в решении задачи классификации. От того, насколько качественно составлен индекс документа, напрямую зависит эффективность работы классификатора.

В общем случае индексация состоит из следующих шагов:

· Построения вектора терминов документа

· Уменьшение размерности вектора терминов

· Расчет весов терминов Индексом документа в большинстве случаев является вектор взвешенных терминов Термин (терм, признак документа) — это слово или словосочетание из документа, важное для классификатора.

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

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

· в понимании, что считать термином

· в способах определения веса термина

3.1 Построение вектора терминов и уменьшение его размерности

Чаще всего предполагают, что терминами являются отдельные слова, встречающиеся в документе.

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

Множество всех терминов, встречающихся в документе, обозначим за .

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

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

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

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

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

Для некоторого класса задач удаления семантически нейтральных слов будет достаточно, особенно если исходный текст имеет небольшой размер (новостные заметки, электронные письма). Если текст имеет больший размер, вполне вероятно, что в нем есть слова близкие по смыслу (синонимы, однокоренные слова). Такие термины можно объединять в кластеры (искусственные термины).

Есть несколько различных подходов к кластеризации терминов.

Во-первых можно применять словари синонимов и словари омонимичных словоформ. Это наиболее простой и надежный способ, но очень медленный.

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

Еще одна техника уменьшения размерности вектора терминов заключается в определении «коэффициентов полезности» терминов. Как уже было сказано выше, любую задачу классификации можно свести к бинарной: для каждой категории определяем, принадлежит ли данный документ к данной категории или к ее дополнению. Тогда можно рассчитать вероятность встретить термин в документе при условии, что он принадлежит категории и вероятность встретить термин в документе при условии, что он принадлежит дополнению. Если обе вероятности близки по значению, то значит документ с таким термином, с примерно равной вероятностью, может попасть как в категорию, так и в ее дополнение. Значит, для классификатора такой термин бесполезен, и может быть исключен из рассмотрения. Коэффициент полезности, в данном случае, можно определить как модуль разности этих двух вероятностей.

3.2 Расчет весов терминов

Пусть каждый термин имеет вес по отношению к документу. Тогда, каждый документ можно представить в виде вектора весов его терминов:

.

Веса терминов удобно нормировать так, что бы для

.

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

Есть несколько подходов к тому, как рассчитывать веса терминов.

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

Для нормировки веса так, что бы можно рассчитывать вес термина в документе как отношение к общему числу терминов в документе (обозначим):

Еще один подход, заключающийся в вычислении функции, вытекает из двух, интуитивно понятных, наблюдений:

· Чем чаще термин встречается в документе, тем лучше он отражает его содержание (тем выше его значимость для классификатора)

· Чем в большем количестве документов встречается термин, тем менее значимым он является для классификатора Для реализации данного метода индексации необходимо иметь обучающие множество документов. Обозначим за подмножество документов из обучающего множества (), в которых встречается термин из документа .

Величину иногда называют документной частотой[2].

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

Вот примеры реализаций:

Для нормализации веса термина, рассчитанного с помощью функции, используют следующую стандартную формулу:

где — количество всех терминов в обучающем множестве документов.

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

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

4. Методы построения классификаторов

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

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

Далее задача заключается в том, что бы от вектора перейти к точной классификации.

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

Рассмотрим далее различные способы построения классификатора.

4.1 Метод Rocchio

Метод Rocchio является одним из самых простых и распространенных методов построения классификатора. Данный метод использует так называемый профайл документа для категории.

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

Профайл для категории в методе Rocchio рассчитывается по следующей формуле:

где:

· - вес термина в документе

· - множество документов, являющихся положительными примерами обучающего множества документов (иными словами, множество документов из обучающих данных, принадлежащих категории)

· - множество документов, являющихся отрицательными примерами обучающего множества документов (иными словами, множество документов из обучающих данных, не принадлежащих категории)

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

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

4.2 Метод вероятностной классификации (метод Байеса)

Вероятностные классификаторы рассматривают классификатор в терминах, т. е. как вероятность того, что документ принадлежит категории. Эту вероятность подсчитывают с помощью теоремы Байеса[3]:

где:

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

Вычисление в формуле Байеса затруднительно, из-за большого количества всевозможных векторов. В качестве решения данной проблемы обычно вводится допущение независимости (independence assumption), которое заключается в том, что любые две координаты вектора документа, рассмотренные как случайные переменные, статистически независимы друг от друга, и выражаются как:

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

4.3 Метод разрешающих деревьев (деревья решений)

Данный метод основан на построении дерева принятия решений по обучающему множеству документов.

В общем случае, это дерево представляет собой связный ациклический орграф, внутренние узлы которого представлены терминами, дуги помечены тестами на вес, который термин имеет в обрабатываемом документе, листья помечены категориями.

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

Наиболее простым является способ, при котором строится двоичное дерево, одна из дуг которого помечена условием (что означает отсутствие термина, соответствующего узлу, в документе), а вторая дуга помечена условием (что означает присутствие термина, соответствующего узлу, в документе). Чаще всего, такие деревья выясняют, принадлежит ли данный документ категории, или ее дополнению (т.е. дерево имеет только два различных вида листьев). В таком случае, в системе может быть построено не одно дерево, а отдельных деревьев для пар. Впрочем, вполне допустимо, затем, объединить эти деревья в одно.

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

· Для текущего узла выясняется, принадлежат ли документы, соответствующие данному узлу, к одной категории

· если нет, выбирается термин, разбивающий обучающее множество на два подмножества, в которых вес категории постоянный (или). Эти подмножества относят к разным поддеревьям, а текущая вершина помечается данным термином.

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

Другой метод — присвоение дугам условий проверки значений весов вида, где пороговое значение дляго узла, — количество дуг, выходящих из данного узла. В общем случае это допускает возможность построения n-арных деревьев решений.

Деревья решений могут также различаться видом листьев: с ними могут быть ассоциированы как конкретные категории, так и вещественные числа, отражающие степень принадлежности к какой-либо категории, или булевы значения true (принадлежит категории) и false (не принадлежит категории).

Обучение алгоритма построения дерева принятия решений включает в себя два основных этапа:

1. Построение дерева

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

Существует целый ряд стандартных алгоритмов построения дерева принятия решений: C4.5, CART, CHAID, MARS

4.4 Правила принятия решений

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

Идея ДНФ-методов заключается в отборе из всевозможных покрывающих правил (правил, которые корректно классифицируют все обучающие документы) «наилучшее» правило с точки зрения некоторого критерия минимальности. В то время как деревья принятия решений обычно строятся сверху вниз с помощью стратегии «разделяй и властвуй», ДНФ-правила зачастую формируются снизу вверх. В начале индуктивного процесса построения классификатора для категории каждый обучающий документ представляет собой утверждение вида, где это термины документа из обучающего множества, а равно ее дополнению. Этот набор утверждений уже является ДНФ-классификатором для ci, но очевидно, что в таком виде он подвержен эффекту переобучения. Поэтому процесс обучения включает в себя стадию генерализации, в ходе которой правила упрощаются, проходя через серию модификаций (сокращение посылок утверждений, слияние утверждений). Это делает правила более компактными и, в то же время, не нарушает свойства покрываемости классификатора. В завершении этого процесса, как и в случае с деревьями, выполняется стадия усечения, в результате которой повышается обобщающая способность классификатора.

Каждый обучающийся алгоритм на основе правил принятия решений может сильно отличаться в методах и критериях генерализации и усечения. Вот несколько индуктивных обучающихся стандартных ДНФ-алгоритмов построения классификатора: Charade, DL-ESC, Ripper, Scar и Swap-1.

4.5 Модели регрессии

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

В МНК с каждым документом ассоциировано два вектора:

· Исходный вектор, являющийся стандартным вектором весов терминов из множества

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

где:

· - норма Фробениуса для матрицы размером

· - матрица, составленная из исходных векторов обучающих документов

· - матрица, составленная из результирующих векторов обучающих документов Матрица обычно вычисляется с помощью сингулярного разложения векторов обучающего множества. Элементы найденной матрицы характеризуют степень ассоциированности категории и термина .

Эксперименты показывают, что МНК является одним из наиболее эффективных классификаторов, однако вычисление матрицы приводит к высоким вычислительным затратам.

4.6 Искусственные нейронные сети

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

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

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

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

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

4.7 Классификаторы на основе примеров. Метод k ближайших соседей

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

Наиболее распространенным вариантом «ленивой» классификации является метод — (k nearest neighbors, k ближайших соседей). Алгоритм метода состоит из трех последовательных шагов:

· Вычисляется расстояние между обрабатываемым документом и всеми документами обучающего множества. Для этих целей может быть использована любая функция сходства (например косинус угла между векторами документов)

· Далее выбирают документов, расстояние которых до обрабатываемого документа минимально. Обычно выбирают .

· Документу присваивается та категория, к которой принадлежит большинство из документов

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

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

5.1 Оценка автоматической классификации в традициях информационного поиска

Перед любым исследователем в области текстовой классификации рано или поздно встают вопросы: какой метод построения классификаторов является наиболее эффективным, какой метод применить к поставленной задаче? Ответить на эти вопросы — задача нетривиальная, потому что существует ряд трудностей на пути получения объективной оценки методов классификации. Эти трудности связаны в первую очередь со следующими требованиями: необходимость тестирования в одинаковых условиях, а следовательно. на одних и тех же стандартных коллекциях документов и тематик, на которых заранее известен корректный результат классификации, и при условии наличия сравнимых мер эффективности выполнения методов, не говоря уже о том, что метод может не оправдать ожиданий авторов только из-за ошибок реализации[3].

В настоящее время проводятся работы по созданию общедоступных коллекций документов. Примером может служить «Reuters», состоящая из множества новостных статей, принадлежащих категориям экономической тематики[3].

Вторая важная проблема оценки эффективности построенного классификатора — выбор мер эффективности[3]:

· Полнота (recall) — вычисляется как отношение количества корректных положительных предсказаний к общему числу положительных примеров

· Точность (precision) — вычисляется как отношение количества корректных положительных предсказаний к общему числу положительных предсказаний

· Аккуратность (accuracy) — вычисляется как отношение правильно принятых системой решений к общему числу решений

· Ошибка (error) — вычисляется как отношение неправильно принятых системой решений к общему числу решений Важным вопросом построения метрик в задаче классификации является метод усреднения результатов. В случае построения усредненной по множеству заданий той или иной множественной метрики возможны две последовательности действий[3]:

1. Сначала вычислить метрики для каждой категории отдельно, и затем их усреднить. Этот способ называют микроусреднением.

2. Получить предсказания для всех категорий и уже на их основе вычислить искомую метрику. Этот способ называют макроусреднением.

5.2 Оценка автоматической классификации с точки зрения особенностей реализации

Традиционные метрики информационного поиска дают некоторое представление о сравнительной оценке методов классификации и тем не менее, во-первых, остаются не полностью объективными, а во вторых, охватывают далеко не все аспекты использования алгоритмов. В реальных задачах автоматической классификации выбор алгоритма целесообразно проводить исходя из конкретных условий задачи, поэтому бывают необходимы и другие оценки выполнения алгоритмов. Вот наиболее существенные[3]:

· Способ разделения образцов. Большинство NLP-проблем (NLP — обработка естественного языка) не являются линейно разделимыми, это относится и ко многим обучающим множествам документов в задаче автоматической классификации (имеется в виду, что положительные и отрицательные примеры для заданной категории могут быть не разделимы линейно). В таких задачах наиболее предпочтительными методами являются методы на основе деревьев, методы на основе правил принятия решений, способные разделить множество образцов нелинейно. А в случае линейного разделения для бинарной классификации предпочтительнее применять линейную регрессию или метод наивного классификатора Байеса.

· Время выполнения. Существует ряд задач, в которых особенно актуальным является время обучения или выполнения алгоритма классификации, например, задачи он-лайн классификации при которой документ классифицируется «на лету». Во многих приложениях особенно важным является показатель скорости классификации новых объектов.

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

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

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

· Ограничения на размер обучающей коллекции документов и требования к ее качеству форматирования. Очевидно, что все методы обучения являются зависимыми от размера и качества обучающих данных, однако можно выделить и наиболее требовательные по данному признаку, т. е. те, на аккуратность которых наиболее существенно влияет качество обучающего множества документов. Среди них — классификаторы по методу разрешающих деревьев, для которых ограничение снизу на размер и качество обучающего множества продиктовано тем обстоятельством, что чем меньше обучающее множество, тем выше вероятность при построении классификатора принять случайность за закономерность. Построение нейронных сетей также очень требовательный процесс по отношению к качеству и размеру обучающего и проверочного множества документов, потому что нейронные сети обладают низкой устойчивостью к шуму в обучающей выборке. А вот метод Rocchio, наоборот, имеет некоторое преимущество в случае скудного обучающего множества, поскольку данный метод учитывает так же и отрицательные примеры.

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

Заключение

В рамках курсовой работы были рассмотрены методы автоматической классификации документов и основные этапы построения классифицирующей системы: индексация документа, методы построения классификаторов на основе обучающих данных, оценка работы классификатора.

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

1. Lewis, D.D., An evaluation of phrasal and clustered representations on a text categorization task. In Proceedings of SIGIR-92, 15th ACM International Conference on Researchand Development in Information Retrieval (Kobenhavn, DK, 1992), pp. 37−50., 1992

2. Sebastiani F. Machine Learning in Automated Text Categorization // Proc. ACM Computing Surveys (CSUR). — New York: ACM Press, 2002. — Vol. 34, Issue 1. — 48 p.

3. Пескова, О. В. Методы автоматической классификации текстовых электронных документов / О. В. Пескова // Научно-техническая информация. Серия 2: Информационные процессы и системы. — 2006. — № 3. — С.13−20.