2015-04-01
666
В основе данного метода лежит использование построенного на исходном графе минимального остовного дерева, то есть такого подграфа который бы имел столько же компонент связности, сколько и исходный, но не содержал петель и сумма весов всех его ребер была бы минимальной (количество ребер для графа с n узлами равно n(n–1)/2). Алгоритмов построения такого дерева множество. Одним из простейших, но в то же время достаточно эффективных для графов, является алгоритм Краскала [20]:
Существует несколько алгоритмов, использующих остовное дерево для выделения кластеров. Например, в одном из них предлагается на каждом шаге удалять ребро с наименьшим весом (то есть, наибольшей длиной, расстоянием между точками), таким образом, разделяя данные на два под-графа-кластера, в другом предлагается удалять ребра, вес которых превышает некий заданный критерий.
Существует также более интеллектуальный метод, который выбирает ребро для удаления следующим образом. Длина (обратная величина сходства) ребра, необходимого для удаления, сравнивается с длинами ребер, инцидентными узлам соединяющими рассматриваемое ребро. Таким образом, можно считать, что ребро наиболее подходит для удаления, если его длина намного больше средней длины всех остальных ребер, инцидентных соответствующим узлам. Данный подход гибче предыдущего, поскольку позволяет получать кластеры, находящиеся на различных расстояниях друг от друга и, частично, решает одну из основных проблем данного метода – проблему отдельно стоящих точек (или, фактически, кластеров из очень малого количества точек), которые отрицательно влияют на качество разбиения.
