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

Самоорганизу́ющаяся ка́рта Ко́хонена (англ. Self-organizing map — SOM) — нейронная сеть с обучением без учителя, выполняющая задачу визуализации и кластеризации. Идея сети предложена финским учёным Т. Кохоненом. Является методом проецирования многомерного пространства в пространство с более низкой размерностью (чаще всего, двумерное), применяется также для решения задач моделирования, прогнозирования, выявление наборов независимых признаков, поиска закономерностей в больших массивах данных, разработке компьютерных игр, квантизации цветов к их ограниченному числу индексов в цветовой палитре: при печати на принтере и ранее на ПК или же на приставках с дисплеем с пониженным числом цветов, для архиваторов [общего назначения] или видео-кодеков, и прч. Является одной из версий нейронных сетей Кохонена.

История

Метод был предложен финским учёным Теуво Кохоненом в 1984 году. Существует множество модификаций исходной модели.

Структура сети

Самоорганизующаяся карта состоит из компонентов, называемых узлами или нейронами. Их количество задаётся аналитиком. Каждый из узлов описывается двумя векторами. Первый — т. н. вектор веса m, имеющий такую же размерность, что и входные данные. Второй — вектор r, представляющий собой координаты узла на карте. Карта Кохонена визуально отображается с помощью ячеек прямоугольной или шестиугольной формы; последняя применяется чаще, поскольку в этом случае расстояния между центрами смежных ячеек одинаковы, что повышает корректность визуализации карты.

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

В результате работы алгоритма получаются следующие карты:

карта входов нейронов — визуализирует внутреннюю структуру входных данных путём подстройки весов нейронов карты. Обычно используется несколько карт входов, каждая из которых отображает один из них и раскрашивается в зависимости от веса нейрона. На одной из карт определенным цветом обозначают область, в которую включаются приблизительно одинаковые входы для анализируемых примеров.
карта выходов нейронов — визуализирует модель взаимного расположения входных примеров. Очерченные области на карте представляют собой кластеры, состоящие из нейронов со схожими значениями выходов.
специальные карты — это карта кластеров, полученных в результате применения алгоритма самоорганизующейся карты Кохонена, а также другие карты, которые их характеризуют.^[1]

Работа сети

Инициализация карты, то есть первоначальное задание векторов веса для узлов.
Цикл:
- Выбор следующего наблюдения (вектора из множества входных данных).
- Нахождение для него лучшей единицы соответствия (best matching unit, BMU, или Winner) — узла на карте, вектор веса которого меньше всего отличается от наблюдения (в метрике, задаваемой аналитиком, чаще всего, евклидовой).
- Определение количества соседей BMU и обучение — изменение векторов веса BMU и его соседей с целью их приближения к наблюдению.
- Определение ошибки карты.

Алгоритм

Инициализация

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

- Задание всех координат случайными числами.
- Присваивание вектору веса значения случайного наблюдения из входных данных.
- Выбор векторов веса из линейного пространства, натянутого на главные компоненты набора входных данных.
Цикл

Пусть [math]\displaystyle{ t }[/math] — номер итерации (инициализация соответствует номеру 0).

- Выбрать произвольное наблюдение [math]\displaystyle{ x(t) }[/math] из множества входных данных.
- Найти расстояния от него до векторов веса всех узлов карты и определить ближайший по весу узел [math]\displaystyle{ M_c(t) }[/math]. Это — BMU или Winner. Условие на [math]\displaystyle{ M_c(t) }[/math]:

[math]\displaystyle{ \| x(t)-m_c(t)\|\leq\| x(t)-m_i(t)\| }[/math],

для любого [math]\displaystyle{ m_i(t) }[/math], где [math]\displaystyle{ m_i(t) }[/math] — вектор веса узла [math]\displaystyle{ M_i(t) }[/math]. Если находится несколько узлов, удовлетворяющих условию, BMU выбирается случайным образом среди них.

- Определить с помощью функции [math]\displaystyle{ h }[/math] (функции соседства) соседей [math]\displaystyle{ M_c }[/math] и изменение их векторов веса.
  - Задание [math]\displaystyle{ h }[/math]

Функция определяет «меру соседства» узлов [math]\displaystyle{ M_i }[/math] и [math]\displaystyle{ M_c }[/math] и изменение векторов веса. Она должна постепенно уточнять их значения, сначала у большего количества узлов и сильнее, потом у меньшего и слабее. Часто в качестве функции соседства используется гауссовская функция:

[math]\displaystyle{ h_{ci}(t)=\alpha(t)\cdot\exp(-\frac{\|r_c-r_i\|^2}{2\sigma^2(t)}) }[/math]

где [math]\displaystyle{ 0\lt \alpha(t)\lt 1 }[/math] — обучающий сомножитель, монотонно убывающий с каждой последующей итерацией (то есть определяющий приближение значения векторов веса BMU и его соседей к наблюдению; чем больше шаг, тем меньше уточнение);

[math]\displaystyle{ r_i }[/math], [math]\displaystyle{ r_c }[/math] — координаты узлов [math]\displaystyle{ M_i(t) }[/math] и [math]\displaystyle{ M_c(t) }[/math] на карте;

[math]\displaystyle{ \sigma(t) }[/math] — сомножитель, уменьшающий количество соседей с итерациями, монотонно убывает.

Параметры [math]\displaystyle{ \alpha }[/math], [math]\displaystyle{ \sigma }[/math] и их характер убывания задаются аналитиком.

Более простой способ задания функции соседства:

[math]\displaystyle{ h_{ci}(t)=\alpha(t) }[/math],

если [math]\displaystyle{ M_i(t) }[/math] находится в окрестности [math]\displaystyle{ M_c(t) }[/math] заранее заданного аналитиком радиуса, и 0 в противном случае.

Функция [math]\displaystyle{ h(t) }[/math] равна [math]\displaystyle{ \alpha(t) }[/math] для BMU и уменьшается с удалением от BMU.

- - Изменение векторов веса

Изменить вектор веса по формуле:

[math]\displaystyle{ m_i(t)=m_i(t-1)+h_{ci}(t)\cdot(x(t)-m_i(t-1)) }[/math]

Т.о. вектора веса всех узлов, являющихся соседями BMU, приближаются к рассматриваемому наблюдению.

- Вычисление ошибки карты

Например, как среднее арифметическое расстояний между наблюдениями и векторами веса соответствующих им BMU:

[math]\displaystyle{ \frac{1}{N}\sum_{i=1}^{N}\|x_{i}-m_{c}\| }[/math],

где N — количество элементов набора входных данных.

Особенности модели

Устойчивость к зашумленным данным, быстрое и неуправляемое обучение, возможность упрощения многомерных входных данных с помощью визуализации.^[2]

Самоорганизующиеся карты Кохонена могут быть использованы для кластерного анализа только в том случае, если заранее известно число кластеров^[2].

Важным недостатком является то, что окончательный результат работы нейронных сетей зависит от начальных установок сети. С другой стороны, нейронные сети теоретически могут аппроксимировать любую непрерывную функцию, что позволяет исследователю не принимать заранее какие-либо гипотезы относительно модели^[2].

См. также

Примечания

↑ Чубукова, 2000, с. 140.
↑ ^2,0 ^2,1 ^2,2 Манжула, 2011.

Литература

T. Kohonen, Self-Organizing Maps (Third Extended Edition), New York, 2001, 501 pages. ISBN 3-540-67921-9
Дебок Г., Кохонен Т. Анализ финансовых данных с помощью самоорганизующихся карт, Альпина Паблишер, 2001, 317 стр. ISBN 5-89684-013-6
Зиновьев А. Ю. Визуализация многомерных данных. — Красноярск: Изд. Красноярского государственного технического университета, 2000. — 180 с.
Чубукова И.А. Data Mining. — 2000. — 326 с.
Манжула В.Г., Федяшов Д.С. Нейронные сети Кохонена и нечеткие нейронные сети в интеллектуальном анализе данных. — 2011.
Lakhmi C. Jain; N.M. Martin Fusion of Neural Networks, Fuzzy Systems and Genetic Algorithms: Industrial Applications. — CRC Press, CRC Press LLC, 1998

Ссылки

SOM-Research на сайте Хельсинкского технического университета
WEBSOM, a Kohonen network project
PCA, SOM and GSOM: applet, Е. М. Миркес и университет Лейстера. Метод главных компонент, самоорганизующиеся карты и растущие самоорганизующиеся карты. Глава онлайн учебника c программами, позволяющими проводить сравнительные исследования.
Лекция по самоорганизующимся картам Кохонена

[_99ce472bb073a430-1] Чубукова, 2000, с. 140.

[_fa12af322db5d569-2] 2,0 ^2,1 ^2,2 Манжула, 2011.

[1]

[2]

Машинное обучение и data mining
Задачи	Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение
Обучение с учителем	Метод k-ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамбли моделей Бэггинг Бустинг Random forest Метод релевантных векторов
Кластерный анализ	Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift
Снижение размерности	Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE
Структурное прогнозирование	Графовая вероятностная модель Байесовская сеть Скрытая марковская модель CRF
Выявление аномалий	Метод k-ближайших соседей Локальный уровень выброса
Графовые вероятностные модели	Байесовская сеть Марковская сеть Скрытая марковская модель
Нейронные сети	Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации Сигмоида Softmax Радиально-базисная функция Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть Долгая краткосрочная память Управляемый рекуррентный блок Свёрточная нейронная сеть U-Net Автокодировщик
Обучение с подкреплением	Марковский процесс Уравнение Беллмана Жадный алгоритм Q-обучение SARSA Temporal difference (TD)
Теория	Теория Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения
Журналы и конференции	NeurIPS ICML ML JMLR ArXiv:cs.LG