Средства кластеризации распределенных данных на основе нейронных сетей Кохонена тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Рукавицын Андрей Николаевич

• Рукавицын Андрей Николаевич
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Рукавицын Андрей Николаевич

ВВЕДЕНИЕ

ГЛАВА 1. АНАЛИЗ СУЩЕСТВУЮЩИХ МОДЕЛЕЙ И МЕТОДОВ КЛАСТЕРИЗАЦИИ ДАННЫХ В РАСПРЕДЕЛЕННОЙ

ВЫЧИСЛИТЕЛЬНОЙ СРЕДЕ

1.1 Интеллектуальный анализ данных в распределенной вычислительной среде

1.2 Модель системы мониторинга

1.3 Обзор методов кластерного анализа

1.4 Формальное представление нейронных сетей

1.5 Обучение нейронных сетей на распределенных данных

1.6 Выводы

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

2.1 Алгоритм кластеризации на основе нейронных сетей

2.2 Формальное представление

2.3 Алгоритм БОМ как композиция функций

2.4 Алгоритм ОКО как композиция функций

2.5 Выводы

ГЛАВА 3. РАСПАРАЛЛЕЛИВАНИЕ АЛГОРИТМА ДЛЯ РАСПРЕДЕЛЕННЫХ ДАННЫХ

3.1 Стратегии кластеризации в распределенных системах мониторинга

3.2 Параллельные формы алгоритма БОМ для разных типов распределения данных

3.2 Параллельные формы алгоритма ОКО для разных типов распределения

данных

3.3 Методика построения алгоритма в распределенных системах мониторинга

3.4 Выводы

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

4.1 Программная реализация

4.2 Результаты методики

4.3 Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ

ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ

OLTP - online transaction processing ETL - extract, transform, load LA - lambda architecture

BIRCH - balanced iterative reducing and clustering using hierarchies DBSCAN - density-based spatial clustering of applications with noise OPTICS - ordering points to identify the clustering structure SOM - self-organizing map GNG - growing neural gas IoT - Internet of Things

Введение

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

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

• анализ существующих средств кластеризации, в том числе распределенных данных;

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

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

• разработка методики выполнения кластеризации на основе нейронных сетей кохонена на распределенных источниках, данных с учетом типа распределения данных;

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

• экспериментальная проверка полученных результатов.

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

Предметом исследования являются средства выполнения алгоритмов

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

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

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

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

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

Практическая значимость:

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

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

Положения, выносимые на защиту:

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

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

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

Реализация и внедрение результатов работы.

Результаты исследования были использованы в работах, выполняемых в АО «НИЦ СПб ЭТУ», также использованы при проведении практических занятий

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

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

Апробация работы.

Основные положения и результаты диссертационной работы докладывались и обсуждались на международных конференциях ElConRus, St. Petersburg, Russia, 2019 г, SCM, St. Petersburg, Russia, 2018 г., ElConRus, St. Petersburg, Russia, 2018 г, NEW2AN , St. Petersburg, Russia, 2017 г, ElConRus, St. Petersburg, Russia, 2017 г., SCM, St. Petersburg, Russia, 2017 г.

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

Публикации. Основные теоретические и практические результаты диссертации опубликованы в 22 трудах, среди них: 4 научных статей, опубликованных в журнале, входящем в рекомендуемый перечень ВАК, 7 научных публикаций в журналах и сборниках трудов, входящих в базы цитирования Web of Science и Scopus, 4 публикаций в сборниках конференций, и 7 свидетельств о регистрации программы ЭВМ.

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

среде

В последнее время все большую актуальность приобретает задача анализа информации, собираемой из разных источников. Человечество вступило в эру больших данных, характеризующихся большими объемами информации, высокой скоростью ее появления, вариативностью форматов ее представления и хранения. Большинство современных систем, анализируют данные, полученные не только от транзакционных (OLTP) систем, но и от различного рода датчиков и измерительных средств, фото- и видео-регистраторов, систем контроля, социальных сетей, провайдеров финансовой информации и т.п. Подобные источники генерируют потоки информации в реальном режиме времени, которые для передачи данных используют разные каналы связи, в том числе и беспроводные (спутниковая, радиорелейная, сотовая связи и др.), характеризующиеся ограниченной пропускной способностью. Необходимость решения задач в новых условиях привела к появлению новых направлений и понятий в области информационных технологий: большие данные (Big data), облачные вычисления (Cloud computing), интернет вещей (Internet of Things), потоковая обработка (Stream Processing), интеллектуальный анализ данных (Data Mining) и др.

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

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

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

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

1.1 Интеллектуальный анализ данных в распределенной вычислительной

среде

Традиционные подходы к решению задач сбора, обработки и анализа информации не позволяют достичь оперативности, необходимой для принятия решений в современном мире. Технологии сбора и обработки информации, такие как хранилища данных, ETL (Extraction, Transformation, Loading) и методы потоковой обработки (stream processing), предполагают небольшое (до 10) число источников, с заранее известной структурой, не меняющейся во времени. Проблемы возникают как с вычислительными, так и с сетевыми ресурсами, которые требуют постоянного наращивания в связи с ростом объемов

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

Задача сбора информации из различных источников не является новой [4]. В начале 2000 годов широкое распространение получила концепция построения хранилища данных [5]. В соответствии с ней, данные из OLTP систем собирались в хранилища данных для последующего анализа. Интеграция данных выполнялась периодически из стационарных, как правило, реляционных источников.

Выделяют следующие типы архитектур хранилищ данных [6, 7]:

- физические - содержит консолидированные данные, извлеченные из нескольких операционных источников;

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

Их характеристики приведены в таблице 1.1.

Таблица 1.1 - Характеристики архитектур хранилищ данных

Характеристики Тип хранилища данных

Физический (Physical) Витрина данных (Data marts) Виртуальный (Virtual)

Предметно-ориентированный + + +

Данные интегрированы + + -

Данные энергонезависимые + +

Исторические данные + + -

Текущие данные - - +

Агрегирование + + -

Детализация + + +

Стандартные инструменты ETL [8] извлекают информацию из источников данных (Извлечение), преобразуют ее в формат, поддерживаемый хранилищем данных (Transformation), а затем загружают в него преобразованную информацию (Загрузка).

В настоящее время из десятка популярных инструментов ETL следующие системы являются open-source [9]:

- Pentaho Data Integration (PDI) [10] — ETL средство комплекса Pentaho.

- CloverETL [11] — библиотека для интеграции, преобразования, очистки и унификации данных в приложениях, базах данных и хранилищах данных.

- Talend Open Studio (TOS) [12] — ETL инструмент для интеграции данных.

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

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

Различные инструменты ETL включают в себя различные единицы преобразования и обработки данных. Например, интеграция данных Pentaho включает следующие блоки [13]:

- SwitchCase переключить строку на определенный целевой шаг, основанный на значении случая в поле.

- MergeJoin соединяет два потока на заданной клавише и выводит объединенный набор. Потоковые потоки должны быть отсортированы по ключу.

- и другие.

Кроме того, инструменты ETL могут быть расширены пользовательскими устройствами. Например, шаг UserDefinedJavaClass в PDI позволяет программировать шаг с использованием Java-кода.

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

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

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

С увеличением вариативности форматов источников данных, ростом объемов информации и частотой ее обновления встала проблема сбора и обработки больших данных. Для этого в настоящее время широко используются технологии noSQL, stream processing и системы, построенные на базе lambda architecture (LA) [17].

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

Структура LA имеет три уровня [18]:

- Batch layer - архив необработанных исторических данных. Этот уровень поддерживает и поддерживает передачу пакетных данных.

- Service layer индексирует пакеты и обрабатывает результаты расчета, которые формируются на уровне пакета. Результаты немного

задерживаются во времени из-за индексации и обработки поступающей информации.

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

Системы с интегрированными гетерогенными компонентами, которые передают данные от одного компонента к другому (внутри каждого из слоев). Примерами таких компонентов могут быть системы Apache [19]:

- Apache Hadoop для обработки больших объемов данных на уровне партии.

- Apache Spark Streaming для обработки потока данных в режиме реального времени на уровне скорости.

- Apache Spark SQL и Apache Spark MLib для создания запросов и анализа на уровне обслуживания.

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

С ростом Интернета и подключаемых к нему источников: новостных ресурсов, финансовых провайдеров, социальных сетей (и их пользователей), различных устройств, активно развивается концепция Internet of Things (IoT) [20] и различных ее вариаций [21-24]: Social Internet of Things (SIoT), Internet of Social Things (IoST), Internet of Everythings (IoE) и другие.

Основная архитектура IoT, которая широко используется для объяснения подходов IoT, представляет собой три слоя [25]:

- the perception layer является нижним слоем, который можно рассматривать как аппаратный или физический уровень, который выполняет сбор данных;

- the network layer (middle layer), отвечает за подключение уровня восприятия и уровня приложения, так что данные могут передаваться между ними;

- the application layer обычно играет роль предоставления услуг или приложений, которые интегрируют или анализируют данные, полученные из двух других слоев.

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

Ведущие поставщики облачных виртуализированных сред (ОВС) предлагают несколько платформ, предоставляющих услуги кластеризации данных для интернета вещей [27]: Azure Machine Learning Studio [28] от Microsoft, Machine Learning AWS от Amazon [29], платформа облачного машинного обучения [30] от Google и Watson Analytics [31] от IBM. Общей особенностью этих платформ является то, что они основаны на модели MapReduce [32]. Рисунок 1.1 показывает, как распределенная кластеризация выполняется при использовании модели MapReduce и в соответсвии с парадигмой тумана.

ОВС

(Х' Источник данныданные генные >

t . Устройство

Данные'

т Источник данныданные Изданные

(■ • Устройстве

^данные1 хранения

Источникданных

Devices ,

, Middle layer

layer J

Вычислительный узел

Application layer

layer

данных

Узел тумана (капля) Middle layer

Application layer

Рисунок 1.1 - Варианты алгоритмов интеллектуального анализа данных, применяемые к распределенным данным: а) традиционная модель MapReduce; б)

подход в соответствии с парадигмой тумана

В случае использования модели MapReduce в интернете вещей средний уровень отвечает за соединение устройств (таких как датчики или камеры) с облаком. Эти соединения часто негативно влияют на производительность интеллектуального анализа данных, потому что они [33, 34]:

- создает высокий трафик;

- увеличивает задержку узлов при анализе данных;

- увеличивает риск несанкционированного доступа к данным.

Альтернативным решением может быть использование парадигмы туманных вычислений [35, 36] для преодоления этих проблем. В туманных вычислениях данные обрабатываются ближе к своим источникам, что обеспечивает низкую задержку и понимание контекста [37].

На рисунке 1.1 б показан альтернативный подход, на основе парадигмы туманных вычислений. Анализ выполняется в два этапа (Рисунок 1.1 б):

- кластеризация в узлах тумана и передача результатов в облако;

- объединение результатов в облаке.

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

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

Методики обычно сводятся к двум этапам [41-45]:

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

2. Объединение результатов и группировка кластеризации. Объединение может быть выполнено иерархически [46], при таком подходе

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

В работе Gorgonю F. L. [47] описан подход, использующий ансамбль моделей (нейронных сетей), построенных SOM алгоритмом. В нем на обоих этапах используется один и тот же алгоритм кластеризации, но для разных задач. На первом этапе SOM определяет нейронную сеть с кластерами и передает глобальной модели. На втором этапе SOM используется процесс кластеризации карт для определения кластеров из переданных карт. Такой метод может привести к увеличению степени неопределенности.

Одним из наиболее распространенных подходов анализа распределенных данных является централизация в хранилище данных, на котором применяются традиционные методы интеллектуального анализа данных [48-50]. Хранилище данных - популярная технология, которая объединяет данные из нескольких источников в один, чтобы эффективно выполнять сложные аналитические запросы [51]. Однако, несмотря на широкое распространение, этот подход может быть непрактичным или невозможным при следующих условиях [52-54]:

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

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

- технически невозможно из-за ограниченной пропускной способности и

высокой нагрузки при передаче данных.

Соответственно, подход для интеллектуального анализа распределенных данных должен учитывать:

- адаптацию алгоритма построения модели в распределенной сети;

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

точностью анализа;

- вид распределения.

1.2 Модель системы мониторинга

Рассмотрим систему мониторинга с использованием сенсорных сетей, где узлы датчиков могут быть оснащены звуковыми, вибрационными, температурными и отражающими зондами. Допустим, датчики контролируют географический регион и должны следить, обрабатывать и обмениваться данными друг с другом, чтобы отслеживать и идентифицировать объекты, представляющие интерес для пользователя. Наблюдения обычно представляют собой данные в виде временных рядов. Система мониторинга может контролировать множество объектов X [55]:

X = Iх!, х2 , . . ., X, . . ., Хп }.

Каждый объект характеризуется набором атрибутов А:

А = {а1,а2, ...,аг...,ат}.

При этом система мониторинга следит за значением атрибута Х каждого объекта в каждый момент времени

Х (*) = {а1, (*) , а2г (*) , аП (*) аш (*)}.

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

Таблица 1.2 - Анализируемые данные для системы мониторинга

г X А1 А2 А] А ^т м

и х1(г1) аи(гО а21(г0 ал(Г1) ат1(г1) м1

Х2(г0 ап(гО а22(г0 а]2(г0 ат2(г1)

х(гО ац^О а2$1) а/гО ат1(г1)

хп(г1) а1п(г1) а2п(г1) а]п(г1) атп(г1)

г2 Х1(г2) ап(г2) а21(г2) ад(г2) ат1(г2) мг

Х2(г2) а12(г2) а22(г2) а^2) ат2(г2)

х(г2) ац(г2) а2$2) а/г2) ат1(г2)

Хп(г2) а1п(г2) а2п(г2) а]п(г2) атп(г2)

Стоит обратить внимание, что системы могут быть однородными (то есть каждый узел наблюдает общее подмножество данных) или гетерогенными (то есть каждый узел наблюдает соответствующее подмножество данных). Гетерогенная система рассматривает два вида распределения данных: горизонтальное и вертикальное. При горизонтальном распределении данные делятся на источники по строкам или для временных рядов по времени или по объектам из X. При вертикальном распределении данные делятся на источники по столбцам или по атрибутам из А.

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

данных в распределенных системах мониторинга [57]. Целью этого метода является разложение или разбиение набора данных на группы путем минимизации межгруппового несходства и максимизации внутригруппового сходства. В таком случае требуется организовать передачу данных от датчиков в единое хранилище для последующей кластеризации. В сенсорных системах мониторинга это сложно выполнимо из-за различных причин, таких как ограниченная пропускная способность связи или вычислительная мощность. Традиционная структура централизованных алгоритмов кластеризации плохо масштабируется в распределенных приложениях, так как предполагает передачу данных на базовый узел. При этом интенсивная передача данных по ограниченному каналу полосы пропускания может привести к снижению времени отклика всей системы.

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

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

- количество обрабатываемых измерений чрезвычайно велико - 106 и более;

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

- нет предварительной информации о количестве и местонахождении искомых регионов;

- данные распределены на нескольких источниках и не могут быть объединены в центральном хранилище.

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

- однопроходность по данным - алгоритм должен выполнять кластеризацию за один проход по всем данным;

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

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

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

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

- выделение наиболее значимых атрибутов;

- масштабирование больших объемов данных;

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

- выполнение анализа без предположений о распределении входных данных;

- обнаружение аномалий;

- анализ данных на источниках информации без их передачи третьей стороне;

- поддержка анализа распределенных данных.

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

1.3 Обзор методов кластерного анализа

С появлением интеллектуального анализа данных было предложено множество методов кластеризации. Кластеризацию можно классифицировать по нескольким категориям [59-62] в соответствии с их принципом формирования кластеров:

Иерархическая кластеризация

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

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

Дивизимный подход («сверху-вниз») строит новые кластеры путем деления более крупных кластеров на мелкие - дерево иерархии строится от ствола к листьям.

Одним из популярных алгоритмов иерархической кластеризации является BIRCH (Balanced Iterative Reducing and Clustering Using Hierarchies)[63]. В отличие от своих аналогов, он был специально разработан для минимизации количества операций ввода-вывода. Алгоритм особенно подходит для больших объемов данных [64]. Он динамически сегментирует входящие многомерные метрические точки данных, чтобы создать кластер с наилучшим качеством и доступными ресурсами (доступной памятью и временными ограничениями) [63]. После первой кластеризации может дополнительно улучшить качество с помощью нескольких дополнительных сканирований. Он также является первым алгоритмом кластеризации, предложенным в области базы данных для эффективного управления «шумом». Имеет два существенных недостатка:

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

1. Гибкость в отношении уровня детализации.

2. Удобство представления для иерархических данных.

3. Быстрота обработки.

Недостатки:

1. Невозможность внести исправления после разделения/слияния.

2. Отсутствие интерпретируемости дескрипторов кластера.

3. Нечеткость критерия завершения.

4. Невозможность работать с асферическими кластерами разного размера.

5. Неэффективность в высокоразмерных пространствах из-за проклятия размерности.

6. Чувствительность порядка данных.

Центроидная кластеризация

Список литературы диссертационного исследования кандидат наук Рукавицын Андрей Николаевич, 2020 год

Источник Источник

данных 1 ООО данных п

С^Кл!

а)

вектор расстояний

номер

нейроны ---------------►

нейроны

б)

Рисунок 3.1 - Схема передачи данных в распределенном алгоритме WTA-WTM: а) промежуточная синхронизация (стратегия 1); б) слияние результатов (стратегия 2)

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

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

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

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

Щ = /(Щ, Щ2,, ), 0 < I < п

Функция вычисления общего веса f может быть разной. В простейшем

случае это может быть функция вычисления среднего:

/ (Щ ,, Щ2 ,, ЩЩ ) = ( Щ, + Щ2 , + ...+ щЩ) / Щ

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

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

Таблица 3.1 - Условия применения стратегий для разных видов

распределения данных

Вид распределения данных Тип стратегии Условия использования

Горизонтальное 1я стратегия Не применимо

2я стратегия При использовании небольшой окрестности

Вертикальное 1я стратегия Применимо

2я стратегия При наличии зависимости между атрибутами

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

< - 1 )2; <г,

При синхронизации будет вычислено общее расстояние: dj =

Очевидно, что в случае использования Евклидова расстояния сумма частей не равна общему расстоянию:

а'1 ф а1 + а21 =^£">"-17

] ] ] где 1 \¿—¡1=1к 1 1г/

Однако отношение неравенства при таком преобразовании сохраняется:

< +1, (а1} + а2}) < (а1}+1+а2}+1)

Это дает возможность корректно выбрать нейрона-победителя. Источникам после вычисления возвращается номер глобального нейрона-

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

W = {a i, a2, a3, a4, a5, «б};

W ={ai,a2,a3,0,0,0} + {0,0,0, a4, a5,a6}.

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

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

3.2 Параллельные формы алгоритма SOM для разных типов распределения

данных

Для определения возможности выполнения алгоритма распределено построим представление множества входящих (In) и выходящих (Out) данных функциональных блоков (Таблица 3.2).

Таблица 3.2 - Множества In и Out для FMBs алгоритма SOM

ФОМ In Out

fdc d m[1], m[2]

fi m[1,1],..., m[1,n] m[1,1,1].w,..., m[1,n,m].w

ФОМ 1п Ои1

£2 ш[1Д,1]^,..., ш[1,1,ш].^' ш[1д,1]^,..., ш[1,i,ш].w,

fз т[1, 1, ^^ ш[1, 1, j].w

£¿6 ё, ш[1]Л, ш[1].Т, ш[1].Ь, , ш[1].1 шт ш[1, 1], ..., ш[1, п], ш[2,1].г, ..., ш[2,п].г ш[1].Ь, ш[1, 1], ..., ш[1, п], ш[2,1].г, ..., ш[2,п].г

ё, ш[1]л_шт, ш[1,1],..., ш[1,п], ш[2,1].г, ..., ш[2,п].г ш[1,1],..., ш[1,п], ш[2,1].г, ..., ш[2,п].г

ё[к], ш[1,1],..., ш[1,п], ш[2,1].г, ..., ш[2,п].г ш[1,1,1]^,..., ш[1,п,ш]^, ш[2,1].г, ..., ш[2,п].г

¿[к], ш[1Д,1]^,..., ш[1д,ш]^, ш[2Д].г, ..., ш[2,п].г ш[1д,1]^,..., ш[1Д,ш]^, ш[2,1].г, ..., ш[2,п].г

ё[кД ш[1,i,j].w, ш[2Д].г ш[1,i,j].w, ш[2,1].г

£13 ш[2,1].г, ..., ш[2,п].г ш[2,1].г, ..., ш[2,п].г

£14 ш[2,1].г, ..., ш[2,п].г ш[2, i]. г

«117 ш[2,1].г, ..., ш[2,п].г, ш[1].1 шт ш[2,1].г, ..., ш[2,п].г, ш[1]л ш1п

ФОМ In Out

fd18 m[2,i].r, ..., m[2,n].r, m[1].i min m[1].i min

f 20 d, m[1].i_min, m[1,1],..., m[1,n] m[1,1,1].w,..., m[1,n,m].w

f21 d[k] , m[1].i min, , m[1].t, m[1, i, 1].w, ..., m[1, i, m].w m[1, i, 1].w, ..., m[1, i, m].w

f22 d[k] , m[1].i min, m[1].t, m[1, i, j].w m[1].h, m[1].a, m[1, i, j].w

f27 m[1].t m[1].t

ФОМ fd4 и fdn обрабатывают матрицу данных напрямую. В соответствии с концепцией тумана эти функции должны выполняться в узлах тумана. Для этого мы преобразуем последовательную форму алгоритма в параллельные формы для разных типов распределения данных. Для горизонтально распределенных данных преобразуем ФОМ в параллельную форму для распределенной памяти, вставив функцию paralleld:

somHpar = (paralleld [loopr 1 z (fd^fy^^)] d)°fo(16)

Функция union вызывается после завершения обработки всех строк матрицы данных d. Она рассчитывает вес нейронов с одинаковыми показателями из разных карт SOM:

join ц = [[а(^[1].ю[1], ..., ^[1].ю[1])], ..., [а(^[п].ю[р], ..., ^s[n].®[p])]],

где r =1..s SOM построен в r-м узле тумана; а является функцией для расчета общего веса, например, вычисления среднего значения:

[а(^И.ю[1], ..., ^s[i].®[1])] = (^1[i].®[1] + .+ ^s[i].®[1]) / s.

Это моделирует обучение БОМ, если строки подаются на вход последовательно.

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

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

Рисунок 3.2 - Распределенное выполнение алгоритма БОМ для горизонтально

распределенных данных Для реализации параллельной формы алгоритма БОМ для вертикально распределенных данных функция рагаИвМ должна быть применены к циклам Iоорс:

БошУраг = (1оорг 1 ъ (1оорп 1 п (рага11еЫ [1оорс 1 р Гёп]))^0^0 (1оорп 1 п (£0(рага11еМ [1оорс 1 р ГВД))

В этом случае функция вычисляет расстояния:

^[¿№1 =

J1 -d[j,k 1)2 ;...;ц'[i]d[j] =

k=1 \

J Ш.Ф 1 - d[ j, k ])2

k=r+1

Общее расстояние можно рассчитать по функции join как сумма:

join /л[.iJ.Sj] = /1[i].d[j_] + ... + /s[i].d[j]

Очевидно, что в случае использования Евклидова расстояния сумма частей не равна общему расстоянию:

M1[i].S[ j ] +... + [i]d[ j] ф

£ ШМЬ ] - d[ j, k ])2

k=1

Однако в этом преобразовании сохраняется соотношение неравенства, т. е. если ^[i]5[j]<^[i+1].5[j] тогда и

(^1[i].5[j]+^+^s[i].5[j])<(^1[i+1].5[j]+^+^s[i+1].5[j]).

Это позволяет нам правильно выбрать нейрона-победителя.

Функция fd11 корректирует веса нейронов в узлах тумана только относительно столбцов подматрицы:

^ = [[ю'ь ..., Ю^,..., Юг+1,..., Юр], •••, [ю'1, •••, ®'g,— , Юг+1,..., Юр]], •••

= [[Ю1, ®g,., Ю'г+1,., Ю'р], [Ю1, ®g, ®'g+1,., Ю'р]],

где ®'g измененный вес, ®g не измененный вес.

Функция join объединяет SOM :

join ^ = [[Ю'1, ..., ffl'g,., Ю'г+1,., ю'р], ..., [Ю'1, ..., ffl'g,., Ю'г+1,., Ю'р]].

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

На рисунке 3.3 показано размещение функций на узлах тумана. В этом случае распределяем циклы loopc между узлами тумана в соответствии с распределением матрицы данных d.

Вычислительный узел

Рисунок 3.3 - Распределенное выполнение алгоритма SOM для вертикально

распределенных данных

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

Чтобы избежать этого, мы восстанавливаем алгоритм SOM двумя преобразованиями цикла расщепления и перестановкой циклов (которые используются в компиляторах) [106]. Сперва расщепляем цикл loopr:

som'=

(loopr 1 z (loopn 1 n (loopc 1 p fd11)))° (loopr 1 z (loopn 2 n f8)°f6°(loopn 1 n f5))° (loopr 1 z (loopn 1 n (loopc 1 p fd4))) d))° fo

Далее применяем перестановку на вложенные циклы loopc и loopr: som'=

(loopc 1 p (loopn 1 n (loopr 1 z fd11)))° (loopr 1 z (loopn 2 n f8)°f6°(loopn 1 n f5))° (loopc 1 p (loopn 1 n (loopr 1 z fd4)))° f0.

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

бош' = где:

• 1^' цикл по колонкам: 1^' = 1оорс 1 р 1(2' ё;

• 1(2' цикл по нейронам: 1(2' = 1оорп 1 п 1ё3';

• 1(3' цикл по строкам: 1(3' = 1оорг 1 ъ 1^;

• 14' цикл по строкам: 14' = 1оорг 1 ъ 17°16°15';

• 15' цикл по нейронам: 15' = 1оорп 1 п 15;

• 1(8' цикл по колонкам: Ш8' = 1оорс 1 р 19' ё;

• 1(9' цикл по нейронам: 1(9' = 1оорп 1 п 1(10';.

• Ш10' цикл по строкам: 1(10' = 1оорг 1 ъ Шп.

Функция рагаИвМ должна быть применена к циклам ¡воре выражения (чтобы выполнить его параллельно на узлах тумана с распределенной памятью для вертикально распределенных данных:

вошУраг'=(рага11еЫ [1оорс 1 р Ш9'])°14'° (рага11еМ [1оорс 1 р й2' ё] ё)°10

Основная проблема этого варианта - различный выбор победителей в каждом из узлов тумана. В результате БОМ с различными кластерами

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

На рисунке 3.4 показано размещение функций композиции на узлах тумана.

-Ц

Г0 У-ЧН( Гогк<<

)

рагаПеШ

..101П

Гогк^ рагаИеШ

Вычислительный узел

М

Рисунок 3.4 - Распределенное выполнение оптимизированного алгоритма БОМ

для вертикально распределенных данных

Здесь мы распределяем циклы loopc между узлами тумана в соответствии с распределением матрицы данных d.

3.2 Параллельные формы алгоритма GNG для разных типов распределения

данных

В главе 2 были определены общие и отличные блоки для алгоритмов БОМ и ОКО. Для ОКО можно выделить ФОМ, которые отличаются от представленных в БОМ:

- Г13 - обновление связей;

- Г14 - удаление устаревших связей;

- Г17 = 1оорп 1 п Г18 - удаление устаревших нейронов;

- f19 = ((loopc 1 p f26) (loopq 1 n f24) (loopn 1 n f22) f20) - генерация новых нейронов;

- f28 - обновление ошибки;

Для определения возможности выполнения алгоритма GNG распределено построим представление множества входящих (In) и выходящих (Out) данных функциональных блоков (Таблица 3.3).

Таблица 3.3 - Множества In и Out для FMBs алгоритма GNG

ФОМ In Out

f13 i min1, i min2, m[1, i min1], m[1, i min2] m[1, i_min1].edge.get(i_min2).age, m[1, i_min2].edge.get(i_min1).age

f14 m[1,1]...m[1,n] m[1,1,1]...m[1,n,n]

f15 m[1,i,1]...m[1,i,n] m[1,i,1]...m[1,i,n]

f16 m[1,i,q] m[1,i,q].edge

f17 m[1,1]...m[1,n] m[1,i]

f18 m[1,i] m[1,i]

f19 t, ALPHA

f20 u, v u, v

f21 m[1,1]...m[1,n] m[1,1].e...m[1,n].e

f22 u, m[1,i].e...m[1,n].e u

f23 m[1,u].edge.get(1)... m[1,u].edge.get(n) m[1,u].edge.get(1)... m[1,u].edge.get(n)

f24 v, m[1,q].e, m[0,v].e v

ФОМ 1п Ои;

125 ш[1,и,1]...ш[1,и,р], т[1^,1]...т[1,^р] т[1,и,1]^...т[1 ,u,p].w, ш[1,v,1].w...ш[1,v,p].w

126 т[1,и,1]^...т[1 ,и,р]^, т[1^,1]^...т[1^,р]^ new пеигоп

127 пе^^пеигоп, т[1], т[1,и], ш[1,v] new_neuгon, т[1, и].её§е, т[1, v].edge, т[1, new пеигоплпёех]

128 т[1,1]...т[1,п] т[1,1].е...т[1,п].е

129 т[1,1].е, ББТЛ т[1,1].е

Н4 и Н5 имеют зависимость по входным и выходным данным т[1,у]:

- П4 распараллелим по итерациям

- А5 распараллелим по итерациям

- 114 = рага11е1Б[1оорп 1 п рага11е1в[1оорд 1 п 116]]

Н7 и Н8 имеют зависимость по входным и выходным данным ш[1д]:

- А7 распараллелим по итерациям

- :18 распараллелим по итерациям

- 117 = рага11е1Б[1оорп 1 п 118]

120 имеют зависимость по входным и выходным данным и, V для 122, 124, 126, 127. ФОМ в 119 можно распараллелить по итерациям в следующим образом:

119 = (рага11е1в[1оорс 1 р 126] рага11е1в[1оорд 1 п 124] рага11е1Б[1оорп 1 п 122] 120)

Тогда представим алгоритм GNG в виде композиции функций для горизонтального распределения данных: ИвЫв = f28

рага11е1с1(

1оорг 1 с (

(рага!!е!5[!оорс 1 р f26]) (рага!!е!5[!оорд 1 п f24]) (рага!!е!5[!оорп 1 п f22]) f20

)

(рага!!е!5[!оорп 1 п f18])

(рага!!е!5[!оорп 1 п (рага!!е!з[!оорд 1 п Й6])]

f13

(рага!!е!5[!оорп 1 п (рага!!е!5[!оорс 1 р fC 12])]) f9

(рага!!е!5[!оорп 2 п f8]) f6

(рага!!е!5[!оорп 1 п (f5 (рага!!е!Б[!оорс 1 р fC4]))])

)

)

ГО

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

Рисунок 3.5 - Распределенное выполнение алгоритма GNG для горизонтально

распределенных данных Преобразуем модель для вертикального распределения данных: увЫв = 128 11 10 = = 128

( 1оорг 1 с ( 119 117 114 113 1С10 19 17 16 1С2 ) ) Полученная модель не позволяет выполнить алгоритм в среде с вертикально распределенными данными, так как ФОМ Ш10 и Ш2 имеют зависимость по данным с другими ФОМ. Поэтому необходимо выполнить расщепление тела цикла для (1оорг 1 с ( Н9 Н7 Н4 Н3 19 17 16 fd2 )). увЫв = =128

( 1оорг 1 с (

119 117 114 113 ) )

( 1оорг 1 с ( 1с110

) )

( 1оорг 1 с (

19 17 16 ) )

( 1оорг 1 с ( 1С2

) )

fO = f28

( loopr l c (

fl9 fl7 fl4 fl3 ) )

( loopr l c (

loopn l n (fdll)

) )

( loopr l c (

f9 f7 f6 ) )

( loopr l c (

loopn l n (f5 fd3)

) )

fO = f28

( loopr l c (

fl9 fl7 fl4 fl3 ) )

( loopr l c (

loopn l n (

loopc l p (fdl2)

) )

( loopr l c (

f9 f7 f6 ) )

( !оорг 1 с (

!оорп 1 п ( f5 (!оорс 1 р ^4))

) ) )

Следующий этап оптимизации будет перестановка циклов (1оорс 1 р) и (1оорг 1 с), которые имеют зависимостью от данных в ФОМ Ш12 и Ш4.

увЫв = f28

( !оорг 1 с (

f19 f 17 f14 f13 ) )

( !оорс 1 р (

!оорп 1 п (

!оорг 1 с (fd12)

) )

( !оорг 1 с (

f9 f7 f6 ) )

( !оорс 1 р (

!оорп 1 п ( f5 (!оорг 1 с (fd4))

)

Полученная композиция функций может быть выполнена распределено: увЫв = f28

( !оорг 1 с (

(рэга!!е!5[!оорс 1 р f26]) (рага!!е!з[!оорд 1 п f24]) (рага!!е!5[!оорп 1 п f22])

f20 ) )

(рага!!е!5[!оорп 1 п f18]) (рага!!е!5[!оорп 1 п ( рага!!е!з[!оорд 1 п Й6]

)]) f13

[рага!!е!С( !оорс 1 р ( !оорп 1 п (

!оорг 1 с ^12)

)

) )]

( !оорг 1 с ( f9

(рага!!е!5[!оорп 2 п f8])

f6

) )

[рага!!е!С( !оорс 1 р ( !оорп 1 п ( f5 (!оорг 1 с ^4))

)

) )]

Пусть, 14' =

17 16 15' =

17 16 (1оорп 1 п 15)

В соответствии с предложенной моделью часть алгоритма переносится на узлы источников (Рисунок 3.6).

Вычислительный узел

Рисунок 3.6 - Распределенное выполнение оптимизированного алгоритма GNG

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

3.3 Методика построения алгоритма в распределенных системах

мониторинга

В соответствии с предложенными стратегиями и описанными условиями работы для построения кластеризации на основе нейронных сетей в распределённых системах предлагается методика (Рисунок 3.7).

Выбрать коэффициент слияния п

___I

( )

Рисунок 3.7 - Схема построения алгоритма в распределенных системах

мониторинга

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

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

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

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

3.4 Выводы

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

1. Стратегии для горизонтального и вертикального распределения данных.

2. Анализ возможности работы алгоритмов БОМ и ОКО с распределенными данными.

3. Оптимизированы алгоритмы БОМ и ОКО для работы с вертикально и горизонтально распределенными данными с использованием расщепления и перестановок циклов.

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

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

4.1 Программная реализация

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

- MiningSequence - блок последовательного выполнения вложенных в него блоков.

- Мт^ЬоорЕ1етеП - блок цикла по указанному элементу (ШБЕХ_КЕШОШ - по нейронам карты, ШБЕХ_АТТШВШ^ЕТ - по признакам), принимает последовательность функциональных блоков, которые будут выполняться в цикле.

- Мт^ЬоорУе^оге - блок цикла по векторам, принимает последовательность функциональных блоков для выполнения в цикле.

- ^ЪйеСЬа^е№игошЬоор - блок цикла по нейронам, принимает в качестве условия окончания максимальное количество итераций или дельту изменения весов.

- Мт^Рага11е1 - блок разделения выполнения по данным. Для каждого выполняемого процесса выделяется собственная модель. Модели объединяются при завершении выполнения блока.

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

Модель знаний алгоритма кластеризации на основе нейронных сетей Кохонена состоит:

Кластеры.

Узлы нейронной сети и связи между узлами. Ближайший к вектору узел сети. Дистанция от узла нейронной сети до вектора.

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

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

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

r^SOMMiningModel

" SOMMinîngModeifEMiningFunctionSettings)

^ WinnerNeuronForVector

i WinnerNeuronFoiVector (String)

SOMFunction5ettings

SOMFuncffonSe [ tingi (ELogkaiData)

= SOMMIningModelS MODULES SOMMiningModelS

г oddWinnerNeuronforVectorfWinnerNeuronforVector) r addVectorToNeuronDistancefint, VectorToNeuronDistance) " getNeuronWeightfint, int) r getVectorToNeuronDistancefint, int) T get WinnerNeuronForVector (in t) " Ъ initModelO « г clorteO

" t INDEX_ CLUSTEP_ VECTORQ n Ъ CL USTER_ VECTORQ 3 currentNeuronlnâex 3 neuronSet

Coordinate VectorToNeuronDistance WlnnerNeuronForVecto void

SOMMiningModel intQ

1 merge (List < MiningModelEiement >) void

» idQ String

' distonce ToNeuronQ double

" distanceToNeuron_Seq(double) void

i iNeuronf) int

' i№u!on_5eqfu>t) void

1 createNewCopyEiementQ WinnerNeuronForVecto

1 propertiesToStringQ String

m getNeighboursfmt) m neuronfJeighbcurs fj m neuronNeighbours_$eq(intQ[j) m ' setNeigtiboursfmt, intlj)

i SOMMiningModelSO

n INODt_CLUSTER_VECTOR0 » T. Ci USTER_ VECTORQ

I maxNumberOfClusters

S О MAI go rithmS ett i n g s

, VectorToNeuronDistance

1 VectorToNeuronDistance(String)

> distanceToNeuron

> indexOfl^euron

Self Org a n izingM apBa d VerPa га I lelAI g о rith m

в VectrosDistribution 1 VectrosOistribu tion (String)

SeifOrganizingMapBodVerParalleiAlgorithmfSOMFunctionSettings)

initBlockst)

createModelfMininglnputStream)

r, Self Org anizl n g M а p H о rPa га I lelAI g о rith m

n" SeifOrganizingMapHorPcraiielA igori thmfSOMFunctionSe £ tings)

rr Ь initBiocksQ

n" createModel{Minir>glnputStream)

EMiningModel

" Я add(MiningModelEtement) wo

* S mapVectorsQ HashMap<String, Integi

n- mapVectors_Seq(HashMap<Strir>g, Integer*) vo

« n replace (int, MiningModeiElernent) vo

" Ь removefint) wo

f j getElerrKntfint) MiningModelElement

merge (List < MiningModelEiement>) void

О ъ cioneO Object

rr fa idO String

m □ propertiesToStringQ String

i distanced double

1,1 6 distance_$eq(double) void

m i merge(List<MiningModelEtement>) void

" "a idO String

m о addDistance(doubte) void

m createNewCopyElementQ VectorCluster

m propertiesToStringd String

я distance

double

*f a TAG_MAX_NUMBER_CLUSTERS String

*f a TAG.EPS String

it % S О MAI g о rit h m Settings 0

:p maxNumberOflterations int

: P eps double

£ SelfOrganizingMapAlgorithm

it Ь SelfOrganizingMapAlgorithmfSOMFunctionSettings)

it t initBiocksQ

it createModel(MininginputStream)

SelfQrganizingMapVerParailelAigorithm

ti SelfOrganizingMapVerParaltelAlgorithm(SOMFunctioriSettings)

initBlodsQ

createModel(MimnglnputStream)

Рисунок 4.1 - Базовые блок алгоритма Были реализованы следующие методы алгоритма:

ТпйКеигопБуКапёош - инициализация начального значения весов нейронов (случайным образом). Генератор псевдослучайных чисел определяет значение весов для каждого вектора. Возможен вариант

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

- Accumu1ateDistanceFromVectorToNeuron - определение суммы дистанций на основе указанной метрики для текущего нейрона.

- Ca1cu1ateDistanceFromVectorToNeuron - вычисление дистанции на основе полученной суммы после цикла Accumu1ateDistanceFromVectorToNeuron. Для Евклидовой метрики берется квадрат.

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

- AdjustNeuronWeights - обновление весов нейронов. Программную реализация методов алгоритма представлена на рисунке 4.2.

Рисунок 4.2 - Диаграмма классов методов алгоритма

На основе базовых блоков DXe1opes и реализованных методов на рисунке 4.3 представлено общая схема алгоритма.

MiningSequence

Инициализация нейронов

Обработка входного вектора данных

Рисунок 4.3 - Общая схема алгоритма кластеризации на основе нейронных

сетей Кохонена

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

Инициализация нейронов

MiningLoopElement INDEX_NEURONS

MiningLoopElement INDEX ATTRIBUTE SET

InitNeuronByRandom

Рисунок 4.4 - Схема вложения блоков для инициализации нейронов Используя описанные блоки можно представить код без параллелизации:

1. М1п^Бедиепсе(

2. MiningLoopElement(INDEX_NEURONS)(

3. MiningLoopElement(INDEX_ATTRIBUTE_SET)

4. (InitNeuronByRandom())

6. WhileChangeNeuronsLoop(

7. Мт^1_оорУес1:ог5(

8. MiningLoopElement(INDEX_NEURONS)(

9. MiningLoopElement(INDEX_ATTRIBUTE_SET)

10. (AccumulateDistanceFromVectorToNeuron()),

11. CalculateDistanceFromVectorToNeuron(),

12. ),

13. MiningLoopElement(INDEX_NEURONS)

14. (ChooseWinnerNeuron()),