Решение задачи поиска минимальных остовных деревьев ( mst minimum spanning tree) является распространенной задачей в различных областях исследований: распознавание различных объектов, компьютерное зрение, анализ и построение сетей

Введение
Решение задачи поиска минимальных остовных деревьев ( MST — minimum spanning tree) является распространенной задачей в различных областях исследований: распознавание различных объектов, компьютерное зрение, анализ и построение сетей (например, телефонных, электрических, компьютерных, дорожных и т.д.), химия и биология и многие другие. Существует по крайней мере три известных алгоритма, решающих данную задачу: Борувки, Крускала и Прима. Обработка больших графов (занимающих несколько ГБ) является достаточно трудоемкой задачей для центрального процессора (CPU) и является востребованной в данное время. Все более широкое распространение получают графические ускорители (GPU), способные показывать намного большую производительность, чем CPU. Но задача MST, как и многие задачи по обработке графов, плохо ложатся на архитектуру GPU. В данной статье будет рассмотрена реализация данного алгоритма на GPU. Также будет показано, как можно использовать CPU для построения гибридной реализации данного алгоритма на общей памяти одного узла (состоящего из GPU и нескольких CPU).
Вариант 3- Алгоритм MST (Algorithm based on Minimum Spanning Tree)


1.Описание алгоритма кластерного анализа (со ссылками на литературу)

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

Достоинства: выделяет кластеры произвольной формы, в т.ч. кластеры выпуклой и впуклой формы, выбирает из нескольких оптимальных решений самое оптимальное.
Описание алгоритма [13]
Шаг 1 Построение минимального остовного дерева:
Связный, неориентированный граф с весами на ребрах G(V, E), в котором V – множество вершин(контактов), а E – множество их возможных попарных соединений (ребер), для каждого ребра (u,v) однозначно определено некоторое вещественное число w(u,v) — его вес (длина или стоимость соединения).
Алгоритм Борувки:
1. Для каждой вершины графа находимо ребро с минимальным весом.
2. Добавляем найденные ребра к остовному дереву, при условии их безопасности.
3. Находим и добавляем безопасные ребра для несвязанных вершин к остовному дереву.
4. Общее время работы алгоритма: O(ELogV).
Алгоритм Крускала:
1. Обход ребер по возрастанию весов. При условии безопасности ребра добавляем его к основному дереву.
2. Общее время работы алгоритма: O(ELogE).
Алгоритм Прима:
1. Выбор корневой вершины.
2. Начиная с корня добавляем безопасные ребра к остовному дереву.
Общее время работы алгоритма: O(ELogV).
Шаг 2 Разделение на кластеры. Дуги с наибольшими весами разделяют кластеры. Принцип работы описанных выше групп методов в виде дендрограммы показан на рис. 1

.1 – Дендограмма работы агломеративных и дивизимных методов (анимация: объем 106 KB, размер 586x364, количество кадров 10, задержка между кадрами 50мс, задержка между последним и первым кадром 100 мс количество циклов повторения 5)

Алгоритм k-средних (k-means)
Наиболее распространен среди неиерархических методов алгоритм k-средних, также называемый быстрым кластерным анализом. Полное описание алгоритма можно найти в работе Хартигана и Вонга (Hartigan and Wong, 1978). В отличие от иерархических методов, которые не требуют предварительных предположений относительно числа кластеров, для возможности использования этого метода необходимо иметь гипотезу о наиболее вероятном количестве кластеров.
Алгоритм k-средних строит k кластеров, расположенных на возможно больших расстояниях друг от друга. Основной тип задач, которые решает алгоритм k-средних, – наличие предположений (гипотез) относительно числа кластеров, при этом они должны быть различны настолько, насколько это возможно. Выбор числа k может базироваться на результатах предшествующих исследований, теоретических соображениях или интуиции.
Общая идея алгоритма: заданное фиксированное число k кластеров наблюдения сопоставляются кластерам так, что средние в кластере (для всех переменных) максимально возможно отличаются друг от друга.
Описание алгоритма:
1. Первоначальное распределение объектов по кластерам.
Выбирается число k, и на первом шаге эти точки считаются "центрами" кластеров. Каждому кластеру соответствует один центр.
Выбор начальных центроидов может осуществляться следующим образом:
– выбор k-наблюдений для максимизации начального расстояния;
– случайный выбор k-наблюдений;
– выбор первых k-наблюдений.
В результате каждый объект назначен определенному кластеру.
2.Итеративный процесс.
Вычисляются центры кластеров, которыми затем и далее считаются покоординатные средние кластеров. Объекты опять перераспределяются.
Процесс вычисления центров и перераспределения объектов продолжается до тех пор, пока не выполнено одно из условий:
– кластерные центры стабилизировались, т.е. все наблюдения принадлежат кластеру, которому принадлежали до текущей итерации;
– число итераций равно максимальному числу итераций.
На рис. 2 приведен пример работы алгоритма k-средних для k, равного двум.


.2 – Пример работы алгоритма k-средних (k=2)
Выбор числа кластеров является сложным вопросом. Если нет предположений относительно этого числа, рекомендуют создать 2 кластера, затем 3, 4, 5 и т.д., сравнивая полученные результаты.
После получений результатов кластерного анализа методом k-средних следует проверить правильность кластеризации (т.е. оценить, насколько кластеры отличаются друг от друга). Для этого рассчитываются средние значения для каждого кластера. При хорошей кластеризации должны быть получены сильно отличающиеся средние для всех измерений или хотя бы большей их части.
Достоинства алгоритма k-средних:
– простота использования;
– быстрота использования;
– понятность и прозрачность алгоритма.
Недостатки алгоритма k-средних:
– алгоритм слишком чувствителен к выбросам, которые могут искажать среднее. Возможным решением этой проблемы является использование модификации алгоритма – алгоритм k-медианы;
– алгоритм может медленно работать на больших базах данных. Возможным решением данной проблемы является использование выборки данных.