乐山做网站,怎么成立网站,怎么在小程序里开店铺,wordpress创建子主题第1关#xff1a;什么是决策树
任务描述
本关任务#xff1a;根据本节课所学知识完成本关所设置的选择题。
相关知识
为了完成本关任务#xff0c;你需要掌握决策树的相关基础知识。
引例
在炎热的夏天#xff0c;没有什么比冰镇后的西瓜更能令人感到心旷神怡的了。现…第1关什么是决策树
任务描述
本关任务根据本节课所学知识完成本关所设置的选择题。
相关知识
为了完成本关任务你需要掌握决策树的相关基础知识。
引例
在炎热的夏天没有什么比冰镇后的西瓜更能令人感到心旷神怡的了。现在我要去水果店买西瓜但什么样的西瓜能入我法眼呢那根据我的个人习惯在挑西瓜时可能就有这样的脑回路。 假设现在水果店里有3个西瓜它们的属性如下
编号瓤是否够红够不够冰是否便宜是否有籽1是否是否2是是否是3否是是否
那么根据我的脑回路我会买1和2号西瓜。
其实我的脑回路可以看成一棵树并且这棵树能够帮助我对买不买西瓜这件事做决策所以它就是一棵决策树。
决策树的相关概念
决策树是一种可以用于分类与回归的机器学习算法但主要用于分类。用于分类的决策树是一种描述对实例进行分类的树形结构。决策树由结点和边组成其中结点分为内部结点和叶子结点内部结点表示一个特征或者属性叶子结点表示标签脑回路图中黄色的是内部结点蓝色的是叶子结点。
从代码角度来看决策树其实可以看成是一堆if-else语句的集合例如引例中的决策树完全可以看成是如下代码 if isRed:if isCold:if hasSeed:print(buy)else:print(dont buy)else:if isCheap:print(buy)else:print(dont buy)else:print(dont buy)
因此决策树的一个非常大的优势就是模型的可理解性非常高甚至可以用来挖掘数据中比较重要的信息。
那么如何构造出一棵好的决策树呢其实构造决策树时会遵循一个指标有的是按照信息增益来构建如ID3算法有的是信息增益率来构建如C4.5算法有的是按照基尼系数来构建的如CART算法。但不管是使用哪种构建算法决策树的构建过程通常都是一个递归选择最优特征并根据特征对训练集进行分割使得对各个子数据集有一个最好的分类的过程。
这一过程对应着对特征空间的划分也对应着决策树的构建。一开始构建决策树的根结点将所有训练数据都放在根结点。选择一个最优特征并按照这一特征将训练数据集分割成子集使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类那么构建叶子结点并将这些子集分到所对应的叶结点中去如果还有子集不能被基本正确分类那么就对这些子集选择新的最优特征继续对其进行分割并构建相应的结点。如此递归进行下去直至所有训练数据子集被基本正确分类或者没有合适的特征为止。最后每个子集都被分到叶子结点上即都有了明确的类别。这就构建出了一棵决策树。
编程要求
根据本关所学习到的知识完成所有选择题。
测试说明
平台会对你的选项进行判断如果实际输出结果与预期结果相同则通关反之则 GameOver。
1、下列说法正确的是A、B)A、训练决策树的过程就是构建决策树的过程B、ID3算法是根据信息增益来构建决策树C、C4.5算法是根据基尼系数来构建决策树D、决策树模型的可理解性不高2、下列说法错误的是(A)A、从树的根节点开始根据特征的值一步一步走到叶子节点的过程是决策树做决策的过程B、决策树只能是一棵二叉树C、根节点所代表的特征是最优特征 第2关信息熵与信息增益
任务描述
本关任务掌握什么是信息增益完成计算信息增益的程序设计。
相关知识
为了完成本关任务你需要掌握 信息熵 条件熵 信息增益。
信息熵
信息是个很抽象的概念。人们常常说信息很多或者信息较少但却很难说清楚信息到底有多少。比如一本五十万字的中文书到底有多少信息量。
直到1948年香农提出了“信息熵”的概念才解决了对信息的量化度量问题。信息熵这个词是香农从热力学中借用过来的。热力学中的热熵是表示分子状态混乱程度的物理量。香农用信息熵的概念来描述信源的不确定度。信源的不确定性越大信息熵也越大。
从机器学习的角度来看信息熵表示的是信息量的期望值。如果数据集中的数据需要被分成多个类别则信息量I(xi)的定义如下(其中xi表示多个类别中的第i个类别p(xi)数据集中类别为xi的数据在数据集中出现的概率表示)
I(Xi)−log2p(xi)
由于信息熵是信息量的期望值所以信息熵H(X)的定义如下(其中n为数据集中类别的数量)
H(X)−sumi1np(xi)log2p(xi)
从这个公式也可以看出如果概率是0或者是1的时候熵就是0因为这种情况下随机变量的不确定性是最低的。那如果概率是0.5也就是五五开的时候此时熵达到最大也就是1。就像扔硬币你永远都猜不透你下次扔到的是正面还是反面所以它的不确定性非常高。所以呢熵越大不确定性就越高。
条件熵
在实际的场景中我们可能需要研究数据集中某个特征等于某个值时的信息熵等于多少这个时候就需要用到条件熵。条件熵H(Y|X)表示特征X为某个值的条件下类别为Y的熵。条件熵的计算公式如下
H(Y∣X)sumi1npiH(Y∣Xxi)
当然条件熵的性质也和熵的性质一样概率越确定条件熵就越小概率越五五开条件熵就越大。
信息增益
现在已经知道了什么是熵什么是条件熵。接下来就可以看看什么是信息增益了。所谓的信息增益就是表示我已知条件X后能得到信息Y的不确定性的减少程度。
就好比我在玩读心术。你心里想一件东西我来猜。我已开始什么都没问你我要猜的话肯定是瞎猜。这个时候我的熵就非常高。然后我接下来我会去试着问你是非题当我问了是非题之后我就能减小猜测你心中想到的东西的范围这样其实就是减小了我的熵。那么我熵的减小程度就是我的信息增益。
所以信息增益如果套上机器学习的话就是如果把特征A对训练集D的信息增益记为g(D, A)的话那么g(D, A)的计算公式就是
g(D,A)H(D)−H(D,A)
为了更好的解释熵条件熵信息增益的计算过程下面通过示例来描述。假设我现在有这一个数据集第一列是编号第二列是性别第三列是活跃度第四列是客户是否流失的标签0表示未流失1表示流失。
编号性别活跃度是否流失1男高02女中03男低14女高05男高06男中07男中18女中09女低110女中011女高012男低113女低114男高015男高0
假如要算性别和活跃度这两个特征的信息增益的话首先要先算总的熵和条件熵。总的熵其实非常好算就是把标签作为随机变量X。上表中标签只有两种0和1因此随机变量X的取值只有0或者1。所以要计算熵就需要先分别计算标签为0的概率和标签为1的概率。从表中能看出标签为0的数据有10条所以标签为0的概率等于2/3。标签为1的概率为1/3。所以熵为
−(1/3)∗log(1/3)−(2/3)∗log(2/3)0.9182
接下来就是条件熵的计算以性别为男的熵为例。表格中性别为男的数据有8条这8条数据中有3条数据的标签为1有5条数据的标签为0。所以根据条件熵的计算公式能够得出该条件熵为
−(3/8)∗log(3/8)−(5/8)∗log(5/8)0.9543
根据上述的计算方法可知总熵为
−(5/15)∗log(5/15)−(10/15)∗log(10/15)0.9182
性别为男的熵为
−(3/8)∗log(3/8)−(5/8)∗log(5/8)0.9543
性别为女的熵为
−(2/7)∗log(2/7)−(5/7)∗log(5/7)0.8631
活跃度为低的熵为
−(4/4)∗log(4/4)−00
活跃度为中的熵为
−(1/5)∗log(1/5)−(4/5)∗log(4/5)0.7219
活跃度为高的熵为
−0−(6/6)∗log(6/6)0
现在有了总的熵和条件熵之后就能算出性别和活跃度这两个特征的信息增益了。
**性别的信息增益总的熵-(8/15)性别为男的熵-(7/15)性别为女的熵0.0064
**活跃度的信息增益总的熵-(6/15)*活跃度为高的熵-(5/15)活跃度为中的熵-(4/15)活跃度为低的熵0.6776
那信息增益算出来之后有什么意义呢回到读心术的问题为了我能更加准确的猜出你心中所想我肯定是问的问题越好就能猜得越准换句话来说我肯定是要想出一个信息增益最大减少不确定性程度最高的问题来问你。其实ID3算法也是这么想的。ID3算法的思想是从训练集D中计算每个特征的信息增益然后看哪个最大就选哪个作为当前结点。然后继续重复刚刚的步骤来构建决策树。
编程要求
根据提示在右侧编辑器补充代码完成calcInfoGain函数实现计算信息增益。
calcInfoGain函数中的参数: feature测试用例中字典里的feature类型为ndarray label测试用例中字典里的label类型为ndarray index测试用例中字典里的index即feature部分特征列的索引。该索引指的是feature中第几个特征如index:0表示使用第一个特征来计算信息增益。
测试说明
平台会对你编写的代码进行测试期望您的代码根据输入来输出正确的信息增益以下为其中一个测试用例
测试输入 {feature:[[0, 1], [1, 0], [1, 2], [0, 0], [1, 1]], label:[0, 1, 0, 0, 1], index: 0}
预期输出 0.419973
提示 计算log可以使用NumPy中的log2函数
import numpy as npdef calcInfoGain(feature, label, index):计算信息增益:param feature:测试用例中字典里的feature类型为ndarray:param label:测试用例中字典里的label类型为ndarray:param index:测试用例中字典里的index即feature部分特征列的索引。该索引指的是feature中第几个特征如index:0表示使用第一个特征来计算信息增益。:return:信息增益类型float #*********** Begin ***********## 计算熵def calcInfoEntropy(feature, label):计算信息熵:param feature:数据集中的特征类型为ndarray:param label:数据集中的标签类型为ndarray:return:信息熵类型floatlabel_set set(label)result 0for l in label_set:count 0for j in range(len(label)):if label[j] l:count 1# 计算标签在数据集中出现的概率p count / len(label)# 计算熵result - p * np.log2(p)return result# 计算条件熵def calcHDA(feature, label, index, value):计算信息熵:param feature:数据集中的特征类型为ndarray:param label:数据集中的标签类型为ndarray:param index:需要使用的特征列索引类型为int:param value:index所表示的特征列中需要考察的特征值类型为int:return:信息熵类型floatcount 0# sub_feature和sub_label表示根据特征列和特征值分割出的子数据集中的特征和标签sub_feature []sub_label []for i in range(len(feature)):if feature[i][index] value:count 1sub_feature.append(feature[i])sub_label.append(label[i])pHA count / len(feature)e calcInfoEntropy(sub_feature, sub_label)return pHA * ebase_e calcInfoEntropy(feature, label)f np.array(feature)# 得到指定特征列的值的集合f_set set(f[:, index])sum_HDA 0# 计算条件熵for value in f_set:sum_HDA calcHDA(feature, label, index, value)# 计算信息增益return base_e - sum_HDA#*********** End *************#
第3关使用ID3算法构建决策树
任务描述
本关任务补充python代码完成DecisionTree类中的fit和predict函数。
相关知识
为了完成本关任务你需要掌握 ID3算法构造决策树的流程 如何使用构造好的决策树进行预测。
ID3算法
ID3算法其实就是依据特征的信息增益来构建树的。其大致步骤就是从根结点开始对结点计算所有可能的特征的信息增益然后选择信息增益最大的特征作为结点的特征由该特征的不同取值建立子结点然后对子结点递归执行上述的步骤直到信息增益很小或者没有特征可以继续选择为止。
因此ID3算法伪代码如下 #假设数据集为D标签集为A需要构造的决策树为treedef ID3(D, A):if D中所有的标签都相同:return 标签if 样本中只有一个特征或者所有样本的特征都一样:对D中所有的标签进行计数return 计数最高的标签计算所有特征的信息增益选出增益最大的特征作为最佳特征(best_feature)将best_feature作为tree的根结点得到best_feature在数据集中所有出现过的值的集合(value_set)for value in value_set:从D中筛选出best_featurevalue的子数据集(sub_feature)从A中筛选出best_featurevalue的子标签集(sub_label)#递归构造treetree[best_feature][value] ID3(sub_feature, sub_label)return tree
使用决策树进行预测
决策树的预测思想非常简单假设现在已经构建出了一棵用来决策是否买西瓜的决策树。 并假设现在在水果店里有这样一个西瓜其属性如下
瓤是否够红够不够冰是否便宜是否有籽是否是否
那买不买这个西瓜呢只需把西瓜的属性代入决策树即可。决策树的根结点是瓤是否够红所以就看西瓜的属性经查看发现够红因此接下来就看够不够冰。而西瓜不够冰那么看是否便宜。发现西瓜是便宜的所以这个西瓜是可以买的。
因此使用决策树进行预测的伪代码也比较简单伪代码如下 #tree表示决策树feature表示测试数据def predict(tree, feature):if tree是叶子结点:return tree根据feature中的特征值走入tree中对应的分支if 分支依然是课树:result predict(分支, feature)return result
编程要求
填写fit(self, feature, label)函数实现ID3算法要求决策树保存在self.tree中。其中 feature训练集数据类型为ndarray数值全为整数 label训练集标签类型为ndarray数值全为整数。
填写predict(self, feature)函数实现预测功能并将标签返回其中
feature测试集数据类型为ndarray数值全为整数。PSfeature中有多条数据
测试说明
只需完成fit与predict函数即可程序内部会调用您所完成的fit函数构建模型并调用predict函数来对数据进行预测。预测的准确率高于0.92视为过关。(PS:若self.tree is None则会打印决策树构建失败)
import numpy as npclass DecisionTree(object):def __init__(self):#决策树模型self.tree {}def calcInfoGain(self, feature, label, index):计算信息增益:param feature:测试用例中字典里的feature类型为ndarray:param label:测试用例中字典里的label类型为ndarray:param index:测试用例中字典里的index即feature部分特征列的索引。该索引指的是feature中第几个特征如index:0表示使用第一个特征来计算信息增益。:return:信息增益类型float# 计算熵def calcInfoEntropy(label):计算信息熵:param label:数据集中的标签类型为ndarray:return:信息熵类型floatlabel_set set(label)result 0for l in label_set:count 0for j in range(len(label)):if label[j] l:count 1# 计算标签在数据集中出现的概率p count / len(label)# 计算熵result - p * np.log2(p)return result# 计算条件熵def calcHDA(feature, label, index, value):计算信息熵:param feature:数据集中的特征类型为ndarray:param label:数据集中的标签类型为ndarray:param index:需要使用的特征列索引类型为int:param value:index所表示的特征列中需要考察的特征值类型为int:return:信息熵类型floatcount 0# sub_feature和sub_label表示根据特征列和特征值分割出的子数据集中的特征和标签sub_feature []sub_label []for i in range(len(feature)):if feature[i][index] value:count 1sub_feature.append(feature[i])sub_label.append(label[i])pHA count / len(feature)e calcInfoEntropy(sub_label)return pHA * ebase_e calcInfoEntropy(label)f np.array(feature)# 得到指定特征列的值的集合f_set set(f[:, index])sum_HDA 0# 计算条件熵for value in f_set:sum_HDA calcHDA(feature, label, index, value)# 计算信息增益return base_e - sum_HDA# 获得信息增益最高的特征def getBestFeature(self, feature, label):max_infogain 0best_feature 0for i in range(len(feature[0])):infogain self.calcInfoGain(feature, label, i)if infogain max_infogain:max_infogain infogainbest_feature ireturn best_featuredef createTree(self, feature, label):# 样本里都是同一个label没必要继续分叉了if len(set(label)) 1:return label[0]# 样本中只有一个特征或者所有样本的特征都一样的话就看哪个label的票数高if len(feature[0]) 1 or len(np.unique(feature, axis0)) 1:vote {}for l in label:if l in vote.keys():vote[l] 1else:vote[l] 1max_count 0vote_label Nonefor k, v in vote.items():if v max_count:max_count vvote_label kreturn vote_label# 根据信息增益拿到特征的索引best_feature self.getBestFeature(feature, label)tree {best_feature: {}}f np.array(feature)# 拿到bestfeature的所有特征值f_set set(f[:, best_feature])# 构建对应特征值的子样本集sub_feature, sub_labelfor v in f_set:sub_feature []sub_label []for i in range(len(feature)):if feature[i][best_feature] v:sub_feature.append(feature[i])sub_label.append(label[i])# 递归构建决策树tree[best_feature][v] self.createTree(sub_feature, sub_label)return treedef fit(self, feature, label)::param feature: 训练集数据类型为ndarray:param label:训练集标签类型为ndarray:return: None#************* Begin ************#self.tree self.createTree(feature, label)#************* End **************#def predict(self, feature)::param feature:测试集数据类型为ndarray:return:预测结果如np.array([0, 1, 2, 2, 1, 0])#************* Begin ************#result []def classify(tree, feature):if not isinstance(tree, dict):return treet_index, t_value list(tree.items())[0]f_value feature[t_index]if isinstance(t_value, dict):classLabel classify(tree[t_index][f_value], feature)return classLabelelse:return t_valuefor f in feature:result.append(classify(self.tree, f))return np.array(result)#************* End **************# 第4关信息增益率
任务描述
本关任务根据本关所学知识完成calcInfoGainRatio函数。
相关知识
为了完成本关任务你需要掌握信息增益率
信息增益率
由于在使用信息增益这一指标进行划分时更喜欢可取值数量较多的特征。为了减少这种偏好可能带来的不利影响Ross Quinlan使用了信息增益率这一指标来选择最优划分属性。
信息增益率的数学定义为如下其中D表示数据集a表示数据集中的某一列Gain(D,a)表示D中a的信息增益V表示a这一列中取值的集合v表示V中的某种取值∣D∣表示D中样本的数量∣Dv∣表示D中a这一列中值等于v的数量。
Gain_ratio(D,a)−v1∑V∣D∣∣Dv∣log2∣D∣∣Dv∣Gain(D,a)
从公式可以看出信息增益率很好算只是用信息增益除以另一个分母该分母通常称为固有值。举个例子还是使用第二关中提到过的数据集第一列是编号第二列是性别第三列是活跃度第四列是客户是否流失的标签0表示未流失1表示流失。
编号性别活跃度是否流失1男高02女中03男低14女高05男高06男中07男中18女中09女低110女中011女高012男低113女低114男高015男高0
根据第二关已经知道性别的信息增益为0.0064设a为性别则有Gain(D,a)0.0064。由根据数据可知V2假设当v1时表示性别为男v2时表示性别为女则有∣D∣15∣D1∣8∣D2∣7。因此根据信息增益率的计算公式可知Gainratio(D,a)0.0642。同理可以算出活跃度的信息增益率为0.4328。
编程要求
根据提示在右侧编辑器补充代码完成calcInfoGainRatio函数实现计算信息增益。
calcInfoGainRatio函数中的参数: feature测试用例中字典里的feature类型为ndarray label测试用例中字典里的label类型为ndarray index测试用例中字典里的index即feature部分特征列的索引。该索引指的是feature中第几个特征如index:0表示使用第一个特征来计算信息增益率。
测试说明
平台会对你编写的代码进行测试期望您的代码根据输入来输出正确的信息增益以下为其中一个测试用例
测试输入 {feature:[[0, 1], [1, 0], [1, 2], [0, 0], [1, 1]], label:[0, 1, 0, 0, 1], index: 0}
预期输出 0.432538
提示 计算log可以使用NumPy中的log2函数.
import numpy as npdef calcInfoGain(feature, label, index):计算信息增益:param feature:测试用例中字典里的feature类型为ndarray:param label:测试用例中字典里的label类型为ndarray:param index:测试用例中字典里的index即feature部分特征列的索引。该索引指的是feature中第几个特征如index:0表示使用第一个特征来计算信息增益。:return:信息增益类型float# 计算熵def calcInfoEntropy(label):计算信息熵:param label:数据集中的标签类型为ndarray:return:信息熵类型floatlabel_set set(label)result 0for l in label_set:count 0for j in range(len(label)):if label[j] l:count 1# 计算标签在数据集中出现的概率p count / len(label)# 计算熵result - p * np.log2(p)return result# 计算条件熵def calcHDA(feature, label, index, value):计算信息熵:param feature:数据集中的特征类型为ndarray:param label:数据集中的标签类型为ndarray:param index:需要使用的特征列索引类型为int:param value:index所表示的特征列中需要考察的特征值类型为int:return:信息熵类型floatcount 0# sub_feature和sub_label表示根据特征列和特征值分割出的子数据集中的特征和标签sub_feature []sub_label []for i in range(len(feature)):if feature[i][index] value:count 1sub_feature.append(feature[i])sub_label.append(label[i])pHA count / len(feature)e calcInfoEntropy(sub_label)return pHA * ebase_e calcInfoEntropy(label)f np.array(feature)# 得到指定特征列的值的集合f_set set(f[:, index])sum_HDA 0# 计算条件熵for value in f_set:sum_HDA calcHDA(feature, label, index, value)# 计算信息增益return base_e - sum_HDAdef calcInfoGainRatio(feature, label, index):计算信息增益率:param feature:测试用例中字典里的feature类型为ndarray:param label:测试用例中字典里的label类型为ndarray:param index:测试用例中字典里的index即feature部分特征列的索引。该索引指的是feature中第几个特征如index:0表示使用第一个特征来计算信息增益。:return:信息增益率类型float#********* Begin *********#info_gain calcInfoGain(feature, label, index)unique_value list(set(feature[:, index]))IV 0for value in unique_value:len_v np.sum(feature[:, index] value)IV - (len_v/len(feature))*np.log2((len_v/len(feature)))return info_gain/IV#********* End *********#
第5关基尼系数 任务描述
本关任务根据本关所学知识完成calcGini函数。
相关知识
为了完成本关任务你需要掌握基尼系数。
基尼系数
在ID3算法中我们使用了信息增益来选择特征信息增益大的优先选择。在C4.5算法中采用了信息增益率来选择特征以减少信息增益容易选择特征值多的特征的问题。但是无论是ID3还是C4.5,都是基于信息论的熵模型的这里面会涉及大量的对数运算。能不能简化模型同时也不至于完全丢失熵模型的优点呢当然有那就是基尼系数
CART算法使用基尼系数来代替信息增益率基尼系数代表了模型的不纯度基尼系数越小则不纯度越低特征越好。这和信息增益与信息增益率是相反的(它们都是越大越好)。
基尼系数的数学定义为如下其中D表示数据集pk表示D中第k个类别在D中所占比例。
Gini(D)1−sumk1∣y∣pk2
从公式可以看出相比于信息增益和信息增益率计算起来更加简单。举个例子还是使用第二关中提到过的数据集第一列是编号第二列是性别第三列是活跃度第四列是客户是否流失的标签0表示未流失1表示流失。
编号性别活跃度是否流失1男高02女中03男低14女高05男高06男中07男中18女中09女低110女中011女高012男低113女低114男高015男高0
从表格可以看出D中总共有2个类别设类别为0的比例为p1则有p11510。设类别为1的比例为p2则有p2155。根据基尼系数的公式可知Gini(D)1−(p12p22)0.4444。
上面是基于数据集D的基尼系数的计算方法那么基于数据集D与特征a的基尼系数怎样计算呢其实和信息增益率的套路差不多。计算公式如下
Gini(D,a)sumv1V∣D∣∣Dv∣Gini(Dv)
还是以用户流失的数据为例现在算一算性别的基尼系数。设性别男为v1性别女为v2则有∣D∣15∣D1∣8∣D2∣7Gini(D1)0.46875Gini(D2)0.40816。所以Gini(D,a)0.44048。
编程要求
根据提示在右侧编辑器补充代码完成calcGini函数实现计算信息增益。
calcGini函数中的参数: feature测试用例中字典里的feature类型为ndarray label测试用例中字典里的label类型为ndarray index测试用例中字典里的index即feature部分特征列的索引。该索引指的是feature中第几个特征如index:0表示使用第一个特征来计算基尼系数。
测试说明
平台会对你编写的代码进行测试期望您的代码根据输入来输出正确的信息增益以下为其中一个测试用例
测试输入 {feature:[[0, 1], [1, 0], [1, 2], [0, 0], [1, 1]], label:[0, 1, 0, 0, 1], index: 0}
预期输出 0.266667
import numpy as npdef calcGini(feature, label, index):计算基尼系数:param feature:测试用例中字典里的feature类型为ndarray:param label:测试用例中字典里的label类型为ndarray:param index:测试用例中字典里的index即feature部分特征列的索引。该索引指的是feature中第几个特征如index:0表示使用第一个特征来计算信息增益。:return:基尼系数类型float#********* Begin *********#def _gini(label):unique_label list(set(label))gini 1for l in unique_label:p np.sum(label l)/len(label)gini - p**2return giniunique_value list(set(feature[:, index]))gini 0for value in unique_value:len_v np.sum(feature[:, index] value)gini (len_v/len(feature))*_gini(label[feature[:, index] value])return gini#********* End *********#
第6关预剪枝与后剪枝
任务描述
本关任务补充python代码完成DecisionTree类中的fit和predict函数。
相关知识
为了完成本关任务你需要掌握 为什么需要剪枝 预剪枝 后剪枝。
为什么需要剪枝
决策树的生成是递归地去构建决策树直到不能继续下去为止。这样产生的树往往对训练数据有很高的分类准确率但对未知的测试数据进行预测就没有那么准确了也就是所谓的过拟合。
决策树容易过拟合的原因是在构建决策树的过程时会过多地考虑如何提高对训练集中的数据的分类准确率从而会构建出非常复杂的决策树树的宽度和深度都比较大。在之前的实训中已经提到过模型的复杂度越高模型就越容易出现过拟合的现象。所以简化决策树的复杂度能够有效地缓解过拟合现象而简化决策树最常用的方法就是剪枝。剪枝分为预剪枝与后剪枝。
预剪枝
预剪枝的核心思想是在决策树生成过程中对每个结点在划分前先进行一个评估若当前结点的划分不能带来决策树泛化性能提升则停止划分并将当前结点标记为叶结点。
想要评估决策树算法的泛化性能如何方法很简单。可以将训练数据集中随机取出一部分作为验证数据集然后在用训练数据集对每个结点进行划分之前用当前状态的决策树计算出在验证数据集上的正确率。正确率越高说明决策树的泛化性能越好如果在划分结点的时候发现泛化性能有所下降或者没有提升时说明应该停止划分并用投票计数的方式将当前结点标记成叶子结点。
举个例子假如上一关中所提到的用来决定是否买西瓜的决策树模型已经出现过拟合的情况模型如下 假设当模型在划分是否便宜这个结点前模型在验证数据集上的正确率为0.81。但在划分后模型在验证数据集上的正确率降为0.67。此时就不应该划分是否便宜这个结点。所以预剪枝后的模型如下 从上图可以看出预剪枝能够降低决策树的复杂度。这种预剪枝处理属于贪心思想但是贪心有一定的缺陷就是可能当前划分会降低泛化性能但在其基础上进行的后续划分却有可能导致性能显著提高。所以有可能会导致决策树出现欠拟合的情况。
后剪枝
后剪枝是先从训练集生成一棵完整的决策树然后自底向上地对非叶结点进行考察若将该结点对应的子树替换为叶结点能够带来决策树泛化性能提升则将该子树替换为叶结点。
后剪枝的思路很直接对于决策树中的每一个非叶子结点的子树我们尝试着把它替换成一个叶子结点该叶子结点的类别我们用子树所覆盖训练样本中存在最多的那个类来代替这样就产生了一个简化决策树然后比较这两个决策树在测试数据集中的表现如果简化决策树在验证数据集中的准确率有所提高那么该子树就可以替换成叶子结点。该算法以bottom-up的方式遍历所有的子树直至没有任何子树可以替换使得测试数据集的表现得以改进时算法就可以终止。
从后剪枝的流程可以看出后剪枝是从全局的角度来看待要不要剪枝所以造成欠拟合现象的可能性比较小。但由于后剪枝需要先生成完整的决策树然后再剪枝所以后剪枝的训练时间开销更高。
编程要求
填写fit(self, train_feature, train_label, val_featrue, val_label)函数实现带后剪枝的ID3算法要求决策树保存在self.tree中。其中 train_feature训练集数据类型为ndarray数值全为整数 train_label训练集标签类型为ndarray数值全为整数 val_feature验证集数据类型为ndarray数值全为整数 val_label验证集标签类型为ndarray数值全为整数。
填写predict(self, feature)函数实现预测功能并将标签返回其中
feature测试集数据类型为ndarray数值全为整数。PSfeature中有多条数据
测试说明
只需完成fit与predict函数即可程序内部会调用您所完成的fit函数构建模型并调用predict函数来对数据进行预测。预测的准确率高于0.935视为过关。(PS:若self.tree is None则会打印决策树构建失败)
import numpy as np
from copy import deepcopyclass DecisionTree(object):def __init__(self):#决策树模型self.tree {}def calcInfoGain(self, feature, label, index):计算信息增益:param feature:测试用例中字典里的feature类型为ndarray:param label:测试用例中字典里的label类型为ndarray:param index:测试用例中字典里的index即feature部分特征列的索引。该索引指的是feature中第几个特征如index:0表示使用第一个特征来计算信息增益。:return:信息增益类型float# 计算熵def calcInfoEntropy(feature, label):计算信息熵:param feature:数据集中的特征类型为ndarray:param label:数据集中的标签类型为ndarray:return:信息熵类型floatlabel_set set(label)result 0for l in label_set:count 0for j in range(len(label)):if label[j] l:count 1# 计算标签在数据集中出现的概率p count / len(label)# 计算熵result - p * np.log2(p)return result# 计算条件熵def calcHDA(feature, label, index, value):计算信息熵:param feature:数据集中的特征类型为ndarray:param label:数据集中的标签类型为ndarray:param index:需要使用的特征列索引类型为int:param value:index所表示的特征列中需要考察的特征值类型为int:return:信息熵类型floatcount 0# sub_feature和sub_label表示根据特征列和特征值分割出的子数据集中的特征和标签sub_feature []sub_label []for i in range(len(feature)):if feature[i][index] value:count 1sub_feature.append(feature[i])sub_label.append(label[i])pHA count / len(feature)e calcInfoEntropy(sub_feature, sub_label)return pHA * ebase_e calcInfoEntropy(feature, label)f np.array(feature)# 得到指定特征列的值的集合f_set set(f[:, index])sum_HDA 0# 计算条件熵for value in f_set:sum_HDA calcHDA(feature, label, index, value)# 计算信息增益return base_e - sum_HDA# 获得信息增益最高的特征def getBestFeature(self, feature, label):max_infogain 0best_feature 0for i in range(len(feature[0])):infogain self.calcInfoGain(feature, label, i)if infogain max_infogain:max_infogain infogainbest_feature ireturn best_feature# 计算验证集准确率def calc_acc_val(self, the_tree, val_feature, val_label):result []def classify(tree, feature):if not isinstance(tree, dict):return treet_index, t_value list(tree.items())[0]f_value feature[t_index]if isinstance(t_value, dict):classLabel classify(tree[t_index][f_value], feature)return classLabelelse:return t_valuefor f in val_feature:result.append(classify(the_tree, f))result np.array(result)return np.mean(result val_label)def createTree(self, train_feature, train_label):# 样本里都是同一个label没必要继续分叉了if len(set(train_label)) 1:return train_label[0]# 样本中只有一个特征或者所有样本的特征都一样的话就看哪个label的票数高if len(train_feature[0]) 1 or len(np.unique(train_feature, axis0)) 1:vote {}for l in train_label:if l in vote.keys():vote[l] 1else:vote[l] 1max_count 0vote_label Nonefor k, v in vote.items():if v max_count:max_count vvote_label kreturn vote_label# 根据信息增益拿到特征的索引best_feature self.getBestFeature(train_feature, train_label)tree {best_feature: {}}f np.array(train_feature)# 拿到bestfeature的所有特征值f_set set(f[:, best_feature])# 构建对应特征值的子样本集sub_feature, sub_labelfor v in f_set:sub_feature []sub_label []for i in range(len(train_feature)):if train_feature[i][best_feature] v:sub_feature.append(train_feature[i])sub_label.append(train_label[i])# 递归构建决策树tree[best_feature][v] self.createTree(sub_feature, sub_label)return tree# 后剪枝def post_cut(self, val_feature, val_label):# 拿到非叶子节点的数量def get_non_leaf_node_count(tree):non_leaf_node_path []def dfs(tree, path, all_path):for k in tree.keys():if isinstance(tree[k], dict):path.append(k)dfs(tree[k], path, all_path)if len(path) 0:path.pop()else:all_path.append(path[:])dfs(tree, [], non_leaf_node_path)unique_non_leaf_node []for path in non_leaf_node_path:isFind Falsefor p in unique_non_leaf_node:if path p:isFind Truebreakif not isFind:unique_non_leaf_node.append(path)return len(unique_non_leaf_node)# 拿到树中深度最深的从根节点到非叶子节点的路径def get_the_most_deep_path(tree):non_leaf_node_path []def dfs(tree, path, all_path):for k in tree.keys():if isinstance(tree[k], dict):path.append(k)dfs(tree[k], path, all_path)if len(path) 0:path.pop()else:all_path.append(path[:])dfs(tree, [], non_leaf_node_path)max_depth 0result Nonefor path in non_leaf_node_path:if len(path) max_depth:max_depth len(path)result pathreturn result# 剪枝def set_vote_label(tree, path, label):for i in range(len(path)-1):tree tree[path[i]]tree[path[len(path)-1]] vote_labelacc_before_cut self.calc_acc_val(self.tree, val_feature, val_label)# 遍历所有非叶子节点for _ in range(get_non_leaf_node_count(self.tree)):path get_the_most_deep_path(self.tree)# 备份树tree deepcopy(self.tree)step deepcopy(tree)# 跟着路径走for k in path:step step[k]# 叶子节点中票数最多的标签vote_label sorted(step.items(), keylambda item: item[1], reverseTrue)[0][0]# 在备份的树上剪枝set_vote_label(tree, path, vote_label)acc_after_cut self.calc_acc_val(tree, val_feature, val_label)# 验证集准确率高于0.9才剪枝if acc_after_cut acc_before_cut:set_vote_label(self.tree, path, vote_label)acc_before_cut acc_after_cutdef fit(self, train_feature, train_label, val_feature, val_label)::param train_feature:训练集数据类型为ndarray:param train_label:训练集标签类型为ndarray:param val_feature:验证集数据类型为ndarray:param val_label:验证集标签类型为ndarray:return: None#************* Begin ************#self.tree self.createTree(train_feature, train_label)# 后剪枝self.post_cut(val_feature, val_label)#************* End **************#def predict(self, feature)::param feature:测试集数据类型为ndarray:return:预测结果如np.array([0, 1, 2, 2, 1, 0])#************* Begin ************#result []# 单个样本分类def classify(tree, feature):if not isinstance(tree, dict):return treet_index, t_value list(tree.items())[0]f_value feature[t_index]if isinstance(t_value, dict):classLabel classify(tree[t_index][f_value], feature)return classLabelelse:return t_valuefor f in feature:result.append(classify(self.tree, f))return np.array(result)#************* End **************#
第7关鸢尾花识别 任务描述
本关任务使用sklearn完成鸢尾花分类任务。
相关知识
为了完成本关任务你需要掌握如何使用sklearn提供的DecisionTreeClassifier。
数据简介 鸢尾花数据集是一类多重变量分析的数据集。通过花萼长度花萼宽度花瓣长度花瓣宽度4个属性预测鸢尾花卉属于(SetosaVersicolourVirginica)三个种类中的哪一类(其中分别用012代替)。
数据集中部分数据与标签如下图所示 DecisionTreeClassifier
DecisionTreeClassifier的构造函数中有两个常用的参数可以设置
criterion:划分节点时用到的指标。有gini基尼系数,entropy(信息增益)。若不设置默认为ginimax_depth:决策树的最大深度如果发现模型已经出现过拟合可以尝试将该参数调小。若不设置默认为None
和sklearn中其他分类器一样DecisionTreeClassifier类中的fit函数用于训练模型fit函数有两个向量输入 X大小为[样本数量,特征数量]的ndarray存放训练样本 Y值为整型大小为[样本数量]的ndarray存放训练样本的分类标签。
DecisionTreeClassifier类中的predict函数用于预测返回预测标签predict函数有一个向量输入
X大小为[样本数量,特征数量]的ndarray存放预测样本。
DecisionTreeClassifier的使用代码如下 from sklearn.tree import DecisionTreeClassifierclf tree.DecisionTreeClassifier()clf.fit(X_train, Y_train)result clf.predict(X_test)
编程要求
补充python代码实现鸢尾花数据的分类任务其中训练集数据保存在./step7/train_data.csv中训练集标签保存在。./step7/train_label.csv中测试集数据保存在。./step7/test_data.csv中。请将对测试集的预测结果保存至。./step7/predict.csv中。这些csv文件可以使用pandas读取与写入。
注意当使用pandas读取完csv文件后请将读取到的DataFrame转换成ndarray类型。这样才能正常的使用fit和predict。
示例代码 import pandas as pd# as_matrix()可以将DataFrame转换成ndarray# 此时train_df的类型为ndarray而不是DataFrametrain_df pd.read_csv(train_data.csv).as_matrix()
数据文件格式如下图所示: 标签文件格式如下图所示: PSpredict.csv文件的格式必须与标签文件格式一致。
测试说明
只需将结果保存至./step7/predict.csv即可程序内部会检测您的代码预测准确率高于0.95视为过关。
#********* Begin *********#
import pandas as pd
from sklearn.tree import DecisionTreeClassifiertrain_df pd.read_csv(./step7/train_data.csv).as_matrix()
train_label pd.read_csv(./step7/train_label.csv).as_matrix()
test_df pd.read_csv(./step7/test_data.csv).as_matrix()dt DecisionTreeClassifier()
dt.fit(train_df, train_label)
result dt.predict(test_df)result pd.DataFrame({target:result})
result.to_csv(./step7/predict.csv, indexFalse)#********* End *********#
文章转载自： http://www.morning.dwzwm.cn.gov.cn.dwzwm.cn http://www.morning.plhhd.cn.gov.cn.plhhd.cn http://www.morning.xkzr.cn.gov.cn.xkzr.cn http://www.morning.nydtt.cn.gov.cn.nydtt.cn http://www.morning.lrnfn.cn.gov.cn.lrnfn.cn http://www.morning.ndmh.cn.gov.cn.ndmh.cn http://www.morning.xtkw.cn.gov.cn.xtkw.cn http://www.morning.bwgrd.cn.gov.cn.bwgrd.cn http://www.morning.rhzzf.cn.gov.cn.rhzzf.cn http://www.morning.njntp.cn.gov.cn.njntp.cn http://www.morning.xrtsx.cn.gov.cn.xrtsx.cn http://www.morning.rrgqq.cn.gov.cn.rrgqq.cn http://www.morning.mcjrf.cn.gov.cn.mcjrf.cn http://www.morning.jpgfx.cn.gov.cn.jpgfx.cn http://www.morning.gwtgt.cn.gov.cn.gwtgt.cn http://www.morning.nfzzf.cn.gov.cn.nfzzf.cn http://www.morning.xckdn.cn.gov.cn.xckdn.cn http://www.morning.ssjtr.cn.gov.cn.ssjtr.cn http://www.morning.nhlnh.cn.gov.cn.nhlnh.cn http://www.morning.kcxtz.cn.gov.cn.kcxtz.cn http://www.morning.gfprf.cn.gov.cn.gfprf.cn http://www.morning.mxxsq.cn.gov.cn.mxxsq.cn http://www.morning.owenzhi.com.gov.cn.owenzhi.com http://www.morning.dqwkm.cn.gov.cn.dqwkm.cn http://www.morning.frsbf.cn.gov.cn.frsbf.cn http://www.morning.lbbgf.cn.gov.cn.lbbgf.cn http://www.morning.hrdx.cn.gov.cn.hrdx.cn http://www.morning.kqbzy.cn.gov.cn.kqbzy.cn http://www.morning.ptdzm.cn.gov.cn.ptdzm.cn http://www.morning.nzmhk.cn.gov.cn.nzmhk.cn http://www.morning.rnxw.cn.gov.cn.rnxw.cn http://www.morning.fwzjs.cn.gov.cn.fwzjs.cn http://www.morning.mnwsy.cn.gov.cn.mnwsy.cn http://www.morning.pfbx.cn.gov.cn.pfbx.cn http://www.morning.kjyfq.cn.gov.cn.kjyfq.cn http://www.morning.lbcbq.cn.gov.cn.lbcbq.cn http://www.morning.mjgxl.cn.gov.cn.mjgxl.cn http://www.morning.kkwgg.cn.gov.cn.kkwgg.cn http://www.morning.pndhh.cn.gov.cn.pndhh.cn http://www.morning.pnljy.cn.gov.cn.pnljy.cn http://www.morning.fgwzl.cn.gov.cn.fgwzl.cn http://www.morning.zrmxp.cn.gov.cn.zrmxp.cn http://www.morning.dhrbj.cn.gov.cn.dhrbj.cn http://www.morning.kdlzz.cn.gov.cn.kdlzz.cn http://www.morning.jxgyg.cn.gov.cn.jxgyg.cn http://www.morning.crkhd.cn.gov.cn.crkhd.cn http://www.morning.bjjrtcsl.com.gov.cn.bjjrtcsl.com http://www.morning.yxnkr.cn.gov.cn.yxnkr.cn http://www.morning.xdmsq.cn.gov.cn.xdmsq.cn http://www.morning.xkmrr.cn.gov.cn.xkmrr.cn http://www.morning.sxmbk.cn.gov.cn.sxmbk.cn http://www.morning.rqqkc.cn.gov.cn.rqqkc.cn http://www.morning.zrlwl.cn.gov.cn.zrlwl.cn http://www.morning.qshxh.cn.gov.cn.qshxh.cn http://www.morning.irqlul.cn.gov.cn.irqlul.cn http://www.morning.mmplj.cn.gov.cn.mmplj.cn http://www.morning.wjhpg.cn.gov.cn.wjhpg.cn http://www.morning.tkyry.cn.gov.cn.tkyry.cn http://www.morning.yyzgl.cn.gov.cn.yyzgl.cn http://www.morning.ttshf.cn.gov.cn.ttshf.cn http://www.morning.cpktd.cn.gov.cn.cpktd.cn http://www.morning.ypklb.cn.gov.cn.ypklb.cn http://www.morning.rbmm.cn.gov.cn.rbmm.cn http://www.morning.lkrmp.cn.gov.cn.lkrmp.cn http://www.morning.jxrpn.cn.gov.cn.jxrpn.cn http://www.morning.nyqnk.cn.gov.cn.nyqnk.cn http://www.morning.ppqzb.cn.gov.cn.ppqzb.cn http://www.morning.wyctq.cn.gov.cn.wyctq.cn http://www.morning.rgyts.cn.gov.cn.rgyts.cn http://www.morning.dxqwm.cn.gov.cn.dxqwm.cn http://www.morning.grzpc.cn.gov.cn.grzpc.cn http://www.morning.mxmtt.cn.gov.cn.mxmtt.cn http://www.morning.jbfzx.cn.gov.cn.jbfzx.cn http://www.morning.gwdmj.cn.gov.cn.gwdmj.cn http://www.morning.qbdsx.cn.gov.cn.qbdsx.cn http://www.morning.rtlg.cn.gov.cn.rtlg.cn http://www.morning.dmzzt.cn.gov.cn.dmzzt.cn http://www.morning.hwycs.cn.gov.cn.hwycs.cn http://www.morning.lsjtq.cn.gov.cn.lsjtq.cn http://www.morning.ylrxd.cn.gov.cn.ylrxd.cn
