决策树算法 基本算法(贪心算法) 自上而下分而治之的方法 开始时所有的实例都在根节点 属性都是分类型(如果是连续的,将其离散化) 所有记录用所选属性递归的进行分割 属性的选择是基于一个启发式规则或者一个统计的度量(如信息增 停止分割的条件 一个节点上的实例都属于同一个类别; ■没有属性可以再用于对数据进行分割
6 决策树算法 ◼ 基本算法（贪心算法） ◼ 自上而下分而治之的方法 ◼ 开始时所有的实例都在根节点 ◼ 属性都是分类型 (如果是连续的，将其离散化) ◼ 所有记录用所选属性递归的进行分割 ◼ 属性的选择是基于一个启发式规则或者一个统计的度量 (如信息增 益) ◼ 停止分割的条件 ◼ 一个节点上的实例都属于同一个类别； ◼ 没有属性可以再用于对数据进行分割
属性选择的统计度量 ■信息增益— information gain(ID3/C5.0) 所有属性假设都是分类型字段 ■经过修改之后可以适用于数值型字段 ■信息增益率(C4.5) 基尼指数— Gini index( IBM Intelligent Miner) 能够适用于分类和数值字段 Ⅹ检验 CHAID) 其他
7 属性选择的统计度量 ◼ 信息增益—Information gain (ID3/C5.0) ◼ 所有属性假设都是分类型字段 ◼ 经过修改之后可以适用于数值型字段 ◼ 信息增益率（C4.5) ◼ 基尼指数—Gini index (IBM Intelligent Miner) ◼ 能够适用于分类和数值字段 ◼ χ 2检验(CHAID) ◼ 其他
信息增益(ID3) 任意样本分类的期望信息: I(1s…Sm)=-ΣPilg2(p)(=1.m) 其中,数据集为S,m为S的分类数目,PS C为某分类标号,P为任意样本属于C的概率,s为分 类Ci上的样本数 由A划分为子集的熵: E(A)=∑(|1j|+…+|sm)/|s*I(S1j, A为属性,具有V个不同的取值 信息增益:Gain(A)=I(s1,S2…m)-E(A)
8 信息增益(ID3) ◼ 任意样本分类的期望信息： ◼ I(s1,s2,……,sm)=－∑Pi log2(pi) (i=1..m) ◼ 其中，数据集为S，m为S的分类数目， Pi ◼ Ci为某分类标号，Pi为任意样本属于Ci的概率， si为分 类Ci上的样本数 ◼ 由A划分为子集的熵： ◼ E(A)= ∑j(|s1j|+ ……+|smj|)/|s| * I(s1j， ……，smj) ◼ A为属性，具有V个不同的取值 ◼ 信息增益：Gain(A)= I(s1,s2,……,sm) － E(A) | | | | S Si
训练集 age income student credit_rating buys_ computer <=30 high no fair no =30 high no excellent no 30...40 high no fair es 40 medium no fair yes >40 OW yesfair yes >40 low yes excellent no 31.40|ow yes excellent yes <=30 medium no fair no =30|ow yes fair yes >40 medium fair yes <=30medium yes excellent yes 31.40medium no excellent yes 31..40high es aIr es >40 medium no excellent no
9 训练集 age income student credit_rating buys_computer <=30 high n o fair n o <=30 high n o excellent n o 30…40 high n o fair yes >40 medium n o fair yes >40 low yes fair yes >40 low yes excellent n o 31…40 low yes excellent yes <=30 medium n o fair n o <=30 low yes fair yes >40 medium yes fair yes <=30 medium yes excellent yes 31…40 medium n o excellent yes 31…40 high yes fair yes >40 medium n o excellent n o
使用信息增益进行属性选择 Class p: buys_computer =yes e(age) 1(2,3)又 Class n: buys_computer ="no q(40) 5 I(p,n)=I(9,5)=0.940 (3,2)=0.9 0.694 Compute the entropy for age Hence Gain(age)=/(p, n)-e(age) age pi (p,n) <=30230.971 30..40400 Similarly >40 320.971 Gain(income)=0.029 Gain(student)=0.151 Gain(credit rating)=0.048
10 使用信息增益进行属性选择 Class P: buys_computer = “yes” Class N: buys_computer = “no” I(p, n) = I(9, 5) =0.940 Compute the entropy for age: Hence Similarly age pi ni I(pi , ni ) <=30 2 3 0.971 30…40 4 0 0 >40 3 2 0.971 (3,2) 0.971 14 5 (4,0) 14 4 (2,3) 14 5 ( ) + = = + I E age I I ( _ ) 0.048 ( ) 0.151 ( ) 0.029 = = = Gain credit rating Gain student Gain income Gain(age) = I( p,n) − E(age) 0.694