Abstract
The use of combinations of weak learners to learn a dataset has been shown to be better than the use of a single strong learner. In fact, the idea is so successful that boosting, an algorithm combining several weak learners for supervised learning, has been considered to be the best off the shelf classifier. However, some problems still exist, including determining the optimal number of weak learners and the over fitting of data. In an earlier work, we developed the RPHP algorithm which solves both these problems by using a combination of global search, weak learning and pattern distribution. In this chapter, we revise the global search component by replacing it with a cluster based combinatorial optimization. Patterns are clustered according to the output space of the problem, i.e., natural clusters are formed based on patterns belonging to each class. A combinatorial optimization problem is therefore created, which is solved using evolutionary algorithms. The evolutionary algorithms identify the “easy” and the “difficult” clusters in the system. The removal of the easy patterns then gives way to the focused learning of the more complicated patterns. The problem therefore becomes recursively simpler. Over fitting is overcome by using a set of validation patterns along with a pattern distributor. An algorithm is also proposed to use the pattern distributor to determine the optimal number of recursions and hence the optimal number of weak learners for the problem. Empirical studies show generally good performance when compared to other state of the art methods.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Dayhoff, DeLeo (2001) Artificial neural networks: Opening the black box. Cancer 91(8):1615–1635
Engelbrechet AP, Brits R (2002) Supervised training using an unsupervised approach to active learning. Neur Proc Lett 15(3):247–260
Fukunaga K (1990) Introduction to statistical pattern recognition. Academic Press, Boston
Guan SU, Li S (2002) Parallel growing and training of neural networks using output parallelism. IEEE Trans Neur Netw 13(3):542–550
Guan SU, Ramanathan K (2004) Recursive percentage based hybrid pattern training. In: Proc of IEEE conf on cybernetics and intelligent systems, pp. 455–460
Guan SU, Neo TN, Bao C (2004) Task decomposition using pattern distributor. J Intell Syst 13(2):123–150
Guan SU, Qi Y, Tan SK, Li S (2005) Output partitioning of neural networks. Neurocomputing 68:38–53
Guan SU, Ramanathan K, Iyer LR (2006) Multi learner based recursive training. In: Proc of IEEE conf on cybernetics and intelligent systems (Under review)
Guan SU, Zhu F (2004) Class decomposition for GA-based classifier agents—a pitt approach. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics 34(1):381–392
Hastie T, Tibshirani R, Friedman J (2001) The elements of statistical learning: data mining, inference, and prediction, Springer Series in Statistics Springer-Verlag
Haykins S (1999) Neural networks, a comprehensive foundation. Prentice Hall
Holland JH (1973) Genetic algorithms and the optimal allocation of trials. SIAM Journal on Computing 2(2): 88–105
MacQueen JB (1967) Some methods for classification and analysis of multivariate observations. In: Proceedings of 5-th Berkeley symposium on mathematical statistics and probability. Berkeley, University of California, vol. 1, pp. 281–297
Jain AK, Murty MN, Flynn PJ (1999), Data clustering: a review. ACM Comput Surv 31(3):264–323
Kohonen T (1997) Self organizing maps. Springer-Verlag, Berlin
Lasarzyck CWG Dittrich P, Banzhaf W (2004) Dynamic subset selection based on a fitness case topology. Evol Comput 12(4):223–242
Lehtokangas (1999) Modeling with constructive Backpropagation. Neur Netw 12:707
Lu BL, Ito K, Kita H, Nishikawa Y(1995) Parallel and modular multi-sieving neural network architecture for constructive learning. In: Proceedings of the 4th international conference on artificial neural networks, vol. 409, pp. 92–97.
Schapire RE (1999) A brief introduction to boosting. In: Proceedings of the sixteenth international joint conference on artificial intelligence
Wong MA, Lane T (1983) A kth nearest neighbor clustering procedure. J Royal Statist Soc (B), 45(3):362–368
Zhang BT, Cho DY (1998) Genetic programming with active data selection. Lecture notes in computer science 1585:146–153
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ramanathan, K., Guan, S.U. Clustering and combinatorial optimization in recursive supervised learning. J Comb Optim 13, 137–152 (2007). https://doi.org/10.1007/s10878-006-9017-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-006-9017-5