随机非参数学习算法，第 1 部分: 随机决策树基本方法和理论探讨
大多数机器学习算法的计算复杂度都是随着数据量或者维度呈线性增长，这是大规模机器学习的一大挑战。本文将介绍随机决策树算法的基本方法，并从理论层面粗略的探讨了为什么随机决策树具有学习能力。
引言
大数据给机器学习带来了挑战，效率成为大规模机器学习的关键问题。 随着互联网和移动互联网的发展，人类社会产生的数据越来越多。根据新摩尔定律，数据的规模每 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 模型具有较好的泛化能力，但本质上还是遵循经典决策树算法的基本思想，通过贪婪算法来寻找最好的分类界面。而随机决策树算法则是随机的把数据划分成不同的部分，统计每个部分的类别分布。这是随机决策树与随机森林和一般监督学习器之间的根本区别，通过下一节的分析，我们将更深入的了解这个区别。
没有“学习”为什么能做预测
随机决策树算法的基本思想与一般学习算法有很大的不同，是违反一般监督学习理论的常识的。因为在决策树的结构构建中，根本没有利用监督信息，从常识出发，该算法产生的模型不应该有预测能力。 但在实践中，随即决策树算法的预测精度是可以跟经典的算法相媲美的。随机决策树为什么能有学习能力，一直是令我着迷的一个问题。其相关文献都只有一些在理论上都不够严谨的说明和分析。本节将简要介绍个人对这个问题的理解。
机器学习和统计学
机器学习是伴随着计算机的发明而出现的，上世纪 40 年代现代计算机发明后，50 年代就兴起了第一波机器学习的研究浪潮。在计算机出现以前，统计学已经建立了严密的体系和方法。这些方法在小样本量和很少维度的数据上，能够有很多不错的结果。到现在我们大学里学的统计学都是专注在研究这些小样本量和 1-2 维的问题。在理论上，把统计学的方法往高维空间中推广并没有困难，但在实际上这些方法往多维推广遇到了维数诅咒问题。统计学很重要的一个工作就是估计概率密度函数，也提供了很多概率密度函数的模型，如最典型的正态分布函数。实质上概率密度函数估计就是函数拟合。但是随着维度的增加，达到同样估计精度需要的样本数量几何数级的增加，这就是维数诅咒问题。在多维情况下，经典的统计学工具无法有效解决问题。为此，机器学习在处理这些问题时，采用了两种不同的策略。一种是放弃对估计精度的严格要求，采用简单、强假设的、线性模型来拟合，典型的如朴素贝叶斯和逻辑回归（Logistic Regression）。另一个方法，就如 Vapnik 所说，为了解决一个问题，不应该去解决比这个更难的问题。就分类问题而言，就是应该直接找分类界面而不是估计类别的分布概率函数。典型的算法就是 SVM, 而决策树算法也可以归为这一类。总之，机器学习实际上是统计在多维情况下对维数诅咒问题的妥协。
上面讨论的机器学习和统计学主要涉及参数估计方法，也是我们在大学统计学教材中主要讨论的方法。但是在统计学上有另外一套概率密度函数估计的方法，那就是非参数估计方法。非参数估计不需要假设数据是服从哪种分布模型的，因此该方法的适应性要强很多。但同时，非参数估计得出的模型相比参数模型则复杂很多，从数学上看也比较丑陋。最简单的非参数估计方法就是直方图。直方图的缺点是估计出来的函数图形是阶梯壮的，两个方柱之间估计结果是断层跳跃的，这就使得直方图的估计精度比较粗糙。为了克服直方图的问题，Parzen Window 方法又在直方图划分的箱中引入了高斯核来平滑直方图的估计。但是其计算开销也远大于直方图。 而另一种比较小众的非参数估计方法，平衡了这两种方法的优缺点。这个方法就是 Averaged Shifted Histogram（平均偏移直方图）。简单来说 ASH 方法就是把多个直方图的结果做简单平均，这些直方图的规格都是一样的，不同的是这些直方图之间有平移，也就是说用一组有平移关系的直方图融合起来做概率估计。图 2 中 ASH 的例子，展示了从一个直方图到 32 个直方图时估计的概率密度函数的变化。显然，随着直方图数量的增加，概率函数的估计越来越平滑。虽然非参数估计有自身的优点，但是同样受制于维数诅咒的问题，难以扩展到多维问题上。
随机决策树算法的理论探讨
回过头来看随机决策树算法。如果我们把随机决策树算法用在一维的问题上，就会发现其跟 ASH 非常相似。一个一维问题的决策树，实际上就是对一维空间做了分段，然后统计每个分段里的类别出现频率。这在形式上与直方图是十分相似的。唯一的不同是一维的决策树不要求每个段的宽度是一样的。显然， 多棵一维随机决策树算法也跟 ASH 算法相似，实际上也是一种非参数估计方法。
基于上面的分析，随机决策树拥有学习能力从原则上也并不是什么神秘的事情，它可以看作是 ASH 算法在多维问题上的一种变种。ASH 算法由于直方图在多维问题上的直接扩展会导致大量的空箱和一个样本的箱使得估计误差会变得很大而失去意义。而树的结构却克服了这个问题，树结构实际上根据样本在数据特征空间中的分布进行了划分，并确保每个叶子节点上的样本数不会少于一个给定的阈值。这就使得树划分出来的各个数据子空间（对应直方图的箱）里的概率估计相对准确。当然，在高维问题下，由于每个叶子节点几乎���可能覆盖所有的维度空间，这些叶子节点上的概率估计实际也只是边缘概率的估计。由于有多棵树对数据特征空间的不同划分，使得对于一个给定点的联合概率的估计由多组不同的边缘概率的平均值来估计。随机决策树实际上就是非参数估计方法在高维问题上的一种妥协。
图 2. 从一个到 32 个直方图时概率密度函数的变化
结束语
限于篇幅本篇文章仅简要介绍了随机决策树算法的基本方法，以及为什么这样的纯随机算法具有学习能力。 我们看到随机决策树算法实际上是非参数估计方法在高维问题下的一种妥协。虽然非参数估计方法在低维问题上和效率上与参数估计方法相比并没有什么优势，但是随机决策树算法在高维问题上显示出了很高的效率优势。本系列的下一篇文章将对随机决策树的两种实现方式和算法复杂度进行具体分析，并与其他的一些算法的实际效果进行对比。