门户网站代码结构,开原网站开发,梁园区官方网站,上海网上推广决策树的生成与剪枝 决策树的生成生成决策树的过程决策树的生成算法 决策树的剪枝决策树的损失函数决策树的剪枝算法 代码 决策树的生成
生成决策树的过程
为了方便分析描述#xff0c;我们对上节课中的训练样本进行编号#xff0c;每个样本加一个ID值#xff0c;如图所示… 决策树的生成与剪枝 决策树的生成生成决策树的过程决策树的生成算法 决策树的剪枝决策树的损失函数决策树的剪枝算法 代码 决策树的生成
生成决策树的过程
为了方便分析描述我们对上节课中的训练样本进行编号每个样本加一个ID值如图所示 从根结点开始生成决策树先将上述训练样本1-9全部放在根节点中。
然后选择信息增益或信息增益比最大的特征向下分裂按照所选特征取值的不同将训练样本分发到不同的子结点中。
例如所选特征有3个取值则分裂出3个子结点然后在子结点中重复上述过程直到所有特征的信息增益比很小或者没有特征可选为止完成决策树的构建如下图所示 图中的决策树共有2个内部结点和3个叶子结点每个结点旁边的编号代表训练样本的 ID 值。内部结点代表样本的特征叶子结点代表样本的预测类别我们将叶子节点中训练样本占比最大的类作为决策树的预测标记。
在使用构建好的决策树在测试数据上分类时只需要从根节点开始依次测试内部结点代表的特征即可得到测试样本的预测分类。
决策树的生成算法
下面我们先来总结一下 ID3分类决策树的生成算法
输入训练数据集 D 、特征集合 A 的信息增益阈值 输出决策树 T 若 D 中的训练样本属于同一类则 T 为单结点树返回 D 中任意样本的类别。 若 A 中的特征为空则 T 为单结点树返回 D 中数量最多的类别。 使用信息增益在 A 中进行特征选择若所选特征 A_i 的信息增益小于设定的阈值则 T 为单结点树返回 D 中数量最多的类别。 否则根据 A_i 的每一个取值将 D 分成若干子集 D_i将 D_i 中数量最多的类作为标记值构建子结点返回 T。 以 D_i 为训练集{A - A_i} 为特征集递归地调用上述步骤得到子树 T_i返回 T。
使用 C4.5 算法进行决策树的生成只需要将信息增益改成信息增益比即可。
决策树的剪枝
决策树的损失函数
决策树的叶子节点越多模型越复杂。决策树的损失函数考虑了模型复杂度我们可以通过优化其损失函数来对决策树进行剪枝。决策树的损失函数计算过程如下 计算叶子结点 t 的样本类别经验熵 对于叶子结点 t 来说其样本类别的经验熵越小 t 中训练样本的分类误差就越小。当叶子结点 t 中的训练样本为同一类别时经验熵为零分类误差为零。 计算决策树 T 在所有训练样本上的损失之和 C(T) 对于叶子结点 t 中的每一个训练样本其类别标记都是随机变量 Y 的一个取值这个取值的不确定性用信息熵来衡量且可以用经验熵来估计。由上文可知经验熵在一定程度上可以反映决策树在该样本上的预测损失累加所有叶子结点上的训练样本损失即上图中的计算公式。 计算考虑模型复杂度的的决策树损失函数 决策树的叶子结点个数表示模型的复杂度通过最小化上面的损失函数一方面可以减少模型在训练样本上的预测误差另一方面可以控制模型的复杂度保证模型的泛化能力。
决策树的剪枝算法 计算决策树中每个结点的样本类别经验熵 如上图所示对于本课示例中的决策树需要计算 5 个结点的经验熵。 遍历非叶子结点剪枝相当于去除其子结点自身变为叶子结点 对于图中的非叶子结点有工作剪枝后变为叶子结点并通过多数表决的方法确定其类别标记。
以上就是这节课的所有内容了实际上还有一种决策树算法分类与回归树classification and regression tree简称 CART它既可以用于分类也可以用于回归同样包含了特征选择、决策树的生成与剪枝算法。
关于 CART 算法的内容我们将在最后一章 XGBoost 中进行学习下面请你来做一道关于信息增益比的题目顺便回顾一下前面所学的知识
代码
## 1. 创建数据集import pandas as pd
data [[yes, no, 青年, 同意贷款],[yes, no, 青年, 同意贷款],[yes, yes, 中年, 同意贷款],[no, no, 中年, 不同意贷款],[no, no, 青年, 不同意贷款],[no, no, 青年, 不同意贷款],[no, no, 中年, 不同意贷款],[no, no, 中年, 不同意贷款],[no, yes, 中年, 同意贷款]]# 转为 dataframe 格式
df pd.DataFrame(data)
# 设置列名
df.columns [有房, 有工作, 年龄, 类别]## 2. 经验熵的实现from math import log2
from collections import Counter
def H(y):y: 随机变量 y 的一组观测值例如[1,1,0,0,0]# 随机变量 y 取值的概率估计值probs [n/len(y) for n in Counter(y).values()]# 经验熵根据概率值计算信息量的数学期望return sum([-p*log2(p) for p in probs])## 3. 经验条件熵的实现def cond_H(a):a: 根据某个特征的取值分组后的 y 的观测值例如[[1,1,1,0],[0,0,1,1]]每一行表示特征 Aa_i 对应的样本子集# 计算样本总数sample_num sum([len(y) for y in a])# 返回条件概率分布的熵对特征的数学期望return sum([(len(y)/sample_num)*H(y) for y in a])## 4. 特征选择函数
def feature_select(df,feats,label):df训练集数据dataframe 类型feats候选特征集labeldf 中的样本标记名字符串类型# 最佳的特征与对应的信息增益比best_feat,gainR_max None,-1# 遍历每个特征for feat in feats:# 按照特征的取值对样本进行分组并取分组后的样本标记数组group df.groupby(feat)[label].apply(lambda x:x.tolist()).tolist()# 计算该特征的信息增益经验熵-经验条件熵gain H(df[label].values) - cond_H(group)# 计算该特征的信息增益比gainR gain / H(df[feat].values)# 更新最大信息增益比和对应的特征if gainR gainR_max:best_feat,gainR_max feat,gainRreturn best_feat,gainR_max ## 5. 决策树的生成函数
import pickle
def creat_tree(df,feats,label):df训练集数据dataframe 类型feats候选特征集字符串列表labeldf 中的样本标记名字符串类型# 当前候选的特征列表feat_list feats.copy()# 若当前训练数据的样本标记值只有一种if df[label].nunique()1:# 将数据中的任意样本标记返回这里取第一个样本的标记值return df[label].values[0]# 若候选的特征列表为空时if len(feat_list)0:# 返回当前数据样本标记中的众数各类样本标记持平时取第一个return df[label].mode()[0]# 在候选特征集中进行特征选择feat,gain feature_select(df,feat_list,label)# 若选择的特征信息增益太小小于阈值 0.1if gain0.1:# 返回当前数据样本标记中的众数return df[label].mode()[0]# 根据所选特征构建决策树使用字典存储tree {feat:{}}# 根据特征取值对训练样本进行分组g df.groupby(feat)# 用过的特征要移除feat_list.remove(feat)# 遍历特征的每个取值 ifor i in g.groups:# 获取分组数据使用剩下的候选特征集创建子树tree[feat][i] creat_tree(g.get_group(i),feat_list,label)# 存储决策树pickle.dump(tree,open(tree.model,wb))return tree# 6. 决策树的预测函数
def predict(tree,feats,x):tree决策树字典结构feats特征集合字符串列表x测试样本特征向量与 feats 对应# 获取决策树的根结点对应样本特征root next(iter(tree))# 获取该特征在测试样本 x 中的索引i feats.index(root)# 遍历根结点分裂出的每条边对应特征取值for edge in tree[root]:# 若测试样本的特征取值当前边代表的特征取值if x[i]edge:# 获取当前边指向的子结点child tree[root][edge]# 若子结点是字典结构说明是一颗子树if type(child)dict:# 将测试样本划分到子树中继续预测return predict(child,feats,x)# 否则子结点就是叶子节点else:# 返回叶子节点代表的样本预测值return child## 7. 在样例数据上测试# 获取特征名列表
feats list(df.columns[:-1])
# 获取标记名
label df.columns[-1]
# 创建决策树此处使用信息增益比进行特征选择
T creat_tree(df,feats,label)
# 计算训练集上的预测结果
preds [predict(T,feats,x) for x in df[feats].values]
# 计算准确率
acc sum([int(i) for i in (df[label].valuespreds)])/len(preds)
# 输出决策树和准确率
print(T,acc)
文章转载自： http://www.morning.gqjzp.cn.gov.cn.gqjzp.cn http://www.morning.nxnrt.cn.gov.cn.nxnrt.cn http://www.morning.drhnj.cn.gov.cn.drhnj.cn http://www.morning.bpmfl.cn.gov.cn.bpmfl.cn http://www.morning.darwallet.cn.gov.cn.darwallet.cn http://www.morning.tmbtm.cn.gov.cn.tmbtm.cn http://www.morning.hsrpc.cn.gov.cn.hsrpc.cn http://www.morning.sgmis.com.gov.cn.sgmis.com http://www.morning.rpwm.cn.gov.cn.rpwm.cn http://www.morning.zxqqx.cn.gov.cn.zxqqx.cn http://www.morning.rjxwq.cn.gov.cn.rjxwq.cn http://www.morning.dhckp.cn.gov.cn.dhckp.cn http://www.morning.ghwtn.cn.gov.cn.ghwtn.cn http://www.morning.gjqgz.cn.gov.cn.gjqgz.cn http://www.morning.tgbx.cn.gov.cn.tgbx.cn http://www.morning.hqsnt.cn.gov.cn.hqsnt.cn http://www.morning.gjws.cn.gov.cn.gjws.cn http://www.morning.zgdnz.cn.gov.cn.zgdnz.cn http://www.morning.tpwrm.cn.gov.cn.tpwrm.cn http://www.morning.mlpch.cn.gov.cn.mlpch.cn http://www.morning.rysmn.cn.gov.cn.rysmn.cn http://www.morning.jbnss.cn.gov.cn.jbnss.cn http://www.morning.wklyk.cn.gov.cn.wklyk.cn http://www.morning.cpktd.cn.gov.cn.cpktd.cn http://www.morning.yzsdp.cn.gov.cn.yzsdp.cn http://www.morning.xhsxj.cn.gov.cn.xhsxj.cn http://www.morning.gpnwq.cn.gov.cn.gpnwq.cn http://www.morning.dswtz.cn.gov.cn.dswtz.cn http://www.morning.sfnjr.cn.gov.cn.sfnjr.cn http://www.morning.ccsdx.cn.gov.cn.ccsdx.cn http://www.morning.sbqrm.cn.gov.cn.sbqrm.cn http://www.morning.c-ae.cn.gov.cn.c-ae.cn http://www.morning.ldfcb.cn.gov.cn.ldfcb.cn http://www.morning.ydxx123.cn.gov.cn.ydxx123.cn http://www.morning.wqpsf.cn.gov.cn.wqpsf.cn http://www.morning.tkqzr.cn.gov.cn.tkqzr.cn http://www.morning.hlfnh.cn.gov.cn.hlfnh.cn http://www.morning.xckqs.cn.gov.cn.xckqs.cn http://www.morning.jkzjs.cn.gov.cn.jkzjs.cn http://www.morning.phwmj.cn.gov.cn.phwmj.cn http://www.morning.bcjbm.cn.gov.cn.bcjbm.cn http://www.morning.eronghe.com.gov.cn.eronghe.com http://www.morning.rqkzh.cn.gov.cn.rqkzh.cn http://www.morning.kyhnl.cn.gov.cn.kyhnl.cn http://www.morning.bsrqy.cn.gov.cn.bsrqy.cn http://www.morning.wkpfm.cn.gov.cn.wkpfm.cn http://www.morning.znqmh.cn.gov.cn.znqmh.cn http://www.morning.dfrenti.com.gov.cn.dfrenti.com http://www.morning.mkygc.cn.gov.cn.mkygc.cn http://www.morning.pqcbx.cn.gov.cn.pqcbx.cn http://www.morning.rxcqt.cn.gov.cn.rxcqt.cn http://www.morning.zlnf.cn.gov.cn.zlnf.cn http://www.morning.wgzgr.cn.gov.cn.wgzgr.cn http://www.morning.wnbpm.cn.gov.cn.wnbpm.cn http://www.morning.bncrx.cn.gov.cn.bncrx.cn http://www.morning.bzbq.cn.gov.cn.bzbq.cn http://www.morning.yprjy.cn.gov.cn.yprjy.cn http://www.morning.tyjp.cn.gov.cn.tyjp.cn http://www.morning.jkzjs.cn.gov.cn.jkzjs.cn http://www.morning.qnpyz.cn.gov.cn.qnpyz.cn http://www.morning.pflry.cn.gov.cn.pflry.cn http://www.morning.kyhnl.cn.gov.cn.kyhnl.cn http://www.morning.nmfml.cn.gov.cn.nmfml.cn http://www.morning.ptdzm.cn.gov.cn.ptdzm.cn http://www.morning.fwblh.cn.gov.cn.fwblh.cn http://www.morning.krdmn.cn.gov.cn.krdmn.cn http://www.morning.rbktw.cn.gov.cn.rbktw.cn http://www.morning.qzfjl.cn.gov.cn.qzfjl.cn http://www.morning.ygkb.cn.gov.cn.ygkb.cn http://www.morning.rxkq.cn.gov.cn.rxkq.cn http://www.morning.nkllb.cn.gov.cn.nkllb.cn http://www.morning.spsqr.cn.gov.cn.spsqr.cn http://www.morning.qhln.cn.gov.cn.qhln.cn http://www.morning.msgcj.cn.gov.cn.msgcj.cn http://www.morning.nrbqf.cn.gov.cn.nrbqf.cn http://www.morning.mdmqg.cn.gov.cn.mdmqg.cn http://www.morning.dyxlm.cn.gov.cn.dyxlm.cn http://www.morning.srsln.cn.gov.cn.srsln.cn http://www.morning.bklhx.cn.gov.cn.bklhx.cn http://www.morning.xwbwm.cn.gov.cn.xwbwm.cn
