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

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

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

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

• Сперва создаются два узла (здесь и далее, узел=нейрон) с векторами весов, разрешенными распределением входных векторов, и нулевыми значениями локальных ошибок;
• Узлы соединяются связью, которой можно установить возраст. На начальном этапе возраст равен 0.
• Затем на вход нейросети подаётся вектор ${\displaystyle {\vec {X}}}$.
• На следующем этапе находятся два нейрона ${\displaystyle S}$ и ${\displaystyle T}$, ближайших к ${\displaystyle {\vec {X}}}$ (${\displaystyle S}$ ближе, чем ${\displaystyle T}$), то есть узлы с векторами весов ${\displaystyle {\vec {W_{s}}}}$ и ${\displaystyle {\vec {W_{t}}}}$, такими, что ${\displaystyle \left\|{\vec {W_{s}}}-{\vec {X}}\right\|}$ - минимальное, а ${\displaystyle \left\|{\vec {W_{t}}}-{\vec {X}}\right\|}$ — второе минимальное значение расстояния среди всех узлов.
• Обновляется локальная ошибка наиболее близкого нейрона — победителя ${\displaystyle S}$, к ней добавляется квадрат расстояния между векторами ${\displaystyle {\vec {W_{s}}}}$ и ${\displaystyle {\vec {X}}}$.

  ${\displaystyle E_{s}\Rightarrow E_{s}+\left\|{\vec {W_{s}}}-{\vec {X}}\right\|^{2}}$

• При реализации этой процедуры наиболее часто выигрывающие узлы (в их окрестности попадает максимальное число входных сигналов) получают наибольшее значение ошибки. Эти области «уплотняются» в первую очередь и происходит это за счеёт добавления новых узлов.
• Нейрон-победитель ${\displaystyle S}$ и все его топологические соседи (то есть все нейроны ${\displaystyle N}$, имеющие соединение с победителем) смещаются в сторону входного вектора на расстояния, равные долям ${\displaystyle \varepsilon _{w}}$ и ${\displaystyle \varepsilon _{n}}$ от полного.

  ${\displaystyle {\vec {W_{s}}}\Rightarrow {\vec {W_{s}}}+\varepsilon _{w}({\vec {W_{s}}}-{\vec {X}})}$

  ${\displaystyle {\vec {W_{n}}}\Rightarrow {\vec {W_{n}}}+\varepsilon _{n}({\vec {W_{n}}}-{\vec {X}})}$

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

• Увеличить на 1 возраст всех соединений, исходящих от победителя ${\displaystyle S}$.
• Если два лучших нейрона ${\displaystyle S}$ и ${\displaystyle T}$ соединены, то требуется обнулить возраст их связи. Иначе нужно создать связь между ними.
• Удалить все связи, возраст которых превышает максимальный возраст. Нейроны, у которых нет связей с другими узлами удаляются.
• Если номер текущей итерации кратен ${\displaystyle \lambda }$, и предельный размер сети не достигнут требуется создать новый нейрон ${\displaystyle R}$ по правилам. Со временем после нескольких циклов смещений накапливается информация, на основании которой принимается решение о месте, в котором должен быть добавлен новый нейрон. В ходе этого процесса происходит коррекция переменных ошибок всех нейронов слоя. В результате этого сеть «забывает» старые входные векторы и лучше реагирует на новые. Появляется возможность использования Расширяющегося нейронного газа для подстройки нейросети под медленно дрейфующие распределения входных сигналов.
• Найти нейрон ${\displaystyle U}$ с максимальной локальной ошибкой.
• Среди соседей ${\displaystyle U}$ найти нейрон ${\displaystyle V}$ с самой большой ошибкой.
• Создать узел ${\displaystyle R}$ «посередине» между ${\displaystyle U}$ и ${\displaystyle V}$:

  ${\displaystyle {\vec {W_{r}}}={\frac {{\vec {W_{u}}}+{\vec {W_{v}}}}{2}}}$

• Заменить связь между ${\displaystyle U}$ и ${\displaystyle V}$ на связи между ${\displaystyle U}$ и ${\displaystyle R}$, ${\displaystyle R}$ и ${\displaystyle V}$.
• Уменьшить ошибки нейронов ${\displaystyle U}$ и ${\displaystyle V}$, установить значение ошибки нейрона ${\displaystyle R}$.

  ${\displaystyle E_{u}\Rightarrow E_{u}*a}$

  ${\displaystyle E_{v}\Rightarrow E_{v}*a}$

  ${\displaystyle E_{r}\Rightarrow E_{u}}$

• Большое значение этой ошибки служит указанием на то, что соответствующий нейрон лежит в области небольшого числа нейронов.
• Каждый раз, когда для случайно выбранного ${\displaystyle X}$ определяется ближайший к нему нейрон ${\displaystyle {\vec {W_{j}}}}$, локальная ошибка для последнего ${\displaystyle E_{j}}$ получает приращение ${\displaystyle \left\|{\vec {W_{j}}}-{\vec {X}}\right\|^{2}}$.

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

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

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

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

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

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

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

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

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

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

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

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

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.