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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[math] d_k(t)=||x(t)-w_k(t)||, k=1,...,n[/math],

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

[math] d_w(t)=\min\limits_{k}(d_k(t)), k=1,...,n[/math]

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

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

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

Переменные

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

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

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

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

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

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

Задание [math]h[/math]

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

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

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

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

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

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

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