第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

当我们把一个节点破碎成两个子节点时，我们但愿每个分类的后验概率尽也许的差异。假如差别到达最大，则每个分类都是趋于更纯的。
假如每个子节点分类的后验概率与父节点几本同等，声名子节点的分别并没有使得纯度比父节点更好，因此不是一个好的分别。

（编辑：湖南网）

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