教材配套教学――基本数据挖掘技术

第2章基本数据挖掘技术之一决策树清华大学出版社本章目标•决策树–了解决策树的概念；–了解C4.5决策树建立过程、关键技术、和决策树规则；–了解其他决策树算法。•关联规则–了解关联规则；–掌握Apriori关联分析过程。•聚类分析–掌握K-均值算法。•了解数据挖掘技术的选择考虑。2020年4月15日星期三第2页，共28页2.1决策树清华大学出版社决策树学习•从数据产生决策树的机器学习技术称为决策树学习，简称决策树（DecisionTree）。•决策树是数据挖掘中最常用的一种分类和预测技术，使用其可建立分类和预测模型。•决策树模型是一个树状结构，树中每个节点表示分析对象的某个属性，每个分支表示这个属性的某个可能的取值，每个叶节点表示经历从根节点到该叶节点这条路径上的对象的值。模型通过树中的各个分支对对象进行分类，叶节点表示的对象值表达了决策树分类的结果。决策树仅有一个输出，若需要有多个输出，可以建立多棵独立的决策树以处理不同输出。2020年4月15日星期三第4页，共28页清华大学出版社2.1.1决策树算法的一般过程（C4.5）（1）给定一个表示为“属性-值”格式的数据集T。数据集由多个具有多个输入属性和一个输出属性的实例组成。（2）选择一个最能区别T中实例的输入属性，C4.5使用增益率来选择该属性。（3）使用该属性创建一个树节点，同时创建该节点的分支，每个分支为该节点的所有可能取值。（4）使用这些分支，将数据集中的实例进行分类，成为细分的子类。（5）将当前子类的实例集合设为T，对数据集中的剩余属性重复（2）（3）步，直到满足以下两个条件之一时，该过程终止，创建一个叶子节点，该节点为沿此分支所表达的分类类别，其值为输出属性的值。该子类中的实例满足预定义的标准，如全部分到一个输出类中，分到一个输出类中的实例达到某个比例；没有剩余属性。2020年4月15日星期三第5页，共28页【例2.1】给定如表2.1所示的数据集T，建立一棵决策树，用于预测某个学生是否决定去打篮球。清华大学出版社表2.1一个假想的打篮球数据集2020年4月15日星期三第7页，共28页序号WeatherTemperature/CCoursesPartnerPlay1Sunny20~304YesYes2Sunny20~304NoYes3Rain10~01YesYes4Sunny30~405YesYes5Rain20~308NoNo6Sunny-10~05YesYes7Sunny-10~07NoNo8Rain20~302YesYes9Rain20~306YesNo10Sunny10~206YesNo11Rain10~203NoNo12Rain10~201YesNo13Sunny10~208YesNo14Sunny0~103YesYes15Rain0~102YesNo清华大学出版社决策树•使用15个实例进行有训练，其中Weather、Temperature、Courses和Partner作为输入属性，Play作为输出属性。2020年4月15日星期三第8页，共28页WeatherYesNoSunnyRainCoursesNo≤55图2.1打篮球决策树清华大学出版社2.1.2决策树算法的关键技术•三项关键技术（1）选择最能区别数据集中实例属性的方法（2）剪枝方法（3）检验方法2020年4月15日星期三第9页，共28页清华大学出版社1、选择最能区别数据集中实例属性的方法•C4.5使用了信息论（InformationTheory）的方法，即使用增益率（GainRatio）的概念来选择属性；•目的是使树的层次和节点数最小，使数据的概化程度最大化。•C4.5选择的基本思想–选择具有最大增益率的属性作为分支节点来分类实例数据。2020年4月15日星期三第10页，共28页清华大学出版社1）信息熵•1948年，克劳德·香农（ClaudeShannon）提出“信息熵”（InformationEntropy）的概念•信息变化的平均信息量称为“信息熵”（信息量化）•在信息论中，信息熵是信息的不确定程度的度量。熵越大，信息就越不容易搞清楚，需要的信息量就越大，能传输的信息就越多。2020年4月15日星期三第11页，共28页niiixpxpxH12)((log)()(清华大学出版社2）信息增益（InformationGain）•信息增益表示当x取属性xi值时，其对降低x的熵的贡献大小。•信息增益值越大，越适于对x进行分类。•C4.5使用信息量和信息增益的概念计算所有属性的增益，并计算所有属性的增益率，选择值最大的属性来划分数据实例。2020年4月15日星期三第12页，共28页计算属性A的增益率的公式)(SplitsInfo)Gain()GainRatio(AAA•其中，对于一组I实例，计算Gain(A)——),Info()Info()Gain(AIAA清华大学出版社2）信息增益（InformationGain）•Info(I)为当前数据集所有实例所表达的信息量2020年4月15日星期三第13页，共28页niiiI12)(log)Info(所有实例总数类中的实例个数出现在所有实例总数类中的实例个数出现在•Info(I,A)为根据属性A的k个可能取值分类I中实例之后所表达的信息量kjjjAI1)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,Weather)=8/15Info(Sunny)+7/15Info(Rain)=0.9118其中：Info(Sunny)=(5/8log2(5/8)+3/8log2(3/8))=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.99680.9118=-0.085（5）GainRatio(Weather)=Gain(Weather))/SplitsInfo(Weather)=-0.085/0.9968=-0.0852020年4月15日星期三第14页，共28页Weather5Yes3No2Yes5NoSunnyRain图2.2Weather作为根节点的局部决策树清华大学出版社二元分裂点（BinarySplits）•数值型属性Courses的增益值如何计算呢？–C4.5算法对这些数值型数据进行排序，计算每个可能的二元分裂点的增益率值来离散化这个属性值。2020年4月15日星期三第15页，共28页表2.2打篮球数据集中数值型属性Courses的排序结果112233445566788YesNoYesNoNoYesYesYesYesYesNoNoNoNoNo清华大学出版社Courses属性作为根节点•计算4个属性的增益率值后，发现Courses属性的≤5和5分裂点处具有最佳增益率值，为0.4457。2020年4月15日星期三第16页，共28页Courses7Yes3No0Yes5No≤55图2.3Courses作为根节点的局部决策树清华大学出版社完整决策树2020年4月15日星期三第17页，共28页Weather5Yes0No2Yes3NoSunnyRainCourses0Yes5No≤55图2.4Courses作为根节点的完整决策树【例2.2】使用表2.1所示的数据集T，使用Weka软件，应用C4.5算法建立决策树，用于预测某个学生是否决定去打篮球。清华大学出版社实验结果•使用Weka软件，选择C4.5算法（名为J48）2020年4月15日星期三第19页，共28页图2.10WekaJ48建立的打篮球决策树清华大学出版社2、决策树剪枝•剪枝（Pruning）–为控制决策树规模，优化决策树而采取的剪除部分分支的方法。•剪枝分为两种–预剪枝（Pre-Pruning）–后剪枝（Post-Pruning）2020年4月15日星期三第20页，共28页【例2.3】使用来自UCI的CreditScreeningDatabases数据集，应用Weka的J48（C4.5）算法建立两棵决策树，分别为剪枝和未剪枝的。清华大学出版社方法和结果2020年4月15日星期三第22页，共28页图2.11设置“未剪枝的”图2.12经过剪枝的决策树2.13未经过剪枝的决策树清华大学出版社3、决策树检验•Weka提供了4种检验方法（1）usetrainingset：使用在训练集实例上的预测效果进行检验。（2）suppliedtestset：使用另外提供的检验集实例进行检验，此时需要单击Set按钮来选择用来检验的数据集文件。（3）cross-validation：使用交叉验证（CrossValidation，简称CV）来检验分类器，所用的折数填在Folds文本框中。（4）percentsplit：百分比检验。从数据集中按一定百分比取出部分数据作为检验集实例用，根据分类器在这些实例上的预测效果来检验分类器的质量。取出的数据量由“%”栏中的值决定。2020年4月15日星期三第23页，共28页清华大学出版社交叉检验•检验分类器性能的一种最为常用的统计分析方法，•基本思想–将数据集分为训练集和检验集，划分方法不同有不同CV检验方法。①Hold-Out方法②k-折交叉检验（k-CV）③Leave-One-Out交叉检验（LOO-CV）2020年4月15日星期三第24页，共28页清华大学出版社2.1.3决策树规则•决策树每一条路径都可使用一条产生式规则来解释，整个决策树可以被映射为一组规则。Courses≤5|Weather=Sunny:Yes(5.0)|Weather=Rain:No(5.0/2.0)Courses5:No(5.0)•将以上Weka产生的规则翻译为三条产生式规则（1）IFCourses≤5andWeather=SunnyTHENPlay=Yes正确率：5/5=100%覆盖率：5/7=71.4%（2）IFCourses≤5andWeather=RainTHENPlay=No正确率：3/5=60%覆盖率：3/8=37.5%（3）IFCourses5THENPlay=No正确率：5/5=100%覆盖率：5/8=62.5%2020年4月15日星期三第25页，共28页清华大学出版社简化或淘汰规则•例如，若出现如下一条规则：–IFCourses≤5andWeather=SunnyandTemperature=20~30THENPlay=Yes–正确率：2/2=100%覆盖率：2/7=28.6%–可简化为•IFCourses≤5andWeather=SunnyTHENPlay=Yes•正确率：5/5=100%覆盖率：5/7=71.4%2020年4月15日星期三第26页，共28页清华大学出版社2.1.4其他决策树算法•ID3算法–C4.5的前身–J.罗斯·昆兰1986年提出的。–与C4.5最大的不同——ID3使用信息增益来选择分裂属性。•CART（ClassificationAndRegressionTree，分类回归树）–1984年雷奥·布莱曼（LeoBreiman）等人提出的。•CHAID决策树算法–戈登V.凯斯（GordonV.Kass）于1980年提出的。–CHAID与C4.5和CART不同，它要求所有属性为分类类型，且使用x2显著性检验来选择分裂属性。–CHAID具有统计学特色，在SAS和SPSS等商业统计软件中应用