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

Кластеризация сетями Кохонена

Рисунок 0.

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

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

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

Рисунок 1. Массив узлов в двумерной SOM сетке.

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

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

Каждый нейрон сети соединен со всеми компонентами n - мерного входного вектора $x(t)=[\xi_1(t),\xi_2(t),...,\xi_n(t)]$ Входной вектор— это описание одного из объектов, подлежащих кластеризации. Количество нейронов совпадает с количеством кластеров, которое должна выделить сеть.

Каждый j-ый нейрон описывается вектором весов $w_j(t)=(w_{j1}(t),...,w_{jn}(t))$, где n– число компонентов входных векторов.

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

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

шаг 0: Подача исходных данных на входы. Весовой вектор $w$ выбирается случайным образом. Величины $\alpha$, $h_{kc}$ известны.

шаг 1: Выбрать произвольное наблюдение $x ( t )$ из множества входных данных.

шаг 2: Определить расстояние между между входным вектором и каждого вектора весовых коэффициентов

$d_k(t)=||x(t)-w_k(t)||, k=1,...,n$,

шаг 3: Определение нейрона -победителя (веса которого в наименьшей степени отличаются от соответствующих компонентов входного вектора)

$d_w(t)=\min\limits_{k}(d_k(t)), k=1,...,n$

шаг 4: Векторы весовых коэффициентов обновляются с помощью функции соседства по формуле

$w_k(t+1)=w_k(t)+\alpha(t)h_{kc}(t)||x(t)-w_k(t)||,$

шаг 5: Прекратите, если максимальное число итераций достигнуто; в противном случае изменить параметры $\alpha$ и $h_{kc}$ продолжите с шага 1 .

Переменные

• $t$ -текущая итерация
• $\lambda$ -предельное значение итераций
• $x(t)$ -вектор входных данных
• $k$ -индекс узла в карте
• $w_k$ -текущий вектор веса в узле k
• $c$ -индекс нейрона-побдителя
• $h_{kc}(t)$- функция "соседства", определяет расстояне между нейроном $w_k$ и $w_c$
• $\alpha (t)$- монотонно убывающий коэффициент обучения .

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

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

• Инициализация случайными значениями, когда всем весам даются малые случайные величины.

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

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

Задание $h$

Часто в качестве функции соседства используется гауссовская функция:

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

где $0\lt \alpha(t)\lt 1$ — обучающий сомножитель, монотонно убывающий с каждой последующей итерацией (то есть определяющий приближение значения векторов веса нейрона-победителя и его соседей к наблюдению; чем больше шаг, тем меньше уточнение);
$r_k$, $r_c$ — координаты узлов $W_k(t)$ и $W_c(t)$ на карте;

$\sigma(t)$ — сомножитель, уменьшающий количество соседей с итерациями, монотонно убывает. Параметры $\alpha$, $\sigma$ и их характер убывания задаются аналитиком.

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

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

если $W_k(t)$ находится в окрестности $W_c(t)$ заранее заданного аналитиком радиуса, и 0 в противном случае. Функция $h(t)$ равна $\alpha(t)$ для BMU и уменьшается с удалением от BMU.