Анализ текстовых документов для извлечения тематически сгруппированных ключевых терминов

Мария Гринева, Максим Гринев, Дмитрий Лизоркин
Труды Института системного программирования РАН

АннотацияАннотация (от лат.annotatio— замечание) или резюме (от фр.rsum — «сокращённый»)— краткая характеристика издания: рукописи, монографии, статьи или книги. Аннотация показывает отличительные особенности и достоинства издаваемого произведения, помогает читателям сориентироваться в их выборе.. В статье предлагается новый метод извлечения ключевых терминов из текстовых документов. В качестве важной особенности метода мы отмечаем тот факт, что результатом его работы являются группы ключевых терминов; при этом термины из каждой группы семантически связаны одной из основных тем документа. Метод основан на комбинации следующих двух техник: мера семантической близости терминов, посчитанная с использованием Википедии; алгоритм для обнаружения сообществ в сетях. Одним из преимуществ нашего метода является отсутствие необходимости в предварительном обучении, поскольку метод работает с базой знаний Википедии. Экспериментальная оценка метода показала, что он извлекает ключевые термины с высокой точностью и полнотой.

Содержание

1. Введение

2. Близкие работы

3. Метод извлечения ключевых терминов

3.1. Извлечение терминов-кандидатов

3.2. Разрешение лексической многозначности терминов

3.3. Построение семантического графа

3.4. Обнаружение сообществ в семантическом графе

3.5. Выбор подходящих сообществ

4. Экспериментальная оценка

4.1. Оценка полноты выделенных ключевых терминов

4.2. Оценка точности выделенных ключевых терминов

4.3. Пересмотр оценки полноты и точности

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

Литература

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

Ключевыми терминами (ключевыми словами или ключевыми фразами) являются важные термины в документе, которые могут дать высокоуровневое описание содержания документа для читателя. Извлечение ключевых терминов является базисным этапом для многих задач обработки естественного языка, таких как классификация документов, кластеризацияКластерный анализ (англ.Data clustering)— задача разбиения заданной выборки объектов (ситуаций) наподмножества, называемые кластерами, так, чтобы каждый кластер состоял изсхожих объектов, аобъекты разных кластеров существенно отличались. Задача кластеризации относится к статистической обработке, а также к широкому классу задач обучения без учителя. Кластерный анализ— это многомерная статистическая процедура, выполняющая сбор данных, содержащих информацию о выборке объектов, и затем упорядочивающая объекты в сравнительно однородные группы (кластеры)(Q-кластеризация, или Q-техника, собственно кластерный анализ). Кластер— группа элементов, характеризуемых общим свойством, главная цель кластерного анализа— нахождение групп схожих объектов в выборке (примечание 1). Спектр применений кластерного анализа очень широк: его используют в археологии, медицине, психологии, химии, биологии, государственном управлении, филологии, антропологии, маркетинге, социологии и других дисциплинах. «Тематика исследований варьирует от анализа морфологии мумифицированных грызунов в Новой Гвинее до изучения результатов голосования сенаторов США, от анализа поведенческих функций замороженных тараканов при их размораживании до исследования географического распределения некоторых видов лишая в Саскачеване» (примечание 1). Однако универсальность применения привела к появлению большого количества несовместимых терминов, методов и подходов, затрудняющих однозначное использование и непротиворечивую интерпретацию кластерного анализа. документов, суммаризация текста и вывод общей темы документа [7]. В этой статье мы предлагаем метод для извлечения ключевых терминов документа, используя Википедию в качестве ресурса, насыщенного информацией о семантической близости терминов.

Википедия (www.wikipedia.org) – свободно распространяемая энциклопедия, на сегодняшний день являющаяся самой большойГосударственный академический Большой театр России (ГАБТ), Государственный академический театр оперы и балета России, или просто Большой театр— один из крупнейших в России и один из самых значительных в мире театров оперы и балета. Расположен в центре Москвы, на Театральной площади. энциклопедией в мире. Она содержит миллионы«Миллионы» — кинофильм. Экранизация произведения, автор которого — Ренцо Барбьери. Не рекомендуется просмотр детям и подросткам моложе 16 лет. статей, доступных на нескольких языках. В сентябре 2008 года Википедия содержит более 2.5 миллионов статей (более 6 миллионов, если считать перенаправляющие страницы, представляющие синонимы заголовка основной статьи). Обладая огромной сетью ссылок между статьями, большим числом категорий, перенаправляющих страниц (redirect pages) и страниц для многозначных терминов (disambiguation pages), Википедия представляет собой исключительно мощный ресурсРесурсы— всё, что необходимо человеку (физическому лицу) и организации (в том числе юридическому лицу) для достижения цели, для удовлетворения собственных потребностей и потребностей субъектов или объектов внешней среды. Ресурсы могут быть трудовые, информационные, материальные, финансовые. для нашей работы и для многих других приложений обработки естественного языка и информационного поиска.

В основе нашего метода лежит использование следующих двух техник: мера семантической близости, посчитанная по Википедии, и алгоритмАлгоритм, от имени учёного аль-Хорезми (перс. [al-Khwrazm])— точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что работа каких-то инструкций алгоритма может быть зависима от других инструкций или результатов их работы. Таким образом, некоторые инструкции должны выполняться строго после завершения работы инструкций, от которых они зависят. Независимые инструкции или инструкции, ставшие независимыми из-за завершения работы инструкций, от которых они зависят, могут выполняться в произвольном порядке, параллельно или одновременно, если это позволяют используемые процессор и операционная система. анализа сетей, а именно, алгоритм Гирвана-Ньюмана для обнаружения сообществ в сетях. Ниже мы дадим краткое описание этих техник.

Установление семантической близости концепций в Википедии является естественным шагом на пути к построению инструмента, полезного для задач обработки естественного языка и информационного поиска. За последние три года появилось порядочное количество работ по вычислению семантической близости между концепциями с использованием различных подходов [13, 14, 4, 19, 21]. Работа [14] дает развернутый обзор многих существующих методов подсчета семантической близости концепций с использованием Википедии. Хотя метод, описываемый в нашей работе, не устанавливает каких-либо требований к способу определения семантической близости, эффективность работы метода зависит от качества работы выбранного метода подсчета семантической близости. Для экспериментов, описанных в этой работе, мы использовали метод подсчета семантической близости, описанный в работе Д. Турдакова и П. Велихова [21].

Зная семантическую близость терминов, мы можем построить семантическийСемантика в программировании— дисциплина, изучающая формализации значений конструкций языков программирования посредством построения их формальных математических моделей. В качестве инструментов построения таких моделей могут использоваться различные средства, например, математическая логика, -исчисление, теория множеств, теория категорий, теория моделей, универсальная алгебра. Формализация семантики языка программирования может использоваться как для описания языка, определения свойств языка, так и для целей формальной верификации программ на этом языке программирования. граф для всех терминов обрабатываемого документа. Семантический граф представляет собой взвешенный граф, в котором узлами являются термины документа, наличие ребра между парой терминов означает, что эти два термина семантически близки, весом ребра является численное значение семантической близости этих двух терминов. Мы заметили, что граф, построенный таким образом, обладает важным свойством: семантически близкие термины «сбиваются» в плотные подграфы, в так называемые сообщества, наиболее массивные и сильно связанные подграфы, как правило, соотносятся с главными темами документа, и термины, входящие в такие подграфы, являются ключевыми для данного документа. Новшество нашего подхода состоит в применении алгоритма обнаружения сообществ в сетях, который позволяет нам выявить тематические группы терминов, и затем выбрать из них наиболее плотные. Такие наиболее плотные группы терминов являются результатом работы метода – тематически сгруппированными ключевыми терминами.

Задача анализа структуры сетей и обнаружения сообществ в них на сегодняшний день хорошо изучена. Было предложено много алгоритмов, которые с успехом применялись для анализа социальных сетей [22], сетей цитирования научных статей [16, 3], сетей покупок товаров крупных Интернет-магазинов таких как Amazon [1], биохимических сетей [6] и многих других. В то же время авторам данной работы неизвестны примеры применения таких алгоритмов к сетям, построенным на основе Википедии. В нашем методе используется алгоритм, предложенный М. Ньюманом и
М. Гирваном [15]. Существуют работы, показывающие, что данный алгоритм является высокоэффективным при анализе как синтетических сетей, так и сетей реального мира.

2. Близкие работы

В области статистической обработки естественного языка существуют классические подходы к извлечению ключевых терминов: tf.idf и анализ колокаций (collocation analysis) [7]. Tf.idf (term frequency-inverse document frequency) является популярной метрикой при решении задач информационного поиска и анализа текста [17]. Tf.idf представляет собой статистическую меру того, насколько терминТермин (от лат.terminus — предел, граница) — слово или словосочетание, точно и однозначно именующее понятие и его соотношение с другими понятиями в пределах специальной сферы. Термины служат специализирующими, ограничительными обозначениями характерных для этой сферы предметов, явлений, их свойств и отношений. В отличие от слов общей лексики, которые зачастую многозначны и несут эмоциональную окраску, термины в пределах сферы применения однозначны и лишены экспрессии. важен в документе, который является частью коллекции документов. С использованием Tf.idf важность термина пропорциональна количеству встречаемости термина в документе и обратно пропорциональна количеству встречаемости термина во всей коллекции документов. В то время как tf.idf используется для извлечения ключевых терминов, состоящих из одного слова, анализ коллокаций используется для обнаружения фраз.

Подход Tf.idf, дополненный анализом коллокаций, позволяет извлечь ключевые фразы. Оба подхода требуют наличия некоторой коллекции документов для сбора статистики; такую коллекцию документов называют обучающим множеством. Качества работы подходов зависит от того, насколько удачно подобрано обучающее множество.

Преимуществом данных подходов является простота реализации и удовлетворительное качество работы, когда обучающее множество хорошо подобрано. Благодаря этим преимуществам данные подходы широко распространены на практике. Мы бы хотели отметить интересный факт: существуют работы [9, 11, 2, 8], где Википедия использовалась в качестве обучающего множестваМножество— один из ключевых объектов математики, в частности, теории множеств и логики., и было показано, что Википедия может служить хорошим обучающим множеством для многих практических приложений.

Существует альтернативный класс подходов к решению задач обработки естественного языка (извлечение ключевых слов является одной из таких задач), и данная работа принадлежит к этому классу подходов. Подходы этого класса основаны на использовании знании о семантической близости терминов. Семантическая близость терминов может быть получена при помощи словаря или тезауруса (например, WordNet [12]), но нас интересуют работы, использующие семантическую близость терминов, полученную по Википедии.

Посчитать семантическую близость терминов с использованием Википедии можно двумя способами: используя гипертекстовые ссылки между статьями Википедии, которые соответствуют данным терминам [13, 14, 21], или измеряя косинус угла между векторами, построенными по текстам соответствующих статей Википедии [4]. Существует множество работ, где семантическая близость терминов, полученная по Википедии, используется для решения следующих задач обработки естественного языка и информационного поиска: разрешение лексической многозначности термина [10, 18, 8, 21], выведение общей темы документа [20], категоризацияКлассификация (классифицирование) (от лат. classis- разряд и facere-делать) — особый случай применения логической операции деления объема понятия, представляющий собой некоторую совокупность делений (деление некоторого класса на виды, деление этих видов и т.д.). Классификация предназначена для постоянного использования в какой-либо науке или области практической деятельности (например, классификация животных и растений). Обычно в качестве основания деления в классификации выбирают признаки, существенные для данных предметов. В этом случае классификация (называемая естественной) выявляет существенные сходства и различия между предметами и емеет познавательное значение. В других случаях, когда цель классификации состоит лишь в систематизации предметов, в качестве основания выбираются признаки, удобные для этой цели, но несущественные для самих предметов (например, алфавитные каталоги). Такие классификации называют искусственными. Наиболее ценными являются классификации, основанные на познании законов связи между видами, перехода от одного вида к другому в процессе развития (такова, например, классификация химических элементов, созданная Менделеевым). Классификация по существенным признакам называется типологией; она основана на понятии типа, как единицы расчленения изучаемой реальности, конкретной идеальной модели исторически развивающихся объектов (биологические, языковые и т.п. типологии). Всякая классификация является результатом некоторого огрубления дейтвительных граней между видами, ибо они всегда условны и относительны. С развитием знаний происходит уточнение и изменение классификаций. [5], разрешение кореферентности (coreference resolution) [19].

Авторам данной статьи неизвестны работы, где семантическая близость терминов использовалась бы для извлечения ключевых терминов документа, однако, работа [5] является наиболее близкой к нашей. В работе [5] решается задача категоризации текста, при этом из терминов текста строится семантический граф, аналогично тому, как мы предлагаем в данной работе. Идея применения алгоритмов анализа графов в этой работе проявляется в простой форме: выбираются наиболее центральные термины в графе при помощи алгоритма оценки центральности (betweenness centrality), далее эти термины используются для категоризации документа.

Мы выделяем следующие преимущества нашего метода:

• Наш метод не требует обучения, в отличие от описанных традиционных подходов. Благодаря тому, что Википедия является крупномасштабной и постоянно обновляемой миллионами людей энциклопедией, она остается актуальной и покрывает много специфических областей знаний. Таким образом, практически любой документ, большая часть терминов которого описана в Википедии, может быть обработан нашим методом.
• Ключевые термины сгруппированы по темам, и метод извлекает столько различных тематических групп терминов, сколько различных тем покрывается в документе. Тематически сгруппированные ключевые термины могут значительно улучшить выведение общей темы документа (используя, например, применение метода «spreading activation» по графу категорий Википедии, как описано в [20]), и категоризацию документа [5].
• Наш метод высокоэффективен с точки зрения качества извлеченных ключевых терминов. Экспериментальные оценки метода, обсуждаемые далее в этой статье, показали, что метод извлекает ключевые термины из документов с высокой точностью и полнотой.

Содержание Вперёд