一个简单例子
该例子引自范伟博士的网站：有一二维的人造正负样本分布，如图 1 所示。其中红色为正样本，绿色为负样本。显然这个问题不是线性可分的，
图 1. 二维人造正负样本分布 下面图 2—图 5 分别给出随机决策树算法、决策树，线性 SVM 和 RBF 核的 SVM 算法的训练结果。
图 2. 随机决策树（训练时间 5 秒） 图 3. 决策树 (训练时间 1 秒) 图 4. 线性 SVM(训练时间半天) 图 5. RBF SVM(训练时间 1 天) 显然，随机决策树对原分布的估计是较好的，与 RBFSVM 的效果在同一水平上。而决策树算法则带来了明显的锯齿型边界，而线性 SVM 则无法将右上方的正样本正确划分。从训练时间看，SVM 开销非常大（可能未使用 SMO 方法），树的算法都很快。但是随机决策树算法的训练开销比决策树要高 5 倍，与我们前面的分析相反。这有两个原因，一是对于低维度问题，随机决策树算法的效率与决策树相比并没有明显优势。因为决策树算法的时间复杂度与特征数量的关系是超线性的，在特征较少时，其复杂度并不会太高，而随着特征的增长，计算复杂度会快速增长。二是这个实验是使用的随机决策树的原始实现，其效率并不是太高。
Dice 测试结果
我们从 Libsvm 选取了 9 个二分类数据集，这些数据集的统计信息列在表 1 中。
表 1. 从 Libsvm 选取的 9 个二分类数据集的统计信息
NameFeature TypeFeature NumberTrain Data NumberTest Data NumberTrain Data SizeTest Data Sizea1aBinary1231,605 30,9560.11M2.11Ma9aBinary12332,561 16,2812.22M3.33MmushroomsBinary1127,1241,0000.753M0.105Mw1aBinary3002,47747,272 0.166M3.15Mw8aBinary30049,74914,951 3.31M1.00MspliceCategorical601,0002,1750.7M1.48Mcod-rnaNumeric859,535271,6174.45M20.3McovtypeNumeric54481,082100,00056.2M11.6MgisetteNumeric5,0006,000 1,00050.4M8.52M对于以上数据集，我们使用 30 棵树的随机决策树（其叶子节点最少保留 4 个训练样本，最大深度为特征数）进行实验。并使用 Weka 测试 J48(C4.5 决策树)，SMO(SMO 算法实现的 SVM) 和 Logistic Regression 算法。Weka 测试的算法的参数使用默认参数。所有的实验结果列在表 2，其中训练时间的单位为秒。表 1. Weka 测试结果
表 2. Weka 测试结果
DataRDTJ48SMOLR
AUCTr.TimeAUCTr.TimeAUCTr.TimeAUCTr.Timea1a0.8790.5690.7121.8610.7601.5740.7511.010a9a0.89024.1710.755647.0130.7611637.0110.76335.901mushrooms1.0003.6081.00013.6511.0001.6651.0003.993w1a0.9530.9340.61323.0220.7480.7590.7326.561w8a0.99733.759--0.797487.390.822371.836splice0.9090.3870.935 0.7700.8431.7420.8530.819cod-rna0.9697.7990.944155.7630.94462.7050.9374.271covtype0.76824.392----0.705299.667gisette0.93482.513-----
从上表中我们可以看到，随机决策树的精度总体上超过其他 3 个经典算法。虽然其他三个算法使用的是默认参数，但是随机决策树使用的也是默认参数，并未对不同数据集进行调参，因此比较也是基本公平的。而速度上可以看到随机决策树算法也是具有很大的优势。注意到表中有一些空缺项，那是在 1 个小时内跑不出结果从而终止的实验。可以看到 RDT 可以在所有数据集上跑出结果，而其他的算法则在稍大的数据集上有可能跑不出结果（Weka 的实现不够高效可能也是原因之一）。
算法并行化讨论Dice 的实现是比较高效的，我曾经用在过腾讯广点通的 CTR 估计上训练上千万样本的问题，仅需要 10 分钟就能完成训练。但是毕竟这是个单机实现，处理问题的规模总有上限。为了处理更大规模的问题，我们需要考虑随机决策树算法的并行化问题（仅考虑在 Hadoop 和 Spark 上的并行）。但是，随机决策树算法的并行化却有比较大的困难。Dice 对原始实现的优化中，很重要的一条就是将先建空树改成逐层建树，从而减少了内存的消耗。但是这会要求要多次使用训练数据，即多次迭代训练数据，在单机模式下不是大问题。但是在 Hadoop 上并行实现，则会要多次从 HDFS 上读取训练数据，而 Hadoop 程序最大的开销就在 IO 上，这一实现会带来效率的严重降低。而原始实现的先建空树，反而可以只需要再读一次数据进行剪枝，统计即可，只不过树深受到极大限制。当然在 Spark 平台上可以把数据都存放在内存中，但是由于内存资源比较稀缺，并不是所有的问题，都可以把数据放在内存中，这一问题仅仅是缓解了而不是彻底解决了。同时，树结构的复杂性，使得树模型在不同节点间的同步和合并也有很多麻烦。目前，随机决策树在并行化上的困难，也让该算法在解决大数据问题时遇到瓶颈。
结束语随机决策树算法在精度和效率上都有不错的表现，但是并行化却很困难。可以看到我们在决策树算法中用随机方法替代了贪婪方法来构建树结构，从而获得了效率上的很大的提高。但是树结构本身的复杂性，使得其很难进行并行。为了克服这个问题，我们是否可以考虑用其他方法（例如随机决策哈希算法）来取代树结构对数据空间的划分，从而克服并行化困难呢？但由于篇幅有限，该问题暂不属于本文的讨论范围，有机会笔者将在后续文章中讨论。 |
