Файл: Средства разработки клиентских программ (ГЛАВА 1. АНАЛИЗ СУЩЕСТВУЮЩИХ РЕШЕНИЙ).pdf

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

Извлечение признаков – ключевой этап любой задачи машинного обучения, именно признаковое описание исходные данных наиболее всего влияет на итоговое качество разработанного алгоритма. При обработке текстов необходимо представить каждый документ в понятном основному алгоритму числовом формате. В задаче АА необходимо выделить такие числовые характеристики каждого текста, которые будут максимально полно описывать стиль автора. В работе [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], или отношение количества документов в выборке к количеству документов, в которых встретился искомый признак (слово); ее основная идея состоит в том, чтобы уменьшить большие веса признаков наиболее частотных слов и повысить веса маленьких признаков. Таким образом классификатор будет уделять больше внимания редко встречающимся словам, которые, предположительно, в большей мере являются носителями авторского стиля.

В задачах АА при подборе алгоритма классификации обычно используют следующие методы [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-ого ближайшего соседа обучающей выборки.

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

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

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

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

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

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

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

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

Таблица 2

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

Далее введём две метрики – точность и полнота. Первая метрика точности показывает насколько можно доверять алгоритму в случае положительного срабатывания. Данная метрика демонстрирует долю ошибки классификатора при выборе того или иного класса, например, к классу 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 секунд.