Clustering problems in a multiobjective framework

• Autores: Yunay Hernández, Ricardo Beausoleil Delgado
• Localización: Revista de Matemática: Teoría y Aplicaciones, ISSN 2215-3373, ISSN-e 2215-3373, Vol. 23, Nº. 2, 2016, págs. 445-461
• Idioma: inglés
• DOI: 10.15517/rmta.v23i2.25270
• Títulos paralelos:
  • Problemas de agrupacion en un ambiente multiobjetivo
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    En este trabajo proponemos un nuevo algoritmo usando un enfoque de búsqueda tabú para dar solución a problemas de agrupación (clusters) tomando en consideración dos objetivos. La tarea de agrupación se refiere a la agrupación de objetos, observaciones, o casos. Una agrupación es una colección de objetos similares entre sí y disímiles entre agrupaciones. Aplicaciones de agrupaciones tienen lugar en los diseños VLSI, redes de interacción proteina-proteina, minería de datos y muchas otras áreas. Los problemas de agrupación han sido ampliamente estudiados, pero su descripción se ha basado en la consideración de solamente un objetivo. En el contexto de optimización multiobjetivo nuestro objetivo es hallar una buena aproximación de la frontera Pareto y proveer un método para la toma de decisión. Como aplicación presentamos el problema de zonificación optimizando dos objetivos.

  • English

    We propose a new algorithm using tabu search to deal with biobjective clustering problems. A cluster is a collection of records that are similar to one other and dissimilar to records in other clusters. Clustering has applications in VLSI design, protein-protein interaction networks, data mining and many others areas. Clustering problems have been subject of numerous studies; however, most of the work has focused on single-objective problems. In the context of multiobjective optimization our aim is to find a good approximation to the Pareto front and provide a method to make decisions. As an application problem we present the zoning problem by allowing the optimization of two objectives.

• Referencias bibliográficas
  • Aeberhard, S.; Coomans, D.; de Vel, O. (1994) “Comparative analysis of statistical pattern recognition methods in high dimensional settings”,...
  • Beausoleil, R.P. (2001) “Multiple criteria scatter search”, in: Proceedings MIC’2001- 4th Metaheuristics International Conference, Porto,...
  • Bernábe, B.; Coello, C.A., Osorio, M. (2012) “A multiobjective approach for the heuristic optimization of compactness and homogeneity in the...
  • Brusco, M.J.; Cradit, J.D. (2005) “Bicriterion methods for partitioning dissimilarity matrices”, British Journal of Mathematical and Statistical...
  • Brusco, M.J.; Stahl, S. (2005) Branch-and-Bound Applications in Combinatorial Data Analysis. Springer, New York.
  • Caballero, R.; Laguna, M.; Martí, R.; Molina, J. (2006) “Multiobjective clustering with metaheuristic optimization technology”, Technical...
  • Boulder, CO, available in: http://www.uv.es/sestio/TechRep/tr02-06.pdf
  • Delattre, M.; Hansen, P, (1980) “Bicriterion cluster analysis", IEEE Transaction on Pattern Analysis and Machine Intelligence 2(4): 227–291.
  • Fisher, R.A. (1936) “The use of multiple measurements in taxonomic problems”, Annals of Eugenics 7(2): 179–188.
  • Glover, F. (1986) “Future paths for integer programming and links to artificial intelligence”, Computers and Ops. Res. 13(5): 533–549.
  • Handl, J.; Knowles, J. (2004) “Evolutionary multiobjective clustering”, in: X. Yao et al. (Eds.) Parallel Problem Solving from Nature (PPSN...
  • Hansen, P.; Jaumard, B. (1997) “Cluster analysis and mathematical programming”,Mathematical Programming 79(1-3): 191–215.
  • Jain, A.K.; Dubes, R.C. (1988) Algorithms for Clustering Data. Prentice- Hall, Upper Saddle River NJ.
  • Kurgan, L.A.; Cios, K.J.; Tadeusiewicz, R.; Ogiela, M.; Goodenday, L.S. (2001) “Knowledge discovery approach to automated cardiac SPECT diagnosis”,...
  • Mc Queen, J. (1967) “Some methods for classification and analysis of multivariate observations”, in: Proceedings of the Fifth Berkeley Symposiums...
  • Pacheco, J.; Valencia, O. (2003) “Design of hybrids for the minimum sum-of-squares clustering problem”, Computational Statistics and Data...
  • Rand, W.M. (1971) “Objective criteria for the evaluation of clustering methods”, J. Am. Stat. Assoc. 66(336): 846–850.
  • Reeves, C.R. (Ed.) (1993) Modern Heuristics Techniques for Combinatorial Problems. Wiley, New York.
  • Vendramin, L.; Campello, R.J.G.B.; Hruschka, E.R. (2010) “Relative clustering validity criteria: A comparative overview”, Statistical Analysis...