Участник:Emaksimov/Кластеризация сетями Кохонена

Кластеризация сетями Кохонена
Последовательный алгоритм
Последовательная сложность	[math]O(tnkd)[/math]
Объём входных данных	[math]nd[/math]
Объём выходных данных	[math]n[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]O(t * \log kdn)[/math]
Ширина ярусно-параллельной формы	[math]O(kdn)[/math]

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

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

Искусственная нейронная сеть Кохонена или самоорганизующаяся карта признаков (SOM) была предложена финским исследователем Тойво Кохоненом в начале 1980-х годов.

Рисунок 2. Кохонен, Теуво.

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

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

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

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

Рисунок 1. Кластеризация сетями Кохонена

Пусть имеется некоторое множество векторов [math] x^{(i)}=(x_1^{(i)},x_2^{(i)},...,x_m^{(i)}) \in \mathbb{R}^m, i=1, \dots, k[/math]. Заранее зададим количество кластеров равным [math]n[/math]. Соответственно, Карта Кохонена представляет собой двухслойную fully-connected нейронную сеть, где первый слой состоит из [math]m[/math] нейронов, а второй - из [math]n[/math]. Каждый j-ый нейрон описывается вектором весов [math] w_j=(w_{1j},w_{2j},...,w_{mj}), j=1, \dots, n[/math].

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

Обучение состоит из последовательности коррекций векторов, представляющих собой нейроны. Сначала следует инициализировать векторы весов. Далее определенное количество раз (эпох) производятся следующие действия:

1. Случайным образов выбирается вектор [math]x(t)[/math] из входных данных.

1. Выбирается нейрон-победитель [math]w_c[/math] "наиболее похожий" (по евклидову расстоянию) на вектор [math]x(t)[/math]:

[math] ||x(t)-w_c||=\min\limits_{i}(||x(t)-w_i(t)||)[/math].

1. Веса всех нейронов обновляются по формуле:

[math] w_i(t+1)=w_i(t)+\alpha(t)h_{ic}(t)||x(t)-w_i(t)||[/math],

где [math]t[/math] - номер эпохи, [math] h_{ic}(t)[/math]- функция соседства нейронов, [math]\alpha (t)[/math] - функция скорости обучения сети.

Инициализация начальных весов

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

Функция соседства нейронов

Функции от расстояния применяются двух видов:

Константа: [math] h(d,t) = \begin{cases} c, & \mbox{if } n \ d\lt =\delta \\ 0, & \mbox{if } n \ d\gt \delta \end{cases}[/math]

Функция Гаусса: [math]h_{ic}(t)=\exp(-\frac{\|r_c-r_i\|^2}{2\sigma^2(t)})[/math],

где [math]r_i[/math] определяет положение [math]i[/math]-го нейрона в сетке

Функция скорости обучения сети

Главное требование к ней - монотонное убывание при возрастании [math]t[/math] для замедления темпов вариации весов нейронов слоя Кохонена. Функция может быть задана, например, как [math]\alpha(t)=\frac{A}{B+t}[/math], где [math]A[/math] и [math]B[/math] - некоторые константы.

1.3 Вычислительное ядро алгоритма

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

1.4 Макроструктура алгоритма

[math]\mathbf{W} \leftarrow ComputeInitialWeights(\mathbf{W})[/math]

Далее следует цикл, повторяющийся [math]T_{max}[/math] (максимальное число "эпох") раз:

1. [math]\mathbf{W_i} \leftarrow CalculateEucledeNorm(\mathbf{W_i})[/math]
2. [math]\mathbf{W_i(t+1)}\leftarrow CorrectWeights(\mathbf{W_i(t)})[/math]

1.5 Схема реализации последовательного алгоритма

[math]\mathbf{W} := InitializeWeights()[/math]
[math]\mathbf{FOR} \ t=1 \ \mathbf{TO} \ T_{max} \ \mathbf{DO}[/math]
    [math] \quad \mathcal{X} \leftarrow ChooseRandomVector\left( \{1, \dots, N\} \right)[/math]
    [math]\mathbf{FOR} \ t=1 \ \mathbf{TO} \ T_{max} \ \mathbf{DO}[/math]
        [math]CalculateEucledeNorm(\mathbf{W_i})[/math]
        [math]\mathbf{W_i(t+1)} \leftarrow CorrectWeights(\mathbf{W_i(t)})[/math]

1.9 Входные и выходные данные алгоритма

Входные данные: множество входных векторов (нейронов первого уровня), множество кластеров (выходов, нейронов второго уровня), максимальное число "эпох" [math]T_{max}[/math], константа [math] \delta [/math], константы [math]A[/math] и [math]B[/math], константа [math]c[/math] (в случае, если выбрана простая константа).

Выходные данные: матрица весов

1.10 Свойства алгоритма

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

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