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

Авторы: Быковец Евгений Владимирович, Ворона Игорь Игоревич

Алгоритм кластеризации, основанный на самоорганизующихся сетях Кохонена
Последовательный алгоритм
Последовательная сложность	[math]O(n^3)[/math]
Объём входных данных	[math]\frac{n (n + 1)}{2}[/math]
Объём выходных данных	[math]\frac{n (n + 1)}{2}[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]O(n)[/math]
Ширина ярусно-параллельной формы	[math]O(n^2)[/math]

1 Свойства и структура алгоритмов

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

Cамоорганизующаяся карта Кохонена (Self-Organizing Map, SOM) представляет из себя вычислительный метод, предназначенный для задач, в первую очередь, кластеризации и визуализации, а также анализа данных из пространств высокой размерности (иначе, многомерных данных), полученных экспериментально. Методы был предложен Туево Кохоненом (1982). Прародителями модели самоорганизующейся сети Кохонена были ранние нейросетевые модели (в частности, модель ассоциативной памяти и модель адаптивного обучения).

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

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

Каждый нейрон выходного слоя определяется вектором весов (размерность вектора - есть разность входного пространства) и упорядоченной парой : [math](x,y)[/math], определяющую позицию нейрона на карте Кохонена.

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

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

1.2 Математическое описание алгоритма

1.2.1 Используемые обозначения

[math]t[/math] - номер итерации,

[math]n[/math] - размерность исходного пространства,

[math] \chi \in R^n[/math] - обучающая выборка,

[math] \Phi \in R^n [/math] - тестовая выборка,

[math] N = |\chi|[/math] - размер обучающей выборки,

[math] K = |\Phi|[/math] - размер тестовой выборки,

[math] a [/math] - высота слоя Кохонена,

[math] b [/math] - ширина слоя Кохонена,

[math] M = a \times b [/math] - общее количество нейронов в слое Кохонена,

[math] ne_j, j=1,...M [/math] - нейрон с индексом [math]j[/math],

[math]\vec{x}^{(i)}(t) = (x_1^{(i)}(t),...,x_n^{(i)}(t)), i=1,..,N[/math] - [math]i[/math]-й вектор, подлежайщий кластеризации,

[math]\vec{w}^{(j)}(t) = (w_1^{(j)}(t),...,w_n^{(j)}(t)), j = 1,..,M[/math] - вектор весовых коэффициентов для [math]j[/math]-го нейрона,

[math] r_k[/math] - положение [math]k[/math]-го нейрона в топологии карты, то есть [math](i_k,j_k)[/math],

[math] h_{ij}(t)[/math] - функция соседства между нейронами с индексами [math]i[/math] и [math]j[/math] на итерации t,

[math] h(d,t) [/math] - функция от расстояния между нейронами,

[math] \alpha(t)[/math] - скорость обучения сети,

[math] \sigma(t) [/math] - функция, уменьшающая количество соседей с при увеличении итерации (монотонно убывающий)

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

Шаг №0. Определить значение параметров алгоритма: используемые метрики, функции [math]\alpha(t) [/math], [math]\sigma(t) [/math], [math]t:= 0 [/math]

Шаг №1. Инициализировать векторы начальных весов нейронов [math] \vec{w}^{(j)}(0) \forall j=1,..,M[/math]. Подробнее о стратегии начальной инициализации далее.

шаг №2. Если есть еще элементы в обучающей выборке, вытащить случайным образом (например, индекс [math]i[/math] - может быть реализацией случайной величины из равномерного дискретного распределения на [math] [0,N] [/math]) входной вектор [math]\vec{x}^{(i)}(t), N:=N-1, \chi = \chi \setminus \vec{x}^{(i)}(t)[/math], в противном случае алгоритм завершает свою работу

шаг №3. Для [math]\vec{x}^{(i)}(t)[/math] и [math] \vec{w}^{(j)}(t) \forall j=1,..,M[/math] найти [math] = \rho(\vec{x}^{(i)}(t), \vec{w}^{(j)}(t)) = || \vec{x}^{(i)}(t) - \vec{w}^{(j)}(t)||^2 [/math].

шаг №4. Находим нейрон-победитель [math]ne_c[/math], [math] c = \arg \min_{\forall j \in \{1, \dots, L\}} \rho(\vec{x}^{(i)}(t), \vec{w}^{(j)}(t))[/math], который лежит ближе к текущему объекту [math]\vec{x}^{(i)}(t)[/math] по рассматриваемой метрике [math] || \circ || [/math].

шаг №5. Для всех нейронов [math] ne_{j} [/math] выполнить пересчет весовых векторов: [math] \vec{w}^{(j)}(t+1) := \vec{w}^{(j)}(t) +\alpha(t)h_{ci}(t)[\vec{x}^{(i)}(t) - \vec{w}^{(j)}(t)][/math].

шаг №6. [math]t := t+1 [/math]

шаг №7. Перейти к шагу 2.

1.2.3 Настройка алгоритма

В этом разделе опишем более подробно настраиваемые аспекты алгоритма.

1.2.3.1 Выбор начального приближения для [math]\vec{w}^{j}(0) \forall j=1,\dots,M[/math]

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

Во-вторых, инициализацию весов можно проводить какими-то случайными значениями. Например можно взять нескорое распределение, пусть равномерное или нормальное, и для каждой сгенерировать псевдослучайное число из выбранного распределения, то есть [math] w_i^{(j)} \sim \mathbf P [/math], где [math] \mathbf P [/math] - это заданное распределение. Плюсом данного подхода является простота однако, "настройка" в данном случае может быть долгой.

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

1.2.3.2 Выбор скорости обучения сети

Функцию скорости обучения сети [math]\alpha(t)[/math] можно выбрать, например, следующим образом:

Самый простой способ: [math]\alpha(t) := \frac{A}{B+t}[/math], где [math]A = const, B = const [/math]

Экспоненциальная скорость обучения: [math]\alpha(t) := \alpha_0 e^{ -\frac{t}{\lambda}}, \lambda \in (0, 1), \lambda = const, \alpha_0 = const[/math]

Показательная скорость обучения: [math]\alpha(t) := \lambda^{\frac{t}{T}}, \lambda \in (0, 1), \lambda = const[/math]

1.2.3.3 Выбор функции соседства между нейронами

Обычно полагают [math] h_{cj}(t) := \alpha(t) h(d,t) [/math], где [math] d = || ne_c - ne_j ||, c [/math] -индекс нейрона победителя, при этом:

[math] h(d,t) = \begin{cases}const, d\leq \sigma(t) \\0, d \gt \sigma(t) \end{cases}[/math]

[math] h(d,t) = e ^{-\frac{d^2}{2(\sigma(t)^2)}}[/math], где [math]\sigma(t)[/math] - это некоторый сомножитель, уменьшающий количество соседей, которые будут подвержены корректировке весов с увеличением итераций, эта функция монотонно убывает.

Функция [math] \sigma(t) [/math] также является параметром алгоритма. Возможная функциональная зависимость для нее: [math]\sigma(t) = \frac{\sigma_0}{1 + \frac{t}{T}}[/math], где [math]T[/math] - максимальное количество итераций, а [math]\sigma_0 = \max \left\{ \frac{a}{2}, \frac{b}{2} \right\} [/math],

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

1.2.4 Алгоритм работы карты

шаг 0. Пока есть вектора в тестовой выборке извлечь (последовательно), [math]\vec{x}^{(i)}, K:=K-1, \Phi = \Phi \setminus \vec{x}^{(i)}[/math], в противном случае алгоритм завершает свою работу.

шаг 1. Для [math]\vec{x}^{(i)}[/math] и [math] \vec{w}^{(j)} \forall j=1,..,M[/math] найти [math] = \rho(\vec{x}^{(i)}, \vec{w}^{(j)}) = || \vec{x}^{(i)} - \vec{w}^{(j)}||^2 [/math].

шаг 2. Находим нейрон-победитель [math]ne_c[/math], [math] c = \arg \min_{\forall j \in \{1, \dots, L\}} \rho(\vec{x}^{(i)}, \vec{w}^{(j)})[/math], который лежит ближе к текущему объекту [math]\vec{x}^{(i)}[/math] по рассматриваемой метрике [math] || \circ || [/math] и относим [math]\vec{x}^{(i)} [/math] к кластеру, соответствующему нейрону [math]ne_c[/math].

шаг 3. Переход к шагу 0.

1.6 Последовательная сложность алгоритма

Fyffdfghdgh

sd