Автореферат (Разработка вычислительных методов анализа текстов с использованием аннотированных суффиксных деревьев)

На правах рукописиЧерняк Екатерина ЛеонидовнаРАЗРАБОТКА ВЫЧИСЛИТЕЛЬНЫХ МЕТОДОВ АНАЛИЗАНЕСТРУКТУРИРОВАННЫХ ТЕКСТОВ СИСПОЛЬЗОВАНИЕМ АННОТИРОВАННЫХСУФФИКСНЫХ ДЕРЕВЬЕВСпециальность 05.13.18 ––«Математическое моделирование, численные методы и комплексыпрограмм»Авторефератдиссертации на соискание учёной степеникандидата технических наукМосква –– 2016Работа выполнена на Департаменте анализа данных и искусственного интеллекта федерального государственного автономного образовательного учреждениявысшего образования Национальный исследовательский университет «Высшаяшкола экономики»Научный руководитель:доктор технических наук, старший научный сотрудникМиркин Борис ГригорьевичОфициальные оппоненты:Моттль Вадим Вячеславович,доктор технических наук, профессор,Федеральный исследовательский центр «Информатика и управление» Российской Академии Наук,ведущий научный сотрудникПетровский Михаил Игоревич,кандидат физико-математических наук,Факультет вычислительной математики и кибернетики Московского государственного университетаимени М.

В. Ломоносова,доцентВедущая организация:Институт прикладной математики им. М. В. Келдыша РАНЗащита состоится –.–.—- г. в 11 часов на заседании диссертационного совета Д 002.073.04 при Федеральном исследовательском центре «Информатика иуправление» Российской Академии Наук по адресу: 117312, Москва, проспект60-летия Октября, д. 9.С диссертацией можно ознакомиться в библиотеке Федерального исследовательского центра «Информатика и управление» Российской Академии Наук по адресу: 119333, Москва, ул. Вавилова д.40.Отзывы на автореферат в двух экземплярах, заверенные печатью учреждения,просьба направлять по адресу: 117312, Москва, проспект 60-летия Октября, д.

9,ученому секретарю диссертационного совета Д 002.073.04.Автореферат разослан –.–.—-.Телефон для справок: +7 (499) 135-51-64.Ученый секретарьдиссертационного советаД 002.073.04,д.т.н., профессорКрутько В. Н.Общая характеристика работыАктуальность темы. Проникновение вычислительной техники во всесферы производственной, социальной и политической систем привело к необходимости разработки методов автоматического семантического анализа текстовых документов, размещенных в индивидуальных компьютерах и в интернете.Часть связанных с этим задач хорошо осознана и получает решение в научной итехнической литературе.

Это, прежде всего, задачи поиска и извлечения информации, категоризации текстов, извлечения ключевых словосочетаний, извлечение фактов и др. Большинство методов решения таких задач основано на предварительной «ручной» разметке текстов (выделение ключевых слов и других данных для обучения). Однако, в связи с наступлением эры глобализации, существует явная потребность в разработке методов, не требующих предварительной разметки текстов. Кроме того, создание корректных и эффективных морфологических и синтаксических парсеров – это трудоемкая задача, решенная не для всехязыков.

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

Мера релевантности должна удовлетворять следующиместественным свойствам:1. Интуитивная простота (понятные единицы и границы измерения);2. Независимость от длины текста;3. Независимость от лексической вариативности текста;4. Возможность эффективной вычислительной реализации.Большинство известных мер релевантности основаны на использованиив качестве элементарной единицы текста слова (или его нормальной формы –леммы, или его (псевдо)основы – стема). К этому классу моделей релевантности относятся векторная модель релевантности [Salton, 1988] вероятностная модель релевантности [Robertson, Zaragoza, 2009] языковая модель релевантностина словах или символьных n-граммах [Ponte, Croft, 1998], модель суффиксного дерева [Zamir, Etzioni, 1998].

Эти модели предполагают представление текстав виде неупорядоченного набора слов – «мешка» слов, а также предполагаютучет морфологии и синтаксиса языка для идентификации и унификации слов.Существенным недостатком этих моделей можно считать невозможность учестьнечеткие (то есть, с различием на несколько символов) совпадения между строками и текстами. До некоторой степени этот недостаток помогают преодолетьязыковая модель релевантности на символьных n–граммах [Ponte, Croft, 1998] имодель суффиксного дерева [Pampapathi и др., 2006]. Однако же, языковая модель3релевантности на символьных n–граммах часто бывает неэффективной с вычислительной точки зрения, поскольку возникающая в ней проблема нулевых вероятностей зачастую решается с помощью вычислительно неэффективных алгоритмов сглаживания, а модель суффиксного дерева, предложенная в [Pampapathiи др., 2006], по определению не удовлетворяет требованиям 3 и 4, сформулированным выше.Для решения обозначенных выше задач – необходимости предобработки инечеткости меры релевантности – и с учетом требований 1-4 необходима новаямодель совокупности «строка – текст», а также структура данных, позволяющаявычислять нечеткие оценки релевантности.В данном исследовании предлагается и верифицируется теоретикомножественная модель совокупности «строка – текст», а адекватной структуройданных для вычисления параметров оценки является аннотированное суффиксное дерево.В теоретико-множественной модели совокупности «строка – текст» текстпредставляется в виде множества коротких строк, например, последовательныхпар или троек слов, а строка S, состоящая из n символов, S = s1 s2 .

. . sn – множеством всех подстрок si . . . sj , где i >= 1, j <= n, i <= j. Для каждой пары строка – текст несложно найти все возможные общие подстроки, иначе говоря, совпадения. Максимальным совпадением назовем такое совпадение, придобавлении символа в начало или в конец которого, перестает быть совпадением. Допустим, существует совпадение строки с текстом si .

. . sj . Определимего вероятность, как условную частоту последнего символа sj : P (si . . . sj ) =P (sj |si . . . sj−1 ) (УВС). Вероятностью максимального совпадения тогда является средняя сумма совпадений, в него входящих (СУВС), а полной релевантностью строки тексту – сумма вероятностей максимальных совпадений данномутексту (СУВСС). Для эффективной реализации вычисления оценок релевантности следует использовать аппарат аннотированного суффиксного дерева – структуры данных, которая позволяет вычислять все частоты всех подстрок.Объект исследования – вычислительные задачи анализа текстовых документов, написанных на естественном языке.Предмет исследования – вычислительное моделирование текстов какстрок символов и задачи их анализа, решаемые путем наложения разных строкдруг на друга.Цель данного диссертационного исследования – разработка оригинальных моделей, методов, алгоритмов и программных комплексов, предназначенных для решения некоторых задач анализа текстовых документов на естественном языке на уровне последовательностей символов.К задачам исследования относятся:1.

Разработка модели представления коллекции текстовых документовстроками и ассоциированной с ней функции релевантности;2. Верификация разработанной модели на реальных задачах анализа коллекций текстовых документов:4a) Рубрикация текстовых документов в соответствии с заданнойсистемой рубрик;b) Пополнение таксономии с использованием внешней коллекции текстов;c) Фильтрация коллекции текстовых документов от обсценнойлексики.3.

Реализация разработанных моделей и методов в виде комплекса программ.К методам, использованным в исследовании, относятся:1. Метод Укконена для построения аннотированного суффиксного дереваза линейное время;2. Метод вычисления релевантности строки тексту с помощью наложениястроки на аннотированное суффиксное дерево его представляющее;3. Методы вычисления релевантности строки тексту, основанные на представлении текстов векторными пространствами и вероятностными моделями.Научная новизна. В диссертации получен ряд новых научных результатов, которые выносятся на защиту:1.

Разработана теоретико-множественная модель совокупности «строкатекст» с методом оценки релевантности строк тексту, основанном на аннотированных суффиксных деревьев. Предложен новый метод вычисления оценок релевантности строки тексту СУВСС, апробированный вработе;2.

Предложен метод рубрикации научных статей с использованием критерия релевантности СУВСС, более точного, чем популярные методы,традиционно используемые в международных публикациях;3. Разработан метод использования справочных материалов интернета, сучетом наличия в них шумовой компоненты, для пополнения предметных таксономий.