Keywords
clustering
tabu search
multiobjective optimization
Análisis de datos combinatorio
cluster
búsqueda tabú
optimización multiobjetivo
How to Cite
Abstract
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.
References
Aeberhard, S.; Coomans, D.; de Vel, O. (1994) “Comparative analysis of statistical pattern recognition methods in high dimensional settings”, Pattern Recognition 27(8): 1065–1077.
Beausoleil, R.P. (2001) “Multiple criteria scatter search”, in: Proceedings MIC’2001- 4th Metaheuristics International Conference, Porto, Portugal: 539–543.
Bernábe, B.; Coello, C.A., Osorio, M. (2012) “A multiobjective approach for the heuristic optimization of compactness and homogeneity in the optimal zoning”, Journal of Applied Research and Technology 10(3): 447–457.
Brusco, M.J.; Cradit, J.D. (2005) “Bicriterion methods for partitioning dissimilarity matrices”, British Journal of Mathematical and Statistical Psychology 58(2): 319–332.
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 Report 02-06, Leeds School of Business in the University of Colorado at 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 VIII), Lecture Notes on Computer Science 3242, Springer, Heidelberg: 1081–1091.
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”, Artificial Intelligence in Medicine 23(2): 149–169.
Mc Queen, J. (1967) “Some methods for classification and analysis of multivariate observations”, in: Proceedings of the Fifth Berkeley Symposiums on Mathematical Statistics and Probability, Vol. 1: 281–297.
Pacheco, J.; Valencia, O. (2003) “Design of hybrids for the minimum sum-of-squares clustering problem”, Computational Statistics and Data Analysis 43(2): 235–248.
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 and Data Mining 3(4): 209–235.
Comments
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Copyright (c) 2016 Revista de Matemática: Teoría y Aplicaciones