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

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

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

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

Обзор

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

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

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

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

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

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

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

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

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

$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 шагов.

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

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

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

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

Алгоритм

1. Рандомизировать векторы весов узлов на карте
2. Для $s=0,1,2,...,\lambda$
   1. Случайным образом выберите входной вектор ${D}(t)$
   2. Найдите узел на карте, ближайший к входному вектору. Этот узел является блоком наилучшего согласования (BMU). Обозначим его через $u$
   3. Для каждого узла $v$, обновите его вектор, приблизив его к входному вектору: $$W_{v}(s+1)=W_{v}(s)+\theta (u,v,s)\cdot \alpha (s)\cdot (D(t)-W_{v}(s))$$

Имена переменных означают следующее: векторы выделены жирным шрифтом:

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

Ключевыми вариантами проектирования являются форма SOM, функция соседства и график скорости обучения. Идея функции соседства состоит в том, чтобы сделать так, чтобы BMU обновлялся больше всего, его непосредственные соседи обновлялись немного меньше и так далее. Идея графика скорости обучения состоит в том, чтобы сделать так, чтобы обновления карт были большими в начале и постепенно прекращали обновление.

Например, если мы хотим изучить SOM, используя квадратную сетку, мы можем проиндексировать ее, используя $(i,j)$ где оба $i,j\in 1:N$. Функция соседства может сделать так, чтобы BMU обновлялся полностью, ближайшие соседи обновлялись наполовину, а их соседи обновлялись снова наполовину и т. д. $$\theta ((i,j),(i',j'),s)={\frac {1}{2^{|i-i'|+|j-j'|}}}={\begin{cases}1&{\text{if }}i=i',j=j'\\1/2&{\text{if }}|i-i'|+|j-j'|=1\\1/4&{\text{if }}|i-i'|+|j-j'|=2\\\cdots &\cdots \end{cases}}$$И мы можем использовать простой график линейной скорости обучения. $\alpha (s)=1-s/\lambda$.

Обратите внимание, в частности, что скорость обновления не зависит от того, где находится точка в евклидовом пространстве, а только от того, где она находится в самой SOM. Например, точки $(1,1),(1,2)$ близки на SOM, поэтому они всегда будут обновляться одинаковым образом, даже если они находятся далеко друг от друга в евклидовом пространстве. Напротив, даже если точки $(1,1),(1,100)$ в конечном итоге перекрывают друг друга (например, если SOM выглядит как сложенное полотенце), они по-прежнему не обновляются одинаковым образом.

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

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

Параметры инициализации

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

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

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

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

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

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

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

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

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

Примеры

• Приоритизация и выбор проекта
• Сейсмофациальный анализ при разведке нефти и газа
• Анализ характера и последствий отказов
• Поиск репрезентативных данных в больших наборах данных
  • репрезентативные виды экологических сообществ
  • репрезентативные дни для моделей энергосистем

Альтернативные подходы

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

См. также

• Глубокое обучение
• Гибридная самоорганизующаяся карта Кохонена
• Обучение векторному квантованию
• Машина жидкого состояния
• Неокогнитрон
• Нейронный газ
• Разреженное кодирование
• Разреженная распределенная память
• Топологический анализ данных

Дальнейшее чтение

• Кохонен, Теуво (январь 2013 г.). «Основы самоорганизующейся карты» . Нейронные сети . 37 : 52–65. дои : 10.1016/j.neunet.2012.09.018 . ПМИД   23067803 . S2CID   17289060 .
• Кохонен, Теуво (2001). Самоорганизующиеся карты: с 22 таблицами . Серия Springer по информационным наукам (3-е изд.). Берлин Гейдельберг: Springer. ISBN  978-3-540-67921-9 .
• Кохонен, Теуво (1988). «Самоорганизация и ассоциативная память» . Серия Спрингера по информационным наукам . 8 . дои : 10.1007/978-3-662-00784-6 . ISBN  978-3-540-18314-3 . ISSN   0720-678X .
• Каски, Самуэль, Яри Кангас и Теуво Кохонен. « Библиография статей по самоорганизующимся картам (SOM): 1981–1997 ». Обзоры нейронных вычислений 1.3 и 4 (1998): 1-176.
• Оя, Мерья, Самуэль Каски и Теуво Кохонен. « Библиография документов по самоорганизующимся картам (SOM): приложение за 1998–2001 годы ». Обзоры нейронных вычислений 3.1 (2003): 1-156.

Внешние ссылки

• СМИ, связанные с самоорганизующимися картами, на Викискладе?