Автоматическое формирование рубрикатора полнотекстовых документов Пескова Ольга Вадимовна Московский государственный технический университет им. Н.Э.Баумана 2008

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

Механизм применения средства тематической навигации

Требования к виду искомой навигационной схемы Рубрикатор, унаследовавший основные характеристики от традиционного предметного рубрикатора библиотеки МГТУ им. Н. Э. Баумана: иерархические связи между рубриками (не более 2-3 уровней); родственные связи между рубриками (типа «см. также»); краткое описание и список ключевых слов.

Способ представления рубрикатора, где – это множество вершин – множество рёбер графа, Граф G* является многоуровневым и содержит подграфы Каждая выявленная группа документов должна иметь название и список ключевых слов. графа, отражающих кластеры документов, полученные при кластеризации коллекции полнотекстовых документов на заданном уровне иерархии; Рубрикатор в виде графа отражающих как иерархические так и родственные связи.

Функциональная схема автоматического формирования рубрикатора

Выбор подхода к формированию образов документов

Предложенный алгоритм формирования образов документов Построение словаря признаков (одиночных слов) всех документов (морфологический анализ – стеммер М.Портера). Принудительная редукция признаков: удаление стоп-слов; Удаление слов по критерию документальной частоты с порогами t DF min и t DF max, где t DF min = и t DF max =. Взвешивание признаков документов по схеме TFIDF. Принудительная редукция признаков (продолжение): для каждого документа в отдельности удаление некоторой доли t WP самых маловесомых признаков, где t WP =0.60. Избирательная редукция: удаление из образов некоторых документов тех признаков, что обладают слабой различительной способностью для представления некоторого тематического класса.

Иллюстрации к предположению об избирательной редукции (1)

Иллюстрации к предположению об избирательной редукции (2) α β

Алгоритм избирательной редукции

Выбор алгоритма кластеризации

Модифицированный алгоритм кластеризации документов

Дополнение кластерной структуры до искомого рубрикатора

Тестовые коллекции 1)On-line библиотека CITFORUM ( наработка эмпирических сведений к методу формирования рубрикатора и оценка его эффективности (CL1572). 2)Ресурсы библиотеки МГТУ им. Н. Э. Баумана – коллекция авторефератов диссертаций – апробация системы формирования рубрикатора (TAL234). 3)Коллекция нормативно-правовых документов законодательства Российской Федерации, сформированная в 2004 году для выполнения заданий в рамках РОМИП (Legal2004_5000). Отобраны те документы, для которых есть информация о их принадлежности рубрикам, документов. 5000

Меры качества кластеризации Внешние меры: автоматическое сравнение полученного разбиения документов с «эталонным» разбиение на кластеры (рубрики). Внутренние меры: автоматическая оценка свойств отделимости и компактности полученного разбиения документов.

Внешние меры качества кластеризации Полнота Точность F1-мера Ошибка Аккуратность и др.

Внутренние меры качества кластеризации Оценка иерархического разбиения: Кофенетический коэффициент корреляции (CPCC) Оценка плоского разбиения: Индекс Данна (Dunn, DI) Индекс Девиса-Булдина (Davies- Bouldin, DB) Индекс Калинского и Гарабача (Calinski и Harabasz, CH) I-индекс (I-index)

Испытания алгоритма формирования образов (на CL1572) (1)(2)(3) Внешние меры качества кластеризации MicroF 1 -мера0,1900,4660,505 Error0,5060,1010,084 Внутренние меры качества кластеризации |CPCC|0,1880,5080,580 DI0,5390,5980,577 DB0,1960,2580,180 CH3,0866,36877,226 I-Index0,00140, ,0018 Скорость кластеризации Время (с) Оценка способа формирования образов. (1) – без редукции, (2) – с принудительной редукцией, (3) – с принудительной и избирательной редукцией

Испытание модифицированного алгоритма кластеризации (на CL1572) Оценка алгоритма кластеризации: (1) – иерархический агломеративный алгоритм (усечение дерева при пороге меры близости – 0,20), (2) – исходный алгоритм послойной кластеризации (два уровня при порогах меры близости {0,40; 0,20}), (3) – модифицированный алгоритм послойной кластеризации (два уровня при порогах меры близости {0,40; 0,20}). (1)(2)(3) Внешние меры качества кластеризации MicroF 1 -мера0,218380,113210,25823 MacroF 1 -мера0,109980,065130,14383 Error0,057410,307990,03439 Внутренние меры качества кластеризации CPCC-0,4642-0,1399-0,3553 DI0,5980,3780,500 DB0,3940,0530,076 CH13,5052,7466,278 I-Index0, , , Скорость кластеризации Время (с)

Пример интерфейса навигации по подмножеству CL1572

Испытание модифицированного алгоритма кластеризации (на TAL234) Ошибка автоматической классификации на TAL234: 3,2% - в сравнении с классификацией авторефератов по УДК; 13,6% - в сравнении с областью знания по номенклатуре ВАК, что объясняется тематическим перекрытием укрупнённых направлений, по которым осуществляется подготовка и защита диссертаций.

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

Испытания системы на Legal2004_5000 (2) Оценка кластеризации модифицированным алгоритмом (Legal2004_5000): (1) – с принудительной редукцией, (2) – с принудительной и избирательной редукцией (порог меры близости = 0,60).

Испытания системы на Legal2004_5000 (3) Количественные характеристики пространства признаков

Дальнейшие планы Закончить эксперименты на 5000 документов Провести исследования на документов Получить основания для выбора дальнейшего пути развития метода формирования рубрикатора

Вопросы