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

划分被蓝线标注。切记我们候选划分的特性，划分区总是被平行于坐标轴的线所分割的。就上面的例子说，我们会觉得是个好的划分，因为左手边比较“纯”了，基本都是 x 类，只有2列属于 o 。右手边同样比“较纯”。

直觉上选择每个划分节点的时候我们都想生成“纯”的节点。如果我们再往更深一层次探索，我们会再多两个划分，如下图

现在，如您所见，坐上区域叶节点仅包含 x 类。因此纯度是100%的，没有其他的分类出现。一旦我们达到这个水平，我们就不必再进行更近一步的划分了。因为所有的划分都是100％的纯度。在此训练集上，更多的划分不再有更好的结果，尽管可能在测试集上会有所不同。

10.2 不纯度的测量公式

不纯度公式是用来测量包含不同分类点划分区域的“纯的程度”的。假设有K个不同的类别，那么就会有 P1,...,Pk 个不纯度的测量，衡量区域中每个点归属于一个分类的概率。训练当中，我们不知道真实的概率，我们只能得到在训练集下的点属于每个分类点百分比。

不纯度的测量公式可以被定义成不同的形式，但是最基本的要要素是要满足下面的三个要素。

定义：一个不纯度的测量公式 Φ ，对于所有K 元组( P1,...,Pk )，满足 ( Pj>=0,j=1,...,K,∑jPj=1 )，且：

1. Φ 值对于均匀分布将达到最大值，即当所有 Pj 都相等时；
2. Φ 值将达到最小值，当点属于某分类的概率是1，属于其他分类概率为0；
3. Φ 对于( P1,...,Pk )是对称的，置换 Pj ，Φ 值不变；

定义：给定一个不纯度的测量公式 Φ ，对于 t 节点不纯度为 i(t) ：

i(t)＝Φ( p(1|t),p(2|t),p(k|t) )

式中，p(j|t) 是给定节点t中的一个点为 j 类的后验概率估计。一旦我们知道了i(t)，我们就可以定义对于节点 t,划分优度，定义为 Φ(s,t):

Φ(s,t)＝△i(s,t)=i(t)?PR?i(tR)?PL?i(tL)

式中，可以看出 Δi(s,t) 是节点 t 的不纯度，与左右子节点不纯度加权求和之间的差值。权值 PR,PL 是节点t中样本被各自划分到左右子节点的比例。

再来看一下下图例子：

假设紫色阴影的左侧区域要被继续划分，上半部分(x)是左侧子节点，下半部分(o)是右侧子节点。那么此时左侧子节点的比例为8/10，右侧为2/10.

分类树算法会遍历所有候选划分集，找到最大△i(s,t)对应的最优划分。

接下来我们定义 I(t) = i(t) p(t),即，节点t 的加权不纯度值。 p(t)与上述中左右子节点的权值定义一致。当然如果节点t 是总体的第一个划分得到的子节点，那么权值是总体的样本中被被划分到节点t 的样本的占比。

那么对于一个树T，不纯度的总测量定义为 ， I(T)：
I(T)=∑t∈T′I(t)=∑t∈T′i(t)?p(t)

这是所有叶节点的加权求和，注意不是所有节点，是叶节点集合T’。

且对于任何节点有：
p(tL)+p(tR)=p(t)
pL=p(tL)/p(t);pR=p(tR)/p(t)
pL+pR=1

进而，我们定义一个父节点与两个子节点之间的不纯度之差：（我们得到了一个递归公式）
△I(s,t)=I(t)?I(tL)?(tR)
= p(t)i(t)?PtLi(tL)?PtRi(tR)
= p(t)i(t)?PLi(tL)?PRi(tR)
= p(t)△i(s,t)

最后，我们揭开了不纯度度量的神秘面纱…
要知道，不论我们如何定义不纯度公式，我们在分类树种使用它的过程是保持一致的。所以，唯一不同的就是具体的不纯度度量公式。

下面介绍可能会经常使用的不纯度度量公式：

1. 熵

   ∑kj=1?pj?log(pj)
   IF pj=0 , lim(pj) → log(pj)=0.

2. 错分率

   1?maxj(pj).

3. Gini

   ∑kj=1pj?(1?pj)=1?∑kj=1p2j
   .

另一种方法：The Twoing Rule

另一种分类树的分裂方法是“the Twoing Rule”. 与上述的不纯度度量公式不同。

直觉上看，在两个子节点的类别的分布应该尽可能的不同，并且落到子节点中的数据占比应该比较均衡。

The twoing rule: 对于节点 t,选择一个分裂是使下面值最大的情况:
PRPL4?[∑kj=1|P(j|tL)?P(j|tR)|]2

当我们把一个节点分裂成两个子节点时，我们希望每个分类的后验概率尽可能的不同。如果差异达到最大，则每个分类都是趋于更纯的。
如果每个子节点分类的后验概率与父节点几本一致，说明子节点的划分并没有使得纯度比父节点更好，因此不是一个好的划分。

（编辑：威海站长网）

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