Главная Коллекция "Revolution" Программирование, компьютеры и кибернетика Разработка метода и программного обеспечения для проведения авторской атрибуции русскоязычных текстов

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

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

Рубрика	Программирование, компьютеры и кибернетика
Вид	курсовая работа
Язык	русский
Дата добавления	05.08.2018
Размер файла	1,3 M

посмотреть текст работы

скачать работу можно здесь

полная информация о работе

весь список подобных работ

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Страница:

Размещено на http://www.allbest.ru/

1.2.1 Текстовые документы
1.2.2 Предварительная обработка текстовых данных
1.2.3 Индексация документов
1.2.4 Извлечение признаков
1.2.5 Алгоритм классификации
1.2.6 Оценка результатов

2. Описание предлагаемого метода АА

2.1 Требования к реализуемому методу
2.2Требования к функционалу программной реализации
2.3 Разработка метода
2.4 Проектирование программной реализации метода

3. Программная реализация метода АА

3.1 Программная реализация

3.1.1 Общие сведения
3.1.2 Функциональное назначение
3.1.3 Описание логической структуры
3.1.4 Входные данные
3.1.5 Выходные данные

3.2 Тестирование программы
3.3 Зависимость качества от числа авторов
3.4 Зависимость качества от объёма текстов
3.5 Выводы по апробации

Заключение
Список литературы
Приложение A - Листинг программы

Введение

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

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

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

Для достижения поставленной цели необходимо выполнить следующие задачи:

· анализ существующих технических решений и исследований в области авторской атрибуции;

· определение и обоснование собственного метода;

· разработка программного обеспечения, реализующего метод;

· составление экспериментальной выборки из русских литературных произведений;

· проведение экспериментов по атрибуции текстов на тестовой выборке с определением показателей качества атрибуции;

· интерпретация полученных экспериментальных данных;

· дача рекомендаций о применимости предложенного метода и его программной реализации.

1. Анализ существующих решений

Авторская атрибуция (далее АА) -- это задача сопоставления исследуемому документу одного автора из конечного множества авторов других документов, среди которых есть автор исследуемого текста [1]. АА обычно направлена на решение задач идентификационного, или диагностического, характера. Идентификация подразумевает проверку документа на истинность авторства и необходима в случаях, когда требуется удостовериться в истинности авторства. Определение авторства производится над анонимным документом, автор которого точно не известен. Как правило, задача идентификации решается через задачу определения авторства, при данном подходе исследуемый текст считается анонимным, и ему сопоставляется автор из заданного множества; в случае, если новый автор совпадает с предполагаемым, истинность авторства подтверждена, в ином случае - нет.

1.1 Обзор готовых программных продуктов

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

Лингвоанализатор [3]. Программа использует метод энтропийного анализа, суть метода заключается в том, что к анонимному документу последовательно добавляются фрагменты документов с известным авторством, после чего модифицированные тексты обрабатываются алгоритмами сжатия. Анонимному тексту присваивается авторство того документа, фрагмент которого в совокупности с исходным текстом показал наибольшую степень сжатия. Наибольший результат в 89 % был продемонстрирован на выборке из 1813 статей 50 авторов, однако для оценки точности использовалась лишь десятая часть от исходной выборки.

СМАЛТ [4]. Система основана на методах кластерного анализа лексических единиц текста (абзацы, предложения и слова) и на критериях Колмогорова-Смирнова, Стьюдента. Из анонимного документа извлекаются различные лексические единицы, строится граф, после чего происходит сравнительный анализ по критериям Колмогорова-Смирнова и Стьюдента с другими текстами выборки. Эксперименты были поставлены на выборках до 900 слов, однако авторы в явном виде не приводят результаты экспериментов, по которым можно было бы оценить их качество.

Атрибутор [5]. В данной системе в качестве описания текстов используются распределения троек символов исходного текста. Полученные текстовые описания сравниваются по принципу каждый с каждым, с использованием математического аппарата Марковских цепей. Автор также не указывает точность предложенного метода.

Стилеанализатор [6]. Автор данной системы извлекает из каждого текста выборки различные признаковые описания, далее решение сводится к задаче классификации текстов по этим признакам. В качестве основных алгоритмов классификации используются нейронные сети. Данный подход позволяет получать точность порядка 90-98 % в задаче авторской атрибуции, однако автор не указывает точный размер выборки, на которой был получен такой результат. Также использование нейронных сетей требует больших вычислительных мощностей и временных задач для проведения классификации на больших выборках.

Авторовед [7]. Автор данного программного обеспечения также сводит авторскую атрибуцию к задаче классификации. В качестве признаков используются 300-700 наиболее употребляемых троек букв текста, а также 500 наиболее употребляемых слов. Для классификации используются нейронные сети и метод опорных векторов. При бинарной классификации (классификация 2 авторов) данный подход показывает точность в 90-98 %, однако данная точность может быть завышена из-за недостаточного размера выборки и количества авторов, также нейронные сети достаточно требовательны к вычислительным мощностям и проигрывают по времени обучения.

Таблица 1

Сравнительное описание программных средств определения авторского инварианта.

Название	Методы	Методы анализа текстов	Требование по объёму текста	Точность, %
Лингвоанализатор	Энтропийный анализ	Статистический и графемный анализы	> 40 000 символов	~89
СМАЛТ	Кластерный анализ, критерии Колмогорова-Смирнова, Стьюдента	Графемный, морфологический, синтактический, статистический анализы	Около 500 цельных слов для определения однородности текста	Нет данных
Атрибутор	Марковские цепи	Статистический, вероятностный анализы	> 20 000 символов	Нет данных
Стилеанализатор	Меры расстояний, марковские цепи, нейросети, деревья решений	Графемные, статистические анализы, работа с первоначально размеченными профессиональными лингвистами текстами	> 30 000 символов	90 - 98
Авторовед	Нейросети, QSUM, опорные векторы	Графемный, морфологический, синтактический, статистический анализы	> 20 000 символов	95

В заключении можно сказать, что большинство описанных программных продуктов обладают различными недостатками, такими как низкая точность АА, требовательность к большому объёму исследуемых текстов, апробация реализаций на малых выборках, требовательность к вычислительным мощностям и большие временные затраты на АА. Однако, исходя из изученного материала, можно сделать вывод о применимости методов статистического анализа применительно к задаче АА. Среди конкретных подходов можно выделить сведение задачи АА к задаче многоклассовой классификации над большими векторными признаками: распределение N-грамм, распределение слов, распределение других грамматических конструкций. Такой подход позволяет получить достаточно высокую точность АА.

1.2 Общие подходы

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

Рисунок 1. Основные этапы в задаче АА.

Рассмотрим основные подходы к реализации этих этапов.

1.2.1 Текстовые документы

Данный этап подразумевает под собой сбор первичных данных, в нашем случае это русскоязычные литературные произведения разных авторов, для которых будет решаться задача АА. Собранная текстовая выборка делится на две части [9], первая используется для обучения классификатора, вторая - для тестирования алгоритма. Соотношения размеров двух выборок могут быть разными, но чаще всего размер тестовой выборки меньше либо равен размеру обучающей выборки. Итоговое решение относительно размеров выборок зависит от количества и состава исходных данных - данная задача суть предмет параметризации метода на материале экспериментов, проводимых при помощи программного обеспечения, реализующего метод. Чем больше обучающая выборка, тем лучше обучается алгоритм, многообразие исходных данных позволяет классификатору уловить сложные редко встречающиеся зависимости, соответственно на меньших данных алгоритм будет обучаться хуже. В то же время, чем больше размер тестовой выборки, тем точнее можно оценить качество алгоритма. Небольшие размеры тестовой выборки могут привести к переоценке или недооценке качества работы алгоритма. Основная задача в разделении выборки - найти оптимальное соотношение размеров двух подмножеств данных.

В случаях, когда для исследования доступны малые объёмы данных, разделение выборки на тестовую и обучающую не рационально, в таком случае применяют кросс-валидацию [9] - процесс, при котором вся выборка делится на несколько равных частей, как правило, (3, 5, 10), после чего одна часть становится отложенной и используется для тестирования, а остальные - для обучения алгоритма. Далее в качестве тестовой выделяется другая часть данных, остальные также идут в обучение. После того, как все части были использованы для тестирования, строится итоговая оценка качества алгоритма, определяемая средним значением оценок каждого из экспериментов. Данный метод хорошо подходит при малых исходных данных, но он обладает большими временными затратами, так как алгоритм обучается не один раз, как в случае с статической тестовой выборкой, а N раз, где N это количество разбиений кросс-валидацией.

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

1.2.2 Предварительная обработка текстовых данных

После сбора исходных данных их необходимо подготовить для дальнейшего использования. Основной целью предварительной обработки является снижение размерности данных за счёт удаления неинформативных частей, которые к тому же могут серьёзно зашумлять полученные результаты. В области классификации текстов, как правило, проводят следующие этапы предварительной обработки [9].

· Понижение регистра слов, удаление пунктуации и числовых символов.

· Удаление стоп-слов, к ним относят союзы, междометия, местоимения, предлоги, а также самые часто встречающиеся слова. Для задачи АА считается, что эти данные не являются носителями авторского стиля [25].

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

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

1.2.3 Индексация документов

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

1.2.4 Извлечение признаков

Извлечение признаков - ключевой этап любой задачи машинного обучения, именно признаковое описание исходные данных наиболее всего влияет на итоговое качество разработанного алгоритма. При обработке текстов необходимо представить каждый документ в понятном основному алгоритму числовом формате. В задаче АА необходимо выделить такие числовые характеристики каждого текста, которые будут максимально полно описывать стиль автора. В работе [11] было проведено сравнительное исследование большого числа признаков, извлекаемых из текстовых документов, и их влияние на качество АА методами классификации текстов. В результате, наилучшие показатели точности в задаче определения авторства текстов были продемонстрированы такими признаковыми описаниями как распределение слов («Мешок слов») и распределение N-грамм символов исходного документа. Подобные результаты были также продемонстрированы в исследованиях программных продуктов АА, описанных в разделе 1.1 настоящей работы, из чего следует полагать, что данные признаки являются наиболее информативными в области АА.

Распределение слов, или «Мешок слов» [11]. Данный признак представляет собой вектор в N мерном пространстве, где N -- это мощность словаря уникальных слов, встречающихся на всех текстовых документах выборки. Каждая координата вектора закреплена за отдельным словом, а значением на этой координате является количество употреблений данного слова в заданном тексте. При большом количестве и объёме текстовой выборки размер векторного описания может достигать значения в 10000-15000, что является недостатком данного признака, однако именно «Мешок слов» наиболее полно описывает текстовый документ.

Распределение N-грамм символов [1, 11]. N-грамма -- это упорядоченное множество встречающихся элементов, в качестве элементов могут выступать как слова, так и символы текста. Считается, что для задачи АА наиболее оправдано выделять именно N-граммы символов в их естественном виде (с пунктуационными символами). Распределение N-грамм похоже на признак «Мешок слов» и также представлено вектором на пространстве словаря всех возможных комбинаций символов текста, где значение на каждой координате равно количеству той или иной N-граммы, встречающейся в данном тексте. Чаще всего выделяют 2-, 3-, 4-, 5-граммы символов, однако разные N-граммы показывают разные эффективности [12] для отдельных языков, так, например, задача АА для английского лучше всего решается при использовании биграмм, а для немецкого это уже триграммы. Поэтому нельзя однозначно определить, какая из N-грамм окажется наиболее эффективной применительно к русскому языку: данный факт нуждается в экспериментальной проверке.

Извлеченные признаки нуждаются в дополнительной обработке, так как все веса признакового описания находятся в разных масштабах, что плохо сказывается на точности основного алгоритма, для разрешения этой проблемы используют алгоритмы нормализации весов признаков [13].

где x - исходный вес,

x` - нормализированный вес,

- среднее значение исходных весов на объекте выборки,

max(x) - максимальное значение весов на исходной выборке,

min(x) - минимальное значение весов на исходной выборке.

В текстовой выборке могут находиться тексты разных размеров, и чем больше текст, тем число словоупотреблений будет больше относительно текста средней длины. При условии, что оба текста принадлежат одному автору, классификатор, вероятнее всего, не определит их к одному классу. Исправить ситуацию призвана статистическая мера TF (Term Frequency) - частота слов [14], ее основная идея в том, чтобы поделить количество употреблений конкретного слова в тексте на общее количество словоупотреблений в тексте, в результате чего частотные характеристики будут нормализированы относительно разных текстовых документов.

После частотной нормализации остаётся проблема переоценки некоторых признаков, так, например, предлоги, частицы и союзы встречаются во всех документах очень часто, но при этом они не несут информацию об авторском стиля и являются шумом. Один из подходов, разрешающий эту проблему, был описан выше -- это удаление стоп-слов, однако данная операция достаточно дорогая для реализации. В подобных случаях часто используют статистическую меру IDF (Inverse Document Frequency) - обратная документная частота [14], или отношение количества документов в выборке к количеству документов, в которых встретился искомый признак (слово); ее основная идея состоит в том, чтобы уменьшить большие веса признаков наиболее частотных слов и повысить веса маленьких признаков. Таким образом классификатор будет уделять больше внимания редко встречающимся словам, которые, предположительно, в большей мере являются носителями авторского стиля.

1.2.5 Алгоритм классификации

В задачах АА при подборе алгоритма классификации обычно используют следующие методы [8, 11]: наивный байесовский классификатор, линейная и нелинейная формы метода опорных векторов, а также метод k-ближайших соседей.

Наивный байесовский классификатор [15] - простой классификатор, в основе которого лежит теория вероятностей и теорема Байеса о строгом (наивном) предположении независимости:

p(C|F₁, … , F_n) -вероятность принадлежности документа F к классу С;

p(F₁, … , F_n|C) - вероятность встретить документ F среди документов класса С;

p(C) - безусловная вероятность встретить документ класса С среди выборки;

p(F₁, … , F_n) - безусловная вероятность встретить документ F_n.

Байесовский классификатор представляет текстовый документ в виде множества слов, вероятности которых предположительно не зависят друг от друга. Исходя из этого предположения условная вероятность текстового документа аппроксимируется при помощи произведения условных вероятностей всех слов документа.

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

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

Формула 1.2.5.4 оценивает вероятность принадлежности слова W_ic к классу С. Эта величина равна отношению числа слов W_i_, встречающемся в классе С, к числу всех слов, встречающихся в документах класса С.

В формуле 1.2.5.4 в случае, если встречается слово, которого нет ни в одном документе выборки, то вся условная вероятность документа с этим словом будет равна. Исправить данную ситуацию может сглаживание Лапласа (формула 1.2.5.5), которое строится из допущения, что все слова встречаются в выборке n+1 раз. Посредством совершения всех описанных шагов получаем итоговую формулу байесовского классификатора (формула 1.2.5.6):

Метод опорных векторов [17] - частный случай линейного классификатора (1.2.5.7), использующий L2-регуляризатор и кусочно-заданную функцию потерь:

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

В случае, если объекты выборки нелинейно разделимы, то классический метод опорных векторов будет ошибаться. Единственным способом построить полиномиальную плоскость, способную разделять нелинейные классы, является введение ошибок и штрафов алгоритма за ошибки в минимизируемой функции следующим образом [16]:

K-ближайших соседей [16] - самый простой метрический метод классификации в машинном обучении, его суть состоит объекту из тестовой выборки присваивается тот же класс, к которому принадлежит объект из обучающей выборки, лежащий к нему ближе всего. Для повышения надёжности можно принимать решение более, чем по одной точке обучающей выборки - в этом состоит основной принцип метода, объект относится к тому классу, к которому принадлежит большинство из K ближайших соседей.

Ещё одним методом повышения надёжности предсказания является распределение весов между соседями [16]. Веса ближайших соседей как правило зависят от расстояния до точки - евклидово расстояние от исходной точки тестовой выборки до i-ого ближайшего соседа обучающей выборки.

1.2.6 Оценка результатов

Для оценки качества работы алгоритма машинного обучения используют специальные метрики, наиболее популярными являются следующие метрики: достоверность, точность, полнота, f1-мера. Дано , где

X - множество объектов обучающей выборки,

x - объект обучающей выборки,

Y - множество ответов над объектами обучающей выборки,

y - ответ над отдельным объектом обучающей выборки,

y=a(x) - алгоритм, предсказывающий ответы для объектов множества X.

Достоверность или доля верных ответов - простейшая метрика качества, широко применяемая в задачах машинного обучения [16].

Для описания следующих метрик необходимо представить матрицу ошибок [18], позволяющую классифицировать различные случаи работы бинарного классификатора. В случаях, когда объект относится к классу +1 и алгоритм предсказал +1, то имеет место верное срабатывание алгоритма (ИП), если же при истинном классе +1 алгоритм также предсказывает -1, то это ложное срабатывание алгоритма (ЛН). Если алгоритм предсказывает ответ -1, то это называется пропуском объекта, в случае если объект относился к классу -1, то имеет место быть истинному пропуску (ИН), в ином случае это будет ложным пропуском (ЛП).

Таблица 2

Матрица ошибок

	y = 1	y = - 1
a( x ) = 1	Истинно положительный (ИП)	Ложно положительный (ЛП)
a( x ) = - 1	Ложно негативный (ЛН)	Истинно негативный (ИН)

Далее введём две метрики - точность и полнота. Первая метрика точности показывает насколько можно доверять алгоритму в случае положительного срабатывания. Данная метрика демонстрирует долю ошибки классификатора при выборе того или иного класса, например, к классу N относится 5 объектов, классификатор определил класс N не только к этим 5 объектам, но и к 10 другим объектам, относящимся к другим классам. В результате измерения метрик качества на этом классе получим следующее - достоверность 100 %, точность 33 %; как видно, метрика точности наиболее корректно описала работу алгоритма на этом классе.

Вторая метрика, полнота, оценивает на какой доле объектов +1 класса классификатор срабатывает верно. Исходя из предыдущего примера, классификатор продемонстрирует на классе N полноту 100 %.

Как видно из представленных примеров, полнота и точность могут принимать кардинально разные величины на одном классе, и для более полной оценки алгоритма данные метрики необходимо объединить, для объединения точности и полноты используют F1-меру [19]. Данная мера позволяет наиболее точно оценить работу классификатора на несбалансированных выборках:

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

2. Описание предлагаемого метода АА

2.1 Требования к реализуемому методу

программный индексация документ

Реализованный метод должен в первую очередь показывать достаточную точность определения авторства текстов, требуемая минимальная точность равна 75 %. Метод должен демонстрировать заданную минимальную точность на текстовой выборке, состоящей минимум из 10 авторов русских литературных произведений. Использование всех алгоритмов в методе должно быть аргументировано либо научными фактами, либо экспериментальной апробацией. Каждый использованный алгоритм должен быть оптимизирован гиперпараметрами под задачу АА. Реализованный метод должен быть исследован на разных количествах авторов в диапазоне от 2 до 20, необходимо привести рекомендации к оптимальному количеству авторов. Исследовать поведение метода на текстах разных объёмов в диапазоне от 2 до 60 тысяч символов для каждого текста выборки, представить рекомендации к оптимальному объёму исследуемых текстов.

2.2 Требования к функционалу программной реализации

Программная реализация предложенного метода должна предсказывать авторство текстов из тестовой выборки на основе предварительного анализа обучающей выборки, состоящей из других текстов этих же авторов. Программа должна оценивать качество алгоритма по следующим метрикам: достоверность, точность, полнота, f1-мера. Программная реализация должна предусматривать гибкую настройку параметров метода: количество авторов, количество статей авторов для обучающей и тестовой выборки, гиперпараметры классификаторов, максимальный размер исследуемых текстов. Программа должна представлять визуализацию исследования зависимости качества алгоритма от размера текстов из экспериментальной выборки. Максимальный объём требуемой оперативной памяти, необходимый для работы программы, не должен превышать 1024 Мб. Максимальное время работы программы при определении авторства текста на выборке объёмом из 2000 тысяч символов и 10 авторов не должен превышать 90 секунд.

2.3 Разработка метода

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

Предварительная обработка текстовых данных. Из всех возможных путей по предварительной обработке данных было принято решение оставить только понижение регистра символов текстовых документов. Удаление стоп-слов является ресурсоёмкой задачей, которая вполне может быть решена на этапе отбора признакового описания при применении статистической меры IDF, позволяющей понизить веса больших признаков - часто встречающихся слов. Удаление пунктуационных символов производиться также не будет, ввиду того, что признаковое описание, состоящее из N-грамм, будет извлекаться из исходного текстового документа, так как считается, что N-граммы в их естественном употреблении текста наиболее полно описывают авторский стиль. Нормализация форм слов будет проводиться исключительно для дополнительного эксперимента, данная предобработка данных не войдёт в итоговую модель из-за высокой требовательности к ресурсам оперативной памяти и низкой скорости работы (найденные реализации нормализации форм слов русского языка позволяют производить порядка 200-800 операций в секунду, при объёме текстовой выборки в несколько сотен тысяч слов время работы программы выйдет за установленные нормы).

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

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

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

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

2.4 Проектирование программной реализации метода

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

Рисунок 2. IDEF0 модель метода АА

3. Программная реализация метода АА

3.1 Программная реализация

3.1.1 Общие сведения

Программа проведения авторской атрибуции русских литературных произведений «AuthorAttributor» имеет следующие атрибуты:

· Наименование файла программы - AuthorAttributor.py.

· Размер файла программы - 57 480 байт.

· Версия продукта - 0.1.0

· Название продукта - AuthorAttributor.

· Язык - Русский, English (United Kingdom).

Для корректной работы программы AuthorAttributor.py необходимы системные программные средства, представленные операционной системой Windows 10. Также для функционирования «AuthorAttributor.py» необходим python интерпретатор (версия 3.6.5) со следующими библиотеками: Pandas (версия 0.22.0), NumPy (версия 1.11.1), SkLearn (версия 0.19.1), Pymorphy2(версия 0.3.1), RegExp (версия 3.5.0), OS (версия 16.1.0).

Исходным языком программы «AuthorAttributor.py» является Python 3.6.5. Среда разработки, интерактивная оболочка для языка программирования Python - Jupyter версии 5.4.1.

3.1.2 Функциональное назначение

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

3.1.3 Описание логической структуры

Алгоритм программы. На рисунке 3 приведена блок-схема общего алгоритма программы, описывающая основные структурные единицы и способы их взаимодействия. На рисунке 4 представлено описание функции text_extraction, функция осуществляет считывание текстовых файлов и их разметку по классам авторов. Алгоритмы большинства остальных функций программы построены из узко ориентированных библиотечных методов, и имеют простое алгоритмическое представление в виде последовательного вызова данных методов, в связи с чем нет необходимости в графическом представлении алгоритмов этих структурных единиц программы. Полный код реализованной программы приведён в приложении А данной работы.

Рисунок 3. Общий алгоритм программы.

Рисунок 4. Схема алгоритма функции text_extraction.

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

· list_of_file( directory ) - функция осуществляет получение имен текстовых файлов, находящихся по заданному пути. В качестве единственного аргумента функция принимает на вход строковую переменную directory, описывающую путь к директории с текстовыми файлами. В результате своей работы функция возвращает массив имён текстовых файлов files_in_dir. В случае подачи на вход функции некорректного пути, программа прекращает работу с выдачей системной ошибки.

· read_text_file ( way_to_file, text_size ) - функция осуществляет чтение содержимого текстового файла, находящегося по заданному пути. Функция принимает на вход в качестве аргументов way_to_file - строковая переменная с описанием пути к текстовому файлу и text_size - целочисленная переменная, описывает число символов, которое будет считано из файла. В результате работы функция возвращает строковую переменную text с текстом размера text_size.

· text_extraction (text_size = 60000) - функция предназначена для индексации текстовых документов разных авторов. Функция в качестве аргумента принимает целочисленную переменную text_size (значение по умолчанию 60000), описывающую ограничение на размер каждого текста выборки в символах. Алгоритм данной функции подробно описан на блок-схеме, представленной на рисунке 4. Результатом работы функции является кортеж из 4 массивов (тексты для обучения, тестирования, а также массивы меток классов для обучения и тестирования).

· text_token(text) - функция производящая нормализацию форм слов исходного текста, принимает на вход строковую переменную text с текстом литературного произведения. Далее производится разбиения текста на упорядоченный массив отдельных слов, которые приводятся в нормальную форму при помощи функционала библиотеки pymorphy2 [20]. После нормализации слова вновь склеиваются через пробелы в модифицированный текст, который и является результатом работы функции.

· text_clf_method(algorithm) - функция необходимая для описания классификатора, в качестве аргумента принимает на вход объект классификатора, созданный библиотекой sklearn. В данной функции при помощи метода pipeline [21], несколько основных этапов (извлечение признаков, предварительная обработка признаков) задачи АА объединяются в поток. Результатом работы функции является модифицированный объект классификатора.

· test_methods(clf_methods, text_size=60000) - функция производит тестирование нескольких классификаторов. В качестве аргументов принимает на вход clf_methods - массив объектов базовых параметризированных классификаторов и переменную text_size (значение по умолчанию 60000), описывающую ограничение на размер каждого текста выборки в символах. Функция осуществляет обучение каждого классификатора на обучающей выборке текстов и тестирует полученный метод на тестовой выборке. После чего при помощи предсказанных меток классов для каждого текста из тестовой выборки и истинных меток классов производится оценка качества алгоритма. Для этой задачи используется метод metrics [22] библиотеки sklearn. Результат работы функции - текстовое сообщение со значениями метрик качества для каждого классификатора.

· size_dependence(method, list_of_sizes) - функция предназначена для исследования зависимости качества классификатора от максимального размера текстов из обучающей и тестовой выборок. Функция принимает на вход в качестве аргументов method - объект классификатора с параметрами, а также list_of_sizes - массив со значениями максимальных размеров текстов. Функция последовательно обучает и тестирует классификатор на выборках, состоящих из различного размера текстов, на каждой итерации оценивается качество алгоритма (достоверность, точность, полнота и f1-мера), для каждой из метрик строится график зависимости величины метрики от размера текстов. Результатом работы функции являются 4 файловых дескриптора, содержащих графики по каждой метрике.

3.1.4 Входные данные

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

· файловое расширение - txt;

· язык содержания файла - русский;

· разрешённые кодировки содержания - 1251, CP866, UTF8;

· минимальный размер файла - 10 Кб;

· максимальный размер файла - 4 Гб;

· рекомендуемый размер файла - 150 Кб.

На рисунке 5 представлена необходимая файловая структура входных данных. Все текстовые файлы разделены на два подмножества, первое необходимо для обучения алгоритма и содержится в папке Train, второе - для тестирования алгоритма (папка Test). Папки подвыборок содержат папки авторов, названия этих папок должны совпадать в обоих подмножествах, однако их количество может отличаться. В каждой папке автора содержатся текстовые файлы с произведениями этого автора, множества произведений одного автора из папки Train и Test не должны пересекаться, если того не предполагают условия эксперимента.

Рисунок 5. Файловая структура входных данных.

3.1.5 Выходные данные

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

· Ошибки в работе программы, системные сообщения, предупреждения интерпретатора и среды разработки выводятся программой в стандартный поток данных.

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

· Изображения графиков зависимости метрик качества метода от размера исходной выборки представлены в виде файлов с расширениями jpg и с названиями соответственно исследуемой метрики (accuracy, precision, recall, f1-score). Файлы сохраняются в директории хранения основной программы «AuthorAttributor.py».

3.2 Тестирование программы

После разработки программного кода, реализованное ПО было протестировано на тестовой выборке, описанной в разделе 4.1. текущей работы, в результате тестирования было определено соответствие фактического и необходимого функционала программы. Основным критерием проверки реализованной программы является время работы программы и необходимые ресурсы ЭВМ.

В таблице 3 представлены данные по тестированию ПО на затраты ресурсов ЭВМ. Программа была протестирована при использовании 4 основных классификаторов, с применением комбинации признаков распределения слов и 5-грамм символов текста, все признаки были нормализированы и обработаны при помощи меры TF-IDF. Каждый из подобных режимов был протестирован с использованием нормализации форм слов и без нормализации. Как видно из представленной таблицы 3, нормализация форм слов является вычислительной операцией, требующей больших затрат как по времени, так и по ОЗУ, при этом не давая критического эффекта повышения качества, в результате чего данная операция не войдёт в итоговую программу АА. Также все остальные алгоритмы без использования нормализации форм слов показывают хорошие результаты по затратам ресурсов ЭВМ, в следствие данные подходы будут использованы в дальнейшей работе.

Таблица 3

Тестирование ПО на затраты ресурсов

Классификатор	Предварительная обработка признаков	Время, с	ОЗУ, Мб
Наивный байесовский классификатор	без нормализации	12	67
	с нормализацией	543	259
Метод опорных векторов (линейный)	без нормализации	16	73
	с нормализацией	552	256
Метод опорных векторов (нелинейный)	без нормализации	16	74
	с нормализацией	549	253
k-ближайших соседей	без нормализации	13	66
	с нормализацией	561	245

3. Описание исследования

3.1 Экспериментальная выборка

Для проведения эксперимента были отобраны русскоязычные современные литературные произведения. Для выборки были использованы ознакомительные фрагменты произведений объёмами от 60000 до 120000 символов, выложенные в свободный доступ порталом litres.ru, как следствие, все авторские права издателей и авторов произведений были полностью соблюдены. Всего было отобрано 120 произведений 20 авторов, то есть по 6 произведений для каждого автора. Совокупный объём выборки составил 1823456 символов или 45,6 печатных листов. Все произведения были опубликованы в период с 1990 по 2017 годы, предполагается, что выборка из произведений одной эпохи будет более репрезентативна. Все произведения выборки являются романами и относятся к следующим жанрам: художественная литература и фантастика.

Вся выборка была случайным образом разделена на две равные части, одна предназначена для обучения алгоритма, другая - для тестирования. Обучающая и тестовая выборка содержат по три произведения каждого автора. Все произведения записаны в файлы с расширением .txt кодировки UTF8, каждый текстовый файл назван одноименно с записанным в него произведением. Вся выборка разбита на 20 папок, каждая папка носит имя одного автора и содержит 6 текстовых файлов с произведениями этого автора.

3.2 Основной эксперимент

Для определения лучшего подхода АА была проведена серия экспериментов: были исследованы различные классификаторы, описанные в главе 2.3 с применением следующих признаков, извлекаемых из текстов: «мешок слов», 2-, 3-, 4-, 5-граммы символов, «Мешок слов» + 5-граммы. Все признаки предварительно обработаны алгоритмами нормализации и TF-IDF. Все алгоритмы были оптимизированы гиперпараметрами классификаторов, были измерены метрики качества на каждом эксперименте, полученные данные приведены в таблице 4.

Наиболее высокая точность была продемонстрирована наивным байесовским классификатором с применением комбинации признаков «Мешок слов» + 5-граммы символов, после оптимизации гиперпараметров средневзвешенное качество данного подхода достигло 0.87. Остальные подходы показали существенно худший результат, методы опорных векторов продемонстрировали долю верных ответов на уровне 0.7 , однако линейная форма классификатора показала наивысший результат достоверности при использовании 3-грамм, а нелинейная форма при использовании 5-грамм символов. Метод k-ближайших соседей показал наихудший результат, не превышающий 0.56 при оценке доли верных ответов, также значение гиперпараметров «по умолчанию» оказалось для данного классификатора оптимальным. Остальные методы показали уверенное улучшение по всем показателям качества после оптимизации гиперпараметров классификаторов.

Таблица 4

Качество классификатора в зависимости от признаков и оптимизации гиперпараметров

Классификатор	Признак	Качество классификатора
		До оптимизации параметров	После оптимизации параметров
		Достоверность	Точность	Полнота	F1	Достоверность	Точность	Полнота	F1
Наивный байесовский классификатор	Мешок слов	0.48	0.52	0.48	0.43	0.84	0.83	0.84	0.81
	2-грамм	0.63	0.62	0.63	0.58	0.7	0.8	0.7	0.72
	3-грамм	0.54	0.59	0.54	0.52	0.77	0.82	0.78	0.77
	4-грамм	0.57	0.51	0.57	0.5	0.8	0.87	0.8	0.8
	5-грамм	0.61	0.53	0.61	0.54	0.83	0.85	0.83	0.82
	Мешок слов + 5-грамм	0.53	0.52	0.53	0.49	0.87	0.86	0.87	0.85
Метод опорных векторов (линейный)	Мешок слов	0.49	0.43	0.48	0.44	0.51	0.45	0.51	0.46
	2-грамм	0.6	0.6	0.62	0.58	0.65	0.71	0.65	0.63
	3-грамм	0.65	0.69	0.67	0.64	0.7	0.74	0.7	0.69
	4-грамм	0.58	0.63	0.6	0.58	0.63	0.66	0.63	0.6
	5-грамм	0.65	0.64	0.67	0.62	0.7	0.69	0.7	0.67
	Мешок слов + 5-грамм	0.59	0.61	0.62	0.59	0.63	0.63	0.63	0.6
Метод опорных векторов (нелинейный)	Мешок слов	0.52	0.47	0.41	0.42	0.48	0.44	0.48	0.42
	2-грамм	0.6	0.62	0.6	0.59	0.65	0.71	0.65	0.63
	3-грамм	0.5	0.51	0.55	0.5	0.65	0.7	0.65	0.63
	4-грамм	0.55	0.57	0.56	0.53	0.59	0.6	0.59	0.55
	5-грамм	0.61	0.63	0.67	0.63	0.7	0.69	0.7	0.67
	Мешок слов + 5-грамм	0.49	0.55	0.49	0.52	0.55	0.57	0.55	0.53
K-ближайших соседей	Мешок слов	0.41	0.49	0.41	0.39	0.41	0.49	0.41	0.39
	2-грамм	0.48	0.63	0.48	0.49	0.48	0.63	0.48	0.49
	3-грамм	0.5	0.59	0.5	0.5	0.5	0.59	0.5	0.5
	4-грамм	0.55	0.54	0.56	0.51	0.55	0.54	0.56	0.51
	5-грамм	0.56	0.53	0.56	0.51	0.56	0.53	0.56	0.51
	Мешок слов + 5-грамм	0.4	0.56	0.4	0.42	0.4	0.56	0.4	0.42

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

Эксперименты показали, что полный отказ от предварительной обработки серьёзно повышает качество наивного байесовского классификатора и линейного метода опорных векторов. В то же время нелинейный метод опорных векторов показал наихудший результат без нормализации признаков, что связано с особенностями математического аппарата классификатора. По итогам данного эксперимента максимальная точность была повышена с 0.85 до 0.95.

Таблица 5

Качество классификатора в зависимости от предобработки признаков

Классификатор	Предварительная обработка признаков	Качество классификатора
		Достоверность	Точность	Полнота	f1 метрика
Наивный байесовский классификатор	без обработки	0.91	0.95	0.91	0.91
	нормализация	0.91	0.92	0.91	0.91
	TF-IDF	0.87	0.9	0.87	0.87
	нормализация + TF-IDF	0.87	0.86	0.87	0.85
Метод опорных векторов (линейный)	без обработки	0.76	0.89	0.76	0.76
	нормализация	0.64	0.56	0.64	0.58
	TF-IDF	0.44	0.52	0.44	0.44
	нормализация + TF-IDF	0.7	0.74	0.7	0.69
Метод опорных векторов (нелинейный)	без обработки	0.06	0.01	0.06	0.01
	нормализация	0.7	0.67	0.7	0.67
	TF-IDF	0.44	0.52	0.44	0.44
	нормализация + TF-IDF	0.7	0.69	0.7	0.67
K-ближайших сосед...