分类基本原理与决策树.ppt

如何选择最优划分 划分前: 10 条记录是类 0, 10 条记录是类 1 哪一种测试条件是最优的? 贪婪方法: 选择纯度更高的结点来进行划分 需要表明划分后子女结点不纯性的度量: 高不纯性 低不纯性 如何选择最优划分 结点不纯性度量 Gini指标值 Entropy熵 Classification error 分类误差 寻找最优划分 计算划分前的不纯性度量值(P) 计算划分后的不纯性度量值(M) 计算每个子节点的不纯性度量 计算子节点的平均不纯性度量(M) 选择具有最大增益的属性作为属性测试条件也就是，具有划分后具有最小不纯性度量值的属性(M) Gain = P – M 寻找最优划分 B? Yes No Node N3 Node N4 A? Yes No Node N1 Node N2 划分前: P M11 M12 M21 M22 M1 M2 Gain = P – M1 vs P – M2 不纯性度量: GINI 结点t的 Gini 指标值的计算公式如下: (注意: p( j | t) 表示给的结点t中属于类别j的记录所占的比例). 最大值 (1 - 1/nc) ：当各个样本等可能的属于各个类别,意味着蕴含最少信息 最小值 (0.0) ：当所有记录都属于同一类别, 意味着蕴含最多信息 计算单个结点的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指标值 当结点p被划分为k个划分部分时(子结点) 其中, ni = 子结点i中的样本记录数目, n = 父节点p中的样本记录数目. 选择具有最小值的子结点加权平均Gini指标值的属性进行划分 CART, SLIQ, SPRINT决策树算法使用GINI指标值来进行划分 二元属性: 计算GINI指标值 划分为两个部分 需要进行加权平均，是因为: 寻求更大、更纯的划分. B? Yes No Node N1 Node N2 Gini(N1) = 1 – (5/6)2 – (1/6)2 = 0.278 Gini(N2) = 1 – (2/6)2 – (4/6)2 = 0.444 Gini(Children) = 6/12 * 0.278 +  6/12 * 0.444= 0.361 标称属性: 计算Gini指标值 对于每一个属性值, 计算数据集中每一个类别的样本数量 使用计数矩阵进行决策 多路划分 二元划分 (寻找最优划分) 连续属性: 计算Gini指标值 进行二元决策 有多个划分点可供选择 可能的划分点的数目 = 不同的属性值的数目 每一个划分点都有一个计数矩阵与之关联 每一个划分中不同类别样本的数目, A v 和 A ? v 选择最优v的简单方法 对于每一个候选v, 扫描数据库获得计数矩阵并计算相应的 Gini 指标值 缺点： 计算效率低下! 重复的工作. 连续属性: 计算Gini指标值 更高效的计算方式: 首先对某一属性值进行排序 从两个相邻的排过序的属性值中选择中间值作为候选划分点，计算其Gini指标值 重复这样的计算，直到算出所有后续的Gini指标值，最佳划分点对应于最小Gini指标值的点 划分点 排序后的值 不纯性度量: 熵Entropy 结点t的熵Entropy的计算公式如下: (注意: p( j | t) 表示给的结点t中属于类别j的记录所占的比例). 最大值(log nc) ：当各个样本等可能的属于各个类别,意味着蕴含最少信息 最小值 (0.0) ：当所有记录都属于同一类别, 意味着蕴含最多信息 计算单个结点的熵Entropy P(C1) = 0/6 = 0 P(C2) = 6/6 = 1 Entropy = – 0 log 0 – 1 log 1 = – 0 – 0 = 0 P(C1) = 1/6 P(C2) = 5/6 Entropy = – (1/6) log2 (1/6) – (5/6) log2 (1/6) = 0.65 P(C1) = 2/6 P(C2) = 4/6 Entropy = – (2/6) log2 (2/6) – (4/6) log2 (4/6) =