Выделение терминов из документов с заданным тематическим делением Голомазов Денис Дмитриевич Механико - математический факультет МГУ 5 курс 15 апреля 2008 года

План доклада Постановка задачи Алгоритм Brainsterm Анализ эффективности Результаты

22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 3 Задача Дано : Коллекция документов, разделенных по тематике на рубрики. Требуется : Выделить из этих документов пары слов, являющиеся терминами.

22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 4 Основное определение Термин – пара слов, характеризующая документ, в котором она встречается, с точки зрения принадлежности к одной или нескольким рубрикам. Важно : Свойство « быть термином » зависит от контекста имеющихся рубрик.

22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 5 Примеры « Доказательство теоремы » Рубрики : наука, искусство, спорт. Термин « Доказательство теоремы » Рубрики : алгебра, геометрия, топология. Не термин

22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 6 Зачем нужны термины Термины – описание документа. В данной работе термины – формальное относительное описание документа. Краткое Существенное Ранжированное Относительное описание позволяет учесть специфику задачи.

Векторная модель представления документов Документы отображаются в точки векторного пространства. Расстояние между точками : Основной вопрос – выбор базиса.

Выбор базиса Полный базис – TF-IDF Сокращенный базис : Удаление стоп - слов Базис не из слов - LSI Выделение значимых слов - Brainsterm

22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 9 Исходные данные Таблица чисел из 4 колонок : Номер рубрики Номер документа Номер абзаца Номер слова

22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 10 Модель : множества – множество рубрик – множество документов – множество абзацев – множество слов, включая – пустое слово – множество пар слов Документ – отображение Абзац – отображение

22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 11 Модель : отображения ( каждый документ относится к некоторой рубрике ) ( каждый абзац относится к некоторому документу ) – проекции пары – число вхождений пары в документ – длина документа – число документов в рубрике среднее значение функции на множестве –

22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 12 Вес пары в рубрике

22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 13 Обоснование выбора функций

22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 14 Алгоритм Brainsterm : четыре критерия Пространственный критерий Критерий частотности Критерий характерности Критерий значимых рубрик На каждом из четырех шагов выбирается подмножество множества, полученного на предыдущем шаге, с помощью некоторого правила. На первом шаге выбор производится из множества ( пар слов ), т. е.. Множество есть результат – все пары, являющиеся терминами.

22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 15 I. Пространственный критерий Смысл критерия : отбираются пары слов, находящихся в одном абзаце на расстоянии, не превышающем константы.

22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 16 II. Критерий частотности Смысл критерия : отбираются пары слов, встречающиеся во всей коллекции не менее, чем раз.

22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 17 III. Критерий характерности Пусть - некоторое множество неотрицательных действительных чисел, не равных одновременно нулю. Определим функцию Пусть. Тогда

22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 18 Функция характерности

22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 19 IV. Критерий значимых рубрик Пусть Определим отображение Тогда Смысл критерия : Отбираются пары, у которых среди значимых рубрик найдется рубрика, в которой сумма весов каждого из слов пары превышает вес пары не более, чем в раз.

22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 20 Реализация С ++ Большие объемы данных Итеративность

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

Анализ эффективности : алгоритмы Помимо алгоритма Brainsterm, в сравнении принимали участие следующие методы : 1.TF-IDF (term frequency - inversed document frequency) 2.LSI (latent semantic indexing): o LSI with tf-idf matrix o LSI with frequency matrix o LSI with boolean matrix

Анализ эффективности : методика Каждый из рассматриваемых алгоритмов предоставляет способ отображения множества документов в точки пространства некоторой размерности. Множество документов делится на две группы : обучающую выборку и тестовую выборку. С помощью обучающей выборки производится построение базиса целевого пространства и отображение документов обучающей и тестовой выборок в это пространство. Проводится анализ точек - образов документов из тестовой выборки.

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

2. Кластеризация Полученные тестовые точки естественным образом формируют кластеры ( на основе исходных рубрик ). С помощью стандартного алгоритма оценивается качество кластеризации. Суть алгоритма : расчет двух величин - суммарного квадратичного внутриклассового разброса точек и общего квадратичного разброса точек вокруг центра масс. Итоговый показатель есть отношение этих величин. Чем он меньше, тем алгоритм эффективней.

22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 26 Тестирование 1.4 млн. слов 7 тыс. документов 33 рубрики Параметры Brainsterm -1: ( фильтр отключен ) Параметры Brainsterm -2: 1 1 ( фильтр отключен ) ( фильтр отключен )

Результаты : классификация

Результаты : кластеризация

22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 22 ноября 2012 г. 29 Итоги работы Разработан алгоритм Brainsterm Написана программа, полностью реализующая его Разработана методика анализа эффективности Написана программа, реализующая методику Проведено формальное сравнение эффективности с популярными алгоритмами Результаты доказывают практическую значимость алгоритма Brainsterm

Дальнейшая работа Варьирование параметров в зависимости от размерности Использование лингвистических методов Соединение алгоритмов Brainsterm и LSI Расширение сферы применения алгоритма

15 апреля 2008 года Спасибо за внимание !