Revision 45285698 of "Нейронный газ" on ruwiki

[[Файл:Нейронный газ.gif|thumb|Деление нейрона с максимальной ошибкой в "растущем нейронном газе"]]


Нейронный газ  – это алгоритм, позволяющий осуществлять адаптивную кластеризацию входных данных, т.е. не только разделить пространство на кластеры, но и определить необходимое их количество исходя из особенностей самих данных. Это новый класс вычислительных механизмов. Количество и расположение искусственных нейронов в пространстве признаков не задается заранее,  а вычисляется в процессе обучения  моделей в соответствии с особенностями входных данных, самостоятельно подстраиваясь под них <ref>[[Растущий нейронный газ - реализация на языке программирования MQL5]],[http://www.mql5.com/ru/articles/163]</ref>

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

Существуют методики, которые способны выделять наиболее похожие объекты в пространстве  и формировать из них группы. В процессе анализа   множество объектов организуются в подмножества на основе измеряемого сходства. Обычно методы основываются на стандартной схеме:  оптимизация отношений между пространственным расположением  векторов и множества объектов, таких, что каждый вектор определяет структуру кластеров. Однако большинство техник имеют два значительных недостатка: проведение анализа зависит от заданного количества кластеров и разделения на кластеры локализовано во времени. Все современные методы кластеризации были статичны и не могли адаптировать результаты, если к данным добавлялись новые данные, необходимо было повторно выполнять алгоритм. 
В 90-х годах исследователи искусственных нейросетей <ref>[[Искусственные нейронные сети]],[http://ru.wikipedia.org/wiki/%D0%98%D1%81%D0%BA%D1%83%D1%81%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%BD%D0%B5%D0%B9%D1%80%D0%BE%D0%BD%D0%BD%D1%8B%D0%B5_%D1%81%D0%B5%D1%82%D0%B8]</ref> пришли к выводу о том, что необходимо развивать новый класс вычислительных механизмов. Такого метода, чтобы количество и расположение искусственных нейронов в пространстве признаков не задавалось заранее,  а вычислялась в процессе обучения таких моделей в соответствии с особенностями входных данных, самостоятельно подстраиваясь под них.


== Определение ==
«Нейронный газ  – это алгоритм, позволяющий осуществлять адаптивную кластеризацию входных данных, т.е. не только разделить пространство на кластеры, но и определить необходимое их количество исходя из особенностей самих данных. Нейронный газ  не требует априорной информации о данных, таких как оценка количества кластеров или форма кластеров»<ref>[[Словарь Neural.ru]],[http://www.neural.ru/dictionary/%D0%9D%D0%B5%D0%B9%D1%80%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9%20%D0%B3%D0%B0%D0%B7]</ref>
В данной модели  не фиксировано соседство узлов, а динамически меняется по мере улучшения кластеризации. В относительно недавней модификации метода, получившей название "расширяющийся нейронный газ", переменными являются не только отношения соседства, но и число нейронов-кластеров.



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

Начиная всего с двух нейронов, алгоритм последовательно изменяет (по большей части, увеличивает) их число, одновременно создавая набор связей между нейронами, наилучшим образом отвечающую распределению входных векторов.  У каждого нейрона имеется внутренняя переменная, в которой накапливается «локальная ошибка». Соединения между узлами характеризуются переменной, называемой «возраст».<ref name="multiple">Isaac J. Sledge,Growing Neural Gas for Temporal Clustering/IEEE, 2008</ref>
	
* Сперва создаются  два узла с векторами весов, разрешенными распределением входных векторов, и нулевыми значениями локальных ошибок;  
* Узлы соединяются связью, которой можно установить возраст. На начальном этапе возраст равен 0.  
* Затем  на вход нейросети подаётся вектор X. 
* На следующем этапе находятся  два нейрона  S и T, ближайших к X , т.е. узлы с векторами весов и Wt, такими, что  ||Ws – X||2 минимальное, а  ||Wt– X|| второе минимальное значение расстояния среди всех узлов. 
* 	Обновляется локальная ошибка, наиболее близкого нейрона - победителя S, к ней добавляется  квадрат расстояния между векторами Ws  и X.  
 
                                              Е s → Е s+||Ws – X||2 
* Эта процедура приводит к тому, что наиболее часто выигрывающие узлы, т.е. те, в окрестности которых попадает наибольшее количество входных сигналов, имеют наибольшее значение ошибки, а значит, именно эти области становятся главными кандидатами на «уплотнение» путем добавления новых узлов. 

* Нейрон-победитель S и все его топологические соседи (т.е. все нейроны, имеющие соединение с победителем) смещаются в сторону входного вектора   на расстояния, равные долям еw и еn  от полного. 
                                               Ws→ Ws + еw( Ws –X) 
                                               Wn→ Wn + еn( Wn –X) 
Cмещение узлов в сторону входного вектора на данном шаге означает, что победитель стремится «усреднить» свое положение среди входных сигналов, расположенных в его окрестностях. При этом лучший нейрон немного «подтягивает» в сторону сигнала и своих соседей  
* Увеличить на 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  - это количество векторов внутри скопления, которое находится с помощью теоремы Жордана Брауера (9), а ap – площадь поверхности скопления и ψ – заданный пользователем порог. Если это неравенство приобретает форму np/na<ψ, то формой кластера будет «гипертруба». <ref name="multiple" />

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

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

[[Файл:Труба.jpg|Для кластера в виде гипертрубы рассчитывается радиальная мера расстояния ]]

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

'''Для определения расстояний в гиперплоскости следует использовать следующую формулу:'''
[[Файл:Линейная.jpg|Формула для определения расстояний в гиперплоскости ]]

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

'''Для определения расстояния в гиперсфере необходимо использовать формулу:'''
[[Файл:Сфера.jpg|Формула для определения расстояний в гиперсфере ]]

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

== Визуализация данных ==
В трёхмерном пространстве данные очень легко визуализировать.<ref name="multiple" />Вы можете видеть это на рисунке.  
[[File:3ddddd.png|thumb|Визуализация в 3d пространстве]]
 
Однако если наше пространство больше, чем трёхмерное, то визуализация данных затруднительна. Для решения этой задачи используется техника, основанная на VAT (13). Суть построения заключается в том, что находится минимальное остовное дерево модели.  После того как завершён процесс сортировки, структуру кластеров можно анализировать по квадратам около диагонали. Сперва происходит вычисление нормированных, попарно-различающихся нейронов в каждом изолированном графе. Затем различающиеся нейроны перестраиваются для того чтобы создать наиболее плотное внутрикластерное распределение.  Затем каждый кластер окрашивается в свой цвет и размещается вдоль главной диагонали. Внутрикластерные отношения также включены в диаграмму, максимальное расстояние между двумя кластерами обозначено белым цветом, а чёрным – наименьшее расстояние. Объём кластера может быть добавлена как ещё одно измерение, это увеличение квадратов в вышину. 

[[Файл:Jjjаа.jpg|Решение проблем визуализации ]]


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

После чего было запущено ещё 150 новых векторов. Это привело к формированию нового сферического класса, обозначенного на рисунке ниже:
[[File:4 кл.png|4 кл]]
 
Несмотря на пространственную близость зелёного и пурпурного кластеров, алгоритм отметил увеличение кластеров и адаптировался к этим изменениям. В данном случае оставшиеся 120 объектов были многократно перемешаны между  зелёным и пурпурным кластером. Алгоритм впоследствии распределил данные между двумя кластерами и сохранил первоначальное число кластеров.

[[File:3 кл.png|3 кл]]
 




==Примечания==
<references/>

== См. также ==

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

[[Категория:Кластерный анализ]]
[[Категория:Машинное обучение]]

[[de:Neural Gas]]
[[en:Neural gas]]