ch10决策树
Ch 10. 决策树
特征类型 数值数据( numerical data) 例:{1.2,4.5,33} ·模式间可以计算距离度量 ·基于度量的模式分类方法 标称数据( nominal data) 例:{红色,有光泽,甜,小} ·模式间没有距离的概念 ·非度量方法
特征类型 • 数值数据（numerical data） • 例：{1.2, 4.5, 3.3} • 模式间可以计算距离度量 • 基于度量的模式分类方法 • 标称数据 （nominal data） • 例：{红色，有光泽，甜，小} • 模式间没有距离的概念 • 非度量方法
决策树 ·什么是决策树? 决策树是一种类似流程图的树形结构,每个内部节点表 示一个测试(查询),该节点的每个分支表示该测试的 个结果,每个叶节点表示一个类别 决策树的构成 根节点(root) 分支( branch) 叶节点(leaf)
决策树 • 什么是决策树？ • 决策树是一种类似流程图的树形结构，每个内部节点表 示一个测试（查询），该节点的每个分支表示该测试的 一个结果，每个叶节点表示一个类别 • 决策树的构成 • 根节点（root） • 分支（branch） • 叶节点（leaf）
决策树 root Color? level o green red vellow Size? Shape? Size? level bis round thin medium Watermelon Apple grape Size?) Banana( Apple (taste? level 2 g sweet soul Grapefruit Lemon Cherry Grape level 3
决策树
决策树 ·决策树分类过程 ·从根节点开始,首先对某一属性的取值提问 Color? ·与根节点相连的不同分支,对应这个属性的不同取值 ° green;yeow;red; ·根据不同的回答,转向相应的分支 green ·在新到达的节点处做同样的分支判断 Size?-big ·这一过程持续,直到到达某个叶节点,输出该叶节点的 类别标记 Watermelon
决策树 • 决策树分类过程 • 从根节点开始，首先对某一属性的取值提问 • Color? • 与根节点相连的不同分支，对应这个属性的不同取值 • green; yellow;red; • 根据不同的回答，转向相应的分支 • green • 在新到达的节点处做同样的分支判断 • Size? – big. • 这一过程持续，直到到达某个叶节点，输出该叶节点的 类别标记 • Watermelon
决策树 ·决策树的判决面 x2 R 尺1 R
决策树 • 决策树的判决面
决策树 ·决策树的优势 ·语义可表示性 ·从根节点到叶节点表示为合取式 (颜色=黄)AND(形状=细长)□香蕉 ·利用合取式和析取式获得某个类别的明确描述 ·苹果=(绿色AND中等大小)OR(红色AND中等大小) 分类速度快 ·只需一系列简单查询即可对模式的类别做出判断 可以很自然地嵌入专家的先验知识
决策树 • 决策树的优势 • 语义可表示性 • 从根节点到叶节点表示为合取式 • （颜色=黄）AND（形状=细长） 香蕉 • 利用合取式和析取式获得某个类别的明确描述 • 苹果=（绿色 AND 中等大小）OR（红色 AND 中等大小） • 分类速度快 • 只需一系列简单查询即可对模式的类别做出判断 • 可以很自然地嵌入专家的先验知识
决策树学习算法 ·决策树研究历史 第一个决策树算法称为cLs( Concept Learning System [E B Hunt, J. Marin, and P. T. Stone's book"Experiments in Induction"published by Academic Press in 19667 真正引发决策树研究热潮的算法是ID3 [J.R. Quinlan's paper in a book "Expert Systems in the Micro Electronic Age"edited by D. Michie, published by Edinburgh University Press in 1979 最流行的决策树算法c45 J.R. Quinlan's book"C4. 5: Programs for Machine Learning"published by Morgan Kaufmann in 19931
决策树学习算法 • 决策树研究历史 • 第一个决策树算法称为CLS (Concept Learning System) [E. B. Hunt, J. Marin, and P. T. Stone’s book “Experiments in Induction”published by Academic Press in 1966] • 真正引发决策树研究热潮的算法是ID3 [J. R. Quinlan’s paper in a book “Expert Systems in the Micro Electronic Age” edited by D. Michie, published by Edinburgh University Press in 1979] • 最流行的决策树算法C4.5 [J. R. Quinlan’s book “C4.5: Programs for Machine Learning” published by Morgan Kaufmann in 1993]
决策树学习算法 ·决策树研究历史 通用的决策树算法 CART (Classification and Regression Tree) [L. Breiman, J H. Friedman, R A. Olshen, and C J. Stone's book"Classification and Regression Trees"published by Wadsworth in 1984] ·基于决策树的集成学习算法:随机森林( Random Forests [L. Breiman's MLJ01 paper"Random Forests"'I
决策树学习算法 • 决策树研究历史 • 通用的决策树算法CART (Classification and Regression Tree) [L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone’s book “Classification and Regression Trees” published by Wadsworth in 1984] • 基于决策树的集成学习算法：随机森林 (Random Forests) [L. Breiman’s MLJ’01 paper “Random Forests”]
构造决策树 基本过程 从上到下,分而治之(dide-and- conquer),递归生 长 ·最初,所有的样本都在根节点 ·所有属性都是标称型的(如果是连续数值型的,则需要 预先离散化) ·所有样本根据每次选择出的属性递归的逐渐划分开来 选择出来的属性称为一个划分(sp|t)或测试(test)或查询 (query) 査询的选择基于启发式或者统计特征
构造决策树 • 基本过程 • 从上到下，分而治之（divide-and-conquer），递归生 长 • 最初，所有的样本都在根节点 • 所有属性都是标称型的（如果是连续数值型的，则需要 预先离散化） • 所有样本根据每次选择出的属性递归的逐渐划分开来 选择出来的属性称为一个划分（split）或测试（test）或查询 （query） • 查询的选择基于启发式或者统计特征