1、第2章 基本数据挖掘技术 之一决策树清华大学出版社本章目标决策树 了解决策树的概念；了解C4.5决策树建立过程、关键技术、和决策树规则；了解其他决策树算法。关联规则 了解关联规则；掌握Apriori关联分析过程。聚类分析 掌握K-均值算法。了解数据挖掘技术的选择考虑。2022年7月27日星期三第2页，共28页2.1 决策树清华大学出版社决策树学习从数据产生决策树的机器学习技术称为决策树学习，简称决策树（Decision Tree）。决策树是数据挖掘中最常用的一种分类和预测技术，使用其可建立分类和预测模型。决策树模型是一个树状结构，树中每个节点表示分析对象的某个属性，每个分支表示这个属性的某个可
2、能的取值，每个叶节点表示经历从根节点到该叶节点这条路径上的对象的值。模型通过树中的各个分支对对象进行分类，叶节点表示的对象值表达了决策树分类的结果。决策树仅有一个输出，若需要有多个输出，可以建立多棵独立的决策树以处理不同输出。2022年7月27日星期三第4页，共28页清华大学出版社2.1.1 决策树算法的一般过程（C4.5）（1）给定一个表示为“属性-值”格式的数据集T。数据集由多个具有多个输入属性和一个输出属性的实例组成。（2）选择一个最能区别T中实例的输入属性，C4.5使用增益率来选择该属性。（3）使用该属性创建一个树节点，同时创建该节点的分支，每个分支为该节点的所有可能取值。（4）使用这
3、些分支，将数据集中的实例进行分类，成为细分的子类。（5）将当前子类的实例集合设为T，对数据集中的剩余属性重复（2）（3）步，直到满足以下两个条件之一时，该过程终止，创建一个叶子节点，该节点为沿此分支所表达的分类类别，其值为输出属性的值。l 该子类中的实例满足预定义的标准，如全部分到一个输出类中，分到一个输出类中的实例达到某个比例；l 没有剩余属性。2022年7月27日星期三第5页，共28页【例2.1】给定如表2.1所示的数据集T，建立一棵决策树，用于预测某个学生是否决定去打篮球。清华大学出版社表2.1 一个假想的打篮球数据集2022年7月27日星期三第7页，共28页序号WeatherTempe
4、rature/CCoursesPartnerPlay1Sunny20304YesYes2Sunny20304NoYes3Rain1001YesYes4Sunny30405YesYes5Rain20308NoNo6Sunny-1005YesYes7Sunny-1007NoNo8Rain20302YesYes9Rain20306YesNo10Sunny10206YesNo11Rain10203NoNo12Rain10201YesNo13Sunny10208YesNo14Sunny0103YesYes15Rain0102YesNo清华大学出版社决策树使用15个实例进行有训练，其中Weather、Te
5、mperature、Courses和Partner作为输入属性，Play作为输出属性。2022年7月27日星期三第8页，共28页WeatherYesNoSunnyRainCoursesNo55图2.1 打篮球决策树清华大学出版社2.1.2 决策树算法的关键技术三项关键技术（1）选择最能区别数据集中实例属性的方法（2）剪枝方法（3）检验方法2022年7月27日星期三第9页，共28页清华大学出版社1、选择最能区别数据集中实例属性的方法C4.5使用了信息论（Information Theory）的方法，即使用增益率（Gain Ratio）的概念来选择属性；目的是使树的层次和节点数最小，使数据的概化程
6、度最大化。C4.5选择的基本思想 选择具有最大增益率的属性作为分支节点来分类实例数据。2022年7月27日星期三第10页，共28页清华大学出版社1）信息熵 1948年，克劳德香农（Claude Shannon）提出“信息熵”（Information Entropy）的概念 信息变化的平均信息量称为“信息熵”（信息量化）在信息论中，信息熵是信息的不确定程度的度量。熵越大，信息就越不容易搞清楚，需要的信息量就越大，能传输的信息就越多。2022年7月27日星期三第11页，共28页niiixpxpxH12)(log)()(清华大学出版社2）信息增益（Information Gain）信息增益表示当x取
7、属性xi值时，其对降低x的熵的贡献大小。信息增益值越大，越适于对x进行分类。C4.5使用信息量和信息增益的概念计算所有属性的增益，并计算所有属性的增益率，选择值最大的属性来划分数据实例。2022年7月27日星期三第12页，共28页计算属性A的增益率的公式)(SplitsInfo)Gain()GainRatio(A A A其中，对于一组 I 实例，计算Gain(A),Info()Info()Gain(AIA A清华大学出版社2）信息增益（Information Gain）Info(I)为当前数据集所有实例所表达的信息量2022年7月27日星期三第13页，共28页niiiI12)(log)Info
8、(所有实例总数类中的实例个数出现在所有实例总数类中的实例个数出现在 Info(I,A)为根据属性 A 的 k 个可能取值分类 I 中实例之后所表达的信息量 kjjj AI1)Info(),Info(类所有实例总数实例个数的类中出现在kjjjA12)(log)(SplitsInfo所有实例总数类中的实例个数出现在所有实例总数类中的实例个数出现在SplitsInfo(A)是对A属性的增益值的标准化，目的是消除属性选择上的偏差（Bias），清华大学出版社以Weather作为根节点（1）Info(I)=(7/15log2(7/15)-8/15log2(8/15)=0.9968（2）Info(I,Wea
9、ther)=8/15Info(Sunny)+7/15Info(Rain)=0.9118 其中：Info(Sunny)=(5/8log2(5/8)+3/8log2(3/8)=0.9544 Info(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)/SplitsI
10、nfo(Weather)=-0.085/0.9968=-0.0852022年7月27日星期三第14页，共28页图2.2 Weather作为根节点的局部决策树清华大学出版社二元分裂点（Binary Splits）数值型属性Courses的增益值如何计算呢？C4.5算法对这些数值型数据进行排序，计算每个可能的二元分裂点的增益率值来离散化这个属性值。2022年7月27日星期三第15页，共28页表2.2 打篮球数据集中数值型属性Courses的排序结果112233445566788YesNoYesNoNoYesYesYesYesYesNoNoNoNoNo清华大学出版社Courses属性作为根节点计算4
11、个属性的增益率值后，发现Courses属性的 5 和 5 分裂点处具有最佳增益率值，为0.4457。2022年7月27日星期三第16页，共28页图2.3 Courses作为根节点的局部决策树清华大学出版社完整决策树2022年7月27日星期三第17页，共28页Weather5 Yes0 No2 Yes3 NoSunnyRainCourses0 Yes5 No55图2.4 Courses作为根节点的完整决策树【例2.2】使用表2.1所示的数据集T，使用Weka软件，应用C4.5算法建立决策树，用于预测某个学生是否决定去打篮球。清华大学出版社实验结果 使用Weka软件，选择C4.5算法（名为J48）
12、2022年7月27日星期三第19页，共28页图2.10 Weka J48建立的打篮球决策树清华大学出版社2、决策树剪枝 剪枝（Pruning）为控制决策树规模，优化决策树而采取的剪除部分分支的方法。剪枝分为两种 预剪枝（Pre-Pruning）后剪枝（Post-Pruning）2022年7月27日星期三第20页，共28页【例2.3】使用来自UCI的 Credit Screening Databases数据集，应用Weka的J48（C4.5）算法建立两棵决策树，分别为剪枝和未剪枝的。清华大学出版社方法和结果2022年7月27日星期三第22页，共28页图2.11 设置“未剪枝的”图2.12 经过剪
13、枝的决策树2.13 未经过剪枝的决策树清华大学出版社3、决策树检验 Weka提供了4种检验方法（1）use training set：使用在训练集实例上的预测效果进行检验。（2）supplied test set：使用另外提供的检验集实例进行检验，此时需要单击 Set按钮来选择用来检验的数据集文件。（3）cross-validation：使用交叉验证（Cross Validation，简称CV）来检验分类器，所用的折数填在Folds 文本框中。（4）percent split：百分比检验。从数据集中按一定百分比取出部分数据作为检验集实例用，根据分类器在这些实例上的预测效果来检验分类器的质量。取
14、出的数据量由“%”栏中的值决定。2022年7月27日星期三第23页，共28页清华大学出版社交叉检验 检验分类器性能的一种最为常用的统计分析方法，基本思想 将数据集分为训练集和检验集，划分方法不同有不同CV检验方法。Hold-Out方法 k-折交叉检验（k-CV）Leave-One-Out交叉检验（LOO-CV）2022年7月27日星期三第24页，共28页清华大学出版社2.1.3决策树规则决策树每一条路径都可使用一条产生式规则来解释，整个决策树可以被映射为一组规则。Courses5|Weather=Sunny:Yes(5.0)|Weather=Rain:No(5.0/2.0)Courses 5:
15、No(5.0)将以上Weka产生的规则翻译为三条产生式规则（1）IF Courses 5 and Weather=Sunny THEN Play=Yes 正确率：5/5=100%覆盖率：5/7=71.4%（2）IF Courses 5 THEN Play=No正确率：5/5=100%覆盖率：5/8=62.5%2022年7月27日星期三第25页，共28页清华大学出版社简化或淘汰规则 例如，若出现如下一条规则：IF Courses 5 and Weather=Sunny and Temperature=2030 THEN Play=Yes 正确率：2/2=100%覆盖率：2/7=28.6%可简化为
16、 IF Courses 5 and Weather=Sunny THEN Play=Yes 正确率：5/5=100%覆盖率：5/7=71.4%2022年7月27日星期三第26页，共28页清华大学出版社2.1.4 其他决策树算法ID3算法 C4.5的前身 J.罗斯昆兰 1986年提出的。与C4.5最大的不同ID3使用信息增益来选择分裂属性。CART（Classification And Regression Tree，分类回归树）1984年雷奥布莱曼（Leo Breiman）等人提出的。CHAID决策树算法 戈登V.凯斯（Gordon V.Kass）于1980年提出的。CHAID与C4.5和CA
17、RT不同，它要求所有属性为分类类型，且使用x2显著性检验来选择分裂属性。CHAID具有统计学特色，在SAS和SPSS等商业统计软件中应用很好。2022年7月27日星期三第27页，共28页清华大学出版社2.1.5 决策树小结优点（1）容易被理解和被解释，并且可以被映射到一组更具吸引力的产生式规则。（2）不需要对数据的性质作预先的假设。（3）能够使用数值型数据和分类类型数据的数据集建立模型。局限性（1）输出属性必须是分类类型，且输出属性必须为一个。（2）决策树算法是不稳定（Unstable）的。（3）用数值型数据集创建的树较为复杂（如例2.3中的未剪枝的决策树），因为数值型数据的属性分裂通常是二元分裂。2022年7月27日星期三第28页，共28页
