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

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

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

Существуют реализации сбалансированных k-средних. ^[4] и Нкут ^[5]

Ссылки

^ М.И. Малинен и П. Френти (август 2014 г.). «Сбалансированные K-средства для кластеризации». Структурное, синтаксическое и статистическое распознавание образов . Конспекты лекций по информатике. Том. 8621. стр. 32–41. дои : 10.1007/978-3-662-44415-3_4 . ISBN 978-3-662-44414-6 .
^ Л. Хаген и А.Б. Канг (1992). «Новые спектральные методы разделения и кластеризации с сокращением отношения». Транзакции IEEE в области автоматизированного проектирования . 11 (9): 1074–1085. дои : 10.1109/43.159993 .
^ Дж. Ши и Дж. Малик (2000). «Нормализованные разрезы и сегментация изображений» . Транзакции IEEE по анализу шаблонов и машинному интеллекту . 22 (8): 888–905. дои : 10.1109/34.868688 .
^ М.И. Малинен и П. Френти. «Сбалансированная реализация k-средних» . Университет Восточной Финляндии.
^ Т. Кур, С. Ю и Дж. Ши. «Реализация Ncut» . Пенсильванский университет.

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

[1] М.И. Малинен и П. Френти (август 2014 г.). «Сбалансированные K-средства для кластеризации». Структурное, синтаксическое и статистическое распознавание образов . Конспекты лекций по информатике. Том. 8621. стр. 32–41. дои : 10.1007/978-3-662-44415-3_4 . ISBN 978-3-662-44414-6 .

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

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

[4] М.И. Малинен и П. Френти. «Сбалансированная реализация k-средних» . Университет Восточной Финляндии.

[5] Т. Кур, С. Ю и Дж. Ши. «Реализация Ncut» . Пенсильванский университет.

[1]

[2]

[3]

[4]

[5]