,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,*,页，共,27,页,清华大学出版社,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,2,章 基本数据挖掘技术,之一,决策树,第2章 基本数据挖掘技术 之一决策树,本章目标,决策树,了解决策树的概念；,了解,C4.5,决策树建立过程、关键技术、和决策树规则；,了解其他决策树算法。,关联规则,了解关联规则；,掌握,Apriori,关联分析过程。,聚类分析,掌握,K-,均值算法。,了解数据挖掘技术的选择考虑。,20 十一月 2024,第,2,页，共,28,页,本章目标决策树07 十月 2023第2页，共28页,2.1,决策树,2.1 决策树,决策树学习,从数据产生决策树的机器学习技术称为决策树学习，简称决策树（,Decision Tree,）。,决策树是数据挖掘中最常用的一种分类和预测技术，使用其可建立分类和预测模型。,决策树模型是一个树状结构，树中每个节点表示分析对象的某个属性，每个分支表示这个属性的某个可能的取值，每个叶节点表示经历从根节点到该叶节点这条路径上的对象的值。模型通过树中的各个分支对对象进行分类，叶节点表示的对象值表达了决策树分类的结果。决策树仅有一个输出，若需要有多个输出，可以建立多棵独立的决策树以处理不同输出。,20 十一月 2024,第,4,页，共,28,页,决策树学习从数据产生决策树的机器学习技术称为决策树学习，简称,2.1.1,决策树算法的一般过程,（,C4.5,）,（,1,）给定一个表示为“属性,-,值”格式的数据集,T,。数据集由多个具有多个输入属性和一个输出属性的实例组成。,（,2,）选择一个最能区别,T,中实例的输入属性，,C4.5,使用增益率来选择该属性。,（,3,）使用该属性创建一个树节点，同时创建该节点的分支，每个分支为该节点的所有可能取值。,（,4,）使用这些分支，将数据集中的实例进行分类，成为细分的子类。,（,5,）将当前子类的实例集合设为,T,，对数据集中的剩余属性重复（,2,）（,3,）步，直到满足以下两个条件之一时，该过程终止，创建一个叶子节点，该节点为沿此分支所表达的分类类别，其值为输出属性的值。,该子类中的实例满足预定义的标准，如全部分到一个输出类中，分到一个输出类中的实例达到某个比例；,没有剩余属性。,20 十一月 2024,第,5,页，共,28,页,2.1.1 决策树算法的一般过程（C4.5）（1）给定一个表,【例,2.1,】,给定如表,2.1,所示的数据集,T,，建立一棵决策树，用于预测某个学生是否决定去打篮球。,【例2.1】给定如表2.1所示的数据集T，建立一棵决策树，用,表,2.1,一个假想的打篮球数据集,20 十一月 2024,第,7,页，共,28,页,序号,Weather,Temperature/,C,Courses,Partner,Play,1,Sunny,2030,4,Yes,Yes,2,Sunny,2030,4,No,Yes,3,Rain,100,1,Yes,Yes,4,Sunny,3040,5,Yes,Yes,5,Rain,2030,8,No,No,6,Sunny,-100,5,Yes,Yes,7,Sunny,-100,7,No,No,8,Rain,2030,2,Yes,Yes,9,Rain,2030,6,Yes,No,10,Sunny,1020,6,Yes,No,11,Rain,1020,3,No,No,12,Rain,1020,1,Yes,No,13,Sunny,1020,8,Yes,No,14,Sunny,010,3,Yes,Yes,15,Rain,010,2,Yes,No,表2.1 一个假想的打篮球数据集07 十月 2023第7页，,决策树,使用,15,个实例进行有训练，其中,Weather,、,Temperature,、,Courses,和,Partner,作为输入属性，,Play,作为输出属性。,20 十一月 2024,第,8,页，共,28,页,图,2.1,打篮球决策树,决策树使用15个实例进行有训练，其中Weather、Temp,2.1.2,决策树算法的关键技术,三项关键技术,（,1,）选择最能区别数据集中实例属性的方法,（,2,）剪枝方法,（,3,）检验方法,20 十一月 2024,第,9,页，共,28,页,2.1.2 决策树算法的关键技术三项关键技术07 十月 20,1,、,选择最能区别数据集中实例属性的方法,C4.5,使用了信息论（,Information Theory,）的方法，即使用增益率（,Gain Ratio,）的概念来选择属性,；,目的是使树的层次和节点数最小，使数据的概化程度最大化。,C4.5,选择的基本思想,选择具有最大增益率的属性作为分支节点来分类实例数据。,20 十一月 2024,第,10,页，共,28,页,1、选择最能区别数据集中实例属性的方法C4.5使用了信息论,1,）信息熵,1948,年，克劳德香农（,Claude Shannon,）提出,“,信息熵,”,（,InformationEntropy,）的概念,信息变化的平均信息量称为“信息熵”,（,信息量化,）,在信息论中，信息熵是信息的不确定程度的度量。熵越大，信息就越不容易搞清楚，需要的信息量就越大,，,能传输的信息就越多。,20 十一月 2024,第,11,页，共,28,页,1）信息熵1948年，克劳德香农（Claude Shann,2,）信息增益（,InformationGain,）,信息增益表示当,x,取属性,x,i,值时，其对降低,x,的熵的贡献大小。,信息增益值越大，越适于对,x,进行分类。,C4.5,使用信息量和信息增益的概念计算所有属性的增益，并计算所有属性的增益率，选择值最大的属性来划分数据实例。,20 十一月 2024,第,12,页，共,28,页,计算属性,A,的增益率的公式,其中，对于一组,I,实例，计算,Gain(A),2）信息增益（InformationGain）信息增益表,2,）信息增益（,InformationGain,）,Info(,I,),为当前数据集所有实例所表达的信息量,20 十一月 2024,第,13,页，共,28,页,Info(I,A),为根据属性,A,的,k,个可能取值分类,I,中实例之后所表达,的信息量,SplitsInfo(A),是对,A,属性的增益值的标准化，目的是消除属性选择上的偏差（,Bias,），,2）信息增益（InformationGain）Info(,以,Weather,作为根节点,（,1,）,Info(,I,)=,(7/15log,2,(7/15)-8/15log,2,(8/15)=0.9968,（,2,）,Info(,I,Weather)=8/15Info(Sunny)+7/15Info(Rain)=0.9118,其中：,Info(Sunny)=,(5/8log,2,(5/8)+3/8log,2,(3/8)=0.9544,Info(Rain)=,(2/7(log,2,(2/7)+5/7log,2,(5/7)=0.8631,（,3,）,SplitsInfo(Weather)=(8/15log,2,(8/15)+7/15log,2,(7/15)=0.9968,（,4,）,Gain(Weather)=Info(,I,),Info(,I,Weather)=0.9968,0.9118=-0.085,（,5,）,GainRatio(Weather)=Gain(Weather)/SplitsInfo(Weather),=-0.085/0.9968=-0.085,20 十一月 2024,第,14,页，共,28,页,图,2.2 Weather,作为根节点的局部决策树,以Weather作为根节点（1）Info(I)=(7/1,二元分裂点（,Binary Splits,）,数值型属性,Courses,的增益值如何计算呢？,C4.5,算法对这些数值型数据进行排序，计算每个可能的二元分裂点的增益率值来离散化这个属性值。,20 十一月 2024,第,15,页，共,28,页,表,2.2,打篮球数据集中数值型属性,Courses,的排序结果,1,1,2,2,3,3,4,4,5,5,6,6,7,8,8,Yes,No,Yes,No,No,Yes,Yes,Yes,Yes,Yes,No,No,No,No,No,二元分裂点（Binary Splits）数值型属性Cours,Courses,属性作为根节点,计算,4,个属性的增益率值后，发现,Courses,属性的,5,和,5,分裂点处具有最佳增益率值，为,0.4457,。,20 十一月 2024,第,16,页，共,28,页,图,2.3 Courses,作为根节点的局部决策树,Courses属性作为根节点计算4个属性的增益率值后，发现C,完,整,决策树,20 十一月 2024,第,17,页，共,28,页,图,2.4,Courses,作为根节点的完,整,决策树,完整决策树07 十月 2023第17页，共28页图2.4 C,【例,2.2,】,使用表,2.1,所示的数据集,T,，使用,Weka,软件，应用,C4.5,算法建立决策树，用于预测某个学生是否决定去打篮球。,【例2.2】使用表2.1所示的数据集T，使用Weka软件，应,实验结果,使用,Weka,软件，选择,C4.5,算法（名为,J48,）,20 十一月 2024,第,19,页，共,28,页,图,2.10 Weka J48,建立的打篮球决策树,实验结果使用Weka软件，选择C4.5算法（名为J48）07,2,、,决策树剪枝,剪枝（,Pruning,）,为控制决策树规模，优化决策树而采取的剪除部分分支的方法。,剪枝分为两种,预剪枝（,Pre-Pruning,）,后剪枝（,Post-Pruning,）,20 十一月 2024,第,20,页，共,28,页,2、决策树剪枝剪枝（Pruning）07 十月 2023第2,【例,2.3,】,使用来自,UCI,的,Credit Screening Databases,数据集，应用,Weka,的,J48,（,C4.5,）算法建立两棵决策树，分别为剪枝和未剪枝的。,【例2.3】使用来自UCI的 Credit Screenin,方法和结果,20 十一月 2024,第,22,页，共,28,页,图,2.11,设置“未剪枝的”,图,2.12,经过剪枝的决策树,2.13,未经过剪枝的决策树,方法和结果07 十月 2023第22页，共28页图2.11,3,、,决策树检验,Weka,提供了,4,种检验方法,（,1,）,use training set,：使用在训练集实例上的预测效果进行检验。,（,2,）,supplied test set,：使用另外提供的检验集实例进行检验，此时需要单击,Set,按钮来选择用来检验的数据集文件。,（,3,）,cross-validation,：使用交叉验证（,Cross Validation,，,简称,CV,）来检验分类器，所用的折数填在,Folds,文本框中。,（,4,）,percent split,：百分比检验。从数据集中按一定百分比取出部分数据作为检验集实例用，根据分类器在这些实例上的预测效果来检验分类器的质量。取出的数据量由“,%,”栏中的值决定。,20 十一月 2024,第,23,页，共,28,页,3、决策树检验Weka提供了4种检验方法07 十月 2023,交叉检验,检验分类器性能的一种最为常用的统计分析方法，,基本思想,将数据集分为训练集和检验集，划分方法不同,有,不同,CV,检验方法。,Hold-Out,方法,k-,折交叉检验（,k-CV,）,Leave-One-Out,交叉检验（,LOO-CV,）,20 十一月 2024,第,24,页，共,28,页,交叉检验检验分类器性能的一种最为常用的统计分析方法，07 十,2.1.3,决策