实现三遍决策树，你就会想出更快的算法！

背景

决策树（Decision Tree）可以说是当下使用最为广泛的机器学习模型，任何一个刚刚学习人工智能或者数据挖掘的同学可能都接触过实现决策树的课程作业。

决策树的想法可以追溯到二十世纪60年代（Hunt's Algorithm），但是那个时候的计算机速度比现在慢好多个数量级，内存也很小，能做一些简单的方程求解就谢天谢地了。随着硬件计算能力的提升，也是到了90年代，决策树算法才真正逐渐走进更多的实践舞台。当时比较常见的决策树算法是ID3，C4.5和CART，这三个模型直到今天也被广发使用于各行各业。在我们今天的教程上，介绍的主流算法依然是这三个模型。

我个人最喜欢的模型是CART，其中tree pruning的办法非常精妙，每次复习到这里都会仔细体会一番先人的智慧。事实上，CART模型pruning的办法也被用于Variable-order Markov Model（生物信息经典模型之一）中variable-order state空间的pruning。我刚读博的时候发现我的co-advisor非常精通决策树算法和它的各种变体，我当时还十分诧异为什么她会如此了解，过了几年才意识到原来她读博的co-advisor就是CART的发明者之一。

在90年代，当时计算机的内存很小，IBM的科学家发现运行决策树算法的最大瓶颈是没法一次性把所有数据读进内存，于是研发了SLIQ算法。相比经典的递归实现，SLIQ是一个广度优先的决策树算法，它一层一层地来生成一棵树，每次生成新的一层需要遍历整个数据集两次。第一次用来寻找当前层所有最优的分割点，第二次根据找到的分割点，用来更新每个样本所在的叶子节点。

SLIQ算法同时也比传统的实现办法更快。这个没出现过在教程里的算法正是XGBoost里面使用的"exact" tree method的模块，Tianqi Chen在实现了SLIQ之后让XGBoost成了当时各大数据挖掘比赛又快又好的利器。到了今天，随着计算机硬件水平提升到新的高度，决策树算法的内存瓶颈逐渐弱化，单模型的计算速度和模型的复杂性和准确率逐渐变得更加重要。决策树的使用也逐渐从过去的单模型向集成模型（ensemble model）发展，Random Forest和Gradient Boosted Trees成了业界主流的两个集成模型。在这样的背景下，机器学习顶级会议NIPS最近几年依然会接受与提升决策树性能相关的文章。比如之前比较火的LightGBM就是高效实现了决策树的一种近似算法。

在这篇文章，我打算简要谈谈我过去三次实现决策树算法的经历和心得，以及我最近是如何发现一个新的又快又简单的决策树算法实现的。

第一次实现

第一次实现决策树是在大四的时候，用的语言是Matlab，当时在学习机器学习的基础内容。现在回想起来，自己当时实现的主要目的是为了重现一个正确的决策树算法，有很多实现细节都没有做到最优或者正确。比如在没有事先排序特征的情况下计算Gini index，在算法执行过程中对数据做了多份拷贝，没有实现tree pruning而只用了简单的termination criterion，以及duplicated values的处理等等。这些细节如果搞不清楚，实现出来的决策树会有很大问题，如果拿Matlab标准实现做一下对比，就会发现差异很大。

第二次实现

时隔三年，我在数据挖掘的课程上又有一次机会接触决策树的实现，这次是正儿八经的要实现CART。恰好当时我还在学习Scala，于是就用Scala写了一个决策树的实现。第一次实现过程中没有注意到的细节，这次都尽量体现出来。实际上，Scala的语言特性在很多时候会让实现变得更加方便，最终写出来大约也就200行的Scala code。

这次我还特别做了一个可视化的工具，可以用dot把整棵树画出来并用深浅的颜色标注reSubstition error。

具体的介绍可以参考：bobye/scalaCART

转自：豆豆叶