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

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

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

Задача кластеризации — это задача, в которой требуется разбить объекты во ыходных данных на группы, иначе называемые кластерами, таким образом, что внутри каждого кластера объекты в каком-то смысле похожи, а объекты в разных кластерах в каком-то смысле различны. Алгоритм кластеризации, основанный на сетях Кохонена, предназначен для кластеризации вещественных векторов. В основе алгоритма лежит однослойная нейронная сеть, называемая картой Кохонена. Нейроны образуют сетку, в которой каждый нейрон имеет свои координаты. У каждого нейрона есть вектор весов, размерность которого равна размерности входных векторов. Все узлы входного слоя соединены с каждым из нейронов.

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

Процесс обучения сети состоит в «соревновании» между нейронами. На каждом шаге случайным образом выбирается один из входных векторов. Из всех нейронов выбирается нейрон-победитель, который имеет наименьшее расстояние между вектором весов и входным вектором. Векторы весов всех нейронов, находящихся в пределах радиуса обучения от нейрона-победителя, сдвигаются в сторону входного вектора Вектор весов этого нейрона сдвигается в сторону входного вектора. Также в сторону входного вектора сдвигаются векторы весов остальных нейронов, причем степень сдвига зависит от расстояния до нейрона-победителя на сетке. В результате этого процесса векторы весов нейронов распределяются по входному пространству.

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

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

1.2.1 Обозначения и формулы

Входные данные: набор вещественных векторов $x_1, x_2, ..., x_N$, где $x_i$ принадлежит $R^m$, N — число входных векторов

Текущее время: $t$

Входной вектор, выбранный случайным образом в момент времени $t$: $x^{t}$

Веса нейронов: набор векторов $w_{1}^{t}, w_{2}^{t}, ..., w_{n}^{t}$, где $w_{j}^{t}$ принадлежит $R^m$, $n$ — число нейронов, $t$ - текущее время

Нейрон-победитель: его номер определяется формулой $c = arg \min_{j} \parallel x^{t} - w_{j}^{t} \parallel$

Функция скорости обучения сети: $a\left(t\right) = a_0 \cdot exp\left\{-\frac{t}{\lambda}\right\}$, где $a_0, \lambda$ - настраиваемые параметры. Возможно использование других функций.

Радиус нейрона-победителя: $\sigma\left(t\right) = \sigma_0 \cdot exp\left\{-\frac{t}{\lambda}\right\}$, где $\sigma_0, \lambda$ - настраиваемые параметры.

Функция расстояния между нейроном-победителем и другим нейроном: $h\left(d, t\right) = exp\left\{-\frac{d^2}{2 \cdot \sigma^2\left(t\right)}\right\}$, где $d$ - расстояние между нейроном-победителем и другим нейроном на сетке.

Функция соседства нейрона $j$: $h_{j}\left(t\right) = h\left(\parallel w_{c}^{t} - w_{j}^{t} \parallel, t\right) \cdot a\left(t\right)$, где $h\left(\parallel w_{c}^{t} - w_{j}^{t} \parallel, t\right)$ - функция расстояния между нейроном $j$ и нейроном-победителем.

Данные, вычисляемые при обучении сети: веса нейронов в момент времени $t + 1$, вычисляемые по формуле $w_{j}^{t + 1} = w_{j}^{t} + h_j(t) \cdot \left[x^{t} - w_{j}^{t}\right]$, где $x^{t}$ - случайным образом выбранный входной вектор, $w_{j}^{t}$ - вектор весов нейрона $j$ в момент времени $t$, $h_{j}\left(t\right)$ - функция соседства нейрона $j$

Данные, вычисляемые при использовании сети: Расстояния между векторами весов нейронов и входным вектором: $\parallel x_i - w_j \parallel$ для всех $j \in \left\{1, 2, \dots, n\right\}$

1.2.2 Шаги обучения сети

1. Проинициализировать время: $t = 0$ и выбрать максимальное время $t_{max}$
2. Проинициализировать векторы весов нейронов случайным образом
3. Случайным образом выбрать входной вектор $x^{t}$
4. Вычислить расстояния от векторов весов нейронов до входного вектора
5. Найти номер $c$ нейрона-победителя, у которого расстояние от вектора весов до входного вектора минимально
6. Вычислить радиус обучения $\sigma\left(t\right)$
7. Вычислить расстояния на сетке от нейрона-победителя до остальных нейронов
8. Для всех нейронов, находящихся в пределах радиуса обучения от нейрона-победителя, вычислить новые векторы весов
9. Увеличить время: $t = t + 1$
10. Если текущее время $t$ равно максимальному $t_{max}$, то алгоритм завершается. Иначе перейти на шаг 3.

1.2.3 Шаги использования сети

1. Вычислить расстояния от векторов весов нейронов до входного вектора
2. Активировать нейрон с минимальным расстоянием