Discrete support vector decision trees via tabu-search

An algorithm is proposed for generating decision trees in which multivariate splitting rules are based on the new concept of discrete support vector machines. By this term a discrete version of SVMs is denoted in which the error is properly expressed as the count of misclassified instances, in place of a proxy of the misclassification distance considered by traditional SVMs. The resulting mixed integer programming problem formulated at each node of the decision tree is then efficiently solved by a tabu search heuristic. Computational tests performed on both well-known benchmark and large marketing datasets indicate that the proposed algorithm consistently outperforms other classification approaches in terms of accuracy, and is therefore capable of good generalization on validation sets.