决策树ppt课件.ppt

文档介绍：Ch 10. 决策树
特征类型
数值数据(numerical data)
例:{, , }
模式间可以计算距离度量
基于度量的模式分类方法
标称数据(nominal data)
例:{红色,有光泽,甜,小}
模式间没有距离的概念
非度量方法
决策树
什么是决策树?
决策树是一种类似流程图的树形结构,每个内部节点表示一个测试(查询),该节点的每个分支表示该测试的一个结果,每个叶节点表示一个类别
决策树的构成
根节点(root)
分支(branch)
叶节点(leaf)
决策树
决策树
决策树分类过程
从根节点开始,首先对某一属性的取值提问
Color?
与根节点相连的不同分支,对应这个属性的不同取值
green; yellow; red;
根据不同的回答,转向相应的分支
green
在新到达的节点处做同样的分支判断
Size? – big.
这一过程持续,直到到达某个叶节点,输出该叶节点的类别标记
Watermelon
决策树学****算法
决策树研究历史
第一个决策树算法称为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]
[J. R. Quinlan’s book “: 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 MLJ’01 paper “Random Forests”]
构造决策树
基本过程
从上到下,分而治之(divide-and-conquer),递归生长
最初,所有的样本都在根节点
所有属性都是标称型的(如果是连续数值型的,则需要预先离散化)
所有样本根据每次选择出的属性递归的逐渐划分开来
选择出来的属性称为一个划分(split)或测试(test)或查询(query)
查询的选择基于启发式或者统计特征