K-means
Простой и широко используемый неиерархический алгоритм кластеризации.
Основная идея алгоритма: разбиение всего множества объектов на k кластеров с последующим пересчетом их центров и перераспределением объеков по кластерам. Значение k — количество кластеров задется заранее и является основным из входных данных алгоритма.
Достоинства: простота использования; быстрота использования; понятность и прозрачность алгоритма.
Недостатки: качество результата сильно зависит от выбора начального разбиения; медленная работа на больших объемах исходных данных; необходимо задавать количество кластеров; алгоритм чувствителен к выбросам.
Алгоритм:
- Выбирается k объектов (по числу кластеров) и на первом шаге они считаются в качестве центров.
- В соответствии с выбранной метрикой каждый объект исходного множества присваивается определенному кластеру, исходя из близости его к центру кластера.
- Пересчитываются центры кластеров в соответствии с влиянием новых объектов, попавших в кластер.
- Далее Пункт 2.
- Алгоритм заканчивается когда кластерные центры стабилизировались или число итераций стало равно максимальному числу итераций.
Fuzzy c-means
Алгоритм нечеткой кластеризации.
Основная идея алгоритма: кластеры представляют собой нечеткие множества, т.е. каждый объект принадлежит всем кластерам с разной степенью принадлежности.
Достоинства: нечеткость при определении объекта в кластер позволяет определять объекты, которые находятся на границе, в кластеры.
Недостатки: вычислительная сложность, задание количества кластеров, возникает неопределенность с объектами, которые удалены от центров всех кластеров.
Алгоритм:
- Инициализация. Выбираются следующие параметры: необходимое количество кластеров N, 2 < N < К; мера расстояний; экспоненциальный вес m, определяющий нечеткость; количество кластеров k.
- Генерация начальной матрицы принадлежности объектов с учетом заданных начальных центров кластеров.
- Расчет центров кластеров.
- Расчет расстояния между объектами и центрами кластеров
- Пересчет матрицы разбиения
- Далее Пункт 3.
- Алгоритм заканчивается когда текущая матрица отличается от предыдущей менее чем на заданное значение.
MST (Minimum Spanning Trees)
Иерархический дивизимный алгоритм, основанный на теории графов.
Основная идея алгоритма: строится минимальное остовное дерево на основе множества всех исходных объектов, далее дерево делится на кластеры.
Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном, взвешенном, неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.
Достоинства: алгоритм выделяет кластеры произвольной формы.
Алгоритм:
- Построение минимального остовного дерева. (Алгоритмы Борувки, Крускала, Прима).
- Разделение на кластеры. Дуги с наибольшими весами разделяют кластеры.
Алгоритм Борувки:
1: Для каждой вершины графа находим ребро с минимальным весом.
2: Добавляем найденные ребра к остовному дереву, при условии их безопасности.
3: Находим и добавляем безопасные ребра для несвязанных вершин к остовному дереву.
Общее время работы алгоритма: O(ELogV).
Алгоритм Крускала: Обход ребер по возрастанию весов. При условии безопасности ребра добавляем его к остновному дереву.
Общее время работы алгоритма: O(ELogE).
Алгоритм Прима:
1: Выбор корневой вершины.
2: Начиная с корня добавляем безопасные ребра к остовному дереву.
Общее время работы алгоритма: O(ELogV).