计算gini指数.ppt

处理缺失属性值 缺失值对决策树构造产生影响: 影响不纯度如何计算 影响带有缺失值的记录如何分配到子结点中 影响一个测试实例如何被分类 计算不纯度 根据偿还借款属性分裂: Entropy(偿还借款=Yes) = 0 Entropy(偿还借款=No)  = -(2/6)log(2/6) – (4/6)log(4/6) = 0.9183 Entropy(Children)  = 0.3 (0) + 0.6 (0.9183) = 0.551 Gain = 0.9 ? (0.8813 – 0.551) = 0.3303 缺失值 分裂前: Entropy(Parent)  = -0.3 log(0.3)-(0.7)log(0.7) = 0.8813 分配记录 偿还 借款 Yes No 偿还 借款 Yes No 偿还借款=Yes 的概率 为 3/9 偿还借款=No 的概率 为 6/9 将该记录分配到左子结点的权重（概率）为 3/9，分配到右子结点的权重（概率）为 6/9 对实例进行分类 偿还借款 MarSt TaxInc YES NO NO NO Yes No Married Single, Divorced 80K 80K 已婚 单身 离异 合计 Class=No 3 1 0 4 Class=Yes 6/9 1 1 2.67 Total 3.67 2 1 6.67 新纪录: 婚否 = 已婚 的概率为 3.67/6.67 婚否 ={单身,离异} 的概率为 3/6.67 对应于Refund=No 问 答 * * 计算GINI指数的例子 P(C1) = 0/6 = 0 P(C2) = 6/6 = 1 Gini = 1 – P(C1)2 – P(C2)2 = 1 – 0 – 1 = 0 P(C1) = 1/6 P(C2) = 5/6 Gini = 1 – (1/6)2 – (5/6)2 = 0.278 P(C1) = 2/6 P(C2) = 4/6 Gini = 1 – (2/6)2 – (4/6)2 = 0.444 基于GINI指数的分裂 在CART, SLIQ, SPRINT等算法中使用 当一个结点p分裂为k个部分时，该分裂的质量定义为： 其中, ni 是子结点i中的记录数目, n 是结点p中的记录数目. 二元属性: 计算GINI指数 分裂为两个部分,假设有两种方法将数据划分成较小的子集 B? Yes No Node N1 Node N2 A属性划分: Gini(N1) = 1 – (4/7)2 – (3/7)2 = 0.49 Gini(N2) = 1 – (2/5)2 – (3/5)2 = 0.48 Gini(Children) = 7/12 * 0.49 +  5/12 * 0.48= 0.49 N1 N2 C1 1 5 C2 4 2 Gini=0.371 A? Yes No Node N1 Node N2 B属性划分 B属性划分: Gini(N1) = 1 – (1/5)2 – (4/5)2 = 0.32 Gini(N2) = 1 – (5/7)2 – (2/7)2 = 0.41 Gini(Children) = 5/12 * 0.32 +  7/12 * 0.41= 0.371 结论：属性B具有更小的Gini指标，比属性A更可取。 N1 N2 C1 4 2 C2 3 3 Gini=0.49 A属性划分 分类属性: 计算Gini指数 对于每个值，统计每类记录的个数 可以使用计数矩阵来辅助理解 多路分裂 二路分裂 (需要确定最佳方案) 连续属性: 计算Gini指数 选取一个值，做二元决策 对于分裂值，有多种选择 取决于不同的值的个数 穷举法：将N个记录中所有的属性值都作为候选划分点 每个分裂值对应了一个计数矩阵 对于值v，统计每个类在两个部分A v 和 A ? v的计数 选择最佳v的直观方法 对于每个值v，扫描一次数据库，构造计数矩阵，计算Gini指数 计算代价昂贵，效率太低，每个候选划分点计算Gini指标需要O(N)次操作，N个候选，总的计算复杂度为O(N2) 连续属性: 计算Gini指数... 较高效的计算方法: 对于每个属性, 将属性值排序,从两个相邻的排过序的属性值中选择中间值作为候选划分 依次扫描这些值，每次扫描一个值后, 更新计数矩阵，并计算Gini指数 选择对应了最小的Gini指数的分裂位置 分裂位置 排序后的属性值 进一步优化该过程 仅考虑位于具有不同类标号的两个相邻记录之间的候选划分点 基于信息论的分裂准则 给定结点t