资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,机器学习,周志华,第,4,章 决策树,第,5,章 神经网络和深度学习,第,6,章 支持向量机,第,8,章 集成学习,第,9,章 聚类,关联规则学习,第,4,章 决策树,根据训练数据是否拥有标记信息,学习任务,决策树,（,decision tree,）模型常常用来解决分类和回归问题。常见的算法包括 CART(Classification And Regression Tree)、ID3、C4.5等。,半监督学习：输入数据部分被标识，部分没有被标识，介于监督学习与非监督学习之间。,分类、回归,聚类,监督学习,(supervised learning),无监督学习,(unsupervised learning),半监督学习,(semi-supervised learning),强化学习,(reinforcement learning),二分类学习任务,属性,属性值,根结点：包含全部样本,叶结点：对应决策结果“好瓜”“坏瓜”,内部结点：对应属性测试,决策树学习的目的：为了产生一颗泛化能力强的决策树，即处理未见示例能力强。,无需划分,无法划分,不能划分,无需划分,无法划分,不能划分,Hunt,算法：,1,2,3,4,5,6,8,10,15,1,2,3,4,5,6,8,15,10,6,8,15,8,15,第（,2,）种情形：设定为,该结点,所含样本最多的类别,利用当前结点的,后验分布,第（,3,）种情形：设定为,其父结点,所含样本最多的类别,把父结点的样本分布作为当前结点的,先验分布,决策树学习的关键是算法的第8行：选择最优划分属性,什么样的划分属性是最优的？,我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高，可以高效地从根结点到达叶结点，得到决策结果。,三种度量结点“纯度”的指标：,信息增益,增益率,基尼指数,1.,信息增益,香农提出了“信息熵”的概念，解决了对信息的量化度量问题。,香农用“信息熵”的概念来描述信源的不确定性。,信息熵,对于二分类任务,一个事件的,信息量,就是这个事件发生的概率的负对数。,信息熵,是跟所有事件的可能性有关的，是平均而言发生一个事件得到的信息量大小。所以信息熵其实是信息量的期望。,假设我们已经知道,衡量不确定性大小的,这个量已经存在了，不妨就叫做“,信息量,”,不会是负数,不确定性函数,是概率,的单调递减函数；,可加性：,两个独立符号所产生的不确定性应等于各自不确定性之和，即,同时满足这三个条件的函数,是负的对数函数，即,信息增益,一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。,决策树算法第8行选择属性,著名的,ID3,决策树算法,举例：求解划分根结点的最优划分属性,根结点的信息熵：,以属性“色泽”为例计算其信息增益,数据集包含,17,个训练样例：,8,个正例（好瓜）占,9,个反例（坏瓜）占,对于二分类任务,用“色泽”将根结点划分后获得,3,个分支结点的信息熵分别为：,属性,“,色泽,”,的信息增益为：,若把“编号”也作为一个候选划分属性，则属性“编号”的信息增益为：,根结点的信息熵仍为,：,用“编号”将根结点划分后获得,17,个分支结点的信息熵均为：,则“编号”的信息增益为：,远大于其他候选属性,信息增益准则对可取值数目较多的属性有所偏好,2.,增益率,增益率准则对可取值数目较少的属性有所偏好,著名的,C4.5,决策树算法综合了,信息增益准则,和,信息率准则,的特点：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。,3.,基尼指数,基尼值,基尼指数,著名的,CART,决策树算法,过拟合,：学习器,学习能力过于强大,，把训练样本自身的一些特点当作了所有潜在样本都会具有的一般性质，导致泛化性能下降。,欠拟合,：,学习器学习能力低下，,对训练样本的一般性质尚未学好。,过拟合无法彻底避免，只能做到“缓解”。,剪枝，即通过主动去掉一些分支来降低过拟合的风险。,预剪枝,决策树的剪枝策略,后剪枝,预剪枝,：在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点,后剪枝,：先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。,留出法：将数据集D划分为两个互斥的集合：训练集S和测试集T,且,预剪枝,1,2,3,14,训练集,：,好瓜,坏瓜,1,2,3,6,7,10,14,15,16,17,6,7,15,17,10,16,精度：正确分类的样本占所有样本的比例,4,5,13,(T,T,F),8,9,(T,F),11,12,(T,T),验证集,：,4,5,8,9,11,12,13,不足,：,基于“贪心”本质禁止某些分支展开，带来了欠拟合的风险,预剪枝使得决策树的很多分支都没有“展开”,优点,：,降低过拟合的风险,减少了训练时间开销和测试时间开销,后剪枝,先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。,验证集,：,4,5,8,9,11,12,4,13,(T,F),5,(F),9,(F),8,(F),11,12,(T,T),验证集精度：,考察结点顺序：,6,7,15,17,6,7,15,17,6,7,15,7,15,8,9,(T,F),减去结点,验证集变为：,训练集,：,好瓜,坏瓜,1,2,3,6,7,10,14,15,16,17,后剪枝,决策树,预剪枝,决策树,保留了更多的分支,欠拟合风险很小,泛化能力优于预剪枝决策树,训练时间开销比,未减枝和预剪枝,决策树大得多,生产完全决策树,所有非叶节点逐一考察,知识回顾：,四类学习任务,Hunt,算法,3,种递归返回情形、第,8,行,3,种度量结点“纯度”的指标：,信息增益,ID3,增益率,C4.5,基尼指数,CART,过拟合、欠拟合,决策树剪枝,预剪枝,后剪枝,离散属性：脐部 根蒂 色泽,连续属性：密度 含糖率,连续属性离散化技术：二分法,C4.5,决策树算法,样本集,连续属性,，有,n,个不同的取值，将,n,个取值从小到大排序：,划分点,t,（数值）,将,划分为两个子集,和,显然，对相邻的属性取值,来说，,t,在区间,中取任意值所产生的划分结果都相同,根结点的信息熵仍为,：,根结点包含,17,个训练样本，密度有,17,个不同取值,候选划分点集合包含,16,个候选值,每一个划分点能得到一个对应的信息增益,选择“纹理”作为根结点划分属性,与离散属性不同，若当前结点划分属性为连续属性，该连续属性还可被再次选作后代结点的最优划分属性。,现实任务中，,尤其在属性数目较多时,，存在大量样本出现缺失值。,出于成本和隐私的考虑,属性值缺失,时，如何,进行划分属性选择？,（如何计算信息增益）,给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？,（对于缺失属性值的样本如何将它从父结点划分到子结点中）,训练集,训练集中在属性,a,上没有缺失值的样本子集,被属性,a,划分后的样本子集,中属于第,k,类的样本子集,无缺失值样本中在属性,上取值,的样本,所占比例,无缺失值样本,所占比例,无缺失值样本中第,k,类所占比例,无缺失值的样本子集,上的信息增益,对于问题,2,：,对于有缺失值的样本如何将它从父结点划分到子结点中,若样本,在划分属性,a,上的取值已知，则将,划入,与其取值对应的子结点,，且样本权值在子结点中保持为,若样本,在划分属性,a,上的取值未知，则将,同时划入,所有子结点,，且样本权值在子结点中调整为,，就是让同一个样本以不同的概率划入不同的子结点中。,其中，,是为每个样本,赋予的一个权重,运用,：,问题,1属性值缺失,时，如何,进行划分属性选择？,=属性值缺失,时，如何计算缺失属性的信息增益？,无缺失值样本中在属性,上取值,的样本,所占比例,无缺失值样本中第,k,类所占比例,根结点包含样本集,中全部,17,个样本,属性“色泽”无缺失值的样例子集,包含,14,个样例：,好瓜,(6,个,),坏瓜,(8,个,),无缺失值样本,所占比例,无缺失值样本中在属性,上取值,的样本,所占比例,无缺失值样本,所占比例,“纹理”被用于对根结点进行划分,问题,2,给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？,样本划分原则：,属性,值已知，,划入与其取值对应的子结点，样本权值不变，仍为,属性,值未知，划入所有子结点,，样本权值调整为,，让同一个样本以不同的概率划入不同的子结点中,无缺失值样本中在属性,上取值,的样本,所占比例,“纹理”属性值缺失的样本编号为：,8,10,权值为：,8,和,10,同时进入三个分支中，权值分别为：,0.381,0.205,每个属性,d,个属性描述的样本,对样本分类,坐标空间中的一个坐标轴,d,维空间中的一个数据点,在坐标空间中寻找不同类样本之间的分类边界,决策树形成的分类边界的明显特点：轴平行，分类边界由若干个与坐标轴平行的分段组成。,优点：,学习结果解释性强，每个划分都对应一个属性取值,2,个属性,二维平面,不足：,可以从该结点所含的样本集,D,和属性集,A,上学得,
展开阅读全文