zhChinese    enEnglish
  ПМ-ПУ  » Структура » Преподаватели » Добрынин В. Ю. » Проект SOPHIA

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

Алгоритм SOPHIA разработан в рамках совместного проекта, выполняемого факультетом Прикладной Математики - Процессов Управления Санкт Петербургского Государственного Университета и Лабораторией инженерии знаний (NIKEL) университета Ольстера (University of Ulster, UK). Подробное описание алгоритма и результаты некоторых экспериментов приведены в статье Dobrynin V., Patterson D, Rooney N., Contextual Document Clustering, Lecture Notes in Computer Science ╧ 2997, Advances in Information Retrieval, 2004, p.167-180. Далее мы проведем анализ полученных с помощью алгоритма результатов при классификации русскоязычной коллекции документов по заранее заданным темам. В качестве исходных данных для тестирования были использованы коллекция правовых документов, категории документов и обучающая выборка для каждой категории. Для разбиения документов по категориям применялись 3 различные версии алгоритма. Разработку и тестирование системы в 2004 г. проводила Осипова Наталия, студентка 5-ого курса СПбГУ факультета ПМ-ПУ. Тестирование результатов работы алгоритма проводилось Российским семинаром по Оценке Методов Информационного Поиска (РОМИП).

1. Алгоритм SOPHIA

Алгоритм SOPHIA обеспечивает разбиение множества документов на узкие по смыслу кластеры. Он состоит из следующих шагов:

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

Шаг 2. Кластеризация документов.

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

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

2. Структура и функциональные возможности ИПС SOPHIA

На основе алгоритма SOPHIA была реализована информационно поисковая система (ИПС) SOPHIA.

Структурно ИПС состоит из следующих элементов:

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

В ИПС используется СУБД MS SQL Server 2000.

WEB сервер обеспечивает доступ пользователей к ИПС через Интернет или Интранет.

Клиентское рабочее место обеспечивает интерфейс для доступа пользователя к ИПС.

Сервер приложений обеспечивает работу клиентских рабочих мест. При реализации клиентских рабочих мест используются средства разработки C# и технология ASP.

БД ИПС содержит:

В ИПС решаются следующие задачи:

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

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

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

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

3. Методика тестирования

Целями тестирования являлись:

Для тестирования алгоритма использовалась коллекция русскоязычных правовых документов. Объем коллекции составляет 65000 документов. При этом размер отдельных текстов в 85% случаев не превышает 1000 слов. В состав коллекции входили законодательные документы, относящиеся к различным тематикам.

Первый этап тестирования заключался в классификации документов по заданным темам. Каждому документу коллекции нужно было поставить в соответствие не более 5-ти тем. Для каждой категории существовал предопределенный набор релевантных для данной категории документов - обучающая выборка. Объем обучающей выборки составлял 5% от объема всей коллекции. Классификация проводилась с помощью трех версий алгоритма SOPHIA. Было применено два метода кластеризации и два метода классификации документов.

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

При кластеризации применялось два метода уменьшения количества обрабатываемых слов. Первый метод (А1) заключался в том, что из рассмотрения были исключены слова, которые встречались более чем в 1000 документов, при объеме коллекции в 65000, т.е. в 1.5% всех документов. Такой прием обосновывается тем, что часто встречающиеся слова не могут быть узкоспециализированными, они усложняют дальнейшее вычисление энтропии слов и расстояний между узкими контекстами и документами. Границы рассматриваемых слов обычно определяются в зависимости от размера коллекции, количества слов и документов. Сужение словаря по этому методу позволило уменьшить время построения кластеров в 10 раз.

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

Для классификации документов применялось два метода.

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

По второму методу (В2) вычислялось расстояние между кластерами и контекстами тем. Далее кластеру соотносилось 1-3 наиболее близких ему темы.

Таким образом для тестирования использовались три версии ("дорожки") алгоритма.

В первой (textan) и второй (docsan) версиях алгоритма кластеризация документов проводилась по А1.

Классификация первой версии (textan) проводилась по методу В1, а второй версии (docsan) - по методу В2.

В третьей версии (dicsan) кластеризация проводилась по методу А2, классификация по методу В2.

4. Анализ результатов тестирования

Тестирование результатов классификации документов проводилось независимыми экспертами по методике и с использованием программного обеспечения РОМИП.

Из всего множества тем случайным образом выбиралось некоторое подмножество категорий. С помощью инструмента оценки РОМИП результаты, полученные экспертами, сравнивались с результатами, полученными различными ИПС. Были получены оценки (метрики) таких параметров системы как точность и полнота, и была построена мера F, объединяющая метрики полноты и точности.

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

Были получены сравнительные результаты классификации коллекции как дорожек относительно друг друга, так и относительно других систем. Результаты приведены на графиках (1,2,3). Прочие ИПС, участвовавшие в классификации документов, обозначены как 'xxxx'.



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

Категория
1Семейное право
2Наследственное право
3Водное хозяйство
4Общественное питание
5Бытовое обслуживание населения
6Арендные отношения
7Международное космическое право
8Территория в международном праве
9Субъекты внешнеэкономических отношений
10Внешнеэкономические сделки
11Зоны свободной экономической торговли. Таможенные союзы

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

Полнота
 1234567891011
textan33343560462627987525100
docsan100.23400.90302
dicsan004.32.3050.98300.8
xxxx55867519595180041820
xxxx213922215601.4050
xxxx404316112523101.41.250
xxxx2342.51.11870.901.2100
xxxx2.70001.5000000
xxxx2.20001.5000000
xxxx372112221827510000
Точность
 1234567891011
textan252231124425181613919
docsan7011170011015027
dicsan00190830203710014
xxxx6025552640371000100570
xxxx5135422931113151150
xxxx8300330000000
xxxx55206419472819023140
xxxx665684100100100025050
xxxx6600330000000
xxxx51218522400270000
Метрика F
 1234567891011
textan2827331932262128231332
dicsan007090114501
docsan200.470010604
xxxx45392327276142250
xxxx3474211228102170
xxxx50020000000
xxxx55336929494331029240
xxxx324642612202090
xxxx40020000000
xxxx43212119320360000

Процент верно найденных первым методом (textan) документов составляет около 50%, а у второго (docsan) и третьего (dicsan) методов - 1 - 4%. Так как методы кластеризации первого и второго методов были одинаковы, то отсюда следует, что на результат в значительной степени влияет используемый метод классификации. Для данной коллекции первый метод классификации оказался более эффективным.

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

Кроме ИПС SOPHIA в семинаре РОМИП принимали участие следующие системы: ML Классификатор 2.0, mnogoSearch, RCO, Sophia, Золушка, ИС "Кодекс", Ментал, Поисково-аналитическая система "Галактика-Zoom", Синдбад, УИС РОССИЯ (НИВЦ МГУ + АНО ЦИИ), Яндекс.Server 3.2.

Все результаты опубликованы в сборнике РОМИП. Электронная версия: http://romip.narod.ru/romip2004/index.html

Заключение

Тестирование показало целесообразность дальнейшего развития математического и программного обеспечения ИПС SOPHIA.

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