分类决策树_id3算法(精华-理论加实例)

《分类决策树_id3算法(精华-理论加实例)》由会员分享，可在线阅读，更多相关《分类决策树_id3算法(精华-理论加实例)（83页珍藏版）》请在金锄头文库上搜索。

1、第 6 章 决策树,决策树基本概念,决策树算法,决策树研究问题,主要内容,决策树基本概念,决策树算法,决策树研究问题,决策树基本概念,关于分类问题,分类（Classification）任务就是通过学习获得一个目标函数 （Target Function）f, 将每个属性集x映射到一个预先定义好的类 标号y。,分类任务的输入数据是纪录的集合，每条记录也称为实例 或者样例。用元组(X,y)表示，其中，X 是属性集合，y是一个 特殊的属性，指出样例的类标号（也称为分类属性或者目标属性）,决策树基本概念,关于分类问题,X,y,分类与回归,分类目标属性y是离散的，回归目标属性y是连续的,决策树基本概念,解

2、决分类问题的一般方法,分类技术是一种根据输入数据集建立分类模型的系统方法。 分类技术一般是用一种学习算法确定分类模型，该模型可以很好 地拟合输入数据中类标号和属性集之间的联系。学习算法得到的 模型不仅要很好拟合输入数据，还要能够正确地预测未知样本的 类标号。因此，训练算法的主要目标就是要建立具有很好的泛化 能力模型，即建立能够准确地预测未知样本类标号的模型。 分类方法的实例包括：决策树分类法、基于规则的分类法、 神经网络、支持向量级、朴素贝叶斯分类方法等。,决策树基本概念,解决分类问题的一般方法,通过以上对分类问题一般方法的描述，可以看出分类问题 一般包括两个步骤： 1、模型构建（归纳） 通过

3、对训练集合的归纳，建立分类模型。 2、预测应用（推论） 根据建立的分类模型，对测试集合进行测试。,决策树基本概念,解决分类问题的一般方法,学习算法,学习模型,模型,应用模型,训练集（类标号已知）,检验集（类标号未知）,归纳,推论,决策树基本概念,决策树,决策树是一种典型的分类方法，首先对数据进行处理，利用 归纳算法生成可读的规则和决策树，然后使用决策对新数据进行 分析。本质上决策树是通过一系列规则对数据进行分类的过程。,决策树基本概念,决策树的优点 1、推理过程容易理解，决策推理过程可以表示成If Then形式； 2、推理过程完全依赖于属性变量的取值特点； 3、可自动忽略目标变量没有贡献的属性

4、变量，也为判断属性 变量的重要性，减少变量的数目提供参考。,决策树基本概念,关于归纳学习(1),决策树技术发现数据模式和规则的核心是归纳算法。 归纳是从特殊到一般的过程。归纳推理从若干个事实中表 征出的特征、特性和属性中，通过比较、总结、概括而得出一 个规律性的结论。 归纳推理试图从对象的一部分或整体的特定的观察中获得 一个完备且正确的描述。即从特殊事实到普遍性规律的结论。 归纳对于认识的发展和完善具有重要的意义。人类知识的增长 主要来源于归纳学习。,决策树基本概念,关于归纳学习(2),归纳学习的过程就是寻找一般化描述的过程。这种一般性 描述能够解释给定的输入数据，并可以用来预测新的数据。 锐

5、角三角形内角和等于180度； 钝角三角形内角和等于180度； 三角形内角和 直角三角形内角和等于180度； 等于180度,已知三角形ABC，A角等于76度， B角等于89度，则其C角等于15度,归纳学习由于依赖于检验数据，因此又称为检验学习。归纳学习存在一个基本的假设： 任一假设如果能够在足够大的训练样本集中很好的逼近目标函数，则它也能在未见样本中很好地逼近目标函数。该假定是归纳学习的有效性的前提条件。,决策树基本概念,关于归纳学习(3),决策树基本概念,关于归纳学习(4),归纳过程就是在描述空间中进行搜索的过程。归纳可分为自 顶向下，自底向上和双向搜索三种方式。 自底向上法一次处理一个输入对

6、象。将描述逐步一般化。直 到最终的一般化描述。 自顶向下法对可能的一般性描述集进行搜索，试图找到一些 满足一定要求的最优的描述。,决策树基本概念,从机器学习看分类及归纳推理等问题（1）,从特殊的训练样例中归纳出一般函数是机器学习的中心问题； 从训练样例中进行学习通常被视为归纳推理。每个例子都是一个 对偶（序偶）（x, f(x)），对每个输入的x，都有确定的输出f(x)。 学习过程将产生对目标函数f的不同逼近。F的每一个逼近都 叫做一个假设。假设需要以某种形式表示。例如，y=ax+b。通过 调整假设的表示，学习过程将产生出假设的不同变形。在表示中 通常需要修改参数（如a, b）。,决策树基本概念

7、,从机器学习看分类及归纳推理等问题（2）,从这些不同的变形中选择最佳的假设（或者说权值集合）。 一般方法如定义为使训练值与假设值 预测出的值之间的误差平方 和E最小为最佳。,学习是在假设空间上的一个搜索。概念学习也可以看作是一 个搜索问题的过程。它在预定义的假设空间中搜索假设，使其与 训练样例有最佳的拟合度。多数情况下，为了高效地搜索，可以 利用假设空间中一种自然形成的结构，即一般到特殊的偏序关系。,决策树基本概念,从机器学习看分类及归纳推理等问题（3）,分类模型的性能根据模型正确和错误预测也可以根据的检验记录计数 进行评估。这些计数存储在混同矩阵（Confusion Matrix）的表格中，

8、二元 分类问题混淆矩阵如下：,实际 的类,类1,f11,类0,f01,f10,f00,类1,类0,预测的类,准确率=正确的预测数/预测总数=（f11+f00）/(f11+f01+f10+f00),差错率=错误的预测数/预测总数=（f10+f01）/(f11+f01+f10+f00),归纳学习假设 机器学习的任务是在整个实例集合X上确定与目标概念c相同 的假设 。一般H表示所有可能假设。H中每个假设h表 示X上定义的布尔函数。由于对c仅有的信息只是它在训练样例上 的值，因此归纳学习最多只能保证输出的假设能与训练样例相拟 合。若没有更多的信息，只能假定对于未见实例最好的假设就是 训练数据最佳拟合的

9、假设。 定义 归纳学习假设：任一假设如果在足够大的训练样例中很 好地逼近目标函数，则它也能在未见实例中很好地逼近目标函数。 （Function Approximation）。,决策树基本概念,从机器学习看分类及归纳推理等问题（4）,主要内容,决策树基本概念,决策树算法,决策树研究问题,决策树算法,与决策树相关的重要算法,1、Hunt,Marin和Stone 于1966年研制的CLS学习系统，用于学习单个概 念。 2、1979年, J.R. Quinlan 给出ID3算法，并在1983年和1986年对ID3 进行了总结和简化，使其成为决策树学习算法的典型。 3、Schlimmer 和Fisher

10、 于1986年对ID3进行改造，在每个可能的决策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。 4、1988年，Utgoff 在ID4基础上提出了ID5学习算法，进一步提高了效率。 1993年，Quinlan 进一步发展了ID3算法，改进成C4.5算法。 5、另一类决策树算法为CART，与C4.5不同的是，CART的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例。,CLS, ID3，C4.5，CART,决策树算法,假定公司收集了左表数据，那么对于任意给定的客人（测试样例），你能帮助公司将这位客人归类吗？ 即：你能预测这位客人是属于“买”计算机的那一类

11、，还是属于“不买”计算机的那一类？ 又：你需要多少有关这位客人的信息才能回答这个问题？,决策树的用途,谁在买计算机？,年龄？,学生？,信誉？,青,中,老,否,是,优,良,决策树的用途,决策树算法,谁在买计算机？,年龄？,学生？,信誉？,青,中,老,否,是,优,良,决策树的用途,决策树算法,决策树算法,决策树的表示,决策树的基本组成部分：决策结点、分支和叶子。,年龄？,学生？,信誉？,青,中,老,否,是,优,良,决策树中最上面的结点称为根结点。 是整个决策树的开始。每个分支是一 个新的决策结点，或者是树的叶子。 每个决策结点代表一个问题或者决策. 通常对应待分类对象的属性。 每个叶结点代表一种可

12、能的分类结果,在沿着决策树从上到下的遍历过程中，在每个结点都有一个 测试。对每个结点上问题的不同测试输出导致不同的分枝，最后 会达到一个叶子结点。这一过程就是利用决策树进行分类的过程， 利用若干个变量来判断属性的类别,决策树算法,CLS（Concept Learning System）算法,CLS算法是早期的决策树学习算法。它是许多决策树学习算法 的基础。 CLS基本思想 从一棵空决策树开始，选择某一属性（分类属性）作为测试 属性。该测试属性对应决策树中的决策结点。根据该属性的值的 不同，可将训练样本分成相应的子集，如果该子集为空，或该子 集中的样本属于同一个类，则该子集为叶结点，否则该子集对

13、应 于决策树的内部结点，即测试结点，需要选择一个新的分类属性 对该子集进行划分，直到所有的子集都为空或者属于同一类。,决策树算法,CLS算法,决策树算法,CLS算法-决策树的构建,眼睛颜色,1，6,2，4，8,3，5，7,黑色,兰色,灰色,不属于同一类，非叶结点,眼睛颜色,头发颜色,头发颜色,头发颜色,黑色,兰色,灰色,决策树算法,CLS算法,黄种人1,混血6,白种人2,白种人4,混血8,白种人3,白种人5,混血7,黑色,金色,金色,红色,黑色,金色,红色,黑色,决策树算法,CLS算法,1 生成一颗空决策树和一张训练样本属性集; 2 若训练样本集T 中所有的样本都属于同一类, 则生成结点T ,

14、 并终止学习算法;否则 3 根据某种策略从训练样本属性表中选择属性 A 作为测试属性, 生成测试结点A 4 若A的取值为v1,v2,vm, 则根据A 的取值的 不同,将T 划分成 m个子集T1,T2,Tm; 5 从训练样本属性表中删除属性A; 6 转步骤2, 对每个子集递归调用CLS;,CLS算法问题,在步骤3中，根据某种策略从训练样本属性表中选择属性A作为测试属性。没有规定采用何种测试属性。实践表明，测试属性集的组成以及测试属性的先后对决策树的学习具有举足轻重的影响。 举例加以说明，下表为调查学生膳食结构和缺钙情况的关系，其中1表示包含食物，0表示不包含,决策树算法,CLS算法问题,决策树算

15、法,学生膳食结构和缺钙调查表,CLS算法问题,决策树算法,采用不同的测试属性及其先后顺序将会生成不同的决策树,鸡肉,猪肉,猪肉,牛肉,牛肉,牛肉,不缺钙（2）,缺钙（3，6）,不缺钙（4）,不缺钙（10）,缺钙（5）,不缺钙（1）,鱼肉,缺钙（5）,不缺钙（7，9）,是,否,是,否,否,否,否,否,否,是,是,是,是,是,牛奶,不缺钙 （1，2，4， 7，9，10）,缺钙 （3，5，6，8）,CLS算法问题,决策树算法,在上例中，显然生成的两种决策树的复杂性和分类意义相差 很大由此可见，选择测试属性是决策树学习算法中需要研究的重 要课题。,ID3,决策树算法,ID3算法主要针对属性选择问题。是

16、决策树学习方法中最 具影响和最为典型的算法。 该方法使用信息增益度选择测试属性。 当获取信息时，将不确定的内容转为确定的内容，因此信 息伴着不确定性。 从直觉上讲，小概率事件比大概率事件包含的信息量大。 如果某件事情是“百年一见”则肯定比“习以为常”的事件包含的 信息量大。 如何度量信息量的大小？,ID3 信息量大小的度量,决策树算法,Shannon1948年提出的信息论理论。事件ai的信息量I（ ai ）可 如下度量：,其中p(ai)表示事件ai发生的概率。 假设有n个互不相容的事件a1,a2,a3,.,an,它们中有且仅有一个 发生，则其平均的信息量可如下度量：,ID3 信息量大小的度量,决策树算法,上式，对数底数可以为任何数，不同的取值对应了熵的不同单位。 通常取2，并规定当p(ai)=0时