Uso del metaheurístico GRASP en la construcción de árboles de clasificación

  1. Pacheco Bonrostro, Joaquín A.
  2. Alfaro Cortés, Esteban
  3. Casado Yusta, Silvia
  4. Gámez Martínez, Matías
  5. García Rubio, Noelia
Revista:
Rect@: Revista Electrónica de Comunicaciones y Trabajos de ASEPUMA

ISSN: 1575-605X

Año de publicación: 2010

Volumen: 11

Número: 1

Páginas: 139-154

Tipo: Artículo

DIALNET GOOGLE SCHOLAR lock_openDialnet editor

Otras publicaciones en: Rect@: Revista Electrónica de Comunicaciones y Trabajos de ASEPUMA

Resumen

En este trabajo se propone un nuevo método para la construcción de árboles binarios de clasificación. El objetivo es la construcción de árboles sencillos, es decir, con la menor complejidad posible, lo cual hace que sean de fácil interpretación y propicia el equilibrio entre optimización y generalización en los conjuntos test. El método propuesto se basa en la estrategia metaheurística GRASP usada en la literatura en problemas de optimización. El método básicamente modifica la forma de elección del atributo que determina la partición en cada nodo. Para ello incorpora aleatoriedad de forma controlada. A través de una serie de experimentos computacionales se compara nuestro método GRASP con la forma tradicional de seleccionar atributos. Se puede concluir que nuestro método GRASP, con pequeños niveles de aleatoriedad, consigue árboles significativamente menos complejos que los obtenidos con la forma tradicional.

Referencias bibliográficas

  • M.S. Sanchez (1997). Redes neuronales en clasificación, Tesis Doctoral, Universidad de Valladolid.
  • L. Breiman, J.H. Friedman, R. Olshen and C.J. Stone, Classification and regression trees (Belmont Wadsworth International Group, 1984).
  • C.J. Huberty (1994). Applied Discriminant Analysis. Wiley Interscience
  • P. Komarek (2004). Logistic regression for data mining and high-dimensional classification. Phd Thesis, Carnegie Mellon University, Pittsburgh, Pennylvania, USA.
  • S.M. Weiss and C. Kulikoswki, Computer systems that learn: Classification and prediction methods from statistics, neural nets, machine learning and expert systems (Morgan Kauffmann Publisher, 1991).
  • R.O. Duda, P.E. Hart and D.G. Stork, Pattern classification ( 2nd Ed. John Wiley, 2000).
  • T.A. Feo and M.G.C. Resende, A Probabilistic heuristic for a computationally difficult Set Covering Problem. Oper Res Lett, 8(1989), 67-71.
  • P. Winker and M. Gilli (2004). Applications of optimization heuristics to estimation and modelling problems, Computational Statistics & Data Analysis, 47, 2, 211-223.
  • N. Belacel, H.B. Raval and A.P. Punnen (2007). Learning multicriteria fuzzy classification method PPOAFTN from data, Computers & Operations Research, 34, 7, 1885-1898.
  • P.C. Pendharkar (2006). A data mining-constraint satisfaction optimization problem for cost effective classification, Computers & Operations Research, 33, 11, 3124-3235.
  • F.C.García, M. García, B. Melián, J.A. Moreno y M. Moreno (2006). Solving feature selection problema by a parallel scatter search. European Journal of Operational Research, 169, 2, 477-489.
  • J. Pacheco, S. Casado, L. Núñez and O. Gómez (2006). Analysis of New Variable Selection Methods for Discriminant Analysis, Computational Statistics and Data Analysis, 51, 3, 1463-1478.
  • J.Y. Yang and S. Olafsson (2006). Optimization-based feature selection with adaptive instance sampling. Computers & Operations Research, 33, 11, 3088-3106.
  • J .Pacheco, S. Casado and L. Núñez (2009). A variable selection method based in Tabu Search for Logistic Regression Models, European Journal of Operational Research, 199, 1, 506-511.
  • N. Belacel, P. Hansen and N. Mladenovic (2003). Fuzzy J-Means: a new heuristic for fuzzy clustering, Pattern Recognition, 35, 2193-2200.
  • J. Pacheco and O. Valencia (2003). Design of hybrids for the minimum sum-of-squares clustering problem, Computational Statistics and Data Analysis, 43, 2, 235-248.
  • D.L. Woodruff and T. Reiners (2004). Experiments with, and on, algorithms for maximum likelihood clustering, Computational Statistics & Data Analysis, 47, 2, 237- 253.
  • J. Cadima, J.O. Cerdeira and M. Minhoto (2004). Computational aspects of algorithms for variable selection in the context of principal components, Computational Statistics & Data Análisis, 47, 2, 225-236.
  • C. Gatu and E.J. Kontoghiorghes (2003). Parallel algorithms for computing all possible subset regression models using the QR Descomposition, Parallel Computing, 29, 505- 521.
  • C. Gatu and E.J. Kontoghiorghes (2005). Efficient strategies for deriving the subset {VAR}models. Computational Management Science, 2, 4, 253-278.
  • M. Hofmann, C. Gatu and E.J. Kontoghiorghes (2007). Efficient algorithms for computing the best subset regression models for large-scale problems, Computational Statistics and Data Analysis, 52, 1, 16-29.
  • R. Baragona, F. Battaglia and D. Cucina (2004). Fitting piecewise linear threshold autoregressive models by means of genetic algorithms, Computational Statistics and Data Analysis, 47, 2, 277-295.
  • G. Kapetanios (2007). Variable selection in regression models using nonstandard optimisation of information criteria, Computational Statistics and Data Analysis, 52, 1, 4- 15.
  • J.R. Quinlan, Induction of decision trees. Machine Learning 1(1986), 81–106.
  • J.R. Quinlan, C4.5: Programs for Machine Learning (Morgan Kaufman, 1993).
  • U.M. Fayyad and K.B. Irani, Multi-interval discretization of continuous-valued attributes for classification learning, in: Proceedings of the 13th International Joint Conference on Artificial Intelligence (1993), 1022–1027.
  • U.M. Fayyad and K.B. Irani, On the handling of continuous-valued attributes in decision tree generation. Machine Learning 8 (1992), 87–102.
  • J.R. Quinlan, Improved use of continuous attributes in C4.5. Journal of Artificial Intelligence Research 4 (1996), 77–90.
  • X. Wu and D. Urpani, Induction by attribute elimination, IEEE Transactions on Knowledge and Data Engineering, 11- 5 (1999), 805–812.
  • E. Yen and I.W.M. Chu, Relaxing instance boundaries for the search of splitting points of numerical attributes in classification trees, Information Sciences, 177 (2007); 1276- 1289.
  • T.A. Feo and M.G.C. Resende, Greedy Randomized Adaptive Search Procedures. Journal of Global Optimization, 2 (1995), 1-27.
  • L.S. Pitsoulis and M.G.C. Resende, Greedy Randomized Adaptive Search Procedures in Handbook of Applied Optimization, P. M. Pardalos and M. G. C. Resende Eds. (Oxford University Press, 2002), 168-182.
  • P.M. Murphy and D.W. Aha (1994). UCI repository of Machine Learning (University of California, Department of Information and Computer Science, 1994) http://www.ics.uci.edu/~mlearn/MLRepository.html.
Fuente de los datos: Dialnet