《[精选]第二章决策树(ID3分类算法)》由会员分享，可在线阅读，更多相关《[精选]第二章决策树(ID3分类算法)（45页珍藏版）》请在金锄头文库上搜索。
1、研究生学院,性别 年龄 种族 家庭人口 家庭收入 申请该校原因 家庭住址 ,例2：Wal-Mart的销售与供应商 关心哪一种产品畅销,第二章 决策树Decision Tree （ID3分类算法）,产品名称 产品型号 产品价格 生产厂家 生产国家 出售地点 出售日期,例1：学校录取部门的困扰：新生录取以后会不会来报到？,一、分类问题的提出,为解决上述问题必须进行分类 分类是数据挖掘中的一种主要分析手段 分类的任务是对数据集进行学习并构造一个拥有预测功能的分类模型，用于预测未知样本的类标号，如： 根据瓦斯状态、开采技术条件、煤层赋存状况等对危险进行分类评估 根据核磁共振的结果区分肿瘤是恶性还是良性
2、的 根据星系的形状对它们进行分类 划分出交易是合法或欺诈 将新闻分类金融、天气、娱乐体育等,主要分类方法 决策树分类方法 贝叶斯分类方法 K-最近邻分类方法 神经网络分类方法 支持向量机 组合学习方法 不平衡数据分类问题 分类模型的评价 回归方法,研究生学院,举例说明分类任务,归纳,推论,模型,学习算法,研究生学院,有房,婚姻状况,年收入,是,否,否,否,是,没有,已婚,单身, 离婚, 80K, 80K,极快的属性,训练数据,模型: 决策树,研究生学院,婚姻状况,有房,年收入,是,否,否,是,没有,已婚,单身, 离异, 80K, 80K,测试数据,申请模型到测试数据,研究生学院,开始从树.的根
3、,测试数据,研究生学院,测试数据,开始从树.的根,研究生学院,测试数据,开始从树.的根,研究生学院,测试数据,开始从树.的根,研究生学院,测试数据,开始从树.的根,研究生学院,测试数据,开始从树.的根,研究生学院,归纳,推论,模型,学习算法,研究生学院,有房,婚姻状况,年收入,是,否,否,否,是,没有,已婚,单身, 离婚, 80K, 80K,极快的属性,训练数据,模型: 决策树,决策树的例子,研究生学院,婚姻状况,有房,年收入,是,否,否,是,没有,已婚,单身, 离异, 80K, 80K,决策树的例子,研究生学院,归纳,推论,模型,学习算法,研究生学院,测试数据,开始从树.的根,申请模型到测试
4、数据,研究生学院,测试数据,开始从树.的根,研究生学院,测试数据,开始从树.的根,研究生学院,测试数据,开始从树.的根,研究生学院,测试数据,开始从树.的根,研究生学院,测试数据,开始从树.的根,举例说明分类任务,研究生学院,归纳,推论,模型,学习算法,决策树在构建过程中需重点解决2个问题： (1)如何选择合适的属性作为决策树的节点去划分训练样本； (2)如何在适当位置停止划分过程，从而得到大小合适的决策树。 虽然可以采用任何一个属性对数据集进行划分，但最后形成的决策树会差异很大。需要寻找合适的属性选择方法。 属性选择是决策树算法中重要的步骤，常见的属性选择标准包括信息增益(informati
5、on gain)和Gini系数。 信息增益是决策树常用的分枝准则,在树的每个结点上选择具有最高信息增益的属性作为当前结点的划分属性。 Gini系数是一种不纯度函数，用来度量数据集的数据关于类的纯度。,二、DI3分类算法,1.ID3分类算法提出： 由Quinlan于1986年提出，它使用信息增益(information gain)作为属性的选择标准。 首先检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一个类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。 2.ID3分类算法
6、相关的基本概念： 1）信息熵 2）信息增益,熵(entropy,也称信息熵)用来度量一个属性的信息量。 假定S为训练集，S的目标属性C具有m个可能的类标号值，C=C1,C2,Cm，假定训练集S中，Ci在所有样本中出现的频率为 (i=1,2,3,m)，则该训练集S所包含的信息熵定义为： 熵越小表示样本对目标属性的分布越纯，反之熵越大表示样本对目标属性分布越混乱。,信息熵例题演示考虑数据集weather如下, 求weather数据集关于目标属性play ball的熵。,目标属性,解答：令weather数据集为S，其中有14个样本,目标属性play ball有2个值C1=yes, C2=no。14个
7、样本的分布为： 9个样本的类标号取值为yes，5个样本的类标号取值为No。C1=yes在所有样本S中出现的概率为9/14，C2=no在所有样本S中出现的概率为5/14。 因此数据集S的熵为：,信息增益：是划分前样本数据集的不纯程度(熵)和划分后样本数据集的不纯程度(熵)的差值。 假设划分前样本数据集为S,并用属性A来划分样本集S，则按属性A划分S的信息增益Gain(S,A)为样本集S的熵减去按属性A划分S后的样本子集的熵： 按属性A划分S后的样本子集的熵定义如下：假定属性A有k个不同的取值，从而将S划分为k个样本子集S1,S2,Sk，则按属性A划分S后的样本子集的信息熵为: 其中|Si|(i,
8、=1,2,k)为样本子集Si中包含的样本数，|S|为样本集S中包含的样本数。信息增益越大，说明使用属性A划分后的样本子集越纯，越有利于分类。,以数据集weather为例，设该数据集为S，假定用属性wind来划分S，求S对属性wind的信息增益。,解：(1)首先由前例计算得到数据集S的熵值为0.94； (2)属性wind有2个可能的取值weak,strong，它将S划分为2个子集：S1,S2,S1为wind属性取值为weak的样本子集，共有8个样本；S2为wind属性取值为strong的样本子集，共有6个样本；下面分别计算样本子集S1和S2的熵。 对样本子集S1，play ball=yes的有6
9、个样本，play ball=no的有2个样本，则：,对样本子集S2，play ball=yes的有3个样本，play ball=no的有3个样本，则：,利用属性wind划分S后的熵为： 按属性wind划分数据集S所得的信息增益值为：,以weather数据集为例，讲解ID3的建立过程。,数据集具有属性：outlook, temperature, humidity, wind. outlook = sunny, overcast, rain temperature = hot, mild, cool humidity = high, normal wind = weak, strong ,首先计算
10、总数据集S对所有属性的信息增益，寻找根节点的最佳分裂属性: Gain(S, outlook) = 0.246 Gain(S, temperature) = 0.029 Gain(S, humidity) = 0.152 Gain(S, wind) = 0.049 显然，这里outlook属性具有最高信息增益值，因此将它选为根结点.,以outlook做为根结点，继续往下： 思想是，以outlook的可能取值建立分支，对每个分支递归建立子树。 因为outlook有3个可能值,因此对根结点建立3个分支sunny, overcast, rain. 那么，哪个属性用来最佳划分根结点的Sunny分支？ov
11、ercast分支？Rain分支？,首先对outlook的sunny分支建立子树。 找出数据集中outlook = sunny的样本子集Soutlook=sunny，然后依次计算剩下三个属性对该样本子集Ssunny划分后的信息增益： Gain(Ssunny, humidity) = 0.971 Gain(Ssunny, temperature) = 0.571 Gain(Ssunny, wind) = 0.371,显然humidity具有最高信息增益值，因此它被选为outlook结点下sunny分支下的决策结点。,采用同样的方法，依次对outlook的overcast分支、rain分支建立子树，
12、最后得到一棵可以预测类标号未知的样本的决策树。,ID3决策树对未知样本进行预测 下面利用决策树对类标号未知的样本X进行预测： X=rain, hot, normal, weak, ?,ID3算法总结 ID3算法是所有可能的决策树空间中一种自顶向下、贪婪的搜索方法。 ID3搜索的假设空间是可能的决策树的集合，搜索目的是构造与训练数据一致的一棵决策树，搜索策略是爬山法，在构造决策树时从简单到复杂，用信息熵作为爬山法的评价函数。 ID3算法的核心是在决策树各级结点上选择属性，用信息增益作为属性选择的标准，使得在每个非叶节点进行测试时能获得关于被测数据最大的类别信息，使得该属性将数据集分成子集后，系统
13、的熵值最小。,优点： 理论清晰，方法简单，学习能力较强。 缺点： (1)算法只能处理分类属性数据，无法处理连续型数据； (2)算法对测试属性的每个取值相应产生一个分支，且划分相应的数据样本集,这样的划分会导致产生许多小的子集。随着子集被划分得越来越小，划分过程将会由于子集规模过小所造成的统计特征不充分而停止； (3)ID3算法中使用信息增益作为决策树节点属性选择的标准，由于信息增益在类别值多的属性上计算结果大于类别值少的属性上计算结果，这将导致决策树算法偏向选择具有较多分枝的属性，因而可能导致过度拟合。在极端的情况下，如果某个属性对于训练集中的每个元组都有唯一的一个值，则认为该属性是最好的，这
14、是因为对于每个划分都只有一个元组(因此也是一类)。,优点： 理论清晰，方法简单，学习能力较强。 缺点： (1)算法只能处理分类属性数据，无法处理连续型数据； (2)算法对测试属性的每个取值相应产生一个分支，且划分相应的数据样本集,这样的划分会导致产生许多小的子集。随着子集被划分得越来越小，划分过程将会由于子集规模过小所造成的统计特征不充分而停止； (3)ID3算法中使用信息增益作为决策树节点属性选择的标准，由于信息增益在类别值多的属性上计算结果大于类别值少的属性上计算结果，这将导致决策树算法偏向选择具有较多分枝的属性，因而可能导致过度拟合。在极端的情况下，如果某个属性对于训练集中的每个元组都有
15、唯一的一个值，则认为该属性是最好的，这是因为对于每个划分都只有一个元组(因此也是一类)。,C4.5 基于ID3算法中存在的不足，Quinlan于1993年对其做出改进，提出了改进的决策树分类算法C4.5，该算法继承了ID3算法的优点，并在以下几个方面对ID3算法进行了改进： (1)能够处理连续型属性数据和离散型属性数据； (2)能够处理具有缺失值的数据； (3)使用信息增益率作为决策树的属性选择标准； (4)对生成的树进行剪枝处理，以获取简略的决策树； (5)从决策树到规则的自动产生。 CART算法 CART(Classification and Regression Tree)算法，由美国斯坦福大学和加州大学伯克利分校的Breiman等人于1984年提出。,演讲完毕，谢谢观看！,
