一、【实验目的】
- 理解决策树算法原理，掌握决策树算法框架；
- 理解决策树学习算法的特征选择、树的生成和树的剪枝；
- 能根据不同的数据类型，选择不同的决策树算法；
- 针对特定应用场景及数据，能应用决策树算法解决实际问题。
二、【实验内容】
- 设计算法实现熵、经验条件熵、信息增益等方法。
- 针对给定的房贷数据集(数据集表格见附录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的报错
