З.Н. Русакова, А.В. Орел
2
Задачи кластерного анализа решаются на основе таких подходов,
как вероятностный, иерархический, теория графов, нечеткие алго-
ритмы [4–7]. В современном подходе принятие решение осуществля-
ется группировкой комплекса алгоритмов.
Гибридный алгоритм кластеризации.
В работе проводятся ис-
следование и разработка структурной модификации алгоритма кла-
стеризации на основе объединения двух подходов: метода поиска ло-
кальных сгущений и методов определения связных компонент графа,
построения и анализа минимального покрывающего дерева, объеди-
няющего точки данных. Предложенный алгоритм гибридной класте-
ризации использует идею итеративного метода поиска сгущений и
методов поиска покрытий в графах [5–7].
Разработанный алгоритм обеспечивает кластеризацию таких
классов, как класс типа слабого сгущения, класс типа изолированно-
го облака и обычных классов типа сильного сгущения. В случае пе-
ресекающихся классов алгоритм кластеризации выполняется в пред-
положении слабого их пересечения. Для случая пересекающихся кла-
стеров, например, данные выборки пересекаются в крестообразной
форме, а результат является начальным приближением для разбиения
другими методами.
Двухэтапная процедура кластеризации.
В предлагаемом алго-
ритме реализуется двухэтапная процедура кластеризации, не требу-
ющая априорной информации о центрах предполагаемых кластеров и
форме выборки данных. На первом этапе реализуется модифициро-
ванный метод поиска локальных сгущений: для каждого элемента
выборки определяется локальное сгущение, центром которого явля-
ется сам элемент. Локальное сгущение определяется как список бли-
жайших соседей. На втором этапе на основе алгоритмов построения
связных компонент графа осуществляется кластеризация путем слия-
ния отдельных сгущений в кластеры.
Суть итеративного метода поиска сгущений заключается в при-
менении гиперсферы заданного радиуса и заданного центра для по-
иска ближайших соседей, формирующих локальные сгущения объек-
тов, т. е. совокупности точек, попавших внутрь данной сферы. Для
этого требуется вычисление матрицы расстояний между объектами и
выбор первоначального центра сферы. Алгоритм выбора радиуса
сферы играет определяющую роль при решении задачи. Адаптация
алгоритма к форме кластера реализуется путем настройки параметра,
учитывающего специфику типов кластеров.
На первом этапе алгоритма формируются списки ближайших сосе-
дей, в качестве критерия объединения которых выбирается минималь-
ное расстояние от фиксированной точки до остальных. Процедура
определения локального сгущения состоит в следующем: последова-
