决策树算法中有一步需要确定最优划分属性，选择最优划分属性的准则是：希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越高越好。
  基于该准则，有三种量化标准：

• 信息增益：信息增益最大的作为划分属性
• 信息增益率：信息增益率最大的作为划分属性
• 基尼系数：基尼系数最大的作为划分属性

  下面就这三种总量化标准，分别介绍相应的算法及其实现

信息增益（ID3）

信息熵

首先介绍要求属性信息增益所需用到的信息熵。

信息熵：是度量样本集合纯度最常用的一种指标，通过描述不确定性来量化信息，信息熵越大，不确定性越大，数据纯度越低，最小值为0。

信息熵计算公式：
  假定当前样本集合D中第k类（这里类别一般指标签值的值，如标签值有0和1，则某样本标签值为0属于反例类，为1属于正例子=类）样本所占比例为p_k，则D的信息熵定义为：

求信息熵的python代码实现（省略import版，下同）：
  编写计算信息熵的函数，实现输入标签数组，输出该数组对应的信息熵。
  根据信息熵公式，首先用Counter类函数遍历标签列，.values()得到每种标签值的个数，再对每种标签值求标签值个数占总体标签的比例，根据信息熵公式求出该标签数组的信息熵即可，具体如下。

def entropy(label):
    x = np.array(label)
    # 标签值总数
    total = np.size(x)
    # 将x标签转为一维数组，并用Counter类遍历统计
    counter = Counter(x.reshape(-1))
    # print(counter)
    # 计算每种标签值的个数
    counter_value = list(counter.values())
    # print(counter.values())
    # 计算信息熵
    ent = 0
    for value in counter_value:
        p_k = value / total
        ent += -p_k * (np.log(p_k) / np.log(2))
    return ent

# entropy函数测试
label = [[0], [1]]
ent = entropy(label)
print(ent)
# 输出: 1.0

实现根据指定维度划分数据集和标签集

  实现一个将所给的数据集按照指定维度的特征进行划分为若干个不同的数据集的函数（求信息增益需要用到的），实现输入特征集合、标签集合、指定维度（即特征列的索引），输出划分后所得到的子树属性集合、子树标记集合。
  首先利用切片根据指定维度提取指定特征列，再用np.unique函数得到该特征列中包含的不同取值，最后根据该特征中包含的不同取值使用条件索引划分数据集和标签集即可。

例子:
【输入】:
特征集合:[[0,0,0],[0,0,1],[1,0,2]]
标签集合:[[0],[1],[2]]
指定维度:0

【输出】:
[[0,0,0],[0,0,1]]和[[1,0,2]]
[[0],[1]]和[[2]]
tips:即将特征按其第0维度进行划分，由于第0维特征有0和1两个不同的数值，所以特征集合划分为[[0,0,0],[0,0,1]]和[[1,0,2]]，标签集合划分为[[0],[1]]和[[2]]

具体代码：

def split(feature, label, d):
    feature_arr = np.array(feature)
    label_arr = np.array(label)
    # 根据指定维度提取指定特征列
    d_value = feature_arr[:, d]
    # 得到该特征中包含的不同取值
    d_v = np.unique(d_value[:])
    # print(d_v)
    # 根据该特征中包含的不同取值使用条件索引进行划分
    split_feature = []
    split_label = []
    for i in d_v:
        feature_sub = feature_arr[d_value == i]
        label_sub = label_arr[d_value == i]
        # print(feature_sub)
        # print(label_sub)
        split_feature.append(feature_sub.tolist())
        split_label.append(label_sub.tolist())
        # print(split_feature)
        # print(split_label)
    return split_feature, split_label

# split函数测试
feature = [[0, 0, 0], [0, 0, 1], [1, 0, 2]]
label = [[0], [1], [2]]
d = 0
split_feature, split_label = split(feature, label, d)
print(split_feature)
print(split_label)

# 输出
# [[[0, 0, 0], [0, 0, 1]], [[1, 0, 2]]]
# [[[0], [1]], [[2]]]

实现根据信息增益找到最佳划分特征（一次划分）

计算信息增益公式:

  编写函数为决策树进行一次的结点划分，其中划分属性用信息增益值最大来找，实现输入特征集合、标签集合，输出该次划分的最佳信息增益值、最佳划分维度。
  结合前面已经编写的entropy、split两个函数，分两步走：先根据前面编写的entropy函数求出数据集的信息熵（即输入标签列得到的信息熵），再求出考虑属性信息后的信息熵，两者相减即得到该属性信息（特征值）对应的信息增益。

注意：下面的代码需要配合上面两步编写的entropy、split两个函数来一起运行

def one_split_ID3(x_data, y_label):
    # 数据集的信息熵
    ent_d = entropy(y_label)
    # 考虑属性信息后的信息熵
    gain_arr = []   # 记录所有特征的信息增益
    best_entropy = 0
    best_dimension = 0
    # 得到特征列有几个
    d_val = np.array(x_data).shape[1]
    for d in range(d_val):
        split_feature, split_label = split(x_data, y_label, d)
        gain = ent_d
        for label in split_label:
            d_v_size = len(label)   # 该特征某取值得到的标签的样本数
            d_size = len(y_label)   # 标签的总样本数
            ent_d_v = entropy(label)
            # print(ent_d_v)
            gain -= (d_v_size / d_size) * ent_d_v
        gain_arr.append(gain)
        print(f"第 {d} 维特征的信息增益为 {gain} ")
        if gain > best_entropy:
            best_entropy = gain
            best_dimension = d
    # print(gain_arr, best_entropy, best_dimension)
    return best_entropy, best_dimension

# one_split_ID3函数测试
feature = [[0, 0, 0], [0, 0, 1], [1, 0, 2]]
label = [[0], [1], [2]]
best_entropy, best_dimension = one_split_ID3(feature, label)
print(best_entropy)
print(best_dimension)
'''
输出：
第 0 维特征的信息增益为 0.9182958340544894 
第 1 维特征的信息增益为 0.0 
第 2 维特征的信息增益为 1.584962500721156 
1.584962500721156
2
'''

信息增益率（C4.5）

有了前面的entropy、split函数及信息增益的基础，求信息增益率也是套公式写代码。

计算信息增益率的公式：

  编写函数为决策树进行一次的结点划分，其中划分属性用信息增益率最大来找，实现输入特征集合、标签集合，输出该次划分的最佳信息增益率值、对应的划分维度。
  结合前面已经编写的entropy、split两个函数，根据信息增益率公式，首先求出属性的信息熵IV，再求出该属性的信息增益（用数据集的信息熵-考虑属性信息后端信息熵），二者相除即为信息增益率。

注意：下面的代码需要配合上面两步编写的entropy、split两个函数来一起运行

def one_split_C4_5(x_data, y_label):
    best_gain_ratio = 0
    best_dimension = 0
    # 得到特征列有几个
    d_val = np.array(x_data).shape[1]
    for d in range(d_val):
        split_feature, split_label = split(x_data, y_label, d)
        # 数据集的信息熵
        ent_d = entropy(y_label)
        # 特征的信息熵
        iv = 0
        gain = ent_d
        for label in split_label:
            d_v_size = len(label)  # 该特征某取值得到的标签的样本数
            d_size = len(y_label)  # 标签的总样本数
            iv -= (d_v_size / d_size) * (np.log((d_v_size / d_size)) / np.log(2))   # 该属性的信息熵（IV(a)）
            ent_d_v = entropy(label)
            gain -= (d_v_size / d_size) * ent_d_v   # 该属性的信息增益Gain(D, a)
        # print(f"gain: {gain}")
        # print(f"iv: {iv}")
        gain_ratio = gain / iv     # 该属性的信息增益率
        print(f"第 {d} 维特征的信息增益率为 {gain_ratio} ")
        if gain_ratio > best_gain_ratio:
            best_gain_ratio = gain_ratio
            best_dimension = d
    return best_gain_ratio, best_dimension

# one_split_C4_5函数测试
feature = [[0, 0, 0], [0, 2, 1], [1, 3, 2]]
label = [[0], [1], [2]]
best_gain_ratio, best_dimension = one_split_C4_5(feature, label)
print(best_gain_ratio)
print(best_dimension)
'''
输出：
第 0 维特征的信息增益率为 0.9999999999999999 
第 1 维特征的信息增益率为 1.0 
第 2 维特征的信息增益率为 1.0 
1.0
1
'''

基尼系数（CART）

基尼系数越小，数据浓度越高。

计算公式：

  编写函数为决策树进行一次的结点划分，其中划分属性用基尼系数最大来找，实现输入特征集合、标签集合，输出该次划分的最佳基尼系数、对应的划分维度及对应的最佳划分值。  根据公式，首先编写一个计算基尼系数的函数gini，实现输入标签值，得到标签值对应的基尼系数。接着编写CART算法函数，根据求属性基尼系数的公式，对每列特征的每个非重复值：根据该特征是否为该非重复值划分为两个数据集，得到两个对应的标签集，用gini函数求这两个数据集的基尼系数，再根据公式求该划分下的属性的基尼系数即可。每次更新最大基尼系数，求出所有属性的所有划分下的最大基尼系数，则得到最佳基尼系数、对应的划分维度和该特征的最佳划分值。

# 计算基尼系数
def gini(label):
    x = np.array(label)
    # 标签值总数
    total = np.size(x)
    counter = Counter(x.reshape(-1))
    # 计算每个标签值的个数
    counter_value = list(counter.values())
    # 计算基尼系数
    gini = 1
    for value in counter_value:
        p_k = value / total
        gini -= p_k**2
    return gini


def one_split_CART(x_data, y_label):
    best_gini = 10000
    best_dimension = 0
    best_value = 0
    # 得到特征列有几个
    d_val = np.array(x_data).shape[1]
    # 对每列特征
    for i in range(d_val):
        feature = np.array(x_data)[:, i]
        d_len = len(feature)
        # print(f"feature: {feature}")
        unique_val = np.unique(feature[:])
        # print(f"unique_val: {unique_val}")
        # 对每列特征中的非重复值
        for val in unique_val:
            # 根据属性值是否为某值划分为两个数据集（得到数据集对应标签值，用于求数据集的基尼系数）
            d1 = np.array(y_label)[feature == val]
            d2 = np.array(y_label)[feature != val]
            # print(f"d1: {d1}")
            # print(f"d2: {d2}")
            # 每个数据集分别求对应的基尼系数（传入数据集的标签列求）
            gini_d1 = gini(d1)
            gini_d2 = gini(d2)
            d1_len = len(d1)
            d2_len = len(d2)
            # 求该属性的基尼系数
            gini_index = (d1_len / d_len) * gini_d1 + (d2_len / d_len) * gini_d2
            # print(f"gini_index: {gini_index}")
            # 更新最大基尼系数
            if gini_index < best_gini:
                best_gini = gini_index
                best_dimension = i
                best_value = val
    return best_gini, best_dimension, best_value

# one_split_CART函数测试
feature = [[0, 0, 0], [0, 0, 1], [1, 0, 2]]
label = [[0], [1], [2]]
gini = one_split_CART(feature, label)
print(gini)
'''
输出：
(0.3333333333333333, 0, 0)
'''