# 实验数据
ID,年龄,有工作,有自己的房子,信贷情况,类别
1,青年,否,否,一般,否
2,青年,否,否,好,否
3,青年,是,否,好,是
4,青年,是,是,一般,是
5,青年,否,否,一般,否
6,中年,否,否,一般,否
7,中年,否,否,好,否
8,中年,是,是,好,是
9,中年,否,是,非常好,是
10,中年,否,是,非常好,是
11,老年,否,是,非常好,是
12,老年,否,是,好,是
13,老年,是,否,好,是
14,老年,是,否,非常好,是
15,老年,否,否,一般,否

# classification with Decision Tree by ID3 and C4.5 algorithm

import  numpy as np
import pandas as pd
from sklearn.model_selection import  train_test_split

class DecisionTree():
    def __init__(self, feature_names, eps=0.03, depth=10, min_leaf_size=1, method="gain"):
        '''
        eps:精度
        depth:深度
        min_leaf_size:最小叶子大小
        method:方法gain或者ratio
        '''
        self.feature_names = feature_names
        self.eps = eps
        self.depth = depth
        self.min_leaf_size=min_leaf_size
        self.method = method


    def gain_entropy(self, x):
        """
        计算信息增益
        x: 数据集的某个特征
        :return ent: H(D)=-sum_{k=1}^Kfrac{|C_k|}{|D|}log_2frac{|C_k|}{|D|}
        """
        entropy = 0
        for x_value in set(x):
            p = x[x == x_value].shape[0] / x.shape[0]
            entropy -= p * np.log2(p)
        return entropy

    def gain_condition_entropy(self, x, y):
        entropy = 0
        for x_value in set(x):
            sub_y = y[x == x_value]
            tmp_ent = self.gain_entropy(sub_y)
            p = sub_y.shape[0] / y.shape[0]
            entropy += p * tmp_ent
        return entropy


    def Gain(self, x, y):
        if self.method == "gain":
            return self.gain_entropy(x) - self.gain_condition_entropy(x, y)
        else:
            return 1 - self.gain_condition_entropy(x, y) / self.gain_entropy(x)

    def fit(self, X, y):
       self.tree = self._built_tree(X, y)

    def _built_tree(self, X, y, depth=1):
        if len(set(y)) == 1:
            return y[0]



        label_1, label_2 = set(y)
        max_label = label_1 if np.sum(y == label_1) > np.sum(y == label_2) else label_2
        # print("max_label", max_label)

        if len(X[0]) == 0:
            return max_label
        if depth > self.depth:
            return max_label

        if len(y) 

C4.5
C4.5就是讲ID3中的信息增益换为信息增益比。

决策树的减枝
由于决策树生成后有过拟合现象，缺乏泛化能力，因此需要进行减枝达到全局最优。 

减枝通过极小化决策树整体的损失函数或代价函数来实现。tkNt

基尼指数分类树生成算法

输入：训练数据集，停止条件
输出：分类树
从根节点开始，递归的对每个节点进行一下操作，构建二叉决策树。
（1）计算所有特征的所有可能取值的基尼指数
（2）选择最优特征与最优取值，将数据集切分为两个子数据集
（3）递归调用（1）（2）直到满足停止条件
（4）生成CART分类树
停止条件为：节点中的样本个数小于预定阈值，或样本集的基尼指数小于阈值，或没有更多的特征。

CART减枝

CART减枝步骤：首先从生成算法产生的决策树T0,T1,...,Tn；然后通过交叉验证算法在独立的验证数据集上对子树进行测试，从中选择最优子树。
减枝过程中损失函数为T0,T1,...,Tn，然后从中通过交叉验证选择最优子树。具体可以参看Breiman算法。
在对α，产生新的区间。
然后利用独立的验证数据，交叉验证子树序列T0,T1,...,Tn，平方误差或基尼指数最小的决策树被认为是最优的。

CART减枝算法

输入：原完整的生成树
输出：减枝后的生成树
（1）设k=0,T=T0
（2）设inf
（3）自上而下的对各内部节点t计算

CRAT

'''
Implement the decision_tree to adjust more than 1 dimension
'''

import  numpy as np
import  matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

class DecisionTreeRegression():
    def __init__(self, depth = 5, min_leaf_size = 5):
        self.depth = depth
        self.min_leaf_size = min_leaf_size
        self.left = None
        self.right = None
        self.prediction = None

        self.j = None
        self.s = None


    def mean_squared_error(self, labels, prediction):

        if labels.ndim != 1:
            print("Error: Input labels must be one dimensional")

        return np.mean((labels - prediction) ** 2)

    def train(self, X, y):
        if X.ndim == 1:
            X = X.reshape(-1, 1)

        if y.ndim != 1:
            print("Error: Data set labels must be one dimensional")
            return

        #控制最小叶子
        if len(X) = s
        X_left = X[mask_left, j]
        X_right = X[mask_right, j]

        c_left = np.mean(y[mask_left])
        c_right = np.mean((y[mask_right]))

        error_left = np.sum((X_left - c_left) ** 2)
        error_right = np.sum((X_right - c_right) ** 2)
        return error_left + error_right


    def split(self, X, y):
        min_j = 0
        min_error = np.inf

        for j in range(len(X[0])):
            X_sorted = np.sort(X[:, min_j])  # 不改变X
            slice_value = (X_sorted[1:] + X_sorted[:-1]) / 2
            min_s = X[0, min_j] + X[-1, min_j]
            min_s_index = slice_value[0]
            for s_index in range(len(slice_value)):
                error = self.squaErr(X, y, j, slice_value[s_index])
                if error = self.s:
                return self.right.predict(x)
            else:
                return self.left.predict(x)
        else:
            print("Error: Decision tree not yet trained")
            return None

def main():

    X = np.array([[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6, 6], [7, 7], [8, 8], [9, 9], [10, 10]])
    y = np.array([5.56, 5.70, 5.91, 6.40, 6.80, 7.05, 8.90, 8.70, 9.00, 9.05])



    tree = DecisionTreeRegression(depth = 5, min_leaf_size = 2)
    tree.train(X,y)


    test_cases = np.array([np.arange(0.0, 10.0, 0.01), np.arange(0.0, 10.0, 0.01)]).T
    predictions = np.array([tree.predict(x) for x in test_cases])

    #绘图
    fig = plt.figure(figsize=(10, 8))
    ax = fig.add_subplot(111, projection="3d")
    ax.scatter(X[:, 0], X[:, 1], y, s=20, edgecolor="black",
               c="darkorange", label="data")
    ax.plot(test_cases[:, 0], test_cases[:, 1], predictions, c='r')

    # plt.scatter(X[:, 0], y, s=20, edgecolor="black", c="darkorange", label="data")
    # plt.plot(test_cases[:, 1], predictions, c="r")

    plt.show()



if __name__ == '__main__':
    main()

对比

1. ID3与C4.5区别：
   ID3采用信息增益进行特征选择，C4.5采用信息增益比进行特征选择。信息增益存在偏向于选择取值较多的特征。

2. ID3，C4.5为多叉树，CART为二叉树。

3. CART在一条通路上可以对一个特征进行多次划分，ID3或C4.5在一个通路上只能对一个特征进行一次划分。

4. ID3，C4.5无法直接处理离散问题，CART可以直接处理离散问题。

5. 信息增益、基尼指数、方差都能表示数据的不确定性。
   信息增益通常用在有限离散特征有限离散类型的情况，即特征离散的分类情况，信息增益需要各个特征概率的极大似然估计以及类型概率的极大似然估计。
   基尼指数用于有限离散类型的情况，即特征连续或离散的分类情况。基尼指数只需要知道类型概率的极大似然估计。
   方差不根据分布概率确定不确定性，方差根据特征的取值情况度量信息的离散程度。需要知道具体的值 。可以用于连续型数据。用于KDTree选择切分特征，在主成分分析(PCA)对数据进行降维降噪。

6. 减枝区别
   CART减枝的方法为交叉验证，需要测试数据集，不需要事先确定好T0,T1,...,Tn由训练数据集生成。
   ID3，C4.5需要事先确定α值的大小，但是不需要测试数据。
   两种减枝方法可以互用。