bsnsing: A Decision Tree Induction Method Based on Recursive Optimal Boolean Rule Composition

作     者：Liu, Yanchao 

作者机构：Wayne State Univ Dept Ind & Syst Engn Detroit MI 48202 USA 

出 版 物：《INFORMS JOURNAL ON COMPUTING》 (INFORMS J. Comput.)

年 卷 期：2022年第34卷第6期

页      面：2908-2929页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Science Foundation Division of Civil  Mechanical and Manufacturing Innovation 

主　　题：classification trees mixed-integer programming statistical computing R 

摘      要：This paper proposes a new mixed-integer programming (MIP) formulation to optimize split rule selection in the decision tree induction process and develops an efficient search algorithm that is able to solve practical instances of the MIP model faster than commercial solvers. The formulation is novel for it directly maximizes the Gini reduction, an effective split selection criterion that has never been modeled in a mathematical program for its nonconvexity. The proposed approach differs from other optimal classification tree models in that it does not attempt to optimize the whole tree;therefore, the flexibility of the recursive partitioning scheme is retained, and the optimization model is more amenable. The approach is implemented in an open-source R package named bsnsing. Benchmarking experiments on 75 open data sets suggest that bsnsing trees are the most capable of discriminating new cases compared with trees trained by other decision tree codes including the rpart, C50, party, and tree packages in R. Compared with other optimal decision tree packages, including DL8.5, OSDT, GOSDT, and indirectly more, bsnsing stands out in its training speed, ease of use, and broader applicability without losing in prediction accuracy.