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

Участник:Karibov/Алгоритм кластеризации с использованием представлений: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 14: Строка 14:
 
Выполняет иерархическую кластеризацию с использованием набора определяющих точек для
 
Выполняет иерархическую кластеризацию с использованием набора определяющих точек для
 
определения объекта в кластер.
 
определения объекта в кластер.
 +
 
Назначение: кластеризация очень больших наборов числовых данных.
 
Назначение: кластеризация очень больших наборов числовых данных.
 +
 
Ограничения: эффективен для данных низкой размерности, работает только на числовых данных.
 
Ограничения: эффективен для данных низкой размерности, работает только на числовых данных.
 +
 
Достоинства: выполняет кластеризацию на высоком уровне даже при наличии выбросов, выделяет
 
Достоинства: выполняет кластеризацию на высоком уровне даже при наличии выбросов, выделяет
 
кластеры сложной формы и различных размеров, обладает линейно зависимыми требованиями к месту
 
кластеры сложной формы и различных размеров, обладает линейно зависимыми требованиями к месту
Строка 21: Строка 24:
 
Недостатки: есть необходимость в задании пороговых значений и количества кластеров.
 
Недостатки: есть необходимость в задании пороговых значений и количества кластеров.
 
Описание алгоритма:
 
Описание алгоритма:
 +
 
Шаг 1: Построение дерева кластеров, состоящего из каждой строки входного набора данных.
 
Шаг 1: Построение дерева кластеров, состоящего из каждой строки входного набора данных.
 +
 
Шаг 2: Формирование «кучи» в оперативной памяти, расчет расстояния до ближайшего кластера
 
Шаг 2: Формирование «кучи» в оперативной памяти, расчет расстояния до ближайшего кластера
 
(строки данных) для каждого кластера. При формировании кучи кластеры сортируются по возрастанию
 
(строки данных) для каждого кластера. При формировании кучи кластеры сортируются по возрастанию
Строка 27: Строка 32:
 
ближайшим элементам из соседних кластеров. Для определения расстояния между кластерами
 
ближайшим элементам из соседних кластеров. Для определения расстояния между кластерами
 
используются «манхеттенская», «евклидова» метрики или похожие на них функции.
 
используются «манхеттенская», «евклидова» метрики или похожие на них функции.
2
+
 
 
Шаг 3: Слияние ближних кластеров в один кластер. Новый кластер получает все точки входящих в
 
Шаг 3: Слияние ближних кластеров в один кластер. Новый кластер получает все точки входящих в
 
него входных данных. Расчет расстояния до остальных кластеров для новообразованного кластера. Для
 
него входных данных. Расчет расстояния до остальных кластеров для новообразованного кластера. Для
Строка 38: Строка 43:
 
выполняется следующее: если расстояние до новообразованного кластера ближе, чем предыдущий
 
выполняется следующее: если расстояние до новообразованного кластера ближе, чем предыдущий
 
ближайший кластер, то ближайший кластер меняется. В противном случае ничего не происходит.
 
ближайший кластер, то ближайший кластер меняется. В противном случае ничего не происходит.
 +
 
Шаг 4: Переход на шаг 3, если не получено требуемое количество кластеров.
 
Шаг 4: Переход на шаг 3, если не получено требуемое количество кластеров.
  

Версия 13:10, 15 октября 2016


Алгоритм кластеризации с использованием представлений
Последовательный алгоритм
Последовательная сложность [math][/math]
Объём входных данных [math][/math]
Объём выходных данных [math][/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [math][/math]
Ширина ярусно-параллельной формы [math][/math]


Основные авторы описания: Карибов Евгений, Курашов Александр

1 ЧАСТЬ. Свойства и структура алгоритмов

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

Выполняет иерархическую кластеризацию с использованием набора определяющих точек для определения объекта в кластер.

Назначение: кластеризация очень больших наборов числовых данных.

Ограничения: эффективен для данных низкой размерности, работает только на числовых данных.

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

Шаг 1: Построение дерева кластеров, состоящего из каждой строки входного набора данных.

Шаг 2: Формирование «кучи» в оперативной памяти, расчет расстояния до ближайшего кластера (строки данных) для каждого кластера. При формировании кучи кластеры сортируются по возрастанию дистанции от кластера до ближайшего кластера. Расстояние между кластерами определяется по двум ближайшим элементам из соседних кластеров. Для определения расстояния между кластерами используются «манхеттенская», «евклидова» метрики или похожие на них функции.

Шаг 3: Слияние ближних кластеров в один кластер. Новый кластер получает все точки входящих в него входных данных. Расчет расстояния до остальных кластеров для новообразованного кластера. Для расчета расстояния кластеры делятся на две группы: первая группа – кластеры, у которых ближайшими кластерами считаются кластеры, входящие в новообразованный кластер, остальные кластеры – вторая группа. И при этом для кластеров из первой группы, если расстояние до новообразованного кластера меньше чем до предыдущего ближайшего кластера, то ближайший кластер меняется на новообразованный кластер. В противном случае ищется новый ближайший кластер, но при этом не берутся кластеры, расстояния до которых больше, чем до новообразованного кластера. Для кластеров второй группы выполняется следующее: если расстояние до новообразованного кластера ближе, чем предыдущий ближайший кластер, то ближайший кластер меняется. В противном случае ничего не происходит.

Шаг 4: Переход на шаг 3, если не получено требуемое количество кластеров.

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] Нейский И.М. Классификация и сравнение методов кластеризации http://it-claim.ru/Persons/Neyskiy/Article2_Neiskiy.pdf