大多数机器学习算法的计算复杂度都是随着数据量或者维度呈线性增长，这是大规模机器学习的一大挑战。本文将介绍随机决策树算法的基本方法，并从理论层面粗略的探讨了为什么随机决策树具有学习能力。
引言大数据给机器学习带来了挑战，效率成为大规模机器学习的关键问题。 随着互联网和移动互联网的发展，人类社会产生的数据越来越多。根据新摩尔定律，数据的规模每 5 年增长 10 倍。除了数据量本身的增长外，数据的维度也越来越高。数据规模的快速增长，给机器学习创造了更大价值的机会。但同时也提出了很严峻的挑战：数据量和维度的增长，使得机器学习的计算开销急剧膨胀，使得学习效率问题变得越来越严重。这是因为经典的机器学习算法的计算复杂度大多随着数据量或者维度的增长呈超线性增长。图 1 引用自文献，这个图列出了 10 大经典机器学习算法在单核和多核模式下进行一个迭代的计算复杂度。从图中可以看出，除了 Naïve Bayes、Neural Network、k-means 算法的计算复杂度与数据量和维度是线性关系外，其他的算法都是平方，甚至三次方的关系。这还是没有考虑多次迭代情况下的计算复杂度。如果考虑迭代而又无法把所有数据存在内存中的情况，每次迭代除了计算开销以外，还需要付出巨大的 IO 开销。不幸的是，数据量的增长速度是快于内存增长的速度，而绝大多数机器学习算法都是需要迭代的。数据规模的增长和学习效率降低之间的矛盾变得越来越尖锐。
图 1. 时间复杂度分析
为了解决机器学习计算开销急剧增大的问题，分布式机器学习算法和平台的研 究成为了机器学习领域的热点之一。KDD（Knowledge Discovery and Data Mining）2015 有 3 个 Tutorial 都是关于这方面的内容。但实际上，对现有算法的分布式学习只是解决了计算能力的扩展问题以及在扩展过程中如何减少 IO, 网络和同步开销的问题，但数据量增长和算法效率之间的矛盾并没有解决。而目前机器学习算法发展的主流还是在提高算法的精度，而为了提高精度往往要付出更大的计算代价，目前深度学习的发展就是一个例子。本系列文章将介绍一类非主流的机器学习算法，这类算法有别于经典机器学习算法的思想，采用随机方法建模，使得计算开销能够降低到线性水平。本篇文章将从方法、原理、计算复杂度，效果及其局限等几方面介绍随机决策树算法。
基本方法随机决策树（Random Decision Tree）算法的基本思想是随机构建若干棵决策树，在预测结果时将每棵树的预测分值进行简单平均得到最终结果。因为树的构建过程是随机的，不用计算 Gini Index、Information Gain 或者 Information Gain Ratio，其计算开销非常小，仅与数据量为线性关系。这对解决机器学习问题来说，是很好的性质。其计算复杂度的具体分析，我们将在后面介绍，这里先来看看基本的方法。
当创建一棵树的时候，该算法在每个节点的扩展过程中从“剩余的”的特征中随机选择一个。在这一挑选的过程中，不会使用任何的纯度函数 (如 information gain 和 gini 系数等) 来检查特征。对于一个类别（ categorical）特征（如性别）如果在一条从根节点到当前节点的决策路径上没有出现过，那么就被认为是“剩余的”。因为，一旦一个类别特征被使用了，那么在同一条决策路径上的学习样本在这个 feature 上的值都会是一样的（要么全是男要么全是女）。但是对于连续值特征（比如收入）在同一条决策路径上可以被多次使用的，只是每次的分类阈值只能在当前路径所包含的学习样本的取值范围内随机选择。树的生长停止条件可以有以下两种限制，一是树的最大深度，一是每个叶子节点上最少需要保留的样本个数，通常两个条件一起使用。经验上来讲树的最大深度一般设置为特征数的一半，叶子节点上最少需要保留的样本个数可以在 4-10 之间选择。当树停止生长以后，再统计每个叶子节点上的类别频率，从而获得所有的树模型。
在预测时，对一个给定的数据实例，在每棵树上都能落在一个叶子节点上。以这个叶子节点上的正样本频率（假设是二分类问题）作为这棵树对这个数据实例是正例的预测概率。将所有树的预测概率简单平均，即得到最后的预测概率。
与随机森林的异同随机决策树与随机森林非常容易混淆。随机森林也是使用多棵树，而且在树的构建过程中也引入了随机因素。但最大的不同在于随机决策树算法构建树时是完全随机的，而随机森林虽然引入了一些随机因素，但是还是要计算 Gini Index, Information Gain 或者 Information Gain Ratio 这些分支选择指标。随机森林算法的逻辑比随机决策树要复杂得多，而其计算复杂度也不可能得到很大的改善。随机深林是通过引入一些随机因素来获得有较高 Diversity 的多个模型，从而保证 Ensemble 模型具有较好的泛化能力，但本质上还是遵循经典决策树算法的基本思想，通过贪婪算法来寻找最好的分类界面。而随机决策树算法则是随机的把数据划分成不同的部分，统计每个部分的类别分布。这是随机决策树与随机森林和一般监督学习器之间的根本区别，通过下一节的分析，我们将更深入的了解这个区别。
没有“学习”为什么能做预测