决策树（Decision Tree）原理及实现
一、算法简介
1.1 基本模型介绍
决策树是一类常见的机器学习方法，可以帮助我们解决分类与回归两类问题。模型可解释性强，模型符合人类思维方式，是经典的树形结构。分类决策数模型是一种描述对实例进行分类的树形结构。决策树由结点 (node) 和有向边 (directed edge) 组成。结点包含了一个根结点 (root node)、若干个内部结点 (internal node) 和若干个叶结点 (leaf node)。内部结点表示一个特征或属性，叶结点表示一个类别。
简单而言，决策树是一个多层if-else函数，对对象属性进行多层if-else判断，获取目标属性的类别。由于只使用if-else对特征属性进行判断，所以一般特征属性为离散值，即使为连续值也会先进行区间离散化，如可以采用二分法（bi-partition）。
思考：选哪些特征属性参与决策树建模、哪些属性排在决策树的顶部，哪些排在底部，对属性的值该进行什么样的判断、样本属性的值缺失怎么办、如果输出不是分类而是数值能用么、对决策没有用或没有多大帮助的属性怎么办、什么时候使用决策树？
1.2 决策树特点
决策树优点
1）决策树易于理解和实现，人们在在学习过程中不需要使用者了解很多的背景知识，这同时是它的能够直接体现数据的特点，只要通过解释后都有能力去理解决策树所表达的意义。
2）对于决策树，数据的准备往往是简单或者是不必要的，而且能够同时处理数据型和常规型属性，在相对短的时间内能够对大型数据源做出可行且效果良好的结果。
3）易于通过静态测试来对模型进行评测，可以测定模型可信度；如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。
决策树缺点
1）对连续性的字段比较难预测。
2）对有时间顺序的数据，需要很多预处理的工作。
3）当类别太多时，错误可能就会增加的比较快。
4）一般的算法分类的时候，只是根据一个字段来分类。
二、算法分类和流程
2.1 算法分类
现有的关于决策树学习的主要思想主要包含以下 3 个研究成果：
由 Quinlan 在 1986 年提出的 ID3 算法
由 Quinlan 在 1993 年提出的 C4.5 算法
由 Breiman 等人在 1984 年提出的 CART 算法
算法比较
2.2 算法流程
其他见博客https://www.cnblogs.com/geo-will/p/9773621.html
二、实现
2.1基于sklearn的代码实现
python的sklearn库也提供了决策树的模型-DecisionTreeClassifier，可以直接调用，使用方便。具体介绍参见官方文档
https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html#
lass sklearn.tree.DecisionTreeClassifier(*, criterion='gini', splitter='best', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, class_weight=None, presort='deprecated', ccp_alpha=0.0)[source]
实例：项目采用用决策树预测隐形眼镜类型，数据集下载地址：https://github.com/Jack-Cherish/Machine-Learning/blob/master/Decision%20Tree/classifierStorage.txt
# -*- coding: UTF-8 -*-
from sklearn.preprocessing import LabelEncoder, OneHotEncoder
from sklearn.externals.six import StringIO
from sklearn import tree
import pandas as pd
import numpy as np
import pydotplus
if __name__ == '__main__':
with open('lenses.txt', 'r') as fr: #加载文件
lenses = [inst.strip().split('\t') for inst in fr.readlines()] #处理文件
lenses_target = [] #提取每组数据的类别，保存在列表里
for each in lenses:
lenses_target.append(each[-1])
print(lenses_target)
lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate'] #特征标签
lenses_list = [] #保存lenses数据的临时列表
lenses_dict = {} #保存lenses数据的字典，用于生成pandas
for each_label in lensesLabels: #提取信息，生成字典
for each in lenses:
lenses_list.append(each[lensesLabels.index(each_label)])
lenses_dict[each_label] = lenses_list
lenses_list = []
# print(lenses_dict) #打印字典信息
lenses_pd = pd.DataFrame(lenses_dict) #生成pandas.DataFrame
# print(lenses_pd) #打印pandas.DataFrame
le = LabelEncoder() #创建LabelEncoder()对象，用于序列化
for col in lenses_pd.columns: #序列化
lenses_pd[col] = le.fit_transform(lenses_pd[col])
# print(lenses_pd) #打印编码信息
clf = tree.DecisionTreeClassifier(max_depth = 4) #创建DecisionTreeClassifier()类
clf = clf.fit(lenses_pd.values.tolist(), lenses_target) #使用数据，构建决策树
dot_data = StringIO()
tree.export_graphviz(clf, out_file = dot_data, #绘制决策树
feature_names = lenses_pd.keys(),
class_names = clf.classes_,
filled=True, rounded=True,
special_characters=True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
graph.write_pdf("tree.pdf") #保存绘制好的决策树，以PDF的形式存储。
2.2基于Python实现
2.2.1基于ID3算法，实现预测贷款用户是否具有偿还贷款的能力
可以参考https://blog.csdn.net/Big_Pai/article/details/89516630
2.2.2 CART算法实现
# -*- coding:utf-8 -*-
# Decision tree by cart决策树，cart算法，算法参考李航《统计学习方法》P71
#author:Tomator
import numpy as np
import math
from sklearn.model_selection import train_test_split
# 创建测试数据集
def createDataSet():
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 = ['年龄', '有工作', '有自己的房子', '信贷情况'] # 分类属性
return dataSet, labels # 返回数据集和分类属性
# 计算基尼指数
def cal_gini(data_vector):
nums_data = len(data_vector) # 数据集样本数
counts_by_labels = {} # 用来保存每个label下的样本数
gini = 0 #基尼指数
p_sum=0 #每个类别的样本数
for vector in data_vector:
if vector[-1] not in counts_by_labels: # vector[-1]为label值
counts_by_labels[vector[-1]] = 0
counts_by_labels[vector[-1]] += 1 # 统计label出现的次数
for key in counts_by_labels:
p = float(counts_by_labels[key] / nums_data) # 计算每个标签出现的概率
p_sum+= p**2
gini=1-p_sum # 公式5.24
return gini
# 返回类列表中出现次数最多的类标签
def max_class(label_list):
count_label = {}
for label in label_list:
if label not in count_label:
count_label[label] = 0
count_label[label] += 1
# 选择字典value最大的所对应的key值
return max(count_label, key=count_label.get)
"""
根据每个特征划分数据集
data_vector
index_feature：特征的索引位置i
value：用来划分的特征取值
返回划分后的子数据及样本数，和子数据集（子数据集剔除了第i列特征）
"""
# 根据cart算法划分数据集，cart算法生成的是二叉数，因此分割之后也就只有两个子数据集。返回分割后的D1和D2数据集
def split_datatset_cart(data_vector, index_feature, value):
split_set_yes = [] #判别为“是”的子数据集
split_set_no=[] #判别为“否”的子数据集
for vector in data_vector:
if vector[index_feature] == value:
# 去掉第i列特征
split_1 = vector[:index_feature]
split_1.extend(vector[index_feature + 1:])
split_set_yes.append(split_1)
else:
split_2 = vector[:index_feature]
split_2.extend(vector[index_feature + 1:])
split_set_no.append(split_2)
# 分别输出D1和D2数据集以及对应的数据集样本数
return len(split_set_yes),split_set_yes,len(split_set_no),split_set_no
# 选择最优分类特征
# 生成决策树的方法：cart算法
def choose_bestfeture_cart(data_vector):
nums_data = len(data_vector)
nums_feature = len(data_vector[0]) - 1 # 每个样本所包含的特征个数
min_gini = float('inf') # 表示最小的基尼指数
best_index_feature = 0 # 表示最优特征的索引位置index
best_split_point=None #表示最优的切分点
for i in range(nums_feature): # 遍历所有的特征
features_i_set = [vector[i] for vector in data_vector] # 提取第i个特征中所包含的可能取值
features_i_set = list(set(features_i_set)) # 对特征值去重
feature_gini = 0 #每个特征中每个特征值所对应的基尼指数
# 如果第i个特征向量包含的特征取值个数小于2，则只有一个切分点。参考P71例5.4
if len(features_i_set)<=2:
# 同时选取features_i_set中数值最大特征取值为切分点。当然选取最小取值也有一样的结果，这只是设定的一个规矩。
# fea为切分点
fea=max(features_i_set)
# 根据切分点进行划分子数据集
nums_di_yes, di_set_yes, nums_di_no, di_set_no = split_datatset_cart(data_vector, i, fea) #
p_di_yes = nums_di_yes / nums_data # 计算|Di|/|D|
gini_yes_di = cal_gini(di_set_yes) # 计算yes子类的gini指数
feature_gini += p_di_yes * gini_yes_di
p_di_no = nums_di_no / nums_data
gini_yes_no = cal_gini(di_set_no) # 计算no子类的gini指数
feature_gini += p_di_no * gini_yes_no
# 选取最优的分类特征和最优切分点
if feature_gini < min_gini:
min_gini = feature_gini
best_index_feature = i
best_split_point = fea
# 如果第i个特征向量包含的特征取值个数小于2，则有多个切分点
else:
for fea in features_i_set: # 遍历第i个特征的所有vlaue
nums_di_yes, di_set_yes,nums_di_no, di_set_no = split_datatset_cart(data_vector, i, fea) #
p_di_yes = nums_di_yes / nums_data # 计算|Di|/|D|
gini_yes_di = cal_gini(di_set_yes) # 计算yes子类的gini指数
feature_gini += p_di_yes * gini_yes_di
p_di_no=nums_di_no/nums_data
gini_yes_no=cal_gini(di_set_no)
feature_gini += p_di_no*gini_yes_no
# 选取最优的分类特征和最优切分点
if feature_gini<min_gini:
min_gini=feature_gini
best_index_feature=i
best_split_point=fea
# print(best_index_feature,best_split_point)
return best_index_feature,best_split_point # 返回最优分类特征的索引位置和最优切分点
# 决策树的生成
class Decision_tree(object):
def __init__(self, data_vector, labels):
# 数据集
self.data_vector = data_vector
# 特征标签
self.labels = labels
# 用于保存最优特征的索引信息，列表形式输出
self.best_feature_index_list=[]
# 生成决策树，返回决策树tree，字典形式
def tree_main(self):
tree = self.create_decision_tree(self.data_vector, self.labels)
return tree
"""
递归函数，用于生成每一个子树,并返回。
《统计学习方法》CART算法
data_vector：每一个待分类数据集
labels：待分类特征标签
"""
def create_decision_tree(self,data_vector, labels):
nums_label = [vector[-1] for vector in data_vector]
# 如果数据集中所有实例属于同一个类，则停止划分。返回该类 标签。
if len(set(nums_label)) == 1:
return nums_label[0]
# 如果特征集只有一类时，即已经遍历完了所有特征，则停止划分。返回出现次数最多的类标签
if len(data_vector[0]) == 1:
return max_class(nums_label)
best_index_feature,best_split_point = choose_bestfeture_cart(data_vector) # 选择最优特征
# best_feature_index_list存放每一个最优分类特征的索引值和对应的切分点，以两者的元组形式存放。
self.best_feature_index_list.append((best_index_feature,best_split_point))
best_feature_label = labels[best_index_feature] # 最优特征的标签
myTree = {best_feature_label: {}} # 子决策树，key为最优特征的标签，value为子决策树
del (labels[best_index_feature]) # 删除已经使用过的最优特征标签
# 规定左子树为A=a的样本，右子树为A！=a的样本，并规定右子树的标签为“-best_split_point”！！！这样可以便于在进行predict时方便分类。
nums_di_yes, di_set_yes, nums_di_no, di_set_no = split_datatset_cart(data_vector,best_index_feature,best_split_point)
# 左子树
myTree[best_feature_label][best_split_point] = self.create_decision_tree(di_set_yes, labels)
# 右子树
myTree[best_feature_label][-best_split_point] = self.create_decision_tree(di_set_no, labels)
return myTree
if __name__ == '__main__':
dataSet, labels = createDataSet()
# best_index,point_split=choose_bestfeture_cart(dataSet)
# print(labels[best_index],point_split)
# 划分训练集和测试集
x_train, x_test = train_test_split(dataSet, test_size=0.3, random_state=0)
#
tree= Decision_tree(dataSet, labels)
decision_tree=tree.tree_main()
print(decision_tree)
print(tree.best_feature_index_list)
# test_vector=[2, 1, 0, 0]
# 由于数据集
# score=0
# for test_vector in x_test:
# predict_result=tree.predict(decision_tree,test_vector)
# print(test_vector,predict_result)
# if predict_result == test_vector[-1]:
# score+=1
# print("测试准确率：%f%%"%(score/len(x_test)*100))
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
