Выпускная квалификационная работа разработка программного модуля для автоматической нормализации именных групп в русском языке

Федеральное государственное автономное образовательное учреждение
высшего образования

КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

ВЫСШАЯ ШКОЛА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И
ИНФОРМАЦИОННЫХ СИСТЕМ

Направление подготовки: 09.03.03 – Прикладная информатика

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

РАЗРАБОТКА ПРОГРАММНОГО МОДУЛЯ ДЛЯ АВТОМАТИЧЕСКОЙ НОРМАЛИЗАЦИИ ИМЕННЫХ ГРУПП В РУССКОМ ЯЗЫКЕ

Работа завершена:

«___»_____________201 г. 

Студент группы ______  ____________________

Работа допущена к защите:

Научный руководитель

Научный сотрудник кафедры интеллектуальных технологий поиска

«___»_____________201 г.  ____________________

Директор Высшей школы ИТИС

«___»_____________201 г.  __________________

Казань – 2017 г.

СОДЕРЖАНИЕ

Введение        4

Обзор существующих алгоритмов и программ для решения задачи нормализации именных групп        6 Сбор данных для машинного обучения        9 Получение данных русскоязычной «Википедии»        10 Выбор библиотеки для осуществления структурированного доступа к данным «Википедии»        11 Создание структурного доступа к офлайн базе русскоязычной «Википедии» с помощью библиотеки JWPL        12 Извлечение именных групп из текстов русскоязычных статей «Википедии», используя JWPL API        13 Решение проблемы лемматизации не словарных слов        14 Результат работы по сбору именных групп для тренировочного и тестового множеств        27 Реализация алгоритмов нормализации именных групп        28

3.1 Алгоритм нормализации каждого слова именной группы в отдельности        28

3.2 Алгоритм, при котором обрабатываемая именная группа считается уже нормализованной        29

3.3  Составление вероятностной модели преобразований цепочек окончаний слов именной группы на основе тренировочного множества        30

3.4  Алгоритм нахождения наиболее вероятного преобразования цепочки окончаний именных групп в вероятностной модели при условии полного совпадения цепочек окончаний слов        31

3.5  Алгоритм нахождения очередного преобразования окончания в цепочке, основываясь на предыдущем        32

Результаты экспериментов        35

Заключение        36

Список используемых источников        37

Приложение        38

ВВЕДЕНИЕ

Обоснование научной актуальности, практической значимости, новизны темы

В настоящее время объём текстовой информации, которая нас окружает, постоянно растёт, поэтому возникает целый спектр задач автоматизированного анализа, обработки больших объёмов текстовых массивов данных, таких как генерация новостей, извлечение фактов, анализ тональности и множество других. Для того, чтобы отображать текстовую информацию в интерфейсе пользователя в понятном для него виде, алгоритмы анализа текстов используют нормализированные формы слов, называемые леммами. Большинство слов русского языка с указанными леммами содержатся в машиночитаемых русскоязычных словарях, таких как Opencorpora [2] или AOT. ru [3]. Для того, чтобы получить лемму слова, алгоритму требуется только машиночитаемый словарь, в котором содержатся леммы и словоформы. В процессе своей работы, алгоритм находит нужную словоформу и далее определяет связанную с ней лемму. Так как большинство нормализованных форм слов русского языка уже содержатся в машиночитаемых словарях [2], [3], то задачу лемматизации отдельного слова в русском языке в настоящее время можно считать решённой. Более глобальной задачей нормализации является нормализация именной группы. Именные группы являются словосочетаниями, согласованными в роде, числе и падеже, в которых имя существительное является вершиной, то есть главным словом, определяющим характеристику всего словосочетания [1]. Задача нормализации именных групп является актуальной и практически значимой, так как она применяется в таких задачах анализа текста, как информационный поиск, генерация текста, а также извлечение фактов, в основном в целях нормализации поисковых запросов, найденных фактов, а также нормализации структуры предложений при отображении текстовой информации в интерфейс пользователя. Автоматическая нормализация именных групп позволяет отображать текстовую информацию в интерфейсе пользователя в более понятном для него виде, так как обеспечивает нормализацию более обобщенных смысловых элементов текста – именных групп.

Объект и предмет исследования

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

Цели проводимого исследования

Целью дипломной работы является создание программного модуля для нормализации именных групп русского языка.

Задачи проводимого исследования

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

Подзадачи

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

ОБЗОР СУЩЕСТВУЮЩИХ АЛГОРИТМОВ И ПРОГРАММ ДЛЯ РЕШЕНИЯ ЗАДАЧИ НОРМАЛИЗАЦИИ ИМЕННЫХ ГРУПП

Рассмотрим существующие алгоритмы и программы для решения задачи нормализации именных групп в русском языке:

Морфологическая нормализация, используемая в программе «Томита-парсер»: [6]

Томита-парсер — это инструмент для извлечения структурированных данных (фактов) из текста на естественном языке, разработанный компанией «Яндекс». Основные компоненты парсера: газеттир-словарь, набор контекстно-свободных-грамматик и множество описаний типов фактов, которые порождаются этими грамматиками в результате процедуры интерпретации.

Процесс нормализации именных групп в «Томита-Парсер» происходит во время стадии «Интерпретация». Интерпретация в «Томита-Парсер» - это процедура, которая позволяет отобразить древовидную синтаксическую структуру во множество линейно организованных фактов. Каждый факт можно представить, как таблицу из одной строки и одной или нескольких колонок: в каждой ячейке этой таблицы содержится объект. К терминалам грамматики относятся лемма слова, части речи, знаки пунктуации, специальные символы. Не терминалы состоят из терминалов. Процесс нормализации происходит в два этапа:

Морфологическая нормализация - выбирается синтаксическая вершина именной группы и ставится в словарную форму (нормализуется). Если в цепочке есть слова, связанные с вершиной согласованием, то соответствующие граммемы также принимают новые значения, так чтобы согласование было соблюдено. Нормализация через Газеттир-словарь - если при создании цепочки, которая попала в поле факта, участвовала статья словаря с заполненным полем lemma, то при нормализации часть цепочки описанной этой статьей заменяется значением поля lemma этой статьи.

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

Недостатки нормализации именных групп в «Томита-Парсер»:

Нормализация может применяться только для извлеченных фактов. Использовать нормализацию без процедуры извлечения фактов нельзя. «Томита-Парсер» является коммерческим программным продуктом компании «Яндекс», и его исходный код открыт не полностью, соответственно, модификация и использование необходимого участка кода данного продукта в целях нормализации именных групп не представляется возможным.

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

Библиотека склонения слов и словосочетаний русского языка «Morpher»

Данная библиотека была написана на языке Java, и, судя по заявленным разработчиками функциям, способна: [9]

Склонять по падежам слова и словосочетания на русском языке;

Определять пол человека по имени (грамматического рода слова); Склонять прилагательные по родам; Переводить числа в письменный вид.

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

Достоинства:

Удобный API для склонения слов и словосочетаний русского языка по падежам

Недостатки:

Не выполняет автоматическую нормализацию именных групп Является коммерческим приложением, не имеет открытого исходного кода В демоверсии нет возможности нормализовать именную группу

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

СБОР ДАННЫХ ДЛЯ МАШИННОГО ОБУЧЕНИЯ

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

В «Википедии» существует мощный механизм внутреннего связывания страниц. На одной странице может быть множество ссылок на другие страницы «Википедии». Наиболее ценными ссылками являются так называемые «Внутренние фиксированные ссылки на страницы». Данный вид ссылок выглядит следующим образом:

[[президент Российской Федерации | президенту Российской Федерации]]

Такие ссылки оформляется в двойные квадратные скобки. Слева от символа ‘|’ записывается заголовок целевой статьи, который является нормализованной именной группой. Справа от символа ‘|’ записывается именная группа в той форме, которая согласуется в роде числе и падеже с внутренним контекстом текущей статьи. Таким образом, задача сбора данных для тренировочного и тестового множеств сводилась к задаче извлечения всех «Внутренних фиксированных ссылок на страницы» со всех статей русскоязычного раздела «Википедии».

Получение данных русскоязычной Википедии

Существует несколько способов, как получить неструктурированные данные из русскоязычного раздела «Википедии»:

Посредством использования Wikipedia API.

Посредством загрузки дампов базы данных русскоязычной «Википедии». Парсинг страниц «Википедии».

Первый способ обладает следующими преимуществами: для него не требуется предварительно загружать большой объем данных, структурированный доступ уже предоставлен посредством API, существует возможность выбора формата ответа, среди которых есть XML и Json, что является немаловажным фактором для удобного извлечения необходимой информации. В то же время, у данного метода есть несколько минусов, среди которых ограничение на максимальную длину ответа в 500 строк, ограничение набором команд API, невозможность модификации запросов под свои нужды.

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

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

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

Таким образом, для получения первичных неструктурированных данных русскоязычного раздела «Википедии» был выбран способ загрузки офлайн дампа.

Выбор библиотеки для осуществления структурированного доступа к данным «Википедии»

После анализа всех доступных библиотек для работы с офлайн дампом «Википедии», обнаружилось, что наибольшим функционалом обладает библиотека JWPL. Согласно API данной библиотеки, она может предоставить полный структурированный доступ к офлайн данным «Википедии», например, извлечь все страницы из дампа, извлечь заголовок статьи, текст статьи, список всех страниц, на которые ссылается текущая статья и много другой полезной информации. Исследовав все предоставляемые возможности библиотеки, было решено использовать её для создания структурированного доступа к офлайн базе русскоязычной «Википедии».

Создание структурного доступа к офлайн базе русскоязычной «Википедии» с помощью библиотеки JWPL

Согласно требованиям библиотеки JWPL [8], для инициализации дампов требуется 3 файла:

ruwiki-20170120-pages-articles. xml. bz2 – содержит тексты всех статей русской «Википедии». ruwiki-20170120-pagelinks. sql. gz – содержит информацию и связях между страницами. ruwiki-20170120-categorylinks. sql. gz – содержит информацию и связях между категориями.

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

После завершения выполнения программы, были сформированы 11 текстовых файлов – category, category_inlinks, category_outlinks, category_pages, metadata, page, page_categories, page_ inlinks, page_ outlinks, page_redirects, pagemapline, которые будут соответствовать названию таблиц в локальной базе данных. Данные в этих текстовых файлах имеют следующую структуру: каждая строка соответствует одной записи в таблице, данные в каждой строке разделены между собой знаком табуляции.

Так как библиотека JWPL работает только с системой управления базами данных MySQL [8], то необходимо было установить локальный сервер MySQL и создать базу данных с произвольным названием. Также, из-за большого размера текстовых файлов для импорта, нужно было предварительно правильно настроить такие параметры сервера, как таймауты, максимальный размер передаваемых пакетов, максимальный размер кэша, максимальное время выполнения запросов, иначе соединение с сервером базы данных могло неожиданно прерваться и импорт данных проходил неуспешно [11]. После того, как нужные параметры были настроены, к созданной базе были применены SQL скрипты из библиотеки JWPL, которые создали все необходимые таблицы для импорта данных. Для импорта данных из текстовых файлов в таблицы, использовалась команда «load data local inline», которая по умолчанию считывает одну строку из текстового файла, как одну запись в таблице, а каждое значение колонки разделяется между собой знаком табуляции. После завершения импорта данных из текстовых файлов приступили к работе с библиотекой JWPL.

Извлечение именных групп из текстов русскоязычных статей «Википедии», используя JWPL API и стандартные средства языка программирования JAVA

После инициализации локальной копии русскоязычного раздела «Википедии» в JWPL, были извлечены все страницы русскоязычного раздела «Википедии», а затем выполнена итерация по данному списку. Из каждой страницы был извлечён текст статьи. Далее из этого текста были извлечены все внутренние ссылки на другие страницы «Википедии». Для извлечения таких ссылок было использовано регулярное выражение:

\[\[([А-ЯЁ]|[а-яё])+(\s([А-ЯЁ]|[а-яё])*)*\|([А-ЯЁ]|[а-яё])+(\s([А-ЯЁ]|[а-яё])+)*\]\]

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

Решение проблемы лемматизации не словарных слов

В ходе нахождения лемм каждого из слов, было обнаружено, что существует множество не словарных слов, лемма для которых не определена, такие примеры игнорировались алгоритмом и не добавлялись в тренировочное множество, хотя подходили по всем критериям. Для повышения точности лемматизации слов и, соответственно повышения качества примеров в тренировочном множестве, в рамках курсовой работы был разработан метод нахождения леммы, основанный на вероятностной модели преобразований слов русского языка, построенной из открытого машиночитаемого словаря “Opencorpora”.

Рассмотрим алгоритм лемматизации не словарного слова, разработанный в рамках курсовой работы. Данный алгоритм будет использовать статистику преобразований словоформ русского языка, которые приводят их к лемме. Для этого была построена вероятностная модель преобразований слов для каждой части речи, основываясь на большом структурированном текстовом наборе с уже определёнными грамматическими категориями (такими как лемма, её словоформы, а также часть речи, падеж, род, число и другие). Обладая таким набором уже размеченных данных, подсчитаем сначала общее количество преобразований одного типа, а затем и вероятность применения того или иного преобразования относительно других (в пределах этого набора данных). Вероятностная модель имеет следующую структуру: в ней записаны список частей речи, и для каждой части речи - список преобразований с определёнными параметрами, такими как количество повторений идентичных преобразований во всём словаре, вероятность конкретного преобразования относительно других преобразований, а также коэффициента, который учитывает и вероятность появления данного преобразования, и количество его повторений в словаре.

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

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

а) Составление вероятностной модели

Для составления вероятностной модели было определено следующее правило преобразования словоформы в лемму:

Выбор преобразования на основе посимвольного сравнения всех словоформ в совокупности с леммой, с запоминанием позиции отличия. При применении данного подхода сначала находили позицию первого отличного символа среди всех словоформ. Затем составляли слово, равное отсечению от леммы подстроки с начального символа до позиции уникального. В дальнейшем такое слово будем называть The Longest Stem (самая длинная основа слова). За преобразование будем считать комбинацию символов, равную отсечению самой длинной основы от одной из словоформ и леммы. Следовательно, такая операция применяется к каждой из словоформ и лемме.

Схема этого алгоритма представлена на рисунке 3.5.1.