决策树-ID3实例
参考书籍：
《机器学习》周志华，第1版
《统计学习方法》李航，第2版
用来记录自己对书中知识的理解，加强自己的理解和记忆，同时提出自己迷惑不解的地方，提高自己编辑的表达能力。

代码参考博客：https://blog.csdn.net/weixin_43084928/article/details/82455326?
https://blog.csdn.net/laojie4124/article/details/92018932?

数据集：

ID3是通过计算信息增益来选择分类特征
后面会在此基础上通过graphviz模块打印输出决策树，并增加C4.5算法，预剪枝和后剪枝
结合数据集，具体的算法流程：
1）计算分类的信息熵：buy

# 计算分类特征的信息熵，数据集是最后一列，买或者不买，并返回信息熵
def calEnt(dataset):
    # 获取数据集的维度，有多少行数据
    n = dataset.shape[0]
	 # 每一列有哪些数据，数量是多少
    columns_set = dataset.iloc[:,-1].value_counts()
    # 每种数据占总数量的比重
    p = columns_set / n 
    # print('p:',p)
    # 信息熵
    ent = (-p*np.log2(p)).sum()
    return ent

2）计算4个特征的信息熵：income，credit_rating，age，student，这个完全根据数学计算步骤来来处理的。
计算信息增益最高的特征，并返回，以便选择节点：

def best_split(dataset):
    base_ent = calEnt(dataset)
    best_Gain = 0                                         #计算分类信息熵
    axis = 0                                             #初始化标签列，最优列
    gain = []
    for i in range(1,dataset.shape[1]-1):
        levels = dataset.iloc[:,i].value_counts()        #获取每一行的数据
        dict_levels = dict(levels)
        # print('levels:\n',dict_levels)
        ents = 0                                           #初始化信息熵
        for j in dict_levels.keys():
            # print('j:',j)
            child_set = dataset[dataset.iloc[:,i] == j]
            child_ent = calEnt(child_set)
            ents += (child_set.shape[0]/dataset.shape[0])*child_ent
            # print('ents:',ents)
        infogain = base_ent - ents
        gain.append(infogain)
        # print('infogain:',infogain)
        if infogain > best_Gain:
            best_Gain = infogain
            axis = i
    return axis

3）创建决策树，用的是字典结构

def get_feature_2(dataset):
    # 返回特征值列表
    feature_list = list(dataset.columns)
    return feature_list
def sub_Split(dataset,axis,value):
    # 根据信息增益最高坐标返回特征值
    col = dataset.columns[axis]
    # drop()删除某一行或列，axis = 0 表示行，axis = 1表示列
    # 获取value值所在行，然后将col列删除
    redataset = dataset.loc[dataset[col]==value,:].drop(col,axis=1)
    return redataset
def create_tree(dataset):
    # 获得特征列表
    feature_list = get_feature_2(dataset)
    # print(feature_list)
    # 获得分类值，例如yes和no
    class_list = dataset.iloc[:,-1].value_counts()
    # 判断目前这个数据集是否都是一类，或者数据集只有一个特征
    if class_list[0]==dataset.shape[0] or dataset.shape[1] == 1:
        # print('class_list的索引：',class_list.index[0])
        #如果是，返回类标签
        return class_list.index[0]
    # 第一次寻找所有特征中信息增益最高的那个特征的坐标，1-4中任意一个，第一个是RID，最后一个分类标签
    best_ent_axis = best_split(dataset)
    best_ent_feature = feature_list[best_ent_axis]
    # print(best_ent_feature)
    # 采用字典嵌套来存储树信息
    class_tree = {best_ent_feature:{}}
    # print(class_tree)
    # 从特征列表中删除信息增益最高的特征
    del feature_list[best_ent_axis]
    # print(feature_list)
    # 提取信息增益最高特征的数据
    value_list = set(dataset.iloc[:,best_ent_axis])
    # print(value_list)
    # 对每一个特征值递归建树，例如age：youth，middle_age,senior
    for value in value_list:
        class_tree[best_ent_feature][value] = create_tree(sub_Split(dataset,best_ent_axis,value))
        # print("生成的树：",class_tree)
    return class_tree

5）分类，递归调用，对训练集进行判断

# 分类判断
def classify(input_tree,labels,test_vec):
    # 获取决策树的根节点
    first_str = next(iter(input_tree))
    seconde_dict = input_tree[first_str]
    # 第一个节点所在的索引
    feature_index = labels.index(first_str)
    for key in seconde_dict.keys():
        # print('key:',key)
        # 如果测试数据的索引键值和根结点的键值一样
        if test_vec[feature_index] == key:
            # 如果子结点是一个字典，就继续分类，否则就是一个叶子结点
            if type(seconde_dict[key]) == dict :
                # 递归分类
                class_label = classify(seconde_dict[key], labels, test_vec)
            else:
                class_label = seconde_dict[key]
    return class_label

6）计算测试数据集在训练好的决策树的精度

# 测试精度
def acc_classify(train_dataset,test_dataset):
    # 根据训练数据得到决策树
    input_tree = create_tree(train_dataset)
    labels = list(train_dataset.columns)
    results = []
    for i in range(test_dataset.shape[0]):
        test_vec = train_dataset.iloc[i,:-1]
        class_label = classify(input_tree,labels,test_vec)
        results.append(class_label)
    # 在数据集增加一列predict，将预测出来的分类保存在这一列
    test_dataset['predict'] = results
    acc = (test_dataset.iloc[:,-1] == test_dataset.iloc[:,-2]).mean()
    print('测试的精度：')
    print(acc)

前面需要导入用的模块：

import csv
from sklearn.feature_extraction import DictVectorizer   #用来转换数据
from sklearn import preprocessing
import pandas as pd
import numpy as np

调用写好的函数，得到结果，由于用的训练数据和测试数据是一个，所以这个精度不准，但是整个流程是没问题的：

file_path = 'E:\\arithmetic_practice\\tree.csv'
dataset = pd.read_csv(file_path)
dataset = pd.DataFrame(dataset)
train_dataset = dataset
test_dataset = dataset
acc_classify(train_dataset, test_dataset)