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

2.Листинг программы кластерного анализа.
Обширный класс алгоритмов кластеризации основан на представлении выборки в виде графа. Вершинам графа соответствуют объекты выборки, а рёбрам — попарные расстояния между объектами.
Достоинством графовых алгоритмов кластеризации является наглядность, относительная простота реализации и возможность вносить различные усовершенствования, опираясь на простые геометрические соображения.

Алгоритм минимального покрывающего дерева (MST) строит граф из N-1 рёбер так, чтобы они соединяли все N точек и обладали минимальной суммарной длиной. Такой граф называется кратчайшим незамкнутым путём, минимальным покрывающим деревом или каркасом графа.

Описание работы алгоритма:

• 
  Найти пару точек с наименьшим расстоянием (весом ребра) и соединить их ребром;
  

• 
  пока в выборке остаются изолированные точки:
  

• 
  найти изолированную точку, ближайшую к некоторой неизолированной;
  

• 
  соединить эти две точки ребром;
  

• 
  удалить K-1 самых длинных рѐбер;
  

На последнем шаге алгоритм удаляет из полученного графа K-1 самых длинных рёбер, что приводит к распаду графа на отдельные связанные компоненты, которые и будут искомыми кластерами.

Общеизвестны два недостатка этого алгоритма:

• 
  ограниченная применимость. Алгоритм наиболее подходит для выделения кластеров типа сгущений или лент. Наличие разреженного фона или «узких перемычек» между кластерами приводит к неадекватным результатам;
  

• 
  высокая трудоёмкость — для построения кратчайшего незамкнутого пути требуется O(N^3) операций.
  

Для работы с графами будет использоваться NetworkX — библиотека для создания и манипуляции графами. Кроме этого, она предоставляет готовую реализацию алгоритма нахождения минимального остовного дерева и удобное API для визуализации результатов.

Для начала необходимо получить исходные данные и расстояния между всеми элементами набора.

from scipy.spatial.distance import pdist
names, data = get_data()
dist = pdist(data, 'euclidean')
Функции get_data() и pdist() были описаны в первой заметке, поэтому не будем на них останавливаться.

Следом попробуем построить граф, представляющий наш исходный набор данных. Каждая вершина этого графа будет обозначать отдельный объект исходной выборки и будет связана со всеми остальными вершинами посредством взвешенных рёбер. Вес каждого ребра будет равен расстоянию близости между объектами.