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
Journal:
Rect@: Revista Electrónica de Comunicaciones y Trabajos de ASEPUMA

ISSN: 1575-605X

Year of publication: 2010

Volume: 11

Issue: 1

Pages: 139-154

Type: Article

DIALNET GOOGLE SCHOLAR lock_openDialnet editor

More publications in: Rect@: Revista Electrónica de Comunicaciones y Trabajos de ASEPUMA

Abstract

This paper proposes a new method for constructing binary classification trees. The aim is to build simple trees, i.e. trees which are as uncomplicate as possible, thereby facilitating interpretation and favouring the balance between optimization and generalization in the test data sets. The proposed method is based on the metaheuristic strategy known as GRASP in conjunction with optimization tasks. Basically, this method modifies the criterion for selecting the attributes that determine the split in each node. In order to do so, a certain amount of randomisation is incorporated in a controlled way. We compare our method with the traditional method by means of a set of computational experiments. We conclude that the GRASP method (for small levels of randomness) significantly reduces tree complexity without decreasing classification accuracy.

Bibliographic References

  • 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.
Data source: Dialnet