决策树讲义讲解.ppt

决策树的数据准备 姓名 年龄 收入 学生 信誉 电话 地址 邮编 买计算机 张三 23 4000 是 良 281-322-0328 2714 Ave. M 77388 买 李四 34 2800 否 优 713-239-7830 5606 Holly Cr 78766 买 王二 70 1900 否 优 281-242-3222 2000 Bell Blvd. 70244 不买 赵五 18 900 是 良 281-550-0544 100 Main Street 70244 买 刘兰 34 2500 否 优 713-239-7430 606 Holly Ct 78566 买 杨俊 27 8900 否 优 281-355-7990 233 Rice Blvd. 70388 不买 张毅 38 9500 否 优 281-556-0544 399 Sugar Rd. 78244 买 。。。 。。 。。。 原始表 决策树算法 计数 年龄 收入 学生 信誉 归类：买计算机？ 64 青 高 否 良 不买 64 青 高 否 优 不买 128 中 高 否 良 买 60 老 中 否 良 买 64 老 低 是 良 买 64 老 低 是 优 不买 64 中 低 是 优 买 128 青 中 否 良 不买 64 青 低 是 良 买 。。。 整理后的数据表 决策树的数据准备 Data cleaning 删除/减少noise， 补填missing values Data transformation 数据标准化（data normalization） 数据归纳（generalize data to higher-level concepts using concept hierarchies） 例如：年龄归纳为老、中、青三类 控制每个属性的可能值不超过七种 （最好不超过五种） Relevance analysis 对于与问题无关的属性：删 对于属性的可能值大于七种 又不能归纳的属性：删 决策树算法 决策树的数据准备 决策树算法 处理连续属性值 决策树算法比较适合处理离散数值的属性。实际应用中 属性是连续的或者离散的情况都比较常见。 在应用连续属性值时，在一个树结点可以将属性Ai的值 划分为几个区间。然后信息增益的计算就可以采用和离散值 处理一样的方法。原则上可以将Ai的属性划分为任意数目的 空间。C4.5中采用的是二元分割（Binary Split）。需要找出 一个合适的分割阈值。 参考C4.5算法 Top 10 algorithms in data mining Knowledge Information System 2008 14:1–37 决策树归纳的基本算法是贪心算法，它以自顶向下递归各个击破的方式构造决策树。 贪心算法：在每一步选择中都采取在当前状态下最好/优的选择。 在其生成过程中，分割方法即属性选择度量是关键。通过属性选择度量，选择出最好的将样本分类的属性。 根据分割方法的不同，决策树可以分为两类：基于信息论的方法（较有代表性的是ID3、C4.5算法等）和最小GINI指标方法（常用的有CART、SLIQ及SPRINT算法等）。 决策树算法 决策树算法 ID3算法小结 ID3算法是一种经典的决策树学习算法，由Quinlan于1979年 提出。ID3算法的基本思想是，以信息熵为度量，用于决策树节 点的属性选择，每次优先选取信息量最多的属性，亦即能使熵值 变为最小的属性，以构造一颗熵值下降最快的决策树，到叶子节 点处的熵值为0。此时，每个叶子节点对应的实例集中的实例属于 同一类。 决策树研究问题 理想的决策树有三种： (1)叶子结点数最少； (2)叶子结点深度最小； (3)叶子结点数最少且叶子结点深度最小。 然而，洪家荣等人已经证明了要找到这种最优的决策树是NP难 题。因此，决策树优化的目的就是要找到尽可能趋向于最优的 决策树。 * 决策树 主讲人：王孝润 江克州 孙竟豪 主要内容 决策树基本概念 决策树算法 决策树研究问题 决策树基本概念 决策树的优点 1、推理过程容易理解，决策推理过程可以表示成If Then形式； 2、推理过程完全依赖于属性变量的取值特点； 3、可自动忽略目标变量没有贡献的属性变量，也为判断属性 变量