Участник:Ivan kolosov/Алгоритм кластеризации, основанный на сетях Кохоннена: различия между версиями
| Строка 5: | Строка 5: | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| − | Задача кластеризации — это задача, в которой требуется разбить объекты во | + | Задача кластеризации — это задача, в которой требуется разбить объекты во входных данных на группы, иначе называемые кластерами, таким образом, что внутри каждого кластера объекты в каком-то смысле похожи, а объекты в разных кластерах в каком-то смысле различны. Алгоритм кластеризации, основанный на сетях Кохонена, предназначен для кластеризации вещественных векторов. В основе алгоритма лежит однослойная нейронная сеть, называемая картой Кохонена. Нейроны образуют сетку, в которой каждый нейрон имеет свои координаты. У каждого нейрона есть вектор весов, размерность которого равна размерности входных векторов. Все узлы входного слоя соединены с каждым из нейронов. Всюду в данной статье будем считать, что сетка нейронов двумерная, хотя ее размерность может выбираться произвольно, в том числе она может быть одномерной или трехмерной. |
| − | Для того, чтобы определить кластер, к которому принадлежит данный входной вектор, вектор подают во входной слой сети. Для каждого нейрона вычисляется расстояние между входным вектором и вектором весов. Нейрон с наименьшим расстоянием между вектором весов и входным вектором | + | Для того, чтобы определить кластер, к которому принадлежит данный входной вектор, вектор подают во входной слой сети. Для каждого нейрона вычисляется расстояние между входным вектором и вектором весов. Нейрон с наименьшим расстоянием между вектором весов и входным вектором активируется, обозначая принадлежность входного вектора соответствующему кластеру. Таким образом, число кластеров определяется числом нейронов. Особенностью работы алгоритма является то, что близкие друг к другу входные векторы активируют нейроны, близкие друг к другу на сетке. Это свойство оказывается удобным для визуализации кластеризованных данных. |
| − | Процесс обучения сети состоит в «соревновании» между нейронами. На каждом шаге случайным образом выбирается один из входных векторов. Из всех нейронов выбирается нейрон-победитель, который имеет наименьшее расстояние между вектором весов и входным вектором. Векторы весов всех нейронов, находящихся в пределах радиуса обучения от нейрона-победителя, сдвигаются в сторону входного вектора Вектор весов этого нейрона сдвигается в сторону входного вектора. Также в сторону входного вектора сдвигаются векторы весов остальных нейронов, причем степень сдвига зависит от расстояния до нейрона-победителя на сетке. В результате этого процесса векторы весов нейронов распределяются по | + | Процесс обучения сети состоит в «соревновании» между нейронами. На каждом шаге случайным образом выбирается один из входных векторов. Из всех нейронов выбирается нейрон-победитель, который имеет наименьшее расстояние между вектором весов и входным вектором. Векторы весов всех нейронов, находящихся в пределах радиуса обучения от нейрона-победителя, сдвигаются в сторону входного вектора Вектор весов этого нейрона сдвигается в сторону входного вектора. Также в сторону входного вектора сдвигаются векторы весов остальных нейронов, причем степень сдвига зависит от расстояния до нейрона-победителя на сетке. В результате этого процесса векторы весов нейронов распределяются по пространству входных векторов. |
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
| Строка 23: | Строка 23: | ||
Входной вектор, выбранный случайным образом в момент времени <math>t</math>: <math>x^{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>n</math> |
| + | |||
| + | Размерность сетки нейронов: <math>D</math>. Как упоминалось выше, всюду в данной статье считаем сетку двумерной, т.е. <math>D = 2</math> | ||
| + | |||
| + | Размер двумерной сетки нейронов: <math>k</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>c = arg \min_{j} \parallel x^{t} - w_{j}^{t} \parallel</math> | ||
| − | Функция скорости обучения сети: <math>a\left(t\right) = a_0 \cdot exp\left\{-\frac{t}{\ | + | Функция скорости обучения сети: <math>a\left(t\right) = a_0 \cdot exp\left\{-\frac{t}{\lambda_{1}}\right\}</math>, где <math>a_0, \lambda_{1}</math> — настраиваемые параметры. Возможно использование других функций. |
| − | Радиус нейрона-победителя: <math>\sigma\left(t\right) = \sigma_0 \cdot exp\left\{-\frac{t}{\ | + | Радиус нейрона-победителя: <math>\sigma\left(t\right) = \sigma_0 \cdot exp\left\{-\frac{t}{\lambda_{2}}\right\}</math>, где <math>\sigma_0, \lambda_{2}</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>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>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>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> | Данные, вычисляемые при использовании сети: Расстояния между векторами весов нейронов и входным вектором: <math>\parallel x_i - w_j \parallel</math> для всех <math>j \in \left\{1, 2, \dots, n\right\}</math> | ||
| Строка 58: | Строка 64: | ||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
| + | |||
| + | Алгоритм имеет два вычислительных ядра — нахождение нейрона-победителя и пересчет векторов весов нейронов. Вычисление этих ядер повторяется друг за другом при обучении сети. При использовании сети выполняется только нахождение нейрона-победителя, при этом нейрон-победитель активируется и обозначает кластер, к которому принадлежит входной вектор. | ||
| + | |||
| + | Для нахождения нейрона-победителя вычисляются расстояния между векторами весов нейронов и входным вектором. Нейрон с минимальным расстоянием выбирается в качестве нейрона-победителя. | ||
| + | |||
| + | Для пересчета векторов весов нейронов вычисляется текущий радиус обучения, затем вычисляются расстояния на сетке между нейроном-победителем и остальными нейронами. Векторы весов нейронов, вошедших в радиус обучения, пересчитываются в соответствии с формулами. | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| + | |||
| + | Можно выделить следующие макрооперации: | ||
| + | |||
| + | # Выбор входного вектора | ||
| + | # Вычисление расстояний между векторами весов нейронов и входным вектором | ||
| + | # Нахождение минимального расстояния | ||
| + | # Нахождение радиуса обучения | ||
| + | # Вычисление расстояний между нейронами на сетке | ||
| + | # Пересчет векторов весов | ||
=== Схема реализации последовательного алгоритма === | === Схема реализации последовательного алгоритма === | ||
| + | |||
| + | ==== Последовательность выполнения обучения сети ==== | ||
| + | |||
| + | # Выбрать параметры <math>a_0, \lambda_{1}, \sigma_0, \lambda_{2}, t_{max}</math> | ||
| + | # <math>t = 0</math> | ||
| + | |||
| + | До тех пор, пока <math>t \neq t_{max}</math>, выполняются следующие шаги: | ||
| + | |||
| + | # Случайным образом выбрать входной вектор <math>x^{t}</math> | ||
| + | # <math>\forall j \in \left\{0, \ldots, n\right\}</math> вычислить <math>d_{j}^{t} = \parallel x^{t} - w_{j}^{t} \parallel</math> — расстояние между вектором весов нейрона <math>j</math> и входным вектором | ||
| + | # Найти <math>c = arg \min_{j} d_{j}^{t}</math> | ||
| + | # Вычислить текущий радиус обучения <math>\sigma\left(t\right) = \sigma_0 \cdot exp\left\{-\frac{t}{\lambda_{2}}\right\}</math> | ||
| + | # Вычислить текущую скорость обучения <math>a\left(t\right) = a_0 \cdot exp\left\{-\frac{t}{\lambda_{1}}\right\}</math> | ||
| + | # <math>\forall j \in \left\{0, \ldots, n\right\} \setminus \left\{c\right\}</math> вычислить расстояние от нейрона <math>j</math> до нейрона-победителя: <math>d_{cj}</math>. | ||
| + | # <math>\forall j: d_{c,j} < \sigma\left(t\right)</math> посчитать новый вес нейрона <math>j</math>: <math>w_{j}^{t + 1} = w_{j}^{t} + exp\left\{-\frac{d_{cj}^2}{2 \cdot \sigma^2\left(t\right)}\right\} \cdot a\left(t\right) \cdot \left[x^{t} - w_{j}^{t}\right]</math> | ||
| + | # <math>t = t + 1</math> | ||
| + | |||
| + | ==== Последовательность выполнения использования сети ==== | ||
| + | |||
| + | # <math>\forall j \in \left\{0, \ldots, n\right\}</math> вычислить <math>d_{j} = \parallel x - w_{j} \parallel</math> — расстояние между вектором весов нейрона <math>j</math> и входным вектором | ||
| + | # Найти <math>c = arg \min_{j} d_{j}</math> | ||
| + | # Активировать нейрон <math>c</math> | ||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
| + | |||
| + | Число сложений и вычитаний: <math>t_{max} \cdot \left(n \cdot \left(4m - 1\right) + \left(n - 1\right) \cdot \left(2D - 1\right)\right)</math> | ||
| + | |||
| + | Число умножений: <math>t_{max} \cdot \left( n \cdot \left(2m + 4\right) + \left(n - 1\right) \cdot D + 2\right)</math> | ||
| + | |||
| + | Число делений: <math>t_{max} \cdot \left(n + 2\right)</math> | ||
| + | |||
| + | Число вычислений квадратного корня: <math>t_{max} \cdot \left(2n -1\right)</math> | ||
| + | |||
| + | Число вычислений экспоненты: <math>t_{max} \cdot \left(n + 2\right)</math> | ||
=== Информационный граф === | === Информационный граф === | ||
Версия 14:20, 11 ноября 2016
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
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]n[/math]
Размерность сетки нейронов: [math]D[/math]. Как упоминалось выше, всюду в данной статье считаем сетку двумерной, т.е. [math]D = 2[/math]
Размер двумерной сетки нейронов: [math]k[/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_{1}}\right\}[/math], где [math]a_0, \lambda_{1}[/math] — настраиваемые параметры. Возможно использование других функций.
Радиус нейрона-победителя: [math]\sigma\left(t\right) = \sigma_0 \cdot exp\left\{-\frac{t}{\lambda_{2}}\right\}[/math], где [math]\sigma_0, \lambda_{2}[/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 Шаги обучения сети
- Проинициализировать время: [math]t = 0[/math] и выбрать максимальное время [math]t_{max}[/math]
- Проинициализировать векторы весов нейронов случайным образом
- Случайным образом выбрать входной вектор [math]x^{t}[/math]
- Вычислить расстояния от векторов весов нейронов до входного вектора
- Найти номер [math]c[/math] нейрона-победителя, у которого расстояние от вектора весов до входного вектора минимально
- Вычислить радиус обучения [math]\sigma\left(t\right)[/math]
- Вычислить расстояния на сетке от нейрона-победителя до остальных нейронов
- Для всех нейронов, находящихся в пределах радиуса обучения от нейрона-победителя, вычислить новые векторы весов
- Увеличить время: [math]t = t + 1[/math]
- Если текущее время [math]t[/math] равно максимальному [math]t_{max}[/math], то алгоритм завершается. Иначе перейти на шаг 3.
1.2.3 Шаги использования сети
- Вычислить расстояния от векторов весов нейронов до входного вектора
- Активировать нейрон с минимальным расстоянием
1.3 Вычислительное ядро алгоритма
Алгоритм имеет два вычислительных ядра — нахождение нейрона-победителя и пересчет векторов весов нейронов. Вычисление этих ядер повторяется друг за другом при обучении сети. При использовании сети выполняется только нахождение нейрона-победителя, при этом нейрон-победитель активируется и обозначает кластер, к которому принадлежит входной вектор.
Для нахождения нейрона-победителя вычисляются расстояния между векторами весов нейронов и входным вектором. Нейрон с минимальным расстоянием выбирается в качестве нейрона-победителя.
Для пересчета векторов весов нейронов вычисляется текущий радиус обучения, затем вычисляются расстояния на сетке между нейроном-победителем и остальными нейронами. Векторы весов нейронов, вошедших в радиус обучения, пересчитываются в соответствии с формулами.
1.4 Макроструктура алгоритма
Можно выделить следующие макрооперации:
- Выбор входного вектора
- Вычисление расстояний между векторами весов нейронов и входным вектором
- Нахождение минимального расстояния
- Нахождение радиуса обучения
- Вычисление расстояний между нейронами на сетке
- Пересчет векторов весов
1.5 Схема реализации последовательного алгоритма
1.5.1 Последовательность выполнения обучения сети
- Выбрать параметры [math]a_0, \lambda_{1}, \sigma_0, \lambda_{2}, t_{max}[/math]
- [math]t = 0[/math]
До тех пор, пока [math]t \neq t_{max}[/math], выполняются следующие шаги:
- Случайным образом выбрать входной вектор [math]x^{t}[/math]
- [math]\forall j \in \left\{0, \ldots, n\right\}[/math] вычислить [math]d_{j}^{t} = \parallel x^{t} - w_{j}^{t} \parallel[/math] — расстояние между вектором весов нейрона [math]j[/math] и входным вектором
- Найти [math]c = arg \min_{j} d_{j}^{t}[/math]
- Вычислить текущий радиус обучения [math]\sigma\left(t\right) = \sigma_0 \cdot exp\left\{-\frac{t}{\lambda_{2}}\right\}[/math]
- Вычислить текущую скорость обучения [math]a\left(t\right) = a_0 \cdot exp\left\{-\frac{t}{\lambda_{1}}\right\}[/math]
- [math]\forall j \in \left\{0, \ldots, n\right\} \setminus \left\{c\right\}[/math] вычислить расстояние от нейрона [math]j[/math] до нейрона-победителя: [math]d_{cj}[/math].
- [math]\forall j: d_{c,j} \lt \sigma\left(t\right)[/math] посчитать новый вес нейрона [math]j[/math]: [math]w_{j}^{t + 1} = w_{j}^{t} + exp\left\{-\frac{d_{cj}^2}{2 \cdot \sigma^2\left(t\right)}\right\} \cdot a\left(t\right) \cdot \left[x^{t} - w_{j}^{t}\right][/math]
- [math]t = t + 1[/math]
1.5.2 Последовательность выполнения использования сети
- [math]\forall j \in \left\{0, \ldots, n\right\}[/math] вычислить [math]d_{j} = \parallel x - w_{j} \parallel[/math] — расстояние между вектором весов нейрона [math]j[/math] и входным вектором
- Найти [math]c = arg \min_{j} d_{j}[/math]
- Активировать нейрон [math]c[/math]
1.6 Последовательная сложность алгоритма
Число сложений и вычитаний: [math]t_{max} \cdot \left(n \cdot \left(4m - 1\right) + \left(n - 1\right) \cdot \left(2D - 1\right)\right)[/math]
Число умножений: [math]t_{max} \cdot \left( n \cdot \left(2m + 4\right) + \left(n - 1\right) \cdot D + 2\right)[/math]
Число делений: [math]t_{max} \cdot \left(n + 2\right)[/math]
Число вычислений квадратного корня: [math]t_{max} \cdot \left(2n -1\right)[/math]
Число вычислений экспоненты: [math]t_{max} \cdot \left(n + 2\right)[/math]
