Диссертация (1090484), страница 11
Текст из файла (страница 11)
Итак для каждого термина t есть список (id, x) где x значение координаты по данному термину: X(t) = [(id1 , x1 ), (id2 , x2 )...(idm , xm )],где x1 <= x2 ... <= xm ..Три шага алгоритма KNN с использованием двоичного дерева для классификации текста:Шаг 1: Вычисление координат (TF-IDF) этого текста.Шаг 2: Для каждого термина (t, x), ищем ближайшее значение к x наX(t) = [(id1 , x1 ), (id2 , x2 )...(idm , xm )], используя метод двоичного поиска[178]:Шаг 2-1: i = 1; j = m;Шаг 2-2: Пока i < j :Шаг 2-2-1: k = (i + j)div2,Шаг 2-2-1: если xk < x, то i = k + 1;Шаг 2-2-2: если xk >= x, то j = k;После шага 2-2, xk есть ближайшее значение к x на X(t)Шаг 3: Рассмотрим 2*К текстов вокруг (idk , xk ) на X(t), считая расстояниемежду текстами, проведем сравнение и обновление ближайших соседей данноготекста.98И так, сложность алгоритма «К» ближайших соседей с использованием двоичного дерева: O(K*log(N)*|L|), а KNN: O(N*|L|), где: N - количество текстов вкорпусе, |L| - средняя длина текста в корпусе.Очевидно, что алгоритм «К» ближайших соседей с использованием двоичного дерева имеет преимущество по скорости работы при больших корпусахтекстов.Подход 3: Использование двоичного дерева.Для двоичного дерева должны выполнены 3 условия:[178]1.
Значение в любой вершине не меньше (или не больше), чем значения еёпотомков;2. Глубина листьев (расстояние до корня) отличается не более чем на 1 слой;3. Последний слой заполняется слева направо;Рис. 3.5: Двоичное дерево.Для каждого текста будем хранить его ближайших соседей в двоичном дереве, корень которой есть самый ближайший сосед.Процедура поиска ближайших соседей текста t0 :Шаг 1: Создание пустой двоичного дерева.Шаг 2: При рассмотрении текст ti , если размер двоичного дерева меньшечем K, то просто добавляем ti в двоичное дерево, а если размер двоичного дерева99равен K и расстояние между ti и t0 меньше чем расстояние между корнем двоичного дерева и t0 , то обменяем корень двоичного дерева с ti и восстанавливаемсвойства двоичного дерева.Сложность процедуры поиска ближайших соседей одного текста с использованием двоичного дерева равна O(log(K)), а без нее равна O(K).3.5ВыводыНа основании проведенного исследования в этой главе можно сделать следующие выводы:1.
Морфологического анализа текстов приводит к снятию многозначностьслов, так же дает морфологические характеристики, которые являются полезными для классификации и других задач обработки естественного языка;2. Нейро-семантическая сеть на основе морфологического анализа позволяет создание семантического векторного пространств грамматических структур,таким образом повышается качество классификации текстов;3. Рекурсивный автоэнкодер морфологического анализа более эффективновыбирает векторы - слова для объединения и выдает более адекватное векторноепредставление текста чем обычный рекурсивный автоэнкодер;4.
Использование двоичного дерева для алгоритма «К» ближайших соседейповышает скорость классификации текстов и сохраняет качество классификации;100Глава 4Экспериментальноеисследованиевычислительногокомплекса-классификаторатекстов4.1Разработка программного обеспечения вычислительного комплекса-классификатора текстов с использованием морфологического анализа и нейро-семантических сетейПо результатам диссертационного исследования было разработано программное обеспечение вычислительного комплекса-классификатора текстов на языках програмирования C++ и Python с использованием библиотеки машинногообучения TensorFlow от компании Google [179].101Вычислительный комплекс морфологического анализа состоит из 3частей:1.
Префиксное дерево для хранения префиксов словоформ и номеров моделей префиксов.2. Таблица морфологических моделей, каждая модель состоит из одного илинесколько элементов, а каждый элемент содержит один суффикс и морфологические характеристики.3. Таблица морфологических характеристик.Рис. 4.1: Типичная структура морфологического анализатора [40].102Для создания морфологических словарей нужно собрать морфологическиеданные языков (в данной работе используются OpenCorpora для русского языкаи PennTreeBank для английского). Все слова нужно группировать по леммам,потом для каждой леммы ищем общий префикс (самый длинный общий префиксвсех словоформ этой леммы) и составляем список (суффикс, морфологическиехарактеристики). Поскольку суффиксы и наборы морфологических характеристик повторяются во многих словоформах, создаем модели морфологическиххарактеристик и модели (суффикс, морфологические характеристики).
Построим дерево для хранения префиксов и моделей (суффикс, морфология).Для поиска морфологических вариантов словоформы необходимо обходитьдерево по символам этой словоформы [180], проверять совпадение префиксаи суффикса каждого элемента моделей словоформе, если они совпадают, томорфологические признаки этого элемента добавляются в список морфологических вариантов словоформы. Для разрешения морфологической многозначности применяется скрытая модель Маркова и алгоритм Витерби [181].Вычислительный комплекс-классификатор текстов с использованием морфологического анализа и нейро-семантических сетей:1.
Токенизатор: на вход подается текст, на выходе список предложений, каждое предложение имеет вид списка слов.2. Морфологический анализатор: на вход подается предложение в виде последовательности слов, на выходе список пар (id леммы, id модели морфологических характеристик)3. Классификатор: на вход подается список пар (id леммы, id модели морфологических характеристик), на выходе - распределение категорий.103Рис. 4.2: Типичная структура вычислительного комплекса-классификатора текстов [40].Векторизация слов и морфологических моделей:В данной работе не используется готовый набор векторных представленийслов, а представления обучаются с нуля.
Для вычисления векторных представлений слов и морфологических моделей используется метод word2vec с помощьюмодели CBOW (Continuous Bag-of-Words) [28].104Рис. 4.3: Модель CBOW.Continuous Bag-of-Words (CBOW):JN EG = log Qθ (D = 1|wt , h) + kEw̃∼Pnoise [log Qθ (D = 0|w̃, h)](4.1)После морфологического анализа текста и получения последовательностипар (id леммы, id модели морфологических характеристик), применяем методCBOW для обучения векторных представлений слов и морфологических моделей.
После обучения получаем представления в виде: WordVector(id леммы)и MorphologyVector(id модели морфологических характеристик). Эти наборыпредставлений используются в дальнейшей обработке и классификации.Нейро-семантическая сеть на основе морфологического анализа:105Рис. 4.4: Нейро-семантическая сеть на основе морфологического анализа.106Рекурсивный автоэнкодер морфологического анализа:Рис. 4.5: Рекурсивный автоэнкодер морфологического анализа.4.2Эксперименты и оценка результатов4.2.1Метод оценки результатов экспериментовДля оценки алгоритмов был использован метод K-Fold Cross-validation с параметром K = 10.[182]: разделим выборку данных на К частей. Повторяем процессК раз с i = 1 ..
K:1. Обучать все К частей, кроме i-ой части, которая для тестирования.2. Считаем результаты обучения и тестирования на этой итерации:107Рис. 4.6: Cross-validation.Считаем средние значения результатов обучения и тестирования на всех Китерациях.При проведении экспериментов использовались базы Movie Review и Wikinewsна русском и английском языках. Обучающая выборка Movie Review состоит из10662 текстов по двум категориям (позитивной и негативной).
Обучающая выборка Wikinews-Ru состоит из 7233 текстов - новостей на русском языке, её количество категорий равно 8. Обучающая выборка Wikinews-En состоит из 23588текстов - новостей на английском языке, её количество категорий равно 11.Для улучшения английского морфологического словаря был добавлен наборданных Lingvo.4.2.2Экспериментальное исследование нейро-семантическойсети на основе морфологического анализаНейро-семантическая сеть [40] состоит из трех последовательных частей:1. Часть «семантические векторные представления», которая вычисляет векторные представления грамматических структур предложений, содержит автоэнкодеры по заданным грамматическим структурам (SVO, SVA, ...), которыепринимают на вход слова в виде пар (вектор, морфология) и объединяют их водну пару.108Список используемых грамматических структур для семантических векторных представлений:• AN (прилагательное - существительное);• SVO (субъект - действие - объект);• SVA (субъект - действие - наречие);Для обучения части семантических векторных представлений используютсяавтоэнкодеры разных размеров (n×k, где n - количество элементов в грамматической структуре (например, n = 2 для AN, n = 3 для SVO и SVA), k - размервекторного пространства слов, равно 300).2.
Часть «распределение по категориям сематического представления», которая принимает на вход объединенный вектор и вычисляет распределение категорий по предложению, является слоем Softmax.3. Часть «распределение по категориям текста», которая принимает на входраспределения категорий по предложениям и вычисляет распределение категорий по тексту.Рис. 4.7: Семантическое векторное представление.109Тестирование нейро-семантической сети на основе морфологического анализа - MNSNКлассификация базы данных Movie Review [40]:МетодMovie ReviewRAE (Socher et al., 2011)MV-RNN (Socher et al., 2012)CNN-randCNN-staticCNN-non-staticCNN-multichannel77.779.076.181.081.581.1MNSN79.3Классификация баз данных Wikinews [40]:МетодWikinews-Ru Wikinews-EnNaive BayesNearest CentroidKNNKNN с двоичным деревом66.468.672.571.781.186.387.388.9MNSN75.291.34.2.3Экспериментальное исследование рекурсивного автоэнкодера морфологического анализаРекурсивный автоэнкодер состоит из двух параллельных нейронных сетей [40]:1.
Сеть «слово-вектор» состоит из 3 слоев: входной и выходной слои содержатпо 600 нейронов (соответствует размеру двух векторов слов), скрытый слойсодержит 300 нейронов;2. Сеть «морфология» состоит из 3 слоев: входной и выходной слои содержатпо 600 нейронов (соответствует размеру двух векторов морфологии), скрытыйслой содержит 300 нейронов;Для обучения векторного представления морфологии можно использоватьте же методы обучения векторного представления слов.110Взвешенный параметр для ошибок регрессии и объединения β = 0.2.Тестирование рекурсивного автоэнкодера морфологического анализа - MRAEКлассификация базы данных Movie Review [40]:МетодMovie ReviewRAE (Socher et al., 2011)MV-RNN (Socher et al., 2012)CNN-randCNN-staticCNN-non-staticCNN-multichannel77.779.076.181.081.581.1MRAE80.6Классификация баз данных Wikinews [40]:МетодWikinews-Ru Wikinews-EnNaive BayesNearest CentroidKNNKNN с двоичным деревом66.468.672.571.781.186.387.388.9MRAE74.390.2111Рис.
4.8: Точность классификации базы Wikinews-En рекурсивным автоэнкодером морфологического анализа в зависимости от взвешенного параметра α дляошибок объединений слов и морфологических разборов [40].Тексты в базах новостей Wikinews имеют более стандартную грамматикучем в базе Movie Review, этот морфологический уровень существенно влияет накачество классификации нейро-семантической сети на основе морфологическогоанализа и рекурсивного автоэнкодера морфологического анализа, как показанов результатах тестирования, они работают с Wikinews лучше чем с Movie Review.4.2.4Экспериментальное исследование алгоритма «К» ближайших соседей с использованием двоичного дереваБыло проведено тестирование вычислительного комплекса алгоритма «К» ближайших соседей с использованием двоичного дерева [32] на корпусе Wikinewsна английском и русском языках, и сравнение его скорости, а также точностипо сравнению с другими алгоритмами классификации текстов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
