Участник:Светлана Лукьяненко/Строгий алгоритм С средних (Hard C-Means, HCM): различия между версиями
Строка 1: | Строка 1: | ||
+ | {{algorithm | ||
+ | | name = Строгий алгоритм С средних (Hard C-Means,HCM) | ||
+ | | serial_complexity = <math>-</math> | ||
+ | | pf_height = <math>-</math> | ||
+ | | pf_width = <math>-</math> | ||
+ | | input_data = <math>mn+1</math> | ||
+ | | output_data = <math>cn</math> | ||
+ | }} | ||
+ | |||
+ | Авторы описания: [[Участник:Светлана_Лукьяненко|Лукьяненко Светлана]], [[Участник:Юрий_Комаров|Комаров Юрий]]. | ||
+ | |||
== Свойства и структура алгоритма == | == Свойства и структура алгоритма == | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
− | + | '''Строгий алгоритм C средних''' ('''''Hard C-Means'''''; ''Jang, Sun and Mizutani, 1997'') позволяет распределить большие наборы числовых данных по кластерам в многомерном пространстве<ref>Jan Jantzen «Neurofuzzy Modelling». Электронное издание.</ref>. Алгоритм является управляемым, так как для работы с ним требуется задание одного параметра — числа кластеров, на которое необходимо разделить данные. | |
− | |||
Входными данными для алгоритма является набор векторов и количество кластеров, так же может задаваться пороговое значение величины объектной функции, при достижении которого расчёт прекращается. Выходными данными для алгоритма являются значения кластерных центров и список векторов, принадлежащих каждому из кластеру. | Входными данными для алгоритма является набор векторов и количество кластеров, так же может задаваться пороговое значение величины объектной функции, при достижении которого расчёт прекращается. Выходными данными для алгоритма являются значения кластерных центров и список векторов, принадлежащих каждому из кластеру. | ||
Строка 19: | Строка 29: | ||
==== Входные и выходные данные ==== | ==== Входные и выходные данные ==== | ||
− | + | На вход подаётся набор векторов <math>\{u_k\}_{k=1}^{n}</math> пространства <math>\mathbb{R}^m</math> и количество кластеров <math>c</math>. | |
− | |||
− | |||
− | |||
− | + | Конечным результатом работы алгоритма является построенная рядовая матрица <math>M</math>, содержащая информацию о принадлежности элементов кластерам: | |
− | + | :<math> | |
+ | m_{ij} = \begin{cases} | ||
+ | 1, & u_j \in C_i, \\ | ||
+ | 0, & \text{otherwise}, | ||
+ | \end{cases} | ||
+ | </math> | ||
+ | где под <math>C_i</math> подразумевается <math>i</math>-ый построенный кластер. | ||
==== Описание алгоритма ==== | ==== Описание алгоритма ==== | ||
Строка 72: | Строка 85: | ||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
− | Вычислительное ядро алгоритма составляют вычисления квадратов нормы расстояния от каждого из векторов исходной выборки до промежуточных кластерных центров <math>\|u_k-c_i\|^2</math>. На каждой итерации алгоритма происходит расчёт <math> | + | Вычислительное ядро алгоритма составляют вычисления квадратов нормы расстояния от каждого из векторов исходной выборки до промежуточных кластерных центров <math>\|u_k-c_i\|^2</math>. На каждой итерации алгоритма происходит расчёт <math>cn</math> таких расстояний. |
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
Строка 81: | Строка 94: | ||
</math> | </math> | ||
− | + | Также на шаге вычисления объектной функции производится множественное суммирование полученных расстояний: | |
<math> | <math> | ||
Строка 105: | Строка 118: | ||
=== Входные и выходные данные алгоритма === | === Входные и выходные данные алгоритма === | ||
− | + | '''Входные данные:''' | |
+ | *<math>\{u_k\}_{k=1}^{n} \subset \mathbb{R}^m</math> — исходный набор векторов; | ||
+ | *<math>c</math> — желаемое количество кластеров (<math>2 \leqslant c \leqslant n</math>); | ||
+ | * ''(опционально)'' <math>\varepsilon_{tr}</math> — пороговая точность работы алгоритма. | ||
+ | |||
+ | '''Объём входных данных:''' <math>mn+1</math>. | ||
+ | |||
+ | '''Выходные данные:''' | ||
+ | *<math>M</math> — рядовая матрица из пространства <math>\mathbb{R}^{c \times n}</math>. | ||
− | + | '''Объём выходных данных:''' <math>cn</math>. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
=== Свойства алгоритма === | === Свойства алгоритма === | ||
+ | '''Назначение:''' кластеризация больших наборов числовых данных. | ||
+ | |||
+ | '''Достоинства:''' | ||
+ | * лёгкость реализации; | ||
+ | * вычислительная простота. | ||
+ | |||
+ | '''Недостатки:''' | ||
+ | * нет гарантии, что итеративный процесс сойдётся к оптимальному решению; | ||
+ | * производительность существенно зависит от выбора начальных кластерных центров. | ||
== Программная реализация алгоритма == | == Программная реализация алгоритма == |
Версия 14:06, 29 сентября 2016
Строгий алгоритм С средних (Hard C-Means,HCM) | |
Последовательный алгоритм | |
Последовательная сложность | [math]-[/math] |
Объём входных данных | [math]mn+1[/math] |
Объём выходных данных | [math]cn[/math] |
Параллельный алгоритм | |
Высота ярусно-параллельной формы | [math]-[/math] |
Ширина ярусно-параллельной формы | [math]-[/math] |
Авторы описания: Лукьяненко Светлана, Комаров Юрий.
Содержание
- 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 Общее описание алгоритма
Строгий алгоритм C средних (Hard C-Means; Jang, Sun and Mizutani, 1997) позволяет распределить большие наборы числовых данных по кластерам в многомерном пространстве[1]. Алгоритм является управляемым, так как для работы с ним требуется задание одного параметра — числа кластеров, на которое необходимо разделить данные. Входными данными для алгоритма является набор векторов и количество кластеров, так же может задаваться пороговое значение величины объектной функции, при достижении которого расчёт прекращается. Выходными данными для алгоритма являются значения кластерных центров и список векторов, принадлежащих каждому из кластеру.
Первым шагом выполнения алгоритма является инициализация центров кластеров случайными значениями. Дальнейшие шаги алгоритма выполняются итеративно до того момента, пока объектная функция не станет меньше порогового значения или значение объектной функции будет минимально отличаться от полученного на предыдущей итерации. На каждой итерации вычислений выполняются следующие действия:
1) Расчёт рядовой матрицы, которая показывает для каждого вектора ближайший кластерный центр.
2) Расчёт объектной функции. Проверка условий остановки и завершение расчета в случае их выполнения.
3) Пересчёт кластерных центров.
Так как алгоритм является итеративным и зависит от начальных значений кластерных центров, то он может сходиться локальному минимуму.
1.2 Математическое описание алгоритма
1.2.1 Входные и выходные данные
На вход подаётся набор векторов [math]\{u_k\}_{k=1}^{n}[/math] пространства [math]\mathbb{R}^m[/math] и количество кластеров [math]c[/math].
Конечным результатом работы алгоритма является построенная рядовая матрица [math]M[/math], содержащая информацию о принадлежности элементов кластерам:
- [math] m_{ij} = \begin{cases} 1, & u_j \in C_i, \\ 0, & \text{otherwise}, \end{cases} [/math]
где под [math]C_i[/math] подразумевается [math]i[/math]-ый построенный кластер.
1.2.2 Описание алгоритма
Алгоритм состоит из 5 последовательных шагов.[2]
Шаг 1
Инициализация кластерных центров [math]c_i \, (i=1,2,\ldots,c)[/math] может происходить за счёт случайного выбора необходимого числа точек из входного набора либо путём явного указания.
Шаг 2
Вычисление рядовой матрицы [math]M = \|m_{ik}\|[/math], элементы которой задаются следующими выражениями ([math]n[/math] — количество элементов во входном наборе данных):
- [math] m_{ik} = \begin{cases} 1, & \|u_k-c_i\|^2 \leqslant \|u_k-c_j\|^2 \;\; \text{for all } i \neq j; \;\; (i=1,2,\ldots,c, \; k = 1,2,\ldots,n)\\ 0, & \text{otherwise}. \end{cases} [/math]
Будем говорить, что [math]u_k \in C_i[/math], если [math]m_{ik} = 1[/math].
Шаг 3
Расчёт объектной функции:
- [math] J = \sum\limits_{i=1}^c J_i = \sum\limits_{i=1}^c \left( \sum\limits_{k:\, u_k \in C_i} \|u_k -c_i \|^2 \right) .[/math]
На этом шаге происходит остановка и выход из цикла, если полученное значение ниже пороговой величины [math]\varepsilon_{tr}[/math] или полученное значение не сильно отличается от значений, полученных на предыдущих циклах.
Шаг 4
Пересчёт кластерных центров выполняется в соответствии со следующим уравнением:
- [math] c_i = \frac{1}{|C_i|} \sum\limits_{k:\, u_k \in C_i} u_k, [/math]
где под [math]|C_i|[/math] подразумевается количество элементов в [math]i[/math]-ом кластере.
Шаг 5
Переход по циклу на шаг 2.
1.3 Вычислительное ядро алгоритма
Вычислительное ядро алгоритма составляют вычисления квадратов нормы расстояния от каждого из векторов исходной выборки до промежуточных кластерных центров [math]\|u_k-c_i\|^2[/math]. На каждой итерации алгоритма происходит расчёт [math]cn[/math] таких расстояний.
1.4 Макроструктура алгоритма
Основной операцией, выполняемой в алгоритме, как сказано выше, является операция нахождения расстояний между векторами данных и кластерными центрами.
[math] d_{ki} = \|u_k-c_i\|^2 [/math]
Также на шаге вычисления объектной функции производится множественное суммирование полученных расстояний:
[math] J = \sum\limits_{i=1}^c J_i = \sum\limits_{i=1}^c \left( \sum\limits_{k:\, u_k \in C_i} \|u_k -c_i \|^2 \right), [/math]
а на шаге расчета кластерных центров происходит суммирование векторов:
[math] c_i = \frac{1}{|C_i|} \sum\limits_{k:\, u_k \in C_i} u_k. [/math]
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
Для выполнения одной итерации строгого алгоритма C средних необходимо выполнить несколько ярусов вычислений:
- [math]n[/math] ярусов вычисления [math]c[/math] расстояний между векторами данных и центрами кластеров.
- [math]n[/math] ярусов нахождения минимального среди [math]c[/math] элементов (расстояний).
- Вычисление объектной функции.
- [math]c[/math] ярусов вычисления кластерных центров.
1.9 Входные и выходные данные алгоритма
Входные данные:
- [math]\{u_k\}_{k=1}^{n} \subset \mathbb{R}^m[/math] — исходный набор векторов;
- [math]c[/math] — желаемое количество кластеров ([math]2 \leqslant c \leqslant n[/math]);
- (опционально) [math]\varepsilon_{tr}[/math] — пороговая точность работы алгоритма.
Объём входных данных: [math]mn+1[/math].
Выходные данные:
- [math]M[/math] — рядовая матрица из пространства [math]\mathbb{R}^{c \times n}[/math].
Объём выходных данных: [math]cn[/math].
1.10 Свойства алгоритма
Назначение: кластеризация больших наборов числовых данных.
Достоинства:
- лёгкость реализации;
- вычислительная простота.
Недостатки:
- нет гарантии, что итеративный процесс сойдётся к оптимальному решению;
- производительность существенно зависит от выбора начальных кластерных центров.