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

18.12.2020

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

История создания

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

Определение

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

Описание алгоритма

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

  • Сперва создаются два узла (здесь и далее, узел=нейрон) с векторами весов, разрешенными распределением входных векторов, и нулевыми значениями локальных ошибок;
  • Узлы соединяются связью, которой можно установить возраст. На начальном этапе возраст равен 0.
  • Затем на вход нейросети подаётся вектор X → {displaystyle {vec {X}}} .
  • На следующем этапе находятся два нейрона S {displaystyle S} и T {displaystyle T} , ближайших к X → {displaystyle {vec {X}}} ( S {displaystyle S} ближе, чем T {displaystyle T} ), то есть узлы с векторами весов W s → {displaystyle {vec {W_{s}}}} и W t → {displaystyle {vec {W_{t}}}} , такими, что ‖ W s → − X → ‖ {displaystyle left|{vec {W_{s}}}-{vec {X}} ight|} - минимальное, а ‖ W t → − X → ‖ {displaystyle left|{vec {W_{t}}}-{vec {X}} ight|} — второе минимальное значение расстояния среди всех узлов.
  • Обновляется локальная ошибка наиболее близкого нейрона — победителя S {displaystyle S} , к ней добавляется квадрат расстояния между векторами W s → {displaystyle {vec {W_{s}}}} и X → {displaystyle {vec {X}}} . E s ⇒ E s + ‖ W s → − X → ‖ 2 {displaystyle E_{s}Rightarrow E_{s}+left|{vec {W_{s}}}-{vec {X}} ight|^{2}}
  • Эта процедура приводит к тому, что наиболее часто выигрывающие узлы, то есть те, в окрестности которых попадает наибольшее количество входных сигналов, имеют наибольшее значение ошибки, а значит, именно эти области становятся главными кандидатами на «уплотнение» путём добавления новых узлов.
  • Нейрон-победитель S {displaystyle S} и все его топологические соседи (то есть все нейроны N {displaystyle N} , имеющие соединение с победителем) смещаются в сторону входного вектора на расстояния, равные долям ε w {displaystyle varepsilon _{w}} и ε n {displaystyle varepsilon _{n}} от полного. W s → ⇒ W s → + ε w ( W s → − X → ) {displaystyle {vec {W_{s}}}Rightarrow {vec {W_{s}}}+varepsilon _{w}({vec {W_{s}}}-{vec {X}})} W n → ⇒ W n → + ε n ( W n → − X → ) {displaystyle {vec {W_{n}}}Rightarrow {vec {W_{n}}}+varepsilon _{n}({vec {W_{n}}}-{vec {X}})}

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

  • Увеличить на 1 возраст всех соединений, исходящих от победителя S {displaystyle S} .
  • Если два лучших нейрона S {displaystyle S} и T {displaystyle T} соединены, обнулить возраст их связи. В противном случае создать связь между ними.
  • Удалить все соединения, возраст которых превышает максимальный возраст. Если после этого имеются нейроны, не имеющие связей с другими узлами, удалить эти нейроны.
  • Если номер текущей итерации кратен λ {displaystyle lambda } , и предельный размер сети не достигнут, создать новый нейрон R {displaystyle R} по правилам. Со временем после нескольких циклов смещений накапливается информация, на основании которой принимается решение о месте, в котором должен быть добавлен новый нейрон. Этот процесс представляет собой коррекцию переменных ошибок всех нейронов слоя. Это необходимо для того, чтобы сеть «забывала» старые входные векторы и лучше реагировала на новые. Таким образом, достигается возможность использовать Расширяющийся нейронный газ для адаптации нейросети под нестационарные, а именно, медленно дрейфующие распределения входных сигналов.
  • Найти нейрон U {displaystyle U} с наибольшей локальной ошибкой.
  • Среди соседей U {displaystyle U} найти нейрон V {displaystyle V} с максимальной ошибкой.
  • Создать узел R {displaystyle R} «посередине» между U {displaystyle U} и V {displaystyle V} : W r → = W u → + W v → 2 {displaystyle {vec {W_{r}}}={frac {{vec {W_{u}}}+{vec {W_{v}}}}{2}}}
  • Заменить связь между U {displaystyle U} и V {displaystyle V} на связи между U {displaystyle U} и R {displaystyle R} , R {displaystyle R} и V {displaystyle V} .
  • Уменьшить ошибки нейронов U {displaystyle U} и V {displaystyle V} , установить значение ошибки нейрона R {displaystyle R} . E u ⇒ E u ∗ a {displaystyle E_{u}Rightarrow E_{u}*a} E v ⇒ E v ∗ a {displaystyle E_{v}Rightarrow E_{v}*a} E r ⇒ E u {displaystyle E_{r}Rightarrow E_{u}}
  • Большое значение этой ошибки служит указанием на то, что соответствующий нейрон лежит в области небольшого числа нейронов.
  • Каждый раз, когда для случайно выбранного X {displaystyle X} определяется ближайший к нему нейрон W j → {displaystyle {vec {W_{j}}}} , локальная ошибка для последнего E j {displaystyle E_{j}} получает приращение ‖ W j → − X → ‖ 2 {displaystyle left|{vec {W_{j}}}-{vec {X}} ight|^{2}} .

Форма структуры данных

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

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

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

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

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

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

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

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

Визуализация данных

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

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

Пример использования расширяющегося нейронного газа

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

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

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



Имя:*
E-Mail:
Комментарий: