Характеристика классификации документов

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО образования и науки, молодежи и спорта Украины

Одесский национальный политехнический университет

Кафедра экономической кибернетики и информационных технологий

РЕФЕРАТ

ПО ДИСЦИПЛИНЕ «Технологии обработки электронных документов»

НА ТЕМУ «Классификация документов»

Выполнил:

Ушкова А.Ю.

Проверила:

Павличенко Т.В.

г. Одесса 2013 г

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

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

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

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

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

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

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

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

Классификатор может выдавать точный ответ или степень подобия .

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

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

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

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

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

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

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

Знаменатель опущен, так как не зависит от c и, следовательно, не влияет на нахождение максимума; P(c) - вероятность того, что встретится класс c, независимо от рассматриваемого документа; P(d|c) - вероятность встретить документ d среди документов класса количество документов в классе c, N - общее количество документов в обучающем множестве. Здесь использован другой знак для вероятности, поскольку с помощью обучающего множества можно лишь оценить вероятность, но не найти её точное значение.

Чтобы оценить вероятность , где - терм из документа d, - общее количество термов в документе (включая повторения), необходимо ввести упрощающие предположения (1) о условной независимости термов и (2) о независимости позиций термов. Другими словами, мы пренебрегаем, во-первых, тем фактом, что в тексте на естественном языке появление одного слова часто тесно связано с появлением других слов (например, вероятнее, что слово интеграл встретится в одном тексте со словом уравнение, чем со словом бактерия), и, во-вторых, что вероятность встретить одно и то же слово различна для разных позиций в тексте. Именно из-за этих грубых упрощений рассматриваемая модель естественного языка называется наивной (тем не менее она является достаточно эффективной в задаче классификации). Итак, в свете сделанных предположений, используя правило умножения вероятностей независимых событий, можно записать количество вхождений терма t во всех документах класса c (и на любых позициях - здесь существенно используется второе упрощающее предположение, иначе пришлось бы вычислить эти вероятности для каждой позиции в документе, что невозможно сделать достаточно точно из-за разреженности обучающих данных - трудно ожидать, чтобы каждый терм встретился в каждой позиции достаточное количество раз); общее количество термов в документах класса c. При подсчёте

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

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

Примеры видов документов

Таблица 1 Форма 12

Вывод

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

Список литературы

1. Christopher D. Manning, PrabhakarRaghavan, HinrichSchьtzeAn Introduction to Information Retrieval Draft. Online edition. Cambridge University Press. - 2009. - 544 p.

2. Лекция № 6 по классификации текстов курса «Современные задачи теоретической информатики» (постановка задачи, построение и обучение классификатора, оценка качества).

3. F. Sebastiani. Machine Learning in Automated Text Categorization (PDF). (англ.)

4. "Семантическое зеркало". Пример технологии автоматической классификации документов.

5. "Textmining. Классификация текста". Пример классификации документов с использованием программных алгоритмов STATISTICA

Размещено на Allbest.ru