Марк Ш. Левин

О балансной кластеризации (индексы, модели, примеры)

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

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