Уровень алгоритма

Участник:Каледа Александр/Строгий алгоритм С средних (Hard C-Means)

Материал из Алговики
Перейти к навигации Перейти к поиску


Строгий алгоритм С средних (Hard C-Means)
Последовательный алгоритм
Последовательная сложность [math]O(n)[/math]
Объём входных данных [math]nm+1[/math]
Объём выходных данных [math]n+Cm[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [math]O(1)[/math]
Ширина ярусно-параллельной формы [math]O(n)[/math]


Авторы описания: Каледа Александр, Шапулин Андрей.

Содержание

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

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

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

На вход алгоритму подается набор векторов и количество кластеров. Дополнительно может задаваться пороговая величина объектной функции, при достижении которой алгоритм останавливается. После окончания работы алгоритма каждый вектор будет отнесет к определенному кластерному центру. Алгоритм, являясь итерационным, зависит от начальных значений кластерных центров, а следовательно может не сходиться к локальному минимуму.

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

Вычисления, выполняющиеся на очередной итерации алгоритма:

  1. Расчёт рядовой матрицы (сопоставление вектора соответствующему кластерному центру).
  2. Расчёт объектной функции.
  3. Пересчёт кластерных центров.

1.2 Математическое описание алгоритма

1.2.1 Входные и выходные данные

1.2.2 Описание алгоритма

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности
2.2.1.2 Количественная оценка локальности

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Масштабируемость алгоритма

2.4.2 Масштабируемость реализации алгоритма

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

  1. Jan Jantzen «Neurofuzzy Modelling». Электронное издание.