Классификации текстов на основе алгоритмов машинного обучения и синтаксического анализа естественного языка - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
Похожие работы
Название работы Кол-во страниц Размер
3 Транслятор 1 30.45kb.
Программа: «Прикладная, экспериментальная и математическая лингвистика» 1 14.3kb.
Курсовая работа Построение риторических деревьев текста на основе... 5 467.83kb.
Классификация древнетибетских текстов с помощью методов спектрального... 1 173.87kb.
Рабочая программа дисциплины «Математическая логика и теория алгоритмов»... 3 543.74kb.
Исследование машинного агрегата задачи динамического анализа машины 1 90.07kb.
Гибридный алгоритм классификации текстовых документов на основе анализа... 1 109.22kb.
Машинный перевод 1 54.27kb.
Машинный перевод 1 23.65kb.
Программа сентимент-анализа текстов Дегтярёв Константин Юрьевич 05. 1 81.21kb.
Сборник текстов для домашнего чтения составители: соловьева т. 1 172.74kb.
Компьютер и окружающий мир введение 1 194.34kb.
Направления изучения представлений о справедливости 1 202.17kb.

Классификации текстов на основе алгоритмов машинного обучения и синтаксического анализа - страница №1/7



Московский Энергетический Институт

(технический университет)


Кафедра вычислительных машин, систем и сетей.

Система классификации текстов на основе алгоритмов машинного обучения и синтаксического анализа естественного языка.


Выполнил: Коростелёв И.В., А-8-02

Руководитель: Вышеславцев А.П.

Москва, 2007


Содержание





Содержание 3

Обозначения и сокращения 4

Введение 5

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

2. Выбор подхода к построению системы 7

3. Выбор представления текста 10

4. Выбор алгоритма машинного обучения 16

5. Выбор алгоритма морфологического анализа 31

6. Разработка алгоритма синтаксического анализа и выбора термов (нет) 39

7. Экспериментальная часть 40

8. Ещё предстоит сделать (TODO) 44

Список использованных источников 45


Обозначения и сокращения

АПТ – автоматическое понимание текста

ДОК – Документ-ориентированная классификация

КОК – Класс-ориентированная классификация

ИП – информационный поиск

МО – машинное обучение

МОВ – метод опорных векторов

ТК – текстовая классификация

k-NN – k ближайших соседей

Введение

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

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

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


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

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

Задача текстовой классификации заключается в присвоении булевского значения каждой упорядоченной паре (dj, ci) из D x C, где D – множество всех документов, а C – множество определённых категорий. Истина, в случае, если документ принадлежит категории, и ложь иначе. Более формально, задача заключается в приближении неизвестной целевой функции ’: D x C  {T, F}, которая описывает как документы должны быть классифицированы, некоторой функцией : D x C  {T, F}, которая называется классификатором, так, чтобы функции ’ и  совпадали как можно больше. Существует несколько метрик совпадения этих функций, они будут даны в разделе 4.2.

При теоретическом решении задачи текстовой классификации, как правило, предполагают, что:



  • Категории это просто метки. Их «физический» смысл неизвестен;

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

Категории могут быть объединены в иерархию, которая задаётся множеством H: C x C, состоящим из упорядоченных пар i, cj>, которые указывают, что категория cj является подкатегорией ci.

2.Выбор подхода к построению системы

Существует два основных способа построения системы текстовой классификации:



  • ручное создание правил классификации;

  • применение методов машинного обучения.

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

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


Как правило, система состоит из набора вручную определённых логических правил, по одному на категорию. «Если (ДНФ формула), то документ принадлежит к категории». Эта модель классификации соответствует булевской модели поиска [1].

ДНФ (дизъюнктивная нормальная форма) – дизъюнкция нескольких конъюнкций-подвыражений. Документ классифицируется, как относящийся к категории, если формула принимает истинное значение, т.е. хотя бы одно подвыражение – истинно. На рисунке Рисунок 2.1 .1 приведён пример одного правила из системы Construe [3].


Рисунок 2.1.1 – Правило для классификации текста под категорией «пшеница» (wheat)

Этот подход за счёт тонкой ручной настройки может давать очень хорошие результаты. Хайес используя этот подход добился результата нахождения точки перелома в 0.90 [3], что превосходит большинство классификаторов построенных на основе методик машинного обучения.

Недостатком этого метода является проблема «выделения знаний», хорошо известная в области экспертных систем. В частности, правило должно быть вручную определено двумя людьми: экспертом в проблемной области и инженером экспертной системы. Если набор категорий изменился, то вновь придётся вручную добавлять новые и изменять старые правила. В случае переноса системы на новую область знаний необходимо выполнять всю работу по созданию правил с нуля.



2.2.Характеристика методов, основанных на машинном обучении


С развитием локальных и глобальных сетей объёмы информации, требующей классификации, возросли многократно – ручное построение правил слишком трудоёмко, а зачастую и вовсе невозможно, например, в случае каталогов Интернет-ресурсов. Зачастую, можно пожертвовать небольшой потерей точности, значительно упростив процесс настройки классификатора. Этого можно добиться, применяя методы машинного обучения.

МО подход основывается на наличии исходного корпуса документов, классификация которых была произведена заранее. Т.е. значение функции : D x C -> {T, F} известно для каждой пары (d, c) из   C. Документ dj – положительный пример ci, если (dj, ci) = T, и отрицательный в противном случае.

Большинство методов МО являются бинарными: рассматривают всего два класса ci или . Если документ может принадлежать к 0 или более категориям, то это классификация с пересекающимися категориями (overlapping categories, multi-label). С теоретической точки зрения случай бинарной классификации является более общим, чем с пересекающимися категориями, т.к. алгоритм бинарной классификации можно применить к нескольким категориям: достаточно переформулировать задачу классификации под несколькими пересекающимися категориями c1, … , c|C|, как |C| непересекающихся задач бинарной классификации для (ci и ). Поэтому далее будут рассматриваться только бинарные методы.

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

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


следующая страница >>



Мера любви — любовь без меры. Видоизмененный Франциск Саль
ещё >>