Моделирование кластеризации многомерных объектов в Visual С++
7
Основные шаги алгоритма кластеризации.
Создание струк-
туры нелинейного списка.
Под нелинейным разветвленным списком
понимается список, элементами которого могут быть тоже списки.
Из входного потока объектов выборки формируются звенья горизон-
тального нелинейного двунаправленного списка элементов: в инфор-
мационные поля записываются многомерный вектор и его основные
параметры (в двумерном случае — точка и ее параметры) и номер
точки, заданный при вводе. Поле — номер кластера — является вы-
числяемым и определяется в процессе кластеризации.
Звено списка описано классом class Element. Класс описывает
многомерный вектор и его основные параметры, в двумерном слу-
чае — точку на плоскости и ее параметры: номер точки, заданный
при вводе, вычисляемый параметр — номер кластера, которому
назначается точка.
Формирование списков локальных сгущений.
На этом этапе
точки не назначаются кластерам, а формируются локальные сгуще-
ния, которые необходимо объединить в кластеры на следующем ша-
ге. Для каждого элемента звена горизонтального списка, т. е. для
каждой точки, создается список ближайших соседей в смысле неко-
торой метрики. Алгоритм формирования локального сгущения осно-
ван на применении сферы с центром в рассматриваемой точке и ра-
диусом, вычисляемым в процессе формирования матрицы близости
(в данном случае — расстояний). Радиус сферы модифицируется
адаптивным коэффициентом со значениями в интервале 1…3, мас-
штабирующим минимальное расстояние среди расстояний от теку-
щей точки до всех остальных. Этот параметр управляет процессом
кластеризации. Один из вариантов его выбора эвристически обосно-
вывается правилом трех сигм. В ближайшие точки текущего элемен-
та включаются те, которые попадают в определяемую алгоритмом
сферу. Эти элементы записываются в вертикальные списки для каж-
дого элемента горизонтального списка.
Для каждого списка локального сгущения определяется среднее
значение и сохраняется в соответствующем поле класса. По значени-
ям средних каждого списка локального сгущения вычисляется сред-
нее значение для всех списков ближайших. Если среднее списка
ближайших больше среднего всех ближайших, то список ближайших
удаляется, что позволяет удалить возможные связи между точками
соседних кластеров.
Кластеризация элементов.
В поле номер кластера для всех
элементов горизонтального и вертикальных списков записывается
номер кластера, в который элемент попадает в результате кластери-
зации. Алгоритм разнесения точек по кластерам можно реализовать
как рекурсивно, так и итеративно. Цель алгоритма — объединить це-
почки ближайших элементов в одну цепочку, соответствующую аг-
регированному кластеру.
