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

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

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

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

Определение

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

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

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

• Сперва создаются два узла (здесь и далее, узел=нейрон) с векторами весов, разрешенными распределением входных векторов, и нулевыми значениями локальных ошибок;
• Узлы соединяются связью, которой можно установить возраст. На начальном этапе возраст равен 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 — это количество векторов внутри скопления, которое находится с помощью теоремы Жордана Брауера, а ap — площадь поверхности скопления и ψ — заданный пользователем порог. Если это неравенство приобретает форму np/na<ψ, то формой кластера будет «гипертруба».

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

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

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

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

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

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

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

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

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

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

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

Этот пример представлен для демонстрации того, как система адаптируется при вводе новых данных. База данных представляет собой 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.

Отрывок, характеризующий Нейронный газ

Княжна Марья перебила его.
– О, это было бы так ужа… – начала она и, не договорив от волнения, грациозным движением (как и все, что она делала при нем) наклонив голову и благодарно взглянув на него, пошла за теткой.
Вечером этого дня Николай никуда не поехал в гости и остался дома, с тем чтобы покончить некоторые счеты с продавцами лошадей. Когда он покончил дела, было уже поздно, чтобы ехать куда нибудь, но было еще рано, чтобы ложиться спать, и Николай долго один ходил взад и вперед по комнате, обдумывая свою жизнь, что с ним редко случалось.
Княжна Марья произвела на него приятное впечатление под Смоленском. То, что он встретил ее тогда в таких особенных условиях, и то, что именно на нее одно время его мать указывала ему как на богатую партию, сделали то, что он обратил на нее особенное внимание. В Воронеже, во время его посещения, впечатление это было не только приятное, но сильное. Николай был поражен той особенной, нравственной красотой, которую он в этот раз заметил в ней. Однако он собирался уезжать, и ему в голову не приходило пожалеть о том, что уезжая из Воронежа, он лишается случая видеть княжну. Но нынешняя встреча с княжной Марьей в церкви (Николай чувствовал это) засела ему глубже в сердце, чем он это предвидел, и глубже, чем он желал для своего спокойствия. Это бледное, тонкое, печальное лицо, этот лучистый взгляд, эти тихие, грациозные движения и главное – эта глубокая и нежная печаль, выражавшаяся во всех чертах ее, тревожили его и требовали его участия. В мужчинах Ростов терпеть не мог видеть выражение высшей, духовной жизни (оттого он не любил князя Андрея), он презрительно называл это философией, мечтательностью; но в княжне Марье, именно в этой печали, выказывавшей всю глубину этого чуждого для Николая духовного мира, он чувствовал неотразимую привлекательность.
«Чудная должна быть девушка! Вот именно ангел! – говорил он сам с собою. – Отчего я не свободен, отчего я поторопился с Соней?» И невольно ему представилось сравнение между двумя: бедность в одной и богатство в другой тех духовных даров, которых не имел Николай и которые потому он так высоко ценил. Он попробовал себе представить, что бы было, если б он был свободен. Каким образом он сделал бы ей предложение и она стала бы его женою? Нет, он не мог себе представить этого. Ему делалось жутко, и никакие ясные образы не представлялись ему. С Соней он давно уже составил себе будущую картину, и все это было просто и ясно, именно потому, что все это было выдумано, и он знал все, что было в Соне; но с княжной Марьей нельзя было себе представить будущей жизни, потому что он не понимал ее, а только любил.
Мечтания о Соне имели в себе что то веселое, игрушечное. Но думать о княжне Марье всегда было трудно и немного страшно.
«Как она молилась! – вспомнил он. – Видно было, что вся душа ее была в молитве. Да, это та молитва, которая сдвигает горы, и я уверен, что молитва ее будет исполнена. Отчего я не молюсь о том, что мне нужно? – вспомнил он. – Что мне нужно? Свободы, развязки с Соней. Она правду говорила, – вспомнил он слова губернаторши, – кроме несчастья, ничего не будет из того, что я женюсь на ней. Путаница, горе maman… дела… путаница, страшная путаница! Да я и не люблю ее. Да, не так люблю, как надо. Боже мой! выведи меня из этого ужасного, безвыходного положения! – начал он вдруг молиться. – Да, молитва сдвинет гору, но надо верить и не так молиться, как мы детьми молились с Наташей о том, чтобы снег сделался сахаром, и выбегали на двор пробовать, делается ли из снегу сахар. Нет, но я не о пустяках молюсь теперь», – сказал он, ставя в угол трубку и, сложив руки, становясь перед образом. И, умиленный воспоминанием о княжне Марье, он начал молиться так, как он давно не молился. Слезы у него были на глазах и в горле, когда в дверь вошел Лаврушка с какими то бумагами.
– Дурак! что лезешь, когда тебя не спрашивают! – сказал Николай, быстро переменяя положение.
– От губернатора, – заспанным голосом сказал Лаврушка, – кульер приехал, письмо вам.
– Ну, хорошо, спасибо, ступай!
Николай взял два письма. Одно было от матери, другое от Сони. Он узнал их по почеркам и распечатал первое письмо Сони. Не успел он прочесть нескольких строк, как лицо его побледнело и глаза его испуганно и радостно раскрылись.
– Нет, это не может быть! – проговорил он вслух. Не в силах сидеть на месте, он с письмом в руках, читая его. стал ходить по комнате. Он пробежал письмо, потом прочел его раз, другой, и, подняв плечи и разведя руками, он остановился посреди комнаты с открытым ртом и остановившимися глазами. То, о чем он только что молился, с уверенностью, что бог исполнит его молитву, было исполнено; но Николай был удивлен этим так, как будто это было что то необыкновенное, и как будто он никогда не ожидал этого, и как будто именно то, что это так быстро совершилось, доказывало то, что это происходило не от бога, которого он просил, а от обыкновенной случайности.
Тот, казавшийся неразрешимым, узел, который связывал свободу Ростова, был разрешен этим неожиданным (как казалось Николаю), ничем не вызванным письмом Сони. Она писала, что последние несчастные обстоятельства, потеря почти всего имущества Ростовых в Москве, и не раз высказываемые желания графини о том, чтобы Николай женился на княжне Болконской, и его молчание и холодность за последнее время – все это вместе заставило ее решиться отречься от его обещаний и дать ему полную свободу.
«Мне слишком тяжело было думать, что я могу быть причиной горя или раздора в семействе, которое меня облагодетельствовало, – писала она, – и любовь моя имеет одною целью счастье тех, кого я люблю; и потому я умоляю вас, Nicolas, считать себя свободным и знать, что несмотря ни на что, никто сильнее не может вас любить, как ваша Соня».
Оба письма были из Троицы. Другое письмо было от графини. В письме этом описывались последние дни в Москве, выезд, пожар и погибель всего состояния. В письме этом, между прочим, графиня писала о том, что князь Андрей в числе раненых ехал вместе с ними. Положение его было очень опасно, но теперь доктор говорит, что есть больше надежды. Соня и Наташа, как сиделки, ухаживают за ним.
С этим письмом на другой день Николай поехал к княжне Марье. Ни Николай, ни княжна Марья ни слова не сказали о том, что могли означать слова: «Наташа ухаживает за ним»; но благодаря этому письму Николай вдруг сблизился с княжной в почти родственные отношения.
На другой день Ростов проводил княжну Марью в Ярославль и через несколько дней сам уехал в полк.


Письмо Сони к Николаю, бывшее осуществлением его молитвы, было написано из Троицы. Вот чем оно было вызвано. Мысль о женитьбе Николая на богатой невесте все больше и больше занимала старую графиню. Она знала, что Соня была главным препятствием для этого. И жизнь Сони последнее время, в особенности после письма Николая, описывавшего свою встречу в Богучарове с княжной Марьей, становилась тяжелее и тяжелее в доме графини. Графиня не пропускала ни одного случая для оскорбительного или жестокого намека Соне.
Но несколько дней перед выездом из Москвы, растроганная и взволнованная всем тем, что происходило, графиня, призвав к себе Соню, вместо упреков и требований, со слезами обратилась к ней с мольбой о том, чтобы она, пожертвовав собою, отплатила бы за все, что было для нее сделано, тем, чтобы разорвала свои связи с Николаем.
– Я не буду покойна до тех пор, пока ты мне не дашь этого обещания.
Соня разрыдалась истерически, отвечала сквозь рыдания, что она сделает все, что она на все готова, но не дала прямого обещания и в душе своей не могла решиться на то, чего от нее требовали. Надо было жертвовать собой для счастья семьи, которая вскормила и воспитала ее. Жертвовать собой для счастья других было привычкой Сони. Ее положение в доме было таково, что только на пути жертвованья она могла выказывать свои достоинства, и она привыкла и любила жертвовать собой. Но прежде во всех действиях самопожертвованья она с радостью сознавала, что она, жертвуя собой, этим самым возвышает себе цену в глазах себя и других и становится более достойною Nicolas, которого она любила больше всего в жизни; но теперь жертва ее должна была состоять в том, чтобы отказаться от того, что для нее составляло всю награду жертвы, весь смысл жизни. И в первый раз в жизни она почувствовала горечь к тем людям, которые облагодетельствовали ее для того, чтобы больнее замучить; почувствовала зависть к Наташе, никогда не испытывавшей ничего подобного, никогда не нуждавшейся в жертвах и заставлявшей других жертвовать себе и все таки всеми любимой. И в первый раз Соня почувствовала, как из ее тихой, чистой любви к Nicolas вдруг начинало вырастать страстное чувство, которое стояло выше и правил, и добродетели, и религии; и под влиянием этого чувства Соня невольно, выученная своею зависимою жизнью скрытности, в общих неопределенных словах ответив графине, избегала с ней разговоров и решилась ждать свидания с Николаем с тем, чтобы в этом свидании не освободить, но, напротив, навсегда связать себя с ним.
Хлопоты и ужас последних дней пребывания Ростовых в Москве заглушили в Соне тяготившие ее мрачные мысли. Она рада была находить спасение от них в практической деятельности. Но когда она узнала о присутствии в их доме князя Андрея, несмотря на всю искреннюю жалость, которую она испытала к нему и к Наташе, радостное и суеверное чувство того, что бог не хочет того, чтобы она была разлучена с Nicolas, охватило ее. Она знала, что Наташа любила одного князя Андрея и не переставала любить его. Она знала, что теперь, сведенные вместе в таких страшных условиях, они снова полюбят друг друга и что тогда Николаю вследствие родства, которое будет между ними, нельзя будет жениться на княжне Марье. Несмотря на весь ужас всего происходившего в последние дни и во время первых дней путешествия, это чувство, это сознание вмешательства провидения в ее личные дела радовало Соню.
В Троицкой лавре Ростовы сделали первую дневку в своем путешествии.