Марк Ш. Левин

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

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

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