Участник:Urandon/Строгий алгоритм С средних (Hard C-Means, HCM): различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 39: Строка 39:
 
'''''Шаг 1 -- инициализация центров кластеров'''''
 
'''''Шаг 1 -- инициализация центров кластеров'''''
  
<math> c_i \sim Uniform\{u_1, \dots, u_N\} </math> -- инициализация путём
+
<math> c_i \sim Uniform \{u_1, \dots, u_N\} </math> -- инициализация путём
 
случайного выбора центров кластеров из точек входного набора. Начальные центры кластером так же могут быть заданы пользователем явно.
 
случайного выбора центров кластеров из точек входного набора. Начальные центры кластером так же могут быть заданы пользователем явно.
  

Версия 23:23, 20 января 2017

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


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

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

Строгий алгоритм C средних (Hard C-Means; Jang, Sun and Mizutani, 1997[1]) пытается определить центры кластеров в многомерном признаковом пространстве[2]. Цель заключается в том, что бы сопоставить каждой точке признакового пространства соответствующий кластер.

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

На вход алгоритму задаются точки конечномерного признакового пространства и количество кластеров. Так же могут задаваться пороговые значения, использующиеся в критерии останова алгоритма: величина целевого функционала, скорость изменения функционала при выполнении основного цикла алгоритма. Целевой функционал алгоритма -- среднее внутрикластерное расстояние.

На первом шаге алгоритма производится инициализация центров кластеров. Это может быть осуществлено путём выбора случайных значений. Затем выполняется основной цикл алгоритма:

  1. Расчёт рядовой матрицы, сопоставляющей каждую точку признакового пространства с ближайшим к ней кластерному центру. Иначе это можно рассматривать как оптимизацию целевого функционала по принадлежности точек к кластерам
  2. Расчёт целевого функционала. Проверка условий критерия останова и выход из цикла в случае его выполнения.
  3. Пересчёт кластерных центров как центров масс точек кластера. Представляет собой оптимизацию целевого функционала по координатам центров кластеров.

Алгоритм гарантирует монотонное невозрастание целевой функционала, следовательно, сходимость к локальному минимуму.


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] -- инициализация путём случайного выбора центров кластеров из точек входного набора. Начальные центры кластером так же могут быть заданы пользователем явно.

Шаг 2 -- вычисление рядовой матрицы [math]M[/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 Литература

  1. 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.
  2. Jan Jantzen (1998). Neurofuzzy Modelling.
  3. Нейский И. М. Классификация и сравнение методов кластеризации. // Интеллектуальные технологии и системы. Сборник учебно-методических работ и статей аспирантов и студентов. – М.: НОК «CLAIM», 2006. – Выпуск 8. – С. 130-142.