第2章 基本数据挖掘技术-分类

1、第2章基本数据挖掘技术,分类-决策树、关联规则、聚类-k-means,分类-决策树了解决策树的概念；了解C4.5决策树建立过程、关键技术、和决策树规则；了解其他决策树算法。关联规则了解关联规则；掌握Apriori关联分析过程。聚类分析掌握K-均值算法。了解数据挖掘技术的选择考虑。,本章目标,2.1分类-决策树,4,预测肿瘤细胞是良性还是恶性将信用卡交易分为正常或是欺诈对蛋白质的二级结构进行分类手写体的识别:0,1,9Email过滤:识别垃圾邮件,分类任务例子,决策树基本概念,分类也称为有监督学习(supervisedlearning),与之相对于的是无监督学习(unsupervisedlear

2、ning),比如聚类。分类与聚类的最大区别在于，分类数据中的一部分的类别是已知的，而聚类数据的类别未知。建立分类模型需要学习一部分已知数据，如果训练时间过长，或者预测模型参数太多而样本较少，将导致过拟合(overfitting)。,2020/7/4,6,如何避免过度训练,避免过度训练最重要一点是，模型的参数量应远小于样本的数量。应建立训练集(trainingset)和测试集(testset)。训练集应用于建立分类模型测试集应用于评估分类模型K折叠交叉验证(K-foldcrossvalidation)：将初始采样分割成K个子样本(S1，S2,.,Sk)，取K-1个做训练集，另外一个做测试集。交叉

3、验证重复K次，每个子样本都作为测试集一次，平均K次的结果，最终得到一个单一估测。,7,决策树(Decisiontrees)规则归纳(Ruleinduction)贝叶斯学习(Bayesianlearning)神经网络(Neuralnetworks)支持向量机(SupportVectorMachine)Ensemble方法(AdaBoost,Bagging.),常用的方法,从数据产生决策树的机器学习技术称为决策树学习，简称决策树（DecisionTree）。决策树是数据挖掘中最常用的一种分类和预测技术，使用其可建立分类和预测模型。,决策树学习,决策树基本概念,决策树,每个决策或事件（即自然状态）都

4、可能引出两个或多个事件，导致不同的结果，把这种决策分支画成图形很像一棵树的枝干，故称决策树。决策树是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。,决策树分类的步骤,10,数据库,2020/7/4,训练样本(trainingsamples),建立模型,测试样本(testingsamples),评估模型,决策树基本概念,解决分类问题的一般方法,通过以上对分类问题一般方法的描述，可以看出分类问题一般包括两个步骤：1、模型构建（归纳）通过对训练集合的归纳，建立分类模型。2、预测应用（推论）根

5、据建立的分类模型，对测试集合进行测试。,决策树基本概念,解决分类问题的一般方法,学习算法,学习模型,模型,应用模型,训练集（类标号已知）,检验集（类标号未知）,归纳,推论,决策树基本概念,决策树的优点1、推理过程容易理解，决策推理过程可以表示成IfThen形式；2、推理过程完全依赖于属性变量的取值特点；3、可自动忽略目标变量没有贡献的属性变量，也为判断属性变量的重要性，减少变量的数目提供参考。,决策树基本概念,关于归纳学习(1),决策树技术发现数据模式和规则的核心是归纳算法。归纳是从特殊到一般的过程。归纳推理从若干个事实中表征出的特征、特性和属性中，通过比较、总结、概括而得出一个规律性的结论。

6、归纳推理试图从对象的一部分或整体的特定的观察中获得一个完备且正确的描述。即从特殊事实到普遍性规律的结论。归纳对于认识的发展和完善具有重要的意义。人类知识的增长主要来源于归纳学习。,决策树基本概念,关于归纳学习(2),归纳学习的过程就是寻找一般化描述的过程。这种一般性描述能够解释给定的输入数据，并可以用来预测新的数据。锐角三角形内角和等于180度；钝角三角形内角和等于180度；三角形内角和直角三角形内角和等于180度；等于180度,已知三角形ABC，A角等于76度，B角等于89度，则其C角等于15度,归纳学习由于依赖于检验数据，因此又称为检验学习。归纳学习存在一个基本的假设：任一假设如果能够在足

7、够大的训练样本集中很好的逼近目标函数，则它也能在未见样本中很好地逼近目标函数。该假定是归纳学习的有效性的前提条件。,决策树基本概念,关于归纳学习(3),决策树提供了一种展示类似“在什么条件下会得到什么值”这类规则的方法。比如，在贷款申请中，要对申请的风险大小做出判断，为了解决这个问题而建立的一棵决策树，从中我们可以看到决策树的基本组成部分：决策节点、分支和叶子。决策树中最上面的节点称为根节点，是整个决策树的开始。模型通过树中的各个分支对对象进行分类，叶节点表示的对象值表达了决策树分类的结果。决策树仅有一个输出，若需要有多个输出，可以建立多棵独立的决策树以处理不同输出。,决策树,18,决策树例子

8、,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,80K,划分属性,训练数据,模型:决策树,19,另一个决策树例子,categorical,categorical,continuous,class,MarSt,Refund,TaxInc,YES,NO,NO,Yes,No,Married,Single,Divorced,80K,80K,可能有多棵决策树拟合同一个数据集!,20,决策树分类任务,决策树,21,对测试数据应用模型,测试数据,从树的根节点开始.,22,对测试数据应用模型,测试数据,23,对测试数据应

9、用模型,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,80K,测试数据,24,对测试数据应用模型,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,80K,测试数据,25,对测试数据应用模型,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,80K,测试数据,26,对测试数据应用模型,Refund,MarSt,TaxInc,YES,NO

10、,NO,NO,Yes,No,Married,Single,Divorced,80K,80K,AssignCheatto“No”,测试数据,决策树算法,假定公司收集了左表数据，那么对于任意给定的客人（测试样例），你能帮助公司将这位客人归类吗？即：你能预测这位客人是属于“买”计算机的那一类，还是属于“不买”计算机的那一类？又：你需要多少有关这位客人的信息才能回答这个问题？,决策树的用途,谁在买计算机？,年龄？,学生？,信誉？,青,中,老,否,是,优,良,决策树的用途,决策树算法,决策树算法,决策树的表示,决策树的基本组成部分：决策结点、分支和叶子。,年龄？,学生？,信誉？,青,中,老,否,是,优,

11、良,决策树中最上面的结点称为根结点。是整个决策树的开始。每个分支是一个新的决策结点，或者是树的叶子。每个决策结点代表一个问题或者决策.通常对应待分类对象的属性。每个叶结点代表一种可能的分类结果,在沿着决策树从上到下的遍历过程中，在每个结点都有一个测试。对每个结点上问题的不同测试输出导致不同的分枝，最后会达到一个叶子结点。这一过程就是利用决策树进行分类的过程，利用若干个变量来判断属性的类别,决策树算法,与决策树相关的重要算法,1、Hunt,Marin和Stone于1966年研制的CLS学习系统，用于学习单个概念。2、1979年,J.R.Quinlan给出ID3算法，并在1983年和1986年对I

12、D3进行了总结和简化，使其成为决策树学习算法的典型。3、Schlimmer和Fisher于1986年对ID3进行改造，在每个可能的决策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。4、1988年，Utgoff在ID4基础上提出了ID5学习算法，进一步提高了效率。1993年，Quinlan进一步发展了ID3算法，改进成C4.5算法。5、另一类决策树算法为CART，与C4.5不同的是，CART的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例。,CLS,ID3，C4.5，CART,决策树算法,CLS（ConceptLearningSystem）算法,CLS

13、算法是早期的决策树学习算法。它是许多决策树学习算法的基础。CLS基本思想从一棵空决策树开始，选择某一属性（分类属性）作为测试属性。该测试属性对应决策树中的决策结点。根据该属性的值的不同，可将训练样本分成相应的子集，如果该子集为空，或该子集中的样本属于同一个类，则该子集为叶结点，否则该子集对应于决策树的内部结点，即测试结点，需要选择一个新的分类属性对该子集进行划分，直到所有的子集都为空或者属于同一类。,决策树算法,CLS算法,决策树算法,CLS算法-决策树的构建,眼睛颜色,1，6,2，4，8,3，5，7,黑色,蓝色,灰色,不属于同一类，非叶结点,眼睛颜色,头发颜色,头发颜色,头发颜色,黑色,蓝色

14、,灰色,决策树算法,CLS算法,黄种人1,混血6,白种人2,白种人4,混血8,白种人3,白种人5,混血7,黑色,金色,金色,红色,黑色,金色,红色,黑色,决策树算法,CLS算法步骤,1生成一颗空决策树和一张训练样本属性集;2若训练样本集T中所有的样本都属于同一类,则生成结点T,并终止学习算法;否则3根据某种策略从训练样本属性表中选择属性A作为测试属性,生成测试结点A4若A的取值为v1,v2,vm,则根据A的取值的不同,将T划分成m个子集T1,T2,Tm;5从训练样本属性表中删除属性A;6转步骤2,对每个子集递归调用CLS;,CLS算法问题,在步骤3中，根据某种策略从训练样本属性表中选择属性A作

15、为测试属性。没有规定采用何种测试属性。实践表明，测试属性集的组成以及测试属性的先后对决策树的学习具有举足轻重的影响。(为什么？),决策树算法,CLS算法测试属性的选择,学生膳食结构和缺钙调查表,其中1该学生的表示食物中包含相应的肉类或蔬菜，0表示不包含。,采用不同的测试属性及其先后顺序将会生成不同的决策树,鸡肉,猪肉,猪肉,牛肉,牛肉,牛肉,不缺钙（2）,缺钙（3，6）,不缺钙（4）,不缺钙（10）,缺钙（5）,不缺钙（1）,鱼肉,缺钙（5）,不缺钙（7，9）,是,否,是,否,否,否,否,否,否,是,是,是,是,是,CLS算法测试属性的选择,牛奶,不缺钙（1，2，4，7，9，10）,缺钙（3，

16、5，6，8）,CLS算法问题,决策树算法,在上例中，显然生成的两种决策树的复杂性和分类意义相差很大由此可见，选择测试属性是决策树学习算法中需要研究的重要课题。,ID3,决策树算法,ID3算法主要针对属性选择问题。是决策树学习方法中最具影响和最为典型的算法。该方法使用信息增益度选择测试属性。当获取信息时，将不确定的内容转为确定的内容，因此信息伴着不确定性。从直觉上讲，小概率事件比大概率事件包含的信息量大。如果某件事情是“百年一见”则肯定比“习以为常”的事件包含的信息量大。如何度量信息量的大小？,决策树基础,C4.5算法,ID3算法,决策树基础,信息论基础,选哪个？,怎么生成好的？,NextOne

17、!,香农的信息论,1948年，香农提出了“信息熵”(shng)的概念，解决了对信息的量化问题。信息量的大小，由其所消除的不确定性大小来衡量！,例,你已经确知的东西，别人告诉你，你会觉得信息量不大。,信息论之父C.E.Shannon,信息的定量描述,衡量信息多少的物理量称为信息量。若概率很大，受信者事先已有所估计，则该消息信息量就很小；若概率很小，受信者感觉很突然，该消息所含信息量就很大。,信息量的定义,根据客观事实和人们的习惯概念，函数f(p)应满足以下条件：f(p)应是概率p的严格单调递减函数，即当p1p2，f(p1)f(p2)；当p=1时，f(p)=0；当p=0时，f(p)=；两个独立事件

18、的联合信息量应等于它们分别的信息量之和。,对信息量的认识理解,信息量的定义若一个消息x出现的概率为p，则这一消息所含的信息量为其中，对数的底大于1信息量单位以2为底时，单位为bit（binaryunit，比特）以e为底时，单位为nat（naturalunit，奈特）以10为底时，单位为hart（Hartley，哈特）,抛一枚均匀硬币，出现正面与反面的信息量是多少？解：出现正面与反面的概率均为0.5，它们的信息量是I(正)=-lbp(正)=-lb0.5=1bI(反)=-lbp(反)=-lb0.5=1b其中lb代表,抛一枚畸形硬币，出现正面与反面的概率分别是1/4，3/4，出现正面与反面时的信息量

19、是多少？解：出现正面与反面的概率分别是1/4，3/4，它们的信息量是I(正)=-lbp(正)=-lb1/4=2bI(反)=-lbp(反)=-lb3/4=0.415b,信源含有的信息量是信源发出的所有可能消息的平均不确定性，香农把信源所含有的信息量称为信息熵，是指每个符号所含信息量的统计平均值。m种符号的平均信息量为,抛一枚均匀硬币的信息熵是多少？解：出现正面与反面的概率均为0.5，信息熵是,抛一枚畸形硬币，出现正面与反面的概率分别是1/4，3/4，出现正面与反面时的信息量是多少？解：出现正面与反面的概率分别是1/4，3/4，信息熵是,例：气象预报,52,条件自信息量,在事件yj出现的条件下，随

20、机事件xi发生的条件概率为p(xi|yj)，则它的条件自信息量定义为条件概率对数的负值：,53,条件熵,在给定yj条件下，xi的条件自信息量为I(xi|yj),X集合的条件熵H(X|yj)为,在给定Y(即各个yj)条件下,X集合的条件熵H(X|Y),条件熵H(X|Y)表示已知Y后，X的不确定度,是否适合打垒球的决策表,活动,天气,是否进行垒球活动,进行,取消,晴,阴,雨,晴,阴,雨,活动,进行,取消,活动的熵,活动有2个属性值，进行，取消。其熵为：H(活动)=-(9/14)*log2(9/14)-(5/14)*log2(5/14)=0.94,活动,进行,取消,已知天气情况下活动的条件熵,天气有

21、三个属性值，晴，阴和雨。其熵分别为：H(活动|天气=晴)=-(2/5)*log2(2/5)-(3/5)*log2(3/5)=0.971H(活动|天气=阴)=-(4/4)*log2(4/4)=0H(活动|天气=雨)=-(3/5)*log2(3/5)-(2/5)*log2(2/5)=0.971,活动,天气,进行,取消,晴,阴,雨,已知天气时活动的条件熵,H(活动|天气)=5/14*H(活动|天气=晴)+4/14*H(活动|天气=阴)+5/14*H(活动|天气=雨)=(5/14)*0.971+(4/14)*0+(5/14)*0.971=0.693,晴,阴,雨,信息增益,I(活动;天气)=H(活动)-

22、H(活动|天气)=0.94-0.693=0.246,信息增益是针对一个一个特征而言的，就是看一个特征，系统有它和没有它时的信息量各是多少，两者的差值就是这个特征给系统带来的信息量，即信息增益。,活动的熵,H(活动)=-(9/14)*lb(9/14)-(5/14)*lb(5/14)=0.94,已知天气时活动的条件熵,H(活动|天气)=5/14*H(活动|天气=晴)+4/14*H(活动|天气=阴)+5/14*H(活动|天气=雨)=(5/14)*0.971+(4/14)*0+(5/14)*0.971=0.693,已知温度时活动的条件熵,H(活动|温度)=0.911,H(活动|湿度)=0.789,已知

23、湿度时活动的条件熵,H(活动|风速)=0.892,已知风速时活动的条件熵,信息增益,I(活动;天气)=H(活动)-H(活动|天气)=0.94-0.693=0.246I(活动;温度)=H(活动)-H(活动|温度)=0.94-0.911=0.029I(活动;湿度)=H(活动)-H(活动|湿度)=0.94-0.789=0.151I(活动;风速)=H(活动)-H(活动|风速)=0.94-0.892=0.048,阴,晴,雨,ID3算法生成的决策树,决策规则（产生式规则）,天气=阴进行天气=晴湿度=正常进行天气=晴湿度=高取消天气=雨风速=强取消天气=雨风速=弱进行,决策树算法,第1步计算决策属性的熵,决

24、策属性“买计算机？”。该属性分两类：买/不买S1(买)=641S2（不买）=383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740H(S)=H(S1)+H(S2)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9537,决策树算法,第2步计算条件属性的熵,条件属性共有4个。分别是年龄、收入、学生、信誉。分别计算不同属性的信息增益。,决策树算法,第2-1步计算年龄的熵,年龄共分三个组：青年、中年、老年青年买与不买比例为128/256S1(买)=128S2（不买）=256S=S1+S2=384P1=128/384

25、P2=256/384H(S)=H(S1)+H(S2)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183,决策树算法,第2-2步计算年龄的熵,年龄共分三个组：青年、中年、老年中年买与不买比例为256/0S1(买)=256S2（不买）=0S=S1+S2=256P1=256/256P2=0/256H(S)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0,决策树算法,第2-3步计算年龄的熵,年龄共分三个组：青年、中年、老年老年买与不买比例为125/127S1(买)=125S2（不买）=127S=S1+S2=252P1=12

26、5/252P2=127/252H(S)=H(S1)+H(S2)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9157,决策树算法,第2-4步计算年龄的熵,年龄共分三个组：青年、中年、老年所占比例青年组384/1025=0.375中年组256/1024=0.25老年组384/1024=0.375计算年龄的平均信息期望E（年龄）=0.375*0.9183+0.25*0+0.375*0.9157=0.6877G（年龄信息增益）=0.9537-0.6877=0.2660（1）,决策树算法,第3步计算收入的熵,收入共分三个组：高、中、低E（收入）=0.9361收入

27、信息增益=0.9537-0.9361=0.0176(2),决策树算法,第4步计算学生的熵,学生共分二个组：学生、非学生E（学生）=0.7811学生信息增益=0.9537-0.7811=0.1726（3）,决策树算法,第5步计算信誉的熵,信誉分二个组：良好，优秀E（信誉）=0.9048信誉信息增益=0.9537-0.9048=0.0453（4）,决策树算法,第6步计算选择节点,年龄信息增益=0.9537-0.6877=0.2660（1）收入信息增益=0.9537-0.9361=0.0176（2）学生信息增益=0.9537-0.7811=0.1726（3）信誉信息增益=0.9537-0.9048=

28、0.0453（4）,决策树算法,年龄,青年,中年,老年,买/不买,买,买/不买,叶子,决策树算法,青年买与不买比例为128/256S1(买)=128S2（不买）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183,决策树算法,如果选择收入作为节点分高、中、低,平均信息期望（加权总和）：E(收入）=0.3333*0+0.5*0.9183+0.1667*0=0.4592Gain(收入)=I(128,256)-E(收入)=0.91830.4592=0.

29、4591,I(0,128)=0比例:128/384=0.3333I(64,128)=0.9183比例:192/384=0.5I(64,0)=0比例:64/384=0.1667,注意,决策树算法,年龄,青年,中年,老年,学生,买,信誉,叶子,否,是,优,良,买,不买,买/不买,买,叶子,叶子,叶子,决策树算法,ID3决策树建立算法1决定分类属性；2对目前的数据表，建立一个节点N3如果数据库中的数据都属于同一个类，N就是树叶，在树叶上标出所属的类4如果数据表中没有其他属性可以考虑，则N也是树叶，按照少数服从多数的原则在树叶上标出所属类别5否则，根据平均信息期望值E或GAIN值选出一个最佳属性作为节

30、点N的测试属性6节点属性选定后，对于该属性中的每个值：从N生成一个分支，并将数据表中与该分支有关的数据收集形成分支节点的数据表，在表中删除节点属性那一栏如果分支数据表非空，则运用以上算法从该节点建立子树。,决策树算法,决策树的数据准备,原始表,决策树算法,整理后的数据表,决策树的数据准备,Datacleaning删除/减少noise，补填missingvaluesDatatransformation数据标准化（datanormalization）数据归纳（generalizedatatohigher-levelconceptsusingconcepthierarchies）例如：年龄归纳为老、

31、中、青三类控制每个属性的可能值不超过七种（最好不超过五种）Relevanceanalysis对于与问题无关的属性：删对于属性的可能值大于七种又不能归纳的属性：删,决策树算法,决策树的数据准备,决策树算法,处理连续属性值,决策树算法比较适合处理离散数值的属性。实际应用中属性是连续的或者离散的情况都比较常见。在应用连续属性值时，在一个树结点可以将属性Ai的值划分为几个区间。然后信息增益的计算就可以采用和离散值处理一样的方法。原则上可以将Ai的属性划分为任意数目的空间。C4.5中采用的是二元分割（BinarySplit）。需要找出一个合适的分割阈值。参考C4.5算法Top10algorithmsin

32、dataminingKnowledgeInformationSystem200814:137,（1）给定一个表示为“属性-值”格式的数据集T。数据集由多个具有多个输入属性和一个输出属性的实例组成。（2）选择一个最能区别T中实例的输入属性，C4.5使用增益率来选择该属性。（3）使用该属性创建一个树节点，同时创建该节点的分支，每个分支为该节点的所有可能取值。（4）使用这些分支，将数据集中的实例进行分类，成为细分的子类。（5）将当前子类的实例集合设为T，对数据集中的剩余属性重复（2）（3）步，直到满足以下两个条件之一时，该过程终止，创建一个叶子节点，该节点为沿此分支所表达的分类类别，其值为输出属性的

33、值。该子类中的实例满足预定义的标准，如全部分到一个输出类中，分到一个输出类中的实例达到某个比例；没有剩余属性。,2.1.1决策树算法的一般过程（C4.5）,【例2.1】,给定如表2.1所示的数据集T，建立一棵决策树，用于预测某个学生是否决定去打篮球。,表2.1一个假想的打篮球数据集,使用15个实例进行有训练，其中Weather、Temperature、Courses和Partner作为输入属性，Play作为输出属性。,决策树,图2.1打篮球决策树,三项关键技术（1）选择最能区别数据集中实例属性的方法（2）剪枝方法（3）检验方法,2.1.2决策树算法的关键技术,C4.5使用了信息论（Inform

34、ationTheory）的方法，即使用增益率（GainRatio）的概念来选择属性；目的是使树的层次和节点数最小，使数据的概化程度最大化。C4.5选择的基本思想选择具有最大增益率的属性作为分支节点来分类实例数据。,1、选择最能区别数据集中实例属性的方法,信息增益表示当x取属性xi值时，其对降低x的熵的贡献大小。信息增益值越大，越适于对x进行分类。C4.5使用信息量和信息增益的概念计算所有属性的增益，并计算所有属性的增益率，选择值最大的属性来划分数据实例。,2）信息增益（InformationGain）,计算属性A的增益率的公式,其中，对于一组I实例，,信息增益有选择取值多的属性的倾向信息增益率

35、通过类似于标准化的方式，克服了这种倾向,Info(I)为当前数据集所有实例所表达的信息量,2）信息增益（InformationGain）,Info(I,A)为根据属性A的k个可能取值分类I中实例之后所表达的信息量,SplitsInfo(A)是对A属性的增益值的标准化，目的是消除属性选择上的偏差（Bias），,（1）Info(I)=(7/15log2(7/15)-8/15log2(8/15)=0.9968（2）Info(I,Weather)=8/15Info(Sunny)+7/15Info(Rain)=0.9118其中：Info(Sunny)=(5/8log2(5/8)+3/8log2(3/8)

36、=0.9544Info(Rain)=(2/7(log2(2/7)+5/7log2(5/7)=0.8631（3）SplitsInfo(Weather)=-(8/15log2(8/15)+7/15log2(7/15)=0.9968（4）Gain(Weather)=Info(I)Info(I,Weather)=0.99680.9118=0.085（5）GainRatio(Weather)=Gain(Weather)/SplitsInfo(Weather)=0.085/0.9968=-0.085,以Weather作为根节点,图2.2Weather作为根节点的局部决策树,假设天气有3种，其中Sunny5

37、天，其中3天打球；Cloudy3天，其中两天打球；其它不变。（2）Info(I,Weather)=5/15Info(Sunny)+3/15Info(Cloudy)+7/15Info(Rain)=0.9102其中：Info(Sunny)=(3/5log2(3/5)+2/5log2(2/5)=0.9710Info(Cloudy)=(2/3log2(2/3)+1/3log2(1/3)=0.9183Info(Rain)=(2/7(log2(2/7)+5/7log2(5/7)=0.8631（3）SplitsInfo(Weather)=-(5/15log2(5/15)+3/15log2(3/15)+7/1

38、5log2(7/15)=1.5058（4）Gain(Weather)=Info(I)Info(I,Weather)=0.99680.9118=0.0866（5）GainRatio(Weather)=Gain(Weather)/SplitsInfo(Weather)=0.0866/1.5058=-0.0575,数值型属性Courses的增益值如何计算呢？C4.5算法对这些数值型数据进行排序，计算每个可能的二元分裂点的增益率值来离散化这个属性值。,二元分裂点（BinarySplits）,表2.2打篮球数据集中数值型属性Courses的排序结果,计算4个属性的增益率值后，发现Courses属性的5和

39、5分裂点处具有最佳增益率值，为0.4457。,Courses属性作为根节点,图2.3Courses作为根节点的局部决策树,完整决策树,图2.4Courses作为根节点的完整决策树,【例2.2】,使用表2.1所示的数据集T，使用Weka软件，应用C4.5算法建立决策树，用于预测某个学生是否决定去打篮球。,使用Weka软件，选择C4.5算法（名为J48）,实验结果,图2.10WekaJ48建立的打篮球决策树,2020/7/4,102,决策树修剪算法,基本的决策树构造算法没有考虑噪声，因此生成的决策树完全与训练集拟合。在有噪声情况下，将导致过分拟合（Overfitting），即对训练数据的完全拟合反

40、而使对现实数据的分类预测性能下降。比如每个样本都是一个叶子节点。现实世界的数据一般不可能是完美的，可能缺值（MissingValues）；数据不完整；含有噪声甚至是错误的。剪枝是一种克服噪声的基本技术，同时它也能使树得到简化而变得更容易理解。有两种基本的剪枝策略。,2020/7/4,103,决策树修剪算法,预先剪枝（Pre-Pruning）：在生成树的同时决定是继续对不纯的训练子集进行划分还是停机。后剪枝（Post-Pruning）：是一种拟合+化简（fitting-and-simplifying）的两阶段方法。首先生成与训练数据完全拟合的一棵决策树，然后从树的叶子开始剪枝，逐步向根的方向剪。剪枝时要用到一个测试数据集合（TuningSet或AdjustingSet），如果存在某个叶子剪去后能使得在测试集上的准确度或其他测度不降低（不变得更坏），则剪去该叶子；否则停机。理论上讲，后剪枝好于预先