ML08-决策树

一、决策树应用体验

  1. 分类
import numpy as np
from sklearn  import datasets
from sklearn.tree import DecisionTreeClassifier

# 认知红酒数据集（178个样本，3类红酒，每类样本数 ( 59, 71, 48 ) ）
data,target=datasets.load_iris(return_X_y=True)
#data,target=datasets.load_wine(return_X_y=True)
print(data.shape,target.shape)
print((target==0).sum())
print((target==1).sum())
print((target==2).sum())

# ============================
clf = DecisionTreeClassifier()
clf = clf.fit(data[0:145], target[0:145])
# ============================

# 分类结果
pre_cls = clf.predict( data )
# 分类概率
pre_pro = clf.predict_proba(data)
# 分类准确率
score = clf.score(data, target)
# print(pre_cls) 
# print(pre_pro) 
print(score)
# path=clf.decision_path(data)
# print(path)
print(clf.predict( data[145:150]))

(150, 4) (150,)
50
50
50
1.0
[2 2 2 2 2]

  从上面可以看出，决策树对分类具有线性回归无可比拟的优势, 如果对未参与训练的数据集是否也有这么好的分类效果。

  1. 回归
import numpy as np
from sklearn  import datasets
from sklearn.tree import DecisionTreeRegressor
# 体能数据physiological Data（Weight重, Waist腰 and Pulse脉搏.），exercise Target（Chins下巴, Situps仰卧起坐 and Jumps跳跃.）
data,target=datasets.load_linnerud(return_X_y=True)
print(data.shape)
print(target.shape)
clf = DecisionTreeRegressor()
clf = clf.fit(data[0:15], target[0:15])
pre=clf.predict([data[14]])

print(pre)
print(target[14])

(20, 3)
(20, 3)
[[193.  36.  46.]]
[193.  36.  46.]

二、决策树的数学基础

1. 决策与信息论

  1. 从决策开始谈起
    人类经常面临各种决策，比如到了周末，准备安排下自己的周末活动，就会使用到决策：
      ---->公司老板是否有约------------------------------------------有---【加班】
            |---->女朋友是否有约-------------------------------有---【嗨皮】
                  |---->朋友是否有约打球----------------有---【锻炼】
                        |-----------------------------无---【游戏】
      
    上述决策中，抽象成一般的数学描述是：
      |-一个人的分类结果：加班，嗨皮，锻炼，游戏
      |-分类的数据行为数据：[公司老板是否，女朋友是否有约，朋友是否有约球]，我们称为样本数据，数据中的三个情况，称为数据特征。

  如果使用鸢尾花数据应该更加细致一点说明，见后面程序中的可视化数据。
  
  循环直到样本都属于某一类，最后分类成功。上面分类产生的决策结构就是决策树(一种形象的称呼)

  1. 决策的核心要素
    决策中有两个核心要素：
      |-（1）选择合适的特征
      |-（2）分类的阈值
      
      决策的结果：决策树

  2. 决策的数学知识
    其中选取哪个特征，特征的阈值怎么取，依赖一个数学分支学科：信息论。
      
    信息论是运用概率论与数理统计的方法研究信息、信息熵、通信系统、数据传输、密码学、数据压缩等问题的应用数学学科。信息论将信息的传递作为一种统计现象来考虑。
    信息论之父：克劳德·香农（Claude Shannon）

  3. 决策分类与信息论
    决定决策特征与分类阈值的数学过程就是决策树算法，该算法使用信息论理论知识。其中最基础的算法称为ID3算法。该算法还衍生出C4.5，C5.0和CART算法。

ID3（Iterative Dichotomiser 3）算法也称迭代二分法，是一种贪心算法，用来构造决策树。ID3算法起源于概念学习系统（CLS），以信息熵的下降速度为选取测试属性的标准，即在每个节点选取还尚未被用来划分的具有最高信息增益的特征作为划分标准，然后继续这个过程，直到生成的决策树能完美分类训练样例。

2. 决策树基本概念

  1. 不纯度
      当在某个节点上，样本不是属于单一的一个类别，我们称为样本不纯，度量样本不纯的概念称为不纯度。 当某个节点上样本都属于某一类，该节点的样本的不纯度为0。
      
      度量不纯度有三种方式：
        |- 基尼指数：Gini index(I_G)
        |- 信息熵：Entropy(I_H)
        |- 分类误差：Classification Error(I_E)

  2. 基尼指数（Gini Index）
       假设在某个决策节点，有n个样本，m个类别。每个类别的概率为p_i：
        |- I_G=\sum \limits _{i=1}^{m} p_i(1-p_i)=1-\sum \limits _{i=1}^{m} {p_i}^2

  3. 信息熵（Entropy）
       假设在某个决策节点，有n个样本，m个类别。每个类别的概率为p_i：
        |-I_H = - \sum \limits _{i=1}^{m} p_i log(p_i)

备注： 当年Claude Shannon提出这个公式的时候，冯诺依曼（John von Neumann）建议给一个名字为：熵（Entropy：平均信息值）

  1. 分类误差（Classification Error）
       假设在某个决策节点，有n个样本，m个类别。每个类别的概率为p_i：
        |- I_E = 1- \overset{m}{\underset{i=1}{\text{Max}}} \ p_i

  2. 概率与占比
      上述度量公式中使用的概率，可以使用样本在每个决策节点中的类别占比来代替：
       假设在某个决策节点，有n个样本(x_1,x_2,\dots,x_n)，m个类别{C_1,C_2,\dots,C_m}。每个类别的概率为p_i可以使用占比替代：
        |- p_i= \dfrac{1}{n} \sum \limits _{x_j \in C_i} 1，其实就是：每类总数 / 样本总数

  3. 信息增益
      信息增益用来决定分类的阈值，每个算法的信息增益值不一样，下面在具体的算法中给不不同算分信息增益计算公式。

3. 决策树模型

  1. 生成决策树
      |- (1)计算信息熵
      |- (2)计算信息增益
      |- (3)根据信息增益，选择分类特征；
      |- (4)计算特征的不纯度，不纯度为0，就是叶子节点，不在继续分类，不纯度不为0，则继续（1）步骤，直到所有样本的不纯度都是0，就是被正确分类。
      
    两个关键项：
      |-信息增益值确定分类特征 。
      |-不纯度确定子节点产生（ 纯与不纯 ），确定分类的阈值 。

  2. 决策模型
    直接输入分类特征，按照决策树分类，到叶子节点的结果就是最终的分类输出。

三、决策树算法验证与数学基础

1. 决策树算法验证

  1. 过拟合缺陷体验
    下面代码用来体验，决策树的过拟合缺点。尽管决策树有容易理解，算法容易实现，计算量小等优点，但他有个缺陷就是：过拟合。
import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn import datasets
from sklearn.model_selection import train_test_split    # 训练集切分

data,target=datasets.load_iris(return_X_y=True)
train_data, test_data,train_target, test_target = train_test_split(data, target, test_size=0.4,shuffle=True)
print(train_data.shape)
print(train_target.shape)
print(test_data.shape)
print(test_target.shape)

dtc=DecisionTreeClassifier()
# 使用训练样本训练
dtc.fit(train_data,train_target)
# 使用测试集测试
score=dtc.score(test_data,test_target)
print('预测评估：',score)

# 使用全部样本训练
dtc.fit(data,target)
# 使用全部样本测试
score=dtc.score(data,target)
print('预测评估：',score)


(90, 4)
(90,)
(60, 4)
(60,)
预测评估： 0.9333333333333333
预测评估： 1.0
  1. 决策树属性的理解体验
    下面代码输出决策树的属性，可以结合上面决策树的模型去理解。
import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn import datasets
from sklearn.model_selection import train_test_split    # 训练集切分

data,target=datasets.load_iris(return_X_y=True)
#data,target=datasets.load_linnerud(return_X_y=True)


dtc=DecisionTreeClassifier(random_state=0,min_samples_split=2)    # 为了保证输出结果的稳定性，需要random_state固定。
dtc.fit(data,target)                  #训练

print('分类类别：',dtc.classes_)
print('特征的重要性：',dtc.feature_importances_ )
print('最大特征数：',dtc.max_features_)
print('类别数：',dtc.n_classes_)
print('训练时的特征数：',dtc.n_features_)
print('训练输出数据的维数：',dtc.n_outputs_)     # 一般对分类来说都是一个标量来判定，体能数据的输出就是3

print('评估：',dtc.score(data,target))

分类类别： [0 1 2]
特征的重要性： [0.         0.01333333 0.06405596 0.92261071]
最大特征数： 4
类别数： 3
训练时的特征数： 4
训练输出数据的维数： 1
评估： 1.0
  1. 决策树的树结构体验
    通过决策树的结构体验，我们基本上知道决策事是怎么实现的，然后关注特征选择的信息熵的计算，以及不纯度的计算，我们就可以实现决策树。
import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn import datasets
from sklearn.model_selection import train_test_split    # 训练集切分
import sklearn

data,target=datasets.load_iris(return_X_y=True)
#data,target=datasets.load_linnerud(return_X_y=True)


dtc=DecisionTreeClassifier(random_state=0,min_samples_split=2)    # 为了保证输出结果的稳定性，需要random_state固定。
dtc.fit(data,target)  
tree=dtc.tree_

# 打印树的帮助
# help(sklearn.tree._tree.Tree)

print('结点数：\n',tree.node_count)
print('容量：\n',tree.capacity)
print('最大深度：\n',tree.max_depth)
print('节点分类的特征索引：-2表示没有分类特征，就是叶子节点：\n',tree.feature)     #-2表示是叶子节点（因为没有分类特征）
# 说明：3表示使用的第4个特征，进行子节点分叉。-2表示叶子节点，没有子节点分叉。   

结点数：
 17
容量：
 17
最大深度：
 5
节点分类的特征索引：-2表示没有分类特征，就是叶子节点：
 [ 3 -2  3  2  3 -2 -2  3 -2  2 -2 -2  2  1 -2 -2 -2]

print('节点的样本总数：\n',tree.n_node_samples)   
#  150表示决策树上每个节点，未分叉样本数。

节点的样本总数：
 [150  50 100  54  48  47   1   6   3   3   2   1  46   3   2   1  43]

print('节点每类样本数：\n',tree.value)    
# [[50.  0.  0.]] 表述决策树上，，节点的样本所属类别（标签）的样本数：A类50个，B类0个，C类0个，这是一个不纯度为0的节点，是叶子节点。

节点每类样本数：
 [[[50. 50. 50.]]

 [[50.  0.  0.]]

 [[ 0. 50. 50.]]

 [[ 0. 49.  5.]]

 [[ 0. 47.  1.]]

 [[ 0. 47.  0.]]

 [[ 0.  0.  1.]]

 [[ 0.  2.  4.]]

 [[ 0.  0.  3.]]

 [[ 0.  2.  1.]]

 [[ 0.  2.  0.]]

 [[ 0.  0.  1.]]

 [[ 0.  1. 45.]]

 [[ 0.  1.  2.]]

 [[ 0.  0.  2.]]

 [[ 0.  1.  0.]]

 [[ 0.  0. 43.]]]

print('分类阈值：-2表示叶子节点，不在分子节点：\n',tree.threshold)
# -2表示没有分叉 ，是叶子节点，阈值就是-2表示。每个样本分叉就按照阈值分叉，这儿每个样本应该有一个信息熵。

分类阈值：-2表示叶子节点，不在分子节点：
 [ 0.80000001 -2.          1.75        4.94999981  1.6500001  -2.
 -2.          1.54999995 -2.          5.44999981 -2.         -2.
  4.85000038  3.0999999  -2.         -2.         -2.        ]

print('节点的不纯度：\n',tree.impurity) 
# 不纯度为0，表示叶子节点，不会分叉。不纯度非0，表示需要分叉，分类按照每个样本的阈值

节点的不纯度：
 [0.66666667 0.         0.5        0.16803841 0.04079861 0.
 0.         0.44444444 0.         0.44444444 0.         0.
 0.04253308 0.44444444 0.         0.         0.        ]

print('左节点：-1表示叶子节点：\n',tree.children_left)   
print('右节点：-1表示叶子节点：\n',tree.children_right) 
# 列出决策树的每个节点的id（按照顺序排列）-1表示叶子节点。

左节点：-1表示叶子节点：
 [ 1 -1  3  4  5 -1 -1  8 -1 10 -1 -1 13 14 -1 -1 -1]
右节点：-1表示叶子节点：
 [ 2 -1 12  7  6 -1 -1  9 -1 11 -1 -1 16 15 -1 -1 -1]
  1. 决策树的树结构可视化
% matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn import datasets
from sklearn.model_selection import train_test_split    # 训练集切分
import sklearn
from sklearn import tree
from sklearn.externals.six import StringIO    #数据缓冲
import pydot    # 把数据转换为图像

data,target=datasets.load_iris(return_X_y=True)
#data,target=datasets.load_linnerud(return_X_y=True)


dtc=DecisionTreeClassifier(random_state=0,criterion='entropy')    # 为了保证输出结果的稳定性，需要random_state固定。
dtc.fit(data,target)  

buff = StringIO()
# tree.export_graphviz(dtc,out_file=buff)     # export_graphviz只能导出数据
tree.export_graphviz(dtc, out_file=buff, feature_names=['特征1','特征2','特征3','特征4'], class_names=['A类','B类','C类'], filled=True, rounded=True, special_characters=True)  

(graph,)= pydot.graph_from_dot_data(buff.getvalue())   # 转换为图像
graph.write_svg("iris.svg")

显示上面产生的图片。
鸢尾花决策过程可视化

2. ID3决策算法

  1. 样本总体信息熵

   假设在某个决策节点，有n个样本，m个类别。每个类别的概率为p_i：
    |-I_H = - \sum \limits _{i=1}^{m} p_i log(p_i)

   比如鸢尾花数据集一共150个，共分3类，按照如下步骤计算信息熵 ：
    |- （1）计算样本属于每类的概率为： p_1=50/150=\dfrac{1}{3},p_2=50/150=\dfrac{1}{3},p_3=50/150=\dfrac{1}{3}
    |- （2）计算信息熵为：I_H=- (\dfrac{1}{3} log\dfrac{1}{3} + \dfrac{1}{3} log \dfrac{1}{3} + \dfrac{1}{3} log \dfrac{1}{3})
  
   样本总体信息熵与训练特征无关，只与标签有关，具体代码如下：

from sklearn  import datasets
import numpy as np
def calcute_total_entropy(train_label):
    # train_label：总体样本的输出标签

    # 获取总得样本数
    total_num=len(train_label)
    # 循环得到所有类别的样本总数
    label_num={}
    for data in train_label:
        if  data not in label_num:
            label_num[data]=0
        label_num[data]+=1
    # 计算每类的概率
    entropy=0.0
    for  cls,num in label_num.items():
        prop=1.0*num/total_num
        entropy+=prop *np.log2(prop)
    return [-entropy,label_num.items()]

data,target=datasets.load_iris(return_X_y=True)
ent=calcute_total_entropy(target)
print(ent)

[1.584962500721156, dict_items([(0, 50), (1, 50), (2, 50)])]

from sklearn  import datasets
import numpy as np
dtc=DecisionTreeClassifier(criterion='entropy')
# 使用训练样本训练
dtc.fit(data,target)
print(dtc.tree_.impurity)

[1.5849625  0.         1.         0.44506486 0.14609425 0.
 0.         0.91829583 0.         0.91829583 0.         0.
 0.15109697 0.91829583 0.         0.         0.        ]

注意：  通过对我们与sklearn实现的结果比较，发现sklearn的对数运算使用的是以2为底的对数运算。

  1. 样本特征值信息熵
      样本总体信息熵是所有样本按照标签值作为特征计算信息熵（分类标准按照标签分类），样本特征信息熵就是按照训练样本的某个特征值来计算信息熵（分类标准按照标签分类） ，一个特征值一个信息熵，使用这些特征熵就可以计算条件熵。
      
      样本特征值信息熵，就是某个特征中某个值的信息熵，比如鸢尾花中4个特征，第一个特征150个取值，其中有一个取值值一样有20个，其中A类6个，B类9个，C类5个，这样就可以求出这个20个相同特征值的信息熵：H_{20}=\dfrac{6}{20} log \dfrac{6}{20} + \dfrac{9}{20} log \dfrac{9}{20} + \dfrac{5}{20} log \dfrac{5}{20}， 下面通过例子来说明：
from sklearn  import datasets
import numpy as np
def calcute_value_entropy(data_train, data_label, index, value):
    # data_train 训练样本
    # data_label 样本标签
    # index，特征索引，就是训练样本中的第几个特征，从0开始。
    # value，需要计算信息熵的特征值。某些特征值在样本中只有一个。这种信息熵等于0，就是不纯度为0。
    total_num=0   # 某个特征值在数据集中的个数
    label_num={}  # 特征值按照分类统计，鸢尾花A类多少个，B类多少个，C类多少个
    i=0                # 用来索引data_train与data_label对应位置的数据
    # 下面只对index的特征处理，其他特征不处理
    for data in data_train[:,index]:
        # 只对指定的特征值进行统计
        if data == value:
            total_num+=1  # 特征值总数递增
            # 判定类别
            label=data_label[I]
            if label not in  label_num:
                label_num[label]=0
            label_num[label]+=1
            
        # 标签对应位置下移
        I+=1
    # 统计特征值的分类个数，下面计算熵
    entropy=0.0
    for  cls,num in label_num.items():
        prop=1.0*num/total_num
        entropy+=prop *np.log2(prop)
    return [-entropy,total_num,label_num.items()]
data,target=datasets.load_iris(return_X_y=True)
#print(data)
ent=calcute_value_entropy(data,target,0,5.1)
print(ent)

[0.34883209584303193, 9, dict_items([(0, 8), (1, 1)])]

  下面我们可以计算出鸢尾花某个特征的所有特征值的信息熵。

from sklearn  import datasets
import numpy as np

def calcute_feature_entropy(data_train, data_label, index):
    # data_train 训练样本
    # data_label 样本标签
    # index，特征索引，就是训练样本中的第几个特征，从0开始。
    label_entropy={}
    # 对训练样本遍历，统计计算每个值的信息熵(只对某个特征值统计)
    for data in data_train[ :, index]:
        if data not in label_entropy:
            ent=calcute_value_entropy(data_train, data_label,index,data)
            label_entropy[data]=ent# 只使用前面两个值，其他值可以根据情况使用
    return label_entropy

data,target=datasets.load_iris(return_X_y=True)    
ents=calcute_feature_entropy(data,target,0)
print(len(ents))
for k,v in ents.items():
    print(k,":",v)

35
5.1 : [0.5032583347756457, 9, dict_items([(0, 8), (1, 1)])]
4.9 : [1.2516291673878228, 6, dict_items([(0, 4), (1, 1), (2, 1)])]
4.7 : [-0.0, 2, dict_items([(0, 2)])]
4.6 : [-0.0, 4, dict_items([(0, 4)])]
5.0 : [0.7219280948873623, 10, dict_items([(0, 8), (1, 2)])]
5.4 : [0.6500224216483541, 6, dict_items([(0, 5), (1, 1)])]
4.4 : [-0.0, 3, dict_items([(0, 3)])]
4.8 : [-0.0, 5, dict_items([(0, 5)])]
4.3 : [-0.0, 1, dict_items([(0, 1)])]
5.8 : [1.4488156357251847, 7, dict_items([(0, 1), (1, 3), (2, 3)])]
5.7 : [1.2987949406953985, 8, dict_items([(0, 2), (1, 5), (2, 1)])]
5.2 : [0.8112781244591328, 4, dict_items([(0, 3), (1, 1)])]
5.5 : [0.863120568566631, 7, dict_items([(0, 2), (1, 5)])]
4.5 : [-0.0, 1, dict_items([(0, 1)])]
5.3 : [-0.0, 1, dict_items([(0, 1)])]
7.0 : [-0.0, 1, dict_items([(1, 1)])]
6.4 : [0.863120568566631, 7, dict_items([(1, 2), (2, 5)])]
6.9 : [0.8112781244591328, 4, dict_items([(1, 1), (2, 3)])]
6.5 : [0.7219280948873623, 5, dict_items([(1, 1), (2, 4)])]
6.3 : [0.9182958340544896, 9, dict_items([(1, 3), (2, 6)])]
6.6 : [-0.0, 2, dict_items([(1, 2)])]
5.9 : [0.9182958340544896, 3, dict_items([(1, 2), (2, 1)])]
6.0 : [0.9182958340544896, 6, dict_items([(1, 4), (2, 2)])]
6.1 : [0.9182958340544896, 6, dict_items([(1, 4), (2, 2)])]
5.6 : [0.6500224216483541, 6, dict_items([(1, 5), (2, 1)])]
6.7 : [0.954434002924965, 8, dict_items([(1, 3), (2, 5)])]
6.2 : [1.0, 4, dict_items([(1, 2), (2, 2)])]
6.8 : [0.9182958340544896, 3, dict_items([(1, 1), (2, 2)])]
7.1 : [-0.0, 1, dict_items([(2, 1)])]
7.6 : [-0.0, 1, dict_items([(2, 1)])]
7.3 : [-0.0, 1, dict_items([(2, 1)])]
7.2 : [-0.0, 3, dict_items([(2, 3)])]
7.7 : [-0.0, 4, dict_items([(2, 4)])]
7.4 : [-0.0, 1, dict_items([(2, 1)])]
7.9 : [-0.0, 1, dict_items([(2, 1)])]
  1. 样本特征总体熵（条件熵）
      样本特征总体上，就是固定某个特征的信息熵，为了更加容易理解，按照我们前面的定义，总体信息熵定义如下：
        假设在某个决策节点，有n个样本，m个类别。每个类别的概率为p(C_i)，其中C_i表示属于某类别，C表示所有类别 ：
          |-I_H(C) = - \sum \limits _{i=1}^{m} p_i（C_i） log(p_i(C_i))
      
      我们可以把特征熵按照条件概率建模，特征信息熵定义如下：
        假设某个特征的样本值不同的是k个，特征值集合表示为(x_1,x_2,\dots,x_k)，则特征的总体熵（条件熵）定义如下：
        |-I_H(C | X) = - \sum \limits _{i=1}^{k} p_i H（C | X=x_i）
      
      我们就可以计算出鸢尾花4个特征的信息熵（ 也称条件熵 ）
from sklearn  import datasets
import numpy as np

# 计算某个特征中某个值的信息熵
def calcute_value_entropy(data_train, data_label, index, value):
    # data_train 训练样本
    # data_label 样本标签
    # index，特征索引，就是训练样本中的第几个特征，从0开始。
    # value，需要计算信息熵的特征值。某些特征值在样本中只有一个。这种信息熵等于0，就是不纯度为0。
    total_num=0   # 某个特征值在数据集中的个数
    label_num={}  # 特征值按照分类统计，鸢尾花A类多少个，B类多少个，C类多少个
    i=0                # 用来索引data_train与data_label对应位置的数据
    # 下面只对index的特征处理，其他特征不处理
    for data in data_train[:,index]:
        # 只对指定的特征值进行统计
        if data == value:
            total_num+=1  # 特征值总数递增
            # 判定类别
            label=data_label[I]
            if label not in  label_num:
                label_num[label]=0
            label_num[label]+=1
            
        # 标签对应位置下移
        I+=1
    # 统计特征值的分类个数，下面计算熵
    entropy=0.0
    for  cls,num in label_num.items():
        prop=1.0*num/total_num
        entropy+=prop *np.log2(prop)
    return [-entropy,total_num,label_num.items()]

#  计算某个特征的信息熵
def calcute_feature_entropy(data_train, data_label, index):
    # data_train 训练样本
    # data_label 样本标签
    # index，特征索引，就是训练样本中的第几个特征，从0开始。
    
    total_num=len(data_train)  # 
    label_entropy={}
    # 对训练样本遍历，统计计算每个值的信息熵(只对某个特征值统计)
    for data in data_train[ :, index]:
        if data not in label_entropy:
            ent=calcute_value_entropy(data_train, data_label,index,data)
            label_entropy[data]=[ ent[0], ent[1] ]
    
    # 计算整个特征的信息熵
    feature_entropy=0.0
    for _, v in  label_entropy.items():
        prop=1.0 * v[1] / total_num
        feature_entropy+=prop * v[0]
    return feature_entropy

# 计算鸢尾花四个特征的信息熵
data,target=datasets.load_iris(return_X_y=True)    
feature_num=data.shape[1]  # 特征数
for idx  in range(feature_num):
    ent=calcute_feature_entropy(data,target,idx)
    print(ent)

0.7080248798300983
1.07409253659755
0.1386459770753561
0.14906466204571436
  1. 特征信息增益
      所谓信息增益值，是针对样本总体信息熵而言，起定义如下：
        假设训练样本集有N个特征，i表示样本特征的索引：0 \le i \le N。X_i就表示第i个特征。则第i个特征X_i的信息增益表示如下：
        |-IG(X) =I_H(C)-I_H(C|X_i)
      
      下面使用代码来说明鸢尾花的特征信息增益的计算结果（为了保证大家的阅读方便，我把所有代码汇集在一起形成一个独立完整的程序）。
from sklearn  import datasets
import numpy as np

# 计算总体信息熵========================================
def calcute_total_entropy(train_label):
    # train_label：总体样本的输出标签
    # 获取总得样本数
    total_num=len(train_label)
    # 循环得到所有类别的样本总数
    label_num={}
    for data in train_label:
        if  data not in label_num:
            label_num[data]=0
        label_num[data]+=1
    # 计算每类的概率
    entropy=0.0
    for  cls,num in label_num.items():
        prop=1.0*num/total_num
        entropy+=prop *np.log2(prop)
    # print('不纯度：', -entropy)
    return [-entropy,label_num.items()]

# 计算某个特征中某个值的信息熵========================================
def calcute_value_entropy(data_train, data_label, index, value):
    # data_train 训练样本
    # data_label 样本标签
    # index，特征索引，就是训练样本中的第几个特征，从0开始。
    # value，需要计算信息熵的特征值。某些特征值在样本中只有一个。这种信息熵等于0，就是不纯度为0。
    total_num=0   # 某个特征值在数据集中的个数
    label_num={}  # 特征值按照分类统计，鸢尾花A类多少个，B类多少个，C类多少个
    i=0                # 用来索引data_train与data_label对应位置的数据
    # 下面只对index的特征处理，其他特征不处理
    for data in data_train[:,index]:
        # 只对指定的特征值进行统计
        if data == value:
            total_num+=1  # 特征值总数递增
            # 判定类别
            label=data_label[I]
            if label not in  label_num:
                label_num[label]=0
            label_num[label]+=1
            
        # 标签对应位置下移
        I+=1
    # 统计特征值的分类个数，下面计算熵
    entropy=0.0
    for  cls,num in label_num.items():
        prop=1.0*num/total_num
        entropy+=prop *np.log2(prop)
    return [-entropy,total_num,label_num.items()]

#  计算某个特征的信息熵========================================
def calcute_feature_entropy(data_train, data_label, index):
    # data_train 训练样本
    # data_label 样本标签
    # index，特征索引，就是训练样本中的第几个特征，从0开始。
    
    total_num=len(data_train)  # 
    label_entropy={}
    # 对训练样本遍历，统计计算每个值的信息熵(只对某个特征值统计)
    for data in data_train[ :, index]:
        if data not in label_entropy:
            ent=calcute_value_entropy(data_train, data_label,index,data)
            label_entropy[data]=[ ent[0], ent[1] ]
    
    # 计算整个特征的信息熵
    feature_entropy=0.0
    for _, v in  label_entropy.items():
        prop=1.0 * v[1] / total_num
        feature_entropy+=prop * v[0]
    return feature_entropy

#  计算特征的信息增益========================================
def calcute_gain_value(data_train, data_label):
    feature_num=data_train.shape[1]  # 特征数
    # 样本总体信息熵
    total_entropy=calcute_total_entropy(data_label)
    gains=[]
    for idx  in range(feature_num):
        entropy=calcute_feature_entropy(data,target,idx)
        gain=total_entropy[0]-entropy
        gains.append(gain)
    return gains

#  加载数据集========================================
data,target=datasets.load_iris(return_X_y=True)    
iris_gains=calcute_gain_value(data,target)
print(iris_gains)


[0.8769376208910578, 0.5108699641236061, 1.4463165236458, 1.4358978386754417]

  1. 特征选择
      根据上面计算出来的信息增益值的结果，我们可以选择具有最大信息增益值的特征作为子节点分类特征。从上面的计算结果来看，我们选择第3个特征来作为分类特征。

  2. 子节点分类
      我们选择使用第三个特征（index=2）来做子节点分类，下面我们看下第三类特征的特征值熵的情况与信息增益值。并得到观察决策树子节点生成阈值情况：

from sklearn  import datasets
import numpy as np

# 计算总体信息熵========================================
def calcute_total_entropy(train_label):
    # train_label：总体样本的输出标签
    # 获取总得样本数
    total_num=len(train_label)
    # 循环得到所有类别的样本总数
    label_num={}
    for data in train_label:
        if  data not in label_num:
            label_num[data]=0
        label_num[data]+=1
    # 计算每类的概率
    entropy=0.0
    for  cls,num in label_num.items():
        prop=1.0*num/total_num
        entropy+=prop *np.log2(prop)
    # print('不纯度：', -entropy)
    return [-entropy,label_num.items()]

# 计算某个特征中某个值的信息熵========================================
def calcute_value_entropy(data_train, data_label, index, value):
    # data_train 训练样本
    # data_label 样本标签
    # index，特征索引，就是训练样本中的第几个特征，从0开始。
    # value，需要计算信息熵的特征值。某些特征值在样本中只有一个。这种信息熵等于0，就是不纯度为0。
    total_num=0   # 某个特征值在数据集中的个数
    label_num={}  # 特征值按照分类统计，鸢尾花A类多少个，B类多少个，C类多少个
    i=0                # 用来索引data_train与data_label对应位置的数据
    # 下面只对index的特征处理，其他特征不处理
    for data in data_train[:,index]:
        # 只对指定的特征值进行统计
        if data == value:
            total_num+=1  # 特征值总数递增
            # 判定类别
            label=data_label[I]
            if label not in  label_num:
                label_num[label]=0
            label_num[label]+=1
            
        # 标签对应位置下移
        I+=1
    # 统计特征值的分类个数，下面计算熵
    entropy=0.0
    for  cls,num in label_num.items():
        prop=1.0*num/total_num
        entropy+=prop *np.log2(prop)
    return [-entropy,total_num,label_num.items()]

#  计算某个特征的信息熵========================================
def calcute_feature_entropy(data_train, data_label, index):
    # data_train 训练样本
    # data_label 样本标签
    # index，特征索引，就是训练样本中的第几个特征，从0开始。
    
    total_num=len(data_train)  # 
    label_entropy={}
    # 对训练样本遍历，统计计算每个值的信息熵(只对某个特征值统计)
    for data in data_train[ :, index]:
        if data not in label_entropy:
            ent=calcute_value_entropy(data_train, data_label,index,data)
            label_entropy[data]=ent
    return label_entropy
    
#  加载数据集========================================
data,target=datasets.load_iris(return_X_y=True)    
ents=calcute_feature_entropy(data,target,3)
for k,v in ents.items():
    print(k,':',v)


0.2 : [-0.0, 28, dict_items([(0, 28)])]
0.4 : [-0.0, 7, dict_items([(0, 7)])]
0.3 : [-0.0, 7, dict_items([(0, 7)])]
0.1 : [-0.0, 6, dict_items([(0, 6)])]
0.5 : [-0.0, 1, dict_items([(0, 1)])]
0.6 : [-0.0, 1, dict_items([(0, 1)])]
1.4 : [0.5435644431995964, 8, dict_items([(1, 7), (2, 1)])]
1.5 : [0.6500224216483541, 12, dict_items([(1, 10), (2, 2)])]
1.3 : [-0.0, 13, dict_items([(1, 13)])]
1.6 : [0.8112781244591328, 4, dict_items([(1, 3), (2, 1)])]
1.0 : [-0.0, 7, dict_items([(1, 7)])]
1.1 : [-0.0, 3, dict_items([(1, 3)])]
1.8 : [0.41381685030363374, 12, dict_items([(1, 1), (2, 11)])]
1.2 : [-0.0, 5, dict_items([(1, 5)])]
1.7 : [1.0, 2, dict_items([(1, 1), (2, 1)])]
2.5 : [-0.0, 3, dict_items([(2, 3)])]
1.9 : [-0.0, 5, dict_items([(2, 5)])]
2.1 : [-0.0, 6, dict_items([(2, 6)])]
2.2 : [-0.0, 3, dict_items([(2, 3)])]
2.0 : [-0.0, 6, dict_items([(2, 6)])]
2.4 : [-0.0, 3, dict_items([(2, 3)])]
2.3 : [-0.0, 8, dict_items([(2, 8)])]

  对上面不纯度不为0的样本子集继续递归，直到所有节点是叶子节点。

3. C4.5决策算法

  1. C4.5决策算法的思想
      以信息增益进行分类决策时，存在偏向于取值较多的特征的问题（因为总数多，样本概率取值其每个值的概率就小，总体值就小，从而信息增益值就大）。
      
      为了解决这个问题，提出了使用信息增益比来作为特征选择的度量方法。
      
      C4.5决策算法是ID3决策算法的优化，优化提现如下几个方面：
        |-（1）特征选取的依据是：特征信息增益比最大；
        |-（2）对决策树之后进行剪枝；
        |-（3）能够处理离散型和连续型的属性类型，就是：将连续型的属性进行离散化处理；
        |-（4）能够处理具有缺失属性值的训练数据；

  2. 分裂信息熵
      在介绍特征信息增益比，需要对上面的样本信息熵进行改进：
        假设某个特征X的样本值不同的是k个，特征值集合表示为(x_1,x_2,\dots,x_k)，则可以把其中的样本值信息熵改成概率的对数：
        |-IS(X) = - \sum \limits _{i=1}^{k} p_i log(p_i) ）
      该信息熵为分裂信息熵，分裂信息熵与样本总体信息熵计算方式一样，只是这儿是对某个特征而言，而且概率计算方式也不同。
      
      下面用代码来说明：

#  计算分裂信息熵   
def calcute_split_entropy(data_train,index):
    # data_train 训练样本
    # data_label 样本标签
    # index，特征索引，就是训练样本中的第几个特征，从0开始。
    
    total_num=len(data_train)   # 某个特征值在数据集中的个数
    value_num={}
    # 下面只对index的特征处理，其他特征不处理
    for data in data_train[:,index]:
        if data not in value_num:
            value_num[data]=0
        value_num[data]+=1
    
    # 计算分裂熵
    entropy=0.0
    for _, num in value_num.items():
        prop=1.0*num/total_num
        entropy+=prop *np.log2(prop)
    return -entropy
    
#  加载数据集========================================
data,target=datasets.load_iris(return_X_y=True)    
ent=[
    calcute_split_entropy(data,0),
    calcute_split_entropy(data,1),
    calcute_split_entropy(data,2),
    calcute_split_entropy(data,3)]
# 打印分裂熵
print(ent)


[4.8220180883811645, 4.011709761218928, 5.033829378702226, 4.065662933799395]
  1. 特征信息增益比
      信息增益比就是信息增益比与分裂信息熵的比值：
        |-IR_{X}=\dfrac{IG(X)} {IS(X)}
      
      下面可以计算鸢尾花数据的增益值比。
from sklearn  import datasets
import numpy as np

# 计算总体信息熵========================================
def calcute_total_entropy(train_label):
    # train_label：总体样本的输出标签
    # 获取总得样本数
    total_num=len(train_label)
    # 循环得到所有类别的样本总数
    label_num={}
    for data in train_label:
        if  data not in label_num:
            label_num[data]=0
        label_num[data]+=1
    # 计算每类的概率
    entropy=0.0
    for  cls,num in label_num.items():
        prop=1.0*num/total_num
        entropy+=prop *np.log2(prop)
    # print('不纯度：', -entropy)
    return [-entropy,label_num.items()]

# 计算某个特征中某个值的信息熵========================================
def calcute_value_entropy(data_train, data_label, index, value):
    # data_train 训练样本
    # data_label 样本标签
    # index，特征索引，就是训练样本中的第几个特征，从0开始。
    # value，需要计算信息熵的特征值。某些特征值在样本中只有一个。这种信息熵等于0，就是不纯度为0。
    total_num=0   # 某个特征值在数据集中的个数
    label_num={}  # 特征值按照分类统计，鸢尾花A类多少个，B类多少个，C类多少个
    i=0                # 用来索引data_train与data_label对应位置的数据
    # 下面只对index的特征处理，其他特征不处理
    for data in data_train[:,index]:
        # 只对指定的特征值进行统计
        if data == value:
            total_num+=1  # 特征值总数递增
            # 判定类别
            label=data_label[I]
            if label not in  label_num:
                label_num[label]=0
            label_num[label]+=1
            
        # 标签对应位置下移
        I+=1
    # 统计特征值的分类个数，下面计算熵
    entropy=0.0
    for  cls,num in label_num.items():
        prop=1.0*num/total_num
        entropy+=prop *np.log2(prop)
    return [-entropy,total_num,label_num.items()]

#  计算某个特征的信息熵========================================
def calcute_feature_entropy(data_train, data_label, index):
    # data_train 训练样本
    # data_label 样本标签
    # index，特征索引，就是训练样本中的第几个特征，从0开始。
    
    total_num=len(data_train)  # 
    label_entropy={}
    # 对训练样本遍历，统计计算每个值的信息熵(只对某个特征值统计)
    for data in data_train[ :, index]:
        if data not in label_entropy:
            ent=calcute_value_entropy(data_train, data_label,index,data)
            label_entropy[data]=[ ent[0], ent[1] ]
    
    # 计算整个特征的信息熵
    feature_entropy=0.0
    for _, v in  label_entropy.items():
        prop=1.0 * v[1] / total_num
        feature_entropy+=prop * v[0]
    return feature_entropy

#  计算特征的信息增益========================================
def calcute_gain_value(data_train, data_label):
    feature_num=data_train.shape[1]  # 特征数
    # 样本总体信息熵
    total_entropy=calcute_total_entropy(data_label)
    gains=[]
    for idx  in range(feature_num):
        entropy=calcute_feature_entropy(data,target,idx)
        gain=total_entropy[0]-entropy
        gains.append(gain)
    return gains
#  计算分裂信息熵========================================   
def calcute_split_entropy(data_train,index):
    # data_train 训练样本
    # data_label 样本标签
    # index，特征索引，就是训练样本中的第几个特征，从0开始。
    
    total_num=len(data_train)   # 某个特征值在数据集中的个数
    value_num={}
    # 下面只对index的特征处理，其他特征不处理
    for data in data_train[:,index]:
        if data not in value_num:
            value_num[data]=0
        value_num[data]+=1
    
    # 计算分裂熵
    entropy=0.0
    for _, num in value_num.items():
        prop=1.0*num/total_num
        entropy+=prop *np.log2(prop)
    return -entropy

def calcute_all_split_entropy(data_train):
    feature_num=data_train.shape[1]
    ents=[]
    for idx in range(feature_num):
        ent=calcute_split_entropy(data_train,idx)
        ents.append(ent)
    return ents
#  加载数据集========================================
data,target=datasets.load_iris(return_X_y=True)    
iris_gains=calcute_gain_value(data,target)
iris_split=calcute_all_split_entropy(data)
print(iris_gains)
print(iris_split)
ratio=[]
for i in range(len(iris_gains)):
    ratio.append(iris_gains[i]/iris_split[I])
print(ratio)



[0.8769376208910578, 0.5108699641236061, 1.4463165236458, 1.4358978386754417]
[4.8220180883811645, 4.011709761218928, 5.033829378702226, 4.065662933799395]
[0.1818611222143841, 0.12734469703221554, 0.28731933779183344, 0.35317680340351865]

  如果使用信息增益比，则分类特征选择第四个特征（[0.1818611222143841, 0.12734469703221554, 0.28731933779183344, 0.35317680340351865]）。由于评估了分裂度，对某个特征中值比较多的情况，使用分类信息熵作为分母，可以同比降低这种影响。
  计算结果与sklearn一致。

  1. 离散化处理
      如果按照上面的方式，对连续值得情况会出现很多子节点。为了避免这种情况，需要进行离散化处理。 离散处理的思路相对比较简单：
      假设某个分类特征具有N个值。
        |-（1）对某个分类特征的所有值进行排序（升序），得到(x_1,x_2,\dots,x_N)。
        |-（2）对相邻两个值取平均值，并使用这个平均值作为分类阈值\bar{x}=\dfrac{x_i + x_{i+1}}{2}，把特征的值分成两类，A={x_i | x_i>\bar{x}} 与B={x_i | x_i \le \bar{x}}
        |-（3）计算按照A、B分成两类的分类增益值，这样得到N-1个增益值；
        |-（4） 取信息增益值最大那个\bar{x}作为分类阈值。
      
      其中分类增益值计算公式为：
      假设：A类的格式是N_A,B类的个数是N_B，则信息增益为：I=\dfrac{N_A}{N} H_A + \dfrac{N_B}{N} H_B
       下面使用代码实现计算鸢尾花第一个节点的阈值，分类特征使用上面的计算结果，使用第四个特征。

注意：对于离散特征值，也可以采用二分的分组模式，每个分组的增益值最大，作为最终分组来划分直接点。

import numpy as np
from sklearn import datasets
def calcute_entrop(train_label):
    # 统计类别
    category_num={}
    for label in train_label:
        if label not in  category_num:
            category_num[label]=0
        category_num[label]+=1
    
    # 开始计算基尼系数
    total_num=len(train_label)
    gini=0.0
    for _,num in  category_num.items():
        prop=1.0 * num/total_num
        gini+=prop * ( 1.0 - prop )
    return gini

def  calcute_gini_split(train_data,train_label,index):
    # 找到某个特征最大基尼系数的切分
    data=np.hstack((train_data,train_label.reshape(train_label.shape[0],1)))
    
    total_num=len(train_label)
    gini={}
    # 对index特征划分数据集
    data_set=list(set(data[:,index]))
    data_set=sorted(data_set)
    for idx in range(len(data_set)-1):
        x_=(data_set[idx] + data_set[idx+1]) /2.0
        new_data = data[data[:,index].argsort()] 
        data1=new_data[new_data[:,index]<=x_]
        data2=new_data[new_data[:,index]>x_]
        gini1=calcute_gini(data1[:,-1])
        gini2=calcute_gini(data2[:,-1])
        gini_=1.0* len(data1) / total_num * gini1 + 1.0* len(data2) / total_num * gini2
        gini[x_]=[gini_,len(data1), len(data2)]
    return gini
        
data,target=datasets.load_iris(return_X_y=True)    
#gini=calcute_gini_split(data,target,3)
#for k,v in gini.items():
#    print(k,':',v)
# ====最小基尼系数
#re=min(gini.items(),key=lambda x:x[1])
for idx in range(data.shape[1]):
    gini=calcute_gini_split(data,target,idx)
    re=min(gini.items(),key=lambda x:x[1][0])
    print(re)

0.15000000000000002 : 0.14906466204571436
0.25 : 0.1490646620457144
0.35 : 0.1490646620457144
0.45 : 0.14906466204571436
0.55 : 0.1490646620457144
0.8 : 0.14906466204571434
1.05 : 0.1490646620457144
1.15 : 0.1490646620457144
1.25 : 0.14906466204571436
1.35 : 0.14906466204571436
1.45 : 0.14906466204571436
1.55 : 0.1490646620457144
1.65 : 0.1490646620457144
1.75 : 0.14906466204571436
1.85 : 0.1490646620457144
1.95 : 0.1490646620457144
2.05 : 0.14906466204571436
2.1500000000000004 : 0.1490646620457144
2.25 : 0.1490646620457144
2.3499999999999996 : 0.14906466204571436
2.45 : 0.14906466204571436
  1. 剪枝
      由于决策树的构建完全是依赖于训练样本，因此该决策树对训练样本能够产生完美的拟合效果。但这样的决策树容易过拟合。
      解决过拟合问题的解决方案就是剪枝。，剪枝方法分为预剪枝和后剪枝两大类。
        |-预剪枝：是在构建决策树的过程中，终止决策树分支，从而避免过多的节点产生。预剪枝方法虽然简单但实用性不强，因为很难精确的判断何时终止树的生长。
        |-后剪枝：是在决策树构建完成之后，对那些置信度不达标的节点子树用叶子结点代替，该叶子结点的类标号用该节点子树中频率最高的类标记。
      
      常见的后剪枝方法有：
        |-CCP(Cost Complexity Pruning)
        |-REP(Reduced Error Pruning)
        |-PEP(Pessimistic Error Pruning)
        |-MEP(Minimum Error Pruning)
      剪枝的算法这里不介绍。

4.CART决策算法

  CART算法与C4.5差不多，主要CART采用的是基尼系数。 对一个数据集来说，基尼系数计算方式为：
  假设有K个类别，第k个类别的概率为p_k
    |- Gini(p) = \sum\limits_{k=1}^{K}p_k(1-p_k) = 1- \sum\limits_{k=1}^{K}p_k^2
  而且采用的是把数据集按照某个特征A分成两部分处理，假设训练样本是D，则可以分成两个数据集D_1,D_2 ,则A特征在该划分模式下的基尼系数为：
    |- Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)
  
  特征选择：所有二分中基尼系数最小的特征与对应的二分特征值。

  1. sklearnCART决策算法体验
    sklearn实现的决策算法使用的就是CART算法，其典型结果就是采用二叉树。
    下面是skleran二叉树决策算法的可视化结果
% matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn import datasets
from sklearn.model_selection import train_test_split    # 训练集切分
import sklearn
from sklearn import tree
from sklearn.externals.six import StringIO    #数据缓冲
import pydot    # 把数据转换为图像

data,target=datasets.load_iris(return_X_y=True)
# data,target=datasets.load_linnerud(return_X_y=True)
# data=data[0:100]
# target=target[0:100]

dtc=DecisionTreeClassifier(random_state=0,criterion='gini')    # 为了保证输出结果的稳定性，需要random_state固定。
dtc.fit(data,target)  

buff = StringIO()
# tree.export_graphviz(dtc,out_file=buff)     # export_graphviz只能导出数据
tree.export_graphviz(dtc, out_file=buff, feature_names=['特征1','特征2','特征3','特征4'], class_names=['A类','B类','C类'], filled=True, rounded=True, special_characters=True)  
#tree.export_graphviz(dtc, out_file=buff, feature_names=['特征1','特征2','特征3','特征4'], class_names=['A类','B类'], filled=True, rounded=True, special_characters=True)  
(graph,)= pydot.graph_from_dot_data(buff.getvalue())   # 转换为图像
graph.write_svg("iris_gini.svg")
鸢尾花在基尼系数判别方式下的决策过程可视化
  1. 计算总体Gini系数
import numpy as np
from sklearn import datasets

def calcute_gini(train_label):
    # 统计类别
    category_num={}
    for label in train_label:
        if label not in  category_num:
            category_num[label]=0
        category_num[label]+=1
    
    # 开始计算基尼系数
    total_num=len(train_label)
    gini=0.0
    for _,num in  category_num.items():
        prop=1.0 * num/total_num
        gini+=prop * ( 1.0 - prop )
    return gini

# 加载数据集
_,target=datasets.load_iris(return_X_y=True)
print(calcute_gini(target))
print(calcute_gini(target[0:100]))
print(calcute_gini(target[0:50]))

0.6666666666666667
0.5
0.0
  1. 计算一个数据集分成两个子集的基尼系数
import numpy as np
from sklearn import datasets
def calcute_gini(train_label):
    # 统计类别
    category_num={}
    for label in train_label:
        if label not in  category_num:
            category_num[label]=0
        category_num[label]+=1
    
    # 开始计算基尼系数
    total_num=len(train_label)
    gini=0.0
    for _,num in  category_num.items():
        prop=1.0 * num/total_num
        gini+=prop * ( 1.0 - prop )
    return gini

def  calcute_gini_split(train_data,train_label,index):
    # 找到某个特征最大基尼系数的切分
    data=np.hstack((train_data,train_label.reshape(train_label.shape[0],1)))
    
    total_num=len(train_label)
    gini={}
    # 对index特征划分数据集
    data_set=list(set(data[:,index]))
    data_set=sorted(data_set)
    for idx in range(len(data_set)-1):
        x_=(data_set[idx] + data_set[idx+1]) /2.0
        new_data = data[data[:,index].argsort()] 
        data1=new_data[new_data[:,index]<=x_]
        data2=new_data[new_data[:,index]>x_]
        gini1=calcute_gini(data1[:,-1])
        gini2=calcute_gini(data2[:,-1])
        gini_=1.0* len(data1) / total_num * gini1 + 1.0* len(data2) / total_num * gini2
        gini[x_]=[gini_,len(data1), len(data2)]
    return gini
        
data,target=datasets.load_iris(return_X_y=True)    
#gini=calcute_gini_split(data,target,3)
#for k,v in gini.items():
#    print(k,':',v)
# ====最小基尼系数
#re=min(gini.items(),key=lambda x:x[1])
for idx in range(data.shape[1]):
    gini=calcute_gini_split(data,target,idx)
    re=min(gini.items(),key=lambda x:x[1][0])
    print(re)

(5.45, [0.4389063317634746, 52, 98])
(3.3499999999999996, [0.5462962962962963, 114, 36])
(2.45, [0.3333333333333333, 50, 100])
(0.8, [0.3333333333333333, 50, 100])

四、决策树的使用

  1. 分类

当样本根据决策树规则，路由到最后叶子节点的时候，如果最后节点不纯度为0，则直接返回类别，如果不纯度不为0，则返回概率最大的类别。

  1. 回归

当样本根据决策树规则，路由到最后叶子节点的时候，返回叶子节点的平均值或者中间值。

五、决策树算法实现

下面代码是直接抄袭别人的，实现的是ID3算法（使用的是纯Python，没有使用numpy）。
如果上面思路清楚后，实际实现二叉树相对来说思维比较简单。

from sklearn  import datasets
import numpy as np
import math


def calcShannonEnt(trainData):
    numEntries = len(trainData)
    labelDic = {}
    for trainLine in trainData:
        currentLabel = trainLine[-1]
        if currentLabel not in labelDic:
            labelDic[currentLabel] = 0
        labelDic[currentLabel] += 1

    shannonEnt = 0.0
    for key,value in labelDic.items():
        prob = float(value)/numEntries
        shannonEnt -= prob * math.log(prob,2)
    return shannonEnt

def splitData(trainData,index,value):
    subData = []
    for trainLine in trainData:
        if trainLine[index]==value:
            reducedFeatVec = []
            for i in range(0,len(trainLine),1):
                if i==index:
                    continue
                reducedFeatVec.append(trainLine[I])
            subData.append(reducedFeatVec)
    #print('subData',subData)
    #print(len(trainData),len(subData))
    return subData

def chooseBestFeature(trainData):
    numFeatures = len(trainData[0])-1
    baseEntropy = calcShannonEnt(trainData)
    bestInfoGain = 0.0
    bestFeature = -1
    for i in range(0,numFeatures,1):
        currentFeature = [temp[i] for temp in trainData]
        uniqueValues = set(currentFeature)
        newEntropy = 0.0
        splitInfo = 0.0
        for value in uniqueValues:
            subData = splitData(trainData,i,value)
            prob = float(len(subData))/len(trainData)
            newEntropy += prob * calcShannonEnt(subData)
            splitInfo -= prob * math.log(prob,2)
        infoGain = (baseEntropy - newEntropy) / splitInfo
        if infoGain > bestInfoGain :
            bestInfoGain = infoGain
            bestFeature = I
    return bestFeature


def CreateTree(trainData):
    classList = [temp[-1] for temp in trainData]
    classListSet = set(classList)
    if len(classListSet)==1:
        return classList[0]
    if len(trainData[0])==1:
        return majorityCnt(classList)

    bestFeature = chooseBestFeature(trainData)
    myTree = {bestFeature:{}}
    featureValues = [example[bestFeature] for example in trainData]
    uniqueValues = set(featureValues)
    for value in uniqueValues:
        myTree[bestFeature][value] = CreateTree(splitData(trainData, bestFeature, value))
    return myTree


def app_test(data_train,label_train,index):
    # data_train：离散化数据集
    # label_train: 训练数据集的标签
    # index：离散化特征
    
    # 为了避免排序产生的错乱，合并数据集与标签集
    data = np.hstack((data_train,label_train.reshape(label_train.shape[0],1)))
    # 按照指定特征排序（按照index排序）
    return CreateTree(data)
    
#  加载数据集========================================
data,target=datasets.load_iris(return_X_y=True)    
ent=app_test(data,target,3)
print(ent)


{3: {0.2: 0.0, 0.4: 0.0, 0.3: 0.0, 0.5: 0.0, 0.6: 0.0, 1.4: {2: {3.9: 1.0, 4.8: 1.0, 4.7: 1.0, 4.4: 1.0, 4.6: 1.0, 5.6: 2.0}}, 1.5: {2: {4.7: 1.0, 4.2: 1.0, 4.5: 1.0, 4.9: 1.0, 4.6: 1.0, 5.0: 2.0, 5.1: 2.0}}, 1.3: 1.0, 1.6: {0: {7.2: 2.0, 6.3: 1.0, 6.0: 1.0}}, 1.0: 1.0, 1.1: 1.0, 2.5: 2.0, 2.0: 2.0, 2.1: 2.0, 1.2: 1.0, 1.7: {0: {4.9: 2.0, 6.7: 1.0}}, 0.1: 0.0, 2.2: 2.0, 2.3: 2.0, 1.8: {1: {2.5: 2.0, 3.0: 2.0, 2.9: 2.0, 3.2: {0: {5.9: 1.0, 7.2: 2.0}}, 2.7: 2.0, 2.8: 2.0, 3.1: 2.0}}, 1.9: 2.0, 2.4: 2.0}}

四、决策树相关的集成算法

  绝决策树与其他算法集成产生如下集成算法
    |-（1）Bagging + 决策树 = 随机森林
    |-（2）AdaBoost + 决策树 = 提升树
    |-（3）Gradient Boosting + 决策树 = GBDT

1. 随机森林算法

（1）从原始训练集中使用Bootstraping方法随机有放回采样选出m个样本
（2）对m个样本采用决策树（也可以使用其他分类算法）建立分类器
（3）重复n次，产生n个分类器
（4）把测试样本对n个分类器执行运算，所以分类的结果中，选择分类器最多的类别为最终输出；

from sklearn.ensemble import RandomForestClassifier
from sklearn  import datasets
from sklearn.model_selection import train_test_split    # 训练集切分

data,target=datasets.load_iris(return_X_y=True)
train_data, test_data,train_target, test_target = train_test_split(data, target, test_size=0.4,shuffle=True)

# 使用训练样本训练
rfc = RandomForestClassifier(n_estimators=100,random_state=0)
data,target=datasets.load_iris(return_X_y=True)   
rfc.fit(train_data,train_target)
print(rfc.score(test_data,test_target))
print(rfc.predict(test_data))
print(test_target)

0.9166666666666666
[0 2 2 1 1 1 0 0 0 0 2 2 2 0 1 2 1 1 2 0 2 0 2 2 2 2 2 1 2 2 2 1 2 2 1 1 1
 2 2 1 0 0 1 0 2 0 1 2 1 1 2 1 1 2 1 0 2 1 0 0]
[0 2 2 1 2 1 0 0 0 0 2 1 2 0 1 2 1 1 2 0 2 0 2 2 2 2 2 1 2 2 1 1 2 2 1 1 1
 2 2 1 0 0 1 0 2 0 1 2 1 1 2 1 1 1 1 0 1 1 0 0]

说明：

  1. 本主题，没有完整实现决策树的过程，在这里mark一下，有时间完整写一下这个算法，可以与sklearn的实现输出做一个比较。
  2. 随机森林等决策树相关的集成算法没有深入解释，后面在相关算法的时候，再深入说明。
  3. 本主题信息熵离散化二分，算出来的信息增益与信息增益比都有误差，与sklearn的结果匹配不上，估计是算某个特征的信息增益的时候，其中的标签按照是多叉方式的计算的，有时间需要调试一下。
  4. 实际很多机器学习的算法在sklearn都有实现，我们阐述这些原理，更多的是更好的调用二叉树。
  5. 可以考虑使用tensorflow实现一下，毕竟tensorflow更多的是偏向深度学习。
  6. 本主题没有实现多叉树与二叉树的完整实现，会单独开一个python数据结构之二叉树的主题来说明，并使用决策树作为使用背景。
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 211,376评论 6赞 491
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,126评论 2赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 156,966评论 0赞 347
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,432评论 1赞 283
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,519评论 6赞 385
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,792评论 1赞 290
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,933评论 3赞 406
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,701评论 0赞 266
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,143评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,488评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,626评论 1赞 340
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,292评论 4赞 329
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,896评论 3赞 313
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,742评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,977评论 1赞 265
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,324评论 2赞 360
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,494评论 2赞 348

推荐阅读更多精彩内容

  • 分类算法-决策树
    决策树理论在决策树理论中，有这样一句话，“用较少的东西，照样可以做很好的事情。越是小的决策树，越优于大的决策树”。...
    制杖灶灶阅读 5,840评论 0赞 25
  • 决策树（Decision Tree）
      决策树（Decision Tree）是一种基本的分类与回归方法，其模型呈树状结构，在分类问题中，表示基于特征对...
    殉道者之花火阅读 4,514评论 2赞 2
  • 机器学习--决策树
    一. 决策树（decision tree）：是一种基本的分类与回归方法，此处主要讨论分类的决策树。在分类问题中，表...
    YCzhao阅读 2,127评论 0赞 2
  • 决策树、随机森林
    1 前言 在了解树模型之前，自然想到树模型和线性模型，他们有什么区别呢？ 树形模型是一个一个特征进行处理，之前线性...
    高永峰_GYF阅读 1,377评论 0赞 1
  • 遥控器风波（日更第101天）
    从昨天开始遥控器突然失灵了，调个台那得需要天大的耐心，很无语，我总是觉得这是小宝的功劳老是拿着遥控器玩。不...
    盖金辉教育碎思阅读 502评论 0赞 6