1
УДК 519.876.5
Моделирование кластеризации
многомерных объектов в Visual C++
©
З.Н. Русакова, А.В. Орел
МГТУ им. Н.Э. Баумана, Москва, 105005, Россия
Представлен гибридный алгоритм кластеризации, не требующей априорной ин-
формации ни о числе кластеров, ни о форме выборки. Алгоритм основан на объ-
единении итеративного метода поиска локальных сгущений и методов определе-
ния связных компонент графа. Описан программный модуль моделирования задач
кластерного анализа, использующий для реализации нелинейные динамические
структуры.
Ключевые слова
: кластеризация, моделирование, программа, алгоритм, графы,
метрика, динамические нелинейные структуры.
Введение.
Одна из актуальных задач интеллектуального анализа
данных — кластерный анализ, используемый в различных областях:
в информационных системах при решении задач распознавания, клас-
сификации закономерностей, обработке изображений [1–4].
Под методами кластеризации понимается множество вычисли-
тельных процедур, решающих задачу классификации объектов на
однородные группы при отсутствии априорной информации о харак-
тере распределения [5, 6].
Постановка задачи
. Выборка многомерных перемешанных век-
торов наблюдений представляется в виде прямоугольной таблицы,
где строка — вектор измерения признаков объекта. Задача кластери-
зации состоит в разбиении выборки на кластеры (на подмножества)
так, чтобы обеспечить экстремум некоторого критерия функционала
качества — максимально правильное количество классифицирован-
ных объектов [3, 4, 6].
К наиболее используемым критериям относятся сумма квадратов
расстояний до центров кластеров, cумма внутрикластерных расстоя-
ний между объектами, сумма попарных внутриклассовых расстояний
между элементами кластеров. Критерием управления процессом кла-
стеризации является выбор меры сходства между объектами, называ-
емой также метрикой, или функцией расстояний. Выбор метрики
определяет результат кластеризации и, в свою очередь, определяется
формой выборки и типами признаков объекта [4, 6].
На практике применяют следующие метрики: евклидово расстоя-
ния; манхэттенское расстояние (расстояние городских кварталов);
расстояние Чебышева, расстояние Махаланобиса, вычисляющее рас-
стояние между векторами с помощью матрицы ковариаций.
