文档介绍：第七章决策树概念“ puter ”的决策树 age? overcast student? credit rating? no yes fair excellent <=30 >40 nono yes yes yes 30..40 ?什么是决策树? –类似于流程图的树结构–每个内部节点表示在一个属性上的测试–每个分枝代表一个测试输出–每个树叶节点代表类或类分布?:衡量不确定性?离散型 的无条件熵?式中 p(x i)为 X=x i时的概率; u为X的可能取值个数。)( log ) p(x )( 2 u1i iix XH????? C的无条件熵?设描述属性 A1 , A2 … Am ,类标属性为 的无条件熵为: ?u为C可能取值个数,即类别个数,记为 c 1,c 2…c u.?S i为属于类别 c i的记录个数。 n sn sCE i ui i21 log )(????? A k( 1<=k<=m) 类标属性 C的有条件熵定义为: 。 C aAs 。 aAs aaa, A s ss sn sACEi jk ij jkj k j ij ui j ij j jK的记录数目且属于类别即为的记录数目为取值为的可能取值个数为其中????????...., ) log (),( 21 211 ????思想:分类算法应尽可能地选择对减少类标属性贡献最大的描述属性。?:它用来度量描述属性减少类标属性不确定性的程度。?给定描述属性 A k( 1<=k<=m), 类标属性 C的信息增益定义为: 。 AACG ACECEACG kk k k 就越大对减少不确定性的贡献越大,),( ),()(),(??决策树策略(1) ?算法使用基于熵的度量——信息增益作为指导信息,选择能够最好的将样本分类的属性;该属性成为节点的“测试”属性。(使用分类属性) ?对测试属性每个已知的值,创建一个分支,并以此划分样本决策树策略(2) 3. 算法使用同样的过程,递归的形成每个划分上的样本判定树。一旦一个属性出现在一个节点上,就不在该节点的任何子节点上出现 4. 递归划分步骤停止的条件–给定节点的所有样本属于同一类–没有剩余属性可以用来进一步划分样本——使用多数表决–没有剩余的样本