决策树(完整).ppt

《机器学****周志华第4章决策树第5章神经网络和深度学****第6章支持向量机第8章集成学****第9章聚类关联规则学****1第4章决策树根据训练数据是否拥有标记信息学****任务决策树(decisiontree)模型常常用来解决分类和回归问题。常见的算法包括CART(ClassificationAndRegressionTree)、ID3、。半监督学****输入数据部分被标识,部分没有被标识,介于监督学****与非监督学****之间。分类、回归聚类监督学****supervisedlearning)无监督学****unsupervisedlearning)半监督学****semi-supervisedlearning)强化学****reinforcementlearning)2二分类学****任务属性属性值根结点:包含全部样本叶结点:对应决策结果“好瓜”“坏瓜”内部结点:对应属性测试决策树学****的目的:为了产生一颗泛化能力强的决策树,即处理未见示例能力强。3无需划分无法划分不能划分无需划分无法划分不能划分Hunt算法:41,2,3,4,5,6,8,10,151,2,3,4,56,8,151068,15815第(2)种情形:设定为该结点所含样本最多的类别利用当前结点的后验分布第(3)种情形:设定为其父结点所含样本最多的类别把父结点的样本分布作为当前结点的先验分布5决策树学****的关键是算法的第8行:选择最优划分属性什么样的划分属性是最优的?我们希望决策树的分支结点所包含的样本尽可能属于同一类别,即结点的“纯度”越来越高,可以高效地从根结点到达叶结点,得到决策结果。三种度量结点“纯度”的指标:“信息熵”的概念,解决了对信息的量化度量问题。香农用“信息熵”的概念来描述信源的不确定性。信息熵对于二分类任务7一个事件的信息量就是这个事件发生的概率的负对数。信息熵是跟所有事件的可能性有关的,是平均而言发生一个事件得到的信息量大小。所以信息熵其实是信息量的期望。假设我们已经知道衡量不确定性大小的这个量已经存在了,不妨就叫做“信息量”不会是负数不确定性函数 是概率的单调递减函数;可加性:两个独立符号所产生的不确定性应等于各自不确定性之和,即同时满足这三个条件的函数是负的对数函数,即8信息增益一般而言,信息增益越大,则意味着使用属性a来进行划分所获得的“纯度提升”越大。决策树算法第8行选择属性著名的ID3决策树算法9举例:求解划分根结点的最优划分属性根结点的信息熵:以属性“色泽”为例计算其信息增益数据集包含17个训练样例:8个正例(好瓜)占9个反例(坏瓜)占对于二分类任务10