1、算法简介
1-1、算法思路
决策树是一种非参数的监督学习方法，用于分类和回归。它是一种特殊的树形结构，一般由节点和有向边组成。节点表示特征或者标签值。而有向边包含有判断条件。如1-2图示，这是判断是否录用机器学习工程师的一种决策路径。
可以看出在每个特征上都做了一个分割，分割后的子节点或成为新的父节点，或成为最终的叶子节点。这里要引出两个重要的问题，每个节点在哪个特征上做划分？某个特征在哪个值上做划分？
解决这两个问题要引入一个新的知识点--信息熵。熵在信息论中代表随机变量不确定度的度量，也就是熵越大，数据的不确定性越高；也就是熵越小，数据的不确定性越低。有了这个知识点后，就可以解决上边的两个问题了，遍历特征后，再遍历该特征上的每一种划分方式，选出信息熵最低的特征值。
循环往复，选择出信息熵最低的特征值的过程，就是训练的过程。
1-2、图示
1-3、算法流程
1--- 遍历所有的特征，在每个特征上遍历所有的划分方式，求出遍历后的最小信息熵对应的特征及特征值，该特征作为根节点，特征值作为判断条件；
2--- 将节点划分，作为其子节点，如划分成A和B；
3--- 此时对A、B求信息熵，如果信息熵足够小（接近于0）的部分，则可以停止求解，直接作为叶子结点，也就是标签；信息熵比较大的话，则执行步骤1，求出的特征作为新的节点。循环往复。
1-4、优缺点
1-4-1、优点
简单易懂，可解释性强，且构造的树能够可视化。
只需要较少的数据准备，而其他一些技术常常需要做数据标准化、哑变量的创建等等数据准备工作。
使用成本低，一旦创建了树，对目标变量的决策所需要消耗的时间很少。
能够同时处理数值和分类变量，其他的一些技术往往只能处理特定数据类型的变量。
能处理多输出问题。
可使用统计检验来验证模型，从而可保证模型的可靠性。
1-4-2、缺点
容易出现过拟合，特别是在构造了过于复杂的树的情况下。
不够稳定，哪怕是训练数据出现了一点小的变化，最后生成的树也可能千差万别。
训练寻找一个最优的决策树是一个NP完全问题，因此决策树的构造算法也多使用贪心算法，得到的往往是一个局部最优结果。
对于异或、多路复用等问题，决策树表现一般，因为决策树很难去表达它们
2、实践
2-1、采用bobo老师创建简单测试用例
import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from collections import Counter
from math import log
iris = datasets.load_iris()
X = iris.data[:,2:] #只取出后两个feature
y = iris.target #只取出所有类
def split(X, y, d, value):
index_a = (X[:,d] <= value)# 在第 d 个维度数据上 值小于value的索引
index_b = (X[:,d] > value)# 在第 d 个维度数据上 值小于value的索引
return X[index_a], X[index_b], y[index_a], y[index_b]
def entropy(y):
counter = Counter(y)
res = 0.0
for num in counter.values():
p = num / len(y)
res += -p * log(p)
return res
def try_split(X, y):
best_entropy = float('inf')
best_d, best_v = -1, -1
for d in range(X.shape[1]):# 遍历所有维度
sorted_index = np.argsort(X[:,d]) # 当前维度数据从小到大的索引
for i in range(1, len(X)):# 遍历所有数据 求出按前后两个值的平均值来划分的熵值
if X[sorted_index[i], d] != X[sorted_index[i-1], d]:
v = (X[sorted_index[i], d] + X[sorted_index[i-1], d])/2
X_l, X_r, y_l, y_r = split(X, y, d, v)
p_l, p_r = len(X_l) / len(X), len(X_r) / len(X) # 分为两部分 每部分的概率为->这部分的数据数目/数据总数
e = p_l * entropy(y_l) + p_r * entropy(y_r)
if e < best_entropy:
best_entropy, best_d, best_v = e, d, v
return best_entropy, best_d, best_v
best_entropy, best_d, best_v = try_split(X, y)
print("best_entropy =", best_entropy)
# best_entropy = 0.46209812037329684
print("best_d =", best_d)
# best_d = 0
print("best_v =", best_v)
# best_v = 2.45
X1_l, X1_r, y1_l, y1_r = split(X, y, best_d, best_v)
entropy(y1_l)
# 0.0
entropy(y1_r)
# 0.6931471805599453
best_entropy2, best_d2, best_v2 = try_split(X1_r, y1_r)
print("best_entropy =", best_entropy2)
# best_entropy = 0.2147644654371359
print("best_d =", best_d2)
# best_d = 1
print("best_v =", best_v2)
# best_v = 1.75
X2_l, X2_r, y2_l, y2_r = split(X1_r, y1_r, best_d2, best_v2)
entropy(y2_l)
# 0.30849545083110386
entropy(y2_r)
# 0.10473243910508653
