对于以上数据集，我们使用 30 棵树的随机决策树（其叶子节点最少保留 4 个训练样本，最大深度为特征数）进行实验。并使用 Weka 测试 J48(C4.5 决策树)，SMO(SMO 算法实现的 SVM) 和 Logistic Regression 算法。Weka 测试的算法的参数使用默认参数。所有的实验结果列在表 2，其中训练时间的单位为秒。 表 1. Weka 测试结果
表 2. Weka 测试结果Data RDT J48 SMO LR
AUC Tr.Time AUC Tr.Time AUC Tr.Time AUC Tr.Time
a1a 0.879 0.569 0.712 1.861 0.760 1.574 0.751 1.010
a9a 0.890 24.171 0.755 647.013 0.761 1637.011 0.763 35.901
mushrooms 1.000 3.608 1.000 13.651 1.000 1.665 1.000 3.993
w1a 0.953 0.934 0.613 23.022 0.748 0.759 0.732 6.561
w8a 0.997 33.759 - - 0.797 487.39 0.822 371.836
splice 0.909 0.387 0.935 0.770 0.843 1.742 0.853 0.819
cod-rna 0.969 7.799 0.944 155.763 0.944 62.705 0.937 4.271
covtype 0.768 24.392 - - - - 0.705 299.667
gisette 0.934 82.513 - - - - -
从上表中我们可以看到，随机决策树的精度总体上超过其他 3 个经典算法。虽然其他三个算法使用的是默认参数，但是随机决策树使用的也是默认参数，并未对不同数据集进行调参，因此比较也是基本公平的。而速度上可以看到随机决策树算法也是具有很大的优势。注意到表中有一些空缺项，那是在 1 个小时内跑不出结果从而终止的实验。可以看到 RDT 可以在所有数据集上跑出结果，而其他的算法则在稍大的数据集上有可能跑不出结果（Weka 的实现不够高效可能也是原因之一）。
算法并行化讨论Dice 的实现是比较高效的，我曾经用在过腾讯广点通的 CTR 估计上训练上千万样本的问题，仅需要 10 分钟就能完成训练。但是毕竟这是个单机实现，处理问题的规模总有上限。为了处理更大规模的问题，我们需要考虑随机决策树算法的并行化问题（仅考虑在 Hadoop 和 Spark 上的并行）。但是，随机决策树算法的并行化却有比较大的困难。Dice 对原始实现的优化中，很重要的一条就是将先建空树改成逐层建树，从而减少了内存的消耗。但是这会要求要多次使用训练数据，即多次迭代训练数据，在单机模式下不是大问题。但是在 Hadoop 上并行实现，则会要多次从 HDFS 上读取训练数据，而 Hadoop 程序最大的开销就在 IO 上，这一实现会带来效率的严重降低。而原始实现的先建空树，反而可以只需要再读一次数据进行剪枝，统计即可，只不过树深受到极大限制。当然在 Spark 平台上可以把数据都存放在内存中，但是由于内存资源比较稀缺，并不是所有的问题，都可以把数据放在内存中，这一问题仅仅是缓解了而不是彻底解决了。同时，树结构的复杂性，使得树模型在不同节点间的同步和合并也有很多麻烦。目前，随机决策树在并行化上的困难，也让该算法在解决大数据问题时遇到瓶颈。
结束语