百面机器学习笔记——经典算法 决策树

03 决策树

决策树是一种自上而下,对样本数据进行树形分类的过程,由结点和有向边组成。结点分为内部结点和叶结点,其中每个内部结点表示一个特征或属性,叶结点表示类别。从顶部根结点开始,所有样本聚在一起。经过根结点的划分,样本被分到不同的子结点中。再根据子结点的特征进一步划分,直至所有样本都被归到某一个类别(即叶结点)中。

决策树作为最基础、最常见的有监督学习模型,常被用于分类问题和回归问题,在市场营销和生物医药等领域尤其受欢迎,主要因为树形结构与销售、诊断等场景下的决策过程十分相似。将决策树应用集成学习的思想可以得到随机森林、梯度提升决策树等模型,这些将在第12章中详细介绍。完全生长的决策树模型具有简单直观、解释性强的特点,值得读者认真理解,这也是为融会贯通集成学习相关内容所做的铺垫。

一般而言,决策树的生成包含了特征选择、树的构造、树的剪枝三个过程,本节将在第一个问题中对几种常用的决策树进行对比,在第二个问题中探讨决策树不同剪枝方法之间的区别与联系。

问题1 决策树有哪些常用的启发函数?

从若干不同的决策树中选取最优的决策树是一个NP完全问题,在实际中我们通常会采用启发式学习的方法去构建一棵满足启发式条件的决策树。常用的决策树算法有ID3C4.5CART,它们构建树所使用的启发式函数各是什么?除了构建准则之外,它们之间的区别与联系是什么?

1. ID3—— 最大信息增益

对于样本集合D,类别数为K,数据集D的经验熵表示为

H(D) = -\sum_{k=1}^{K}{\frac{|C_{k}|}{|D|}\log_{2}\frac{|C_{k}|}{|D|}} ——(3.18)

其中$C_{k}是样本集合D中属于第k类的样本子集,|C_{k}|表示该子集的元素个数,|D|$表示样本集合的元素个数。然后计算某个特征A对于数据集D的经验条件熵$H(D|A)$为

H(D|A) = \sum_{i=1}^{n}\frac{|D_{i}|}{|D|}H(D_{i}) = \sum_{i=1}^{n}\frac{|D_{i}|}{|D|}(-\sum_{k=1}^{K}{\frac{|D_{ik}|}{|D_{i}|}\log_{2}\frac{|D_{ik}|}{|D_{i}|}}) ——(3.19)

其中,$D_{i}$表示D中特征A取第i个值的样本子集,$D_{ik}$表示$D_{i}$中属于第k类的样本子集。于是信息增益$g(D,A)$可以表示为二者之差,可得

g(D,A) = H(D) - H(D|A) ——(3.20)

这些定义听起来有点像绕口令,不妨我们用一个例子来简单说明下计算过程。假设共有5个人追求场景中的女孩,年龄有两个属性(老,年轻),长相有三个属性(帅,一般,丑),工资有三个属性(高,中等,低),会写代码有两个属性(会,不会),最终分类结果有两类(见,不见)。我们根据女孩有监督的主观意愿可以得到表3.1。

# 构建数据
import pandas as pd
import numpy as np
columns = ['姓名', '年龄', '长相', '工资', '写代码', '类别']
data = [['小A', '老' ,'帅', '高', '不会', '不见'],
['小B', '年轻', '一般', '中等', '会', '见'],
['小C', '年轻', '丑', '高', '不会', '不见'],
['小D', '年轻', '一般', '高', '会', '见'],
['小L', '年轻', '一般', '低', '不会', '不见']]
data = pd.DataFrame(data, columns = columns)
print('表3.15个候选对象的属性以及女孩对应的主观意愿')
data
表3.15个候选对象的属性以及女孩对应的主观意愿
.dataframe tbody tr th:only-of-type { vertical-align: middle; }
.dataframe tbody tr th {
    vertical-align: top;
}

.dataframe thead th {
    text-align: right;
}
姓名 年龄 长相 工资 写代码 类别
0 小A 不会 不见
1 小B 年轻 一般 中等
2 小C 年轻 不会 不见
3 小D 年轻 一般
4 小L 年轻 一般 不会 不见

1.1 计算经验熵

from collections import Counter

def caculate_entropy(lst):
    """计算经验熵,也可以计算不同属性的信息熵
    lst: 传入一个特征列
    return: 信息熵
    """
    n = len(lst)
    lst = Counter(lst)
    res = sum(-(v/n) * np.log2(v/n) for k,v in lst.items())
#     for k, v in lst.items():
#         p = v/n
#         res -= p * np.log2(p)
    return res

print("H(D)=%.3f"%caculate_entropy(data['类别'].tolist()))
H(D)=0.971

1.2 计算条件经验熵

def attribute_entropy(attribute, data, flag = '类别'):
    """计算条件经验熵,即计算不同特征下的信息熵
    attribute: 特征
    data: 数据
    flag: 标签
    return 条件信息熵
    """
    res = 0
    n = len(data)
    for name in data[attribute].unique():
        temp = data[data[attribute]==name]
        n_ = len(temp)
        res += n_/n * caculate_entropy(temp[flag].tolist())
    return res

for attribute in ['年龄', '长相', '工资', '写代码']:
    print("H(D|%s)=%.3f"%(attribute, attribute_entropy(attribute, data)))
H(D|年龄)=0.800
H(D|长相)=0.551
H(D|工资)=0.551
H(D|写代码)=0.000

1.3 计算各个特征的信息增益

# 信息增益
def caculate_gain(H_D, attribute, data):
    return H_D - attribute_entropy(attribute, data)

H_D = caculate_entropy(data['类别'].tolist())
for attribute in ['年龄', '长相', '工资', '写代码']:
    print("g(D,%s)=%.3f"%(attribute, caculate_gain(H_D, attribute, data)))
g(D,年龄)=0.171
g(D,长相)=0.420
g(D,工资)=0.420
g(D,写代码)=0.971

1.4 实现决策树算法

根据信息增益原理实现决策树算法,借助pandas、numpy、Counter等包实现。

from collections import Counter
class Tree:
    
    def __init__(self, x):
        self.x = x
        self.children = []

class MyDecisionTreeClassifier:
    
    def __init__(self):
        self.node = None                 # 决策树根节点
        self.available_attribute = set() # 特征列
        self.flag = None                 # 标签列
        self.target = set()              # 目标值
        
    # 计算信息熵
    def caculate_entropy(self, lst):
        """计算经验熵,也可以计算不同属性的信息熵
        lst: 传入一个特征列
        return: 信息熵
        """
        n = len(lst)
        lst = Counter(lst)
        res = sum(-(v/n) * np.log2(v/n) for k,v in lst.items())
        return res

    def attribute_entropy(self, attribute, data):
        """计算条件经验熵,即计算不同特征下的信息熵
        attribute: 特征
        data: 数据
        return 条件信息熵
        """
        res = 0
        n = len(data)
        for name in data[attribute].unique():
            temp = data[data[attribute]==name]
            n_ = len(temp)
            res += n_ / n * self.caculate_entropy(temp[self.flag].tolist())
        return res
    
    # 信息增益
    def caculate_gain(self, H_D, attribute, data):
        return H_D - self.attribute_entropy(attribute, data)
    
    # 筛选信息熵
    def select_method(self, data):
        H_D = self.caculate_entropy(data[self.flag].tolist())
        # 计算全部的信息增益,从中选出最大的
        gain_res = [(i, self.caculate_gain(H_D, i, data)) for i in self.available_attribute]
        gain_res.sort(key = lambda x:x[1], reverse = True)
        return gain_res[0][0]
    
    def back_track(self, data, node = None):
        '''递归'''
        temp = data[self.flag].value_counts()
        # 递归终止条件: 1. 只剩一个类别   2. 没有其他特征可选
        if len(temp) == 1 or len(self.available_attribute) == 0:
            flag = Tree(temp.index[0])
            node.children = [flag]
            return
        
        attribute = self.select_method(data)
        if node is None:
            self.node = Tree(attribute)
            node = self.node
        
        self.available_attribute.remove(attribute)
        for a in data[attribute].unique():
            next_temp = data[data[attribute] == a]
            node_i = Tree('%s=%s'%(attribute, a))
            node.children.append(node_i)
            self.back_track(next_temp, node_i)
        #self.available_attribute.add(attribute)
            
    def fit(self, data, flag = None):
        self.available_attribute = set(data.columns) # 属性
        self.available_attribute.remove(flag)
        self.target = data[flag].unique()
        self.flag = flag
        # 构建决策树
        # 初始化决策树根节点
        self.back_track(data, None)
        
    # 打印规则
    def show_rule(self):
        def backtract(root, pre):
            if not root:
                return
            pre += ' ---> %s'%root.x
            if root.x in self.target:
                print(pre.lstrip('---> '))
                pre = ''
            for x in root.children:
                backtract(x, pre)
        backtract(self.node, '')
        
    # 预测分类
    def predict(self, data):
        stack = self.node.children
        def bfs(stack, target):
            while stack:
                children = []
                for i in stack:
                    if i.x in self.target:
                        return i.x
                    elif i.x in target:
                        children.extend(i.children)
                    else:
                        continue
                stack = children
            return None
        res = []
        for i in data.index:
            target = set('%s=%s'%(k,v) for k,v in dict(data.loc[i]).items())
            res.append(bfs(stack, target))
        return res
        
        
features = ['年龄', '长相', '工资', '写代码','类别']
c_f = MyDecisionTreeClassifier()
c_f.fit(data[features], flag = '类别')
print("打印规则:")
c_f.show_rule()
print("\n原始分类:")
print(data["类别"].tolist())
print("决策树预测类别:")
print(c_f.predict(data[features[:-1]]))
打印规则:
写代码 ---> 写代码=不会 ---> 不见
写代码 ---> 写代码=会 ---> 见

原始分类:
['不见', '见', '不见', '见', '不见']
决策树预测类别:
['不见', '见', '不见', '见', '不见']

换一个数据集

data_2 = pd.DataFrame(columns = ['色泽','根蒂','敲声','纹理','脐部','触感','好瓜'])
map_dict = {'色泽':{1:'青绿',2:'乌黑',3:'浅白'},
            '根蒂':{1:'蜷缩',2:'稍蜷',3:'硬挺'},
            '敲声':{1:'浊响',2:'沉闷',3:'清脆'},
            '纹理':{1:'清晰',2:'稍糊',3:'模糊'},
            '脐部':{1:'凹陷',2:'稍凹',3:'平坦'},
            '触感':{1:'硬滑',2:'软粘'},
            '好瓜':{1:'是',2:'否'}}

def get_attibute(lst):
    name_dict = dict(zip(range(7), ['色泽','根蒂','敲声','纹理','脐部','触感','好瓜']))
    f = lambda x:map_dict[name_dict[x[0]]][x[1]]
    return list(map(f, enumerate(lst)))

lsts = [[1,1,1,1,1,1,1],
        [2,1,2,1,1,1,1],
        [2,1,1,1,1,1,1],
        [1,1,2,1,1,1,1],
        [3,1,1,1,1,1,1],
        [1,2,1,1,2,2,1],
        [2,2,1,2,2,2,1],
        [2,2,1,1,2,1,1],
        [2,2,2,2,2,1,2],
        [1,3,3,1,3,2,2],
        [3,3,3,3,3,1,2],
        [3,1,1,3,3,2,2],
        [1,2,1,2,1,1,2],
        [3,2,2,2,1,1,2],
        [2,2,1,1,2,2,2],
        [3,1,1,3,3,1,2],
        [1,1,2,2,2,1,2]]
for lst in lsts:
    data_2.loc[len(data_2)] = get_attibute(lst)
    
data_2
.dataframe tbody tr th:only-of-type { vertical-align: middle; }
.dataframe tbody tr th {
    vertical-align: top;
}

.dataframe thead th {
    text-align: right;
}
色泽 根蒂 敲声 纹理 脐部 触感 好瓜
0 青绿 蜷缩 浊响 清晰 凹陷 硬滑
1 乌黑 蜷缩 沉闷 清晰 凹陷 硬滑
2 乌黑 蜷缩 浊响 清晰 凹陷 硬滑
3 青绿 蜷缩 沉闷 清晰 凹陷 硬滑
4 浅白 蜷缩 浊响 清晰 凹陷 硬滑
5 青绿 稍蜷 浊响 清晰 稍凹 软粘
6 乌黑 稍蜷 浊响 稍糊 稍凹 软粘
7 乌黑 稍蜷 浊响 清晰 稍凹 硬滑
8 乌黑 稍蜷 沉闷 稍糊 稍凹 硬滑
9 青绿 硬挺 清脆 清晰 平坦 软粘
10 浅白 硬挺 清脆 模糊 平坦 硬滑
11 浅白 蜷缩 浊响 模糊 平坦 软粘
12 青绿 稍蜷 浊响 稍糊 凹陷 硬滑
13 浅白 稍蜷 沉闷 稍糊 凹陷 硬滑
14 乌黑 稍蜷 浊响 清晰 稍凹 软粘
15 浅白 蜷缩 浊响 模糊 平坦 硬滑
16 青绿 蜷缩 沉闷 稍糊 稍凹 硬滑
# 随机打乱数据
from sklearn.utils import shuffle
data_2 = shuffle(data_2)

features = ['色泽','根蒂','敲声','纹理','脐部','触感','好瓜']
c_f = MyDecisionTreeClassifier()
c_f.fit(data_2[features][:14], flag = '好瓜')
print("打印规则:")
c_f.show_rule()
print("\n原始分类:")
print(data_2["好瓜"][14:].tolist())
print("决策树预测类别:")
print(c_f.predict(data_2[14:]))
打印规则:
纹理 ---> 纹理=模糊 ---> 否
纹理 ---> 纹理=清晰 ---> 敲声=沉闷 ---> 是
纹理 ---> 纹理=清晰 ---> 敲声=浊响 ---> 是
纹理 ---> 纹理=清晰 ---> 敲声=清脆 ---> 否
纹理 ---> 纹理=稍糊 ---> 触感=硬滑 ---> 否
纹理 ---> 纹理=稍糊 ---> 触感=软粘 ---> 是

原始分类:
['是', '是', '否']
决策树预测类别:
['是', '是', '是']

我们可以看到上述实验中,我们仅采用了一部分数据作为训练集进行构建决策树,然后用新的数据进行预测,结果已经开始出现错误了,这是因为新的数据集中可能包含了新的特征值,训练集中的规则没有覆盖到或者说训练集中的规则已经过拟合了导致测试集的预测效果不佳。

2. C4.5 —— 最大信息增益比

特征A对于数据集D的信息增益比定义为

g_{R}(D,A) = \frac{g(D,A)}{H_{A}(D)}——(3.21)

其中

H_{A}(D) = -\sum_{i=1}^{n}\frac{|D_{i}|}{|D|}\log_{2}\frac{|D_{i}|}{|D|}——(3.22)

称为数据集D关于A的取值熵。针对上述问题,我们可以根据式(3.22)求出数据集关于每个特征的取值熵。这里的取值熵类似于上面提到的经验熵,不同点就在于经验熵是关于目标值的取值熵,因此我们可以复用经验熵的代码,计算结果如下:

2.1 计算取值熵

for attribute in ['年龄', '长相', '工资', '写代码']:
    lst = data[attribute].tolist()
    HA_D = caculate_entropy(lst)
    print("H_%s(D)=%.3f"%(i, HA_D))
H_写代码(D)=0.722
H_写代码(D)=1.371
H_写代码(D)=1.371
H_写代码(D)=0.971

2.2 计算信息增益比

# 1. 计算经验熵
H_D = caculate_entropy(data['类别'].tolist())
for attribute in ['年龄', '长相', '工资', '写代码']:
    # 2. 计算信息增益
    gD_A = caculate_gain(H_D, attribute, data)
    # 3. 计算取值熵
    lst = data[attribute].tolist()
    HA_D = caculate_entropy(lst)
    # 4. 计算信息增益比
    grD_A = gD_A / HA_D
    
    print("gr(D,%s)=%.3f"%(attribute, grD_A))
gr(D,年龄)=0.237
gr(D,长相)=0.306
gr(D,工资)=0.306
gr(D,写代码)=1.000

信息增益比最大的仍是特征“写代码”,但通过信息增益比,特征“年龄”对应的指标上升了,而特征“长相”和特征“工资”却有所下降。

注:
电子书中

g_{R}(D,长相)=0.402,
g_{R}(D,工资)=0.402

个人认为是算错了的,如果有知道的小伙伴欢迎讨论该问题。

2.3 实现决策树算法

根据信息增益比原理实现决策树算法,考虑到和ID3算法相似点很多,因此对MyDecisionTreeClassifier类进行一定程度的改进,即可兼容两种决策树算法,具体做法如下:

  1. 补充C4.5算法中计算信息增益比的函数;
  2. MyDecisionTreeClassifier类中增加特征选择筛选器,用来根据传入的参数决定使用相应的算法:ID3对应信息增益,C4.5对应信息增益比。
# ID3 算法
class MyDecisionTreeClassifier_ID3:
    
    def __init__(self):
        self.node = None                 # 决策树根节点
        self.available_attribute = set() # 特征列
        self.flag = None                 # 标签列
        self.target = set()              # 目标值
    
    # 计算信息熵
    def caculate_entropy(self, lst):
        """计算经验熵,也可以计算不同属性的信息熵
        lst: 传入一个特征列
        return: 信息熵
        """
        n = len(lst)
        lst = Counter(lst)
        res = sum(-(v/n) * np.log2(v/n) for k,v in lst.items())
        return res

    # 条件信息熵
    def attribute_entropy(self, attribute, data):
        """计算条件经验熵,即计算不同特征下的信息熵
        attribute: 特征
        data: 数据
        return 条件信息熵
        """
        res = 0
        n = len(data)
        for name in data[attribute].unique():
            temp = data[data[attribute]==name]
            n_ = len(temp)
            res += n_ / n * self.caculate_entropy(temp[self.flag].tolist())
        return res
    
    # 信息增益
    def caculate_gain(self, H_D, attribute, data):
        return H_D - self.attribute_entropy(attribute, data)
    
    # 筛选信息熵
    def select_method(self, data):
        H_D = self.caculate_entropy(data[self.flag].tolist())
        # 计算全部的信息增益,从中选出最大的
        gain_res = [(i, self.caculate_gain(H_D, i, data)) for i in self.available_attribute]
        gain_res.sort(key = lambda x:x[1], reverse = True)
        return gain_res[0][0]
    
    # 递归构建决策树
    def back_track(self, data, node = None):
        '''递归'''
        temp = data[self.flag].value_counts()
        # 递归终止条件: 1. 只剩一个类别   2. 没有其他特征可选
        if len(temp) == 1 or len(self.available_attribute) == 0:
            flag = Tree(temp.index[0])
            node.children = [flag]
            return
        
        attribute = self.select_method(data)
        if node is None:
            self.node = Tree(attribute)
            node = self.node
        
        self.available_attribute.remove(attribute)
        for a in data[attribute].unique():
            next_temp = data[data[attribute] == a]
            node_i = Tree('%s=%s'%(attribute, a))
            node.children.append(node_i)
            self.back_track(next_temp, node_i)
    
    # 训练
    def fit(self, data, flag = None):
        self.available_attribute = set(data.columns) # 属性
        self.available_attribute.remove(flag)
        self.target = data[flag].unique()
        self.flag = flag
        # 构建决策树
        self.back_track(data, None)
        
    # 打印规则
    def show_rule(self):
        def backtract(root, pre):
            if not root:
                return
            pre += ' ---> %s'%root.x
            if root.x in self.target:
                print(pre.lstrip('---> '))
                pre = ''
            for x in root.children:
                backtract(x, pre)
        backtract(self.node, '')
        
    # 预测分类
    def predict(self, data):
        stack = self.node.children
        def bfs(stack, target):
            while stack:
                children = []
                for i in stack:
                    if i.x in self.target:
                        return i.x
                    elif i.x in target:
                        children.extend(i.children)
                    else:
                        continue
                stack = children
            return None
        res = []
        for i in data.index:
            target = set('%s=%s'%(k,v) for k,v in dict(data.loc[i]).items())
            res.append(bfs(stack, target))
        return res
    
# C4.5算法
class MyDecisionTreeClassifier_C45(MyDecisionTreeClassifier_ID3):
    
    # 信息增益率
    def caculate_gain_r(self, ent_D, attribute, data):
        lst = data[attribute].tolist()
        return self.caculate_gain(ent_D, attribute, data) / self.caculate_entropy(lst)
    
    # 筛选信息熵
    def select_method(self, data):
        H_D = self.caculate_entropy(data[self.flag].tolist())
        # 计算全部的信息增益,从中选出最大的
        gain_res = [(i, self.caculate_gain_r(H_D, i, data)) for i in self.available_attribute]
        gain_res.sort(key = lambda x:x[1], reverse = True)
        return gain_res[0][0]
    
# 调用主类
class MyDecisionTreeClassifier:
    
    def __new__(self, method = 'ID3'):
        self.method_map = {'ID3':MyDecisionTreeClassifier_ID3,
                      'C45':MyDecisionTreeClassifier_C45}
        self.decisiontree = self.method_map[method.upper()]
        print('调用【', self.decisiontree.__name__, '】\n')
        return self.decisiontree()
# 测试 1. 调用ID3
c_f = MyDecisionTreeClassifier()
features = ['年龄', '长相', '工资', '写代码','类别']
c_f.fit(data[features], flag = '类别')
print("打印规则:")
c_f.show_rule()
print("\n原始分类:")
print(data["类别"].tolist())
print("决策树预测类别:")
print(c_f.predict(data[features[:-1]]))
调用【 MyDecisionTreeClassifier_ID3 】

打印规则:
写代码 ---> 写代码=不会 ---> 不见
写代码 ---> 写代码=会 ---> 见

原始分类:
['不见', '见', '不见', '见', '不见']
决策树预测类别:
['不见', '见', '不见', '见', '不见']
# 测试 2. 调用C45
c_f = MyDecisionTreeClassifier(method='c45')
features = ['年龄', '长相', '工资', '写代码','类别']
c_f.fit(data[features], flag = '类别')
print("打印规则:")
c_f.show_rule()
print("\n原始分类:")
print(data["类别"].tolist())
print("决策树预测类别:")
print(c_f.predict(data[features[:-1]]))
调用【 MyDecisionTreeClassifier_C45 】

打印规则:
写代码 ---> 写代码=不会 ---> 不见
写代码 ---> 写代码=会 ---> 见

原始分类:
['不见', '见', '不见', '见', '不见']
决策树预测类别:
['不见', '见', '不见', '见', '不见']

3. CART——最大基尼系数(Gini)

Gini描述的是数据的纯度,与信息熵含义类似。

Gini(D) = 1 - \sum_{k=1}^{K}(\frac{|C_{k}|}{|D|})^{2}——(3.23)

CART在每一次迭代中选择基尼指数最小的特征及其对应的切分点进行分类。但与ID3、C4.5不同的是,CART是一颗二叉树,采用二元切割法,每一步将数据按特征A的取值切成两份,分别进入左右子树。特征A的Gini指数定义为

Gini(D|A) = \sum_{i=1}^{n}\frac{|D_{i}|}{|D|}Gini(D_{i})——(3.24)

还是考虑上述的例子,应用CART分类准则,根据式(3.24)可计算出各个特征的Gini指数为

3.1 计算基尼系数

# 基尼系数
def gini_Di(c1, nums):
    c1_sum = c1.sum()
    c1 = c1 / c1_sum
    return c1_sum / nums * np.sum(np.square(c1))

def gini_D(data, A, flag):
    values = data[A].unique()  # 特征A的取值
    nums = len(data)
    for value in values:
        c1 = np.array(data[data[A]==value][flag].value_counts().tolist())
        c2 = np.array(data[data[A]!=value][flag].value_counts().tolist())
        res["%s=%s"%(A,value)] = 1 - gini_Di(c1, nums) - gini_Di(c2, nums)
    
print("=====Gini系数=====")
res = {}
for A in ['年龄', '长相', '工资', '写代码']:
    gini_D(data, A, '类别')
print(res)
=====Gini系数=====
{'年龄=老': 0.4, '年龄=年轻': 0.39999999999999997, '长相=帅': 0.4, '长相=一般': 0.2666666666666667, '长相=丑': 0.4, '工资=高': 0.46666666666666673, '工资=中等': 0.30000000000000004, '工资=低': 0.4, '写代码=不会': 0.0, '写代码=会': 0.0}

3.2 实现决策树算法

基于基尼系数的决策树为二叉树,因此在实现上和ID3算法和C4.5算法有点不同。

class Tree_2:
    
    def __init__(self, x):
        self.x = x
        self.left = None
        self.right = None
        
class MyDecisionTreeClassifier_Gini:
    
    def __init__(self):
        self.node = None                 # 决策树根节点
        self.available_attribute = set() # 特征列
        self.flag = None                 # 标签列
        self.target = set()              # 目标值
        self.n = None                    # 记录数
        self.res = {}                    # 不同属性值的基尼系数字典
        self.attribute_value = {}        # 所有特征值的可能性
        
    # 基尼系数
    def gini_Di(self, c1, nums):
        c1_sum = c1.sum()
        c1 = c1 / c1_sum
        return c1_sum / nums * np.sum(np.square(c1))

    def gini_D(self, data, attribute):
        values = data[attribute].unique()  # 特征A的取值
        nums = len(data)
        for value in values:
            c1 = np.array(data[data[attribute]==value][self.flag].value_counts().tolist())
            c2 = np.array(data[data[attribute]!=value][self.flag].value_counts().tolist())
            self.res["%s=%s"%(attribute, value)] = 1 - gini_Di(c1, nums) - gini_Di(c2, nums)
            
    # 筛选信息熵
    def select_method(self, data):
        self.res = {}
        # 计算全部的信息增益,从中选出最大的
        for attribute in self.available_attribute:
            self.gini_D(data, attribute)
        gini = sorted(self.res.items(), key = lambda x:x[1])
        return gini[0][0].split('=')
    
    # 递归构建决策树
    def back_track(self, data, node = None):
        '''递归'''
        temp = data[self.flag].value_counts()
        # 递归终止条件: 1. 只剩一个类别   2. 没有其他特征可选
        if len(temp) == 1 or len(self.available_attribute) == 0:
            flag = Tree_2(temp.index[0])
            node.left = flag
            return 
        
        attribute, value = self.select_method(data)
        if node is None:
            self.node = Tree_2('%s=%s'%(attribute, value))
            node = self.node
        
        self.available_attribute.remove(attribute)
        # 构建左右子树
        left_data = data[data[attribute] == value]
        right_data = data[data[attribute] != value]
        node_left = Tree_2('%s=%s, 是'%(attribute, value))
        node_right = Tree_2('%s=%s, 否'%(attribute, value))
        node.left = node_left
        node.right = node_right
        self.back_track(left_data, node_left)
        self.back_track(right_data, node_right)
        
    def fit(self, data, flag = None):
        self.available_attribute = set(data.columns) # 属性
        self.available_attribute.remove(flag)
        for attribute in self.available_attribute:
            self.attribute_value[attribute] = data[attribute].unique()
        self.target = data[flag].unique()
        self.flag = flag
        # 构建决策树
        self.back_track(data, None)

    # 打印规则
    def show_rule(self):
        def backtract(root, pre):
            if not root:
                return
            pre += ' ---> %s'%root.x
            if root.x in self.target:
                print(pre.lstrip('---> '))
                pre = ''
            backtract(root.left, pre)
            backtract(root.right, pre)
        backtract(self.node, '')
        
    # 预测分类
    def predict(self, data):
        def dfs(root):
            if not root:
                return
            if root.left and root.left.x in self.target:
                return root.left.x
            elif root.left and root.left.x in target:
                #print("#1", root.left.x)
                return dfs(root.left)
            elif root.right and root.right.x in target:
                #print("#2", root.right.x)
                return dfs(root.right)
        
        res = []
        for i in data.index:
            target = set('%s=%s, 是'%(k,v) for k,v in dict(data.loc[i]).items())
            target |= set('%s=%s, 否'%(k.split("=")[0], v) for k in target for v in self.attribute_value[k.split("=")[0]] if v != k.split("=")[1])
            # print(target)
            res.append(dfs(self.node))
        return res
c_f = MyDecisionTreeClassifier_Gini()
features = ['年龄', '长相', '工资', '写代码','类别']
c_f.fit(data[features], flag = '类别')
print("打印规则:")
c_f.show_rule()
print("\n原始分类:")
print(data["类别"].tolist())
print("决策树预测类别:")
print(c_f.predict(data[features[:-1]]))
打印规则:
写代码=不会 ---> 写代码=不会, 是 ---> 不见
写代码=不会 ---> 写代码=不会, 否 ---> 见

原始分类:
['不见', '见', '不见', '见', '不见']
决策树预测类别:
['不见', '见', '不见', '见', '不见']
features = ['色泽','根蒂','敲声','纹理','脐部','触感','好瓜']
c_f = MyDecisionTreeClassifier_Gini()
c_f.fit(data_2[features], flag = '好瓜')
print("打印规则:")
c_f.show_rule()
print("\n原始分类:")
print(data_2["好瓜"].tolist())
print("决策树预测类别:")
print(c_f.predict(data_2[features[:-1]]))
打印规则:
纹理=清晰 ---> 纹理=清晰, 是 ---> 触感=硬滑, 是 ---> 是
纹理=清晰 ---> 纹理=清晰, 是 ---> 触感=硬滑, 否 ---> 敲声=清脆, 是 ---> 否
纹理=清晰 ---> 纹理=清晰, 是 ---> 触感=硬滑, 否 ---> 敲声=清脆, 否 ---> 色泽=青绿, 是 ---> 是
纹理=清晰 ---> 纹理=清晰, 是 ---> 触感=硬滑, 否 ---> 敲声=清脆, 否 ---> 色泽=青绿, 否 ---> 否
纹理=清晰 ---> 纹理=清晰, 否 ---> 脐部=稍凹, 是 ---> 根蒂=稍蜷, 是 ---> 是
纹理=清晰 ---> 纹理=清晰, 否 ---> 脐部=稍凹, 是 ---> 根蒂=稍蜷, 否 ---> 否
纹理=清晰 ---> 纹理=清晰, 否 ---> 脐部=稍凹, 否 ---> 否

原始分类:
['否', '是', '是', '否', '否', '否', '是', '否', '否', '否', '是', '是', '是', '否', '是', '是', '否']
决策树预测类别:
['否', '是', '是', '否', '是', '否', '是', '否', '否', '否', '是', '是', '是', '否', '是', '是', '否']

参考资料:百面机器学习