机器学习入门机器学习入门 (25).pdf

《机器学习入门机器学习入门 (25).pdf》由会员分享，可在线阅读，更多相关《机器学习入门机器学习入门 (25).pdf（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、决策树的基本流程和划分2.1 决策树的基本流程输入：过程：函数函数TreeGenerate(D,A)1:生成结点生成结点node;2:if D中样本全属于同一类别中样本全属于同一类别C then 3:将将node标记为标记为C类叶结点类叶结点return4:end if 5:if A=0 OR D中样本在中样本在A上取值相同上取值相同then6:将将node标记为叶结点，其类别标记为标记为叶结点，其类别标记为D中样本数最多的类中样本数最多的类;return 7:end if 8:从从A中选择最优划分属性中选择最优划分属性a*;9:for a*的每一个值的每一个值do 10:为为node生成一个

2、分支生成一个分支;令令Dv表示表示D中在中在a*上取值为的样本子集上取值为的样本子集;11:if Dv为空为空then12:将分支结点标记为叶结点，其类别标记为将分支结点标记为叶结点，其类别标记为D中样本最多的类中样本最多的类;return 13:else 14:以以TreeGenerate(Dv,A *)为分支结点为分支结点15:end if 16:end for 输出：流程来自周志华教授机器学习训练集训练集D=(X1,Y1),(X2,Y2),.,(Xm,Ym);属性集属性集A=a1,a2,.,ad.以以node为根结点的一棵决策树为根结点的一棵决策树何为最优？2.2 量化纯度Gini系数G

3、ini系数熵（Entropy）熵（Entropy）错误率错误率2.2 量化纯度-熵2.3 信息熵和信息增益信息熵(information entropy)是度量样本集合纯度信息熵(information entropy)是度量样本集合纯度最常用的一种指标.假定当前样本集合D中第k类样本最常用的一种指标.假定当前样本集合D中第k类样本所占的比例为Pk(k=1,2,.,|Y|)，则D的信息熵所占的比例为Pk(k=1,2,.,|Y|)，则D的信息熵定义为定义为Ent(D)的值越小，则D的纯度越高Ent(D)的值越小，则D的纯度越高2.3 信息熵和信息增益假定离散属性a有V个可能的取值，若使用a来假定

4、离散属性a有V个可能的取值，若使用a来对样本集D进行划分，则会产生V个分支结点，其中第v个分支对样本集D进行划分，则会产生V个分支结点，其中第v个分支结点包含了D中所有在属性a上取值为a v的样本,记为Dv结点包含了D中所有在属性a上取值为a v的样本,记为Dv根据信息熵定义公式计算出Dv的信息熵,再考虑到不同的分支根据信息熵定义公式计算出Dv的信息熵,再考虑到不同的分支结点所包含的样本数不同,给分支结点赋予权重|Dv|/|D|，结点所包含的样本数不同,给分支结点赋予权重|Dv|/|D|，即样本数越多的分支结点的影响越大，于是可计算出用属性a即样本数越多的分支结点的影响越大，于是可计算出用属性

5、a对样本集D进行划分所获得的信息增益(information 对样本集D进行划分所获得的信息增益(information gain)gain)2.3 信息熵和信息增益一般而言，信息增益越大，则意味着使用属性a来进行划分所一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。因此，我们可用信息增益来进行获得的“纯度提升”越大。因此，我们可用信息增益来进行决策树的划分属性选择，即在决策树算法第8行选择属性决策树的划分属性选择，即在决策树算法第8行选择属性2.4 决策树案例可知：可知：1、|Y|=21、|Y|=22、其中正例2、其中正例占P1=8/17占P1=8/173、反例

6、占3、反例占P2=9/17P2=9/17可计算出根节点可计算出根节点的信息熵为的信息熵为案例来自周志华教授机器学习2.4 决策树案例按色泽计算，其子集为:按色泽计算，其子集为:1、D1青绿包含编号为1,4,6,10,13,17的6个样例，其中正例1、D1青绿包含编号为1,4,6,10,13,17的6个样例，其中正例占p1=3/6，反例占的p2=3/6占p1=3/6，反例占的p2=3/62、D2乌黑包含编号为2,3,7,8,9,156个样例，其中正、反例2、D2乌黑包含编号为2,3,7,8,9,156个样例，其中正、反例分别占Pl=4/6，P2=2/6分别占Pl=4/6，P2=2/63、D3浅白

7、包含编号为5,11,12,14,165个样例，其中正、反例3、D3浅白包含编号为5,11,12,14,165个样例，其中正、反例分别占pl=1/5，p2=4/5分别占pl=1/5，p2=4/5计算得3个分支结点的信息熵为计算得3个分支结点的信息熵为2.4 决策树案例计算出属性色泽的信息增益为:计算出属性色泽的信息增益为:同样可计算出其他属性的信息增益:同样可计算出其他属性的信息增益:2.4 决策树案例基于纹理属性对根结点划分基于纹理属性对根结点划分2.4 决策树案例结点包含的样例集合D1中有编号为1,2,3,4,5,结点包含的样例集合D1中有编号为1,2,3,4,5,6,8,10,15的9个样

8、例，可用属性集合为色泽，6,8,10,15的9个样例，可用属性集合为色泽，根蒂，敲声，脐部，触感根蒂，敲声，脐部，触感基于D1计算出各属性的信息增益:基于D1计算出各属性的信息增益:2.4 决策树案例最终得到的决策树如下：最终得到的决策树如下：2.5 决策树停止条件决策树的构建过程是一个递归的过程，所以需要确定决策树的构建过程是一个递归的过程，所以需要确定停止条件，否则过程将不会结束停止条件，否则过程将不会结束一种最直观的方式是当每个子节点只有一种类型的记一种最直观的方式是当每个子节点只有一种类型的记录时停止;录时停止;另一种可行的方法是当前节点中的记录数低于一个最另一种可行的方法是当前节点中的记录数低于一个最小的阀值，那么就停止分割，将max(P(i)对应的分小的阀值，那么就停止分割，将max(P(i)对应的分类作为当前叶节点的分类类作为当前叶节点的分类2.6 有些属性假如把“编号”也作为一个候选划分属性假如把“编号”也作为一个候选划分属性编号的信息增益为0.998