Частотный анализ текстовой информации на параллельных вычислителях тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Ба Хла Тхан

• Ба Хла Тхан
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Ба Хла Тхан

Введение

ГЛАВА 1. ЗАДАЧИ АНАЛИЗА ТЕКСТОВОЙ ИНФОРМАЦИИ И ИХ ПРИМЕНЕНИЕ

1.1 Классификация текста

1.1.1 Классификаторы

1.2 Особенности предварительной обработки текстов на турецком языке при их классификации

1.3 Классификация текста с помощью комбинаций классификаторов

1.4 Классификация текста с помощью частотных профилей N-грамм

1.4.1 Инверсные индексы N-грамм

1.4.2 Авторизация арабских текстов с помощью N-грамм

1.4.3 Анализ статистики N-грамм в MapReduce

1.5 Методы извлечения информации из текстовых документов

1.5.1 Особенности анализа текстов на естественном языке

Выводы по главе

ГЛАВА 2. МОДЕЛИ И АЛГОРИТМЫ АВТОМАТИЧЕСКОГО АНАЛИЗА ТЕКСТОВОЙ ИНФОРМАЦИИ

2.1 Распределенные вычисления в модели MapReduce

2.2 Синхронизация работы узлов

2.3 Частота парных словосочетаний

2.4. Извлечение ключевых слов на основе модели MapReduce

2.4.1 Реализация алгоритма на основе MapReduce

2.5. Упрощенный вариант алгоритма частотного анализа

Выводы по главе

ГЛАВА 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА ЧАСТОТНОГО АНАЛИЗА ТЕКСТА

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

3.1.1 Разделение алфавита между потоками

3.1.2 Разделение текста между потоками

3.2 Статическая балансировка нагрузки при частотном анализе текстовой информации

3.2.1 Статическая балансировка нагрузки при анализе биграмм

3.2.2 Балансировка нагрузки для ускорителя Intel Xeon Phi

ГЛАВА 4. РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЙ ЭФФЕКТИВНОСТИ ПАРАЛЛЕЛЬНОЙ РЕАЛИЗАЦИИ АЛГОРИТМА

4.1 Частотный анализ монограмм

4.1.1 Результаты для вычислительной платформы

4.1.2 Результаты для вычислительной платформы

4.1.3 Результаты для вычислительной платформы

4.2 Частотный анализ биграмм

4.2.1 Результаты для вычислительной платформы

4.2.2 Результаты для вычислительной платформы

4.2.3 Результаты для вычислительной платформы

Выводы по главе

Заключение

Список литературы

Приложение 1. Результаты вычислительных экспериментов

Приложение 2. Акт внедрения

КТ Классификации текста

IPS Intel Parallel Studio

KNN Метод k-ближайших соседей

MapReduce Модель распределенных вычислений

ME Принцип максимума энтропии

NBC Наивные классификаторы Байеса

RC Классификатор Роккио

SVM Метод опорных векторов

SPMD Single Program Multiple Data

Актуальность проблемы. На протяжении всей истории человеческого

общества люди накапливали информацию. Сначала они использовали для

этого примитивные рисунки, а с появлением алфавита основными

носителями знаний стали книги. Их собирали в библиотеки,

систематизировали и каталогизировали. При этом люди давно поняли, что

ценностью обладает не сам носитель информации, а те знания, которые в нем

заключены. Хотя традиция заключать особо ценные знания в

соответствующую оболочку жива и по сей день, сегодня на первый план

выходит именно доступность информации. И важнейшую роль в этом играют

информационные технологии и компьютеры. Если оценивать объемы

ежедневно производимой человечеством информации, то их рост за

последние десятилетия относят к категории взрывных явлений и называют

информационным взрывом. Конечно, речь в данном случае идет только об

объеме информации, а не о тех знаниях, которые она несет. Скептики

считают, что объем новых знаний, производимых человечеством и

достойных хранения и передачи, растет гораздо медленнее. Парадоксально,

но прогресс привел нас к тому, что концентрация знаний в общем объеме

информации постоянно снижается. Для хранения колоссальных объемов

информации требуются все большие мощности, а задача выделения в этой

«куче» нужной «крупинки» становится все труднее. Не менее интересны и

задачи, связанные с исследованием древних рукописей. Если раньше этот

процесс требовал непременного участия человека, то сейчас мы можем

многие задачи решать с помощью компьютеров. К задачам анализа текстов,

для которых найдены достаточно эффективные алгоритмы решения, можно

отнести такие, как категоризация, установление авторства и выделение

ключевых слов. При всем разнообразии применяемых подходов,

большинство из них базируются на частотном анализе текста, результатом

которого будут частотные профили ^грамм или, в частном случае,

отдельных слов. На их основе может быть сформировано решение о

5

принадлежности текстового фрагмента одному из классов или авторов.

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

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

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

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

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

1. Проанализированы различные системы анализа текстовой информации и

используемые в них метрологические параметры. Показано, что

6

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

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

3. Разработана параллельная реализации алгоритма частотного анализа текста.

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

Объект и предмет исследования. Объектом исследования являются системы анализа текстовой информации.

Предмет исследования составляют параллельные алгоритмы частотного анализа текста.

Методы исследования. При решении поставленных задач были использованы положения теории вероятностей, теории множеств, методы параллельного программирования.

Научная новизна диссертационного исследования заключается в научном обосновании нового подхода к повышению эффективности методов частотного анализа текста, и состоит в следующем:

1. Предложен метод статической балансировки нагрузки узлов для параллельного алгоритма частотного анализа текстовой информации, основанный на учёте статистики появления N-грамм в различных языках.

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

3. Исследованы особенности реализации многопоточных приложений для построения частотных профилей N-грамм на различных многоядерных платформах.

4. Разработана и реализована в среде Intel Parallel Studio параллельная

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

7

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

Теоретическая и практическая значимость работы заключается в следующем:

1. Предложен и практически апробирован метод статической балансировки нагрузки вычислительных узлов для параллельного алгоритма построения частотных профилей К-грамм.

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

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

4. Предложенный в диссертационной работе метод балансировки нагрузки узлов для параллельных приложений используется при изучении курса «Применение высокопроизводительных вычислительных систем в научных исследованиях» в Институте МПСУ НИУ МИЭТ. Акт внедрения представлен в диссертации.

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

Внедрение результатов. Результаты диссертационных исследований внедрены в учебный процесс в Национальном исследовательском университете МИЭТ при изучении курса «Параллельное и распределенное программирование».

Результаты, выносимые на защиту.

1. Метод статической балансировки нагрузки узлов для параллельно алгоритма частотного анализа текстовой информации.

2. Сравнительный анализ эффективности методов распределения нагрузки для алгоритма частотного анализа текстовой информации.

3. Программная реализация алгоритма частотного анализа в среде Intel Parallel Studio.

4. Результаты экспериментальных исследований эффективности многопоточной реализации алгоритма частотного анализа.

Апробация работы. Основные положения диссертации были представлены и обсуждались на 14 международных, всероссийских и межвузовских научных конференциях:

1. Актуальные проблемы информатизации в науке, образовании и экономике. 6-я Всероссийская межвузовская научно-практическая конференция. МИЭТ,

2. Международная научно-практическая конференция «Образование и наука: современное состояние и перспективы развития». Тамбов,

3. XIV Международная конференция «Высокопроизводительные параллельные вычисления на кластерных системах», Пермь,

4. Международная научно-практическая конференция «Актуальные вопросы образования и науки». Тамбов,

5. Всероссийская научно-практическая конференция «Информационно-телекоммуникационные системы и технологии» (ИТСиТ-2014), Кемерово,

6. Микроэлектроника и информатика - 2014. 21-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. МИЭТ,

7. Актуальные проблемы информатизации в науке, образовании и экономике. 7-я Всероссийская межвузовская научно-практическая конференция. МИЭТ,

8. Международная конференция «Инновационные подходы к решению технико-экономических проблем». МИЭТ,

9. Актуальные проблемы информатизации в науке, образовании и экономике. 8-я Всероссийская межвузовская научно-практическая конференция. МИЭТ,

10. Fifth International Conference on Internet Technologies and Applications (ITA 15), Glyndwr University, Wrexham, North Wales, UK,

11.Микроэлектроника и информатика - 2016. 23-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. МИЭТ,

12.IEEE NW Russia Young Researches in Electrical and Electronic Engineering Conference (EIConRusNW). St. Petersburg, Russia,

13. IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus) Moscow, Russia,

14. IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus) Moscow, Russia, 2018 Публикации. По материалам диссертации опубликовано 5 тезисов

докладов и 12 статей, в том числе 2 в журналах, входящих в перечень ВАК, 5 работ включены в базу Scopus.

Структура и объём диссертационной работы. Рукопись диссертационной работы, общим объемом 112 страниц, состоит из введения, четырех глав, заключения, списка литературы из 72 источников и двух приложений.

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

Поиск и обработка информации относится к одной из наиболее востребованных в современном мире задач, что определяет ее актуальность и интерес к ней исследователей. Рассмотрим некоторые общие задачи, связанные с анализом текстовой информации, представленной в электронном виде, и основные методы их решения.

1.1 Классификация текста

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

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

1. Классификация начинается со сбора коллекции текстов, возможно в различных форматах.

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

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

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

5. После выбора признаков производится непосредственная классификация с использованием одного из алгоритмов (классификаторов).

6. На последнем этапе проводится оценка качества проведенной классификации. Если получен неудовлетворительный результат, проводится корректировка признаков или даже смена классификатора.

1.1.1 Классификаторы

В качестве классификаторов используют различные алгоритмические подходы [2]. Рассмотрим наиболее популярные.

Наивные классификаторы Байеса (NBC) - простые вероятностные классификаторы, основанные на теореме Байеса. Эти классификаторы хорошо масштабируются и включают в себя семейство алгоритмов, основанных на предположении, что значение одного классифицирующего признака не зависит от значения другого. На практике предположение о независимости часто нарушается, но байесовские классификаторы по-прежнему очень популярны, во многом благодаря простоте реализации.

Принцип максимума энтропии (ME) - это общий и интуитивно

понятный способ оценки вероятности состояний, и он успешно применяется

в различных задачах обработки естественного языка, таких как

моделирование языка, разделение на части речи и сегментация текста. В его

основе лежит предположение, что условная вероятность должна быть как

можно более однородной, т.е. должна иметь максимальную энтропию.

Основным преимуществом такого подхода для задачи классификации

Введение диссертации (часть автореферата) на тему «Частотный анализ текстовой информации на параллельных вычислителях»

является универсальность и применимость для любой произвольной

релевантной информации. Недостаток метода связан с тем, что алгоритм,

12

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

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

Метод ^ближайших соседей (КЫЫ) - непараметрический метод, который является одним из простейших алгоритмов классификации. Это метод простого обучения, в котором функция локально аппроксимируется, а все вычисления производятся до классификации, а результатом является член класса. Классификация объекта выполняется на основе общности его к-ближайших соседей, где к - положительное целое число. Если к = 1, то объект просто присваивается тому же классу, что и единственный ближайший сосед. Преимуществом метода является простая реализация и непараметрические свойства, но при этом процесс классификации занимает много времени.

Метод опорных векторов (БУМ) - это алгоритм классификации текста,

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

классификации, потому что он нуждается как в положительных, так и в

отрицательных обучающих выборках. Это нужно для поиска поверхности

решения (гиперплоскости), которая лучше всего отделяет положительные от

отрицательных данных в п-мерном пространстве. Тексты, которые находятся

ближе всего к гиперплоскости, называются опорными векторами. Метод

опорных векторов стремится найти линейные функции для решения

13

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

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

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

1.2 Особенности предварительной обработки текстов на турецком языке

при их классификации

Анализ текста на естественном языке (NLP) включает в себя различные

задачи, например, классификация текста, исправление ошибок, машинный

перевод. В этом ряду выделяется задача классификации текста, важность

которой быстро растет, учитывая значительный рост объема текстовых

документов, доступных в интернете. Основные подходы к ее решению

опираются на нейронные сети, а многочисленные современные алгоритмы

обучения позволяют получить высокое качество классификации.

Автоматические методы классификации текста позволяют не только

14

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

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

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

В работе [2] описан опыт использования п-грамм для классификации

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

Выборка состоит из статей, полученных из турецких ежедневных газет. В

обучающей выборке есть информация об авторах, их поле и жанре статей. С

использованием этой информации, проводится обучение классификатора.

Первоначальные ожидания заключались в достижении более высоких

значений точности для жанровых и гендерных классификаций, чем

15

классификация авторов. На первом этапе авторы извлекают би- и триграммы из текстов. В общем случае, n-граммы являются конкатенацией каждого n-слова (или символьной последовательности) в тексте. Однако конкатенация каждого n-слова во всех статьях может значительно увеличить число параметров функции. Например, биграммы одного документа дают приблизительно 500 признаков. Если применить этот процесс ко всем документам, количество параметров будет очень высоким, что приведет к переобучению или комбинаторному взрыву. Поэтому для уменьшения числа признаков и удаляются n-граммы, если число их появления в тексте меньше двух. После фильтрации параметров документы классифицируют с разными наборами n-грамм, чтобы оценить влияние фильтрации на точность классификации. Для этого авторы вводят функцию Fj для численной оценки влияния выбора наборов n-грамм: уровень символа, слова, биграммы или триграммы.

р _ 2 * Precision * recall 1 precision + recall

В этом выражении параметр precision показывает долю объектов, которые были правильно отнесены к своему классу, а параметр recall - долю классифицированных объектов. Таким образом, функция Fj обеспечивает баланс между точностью классификации и отзывчивостью классификатора.

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

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

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

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

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

В работе [7] представлено подробное исследование эффективности объединения классификаторов при классификации мультимедийных документов в гетерогенных классах. Различные комбинации классификаторов опробованы на выборке из 5000 документов веб-страниц Европейского исследовательского проекта Net Protect II. Результаты экспериментов доказывают, что объединение классификаторов дает лучшее

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

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

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

Интересные результаты анализа совместной работы методов KNN и RC представлены в [11]. Первичный набор используется для формирования нижних и верхних границ функций для каждого класса, классифицируемого по методу Роккио. Но он не может работать, если параметры анализируемого документа находятся в граничной области, и здесь уже используется KNN. Такой стиль объединения методов классификации позволяет преодолевать их недостатки.

Соединения методов классификации текста, относящихся к одной и той

же вероятностной парадигме, исследованы в работе [12]. Для тестирования

18

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

Авторы в работе [13] представили результаты распознавания объектов из медицинского набора данных, содержащего неформальный и неструктурированный текст. Они используют объединение результатов классификации методами условного случайного поля (CRF) и ME. Каждый классификатор обучается с использованием своего набора функций. CRF специализируется на контекстных особенностях текстов, а ME на лингвистических особенностях каждого слова. Комбинированные результаты были лучше, чем индивидуальные результаты обоих классификаторов.

Метод улучшения алгоритма классификации N-граммов за счет применения в нем поиска на основе имитации отжига (Simulated Annealing, SA) описан в статье [14]. Гибридный классификатор назван авторами NGramsSA. Его можно считать модификацией классификатора NGrams, использующей все преимущества оригинального подхода. Используется метод уменьшения числа параметров, поскольку при высокой размерности производительность классификатора падает.

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

Поскольку в диссертации основное внимание уделяется параллельной реализации частотного анализа текста, рассмотрим более подробно примеры классификаторов, использующих ^граммы. В общем случае ^грамма это фрагмент ^символов из более длинной строки. Иногда этот термин может использоваться и для фрагментов из не соседних символов, например, биграммы, составленные из первого и третьего символов слова. Но смежные срезы используются гораздо чаще. Как правило, на первом этапе анализатор переводит строку текста в набор перекрывающихся ^грамм. Классификаторы могут использовать как ^граммы одинаковой длины, так и различной. Это повышает точность классификации. Рассмотрим пример выделения смежных №грамм из слова «МАСКА»: биграммы: _М, МА, АС, СК, КА, А_ триграммы: _МА, МАС, АСК, СКА, КА _ квадрограммы: _МАС, МАСК, АСКА, СКА _

Если учесть лидирующие и замыкающие пробелы, то строка длиной к порождает k+1 биграмм, k триграмм и квадрограмм.

Важной особенностью №грамм, объясняющих их широкое применение, является их устойчивость к ошибкам в тексте по сравнению с анализаторами слов. Кроме того, в любых языках есть устоявшийся набор наиболее часто употребляемых слов. То же можно сказать и об устоявшемся наборе слов для определенных классов текста. Можно считать, что существует плавное распределение частот появления различных слов во всех языках человечества. Это утверждение верно и для частоты появления N грамм. Как следствие, классификация документов на основе частоты N грамм не будет очень чувствительной к отсечению наименее часто встречающихся компонентов. Это также подразумевает, что документы из той же категории, будут иметь аналогичные распределения частот ^грамм. На практике, отсечения №грамм используются во всех классификаторах.

New

Document

Selected Category'

Рис. 1 Классификация текстов с использованием N-грамм.

Рассмотрим отдельные этапы классификации.

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

Построение профиля включает следующие процедуры:

Category Samples

- из образца удаляются все литеры, не анализируемые классификатором (в некоторых реализациях такие литеры игнорируются при последующем сканировании);

- сканируется текст и формируется частотный профиль для ^граммы;

- процесс повторяется для всех значений N

- профили сортируются по убыванию частоты №грамм (при сокращенном наборе ^грамм процедура не выполняется).

В результате получается файл - частотный профиль №грамм для классифицируемого документа.

Использование различных ^граммных профилей частот для классификации имеет некоторые особенности. Необходимо учитывать, что частоты 300-400 наиболее часто встречающихся ^грамм гораздо сильнее коррелируют с языком текста, чем с его содержанием. Это значит, что длинные отрывки текстов из различных классов, но на одном языке будут иметь сходные профили №грамм.

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

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

1.4.1 Инверсные индексы ^грамм

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

Для определения числа вхождений некоторого фрагмента в текст, есть

два известных класса алгоритмов. Первый обрабатывает текст как поток

22

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

Второй класс алгоритмов использует индексные файлы, которые обеспечивают быстрый доступ к вхождениям. Временная сложность алгоритмов этого класса зависит от числа элементов в индексном файле [16]. Индексный файл должен быть загружен в оперативную память, а его размер может значительно превышать объём исходного текста. Ускорение поиска в таких алгоритмах достигается в основном за счет модификации структуры самих индексов: инвертированные индексы [17], суффикс-деревья [18] и массивы суффиксов [19]. Однако при этом растёт и объём индексных файлов. Он может быть в 4-20 раз больше исходного текста [20].

Наиболее часто используются два типа инвертированного индекса: первый основан на словах, а второй на К-граммах. Преимущества К-грамм индекса заключаются в том, что он является инвариантным по отношению к языкам и устойчивым к ошибкам. Однако, по крайней мере, в четыре раза больше размера индексируемого текста.

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

В работе [21] представлен подход, основанный на статистических свойствах текстовых компонентов. Текст разбивается на сегменты равной длины, а затем формируется набор наименее частых К-грамм для каждого сегмента. На втором этапе формируется частичный инвертированный индекс, в словаре которого хранятся только менее частые К-граммы и указатели на все сегменты.

Важнейшим преимуществом метода частичного индексирования

является его гибкость. Фактически, параметры легко настраиваются, делая

23

индекс адаптированным в соответствии с потребностями пользователей. Время поиска и размер индекса можно сбалансировать, варьируя три параметра: длину сегмента, порог частоты и размер ^граммы.

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

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

1.4.2 Авторизация арабских текстов с помощью ^грамм

Развитие компьютерных и интернет-технологий в последние десятилетия приводит к лавинообразному увеличению объёмов онлайн-данных - за одну секунду интернет-трафик превышает 50 ГБ. Этот огромный объем данных, большая часть которых текстовая, является общедоступным и свободно распространяемым. Очень часто анонимным способом. Значительная часть пользователей интернета скрывается за псевдонимами, поэтому во время серфинга в сети приходится иметь дело с данными, источник которых неизвестен.

В установлении потенциального источника данных заинтересован

коммерческий сектор, где такая информация о клиенте, как его возраст, пол,

национальность и родной язык, имеет большую ценность для маркетинговой

политики. А, кроме того, сектор безопасности, который призван защищать

ресурсы интернета от таких преступлений, как плагиат и кража личных

24

данных. Поэтому исследование и разработки эффективных методов авторизации текстов является востребованным.

В работе [22] исследованы методы классификации арабских пользователей по гендерному типу на основе анализа сообщений в твитерах.

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

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

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

Частотные профили используются в качестве входных данных для обучения классификатора. Авторы применяют для обучения известный блочный метод [23], который заключается в объединении нескольких базовых классификаторов различного типа. В этом приложении используют три самых популярных алгоритма машинного обучения - SVM, деревья решений и NBC [24]. Такой подход позволил достичь высоких результатов при определении разнообразия языков и пола [25].

1.4.3 Анализ статистики N-грамм в MapReduce

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

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

Для построения индексных файлов часто используется технология MapReduce (реализация Hadoop), которая обеспечивает платформу для распределенной обработки больших данных. MapReduce предлагает модель программирования, которая обеспечивает обработку отказов узлов во время вычислений и автоматическое распределение работы. Более подробно анализ MapReduce будет представлен в главе 2, здесь отметим лишь то, что эта технология не предназначена для создания инверсных индексов, используемых в комбинированных классификаторах.

В работе [26] рассматривается проблему эффективного вычисления ограниченной статистики N-грамм на платформах MapReduce.

Эксперименты авторов на двух реальных наборах данных показывают, что адаптация MapReduce на основе методов APRIORI [27], [28] работает не эффективно, поэтому ими был предложен новый метод SUFFIX, основанный на идеях строковой обработки. Метод позволяет использовать функциональность этапов группировки и сортировки MapReduce и использует их для экономии основной памяти при определении частот всех рассматриваемых N-грамм. Метод SUFFIX превосходит конкурентов в 12 раз, когда анализируются частоты длинных или редких N-грамм.

Еще один пример использования MapReduce для определения частоты появления слов в коллекции документов представлен в работе [29]. Он позволяет адаптировать метод для подсчета N-грамм переменной длины и уменьшить размер индексного файла.

1.5 Методы извлечения информации из текстовых документов

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

объектах, принятым во всем мире, являются текстовые данные. Это

Список литературы диссертационного исследования кандидат наук Ба Хла Тхан, 2019 год

СП 20

0

5 4,5 4 3,5

Ш

I з

0.2,5 О * 2

£

1,5 1 0,5 0

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

Размер текста 1010

Размер текста 5*109

Размер текста 1010

Размер текста 1010

Размер текста 5*109

Размер текста 1010

Размер текста 5*109

Размер текста 1010

Размер текста 1010

Размер текста 1010

Размер текста 5*109

Размер текста 1010

о

Размер текста 5*10

Размер текста 1 09

-—160 ш

^.¿.140

ОС ^ 120 I

ш

I

с;

О 80

С

о

Размер текста 5*10

(и и

I

(и

I

с; о с

-О

со

90

80

70

60

50

40

30

20

(и а

СО 10

4

I

(и

& 3 £

2

Размер текста 1 09

6

5

1

0

0

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

о

Размер текста 5*10

Размер текста 1 09

о

Размер текста 5*10

90

80

^ Ш

^ 70

ОС ^ 60 I

си

I

с;

о 40 С

Ю 30

50

20

си о. со

10

ш 4

5

I

Ш а

О

^2

Размер текста 1 09

180

"^160 (и

■¿(140 с: ^ 120

си 1100

| 80 .с

аз 60 с:

§ 40

Ш

С^

СП 20

0

Ш4 5 I Ша

0.3 О

^2

6

5

1

0

0

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

6

5

1

0

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

о

Размер текста 5*10

Размер текста 1 09

о

Размер текста 5*10

Размер текста 1 09

о

Размер текста 5*10

Размер текста 109

о

Размер текста 5*10

Размер текста 1 09

о

Размер текста 5*10

Размер текста 1 09

о

Размер текста 5*10

Размер текста 1 09

о

Размер текста 5*10

Размер текста 1 09

о

Размер текста 5*10

Размер текста 1 09