Моделирование кластеризации многомерных объектов в Visual С++
3
тельно перебирается выборка объектов, которые рассматриваются как
точки в многомерном пространстве. Важный частный случай — точка
на плоскости, которую можно рассматривать или как проекцию много-
мерного вектора, или как результат редукции. Для каждой точки созда-
ется список ближайших точек в смысле некоторой метрики. C этой
целью для каждой рассматриваемой точки (текущая точка) вычисляют-
ся расстояния в евклидовой метрике между ней и всеми остальными и
расчитывается минимальное расстояние. Это расстояние определяет
радиус сферы для поиска локального сгущения.
Далее применяется модифицированный метод поиска сгущений
для ближайших соседей с адаптивным радиусом сферы: радиус мас-
штабируется коэффициентом
k
, который выбирается из соображения,
что разброс значений лежит в интервале 3σ, где σ — среднеквадрати-
ческое отклонение, а для минимума это условие выполняется строже.
Из анализа процесса кластеризации в качестве начального использу-
ется эвристическое значение
k
= 1,5. Оно оказывается допустимым с
учетом таких факторов, как скорость и качество кластеризации. Для
адаптации алгоритма к форме выборки значение
k
модифицируется и
принятие решения осуществляется на основе комплекса алгоритмов с
разными значениями
k
, определяющего радиус сферы поиска локаль-
ного сгущения. В ближайшие соседи включаются все точки, попада-
ющие в рассматриваемую сферу.
На втором этапе кластеризации объединяются полученные цепочки.
Принцип объединения вытекает из инцидентности вершин и дерева ми-
нимального покрытия в представлении графов. Если элемент входит в
список ближайших родительского элемента, к этому списку подключа-
ется список ближайших дочернего элемента (его самого), что обеспечи-
вает разделение на классы для многих видов кластеров.
Нелинейные динамические структуры гибридного алгорит-
ма.
Исходные данные представляются в виде прямоугольной табли-
цы, где строка — вектор измерения признаков, описывающих объек-
ты. Объекты во входной выборке перемешаны.
Для моделирования кластеризации разработана нелинейная ди-
намическая структура, описываемая двунаправленным динамическим
списком [8–10], информационным полем которого является другой
список. Эту структуру можно представить как горизонтальный дву-
направленный динамический список, к каждому звену которого под-
вешен вертикальный список. Горизонтальный список включает эле-
менты всей выборки. В вертикальный список для каждой точки, за-
писанной в звене горизонтального списка, включаются ближайшие
соседи, определяющие локальное сгущение. Информационные поля
звеньев содержат номера точек, заданных при вводе, и вектор их ко-
ординат. Описанная структура представлена на рис. 1.
