Участник:Urandon/Строгий алгоритм С средних (Hard C-Means, HCM): различия между версиями
Urandon (обсуждение | вклад) |
Urandon (обсуждение | вклад) |
||
| Строка 43: | Строка 43: | ||
'''''Шаг 2 – вычисление рядовой матрицы <math>M</math>''''' | '''''Шаг 2 – вычисление рядовой матрицы <math>M</math>''''' | ||
| − | < | + | <math>M = \|m_{ik}\|</math>. Здесь: |
| − | < | + | <math> |
m_{ik} = \begin{cases} | m_{ik} = \begin{cases} | ||
1, & \|u_k-c_i\|^2 \leqslant \|u_k-c_j\|^2 \;\; \text{for all } i \neq j; \;\; (i,j=1,2,\ldots,C; \; k = 1,2,\ldots,N)\\ | 1, & \|u_k-c_i\|^2 \leqslant \|u_k-c_j\|^2 \;\; \text{for all } i \neq j; \;\; (i,j=1,2,\ldots,C; \; k = 1,2,\ldots,N)\\ | ||
0, & \text{otherwise}. | 0, & \text{otherwise}. | ||
\end{cases} | \end{cases} | ||
| − | </ | + | </math> |
где <math>N</math> — количество элементов во входном наборе данных. | где <math>N</math> — количество элементов во входном наборе данных. | ||
| − | Представляет собой шаг < | + | Представляет собой шаг <math>J \to \min_{M}</math> при условии, что каждый объект попадает хотя бы в один кластер. |
'''''Шаг 3 – расчёт целевого функционала''''' | '''''Шаг 3 – расчёт целевого функционала''''' | ||
| Строка 69: | Строка 69: | ||
</math> | </math> | ||
| − | Представляет собой шаг < | + | Представляет собой шаг <math>J \to \min_{c_1, \dots, c_N}</math> |
Версия 18:39, 31 января 2017
В первой части описываются собственно алгоритмы и их свойства, а вторая посвящена описанию особенностей их программной реализации с учетом конкретных программно-аппаратных платформ. Такое деление на части сделано для того, чтобы машинно-независимые свойства алгоритмов, которые определяют качество их реализации на параллельных вычислительных системах, были бы выделены и описаны отдельно от множества вопросов, связанных с последующими этапами программирования алгоритмов и исполнения результирующих программ.
Содержание
- 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]) пытается определить центры кластеров в многомерном признаковом пространстве[2]. Цель заключается в том, что бы сопоставить каждой точке признакового пространства соответствующий кластер.
Назначение алгоритма заключается в кластеризации больших наборов числовых данных представленных признаковыми описаниями объектов. Достоинства алгоритма в классе алгоритмов, решающих данную задачу, -- лёгкость реализации и вычислительная простота. Недостатки же -- явное задание количества кластеров, отсутствие гарантии нахождения оптимального решения.
На вход алгоритму задаются точки конечномерного признакового пространства и количество кластеров. Так же могут задаваться пороговые значения, использующиеся в критерии останова алгоритма: величина целевого функционала, скорость изменения функционала при выполнении основного цикла алгоритма. Целевой функционал алгоритма -- среднее внутрикластерное расстояние.
На первом шаге алгоритма производится инициализация центров кластеров. Это может быть осуществлено путём выбора случайных значений. Затем выполняется основной цикл алгоритма:
- Расчёт рядовой матрицы, сопоставляющей каждую точку признакового пространства с ближайшим к ней кластерному центру. Иначе это можно рассматривать как оптимизацию целевого функционала по принадлежности точек к кластерам
- Расчёт целевого функционала. Проверка условий критерия останова и выход из цикла в случае его выполнения.
- Пересчёт кластерных центров как центров масс точек кластера. Представляет собой оптимизацию целевого функционала по координатам центров кластеров.
Алгоритм гарантирует монотонное невозрастание целевой функционала, следовательно, сходимость к локальному минимуму.
1.2 Математическое описание алгоритма
На вход алгоритм принимает точки признакового пространства [math]\{u_k\}_{k=1}^{N}[/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]-му кластеру, и а [math]c_i[/math] -- центр [math]i[/math]-го кластера.
Алгоритм состоит из пяти шагов[3], включающих инициализацию и цикл оптимизации.
Шаг 1 – инициализация центров кластеров
[math] c_i \sim Uniform \{u_1, \dots, u_N\} [/math] -- инициализация путём случайного выбора центров кластеров из точек входного набора. Начальные центры кластером так же могут быть заданы пользователем явно. [math]test[/math]
Шаг 2 – вычисление рядовой матрицы [math]M[/math]
[math]M = \|m_{ik}\|[/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,j=1,2,\ldots,C; \; k = 1,2,\ldots,N)\\ 0, & \text{otherwise}. \end{cases} [/math] где [math]N[/math] — количество элементов во входном наборе данных.
Представляет собой шаг [math]J \to \min_{M}[/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]
На этом шаге, после расчёта целевого функционала проверяем критерий останова (зависит от реализации) и принимаем решение, следует ли остановить цикл оптимизации.
Шаг 4 – пересчёт кластерных центров
[math] c_i = \frac{1}{|C_i|} \sum\limits_{k:\, u_k \in C_i} u_k, [/math]
Представляет собой шаг [math]J \to \min_{c_1, \dots, c_N}[/math]
Шаг 5 – зацикливание
Переход по циклу к шагу 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 Литература
- ↑ Jang, J.-S. R., Sun, C.-T. and Mizutani, E. (1997). Neuro-Fuzzy and Soft Computing, number isbn 0-13-261066-3 in Matlab Curriculum Series, Prentice Hall, Upper Saddle River, NJ, USA.
- ↑ Jan Jantzen (1998). Neurofuzzy Modelling.
- ↑ Нейский И. М. Классификация и сравнение методов кластеризации. // Интеллектуальные технологии и системы. Сборник учебно-методических работ и статей аспирантов и студентов. – М.: НОК «CLAIM», 2006. – Выпуск 8. – С. 130-142.
