Сбалансированная кластеризация

Сбалансированная кластеризация — это особый случай кластеризации , где, в самом строгом смысле, размеры кластеров ограничены или , где — количество точек, а — количество кластеров. ^[1] Типичным алгоритмом является сбалансированный алгоритм k-средних , который минимизирует среднеквадратичную ошибку (MSE) . Другой тип сбалансированной кластеризации, называемый кластеризацией на основе баланса, имеет двухцелевую функцию стоимости, которая минимизирует как дисбаланс, так и MSE. Типичными функциями стоимости являются ratio cut ^[2] и Ncut. ^[3] Сбалансированную кластеризацию можно использовать, например, в сценариях, когда грузы должны быть доставлены в пункты назначения автомобилями. Тогда предпочтительно, чтобы каждый автомобиль доставлял грузы в равное количество пунктов. $\lfloor {n \over k}\rfloor$ $\lceil {n \over k}\rceil$ $n$ $k$ $n$ $k$

Программное обеспечение

Существуют реализации для сбалансированного k-средних ^[4] и Ncut ^[5]

Ссылки

^ MI Malinen и P. Fränti (август 2014). "Сбалансированное K-среднее для кластеризации". Структурное, синтаксическое и статистическое распознавание образов . Конспект лекций по информатике. Том 8621. С. 32– 41. doi :10.1007/978-3-662-44415-3_4. ISBN 978-3-662-44414-6.
^ Л. Хаген и А. Б. Канг (1992). «Новые спектральные методы для разделения и кластеризации с использованием коэффициентов разбиения». Труды IEEE по автоматизированному проектированию . 11 (9): 1074– 1085. doi :10.1109/43.159993.
^ J. Shi и J. Malik (2000). «Нормализованные разрезы и сегментация изображений». Труды IEEE по анализу образов и машинному интеллекту . 22 (8): 888– 905. doi :10.1109/34.868688.
^ MI Malinen и P. Fränti. «Сбалансированная реализация k-средних». Университет Восточной Финляндии.
^ T. Cour, S. Yu и J. Shi. «Реализация Ncut». Университет Пенсильвании.

Левин, М. Ш. (2017). «О сбалансированной кластеризации (индексы, модели, примеры)». Журнал коммуникационных технологий и электроники . 62 (12): 1506– 1515. doi :10.1134/S1064226917120105. S2CID 255277095.

[1] MI Malinen и P. Fränti (август 2014). "Сбалансированное K-среднее для кластеризации". Структурное, синтаксическое и статистическое распознавание образов . Конспект лекций по информатике. Том 8621. С. 32– 41. doi :10.1007/978-3-662-44415-3_4. ISBN 978-3-662-44414-6.

[2] Л. Хаген и А. Б. Канг (1992). «Новые спектральные методы для разделения и кластеризации с использованием коэффициентов разбиения». Труды IEEE по автоматизированному проектированию . 11 (9): 1074– 1085. doi :10.1109/43.159993.

[3] J. Shi и J. Malik (2000). «Нормализованные разрезы и сегментация изображений». Труды IEEE по анализу образов и машинному интеллекту . 22 (8): 888– 905. doi :10.1109/34.868688.

[4] MI Malinen и P. Fränti. «Сбалансированная реализация k-средних». Университет Восточной Финляндии.

[5] T. Cour, S. Yu и J. Shi. «Реализация Ncut». Университет Пенсильвании.