Bipartición balanceada en grupos homogéneos con correspondencia posicional
Palabras clave:
anticlustering, particionamiento balanceado, emparejamiento posicional, KD-Tree, búsqueda local, optimización combinatoriaResumen
En numerosas aplicaciones donde se requieren comparaciones justas (por ejemplo, control vs. tratamiento o asignación equitativa de recursos), no basta con formar grupos “internamente compactos”: se necesita particionar un conjunto de datos en dos subconjuntos balanceados que sean lo más similares posible entre sí y, además, con correspondencia explícita uno a uno entre elementos. Este trabajo estudia el caso de dos grupos (c = 2) como problema de optimización combinatoria, minimizando una función de costo basada en la suma de distancias cuadráticas entre pares emparejados en posiciones equivalentes (matching posicional). Como contribución principal, se propone una heurística híbrida que construye una solución inicial mediante vecinos cercanos apoyados en indexación espacial (KD-Tree) y la refina con búsqueda local por intercambios (swaps) aceptados por descenso puro, explotando la naturaleza aditiva del costo para evaluar mejoras de forma eficiente. La evaluación experimental sobre datasets sintéticos y reales muestra que el método obtiene soluciones de alta calidad con buen desempeño temporal y estabilidad entre ejecuciones. Finalmente, se discuten líneas futuras para extender el enfoque al caso general c > 2 y estudiar estrategias de escalabilidad (p. ej., paralelización y estructuras ANN), manteniendo la correspondencia posicional como restricción central.
Descargas
Referencias
Baumann, P., Goldschmidt, O., Hochbaum, D.S., Yang, J.: A fast and effective method for Euclidean anticlustering: The Assignment-Based-Anticlustering algorithm (2026). https://doi.org/10.48550/arXiv.2601.06351
Bentley, J.L.: Multidimensional binary search trees used for associative searching. Communications of the ACM 18(9), 509–517 (1975). https://doi.org/10.1145/361002.361007
Brusco, M.J., Cradit, J.D., Steinley, D.: Combining diversity and dispersion criteria for anticlustering: A bicriterion approach. British Journal of Mathematical and Statistical Psychology 73(3), 375–396 (2020). https://doi.org/10.1111/bmsp.12186
Feo, T.A., Goldschmidt, O., Khellaf, M.: One-half approximation algorithms for the k-partition problem. Operations Research 40(S1), S170–S173 (1992). https://doi.org/10.1287/opre.40.1.S170
Gallego, M., Laguna, M., Martí, R., Duarte, A.: Tabu search with strategic oscillation for the maximally diverse grouping problem. Journal of the Operational Research Society 64(5), 724–734 (2013). https://doi.org/10.1057/jors.2012.66
Lai, X., Hao, J.K.: Iterated maxima search for the maximally diverse grouping problem. European Journal of Operational Research 254(3), 780–800 (2016). https://doi.org/10.1016/j.ejor.2016.04.011
Papenberg, M.: K-plus anticlustering: An improved k-means criterion for maximizing between-group similarity. British Journal of Mathematical and Statistical Psychology 77(1), 80–102 (2024). https://doi.org/10.1111/bmsp.12315
Papenberg, M., Klau, G.W.: Using anticlustering to partition data sets into equivalent parts. Psychological Methods 26(2), 161–174 (2021). https://doi.org/10.1037/met0000301
Rosenbaum, P.R., Rubin, D.B.: The central role of the propensity score in observational studies for causal effects. Biometrika 70(1), 41–55 (1983). https://doi.org/10.1093/biomet/70.1.41
Ruiz-Olazar, M., Ihara, D., Barán, B.: Data partitioning into homogeneous groups using a genetic algorithm. In: 2025 IEEE CHILEAN Conference on Electrical, Electronics Engineering and Information and Communication Technologies (CHILECON). IEEE (2025)
Schulz, A.: The balanced maximally diverse grouping problem with block constraints. European Journal of Operational Research 294(1), 42–53 (2021). https://doi.org/10.1016/j.ejor.2021.01.029
Späth, H.: Anticlustering: Maximizing the variance criterion. Control and Cybernetics 15(2), 213–218 (1986)
Stuart, E.A.: Matching methods for causal inference: A review and a look forward. Statistical Science 25(1), 1–21 (2010). https://doi.org/10.1214/09-STS313
Weitz, R.R., Lakshminarayanan, S.: An empirical comparison of heuristic and graph theoretic methods for creating maximally diverse groups. Omega 25(4), 473–482 (1997). https://doi.org/10.1016/S0305-0483(97)00007-5
Yang, X., Cai, Z., Jin, T., Tang, Z., Gao, S.: A three-phase search approach with dynamic population size for solving the maximally diverse grouping problem. European Journal of Operational Research 302(3), 925–953 (2022). https://doi.org/10.1016/j.ejor.2022.02.003
Descargas
Publicado
Número
Sección
Licencia
Derechos de autor 2026 Margarita Ruiz-Olazar, Diego Ihara, Benjamín Barán, Miguel Méndez-Garabetti
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
Acorde a estos términos, el material se puede compartir (copiar y redistribuir en cualquier medio o formato) y adaptar (remezclar, transformar y crear a partir del material otra obra), siempre que a) se cite la autoría y la fuente original de su publicación (revista y URL de la obra), b) no se use para fines comerciales y c) se mantengan los mismos términos de la licencia.
