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

На правах рукописи

Агеев Михаил Сергеевич

МЕТОДЫ АВТОМАТИЧЕСКОЙ РУБРИКАЦИИ ТЕКСТОВ, ОСНОВАННЫЕ НА МАШИННОМ ОБУЧЕНИИ И ЗНАНИЯХ

ЭКСПЕРТОВ

05.13.11 —Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва — 2004

Работа выполнена на кафедре вычислительной математики механико-математического факультета Московского государственного университета им. М.В. Ломоносова.

Научные руководители:

Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук, академик Н.С. Бахвалов, доктор технических наук Н.В. Макаров-Землянский доктор физико-математических наук М.И. Кумсков, кандидат технических наук ЮА Загорулько

Научно-исследовательский институт математики и механики имени акад. В.И.Смирнова Санкт-Петербургского государственного университета (НИИ ММ СПбГУ)

Защита диссертации состоится 11 февраля 2005г. в 15 часов на заседании диссертационного совета K501.001.11 при Московском Государственном Университете им. М.В. Ломоносова по адресу: 119992, Москва, Ленинские горы, НИВЦ МГУ, конференц-зал.

С диссертацией можно ознакомиться в библиотеке НИВЦ МГУ.

Автореферат разослан Гл^Си ¿¿¿75ТУ _

Ученый секретарь диссертационного совета, кандидат физико-математических наук

Суворов В.В.

Общаяхарактеристика работы

Актуальность темы

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

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

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

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

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

К достоинствам методов, основанных на знаниях, относится высокая эффективность и "прозрачность" алгоритма — результаты

1 van Rijsbeigen C.J. Information Retrieval. — Butterworth's and Co., London, 1979 — 2nd edition. — 147 p.

FOC НАЦИОНАЛЬНАЯ (UUynTHl

обработки легко интерпретировать (почему такой-то документ был отнесен к данной рубрике). Основным недостатком этого класса методов является высокая трудоёмкость описания рубрик — до 8 человеко-часов на одну рубрику2.

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

Цель работы

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

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

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

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

Основные методы исследования

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

2 Wasson M. Classification Technology at LexisNexis. // Proc. of Int. Conf. ACM SIGIR 2001, Workshop on Operational Text Classification

Научная новизна

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

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

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

Практическая значимость работы

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

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

- нахождения ошибок ручного рубрицирования;

- итерационного повышения полноты и точности автоматического рубрицирования;

- создания терминологического описания для рубрики.

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

Реализация и внедрение результатов работы

Описанные алгоритмы и технологии реализованы и внедрены в технологический процесс построения систем классификации текстов в Университетской информационной системе РОССИЯ (УИС РОССИЯ), разрабатываемой в Научно-исследовательском вычислительном центре МГУ имени М.В. Ломоносова (НИВЦ МГУ). В течение 2003-2004 годов разработанные средства использовались при выполнении хоздоговорных работ в интересах ряда государственных организаций.

Апробация работы

Результаты диссертации докладывались на следующих конференциях: пятая и шестая всероссийская научная конференция «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» (октябрь 2003 и сентябрь 2004 года), XXVI конференция молодых ученых механико-математического факультета МГУ (апрель 2004 г.), всероссийская научная конференция «Научный сервис в сети ИНТЕРНЕТ» (сентябрь 2003 г.), международная конференция «Information Systems Technology and its Applications» в Харькове (июнь 2003 г.), международная конференция «New Trends in Intelligent Information Processing and Web Mining» в Закопане (Польша, май2004г.).

Публикации

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

Структура и объем работы

Диссертационная работа состоит из введения, трёх глав, заключения и списка литературы. Нумерация разделов диссертации — сквозная иерархическая (основные главы находятся в разделах 2-4).

Объем диссертации — 136 страниц, список литературы содержит 82 наименования. Работа включает 3 таблицы и 8 рисунков.

Краткое содержание диссертации

1. Введение

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

2. Обзор методов автоматической рубрикации текстов

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

Сначала (разделы 2.1-2.3) описываются базовые технологии, применяемые для обработки текстов: преобразование документов в вектор с использованием морфологического анализа слов, вычисление весов слов по формуле ТР*ШР, методы сокращения размерности пространства признаков. Также описываются общепринятые методы оценки результатов классификации.

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

3 Joachims T. Text Categorization with Support Vector Machines: Learning with Many Relevant Features. //Proceedings of ECML-98, 10th European Conference on Machine Learning — 1998.

4 Dumais S., Platt J,, Heckerman D., Sahami M. Inductive learning algorithms and representations for text categorization. // In Proc. Int. Conf. on Inform, and Knowledge Manage., 1998.

5 Yang Y., Liu X. A re-examination of text categorization methods. // Proc. of Int. ACM Conference on Research and Development in Information Retrieval (SIGIR-99), 1999 — pp. 42-49.

сравнению качества классификации методов машинного обучения. Эксперименты проводились на двух текстовых коллекциях: Reuters-21578 и TREC-2001.

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

В разделе 2.5 даётся обзор методов машинного обучения, применяемых для автоматической классификации текстов. Для обзора выбраны, с одной стороны, широко известные методы (в частности, упоминаемые в публикациях по сравнению методов). С другой стороны, рассматриваются методы машинного обучения, которые могут построить описание рубрики в виде, пригодном для анализа человеком: 1) методы построения деревьев решений и 2) методы построения логических правил отнесения документов к рубрике (последние используют перебор вариантов, возможный лишь для задач малой размерности).

В разделе 2.6 даётся обзор методов автоматической классификации текстов, основанных на знаниях.

6 Lewis D. Applying Support Vector Machines to the TREC-2001 Batch Filtering and Routing Tasks. // Proceedings ofTREC-2001 conference.

7 Vapnik V. The Nature of Statistical Learning Theory. — Springer-Verlag — NewYork, 1995.

Проведённый анализ различных методов позволил выбрать для дальнейших исследований

- наиболее эффективный метод машинного обучения SVM в качестве отправной точки для сравнения качества работы других методов машинного обучения;

- метод классификации, используемый в УИС РОССИЯ, в качестве эффективного и доступного для исследования метода, основанного на знаниях.

3. Метод машинного обучения, основанный на моделировании логики рубрикатора

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

В качестве основы для моделирования используется подход к описанию рубрики, используемый в УИС РОССИЯ8. Согласно этому подходу, описание рубрики экспертом представляется в виде булевской формулы над понятиями тезауруса, которую можно интерпретировать как запрос к полнотекстовой информационной системе вида

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

8Добров Б.В., Лукашевич Н.В., Автоматическая рубрикация полнотекстовых документов по классификаторам сложной структуры //Восьмая национальная конференция по искусственному интеллекту — Коломна, 2002.

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

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

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

где 11} — множества документов, содержащих некоторое понятие

тезауруса (или, в общем случае, некоторый терм — элемент векторного представления документов). Конъюнкции, составляющие формулу, имеют длину J¡ от 1 до 3.

В разделе 3.1 приводится описание алгоритма построения формул. На вход алгоритма подаётся множество документов, стандартным образом преобразованных в векторное представление. Каждый документ представляется вектором в пространстве К". Алгоритм применяется отдельно для каждой рубрики. Множество документов, относящихся к рубрике, будем обозначать С.

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

к ■>,

1. и = У } (основной алгоритм)

В результате первого шага определяется множество конъюнктов V — конъюнкций из одного, двух или трёх термов. Для каждого

конъюнкта V, е V вычисляются полнота = точность

р(у,) = ^Я и Б-мера

описания рубрики

запросом, состоящим из одного только этого конъюнкта.

Основным и наиболее трудоёмким шагом является построение

дизъюнкции из набора конъюнктов и( е V . Формула

наращивается постепенно новыми конъюнктами по шагам. Пусть и(_, — формула, вычисленная до шага / > 1, ио = 0. Для добавления в формулу нового конъюнкта определяется конъюнкт-кандидат, для которого функция качества максимальна:

здесь — некоторые весовые коэффициенты, при помощи

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

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

Последним шагом алгоритма является усечение формулы (отсечение «хвоста») для достижения максимума Б-меры: игт =агётахР(Ц.).

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

В разделе 3.2 приводится аналитическое исследование алгоритма построения формул. Рассматривается «идеальная» ситуация, когда

рубрика описывается некоторой формулой и* =иС>Ня ^ ; € ^

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

Рассмотрим поведение алгоритма построения формул на основном шаге — построении дизъюнкции, считая векторное представление документа и набор конъюнктов фиксированными. Оценим метрики качества /-го конъюнкта в формуле, которую построит алгоритм построения формул с параметрами

Эти оценки сформулированы в виде следующей теоремы: Теорема 1. Пусть существует формула и* и* е V

длины п, описывающаярубрику С с полнотой и точностью, равной единице. Обозначим ~ т'п (г(и; ))> Р > ® •

Пусть на шаге/>1 алгоритмомпостроения формул спараметрами Р> О и /¿0 построена формула = и,ии2и...ии(. Тогда выполняются следующие неравенства:

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

N

качества. Пусть алгоритм строит по шагам формулу и = У и,.

1=1

Следствие 1: Пусть выполняются условия теоремы 1 и зада

параметр ?;е(0,1]. Тогда, если у>-—--—то дм любого ¡ = \.1

П Р

Следствие 2: Пусть выполняются условия теоремы I и зада

1-1

у\

, то дл

Л

1-п|

параметр /7е(0,1). Тогда, если /?>—- (п~1)+у

любого Ы\Л: 1) р(и,|)> 1 -77 2) р(и,)>1-/7.

Следствия 1 и 2 позволяют утверждать, что, если существует формула, которая точно описывает заданное множество документов (рубрику), то алгоритм построения формул, при достаточно «жестких» параметрах (т.е. больших значениях /? и у ) построит формулу, описывающую рубрику с заданным уровнем качества. А именно: для любого, сколь угодно малого параметра Ц> О можно выбрать параметры алгоритма так, что

1. точность полученной формулы будет не менее

2. каждый конъюнкт будет иметь покрытие (полноту) почти как у точной формулы:

Следствие 3: Пусть выполняются условия теоремы 1 и задан параметрЦ € (0,1) • Тогдадлялюбого I = 1 „Л^

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

В разделе 3.3 описывается экспериментальное исследование алгоритма построения формул. Исследование основано на общедоступных коллекциях текстов, отрубрицированных экспертами по заданному рубрикатору. Результаты работы алгоритма построения формул сравнивались с результатами работы других методов классификации текстов. Были проведены следующие эксперименты:

1. Эксперименты на коллекции Reuters-21578 — англоязычной коллекции новостей агентства Reuters (12902 документа, 135 рубрик). Эксперименты показали, что:

качество классификации (F-мера) сравнимы с SVM, хотя в среднем — несколько хуже; - создаваемые формулы описания рубрик соответствуют содержанию рубрики;

2. Эксперименты на коллекции ГОМИП-2004 — дорожке тематической классификации нормативных документов РФ Российского семинара по Оценке Методов Информационного Поиска 2004 года (60015 документов, 170 рубрик). Эксперименты показали, что:

Алгоритм построения формул показал лучший результат, обогнав по качеству классификации SVM и алгоритмы других участников ГОМИП'2004 — ещё 6 алгоритмов;

создаваемые формулы описания рубрик соответствуют содержанию рубрики.

4. Тематический анализ коллекции документов

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

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

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

Алгоритмы работы программы-помощников основаны на статистическом анализе коллекции документов с привлечением методов машинного обучения. Разработано три алгоритма программ-помощников:

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

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

3. Алгоритм анализа результатов запроса, основанный на методе машинного обучения, описанном в разделе 3.

В разделе 4.2.1 приведена классификация различных проблем, возникающих при описании рубрик экспертами. В частности, такими проблемами являются: 1) проблема определения и соблюдения ограничивающих правил рубрицирования; 2) проблема документов, отнесенных экспертами к рубрике ошибочно; 3) проблема пропущенных экспертами документов.

В разделе 4.2.2 предложены методы решения указанных проблем с использованием средств анализа коллекции документов.

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

Кроме того, разработанные средства применяются в качестве эффективного средства поиска и анализа информации в полнотекстовой информационной системе УИС РОССИЯ.

5. Заключение

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

Основные результаты работы

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

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

3. Проведено экспериментальное исследование разработанного алгоритма. Экспериментально доказана высокая эффективность алгоритма и соответствие получаемых формул содержанию рубрики. В экспериментах на коллекции РОМИП'2004 (дорожка тематической

классификации Российского семинара по Оценке Методов Информационного Поиска 2004 года) алгоритм построения формул показал лучший результат по сравнению с 8 другими алгоритмами классификации текстов.

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

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

Список работ, опубликованных по теме диссертации

1. Агеев М.С., Добров Б.В., Макаров-Землянский Н.В. Метод машинного обучения, основанный на моделировании логики рубрикатора //RCDL'2003 Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Пятая всеросс. науч. конф. 29-31 октября 2003 г. — Санкт-Петербург, 2003. — С.150-158.

2. Ageev M., Dobrov В., Loukachevitch N. Text Categorization Tasks for Large Hierarchial Systems of Categories // SIGIR 2002 Workshop on Operational Text Classification Systems. Proceedings of the International Conference. August 11-15, 2002 /Eds. F.Sebastiani, S.Dumas, D.D.Lewis, T.Montgomery, I.Moulinier — Univ. of Tampere, 2002. — pp.49-52.

3. Ageev M., Dobrov В., Makarov-Zemlyanskii N. On-line Thematic and Metadata Analysis of Document Collection

// New Trends in Intelligent Information Processing and Web Mining'2004: Proceedings of the International Conference. May 17-20, 2004 /Springer, Advanced in Soft Computing — Zakopane, Poland, 2004. — pp.279-286.

4. Агеев M.C., Добров Б.В., Лукашевич Н.В. Поддержка системы автоматического рубрицирования для сложных задач классификации текстов //RCDL'2004 Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Шестая всероссийская науч. конф. 29 сен. - 1окт. 2004 г. — Пущино, 2004. — С.216-225.

5. Ageev M.S., Dobrov B.V. Support Vector Machine Parameter Optimization for Text Categorization Problems //Вестник Национального Технического Университета «ХПИ» — Харьков, Украина, 2004. — №1 — С.3-14.

6. Агеев М.С., Добров Б.В., Лукашевич Н.В., Сидоров А.В. Экспериментальные алгоритмы поиска/классификации и сравнение с «basic line» //Российский семинар по Оценке Методов Информационного Поиска (РОМИП 2004): Семинар в рамках Всероссийской науч. конф. RCDL'2004. 1 окт. 2004 г. — Пущино, 2004. — С.62-89.

7. Агеев М.С., Добров Б.В., Лукашевич Н.В., Сложные задачи автоматической рубрикации текстов //Научный сервис в сети ИНТЕРНЕТ: Труды Всероссийской науч. конф. 23-28 сентября 2002. — Новороссийск, 2002. — С.251 -252.

8. Агеев М.С., Добров Б.В., Тематический анализ коллекции документов on-line //Научный сервис в сети ИНТЕРНЕТ: Труды Всероссийской науч. конф. 22-27 сентября 2003. — Новороссийск, 2003. —С.249-252.

9. Ageev M., Dobrov В. Support Vector Machine Parameter Optimization for Text Categorization Problems //Information Systems Technology and its Applications (ISTA'2003): Proceedings of International Conference. June 19-21,2003. / Lecture Notes in Informatics GI, 2003. — Vol 30 — pp. 165-176.

10. M. Ageev. Martin's game: a lower bound for the number of sets. // Theoretical Computer Science, 2002. — Vol. 289/1 — pp.871-876.

Принято к исполнению 30/12/2004 Исполнено 30/12/2004

Заказ №537 Тираж: 100 экз.

ООО «11-й ФОРМАТ» ИНН 7726330900 Москва, Балаклавский пр-т, 20-2-93 (095)747-64-70 (095)318-40-68

•S О 4

1 ВВЕДЕНИЕ.

2 ОБЗОР МЕТОДОВ АВТОМАТИЧЕСКОЙ РУБРИКАЦИИ ТЕКСТОВ.

2.1 Основные подходы к представлению текстов для компьютерной обработки.

2.1.1 Использование морфологии.

2.1.2 TF*IDF.

2.1.3 Борьба с высокой размерностью: сокращение числа используемых атрибутов путем выделения наиболее значимых.

2.1.4 Использование дополнительных атрибутов документа.

2.2 Метрики качества рубрицирования.

2.3 Оценки метода машинного обучения на коллекции документов.

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

2.5 Обзор методов машинного обучения.

2.5.1 Метод Байеса.

2.5.2 Метод k-ближайших соседей.

2.5.3 Rocchio classifier.

2.5.4 Нейронные сети.

2.5.5 Деревья решений.

2.5.6 Построение булевых функций.

2.5.7 Support Vector Machines.

2.6 Обзор методов, основанных на знаниях.

2.6.1 Технология классификации LexisNexis.

2.6.2 Технология классификации Reuters.

2.6.3 Технология классификации документов на основе тезауруса

УИС РОССИЯ.

2.7 Выводы.

3 МЕТОД МАШИННОГО ОБУЧЕНИЯ, ОСНОВАННЫЙ НА МОДЕЛИРОВАНИИ ЛОГИКИ РУБРИКАТОРА.

3.1 Описание алгоритма ПФА (алгоритма построения формул).

3.1.1 Шаг 1: вычисление векторного представления.

3.1.2 Шаг 2: построение конъюнктов.

3.1.3 Шаг 3: построение дизъюнкции.

3.1.4 Шаг 4: усечение формулы.

3.1.5 Построение формулы с отрицаниями.

3.2 Аналитическое исследование алгоритма.

3.2.1 Описание алгоритма ПФБА.

3.2.2 Свойства метрик полнота, точность, F-мера.

3.2.3 Исследование сходимости алгоритма ПФБА для «идеальной» рубрики.

3.3 Экспериментальное исследование алгоритма построения формул ПФА.

3.3.1 Описание программной реализации алгоритма.

3.3.2 Эксперименты на коллекции Reuters-21578.

3.3.3 Эксперименты на коллекции РОМИП-2004.

3.4 Выводы.

4 ТЕМАТИЧЕСКИЙ АНАЛИЗ КОЛЛЕКЦИИ ДОКУМЕНТОВ.

4.1 Тематический анализ коллекции документов on-line.

4.1.1 Анализ по тезаурусу.

4.1.2 Анализ по метаданным.

4.1.3 Анализ с использованием алгоритма построения формул.

4.1.4 Применение тематического анализа в ИС.

4.2 Повышение эффективности рубрицирования, основанное на тематическом анализе.

4.2.1 Общие проблемы ручной классификации для больших рубрикаторов.

4.2.2 Использование информеров при решении задач классификации.

4.3 Выводы.

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

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

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

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

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

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

В исследованиях, посвященных применению методов машинного обучения для классификации текстов, применяются универсальные алгоритмы, которые применимы для широкого круга задач анализа и обработки информации. Например, метод SVM (Support Vector Machines, [78, 55]) успешно используется для задач распознавания образов и оценки плотности сред. Для задачи классификации текстов эти методы работают с абстрактной векторной моделью документа и не учитывают особенностей задачи тематической классификации текстов и структуры рубрикатора. Тем не менее, во многих случаях методы машинного обучения дают весьма высокие результаты. Качество рубрикации для систем, основанных на машинном обучении, является довольно высоким для небольших рубрикаторов, и сильно падает с увеличением количества рубрик и усложнением структуры рубрикатора.

Во многих случаях, даже при наличии заранее отрубрицированной коллекции документов, методы машинного обучения неприменимы и используется значительно более трудоемкий инженерный подход [2, 8]. Необходимость применения методов, основанных на знаниях, для больших рубрикаторов — 500 и более рубрик — отмечалась, в частности, нескольких докладах на семинаре по практической классификации текстов в рамках конференции SIGIR-2001 и SIGIR-2002 [71, 59]. Инженерный подход обычно обеспечивает высокое качество рубрицирования и "прозрачность" алгоритма 6 результаты обработки легко интерпретировать (почему такой-то документ был отнесен к рубрике). К сожалению, при использовании инженерного подхода зачастую совсем не используется ресурс, состоящий в наличии коллекции отрубрицированных текстов. Основной проблемой инженерного подхода является высокая трудоёмкость создания системы автоматической классификации (от 1 до 8 человеко-часов на одну рубрику [82, 30]).

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

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

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

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

Содержание диссертации организовано в соответствии с указанными целями:

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

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

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

Экспериментальное исследование на различных коллекциях реальных текстов позволяет утверждать что

1. создаваемые алгоритмом правила описания рубрики соответствуют содержанию рубрики;

2. алгоритм показывает высокое качество классификации текстов (в одном из сравнительных тестов — лучший результат по сравнению с 8 другими алгоритмами).

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

Данные средства внедрены в технологический процесс построения систем классификации текстов проекта Университетская Информационная Система РОССИЯ, разрабатываемого в НИВЦ МГУ (Научно-Исследовательском Вычислительном Центре МГУ им. М.В. Ломоносова).

4.3 Выводы

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

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

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

Кроме того, разработанные средства применяются в качестве эффективного средства поиска и анализа информации в полнотекстовой информационной системе УИС РОССИЯ.

5 Заключение

К основным результатам, полученным автором и описанным в данной диссертации (главы 3 и 4), относятся:

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

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

3. Проведено экспериментальное исследование разработанного алгоритма. Экспериментально доказана высокая эффективность алгоритма и соответствие получаемых формул содержанию рубрики. В экспериментах на коллекции РОМИП'2004 (дорожка тематической классификации Российского семинара по Оценке Методов Информационного Поиска 2004 года) алгоритм построения формул показал лучший результат по сравнению с 8 другими алгоритмами классификации текстов.

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

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

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

По теме диссертационной работы опубликовано 18 печатных работ. Основное содержание диссертации отражено в публикациях [1-8, 10, 11, 18].

Описанные алгоритмы и технологии реализованы и внедрены в технологический процесс построения систем классификации текстов проекта УИС РОССИЯ, разрабатываемого в НИВЦ МГУ.

1. Публикации автора по теме диссертации

2. Агеев M.C. Метод машинного обучения для автоматической классификации текстов. // Труды XXVI Конференции молодых ученых механико-математического факультета МГУ. Москва, Мехмат, МГУ, 2004. (в печати).

3. Ageev M.S., Dobrov B.V. Support Vector Machine Parameter Optimization for Text Categorization Problems. // Вестник Национального Технического Университета «ХПИ» — Харьков, Украина, 2004. — №1 — стр. 3-14128

4. Агеев М.С., Добров Б.В., Лукашевич Н.В., Сидоров А.В. Экспериментальные алгоритмы поиска/классификации и сравнение с «basic line». // Российский семинар по Оценке Методов Информационного Поиска (РОМИП 2004) — Пущино, 2004. — стр. 6289

5. Агеев М.С., Добров Б.В., Лукашевич Н.В., Сложные задачи автоматической рубрикации текстов. // Научный сервис в сети ИНТЕРНЕТ: Труды Всероссийской науч. конф. — Новороссийск, сентябрь 2002.

6. Агеев М.С., Кураленок И.Е. Официальные метрики РОМИП'2004. //Российский семинар по Оценке Методов Информационного Поиска (РОМИП 2004) — Пущино, 2004.

7. Агеев М.С., Добров Б.В., Тематический анализ коллекции документов on-line. // Научный сервис в сети ИНТЕРНЕТ: Труды Всероссийской науч. конф. — Новороссийск, сентябрь 2003. — стр 249-252.

8. Ageev М., Dobrov В. Support Vector Machine Parameter Optimization for Text Categorization Problems. // Information Systems Technology and its Applications (ISTA'2003): Proceedings of International Conference / LNI GI, 2003. —Vol 30 —pp. 165-176.

9. Агеев М.С., Журавлев С.В., Ламбурт В.Г. Подготовка Web-версий традиционных изданий. // Открытые Системы, 2000. — №12

10. Агеев М.С., Журавлев С.В., Карасев О.И., Ламбурт В.Г. Некоторые вопросы автоматизации подготовки публикаций в Интернет // Научный сервис в сети ИНТЕРНЕТ: Труды Всероссийской науч. конф. — Новороссийск, сентябрь 2000

11. М. Ageev. Martin's game: a lower bound for the number of sets. // Theoretical Computer Science, 2002. — V. 289/1 — pp.871-876.1. Активная библиография

12. Айзерман M.A., Браверман Э.М., Розоноер Л.И. Метод потенциальных функций в теории обучения машин. — М.: Наука, 1970.

13. Аношкина Ж.Г. Морфологический процессор русского языка. // Бюллетень машинного фонда русского языка / отв. редактор В.М. Андрющенко — М., 1996. — Вып.З, с.53-57.

14. Антонов А.В., Пример задачи поиска "жизненных историй" — НТИ, Серия 1. —2003. —№7 —С.12-17.

15. Антонов А.В., Козачук М.В., Мешков B.C. Галактика-Зум: Отчет об участии в семинаре РОМИП 2004. //Российский семинар по Оценке

16. Методов Информационного Поиска (РОМИП 2004) — Пущино, 2004. — стр. 133-141

17. Бонгард М.М. Проблема узнавания. — М.: Наука, 1967. — 320 с.

18. Брукинг А. и др. Экспертные системы. Принципы работы и примеры. Пер. с англ.; Под ред. Р.Форсайта. — М.: Радио и связь, 1987.

19. Вагин В.Н., Головина Е.Ю., Загорянская А.А., Фомина М.В. Достоверный и правдоподобный вывод в интеллектуальных системах — М: Физматлит, 2004 — 704 стр.

20. Вайнцвайг М.Н. Алгоритм обучения распознаванию образов "Кора" // Алгоритмы обучения распознаванию образов / Под ред. В.Н. Вапника.

21. М.: Сов. радио, 1973. — стр. 110-116.

22. Вапник В.Н. Восстановление зависимостей по эмпирическим данным.1. М.: Наука, 1979.

23. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем: Учебник для вузов. — СПб.: Питер, 2000. — 384 с.

24. Добров Б.В., Лукашевич Н.В., Автоматическая интеллектуальная обработка текстов на основе тезаурусно организованных знаний // Труды шестой национальной конференции по ИИ (КИИ-98). — 1998.т. II. —с.486-491.

25. Добров Б.В., Лукашевич Н.В., Автоматическая рубрикация полнотекстовых документов по классификаторам сложной структуры // Восьмая национальная конференция по искусственному интеллекту — Коломна, 2002.

26. Добров Б.В., Лукашевич Н.В., Использование тематического представления содержания текста для автоматической обработки документов // V Нац. конф. по искусственному интеллекту. — Казань, 1996.

27. Дюк В., Самойленко A. Data Mining: учебный курс. — изд-во Питер, 2001.

28. Журавлев С.В., Юдина Т.Н., Информационная система РОССИЯ // НТИ. Сер.2. — 1995.— №3.— С.18-20.

29. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации //Проблемы кибернетики, 1978, — вып. 33, — с. 5-68.

30. Загоруйко Н.Г. Прикладные методы анализа данных и знаний — Новосибирск: Изд-во Ин-та математики, 1999. — 270 с.

31. Загорулько Ю.А., Кононенко И.С., Костов Ю.В., Сидорова Е.В. Классификация деловых писам в системе документооборота // Международная конференция ИСТ'2003 "Информационные системы и технологии" — Новосибирск, 2003,

32. Искусственный интеллект. Справочник в трех томах. / под ред. Захарова

33. B.Н., Попова Э.В., Поспелова Д.А., Хорошевского В.Ф. — М.: Радио и связь, 1990. —Т.2

34. Лукашевич Н.В., Автоматическое рубрицирование потоков текстов по общественно-политической тематике // НТИ. Сер.2., 1996. — № 10. —1. C.22—30.

35. Мегапьютер Интеллидженс: Реферирование и классификация текстов (информация на web-сайте компании) http://www.megaputer.ru/doc.php7detail/040923 detail.html

36. И. Кураленок, И. Некрестьянов. Оценка систем текстового поиска. / Программирование. — 28(4), 2002 — стр. 226-242

37. Некрестьянов И.С. Тематико-ориентированные методы информационного поиска: Дис. канд. физ-мат. наук: 05.13.11 / С-Пб. гос. унив. — Санкт-Петербург, 2000.

38. О классификаторе правовых актов: Указ Президента РФ №511 от 15 марта 2000г.

39. Объедков С. А. Алгоритмические аспекты ДСМ-метода автоматического порождения гипотез. / НТИ, Серия 2. — Выпуск 1-2, 1999 — стр. 64-74.

40. Осипова Н. Анализ результатов тестирования алгоритма София при решении задачи классификации коллекции правовых документов. //Российский семинар по Оценке Методов Информационного Поиска (РОМИП 2004) — Пущино, 2004. — стр. 110-118

41. Плешко В.В., Ермаков А.Е., Голенков В.П. RCO на РОМИП 2004. //Российский семинар по Оценке Методов Информационного Поиска (РОМИП 2004) — Пущино, 2004. — стр. 43-61

42. Поспелов Д.А. Становление информатики в России. /В кн. "Очерки истории информатики в России". — Редакторы-составители Д. А. Поспелов и Я. И. Фет. — Новосибирск: Научно-издательский центр ИГГМ СО РАН, 1998

43. Рубашкин В.Ш. Представление и анализ смысла в интеллектуальных информационных системах — М.: Наука, 1989. — 189 с.

44. Рыбинкин В.В. Система рубрикации данных "Синдбад". //Российский семинар по Оценке Методов Информационного Поиска (РОМИП 2004) — Пущино, 2004. — стр. 90-99

45. Труды РОМИГГ2003 — НИИ Химии СПбГУ /Под ред. И.С.Некрестьянова — Санкт-Петербург, 2003 — 132 с.

46. Хант Э. Искусственный интеллект. — М.: Мир. 1978. — Часть 2. Распознавание образов.

47. Чесноков С.В. Детерминационный анализ социально-экономических данных. — М:, "Наука", 1982.

48. Beuster G. MIC — A System for Classification of Structured and Unstructured Texts. Diploma Thesis. — University Koblenz, 2001.

49. Burges C.J.C. A tutorial on support vector machines for pattern recognition. // Data Mining and Knowledge Discovery, — 2(2):955-974,1998.

50. Debole F., Sebastiani F., An Analysis of the Relative Hardness of Reuters-21578 Subsets // Journal of the American Society for Information Science and Technology, 2004

51. Dumais S., Piatt J„ Heckerman D., Sahami M. Inductive learning algorithms and representations for text categorization. // In Proc. Int. Conf. on Inform, and Knowledge Manage., 1998.

52. Dumais S., Lewis D., Sebastiani F. Report on the Workshop on Operational Text Classification Systems (OTC-02) // SIGIR-2002 — Tampere, Finland, 2002

53. Hayes P.J., Weinstein S.P. Construe: A System for Content-Based Indexing of a Database of News Stories //Proceedings of the Second Annual Conference on Innovative Applications of Intelligence, 1990.

54. Haykin, S. Neural Networks: A Comprehensive Foundation. — New York: Macmillan College Publishing, 1994

55. Joachims T. Text Categorization with Support Vector Machines: Learning with Many Relevant Features. //Proceedings of ECML-98, 10th European Conference on Machine Learning — 1998.

56. Joachims T. A Probabilistic Analysis of the Rocchio Algorithm with TFIDF for Text Categorization. //Proceedings of ICML-97, 14th International Conference on Machine Learning. — 1996.

57. Joachims T. Making Large-Scale SVM Learning Practical. Advances in Kernel Methods / Support Vector Learning, Sch lkopf В., Burges C., Smola A. (ed.), — MIT-Press, 1999.

58. Joachims T. Estimating the Generalization Performance of a SVM Efficiently. //Proceedings of the International Conference on Machine Learning, — Morgan Kaufman, 2000.

59. Legislative Indexing Vocabulary — Congressional Research Service. The Library of Congress. Twenty-first Edition, 1994. — 546 p.

60. Lewis D. Applying Support Vector Machines to the TREC-2001 Batch Filtering and Routing Tasks. Proceedings of TREC-2001 conference.

61. Lewis D. Feature Selection and Feature Extraction for Text Categorization. // Proceedings of the DARPA Workshop on Speech and Natural Language. — Harriman, New York, 1992. — pp. 212-217

62. Lewis D. Reuters-21578 text categorization test collection. Distribution 1.0 http://www.daviddlewis.eom/resources/testcollections/reuters21578/readme.t xt

63. Lewis D., Sebastiani F. Report on the Workshop on Operational Text Classification Systems (OTC-Ol) // SIGIR-2001 — New Orleans, 2001

64. Marshall R,J. Generation of Boolean classification rules. // Proceedings of Computational Statistics 2000 — Utrecht, The Netherlands, / eds Bethlehem and PGM van der Heijden, — Springer-Verlag, Heidelberg, 2000 — pp. 355360.

65. Quinlan J.R. C4.5 Programs for machine learning. — Morgan Kaufmann, — San Mateo, Californie, 1993.74. van Rijsbergen C.J. Information Retrieval. — Butterworth's and Co. — London, 1979 — 2nd edition.

66. Salton G, Buckley C. Term-Weighting Approaches in Automatic Text Retrieval. / Information Processing and Management, —1988 — pp. 513-523.

67. Teoma: Adding a New Dimension to Search: The Teoma Difference is Authority http://sp.teoma.com/docs/teoma/about/searchwithauthoritv.html

68. The Twelfth Text Retrieval Conference (TREC 2003). Appendix 1. Common Evaluation Measures, http://trec.nist.gov/pubs/trec 12/appendices/measures.ps

69. Vapnik V. The Nature of Statistical Learning Theory. — Springer-Verlag — New York, 1995.

70. Yang Y. An Evaluation of Statistical Approaches to Text Categorization. / Journal of Information Retrieval, 1999 — V.l — pp. 67-88.

71. Yang Y., Liu X. A re-examination of text categorization methods. // Proc. of Int. ACM Conference on Research and Development in Information Retrieval (SIGIR-99), 1999 —pp. 42-49.

72. Yang Y., Pedersen J. A comparative study on feature selection in text categorization. //In: Proc. of ICML-97, 14th International Conf. On machine Learning — Nashville, USA, 1997. — pp. 412-420.

73. Wasson M. Classification Technology at LexisNexis. // SIGIR 2001 Workshop on Operational Text Classification.