第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)对应的最优划分。

（编辑：PHP编程网 - 湛江站长网）

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