算法实现随机决策树的基本方法上篇文章已经介绍了，这一方法并不复杂，没有什么高深的东西。但在实现过程中，还是有许多注意的问题。我们这里仅讨论一棵树的构造算法，多棵树仅是需要多次执行这一个算法。
原始算法在随机决策树（参考资源 [1]）中的原始算法采用的是递归方式建立空树，以设置的最大树深为结束条件。然后以递归方式基于训练数据统计每个节点上的类别的频率，再去除掉没有数据或者不满足条件（训练样本数不足）的叶子节点。在空树的构建过程中，非数值型的特征在一条路径上只能出现一次，为所有可能的取值建立分支。而数值型的则可出现多次，每次都是建立两个子分支，但是分裂点则只能在这个节点的可能取值范围内随机选。在统计阶段，把所有训练数据自树的根开始向下逐步分配到叶子节点，中间统计每个节点的类别分布频率。在统计过程中，对于缺失值要做特殊处理。即，首先要统计一个节点的各个子分支的出现频率（非缺失值的频率），然后将缺失值的样本按照这个频率随机选择一个分支分配。在预测的时候，如果遇到缺失值也是根据子分支的频率随机分配。
这个算法的实现并不算复杂，麻烦一点的地方在于缺失值的处理。但是在数据量较大，维度较多和树深较深的时候，会有一些缺点。首先是建立空树就需要考虑所有的可能性。在最简单的情况下，即所有维度都是 2 值时，则需要建立的是满二叉树。如果树深为 d, 则一棵树的节点数为 ，这在树深很大的时候树的结构会急剧膨胀从而使得内存开销无法承受。而一般的情况下，每个特征的可能取值是大于等于 2 的，则树的结构膨胀速度会比二叉树的情况更遭。其次，树的构建过程和统计过程，都是采用的递归实现，这在树结构很大，树很深的时候容易导致栈溢出。特别是在用 Java 实现时，由于栈空间相对于堆空间是非常小的，这个问题很容易出现。再有一个缺点就是缺失值的处理问题，不仅程序上带来一些麻烦，提高了计算开销，更重要的是这种处理方式并不足够科学，特别是在缺失比例很高的情况下。
Dice 实现 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 线性相关。
而传统的 TDIDT 决策树（Top-Down Induction of Decision Trees，包括 ID3 和 C4.5 算法）其训练复杂度为, 其中, 而是第个特征的取值个数。显然，该类算法的算法复杂度与特征个数是超线性关系。在一般情况下，所以随机决策树算法的计算复杂度是远小于这类算法的。
精度和效率前面简单介绍了随机决策树算法的实现和训练复杂度，这一节将简要介绍下其精度和训练效率，并与其他经典算法进行比较。 |
