М.Ш. Левин

Балансная кластеризация с деревом над кластерами

В статье рассматривается балансная кластеризация с покрывающим деревом над кластерами. Такая задача может быть полезна в сетевых приложениях (проектирование, управление, маршрутизация). Рассматриваются элементы разного типа и соответствующие задачи балансной кластеризации с учетом состава элементов кластеров. Сформулированная оптимизационная задача основана на векторной целевой функции, включающей качество балансной кластеризации и качество покрывающего дерева. Предложены четыре базовых эвристических стратегии решения: балансирование-покрытие, покрытие-балансирование, прямое решение, построение много-уровневой структуры с сбалансированными кластерами. Приведено подробное описание стратегии покрытие-балансирование, включая четыре схемы решения и численный пример.

 

КЛЮЧЕВЫЕ СЛОВА: балансная кластеризация, комбинаторная оптимизация, покрывающее дерево, эвристики, сети