(41)--ch2决策树模式识别.pdf
决策树方法引言引言决策树原理决策树原理决策树决策树ID3ID3方法构建方法构建过学习与剪枝过学习与剪枝随机森林随机森林主要内容引言引言 决策树学习决策树学习 有监督有监督学习 属性为离散值离散值 应用广泛 表示为if if-thenthen规则引言引言 决策树的结构决策树的结构引言引言 决策树分类决策树分类 训练阶段训练阶段从给定的训练数据集DB，构造出一棵决策树=()分类阶段分类阶段从根开始按照决策树的分类属性逐层往下划分，直到叶节点，获得分类结果=()引言引言 决策树举例决策树举例引言引言 决策树举例决策树举例引言引言 决策树举例决策树举例引言引言 决策树举例决策树举例决策树原理决策树原理 基本算法基本算法 贪心算法贪心算法 自上而下自上而下 开始时所有数据所有数据在根节点根节点 选择某属性某属性对样本进行划分决策树原理决策树原理 中止条件：中止条件：一个节点上的数据属于同一个类别同一个类别 没有属性没有属性可以再用于分割决策树原理决策树原理 算法过程算法过程1 Samples=1,2,3,4,5,6,7,8,9,101 Samples=1,2,3,4,5,6,7,8,9,10Attribute_listAttribute_list=颜色，形状，尺寸颜色，形状，尺寸 Samples=1,4,7Samples=1,4,7决策树原理决策树原理 算法过程算法过程2 Samples=2,3,5,6,8,9,102 Samples=2,3,5,6,8,9,10Attribute_listAttribute_list=形状，尺寸形状，尺寸 Samples=2,6,9Samples=2,6,9决策树原理决策树原理 算法过程算法过程2 Samples=3,5,8,102 Samples=3,5,8,10Attribute_listAttribute_list=尺寸尺寸 决策树原理决策树原理 算法过程算法过程2 Samples=3,8,5,102 Samples=3,8,5,10Attribute_listAttribute_list=决策树原理决策树原理 算法过程算法过程1,4,71,4,72,6,92,6,93,83,85,105,10本节结束本节结束决策树方法引言引言决策树原理决策树原理ID3ID3方法方法过学习与剪枝过学习与剪枝随机森林随机森林主要内容ID3ID3方法方法 信息熵（信息熵（EntropyEntropy）熵熵：描述物质系统状态 平均信息量平均信息量：系统中存在事件事件,每个事件出现的概率概率,=ID3ID3方法方法 系统越无序无序越混乱混乱熵越大大 结点的类值均匀分布均匀分布结点熵最大最大 结点上的数据类值相同类值相同结点熵最小最小ID3ID3方法方法 选择一个属性，使子结点数据类值相同类值相同 通过分裂，得到尽可能纯尽可能纯的结点 降低系统熵降低系统熵ID3ID3方法方法 信息增益信息增益 属性属性对于数据集数据集的信息增益信息增益(,),=()ID3ID3方法方法 天气数据天气数据 是否打网球是否打网球OutlookTemperatureHumidityWindyPlay?sunnyhothighfalseNosunnyhothightrueNoovercasthothighfalseYesrainmildhighfalseYesraincoolnormalfalseYesraincoolnormaltrueNoovercastcoolnormaltrueYessunnymildhighfalseNosunnycoolnormalfalseYesrainmildnormalfalseYessunnymildnormaltrueYesovercastmildhightrueYesovercasthotnormalfalseYesrainmildhightrueNoID3ID3方法方法 算法步骤算法步骤（1 1）计算样本集的信息熵）计算样本集的信息熵9 9个YesYes，5 5个NoNo,=loglog=.ID3ID3方法方法ID3ID3方法方法 算法步骤算法步骤（2 2）以）以outlookoutlook属性为例属性为例sunny sunny ,overcast overcast (,)rain rain (,)ID3ID3方法方法 算法步骤算法步骤（3 3）计算信息增益）计算信息增益,=.,+,+,=.ID3ID3方法方法 算法步骤算法步骤（4 4）依次计算每个属性的信息增益）依次计算每个属性的信息增益 =0.247 =0.029 =0.152 =0.048 ID3ID3方法方法 算法步骤算法步骤（5 5）选择获得最大信息增益的属性）选择获得最大信息增益的属性 =0.247 ID3ID3方法方法 算法步骤算法步骤（5 5）选择获得最大信息增益的属性）选择获得最大信息增益的属性 =0.247 ID3ID3方法方法 算法步骤算法步骤（6 6）以此类推，继续划分）以此类推，继续划分当天气为晴天气为晴的时，其他属性产生增益为：=.=.=.ID3ID3方法方法 算法步骤算法步骤（6 6）以此类推，继续划分）以此类推，继续划分ID3ID3方法方法 算法步骤算法步骤（6 6）以此类推，继续划分）以此类推，继续划分ID3ID3方法方法 算法步骤算法步骤（7 7）当所有叶结点是）当所有叶结点是纯的纯的，划分过程终止，划分过程终止理想情况可能无法达到当数据不可进一步划分终止ID3ID3方法方法OutlookTemperatureHumidityWindyPlay?sunnyhothighfalseNosunnyhothightrueNoovercasthothighfalseYesrainmildhighfalseYesraincoolnormalfalseYesraincoolnormaltrueNoovercastcoolnormaltrueYessunnymildhighfalseNosunnycoolnormalfalseYesrainmildnormalfalseYessunnymildnormaltrueYesovercastmildhightrueYesovercasthotnormalfalseYesrainmildhightrueNoovercasthighnormalfalsetruesunnyrainNoNoYesYesYesOutlookHumidityWindyID3ID3方法方法 算法特点算法特点 未未搜索整个空间 找到第一棵可接受可接受的树 优先选择复杂度小复杂度小的树 算法不回溯不回溯本节结束本节结束决策树方法引言引言决策树原理决策树原理ID3ID3方法方法过学习与剪枝过学习与剪枝随机森林随机森林主要内容过学习与剪枝过学习与剪枝 也叫过拟合问题（过拟合问题（OverOver-fittingfitting）训练数据少训练数据少不能覆盖真实分布 影响分类模型的泛化能力泛化能力 决策树节点过多节点过多、分支过深分支过深过学习与剪枝过学习与剪枝 解决方法解决方法：剪枝（剪枝（PrunningPrunning）先剪枝先剪枝：控制控制决策树生长 后剪枝后剪枝：允许允许决策树过拟合生长，之后进行修剪修剪过学习与剪枝过学习与剪枝 先剪枝先剪枝 数据划分法数据划分法 阈值法阈值法 信息增益的统计显著性分析信息增益的统计显著性分析过学习与剪枝过学习与剪枝 后剪枝后剪枝 减少分类错误修剪法减少分类错误修剪法 最小代价与复杂性的折中最小代价与复杂性的折中 最小描述长度准则最小描述长度准则随机森林随机森林 数据具有随机性随机性 决策树算法更容易受到影响 过拟合过拟合 利用自举（自举（BootstrapBootstrap）思想 随机构建一个决策树的“森林森林”（Random ForestsRandom Forests）随机森林随机森林 基本步骤：基本步骤：（1）对训练集进行自举重采样自举重采样 N N个个子训练集（2）对每个子训练集每个子训练集构建一棵决策树（mm个特征个特征）（3）对“森林”“森林”的决策结果进行投票投票随机森林随机森林本章结束本章结束
