一、【实验目的】
- 理解决策树算法原理,掌握决策树算法框架;
- 理解决策树学习算法的特征选择、树的生成和树的剪枝;
- 能根据不同的数据类型,选择不同的决策树算法;
- 针对特定应用场景及数据,能应用决策树算法解决实际问题。
二、【实验内容】
- 设计算法实现熵、经验条件熵、信息增益等方法。
- 针对给定的房贷数据集(数据集表格见附录1)实现ID3算法。
- 熟悉sklearn库中的决策树算法;
- 针对iris数据集,应用sklearn的决策树算法进行类别预测。
- 针对iris数据集,利用自编决策树算法进行类别预测。
三、【实验报告要求】
- 对照实验内容,撰写实验过程、算法及测试结果;
- 代码规范化:命名规则、注释;
- 查阅文献,讨论ID3、C4.5算法的应用场景;
- 查询文献,分析决策树剪枝策略。
四、【实验内容及结果】
实验代码及截图
1.设计算法实现熵、经验条件熵、信息增益等方法
import numpy as np import pandas as pd import matplotlib.pyplot as plt %matplotlib inline from sklearn.datasets import load_iris from sklearn.model_selection import train_test_split from collections import Counter import math from math import log import pprint def create_data(): datasets = [['青年', '否', '否', '一般', '否'], ['青年', '否', '否', '好', '否'], ['青年', '是', '否', '好', '是'], ['青年', '是', '是', '一般', '是'], ['青年', '否', '否', '一般', '否'], ['中年', '否', '否', '一般', '否'], ['中年', '否', '否', '好', '否'], ['中年', '是', '是', '好', '是'], ['中年', '否', '是', '非常好', '是'], ['中年', '否', '是', '非常好', '是'], ['老年', '否', '是', '非常好', '是'], ['老年', '否', '是', '好', '是'], ['老年', '是', '否', '好', '是'], ['老年', '是', '否', '非常好', '是'], ['老年', '否', '否', '一般', '否'], ] labels = [u'年龄', u'有工作', u'有自己的房子', u'信贷情况', u'类别'] return datasets, labels datasets, labels = create_data() obtain_data = pd.DataFrame(datasets, columns=labels) obtain_data
# 熵 def calc_ent(datasets): data_length = len(datasets) label_count = {} for i in range(data_length): label = datasets[i][-1] if label not in label_count: label_count[label] = 0 label_count[label] += 1 ent = -sum([(p/data_length)*log(p/data_length, 2) for p in label_count.values()]) return ent # 经验条件熵 def cond_ent(datasets, axis=0): data_length = len(datasets) feature_sets = {} for i in range(data_length): feature = datasets[i][axis] if feature not in feature_sets: feature_sets[feature] = [] feature_sets[feature].append(datasets[i]) cond_ent = sum([(len(p)/data_length)*calc_ent(p) for p in feature_sets.values()]) return cond_ent # 信息增益 def info_gain(ent, cond_ent): return ent - cond_ent def info_gain_train(datasets): count = len(datasets[0]) - 1 ent = calc_ent(datasets) best_feature = [] for c in range(count): c_info_gain = info_gain(ent, cond_ent(datasets, axis=c)) best_feature.append((c, c_info_gain)) print('特征({}) - info_gain - {:.3f}'.format(labels[c], c_info_gain)) # 比较大小 best_ = max(best_feature, key=lambda x: x[-1]) return '特征({})的信息增益最大,选择为根节点特征'.format(labels[best_[0]])
2.针对给定的房贷数据集实现ID3算法
""" 函数说明:计算给定数据集的经验熵(香农熵) Parameters: dataSet - 数据集 Returns: shannonEnt - 经验熵(香农熵) """ def calcShannonEnt(dataSet): numEntires = len(dataSet) #返回数据集的行数 labelCounts = {} #保存每个标签(Label)出现次数的字典 for featVec in dataSet: #对每组特征向量进行统计 currentLabel = featVec[-1] #提取标签(Label)信息 if currentLabel not in labelCounts.keys(): #如果标签(Label)没有放入统计次数的字典,添加进去 labelCounts[currentLabel] = 0 labelCounts[currentLabel] += 1 #Label计数 shannonEnt = 0.0 #经验熵(香农熵) for key in labelCounts: #计算香农熵 prob = float(labelCounts[key]) / numEntires #选择该标签(Label)的概率 shannonEnt -= prob * log(prob, 2) #利用公式计算 return shannonEnt #返回经验熵(香农熵) """ 函数说明:按照给定特征划分数据集 Parameters: dataSet - 待划分的数据集 axis - 划分数据集的特征 value - 需要返回的特征的值 """ def splitDataSet(dataSet, axis, value): retDataSet = [] #创建返回的数据集列表 for featVec in dataSet: #遍历数据集 if featVec[axis] == value: reducedFeatVec = featVec[:axis] #去掉axis特征 reducedFeatVec.extend(featVec[axis+1:]) #将符合条件的添加到返回的数据集 retDataSet.append(reducedFeatVec) return retDataSet #返回划分后的数据集 """ 函数说明:选择最优特征 Parameters: dataSet - 数据集 Returns: bestFeature - 信息增益最大的(最优)特征的索引值 """ def chooseBestFeatureToSplit(dataSet): numFeatures = len(dataSet[0]) - 1 #特征数量 baseEntropy = calcShannonEnt(dataSet) #计算数据集的香农熵 bestInfoGain = 0.0 #信息增益 bestFeature = -1 #最优特征的索引值 for i in range(numFeatures): #遍历所有特征 #获取dataSet的第i个所有特征 featList = [example[i] for example in dataSet] uniqueVals = set(featList) #创建set集合{},元素不可重复 newEntropy = 0.0 #经验条件熵 for value in uniqueVals: #计算信息增益 subDataSet = splitDataSet(dataSet, i, value) #subDataSet划分后的子集 prob = len(subDataSet) / float(len(dataSet)) #计算子集的概率 newEntropy += prob * calcShannonEnt(subDataSet) #根据公式计算经验条件熵 infoGain = baseEntropy - newEntropy #信息增益 print("第%d个特征的增益为%.3f" % (i, infoGain)) #打印每个特征的信息增益 if (infoGain > bestInfoGain): #计算信息增益 bestInfoGain = infoGain #更新信息增益,找到最大的信息增益 bestFeature = i #记录信息增益最大的特征的索引值 return bestFeature #返回信息增益最大的特征的索引值 if __name__ == '__main__': dataSet, features = createDataSet() entropy=calcShannonEnt(dataSet) bestfeature=chooseBestFeatureToSplit(dataSet) print("训练集的熵为:%f"%(entropy)) print("最优特征索引值:" + str(bestfeature))
3.熟悉sklearn库中的决策树算法
from sklearn.preprocessing import LabelEncoder from sklearn.tree import export_graphviz from sklearn import tree import graphviz D=[ {'年龄':'青年','有工作':'否','有自己的房子':'否','信贷情况':'一般','类别':'否'}, {'年龄':'青年','有工作':'否','有自己的房子':'否','信贷情况':'好','类别':'否'}, {'年龄':'青年','有工作':'是','有自己的房子':'否','信贷情况':'好','类别':'是'}, {'年龄':'青年','有工作':'是','有自己的房子':'是','信贷情况':'一般','类别':'是'}, {'年龄':'青年','有工作':'否','有自己的房子':'否','信贷情况':'一般','类别':'否'}, {'年龄':'中年','有工作':'否','有自己的房子':'否','信贷情况':'一般','类别':'否'}, {'年龄':'中年','有工作':'否','有自己的房子':'是','信贷情况':'好','类别':'否'}, {'年龄':'中年','有工作':'是','有自己的房子':'是','信贷情况':'好','类别':'是'}, {'年龄':'中年','有工作':'否','有自己的房子':'是','信贷情况':'非常好','类别':'是'}, {'年龄':'中年','有工作':'否','有自己的房子':'是','信贷情况':'非常好','类别':'是'}, {'年龄':'老年','有工作':'否','有自己的房子':'是','信贷情况':'非常好','类别':'是'}, {'年龄':'老年','有工作':'否','有自己的房子':'是','信贷情况':'好','类别':'是'}, {'年龄':'老年','有工作':'是','有自己的房子':'否','信贷情况':'好','类别':'是'}, {'年龄':'老年','有工作':'是','有自己的房子':'否','信贷情况':'非常好','类别':'是'}, {'年龄':'老年','有工作':'否','有自己的房子':'否','信贷情况':'一般','类别':'否'}, ] data=pd.DataFrame(D) new_clf=tree.DecisionTreeClassifier() LabelEncoder = LabelEncoder() #再次使用sklearn中的tree模块会报错,无法将string类型数据转换为float类型,顾采用One-Hot Encoding编码,即一位有效编码 for i in range(data.shape[1]): data.iloc[:, i] =LabelEncoder.fit_transform(data.iloc[:, i]) new_clf = new_clf.fit(data.iloc[:-4, :-1], data.iloc[:-4, -1]) new_score = new_clf.score(data.iloc[-4:, :-1], data.iloc[-4:, -1]) feature_name = ['年龄', '有工作', '有自己的房子', '信贷情况'] target_name = ['是', '否'] dot_data = tree.export_graphviz(new_clf , out_file=None , feature_names=feature_name , class_names=target_name , rounded=True ) graph=graphviz.Source(dot_data) graph
4.针对iris数据集,应用sklearn的决策树算法进行类别预测
(1)环境的准备
pip install -i https://pypi.tuna.tsinghua.edu.cn/simple sklearn
pip install -i https://pypi.tuna.tsinghua.edu.cn/simple pydotplus
安装Graphviz并进行环境变量的配置
(2)数据集的获取
#导入相应的包 from sklearn import datasets #导入方法类 from sklearn.model_selection import train_test_split from sklearn.preprocessing import LabelEncoder, OneHotEncoderfrom six import StringIO from sklearn import tree import pandas as pd import numpy as np import pydotplus from sklearn.metrics import accuracy_score # 获取所需数据集 iris=datasets.load_iris() #每行的数据,一共四列,每一列映射为feature_names中对应的值 X=iris.data #每行数据对应的分类结果值(也就是每行数据的label值),取值为[0,1,2] Y=iris.target #通过Y=iris.target.size,可以得到一共150行数据,三个类别个50条数据,并且数据是按照0,1,2的顺序放的 #print(iris)
(3)数据集的划分
#划分训练集和测试集,按照7:3的比例划分 X_train, X_test, Y_train, Y_test = train_test_split(X, Y, test_size=0.3, random_state=42) print(X_train.shape) print(X_test.shape)
(4)构建决策树
clf = tree.DecisionTreeClassifier() lenses = clf.fit(X_train, Y_train)
(5)决策树可视化
dot_data = StringIO() tree.export_graphviz(clf, out_file = dot_data, #绘制决策树 feature_names = iris.feature_names, class_names = iris.target_names, filled=True, rounded=True, special_characters=True) graph = pydotplus.graph_from_dot_data(dot_data.getvalue()) graph.write_pdf("treeiris.pdf")
(6)预测准确率
predict_results = clf.predict(X_test) # 使用模型对测试集进行预测 print(accuracy_score(predict_results, Y_test))
五、【实验小结】
ID3算法步骤
步骤1:将所有的数据看成是一个节点,进入下一层步骤2;
步骤2:从所有的数据特征中挑选一个数据特征对节点进行分割,进入步骤3;
步骤3:生成若干孩子节点,对每一个孩子节点进行判断,如果满足停止分裂的条件,进入步骤4;否则,进入步骤2;
步骤4:设置该节点是子节点,其输出的结果为该节点数量占比最大的类别。
构建决策树的关键步骤是分裂属性,指在某个节点按照一类特征属性的不同划分构建不同的分支,使每个分支中的数据类别尽可能的纯。
决策树是一种贪心算法策略,只考虑当前数据特征的最好分割方式,不能回溯操作(只能从上往下分割)
步骤:
1.将所有的特征看成一个一个的节点
2.遍历所有特征,遍历到其中某一个特征时:遍历当前特征的所有分割方式,找到最好的分割点,将数据划分为不同的子节点,计算划分后子节点的纯度信息
3.在遍历的所有特征中,比较寻找最优的特征以及最优特征的最优划分方式,纯度越高,则对当前数据集进行分割操作
4.对新的子节点继续执行2-3步,直到每个最终的子节点都足够纯
决策树算法构建的停止条件:
1.(会导致过拟合)当子节点中只有一种类型的时候停止构建
2.(比较常用)当前节点种样本数小于某个值,同时迭代次数达到指定值,停止构建,此时使用该节点中出现最多的类别样本数据作为对应值
ID3算法: 内部使用信息熵以及’信息增益‘来进行构建,每次迭代选择信息增益最大的特征属性作为分割属性。只支持离散的特征属性
优点:决策树构建速度快,实现简单
缺点:算法依赖样本中出现次数较多的特征属性,但是出现次数最多的属性并不一定最优
2.C4.5算法:使用’信息增益率‘来构建,在树的构建过程中会进行剪枝操作的优化,能够自动完成对连续属性的离散化处理。选择信息增益率大的属性进行分割
优点:准确率较高,实现简单
缺点:对数据集需要进行多次顺序扫描和排序,效率较低。
3.CART算法:使用'基尼系数'作为数据纯度的量化指标来构建,选择‘GINI增益率’来分割,越大的即作为当前数据集的分割属性.可用于分类和回归
无论是ID3, C4.5还是CART,在做特征选择的时候都是选择最优的一个特征来做分类决策,但是大多数,分类决策不应该是由某一个特征决定的,而是应该由一组特征决定的。这样决策得到的决策树更加准确
在实验中遇到的问题
下载和安装Graphviz时需要进行环境变量的配置 否则会出现GraphViz's executables not found的报错