Статья: Анализ текстов на семантическое сходство на основе аппарата теории графов

Анализ текстов на семантическое сходство на основе аппарата теории графов

Бородащенко А.Ю.

The evaluator of affinity of two texts by their meaning content and structure, presented in the article, enables to heighten the quality of informational searching in the Internet, in official (corporative) nets and database programs, which contain full-text information. The evaluator actualize a searching function of affinitive texts by their reference to the text fragments, the most relevant user's needs. An original approach of searching results correlation is given to evaluate the productivity of that evaluator.

В настоящее время информационный ресурс сети Internet составляет свыше десятка миллиардов документов (web-страниц), к которым возможен свободный доступ любого пользователя. Для того чтобы найти необходимую информацию в этой крупнейшей распределенной базе данных, необходимо использовать мощные информационно-поисковые системы (ИПС). Такие системы существуют и конкурируют друг с другом на современном рынке информационных технологий.

Основными зарубежными ИПС в Internet являются поисковые машины Google (http://www.google.com), Yahoo! (http://www.yahoo.com), Ask (http://www.ask.com), Alltheweb (http://www.alltheweb.com), Altavista (http://www.altavista.com), Lycos (http://www.lycos.com). Среди российских поисковых серверов заслуживают внимания Яндекс (http://www.yandex.ru), Рамблер (http://www.rambler.ru) и Апорт (http://www.aport.ru) [1].

Различные ИПС имеют собственные языки запросов, позволяющие в той или иной мере описывать потребности пользователей. Процесс поиска информации в Интернет в целом всегда выглядит одинаково:

- составляется поисковый запрос, соответствующий необходимой тематике;

- анализируется отклик ИПС, и выбираются ссылки на документы, соответствующие информационным потребностям пользователя по его мнению;

- осуществляется анализ первоисточников и отбор нужной информации.

Однако, как правило, на логично сформулированный запрос к ИПС выдается достаточно много (до нескольких сотен) документов, имеющих «слабое» отношение к информационным потребностям пользователя. Наиболее образно данный факт охарактеризовал Гари Флейк [2], один из семи ведущих инженеров Microsoft: «Если бы Web-поиск был совершенен, он бы выдавал ответ на каждый запрос, и это происходило бы так, будто на вопрос отвечает умнейший человек в мире, у которого есть под рукой вся справочная информация, и все это выполняется меньше, чем за мгновение… Поиск будущего можно сравнить с армией из 1000 экспертов, которые знают ваши вкусы и способны сканировать миллионы документов за долю секунды. Поиск будет моделировать человеческий мозг».

Сейчас поисковые технологии находятся только в начале своего развития. Они предоставляют лишь визуальный интерфейс для анализа выделенной ими подборки документов.

Одним из способов повышения качества информационного поиска в полнотекстовых базах данных является функция «поиска подобных документов». Если в результате поиска по запросу найдено избыточное количество документов, а при просмотре первых страниц результатов поиска найдено несколько пертинентных документов, то возможно найти дополнительные документы, сходные с найденными по содержанию, не затрачивая усилий на анализ и составление запроса.

Многие ИПС реализовали опцию «найти подобное», «find similar», «like this». Однако и этот режим не всегда ведет к удовлетворительным результатам. При этом критерий выбора «подобных» документов, как правило, остается не известен.

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

Задача оценки текстов может быть разделена на два этапа.

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

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

Обобщенная функциональная схема оценки массива текстов на семантическое сходство с эталоном представлена на рис. 1.

Рисунок 1 - Обобщенная функциональная схема оценки текстов на семантическое сходство с эталоном

Анализ существующих процедур обработки текстовой информации [1, 3], которые могут быть использованы при решении задачи фильтрации, а также оригинальных авторских разработок позволил сформировать соответствующий структурной схеме (рис. 1) алгоритм определения семантического сходства (рис. 2).

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

Рисунок 2 - Алгоритм определения степени семантического сходства текста с эталоном

Максимальное значение тематического веса (равное 100) соответствует ключевой (важнейшей) теме документа. Близкое к нулю значение веса темы показывает, что она лишь вскользь упомянута в тексте, и в нем мало сведений, относящихся к данной теме.

Связи между парами тем, в свою очередь, также имеют характеристики - веса связей (от 0 до 100). Большое значение веса связи от одной темы к другой, близкое к 100, указывает на то, что подавляющая часть информации в тексте, касающаяся первой, касается в то же время и второй темы - первая тема почти всегда излагается в контексте второй. Малое значение веса отражает тот факт, что первая тема слабо связана со второй (излагается независимо от нее). Связь между парой тем сети всегда двусторонняя, однако связь от первой темы ко второй не всегда имеет тот же самый вес, что и обратная - от второй к первой. Такое различие в весах может указывать на то, что одна тема является подтемой другой.

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

На вход процедуры «Формализация текстов» подается текст с предварительно заданными параметрами анализа. Устанавливаются следующие параметры построения семантической сети:

1. Минимальный вес темы при добавлении в сеть (только темы, имеющие вес в документе не меньше заданного значения, будут включаться в семантическую сеть).

2. Минимальная частота встречаемости связи в тексте при добавлении к сети.

3. Максимальное допустимое число главных тем документа с весом не менее заданного параметром (1) , которые включаются в семантическую сеть.

4. Максимальное допустимое число слов в названии темы.

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

На выходе процедуры «Формализация текстов» получается массив ключевых слов этого текста Ui, массив их весов Vi и матрица весов связей между любыми двумя ключевыми словами Mi, где i - индекс текста. Все веса нормированы от 1 до 100. Кроме того, возможно визуальное представление текста в виде семантической сети.

В качестве меры сравнения двух текстов выбраны три коэффициента: k1, k2, k3.

Первый коэффициент k1 показывает долю общих ключевых слов и рассчитывается как отношение суммы весов ключевых слов, общих для этих текстов, к сумме весов всех ключевых слов обоих текстов [3]:

,(1)

Где

.

Этот коэффициент является наиболее значащим, т.к. он показывает смысловую близость и нормируется от 0 до 1.

Далее создается n-мерное пространство (), и измеряется евклидово расстояние между двумя векторами этого пространства, каждая координата которого отображает вес соответствующего ключевого слова. Коэффициент k2 - нормированное от 0 до 1 расстояние между данными векторами ( - максимально возможное расстояние):

.(2)

Аналогично высчитывается коэффициент k3, только в n2-мерном пространстве, где координата вектора будет отображать вес связи между двумя соответствующими ключевыми словами:

.(3)

Коэффициенты k2 и k3 показывают структурную удаленность этих текстов.

Комплексный коэффициент K по определению не может быть численно больше коэффициента k1, так как похожесть структуры не может добавить смысловой похожести двум текстам. Поэтому в качестве комплексного коэффициента K выбирается:

.(4)

Среднеарифметическое 2-го и 3-го коэффициентов домножается на k12 c целью снижения роли этих коэффициентов.

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

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

Таблица 1 - Шкала степени сходства текстов

Результаты оценки контрольного примера текстов экспертами, а также с использованием разработанного макета приведены в таблице 2. В таблице в первой строке и первом столбце приведены номера текстов с 1 по 10. На пересечении соответствующего столбца и строки в числителе представлен результат сравнения двух текстов экспертами, а в знаменателе - результат работы программы (в баллах).

Таблица 2 - Результаты сравнения текстов экспертами/программой

В ходе обработки данных результатов методами математической статистики получилось, что относительная средняя ошибка составляет 7,8 % , что означает, что при сравнении каждой пары текстов в среднем расхождение в результатах составляет менее 1 балла (0,78).

Экранные формы пользовательского интерфейса прототипа программного модуля анализа текстов представлены на рис. 3-4.

Таким образом, в докладе предложен способ анализа текстов на семантическое сходство на основе аппарата теории графов, получивший практическую проверку на программном макете.

Рисунок 3 - Экранная форма подробного сравнения заданной пары текстов