Участник:Адиев Тохтар/Алгоритм кластеризации, основанный на сетях Кохоннена

Алгоритм кластеризации, основанный на сетях Кохонена

Основные авторы описания: Логвиненко Александра 613 и Адиев Тохтар 616

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

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

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

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

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

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

a)

б)

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

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

Алгоритм обучения Кохонена и карты Кохонена послужили основой для большого количества исследований в области нейронных сетей, благодаря чему Кохонен считается самым цитируемым финским ученым. Количество научных работ по картам Кохонена составляет около 8 000. Т. Кохонен — автор более 300 публикаций и 4 монографий

Общим недостатком всех рассмотренных алгоритмов обучения нейронной сети Кохонена является наличие в них большого числа эвристических параметров и искусственность предлагаемых решений проблемы «мертвых» нейронов.

Структура алгоритма - двухслойная нейронная сеть.

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

Рассмотрим первые элементы данных, которые являются п-мерные евклидовы векторы

[math] x(t)=[\xi_1(t),\xi_2(t),...,\xi_n(t)][/math]

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

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

где [math] n[/math] - число выходящих нейронов

На втором шаге алгоритм ищет выигравшего нейрона [math] d_w[/math] то, есть нейрона, который наилучшим образом соответствует входному нейрону и характеризуется минимальным расстоянием от входного вектора

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

На третьем этапе алгоритм обновляет веса выигравшего нейрона и нейронов, которые лежат в определенной окрестности пользователем следующим образом

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

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