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

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

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

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

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

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

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

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

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

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

Текущее время: [math]t[/math]

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

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

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

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

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

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

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

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

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

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

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

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

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