通用的决策树算法CART

Ch10.决策树特征类型•数值数据（numericaldata）•例：{1.2,4.5,3.3}•模式间可以计算距离度量•基于度量的模式分类方法•标称数据（nominaldata）•例：{红色，有光泽，甜，小}•模式间没有距离的概念•非度量方法决策树•什么是决策树？•决策树是一种类似流程图的树形结构，每个内部节点表示一个测试（查询），该节点的每个分支表示该测试的一个结果，每个叶节点表示一个类别•决策树的构成•根节点（root）•分支（branch）•叶节点（leaf）决策树决策树•决策树分类过程•从根节点开始，首先对某一属性的取值提问•Color?•与根节点相连的不同分支，对应这个属性的不同取值•green;yellow;red;•根据不同的回答，转向相应的分支•green•在新到达的节点处做同样的分支判断•Size?–big.•这一过程持续，直到到达某个叶节点，输出该叶节点的类别标记•Watermelon决策树•决策树的判决面决策树•决策树的优势•语义可表示性•从根节点到叶节点表示为合取式•（颜色=黄）AND（形状=细长）香蕉•利用合取式和析取式获得某个类别的明确描述•苹果=（绿色AND中等大小）OR（红色AND中等大小）•分类速度快•只需一系列简单查询即可对模式的类别做出判断•可以很自然的嵌入专家的先验知识决策树学习算法•决策树研究历史•第一个决策树算法称为CLS(ConceptLearningSystem)[E.B.Hunt,J.Marin,andP.T.Stone’sbook“ExperimentsinInduction”publishedbyAcademicPressin1966]•真正引发决策树研究热潮的算法是ID3[J.R.Quinlan’spaperinabook“ExpertSystemsintheMicroElectronicAge”editedbyD.Michie,publishedbyEdinburghUniversityPressin1979]•最流行的决策树算法C4.5[J.R.Quinlan’sbook“C4.5:ProgramsforMachineLearning”publishedbyMorganKaufmannin1993]决策树学习算法•决策树研究历史•通用的决策树算法CART(ClassificationandRegressionTree)[L.Breiman,J.H.Friedman,R.A.Olshen,andC.J.Stone’sbook“ClassificationandRegressionTrees”publishedbyWadsworthin1984]•基于决策树的集成学习算法：随机森林(RandomForests)[L.Breiman’sMLJ’01paper“RandomForests”]构造决策树•基本过程•从上到下，分而治之（divide-and-conquer），递归生长•最初，所有的样本都在根节点•所有属性都是标称型的（如果是连续数值型的，则需要预先离散化）•所有样本根据每次选择出的属性递归的逐渐划分开来选择出来的属性称为一个划分（split）或测试（test）或查询（query）•查询的选择基于启发式或者统计特征构造决策树•基本过程•满足如下条件之一时，划分操作停止•所有落入某一节点的样本均属于同一类别该节点成为叶节点，标记为该类别•没有特征能够进一步用于划分样本集该节点成为叶节点，类别标签为落入该节点的多数样本所属的类别•没有任何样本落入某一节点该节点成为叶节点，类别标签为落入父节点的多数样本所属的类别CART•分类和回归树（ClassificationAndRegressionTree,CART)•CART为通用的树生长算法框架，涉及如下问题：•属性的值是二值的还是多值的？即节点可以有几个分支？•如何确定某节点处应该测试哪个属性？•何时令某个节点为叶节点？•如果树生长的过大，如何使其变小变简单，即如何剪枝？•如果落入叶节点的样本不都属于同一类，如何给该叶节点赋类别标记？分支数目•同一个节点分出去的分支的数目称为分支系数或分支率（branchingratio）•任意决策树都可以用分支系数为2的决策树（即二叉树）来表示•二叉树是最常用的决策树形式分支数目分支数目测试的选取•决策树设计的核心问题之一•基本思想：使后继结点的数据尽可能的“纯粹”•节点N的不纯度（impurity）i(N)•当N节点上的所有模式都来自同一类时，i(N)=0；•当N节点上的模式类别分布均匀时，i(N)应很大测试的选取•常用不纯度度量•熵不纯度（entropyimpurity）•Gini不纯度•误分类不纯度()jjP属于的样本个数样本总个数测试的选取•常用不纯度度量测试的选取•对N节点如何选择查询？使不纯度下降最快的那个查询！•和分别为左、右子节点•和分别为左、右子节点的不纯度•是N节点的模式划分到的比例•如果采用熵不纯度，则不纯度下降差就是本次查询所能提供的信息增益（informationgain）信息增益•信息增益（informationgain）•：节点N上样本总个数•：其中属于类的样本个数（i=1,2,…,m）•：属性A的第j个取值（j=1,2,…,v）•该节点处的熵不纯度•属性A将S划分为v个子集•中属于类的样本个数为i21()logmiiiSSESSSi信息增益•信息增益（informationgain）•以A作为查询，生长出v个分支的信息熵•以A为查询的信息增益•选择信息增益最大的属性作为N节点的查询2111()()logvvmjjijijjjjijjSSSSEAESSSSS()()()GainAESEA信息增益•例子•训练集S1:buys_computer=“yes”,S2:buys_computer=“no”信息增益•根节点上的熵不纯度•age作为查询的信息熵229955()loglog0.94014141414Eroot1222233()loglog0.9715555Eroot2()0Eroot3223322()loglog0.9715555Eroot123545()()()()0.694141414Eageirootirootiroot信息增益•age作为查询的信息增益•类似可以计算出所有属性的信息增益•age的信息增益最大，所以选择age作为根节点的查询，对训练集进行首次划分()()()0.246GainageErootEage()0.029()0.151(_)0.048GainincomeGainstudentGaincreditrating信息增益率•信息增益作为查询选择标准的缺点：偏向有较多不同取值的属性•为克服这一缺点，J.R.Quinlan在其著名的C4.5算法中采用信息增益率（gainratio）作为选择标准()_()()GainAGainratioAIVA21()logvjjjSSIVASS信息增益率•例子222554455()logloglog1.578141414141414IVage222446644()logloglog1.556141414141414IVincome227777()loglog1.66114141414IVstudent228866(_)loglog0.98514141414IVcreditrating()_()0.156()GainageGainratioageIVage()_()0.019()GainincomeGainratioincomeIVincome(_)_(_)0.049(_)GaincreditratingGainratiocreditratingIVcreditrating()_()0.091()GainstudentGainratiostudentIVstudentGini不纯度•：节点N上样本总个数•：其中属于类的样本个数（i=1,2,…,m）•：属性A的第j个取值（j=1,2,…,v）•该节点处的Gini不纯度•属性A将S划分为v个子集•中属于类的样本个数为i21()1miiSGiniSSiGini不纯度•以A作为查询，生长出v个分支的Gini不纯度•选择Gini不纯度差最大（即Gini(A)最小）的属性作为N节点的查询2111()()1vvmjjijjjjijSSSGiniAGiniSSSSGini不纯度•例子222222523440()111455144453210.3431455Giniage()?Giniincome()?Ginistudent(_)?Ginicreditrating分支停止准则•如果决策树持续生长，直到所有叶节点都达到最小不纯度为止，那么一般将出现“过拟合”•极端情况：所有叶节点仅对应一个训练样本，这时，决策树退化为查找表•如果分支停止过早，则对训练样本的拟合较差，导致分类性能较差•常用分支停止准则•交叉验证•预设一个不纯度下降差的阈值•监测每个节点代表的样本数目是否小于某个阈值分支停止准则•最小化如下指标•不纯度下降的统计显著分析•如果一个划分不能显著降低不纯度，则停止分支正则项剪枝•剪枝（pruning）•用于消除过拟合•预剪枝（prepruning）和后剪枝（postpruning）•预剪枝即前面提到的分支停止技术，也就是在树生长到一定条件时停止继续划分•后剪枝指首先让树充分生长，直到叶节点具有最小不纯度为止，然后对树进行剪枝•可用交叉验证技术来确定剪掉哪些分支•剪掉使不纯度增长最小的分支•一般来讲，后剪枝性能较好，但需要更多计算量叶节点的标记•如果叶节点对应的样本都来自同一类，则用该类别标记该叶节点•一般情况下，叶节点都具有正的不纯度，此时用占优势的样本类别标记该叶节点ID3•ID3:InteractiveDichotomizer-3（交互式二分法第三版）•仅仅适用于标称（无序）数据如果涉及实值数据，则需离散化，然后当做标称数据处理•每个划分的分支因子等于查询属性的取值个数•采用信息增益率作为选择查询的依据•算法直到所有叶节点的不纯度最小，或者没有可用于划分的属性时停止•标准版中无剪枝步骤C4.5•C4.5:ID3算法的后继和改进•可以处理实值数据•每个划分的分支因子等于查询属性的取值个数•采用信息增益率作为选择查询的依据•首先让树充分生长，然后利用分支的统计显著性来实现剪枝•C4.5为目前最为流行的决策树算法之一Ch11.聚类无监督学习•有监督（supervised）学习•训练集中每个样本都有一个类别标记•所有类别事先已知•常用于：分类、回归•无监督（unsupervised）学习•训练集中样本的类别标记未知•给定一组样本，发现其内在性质，如类别和聚类•常用于：聚类、概率密度估计无监督学习的动机•收集并且标记大量模式往往花费巨大•希望首先在一个较小的有标记样本集上训练一个粗略的分类器，然后让这个分类器以非监督的方式在一个较大的样本集上运行•或者，用大量未标记的样本集来训练分类器，让它自动发现数据中的分组，然后用代价更高的办法（如人工）来标记这些分组•在很多应用中，模式的特征会随时间而变化•如果这种特征的变化能够被某种运行在无监督方式下的分类器捕捉到，那么分类性能将得到大幅提高无监督学习的动机•无监督方法可以用来提取特征，或者预处理现存特征，从而为后续的模式识别问题做准备•例如