Abstract
Classifier ensembles aim at a more accurate classification than single classifiers. Different approaches to building classifier ensembles have been proposed in the statistical pattern recognition literature. However, in structural pattern recognition, classifier ensembles have been rarely used. In this paper we introduce a general methodology for creating structural classifier ensembles. Our representation formalism is based on graphs and includes strings and trees as special cases. In the proposed approach we make use of graph embedding in real vector spaces by means of prototype selection. Since we use randomized prototype selection, it is possible to generate n different vector sets out of the same underlying graph set. Thus, one can train an individual base classifier for each vector set und combine the results of the classifiers in an appropriate way. We use extended support vector machines for classification and combine them by means of three different methods. In experiments on semi-artificial and real data we show that it is possible to outperform the classification accuracy obtained by single classifier systems in the original graph domain as well as in the embedding vector spaces.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Kuncheva, L.: Combining Pattern Classifiers: Methods and Algorithms. John Wiley, Chichester (2004)
Breiman, L.: Bagging predictors. Machine Learning 24, 123–140 (1996)
Ho, T.K.: The random subspace method for constructing decision forests. IEEE Trans. on Pattern Analysis ans Machine Intelligence 20(8), 832–844 (1998)
Freund, Y., Shapire, R.E.: A decision theoretic generalization of online learning and application to boosting. Journal of Computer and Systems Sciences 55, 119–139 (1997)
Conte, D., et al.: Thirty years of graph matching in pattern recognition. Int. Journal of Pattern Recognition and Artificial Intelligence 18(3), 265–298 (2004)
Bianchini, M., et al.: Recursive processing of cyclic graphs. IEEE Transactions on Neural Networks 17(1), 10–18 (2006)
Neuhaus, M., Bunke, H.: Edit distance based kernel functions for structural pattern classification. In: Pattern Recognition, pp. 1852–1863 (2006)
Gärtner, T., Lloyd, J., Flach, P.: Kernels and distances for structured data. Machine Learning 57(3), 205–232 (2004)
Marcialis, G.L., Roli, F., Serrau, A.: Fusion of statistical and structural fingerprint classifiers. In: Kittler, J., Nixon, M.S. (eds.) AVBPA 2003. LNCS, vol. 2688, pp. 310–317. Springer, Heidelberg (2003)
Neuhaus, M., Bunke, H.: Graph-based multiple classifier systems – a data level fusion approach. In: Roli, F., Vitulano, S. (eds.) ICIAP 2005. LNCS, vol. 3617, pp. 479–487. Springer, Heidelberg (2005)
Schenker, A., et al.: Building graph-based classifier ensembles by random node selection. In: Roli, F., Kittler, J., Windeatt, T. (eds.) MCS 2004. LNCS, vol. 3077, pp. 214–222. Springer, Heidelberg (2004)
Pekalska, E., Duin, R., Paclik, P.: Prototype selection for dissimilarity-based classifiers. Pattern Recognition 39(2), 189–208 (2006)
Spillmann, B., et al.: Transforming strings to vector spaces using prototype selection. In: Yeung, D.-Y., et al. (eds.) SSPR 2006 and SPR 2006. LNCS, vol. 4109, pp. 287–296. Springer, Heidelberg (2006)
Riesen, K., Neuhaus, M., Bunke, H.: Graph embedding in vector spaces by means of prototype selection. Submitted.
Wilson, R.C., Hancock, E.R., Luo, B.: Pattern vectors from algebraic graph theory. IEEE Trans. on Pattern Analysis ans Machine Intelligence 27(7), 1112–1124 (2005)
Robles-Kelly, A., Hancock, E.R.: A riemannian approach to graph embedding. Pattern Recognition 40, 1024–1056 (2007)
Sanfeliu, A., Fu, K.S.: A distance measure between attributed relational graphs for pattern recognition. IEEE Transactions on Systems, Man, and Cybernetics (Part B) 13(3), 353–363 (1983)
Bunke, H., Allermann, G.: Inexact graph matching for structural pattern recognition. Pattern Recognition Letters 1, 245–253 (1983)
Duin, R., Pekalska, E.: The Dissimilarity Representations for Pattern Recognition: Foundations and Applications. World Scientific, Singapore (2005)
Burges, C.: A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery 2(2), 121–167 (1998)
Shawe-Taylor, J., Cristianini, N.: Kernel Methods for Pattern Analysis. Cambridge University Press, Cambridge (2004)
Chang, C.C., Lin, C.J.: LIBSVM: A Library for Support Vector Machines (2001), Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm
Wu, C.F.J., Lin, C.J., Weng, R.C.: Probability estimates for multi-class classification by pairwise coupling. Journal of Machine Learning Research 5, 975–1005 (2004)
Kittler, J., et al.: On combining classifiers. IEEE Trans. on Pattern Analysis ans Machine Intelligence 20(3), 226–239 (1998)
Pudil, P., Novovicova, J., Kittler, J.: Floating search methods in feature-selection. PRL 15(11), 1119–1125 (1994)
Schölkopf, B., Smola, A.: Learning with Kernels. MIT Press, Cambridge (2002)
Le Saux, B., Bunke, H.: Feature selection for graph-based image classifiers. In: Marques, J.S., Pérez de la Blanca, N., Pina, P. (eds.) IbPRIA 2005. LNCS, vol. 3523, pp. 147–154. Springer, Heidelberg (2005)
Watson, C.I., Wilson, C.L.: NIST special database 4, fingerprint database. National Institute of Standards and Technology (March 1992)
Neuhaus, M., Bunke, H.: A graph matching based approach to fingerprint classification using directional variance. In: Kanade, T., Jain, A., Ratha, N.K. (eds.) AVBPA 2005. LNCS, vol. 3546, pp. 191–200. Springer, Heidelberg (2005)
Development Therapeutics Program DTP. Aids antiviral screen (2004), http://dtp.nci.nih.gov/docs/aids/aids_data.html
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Riesen, K., Bunke, H. (2007). Classifier Ensembles for Vector Space Embedding of Graphs. In: Haindl, M., Kittler, J., Roli, F. (eds) Multiple Classifier Systems. MCS 2007. Lecture Notes in Computer Science, vol 4472. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72523-7_23
Download citation
DOI: https://doi.org/10.1007/978-3-540-72523-7_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72481-0
Online ISBN: 978-3-540-72523-7
eBook Packages: Computer ScienceComputer Science (R0)