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