Нейронный газ

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Деление нейрона с максимальной ошибкой в «расширяющемся нейронном газе»

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

История создания[править | править исходный текст]

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

Определение[править | править исходный текст]

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

Описание алгоритма[править | править исходный текст]

Начиная всего с двух нейронов, алгоритм последовательно изменяет (по большей части, увеличивает) их число, одновременно создавая набор связей между нейронами, наилучшим образом отвечающую распределению входных векторов. У каждого нейрона имеется внутренняя переменная, в которой накапливается «локальная ошибка». Соединения между узлами характеризуются переменной, называемой «возраст».[4]

  • Сперва создаются два узла (здесь и далее, узел=нейрон) с векторами весов, разрешенными распределением входных векторов, и нулевыми значениями локальных ошибок;
  • Узлы соединяются связью, которой можно установить возраст. На начальном этапе возраст равен 0.
  • Затем на вход нейросети подаётся вектор X.
  • На следующем этапе находятся два нейрона S и T, ближайших к X (S ближе, чем T), то есть узлы с векторами весов Ws и Wt, такими, что ||Ws — X|| - минимальное, а ||Wt- X|| - второе минимальное значение расстояния среди всех узлов.
  • Обновляется локальная ошибка, наиболее близкого нейрона — победителя S, к ней добавляется квадрат расстояния между векторами Ws и X.
                                             Е s → Е s+||Ws – X||2 
  • Эта процедура приводит к тому, что наиболее часто выигрывающие узлы, то есть те, в окрестности которых попадает наибольшее количество входных сигналов, имеют наибольшее значение ошибки, а значит, именно эти области становятся главными кандидатами на «уплотнение» путем добавления новых узлов.
  • Нейрон-победитель S и все его топологические соседи (то есть все нейроны N, имеющие соединение с победителем) смещаются в сторону входного вектора на расстояния, равные долям еw и еn от полного.
                                              Ws→ Ws + еw( Ws –X) 
                                              Wn→ Wn + еn( Wn –X) 

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

  • Увеличить на 1 возраст всех соединений, исходящих от победителя S.
  • Если два лучших нейрона S и T соединены, обнулить возраст их связи. В противном случае создать связь между ними.
  • Удалить все соединения, возраст которых превышает максимальный возраст. Если после этого имеются нейроны, не имеющие связей с другими узлами, удалить эти нейроны.
  • Если номер текущей итерации кратен ƛ, и предельный размер сети не достигнут, создать новый нейрон R по правилам. Со временем после нескольких циклов смещений накапливается информация, на основании которой принимается решение о месте, в котором должен быть добавлен новый нейрон. Этот процесс представляет собой коррекцию переменных ошибок всех нейронов слоя. Это необходимо для того, чтобы сеть «забывала» старые входные векторы и лучше реагировала на новые. Таким образом, достигается возможность использовать Расширяющийся нейронный газ для адаптации нейросети под нестационарные, а именно, медленно дрейфующие распределения входных сигналов.
  • Найти нейрон U с наибольшей локальной ошибкой.
  • Среди соседей U найти нейрон V с максимальной ошибкой.
  • Создать узел R «посередине» между U и V:
                                                   Wr= (Wu +Wv)/2  
  • Заменить связь между U и V на связи между U и R, R и V.
  • Уменьшить ошибки нейронов U и V , установить значение ошибки нейрона R.
                                                   Е u→ Е u ×a 
                                                   Е v→ Еv  ×a
  • Большое значение этой ошибки служит указанием на то, что соответствующий нейрон лежит в области небольшого числа нейронов.
  • Каждый раз, когда для случайно выбранного Х определяется ближайший к нему нейрон Wj, локальная ошибка для последнего Еj получает приращение ||Wj- X||2.

Форма структуры данных[править | править исходный текст]

Исследователь может сам задавать форму структуры кластеров, будет ли кластеризация выполнена для гиперсферы, гипертрубы или гиперплоскости. Если он не обладает этими знаниями, то благодаря значению собственной ковариационной матрицы можно определить необходимую форму. Если структура имеет хотя бы одно собственное значение меньше выбранного пользователем порога, то модель будет гиперлинейной, в противном случае структуру необходимо рассматривать как нелинейное многообразие. Дальнейшая проверка покажет является ли модель в форме сферы или трубы. Проверка на сферичность зависит от выполнения неравенства np/na>ψ, где np — это количество векторов внутри скопления, которое находится с помощью теоремы Жордана Брауера[5], а ap — площадь поверхности скопления и ψ — заданный пользователем порог. Если это неравенство приобретает форму np/na<ψ, то формой кластера будет «гипертруба».[4]

Расстояние от вектора Х до нейронов в кластерах разной формы[править | править исходный текст]

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

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

где Aj — это положительной, определённой матрица, посчитанная для для учёта эксцентриситета и ориентации гипертрубы[6]. Значение Aj для этого уравнения находится с помощью гиперлипсоида Лоунера, используя алгоритм Хачияна[7].

Для определения расстояний в гиперплоскости следует использовать следующую формулу: Формула для определения расстояний в гиперплоскости

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

Для определения расстояния в гиперсфере необходимо использовать формулу: Формула для определения расстояний в гиперсфере

где wi — либо среднее значение векторов, заключённых в плоскости.

Визуализация данных[править | править исходный текст]

В трёхмерном пространстве данные очень легко визуализировать.[4] Вы можете видеть это на рисунке.

Визуализация в 3d пространстве

Однако если наше пространство больше, чем трёхмерное, то визуализация данных затруднительна. Для решения этой задачи используется техника, основанная на VAT[8]. Суть построения заключается в том, что находится минимальное остовное дерево модели. После того как завершён процесс сортировки, структуру кластеров можно анализировать по квадратам около диагонали. Сперва происходит вычисление нормированных, попарно-различающихся нейронов в каждом изолированном графе. Затем различающиеся нейроны перестраиваются для того чтобы создать наиболее плотное внутрикластерное распределение. Затем каждый кластер окрашивается в свой цвет и размещается вдоль главной диагонали. Внутрикластерные отношения также включены в диаграмму, максимальное расстояние между двумя кластерами обозначено белым цветом, а чёрным — наименьшее расстояние. Объём кластера может быть добавлен как ещё одно измерение, это высота квадратов.

Решение проблем визуализации

Пример использования расширяющегося нейронного газа[править | править исходный текст]

Этот пример представлен для демонстрации того, как система адаптируется при вводе новых данных. База данных представляет собой 1050 объектов-точек. В начале было проведено 5000 итераций и в алгоритм попало 75 % информации. После того, как небольшая часть — 756 точек данных были введены в систему, нейронные векторы начали адаптироваться к формированию распределения, показанного на рисунке ниже. Последовательное выполнение алгоритма

После чего было запущено ещё 150 новых векторов. Это привело к формированию нового сферического класса, обозначенного на рисунке ниже: 4 кл

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

3 кл

Примечания[править | править исходный текст]

  1. Растущий нейронный газ — реализация на языке программирования MQL5
  2. Искусственные нейронные сети, [1]
  3. Словарь Neural.ru
  4. 1 2 3 Isaac J. Sledge,Growing Neural Gas for Temporal Clustering/IEEE, 2008
  5. M. Berg, M. Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry, Springer-Verlag, New York, 2000.
  6. G. Carpenter, «Competitive Learning: From Interactive Activation to Adaptive Resonance», Cognitive Science, vol. 11, 1987.
  7. L. Khachiyan, M. Todd, «On the Complexity of Approximating the Maximal Inscribed Ellipsoid for a Polytope», Math. Prog., 1993.
  8. J. Keller, I. Sledge, «A Cluster By Any Other Name», IEEE Proc., NAFIPS, 2007.

См. также[править | править исходный текст]

  1. T. Martinetz, Neural Gas Network for Vector Organization and its application to time-serias prediction/IEEE, vol. 4, 1993
  2. T. Martinetz, Neural Gas Network learns topologies.