决策树简单介绍及python实战
简介
决策树是一种预测模型,代表的是对象属性与对象值之间的映射关系。决策树是一种树形结构,其中:
-
每个内部结点表示一个属性的测试
-
每个分支表示一个测试输出
-
每个叶结点代表一种类别
分类
按预测结果的差异,决策树学习可细分两类。
-
分类树,其预测结果仅限于一组离散数值。树的每个分支对应一组由逻辑与连接的分类特征,而该分支上的叶节点对应由上述特征可以预测出的分类标签。
-
回归树,其预测结果为连续值(例如实数)。
按发展历程(分裂特征),决策树学习可细分五(三)类。
-
CLS是最早的决策树算法。
-
ID3是主流的决策树算法之一,基于信息增益进行特征的选择和树的生长
-
C4.5是ID3的改进,基于信息增益率来选择最优属性。
-
CART是可用于分类与回归任务的二叉决策树,广泛使用。
-
RF(Random Forest,随机森林)是把决策树并行集成的组合算法。
-
GBDT/XGBoost/LightGBM/catboost:boosting系列模型,可以基于树模型做串行集成。
选题意义
依据不同算法的用途,可以用于不同的问题。
后文结构描述
-
首先介绍了相关理论
-
其次使用ID3和C4.5做了一个实例。
-
最后做了一个总结
2.相关理论
涉及数学原理
-
贝叶斯定理
-
贝叶斯概率
-
真值表
-
马尔可夫链
问题定义
公式
-
信息熵,它是消除不确定性所需信息量的度量,也是未知事件可能含有的信息量,可以度量样本集合「纯度」。
对应到机器学习中,假定当前数据集 D 中有 y 类,其中第 k类样本占比为 p_k ,则信息熵的计算公式如下:
Ent(D) = - \sum_{K = 1}^{|y|} p_klog_{2}{p_k}
$$
计算信息熵时约定:
若 p = 0 ,则 plog_2 {p} = 0 ;
Ent(D) 的最小值为0,最大值为 log_2{|y|};
Ent(D)的值越小,则D的“ 纯度 ” 越高。
但 P_k 取值为 1 的时候,信息熵 为 0 ,(很显然这时候概率 1 表示确定事件 ,没有任何不确定性) ;而当 p_k 是均匀分布的时候 ,信息熵取最大值 log(|y|) (此时所有候选同等概率,不确定性最大)
-
信息增益,它衡量的是我们选择某个属性进行划分时信息熵的变化(可以理解为基于这个规则划分,不确定性降低的程度)。
Gain(D,a) = Ent(D) - \sum_{v=1}^v \frac{|D^v|}{|D|}Ent(D^v)
$$
信息增益描述了一个特征带来的信息量的多少。在决策树分类问题中,信息增益就是决策树在进行属性选择划分前和划分后的信息差值。典型的决策树算法ID3就是基于信息增益来挑选每一节点分支用于划分的属性(特征)的。
但是信息增益有一个问题,它偏向取值较多的特征。原因是,当特征的取值较多时,根据此特征划分更容易得到纯度更高的子集,因此划分之后的熵更低,由于划分前的熵是一定的。因此信息增益更大,因此信息增益比较偏向取值较多的特征。
-
信息增益率,相比信息增益,多了一个衡量本身属性的分散程度的部分作为分母。
Gain_ratio(D,a) = \frac{Gain(D,a)}{IV(a)}
$$
IV(a) = -\sum_{v=1}^V\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}
$$
启发式:先从候选划分属性中找出信息增益高干平均水平的,再从中选取增益率最高的。
-
基尼系数 ,来表示数据集的不纯度。基尼指数越大,表示数据集越不纯。
Gini(D) = \sum_{k=1}^{|y|}\sum_{k’\not=k}p_kp_{k’} = 1-\sum_{k=1}^{|y|}p_k^2
$$
Gini(D) 越小,数据集 D 的纯度越高。
3.算法描述
算法流程
决策树学习通常包括3个步骤:特征选择、决策树的生成和决策树的修剪。
这里使用ID3算法做一个简单的实例。
ID | 年龄 | 有工作 | 有自己的房子 | 信贷情况 | 类别 |
---|---|---|---|---|---|
1 | 青年 | 否 | 否 | 一般 | 否 |
2 | 青年 | 否 | 否 | 好 | 否 |
3 | 青年 | 是 | 否 | 好 | 是 |
4 | 青年 | 是 | 是 | 一般 | 是 |
5 | 青年 | 否 | 否 | 一般 | 否 |
6 | 中年 | 否 | 否 | 一般 | 否 |
7 | 中年 | 否 | 否 | 好 | 否 |
8 | 中年 | 是 | 是 | 好 | 是 |
9 | 中年 | 否 | 是 | 非常好 | 是 |
10 | 中年 | 否 | 是 | 非常好 | 是 |
11 | 老年 | 否 | 是 | 非常好 | 是 |
12 | 老年 | 否 | 是 | 好 | 是 |
13 | 老年 | 是 | 否 | 好 | 是 |
14 | 老年 | 是 | 否 | 非常好 | 是 |
15 | 老年 | 否 | 否 | 一般 | 否 |
在编写代码之前,我们先对数据集进行属性标注。不对数据集进行属性标注也可以。
-
年龄:0代表青年,1代表中年,2代表老年;
-
有工作:0代表否,1代表是;
-
有自己的房子:0代表否,1代表是;
-
信贷情况:0代表一般,1代表好,2代表非常好;
-
类别(是否给贷款):no代表否,yes代表是。
核心代码
from math import log
import operator
import pickle
import json
import pandas as pd
def calcShannonEnt(dataSet):
# 统计数据数量
numEntries = len(dataSet)
# 存储每个label出现次数
label_counts = {}
# 统计label出现次数
for featVec in dataSet:
current_label = featVec[-1]
if current_label not in label_counts: # 提取label信息
label_counts[current_label] = 0 # 如果label未在dict中则加入
label_counts[current_label] += 1 # label计数
shannon_ent = 0 # 经验熵
# 计算经验熵
for key in label_counts:
prob = float(label_counts[key]) / numEntries
shannon_ent -= prob * log(prob, 2)
return shannon_ent
def calcFeaturesEnt(dataSet,i):
FeaturesEnt = 0
numEntries = len(dataSet)
dict = {}
for key in [x[i] for x in dataSet]:
dict[key] = dict.get(key, 0) + 1
for keys in dict:
FeaturesEnt += -(dict[keys]/numEntries)*log(dict[keys]/numEntries,2)
return FeaturesEnt
def splitDataSet(data_set, axis, value):
ret_dataset = []
for feat_vec in data_set:
if feat_vec[axis] == value:
reduced_feat_vec = feat_vec[:axis]
reduced_feat_vec.extend(feat_vec[axis + 1:])
ret_dataset.append(reduced_feat_vec)
return ret_dataset
def chooseBestFeatureToSplit(dataSet,算法类别):
if 算法类别 == 'ID3':
# 特征数量
num_features = len(dataSet[0]) - 1
# 计算数据香农熵
base_entropy = calcShannonEnt(dataSet)
# 信息增益
best_info_gain = 0.0
# 最优特征索引值
best_feature = -1
# 遍历所有特征
for i in range(num_features):
# 获取dataset第i个特征
feat_list = [exampel[i] for exampel in dataSet]
# 创建set集合,元素不可重合
unique_val = set(feat_list)
# 经验条件熵
new_entropy = 0.0
# 计算信息增益
for value in unique_val:
# sub_dataset划分后的子集
sub_dataset = splitDataSet(dataSet, i, value)
# 计算子集的概率
prob = len(sub_dataset) / float(len(dataSet))
# 计算经验条件熵
new_entropy += prob * calcShannonEnt(sub_dataset)
# 信息增益
info_gain = base_entropy - new_entropy
# 打印每个特征的信息增益
print("第%d个特征的信息增益为%.3f" % (i, info_gain))
# 计算信息增益
if info_gain > best_info_gain:
# 更新信息增益
best_info_gain = info_gain
# 记录信息增益最大的特征的索引值
best_feature = i
print("最优索引值:" + str(best_feature))
print()
return best_feature
elif 算法类别 == 'C4.5':
return chooseBestFeatureToSplit_1(dataSet)
else:
print('还没写好这个算法!')
return 0
def chooseBestFeatureToSplit_1(dataSet):
# 特征数量
num_features = len(dataSet[0]) - 1
# print(num_features)
# 计算数据香农熵
base_entropy = calcShannonEnt(dataSet)
# 信息增益
info_gain = 0.0
# 信息增益比
info_gain_rate = 0.0
# 最优特征索引值
best_feature = -1
# 存储 信息增益 和 信息增益比
info_gain_dict = {}
info_gain_rate_dict = {}
sum_info_gain = 0
for i in range(num_features):
# 获取dataset第i个特征
feat_list = [exampel[i] for exampel in dataSet]
# 创建set集合,元素不可重合
unique_val = set(feat_list)
# 经验条件熵
new_entropy = 0.0
# 计算信息增益
for value in unique_val:
# sub_dataset划分后的子集
sub_dataset = splitDataSet(dataSet, i, value)
# 计算子集的概率
prob = len(sub_dataset) / float(len(dataSet))
# 计算经验条件熵
new_entropy += prob * calcShannonEnt(sub_dataset)
# 信息增益
info_gain = base_entropy - new_entropy
sum_info_gain += info_gain
info_gain_dict[i] = info_gain
# 信息增益比
info_gain_rate = info_gain/calcFeaturesEnt(dataSet,i)
info_gain_rate_dict[i] = info_gain_rate
# 打印每个特征的信息增益和增益比
print("第%d个特征的信息增益为%.3f,信息增益比为%.3f" % (i, info_gain,info_gain_rate))
info_gain_avg = sum_info_gain/num_features
print('平均信息增益为',info_gain_avg)
for i in range(num_features):
if info_gain_dict[i] < info_gain_avg:
del info_gain_rate_dict[i]
best_feature = max(info_gain_rate_dict,key=info_gain_rate_dict.get)
print("最优索引值:" + str(best_feature))
print()
return best_feature
def majority_cnt(class_list):
class_count = {}
# 统计class_list中每个元素出现的次数
for vote in class_list:
if vote not in class_count:
class_count[vote] = 0
class_count[vote] += 1
# 根据字典的值降序排列
sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)
return sorted_class_count[0][0]
def creat_tree(dataSet, labels, featLabels,算法类别):
# 取分类标签(是否放贷:yes or no)
class_list = [exampel[-1] for exampel in dataSet]
# 如果类别完全相同则停止分类
if class_list.count(class_list[0]) == len(class_list):
return class_list[0]
# 遍历完所有特征时返回出现次数最多的类标签
if len(dataSet[0]) == 1:
return majority_cnt(class_list)
# 选择最优特征
best_feature = chooseBestFeatureToSplit(dataSet,算法类别)
# 最优特征的标签
best_feature_label = labels[best_feature]
# print(best_feature_label)
featLabels.append(best_feature_label)
# 根据最优特征的标签生成树
my_tree = {best_feature_label: {}}
# 删除已使用标签
del(labels[best_feature])
# 得到训练集中所有最优特征的属性值
feat_value = [exampel[best_feature] for exampel in dataSet]
# 去掉重复属性值
unique_vls = set(feat_value)
for value in unique_vls:
my_tree[best_feature_label][value] = creat_tree(splitDataSet(dataSet, best_feature, value), labels, featLabels,算法类别)
return my_tree
def get_num_leaves(my_tree):
num_leaves = 0
first_str = next(iter(my_tree))
second_dict = my_tree[first_str]
for key in second_dict.keys():
if type(second_dict[key]).__name__ == 'dict':
num_leaves += get_num_leaves(second_dict[key])
else:
num_leaves += 1
return num_leaves
def get_tree_depth(my_tree):
max_depth = 0 # 初始化决策树深度
firsr_str = next(iter(my_tree)) # python3中myTree.keys()返回的是dict_keys,不在是list,所以不能使用myTree.keys()[0]的方法获取结点属性,可以使用list(myTree.keys())[0]
second_dict = my_tree[firsr_str] # 获取下一个字典
for key in second_dict.keys():
if type(second_dict[key]).__name__ == 'dict': # 测试该结点是否为字典,如果不是字典,代表此结点为叶子结点
this_depth = 1 + get_tree_depth(second_dict[key])
else:
this_depth = 1
if this_depth > max_depth:
max_depth = this_depth # 更新层数
return max_depth
def classify(input_tree, feat_labels, test_vec):
# 获取决策树节点
first_str = next(iter(input_tree))
# 下一个字典
second_dict = input_tree[first_str]
feat_index = feat_labels.index(first_str)
for key in second_dict.keys():
if test_vec[feat_index] == key:
if type(second_dict[key]).__name__ == 'dict':
class_label = classify(second_dict[key], feat_labels, test_vec)
else:
class_label = second_dict[key]
return class_label
def storeTree(input_tree, filename):
# 存储树
with open(filename, 'wb') as fw:
pickle.dump(input_tree, fw)
# 错误的
# with open(filename, 'w') as fw:
# temp = json.dumps(input_tree, indent=4,ensure_ascii=False)
# fw.write(temp)
def grabTree(filename):
# 读取树
fr = open(filename, 'rb')
return pickle.load(fr)
# 错误的
# f = open(filename, 'r')
# temp = json.loads(f.read())
# return temp
if __name__ == "__main__":
# 数据集
dataSet = [[0, 0, 0, 0, 'no'],
[0, 0, 0, 1, 'no'],
[0, 1, 0, 1, 'yes'],
[0, 1, 1, 0, 'yes'],
[0, 0, 0, 0, 'no'],
[1, 0, 0, 0, 'no'],
[1, 0, 0, 1, 'no'],
[1, 1, 1, 1, 'yes'],
[1, 0, 1, 2, 'yes'],
[1, 0, 1, 2, 'yes'],
[2, 0, 1, 2, 'yes'],
[2, 0, 1, 1, 'yes'],
[2, 1, 0, 1, 'yes'],
[2, 1, 0, 2, 'yes'],
[2, 0, 0, 0, 'no']]
# 分类属性
labels = ['年龄', '有工作', '有自己的房子', '信贷情况']
print(dataSet)
print()
print(calcShannonEnt(dataSet))
print()
featLabels = []
myTree = creat_tree(dataSet, labels, featLabels,'C4.5')
print('树的深度为',get_tree_depth(myTree))
print('树的广度为',get_num_leaves(myTree))
#测试数据
testVec = [0, 1, 1, 1]
result = classify(myTree, featLabels, testVec)
if result == 'yes':
print('放贷')
if result == 'no':
print('不放贷')
# 存储树
storeTree(myTree,'classifierStorage.txt')
# 读取树
myTree2 = grabTree('classifierStorage.txt')
print(myTree2)
print(json.dumps(myTree2, indent=4,ensure_ascii=False))
testVec2 = [1, 0]
result2 = classify(myTree2, featLabels, testVec)
if result2 == 'yes':
print('放贷')
if result2 == 'no':
print('不放贷')
参数解释
注释以及比较详细了
4.应用
可以用到一些分类问题。
实验
运行了上述代码。
结果分析
信息增益比作为特征选择的时候,比信息增益更加“公平”。
但是这里没什么区别,可以换数据集查看效果。
算法一直在改进。