【实验目的】
-
理解决策树算法原理，掌握决策树算法框架；
-
理解决策树学习算法的特征选择、树的生成和树的剪枝；
-
能根据不同的数据类型，选择不同的决策树算法；
-
针对特定应用场景及数据，能应用决策树算法解决实际问题。
【实验内容】
-
设计算法实现熵、经验条件熵、信息增益等方法。
-
针对给定的房贷数据集(数据集表格见附录1)实现ID3算法。
-
熟悉sklearn库中的决策树算法；
-
针对iris数据集，应用sklearn的决策树算法进行类别预测。
【实验报告要求】
-
对照实验内容，撰写实验过程、算法及测试结果；
-
代码规范化：命名规则、注释；
-
查阅文献，讨论ID3、5算法的应用场景；
- 查询文献，分析决策树剪枝策略。
【附录一】
| 年龄 | 有工作 | 有自己的房子 | 信贷情况 | 类别 | |
| 0 | 青年 | 否 | 否 | 一般 | 否 |
| 1 | 青年 | 否 | 否 | 好 | 否 |
| 2 | 青年 | 是 | 否 | 好 | 是 |
| 3 | 青年 | 是 | 是 | 一般 | 是 |
| 4 | 青年 | 否 | 否 | 一般 | 否 |
| 5 | 中年 | 否 | 否 | 一般 | 否 |
| 6 | 中年 | 否 | 否 | 好 | 否 |
| 7 | 中年 | 是 | 是 | 好 | 是 |
| 8 | 中年 | 否 | 是 | 非常好 | 是 |
| 9 | 中年 | 否 | 是 | 非常好 | 是 |
| 10 | 老年 | 否 | 是 | 非常好 | 是 |
| 11 | 老年 | 否 | 是 | 好 | 是 |
| 12 | 老年 | 是 | 否 | 好 | 是 |
| 13 | 老年 | 是 | 否 | 非常好 | 是 |
| 14 | 老年 | 否 | 否 | 一般 | 否 |
【实验描述与过程】
1、决策树算法
1.1、决策树
决策树是属于机器学习监督学习分类算法中比较简单的一种，决策树是一个预测模型；它代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。 是通过一系列规则对数据进行分类的过程。
用决策树分类：从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点，此时每个子节点对应着该特征的一个取值，如此递归的对实例进行测试并分配，直到到达叶节点，最后将实例分到叶节点的类中。
1.2、决策树构造过程
一般包含三个部分
1、特征选择：特征选择是指从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准标准，从而衍生出不同的决策树算法，如CART, ID3, C4.5等。
2、决策树生成： 根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止生长。 树结构来说，递归结构是最容易理解的方式。
3、剪枝：决策树容易过拟合，一般来需要剪枝，缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。
1.3、决策树的一般流程
（1）收集数据：可以使用任何方法。
（2）准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化。
（3）分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。
（4）训练算法：构造树的数据结构。
（5）测试算法：使用经验树计算错误率。
（6）使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。
1.4、算法分类
1.4.1、信息熵
信息熵表示可能事件发生的不确定性的度量
H(x)的值越小，样本集合纯度越高。
1.4.2、信息增益（ID3)
样本集A按照第j个特征的某决策值f划分成独立的子集，其划分的信息熵减小，我们将划分前后信息熵的减小量成为信息增益
Gain越大，样本集合纯度越高
1.4.3、基尼指数（CART）
CART决策树算法采用基尼指数来选择划分特征。对于样本集A，假设有K个分类，设样本属于第k类的概率为,则此概率分布的基尼指数为
Gain(p)越小，数据集A的纯度越高。
2、实验内容
2.1、设计算法实现熵、经验条件熵、信息增益等方法
1、设计熵的算法
#熵
2 def calc_ent(datasets):
3 data_length = len(datasets) #返回数据集的行数
4 label_count = {} #保存每个标签(Label)出现次数的字典
5 for i in range(data_length): #对每组特征向量进行统计
label = datasets[i][-1] #提取标签(Label)信息
7 if label not in label_count: #如果标签(Label)没有放入统计次数的字典,添加进去
8 label_count[label] = 0
9 label_count[label] += 1
10 ent = -sum([(p/data_length)*log(p/data_length, 2) #利用公式计算熵
11 for p in label_count.values()])
12 return ent #返回熵
2、设计经验条件熵的算法
1 #经验条件熵
2 def cond_ent(datasets, axis=0):
3 data_length = len(datasets)
4 feature_sets = {} #创建返回的数据集列表
5 for i in range(data_length):
6 feature = datasets[i][axis]
7 if feature not in feature_sets:
8 feature_sets[feature] = []
9 feature_sets[feature].append(datasets[i])
10 cond_ent = sum([(len(p)/data_length)*calc_ent(p) for p in feature_sets.values()])
11 return cond_ent
3、设计信息增益的算法
1 #信息增益
2 def info_gain(ent, cond_ent):
3 return ent - cond_ent
4
5 def info_gain_train(datasets):
6 count = len(datasets[0]) - 1 #特征数量
7 ent = calc_ent(datasets) #计算数据集的熵
8 best_feature = []
9 for c in range(count): #遍历所有特征
10 c_info_gain = info_gain(ent, cond_ent(datasets,axis=c))
11 best_feature.append((c, c_info_gain))
12 print('特征({})的信息增益为 {:.3f}'.format(labels[c], c_info_gain))
13 #比较大小
14 best_ = max(best_feature, key=lambda x: x[-1])
15 return '特征({})的信息增益最大，选择为根节点特征'.format(labels[best_[0]])
2.2、针对给定的房贷数据集(数据集表格见附录1)实现ID3算法
1、导入需要的包
1 # 导入需要的包 2 import numpy as np 3 import pandas as pd 4 import math 5 from math import log
2、创建房贷数据集
1 def create_data(): 2 datasets = [['青年','否','否','一般','否'], #数据集 3 ['青年','否','否','好','否'], 4 ['青年','是','否','好','是'], 5 ['青年','是','是','一般','是'], 6 ['青年','否','否','一般','否'], 7 ['中年','否','否','一般','否'], 8 ['中年','否','否','好','否'], 9 ['中年','是','是','好','是'], 10 ['中年','否','是','非常好','是'], 11 ['中年','否','是','非常好','是'], 12 ['老年','否','是','非常好','是'], 13 ['老年','否','是','好','是'], 14 ['老年','是','否','好','是'], 15 ['老年','是','否','非常好','是'], 16 ['老年','否','否','一般','否'], 17 ] 18 #分类属性 19 labels = [u'年龄', u'有工作', u'有自己的房子', u'信贷情况', u'类别'] 20 #返回数据集和每个维度的名称 21 return datasets, labels 22 datasets,labels = create_data() 23 train_data = pd.DataFrame(datasets,columns=labels) 24 train_data
3、定义节点类二叉树
1 # 定义节点类 二叉树
2 class Node:
3 def __init__(self, root=True, label=None, feature_name=None, feature=None):
4 self.root = root
5 self.label = label
6 self.feature_name = feature_name
7 self.feature = feature
8 self.tree = {}
9 self.result = {
10 'label:': self.label,
11 'feature': self.feature,
12 'tree': self.tree
13 }
14
15 def __repr__(self):
16 return '{}'.format(self.result)
17
18 def add_node(self, val, node):
19 self.tree[val] = node
20
21 def predict(self, features):
22 if self.root is True:
23 return self.label
24 return self.tree[features[self.feature]].predict(features)
25
26
27 class DTree:
28 def __init__(self, epsilon=0.1):
29 self.epsilon = epsilon
30 self._tree = {}
4、设计算法
#计算熵
@staticmethod
def calc_ent(datasets):
4 data_length = len(datasets)
5 label_count = {}
6 for i in range(data_length):
7 label = datasets[i][-1]
8 if label not in label_count:
9 label_count[label] = 0
10 label_count[label] += 1
11 ent = -sum([(p / data_length) * log(p / data_length, 2)
12 for p in label_count.values()])
13 return ent
14
15 # 计算经验条件熵
16 def cond_ent(self, datasets, axis=0):
17 data_length = len(datasets)
18 feature_sets = {}
19 for i in range(data_length):
20 feature = datasets[i][axis]
21 if feature not in feature_sets:
22 feature_sets[feature] = []
23 feature_sets[feature].append(datasets[i])
24 cond_ent = sum([(len(p) / data_length) * self.calc_ent(p)
25 for p in feature_sets.values()])
26 return cond_ent
27
28 # 信息增益
29 @staticmethod
30 def info_gain(ent, cond_ent):
31 return ent - cond_ent
5、特征选择：选择最好的特征划分数据集
1 def info_gain_train(self, datasets): 2 count = len(datasets[0]) - 1 3 ent = self.calc_ent(datasets) 4 best_feature = [] 5 for c in range(count): 6 c_info_gain = self.info_gain(ent, self.cond_ent(datasets, axis=c)) 7 best_feature.append((c, c_info_gain)) 8 # 比较大小 9 best_ = max(best_feature, key=lambda x: x[-1]) 10 return best_ 11 12 def train(self, train_data): 13 """ 14 input:数据集D(DataFrame格式)，特征集A，阈值eta 15 output:决策树T 16 """ 17 _, y_train, features = train_data.iloc[:, : 18 -1], train_data.iloc[:, 19 -1], train_data.columns[: 20 -1] 21 # 1,若D中实例属于同一类Ck，则T为单节点树，并将类Ck作为结点的类标记，返回T 22 if len(y_train.value_counts()) == 1: 23 return Node(root=True, label=y_train.iloc[0]) 24 25 # 2, 若A为空，则T为单节点树，将D中实例树最大的类Ck作为该节点的类标记，返回T 26 if len(features) == 0: 27 return Node( 28 root=True, 29 label=y_train.value_counts().sort_values( 30 ascending=False).index[0]) 31 32 # 3,计算最大信息增益 同5.1,Ag为信息增益最大的特征 33 max_feature, max_info_gain = self.info_gain_train(np.array(train_data)) 34 max_feature_name = features[max_feature] 35 36 # 4,Ag的信息增益小于阈值eta,则置T为单节点树，并将D中是实例数最大的类Ck作为该节点的类标记，返回T 37 if max_info_gain < self.epsilon: 38 return Node( 39 root=True, 40 label=y_train.value_counts().sort_values( 41 ascending=False).index[0]) 42 43 # 5,构建Ag子集 44 node_tree = Node( 45 root=False, feature_name=max_feature_name, feature=max_feature) 46 47 feature_list = train_data[max_feature_name].value_counts().index 48 for f in feature_list: 49 sub_train_df = train_data.loc[train_data[max_feature_name] == 50 f].drop([max_feature_name], axis=1) 51 52 # 6, 递归生成树 53 sub_tree = self.train(sub_train_df) 54 node_tree.add_node(f, sub_tree) 55 56 # pprint.pprint(node_tree.tree) 57 return node_tree 58 59 def fit(self, train_data): 60 self._tree = self.train(train_data) 61 return self._tree 62 63 def predict(self, X_test): 64 return self._tree.predict(X_test)
6、输出结果
1 datasets, labels = create_data() 2 data_df = pd.DataFrame(datasets, columns=labels) 3 dt = DTree() 4 tree = dt.fit(data_df) 5 tree
2.3、针对iris数据集，应用sklearn的决策树算法进行类别预测
1、建模
1 from sklearn.tree import DecisionTreeClassifier 2 3 clf = DecisionTreeClassifier() 4 clf.fit(X_train, y_train,) 5 clf.score(X_test, y_test)
2、画树
1 from sklearn.tree import export_graphviz
2 import graphviz
3
4 tree_pic = export_graphviz(clf, out_file="mytree.pdf")
5 with open('mytree.pdf') as f:
6 dot_graph = f.read()
7
8 graphviz.Source(dot_graph)
3、讨论ID3、5算法的应用场景
ID3算法应用场景：应用于机器学习、知识发现和数据挖掘等领域
C4.5算法应用场景：应用机器学习、知识发现、金融分析、遥感影像分类、生产制造、分子生物学和数据挖掘等领
4、决策树剪枝策略
一、预剪枝
预剪枝的方法主要包括以下几种：
1、树的高度限制：设定树的高度最大值，当达到限定值时，停止树的生长；
2、训练样本限制：对一个拥有较少训练样本的节点进行分裂时容易出现过拟合现象，因此设定样本量阀值，当样本量少于阀值时停止生长；
3、系统性能增益：当属性的信息增益小于某个指定的阀值时停止增长；
4、纯度限制：当该节点中某个类别的占比超过指定阀值时，停止生长。
二、后剪枝
剪枝是一个判断把非叶子节点替代为叶子节点时是否更有利于分类的过程。在实际的应用中，后剪枝比预剪枝具有更广的应用。后剪枝算法之间的差异包括以下几个方面：自上而下还是自下而上、是否需要独立的剪枝数据集、节点的误差估计方法、剪枝条件。主要的剪枝方法有降低错误剪枝、悲观错误剪枝、基于错误剪枝、代价-复杂度剪枝、最小错误剪枝。
5、资料参考
标签：datasets,self,feature,算法,实验,ent,data,决策树 From： https://www.cnblogs.com/STTM-HQ/p/16840993.html