Multi-stage decision tree based on inter-class and inner-class margin of SVM

Motivated by overcoming the drawbacks of traditional decision tree and improving the efficiency of large margin learning based multi-stage decision tree when dealing with multi-class classification problems, this paper proposes a novel Multi-stage Decision Tree algorithm based on inter-class and inner class margin of SVM. This new algorithm is well designed for multi-class classification problem based on the maximum margin of SVM and the cohesion and coupling theory of clustering. Considering the multi-class classification problem as a clustering problem, this new algorithm attempts to convert the multi-class classification problem into a two-class classification problem such that the highest cohesion degree within classes while lowest coupling degree between classes, where the margin of SVM is considered as the measurement of the degree. Then for each two-class problem, this paper uses traditional C4.5 algorithm to generate each stage decision tree which splits a dataset into two subsets for the further induction. Recursively, the Multi-stage decision tree is obtained. Numerical simulations and theoretical analysis show this new multi-stage decision tree improves the performance of traditional decision tree and decreases the computational complexity a lot compare with large margin learning based multi-stage decision tree.