大多数机器学习算法的计算复杂度都是随着数据量或者维度呈线性增长，这是大规模机器学习的一大挑战。上一篇文章介绍了随机决策树算法的基本方法，并从理论层面粗略的探讨了为什么随机决策树具有学习能力。本篇文章我们将着重介绍随机决策树的算法实现，算法的复杂度和实验结果中展示的精度和效率。
算法实现随机决策树的基本方法上篇文章已经介绍了，这一方法并不复杂，没有什么高深的东西。但在实现过程中，还是有许多注意的问题。我们这里仅讨论一棵树的构造算法，多棵树仅是需要多次执行这一个算法。
原始算法在随机决策树（参考资源 [1]）中的原始算法采用的是递归方式建立空树，以设置的最大树深为结束条件。然后以递归方式基于训练数据统计每个节点上的类别的频率，再去除掉没有数据或者不满足条件（训练样本数不足）的叶子节点。在空树的构建过程中，非数值型的特征在一条路径上只能出现一次，为所有可能的取值建立分支。而数值型的则可出现多次，每次都是建立两个子分支，但是分裂点则只能在这个节点的可能取值范围内随机选。在统计阶段，把所有训练数据自树的根开始向下逐步分配到叶子节点，中间统计每个节点的类别分布频率。在统计过程中，对于缺失值要做特殊处理。即，首先要统计一个节点的各个子分支的出现频率（非缺失值的频率），然后将缺失值的样本按照这个频率随机选择一个分支分配。在预测的时候，如果遇到缺失值也是根据子分支的频率随机分配。
这个算法的实现并不算复杂，麻烦一点的地方在于缺失值的处理。但是在数据量较大，维度较多和树深较深的时候，会有一些缺点。首先是建立空树就需要考虑所有的可能性。在最简单的情况下，即所有维度都是 2 值时，则需要建立的是满二叉树。如果树深为 d, 则一棵树的节点数为
Dice[2] 项目是用 Java 语言开发的，支持二分类，多分类，多标签分类和回归。随机决策树的原始实现存在很多问题，为了克服这些问题我在 Dice 项目的实现中进行了一些优化：
首先是先建空树，然后剪枝的方式改成在树的生长过程中根据数据的情况决定是否分支。对于非数值型的特征来说，在某个节点检查在这个节点上的数据有多少种取值，然后根据取值个数分支。举个例子，学历这个特征可以有本科，研究生，博士生三个可能取值，但是在某一个节点上的数据里只有本科生和研究生两种取值，则只会分两支。对于数值型的特征，则会随机选择两个不同的值进行平均作为分裂值，如果所有的特征都相同则不会选择这个特征。
其次，对于缺失值的处理是将其当作一个新的特征值独立分支。这样就不需要统计每个节点上的特征取值的分布，简化了算法实现。
最后，将递归算法改为非递归算法，树是逐层生长的。在生长过程中，有数据结构记录每个样本落在了哪个节点上，避免样本重复从树根走起。非递归实现不依赖于栈。
Dice 实现除了克服以上三个主要问题，算法实现上还做了很多的细节优化。比如，为了尽可能的节省内存，数据的存储尽可能使用 primitive 类型的数组，相比于 Weka 将每个样本封装成一个对象，节省了大量的空间。Dice 的实现克服了原始算法的一些缺点，使得算法的效率和处理的数据规模有较大提高。下一节在算法的计算复杂度分析中将基于 Dice 的实现。
计算复杂度分析随机决策树算法的计算复杂度来自于两部分。一是构建树结构的计算复杂度，二是统计每个叶子节点上的样本类别分布的计算复杂度。构建树结构的计算复杂度与训练样本数和特征数有关。但是在最坏的情况下，即树的生长达到了最大的深度限制时，其复杂度仅与树的最大深度限制和训练数据数量有关。这是因为在最坏的情况下，树的最大深度达到最大限制，而树还是满树，即所有训练样本都走到了最深的深度上。设树的最大深度为 d，训练样本树为 n，则在此种情况下，构造一棵树仅需要分配样本 dn 次。则构造树的最大复杂度为O(dn)。而一般情况下，并不是每棵树都会生成最大深度的满树，实际开销是还会要小不少。至于叶子节点统计时的开销是极小的，这里不做考虑。其他的决策树算法分析里也不考虑这部分开销。基于以上分析，可以认为在训练数据总数为 n，最大树深为 d，树棵树为 m 时，随机决策树算法的训练开销为O(mdn)。一般的情况下，m<<n，d<<n。可以看到，算法的训练复杂度在 m 和 d 给定的情况下仅与训练样本数 n 线性相关。