Самоорганизующаяся карта - Self-organizing map

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

SOM - это тип искусственной нейронной сети, но она обучается с использованием конкурентного обучения, а не обучения с исправлением ошибок (например, обратное распространение с градиентным спуском ), используемого другими искусственными нейронными сетями. SOM был введен финским профессором Теуво Кохоненом в 1980-х годах и поэтому иногда называется картой Кохонена или сетью Кохонена . Карта Кохонена или сеть - это удобная в вычислительном отношении абстракция, построенная на биологических моделях нейронных систем 1970-х годов и моделях морфогенеза, восходящих к Алану Тьюрингу 1950-х годов.

Самоорганизующаяся карта, показывающая схемы голосования в Конгрессе США . Входные данные представляли собой таблицу со строкой для каждого члена Конгресса и столбцами для определенных голосов, содержащими голоса каждого члена «да» / «нет» / «воздержался». Алгоритм SOM расположил эти элементы в двумерной сетке, расположив аналогичные элементы ближе друг к другу. Первый график показывает группировку, когда данные разделены на два кластера. Второй график показывает среднее расстояние до соседей: большие расстояния темнее. Третий график предсказывает членство в республиканской (красный) или демократической (синий) партиях. Каждый другой график накладывает результирующую карту с предсказанными значениями во входном измерении: красный цвет означает прогнозируемое голосование «да» по этому законопроекту, синий означает голосование «нет». Сюжет создан в Synapse .

Обзор

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

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

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

Алгоритм обучения

Цель обучения самоорганизующейся карте - заставить разные части сети одинаково реагировать на определенные входные шаблоны. Это отчасти мотивировано тем , как визуальный, слуховой или иной сенсорной информации осуществляется в отдельных частях коры головного мозга в человеческом мозге .

Иллюстрация тренировки самоорганизующейся карты. Голубая капля - это распределение обучающих данных, а маленький белый диск - текущие обучающие данные, взятые из этого распределения. Сначала (слева) узлы SOM произвольно располагаются в пространстве данных. Выбирается узел (выделен желтым), ближайший к обучающей базе данных. Он перемещается к обучающей базе данных, поскольку (в меньшей степени) являются ее соседями по сетке. После многих итераций сетка приближается к распределению данных (справа).

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

В сеть должно подаваться большое количество векторов-примеров, которые как можно ближе представляют типы векторов, ожидаемых во время сопоставления. Примеры обычно вводятся несколько раз в виде итераций.

В обучении используется соревновательное обучение . Когда обучающий пример загружается в сеть, вычисляется его евклидово расстояние до всех весовых векторов. Нейрон, весовой вектор которого наиболее похож на входной, называется единицей наилучшего согласования (BMU). Веса BMU и близких к нему нейронов в сетке SOM корректируются по входному вектору. Величина изменения уменьшается со временем и с удалением сетки от BMU. Формула обновления для нейрона v с весовым вектором W _v (s):

{\ Displaystyle W_ {v} (s + 1) = W_ {v} (s) + \ theta (u, v, s) \ cdot \ alpha (s) \ cdot (D (t) -W_ {v} ( s))}

,

где s - индекс шага, t - индекс обучающей выборки, u - индекс BMU для входного вектора D (t), α (s) - монотонно убывающий коэффициент обучения; Θ (u, v, s) - функция соседства, которая дает расстояние между нейроном u и нейроном v на шаге s. В зависимости от реализаций t может систематически сканировать набор обучающих данных (t - 0, 1, 2 ... T-1, затем повторять, T - размер обучающей выборки), случайным образом извлекаться из набора данных ( выборка начальной загрузки ) или используйте другой метод отбора проб (например, складывание с помощью складного ножа ).

Функция соседства Θ (u, v, s) (также называемая функцией бокового взаимодействия ) зависит от сеточного расстояния между BMU (нейроном u ) и нейроном v . В простейшей форме это 1 для всех нейронов, достаточно близких к BMU, и 0 для других, но функции Гаусса и мексиканской шляпы также являются обычным выбором. Независимо от функциональной формы функция соседства сжимается со временем. Вначале, когда окружение велико, самоорганизация происходит в глобальном масштабе. Когда соседство сократилось до пары нейронов, веса сходятся к локальным оценкам. В некоторых реализациях коэффициент обучения α и функция соседства Θ постоянно уменьшаются с увеличением s, в других (в частности, в тех, где t сканирует набор обучающих данных) они уменьшаются пошагово, один раз каждые T шагов.

Процесс обучения СОМ на двумерном наборе данных

Этот процесс повторяется для каждого входного вектора в течение (обычно большого) количества циклов λ . В итоге сеть связывает выходные узлы с группами или шаблонами во входном наборе данных. Если эти шаблоны могут быть названы, имена могут быть присоединены к связанным узлам в обученной сети.

Во время сопоставления будет один единственный нейрон- победитель : нейрон, весовой вектор которого находится ближе всего к входному вектору. Это можно просто определить, вычислив евклидово расстояние между входным вектором и вектором весов.

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

Переменные

Это необходимые переменные, векторы выделены жирным шрифтом,

${\ displaystyle s}$ это текущая итерация
${\ displaystyle \ lambda}$ предел итераций
${\ displaystyle t}$ - индекс вектора целевых входных данных во входном наборе данных ${\ displaystyle \ mathbf {D}}$
${\ Displaystyle {D} (т)}$ целевой вектор входных данных
${\ displaystyle v}$ это индекс узла на карте
${\ displaystyle \ mathbf {W} _ {v}}$ текущий весовой вектор узла ${\ displaystyle v}$
${\ displaystyle u}$ это индекс наиболее подходящей единицы (BMU) на карте
${\ Displaystyle \ theta (и, v, s)}$ - ограничение из-за расстояния от BMU, обычно называемое функцией соседства, и
${\ displaystyle \ alpha (s)}$ это ограничение обучения из-за прогресса итерации.

Алгоритм

Рандомизируйте весовые векторы узлов на карте
Случайно выбрать входной вектор ${\ Displaystyle {D} (т)}$
Пройдите по каждому узлу на карте
1. Используйте формулу евклидова расстояния, чтобы найти сходство между входным вектором и вектором веса узла карты.
2. Отслеживайте узел, который производит наименьшее расстояние (этот узел является наиболее подходящей единицей, BMU)
Обновите весовые векторы узлов в окрестности BMU (включая сам BMU), подтянув их ближе к входному вектору.
1. ${\ Displaystyle W_ {v} (s + 1) = W_ {v} (s) + \ theta (u, v, s) \ cdot \ alpha (s) \ cdot (D (t) -W_ {v} ( s))}$
Увеличьте и повторите, начиная с шага 2, пока ${\ displaystyle s}$ ${\ displaystyle s <\ lambda}$

Альтернативный алгоритм

Рандомизируйте весовые векторы узлов карты
Пройдите по каждому входному вектору во входном наборе данных
1. Пройдите по каждому узлу на карте
  1. Используйте формулу евклидова расстояния, чтобы найти сходство между входным вектором и вектором веса узла карты.
  2. Отслеживайте узел, который производит наименьшее расстояние (этот узел является наиболее подходящей единицей, BMU)
2. Обновите узлы в окрестности BMU (включая сам BMU), подтянув их ближе к входному вектору
  1. ${\ Displaystyle W_ {v} (s + 1) = W_ {v} (s) + \ theta (u, v, s) \ cdot \ alpha (s) \ cdot (D (t) -W_ {v} ( s))}$
Увеличьте и повторите, начиная с шага 2, пока ${\ displaystyle s}$ ${\ displaystyle s <\ lambda}$

Варианты инициализации

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

Однако тщательное сравнение случайной инициализации с инициализацией главного компонента для одномерной карты показало, что преимущества инициализации главного компонента не универсальны. Лучший метод инициализации зависит от геометрии конкретного набора данных. Инициализация главного компонента была предпочтительнее (для одномерной карты), когда главная кривая, аппроксимирующая набор данных, могла быть однолистно и линейно спроецирована на первый главный компонент (квазилинейные множества). Однако для нелинейных наборов данных случайное инициирование работает лучше.

Интерпретация

Картографическое представление самоорганизующейся карты ( U-матрица ) на основе данных статей из Википедии (частота слов). Расстояние обратно пропорционально сходству. «Горы» - это грани между кластерами. Красные линии - это ссылки между статьями.

Одномерный SOM по сравнению с анализом главных компонентов (PCA) для аппроксимации данных. SOM - красная ломаная линия с квадратами, 20 узлов. Первый главный компонент представлен синей линией. Точки данных - это маленькие серые кружки. Для PCA доля необъяснимой дисперсии в этом примере составляет 23,23%, для SOM - 6,86%.

Есть два способа интерпретировать SOM. Поскольку в фазе обучения веса всего окружения перемещаются в одном направлении, похожие предметы имеют тенденцию возбуждать соседние нейроны. Таким образом, SOM формирует семантическую карту, где похожие образцы отображаются близко друг к другу, а несходные - отдельно. Это можно визуализировать с помощью U-матрицы (евклидово расстояние между весовыми векторами соседних ячеек) SOM.

Другой способ - рассматривать веса нейронов как указатели на входное пространство. Они образуют дискретную аппроксимацию распределения обучающих выборок. Больше нейронов указывает на области с высокой концентрацией обучающей выборки и меньше нейронов - на мало.

SOM можно рассматривать как нелинейное обобщение анализа главных компонентов (PCA). Было показано, используя как искусственные, так и реальные геофизические данные, что SOM имеет много преимуществ по сравнению с традиционными методами извлечения признаков, такими как эмпирические ортогональные функции (EOF) или PCA.

Первоначально SOM не был сформулирован как решение проблемы оптимизации. Тем не менее, было несколько попыток изменить определение SOM и сформулировать задачу оптимизации, которая дает аналогичные результаты. Например, эластичные карты используют механическую метафору эластичности для аппроксимации основных многообразий : аналогия - эластичная мембрана и пластина.

Примеры

Данные цветка ириса Фишера

Рассмотрим массив узлов $размером$ $n \times m$ , каждый из которых содержит вектор весов и знает свое местоположение в массиве. Каждый весовой вектор имеет ту же размерность, что и входной вектор узла. Первоначально веса могут быть установлены на случайные значения.

Теперь нам нужен ввод для подачи карты. Цвета могут быть представлены их красными, зелеными и синими компонентами. Следовательно, мы будем представлять цвета как векторы в единичном кубе в свободном векторном пространстве над $ℝ$ порожденной основой :

R = <255, 0, 0>

G = <0, 255, 0>

B = <0, 0, 255>

Показанная диаграмма

Самоорганизующиеся карты (SOM) трех и восьми цветов с U-Matrix.

сравнивает результаты обучения на наборах данных

threeColors = [255, 0, 0], [0, 255, 0], [0, 0, 255]

восемьColors = [0, 0, 0], [255, 0, 0], [0, 255, 0], [0, 0, 255], [255, 255, 0], [0, 255, 255], [255, 0, 255], [255, 255, 255]

и исходные изображения. Обратите внимание на поразительное сходство между ними.

Точно так же после обучения сетки нейронов $40 \times 40$ для 250 итераций со скоростью обучения 0,1 на Ирисе Фишера карта уже может обнаруживать основные различия между видами.

Самоорганизующаяся карта (SOM) набора данных Fisher's Iris Flower с U-матрицей. Вверху слева: цветное изображение, образованное первыми тремя измерениями четырехмерных весовых векторов SOM. Вверху справа: псевдоцветное изображение величины весовых векторов SOM. Внизу слева: U-матрица (евклидово расстояние между весовыми векторами соседних ячеек) SOM. Внизу справа: наложение точек данных (красный: I. setosa , зеленый: I. versicolor и синий: I. virginica ) на U-матрице на основе минимального евклидова расстояния между векторами данных и весовыми векторами SOM.

Другой

Приоритезация и отбор проектов
Анализ сейсмофаций при разведке нефти и газа
Анализ видов и последствий отказов
Создание произведений искусства

Альтернативы

Порождающая топографическая карта (GTM) является потенциальной альтернативой ЗВОЛА. В том смысле, что GTM явно требует гладкого и непрерывного отображения из входного пространства в пространство карты, он сохраняет топологию. Однако в практическом смысле этой меры топологической сохранности нет.
Сеть адаптивных самоорганизующихся карт (TASOM) является расширением базового SOM. TASOM использует адаптивную скорость обучения и функции соседства. Он также включает параметр масштабирования, чтобы сделать сеть инвариантной к масштабированию, перемещению и вращению входного пространства. TASOM и его варианты использовались в нескольких приложениях, включая адаптивную кластеризацию, многоуровневую пороговую обработку, аппроксимацию входного пространства и моделирование активного контура. Более того, было предложено двоичное дерево TASOM или BTASOM, напоминающее двоичное естественное дерево, имеющее узлы, состоящие из сетей TASOM, где количество его уровней и количество его узлов адаптируются к его среде.
Растет самоорганизующаяся карта (ВШМ) является растущим вариантом самоорганизующейся карты. ВШМ была разработана для решения проблемы определения подходящего размера карты в ЗВОЛ. Он начинается с минимального количества узлов (обычно четырех) и наращивает новые узлы на границе на основе эвристики. Используя значение, называемое коэффициентом распространения , аналитик данных имеет возможность контролировать рост GSOM.
В упругих картах приближаются заимствуют из сплайна интерполяции идеи минимизации энергии упругой деформации . При обучении он минимизирует сумму квадратичной энергии изгиба и растяжения с ошибкой аппроксимации методом наименьших квадратов .
Конформный подход, который использует конформное отображение для интерполяции каждой обучающей выборки между узлами сетки на непрерывной поверхности. При таком подходе возможно взаимно однозначное сглаживание.
Ориентированная и масштабируемая карта (OS-Map) обобщающая функцию окрестностей и выбор победителя. Однородная гауссова функция окрестности заменяется матричной экспонентой. Таким образом, можно указать ориентацию либо в пространстве карты, либо в пространстве данных. SOM имеет фиксированный масштаб (= 1), так что карты «оптимально описывают область наблюдения». Но как насчет карты, покрывающей область дважды или n-кратно? Это влечет за собой концепцию масштабирования. OS-Map рассматривает масштаб как статистическое описание того, сколько узлов наилучшим образом соответствует входным данным на карте.

Languages

In other projects