Multivariate decision trees with monotonicity constraints

摘要

Classification with monotonicity constraint is a fundamental task in social analysis, management and decision making, where a monotonic function guarantees that objects with better feature values are not assigned with worse decisions. In practice, an object may be better than another on some attributes, while worse on others. These objects are considered to be incomparable. Incomparable object pairs limit the performance of a monotone classifier. In this work, we design an algorithm to combat this issue by constructing multivariate decision trees with monotonicity constraints (MMT). The classification model is naturally deemed as an oblique tree as it discovers partitions via oblique hyperplane in the input space. Our algorithm generates the projections of the objects which are used to split the data by improved splitting criteria with rank mutual information (RMI) or rank Gini impurity (RGI). Moreover, an improved algorithm with L1-regularization is also proposed to compute the optimal subsets of features in the process of constructing the trees, which leads to a more compact tree. Experimental results show that the proposed algorithm improves the classification performance in monotone classification tasks. The proposed algorithm is also effective even if data is contaminated by non-monotonic noisy samples.