资源描述：
《机器学习决策树学习.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第1.2节决策树学习(DecisionTree)内容决策树的基本原理和算法熵、信息增益和特征选择决策树学习中的过拟合问题交叉验证与树的修剪内容决策树的基本原理和算法熵、信息增益和特征选择决策树学习中的过拟合问题交叉验证与树的修剪决策树学习——决定是否打网球看看天气看看湿度阳光明媚下雨看看风速高正常不去打球去打球大小不去打球去打球节点：每一个节点测试一个特征,分支：特征的可选数值（此处为离散值）叶子节点：最终预测去打球阴天基本的决策树学习算法—(ID3,C4.5)node=root循环{1.为当下一个节点选择一个最好的属性x2.将属性x分配给节点node3.对于x的所有可能数值，
2、创建一个降序排列的节点node4.将所有训练样本在叶子节点排序分类5.如果分类结果达到了错误率要求，跳出循环，否则，在叶子节点开始新循环-〉递归}决策树学习的适用问题适用问题的特征实例由“特征-值”对表示目标函数具有离散的输出值训练数据可以包含一定的错误训练数据可以包含缺少特征值的实例问题举例根据天气好坏确定是否去打球根据疾病分类患者根据起因分类设备故障根据拖欠支付的可能性分类贷款申请分类问题核心任务是把样例分类到各可能的离散值对应的类别基本的决策树学习算法—(ID3,C4.5)ID3的思想自顶向下构造决策树从“哪一个特征将在树的根节点被测试”开始使用统计测试来确定每一个实例特
3、征单独分类训练样例的能力ID3的过程分类能力最好的特征被选作树的根节点根节点的每个可能值产生一个分支训练样例排列到适当的分支重复上面的过程基本的决策树学习算法—(ID3,C4.5)编号天气温度湿度风是否去打球1晴天炎热高弱不去2晴天炎热高强不去3阴天炎热高弱去4下雨适中高弱去5下雨寒冷正常弱去6下雨寒冷正常强不去7阴天寒冷正常强去8晴天适中高弱不去9晴天寒冷正常弱去10下雨适中正常弱去11晴天适中正常强去12阴天适中高强去13阴天炎热正常弱去14下雨适中高强不去表-1：是否去打球的数据统计—训练数据决策树学习原理简介—(ID3,C4.5算法)湿度高正常(3+,4-)(6+,1-
4、)S:(9+,5-)风弱强(6+,2-)(3+,3-)S:(9+,5-)问题：哪一个属性（特征）更好？内容决策树的基本原理和算法熵、信息增益和特征选择决策树学习中的过拟合问题交叉验证与树的修剪熵:物理学概念?宏观上：热力学定律—体系的熵变等于可逆过程吸收或耗散的热量除以它的绝对温度（克劳修斯，1865）?微观上：熵是大量微观粒子的位置和速度的分布概率的函数，是描述系统中大量微观粒子的无序性的宏观参数（波尔兹曼，1872）?结论：熵是描述事物无序性的参数，熵越大则无序性越强,在信息领域定义为“熵越大，不确定性越大”（香浓，1948年）熵随机变量的熵熵比较多的用于信源编码，数据压缩
5、，假设是最有效的编码方式是使用位编码于是对于随即变量的最有效编码位之和：熵熵表示训练集合中的样本表示训练集合中反例样本的比例表示训练集合中正例样本的比例表示训练集合的熵信息增益(InformationGain)信息的增加意味着不确定性的减少，也就是熵的减小；信息增益在诸多系统中定义为：在某一个操作之前的系统熵与操作之后的系统熵的差值也即是不确定性的减小量信息增益(InformationGain)原来的不确定性知道x之后的不确定性信息增益:原来-知道x之后的原来不确定性-经过属性x划分以后的不确定性信息增益(InformationGain)选择特征的标准：选择具有最大信息增益(I
6、nformationGain)的特征假设有两个类,+和-假设集合S中含有p个类别为+的样本,n个类别为-的样本将S中已知样本进行分类所需要的期望信息定义为:假设特征x将把集合S划分成K份{S1,S2,…,SK}如果Si中包含pi个类别为“+”的样本,ni个类别为“-”,的样本。那么划分后的熵就是：在x上进行决策分枝所获得的信息增益为:信息增益(InformationGain)信息增益(InformationGain)表示给定特征后不确定性的减少，即信息增益表示了特征与数据集合的互信息问题：哪一个属性（特征）更好？分析极端的情况温度高正常(4+,4-)(4+,4-)S:(8+,8
7、-)心情好坏(8+,0-)(0+,8-)S:(8+,8-)E=1.0E=0.0E=0.0Gain(S,温度）=1.0-（8/16)*1.0-（8/16）*1.0=0.0Gain(S,心情）=1.0-(8/16)*0.0-(8/16)*0.0=1.0E=1.0E=1.0信息增益(InformationGain)湿度高正常(3+,4-)(6+,1-)S:(9+,5-)风弱强(6+,2-)(3+,3-)S:(9+,5-)问题：哪一个属性（特征）更好？I=0.985I=0.592I=0.811I=1
