优化│最优分类树的三种MILP模型及其代码实现
决策树（decision tree）作为机器学习领域经典的分类与回归方法，易于实现，可解释性极强，在诸多领域都有着广泛的应用。而对于决策树的构造，学者们也作出了充分的研究，其中ID3、 C4.5和CART都是广为人知的算法。但是，实际上寻找最佳的决策树是一个NP完全问题。因此，大量的研究只能采用启发式策略去寻找局部最优解。与这些启发式算法不同，本文探讨了三种基于混合整数线性规划（MILP）的最优分类树模型，旨在实现决策树在分类问题上的最优解，并对此进行了一些的探讨和比较。
关于决策树模型
决策树模型是机器学习领域经典的分类与回归方法，是一种有监管学习（Supervised Learning）。它通过树的结构，利用树的分支来表示对样本特征的判断规则——从根节点开始，在每个非叶节点对单个特征进行阈值的if-else判断，然后转入下一个子节点，并最终由叶节点代表一种预测结果。主要的决策树算法包括ID3，C4.5， CART等。
决策树于1966年由E.B.Hunt等人首次提出。而1979年，J. R. Quinlan提出了著名的ID3算法，以信息论为基础，利用信息增益来选择特征。ID3作为最早提出的决策树算法，使决策树模型不再停留于理论，也从此引发了机器学习领域对决策树相关研究的热潮。1993年，J. R. Quinlan改进了自己之前的ID3算法，提出了以信息增益率替代信息增益构造决策树的C4.5算法。此外，后来的研究者们又以决策树为基础，发展了众多优秀的集成学习方法，如随机森林、AdaBoost、GBDT、XGBoost、LightGBM，这些算法在广泛的领域大放异彩，最为出名的XGBoost，常常能在Kaggle数据挖掘比赛中脱颖而出，斩获冠军，也在工业界解决了许多实际问题。
虽然学者们对决策树的研究非常深入，也提出了各类算法，但是，主流的算法却都是启发式的，无法保证决策树的全局最优解。这并不是因为这些算法不够好，早在1976年，H. Laurent和R. L. Rivest就证明了构造最优决策树是一个NP完全问题，因此，我们无法利用计算机在多项式时间内，找出全局最优的解。尽管如此，近些年来随着算力和求解器的飞速发展，整数规划模型的求解效率极大提升，通过优化求解器建模求解最优决策树也不失为另一种选择。
本文将讨论分类问题决策树的三种MILP模型。
MILP模型
首先，为了方便起见，统一定义符号。
Optimal Classification Tree
提到最优分类树，不得不说的就是D. Bertsimas在2017年发表的"Optimal classification trees"，这是近年来最优决策树研究的重要论文，后续许多工作都是对这篇文章的跟进。值得一提的是，论文中提出的最优决策树模型OCT还是D. Bertsimas开设的公司Interpretable AI的明星产品。
Optimal Classification Tree with Binary Encoding
2019年，S. Verwer等人在"Learning optimal classification trees using a binary linear program formulation"提出了一个新的最优分类树方法binOCT。为了减少所需的二值决策变量的数量，binOct公式使用二进制搜索过程对每个节点上决策阈值的选择进行建模。它们将每个可能的决策阈值表示为二进制编码。为了便于说明，我们使用下图所示的9个单一变量数据点作为例子。
我们可以注意到，binOCT的模型公式使用了大量大M，这也许会对模型在求解器分支切割时线性松弛的下界带来负面影响。关于这些大M的取值，在此并不加以赘述，感兴趣的读者可以自行阅读论文原文或者查看GitHub库中的报告
（https://github.com/LucasBoTang/Optimal_Classification_Trees/blob/main/Report.pdf）。
此外，binOCT假设每个分支节点都必须进行拆分，这也意味着binOCT构造的一定是未经剪枝的满二叉树，或将导致过拟合的问题。
Max Flow Classification Tree
为了避免大M对求解MILP最优分类树的负面影响，S. Aghaei等人在2021年提出了flowOCT，该方法发表于"Strong Optimal Classification Trees"。于前两者不同的是，flowOCT是基于仅包含二值特征的数据集，因此对于数据的非二值特征，需要通过one-hot编码等方式进行二值化处理，这无疑会增加特征的维度，对于有序特征（ordinal feature）和连续特征（continous feature），这一处理方式无疑会破坏特征的有序性。
如上图所示，对于固定深度的决策树，在其满二叉树的基础上增加源点（source node）和进点（sink node）,实例在决策树上的分配可以视为网络流（network flow），而最优分类树问题也被转化为最大流问题。
开源代码
以上三种MILP模型已经在GitHub开源，调用Gurobi作为MIP求解器，代码都已经进行了封装，API于scikit-learn相似，方便用户使用。下载代码后，导入模块tree即可调用OCT，binOCT和flowOCT。
实验对比
接下来，我们对三种MILP最优分类树以及scikit-learn的CART算法进行了实验对比，选取了11个来自UCI数据库的小规模数据集，求解器的时间限制为600秒，不使用暖启动。数据集被重复三次随机拆分为训练集（50%），验证集（25%）和测试集（25%），决策树的深度为2、3、4、5，惩罚项系数为0、0.01、0.1，对于每个模型和深度，我们选择验证集上具有最佳性能的惩罚项系数。
在44个案例中，有31种基于MILP的方法不差于CART，其中23种优于CART，主要是在小型数据集上。对于较大数据集，CART能更有效地找到了一个好的解决方案。部分原因是因为我们选择的时限为10分钟，比S. Aghaei等人使用的60分钟时限要少得多。但是，由于CART可以即时求解，因此这不是一个公平的比较。至于基于MIP的方法之间的比较，OCT在小型数据集和浅树（深度为3）上显示出强大的性能。flowOCT在44个案例中的24个案例中实现了最高的预测准确性，这是所有方法中最好的。通常，flowOCT在数据集和树的复杂性方面产生最一致的性能，相比之下，OCT和inOCT的性能不稳定，是因为在很多情况下它们都无法在时限达到最优。但是，当在浅树上训练小型数据集时，它们的非二值的特征表示比flowOCT的特征表示更紧凑，信息量更大，因此可能具有竞争力。
参考文献
Bertsimas, D., & Dunn, J. (2017). Optimal classification trees. Machine Learning, 106(7), 1039-1082.
Verwer, S., & Zhang, Y. (2019). Learning optimal classification trees using a binary linear program formulation. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 33, No. 01, pp. 1625-1632).
Aghaei, S., Gómez, A., & Vayanos, P. (2021). Strong Optimal Classification Trees. arXiv preprint arXiv:2103.15965.
Bertsimas, D., & Paskov, I. (2020). Stable Regression: On the Power of Optimization over Randomization in Training Regression Problems. Journal of Machine Learning Research, 21, 1-25.
https://en.wikipedia.org/wiki/Decision_tree
关注公众号【运筹OR帷幄】，回复关键词，可获得相关资料
<hr/>欢迎关注（公众号） @运筹OR帷幄 ，了解更多运筹学、人工智能及相关学科的干货资讯。
知乎专栏：
『运筹OR帷幄』大数据时代的运筹学
『运筹AI帷幄』大数据时代的人工智能
获得最新运筹学及其相关学科的干货资料、行业前沿信息、学术动态、硕博offer信息等。特别适合你~
欢迎大家交流。
也欢迎大佬们投稿和商业合作，学术信息、会议通讯、征稿启事、硕博招生信息等免费推广。
页:
[1]