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

Кластеризация сетями Кохонена
Последовательный алгоритм
Последовательная сложность	[math]O(Tmn)[/math]
Объём входных данных	[math]mk[/math]
Объём выходных данных	[math]mn[/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 Вычислительное ядро алгоритма

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

• Вычисление расстояния от случайно выбранного вектора [math]x(t)[/math] до каждого нейрона и выбор нейрона с наименьшим расстоянием. Т.е. вычисление [math]n[/math] евклидовых расстояний и сортировка полученного массива расстояний. Сложность евклидового расстояния растет линейно с увеличением длины вектора. Следовательно получаем сложность данного шага [math]O(mn)[/math].
• Обновление весов всех нейронов. Пусть используется гауссовская функция для вычисления расстояний между нейронами. Сложность обновления веса одного нейрона линейно зависит от [math]m[/math]. Т.е. сложность данного шага также [math]O(mn)[/math].

В итоге получаем, что для всего алгоритма с количеством эпох равным [math]T[/math] сложность составляет [math]O(Tmn)[/math].

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

Алгоритм кластеризации можно разбить на следующие этапы:

• Инициализация [math]\mathbf{W} \leftarrow ComputeInitialWeights(\mathbf{W})[/math]

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

1. [math]\mathbf{X} \leftarrow ChooseRandomVector(\mathbf{V})[/math]
2. Вложенный цикл, в котором осуществляется вычисление расстояний [math]\mathbf{D_i} \leftarrow CalculateEucledeNorm(X, \mathbf{W_i})[/math]
3. Выбор победителя [math]\mathbf{W_c} \leftarrow ChooseWinner(\mathbf{D_i})[/math]
4. Вложенный цикл, в котором осуществляется корректировка весов [math]\mathbf{W_i(t+1)}\leftarrow CorrectWeights(\mathbf{W_i(t)})[/math]

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

Пусть [math]\mathbf{W}[/math] - матрица весов, [math]T_{max}[/math] - максимальное число "эпох", [math]k[/math] - мощность входного множества, [math]N[/math] - число нейронов выходного слоя. Тогда схема реализации последовательного алгоритма будет выглядеть следующим образом:

[math]\mathbf{W} := InitializeWeights()[/math]
[math]\mathbf{FOR} \ t:=1 \ \mathbf{TO} \ T_{max} \ \mathbf{DO}[/math]
    [math] \quad \mathbf{X} := ChooseRandomVector\left( \{1, \dots, k\} \right)[/math]
    [math]\mathbf{FOR} \ i:=1 \ \mathbf{TO} \ N \ \mathbf{DO}[/math]
        [math]\mathbf{D} := CalculateEucledeNorm(\mathbf{X}, \mathbf{W_i})[/math]
    [math]\mathbf{W_c} := ChooseWinner(\mathbf{D})[/math]
    [math]\mathbf{FOR} \ i:=1 \ \mathbf{TO} \ N \ \mathbf{DO} \ \mathbf{AND} \ \mathbf{i} \neq \mathbf{c}[/math]
        [math]\mathbf{W_i(t+1)} := CorrectWeights(\mathbf{W_i(t)}, \mathbf{W_c})[/math]

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

Рассмотрим вычислительную сложность описанного алгоритма. Основная часть операций алгоритма приходится на вложенные циклы, где

• выполняется вычисление [math]N[/math] евклидовых норм, функция ([math]CalculateEucledeNorm[/math]), на вычисление каждой из которых требуется по [math]m*N[/math] операций умножения и [math]m*(N-1)[/math] операций сложения ([math]m[/math] - размерность входных векторов) для вычисления всех норм
• на сравнение [math]N[/math] вещественных чисел (функция [math]ChooseWinner[/math])
• на корректировку весов - порядка [math]m*N[/math] операций

1.7 Информационный граф

Общая схема работы алгоритма выглядит следующим образом:

Общая схема работы алгоритма кластеризации

Здесь In - входные данные, Init - шаг, на котором происходит инициализация весов, Norm - вычисление расстояний, Win - выбор победителя, Correct - корректировка весов, Out - выходные данные.

Опишем информационный граф алгоритма.

Первый ярус состоит из [math]n[/math] параллельных операций вычисления евклидового расстояния до случайно выбранного входного вектора.

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

Первый ярус алгоритма

Второй ярус состоит их [math]n[/math] параллельных операций коррекций весов.

Второй ярус алгоритма

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

1.8 Ресурс параллелизма алгоритма

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

Итоговая сложность параллельного алгоритма будет определяться, исходя из формулы [math]Complexity = T * (PComplexity_{Norm} + PComplexity_{Winner} + PComplexity_{Correct})[/math], где [math]PComplexity_{Norm}[/math] - параллельная сложность поиска евклидовых расстояний для определения нейрона-победителя, [math]PComplexity_{Correct}[/math] - параллельная сложность обновления весов нейронов, [math]PComplexity_{Winner}[/math] - сложность глобального поиска минимального значения расстояния, [math]T[/math] - количество эпох (итераций) алгоритма.

Этап Norm заключается в параллельном вычислении евклидовых норм. Сложность этого этапа можно оценить с учетом доступности неограниченного числа процессоров как [math]O(\log m)[/math], где [math]m[/math] - длина векторов. Этап Winner заключается в поиске минимума по подсчитанным расстояниям для определения нейрона-победителя. Параллельная сложность реализации операции нахождения минимума из [math]n[/math] элементов определяется как [math]O(\log n)[/math]. Этап Correct состоит из нескольких операций, но асимптотически сложность определяет именно подсчет евклидова расстояния. Аналогично получаем, что сложность данного этапа составляет [math]O(\log m)[/math].

Итоговую параллельную сложность кластеризации сетями Кохонена можно оценить как [math]O(t * \log max(m,n))[/math].

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

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

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

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

Вычислительная мощность

Вычислительная мощность алгоритма кластеризации сетями Кохонена равна [math]\frac{m*n*T}{m*k+m*n} = \frac{n*T}{k+n}[/math], где, напомним, [math]T[/math] - число итераций, [math]n[/math] - число нейронов выходного слоя, [math]k[/math] - мощность входного множества.

Детерминированность и Устойчивость

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

Сильные и слабые стороны алгоритма

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

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

2 Программная реализация алгоритма

2.7 Существующие реализации алгоритма

Последовательные реализации:

• kohonen Бибилиотека для R
• kohonen Бибилиотека для Python
• KNNL: C++ бибилиотека.
• Matlab realization: Реализация в Matlab.
• JKNNL: Библиотека для Java.
• SAS EM: Реализация в SAS Enterprise Miner

Параллельные реализации:

• Somoclu: Библиотека для Python, R, Julia, и Matlab с поддержкой OpenMP, MPI и CUDA.