Участник:Urandon/Строгий алгоритм С средних (Hard C-Means, HCM)
В первой части описываются собственно алгоритмы и их свойства, а вторая посвящена описанию особенностей их программной реализации с учетом конкретных программно-аппаратных платформ. Такое деление на части сделано для того, чтобы машинно-независимые свойства алгоритмов, которые определяют качество их реализации на параллельных вычислительных системах, были бы выделены и описаны отдельно от множества вопросов, связанных с последующими этапами программирования алгоритмов и исполнения результирующих программ.
Содержание
- 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]\mathbb{R}^D[/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 Вычислительное ядро алгоритма
Для каждой пары [math]\{u_i, c_k\}, i \in \mathbb{N}_N, k \in \mathbb{N}_C[/math] согласно алгоритму необходимо вычислить расстояние [math]\|u_i - c_k\|^2[/math] в [math]D[/math]-мерном пространстве. Такие расстояние вычисляются для [math]NC[/math] пар. Таким образом, происходит вычисление [math]O(NCD)[/math] арифметичеких операций.
1.4 Макроструктура алгоритма
Алгоритм распадается на макрооперации, примитивами которых выступают вектора линейных пространств.
Вычисление разностей векторов с последующим вычислением евклидовой нормы на втором шаге алгоритма. [math] d_{ik} = \|u_k - c_i\|^2 [/math]
Нахождение аргминимума в векторе при фиксированном объекте [math]k[/math]: [math] i^* = \arg\!\min\limits_{i = 1 \dots C} d_{ik} [/math]. После чего [math]m_{ik} := [i = i^*][/math].
Суммирование всех элементов матрицы с заранее определёнными индексами [math] J = \sum\limits_{i=1}^C J_i = \sum\limits_{i=1}^C \left( \sum\limits_{k:\, u_k \in C_i} d_{ki} \right) = \sum\limits_{k=1}^N d_{k, C(u_k)} [/math]
Умножение вектора на скаляр и сложение векторов [math] c_i = \frac{1}{|C_i|} \sum\limits_{k:\, u_k \in C_i} u_k, [/math]
1.5 Схема реализации последовательного алгоритма
Последовательная схема реализована в виде python-подобного псевдокода. Для оптимизации вычислений хранится структура, хранящая номер кластера для каждой точки. Это оптимизация с учётом разреженности матрицы [math]M[/math]
J_history = []
c = u[random.choice(N, C), :]
M = zeros(N, C)
clusterization = zeros(N) # sparse version of M
while not stop_criteria(J_history):
J_curr = 0
c_new_cnt = zeros(C)
c_new = zeros(N, C)
for i in range(N):
M[i, clusterization[i]] = 0
d_min, j_min = +inf, None
for j in range(C):
d_ij = 0
for k in range(D):
d_ij += (u[i,k] - c[j,k])**2
if d_ij < d_min:
d_min, j_min = d_ij, j
J_curr += d_min
clusterization[i] = j_min
M[i, j_min] = 1
for k in range(D):
c_new[clusterization[i], k] += u[i,k]
c_new_cnt[clusterization[i]] += 1
J_history.append(J_curr)
for j in range(C):
for k in range(D):
c_new[j, k] /= c_new_cnt[j]
c = c_new
1.6 Последовательная сложность алгоритма
На каждой итерации основного цикла алгоритма:
- Шаг 2 [math]NC[/math] операций вычисления квадратов расстояний до центров кластеров: [math]NCD[/math] разностей, возведеий в квадрат и [math]NC(D-1)[/math] сумм
- Шаг 2 [math]NC[/math] сравнений
- Шаг 3 [math]N[/math] векторных сложений: [math]NCD[/math] сложений
- Шаг 4 [math]N[/math] векторных сложений, [math]C[/math] векторных умножений на скаляр, [math]C[/math] сложений: [math]ND+C[/math] сложений и [math]CD[/math] умножений.
Итого, одна итерация основного цикла стоит [math]O(3NCD)[/math] элементарных операций. Количество итераций зависит от данных, от начального приближения кластеризации, от критерия останова.
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.