авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 |
-- [ Страница 1 ] --

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

"Московский государственный технический

университет радиотехники,

электроники и автоматики"

МГТУ МИРЭА

Кошкин Дмитрий Евгеньевич

МЕТОДЫ И АЛГОРИТМЫ ОБРАБОТКИ ТЕКСТОВОГО

КОНТЕНТА С ИСПОЛЬЗОВАНИЕМ

ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ КЛАСТЕРОВ Специальность 05.13.15 Вычислительные машины, комплексы и компьютерные сети Диссертация на соискание степени кандидата технических наук Научный руководитель:

доктор технических наук, профессор, Скуратов Алексей Константинович.

Москва Оглавление ГЛОССАРИЙ..................................................................................................................................... ВВЕДЕНИЕ...................................................................................................................................... Глава 1 Анализ существующих методов и алгоритмов разделения текстового контента и извлечения знаний. Типовые архитектуры вычислительных комплексов....................... 1.1 Теории, используемые при анализе текстового контента................................................. 1.2 Методы классификации и алгоритмы кластерного анализа текстового контента......... 1.3 Оценка алгоритмов кластеризации по критериям вычислительной сложности............. 1.4 Аппаратные и программные платформы развертывания вычислительных кластеров.. 1.4.1 Технологии сетевого объединения вычислительных узлов............................. 1.4.2 Программные платформы развертывания вычислительных кластеров......... 1.4.3 Гибридные кластеры с графическими процессорами (GPU)........................... 1.5 Заключение. Постановка задачи.......................................................................................... Глава 2 Развитие существующих методов и алгоритмов специальной обработки текстового контента. Придание вычислительным кластерам свойств расширяемости, масштабируемости и интероперабельности........................................................................ 2.1 Развитие многопоточности для алгоритмов кластеризации на примере алгоритма Нечетких C-средних............................................................................................................... 2.1.1 Метод использования энтропийной меры оценки алгоритма Нечетких C средних для контроля процесса кластеризации и повышения ее качества...................... 2.2 Метод параллельной обработки минимальных синтаксических структур с использованием базовых характеристик объектно-ориентированных языков высокого уровня.

.................................................................................................................................. 2.3 Разработка вычислительного кластера со свойствами расширяемости, масштабируемости и интероперабельности........................................................................ 2.3.1 Допущения и ограничения в выборе аппаратной платформы для реализации вычислительного кластера..................................................................................................... 2.3.2 Допущения и ограничения программной платформы для реализации вычислительного кластера..................................................................................................... 2.3.3 Методика использования особенностей стандартов для повышения производительности сетевых соединений вычислительных кластеров на основе протокола Ethernet.................................................................................................................. 2.4 Заключение............................................................................................................................ Глава 3 Развертывание вычислительного кластера на примере кластера в МГТУ МИРЭА.

Практическая реализация методов и алгоритмов многопоточной обработки текстового контента на высокопроизводительных вычислительных кластерах................................. 3.1 Программная платформа для развертывания кластера MuninnHPC на основе доработанной кластерной платформы PelicanHPC............................................................. 3.2 Реализация алгоритма кластеризации с использованием многопоточности и графических процессоров (GPU Fuzzy C-Means) на языке Python.................................... 3.2.1 Описание дополнительных модулей и способов их использования.

Экспериментальная верификация......................................................................................... 3.3 Апробация созданных кластеров в условиях конкуренции в проекте Folding@HOME. Глава 4 Практические исследования многопоточной кластеризации текстового контента на естественном языке.............................................................................................................. 4.1 Сравнение вычислительной скорости центрального и графического процессоров..... 4.2 Кластеризация тестовой подборки художественных текстов......................................... 4.2.1 Результаты экспериментов предобработки текстов с модулем mystem....... 4.2.2 Предобработка текстов с модулем PyMorphy2............................................... Заключение..................................................................................................................................... Библиография................................................................................................................................. Приложения.................................................................................................................................... Приложение 1. Результаты экспериментов на синтетической подборке текстов с 4, 5 и кластерами............................................................................................................................. Приложение 2. Свидетельство о регистрации программы для ЭВМ 2012660210.................. Приложение 3. Свидетельство о регистрации программы для ЭВМ 2013660292.................. Приложение 4. Акты внедрения кластеров MuninnHPC и HuginnHPC.................................... ГЛОССАРИЙ АРХИТЕКТУРА ИНФОРМАЦИОННОЙ СИСТЕМЫ – концепция, определяющая модель, структуру, выполняемые функции и взаимосвязь компонентов информационной системы. [1].

БАЗА ЗНАНИЙ – организованная совокупность знаний, представленная в форме, которая допускает автоматическое или автоматизированное использование этих знаний на основе реализации возможностей средств информационных технологий.[2] БРАУЗЕР (англ. web browser) – программное обеспечение для поиска и просмотра веб-сайтов, для запроса веб-страниц (преимущественно из Интернет). Служит для их обработки, вывода и перехода от одной страницы к другой [3].

ВАЛИДНОСТЬ (англ. validity) – мера соответствия того, насколько методика и результаты исследования соответствуют поставленным задачам [3].

ВЕБ-ОБОЗРЕВАТЕЛЬ см. браузер.

ВЕБ-ПОРТАЛ см. портал.

ВЕБ-САЙТ (англ. website, от web – паутина и site – «место») – одна или совокупность веб-страниц, доступных в Интернет через протоколы HTTP/HTTPS. Страницы веб-сайта объединены общим корневым адресом, а также обычно темой, логической структурой, оформлением и/или авторством [3].

ВЕБ-СЕРВЕР – сервер, принимающий HTTP-запросы от клиентов, обычно браузеров, и выдающий им HTTP-ответы, обычно вместе с HTML-страницей, изображением, файлом, медиа-потоком или другими данными. Веб-серверы – основа Всемирной паутины. Веб сервером называют как программное обеспечение, выполняющее функции веб-сервера, так и компьютер, на котором это программное обеспечение работает. Клиенты получают доступ к веб-серверу по URL адресу нужной им веб-страницы или другого ресурса [4].

ВТОРИЧНЫЕ ИНФОРМАЦИОННЫЕ РЕСУРСЫ – описания (например уровень образования, тип материала, предмет, аннотация или ключевые слова) и адреса ресурсов, не расположенных на текущем портале, а доступных через Интернет на других порталах, сайтах по гиперссылкам [4].

ВЫЧИСЛИТЕЛЬНЫЙ КЛАСТЕР – группа компьютеров, объединенных каналами связи и представляющая с точки зрения пользователя единый аппаратный ресурс.

ГАРМОНИЗАЦИЯ КОНТЕНТА – систематизация и унификация в результате изменения состава, свойств и признаков составляющих контента [4,5].

ДАННЫЕ – качественные или количественные переменные, принадлежащие к набору элементов. Необработанные данные не были подвергнуты обработке или другим манипуляциям. В качестве абстрактного понятия данные лежат на самом нижнем уровне абстракции из которых далее проистекают информация и знания.

ДОКУМЕНТАЛЬНАЯ ИНФОРМАЦИОННО-ПОИСКОВАЯ СИСТЕМА – информационно-поисковая система, предназначенная для нахождения документов, содержащих затребованную информацию. Поисковый массив документальной ИПС состоит из поисковых образов документов или из самих документов [1].

ЗНАНИЯ – совокупность информации и правил вывода о мире, свойствах объектов, закономерностях процессов и явлений, а также правилах использования их для принятия решений. Главное отличие знаний от данных состоит в их структурности и активности.

ИЗВЛЕЧЕНИЕ ИНФОРМАЦИИ (Information extraction) – это задача автоматического извлечения (построения) структурированных данных из неструктурированных или слабоструктурированных машиночитаемых документов.

ИНДЕКСИРОВАНИЕ – процедура, завершающаяся присвоением документу соответствующего поискового образа [6].

ИНТЕЛЛЕКТУАЛЬНЫЙ АНАЛИЗ ДАННЫХ (Data Mining) – собирательное название, используемое для обозначения совокупности методов обнаружения в данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности.

Термин введён Григорием Пятецким-Шапиро в 1989 году.[3] ИНТЕРНЕТ – глобальная информационная сеть, части которой логически взаимосвязаны друг с другом посредством единого адресного пространства, основанного на протоколе TCP/IP. Интернет состоит из множества взаимосвязанных компьютерных сетей и обеспечивает удаленный доступ к компьютерам, электронной почте, доскам объявлений, базам данных и дискуссионным группам [1].

ИНТЕРФЕЙС ПРОГРАММИРОВАНИЯ ПРИЛОЖЕНИЙ (англ. Application Programming Interface, API) – набор методов (функций), который программист может использовать для доступа к функциональности программного компонента (программы, модуля, библиотеки). API является важной абстракцией, описывающей функциональность «в чистом виде» [3].

ИНТРАНЕТ – распределенная корпоративная вычислительная сеть, предназначенная для обеспечения теледоступа сотрудников к корпоративным информационным ресурсам и использующая программные продукты и технологии Интернет. Интранет позволяет контролировать доступ к корпоративной информации [1].

ИНФОРМАЦИЯ – сведения о чём-либо, независимо от формы их представления.

ИНФОРМАЦИОННЫЙ ОБРАЗОВАТЕЛЬНЫЙ ПОРТАЛ – система тематических профессиональных сайтов, выполненных по сходному замыслу и работающих в единых стандартах обмена информацией. Современное информационно-технологическое средство выхода участников непрерывного образования в единую информационно-образовательную среду в целях информационно-технологической и управленческой поддержки этим средством образовательных технологий. Цель портала – выработка новых стандартов организации и информационного обеспечения образовательного процесса на всех уровнях образования [6].

ИНФОРМАЦИОННЫЙ ПОИСК – некоторая последовательность операций, выполняемых с целью нахождения документов (статей, научно-технических отчетов, описаний к авторским свидетельствам и патентам, книг и т.д.), содержащих определенную информацию (с последующей выдачей самих документов или их копий), или с целью выдачи фактических данных, представляющих собой ответы на заданные вопросы [7].

ИНФОРМАЦИОННО-ПОИСКОВАЯ СИСТЕМА (сокр. ИПС) – некоторая совокупность или комплекс связанных друг с другом отдельных частей, предназначенные для выявления в каком-либо множестве элементов информации (документов, сведений и т.д.), которые отвечают на информационный запрос, предъявленный системе [7].

ИНФОРМАЦИОННО-ПОИСКОВЫЙ ЯЗЫК – определенная семантическая система, предназначенная для выражения основного смыслового содержания документов и информационных запросов с целью отыскания в массиве таких документов, которые содержат требуемую информацию. Правила перевода с естественного языка на информационно-поисковый язык (и наоборот) обычно задаются в виде двуязычного словаря и соответствующего алгоритма [6].

ИНФОСЕТЬ – однородная однослойная сеть объектов, морфологически объединенных отношениями, вытекающими из структуры синтаксической единицы (предложения) КОНТЕНТ (англ. content – содержание) – любое информационно значимое (содержательное) наполнение информационного ресурса (например, веб-сайта) – тексты, графика, мультимедиа – вся информация, которую пользователь может загрузить на диск компьютера с соблюдением соответствующих законностей, как правило, только для личного пользования [3].

КЛАСТЕР – 1. в теории кластерного анализа – группа объектов объединенных по какому-либо признаку.

2. см. Вычислительный кластер.

КЛАСТЕРИЗАЦИЯ – см. кластерный анализ КЛАСТЕРНЫЙ АНАЛИЗ – многомерная статистическая процедура, выполняющая сбор данных, содержащих информацию о выборке объектов, и затем упорядочивающая объекты в сравнительно однородные группы. Задача кластеризации относится к статистической обработке, а также к широкому классу задач обучения без учителя.

ЛЕММАТИЗАЦИЯ – процесс приведения словоформы к лемме – её нормальной (словарной) форме. В русском языке нормальными формами считаются следующие морфологические формы: для существительных — именительный падеж, единственное число;

для прилагательных — именительный падеж, единственное число, мужской род;

глаголов, причастий, деепричастий — глагол в инфинитиве. [3] МЕТАДАННЫЕ см. метаописание.

МЕТАОПИСАНИЕ – описание ресурса, включающее характеристики, которые не могут быть извлечены из его содержимого автоматически. Значительно облегчает поиск и позволяет учесть разнообразные требования и условия, выдвигаемые пользователем [8].

МЕТОД – систематизированная совокупность шагов, действий, которые необходимо предпринять, чтобы решить определённую задачу или достичь определённой цели МЕТОДИКА – определенная, усвоенная процедура или набор процедур для достижения некоторой специфической цели. Обычно этот термин употребляется с коннотацией, что эти процедуры требуют определенной квалификации, и владение ими отражает некоторый уровень опытности. [9] МЕТОДОЛОГИЯ – учение о структуре, логической организации, методах и средствах деятельности;

учение о принципах построения, формах и способах научного познания. [10] МИНИМАЛЬНАЯ СИНТАКСИЧЕСКАЯ СТРУКТУРА (способная нести в себе знания) - простое предложение текстового контента, состоящих из подлежащего в форме существительного, сказуемого в форме глагола (в сложном предложении добавляется прямое дополнение) МНОГОПОТОЧНОСТЬ - независимая обработка частей данных, выполняемых группой инициированных программой процессов.

НОРМИРОВАНИЕ КОНТЕНТА – принятие мер по снижению дисперсии и математического ожидания размеров файла в пределах каждого массива контента [4].

ОНТОЛОГИЯ – это попытка всеобъемлющей и детальной формализации некоторой области знаний с помощью концептуальной схемы. Обычно такая схема состоит из структуры данных, содержащей все релевантные классы объектов, их связи и правила (теоремы, ограничения), принятые в этой области.

ОНТОЛОГИЧЕСКОЕ СОГЛАШЕНИЕ – соглашений о связях между смыслами различных терминов [11] ПЕРТИНЕНТНОСТЬ (англ. pertinence, pertinency) – степень соответствия содержания документов информационной потребности пользователя [6].

ПЕРВИЧНЫЕ ИНФОРМАЦИОННЫЕ РЕСУРСЫ – ресурсы, располагающиеся непосредственно на самом портале [4].

ПОИСКОВЫЙ ОБРАЗ ДОКУМЕНТА – выраженное в терминах информационно поискового языка основное смысловое содержание этого документа, которое поставлено в однозначное соответствие данному документу и предназначено для его отыскания в массиве других документов, характеристика, кратко выражающая основное смысловое содержание документа [6].

ПОИСКОВЫЙ ОБРАЗ ЗАПРОСА – поисковый образ, выражающий смысловое содержание информационного запроса [12].

ПОИСКОВОЕ ПРЕДПИСАНИЕ – текст, включающий поисковый образ запроса и указания о логических операциях, подлежащих выполнению в процессе информационного поиска. Поисковые предписания формируются при поступлении запросов [12].

ПОЛНОТА (англ. recall) – это одна из основных характеристик поисковой системы, которая представляет собой отношение количества найденных поисковой системой документов к общему числу документов, удовлетворяющих данному запросу [12].

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

ПРОПУСКНАЯ СПОСОБНОСТЬ КАНАЛА – или ширина полосы пропускания.

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

РЕЛЕВАНТНОСТЬ (англ. relevance, relevancy) – степень соответствия содержания документа информационному запросу в том виде как он сформулирован. Субъективное понятие, поскольку результаты поиска, полезные для одного пользователя, могут быть бесполезными для другого [3,6].

РЕПОЗИТАРИЙ – место хранения метаданных или сведений о данных [14].

САЙТ см. веб-сайт.

CЕМАНТИЧЕСКАЯ СЕТЬ – информационная модель предметной области, имеющая вид ориентированного графа, вершины которого соответствуют объектам предметной области, а дуги (рёбра) задают отношения между ними. Объектами могут быть понятия, события, свойства, процессы. Таким образом, семантическая сеть является одним из способов представления знаний.

СЕМАНТИЧЕСКИЕ ОТНОШЕНИЯ – при представлении семантической сети в виде графа – нагруженные ребра графа, выражающего семантическую сеть.

СЕРВЕР КЛАСТЕРА – вычислительная машина, являющаяся главным узлом кластера, под управлением которого находятся другие узлы. Является единой точкой входа для управления и администрирования кластера. При использовании системы мониторинга агрегирует поступающую с узлов статистическую информацию. В зависимости от конфигурации и настроек может выполнять широкий диапазон функций и решать обширный круг задач.

СИСТЕМА УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ (сокр. СУБД) – специализированная программа (чаще комплекс программ), предназначенная для манипулирования базами данных [14].

СПЕЦИАЛЬНАЯ ОБРАБОТКА ТЕКСТОВОГО КОНТЕНТА – статистическая, морфологическая обработка, в том числе и с целью передачи полученного массива данных алгоритму кластеризации для дальнейшего анализа.

СТЕММИНГ (Стемматизация) – это процесс нахождения основы слова для заданного исходного слова. Основа слова необязательно совпадает с морфологическим корнем слова.[3] ТАКСОН (лат. taxon, «порядок, устройство, организация») – группа в классификации, состоящая из дискретных объектов, объединяемых на основании общих свойств и признаков.

Классификационные системы, использующие понятие «таксона», обычно носят иерархический характер;

применяются они в языкознании, библиографии и других науках, но прежде всего в биологии. [3] ТАКСОНОМИЯ (греч. – строй, порядок и – закон) – учение о принципах и практике классификации и систематизации. [3] [15].

ТОЧНОСТЬ (англ. precision) – определяется по соответствию найденных документов запросу пользователя [12] УЗЕЛ КЛАСТЕРА – набор технического обеспечения (обычно - процессор, оперативная память, материнская плата, иногда жесткий диск), участвующий в образовании вычислительного кластера и передающий свои вычислительные ресурсы под управление сервера кластера.

ФИТНЕС-ФУНКЦИЯ – в теории генетических алгоритмов – функция оценки приспособленности особи из популяции. [16] CUDA (англ. Compute Unified Device Architecture) – программно-аппаратная архитектура, позволяющая производить вычисления с использованием графических процессоров NVIDIA, поддерживающих технологию GPGPU (произвольных вычислений на видеокартах) FLOPS (FLoating-point Operations Per Second – операции с плавающей точкой в секунду) – внесистемная единица, используемая для измерения производительности компьютеров, показывающая, сколько операций с плавающей запятой в секунду выполняет данная вычислительная система.[3] MPI (Message Passing Interface, интерфейс передачи сообщений) – программный интерфейс (API) для передачи информации, который позволяет обмениваться сообщениями между процессами, выполняющими одну задачу. Разработан Уильямом Гроуппом, Эвином Ласком и другими. [3] HPC – HIGH PERFORMANCE CLUSTER – см. Вычислительный кластер.

OWL (Web Ontology Language – язык Веб-онтологий) – язык описания онтологий для семантической паутины. Язык OWL позволяет описывать классы и отношения между ними, присущие веб-документам и приложениям. OWL основан на более ранних языках OIL и DAML+OIL и в настоящее время является рекомендованным консорциумом Всемирной паутины.

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

HTML (англ. Hypertext Markup Language – язык разметки гипертекста) – стандартный язык разметки документов во Всемирной паутине. Все веб-страницы создаются при помощи языка HTML (или XHTML). Язык HTML интерпретируется браузером и отображается в виде документа, удобном для человека [3].

XML (англ. eXtensible Markup Language – расширяемый язык разметки) – рекомендованный Консорциумом Всемирной паутины язык разметки, представляющий собой свод общих синтаксических правил. Текстовый формат, предназначенный для хранения структурированных данных для обмена информацией между программами, а также для создания на его основе более специализированных языков разметки (например, XHTML), иногда называемых словарями [3].

ВВЕДЕНИЕ.

В настоящее время зародилось и развивается новое направление в области обработки данных – Большие данные (Big Data) [3, 17,18,19]. Это направление характеризуется тем, что работает с данными, подходящими под определение из трех V – Volume, Variety и Velocity.

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

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

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

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

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

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

Следующим шагом по обработке полученных структурированных групп текстов становится обработка групп. Для семантического анализа, текст не просто бессмысленный набором синтаксических единиц, подчиняется законам языка, на котором написан, и может быть формализован [27]. Для такой формализации потребуется изучить особенности построения слов и синтаксических единиц исследуемого языка и используемого стиля изложения материала, например, научно-популярного или просторечного. Английский язык является наиболее распространенным языком мира (112 стран, 56.6% интернет-контента [3]).

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

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

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

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

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

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

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

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

Провести эксперименты для верификации выдвигаемых в диссертации положений;

Внедрить научные положения и выводы диссертации в учебный процесс МГТУ МИРЭА.

Перечисленные задачи будут дополнены и уточнены по результатам аналитического обзора Главы 1.

Структура диссертации состоит из Введения, четырех глав основного текста, Заключения, Библиографии (147 источников) и четырех Приложений. Текст диссертации предваряет развернутый глоссарий терминов, относящийся к данной предметной области.

Диссертация содержит 145 страницы, включая 55 рисунков и 14 таблиц.

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

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

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

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

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

В первую очередь стоит принять во внимание иерархию и определения, представленные ниже на Рисунке 1.1. ДИЗМ (DIKW, англ. data, information, knowledge, wisdom) – данные, информация, знания, мудрость – информационная иерархия, где каждый уровень добавляет определённые свойства к предыдущему уровню.

В основании находится уровень данных. (В контексте диссертации под данными понимается так же текстовый контент, тексты из сети интернет.) Информация добавляет контекст. (Под информацией уже понимаются объекты, описываемые текстом и окруженные контекстом, например, связями с другими объектами.) Знание добавляет механизм использования («как»).

Мудрость добавляет условия использования («когда») (На уровне мудрости получается, что связи и образы действия извлекаются из самих себя и появляются не просто связи, а причинно-следственные связи.) [3] Мудрость Знания Информация Данные Рис. 1.1 Пирамида ДИЗМ Далее будут рассматриваться теории в порядке их возникновения или публикаций с целью определить общую пригодность этих теорий к быстрой обработке текстового контента в задаче извлечения информации и, возможно, знаний.

В статье Л. В. Щербы [33] рассматривается вопрос сравнения существующих языков с точки зрения категорий «части речи». Рассматривая русский язык, Л.В.Щерба говорит о том, что части речи, как категории имеют зависимость от контекста и от логического ударения в устной речи «Во фразе Когда вы приехали? ударение на когда определяет его как наречие, а отсутствие ударения во фразе Когда вы приехали, было еще светло определяет его как союз.»

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

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

В работах Н.Хомского, которые касаются «генеративной грамматики» [34,35,36] уже встает вопрос о контексте, предложениях, синтаксических единицах того или иного языка.

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

«Понятие «грамматически правильный» не может отождествляться с понятиями «осмысленный», «значимый» в каком бы то ни было семантическом смысле. Данные ниже предложения (1) и (2) равно бессмысленны, но любой носитель английского языка назовёт грамматически правильным лишь первое.

(1) Colorless green ideas sleep furiously.

«Бесцветные зелёные мысли спят яростно».

(2) Furiously sleep ideas green colorless»

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

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

Важнейшей реализацией категориальных грамматик является «грамматика Монтегю».

Ричард Монтегю стремился создать «универсальную грамматику» не в смысле лингвистики, т. е. не грамматику, справедливую для всех реальных и потенциальных человеческих языков, — а теорию синтаксиса и семантики, в первую очередь, всех известных искусственных языков логики, и только во вторую — естественных языков.

Центральная идея Монтегю: естественный язык в существенных своих свойствах не отличается от формализованных языков. Монтегю разработал своеобразный алгебраический способ задания соответствий между формой и содержанием в языке, тем самым расширив сферу и методы логики и дав инструменты для формулирования аксиоматической теории для естественного языка, позволяющей понять, какую именно работу следует проделать, чтобы описать семантические свойства той или иной конструкции. Сравнивая работы Монтегю и Хомского можно сказать, что для Н.Хомского грамматика — область психологии и устанавливает, как человек осваивает язык, продуцирует и понимает речь с опорой на универсальные врожденные способности, настраиваемые на конкретный язык. Хомский пытается понять, что же делает язык человеческим языком, отличает от иных систем символов. Для Монтегю грамматика — область логики, например, объясняющей грамматические свойства кванторов через свойства логической системы. Хомский как лингвист стремится объяснить свойства психики через свойства грамматики. Монтегю считал, что математическая логика должна объяснить свойства естественного языка.

Грамматика Монтегю – общее направление, в основе которого лежат – обобщение логики исчисления предикатов в рамках обобщенной теории типов в приложении к семантическому описанию естественного языка. [37] Переходя к семантике языка и возможности автоматизированной обработки текстов на естественном языке рассмотрим модель «Смысл Текст» и ее разработчиков И. А.

Мельчука, А. К. Жолковского и Ю.Д. Апресяна. Теория «Смысл Текст» представляет собой описание естественного языка, понимаемого как устройство («система правил»), обеспечивающее человеку переход от смысла к тексту («говорение», или построение текста) и от текста к смыслу («понимание», или интерпретация текста);

отсюда символ двунаправленной стрелки в названии теории. При этом приоритет в исследовании языка отдаётся переходу от смысла к тексту: считается, что описание процесса интерпретации текста может быть получено на основе описания процесса построения текста. Теория постулирует многоуровневую модель языка, то есть такую, в которой построение текста на основе заданного смысла происходит не непосредственно, а с помощью серии переходов от одного уровня представления к другому. Помимо двух «крайних» уровней — фонологического (уровня текста) и семантического (уровня смысла), выделяются поверхностно-морфологический, глубинно-морфологический, поверхностно-синтаксический и глубинно-синтаксический уровни. Каждый уровень характеризуется набором собственных единиц и правил представления, а также набором правил перехода от данного уровня представления к соседним. На каждом уровне мы имеем дело, таким образом, с особыми представлениями текста — например, глубинно-морфологическим, поверхностно синтаксическим и т. п.

Семантическое представление является неупорядоченным графом («сетью»), синтаксические представления являются графическим деревом («деревом зависимостей»), морфологическое и фонологическое представления линейны.

Данная идеология в целом достаточно типична для многих (так наз.

стратификационных) теорий языка, развивавшихся в середине XX века;

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

интерпретация же приписывается этим текстам впоследствии. Существенно также, что англо-американские синтаксические теории, возникшие на материале английского языка с жёстким порядком слов, как правило, использовали синтаксис составляющих, а не синтаксис зависимостей. [38-43] После рассмотрения теории «смыслтекст» следует отметить теорию коммуникативной грамматики. [44,45] В синтетическом, флективном языке, каким является русский, особое значение имеют отношения между синтаксисом и морфологией. И если в описательной грамматике исследователей интересуют отношения между компонентом предложения и словоформой, то в грамматике объяснительной устанавливаются отношения между типовым значением предложения и категориальным значением частей речи, участвующих в организации того или иного типа предложений. Это отношение оказывается основным критерием классификации моделей в концепции «Коммуникативной грамматики русского языка» [46] Коммуникативная грамматика в основу своей объяснительной теории кладет идею триединой сущности языковой единицы, и тем самым соединяет системное и текстовое исследование языковой единицы.

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

Такими грамматическими инструментами стали (1) модель субъектной перспективы высказывания, (2) понятие коммуникативного регистра речи и (3) таксис как техника межпредикативных отношений в тексте. Если конкретное высказывание исследовать с использованием каждого из трех инструментов, то станет очевидным, что отношение высказывания к действительности интерпретируется системой коммуникативных регистров, отношение высказывания к сфере человека мыслящего и говорящего представлено субъектной перспективой, а отношение высказывания к другому высказыванию объясняется теорией таксиса.

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

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

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

Особенность словообразования и фразопостроения.

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

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

синтетическом и аналитическом.

А.А. Реформатский [47] представляет классификацию А.Шлейхера в следующем виде:

(R – корень слова, r – служебное слово, a – флеския (суффиксы, префиксы, постификсы, окончания и т.д.)) Изолирующие языки 1) R – чистый корень ( например, китайский язык);

2) R + r – корень плюс служебное слово (например, бирманский язык).

Агглютинирующие языки Синтетический тип:

1) Ra – суффигированный тип (например, тюркские и финские языки );

2) aR – префигированный тип (например, языки банту);

3) R / a – инфицированный тип (например, бацбийский язык).

Аналитический тип:

4) Ra (aR) + r – аффигированный корень плюс служебное слово (например, тибетский язык).

Флективные языки Синтетический тип:

1) Rа – чистая внутренняя флексия (например, семитские языки);

2) aRа (Raа) – внутренняя и внешняя флексия (например, индоевропейские, в особенности древние языки).

Аналитический тип:

3) aRа (Raа) + r – флектированный и аффигированный корень плюс служебное слово (например, романские языки, английский язык).

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

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

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

Так же русский в целом можно отнести к языкам с порядком слов в предложениях – SVO – Subject Verb Object, «Подлежащее – сказуемое – прямое дополнение». Один из наиболее популярных (наряду с SOV) типов – около 75 % языков принадлежат к этим двум группам. SVO является самым распространенным порядком слов в креольских языках, что может указывать на его «естественность» в человеческой психологии. Однако порядок слов может меняться на любой в зависимости от смысла, который хотят передать фразой. Такая особенность в русском языке выражена тем, что слова в предложениях можно расставлять практически в любом порядке и все равно будет понятна основная мысль сказанного.

Принимая во внимание пирамиду ДИЗМ и существующие методы извлечения информации и знаний из текстового контента, то наиболее быстрым может стать способ извлечении и представления информации на основе морфологического анализа. Метод, в общем случае, будет близок к идеям, изложенным Л.В. Щербой в статье «О частях речи в русском языке» и предполагает извлечение информации из текстов.

С точки зрения работ в области извлечения информации и знаний можно отметить специалистов из Института системного анализа РАН, которые разработали и развивают систему EXACTUS [49]. Особенностью системы является Интеллектуальный метапоиск в Интернете, интеллектуальный поиск по Википедии и поиск по коллекциям научных текстов.

1.2 Методы классификации и алгоритмы кластерного анализа текстового контента K-средних (k-means) Алгоритм k-means является примером четкой кластеризации, в основе которого лежит итеративный процесс стабилизации центроидов кластеров. Основной характеристикой кластера является его ценроид и вся работа алгоритма направлена на стабилизацию или, в лучшем случае, на полное прекращение изменения центроида кластера. Алгоритм состоит из следующих шагов:

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


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

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

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

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

Если это перемещение существенное, то заметно изменится множество точек, попавших внутрь гиперсферы, а следовательно, и их среднее значение координат. Вновь перемещаем центр гиперсферы в это новое среднее значение и т.д. до тех пор, пока гиперсфера не остановится или зациклится. Тогда все точки, попавшие внутрь этой гиперсферы, исключаются из рассмотрения и процесс повторяется на оставшихся точках. Это продолжается до тех пор, пока не будут исчерпаны все точки. [50] KRAB Примером использования «человеческих критериев» при решении задач таксономии служит алгоритм KRAB. Эти критерии отработаны на двухмерном признаковом пространстве в ходе таксономии, осуществляемой человеком, и применены в алгоритме, функционирующем с объектами произвольной размерности.

Факторы, выявленные при "человеческой" таксономии, можно сформулировать следующим образом:

– внутри таксонов объекты должны быть как можно ближе друг к другу (обобщённый показатель );

– таксоны должны как можно дальше отстоять друг от друга (обобщённый показатель d );

– в таксонах количество объектов должно быть по возможности одинаковым, то есть их различие в разных таксонах нужно минимизировать (обобщённый показатель h );

– внутри таксонов не должно быть больших скачков плотности точек, то есть количества точек на единицу объёма (обобщённый показатель ).

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

Все точки обучающей выборки объединяются в граф, в котором они являются вершинами. Этот граф должен иметь минимальную суммарную длину рёбер, соединяющих все вершины, и не содержать петель (рис. 1.2). [50] Рисунок 1.2 Иллюстрация к алгоритму KRAB[50].

а – точки-объекты в двумерной плоскости;

б – КНП-граф после определения расстояния между точками.

Метод опорных векторов (SVM ) (англ. SVM, support vector machine) — набор схожих алгоритмов вида «обучение с учителем», использующихся для задач классификации и регрессионного анализа. Этот метод принадлежит к семейству линейных классификаторов. Он может также рассматриваться как специальный случай регуляризации по А. Н. Тихонову. Особым свойством метода опорных векторов является непрерывное уменьшение эмпирической ошибки классификации и увеличение зазора. Поэтому этот метод также известен как метод классификатора с максимальным зазором.

Основная идея метода опорных векторов — перевод исходных векторов в пространство более высокой размерности и поиск разделяющей гиперплоскости с максимальным зазором в этом пространстве. Две параллельных гиперплоскости строятся по обеим сторонам гиперплоскости, разделяющей наши классы. Разделяющей гиперплоскостью будет гиперплоскость, максимизирующая расстояние до двух параллельных гиперплоскостей. Алгоритм работает в предположении, что чем больше разница или расстояние между этими параллельными гиперплоскостями, тем меньше будет средняя ошибка классификатора. [3] EM-алгоритм Одним из широко известных в аналитическом сообществе алгоритмов кластеризации, позволяющих эффективно работать с большими объемами данных, является EM-алгоритм.

Его название происходит от слов "expectation-maximization", что переводится как "ожидание максимизация". Это связано с тем, что каждая итерация содержит два шага – вычисление математических ожиданий (expectation) и максимизацию (maximisation). Алгоритм основан на методике итеративного вычисления оценок максимального правдоподобия, предложенной в 1977 г. [51].

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

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

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

Алгоритм CLIQUE [52], адаптированный под кластеризацию данных высокой размерности, является одним из классических сетевых алгоритмов. Метод основан на том предположении, что если в многомерном пространстве данных распределение объектов не равномерно – встречаются регионы плотности и разрежения, то проекция региона плотности в подпространство с меньшей размерностью будет частью региона плотности в этом подпространстве. Алгоритм CLIQUE производит кластеризацию многомерного пространства данных следующим образом: пространство данных разбивается на не пересекающиеся ячейки фиксированного размера, среди них идентифицируются плотные ячейки – такие, плотность объектов данных в которых превышает заданное пороговое значение. Далее из найденных ячеек формируется пространство, в котором могут существовать плотные ячейки большей размерности. Процесс начинается с одномерных пространств (описанная процедура выполняется для каждого измерения) с последующим переходом к подпространствам более высокой размерности.

CLOPE Назначение алгоритма - кластеризация огромных наборов категорийных данных. Из достоинств - высокие масштабируемость и скорость работы, а так же качество кластеризации, что достигается использованием глобального критерия оптимизации на основе максимизации градиента высоты гистограммы кластера. Во время работы алгоритм хранит в RAM небольшое количество информации по каждому кластеру и требует минимальное число сканирований набора данных. CLOPE автоматически подбирает количество кластеров, причем это регулируется одним единственным параметром – коэффициентом отталкивания.[53] pMAFIA [54] Алгоритм pMAFlA (от Merging of Adaptive Finite Intervals, объединение адаптивных конечных интервалов) – масштабируемый параллельный алгоритм кластеризации с использованием адаптивного подпространственного вычисления конечных интервалов в каждом измерении, которые объединяются для изучения кластеров в более высоких измерениях. В алгоритме используются сетки и плотностный подход для обнаружения кластера в подпространствах. В плотностном подходе кластеры рассматриваются как более высокая плотность регионах, чем в их окружении. Качество результатов и вычислительные требования сильно зависят от количества элементов в каждом измерении. Большие размеры ячеек приводят к плохому качеству кластеризации, в то время как мелкие ячейки будут требовать огромный объем вычислений. В то же время, автоматическое определение размеров на основе данных распределения значительно помогает в поиске правильных кластеров и существенно уменьшает время вычислений. Тем не менее, алгоритмам кластеризации необходимо изучить все возможные подпространства для встраиваемых кластеров, и результате временная сложность алгоритма экспоненциально растет от размера данных.

Нечетких C-средних (Fuzzy C-means) Алгоритм нечетких c-средних (Fuzzy Classifier Means, Fuzzy C-Means, FCM) – алгоритм нечеткой кластеризации. Целью алгоритма является автоматическая классификация множества объектов, которые задаются векторами признаков в пространстве.

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

Достоинства: нечеткость при определении объекта в кластер позволяет определять в кластеры объекты, которые находятся на границе.[55,56] Генетические алгоритмы Исследования [57-61] показали эффективность генетических алгоритмов в решении инженерных, экономических, экологических и других задач. Главной идеей, лежащей в основе построения генетического алгоритма, является использование идей природного отбора, селекции и мутаций. Реализация генетического алгоритма предполагает задание функции приспособленности, или фитнес-функции (fitness function). Эта функция получает на вход двоичную хромосому и возвращает число, показывающее, насколько хороша эта хромосома [16].


Канонический вариант алгоритма содержит следующие этапы:

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

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

выборе способа нормирования исходных данных;

выборе варианта кроссовера, мутации и инверсии, а также соответствующих вероятностей.

3. Для каждого элемента i, i 1,..., n вычисляем значения фитнес-функции f i F ( i ) 4. С вероятностями Pik пропорциональными значением fi, выбрать две особи и осуществить кроссовер, вследствие выполнения которого получим две новых особи.

5. С вероятностью 0.5 выбираем одну из полученных особей и с вероятностью Pm осуществляем мутацию.

6. Полученную особь помещаем в новую популяцию n.

7. Повторяем шаги 3-6 (k/2) раз.

8. Переписываем элементы n в популяцию, удаляя старые особи.

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

сходимость элементов популяции к одному элементу;

максимальное абсолютное отклонение между элементами популяции n будет меньше некоторого положительного числа ;

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

Алгоритм Rocckhio Алгоритм Роккио (Rocchio algorithm) [3,62] – классический алгоритм для реализации метода обратной связи. Сам механизм обратной связи по релевантности был реализован в системе Дж. Солтона SMART около 1970 года и стал известен благодаря этой системе [3].

Обратная связь по релевантности может улучшить как полноту, так и точность результата.

Однако на практике было показано, что она является наиболее полезной для повышения полноты в тех ситуациях, когда полнота критична. Частично это объясняется тем, что метод Роккио расширяет запрос (т, е, добавляются новые термины), а частично — контекстом использования. Когда пользователи хотят достичь высокой полноты, они готовы потратить время на просмотр результатов и повторно выполнить поиск, Положительная обратная связь также оказывается более ценной, чем отрицательная, Несмотря на то что многочисленные экспериментальные результаты сравнения разных вариантов обратной связи по релевантности не позволяют сделать окончательные выводы, некоторые исследователи считают, что именно вариант, получивший название Ide dec-hi, является наиболее эффективным или по крайней мере наиболее непротиворечивым.

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

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

Таким образом сеть распознает не только характеристики исходных данных, но и "характеристики характеристик", сформированные скрытым слоем.

Минимальное покрывающее дерево MST Алгоритм минимального покрывающего дерева предполагает сначала построение на графе минимального покрывающего дерева, с последовательным удалением ребер с наибольшим весом. На рисунке 1.3 изображено минимальное покрывающее дерево, полученное для девяти объектов.

Рисунок 1.3 Пример минимального покрывающего дерева.

Путём удаления связи c максимальным расстоянием равным 6 единицам, помеченной EF, получаем два кластера: {A, B, C, D, E} и {F, G, H, I}. Первый кластер в дальнейшем может быть разделён ещё на два кластера путём удаления ребра CD, которое имеет длину, равную 4,5 единицам. Недостатком алгоритма можно считать сложность в определении максимально допустимой длины связи между двумя объектами. [64] ROCK ROCK (Robust Clustering using Links) [65] является иерархическим агломеративным алгоритмом, сочетающим в себе достоинства k-means и алгоритма ближайшего соседа, а также решающий их описанные выше недостатки. Основная идея алгоритма заключается во введении каждой паре объектов нового параметра – количество общих соседей (ссылок).

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

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

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

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

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

Главные особенности WaveCluster:

сложность реализации;

алгоритм может обнаруживать кластеры произвольных форм;

алгоритм не чувствителен к шумам;

алгоритм применим только к данным низкой размерности.

Кластеризация суффиксным деревом Изначально суффиксные деревья (suffix trees) были разработаны и применялись для быстрого поиска подстрок [68]. В диссертациях [69,70] предложено использовать идею суффиксных деревьев для кластеризации результатов запросов поисковой системы.[71] Построение дерева осуществляется поэтапно. Сначала получаемые из сети от поискового сервера документы подвергаются предварительно обработке - очистка от пунктуации, приведение слов в начальную форму (с помощью алгоритмов морфоанализа или стемминга) и т.д. Затем для набора документов строится дерево, но единицей, находящейся на рёбрах дерева является слово или словосочетание, а не буква, как в случае с деревьями для строк. Каждой вершине дерева соответствует фраза. Её можно получить, объединив все слова/словосочетания, находящиеся на рёбрах на пути от корня дерева к данной вершине дерева. В тех вершинах дерева, которые имеют потомков, имеются ссылки на документы, в которых встречается фраза, соответствующая вершине. Множества документов, на которые указывают эти ссылки, образуют базовые кластеры. После этого производится комбинирование базовых кластеров и получение набора кластеров.

Комбинируются кластеры по простой методике:

Пусть Bm и Bn – базовые кластеры, |Bm|, |Bn| - их размеры. - количество общих документов для этих кластеров.

Тогда, если: и, то базовые кластеры объединяются в один общий, иначе не объединяются.

Достоинства метода:

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

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

Недостатки метода:

необходимость повторной обработки текстов документов.

не используется уже имеющаяся информация о значения близости документов или значениях TF•IDF [3].

В работах Холланда [72] и Сахни [73] описан алгоритм построения cуффиксного дерева для строки символов за время O(n), причем количество используемой памяти также растёт линейно с ростом длины строки.

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

Таблица 1.1 Вычислительная сложность алгоритмов Алгоритм кластеризации Вычислительная сложность O(nkl), где k – число кластеров, l – число итераций k-средних O(n2log n) KRAB O(n2) FOREL лучшая – O(n2), худшая – O(n3) Метод опорных векторов (SVM) EM-алгоритм O(nkl) O(2n) CLIQUE O(nkla) k – число кластеров, a – средняя длина CLOPE объекта, l – число итераций Порядка O(2k) k – объект наибольшей размерности pMAFIA Нечетких C-средних (Fuzzy c-means) O(nkl), где k – число кластеров, l – число итераций Генетические алгоритмы Зависит от задачи Обучение: O(|D|Lave + |C||V|) Работа: O(|C|Ma) D – набор размеченных документов Алгоритм Rocckhio Lave – среднее количество терминов на документ C – количество классов V – словарь Ma – количество слов в запросе Нейронные сети Зависит от задачи O(n2log n) Минимальное покрывающее дерево Порядка O(n2log n) ROCK O(n2log n) CURE O(K) K – число ячеек, на которое разделено WaveCluster пространство Кластеризация суффиксным деревом O(nlog n) Кластеризация является затратным по времени процессом, но, в отличие от классификации не требует обучения классификатора, а значит, не требуется создавать или искать обучающие выборки, на которых этот классификатор обучать. Из всех алгоритмов кластеризации наиболее интерес алгоритм Нечетких C-средних. Кроме того, что алгоритм имеет не самую высокую временную сложность, он так же выделяется тем, что в качестве результата выдает вероятностную принадлежность текста к кластеру. Эта особенность позволяет определить объекты, которые, относясь к кластерам с равной вероятностью, могут быть выделены в отдельный кластер.

Кластеризация по тематике контента Так как входными данными для алгоритма кластеризации являются вектора с численными данными, а не слова или строки, то вопрос о способе кластеризации контента решается путем определения методов анализа текстов. Исходя из этого, алгоритм Fuzzy C Means сам по себе не решает по какой категории кластеризовать, и, следовательно, все зависит от способа обработки текстов перед проведением кластеризации. [74][75] Для обработки текста до требуемого вектора, рассмотрим преобразования: текст – обработка (очистка, стемминг/лемматизация) – малый словарь – большой словарь – вектор.

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

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

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

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

Пусть C {C1,..., C C }, K {K1,..., K K } : C K, K C, C K i i Тогда существует функция преобразования : C K, где C – множество текстов, K – множество идеальных кластеров Задача – построить преобразование : min Такая формулировка позволяет определить задачу кластеризации как поиск некоторого преобразования, максимально похожего на идеал, где за идеал принимается разбиение, сделанное человеком.

От количества кластеров зависит качество кластеризации, поэтому, иногда, приходится проводить несколько экспериментов, с варьирующимся количеством. В настоящей работе использовано предположение о том, что для каждого человека характерен свой словарный запас, как множество, пересекающийся с другими авторами, но не полностью. А также для каждого произведения характерна своя тематика, обладающая своими терминами. Следовательно, с прибавлением каждого нового элемента, количество кластеров должно зависеть от количества участвующих векторов, с учетом того, что с каждым новым элементом количество добавляющихся неизвестных слов становится все меньше, а количество кластеров стабилизируется [76]. Для оценки количества кластеров было произведено сравнение пяти функций, плавно зависящих от своего аргумента, которые показали или чрезвычайно малый прирост количества кластеров, или чрезвычайно интенсивный, или очень быстрое выравнивание. Результаты эксперимента представлены на рисунке 1.4 ниже:

Рис 1.4 Сравнение функций выбора количества кластеров [74] Классическая статистическая обработка позволяет алгоритму Нечетких C-средних (Fuzzy C-Means) определять схожесть текстов по тематике их содержимого. Так как при организации вектора участвуют специфические термины, присущие одной или нескольким областям наук.

Кластеризация по предполагаемому автору контента Авторский инвариант (англ. writer invariant, authorial invariant, author's invariant) – это количественная характеристика литературных текстов или некий параметр, который однозначно характеризует своим поведением произведения одного автора или небольшого числа «близких авторов», и принимает разные значения для произведений разных групп авторов. [3] Авторский инвариант применяется в задаче идентификации авторства текста – установления авторства неизвестного текста с помощью выделения особенностей авторского стиля и сравнения этих особенностей с другими произведениями, авторство которых известно.

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

Шаги кластеризации текстов по авторам, можно описать следующим образом:

Выбор группы признаков для проверки и формирования из неё авторского 1.

инварианта.

Выбор метрик и их параметров.

2.

Формирование вектора авторского стиля, позволяющей разделять тексты, на основе 3.

предполагаемых авторов.

Непосредственно применить наиболее подходящий из доступных алгоритмов 4.

кластеризации.

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

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

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

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



Pages:   || 2 | 3 | 4 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.