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

Материал из Алговики
Перейти к навигации Перейти к поиску
(Сброс статьи к шаблону)
(общее описание)
Строка 4: Строка 4:
  
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
 +
 +
Впервые идея использования минимального остовного дерева для кластеризации данных была преждожена C. T. Zah в 1971 году<ref name=zakh>C. T. Zahn, “graph-Theriotical methos for detecting and describing getalt clusters,” IEEE Trans. Computers, vol. 20, no. 1, pp. 68-86, 1971 </ref>. Этот метод широко используется исследователями при анализе изображений <ref>Y. Xu, V. Olman and E. C. Uberbacher, “A mentation using minimum spanning trees,” Image and Vission Computing, vol. 15, pp. 47-57,1997.</ref><ref>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.</ref>, а также при анализе биологических данных <ref>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.</ref>.
 +
 +
В работе алгоритма можно выделить следующие общие шаги:
 +
 +
# Построение минимального остовного дерева по заданному множеству. Для этого могут быть использованы например алгоритм Прима или алгоритм Крускала.
 +
# Разделение полученного дерева на несвязные множества поддеревьев в соответствии с некоторой стратегией. Можно выделить три популярные стратегии кластеризации:
 +
#* SEMST<ref>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</ref> (standard Euclidean minimum spanning tree clustering algorithm) - предполагается, что нам заранее известно число кластеров. В таком случае, если число кластеров равно k, то из полученного в первом пункте остовного дерева удаляются k-1 связей с наибольшим весом.
 +
#* CEMST<ref>Ye, B., Chao, K.M.: Spanning Trees and Optimization Problems. Chapman and
 +
Hall (2004)</ref>(The maximum cost minimum spanning tree) -
 +
#* ZEMST<ref name=zakh /> (The Zahn’s minimum spanning tree)
 +
==== Достоинства ====
 +
 +
Основным достоинством алгоритма является его способность выделять кластеры произвольной формы.
 +
 +
==== Недостатки ====
 +
 +
Недостатком является трудность определения порогового значения, при котором осуществляется разбиение данных на разные кластеры.
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===

Версия 20:44, 10 октября 2016

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

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

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

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

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

  1. Построение минимального остовного дерева по заданному множеству. Для этого могут быть использованы например алгоритм Прима или алгоритм Крускала.
  2. Разделение полученного дерева на несвязные множества поддеревьев в соответствии с некоторой стратегией. Можно выделить три популярные стратегии кластеризации:
    • SEMST[5] (standard Euclidean minimum spanning tree clustering algorithm) - предполагается, что нам заранее известно число кластеров. В таком случае, если число кластеров равно k, то из полученного в первом пункте остовного дерева удаляются k-1 связей с наибольшим весом.
    • CEMST[6](The maximum cost minimum spanning tree) -
    • ZEMST[1] (The Zahn’s minimum spanning tree)

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

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

1.1.2 Недостатки

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

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 Существующие реализации алгоритма

3 Литература

  1. ↑ 1,0 1,1 C. T. Zahn, “graph-Theriotical methos for detecting and describing getalt clusters,” IEEE Trans. Computers, vol. 20, no. 1, pp. 68-86, 1971
  2. ↑ Y. Xu, V. Olman and E. C. Uberbacher, “A mentation using minimum spanning trees,” Image and Vission Computing, vol. 15, pp. 47-57,1997.
  3. ↑ 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.
  4. ↑ 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.
  5. ↑ 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
  6. ↑ Ye, B., Chao, K.M.: Spanning Trees and Optimization Problems. Chapman and Hall (2004)
Источник — https://algowiki-project.org/w/ru/index.php?title=Участник:Astandrik/Алгоритм_кластеризации,_основанный_на_минимальном_остовном_дереве&oldid=5215