Non-Linear Decision Trees - NDT

Abstract

Most decision tree algorithms focus on univariate, i.e. axis-parallel tests at each internal node of a tree. Oblique decision trees use multivariate linear tests at each non-leaf node. This paper reports a novel approach to the construction of non-linear decision trees. The crux of this method consists of the generation of new features and the augmentation of the primitive features with these new ones. The resulted non-linear decision trees are more accurate than their axis-parallel or oblique counterparts. Experiments on several artificial and real-world data sets demonstrate this property.