第10章－基于树的方法(1)-生成树

我们先来定义:

1. 样本个数为N，样本的有K个分类, Nj 是属于j类的样本个数，其中， 1≤j≤K. 如果把所有的 Nj 加起来，将得到N。
2. 对于节点t，t中的样本个数为 N(t)，其中，属于j类的样本数为 Nj

于是，对于节点t，如果把所有的分类加起来，我们得到：
∑kj=iNj(t)=N(t)

并且，对于分类j，如果我们把左右子节点的样本数加起来，应该等于父节点的样本数：
Nj(tL)+Nj(tR)=Nj(t)

接下来我们定义类的先验概率为 πj . 此先验概率通常通过计算数据中没个分类的占比得到。举例，如果我们想知道类别1的先验概率，我们只需要简单的计算属于类1的数量占总体数量的百分比， Nj/N . 这个比例又叫做类的经验频率。

上述数计算先验概率的一种方式，有时也可能是预先给定的。比如说，在医疗的例子中，研究者收集患有某一疾病的病人了大量的数据。在收集数据中，患有某一疾病的样本比例可能远高于总体的实际比例。这种情况下，就不太适合使用实际数据计算得到的经验频率。但如果数据是总体中的随机样本，则是可行的。

j 类样本属于节点 t 的条件概率估计为， p(t|j)=Nj(t)/Nj
显然,
Nj(tL|j)+Nj(tR|j)=Nj(t|j)

假设我们知道如何得到 p(t|j) ，我们将得到类别 j 和 节点 t 的联合概率：
p(j,t)=πjp(t|j)=πjNj(t)/Nj

那么在节点t下的样本的概率为：
p(t)=∑kj=1p(j,t)=∑kj=1πjNj(t)/Nj

现在我们就需要知道如何计算 p(j|t) 了,即节点t下的一个样本属于 j类的条件概率：(注意，此处的条件概率是翻转的，不是p(t|j) )

p(j|t)=p(j,t)/p(t)

.

决定节点所属分类的规则

假设我们已经构建了一个树，那么这个决策树是如何对新的样本点进行分类点呢，步骤如下：
我们先让样本点根据决策树的规则判断该点会落到哪个叶节点(终节点)。叶节点的类就会赋给这个新的样本点。所有落在一个叶几点的样本点都会被赋予同一个类，这点有点像 k-means 和 其他原型方法。

那么，构建决策树的时候是如何确定一个叶节点(终节点)的类别的呢，步骤如下：

如果我们用0-1损失，那么类的确定规则会很像k均值－我们选择叶节点样本中，出现频次最多的类或者具有最大后验概率的类作为该节点的类：

k(t)=argmaxP(j|t)

假设我们已经有了一个树，而且没个叶节点上也都赋予了分类。现在我们就需要估计这个树的分类错误率了。 在这个例子中，我们需要介绍错分概率的再代入估计 r(t)，给定一个落到节点t 的样本，则：
r(t)=1?maxp(j|t)=1?p(k(t)|t)

定义 R(t)=r(t)p(t) ，则全体错分概率的再代入估计 R(T)为
R(T)=∑t∈T′R(t)

接下来，我们要花点时间证明如果我们把节点拆分成子节点，那么错分率一定是又提升的。换句话说，如果用再代入估计计算错误率，那么节点的拆分越多，错误率越小。这就导致了再代入误差的一个问题：偏向更大的树。

证明，对于任何节点t，拆分成子节点 tl和tR 后，均有
R(t)≥R(tL)+R(tR)

定义 j*=k(t).

10.4 例子(略)

10.5 树结构方法的优点

• 如同我们多次提到的，树结构的方法能以简单的方式处理分类变量和定序变量；
• 分类树有时能够自动的分步骤的进行筛选变量和降低复杂度
• 分类树对于测试的样本点提供了错分类估计
• 分类树对于有序变量的单调变换是不变的。分类树的划分是根据阈值，而单调变换并不改变划分节点的阈值
• 分类树对于异常值和误分类点相对稳健。因为除了数据本身，并不需要计算如平均值等其他指标
• 分类树很容易解释， 特别是在医学领域的应用

10.6 变量合并

目前为止，我们假设分类树只是平行坐标轴地对空间进行划分。对于这样严格地划分，会带来什么结果呢？

让我们来看一下下面这个例子：
如图中所示，我们可能更想要把所有的点按照对角线划分成两类。平行于坐标轴的划分对于这个数据集似乎并没那么有效，还需要更多的步骤去划分。

而且对于分类树的延伸方法也是有许多的，比如并不是按照每个独立变量阈值逐一去划分的线性判别分类（划分一次就使用了样本点的所有信息）。

再或者说，我们用更复杂的问题，如，线性变量的线性组合 (显然增加了计算量)：
∑ajxj<=c?

研究似乎表明，使用更灵活(复杂)的问题即使没有使结果变坏，也往往不会导致明显更好的分类结果。而且，更灵活的问题更容易导致过拟合问题。
并且，似乎使用正确规模的分类树 相比于 在各自节点上划分的好坏 更重要。

10.7 缺失变量

在一些训练样本中，有些变量可能会有缺失值。测试样本中可能也会有。决策树有个很好的办法处理缺失值——替代分裂(surrogate splits)。

假设对于节点t ，最优的划分是t，该划分用到了 Xm 变量。那么如果这个变量缺失了怎么办。

分类树将会通过找到一个替代分裂点处理这个问题。通过另一个变量找到另一个划分。遍历所有变量，找到最接近最优划分的替代。如果替代划分同样存在缺失值，那么继续找次优的代替分裂，以此类推。

（编辑：衡阳站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!