【统计学习方法】决策树
- 决策树
-
- 概念简述
- 决策树剪枝
- 编程实现
-
- 自编程实现
- sklearn实现
决策树
概念简述
这个模型的评估方式,在我理解就好像答题,比如你去银行贷款,工作人员会问你一些问题,有房吗,有车吗,有工作吗,然后再根据年龄、信贷情况等,决定是否要发放贷款给你。
那么先问什么再问什么,问到哪就可以决定拒绝放贷,问到哪就同意放贷,这个就是决策树模型要做的工作了。
首先是要决定先问什么和怎么问,即模型构建的问题,先介绍涉及到的概念,叫做熵和条件熵,描述的是数据的混乱程度,其数学表示如下:
如果计算熵和条件熵中的概率,是由数据估计得到时,所对应的熵与条件熵分别称为经验熵和经验条件熵,一般对于实际问题,都是用的经验熵和经验条件熵。
随之而来的概念是信息增益,定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差,与信息增益比,定义为其信息增益g(D,A)与训练数据集D的经验熵H(D)之比,即:
信息增益表示的是当知道某一信息X后,使得Y的信息不确定性减少的程度,简单说,就是我问你两个问题,就能知道我是不是要借给你钱,那么这两个问题的信息增益就比较大了,因为能够帮我看清是否要借
接下来就是构建决策树了,如果对开头的例子构建决策树,
那么这个问题中的经验熵中的Pi中的i就只有两个取值,对应是否放贷;而这个Pi的计算就是统计得到的,对于输入的训练集(比如10个人,4个放贷,6个拒绝),那么P1就是4/10,P2就是6/10,代入公式即可;
条件经验熵则是在限定某一条件后,比如青年人的放贷和拒绝的概率,或者无工作的人的放贷和拒绝的概率,对应着不同的P1和P2,要分别计算出来;
然后就是计算信息增益或者是信息增益比了,不管算哪个,都是对每一个特征算一遍,以上这几步都是在做“要问哪个问题”这一步,所得的增益或者增益比,选择最大的当做根节点;
选定根节点后,会有是否这两种回答,就引出了子节点,在子节点上再次计算增益或增益比,继续向下做这种一分为二的操作,直到增益的数值小于设定的阈值,即“再问这个问题也没什么价值了”,就不用问了,直接决定是否放贷了,这个决定的节点被称为叶子节点。
以上是我对决策树构建的主体思路的理解,当然里边还有一些细节或者前置条件没有提到,我是感觉上边这几步理解了,对决策树的构建基本就能懂了,对于书中的两个具体的算法,放在下边:
我没有提到的上述两个算法中的内容也大概解释如下:
步骤(1):比如来银行借钱,问一句“你是什么物种”,类似的这种问题毫无意义,大家回答的几乎或者全部是同一个答案,那么就做一个类标记,返回就好了;
步骤(2):和上一个步骤一样,问一句“请提供你拥有的火箭类型”,类似这种根本没法分类的问题,A就等于空集合,采取和上边同样的步骤
另外,上述两个算法的区别就在于评价标准是信息增益还是信息增益比,信息增益比,相较于信息增益的有点就是可以校正选择取值比较多的特征的问题,大概就是说,有一些问题,比如说“你的汽车品牌”,这种问题的回答一定是“没有”或者是各种汽车品牌,这种问题如果用信息增益来算,信息增益是很高的,也就是说会提前问这个问题,但是考虑实际,对很多的同价位的品牌的回答,划分是没有意义的,为了抑制这类问题,就用到了信息增益比这个概念。
决策树剪枝
决策树的剪枝可以理解为决策树的优化过程,是为了解决决策树的过拟合问题。
剪枝,即决策树的修剪,修剪过程中在哪下刀,就涉及到了损失函数,数学表示如下:
以下是书上对损失函数相关参数的解释:
- C(T)表示模型对训练数据的预测误差,即模型与训练数据的拟合程度
- |T|表示模型复杂度
- 参数a≥0控制两者之间的影响。较大的a促使选择较简单的模型(树),较小的a促使选择较复杂的模型。a=0意味着只考虑模型与训练数据的拟合程度,不考虑模型的复杂度。
这个算法的意思就是,遍历的选定每个节点的分支,计算一下剪或不剪情况下的决策树的损失函数,剪完更优秀就剪,否则就不剪。
编程实现
自编程实现
import numpy as np
import pandas as pd
import math
from collections import namedtuple
class Node(namedtuple("Node", "children type content feature label")):
# 孩子节点、分类特征的取值、节点内容、节点分类特征、标签
"""定义节点"""
def __repr__(self):
return str(tuple(self))
以上是后边构建决策树建立节点时要用到的类,使用到的方法是namedtuple(具名元组),用来构造一个带字段名的元组;
class DecisionTree:
"""决策树"""
def __init__(self, method="info_gain_ratio"):
self.tree = None
self.method = method
def _experience_entropy(self, X):
"""计算经验熵"""
# 统计每个取值的出现频率
x_types_prob = X.iloc[:, 0].value_counts() / X.shape[0]
# 计算经验熵
x_experience_entropy = sum((-p * math.log(p, 2) for p in x_types_prob))
return x_experience_entropy
def _conditional_entropy(self, X_train, y_train, feature):
"""计算经验条件熵"""
# feature特征下每个特征取值数量统计
x_types_count = X_train[feature].value_counts()
# 每个特征取值频率计算
x_types_prob = x_types_count / X_train.shape[0]
# 每个特征取值下类别y的经验熵
x_experience_entropy = [self._experience_entropy(y_train[(X_train[feature] == i).values]) for i in x_types_count.index]
# 特征feature对数据集的经验条件熵
x_conditional_entropy = (x_types_prob.mul(x_experience_entropy)).sum()
return x_conditional_entropy
以上是经验熵和经验条件熵的计算,即对训练集处理,构建决策树,用到的公式再次贴出:
另外,计算出现频率时用到了pandas库的iloc方法,这里是用来提取X的列数据,以及后边的value_counts方法,是用来统计X中有哪些不同的值,并计算每个值有多少个重复值;
在计算经验条件熵的时候,
x_types_prob.mul(x_experience_entropy)
:x_types_prob是每个类对应出现的经验概率,x_experience_entropy是每个特征取值下类别y的经验熵,".mul"是pandas库中一维数据类型series的子方法,该类型包含了数据及数据对应的索引,而".mul",则是对相同索引的数据进行相乘,最后再用后边的sum函数加和在一起,即得经验条件熵。
def _information_gain(self, X_train, y_train, feature):
"""计算信息增益"""
return self._experience_entropy(y_train) - self._conditional_entropy(X_train, y_train, feature)
def _information_gain_ratio(self, X_train, y_train, features, feature):
"""计算信息增益比"""
index = features.index(feature)
return self._information_gain(X_train, y_train, feature) / self._experience_entropy(
X_train.iloc[:, index:index + 1])
计算信息增益和信息增益比就是比较简单的运算了,涉及公式再次贴出:
其中,计算信息增益比时,计算的是对应特征的信息增益比,而不是全部特征的,所以要用iloc函数结合list中的index方法提取出对应特征的数据;
def _choose_feature(self, X_train, y_train, features):
"""选择分类特征"""
if self.method == "info_gain_ratio":
info = [self._information_gain_ratio(X_train, y_train, features, feature) for feature in features]
elif self.method == "info_gain":
info = [self._information_gain(X_train, y_train, feature) for feature in features]
else:
raise TypeError
optimal_feature = features[np.argmax(info)]
return optimal_feature
以上是选择分类特征,
info_gain_ratio
表示用信息增益比进行计算,
info_gain
表示用信息增益进行计算,这两种计算方式分别对应了C4.5算法和ID3算法;
def _built_tree(self, X_train, y_train, features, type=None):
"""递归构造决策树"""
# 只有一个节点或已经完全分类,则决策树停止继续分叉
if len(features) == 1 or len(np.unique(y_train)) == 1:
label = list(y_train[0].value_counts().index)[0]
return Node(children=None, type=type, content=(X_train, y_train), feature=None, label=label)
else:
# 选择分类特征值
feature = self._choose_feature(X_train, y_train, features)
features.remove(feature)
# 构建节点,同时递归创建孩子节点
features_iter = np.unique(X_train[feature])
children = []
for item in features_iter:
X_item = X_train[(X_train[feature] == item).values]
y_item = y_train[(X_train[feature] == item).values]
children.append(self._built_tree(X_item, y_item, features, type=item))
return Node(children=children, type=type, content=None, feature=feature, label=None)
以上是决策树构造的函数,选择分类特征值时,用到了上述信息增益或信息增益比的计算,选择增益或者增益比最大的特征作为当前子节点,然后从特征列表中删除该特征,进行递归构建;
构建结点时,np.unique函数是:对于一维数组或者列表,unique函数去除其中重复的元素,并按元素由大到小返回一个新的无元素重复的元组或者列表
另外,上述涉及的for循环,
features_iter
表示在当前选定特征下,所有的选择,例如“有工作”的选择就只有“是”和“否”,所以for循环是对选定的特征的每一个选择,在输入的训练集X,Y中找到分别对应这些值的一栏数据,例如:当feature为“有工作”,item为“是”,取得数据后,即取出了所有有工作的人的数据,在这里添加一个孩子节点并且在这个节点的基础上进行递归构建,也就是说,会持续分叉,直到只有一个节点或已经完全分类,则决策树停止继续分叉,进入下一个循环,最后完成决策树的构建;
def fit(self, X_train, y_train, features):
self.tree = self._built_tree(X_train, y_train, features)
def _search(self, X_new):
tree = self.tree
# 若还有孩子节点,则继续向下搜索,否则搜索停止,在当前节点获取标签
while tree.children:
for child in tree.children:
if X_new[tree.feature].loc[0] == child.type:
tree = child
break
return tree.label
def predict(self, X_new):
return self._search(X_new)
search函数即为遍历搜索子节点的函数,完成决策树构建后,对于新输入的数据,用这个方法进行搜寻,predict函数即返回search函数的结果;
def main():
# 训练数据集
features = ["年龄", "有工作", "有自己的房子", "信贷情况"]
X_train = np.array([
["青年", "否", "否", "一般"],
["青年", "否", "否", "好"],
["青年", "是", "否", "好"],
["青年", "是", "是", "一般"],
["青年", "否", "否", "一般"],
["中年", "否", "否", "一般"],
["中年", "否", "否", "好"],
["中年", "是", "是", "好"],
["中年", "否", "是", "非常好"],
["中年", "否", "是", "非常好"],
["老年", "否", "是", "非常好"],
["老年", "否", "是", "好"],
["老年", "是", "否", "好"],
["老年", "是", "否", "非常好"],
["老年", "否", "否", "一般"]
])
y_train = np.array(["否", "否", "是", "是", "否", "否", "否", "是", "是", "是", "是", "是", "是", "是", "否"])
# 转换成pd.DataFrame模式
X_train = pd.DataFrame(X_train, columns=features)
y_train = pd.DataFrame(y_train)
# 训练
clf = DecisionTree(method="info_gain_ratio")
clf.fit(X_train, y_train, features.copy())
# 预测
X_new1 = np.array([["青年", "否", "是", "一般"]])
X_new1 = pd.DataFrame(X_new1, columns=features)
y_predict1 = clf.predict(X_new1)
X_new2 = np.array([["中年", "是", "否", "好"]])
X_new2 = pd.DataFrame(X_new2, columns=features)
y_predict2 = clf.predict(X_new2)
X_new3 = np.array([["老年", "否", "是", "一般"]])
X_new3 = pd.DataFrame(X_new3, columns=features)
y_predict3 = clf.predict(X_new3)
print(y_predict1, y_predict2, y_predict3)
最后就是主函数了,包含输入的训练集以及要测试的数据。
sklearn实现
from sklearn.tree import DecisionTreeClassifier
from sklearn import preprocessing
import numpy as np
import pandas as pd
def main():
star = time.time()
# 原始样本数据
features = ["age", "work", "house", "credit"]
X_train = pd.DataFrame([
["青年", "否", "否", "一般"],
["青年", "否", "否", "好"],
["青年", "是", "否", "好"],
["青年", "是", "是", "一般"],
["青年", "否", "否", "一般"],
["中年", "否", "否", "一般"],
["中年", "否", "否", "好"],
["中年", "是", "是", "好"],
["中年", "否", "是", "非常好"],
["中年", "否", "是", "非常好"],
["老年", "否", "是", "非常好"],
["老年", "否", "是", "好"],
["老年", "是", "否", "好"],
["老年", "是", "否", "非常好"],
["老年", "否", "否", "一般"]
])
y_train = pd.DataFrame(["否", "否", "是", "是", "否", "否", "否", "是", "是", "是", "是", "是", "是", "是", "否"])
# 数据预处理
le_x = preprocessing.LabelEncoder()
le_x.fit(np.unique(X_train))
X_train = X_train.apply(le_x.transform)
le_y = preprocessing.LabelEncoder()
le_y.fit(np.unique(y_train))
y_train = y_train.apply(le_y.transform)
# 调用sklearn.DT建立训练模型
clf = DecisionTreeClassifier()
clf.fit(X_train, y_train)
# 用训练得到模型进行预测
X_new = pd.DataFrame([["青年", "否", "是", "一般"]])
X = X_new.apply(le_x.transform)
y_predict = clf.predict(X)
# 结果输出
X_show = [{features[i]: X_new.values[0][i]} for i in range(len(features))]
print("{0}被分类为:{1}".format(X_show, le_y.inverse_transform(y_predict)))
调用SkLearn库只需要在主函数里写就可以了
其中,在数据预处理部分,用到了
preprocessing.LabelEncoder
函数,作用是标准化标签,将标签值统一转换成range(标签值个数-1)范围内,并且根据字典排序;
构建决策树用到的是
DecisionTreeClassifier
函数,构建方法是CART分类树,其可更改的内参如下:
输出结果如下: