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

Участник:Astandrik/Алгоритм кластеризации, основанный на минимальном остовном дереве

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


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


Основные авторы описания: Стандрик Антон Сергеевич

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

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

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

Впервые идея использования минимального остовного дерева для кластеризации данных была преждожена C. T. Zah в 1971 году[2]. Этот метод широко используется исследователями при анализе изображений [3][4], а также при анализе биологических данных [5].

В общем описании работы алгоритма можно выделить следующие шаги:

  1. Построение минимального остовного дерева по заданному множеству. Этот шаг разбивается на два подшага:
    1. Определение метрики пространства, в котором осуществляется кластерный анализ. В качестве примеров метрик можно привести:
      • Метрика Евклида: [math]d_{ij} = \sqrt{\sum^n_{k=1}(x_{ik} - x_{jk})^2}[/math]
      • Метрика city-block (манхэттенская метрика): [math]d_{ij} = \sum^n_{k=1}|x_{ik} - x_{jk}| [/math]
      • Метрика Брея-Картиса: [math]d_{ij} = \sum^n_{k=1}\frac{|x_{ik} - x_{jk}|}{|x_{ik} + x_{jk}| }[/math]
    2. Выбор алгоритма построения минимального остовного дерева:
  2. Разделение полученного дерева на несвязное множество поддеревьев в соответствии с некоторой стратегией. Можно выделить три популярные стратегии кластеризации:
    • SEMST[6] (standard Euclidean minimum spanning tree clustering algorithm) - предполагается, что нам заранее известно число кластеров. В таком случае, если число кластеров равно [math]k[/math], то из полученного в первом пункте остовного дерева удаляются [math]k-1[/math] связей с наибольшим весом.
    • CEMST[7](The maximum cost minimum spanning tree) - Работает так же как и SEMST, однако вместо веса вершины используется её стоимость, которая вычисляется следующим образом: Пусть ребро [math]e = (x_{i}, x_{j})[/math], тогда [math]cost(e) = w(e) * degree(x_{i}) * degree(x_{j})[/math]. Далее, зная число кластеров [math]k[/math] и стоимости рёбер, удаляются [math]k-1[/math] рёбер с максимальной стоимостью.
    • ZEMST[2] (The Zahn’s minimum spanning tree) - от двух предыдущих эта стратегия отличается тем, что здесь число кластеров не известно заранее, а вычисляется в процессе кластеризации. Его суть в том, что удаляются те рёбра, веса которых значительно превосходят средний вес ребра в соседних поддеревьях.

1.1.1 Достоинства

Основным достоинством алгоритма является его способность выделять кластеры произвольной формы.

1.1.2 Недостатки

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

Кроме того, существуют наборы данных, на которых популярные алгоритмы (SEMST, CEMST, ZEMST) не дают правильного результата, и для которых требуется применение более сложных алгоритмов (например HEMST [8] с временем работы [math]O(n^2 * log(n))[/math])

Point-connected clusters
Кластеры, соединенные через точку.

Если взять в качестве примера набор данных, изображенных на рисунке выше, то видно, что простая стратегия "удалять самые длинные связи" здесь не сработает, и потребуется более сложный алгоритм для правильного нахождения кластеров.

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

Исходные данные: набор векторов размерности [math]n[/math] : [math](a_1, a_2, ..., a_n)[/math], где [math] a_j \in \mathbb {R} \quad \forall j \in [1,n] [/math].

Вычисляемые данные: Сгруппированные по кластерам данные.

1.2.1 Основные обозначения

  • [math]G = (V,E) [/math] - граф, заданный множеством вершин [math]V[/math] и множеством рёбер [math]E[/math]
  • [math]E[/math] - множество рёбер графа
  • [math]V[/math] - множество вершин графа
  • [math]MST(G)[/math] (minimum spanning tree) - минимальное остовное дерево графа [math][/math]. Остовное дерево — ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины. Минимальное остовное дерево в связанном взвешенном неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.

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

Процесс решения задачи кластеризации при помощи минимального остовного дерева может быть разделен на три независимых этапа:

  1. Приведение задачи наборе векторов данных к задаче о поиске минимального остовного дерева в графе (то есть нахождение расстояний между всеми парами данных векторов с использованием выбранной метрики, и запись этого расстояния как веса ребра, соединяющего эти вершины). Последовательная сложность: [math] O(n^2) [/math]
  2. Поиск минимального остовного дерева. Последовательная сложность: [math] O(E*log(E)) [/math]
  3. Разбиение остовного дерева на кластеры. Последовательная сложность зависит от реализации. (от [math] O(1) [/math] в случае SEMST до [math] O(n^2) [/math] в случае ZEMST).

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

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

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

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

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

1.9 Входные и выходные данные алгоритма

В качестве входных данных программе дается множество векторов [math](a_1, a_2, ..., a_n)[/math] размерности [math]n[/math]. Для удобства изучения свойств алгоритма и отображения результатов можно брать массив векторов размерности 2. В этом случае наглядность будет обеспечена естественной возможностью отобразить вектора в плоскости. Выходными данными программы будет множество, состоящее из сгруппированных по кластерам векторов из входных данных.

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

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

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

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

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

3 Литература

  1. Классификация и кластер. Под ред. Дж. Вэн Райзина. М.: Мир, 1980. 390 с.
  2. 2,0 2,1 C. T. Zahn, “graph-Theriotical methos for detecting and describing getalt clusters,” IEEE Trans. Computers, vol. 20, no. 1, pp. 68-86, 1971
  3. Y. Xu, V. Olman and E. C. Uberbacher, “A mentation using minimum spanning trees,” Image and Vission Computing, vol. 15, pp. 47-57,1997.
  4. Zhi Min Wang, Yeng Chai Soh, Qing Song, Kang Sim, “Adaptive spatial information-theoretic clustering for image segmentation,” Pattern Recognition, vol. 42, no. 9, pp. 2029-2044, 2009.
  5. Y. Xu, V. Olman and D. Xu, “Clustering gene expression data using a graph-Theriotic approach: An application of minimum spanning trees,” Bioinformatics, vol. 18, no. 4, pp. 536-545, 2002.
  6. Asano, M.K.T., Bhattacharya, B., Yao, F.: Clustering algorithms based on minimum and maximum spanning trees. In: In Proceedings of the fourth annual symposium on Computational Geometry. (1998) 252–257
  7. Ye, B., Chao, K.M.: Spanning Trees and Optimization Problems. Chapman and Hall (2004)
  8. Clustering with Minimum Spanning Trees Yan Zhou, Oleksandr Grygorash, Thomas F. Hain, Meador Inge Zach Jorgensen School of Computer and Information Sciences University of South Alabama, Mobile, AL 36688 USA Urban Insight Inc. 5657 Wilshire Blvd Ste 290, Los Angeles, CA 90036