第二章决策树(ID3分类算法)

@copyrightbyChunyouDong研究生学院性别年龄种族家庭人口家庭收入申请该校原因家庭住址……例2：Wal-Mart的销售与供应商关心哪一种产品畅销第二章决策树DecisionTree（ID3分类算法）产品名称产品型号产品价格生产厂家生产国家出售地点出售日期例1：学校录取部门的困扰：新生录取以后会不会来报到？一、分类问题的提出@copyrightbyChunyouDong–为解决上述问题必须进行分类–分类是数据挖掘中的一种主要分析手段–分类的任务是对数据集进行学习并构造一个拥有预测功能的分类模型，用于预测未知样本的类标号，如：•根据瓦斯状态、开采技术条件、煤层赋存状况等对危险进行分类评估•根据核磁共振的结果区分肿瘤是恶性还是良性的•根据星系的形状对它们进行分类•划分出交易是合法或欺诈•将新闻分类金融、天气、娱乐体育等•主要分类方法•决策树分类方法•贝叶斯分类方法•K-最近邻分类方法•神经网络分类方法•支持向量机•组合学习方法•不平衡数据分类问题•分类模型的评价•回归方法@copyrightbyChunyouDong研究生学院举例说明分类任务应用模型l归纳推论学习模型模型Tid有房者婚姻状况年收入拖欠贷款1是单身125K否2否已婚100K否3否单身70K否4是已婚120K否5否离异95K是6否已婚60K否7是离异220K否8否单身85K是9否已婚75K否10否单身90K是10Tid有房者婚姻状况2年收入拖欠贷款11否单身l55K?12是已婚80K?13是离异110K?14否单身95K?15否已婚67K?10学习算法@copyrightbyChunyouDong研究生学院有房婚姻状况年收入是否否否是没有已婚单身,离婚80K80K极快的属性训练数据模型:决策树Tid有房者婚姻状况年收入拖欠贷款1是单身125K否2否已婚100K否3否单身70K否4是已婚120K否5否离异95K是6否已婚60K否7是离异220K否8否单身85K是9否已婚75K否10否单身90K是10@copyrightbyChunyouDong研究生学院婚姻状况有房年收入是否否否是没有已婚单身,离异80K80KTid有房者婚姻状况年收入拖欠贷款1是单身125K否2否已婚100K否3否单身70K否4是已婚120K否5否离异95K是6否已婚60K否7是离异220K否8否单身85K是9否已婚75K否10否单身90K是10有房婚姻状况年收入拖欠贷款否已婚80K?10测试数据申请模型到测试数据@copyrightbyChunyouDong研究生学院有房婚姻年收入是否否否是否已婚单身、离婚80K80K开始从树.的根有房婚姻状况年收入拖欠贷款否已婚80K?10测试数据@copyrightbyChunyouDong研究生学院有房婚姻年收入是否否否是否已婚单身、离婚80K80K有房婚姻状况年收入拖欠贷款否已婚80K?10测试数据开始从树.的根@copyrightbyChunyouDong研究生学院有房婚姻年收入是否否否是否已婚单身、离婚80K80K有房婚姻状况年收入拖欠贷款否已婚80K?10测试数据开始从树.的根@copyrightbyChunyouDong研究生学院有房婚姻年收入是否否否是否已婚单身、离婚80K80K有房婚姻状况年收入拖欠贷款否已婚80K?10测试数据开始从树.的根@copyrightbyChunyouDong研究生学院有房婚姻年收入是否否否是否已婚单身、离婚80K80K有房婚姻状况年收入拖欠贷款否已婚80K?10测试数据开始从树.的根@copyrightbyChunyouDong研究生学院有房婚姻年收入是否否否是否已婚单身、离婚80K80K有房婚姻状况年收入拖欠贷款否已婚80K?10测试数据开始从树.的根@copyrightbyChunyouDong研究生学院应用模型l归纳推论学习模型模型Tid有房者婚姻状况年收入拖欠贷款1是单身125K否2否已婚100K否3否单身70K否4是已婚120K否5否离异95K是6否已婚60K否7是离异220K否8否单身85K是9否已婚75K否10否单身90K是10Tid有房者婚姻状况2年收入拖欠贷款11否单身l55K?12是已婚80K?13是离异110K?14否单身95K?15否已婚67K?10学习算法@copyrightbyChunyouDong研究生学院有房婚姻状况年收入是否否否是没有已婚单身,离婚80K80K极快的属性训练数据模型:决策树Tid有房者婚姻状况年收入拖欠贷款1是单身125K否2否已婚100K否3否单身70K否4是已婚120K否5否离异95K是6否已婚60K否7是离异220K否8否单身85K是9否已婚75K否10否单身90K是10决策树的例子@copyrightbyChunyouDong研究生学院婚姻状况有房年收入是否否否是没有已婚单身,离异80K80KTid有房者婚姻状况年收入拖欠贷款1是单身125K否2否已婚100K否3否单身70K否4是已婚120K否5否离异95K是6否已婚60K否7是离异220K否8否单身85K是9否已婚75K否10否单身90K是10决策树的例子@copyrightbyChunyouDong研究生学院应用模型l归纳推论学习模型模型Tid有房者婚姻状况年收入拖欠贷款1是单身125K否2否已婚100K否3否单身70K否4是已婚120K否5否离异95K是6否已婚60K否7是离异220K否8否单身85K是9否已婚75K否10否单身90K是10Tid有房者婚姻状况2年收入拖欠贷款11否单身l55K?12是已婚80K?13是离异110K?14否单身95K?15否已婚67K?10学习算法@copyrightbyChunyouDong研究生学院有房婚姻年收入是否否否是否已婚单身、离婚80K80K有房婚姻状况年收入拖欠贷款否已婚80K?10测试数据开始从树.的根@copyrightbyChunyouDong申请模型到测试数据研究生学院有房婚姻年收入是否否否是否已婚单身、离婚80K80K有房婚姻状况年收入拖欠贷款否已婚80K?10测试数据开始从树.的根@copyrightbyChunyouDong研究生学院有房婚姻年收入是否否否是否已婚单身、离婚80K80K有房婚姻状况年收入拖欠贷款否已婚80K?10测试数据开始从树.的根@copyrightbyChunyouDong研究生学院有房婚姻年收入是否否否是否已婚单身、离婚80K80K有房婚姻状况年收入拖欠贷款否已婚80K?10测试数据开始从树.的根@copyrightbyChunyouDong研究生学院有房婚姻年收入是否否否是否已婚单身、离婚80K80K有房婚姻状况年收入拖欠贷款否已婚80K?10测试数据开始从树.的根@copyrightbyChunyouDong研究生学院有房婚姻年收入是否否否是否已婚单身、离婚80K80K有房婚姻状况年收入拖欠贷款否已婚80K?10测试数据开始从树.的根@copyrightbyChunyouDong举例说明分类任务研究生学院应用模型l归纳推论学习模型模型Tid有房者婚姻状况年收入拖欠贷款1是单身125K否2否已婚100K否3否单身70K否4是已婚120K否5否离异95K是6否已婚60K否7是离异220K否8否单身85K是9否已婚75K否10否单身90K是10Tid有房者婚姻状况2年收入拖欠贷款11否单身l55K?12是已婚80K?13是离异110K?14否单身95K?15否已婚67K?10学习算法@copyrightbyChunyouDong决策树在构建过程中需重点解决2个问题：(1)如何选择合适的属性作为决策树的节点去划分训练样本；(2)如何在适当位置停止划分过程，从而得到大小合适的决策树。虽然可以采用任何一个属性对数据集进行划分，但最后形成的决策树会差异很大。需要寻找合适的属性选择方法。属性选择是决策树算法中重要的步骤，常见的属性选择标准包括信息增益(informationgain)和Gini系数。信息增益是决策树常用的分枝准则,在树的每个结点上选择具有最高信息增益的属性作为当前结点的划分属性。Gini系数是一种不纯度函数，用来度量数据集的数据关于类的纯度。@copyrightbyChunyouDong二、DI3分类算法1.ID3分类算法提出：由Quinlan于1986年提出，它使用信息增益(informationgain)作为属性的选择标准。首先检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一个类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。2.ID3分类算法相关的基本概念：1）信息熵2）信息增益@copyrightbyChunyouDong•熵(entropy,也称信息熵)用来度量一个属性的信息量。–假定S为训练集，S的目标属性C具有m个可能的类标号值，C={C1,C2,…,Cm}，假定训练集S中，Ci在所有样本中出现的频率为(i=1,2,3,…,m)，则该训练集S所包含的信息熵定义为：–熵越小表示样本对目标属性的分布越纯，反之熵越大表示样本对目标属性分布越混乱。miiimpppppEntropySEntropy1221log),...,,()(@copyrightbyChunyouDongoutlooktemperaturehumiditywindplayballsunnyhothighweaknosunnyhothighstrongnoovercasthothighweakyesrainmildhighweakyesraincoolnormalweakyesraincoolnormalstrongnoOvercast（阴天）coolnormalstrongyessunnymildhighweaknosunnycoolnormalweakyesrainmildnormalweakyessunnymildnormalstrongyesovercastmildhighstrongyesovercasthotnormalweakyesrainmildhighstrongno•信息熵例题演示考虑数据集weather如下,求weather数据集关于目标属性playball的熵。目标属性@copyrightbyChunyouDong•解答：令weather数据集为S，其中有14个样本,目标属性playball有2个值{C1=yes,C2=no}。14个样本的分布为：–9个样本的类标号取值为yes，5个样本的类标号取值为No。C1=yes在所有样本S中出现的概率为9/14，C2=no在所有样本S中出现的概率为5/14。–因此数据集S的熵为：94.0145log145149log149)145,149()(22EntropySEntropy@copyrightbyChunyouDong•信息增益：是划分前样本数据集的不纯程度(熵)和划分后样本数据集的不纯程度(熵)的差值。–假设划分前样本数据集为S,并用属性A来划分样本集S，则按属性A划分S的信息增益Gain(S,A)为样本集S的熵减去按属性A划分S后的样本子集的熵：•按属性A划分S后的样本子集的熵定义如下：假定属性A有k个不同的取值，从而将S划分为k个样本子集{S1,S2,…,Sk}，则按属性A划分S后的样本子集的信息熵为:•其中|Si|(i,=1,2,…k)为样本子集Si中包含的样本数，|S|为样本集S中包含的样本数。信息增益越大，说明使用属性A划分后的样本子集越纯，越有利于分类。)()(),(SEntropySEntropyASGainAkiiiASEntropySSSEntropy1)(||||)(@copyrightbyChunyouDong•以数据集weather为例，设该数据集为S，假定用属性wind来划分S，求S对属性wind的