Agrupamiento equilibrado

El agrupamiento equilibrado es un caso especial de agrupamiento en el que, en el sentido más estricto, los tamaños de los clústeres están restringidos a o , donde es el número de puntos y es el número de clústeres. ^[1] Un algoritmo típico es el de k-medias equilibradas , que minimiza el error cuadrático medio (MSE) . Otro tipo de agrupamiento equilibrado, llamado agrupamiento impulsado por el equilibrio, tiene una función de coste de dos objetivos que minimiza tanto el desequilibrio como el MSE. Las funciones de coste típicas son ratio cut ^[2] y Ncut. ^[3] El agrupamiento equilibrado se puede utilizar, por ejemplo, en escenarios en los que la carga tiene que entregarse a ubicaciones con coches. Entonces se prefiere que cada coche entregue en un número igual de ubicaciones. ${\displaystyle \lfloor {n \over k}\rfloor }$ ${\displaystyle \lceil {n \over k}\rceil }$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle k}$

Software

Existen implementaciones para k-medias balanceadas ^[4] y Ncut ^[5]

Referencias

1. MI Malinen y P. Fränti (agosto de 2014). "K-medias equilibradas para agrupamiento". Reconocimiento de patrones estructurales, sintácticos y estadísticos . Notas de clase en informática. Vol. 8621. págs. 32–41. doi :10.1007/978-3-662-44415-3_4. ISBN 978-3-662-44414-6.
2. L. Hagen y AB Kahng (1992). "Nuevos métodos espectrales para la partición y agrupamiento por corte de proporción". IEEE Transactions on Computer-Aided Design . 11 (9): 1074–1085. doi :10.1109/43.159993.
3. J. Shi y J. Malik (2000). "Cortes normalizados y segmentación de imágenes". IEEE Transactions on Pattern Analysis and Machine Intelligence . 22 (8): 888–905. doi :10.1109/34.868688.
4. MI Malinen y P. Fränti. "Implementación de k-Means balanceada". Universidad de Finlandia Oriental.
5. T. Cour, S. Yu y J. Shi. "Implementación de Ncut". Universidad de Pensilvania.

Levin, M. Sh. (2017). "Sobre el agrupamiento equilibrado (índices, modelos, ejemplos)". Revista de tecnología de comunicaciones y electrónica . 62 (12): 1506–1515. doi :10.1134/S1064226917120105. S2CID  255277095.