Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Методы и алгоритмы обработки текстового контента с использованием высокопроизводительных вычислительных кластеров Кошкин Дмитрий Евгеньевич

Методы и алгоритмы обработки текстового контента с использованием высокопроизводительных вычислительных кластеров
<
Методы и алгоритмы обработки текстового контента с использованием высокопроизводительных вычислительных кластеров Методы и алгоритмы обработки текстового контента с использованием высокопроизводительных вычислительных кластеров Методы и алгоритмы обработки текстового контента с использованием высокопроизводительных вычислительных кластеров Методы и алгоритмы обработки текстового контента с использованием высокопроизводительных вычислительных кластеров Методы и алгоритмы обработки текстового контента с использованием высокопроизводительных вычислительных кластеров Методы и алгоритмы обработки текстового контента с использованием высокопроизводительных вычислительных кластеров Методы и алгоритмы обработки текстового контента с использованием высокопроизводительных вычислительных кластеров Методы и алгоритмы обработки текстового контента с использованием высокопроизводительных вычислительных кластеров Методы и алгоритмы обработки текстового контента с использованием высокопроизводительных вычислительных кластеров Методы и алгоритмы обработки текстового контента с использованием высокопроизводительных вычислительных кластеров Методы и алгоритмы обработки текстового контента с использованием высокопроизводительных вычислительных кластеров Методы и алгоритмы обработки текстового контента с использованием высокопроизводительных вычислительных кластеров
>

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

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Кошкин Дмитрий Евгеньевич. Методы и алгоритмы обработки текстового контента с использованием высокопроизводительных вычислительных кластеров: диссертация ... кандидата технических наук: 05.13.15 / Кошкин Дмитрий Евгеньевич;[Место защиты: Московский государственный институт радиотехники, электроники и автоматики (технический университет)].- Москва, 2014.- 145 с.

Содержание к диссертации

Введение

Глава 1 Анализ существующих методов и алгоритмов разделения текстового контента и извлечения знаний. Типовые архитектуры вычислительных комплексов . 14

1.1 Теории, используемые при анализе текстового контента. 14

1.2 Методы классификации и алгоритмы кластерного анализа текстового контента 22

1.3 Оценка алгоритмов кластеризации по критериям вычислительной сложности 31

1.4 Аппаратные и программные платформы развертывания вычислительных кластеров . 35

1.4.1 Технологии сетевого объединения вычислительных узлов 38

1.4.2 Программные платформы развертывания вычислительных кластеров. 41

1.4.3 Гибридные кластеры с графическими процессорами (GPU) 44

1.5 Заключение. Постановка задачи. 46

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

2.1 Развитие многопоточности для алгоритмов кластеризации на примере алгоритма Нечетких C-средних. 48

2.1.1 Метод использования энтропийной меры оценки алгоритма Нечетких C-средних для контроля процесса кластеризации и повышения ее качества. 55

2.2 Метод параллельной обработки минимальных синтаксических структур с использованием базовых характеристик объектно-ориентированных языков высокого уровня . 56

2.3 Разработка вычислительного кластера со свойствами расширяемости, масштабируемости и интероперабельности. 63

2.3.1 Допущения и ограничения в выборе аппаратной платформы для реализации вычислительного кластера. 63

2.3.2 Допущения и ограничения программной платформы для реализации вычислительного кластера. 66

2.3.3 Методика использования особенностей стандартов для повышения производительности сетевых соединений вычислительных кластеров на основе протокола Ethernet. 78

2.4 Заключение. 84

Глава 3 Развертывание вычислительного кластера на примере кластера в МГТУ МИРЭА. Практическая реализация методов и алгоритмов многопоточной обработки текстового контента на высокопроизводительных вычислительных кластерах . 85

3.1 Программная платформа для развертывания кластера MuninnHPC на основе доработанной кластерной платформы PelicanHPC 85

3.2 Реализация алгоритма кластеризации с использованием многопоточности и графических процессоров (GPU Fuzzy C-Means) на языке Python 91

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

3.3 Апробация созданных кластеров в условиях конкуренции в проекте Folding@HOME.97

Глава 4 Практические исследования многопоточной кластеризации текстового контента на естественном языке . 101

4.1 Сравнение вычислительной скорости центрального и графического процессоров 101

4.2 Кластеризация тестовой подборки художественных текстов 104

4.2.1 Результаты экспериментов предобработки текстов с модулем mystem 106

4.2.2 Предобработка текстов с модулем PyMorphy2 110

Заключение. 118

Библиография. 123

Приложения 134

Введение к работе


Актуальность исследования.
В настоящее время зародилось и
развивается новое направление в области обработки данных – Большие данные
(Big Data). Т.е. данные большого объема (Volume), разных типов и меры
структурированности (Variety), которые требуется быстро обработать и
получить результат (Velocity). Текстовый контент, содержащийся в научных
статьях, технической литературе, сети Интернет, художественных

произведениях и других источниках полностью подходит под первые две
характеристики. Обработка текстового контента ведется в информационно-
поисковых системах, или при создании семантических сетей. С учетом
существующего объема информации, часто используемые методы обработки
контента: кластерный анализ, семантический анализ, контент-анализ и другие,
требуют новых инструментов и алгоритмов, уменьшающих процессорное
время, затрачиваемое на обработку массивов данных. Разделение текстов по
тематике является первой задачей при обработке неструктурированных
текстовых массивов, так как существуют термины, имеющие одинаковое
написание, но разное значение в разных областях знания (например, понятие
«онтология» различно трактуется в философии и в теории информации).
Второй задачей является обработка полученных структурированных групп
текстов и извлечение из групп информации посредством морфологического и
семантического анализа. Сложность глубокого семантического анализа текстов
на естественном языке приводит к необходимости искать новые методы
обработки, упрощающие процесс. Для всех методов, основными

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

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

Ряд авторитетных исследователей, таких как И.Е. Поляков, А.К.
Скуратов, Г.С.Осипов, И.А. Тихомиров, Ю.Л. Леохин, Д.В. Ландэ,
Ю.И.Сбитнев, Ю.Д. Апресян, И.А. Мельчук, А.К.Жолковский, Г.А.Золотова,
И.В. Сегалович, G.Salton, S.Guha, A. Singhal, F. Sebastiani, S. Lawrence, P. Foltz,
L. Gravano, G.M.Amdahl, Вл.В. Воеводин, В.В. Воеводин своими работами
внесли значительный вклад в развитие высокопроизводительных

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

Активно ведут работы в этих направлениях такие организации, как
Институт системного анализа РАН, Центр Анализа Интернет Ресурсов, Яндекс,
Wolphram|Alpha, Google, Южный Федеральный Университет, Объединенный
Институт Ядерных Исследований, Центр Высокопроизводительных

Вычислительных Кластерных Технологий, Научно-Исследовательский

Вычислительный Центр МГУ.

Таким образом, актуальность темы диссертации диктуется

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

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

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

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

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

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

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

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

  4. Сформулировать рекомендации, для модификации и реализации алгоритмов кластеризации для работы в среде гибридных кластеров.

  5. Сформировать профиль стандартов, обеспечивающий кластерам свойства расширяемости, масштабируемости и интероперабельности.

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

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

Предмет исследования. Предмет исследования определен паспортом специальности 05.13.15 (областями исследования 2,3 и 4), и состоит в многопоточных методах и алгоритмах кластеризации и извлечения информации из текстового контента и исследование высокопроизводительных кластеров, с целью улучшения их эксплуатационных характеристик.

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

Научная новизна. На основе правил морфологического и

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

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

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

применения алгоритма в области кластеризации текстового контента кластеризации Нечетких С-средних. На основе анализа установлена возможность проводить анализ текста по авторскому стилю, который можно выразить математическим языком. Также установлена взаимосвязь между авторским стилем и полом автора. Как результат, показано, что кластеризация может осуществляться не только по тематике контента, но и по предполагаемому автору и/или полу автора контента. Для контроля и анализа процесса кластеризации модифицированным алгоритмом предложен метод с использованием информационной энтропии в качестве контрольного параметра. Метод позволяет получать информацию о процессе кластеризации до достижения алгоритмом финальной стадии. В результате, уже на первых шагах алгоритма, можно делать вывод о правильность заданных параметров и предполагаемом результате.

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

максимальной расширяемости и масштабируемости оборудования и

программного обеспечения. Для модифицированного алгоритма определены шаги многопоточного вычисления на графических процессорах, исследованы и показаны два способа распределения математических вычислений на графические процессоры: на узлы вычислительного кластера с одним и несколькими графическими ускорителями. Показаны правила распределения строк и столбцов матриц по процессам и потокам, с целью повышения скорости работы алгоритма. Разработано и реализовано программное обеспечение, использующее модифицированный алгоритм с технологией Compute Unified Device Architecture (CUDA) и библиотекой Message Passing Interface, таким образом обеспечивая многопоточность и скорость работы. Реализованный алгоритм подтверждает целесообразность и общую полезность соблюдения предложенных рекомендаций. Универсальность реализованного программного обеспечения обеспечена разделением модулей, отвечающих за статистическую обработку текстов, за процесс кластеризации и передаваемую на узлы информацию. Созданы условия для кластеризации текстового контента по тематике, авторскому стилю, полу автора, а также, наборов числовых данных, не относящихся к текстовому контенту. Установлено, что рекомендации, созданные для повышения пропускной способности сетевых соединений кластеров из специализированных компонентов и для систем хранения данных, при условии соблюдения стандартов всеми узлами также применимы и для кластеров, состоящих из широко распространенных компонентов. Соблюдение

рекомендаций и стандартов позволяет повысить пропускную способность соединений на 4-5%.

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

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

обеспечивающий работу модифицированного алгоритма Нечетких C-средних.

Апробация результатов заключается в том, что научные положения, выводы и результаты диссертационной работы опубликованы в 16 журналах и сборниках, в том числе 3 статьях в журналах из списка ВАК и докладывались и обсуждались на 8 научных и научно-практических российских и международных конференциях. На разработанное программное обеспечение получено 2 свидетельства о регистрации в Роспатенте.

Аппаратные и программные платформы развертывания вычислительных кластеров

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

Следует иметь в виду, что производительность персональных компьютеров на базе процессоров Intel в последние годы также значительно выросла. Такие компьютеры стали создавать серьезную конкуренцию рабочим станциям на базе RISC, особенно по показателю цена/производительность. Одновременно стала приобретать все большую популярность ОС Linux - бесплатно распространяемая версия UNIX. При этом в научных организациях и университетах, как правило, имеются энтузиасты свободного программного обеспечения и специалисты ("гуру") по ОС Linux.

В 1994 году, в NASA возникла идея [30] создания параллельных вычислительных систем (кластеров) из общедоступных компьютеров на базе Intel и недорогих Ethernet-сетей, устанавливая на эти компьютеры Linux и одну из свободно распространяемых коммуникационных библиотек (PVM, а затем MPI). Оказалось, что для многих классов задач при достаточном числе узлов такие системы дают производительность, сравнимую с производительностью суперкомпьютера.

Основным параметром классификации паралелльных компьютеров является наличие общей (SMP) или распределенной памяти (MPP). Нечто среднее между SMP и MPP представляют собой NUMA-архитектуры, где память физически распределена, но логически общедоступна. Кластерные системы являются более дешевым вариантом MPP. При поддержке команд обработки векторных данных говорят о векторно-конвейерных процессорах, которые, в свою очередь могут объединяться в PVP-системы с использованием общей или распределенной памяти. Все большую популярность приобретают идеи комбинирования различных архитектур в одной системе и построения неоднородных систем.

При организациях распределенных вычислений в глобальных сетях (Интернет) говорят о мета-компьютерах, которые, строго говоря, не представляют из себя параллельных архитектур.

Более подробно особенности всех перечисленных архитектур приведены в таблице 1.2. Для каждого класса суперкомпьютеров приводится следующая информация:

краткое описание особенностей архитектуры,

примеры конкретных компьютеров,

перспективы масштабируемости,

типичные особенности построения операционных систем,

наиболее характерная модель программирования (хотя возможны и другие).

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

PelicanHPC GNU Linux (используется и развивается) [84]

PelicanHPC - это модификация хорошо известного Linux-дистрибутива Debian Live, которая позволяет установить кластер компьютеров для выполнения параллельных вычислений с использованием LAM-MPI и/или MPICH реализаций интерфейса MPI или параллельных виртуальных машин PVM. Можно превратить комнату полную машин, работающих под управлением Windows в Linux-кластер, а после выполнения работ и перезагрузки Windows-машины оказываются в исходном состоянии, какое было до загрузки кластера. Компьютеры в кластере могут быть как гомогенные, так и гетерогенные. Если сетевые карты имеют возможность осуществлять PXE-загрузку, то запуск и конфигурация кластера занимает около 5 минут. Поддерживаются кластеры, содержащие от 2 до 200 машин. Руководство содержит детальные и пошаговые инструкции по установке и настройке кластера.

Debian Cluster Components и DCC/Live (используется и развивается) [85] Debian Cluster Components (DCC) - это набор инструментов для максимально простого построения, управления и развертывания высокопроизводительного Linux-кластера. Набор состоит из следующих системных компонентов: инсталляционный набор, C3, система очередей TORQUE, OpenLDAP и Ganglia. Набор Debian-пакетов, установленный в используемой вами Debian-системе, обеспечивает полные функциональные возможности главной консоли кластера.

DCC/Live - основанный на Knoppix загрузочный CD, который обеспечивает виртуальную инфраструктуру Linux-кластера на единственном компьютере. Консоль кластера (front-node) и три виртуальных вычислительных узла (work-nodes) запускаемых с помощью механизма User Mode Linux доступны пользователю после загрузки системы. Планировщик очередей заданий и другие специфические сервисы кластера предустановлены в систему и не требуют дополнительной настройки. Этот проект главным образом разработан для образовательных целей. Примеры параллельных программ и инструкции включены в состав CD. Scalable Cluster Environment (используется и развивается) [86]

Этот набор программ, названный SCE (Scalable Computing Environment), состоит из инструментального набора для построения кластера, комплексной системы управления (SCMS), масштабируемой системы контроля в реальном времени, Web-ориентированной системы мониторинга (KCAP), параллельных версий Unix-команд и планировщика задач.

ComputeMode (используется и развивается) [87]

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

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

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

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

В решении этой задачи могут помочь модели, описывающее связи между предложениями через доступные характеристики слов – число, род, падеж, и т.д. Представим каждое слово объектом-наследником базового класса – части речи. У таких «объектов» присутствуют наследуемые параметры, влияющие на свойства самих объектов. Наборы параметров, характерные для определенной части речи, можно считать аналогами параметров классов в объектно-ориентированном программировании (ООП). Гипотезируя этот тезис, попробуем найти и иные параллели между основными понятиями ООП и семантикой, грамматикой, морфологией русского языка.

В ООП используются понятия «класс», «объект», «абстракция», «инкапсуляция», «наследование» и «полиморфизм» [111].

Класс является моделью ещё не существующей сущности (объекта), описанной на языке программирования. Фактически, этот класс описывает общее устройство объекта, являясь своего рода его чертежом. Обычно классы разрабатывают таким образом, чтобы их объекты соответствовали объектам предметной области [112]. В русском языке аналогом класса является часть речи, которая содержит в себе набор необходимых параметров: числа, рода, падежа, и других.

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

В дальнейшем, под объектом будем понимать экземпляр класса – сущность в адресном пространстве вычислительной системы, появляющуюся при создании экземпляра класса или копирования прототипа. Исходя из этого определения – объект, наследник класса обладает если не всеми, то большинством его характеристик, при этом слово является экземпляром класса «часть речи» и несет в себе признаки класса-родителя.

"Абстракция данных" - популярная и, как полагают, не всегда верно определяемая техника программирования [111]. Фундаментальная идея, по мнению [111] состоит в разделении несущественных деталей реализации подпрограммы и характеристик, существенных для корректного ее использования. Для корректного использования части речи в словосочетаниях и предложениях большую роль играет несколько характеристики – род, число, падеж. Эти характеристики в большей мере задают формообразующие морфемы слова (в частности окончания). Например, несущественным, для существительного, может быть тип склонения, а существенным – род.

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

Свойство системы использовать объекты с одинаковым интерфейсом без информации о типе и внутренней структуре объекта определяют как ее полиморфизм [111]. Использование в предложениях слов как базовых блоков, так же вовлекает во взаимодействие части речи. Так, в предложении одно прилагательное заменяется другим, с равными характеристиками и строй предложения не изменится, хотя и может измениться смысл. Исходя из примеров, аналогий и параллелей, приведенных выше, делается вывод о том, что текст на практически любом естественном языке должен иметь общие черты с исходным кодом компьютерной программы. Следовательно, должны существовать правила семантики «языка программирования», которые могут быть формализованы и представлены в виде, пригодном для машинной обработки. При этом нельзя исключать погрешностей, возникающих при формализации, которые устраняются при коррекции на экспериментах и при накоплении статистической и фактической информации. В построении связей между предложениями будет видна «замена переменных», равносильная объявлением новой переменной, и дальнейшим ее изменением. Например, в научных текстах объект, о котором говорится впервые, в предложении обычно обозначается существительным в именительном или дательном падеже. Во втором предложении, если речь идет о том же объекте – местоимением, но с сохранением числа и рода. Так же, некоторые виды частей речи можно автоматически изменять, руководствуясь принципами перегрузки методов и переопределения классов. Притяжательное местоимение «его» заменяться на пару слов «принадлежит ему» или «он владеет», что автоматически указывает на объект, упомянутый ранее, и отношения между текущим и предыдущим объектами. По этим аналогиям можно строить связи между двумя и более предложениями, основываясь на схожих параметрах слов, и выражая их через граф, с нагруженными ребрами. При этом сам граф – представление семантических отношений между предложениями, а нагрузки ребер графа выражают отношения между вершинами-объектами. [113]

Еще одной особенностью русскоязычных текстов является их «модульность», где каждое предложение является модулем. В общем случае обработка каждого предложения может вестись независимо ото всего текста, а значит, параллельно на множестве одновременно работающих вычислителей. [114,116]. После чего, результат обработки возвращается на главный вычислитель.

Извлечение информации основано на существовании классов семантических отношений в естественном языке и, следовательно, тексте. Выделяют восемь типов семантических отношений [117]. Функциональные и атрибутные отношения можно назвать достаточно простыми для извлечения, по сравнению с остальными типами отношений, так как согласно пункту 2.4 диссертации между элементами, образующими такие связи, больше согласованности по морфологии слов. Так же, отношения синонимии (вероятно и омонимии) могут определяться на уже созданных семантических сетях по связям, где два или более объекта, имеющие идентичные связи и отношения, приравниваются к синониму, а два одинаковых по написанию объекта с разными связями становятся омонимами.

Семантическая сеть является многослойным объектом, в котором созданы все типы отношений для всех объектов. Однако, на данный момент «полного описания всего» в доступном виде не существует. Ввиду сложности самой задачи и требованиям к ее решению предлагается сначала разделить одну семантическую сеть на соответствующее количество подсетей. А каждую подсеть формировать на основе еще более мелких объектов – инфосетей. В теории семантических сетей определим «инфосеть» как «однородную однослойную сеть объектов, морфологически объединенных отношениями, вытекающими из структуры синтаксической единицы (предложения)». В свете приведенных выше исследований, построение семантической сети за один проход экспертной программы пока не представляется возможным, ввиду сложности однозначного определения семантической составляющей слова с первого раза. Построение же инфосетей не потребует многократного прохода, так как ищутся только определенные связи, которые могут быть выявлены путем сопоставления параметров с первого раза. Так же инфосеть отличается от семантической сети тем, что выделяется только из одного предложения или же текста. Объединение множества инфосетей, составленных при анализе текстов в одном тематическом классе, будет образовывать семантическую подсеть класса. [118]

Программная платформа для развертывания кластера MuninnHPC на основе доработанной кластерной платформы PelicanHPC

Для реализации программной платформы вычислительного кластера использован дистрибутив PelicanHPC, актуальной на 2012 год версии 2.8.

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

Из недостатка указанного дистрибутива можно указать предоставление в виде носителя LiveCD, без возможности установить на внутренний накопитель сервера. Этот недостаток не позволяет вносить изменения «на лету» в зависимости от требований проектов. Преодоление указанного недостатка является первым шагом к созданию вычислительного кластера.

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

Копируется оригинальная файловая система узлов: cp /media/cdrom/pool/casper/filesystem.squshfs /live/image/live cp /media/cdrom/pool/casper/initrd.img-2.6.32-5-486 /live/image/live cp /media/cdrom/pool/casper/vmlinuz-2.6.32-5-486 /live/image/live sudo chown root:root /live/image/live/ sudo chmod 644 /live/image/live/filesystem.squshfs sudo chmod 444 /live/image/live/ -2.6.32-5-486

На диске поставляются программы-скрипты (основными являются): Для первой настройки кластера – pelican_boot_setup.

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

Скрипт перезагрузки кластерной подсистемы: pelican_sertart_hpc – выполняется при добавлении новых вычислительных узлов в кластер. При первом успешном запуске сервера должен быть запущен скрипт pelican_boot_setup. Далее этот скрипт должен запускаться только на узлах при загрузке.

В рамках архитектуры сети МГТУ МИРЭА и конкретных настроек кластеров в вышеперечисленные скрипты были внесены изменения, в части внутренней адресации сети кластера и имен машин. Для мониторинга активности системы используется Ganglia, отображающая нагрузки на процессоры, память, дисковую подсистему и сеть. Так же, система поддерживает пользовательские дополнительные сенсоры, на языках C, Perl, Python, PHP.

Для решения задач, поставленных в пункте 2.9, в кластер MuninnHPC были добавлены пакеты программ, основные из которых приведены в таблице 3.2. В рейтинге Top500 – самых производительных суперкомпьютеров планеты – используется специализированный пакет с тестами. Один из тестов, flops.f, был скомпилирован и использован для проверки производительности кластера. Результаты теста приведены ниже.

В первой части эксперимента оценивается производительность всего кластера, составляющая 5,874 GFLOPS, и производительность каждого процесса на узлах. Во второй части эксперимента приводятся результаты производительности каждого отдельного узла. Суммарно, производительность отдельных машин составляет 5,969 GFLOPS, что на 1.7% больше. Потери в первую очередь вызваны сетью передачи данных и текущей загруженностью каждого отдельного вычислителя. Вывод из проведенного эксперимента таков, что итоговая потеря производительности кластера, относительно отдельных машин, настолько незначительна, что может быть списана на условия проведения эксперимента. В результате проведенной работы построен вычислительный кластер, пригодный к многопоточному исполнению программ, использующих MPI. Учебное направление кластеров рассматривалось еще в материалах [132,133]. Работа в образовательном учерезжении, в целом, обеспечивается поддержкой библиотеки MPI, существующей в тех или иных реализациях для большинства языков программирования (C, C++, C#, Java, Python, Perl, Ruby), подходящих для курсов «Информатика», «Основы программирования», «Программирование на ЯВУ» и других, связанных с созданием программ для ЭВМ. Так как большинство современных персональных компьютеров оснащается многоядерными процессорами, то обучение многопоточному программированию на многопроцессорных системах позволит многократно увеличить скорость выполнения приложений. Приблизительная производительность кластера на 10 узлах составляет от 5 до 6 Гфлопс. Пиковая производительность кластера MuninnHPC, с дополнительными узлами из компьютерных аудиторий, может составлять около 20-22 Гфлопс, чего достаточно в учебном процессе.

Так же созданный кластер выступает в качестве так называемой «рендер-фермы» за счет использования сетевого физически корректного рендерера трехмерных сцен LuxRender.

Рендер-ферма – кластер для рендеринга (от английского rendering – «визуализация») компьютерной графики с помощью автономной пакетной обработки. Обычно применяется для создания визуальных эффектов в фильмах и телепередачах, создании трехмерных анимационных мультфильмов. Задача по рендерингу сложных сцен достаточно ресурсоемка. Её распараллеливание и выполнение сразу на множестве компьютеров позволяет значительно сокращать время на получение результата. За счет использования сетевого физически корректного рендерера трехмерных сцен LuxRender [134], круг решаемых задач расширяется до поддержки дисциплины «Компьютерная геометрия и графика». Дополнительная установка программного продукта Blender [135] так же позволит использовать вычислительный кластер как рендер-ферму, особенно при наличии в кластере графических ускорителей, которые поддерживаются рендерером Cycles [136] из пакета Blender.

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

Кластеризация тестовой подборки художественных текстов

Тексты обрабатывались программой Stemming, созданной диссертантом. В качестве входных данных программе подается список текстовых фалов для обработки. Первым шагом программа создает очередь из фалов и равномерно распределяет по процессам. Далее каждый процесс выполняет обработку выделенных для него файлов с помощью программы mystem от компании Яндекс или с помощью модуля PyMorphy2. Разница в модулях не критична, однако представляет научный интерес, так как PyMorphy2 на данный момент не обрабатывает слова не на русском языке, а mystem не изменяет словоформу английских слов. После, все файлы-вектора консолидируются на корневом процессе. Корневой процесс (имеет номер 0 в иерархии) создает полную размерность пространства, и передает результаты дочерним процессам, которые, в свою очередь, приводят вектора-тексты к размерности всего пространства и возвращают результат корневому процессу. Результатом обработки становятся 3 файла: список файлов на входе, полный список всех слов в пространстве и матрица координат текстов.

В раделах 4.3 и 4.4 рассматрены процессы кластеризации текстовых подборок с использованием, соответственно модулей mystem и PyMorphy2.

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

На основании [74] выбрано количество кластеров – 3, и сделан первоначальный анализ подборки с использованием случайного распределения меры принадлежности каждого текста к кластеру. Так же сделаны эксперименты для 4,5,6 и 7 кластеров. В Приложении 3 приведены эксперименты для 4,5,6 кластеров для каждой группы экспериментов, а далее рассматриваются эксперименты для 3 и 7 кластеров.

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

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

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

Геометрический смысл этого показателя – чем он меньше, тем более плотным является кластер и наоборот.

На Рисунках 4.2.1 и 4.2.3 показаны результаты экспериментов с тремя кластерами. На Рисунках 4.2.2 – 4.2.4 показаны результаты экспериментов с 7 кластерами. Изменение энтропии каждого отдельного кластера на шагах алгоритма (Рис. 4.2.1, 4.2.2) явно показывает стабилизацию системы в определенном состоянии. Точность вычислений была выставлена на 0.00010 и, при достижении разности матриц менее порогового значения, расчеты останавливались. В первом эксперименте это произошло на 10 шаге алгоритма, как показано на рисунке 4.3.2, во втором на 21-м шаге (Рис. 4.2.2). Особый интерес представляют рисунки 4.2.3 и 4.2.4 в которых показано распределение текстового контента по кластерам.

На основании результатов, приведенных на Рис. 4.2.3 делается вывод о том, что в подборке тексты имеют свой четкий словарный запас, набор терминов и имен для многосерийных произведений. Отметим сходство фантастической и фентезийной литературы Р. Асприна и рассказа «3 закона робототехники» А. Азимова. Четыре других произведения Азимова четко сгруппированы в одном кластере, куда так же входят и произведения А.С.Пушкина, М.Ю.Лермонтова и 3 произведения Братьев Стругацких. Ф. Герберт отделился по причине специфики содержимого его произведенный. Отметим, что, не смотря на это, произведение «Мессия Дюны» не попало в коллекцию с другими произведениями автора. В приложении 3 так же видно, что эти произведения далеко не всегда попадают в один кластер. В качестве объяснения этой ситуации примем во внимание разницу, вносимую переводчиками. Следовательно, можно сделать вывод о том, что, перевод произведения несет в себе авторский стиль, идущий от переводчика. Произведения же одного автора, переведенные разными переводчиками, без общей договоренности о терминах и определениях алгоритмом кластеризации считаются произведениями из разных кластеров.

На Рис. 4.2.4 приведено исследование при количестве кластеров равное 7. В этом эксперименте уже видно разделение текстов Р. Асприна более по тематике, нежели по авторскому стилю. Так, произведения из серии «ШУТТ» попали в один кластер, а из серии «МИФ» в другом кластере. При этом те же произведения А.Азимова, что и в предыдущем эксперименте оказались в одном кластере с А.С. Пушкиным и М.Ю.Лермонтовым. «Дети Дюны» и «Еретики Дюны» обособились в каждый кластер по отдельности, «Мессия Дюны», как и ранее в эксперименте оказался обособлен от других произведений серии. Так же, «Сталкер» и «Туча» объединились в один кластер, но три других произведения оказались сильнее распределены между кластерами. В произведениях Братьев Стругацких, по мнению соискателя, эксперименты могут показывать соавторство, в котором, в зависимости от произведений, стиль одного из авторов более ярко выражен.

Похожие диссертации на Методы и алгоритмы обработки текстового контента с использованием высокопроизводительных вычислительных кластеров