Вход
Регистрация

Самоорганизующиеся карты Кохонена — математический аппарат

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

Основы

Алгоритм функционирования самообучающихся карт (Self Organizing Maps – SOM) представляет собой один из вариантов кластеризации многомерных векторов. Примером таких алгоритмов может служить алгоритм k-ближайших средних (k-means). Важным отличием алгоритма SOM является то, что в нем все нейроны (узлы, центры классов…) упорядочены в некоторую структуру (обычно двумерную сетку). При этом в ходе обучения модифицируется не только нейрон-победитель, но и его соседи, но в меньшей степени. За счет этого SOM можно считать одним из методов проецирования многомерного пространства в пространство с более низкой размерностью. При использовании этого алгоритма вектора, схожие в исходном пространстве, оказываются рядом и на полученной карте.

Структура

SOM подразумевает использование упорядоченной структуры нейронов. Обычно используются одно и двумерные сетки. При этом каждый нейрон представляет собой n-мерный вектор-столбец ${w} = [w_1, w_2, \ldots, w_n]^T$, где n определяется размерностью исходного пространства (размерностью входных векторов). Применение одно и двумерных сеток связано с тем, что возникают проблемы при отображении пространственных структур большей размерности (при этом опять возникают проблемы с понижением размерности до двумерной, представимой на мониторе).

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

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

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

Начальная инициализация карты

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

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

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

Обучение

Обучение состоит из последовательности коррекций векторов, представляющих собой нейроны. На каждом шаге обучения из исходного набора данным случайно выбирается один из векторов, а затем производится поиск наиболее похожего на него вектора коэффициентов нейронов. При этом выбирается нейрон-победитель, который наиболее похож на вектор входов. Под похожестью в данной задаче понимается расстояние между векторами, обычно вычисляемое в евклидовом пространстве. Таким образом, если обозначит нейрон-победитель как c, то получим $\mid\mid\mathbf {x}- \mathbf {w_c}\mid \mid = \min_i $ $\{ \mid \mid \mathbf {x}- \mathbf {w_i}\mid \mid \}$.

После того, как найден нейрон-победитель производится корректировка весов нейросети. При этом вектор, описывающий нейрон-победитель и вектора, описывающие его соседей в сетке перемещаются в направлении входного вектора. Это проиллюстрировано на рисунке 2 для двумерного вектора.

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

При этом для модификации весовых коэффициентов используется формула:

$w_i (t+1)= \mathbf w_i(t) + h_{ci}(t) * [\mathbf x(t) - \mathbf w (t)]$ ,

где t обозначает номер эпохи (дискретное время). При этом вектор x(t) выбирается случайно из обучающей выборки на итерации t. Функция h(t) называется функцией соседства нейронов. Эта функция представляет собой невозрастающую функцию от времени и расстояния между нейроном-победителем и соседними нейронами в сетке. Эта функция разбивается на две части: собственно функцию расстояния и функции скорости обучения от времени. где r определяет положение нейрона в сетке.

Обычно применяется одни из двух функций от расстояния: простая константа $h(d,t) = \begin{cases} const, d \leq\sigma (t)\\ 0, d >\sigma (t) \end{cases}$. При этом лучший результат получается при использовании Гауссовой функции расстояния. При этом является убывающей функцией от времени. Часто эту величину называют радиусом обучения, который выбирается достаточно большим на начальном этапе обучения и постепенно уменьшается так, что в конечном итоге обучается один нейрон-победитель. Наиболее часто используется функция, линейно убывающая от времени.

Рассмотрим теперь функцию скорости обучения $a(t)$. Эта функция также представляет собой функцию, убывающую от времени. Наиболее часто используются два варианта этой функции: линейная и обратно пропорциональная времени вида ${a(t)} =\frac {\mbox A}{\mbox{t + B}}$, где A и B это константы. Применение этой функции приводит к тому, что все вектора из обучающей выборки вносят примерно равный вклад в результат обучения.
Обучение состоит из двух основных фаз: на первоначальном этапе выбирается достаточно большое значение скорости обучения и радиуса обучение, что позволяет расположить вектора нейронов в соответствии с распределением примеров в выборке, а затем производится точная подстройка весов, когда значения параметров скорости обучения много меньше начальных. В случае использования линейной инициализации первоначальный этап грубой подстройки может быть пропущен.

Применение алгоритма

Так как алгоритм SOM сочетает в себе два основных направления – векторное квантование и проецирование, то можно найти и основные применения этого алгоритма. Данную методику можно использовать для поиска и анализа закономерностей в исходных данных. При этом, после того, как нейроны размещены на карте, полученная карта может быть отображена. Рассмотрим различные способы отображения полученной карты.

Раскраска, порожденная отдельными компонентами

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

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

Отображение кластеров

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

Литература
  • Ф.Уоссермен, "Нейрокомпьютерная техника" , М.: Мир, 1992
  • А.Ежов, С.Шумский, "Нейрокомпьютинг и его применение в экономике и бизнесе",1998.
  • T.Kohonen, "Self-Organizing Maps", Springer, 1995.
  • T.Kohonen, "Self-Organizing Maps"(2-nd edition), Springer, 1997.
  • Juho Vensano, "Data Mining Techniques Baseg on the Self Organized Map"