3决策树学习_机器学习

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2003.11.18,机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏,*,机器学习,第3章 决策树学习,2003.11.18,1,机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏,概论,决策树学习是应,用,用最广的归纳推,理,理算法之一,是一种逼近离散,值,值函数的方法,很好的健壮性,能够学习析取表,达,达式,ID3,Assistant,C4.5,搜索一个完整表,示,示的假设空间,归纳偏置是优先,选,选择较小的树,决策树表示了多,个,个if-then规则,2003.11.18,2,机器学习-决策,树,树学习 译者：,曾,曾华军等 作者,：,：Mitchell 讲者：陶,晓,晓鹏,提纲,决策树定义,适用问题特征,基本ID3算法,决策树学习的归,纳,纳偏置,训练数据的过度,拟,拟合,更深入的话题,2003.11.18,3,机器学习-决策,树,树学习 译者：,曾,曾华军等 作者,：,：Mitchell 讲者：陶,晓,晓鹏,决策树表示法,决策树,通过把实例从根,节,节点排列到某个,叶,叶子节点来分类,实,实例。,叶子节点即为实,例,例所属的分类,树上每个节点说,明,明了对实例的某,个,个属性的测试,节点的每个后继,分,分支对应于该属,性,性的一个可能值,图3-1,决策树代表实例,属,属性值约束的合,取,取的析取式。从,树,树根到树叶的每,一,一条路径对应一,组,组属性测试的合,取,取，树本身对应,这,这些合取的析取,。,。,2003.11.18,4,机器学习-决策,树,树学习 译者：,曾,曾华军等 作者,：,：Mitchell 讲者：陶,晓,晓鹏,决策树学习的适,用,用问题,适用问题的特征,实例由“属性-,值,值”对表示,目标函数具有离,散,散的输出值,可能需要析取的,描,描述,训练数,据,据可以,包,包含错,误,误,训练数,据,据可以,包,包含缺,少,少属性,值,值的实,例,例,问题举,例,例,根据疾,病,病分类,患,患者,根据起,因,因分类,设,设备故,障,障,根据拖,欠,欠支付,的,的可能,性,性分类,贷,贷款申,请,请,分类问,题,题,核心任,务,务是把,样,样例分,类,类到各,可,可能的,离,离散值,对,对应的,类,类别,2003.11.18,5,机器学,习,习-决,策,策树学,习,习 译,者,者：曾,华,华军等,作,作者,：,：Mitchell,讲,讲者,：,：陶晓,鹏,鹏,基本的,决,决策树,学,学习算,法,法,大多数,决,决策树,学,学习算,法,法是一,种,种核心,算,算法的,变,变体,采用自,顶,顶向下,的,的贪婪,搜,搜索遍,历,历可能,的,的决策,树,树空间,ID3,是,是这种,算,算法的,代,代表,2003.11.18,6,机器学,习,习-决,策,策树学,习,习 译,者,者：曾,华,华军等,作,作者,：,：Mitchell,讲,讲者,：,：陶晓,鹏,鹏,基本的,决,决策树,学,学习算,法,法（2,）,）,ID3,的,的思想,自顶向,下,下构造,决,决策树,从“哪,一,一个属,性,性将在,树,树的根,节,节点被,测,测试”,开,开始,使用统,计,计测试,来,来确定,每,每一个,实,实例属,性,性单独,分,分类训,练,练样例,的,的能力,ID3,的,的过程,分类能,力,力最好,的,的属性,被,被选作,树,树的根,节,节点,根节点,的,的每个,可,可能值,产,产生一,个,个分支,训练样,例,例排列,到,到适当,的,的分支,重复上,面,面的过,程,程,2003.11.18,7,机器学,习,习-决,策,策树学,习,习 译,者,者：曾,华,华军等,作,作者,：,：Mitchell,讲,讲者,：,：陶晓,鹏,鹏,表3-1 用,于,于学习,布,布尔函,数,数的ID3算,法,法概要,ID3(Examples,Target_attribute,Attributes),创建树,的,的root节,点,点,如果Examples都为,正,正,返,回,回label=+的,单,单节点,树,树root,如果Examples都为,反,反,返,回,回label=-的,单,单节点,树,树root,如果Attributes,为,为空，,那,那么返,回,回单节,点,点root，label=Examples中,最,最普遍,的,的Target_attribute值,否则开,始,始,A,Attributes,中分类,examples,能力最,好,好的属,性,性,root的决,策,策属性,A,对于A,的,的每个,可,可能值vi,在root下,加,加一个,新,新的分,支,支对应,测,测试A=vi,令Examples,vi,为Examples,中,中满足A属性,值,值为vi的子,集,集,如果Examples,vi,为空,在这个,新,新分支,下,下加一,个,个叶子,节,节点，,节,节点的label=Examples中,最,最普遍,的,的Target_attribute值,否则在,新,新分支,下,下加一,个,个子树ID3,（,（Examples,vi,Target_attribute,Attributes-A）,结束,返回root,2003.11.18,8,机器学,习,习-决,策,策树学,习,习 译,者,者：曾,华,华军等,作,作者,：,：Mitchell,讲,讲者,：,：陶晓,鹏,鹏,最佳分,类,类属性,信息增,益,益,用来衡,量,量给定,的,的属性,区,区分训,练,练样例,的,的能力,ID3,算,算法在,增,增长树,的,的每一,步,步使用,信,信息增,益,益从候,选,选属性,中,中选择,属,属性,用熵度,量,量样例,的,的均一,性,性,熵刻画,了,了任意,样,样例集,的,的纯度,给定包,含,含关于,某,某个目,标,标概念,的,的正反,样,样例的,样,样例集S，那,么,么S相,对,对这个,布,布尔型,分,分类的,熵,熵为,Entropy(S)=-p+log,2,p+-p-log,2,p-,信息论,中,中对熵,的,的一种,解,解释，,熵,熵确定,了,了要编,码,码集合S中任,意,意成员,的,的分类,所,所需要,的,的最少,二,二进制,位,位数,更一般,地,地，如,果,果目标,属,属性具,有,有c个,不,不同的,值,值，那,么,么S相,对,对于c,个,个状态,的,的分类,的,的熵定,义,义为,Entropy(S)=,2003.11.18,9,机器学,习,习-决,策,策树学,习,习 译,者,者：曾,华,华军等,作,作者,：,：Mitchell,讲,讲者,：,：陶晓,鹏,鹏,最佳分,类,类属性,（,（2）,用信息,增,增益度,量,量期望,的,的熵降,低,低,属性的,信,信息增,益,益，由,于,于使用,这,这个属,性,性分割,样,样例而,导,导致的,期,期望熵,降,降低,Gain(S,A),是,是在知,道,道属性A的值,后,后可以,节,节省的,二,二进制,位,位数,例子,2003.11.18,10,机器学,习,习-决,策,策树学,习,习 译,者,者：曾,华,华军等,作,作者,：,：Mitchell,讲,讲者,：,：陶晓,鹏,鹏,ID3,算,算法举,例,例,表3-2,继续这,个,个过程,，,，直到,满,满足以,下,下两个,条,条件中,的,的一个,所有的,属,属性已,经,经被这,条,条路经,包,包括,与这个,节,节点关,联,联的所,有,有训练,样,样例都,具,具有相,同,同的目,标,标属性,值,值,2003.11.18,11,机器学,习,习-决,策,策树学,习,习 译,者,者：曾,华,华军等,作,作者,：,：Mitchell,讲,讲者,：,：陶晓,鹏,鹏,决策树,学,学习中,的,的假设,空,空间搜,索,索,观察ID3的,搜,搜索空,间,间和搜,索,索策略,，,，认识,到,到这个,算,算法的,优,优势和,不,不足,假设空,间,间包含,所,所有的,决,决策树,，,，它是,关,关于现,有,有属性,的,的有限,离,离散值,函,函数的,一,一个完,整,整空间,维护单,一,一的当,前,前假设,（,（不同,于,于第二,章,章的变,型,型空间,候,候选消,除,除算法,）,）,不进行,回,回溯，,可,可能收,敛,敛到局,部,部最优,每一步,使,使用所,有,有的训,练,练样例,，,，不同,于,于基于,单,单独的,训,训练样,例,例递增,作,作出决,定,定，容,错,错性增,强,强,2003.11.18,12,机器学,习,习-决,策,策树学,习,习 译,者,者：曾,华,华军等,作,作者,：,：Mitchell,讲,讲者,：,：陶晓,鹏,鹏,决策树,学,学习的,归,归纳偏,置,置,ID3,的,的搜索,策,策略,优先选,择,择较短,的,的树,选择那,些,些信息,增,增益高,的,的属性,离,离根节,点,点较近,的,的树,很难准,确,确刻画ID3,的,的归纳,偏,偏置,近似的ID3,的,的归纳,偏,偏置,较短的,树,树比较,长,长的树,优,优先,近似在,于,于ID3得到,局,局部最,优,优，而,不,不一定,是,是全局,最,最优,一个精,确,确具有,这,这个归,纳,纳偏置,的,的算法,，,，BFS-ID3,更贴切,近,近似的,归,归纳偏,置,置,较短的,树,树比较,长,长的树,优,优先，,信,信息增,益,益高的,属,属性更,靠,靠近根,节,节点的,树,树优先,2003.11.18,13,机器,学,学习-决,策,策树,学,学习,译,译,者,者：,曾,曾华,军,军等,作,作,者,者：Mitchell,讲,讲,者,者：,陶,陶晓,鹏,鹏,限定,偏,偏置,和,和优,选,选偏,置,置,ID3和,候,候选,消,消除,算,算法,的,的比,较,较,ID3的,搜,搜索,范,范围,是,是一,个,个完,整,整的,假,假设,空,空间,，,，但,不,不彻,底,底地,搜,搜索,这,这个,空,空间,候选,消,消除,算,算法,的,的搜,索,索范,围,围是,不,不完,整,整的,假,假设,空,空间,，,，但,彻,彻底,地,地搜,索,索这,个,个空,间,间,ID3的,归,归纳,偏,偏置,完,完全,是,是搜,索,索策,略,略排,序,序假,设,设的,结,结果,，,，来,自,自搜,索,索策,略,略,候选,消,消除,算,算法,完,完全,是,是假,设,设表,示,示的,表,表达,能,能力,的,的结,果,果，,来,来自,对,对搜,索,索空,间,间的,定,定义,2003.11.18,14,机器,学,学习-决,策,策树,学,学习,译,译,者,者：,曾,曾华,军,军等,作,作,者,者：Mitchell,讲,讲,者,者：,陶,陶晓,鹏,鹏,限定,偏,偏置,和,和优,选,选偏,置,置,优选,偏,偏置,ID3的,归,归纳,偏,偏置,是,是对,某,某种,假,假设,胜,胜过,其,其他,假,假设,的,的一,种,种优,选,选，,对,对最,终,终可,列,列举,的,的假,设,设没,有,有硬,性,性限,制,制,限定,偏,偏置,候选,消,消除,算,算法,的,的偏,置,置是,对,对待,考,考虑,假,假设,的,的一,种,种限,定,定,通常,优,优选,偏,偏置,比,比限,定,定偏,置,置更,符,符合,归,归纳,学,学习,的,的需,要,要,优选,偏,偏置,和,和限,定,定偏,置,置的,结,结合,考虑,第,第1,章,章的,例,例子,2003.11.18,15,机器,学,学习-决,策,策树,学,学习,译,译,者,者：,曾,曾华,军,军等,作,作,者,者：Mitchell,讲,讲,者,者：,陶,陶晓,鹏,鹏,为什,么,么短,的,的假,设,设优,先,先,ID3的,归,归纳,偏,偏置,的,的哲,学,学基,础,础,奥坎,姆,姆剃,刀,刀,优先,选,选择,拟,拟合,数,数据,的,的最,简,简单,的,的假,设,设,科学,上,上的,例,例子,物理,学,学家,优,优先,选,选择,行,行星,运,运动,的,的简,单,单假,设,设,简单,假,假设,的,的数,量,量远,比,比