您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 经营企划 > 决策树-上-ID3C45CART及剪枝
决策树-上武承羲内容•决策树基础•经典决策树•剪枝决策树•决策树:用来表示决策和相应的决策结果对应关系的树。树中每一个非叶节点表示一个决策,该决策的值导致不同的决策结果(叶节点)或者影响后面的决策选择。•示例:天气风阳光不玩玩不玩玩玩雨晴阴强弱强弱决策树•决策树类型–分类树:叶节点对应于一类别–回归树:叶节点对应于一连续值•ID3,C4.5andC5.0(RossQuinlan)•CART(L.Breiman,J.Friedman,R.Olshen和C.Stone)•思想:空间划分!–比如,用变量y表示因变量(分类变量),用x1,x2,x3,...,xm表示自变量。通过递归的方式把关于自变量的m维空间划分为不重叠的矩形。–图示:决策树ID3=C4.5=C5.0•RossQuinlan–ID31986年–C4.51993年–C5.01998年–2011年获得KDD创新奖•••的分类基础•信息熵–1948年,香农提出了“信息熵”的概念,解决了对系统信息的量化度量问题。–香农认为信息的准确信息量可以用下面的信息熵公式计算:–一个系统越是有序,信息熵就越低;反之,一个系统越乱,信息熵就越高。所以,信息熵也可以说是系统有序化程度的一个衡量。21()log()C=CiiiiiEntropySppi其中,S表示样本集,C表示样本集合中类别个数(只含有正负样本,则2),p表示第个类的概率,(p可由类别i中含有样本的个数除以总样本数得到)•信息增益(informationgain)–是指期望信息或者信息熵的有效减少量。2122112211(,)()()log()()()log()(){log()}log()()log()FCiivivVofFCCiivjvjivVofFjCCiivjvjivVofFjGainSFEntropySExpectedEntropySpppvEntropySpppvppppSvppFpV说明:设样本集按离散属性的个不同的取值划分1 ,...VvjvSSVpSj为,共个子集其中,表示中第类的概率•信息增益率(informationgainratio)–由划分个数引起的偏置问题(划分越多=引起每个划分内部数据纯度的变化,分块越小,数据纯度可能越高=进而引起偏置问题):–设样本集S按离散属性F的V个不同的取值划分为,共V个子集–定义Split(S,F):–则用F对S进行划分的信息增益率为:2||||(,)*log()||||vvvVSSSplitSFSS1,..,VSS(,)(,)(,)GainSFGainRatioSFSplitSF2112(,)log(lo)))(g(CvCiivVofFvjjijpGaipvpnSFppID3•1986年由Quilan提出的ID3算法•选择具有最高信息增益的属性作为测试属性。•ID3(DataSet,featureList):–创建根节点R–如果当前DataSet中的数据都属于同一类,则标记R的类别为该类–如果当前featureList集合为空,则标记R的类别为当前DataSet中样本最多的类别–递归情况:•从featureList中选择属性F(选择Gain(DataSet,F)最大的属性)•根据F的每一个值v,将DataSet划分为不同的子集DS,对于每一个DS:–创建节点C–如果DS为空,节点C标记为DataSet中样本最多的类别–如果DS不为空,节点C=ID3(DS,featureList-F)–将节点C添加为R的子节点•C源码:示例-1属性及值域:outlook={sunny,overcast,rain},temperature={hot,mild,cool}humidity={high,normal},wind={weak,strong}210.9402869955()log()loglog14141414CiiiEntropySpp30.97095322()logl1og5555outlookrainEntropyS4400()l0o0glog4444outlookovercastEntropyS定义同属于一类的情况,熵是2233()0.9709loglog555551outlooksunnyEntropyS2211(,)log()()log()5450.940286-()-()-()14141455=0.940286-*0.970951-0-*0.97095114140.24675=CCiivjvjivVofFjoutlooksunnyoutlookovercastoutlookrainGainSoutlookpppvppentropySentropySentropySGain(S,Temperature)=0.029Gain(S,Humidity)=0.151Gain(S,Wind)=0.048由此选择根节点划分属性为outlook•参考:–~ddd/cap6635/Fall-97/Short-papers/2.htm–•1993年由Quilan提出的C4.5算法(对ID3的改进)•信息增益率•连续值属性•缺失值•后剪枝–基于错误剪枝EBP(Error-BasedPruning)C4.5-连续型属性•离散化处理:将连续型的属性变量进行离散化处理,形成决策树的训练集–把需要处理的样本(对应根节点)或样本子集(对应子树)按照连续变量的大小从小到大进行排序–假设该属性对应的不同的属性值一共有N个,那么总共有N-1个可能的候选分割阈值点,每个候选的分割阈值点的值为上述排序后的属性值中两两前后连续元素的中点–用信息增益率选择最佳划分C4.5-缺失值•缺失值:在某些情况下,可供使用的数据可能缺少某些属性的值。例如(X,y)是样本集S中的一个训练实例,X=(F1_v,F2_v,…Fn_v)。但是其属性Fi的值Fi_v未知。•处理策略:–处理缺少属性值的一种策略是赋给它结点t所对应的训练实例中该属性的最常见值–另外一种更复杂的策略是为Fi的每个可能值赋予一个概率。例如,给定一个布尔属性Fi,如果结点t包含6个已知Fi_v=1和4个Fi_v=0的实例,那么Fi_v=1的概率是0.6,而Fi_v=0的概率是0.4。于是,实例x的60%被分配到Fi_v=1的分支,40%被分配到另一个分支。这些片断样例(fractionalexamples)的目的是计算信息增益,另外,如果有第二个缺少值的属性必须被测试,这些样例可以在后继的树分支中被进一步细分。(C4.5中使用)–简单处理策略就是丢弃这些样本C4.5-算法步骤示意•C4.5(DataSet,featureList):–创建根节点R–如果当前DataSet中的数据都属于同一类,则标记R的类别为该类–如果当前featureList集合为空,则标记R的类别为当前DataSet中样本最多的类别–递归情况:•从featureList中选择属性F(选择GainRatio(DataSet,F)最大的属性,连续属性参见上面的离散化过程)•根据F的每一个值v,将DataSet划分为不同的子集DS,对于每一个DS:–创建节点C–如果DS为空,节点C标记为DataSet中样本最多的类别–如果DS不为空,节点C=C4.5(DS,featureList-F)–将节点C添加为R的子节点•源码:•C4.5算法优点:–产生的分类规则易于理解–准确率较高。•C4.5算法缺点:–在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。C5.0•思想:加入Boosting算法框架•特点:–更快–内存使用更有效–更小的决策树•商业机密–C5.0教程:–裁剪版:•分类回归树CART(ClassificationandRegressionTrees)–1984ClassificationandRegressionTrees•L.Breiman,J.Friedman,R.Olshen和C.Stone–~breiman/–~jhf/–~olshen/•目标变量是类别的---分类树•目标变量是连续的---回归树CART•二元划分–二叉树不易产生数据碎片,精确度往往也会高于多叉树,所以在CART算法中,采用了二元划分•不纯性度量–分类目标:Gini指标、Towing、orderTowing–连续目标:最小平方残差、最小绝对残差•剪枝:–用独立的验证数据集对训练集生长的树进行剪枝Gini指标(Giniindex)•Gini指标用来度量数据集的不纯度:•Gini越小,数据越纯•CART中计算Gini指标考虑每个属性上的二元划分,根据训练数据集S中的属性F将S分成的S1和S2,则给定划分的Gini指标如下公式所示:•最小化Gini指标21()1CiiiGiniSpSi其中,p是中类别的概率1212||||()()()FSSGiniSGiniSGiniSSS•离散属性outlook={sunny,overcast,rain}•Outlook值的子集有=8个:{},{sunny},{overcast},{rain},{sunny,overcast},{overcast,rain},{sunny,rain},{sunny,overcast,rain}•去除不代表任何分裂的集合:空集{}和全集{sunny,overcast,rain}。则基于Outlook的划分方式有3种:••分别计算每种划分的Gini指标:323(2-2)/2=3,,,({}{}2222,,,){}({})({},)()95=()()1414963523(1(()()))(1(()()))149914550.45710().3571(sunnyovercastrainsunnyovercastrainsunnovercastovercastyrainsunnyrainGiniSGiniSGiniSGiniGiniS划分划分划分0.7)
本文标题:决策树-上-ID3C45CART及剪枝
链接地址:https://www.777doc.com/doc-613655 .html