Государственное образовательное учреждение высшего профессионального образования «Донецкий национальный технический университет», г. Донецк
83001, г. Донецк, ул. Артёма, 58
СРАВНЕНИЕ НЕКОТОРЫХ МЕТОДОВ МАШИННОГО ОБУЧЕНИЯ ДЛЯ АНАЛИЗА ТЕКСТОВЫХ ДОКУМЕНТОВ
State Educational Institution of Higher Education «Donetsk national technical University», Donetsk city
83001, Donetsk, Artema str., 58
Державна освітня установа вищої професійної освіти «Донецький національний технічний університет», м. Донецьк
83001, м. Донецьк, вул. Артема, 58
В статье рассматривается механизм работы различных методов машинного обучения, которые используются для построения модели многоклассовой классификации слабоструктурированных текстовых документов. Задача модели состоит в отнесении документа к одному или нескольким классам, на основе анализа текстового содержания документа. Проанализирована эффективность работы различных композиций алгоритмов классификации на основе коллекции текстовых документов. Приведены результаты выполненных экспериментов, подтверждающие эффективность составленной модели, используемой для улучшения качества анализа текста. При тестировании на реальных данных наилучший результат показала композиция, состоящая из метода опорных векторов и дерева принятия решений.
The article discusses the mechanism of operation of various machine learning methods that are used to build a model of multi-class classification of semi-structured text documents. The task of the model is to classify the document to one or several classes, based on the analysis of the textual content of the document. Analyzed the effectiveness of the various compositions of the classification algorithms based on a collection of text documents. The results of the performed experiments are presented, confirming the effectiveness of the model used to improve the quality of text analysis. When testing on real data, the best result was shown by the composition consisting of the support vector machine and the decision tree.
У статті розглядається механізм роботи різних методів машинного навчання, які використовуються для побудови моделі багатокласової класифікації слабоструктурованих текстових документів. Завдання моделі полягає у віднесенні документа до одного або декількох класів, на основі аналізу текстового змісту документа. Проаналізовано ефективність роботи різних композицій алгоритмів класифікації на основі колекції текстових документів. Наведено результати виконаних експериментів, що підтверджують ефективність складеної моделі, використовуваної для поліпшення якості аналізу тексту. При тестуванні на реальних даних найкращий результат показала композиція, що складається з методу опорних векторів і дерева прийняття рішень.
Актуальность работы
Обмен информацией является неотъемлемой частью нашей жизни. В связи со стремительным развитием технического прогресса, появлением новых информационных технологий все чаще текстовые данные стали храниться и обрабатываться в электронном виде. В большинстве организаций значительная часть полезных знаний содержится в документальных базах данных. Как следствие, комфортная работа с такими большими объёмами информации затрудняется. Сложность обработки этих массивов увеличивается пропорционально их объему. Отсутствие возможности получать требуемую информацию по конкретной теме делает бесполезной большую часть накопленных данных, представленных текстами в электронном виде.
Такая ситуация обуславливает повышенный интерес к области Text mining – методам автоматического извлечения и обработки знаний из текстовых документов. Получение знаний в автоматическом режиме затрудняется слабой структурированностью текстов на естественном языке. Такие знания могут быть с лёгкостью извлечены экспертом, но с учётом огромного количества электронных документов их эффективная обработка человеком становится весьма затратной как по времени, так и по ресурсам.
Извлечение знаний имеет своей конечной целью информационную поддержку эксперта или автоматизированной системы при принятии проектных решений. В документах, созданных специалистами, могут быть описаны подходы к решению различных проблем, рекомендации к подбору параметров и прочие знания, полезные в различных областях деятельности организации.
Использование автоматической текстовой классификации позволяет сократить время на обработку электронных документов, но также не стоит забывать об особенностях языка, на котором составлены документы.
Востребованность в эффективном решении задачи автоматической классификации ЕЯ-текстов привела к бурному развитию новых методов и повышению эффективности уже существующих подходов.
Цель данной статьи – анализ эффективности применения композиций методов машинного обучения для задач классификации ЕЯ-текстов.
Далее будут рассмотрены различные композиции алгоритмов машинного обучения, используемые для классификации текстов, с точки зрения качества анализа текстовых документов, а также проблемы, которые возникают при применении этих методов.
Основное содержание работы
Процедура автоматической классификации текстов обычно включает две основные части: представление текстов в виде векторов признаков и построение классификатора на созданном массиве векторов. Необходимость представления текстов в виде векторов признаков определяется тем обстоятельством, что все методы классификации требуют, чтобы классифицируемые объекты были представлены в виде последовательностей чисел одинакового размера и одинакового формата.
Стандартное представление документа, используемое в текстовой классификации, является векторной моделью, представленной при помощи статистической меры – tf-idf. Она используется для оценки важности слова в контексте документа, входящего в некоторый текстовый корпус. Согласно определению, данная мера есть вес некоторого слова, который пропорционален количеству употребления этого слова в документе и обратно пропорционален частоте употребления слова в других документах коллекции [1] и вычисляется по формуле:
где tf (term frequency – частота терма) – отношение числа вхождения некоторого терма к общему количеству термов документа. Таким образом, оценивается важность терма w в пределах отдельного документа d и D – число документов в корпусе [1]. Частота слова оценивает важность слова Wi в пределах отдельного документа:
где nt – число вхождений слова i в документ;
Σk nk – общее число слов в данном документе.
idf (inverse document frequency – обратная частота документа) – инверсия частоты, с которой некоторое слово встречается в документах коллекции. Учёт idf уменьшает вес широкоупотребительных слов. Для каждого уникального слова в пределах конкретной коллекции документов существует только одно значение idf [1]:
где |D| – количество документов в корпусе;
|{d ∈ D : w ∈ d}| – количество документов, в которых встречается слово wi.
Когда tf-idf функция применена ко всем словам во всех документах корпуса, слова можно отсортировать по полученным весам. Более высокий tf-idf вес говорит о том, что слово важно для данного документа, и в то же время достаточно редко употребляется в других документах корпуса. Это зачастую можно интерпретировать как знак того, что слово является важным для данного конкретного документа и может быть использовано, чтобы точно описать документ. Статистическая мера tf-idf предоставляет хорошую эвристику для определения кандидатов в ключевые слова, и этот метод (и многие его модификации) за годы исследований показал свою эффективность [2]. Данный метод в связи с эффективностью и простотой продолжает активно применяться для построения векторной модели, которая будет использоваться для классификации. Рассмотрим некоторые методы классификации.
Алгоритм классификации SVM, предложенный В. Н. Вапником [3], является контролируемым алгоритмом обучения, и принадлежит к группе методов детерминистского подхода. Это двоичный линейный классификатор, который отделяет позитивный и негативный примеры в тестовом наборе. Метод ищет гиперплоскости, отделяющие положительные примеры от отрицательных примеров, гарантируя, что граница между ближайшими позитивами и негативами является максимальной.
Метод SVM базируется на таком постулате [4]: наилучшая разделяющая плоскость – это та, которая максимально далеко отстоит от ближайших до нее точек обоих классов. То есть задача метода SVM состоит в том, чтобы найти разделяющую полосу с максимальной шириной, поскольку, чем шире полоса, тем увереннее можно классифицировать объекты, соответственно, в метод SVM считается, что самая широкая полоса является наилучшей. Границами полосы являются две параллельные гиперплоскости с направляющим вектором w. Точки, ближайшие к разделяющей гиперплоскости, расположены точно на границах полосы, при этом сама разделяющая гиперплоскость проходит ровно посередине полосы (рис. 1).
Еще одним методом машинного обучения является латентно-семантический анализ (LSA, Latent Semantic Analysis) – это теория и метод для извлечения контекстно-зависимых значений слов при помощи статистической обработки больших наборов текстовых данных [5]. LSA был запатентован в 1988 году и относится к классификаторам, основанным на функциях подобия. В области информационного поиска данный подход называют латентно семантическим индексированием (LSI, Latent Semantic Indexing). LSA также работает с векторным представлением типа «мешка слов» текстовых единиц. Текстовый корпус представляется в виде числовой матрицы «слово-текст», строки которой соответствуют словам, а столбцы – текстовым единицам.
Объединение слов в темы и представление текстовых единиц в пространстве тем осуществляется путем применения к данной матрице одного из матричных разложений. Наиболее популярными являются: сингулярное разложение [5] и факторизация неотрицательных матриц [6]. Согласно теореме о сингулярном разложении, любая вещественная прямоугольная матрица может быть разложена на произведение трех матриц: A = USVT, где A ∈ Rm×n, матрицы U ∈ Rm×k и V ∈ Rn×k – ортогональные, а S ∈ Rk×k – диагональная матрица, значения на диагонали которой называются сингулярными значениями матрицы A, VT – транспонированная матрица.
Таким образом, каждое слово и текст представляются при помощи векторов в общем пространстве размерности k – пространстве гипотез. Сходство между любой комбинацией слов и/или текстов легко вычисляется при помощи скалярного произведения векторов. Как правило, выбор k зависит от поставленной задачи и подбирается эмпирически. Если выбранное значение k слишком велико, то метод теряет свою мощность и приближается по характеристикам к стандартным векторным методам. Слишком маленькое значение k не позволяет улавливать различия между похожими словами или текстами [4].
Дерево принятия решений представляет собой простой классификатор и широко используется в задачах классификации текстов.
«Деревья решений» (классификации) – это метод, позволяющий предсказывать принадлежность наблюдений или объектов к тому или иному классу категориальной зависимой переменной в соответствии со значениями одной или нескольких продикторных переменных [7].
Итак, дерево решений, подобно его «прототипу» из живой природы, состоит из «ветвей» и «листьев». Ветви (ребра графа) хранят в себе значения атрибутов, от которых зависит целевая функция; на листьях же записывается значение целевой функции. Существуют также и другие узлы – родительские и потомки – по которым происходит их разветвление (рис. 2).
Один из способов автоматического построения деревьев решений заключается в последовательном разбиении множества обучающих документов на классы до тех пор, пока в классе не останется документов, определенных только в одну из категорий. На каждом этапе в качестве узла дерева выбирается терм содержащий множество всех возможных значений и определяется условие для ветвей, затем множество документов разбивается на два классов, каждый из которых имеет свои условия. Обычно построенное дерево решений является сильно детализированным (эффект переобучения), поэтому применяются различные алгоритмы усечения дерева. Широкое применение получили алгоритмы ID3 [8] и C4.5 [8].
Оценкой качества использования методов автоматической классификации текстов является сравнение результатов их тестовых испытаний с теми оценками, которые дают этим методам эксперты. При этом «идеальным» алгоритмом считается тот, для которого выводы, сделанные по результатам тестирования, согласуются с мнением экспертов оценщиков [9].
Одним из показателей критериев при оценке качества, которое реализуется с использованием программной реализации метода классификатора, является точность. Точность (precision) классификации в пределах класса – это доля найденных классификатором документов, действительно принадлежащих данному классу, относительно всех документов, которые система отнесла к этому классу [10]. Точность классификации определяется следующим образом: считается отношение количества правильно классифицированных документов, к общему количеству классифицируемых документов.
Сравнение классификаторов при использовании в их составе различных методов является довольно сложной задачей по причине того, что разные входные данные могут приводить к различным результатам. Чтобы провести сравнение различных композиций, необходимо выполнить их построение и вычисление эффективности на одинаковых наборах документов для обучения и тестирования.
Для апробации предложенных методов классификации был создан тестовый корпус, состоящий из пяти тысяч текстовых документов, который описывает факты узкой предметной области. В качестве исходных данных для классификации используется массив текстовых документов на русском языке. Каждый документ подвергается форматированию. То есть преобразованию данных к единому формату с сохранением основного логически-структурного содержания информации. Также каждый документ подвергается преобразованию при помощи формулы tf-idf, в результате чего мы получаем интересующее нас описание документа – вектор признаков, который и подается на вход классификатору. Для каждого документа, в соответствии с выбранной метрикой, рассчитывается вероятность его принадлежности к каждому классу, и документ относится к соответствующей тематике.
На имеющихся исходных данных были протестированы следующие классификаторы и их композиции, которые состоят из:
- преобразование текста в вектор с помощью формулы tf-idf. Использование вектора для классификации при использовании метода support vector machine, которую условно будем обозначать T-I+SVM;
- преобразование текста в вектор с помощью формулы tf-idf. Использование вектора для классификации при использовании метода Latent Semantic Analysis, которую условно будем обозначать T-I+ LSA;
- преобразование текста в вектор с помощью формулы tf-idf. Использование вектора для классификации при использовании метода дерево принятия решений, которую условно будем обозначать T-I+D;
- преобразование текста в вектор с помощью формулы tf-idf. Использование вектора для классификации при помощи композиции методов support vector machine и дерево принятия решений, которую условно будем обозначать T-I+SVM+D;
- преобразование текста в вектор с помощью формулы tf-idf. Использование вектора для классификации при помощи композиции методов Latent Semantic Analysis и дерево принятия решений, которую условно будем обозначать T-I+LSA+D;
В зависимости от того, какая композиция будет использована, будет меняться и качество классификации, что представлено в табл. 1. В ней приведены данные проведенных экспериментов.
| Название композиций | Точность, % |
|---|---|
| T-I+SVM | 88 |
| T-I+LSA | 85 |
| T-I+D | 80 |
| T-I+SVM+D | 93 |
| T-I+LSA+D | 91 |
В результате серии экспериментов классификаторы, тестируемые на русскоязычных текстовых документах, показали себя хорошо. Лучший результат был достигнут при использовании композиции, состоящей из метода опорных векторов и дерева принятия решений (T-I+SVM+D). Процент правильно классифицированных документов довольно высок, однако он ниже, чем при использовании этих же классификаторов на англоязычном тексте [11]. При этом наилучшим методом классификации считается тот, для которого выводы, сделанные системой, согласуются с мнением экспертов оценщиков. Стоит отметить, что использование данных методов классификации на русскоязычных текстах напрямую зависит не только от качества работы и гибкости выбранного классификатора, но и от морфологии языка, на котором составлены тексты, содержащиеся в массиве документов.
Выводы
В результате проведения серии экспериментов и основываясь на точности классификации, можно прийти к перечисленным далее выводам:
- Рассмотрена задача автоматической классификации текстовых документов.
- Точность комбинированного метода классификации оказалась выше относительно остальных методов. А именно, композиции, объединяющей в себе два классификатора – T-I+SVM+D.
Направления дальнейших исследований можно сформулировать следующим образом:
- Стоит обратить внимание на то, что подбор большего количества признаков для классификации документов при проведении экспериментов может улучшить качество классификации.
- Построение дополнительной обработки, такой как морфологический анализ, просто необходимо в связи с тем, что русский язык является флективным, что может улучшить качество работы классификатора.
Список литературы
1. Епрея А. С. Автоматическая классификация текстовых документов [Текст] / А. С. Епрея // Математические структуры и моделирование. – 2010. – № 21. – С. 65–81.
2. Недяльченко О. С. Этапы и методы автоматического извлечения ключевых слов [Текст] / О. С. Недяльченко // Молодой ученый. – 2017. – № 22. – С. 60.
3. Choosing Multiple Parameters for Support Vector Machines [Текст] / О. Chapelle, V. Vapnik, O. Bousquet, S. Mukherjee // Machine Learning. – 2002. – Vol. 46, № 1. – P. 131–159.
4. Landauer T. K. An Introduction to Latent Semantic Analysis [Электронный ресурс] / T. K. Landauer, P. Foltz, D. Laham // Discourse Processes. – 1998. – Vol. 25. – P. 259–284.
URL: http://lsa.colorado.edu/papers/dp1.LSAintro.pdf (дата обращения 23.10.2018).
5. Kim H. Nonnegative Matrix Factorization Based on Alternating Nonnegativity Constrained Least Squares and Active Set Method [Электронный ресурс] / H. Kim, H. Park // SIAM Journal on Matrix Analysis and Applications, 2008. – Vol. 30, № 2. – P. 713–730.
URL: http://www.cc.gatech.edu/~hpark/papers/simax-mmf.pdf (дата обращения 23.10.2018).
6. Воеводин В. В. Матрицы и вычисления. [Текст] / В. В. Воеводин, Ю. А. Кузнецов. – М. : Наука, 1984. – С. 320.
7. Дорогов В. Г. Введение в методы и алгоритмы принятия решений [Текст] : Учебное пособие / В. Г. Дорогов, Я. О. Теплова. – М. : ИД ФОРУМ, ИНФРА-М, 2012. – С. 240.
8. Паклин Н. Б. Бизнес-аналитика: от данных к знаниям [Текст] : Учебное пособие / Н. Б. Паклин, В. И. Орешков. – 2-е изд. – СПб : Питер, 2013. – С. 706.
9. Агеев М. С. Официальные метрики РОМИП2004 [Текст] / М. С. Агеев, И. Е. Кураленко // Российский семинар по Оценке Методов Информационного Поиска (РОМИП 2004). – Пушкино, 2004. – С. 214.
10. Живинов А. Л. Влияние изменения размерности вектор-контуров изображений на их меру близости [Текст] / А. Л. Живинов, В. В. Зуев // Вопросы радиоэлектроники. – 2010. – Т. 1., № 1. – С. 165–170.
11. Ageev M. Text Categorization Tasks for Large Hierarchial Systems of Categories [Текст] / M. Ageev, B. Dobrov, N. Loukachevitch // SIGIR 2002 Workshop on Operational Text Classification Systems / Eds. F. Sebastiani, S. Dumas, D. D. Lewis, T. Montgomery, I. Moulinier. – Univ. of Tampere, 2002. – P. 49–52.
12. Павлыш В. Н. Проект построения алгоритма классификации текстовых документов [Текст] / В. Н. Павлыш, Е. И. Бурлаева // Проблемы искусственного интеллекта. – Донецк : ГУ ИПИИ. – 2017. – № 4 (7). – С. 24–32.
13. Павлыш В. Н. Задача классификации информации при формировании баз данных в компьютерных обучающих системах [Текст] / В. Н. Павлыш, С. А. Зори, Е. И. Бурлаева // Проблемы искусственного интеллекта. – Донецк : ГУ ИПИИ. – 2018. – № 4 (11). – С. 71–81.