Содержание к диссертации
Введение
1. Анализ алгоритмов кластерного анализа 11
1.1. Классические алгоритмы кластерного анализа 11
1.2. Модель синхронизации Курамото 24
1.3. Алгоритм кластеризации Sync 28
1.4. Иерархический алгоритм кластерного анализа hSync 36
1.5. Основные проблемы использования алгоритмов кластерного анализа 40
1.6. Выводы к главе 1 49
2. Осцилляторный метод кластеризации с кодированием входного пространства признаков 52
2.1. Архитектура разработанного метода Sync-SOM 52
2.2. Результаты экспериментов и анализ разработанного метода Sync-SOM 61
2.3. Многоядерная реализация второго слоя осцилляторной сети 72
2.4. Выводы по главе 2 76
3. Осцилляторный метод сегментации изображений с наращиванием слоев и кодированием входного пространства признаков 77
3.1. Архитектура разработанной осцилляторной сети 77
3.2. Результаты экспериментов и анализ метода сегментации 82
3.3. Выводы по главе 3 86
4. Библиотека pyclustering 88
4.1. Общее описание разработанного программного обеспечения 88
4.2. Непрерывная интеграция (Continues Integration) 92
4.3. Выводы к главе 4 95
Заключение 96
Список литературы
- Алгоритм кластеризации Sync
- Многоядерная реализация второго слоя осцилляторной сети
- Результаты экспериментов и анализ метода сегментации
- Непрерывная интеграция (Continues Integration)
Введение к работе
Актуальность темы исследования и степень ее проработанности Повсеместный и неуклонный рост объема данных в различных сферах деятельности человека вызывает необходимость разработки новых методов обработки и анализа данных с целью извлечения необходимой и полезной информации для ее дальнейшего использования. Это делает задачу кластерного анализа актуальной и вызывает потребность исследования существующих и разработку принципиально новых подходов и методов с учетом повышающихся требований.
Существующие методы по-прежнему имеют ряд ограничений, которые проявляются на практике, и их можно условно разделить на четыре группы.
-
Необходимость априорной информации о входных данных, что приводит к необходимости указания на входе алгоритма таких параметров, как истинное число кластеров, плотность данных, выражаемая радиусом связности.
-
Сложности с обеспечением максимального быстродействия за счет распределения или распараллеливания данных, которые не позволяют задействовать все вычислительные ресурсы параллельных систем.
-
Необходимость иметь весь объем обрабатываемых данных в оперативной памяти вычислительного устройства, что характерно для большинства подходов и алгоритмов.
-
Высокая сложность пост-обработки результатов кластеризации, делающая извлечение полезной информации из выходного результата дорогостоящей процедурой.
Ввиду вышеназванных ограничений особенно актуален биоинспирированный подход, имитирующий когнитивные функции головного мозга, которые в соответствие с рядом исследований по состоянию на сегодняшний день, реализуются процессами синхронизации (самоорганизацией) выходной динамики между нейронами, тем самым позволяя полностью распараллелить решение подобных задач, разрешая все неопределенности путем переключения механизмов внимания. На сегодняшний день большая часть моделей осцилляторных сетей именно имитируют работу нейронов без привязки к решению практических задач.
Математическая модель нейрона, описывающая динамику его работы и токи, протекающие в нем под внешним воздействием, была предложена А.Ходжкиным и Э.Хаксли. Эта модель является на сегодняшний день наиболее правдоподобной из существующих моделей, за что была отмечена нобелевской премией. Большой вклад в развитие теории осцилляторных сетей был внесен группой ученых, сосредоточенных именно на биологически правдоподобном моделировании работы и эволюции нейронных сетей на базе нейронов Ходжкина-Хаксли: Я.Казакевич, Р.Борисюк, Е.Тихонов. Ученые из этой группы смогли построить модель зрительной коры головного мозга, которая позволяет сегментировать простейшие изображения. Одна из известных моделей зрительной коры, способная сегментировать как монохромные, так и цветные изображения, была предложена Д.Вангом и Д.Терманом. Предложенная модель в своей основе использует осцилляторы Ван дер Поля и больше предназначена для решения уже практической задачи - сегментации изображений, а не для моделирования реальных процессов в головном мозгу. На практике моделирование данных сетей является ресурсоемкой задачей, поскольку динамика работы сетей описываются системами из нескольких дифференциальных уравнений. Также именно использование этих систем приводит к методам, имеющим ограничения по пост-обработке выходной динамики, поскольку для извлечения результатов работы сети требуется анализ динамики осцилляторов во временной плоскости, а соответственно необходимо либо хранение выходной динамики, либо ее анализ на каждом шаге моделирования.
На сегодняшний день существует ряд исследований, в которых утверждаетя, что именно процессы синхронизации являются фундаментом построения осцилляторных сетей, поскольку, согласно результатам этих исследований, именно процессы синхронизации, протекающие в головном мозгу, реализуют когнитивные функции, путем кодирования признаков входного пространства. Иными словами, каждый ансамбль синхронных между собой осцилляторов кодирует только один признак, к примеру, в случае задачи кластерного анализа каждый ансамбль кодирует только один кластер данных. В случае сегментации каждый ансамбль может
кодировать один из следующих признаков: цвет, объект, границу, яркость и т.п. Математическая модель синхронизации популяции осцилляторов, предложенная Е.Курамото, обеспечивает режим глобальной синхронизации в сети полностью связанных осцилляторов. Исследованием и развитием данной модели активно занимался коллектив ученых: Х.Асеброн, Л.Бонила, К.Висенти, Ф.Риторт, Р.Спиглер, С.Скардал, Х.Лоу, Дж.Сайкенс, А.Франци, Е.Васильева, М.Кузьмина, Э.Маныкин, И.Сурина, И.Блехман. На сегодняшний день проблема десинхронизации между осцилляторами и ансамблями осцилляторов в рамках модели Курамото является по-прежнему актуальной, поскольку именно за счет локальной (частичной) синхронизации осуществляется кодирование признаков входного пространства. Состояние сети по окончанию переходных процессов не является единственной отправной точкой для анализа результатов работы сети. При наличии дополнительной априорной информации анализ самой динамики сети во временной плоскости также позволяет извлечь дополнительные признаки из входного пространства, что в данном контексте дает право на относительно небольшую ошибку в параметрах настройки модели осцилляторной сети.
Единственным, эффективным способом обеспечения локальной синхронизации в осцилляторных сетях на базе Курамото, существующим на сегодняшний день, является ослабление или полный разрыв связей между ансамблями осцилляторов, кодирующих различные признаки. В противном случае система с течением времени может прийти к состоянию глобальной синхронизации и результаты могут быть утеряны, что потребует, как было отмечено раннее, непосредственного анализа выходной динамики во временной плоскости для извлечения требуемой информации, если связи не были равнозначными. На основании данного подхода с целью решения задач кластерного анализа модифицированные модели Курамото были предложены различными коллективами ученых независимо друг от друга: К.Бохмом, Я.Шао, К.Плант с одной стороны и Т.Мияно, Т.Тсуши с другой. Ограничениями данных методов кластеризации являются вычислительная сложность из-за кубической зависимости сходимости процесса синхронизации от данных в случае вытянутых, близкорасположенных кластеров, и необходимость наличия всех данных входного пространства в оперативной памяти. Это делает невозможным кластеризацию данных большого объема, при которой один нейрон ставится в соответствие только одному объекту из входного пространства.
Цель исследования - разработка нового метода кластерного анализа на базе осцилляторной нейронной сети для преодоления недостатков существующих методов и обеспечения параллельной реализации. Разрабатываемый метод должен позволять решать задачу как кластеризации, так и сегментации.
Задачи исследования
1. Выполнение аналитического обзора в области методов кластерного анализа: задачи
кластеризации и задачи сегментации для выявления возможных подходов преодоления недостатков существующих методов и определения путей их преодоления.
2. Разработка модели осцилляторной сети для решения задач кластерного анализа:
a. Кластеризация данных, решающая проблемы ресурсоемкости пост-
процессинга выходной динамики сети, а также проблемы использования сети
для анализа данных большого объема при невозможности их загрузки в
оперативное запоминающее устройство вычислительной машины.
b. Сегментация изображений для извлечения заданного количества признаков
входного пространства путем наращивания слоев сети и за счет кодирования
внешних стимулов.
3. Разработка параллельной архитектуры обобщенной модели осцилляторной сети для
решения задач кластерного анализа.
4. Разработка средств моделирования для исследования возможностей методов
кластерного анализа и сравнительного анализа.
Объектом исследования является модель синхронизации Курамото с фазовым осциллятором. Предметом исследования являются свойства осцилляторных сетей на базе модели Курамото и их адаптация к решению практических задач кластеризации и сегментации.
Научная новизна
1. Разработанный метод кластеризации не имеет ограничений по объему входных данных,
как большинство классических, так и био-инспирированных методов, тем самым обеспечивая высокое быстродействие за счет кодирования признаков входного пространства в первом слое.
2. Разработанный метод сегментации позволяет наращивать слои для извлечения
дополнительных признаков за счет кодирования внешних стимулов.
3. Предложенная обобщенная модель сети обеспечивает полностью параллельный режим
работы. Теоретическая значимость работы
1. Проведена систематизация знаний в области применения и адаптации моделей
осцилляторных сетей на базе модели Курамото для практического применения.
2. Предложен новый метод сегментации изображений, позволяющий варьировать
количество слоев в зависимости от необходимости выделения дополнительных признаков из уже выделенных предыдущими слоями. При этом нет жесткой привязки правил выделения признаков слоями, все правила определяются только методом кодирования входного пространства для каждого слоя в отдельности, тем самым обеспечивая универсальность сети - одна и та же сеть может сегментировать изображение по разным признакам. Таким образом, процесс сегментации развивается от анализа макро-признаков к анализу микро-признаков, предоставляя возможность снимать результаты с любого из слоев, что имеет значение для развития теории обработки данных и теории осцилляторных сетей, позволяя приблизиться к построению зрительной коры головного мозга.
3. Предложенный подход кодирования данных в первом слое применим во всех моделях
осцилляторных сетей, предназначенных для обработки информации, и в которых допускается кодирование входного пространства, при этом сохраняется возможность параллельной реализации осцилляторной сети. Практическая значимость работы
1. Предложен новый метод кластеризации данных, позволяющий кодировать в первом
слое входные данные, последовательно загружая и выгружая обработанные порции данных в оперативную память и тем самым сокращая размерность входного пространства, увеличивая скорость сходимости процесса синхронизации выходного слоя. Это дает возможность существенно сократить время самого процессе кластеризации.
2. Предложена параллельная обобщенная модель осцилляторной сети, обеспечивающая
параллельное исполнение на многопроцессорных станциях и увеличивающая быстродействие, что дает возможность задействовать осцилляторные сети для решения практических задач.
3. Разработана полноценная библиотека, доведенная до состояния продуктового кода,
для моделирования осцилляторных сетей, анализа выходной динамики сетей и
сравнения моделей с другими широко распространёнными алгоритмами
кластеризации, а также тестирования возможностей кластерного анализа
синтезируемых алгоритмов. Разработанная библиотека руclustering находится в
открытом доступе репозитория github и зарегистрирована в официальном python
сообществе рурі. Библиотека может быть использована как в учебных целях, так и для
проведения НИР.
Положения, выносимые на защиту
1. Метод кластерного анализа с кодированием входного пространства в первом слое (самоорганизующейся карте признаков) для обработки данных без полной загрузки их
в оперативную память вычислительного устройства, что позволяет существенно увеличить производительность обработки информации.
2. Метод сегментации изображений с варьированием количества слоев в осцилляторной
сети, позволяющий выполнять иерархическую сегментацию с наращиваемым числом
признаком, что существенно увеличивает возможности метода по выявлению
особенностей объектов изображения.
3. Новый подход к моделированию параллельно исполняемых осцилляторов на
многопроцессорных вычислительных устройствах на примере осцилляторной сети с фазовым осциллятором на базе модели Курамото, что решает проблему обеспечения приемлемого времени обработки данных большой размерности и объема. Методология и методы исследования. В работе использованы методы теории вероятностей и математической статистики, системного анализа, теории моделирования, теории динамических систем.
Внедрение и реализация результатов работы. Основные результаты диссертации были внедрены в исследовательский R&D центр Nokia для анализа и визуализации типов трафика в мобильных беспроводных сетях, что подтверждается актом о внедрении.
Степень достоверности и апробация результатов. Основные результаты диссертации докладывались и обсуждались на 6-ти конференциях, из них на 4-х международных конференциях:
-
The 11th International Conference "Pattern Recognition and Image Analysis: New Information Technologies" (2013);
-
3rd International Conference on Pattern Recognition Applications and Methods (2014);
-
Parallel Computing Technologies - 13th International Conference (2015);
-
13th International Symposium on Neural Networks (2016),
а также на Всероссийской научной конференция по проблемам информатики (2013) и на Молодёжной научной конференции «Студенты и молодые учёные - инновационной России» (2013).
Результаты работы отмечены дипломом правительства Санкт-Петербурга победителю конкурса грантов Санкт-Петербурга для студентов и аспирантов (2014).
Публикации. По теме диссертационной работы опубликованы 10 печатных работ, из них 3 - в изданиях «Перечня ВАК» и 5 - в изданиях, индексируемых Scopus и Web Of Science.
Объем и структура работы. Диссертация состоит из введения, 4 глав, заключения и 1 приложения. Список использованной литераторы содержит 63 наименования. Основной текст диссертации содержит 105 страниц машинописного текста, включая 44 рисунка, 5 таблиц.
Алгоритм кластеризации Sync
BIRCH алгоритм относится к семейству иерархических, который также кодирует входное пространство признаков путем использования CF-дерева. Входными параметрами являются: число кластеров, которые должны быть извлечены и параметры используемого CF-дерева. Данный способ кодирования будет рассмотрен далее. Отличительным достоинством является масштабирование и возможность работы с реальными базами данных без загрузки их в оперативную память устройства. Недостатком является описание кластеров, как сферических объектов (центр, радиус, диаметр), что сужает возможности по использованию. Алгоритм успешно справляется с решением задач, в которых кластеры имеют или могут быть описаны сферической формой, например, Hepta, TwoDiamonds.
CLARANS является рандомизированным алгоритмом, который позволяет повысить эффективность алгоритма PAM (известный также как K-Medoids) путем случайного поиска минимума заданное пользователем количество раз. Входными параметрами алгоритма являются: число кластеров, которое должно быть извлечено, число итераций для поиска минимумов и число объектов-соседей, которые должны быть проанализированы на предмет возможного минимума. На каждой итерации алгоритма, когда извлечены кластеры, осуществляется оценка кластеров с помощью функции качества. Достоинством является то, что отпадает необходимость делать оценку для каждого из объектов входного пространства, что увеличивает производительность, но это же и является недостатком, поскольку могут быть извлечены кластеры, описываемые псевдо-локальными минимумами. Кроме того, алгоритм наследует возможности K-Medoids и способен работать с данными, в которых кластеры имеют сферическую форму с равномерным или Гаусовым распределением. Недостатком является наличие вероятности, при которой решение задачи не достигнет глобального минимума, то есть результаты кластеризации будут не корректными: содержать ошибку второго рода – объекты неверно соотнесены по кластерам.
Алгоритм CURE является представителем иерархической кластеризации. Каждый кластер описывается точками-представителями в пространстве признаков координатами, которые не являются объектами входного пространства и центром кластера. Точки-представители описывают форму кластера в пространстве признаков. За счет этого алгоритм является чем-то средним между алгоритмами, базирующихся на центрах кластеров и поиска экстремумов на базе всего объема данных. Входными параметрами алгоритма являются: число кластеров, которое должно быть извлечено, число точек-представителей в каждом кластере, коэффициент сжатия для разброс точек. На начальном этапе, как и в большинстве агломеративных иерархических алгоритмов, количество кластеров соответствует количеству объектов во входном пространстве, то есть каждый кластер содержит один объект, которой является центром, точкой-представителем и точкой-разбросом. На каждом шаге объединяются кластеры с ближайшими парами точек-представителей в евклидовом пространстве до тех пор, пока не будет достигнуто требуемое число кластеров. Объединение центров m кластеров не требует перерасчета всех данных [28]: mобъед = (1-1) Точки-представители rep при объединении рассчитываются следующим образом [28]: repобы = repобы {xi + а(meanобьед -xi)} (1.2) Достоинствами алгоритма является способность решать задачу кластеризации не только с данными, в которых кластеры имеют сферическую форму, как для большинства алгоритмов, базирующихся на использовании центров, но также с данными, имеющими вытянутую форму, хотя и с некоторыми ограничениями, к примеру, CURE успешно решает задачу на таких выборках, как Lsun, Target, TwoDiamonds, WingNut, но не способен решить задачу на таких выборках, как Atom или Chainlink.
DBSCAN алгоритм относится к семейству, базирующихся на плотности данных. В качестве входных данных используется радиус связности и минимальное число общих соседей между двумя узлами, требуемое для того, чтобы соединить эти узлы. Каждый узел ставится в соответствие только одному объекту, используя его описание в пространстве признаков. На начальном этапе, случайным образом выбирается узел, с которого начнется обход данных и формирование графов. Для выбранного узла вычисляется число соседей, с которыми он может быть соединен, если число соседей больше порогового, то данные соседи помещаются в очередь для дальнейшего обхода, иначе, узел помечается, как шум и осуществляется переход к анализу следующего узла. Таким образом, все узлы принадлежат одному кластеру, если удается их обойти, удовлетворяя условиям алгоритма. Обходятся только те узлы, которые были добавлены в очередь. Добавляются в кластер только те узлы, которые удовлетворили условиям, соответственно соседи каждого помещенного в кластер узла добавляются в очередь для дальнейшего анализа. Как только очередь становится пустой, то кластер считает полностью сформированным и далее начинается новый обход с узла, который еще не был проанализирован, до тех пор, пока все данные не будет обработаны.
Достоинством алгоритма является высокое быстродействие и возможность извлечения кластеров различных форм и плотностей: задача кластеризации успешно решается на всех выборках FCPS. Недостатком является использование радиуса связности и высокая зависимость корректности результатов на данных с вытянутыми кластерами, которые близко расположены друг к другу. К примеру, для нахождения верных параметров алгоритма на выборке TwoDiamonds пришлось автоматизировать процесс поиска, поскольку получение верной экспертной оценки визуальным анализом является нетривиальной задачей. Для выборок TwoDiamonds и WingNut малое изменение входных параметров алгоритма (радиус связности , минимальное число соседей N) ведет к существенным изменениям результатов кластеризации – рисунок 1.2.
Многоядерная реализация второго слоя осцилляторной сети
В данном примере для осциллятора с индексом 1 рассчитывается евклидово расстояние до каждого осциллятора в сети, поскольку расстояние до осцилляторов с индексами 2, 3 и 4 меньше порогового , то от осциллятора 1 устанавливаются с ними связи. Аналогичная процедура повторяется для каждого последующего осциллятора, пока связи для всех осцилляторов сети не будут рассчитаны.
Алгоритмы и методы, использующие в своей основе осцилляторные сети, требуют наличия оценки того, когда процесс симуляции завершен, который в данном случае рассматривается как процесс решения практической задачи. Признаком окончания процесса симуляции является некоторое устойчивое состояние на выходе динамической системы. В осцилляторной сети Sync таким признаком является установившееся состояние фаз осцилляторов. В отличие от классической модели Курамото в (1.10) отсутствует внутренняя частота осциллятора со, которую грубо можно рассматривать, как коэффициент смещения, наличие данного компонента в уравнении приводит к дрейфу фаз осцилляторов для популяции N 2. Таким образом, одним из способов оценки окончания процесса синхронизации является отсутствие изменения фаз #г в пределах некоторой погрешности а для каждого /-го осциллятора на двух различных шагах (к примеру, на к и к- 1) симуляции сети:
Очевидным достоинством данного подхода оценки завершения процесса симуляции является простота. Недостатком необходимость использовать корректного значения порога изменений ег, поскольку в сетях с различной связностью и размерностью данный порог будет разным. К примеру, в полностью связной сети малого размера пороговое значение может быть существенно большим по отношению пороговому значению в сети с прореженными связями большого размера. Обуславливается это скоростью процесса синхронизации, как было это представлено раннее, то есть в сети с прореженными связями изменение разности фаз осциллятора ві на текущем к и предыдущем к- 1 шаге существенно меньше. Попытка использовать очень малое пороговое значение а приведет лишь к лишним шагам симуляции осцилляторной сети, то есть вычислительные ресурсы будут использоваться впустую.
Существует более формальная оценка состояния локальной синхронизации в осцилляторной сети, которая используется в качестве условия останова симуляции сети [15, 44]: г = с 1 Ъеоге, (1.18) Данная оценка лежит в промежутке от 0 до 1, в случае rc 0 имеет место десинхронизация между осцилляторами, в случае rc 1 в сети наблюдается состояние локальной синхронизации. В ходе симуляции данная оценка будет увеличиваться с каждым шагом. Таким образом, процесс кластеризации можно считать завершенным, когда оценка локальной синхронизации гс 0. Явным достоинством оценки гс является определение точного момента остановки решения - достижения требуемого уровня локальной синхронизации в сети, что позволяет не делать лишних шагов симуляции в отличие от оценки (1.17).
Одним из достоинств модифицированной модели Курамото заключается в возможности использовать метод Эйлера с единичным шагом для решения дифференциального уравнения (1.16) без потери сходимости, что существенно снижает время симуляции осцилляторной сети. Все эксперименты, проводимые далее в данной главе, используют именно данный метод решения [49]: в,[к]=ф-1]+- Isinfo,[ -l]- ([ -lD. (1-І»)
Основная проблема алгоритма заключается в правильности выбора радиуса связности между осцилляторами (входного параметра сети), которые ставятся в прямое соответствие объектам, что по сути напоминает вырожденные алгоритмы DBSCAN [23] и OPTICS [9], где параметр, определяющий количество общих соседей для принятия решения, равен нулю, то есть решение достижимости одного объекта другим принимается только на основании радиуса связности. Как было отмечено раннее модель Курамото имеет кубическую зависимость времени синхронизации в случае двунаправленных списков, и таким образом анализ вытянутых кластеров, расположенных на малом удалении друг от друга, накладывает ограничение на радиус связности между осцилляторами в Sync алгоритме и как следствие ведет к кубической сложности в достижении состояния синхронизации между осцилляторами.
После формирования связей между осцилляторами запускается процесс симуляции работы осцилляторной сети до тех пор, пока не будет достигнут указанный уровень локальной синхронизации, который обычно задается из промежутка (0.99 -0.999). Чем выше уровень локальной синхронизации, тем дольше идет процесс достижения указанного уровня синхронизации в сети, однако, высокий уровень гс позволяет упросить анализ выходной динамики. Поясним данное утверждение: выходное значение осциллятора / из кластера к соответствует вк ± ег, где вк среднее значение фазы самого ансамбля синхронных осцилляторов, соответствующего кластеру К а є,- - отклонение от среднего значения фазы ансамбля вк. Таким образом, при гс 1, ег- 0, следовательно, #г ви для каждого осциллятора / из ансамбля к, что соответственно упрощает вычисление ансамблей синхронных осцилляторов. Малые значения уровня локальной синхронизации гс (на практике это может быть гс = 0.9) являются следствием высоких значений е, что может привести к пересечению границ разброса фаз двух и более ансамблей (вк ± є,) (вк+х ± ej) … (вк+п ± ет). В этом случае потребуется анализ выходной динамики осцилляторов на предыдущих шагах моделирования с целью вычисления корреляции между ними для определения истинного числа кластеров, что в свою очередь усложнит непосредственно сам анализ результатов сети.
Тем не менее, есть отличия от вырожденного случая с DBSCAN, когда используется неверный радиус связности, на котором и принимается решение о достижимости объектами друг друга. Если радиус связности превышает истинный, то DBSCAN выделит меньшее количество кластеров от истинного. В случае использования осцилляторной сети имеется возможность провести анализ выходной динамики, напоминающий анализ дендограммы. Если известно истинное число кластеров, то они могут быть корректно выделены, в случае близких по весу данных, составляющих кластеры. Иллюстрация описанного подхода представлена на рисунке 1.11.
В представленном примере на рисунке 1.11(a) радиус связности X = 0.5 выше истинного Хист. = 0.25, из-за чего сформирована одна сеть, симуляция которой приведет в конечном счете к состоянию глобальной синхронизации. Осцилляторная сеть содержит две подсети, которые имеют огромное число локальных связей, вследствие чего обе подсети выглядят как сплошные ромбы. В тоже самое время две подсети имеют некоторое число связей между собой, которых меньше, чем внутренних. Таким образом, зная, что необходимо извлечь два кластера, то есть появляется дополнительный (второй) входной параметр алгоритма, осцилляторная сеть успешно справляется со своей задачей за счет анализа выходной динамики осцилляторной сети, как это показано на рисунке 1.11(b).
Результаты экспериментов и анализ метода сегментации
Рассмотрим каждое из правил в отдельности. Вычисление средней дистанции для соединения N-го количество осцилляторов во втором слое подразумевает использование N (числа осцилляторов или процента осцилляторов в сети) в качестве входного параметра. Связи между осцилляторами устанавливаются в том случае, если между нейронами входного слоя отсутствуют «мертвые» нейроны и евклидово расстояние между ними меньше, чем среднее расстояние между 10-20% осцилляторов. Под «мертвыми» понимаются нейроны, которые не смогли выиграть ни единого объекта на последней итерации самоорганизации входного слоя. Однако количество нейронов-победителей в первом слое не должно быть менее 10-20% от их общего числа, иначе связи между осцилляторами не устанавливаются, поскольку на входе имеют место кластеры сферической формы, которые удалены друг от друга и вся задачи кластеризации решается первым слоем. Пример кодирования входного пространства первым слоем, активация осцилляторов второго слоя с формированием связей между ними и результатами синхронизации представлена на рисунке 2.3
Недостатком данного подхода является необходимость иметь сведения (априорную информацию) о пространстве входных признаков. Использование диаграммы Делоне для автоматического расчета параметров сети, как это было показано авторами в работе [12, 13, 14] на примере хаотической нейронной сети CNN для кластерного анализа, неприменимо для данной сети, поскольку образованные связи между осцилляторами приведут к глобальной синхронизации. Немаловажным является факт, что рассмотренное правило может привести к слабой связности сети, что в свою очередь приведет к кубической зависимости процесса синхронизации от количества активных осцилляторов во втором слое. Однако в данной модели это не является критическим, ввиду того, что входное пространство полностью кодируется в первом слое и нет необходимости соответствия числа осцилляторов числу объектов входного пространства. Сильная зависимость от первого слоя требует увеличения размерности карты с целью избежать неправильного расчета радиуса связности, поскольку, если сеть имеет малую размерность, то малое изменение входного параметра ведет к существенным изменениям результатов кластеризации. Кроме того, малая размерность может является следствием равноудаленного размещения нейронов в первом слое, что даст на выходе два возможных результата: глобальная синхронизация – один кластер, локальная синхронизация – количество кластеров будет соответствовать количеству осцилляторов. На рисунке 2.3 представлен пример описанной ситуации.
Использование классического радиуса связности подразумевает соединение осцилляторов во втором слое только в том случае, если соответствующие им объекты соединяются между собой. Данный подход подразумевает использование радиуса связности в качестве входного параметра и требует обхода всей базы данных на этапе формирования связей, однако существенно улучшает результаты кластеризации, приближая по качеству кластеризации метод Sync-SOM к таким алгоритмам, как DBSCAN, OPTICS, CURE, позволяя уйти от слабой связности. Недостатком, также, как и в предыдущем случае является необходимость знать плотность распределения данных во входном пространстве.
Третье правило позволяет заменить одну априорную информацию на другую. По завершению процесса самоорганизации (обучения) в первом слое, в каждой области покрытия рассчитывается радиус связности, захваченных нейроном объектов, что также требует обход всей базы данных. На основании U-матрицы делается вывод о радиусе связности в данной конкретной области нейрона. Полученная дистанция также определяет могут ли быть соединены объекты данной области с соседними, если могут, то связь между осцилляторами второго слоя устанавливается. Однако использование данного правила сталкивается с целой предметной областью, в которой до сих пор ведутся исследования, о том, какой подход использовать для вычисления радиуса-связности на базе U-матрицы (матрицы дистанций) или P-матрицы (матрицы плотности). Подходы, которые автоматически рассчитывают нейроны, которые относятся к одним и тем же кластерам, имеют ряд недостатков, связанным с тем, что они ориентированы на определенные формы кластеры и их распределения. По сути данную проблему можно также рассмотреть, как задачу кластеризации, в которой необходимо выявить нейроны, кодирующие одни и те же признаки. В случае, если имеется дополнительная априорная информация, такая как число кластеров во входном пространстве, которое должно быть извлечено, то радиус связности может быть вычислен автоматически (происходит замена одного параметра другим). Это позволяет дать пользователю больше свободы действий: использовать либо радиус связности, либо число кластеров.
Метод Sync-SOM использует второе и третье правило, в зависимости, от априорной информации, имеющейся у пользователя в распоряжении. Первое правило не используется ввиду сложности оценки даже с точки зрения эксперта, поскольку даже глядя на простую выборку не всегда можно ответить на вопрос, каким должно быть число осцилляторов для вычисления средней дистанции между ними, в отличие от радиуса связности или непосредственно числа кластеров.
Непрерывная интеграция (Continues Integration)
Задачу сегментации можно рассматривать также с точки зрения кластерного анализа, в данном случае, каждый цвет с оттенками или без являет собой отдельный кластер на изображении. Аналогично и в случае сегментации изображения по объектам, когда необходимо выделить отдельно стоящие объекты, к примеру, буквы на листе бумаги или фрукты на столе. В данном случае с точки зрения кластерного анализа каждый объект рассматривается как отдельный кластер. Существует также сегментация краев объектов на изображении (наиболее известным представителем в этой области является PCNN сеть [26, 42], которая за счет своей простоты и эффективности заслужила наибольшее распространение).
Формально задачу сегментации можно сформулировать как процесс разбиения цифрового изображения на несколько сегментов (множеств пикселей). Целью сегментации является изменение представления изображения (упрощения) с целью его последующего анализа, к примеру, распознавания каждого объекта в отдельности, анализа сцены и принятия решения на основе полученных данных.
В данной главе предлагается осцилляторный метод сегментации изображений с использованием метода Sync-SOM для сжатия входного пространства. В данной главе будет представлена сегментация изображения по цвету и по объектам. Основной проблемой для осциллляторных алгоритмов в данной области также является ресурсоемкость как по вычислительным ресурсам, так и по памяти, которая требуется для решения задачи, что затрудняет использование осцилляторных алгоритмов на практике. К примеру, при матричном представлении связей, используя тип «целое» (32 бита), для изображения 64x64 — число связей 16.7 млн., что соответствует 66.8 Мб оперативной памяти. Для осцилляторной сети LEGION [58, 59] имеет смысл использовать списки связей, при наличии статических и динамических связей с соседями по двух-мерной для каждого осциллятора число связей для изображения 64x64 требует 65Кб и зависимость потребления памяти имеет линейный характер, однако ввиду малого количества связей увеличивается время синхронизации между осцилляторами, принимая во внимание тот факт, что сеть LEGION описывается даже в упрощенном варианте системой из двух дифференциальных уравнений и требует расчета потенциала, глобального ингибитора, состояния динамических связей и генерации шума на каждом шаге для каждого осциллятора.
В базовом варианте предлагаемого метода сеть содержит два слоя. Первый слой необходим для извлечения цветовых сегментов и активации групп осцилляторов во втором слое. Второй слой предназначен для извлечения объектов на изображении под воздействием первого слоя, активность которого воздействует на силу связей между осцилляторами второго слоя, а также используя описание удаленности пикселей друг от друга (положение пикселей или группы пикселей в пространстве координат изображения). Общее число осцилляторов в каждом слое определяется числом пикселей или областей, которые кодируются входным слоем сети Sync-SOM. Осцилляторы первого слоя активируют осцилляторы второго путем групповой синхронизации, когда группа синхронных осцилляторов первого слоя активирует соответствующую группу осцилляторов во втором слое, которая взаимодействует только между собой за счет усиления связей между собой и за счет ослабления связей с другими осцилляторами второго слоя. В случае многослойной сети данное правило распространяется на все слои, когда слой N активирует группы осцилляторов в слое N + 1, прямо влияя на связи между осцилляторами в N + 1 слое. Важно отметить, что первый слой имеет один кодирующий слой, в то время как в случае со вторым слоем сети (извлечение объектов) каждая активированная группа осцилляторов имеет собственный кодирующий слой. Немаловажным фактом является то, что размер кодирующего слоя должен быть больше, чем число объектов или цветов на изображении. В случае если объекты (случай для второго слоя сети), которые необходимо извлечь, расположены очень близко, что характерно для маленьких изображений, то следует использовать либо большого размера кодирующий слой, либо отказаться от него, иначе объекты могут быть извлечены неверно (вероятность ошибки как первого рода, так и второго). Архитектура осцилляторной сети представлена на рисунке 3.1.
Архитектура двухслойной осцилляторной сети с кодирующими промежуточными слоями для сегментации изображений по цветным объектам. Связи между осцилляторами формируются в ходе симуляции осцилляторной сети и в соответствии с внешними стимулами — признаками обрабатываемого изображения. Внешние стимулы зависят от параметра «сходства», рассматриваемого признака в каждом конкретном слое. Для конкретно рассматриваемой модели имеется два типа признаков: цвет и удаленность пикселя или группы пикселей. Соответственно предлагаемый метод имеет четыре основных параметра, два из которых опциональны: