Building Classifier Ensembles Using Greedy Graph Edit Distance

Abstract

Classifier ensembles aim at more accurate classifications than single classifiers. In the present paper we introduce a general approach to building structural classifier ensembles, i.e. classifiers that make use of graphs as representation formalism. The proposed methodology is based on a recent graph edit distance approximation. The major observation that motivates the use of this particular approximation is that the resulting distances crucially depend on the order of the nodes of the underlying graphs. Our novel methodology randomly permutes the node order N times such that the procedure leads to N different distance approximations. Next, a distance based classifier is trained for each approximation and the results of the individual classifiers are combined in an appropriate way. In several experimental evaluations we make investigations on the classification accuracy of the resulting classifier ensemble and compare it with two single classifier systems.