Combined classifier based on feature space partitioning

Michał Woźniak ; Bartosz Krawczyk

International Journal of Applied Mathematics and Computer Science, Tome 22 (2012), p. 855-866 / Harvested from The Polish Digital Mathematics Library

Résumé

This paper presents a significant modification to the AdaSS (Adaptive Splitting and Selection) algorithm, which was developed several years ago. The method is based on the simultaneous partitioning of the feature space and an assignment of a compound classifier to each of the subsets. The original version of the algorithm uses a classifier committee and a majority voting rule to arrive at a decision. The proposed modification replaces the fairly simple fusion method with a combined classifier, which makes a decision based on a weighted combination of the discriminant functions of the individual classifiers selected for the committee. The weights mentioned above are dependent not only on the classifier identifier, but also on the class number. The proposed approach is based on the results of previous works, where it was proven that such a combined classifier method could achieve significantly better results than simple voting systems. The proposed modification was evaluated through computer experiments, carried out on diverse benchmark datasets. The results are very promising in that they show that, for most of the datasets, the proposed method outperforms similar techniques based on the clustering and selection approach.

Détail

Publié le : 2012-01-01
EUDML-ID : urn:eudml:doc:244582

Bibliographie

[000] Alpaydin, E. (1999). Combined 5 x 2 cv f test for comparing supervised classification learning algorithms, Neural Computation 11(8): 1885-1892.

[001] Alpaydin, E. (2010). Introduction to Machine Learning, 2nd Edn., The MIT Press, London. | Zbl 1191.68485

[002] Ashlock, D. (2006). Evolutionary Computation for Modeling and Optimization, 1st Edn., Springer, New York, NY. | Zbl 1102.68109

[003] Baram, Y. (1998). Partial classification: The benefit of deferred decision, IEEE Transactions on Pattern Analysis and Machine Intelligence 20(8): 769-776.

[004] Baruque, B., Porras, S. and Corchado, E. (2011). Hybrid classification ensemble using topology-preserving clustering, New Generation Computing 29(3): 329-344.

[005] Biggio, B., Fumera, G. and Roli, F. (2007). Bayesian analysis of linear combiners, Proceedings of the 7th International Conference on Multiple Classifier Systems, MCS'07, Prague, Czech Republic, pp. 292-301.

[006] Brown, G. and Kuncheva, L.I. (2010). 'Good' and 'bad' diversity in majority vote ensembles, 9th International Workshop on Multiple Classifier Systems, MCS 2010, Cairo, Egypt, pp. 124-133.

[007] Chmaj, G., Walkowiak, K., Tarnawski, M. and Kucharzak, M. (2012). Heuristic algorithms for optimization of task allocation and result distribution in peer-to-peer computing systems, International Journal of Applied Mathematics and Computer Science 22(3): 733-748, DOI: 10.2478/v10006-012-0055-0.

[008] Chow, C.K. (1965). Statistical independence and threshold functions, IEEE Transactions on Electronic Computers EC-14(1): 66-68. | Zbl 0129.10104

[009] Cordella, L., Foggia, P., Sansone, C., Tortorella, F. and Vento, M. (2000). A cascaded multiple expert system for verification, in J. Kittler and F. Roli (Eds.), Multiple Classifier Systems, Lecture Notes in Computer Science, Vol. 1857, Springer, Berlin/Heidelberg, pp. 330-339.

[010] Dietterich, T.G. and Bakiri, G. (1995). Solving multiclass learning problems via error-correcting output codes, Journal of Artificial Intelligence Research 2: 263-286. | Zbl 0900.68358

[011] Duda, R.O., Hart, P.E. and Stork, D.G. (2001). Pattern Classification, 2nd Edn., Wiley, New York, NY. | Zbl 0968.68140

[012] Duin, R. (2002). The combining classifier: To train or not to train?, 16th International Conference on Pattern Recognition, Quebec, Canada, Vol. 2, pp. 765-770.

[013] Frank, A. and Asuncion, A. (2010). UCI machine learning repository, http://archive.ics.uci.edu/ml.

[014] Giacinto, G., Roli, F. and Fumera, G. (2000). Design of effective multiple classifier systems by clustering of classifiers, 15th International Conference on Pattern Recognition, Barcelona, Spain, Vol. 2, pp. 160-163 . | Zbl 0996.68596

[015] Goebel, K. and Yan, W. (2004). Choosing classifiers for decision fusion, Proceedings of the 7th International Conference on Information Fusion, Stockholm, Sweden, pp. 563-568.

[016] Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning, 1st Edn., Addison-Wesley Longman Publishing Co., Inc., Boston, MA. | Zbl 0721.68056

[017] Hansen, L. and Salamon, P. (1990). Neural network ensembles, IEEE Transactions on Pattern Analysis and Machine Intelligence 12(10): 993-1001.

[018] Ho, T.K. (1998). The random subspace method for constructing decision forests, IEEE Transactions on Pattern Analysis and Machine Intelligence 20(8): 832-844.

[019] Jackowski, K. and Woźniak, M. (2009). Algorithm of designing compound recognition system on the basis of combining classifiers with simultaneous splitting feature space into competence areas, Pattern Analysis and Applications 12(4): 415-425.

[020] Jacobs, R.A. (1995). Methods for combining experts' probability assessments, Neural Computation 7(5): 867-888.

[021] Jacobs, R.A., Jordan, M.I., Nowlan, S.J. and Hinton, G.E. (1991). Adaptive mixtures of local experts, Neural Computation 3(1): 79-87.

[022] Jain, A., Duin, R. and Mao, J. (2000). Statistical pattern recognition: A review, IEEE Transactions on Pattern Analysis and Machine Intelligence 22(1): 4-37.

[023] Jain, A.K., Murty, M.N. and Flynn, P.J. (1999). Data clustering: A review, ACM Computing Surveys 31(3): 264-323.

[024] Kacprzak, T., Walkowiak, K. and Woźniak, M. (2012). Optimization of overlay distributed computing systems for multiple classifier system-Heuristic approach, Logic Journal of the IGPL 20(4): 677-688.

[025] Krawczyk, B. and Woźniak, M. (2011). Designing cost-sensitive ensemble genetic approach, in R. Choras (Ed.), Image Processing and Communications Challenges 3, Advances in Intelligent and Soft Computing, Vol. 102, Springer, Berlin/Heidelberg, pp. 227-234.

[026] Kuncheva, L. (2000). Clustering-and-selection model for classifier combination, 4th International Conference on Knowledge-Based Intelligent Engineering Systems and Allied Technologies, Brighton, UK, Vol. 1, pp. 185-188.

[027] Kuncheva, L., Bezdek, J.C. and Duin, R.P.W. (2001). Decision templates for multiple classifier fusion: An experimental comparison, Pattern Recognition 34(2): 299-314. | Zbl 0991.68064

[028] Kuncheva, L.I. (2004). Combining Pattern Classifiers: Methods and Algorithms, Wiley-Interscience, Hoboken, NJ. | Zbl 1066.68114

[029] Kuncheva, L., Whitaker, C., Shipp, C. and Duin, R. (2003). Limits on the majority vote accuracy in classifier fusion, Pattern Analysis and Applications 6(1): 22-31. | Zbl 1035.68101

[030] Kuratowski, K. and Mostowski, A. (1976). Set Theory: With An Introduction to Descriptive Set Theory, 2nd Edn., North-Holland Pub. Co., Amsterdam. | Zbl 0337.02034

[031] MacQueen, J.B. (1967). Some methods for classification and analysis of multivariate observations, in L.M.L. Cam and J. Neyman (Eds.), Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1, University of California Press, Berkeley, CA, pp. 281-297. | Zbl 0214.46201

[032] Marcialis, G.L. and Roli, F. (2003). Fusion of face recognition algorithms for video-based surveillance systems, in G.L. Foresti, C.S. Regazzoni and P.K. Varshney (Eds.), Multisensor Surveillance Systems: The Fusion Perspective, Dordrecht, The Netherlands, pp. 235-250.

[033] Matan, O. (1996). On voting ensembles of classifiers (extended abstract), Proceedings of the AAAI-96 Workshop on Integrating Multiple Learned Models, Portland, OR, USA, pp. 84-88.

[034] Partridge, D. and Krzanowski, W. (1997). Software diversity: Practical statistics for its measurement and exploitation, Information and Software Technology 39(10): 707-717.

[035] Polikar, R. (2006). Ensemble based systems in decision making, IEEE Circuits and Systems Magazine 6(3): 21-45.

[036] Rastrigin, L. and Erenstein, R.H. (1981). Method of Collective Recognition, Energoizdat, Moscow. | Zbl 0404.68091

[037] Ruta, D. and Gabrys, B. (2005). Classifier selection for majority voting, Information Fusion 6(1): 63-81. | Zbl 0980.68914

[038] Smetek, M. and Trawinski, B. (2011). Selection of heterogeneous fuzzy model ensembles using self-adaptive genetic algorithms, New Generation Computing 29(3): 309-327.

[039] Srinivas, M. and Patnaik, L.M. (1994). Genetic algorithms: A survey, Computer 27(6): 17-26.

[040] Team, R.D.C. (2008). R: A Language and Environment for Statistical Computing, R Foundation for Statistical Computing, Vienna.

[041] Ting, K., Wells, J., Tan, S., Teng, S. and Webb, G. (2011). Feature-subspace aggregating: Ensembles for stable and unstable learners, Machine Learning 82(3): 375-397.

[042] Troć, M. and Unold, O. (2010). Self-adaptation of parameters in a learning classifier system ensemble machine, International Journal of Applied Mathematics and Computer Science 20(1): 157-174, DOI: 10.2478/v10006-010-0012-8. | Zbl 1300.68047

[043] Tumer, K. and Ghosh, J. (1996). Analysis of decision boundaries in linearly combined neural classifiers, Pattern Recognition 29(2): 341-348.

[044] van Erp, M., Vuurpijl, L. and Schomaker, L. (2002). An overview and comparison of voting methods for pattern recognition, 8th International Workshop on Frontiers in Handwriting Recognition, Ontario, Canada, pp. 195-200.

[045] Walkowiak, K. (2010). Anycasting in connection-oriented computer networks: Models, algorithms and results, International Journal of Applied Mathematics and Computer Science 20(1): 207-220, DOI: 10.2478/v10006-010-0015-5. | Zbl 1300.68011

[046] Wilk, T. and Woźniak, M. (2011). Complexity and multithreaded implementation analysis of one class-classifiers fuzzy combiner, in E. Corchado, M. Kurzynski and M. Wozniak (Eds.), Hybrid Artificial Intelligent Systems, Lecture Notes in Computer Science, Vol. 6679, Springer, Berlin/Heidelberg, pp. 237-244.

[047] Wolpert, D.H. (2001). The supervised learning no-free-lunch theorems, 6th Online World Conference on Soft Computing in Industrial Applications, pp. 25-42.

[048] Woods, K., Kegelmeyer Jr., W.P. and Bowyer, K. (1997). Combination of multiple classifiers using local accuracy estimates, IEEE Transactions on Pattern Analysis and Machine Intelligence 19(4): 405-410.

[049] Woźniak, M. (2008). Experiments on linear combiners, in E. Pietka and J. Kawa (Eds.), Information Technologies in Biomedicine, Advances in Soft Computing, Vol. 47, Springer, Berlin/Heidelberg, pp. 445-452.

[050] Woźniak, M. and Jackowski, K. (2009). Some remarks on chosen methods of classifier fusion based on weighted voting, in E. Corchado, X. Wu, E. Oja, A. Herrero and B. Baruque (Eds.), Hybrid Artificial Intelligence Systems, Lecture Notes in Computer Science, Vol. 5572, Springer, Berlin/Heidelberg, pp. 541-548.

[051] Woźniak, M. and Zmyślony, M. (2010). Combining classifiers using trained fuser-Analytical and experimental results, Neural Network World 13(7): 925-934.

[052] Xu, L., Krzyzak, A. and Suen, C. (1992). Methods of combining multiple classifiers and their applications to handwriting recognition, IEEE Transactions on Systems, Man and Cybernetics 22(3): 418-435.