Разработка информационной системы по определению тематики текста с использованием алгоритмов кластеризации

Андрей Дубаков

Разработка информационной системы по определению тематики текста с использованием алгоритмов кластеризации

В данной работе рассматриваются технологии интеллектуального анализа текстов, а также подходы к визуализации результатов анализа. Изучены алгоритмы выделения ключевых слов из текстовых документов и особенности кластеризации многомерных данных. Реализован программный модуль для извлечения ключевых слов и кластерного анализа на языке Python, а также приложение для визуализации результатов анализа текста на языке C# с использованием WPF. Разработанная информационная система позволяет производить интеллектуальный анализ текстов квалификационных работ студентов, визуально оценивать кластерную структуру набора документов, предоставляет данные для анализа причин формирования кластеров и позволяет провести сравнение студенческих работ и файлов УМК по ключевым словам. В ходе эксперимента было выявлено, что чаще всего работы одного направления находятся в одном кластере. В некоторых случаях, документы распределяются между несколькими соседними кластерами. При этом, ключевые слова документов, представленных в таких кластерах, так или иначе соответствуют тематикам, которые изучаются в рамках данного направления.

Информатика

Дипломы

Вуз: Тюменский государственный университет (ТюмГУ)

ID: 5f474d8acd3d3e0001751256

UUID: 755f6990-ca59-0138-220a-0242ac180006

Язык: Русский

Опубликовано: больше 3 лет назад

Просмотры: 44

10.88

Андрей Дубаков

Комментировать 12

Рецензировать 0

Скачать - 529,7 КБ

Поделиться работой

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное автономное образовательное учреждение высшего образования «ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» ИНСТИТУТ МАТЕМАТИКИ И КОМПЬЮТЕРНЫХ НАУК Кафедра программного обеспечения РЕКОМЕНДОВАНО К ЗАЩИТЕ В ГЭК И ПРОВЕРЕНО НА ОБЪЕМ ЗАИМСТВОВАНИЯ Заведующий кафедрой к.т.н., доцент _________М. С. Воробьева _________________2019 г. ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА (бакалаврская работа) Разработка информационной системы по определению тематики текста с использованием алгоритмов кластеризации 02.03.03. Математическое обеспечение и администрирование информационных систем Выполнил работу Студент 4 курса очной формы обучения Дубаков Андрей Александро вич Руководитель работы Воробьева Марина г. Тюмень, 2019

к.т.н., доцент Сергеевна Оглавление ВВЕДЕНИЕ......................................................................................... 3 Глава 1. ИЗУЧЕНИЕ ТЕХНОЛОГИЙ АНАЛИЗА ДАННЫХ И ПОСТАНОВКА ЗАДАЧИ.....................................................................4 1.1 Постановка задачи...................................................................7 1.2 Математическая постановка задачи.......................................8 1.3 Выбор алгоритмов для обработки данных.............................10 1.4 Технологии для программной реализации обработки данных ....................................................................................................... 14 ГЛАВА 2. Разработка модуля для анализа текстовых данных......16 2.1 Подготовка данных.................................................................16 2.2 Программная реализация обработки данных.......................23 Глава 3. Разработка визуализатора................................................30 3.1 Структура данных...................................................................30 3.2 Функционал приложения.......................................................31 3.2 Демонстрация работы приложения.......................................36 ЗАКЛЮЧЕНИЕ................................................................................. 41 Список литературы.......................................................................... 42 Приложение 1.................................................................................. 44 Приложение 2.................................................................................. 48 Приложение 3.................................................................................. 51 Приложение 4.................................................................................. 57 2

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

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

ГЛАВА 1. ИЗУЧЕНИЕ ТЕХНОЛОГИЙ АНАЛИЗА ДАННЫХ И ПОСТАНОВКА ЗАДАЧИ Интеллектуальный анализ данных представляет собой процесс обнаружения пригодных к использованию сведений в крупных наборах математический тенденций, данных. анализ Для для существующих в этого выявления данных. применяется закономерностей Такие и закономерности нельзя обнаружить при традиционном просмотре данных, по причине большой сложности или чрезмерного объема данных [1]. Результаты интеллектуального анализа данных могут применяться по следующим сценариям:  Прогнозирование: Оценка продаж, прогнозирование нагрузки сервера или времени простоя сервера и т.п.  Риск и вероятность: Выбор наиболее подходящих заказчиков для целевой рассылки, определение точки равновесия для рискованных сценариев, назначение вероятностей диагнозам или другим результатам  Рекомендации по: Определение продуктов, которые скорее всего, быть проданы вместе, создание рекомендаций  Выявление последовательностей: Анализ выбора заказчиков во время совершения покупок, прогнозирование следующего возможного события 5

 Группирование: Разделение заказчиков или событий на кластеры связанных элементов, анализ и прогнозирование общих черт Рассмотрим основные задачи интеллектуального анализа данных. Задача классификации – для каждого объекта определяется категория или класс, которому он принадлежит. для решения задачи необходимо, чтобы множество классов было известно заранее и было бы конечным и счетным. Задача регрессии – во многом схожа с задачей классификации, но в ходе ее решения производится поиск шаблонов для определения числового значения. Иными словами, предсказываемый параметр здесь, как правило, число из непрерывного диапазона. Отдельно значений выделяется на основании последовательности (или задача прогнозирования новых имеющихся значений числовой нескольких последовательностей, между значениями в которых наблюдается корреляция). При этом могут учитываться имеющиеся тенденции (тренды), сезонность, другие факторы. Классическим примером является прогнозирование цен акций на бирже. Задача кластеризации - заключается в делении множества объектов на группы (кластеры) схожих по параметрам. При этом, в отличие от классификации, число кластеров и их характеристики могут быть заранее неизвестны и определяться в 6

ходе построения кластеров исходя из степени близости объединяемых объектов по совокупности параметров. Анализ отклонений позволяет отыскать среди множества событий те, Отклонение которые может существенно отличаются от о необычном сигнализировать каком-то нормы. событии или, например, об ошибке ввода данных оператором. Интеллектуальный анализ текстов (англ. text mining) — направление является в искусственном получение документов, интеллекте, информации основываясь на из целью которого коллекций применении текстовых эффективных в практическом плане методов машинного обучения и обработки естественного языка. Название «интеллектуальный анализ текстов» перекликается с понятием «интеллектуальный анализ данных» (англ. data mining), что выражает схожесть их целей, подходов к переработке информации и сфер применения; разница проявляется лишь в конечных методах, а также в том, что данные хранятся в хранилищах и базах данных, а не электронных библиотеках и корпусах текстов. Ключевыми данных группами являются: задач интеллектуального категоризация текстов, анализа извлечение информации и информационный поиск, обработка изменений в коллекциях текстов, а также разработка средств представления информации для пользователя. Категоризация документов заключается в отнесении документов из коллекции к одной или нескольким группам (классам, кластерам) схожих 7 между собой текстов.

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

Если текст подвергся одному, а лучше всем этапам анализа текста (морфологический даст БНФ, синтаксический – связи между словами, семантический – смысловую карту связей), можно получить более точную информацию о тексте, хоть это и более затратно, синтаксического к примеру, разбора на (при основании наличии деревьев синтаксической разметки). Важнейшим этапом в задаче извлечения ключевых фраз является расчет их весов информативности, который позволяет оценить их значимость по отношению друг к другу в документе. Для каждой из отобранных ключевых фраз рассчитываются признаки, которые позволяют судить о важности кандидата для данного документа. Набор отобранных ключевых фраз ранжируется по значениям признаков, например, в соответствии с их частотностью и весами информативности, рассчитанными по одной из методик (к примеру, количество «соседей» в графе связей между словами в тексте). После ранжирования производится отбор лучших ключевых фраз из этого списка или отбираются кандидаты, превышающие установленный минимальный порог значения признака. В процессе предварительной отработки из текста производится удаление не информативных частей, например, стоп-слов. Стоп-слова – это слова, не представляющие ценности при обработке данных. Чаще междометия и пр. 9 всего это предлоги, союзы,

1.1 Постановка задачи Требуется выделения разработать ключевых информационную слов из документов систему и для составления кластерной структуры корпуса документов, а также выявления значимости образовательных дисциплин в сравнении с учебнометодическим комплексом. Исходными данными являются выпускные квалификационные работы в формате pdf. Необходимо произвести подготовку данных к обработке: извлечь текстовые данные из файлов, отфильтровать лишнюю информацию, провести стемминг и токенизацию вычислить коэффициент текстов. Для каждого слова требуется значимости по формуле tf-idf в рамках корпуса документов. Из вычисленных значений составить вектора для каждого документа. Полученные вектора документов кластеризовать, затем подготовить результаты к визуализации. Для этого необходимо уменьшить размерность векторов текстовых документов. Разработать приложение для визуализации результатов кластерного анализа, с возможностью вывода дополнительных данных для упрощения интерпретации результатов обработки данных. Для реализации программой, сравнения необходимо работ загрузить студентов файлы УМК с учебной с сайта университета и обработать их по тому же алгоритму, что и студенческие работы. 11

В приложении организовать сравнение выбранного пользователем набора документов с выбранным файлом УМК[11]. 1.2 Математическая постановка задачи Для выделения ключевых слов необходимо использовать статистическую меру tf-idf. Для каждого слова t каждого документа d в наборе документов D эта величина вычисляется следующим образом: tf −idf ( t , d , D )=tf ( t , d ) ∗idf ( t , D ) (1) Формула 1. Вычисление tf-idf. Функции tf и idf вычисляются по следующим формулам: tf ( t , d )= nt , Σ k nk (2) Формула 2. Вычисление tf. где nt – число вхождений слова t в документе d, Σk nk – общее число слов в документе. idf ( t , D ) =log (|{ |D| ) d i ∈ D∩t ∈ di }| , (3) Формула 3. Вычисление idf. где |D| – количество документов в корпусе, |{di ϵ D & t ϵ di}| – число документов, в которых встречается данное слово. Для проведения векторизации текстовых документов D необходимо выделить из множества всех слов T = {t ϵ d : d ϵ D} массив всех уникальных значений F. Для каждого документа d из D требуется привести в соответствие каждому элементу из F значение tf-idf(t, d, D) 12

такое, что t ϵ F. Если слово из F не содержится в документе d, то установить в этой позиции вектора нулевое значение. Таким образом, набор документов D будет преобразован в набор векторов вида: d ∈ D=∀ t ∈ F t ∈ d → tf − idf ( t , d , D ) t ∉ d →0 { Формула 4. } (4) Вычисление элементов векторов при векторизации документов. Для кластерного анализа необходимо использовать алгоритм k-means. Действие минимизировать алгоритма суммарное таково, квадратичное что он стремится отклонение точек кластеров от центров этих кластеров: 2 V =Σ ki=1 Σ x ∈S ( x − u i ) , i (5) Формула 5. Метрика алгоритма k-средних. где k – число кластеров, Si – полученные кластеры, а ui – центры масс всех векторов x из кластера Si. Для выбора количества k использовать характеристику межкластерного расстояние, известную как «метод силуэтов»: si= b (i) − a (i ) max [ b ( i ) , a ( i ) ] , (6) Формула 6. Метод силуэтов. где a(i) - среднее расстояние между объектами i-го кластера, b(i) - среднее расстояние от объектов i-го кластера до другого кластера, самого близкого к i-му. Для преобразования векторов в двумерные координаты применить алгоритм t-SNE (t-Distributed Stochastic Neighbor Embedding). 13

1.3 Выбор алгоритмов для обработки данных Из набора текстовых документов необходимо выделить ключевых слова. Существует несколько основных подходов к выделению ключевых слов [2]:  «мешок слов» (анг. Bag of Words): текст представляется в виде набора слов, составленного без учета грамматики и порядка следования слов в тексте. Для каждого отдельного слова вычисляется коэффициент значимости;  тематическое текстовых моделирование, документов когда строится для коллекции тематическая модель, которая определяет, к каким темам относится каждый из документов. Тематическая модель (англ. topic model) коллекции текстовых документов определяет, к каким темам относится каждый документ и какие слова (термины) образуют каждую тему;  семантические модели (например, word2vec): значимость слов определяется исходя из взаимного расположения всех слов документа внутри семантической модели. В рамках данной работы выбран первый подход. Представив документ как набор слов и вычислив коэффициент значимости для каждого уникального слова, можно составить вектор документа, отражающий степень присутствия в тексте того или иного понятия. Если пересечь такие вектора всех документов в корпусе, то образуется матрица коэффициентов значимости, и 14

все тексты окажутся в одном векторном пространстве. Так как в дальнейшем планируется кластеризация документов, этот фактор является ключевым при выборе данного подхода. Для расчета коэффициента значимости выбрана метрика tfidf, так как при вычислении этой метрики учитывается частота встречаемости слова во всем наборе документов, что позволяет отфильтровать незначимые слова. Для кластеризации выбран алгоритм k-средних. Алгоритм представляет собой версию EM-алгоритма, применяемого также для разделения смеси гауссиан. Множество элементов векторного пространства разбивается на заранее известное число кластеров k. Основная идея заключается в том, что на каждой итерации перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе согласно выбранной метрике. Алгоритм происходит завершается, изменения когда на какой-то внутрикластерного итерации расстояния. не Это происходит за конечное число итераций, так как количество возможных разбиений конечного множества конечно, а на каждом шаге суммарное квадратичное отклонение уменьшается, поэтому зацикливание невозможно. Результаты работы алгоритма k-средних позволяют выявить взаимное расположение текстов в векторном пространстве, что облегчает визуализацию кластерной 15 структуры корпуса

документов. Недостатком алгоритма является необходимость заранее задавать количество кластеров. Для решения этой проблемы используется метод силуэтов. Основным подходом к визуализации кластерной структуры корпуса документов является представление результатов в виде диаграммы, где каждый документ представляет точку на двумерной плоскости. Для реализации этого подхода требуется преобразовать вектора документов из n-мерных в двумерные. Для решения подобных задач существует целый ряд алгоритмов [8]:  Метод главных компонент (англ. principal component analysis, PCA) — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретён Карлом Пирсоном в 1901 году. Применяется во многих областях, в том числе, в эконометрике, биоинформатике, обработке изображений, для сжатия данных, в общественных науках. Вычисление главных компонент может быть сведено к вычислению сингулярного разложения матрицы данных или к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных. Иногда метод главных компонент называют преобразованием Кархунена — Лоэва или преобразованием Хотеллинга (англ. Hotelling transform).  Линейный дискриминантный анализ (ЛДА, англ. Linear Discriminant Analysis, LDA), нормальный дискриминантный 16

анализ (англ. Normal Discriminant Analysis, NDA) или анализ дискриминантных функций (англ. Discriminant Function Analysis) является обобщением линейного дискриминанта Фишера, метода, используемого в статистике, распознавании образов и обучении машин для поиска линейной комбинации признаков, которая описывает или разделяет два или более классов или событий. Получившаяся комбинация может быть использована как линейный классификатор или для снижения размерности перед классификацией. ЛДА тесно связан с дисперсионным Variance=ANOVA) и анализом регрессионным (англ. ANalyse анализом, Of которые также пытаются выразить одну зависимую переменную в виде линейной измерений. комбинации Однако качественные других дисперсионный независимые признаков анализ переменные и или использует непрерывную зависимую переменную, в то время как дискриминантный анализ имеет непрерывные независимые переменные и качественную класса). зависимую Логистическая переменную регрессия и (то есть метку пробит-регрессия больше похожи на ЛДА, чем дисперсионный анализ, так как они так же объясняют качественную переменную через непрерывные независимые переменные. Эти другие методы более предпочтительны в приложениях, в которых нет резона предполагать, что независимые переменные нормально распределены, что является фундаментальным предположением метода ЛДА. 17

 Стохастическое вложение соседей с t-распределением (англ. t-distributed Stochastic Neighbor Embedding, t-SNE) — это алгоритм машинного обучения для визуализации, разработанный Лоренсом ван дер Маатеном и Джеффри Хинтоном. Он является техникой нелинейного снижения размерности, хорошо подходящей для вложения данных высокой размерности для визуализации в пространство низкой размерности (двух- или трехмерное). В частности, метод моделирует каждый объект высокой размерности двух- или трёхмерной точкой таким образом, что похожие объекты моделируются близко расположенными точками, а непохожие точки моделируются с большой вероятностью точками, далеко друг от друга отстоящими. Алгоритм t-SNE состоит из двух главных шагов. Сначала t-SNE создаёт распределение вероятностей по парам объектов высокой размерности таким образом, что похожие объекты будут выбраны с большой вероятностью, в то время как вероятность выбора непохожих точек будет мала. Затем tSNE определяет похожее распределение вероятностей по точкам в пространстве малой размерности и минимизирует дивергенцию Кульбака — Лейблера между двумя распределениями с учётом положения точек. Заметим, что исходный алгоритм использует евклидово расстояние между объектами как базу измерения сходства, это может быть изменено сообразно обстоятельствам. 18

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

1.4 Технологии для программной реализации обработки данных Программная реализация обработки текстовых данных выполнена на языке Python. Среда разработки данного языка предлагает обширный набор библиотек для работы с текстовыми документами. Python используемых является языков одним из наиболее программирования в часто области интеллектуального анализа данных[9]. Немаловажен тот факт, что скрипты на этом языке интерпретируются в код на языке C, что обеспечивает высокую скорость обработки данных. Помимо этого, Python является кросплатформенным языком, что позволяет организовать обработку текстовых документов на любой платформе, например, на веб-сервере. В рамках данной работы были использованы следующие библиотеки [5]:  sklearn – для вычисления метрики tf-idf, кластеризации и понижения размерности векторов  nltk – для подготовки, стемминга и токенизации текста  numpy – для хранения больших массивов вещественных чисел  pandas – для организации хранения и вывода в файл данных о текстовых документах, включая результаты анализа Для разработки визуализатора выбран язык C# и технология WPF. Данный вреймворк позволяет 20 создать удобный в

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

ГЛАВА 2. РАЗРАБОТКА МОДУЛЯ ДЛЯ АНАЛИЗА ТЕКСТОВЫХ ДАННЫХ Программный модуль для анализа текстовых данных должен обладать следующим функционалом:  входные файлы должны быть в формате txt и иметь кодировку UTF-8  перед обработкой необходимо провести стемминг и токенизацию всех текстов  для каждого слова каждого документа вычислять коэффициент значимости tf-idf, использовать полученные значения для векторизации  проводить кластеризацию с помощью k means с применением анализа оптимального количества кластеров  преобразование векторов всех документов в точки для двумерной системы координат  на каждом этапе сохранять результаты обработки данных в выходные файлы 2.1 Подготовка данных Извлечение текстовых данных из исходных файлов в формате pdf производится с помощью программы на языке C#. Для парсинга разметки pdf используется библиотека iTextSharp. Для тестирования программы и экспериментов с данными были использованы выпускные 22 квалификационные работы

Института Математики и Компьютерных Наук ТюмГУ за 20162018 годы. Исходный корпус документов представляет собой набор файлов в формате pdf. Работы каталогизированы с помощью иерархии системных директорий по следующим правилам:  все работы за каждый год хранятся в отдельной директории, где хранятся работы по всем направлениям, студенты которых писали квалификационные работы в указанном году  для каждого направления обучения предназначена отдельная директория, в названии которой содержится номер студенческой направления и группы, вид полное наименование квалификации (бакалавриат, магистратура, специалитет), содержащая документы всех обучающихся по этому направлению  для каждого студента создана директория с указанием его имени, фамилии и отчества в названии. В ней содержатся все основные документы, необходимые студенту для защиты выпускной квалификационной работы Титульный лист студенческих работ хранится в виде скана бумажного документа. Выделение текстовых данных с изображения не дало стабильных результатов и часто приводило к ошибкам, поэтому решено было брать основную информацию о документах из названий директорий файловой системы. На вход программе подается две строковых переменных: путь к директории, содержащей исходные файлы, и путь, по которому необходимо сохранять результаты извлечения текста. 23

Класс TextExtractor отвечает за извлечение текстовых данных. Описание методов класса содержится в таблице 1. Обработка pdf-файлов производится следующим образом:  перемещение в директорию, содержащую нужный файл. При этом названия всех родительских директорий сохраняются и в дальнейшем используются как дополнительные свойства студенческой работы  проверяются все файлы, содержащиеся в просматриваемой директории – файл должен быть в формате pdf и не должен иметь название ни одного из административных документов. В ходе работы с программой выявлено, что для данного набора документов эти критерии позволяют во всех случаях выделять студенческие работы среди остальных файлов  в директории для выходных файлов создается папка для работ по данному направлению (в случае, если она еще не создана)  создается текстовый файл, в название которого входит номер группы, наименование направления и вид квалификации студента  из pdf-файла выделяется весь содержащийся в нем текст. Из полученной символы строки удаляются переводятся в незначащие нижний регистр. знаки, все Результат записывается в выходной файл  Вышеописанные операции выполняются для всех дочерних папок исходной директории. Схема работы программы представлена на рисунке 1. 24

В ходе экспериментов с данными был реализован функционал извлечения изображений из pdf-файлов. С помощью данного функционала получены титульные листы работ студентов. Были предприняты попытки извлечь текстовые данные с полученных изображений, а именно: направление обучения, год написания, тему работы, вид квалификации, фамилию, имя, отчество автора и научного руководителя ВКР. Для написания прототипа программы использовался язык Python и библиотека Tesseract OCR. Тестирование не дало убедительных и надежных результатов, в следствие чего пришлось отказаться от идеи извлечения данных о студенческой работе из титульного листа. 25

Таблица 1. Описание методов класса TextExtractor № Название Возвращаемый тип 1 ExtractTextFromP void df_dirs(string[] mainDirs, string[] resultDirs, string outputDir) Итерируется по директориям и запускает извлечение текста из содержащихся в них файлов 2 ExctractTextFrom void AllFiles(string inputDirName, string outputDirName) Итерируется по всем файлам директории и запускает извлечение текста 3 ExtractText(string void file, string outputDirName, string description) Извлекает текст из указанного файла, если файл удовлетворяет заданным критериям 4 GetText(string[] mainDirs, string outputDir) Запускает извлечение файлов 5 GetSubdirNames(s List<string> tring parentDirName, string dirNamesSeparate d) void 26 Описание Возвращает полные названия всех дочерних директорий с указанными именами относительно указанной исходной директории

Рисунок 1: Схема работы модуля извлечения текстов Класс WebParser реализует скачивание документов учебнометодического комплекса с сайта университета. Парсинг разметки сайта производится с помощью библиотеки AngleSharp. Файлы скачиваются с удаленного сервера с использованием стандартной библиотеки System.Net с помощью классаWebClient. Описание методов класса приведено в таблице 2. Получение ссылок для скачивания файлов производится следующим образом (см. рис.2):  на вход программе подается гиперссылка на веб-страницу, содержащую перечень УМК по все направления обучения Института Математики и Компьютерных Наук  содержимое веб возвращается страницы список фильтруется ссылок на по html-тегам, веб-страницы с информацией о изучаемых предметах  для каждой такой ссылки создается отдельная директория, в которую будут сохраняться все УМК по соответствующему направлению  среди html-тегов страницы выделяются все ссылки на файлы УМК  инициализируется загрузка файла по полученной ссылке  по завершению загрузки создается директория с названием предмета, для которого выделена ссылка. В эту папку сохраняется скачанный файл. По окончанию комплексов по всем загрузки всех направлениям 28 учебно-методических обучения, происходит

извлечение текстовых данных. УМК обрабатываются таким же образом и теми же средствами, что и студенческие работы. Таблица 2. Описание методов класса WebParser № Название Возвращаемый тип Описание 1 ParseTSUdocsAsy nc(string names) void Получает список ссылок на указанные институты и запускает их обработку 2 ParseInstitute(IBro void wsingContext context, WebClient wc, string uri, string host, DirectoryInfo directory) Получает список ссылок на все направления обучения института и запускает их обработку 3 ParseFaculty(IBro void wsingContext context, WebClient wc, string uri, string host, DirectoryInfo directory) Получает список ссылок на файлы УМК и запускает их скачивание 29

Рисунок 2: Схема работы программы для загрузки УМК 2.2 Программная реализация обработки данных 30

Программа для кластеризации написана на языке программирования Python [7]. Обработка текстовых документов происходит следующим образом:  стемминг и токенизация документов, фильтрация знаков препинания и стоп-слов  подсчет значимости слов относительно всего набора документов с помощью метрики tf-idf  составление векторов документов из значений tf-idf по глобальному ключевых для слов, всего в набора документов словарю результате получается матрица размерностью N на M, где N – количество документов, M – количество уникальных токенов во всем наборе документов  кластеризация текстовых документов используя вектора [6]  преобразование документов, в матрицы, набор состоящей двумерных из векторов векторов с помощью алгоритма LDA для дальнейшей визуализации Блок-схема работы модуля обработки данных представлена на рисунке 3. Рисунок 3: Схема работы модуля обработки данных 31

Результаты обработки данных записываются во внешние файлы на каждом из этапов работы программы [3]. Сохраняются следующие данные:  результаты токенизации - глобальный для всего набора документов соответствует словарь, в полная котором форма каждому этого токена токену (слово без применения стемминга);  матрица tf-idf, где каждому документу соответствует вектор, столбцами которого являются значения tf-idf для каждого из слов в глобальном словаре;  массив, содержащий информацию о номере кластера, которому принадлежит каждый из текстовых документов;  массив точек, представляющих положение документов на двумерной плоскости, после преобразования матрицы tf-idf с помощью алгоритма LDA. Таким образом, благодаря возможности загрузки сохраненных данных каждый шаг может быть выполнен без запуска предыдущих этапов. Сохраненные файлы используются для загрузки данных о ключевых словах и кластерной структуры корпуса документов в визуализатор. За стемминг, токенизацию и построение матрицы значений tfidf отвечает класс spaVectorizer. Более подробное описание класса представлено в таблице 3. Процесс векторизации документов можно разбить на следующие этапы (см. рис.4):  На вход программы подается массив путей к директориям, в которых находятся исходные текстовые документы. 32

 Содержимое каждого документа считывается из файла. Полное имя файла и строка с текстом сохраняются в программе.  Текст каждого документа подвергается разбиению на отельные слова – токены. Фильтруются стоп-слова, числовые значения и знаки припенания. Результаты сохраняются в массив A.  Элементы массива A подвергаются усечению окончаний (стеммингу), результаты сохраняются в массив B.  Из полученных массивов формируется словарь T, в котором элементы B являются ключами, а элементы A – значениями. Данный словарь необходим для того, чтобы каждое слово текста можно было восстановить до его полной формы, более удобной для прочтения пользователей.  После стемминга и токенизации, содержимое всех текстовых файлов передается в функцию вычисления коэффициента значимости слов по метрике tf-idf.  Выходными данными программы являются словарь T, массив названий документов и матрица tf-idf, где столбцам соответствуют элементы словаря T, а строкам – исходные документы. 33

Рисунок 4: Схема алгоритма векторизации текстовых документов Навигация по файловой системе и чтение содержимого текстовых документов производятся стандартными средствами языка Python. Усечение окончаний слов в текстах производится с помощью класса nltk.stem.snowball.RussianStemmer, разбиение на токены – с помощью класса nltk.sent_tokenize. 34

Полученные в ходе работы spaVectorizer данные передаются классу spaClusterizer. Схема работы класса представлена на рисунке 5. В процессе работы spaClusterizer можно выделить следующие шаги:  На вход программе подается матрица значений tf-idf  Размерность матрицы понижается с помощью алгоритма TSNE до массива двумерных точек  Производится кластеризация полученных точек при помощи алгоритма k-means  Выходными данными программы являются массив точек, представляющих документы и информация о кластерной структуре набора документов – каждому документу приведен в соответствие номер кластера, которому принадлежит этот документ Рисунок 5: Диаграмма классов приложения В результате тестирования выявлено, что применение кластеризации не к матрице значений tf-idf, а к результатам понижения размерности матрицы, дает более четкие очертания кластеров при отображении на двумерной плоскости. Так как основным назначением программы является визуализация результатов кластерного анализа, предпочтение было отдано этому подходу. 35

Кластеризация производится sklearn.cluster.Kmeans, уменьшение с помощью размерности векторов матрицы tf-idf – с помощью библиотеки sklearn.manifold.TSNE. После полученные окончания данные обработки сохраняются текстовых в текстовые документов документы согласно стандарту JSON. Таблица 3. Методы класса spaVectorizer № Название метода Возвращаемое значение Описание 1 get_text_from_fi Массив содержимого Загружает содержимое le файлов и названий файлов в память файлов программы 2 tokenize_and_st Массив строковых em токенов Производит стемминг и фильтрацию лишних символов для каждого слова в текстах 3 tokenize_only Производит только фильтрацию лишних символов для каждого слова в текстах Массив строковых токенов 4 vectorize_text_t Матрица значений tf- Производит fidf idf векторизацию текстов с помощью метрики tf-idf Для сравнения текстовых документов была использована реализация word2vec от GenSim[12]. В отличии от модуля обработки данных, программа для сравнения запускается приложением для визуализации с помощью технолгии IronPython – интерпретатора языка Python для C# и .Net. В качестве эксперимента модуль обработки данных был перенесен на веб-платформу. С помощью контейнеризатора 36

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

ГЛАВА 3. РАЗРАБОТКА ВИЗУАЛИЗАТОРА Визуализатор является пользовательским приложением для ОС Windows, технологии написанном WPF предоставить [4]. на языке Основное пользователю C# с использованием назначение приложения визуальное - представление результатов кластерного анализа и упростить их интерпретацию. 3.1 Структура данных Перед началом работы программы данные загружаются из указанных файлов. Для хранения файлов внутри программы используется система классов (см. рис.6). Класс DocumentCorpus хранит общую информацию о полученных данных: словарь ключевых слов корпуса документов, номера кластеров для каждого документа, информация о принадлежности документов определенным кластерам, список документов. Класс DocumentEntity содержит основную информацию о документе: название, ФИО автора, направление обучения, год написания, номер кластера, вектор значений tf-idf. Класс DocumentCluster храни информацию о кластерах: номер, цвет элементов кластера при визуализации, список всех документов, размер, соотношение между количеством работ по разным направлениям обучения. Клас DocumentVisual содержит информацию о документе, необходимую для визуализации, а именно: координаты точки на основной диаграмме, цвет точки и подпись для вывода на экран, 38

словарь, состоящий из ненулевых значений вектора tf-idf и соответствующих им словам из глобального словаря, а также связанный экземпляр класса DocumentData. Рисунок 6: Диаграмма классов приложения 3.2 Функционал приложения Приложение обладает следующим функционалом: 39

 вывод на экран результаты кластеризации в виде набора точек на плоскости, где каждая точка представляет собой документ (см. рис.7)  вывод на экран список документов и список кластеров (см. рис.7)  при выборе документа на плоскости (при нажатии на точку) или в списке, на экран выводится детальная информация о выбранном объекте (см. рис.8)  при выборе кластера в списке кластеров, открывается новое окно и входящие в кластер документы отображаются на плоскости так же, как и в основном окне, но вместо списка кластеров выводится детальная информация о выбранном кластере  имеется возможность открыть окно сравнения с УМК, предоставляющее возможность документы с выбранным файлом УМК 40 сравнить выбранные

Рисунок 7: Главное окно Рисунок 8: Информация о кластере Сравнение набора документов с выбранными УМК происходит следующим образом[10]: 41

 пользователь выбирает направление обучения и формирует набор L, состоящий из файлов УМК  составляется список D ключевых слов из набора документов по выбранному направлению заранее заданного размера d (слова сортируются по коэффициенту значимости в порядке убывания)  для каждого документа из L составляется список N всех ключевых слов выборки документов УМК  загружается обученная семантическая модель, составленная по технологии word2vec  между каждым словом из N и каждым словом из D вычисляется расстояние в семантической модели. На выходе получается матрица размерностью d на n, где d - длина списка D, а n - длина списка N  для каждого слова из D вычисляется среднее значение в соответствующей строке матрицы, полученный вектор размерностью d сохраняется для текущего документа УМК  После обработки матрица из всех документов полученных нормализуются, после векторов. чего из L, составляется Значения матрицы высчитывается среднее арифметическое для каждого документа из L. Полученные значения выводятся на экран. Чем меньше значение, тем сильнее совпадение содержимого документа ключевых слов кластера. Схема работы алгоритма представлена на рисунке 9. 42 УМК и

Рисунок 9: Схема работы алгоритма по оценке УМК 43

3.2 Демонстрация работы приложения Для демонстрации работы программы были обработаны 87 дипломных работ за 2018 год по следующим направлениям обучения:  математическое обеспечение и администрирование информационных систем (МОАИС) – 17 работ,  механика и математическое моделирование (МиММ) – 12 работ ,  информационная безопасность автоматизированных систем (ИБАС) – 25 работ,  прикладная информатика (ПИ) – 33 работы. На рисунке 10 видна кластерная структура набора документов. Всего выделено 3 кластера. Кластер 1 помечен на рисунке черным цветом и содержит 31 документ. Кластер 2 обозначен белым цветом и состоит из 29 элементов. В кластер 3 входит 27 документов, он обозначен красным цветом. Информация о соотношении кластерах представлена в таблице 4. 44 направлений обучения в

Рисунок 10: Демонстрация работы программы Кластер 1 содержит работы по направлениям МиММ, МОАИС, в меньшей степени ПИ и ИБАС. Ключевыми словами кластера являются: «алгоритм», «уравнение», «приложение», «точка», «значение», «коэффициент», «параметр». В кластере 2 располагаются работы по направлению ПИ и несколько работ МОАИС, МиММ и ИБАС. Ключевые слова кластера: «клиент», «система», «пользователь», «заявка», «сервер», «электронный ресурс» и др. В кластере направлениям являются 3 сосредоточены МОАИС, ИБАС «информационная и в ПИ. система», основном работы Ключевыми словами «доступ», «угроза», «сервер», «база данных», «персональные данные» и др. 45 по

Таблица 4. Соотношение направлений обучения в кластерах. Кластер 1 Кластер 2 Кластер 3 Направле Ко Соотношени Ко Соотношени Ко Соотношени ние ле, % ле, % ле, % во во во МОАИС 13 41,94 1 3,45 6 22,22 МиММ 11 35,48 1 3,45 0 0 ИБАС 3 9,68 4 13,79 13 48,15 ПИ 4 12,9 23 79,31 8 29,63 Проанализировав кластерную структуру набора документов, можно сделать вывод о том, что тематика работ студентов соответствует особенностям направлений обучения. МОАИС находится на стыке двух основных тематик – работы студентов этого направления находятся как в кластере с МиММ (что говорит о математической подготовке), так и в кластере с ИБАС (что соответствует тематике администрирования информационных систем). Около 80% работ по направлению ПИ находятся в отдельном кластере. Малое количество работ по другим направлениям в этом же кластере свидетельствует о слабой связи тематик, изучаемых в рамках данного направления, с другими направлениями обучения (из представленных здесь). При рассмотрении кластерной структуры на рисунке 10 можно отметить, что работы по каждому из направлений обучения чаще всего соседствуют друг с другом. Другими 46

словами, визуально легко выделить 4 кластера, каждый из которых соответствовал бы определённому направлению обучения. Это свидетельствует о сходстве работ обучающихся. Учитывая это, наибольший интерес представляют работы, отстоящие от группы документов своего направления. Такая работа может являться результатом несоответствия интересов студента и тематик, предложенных в рамках учебной программы направления, на котором обучается этот студент. Рисунок 11: Сравнение с УМК Демонстрация представлена на сравнения рисунке 11. работ Были 47 студентов взяты файлы с УМК учебных

программ по дискретной ориентированному математике (ДМ), программированию объектно- (ООП) и администрированию баз данных (БД). По алгоритму сравнения, чем меньше значение, тем больше схожесть между работами по направлению и УМК. Результаты сравнения представлены в таблице 5. Проанализировав полученные данные, можно сделать следующие выводы:  При написании направления квалификационных МОАИС в основном работ студенты используют знания, полученные в результате изучения дисциплин ООП и БД.  Работы студентов направления ПИ содержат материалы из дисциплины ООП, но сильнее связаны с использованием баз данных.  Работы студентов направления МиММ слабо касаются сферы информационных технологий, но используемые в них математические термины увеличивают сходство с УМК по дискретной математике.  Студенты направления ИБАС используют базы данных при написании своих работ, программирование и математика при этом применяется менее активно. Таблица 5. Результаты сравнения с УМК. УМК / Направление МОиАИС ПИ МиММ ИБАС Дис. мат. 0,66 0,82 0,41 0,57 ООП 0,21 0,34 0,89 0,31 БД 0,35 0,28 0,92 0,22 48

ЗАКЛЮЧЕНИЕ В результате выполнения выпускной квалификационной работы были изучены технологии интеллектуального анализа текстов, а также подходы к визуализации результатов анализа. Рассмотрена задача выделения ключевых слов из текстовых документов, изучены особенности кластеризации многомерных данных. Реализован программный модуль для извлечения ключевых слов и кластерного анализа на языке Python. Разработано приложение для визуализации результатов анализа текста на языке C# с использованием технологии WPF. Разработанная производить информационная интеллектуальный квалификационных работ студентов, система позволяет анализ текстов визуально оценивать кластерную структуру набора документов, предоставляет данные для анализа причин формирования кластеров и позволяет провести сравнение студенческих работ и файлов УМК по ключевым словам. В ходе эксперимента было выявлено, что чаще всего работы одного направления находятся в одном кластере. В некоторых случаях, документы распределяются между несколькими соседними кластерами. При этом, ключевые слова документов, представленных в таких кластерах, так или иначе соответствуют тематикам, которые изучаются в рамках данного направления. 50

СПИСОК ЛИТЕРАТУРЫ 1. Технологии анализа данных: Data Mining, Visual Mining, Text Mining, OLAP / И.И. Холод, В.В. Степаненко, Куприянов М.С. – М.: БХВ-Петербург, 2007 – 384 с. 2. Мьятт, Г. Making Sense of Data I: A Practical Guide to Exploratory Data Analysis and Data Mining / Г. Мьятт, В. Джонсон – М.: Wiley, 2-е издание, 2014 – 248 с. 3. Маккини, У. Python for Data Analysis: Data Wrangling with Pandas, NumPy, and IPython / У. Маккини – М.: O’Reilly Media, 2-е издание, 2017 – 550 с. 4. Макдональд, М. Pro WPF 4.5 in C#: Windows Presentation Foundation in .NET 4.5 / М. Макдональд – М.: Apress, 4-е издание, 2012 – 1078 с. 5. Document Clustering http://brandonrose.org/clustering (Дата with Python последнего обращения: 10.05.19). 6. Clustering – scikit-learn 0.21.2 documentation https://scikitlearn.org/stable/modules/clustering.htm (Дата последнего обращения: 29.05.19). 7. Tutorial: Extracting Keywords with TF-IDF and Python’s ScikitLearn http://kavita-ganesan.com/extracting-keywords-from-text-tfidf/ Dimensionality (Дата последнего обращения: 15.05.19). 8. Reduction – Zenwa | Python Machine Leatning Tutorials https://pythonmachinelearning.pro/dimensionality-reduction/ последнего обращения: 28.05.19). 51 (Дата

9. Python and Data https://www.datasciencegraduateprograms.com/python/ Science (Дата последнего обращения: 17.06.19) 10. Text Similarities : Estimate the degree of similarity between two texts https://medium.com/@adriensieg/text-similarities- da019229c894 (Дата последнего обращения: 05.06.19) 11. Calculating Semantic Similarity between Academic Articles using Topic Event and Ontology / Минг Л., Бо Л., Зепенг Г. – State Key Laboratory of Software Development Environment, Beihang University, 2016 – 21 с. 12. gensim: models.word2vec – Word2vec https://radimrehurek.com/gensim/models/word2vec.html последнего обращения: 10.06.19) 52 embeddings (Дата

ПРИЛОЖЕНИЕ 1 Извлечение текстовых данных из файлов в формате pdf class TextExtractor { void ExtractTextFromPdf_dirs(string[] mainDirs, string[] resultDirs, string outputDir) { for (int i = 0; i < mainDirs.Length; i++) { var dirList = GetSubdirNames(mainDirs[i]);//, dirNamesSep); foreach (var item in dirList) { ExctractTextFromAllFiles(item, System.IO.Path.Combine(outputDir, resultDirs[i])); }}} void ExctractTextFromAllFiles(string inputDirName, string outputDirName) { DirectoryInfo dir = new DirectoryInfo(inputDirName); string outname = System.IO.Path.Combine(outputDirName, dir.Name); foreach (var subdir in dir.GetDirectories()) { var files = subdir.GetFiles(); for (int i = 0; i < files.Length; i++) { if (System.IO.Path.GetExtension(files[i].FullName) == ".pdf" && ! files[i].FullName.Contains("огласие")) ExtractText(files[i].FullName, outname, subdir.Name); }}} void ExtractText(string file, string outputDirName, string description = "") { var fn = System.IO.Path.GetFileNameWithoutExtension(file); if (!Directory.Exists(outputDirName)) Directory.CreateDirectory(outputDirName); var outfn = System.IO.Path.Combine(outputDirName, description + "_" + fn + "_rawtext.txt"); 53

FileStream fi = new FileStream(outfn, FileMode.Create); StreamWriter sw = new StreamWriter(fi, Encoding.UTF8); PdfReader reader = new PdfReader(file); for (int i = 1; i <= reader.NumberOfPages; ++i) { string text = PdfTextExtractor.GetTextFromPage(reader, i, new SimpleTextExtractionStrategy()); text = text.ToLower(); sw.Write(Encoding.UTF8.GetString(Encoding.Convert(Encoding.Unicode, Encoding.UTF8, Encoding.Unicode.GetBytes(text)))); }} public void GetText(string outputDir) { string[] mainDirs = { @"C:\Users\swite\Desktop\ВКР\2018\", @"C:\Users\swite\Desktop\ВКР\2017\", @"C:\Users\swite\Desktop\ВКР\2016",}; string[] resultDirs = { "2018", "2017", "2016",}; ExtractTextFromPdf_dirs(mainDirs, resultDirs, outputDir); outputDir = @"C:\Users\swite\Desktop\ВКР_2016_2018\ВКР_images"; ExtractImgFromPdf_dirs(mainDirs, resultDirs, outputDir); } void ExtractImgFromPdf_dirs(string[] mainDirs, string[] resultDirs, string outputDir) { for (int i = 0; i < mainDirs.Length; i++) { var dirList = GetSubdirNames(mainDirs[i]);//, dirNamesSep); foreach (var item in dirList) { ExtractImgFromAllFiles(item, System.IO.Path.Combine(outputDir, resultDirs[i])); }}} List<string> GetSubdirNames(string parentDirName, string dirNamesSeparated) { 54

var fn = System.IO.Path.GetFileNameWithoutExtension(file); if (!Directory.Exists(outputDirName)) Directory.CreateDirectory(outputDirName); var outfn = System.IO.Path.Combine(outputDirName, fn + "_" + description + "_TITLELIST.jpg"); var pdf = new PdfReader(file); var pg = pdf.GetPageN(1); var res = PdfReader.GetPdfObject(pg.Get(PdfName.RESOURCES)) as PdfDictionary; var xobj = PdfReader.GetPdfObject(res.Get(PdfName.XOBJECT)) as PdfDictionary; if (xobj == null) return; var keys = xobj.Keys; if (keys.Count == 0) return; var obj = xobj.Get(keys.ElementAt(0)); if (!obj.IsIndirect()) return; var tg = PdfReader.GetPdfObject(obj) as PdfDictionary; var type = PdfReader.GetPdfObject(tg.Get(PdfName.SUBTYPE)) as PdfName; if (!PdfName.IMAGE.Equals(type)) return; int XrefIndex = (obj as PRIndirectReference).Number; var pdfStream = pdf.GetPdfObject(XrefIndex) as PRStream; var data = PdfReader.GetStreamBytesRaw(pdfStream); File.WriteAllBytes(outfn, data); }} 56

ПРИЛОЖЕНИЕ 2 Скачивание файлов УМК с веб-портала университета class WebParser { public static async Task ParseTSUdocsAsync() { var config = Configuration.Default.WithDefaultLoader(); var host = @"https://op.utmn.ru/"; var address = @"https://op.utmn.ru/index.php? STANDARD_ID=340858&DEPARTMENT_ID=331247"; var context = BrowsingContext.New(config); WebClient wc = new WebClient(); await ParseInstitute(context, wc, address, host, new DirectoryInfo(@"C:\ Users\swite\Desktop\УМК ИМиКН\PDF source")); } public static async Task ParseInstitute(IBrowsingContext context, WebClient wc, string uri, string host, DirectoryInfo directory) { var document = await context.OpenAsync(uri); var linkDivs = document.All.Where(m => m.LocalName == "div" && m.ClassList.Contains("col-md-2") && m.ClassList.Contains("cnt")).Where(m => m.Children.Length > 0).Where(m => m.Children.First().LocalName == "a"); foreach (var link in linkDivs) { var facultyElement = link.ParentElement.Children.FirstOrDefault(m => m.LocalName == "div").Children.FirstOrDefault(); string facultyTitle = ""; if (facultyElement == null) 57

facultyTitle = link.ParentElement.Children.FirstOrDefault(m => m.LocalName == "div").TextContent.Trim().Replace(':', ' '); else facultyTitle = facultyElement.TextContent.Trim().Replace(':', ' '); string typeTitle = link.ParentElement.Children.FirstOrDefault(m => m.LocalName == "div" && m.ClassList.Contains("cnt")).TextContent.Trim(); facultyTitle = facultyTitle.Substring(0, 150); string href = link.Children.First().GetAttribute("href"); string address = host + href; Console.WriteLine(directory.FullName + " + " + facultyTitle + " + " + typeTitle); DirectoryInfo faculty = new DirectoryInfo(Path.Combine(directory.FullName, facultyTitle + "_" + typeTitle)); if (!faculty.Exists) faculty.Create(); await ParseFaculty(context, wc, address, host, faculty); }} public static async Task ParseFaculty(IBrowsingContext context, WebClient wc, string uri, string host, DirectoryInfo directory) { var document = await context.OpenAsync(uri); var linkDivs = document.All.Where(m => m.LocalName == "div" && m.ClassList.Contains("col-md-3")).Where(m => m.Children.First().LocalName == "a"); foreach (var link in linkDivs) { string semesterNum = link.ParentElement.Children.FirstOrDefault(m => m.LocalName == "div").Children.FirstOrDefault(m => m.LocalName == "span").TextContent.Split('.').Last(); var child = link.Children.First(); 58

string href = child.GetAttribute("href"); string semesterName = semesterNum + " курс"; string subjectName = child.Text().Trim('\t'); string address = host + href; string filename = href.Split('/').Last(); DirectoryInfo course = new DirectoryInfo(Path.Combine(directory.FullName, semesterName)); if (!course.Exists) course.Create(); DirectoryInfo subject = new DirectoryInfo(Path.Combine(course.FullName, subjectName)); if (!subject.Exists) subject.Create(); string path = Path.Combine(subject.FullName, filename); if (!Path.HasExtension(path)) continue; await wc.DownloadFileTaskAsync(address, path); }}} 59

ПРИЛОЖЕНИЕ 3 Программный код модуля обработки данных class spaVectorizer(object): import nltk import sklearn import pathlib import os import re import pandas as pd text_files = [] locale = 'russian' encoding = 'utf-8' stopwords = nltk.corpus.stopwords.words(locale) vocab_frame = [] def get_text_from_file(self, filename): import os textdata = [] file = open(filename, mode='r', encoding=self.encoding) text = file.read() textdata.append(file.name) textdata.append(text) self.text_files.append(textdata) return textdata def get_texts_from_folder(self, folder): 60

from pathlib import Path p = Path(folder) for file in p.iterdir(): self.get_text_from_file(file) return self.text_files def get_texts_from_folders(self, folders): for folder in folders: self.get_texts_from_folder(folder) return self.text_files def tokenize_and_stem(self, text): from nltk.stem.snowball import RussianStemmer stemmer = RussianStemmer() tokens = [word for sent in self.nltk.sent_tokenize(text, self.locale) for word in self.nltk.word_tokenize(sent, self.locale)] filtered_tokens = [] for token in tokens: if self.re.search('[a-zA-Zа-яА-Я]', token): if token not in self.stopwords: filtered_tokens.append(token) stems = [stemmer.stem(t) for t in filtered_tokens] return stems def tokenize_only(self, text): 61

tokens = [word for sent in self.nltk.sent_tokenize(text, self.locale) for word in self.nltk.word_tokenize(sent, self.locale)] filtered_tokens = [] for token in tokens: if self.re.search('[a-zA-Zа-яА-Я]', token): if token not in self.stopwords: filtered_tokens.append(token) return filtered_tokens def vectorize_text_tfidf(self, text_files): totalvocab_stemmed = [] totalvocab_tokenized = [] for i in text_files: allwords_stemmed = self.tokenize_and_stem(i[1]) totalvocab_stemmed.extend(allwords_stemmed) allwords_tokenized = self.tokenize_only(i[1]) totalvocab_tokenized.extend(allwords_tokenized) vocab_frame = self.pd.DataFrame({'words': totalvocab_tokenized}, index = totalvocab_stemmed) from sklearn.feature_extraction.text import TfidfVectorizer tfidf_vectorizer = TfidfVectorizer(max_df=0.9, max_features=200000, min_df=0.1, use_idf=True, tokenizer=self.tokenize_and_stem, ngram_range=(1,3)) only = [row[1] for row in text_files] tfidf_matrix = tfidf_vectorizer.fit_transform(only) return tfidf_matrix 62

class spaClusterizer(object): clusters = [] positions = [] def clusterize(self, tfidf_matrix, nclusters, labels): import numpy as np import pandas as pd import os import codecs from sklearn import feature_extraction from sklearn.cluster import KMeans from sklearn.manifold import TSNE self.positions = TSNE(n_components=2, init='pca').fit_transform(tfidf_matrix) xs2, ys2 = self.positions[:, 0], self.positions[:, 1] km = KMeans(n_clusters=nclusters) km.fit(tfidf_matrix) self.clusters = km.predict(self.positions) def vectorize(vectorizer, folders, datapath): import numpy as np import json texts = vectorizer.get_texts_from_folders(folders) tfidf = vectorizer.vectorize_text_tfidf(texts) np.save(datapath + r'\data_tfidf.npy', tfidf.toarray()) 63

np.savetxt(datapath + r'\data_tfidf_matrix.txt', tfidf.toarray(), encoding='utf-8') data = [row[0] for row in vectorizer.text_files] with open(datapath + r'\data_titles.txt', 'w', encoding='utf-8') as file: json.dump(data, file, ensure_ascii=False) with open(datapath + r'\data_vocab.txt', 'w', encoding='utf-8') as file: json.dump(vectorizer.vocab_frame, file, ensure_ascii=False) def clusterize(clusterizer, datapath, nclusters): import os import numpy as np import json tfidf = np.load(datapath + r'\data_tfidf.npy') file = open(datapath + r'\data_titles.txt', encoding='utf-8') list = json.load(file) file.close() labels = [os.path.basename(os.path.dirname(item)).split('_')[2] for item in list] clusterizer.clusterize(tfidf, nclusters, labels) with open(datapath + r'\data_clusters.txt', 'w', encoding='utf-8') as file: json.dump(clusterizer.clusters.tolist(), file, ensure_ascii=False) with open(datapath + r'\data_positions.txt', 'w', encoding='utf-8') as file: json.dump(clusterizer.positions.tolist(), file, ensure_ascii=False) def silhouette(tfidf_matrix, nclusters): from sklearn.metrics import silhouette_samples, silhouette_score from sklearn.cluster import KMeans range_n_clusters = [2, 3, 4, 5, 6, 7, 8, 9, 10] for n_clusters in range_n_clusters: 64

clusterer = KMeans(n_clusters=n_clusters) cluster_labels = clusterer.fit_predict(tfidf_matrix) silhouette_avg = silhouette_score(tfidf_matrix, cluster_labels) print("For n_clusters =", n_clusters, "The average silhouette_score is :", silhouette_avg) #r'C:\Users\swite\Desktop\ВКР2018_text\diplomas_text\ YYYY_demo_test_kmeans' folders = [ r'C:\Users\swite\Desktop\ВКР2018_text\diplomas_text\ 2018_ИМИКН_МОАИС_ОДО', r'C:\Users\swite\Desktop\ВКР2018_text\diplomas_text\ 2018_ИМиКН_МиММ_ОДО', r'C:\Users\swite\Desktop\ВКР2018_text\diplomas_text\ 2018_ИМИКН_ИБАС_ОДО', r'C:\Users\swite\Desktop\ВКР2018_text\diplomas_text\2018_ИМИКН_ПИ_ОДО',] datapath = r'C:\Users\swite\Desktop\kmeansRESULTS'; vectorizer = spaVectorizer() vectorize(vectorizer, folders, datapath) clusterizer = spaClusterizer() clusterize(clusterizer, datapath, 10) 65

ПРИЛОЖЕНИЕ 4 Программный код класса, отвечающего за импорт и хранение данных о ключевых словах и кластерной структуре набора документов class DocumentsCorpus { public Dictionary<string, string> vocabulary = new Dictionary<string, string>(); public List<int> clustersMarkup = new List<int>(); public List<double[]> tfidf = new List<double[]>(); public List<Tuple<double, double>> points = new List<Tuple<double, double>>(); public List<string> titles = new List<string>(); public List<byte[]> colorLegend = new List<byte[]>(); public List<DocumentsCluster> clusters = new List<DocumentsCluster>(); public List<DocumentEntity> documents = new List<DocumentEntity>(); public double lowerTfidf = 0.5; void LoadFromFile(string filePath) { JavaScriptSerializer serializer = new JavaScriptSerializer(); using (StreamReader sr = new StreamReader(Path.Combine(filePath, "data_tfidf_matrix.txt"))) { sr.Read(); sr.Read(); 66

while (!sr.EndOfStream) { string vector = ""; char nextChar = (char)sr.Peek(); while (nextChar != '[' && !sr.EndOfStream) { nextChar = (char)sr.Read(); } if (sr.EndOfStream) break; vector += nextChar; do { nextChar = (char)sr.Read(); vector += nextChar; } while (nextChar != ']' && !sr.EndOfStream); var tfidfVector = serializer.Deserialize<List<string>>(vector); tfidf.Add(tfidfVector.Select((value) => { return double.Parse(value.Replace('.', ',')); }).ToArray()); } } var vocabRaw = serializer.Deserialize<List<List<string>>>(File.ReadAllText(Path.Combine(fileP ath, "data_vocab.txt"))); foreach (var list in vocabRaw) { if (!vocabulary.ContainsKey(list[0])) vocabulary.Add(list[0], list[1]); } titles = serializer.Deserialize<List<string>>(File.ReadAllText(Path.Combine(filePath, "data_titles.txt"))); 67

points = serializer.Deserialize<List<List<double>>>(File.ReadAllText(Path.Combine(file Path, "data_positions.txt"))).Select(a => { return new Tuple<double, double>(a[0], a[1]); }).ToList(); clustersMarkup = serializer.Deserialize<List<int>>(File.ReadAllText(Path.Combine(filePath, "data_clusters.txt"))); } public int DeserializeDocuments(string filePath) { LoadFromFile(filePath); if (clustersMarkup.Count != tfidf.Count || tfidf.Count != points.Count || points.Count != titles.Count) return 1; Random rnd = new Random(); for (int i = 0; i < clustersMarkup.Count; i++) byte[] rgb = new byte[3]; rnd.NextBytes(rgb); colorLegend.Add(rgb); } int K = clustersMarkup.Distinct().Count(); for (int i = 0; i < K; i++) { var cluster = new DocumentsCluster(); cluster.SetColor(colorLegend[i]); cluster.number = i; clusters.Add(cluster); } 68 {

for (int i = 0; i < tfidf.Count; i++) { var document = new DocumentEntity(); document.name = titles[i].Split('\\').Last().Split('_')[0]; document.vector = tfidf[i]; document.X = points[i].Item1; document.Y = points[i].Item2; for (int w = 0; w < document.vector.Length; w++) if (document.vector[w] > this.lowerTfidf) { { document.keywords.Add(vocabulary.ElementAt(w).Value, document.vector[w]); } } var cluster = clusters[clustersMarkup[i]]; document.cluster = cluster; documents.Add(document); cluster.documents.Add(document); } return 0; } } 69