Анализ результатов тестирования алгоритма 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.
Структурно ИПС состоит из следующих элементов:
- сервера базы данных
- WEB сервера
- сервера приложений
- клиентских рабочих мест
Документы и вся информация по кластеризации и поиску хранятся в базе данных (БД). Система управления БД (СУБД) обеспечивает хранение документов, реализацию алгоритмов кластеризации и поиска документов, доступ к БД пользователей системы.
В ИПС используется СУБД MS SQL Server 2000.
WEB сервер обеспечивает доступ пользователей к ИПС через Интернет или Интранет.
Клиентское рабочее место обеспечивает интерфейс для доступа пользователя к ИПС.
Сервер приложений обеспечивает работу клиентских рабочих мест. При реализации клиентских рабочих мест используются средства разработки C# и технология ASP.
БД ИПС содержит:
- документы
- словарь коллекции
- темы классификации
- контексты слов
- контексты тем
- кластеры
В ИПС решаются следующие задачи:
- кластеризация документов
- классификация документов
- прямой поиск
- контекстный поиск
- поиск близких документов для данного документа
Исходными данными для кластеризации являются документы и словарь документов. По исходным данным строится таблица контекстов слов. По таблице контекстов вычисляется энтропия каждого слова и отбираются слова с минимальной энтропией - узкоспециализированные термины, на основе которых и строятся кластеры.
Далее вычисляются расстояния между найденными узкоспециализированными терминами и всеми документами из коллекции. На основании расстояний происходит разбиение документов по кластерам
Для классификации коллекции документов с помощью обучающих выборок строятся контексты заданных тем. Множество документов разбивается на кластеры. Каждому кластеру ставится в соответствие одна или несколько тем.
На данный момент времени реализованы алгоритмы кластеризации, классификации и поиска в БД и толстый клиент. Разработка системы проводилась на локальном компьютере, выступавшем в роли сервера базы данных. На него же был установлен толстый клиент. Тонкий клиент находится в стадии разработки.
3. Методика тестирования
Целями тестирования являлись:
- проверка корректности и эффективности работы алгоритма SOPHIA
- сравнительная оценка различных методов, применяемых для кластеризации и классификации документов
- оценка скорости работы различных версий алгоритма SOPHIA
Для тестирования алгоритма использовалась коллекция русскоязычных правовых документов. Объем коллекции составляет 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.
В данный момент ведется разработка усовершенствованного текстового обработчика на основе алгоритма Портера. Также разрабатываются новые алгоритмы поиска и классификации коллекций документов.