测试的选取 ·决策树设计的核心问题之 基本思想: 使后继结点的数据尽可能的“纯粹” 节点N的不纯度( impurity)i(N) 当N节点上的所有模式都来自同一类时,N)=0 当N节点上的模式类别分布均匀时,i(N)应很大
测试的选取 • 决策树设计的核心问题之一 • 基本思想： 使后继结点的数据尽可能的“纯粹” • 节点N的不纯度（impurity）i(N) • 当N节点上的所有模式都来自同一类时，i(N)=0； • 当N节点上的模式类别分布均匀时，i(N)应很大
测试的选取 ·常用不纯度度量 熵不纯度( entropy impurity) i(N)=2P(j)log2 P(ui) P(o, 属于的样本个数 样本总个数 Gin不纯度 i(N)=∑P(a)P( 误分类不纯度 i(n)=1- max P(wi)
测试的选取 • 常用不纯度度量 • 熵不纯度（entropy impurity） • Gini不纯度 • 误分类不纯度 ( ) j P j = 属于 的样本个数 样本总个数
测试的选取 ·常用不纯度度量 i(P) P 0.5
测试的选取 • 常用不纯度度量
测试的选取 ·对N节点如何选择查询? 使不纯度下降最快的那个查询! Ai(n)=i(n)- pli(nl)-(1- Pli(nr) ·NML和NR分别为左、右子节点 i(N)和i(N)分别为左、右子节点的不纯度 P是N节点的模式划分到NL的比例 ·如果采用熵不纯度,则不纯度下降差就是本次査询所能提供的 信息增益( information gain)
测试的选取 • 对N节点如何选择查询？ 使不纯度下降最快的那个查询！ • 和 分别为左、右子节点 • 和 分别为左、右子节点的不纯度 • 是N节点的模式划分到 的比例 • 如果采用熵不纯度，则不纯度下降差就是本次查询所能提供的 信息增益（information gain）
信息增益 信息增益( information gain) ·S:节点N上样本总个数 S;:其中属于类的样本个数(i=1,2,,.m) 属性A的第个取值(j=1,2,…,V) ·该节点处的熵不纯度 E(S)=∑aog2 属性A将S划分为v个子集{S1,S'2,…,S" S”中属于O1类的样本个数为Sn
信息增益 • 信息增益（information gain） • ：节点N上样本总个数 • ：其中属于 类的样本个数（i=1,2, …, m） • ：属性A的第j个取值（j=1,2, …, v） • 该节点处的熵不纯度 • 属性A将S划分为v个子集 • 中属于 类的样本个数为 i 2 1 ( ) log m i i i S S E S = S S = − i