决策树是一类很重要应用也非常广泛的机器学习算法，属于有监督算法。以一个简单的二分类任务来举例，决策树就是针对一些问题，不断问是否，从而进行判断的流程。这些问题组成的分支就像是一颗倒长的树因此被称为决策树。其实和《数据结构与算法》课程中的树的结构比较类似。大多数人应该玩过一个游戏，就是一个人A在脑中想一个答案，由另一个人B发问，A负责回答是或否，从而在连续几次回答后，准确猜中A脑中所想，这个过程其实就是一个决策树的决策过程。周志华《机器学习》中的经典例子如下：
决策树学习的基本算法如下，其实就是一个分而治之的过程：
决策树最关键的问题在于划分的节点如何选择。对于划分节点的选择方法不同，产生了多种不同的算法，其中最著名的是ID3和C4.5算法。
ID3算法是基于信息增益来选择划分节点，C4.5是基于信息增益率来选择划分节点。还有一种CART算法，是可以用户分类和回归的二叉决策树，也被广泛使用。
信息熵
首先，需要定义一个表明信息多少的概念：信息熵，假定当前样本集合D中第k类样本所占的比例为pk(k=1,2,...,|y|)，则D的信息熵定义为：
Ent(D)的值越小，D的纯度越高。直观的理解就是，一个事件发生的概率越低，它所包含的信息量越大，如果一个事件发生的概率越高，它所包含的信息量也越低。比如：太阳从东方升起，这句话的信息量就很低，因为这就是必然事件，至少在地球上是这样的。再比如，中国队获得了世界杯决赛圈的资格，这句话信息量就很高了，因为概率实在太小。
假设有如下的分类问题，根据天气，温度，湿度，是否有风几个因素来判断是否去打高尔夫球，我们首先计算一下各个属性的信息熵。
该决策问题是：是否去打高尔夫球，数据集合为D，结果有两种，是或者否，数据集中有5个“否”，9个“是”，所以：
E(D) = -(p1logp1+p2logp2) = -(5/14 * log(5/14) + 9/14 * log(9/14)) = -(0.36log(0.36) + 0.64log(0.64)) = -(0.36(-1.47) + 0.64(-0.64)) = 0.94
也就是这个分类问题的信息量是0.94。
写成程序如下：
import numpy as np
import math
def entropy(data_list):
# 计算每种类型的概率
probs = [data_list.count(i)/len(data_list) for i in set(data_list)]
# 计算信息熵
entropy = -sum([probs[i]*math.log(probs[i],2) for i in range(len(probs))])
return entropy
import pandas as pd
df = pd.read_excel('计算例子.xlsx')
round(entropy(list(df['是否去打高尔夫球'])),2) # 对结果保留二位小数点
# 输出：0.94
信息增益
假定离散属性a有V个可能的取值{a1,a2,...,aV }，若使用a来对样本集D进行划分，则会产生V个分支结点，其中第v个分支结点包含了D中所有在属性a上取值为av的样本，记为Dv。我们可以计算出v的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重|Dv|/|D|，即样本数越多的分支结点的影响越大，于是可计算出用属性a对样本集D进行划分所获得的“信息增益”。
所以我们需要采用信息增益最大的属性来进行划分。
下面我们再计算每个属性的信息增益。
首先来看天气属性，一共有14个值，其中5个晴，4个阴，5个雨。
E(天气) = 5/14E(晴)+4/14E(阴)+5/14E(雨)
在晴天的情况下，一共有两条记录是去的，三条记录是不去的，所以：E(晴) = -(2/5 * log(2/5) + 3/5 * log(3/5)) = -(0.4log0.4 + 0.6log0.6) = -(0.4(-1.32)+0.6(-0.74)) = 0.97
在阴天的情况下，都是去的，所以：E(阴) = -(1log1) = 0
在雨天的情况下，三条记录是去的，两天记录是不去的，所以：E(雨) = -(2/5 * log(2/5) + 3/5 * log(3/5)) = 0.97
所以：E(天气) = 5/140.97 + 4/140 + 5/140.97 = 0.69
天气的信息增益：Gain(天气) = E(D)-E(天气) = 0.94-0.69 = 0.25，因此天气属性的信息增益是0.25。
计算信息增益的程序如下：
# 根据某个属性划分数据集
def split_data(df, col):
return [df[df[col]==key]['是否去打高尔夫球'] for key in set(df[col])]
# 这里先获取到该属性的值，遍历这个属性的值，把数据集分为该属性的各种不同取值的子集
# 天气取值为阴的时候的信息熵
entropy(list(split_data(df, '天气')[0]))
# 输出：-0.0
# 天气取值为雨的时候的信息熵
entropy(list(split_data(df, '天气')[1]))
# 输出：0.9709505944546686
# 天气取值为晴的时候的信息熵
entropy(list(split_data(df, '天气')[2]))
# 输出：0.9709505944546686
# 属性“天气”的信息熵
entropy_weather =
len(split_data(df, '天气')[0])/len(df)*entropy(list(split_data(df, '天气')[0]))+\
len(split_data(df, '天气')[1])/len(df)*entropy(list(split_data(df, '天气')[1]))+\
len(split_data(df, '天气')[2])/len(df)*entropy(list(split_data(df, '天气')[2]))
round(entropy_weather,2)
# 输出：0.69
# 属性“天气”的信息增益
gain_weather = round(entropy(list(df['是否去打高尔夫球'])),2) - round(entropy_weather,2)
gain_weather
# 输出：0.25
同样的，我们得到属性“温度”的信息增益0.03，属性“湿度”的信息增益0.15，属性“是否有风”的信息增益0.05，所以，天气的信息增益最高，应该按照“天气”属性进行划分。
信息增益率
根据信息增益来划分属性，一般效果不错，但是如果把记录的序号也作为一个属性，那么序号属性就有非常高的信息增益，而这种划分是没有意义的，所以出现了C4.5算法。C4.5算法为了避免ID3算法取值较多的属性有更多的偏好，所以采用了信息增益率来划分属性。a的信息增益率的意思就是把计算出来的信息增益值取除以属性a的IV值，也叫做属性a的固有值，一般来说属性a的取值数越多，IV值越大。
简单来说，信息增益率就是一个属性的信息增益值去除以该属性的一个类似出现频率的值（当然不是出现的频率，但可以类似的理解），避免了因为某个属性取值数目过多导致的信息增益过高。
IV(天气) = -[(5/14)log(5/14) + (4/14)log(4/14) + (5/14)*log(5/14)]=1.58
Gain_ratio(天气) = 0.25/IV(天气) = 0.25/1.58 = 0.16
程序如下：
def iv(col):
iv_weather = 0
for i in range(len(split_data(df, col))):
d = len(split_data(df, col)[i])/len(df)
iv_weather -= d*math.log(d,2)
return iv_weather
# 天气的信息增益率
gain_ratio_weather = gain_weather/iv('天气')
round(gain_ratio_weather,2)
# 输出：0.16
# 温度的信息增益率
gain_ratio_temp = gain_temp/iv('温度')
round(gain_ratio_temp,2)
# 输出：0.02
# 湿度的信息增益率
gain_ratio_wet = gain_wet/iv('湿度')
round(gain_ratio_wet,2)
# 输出：0.15
# 是否有风的信息增益率
gain_ratio_wind = gain_wind/iv('是否有风')
round(gain_ratio_wind,2)
# 输出：0.05
基尼系数
基尼系数是用来衡量数据集纯度的一个值。CART算法采用基尼系数来来划分属性。基尼值定义为：
属性a的基尼指数定义为：
基尼系数，反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。可见一个数据集纯度越高，随机抽取的两个样本应该越一致，也就是基尼系数越小。所以划分数据集生成决策树的时候，应该选择使得划分后的子集基尼系数最小的属性。
拿属性天气的基尼指数来举例，Gini_index(天气) = 5/14(2/5(1-2/5)+3/5(1-3/5)) + 9/14(7/9(1-7/9)+2/9(1-2/9))=0.46，意思就是，一共14条记录，有5条记录天气是晴的，有9条记录天气时非晴的。而5条天晴的记录中，有三天没去打高尔夫球，两天去了；同样的，9天非晴的记录中，7天去打高尔夫球了，2天没去。
程序如下：
# 基尼系数
def gini(data_list):
# 计算每种类型的概率
probs = [data_list.count(i)/len(data_list) for i in set(data_list)]
# 计算基尼系数
gini = sum([probs[i]*(1-probs[i]) for i in range(len(probs))])
return gini
round(gini(list(df['是否去打高尔夫球'])),2)
# 输出基尼系数：0.46
这里定义一个新的分隔数据集函数，获取到数据集col列的值等于key的子集和col列的值不等于key的子集，两个子集互为补集。
def split_data3(df, col, key):
return (df[df[col]!=key]['是否去打高尔夫球'], df[df[col]==key]['是否去打高尔夫球'])
# 基尼指数
def gini_index(df, col, key):
split_result1, split_result2 = split_data3(df, col, key)
gini_index = len(split_result1)/len(df)*gini(list(split_result1))+\
len(split_result2)/len(df)*gini(list(split_result2))
return gini_index
# 天气为晴的时候的基尼指数
gini_index(df, '天气', '晴')
# 输出：0.3936507936507937
# 天气为阴的时候的基尼指数
gini_index(df, '天气', '阴')
# 输出：0.35714285714285715
# 天气为雨的时候的基尼指数
gini_index(df, '天气', '雨')
# 输出：0.4571428571428572
取基尼指数最小的属性和属性值作为分隔节点。
下面我们对这个打高尔夫球问题用sklearn进行编程实现决策树。
from sklearn.tree import DecisionTreeClassifier
from sklearn import tree
X = df.iloc[:,:-1]
y = df.iloc[:,-1]
tree_clf2 = DecisionTreeClassifier(max_depth=2)
tree_clf2.fit(X,y)
可以看到，如果直接把数据这样进行训练，运行会报错：
因为sklearn的决策树不支持对类别数据直接进行计算。所以我们需要对类别数据进行转换，用独热编码OneHotEncoder或者标签编码LabelEncoder。
OneHotEncoder把类别转化成由0，1组成的数据。
from sklearn import preprocessing
from sklearn.preprocessing import OneHotEncoder
#enc = preprocessing.OneHotEncoder()
x = df['天气'].values.reshape(-1, 1)
enc = OneHotEncoder(categories='auto').fit(x)
enc.transform(x).toarray()
# 输出：array([[1., 0., 0.],
[1., 0., 0.],
[0., 1., 0.],
[0., 0., 1.],
[0., 0., 1.],
[0., 0., 1.],
[0., 1., 0.],
[1., 0., 0.],
[1., 0., 0.],
[0., 0., 1.],
[1., 0., 0.],
[0., 1., 0.],
[0., 1., 0.],
[0., 0., 1.]])
LabelEncoder把类别直接转化成整数：
from sklearn.tree import DecisionTreeClassifier
from sklearn import tree
from sklearn.preprocessing import LabelEncoder
LabelEncoder = LabelEncoder()
for i in range(df.shape[1]):
df.iloc[:,i] =LabelEncoder.fit_transform(df.iloc[:,i])
我这里选择LabelEncoder进行编码。编码后训练并输出训练的分数。
X = df.iloc[:,:-1]
y = df.iloc[:,-1]
tree_clf2 = DecisionTreeClassifier(max_depth=2)
tree_clf2.fit(X,y)
score = tree_clf2.score(X,y)
print("acc :", score)
# 输出：acc : 0.8571428571428571
可以看到训练精度接近86%。
# 画出决策树
tree.plot_tree(tree_clf2)
可以看到决策树虽然画出来了，但是结果不是很直观。我们可以用graphviz工具使得结果更直观。
import graphviz
feature_name = ['天气', '温度', '湿度', '是否有风']
target_name = ['不去打高尔夫球', '去打高尔夫球']
dot_data = tree.export_graphviz(tree_clf2
, out_file=None
, feature_names=feature_name
, class_names=target_name
, filled=True
, rounded=True
)
graph = graphviz.Source(dot_data.replace('helvetica', '"Microsoft YaHei"'), encoding='utf-8')
graph.view("tree")
下面我们对一个新的数据进行预测，假设有一个数据：天气：晴，温度：适宜，湿度：高，是否有风：有，想要预测是否去打高尔夫球。
d = [{'天气':'晴','温度':'适宜','湿度':'高','是否有风':'是'}]
d = pd.DataFrame(d)
df = df.append(d, ignore_index = True) # 将要预测的数据附加到训练数据集最后
# 统一进行LabelEncoder编码
from sklearn.preprocessing import LabelEncoder
LabelEncoder = LabelEncoder()
for i in range(df.shape[1]):
df.iloc[:,i] =LabelEncoder.fit_transform(df.iloc[:,i])
# 预测结果
tree_clf2.predict(np.array(df.iloc[-1,:-1]).reshape(1,4))
# 输出：array([0])
# 预测结果概率
tree_clf2.predict_proba(np.array(df.iloc[-1,:-1]).reshape(1,4))
# 输出：array([[1., 0.]])
可以看到这个数据的预测结果是：不去打高尔夫球。
决策树还有包括剪枝和连续值的处理问题可以参考相关的书籍。
网友评论