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

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

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

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

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

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

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

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

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

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

Текущее время: [math]\displaystyle{ t }[/math]

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

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

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

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

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

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

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

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

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

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

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

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

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