数据挖掘之决策树

• 花匠小妙招
• 2025-01-08 00:09

 第一关：什么是决策树

任务描述

本关任务：根据本节课所学知识完成本关所设置的选择题。

相关知识

为了完成本关任务，你需要掌握决策树的相关基础知识。

选择题

第二关：信息熵与信息增益

任务描述

本关任务：根据本关所学知识，完成calcInfoEntropy函数，calcHDA函数以及calcInfoGain函数。

相关知识

为了完成本关任务，你需要掌握：

信息熵条件熵信息增益 信息熵

信息是个很抽象的概念。人们常常说信息很多，或者信息较少，但却很难说清楚信息到底有多少。比如一本五十万字的中文书到底有多少信息量。

直到1948年，香农提出了“信息熵”的概念，才解决了对信息的量化度量问题。信息熵这个词是香农从热力学中借用过来的。热力学中的热熵是表示分子状态混乱程度的物理量。香农用信息熵的概念来描述信源的不确定度。信源的不确定性越大，信息熵也越大。

从机器学习的角度来看，信息熵表示的是信息量的期望值。如果数据集中的数据需要被分成多个类别，则信息量I(xi​)的定义如下(其中xi​表示多个类别中的第i个类别，p(xi​)数据集中类别为xi​的数据在数据集中出现的概率表示)：

I(Xi​)=−log2​p(xi​)

由于信息熵是信息量的期望值，所以信息熵H(X)的定义如下(其中n为数据集中类别的数量)：

H(X)=−i=1∑n​p(xi​)log2​p(xi​)

从这个公式也可以看出，如果概率是0或者是1的时候，熵就是0。（因为这种情况下随机变量的不确定性是最低的），那如果概率是0.5也就是五五开的时候，此时熵达到最大，也就是1。（就像扔硬币，你永远都猜不透你下次扔到的是正面还是反面，所以它的不确定性非常高）。所以呢，熵越大，不确定性就越高。

条件熵

在实际的场景中，我们可能需要研究数据集中某个特征等于某个值时的信息熵等于多少，这个时候就需要用到条件熵。条件熵H(Y|X)表示特征X为某个值的条件下，类别为Y的熵。条件熵的计算公式如下：

H(Y∣X)=i=1∑n​pi​H(Y∣X=xi​)

当然条件熵的一个性质也熵的性质一样，概率越确定，条件熵就越小，概率越五五开，条件熵就越大。

信息增益

现在已经知道了什么是熵，什么是条件熵。接下来就可以看看什么是信息增益了。所谓的信息增益就是表示我已知条件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)−0=0

活跃度为中的熵为：

−(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中计算每个特征的信息增益，然后看哪个最大就选哪个作为当前结点。然后继续重复刚刚的步骤来构建决策树。

编程要求

根据提示，在右侧编辑器补充代码，完成calcInfoEntropy函数实现计算信息熵、calcHDA函数实现计算条件熵、calcInfoGain函数实现计算信息增益。

calcInfoEntropy函数中的参数:

feature：数据集中的特征，类型为ndarraylabel：数据集中的标签，类型为ndarray

calcHDA函数中的参数:

feature：数据集中的特征，类型为ndarraylabel：数据集中的标签，类型为ndarrayindex：需要使用的特征列索引，类型为intvalue：index所表示的特征列中需要考察的特征值，类型为int

calcInfoGain函数中的参数:

feature：测试用例中字典里的featurelabel：测试用例中字典里的labelindex：测试用例中字典里的index，即feature部分特征列的索引 测试说明

平台会对你编写的代码进行测试，期望您的代码根据输入来输出正确的信息增益，以下为其中一个测试用例：

测试输入： {'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 np

def calcInfoEntropy(feature, label):

'''

计算信息熵

:param feature:数据集中的特征，类型为ndarray

:param label:数据集中的标签，类型为ndarray

:return:信息熵，类型float

'''

feature = np.array(feature)

label = np.array(label)

label_counts = np.bincount(label)

label_probs = label_counts / len(label)

info_entropy = -np.sum(label_probs * np.log2(label_probs + 1e-10))

return info_entropy

def calcHDA(feature, label, index, value):

'''

计算信息熵

:param feature:数据集中的特征，类型为ndarray

:param label:数据集中的标签，类型为ndarray

:param index:需要使用的特征列索引，类型为int

:param value:index所表示的特征列中需要考察的特征值，类型为int

:return:信息熵，类型float

'''

feature = np.array(feature)

label = np.array(label)

mask = (feature[:, index] == value)

feature_subset = feature[mask]

label_subset = label[mask]

cond_entropy = calcInfoEntropy(feature_subset, label_subset)

return cond_entropy

def calcInfoGain(feature, label, index):

'''

计算信息增益

:param feature:测试用例中字典里的feature

:param label:测试用例中字典里的label

:param index:测试用例中字典里的index，即feature部分特征列的索引

:return:信息增益，类型float

'''

feature = np.array(feature)

label = np.array(label)

base_entropy = calcInfoEntropy(feature, label)

values = np.unique(feature[:, index])

cond_entropy = sum([(len(feature[feature[:, index] == value]) / len(feature)) * calcHDA(feature, label, index, value) for value in values])

info_gain = base_entropy - cond_entropy

return info_gain

 第三关：使用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_feature=value的子数据集(sub_feature)从A中筛选出best_feature=value的子标签集(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：训练数据集所有特征组成的ndarraylabel：训练数据集中所有标签组成的ndarray

填写predict(self, feature)函数，实现预测功能，并将标签返回，其中：

feature：测试数据集所有特征组成的ndarray。（PS：feature中有多条数据） 测试说明

只需完成fit与predict函数即可，程序内部会调用您所完成的fit函数构建模型并调用predict函数来对数据进行预测。预测的准确率高于90%视为过关。

代码填充

import numpy as np

from copy import deepcopy

from collections import Counter

class DecisionTree(object):

def calcInfoEntropy(self, label):

label_set = set(label)

result = 0

for l in label_set:

count = 0

for j in range(len(label)):

if label[j] == l:

count += 1

p = count/len(label)

result -= p*np.log2(p)

return result

def calcHDA(self, feature, label, index, value):

count = 0

sub_feature = []

sub_label = []

for i in range(len(feature)):

if feature[i][index] == value:

count += 1

sub_feature.append(feature[i])

sub_label.append(label[i])

pHA = count/len(feature)

e = self.calcInfoEntropy(sub_label)

return pHA*e

def calcInfoGain(self, feature, label, index):

base_e = self.calcInfoEntropy(label)

f = np.array(feature)

f_set = set(f[:, index])

sum_HDA = 0

for l in f_set:

sum_HDA += self.calcHDA(feature, label, index, l)

return base_e - sum_HDA

def __init__(self):

self.tree = {}

def fit(self, feature, label):

'''

:param feature: 训练数据集所有特征组成的ndarray

:param label:训练数据集中所有标签组成的ndarray

:return: None

'''

def build_tree(feature, label):

if len(set(label)) == 1:

return label[0]

if len(feature[0]) == 0 or len(set([tuple(row) for row in feature])) == 1:

return Counter(label).most_common(1)[0][0]

best_feature_index = None

best_info_gain = -float('inf')

for i in range(len(feature[0])):

info_gain = self.calcInfoGain(feature, label, i)

if info_gain > best_info_gain:

best_info_gain = info_gain

best_feature_index = i

best_feature_values = set(feature[:, best_feature_index])

sub_trees = {}

for value in best_feature_values:

sub_feature = [row for row in feature if row[best_feature_index] == value]

sub_label = [label[i] for i in range(len(label)) if feature[i][best_feature_index] == value]

sub_trees[value] = build_tree(np.array(sub_feature), np.array(sub_label))

return {'feature_index': best_feature_index, 'sub_trees': sub_trees}

self.tree = build_tree(feature, label)

def predict(self, feature):

'''

:param feature:训练数据集所有特征组成的ndarray

:return:预测结果，如np.array([0, 1, 2, 2, 1, 0])

'''

def classify(tree, sample):

if isinstance(tree, dict):

feature_index = tree['feature_index']

sub_trees = tree['sub_trees']

value = sample[feature_index]

if value in sub_trees:

return classify(sub_trees[value], sample)

else:

return tree

predictions = []

for sample in feature:

predictions.append(classify(self.tree, sample))

return np.array(predictions)

第四关：预剪枝和后剪枝

任务描述

本关任务：通过学习完成关卡设置的选择题

相关知识

为了完成本关任务，你需要掌握：

为什么需要剪枝预剪枝后剪枝 选择题

第5关：sklearn中的决策树

任务描述

本关任务：使用sklearn完成鸢尾花分类任务

相关知识

为了完成本关任务，你需要掌握如何使用sklearn提供的DecisionTreeClassifier

数据简介

鸢尾花数据集是一类多重变量分析的数据集。通过花萼长度，花萼宽度，花瓣长度，花瓣宽度4个属性预测鸢尾花卉属于(Setosa，Versicolour，Virginica)三个种类中的哪一类。

sklearn中已经提供了鸢尾花数据集的相关接口，想要使用该数据集可以使用如下代码：

数据集中部分数据与标签如下图所示：

DecisionTreeClassifier

DecisionTreeClassifier的构造函数中有两个常用的参数可以设置：

criterion:划分节点时用到的指标。有gini（基尼系数）,entropy(信息增益)。若不设置，默认为ginimax_depth:决策树的最大深度，如果发现模型已经出现过拟合，可以尝试将该参数调小。若不设置，默认为None

PS：关于基尼系数 分类问题中，假设有n个类别，则其基尼指数Gini定义如下，其中pi​表示样本属于第i个类别的概率：

Gini=1−i=1∑n​p(i​)2

假设现在有一枚两面都是字的硬币，很明显不管怎么扔硬币都是字朝上，所以根据基尼系数的公式计算后结果为0。如果现在有一枚正常的硬币，那在扔硬币时字朝上和花朝上的概率都是0.5。所以根据基尼系数的公式计算后结果为0.5。可以看出事件越确定基尼系数越低，越模棱两可基尼系数就越高。所以基尼系数与信息熵类似，不确定性越高，基尼系数越高。

和sklearn中其他分类器一样，DecisionTreeClassifier类中的fit函数用于训练模型，fit函数有两个向量输入：

X：大小为[样本数量,特征数量]的ndarray，存放训练样本Y：值为整型，大小为[样本数量]的ndarray，存放训练样本的分类标签

DecisionTreeClassifier类中的predict函数用于预测，返回预测标签，predict函数有一个向量输入：

X：大小为[样本数量,特征数量]的ndarray，存放预测样本

DecisionTreeClassifier的使用代码如下：

from sklearn import datasets

iris = datasets.load_iris()

X = iris.data

y = iris.target

clf = tree.DecisionTreeClassifier()

clf.fit(X_train, Y_train)

result = clf.predict(X_test)

编程要求

填写iris_predict(train_sample, train_label, test_sample)函数完成鸢尾花分类任务，其中：

train_sample：训练样本train_label：训练标签test_sample：测试样本 测试说明

只需返回预测结果即可，程序内部会检测您的代码，预测正确率高于95%视为过关。

代码填充

from sklearn.tree import DecisionTreeClassifier

def iris_predict(train_sample, train_label, test_sample):

'''

实现功能：1.训练模型 2.预测

:param train_sample: 包含多条训练样本的样本集，类型为ndarray

:param train_label: 包含多条训练样本标签的标签集，类型为ndarray

:param test_sample: 包含多条测试样本的测试集，类型为ndarry

:return: test_sample对应的预测标签

'''

dt = DecisionTreeClassifier(max_depth=3)

dt.fit(train_sample, train_label)

return dt.predict(test_sample)

任务完成。

相关知识

数据挖掘之鸢尾花数据集分析
数据挖掘浅谈
【python数据挖掘课程】十九.鸢尾花数据集可视化、线性回归、决策树花样分析
数据挖掘:：实验一 WEKA分类
决策树对鸢尾花数据的处理实践
机器学习算法之决策树实现鸢尾花数据分类
【2016年第1期】基于大数据的小麦蚜虫发生程度决策树预测分类模型
决策树可视化：鸢尾花数据集分类(附代码数据集)
决策树之鸢尾花卉实例解析
基于决策树构建鸢尾花数据的分类模型并绘制决策树模型

网址: 数据挖掘之决策树 https://m.huajiangbk.com/newsview1489756.html

上一篇: 2024年度“浙版传媒好书”揭晓

下一篇: 巴西木好养活吗