@TOC

简介

Hello！
非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～
 
ଘ(੭ˊᵕˋ)੭
昵称：海轰
标签：程序猿｜C++选手｜学生
简介：因C语言结识编程，随后转入计算机专业，获得过国家奖学金，有幸在竞赛中拿过一些国奖、省奖…已保研
学习经验：扎实基础 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！
 
唯有努力💪
 
本文仅记录自己感兴趣的内容

说明

作业要求：每章从课后习题中选取3道题做就可以了

答案来源：题目的解答过程来自于网络，依据个人所学进行了一些修改、总结

仅供参考

4.1

试证明对于不含冲突数据（即特征向量完全相同但标记不同）的训练集，必存在与训练集一致（即训练误差为0）的决策树。

答：使用反证法，假设不存在与训练集一致的决策树，在使用训练集进行划分时，必定会在一个节点发生无法划分当前数据集的情况，无法划分数据说明训练集中存在冲突数据，与题目中不含冲突数据相矛盾，故假设不成立，即一定存在与训练集一致的决策树。从另一个角度来看：当到达某个节点需要进行划分数据集时，因为样本中不存在冲突数据，所以一定可以对这些数据进行进一步的划分，直到样本为空或者样本中所有数据都为一类时，才会终止划分。故经过有限次划分后，一定会得到一颗与训练集完全一致（训练误差为0）的决策树。

4.2

试析使用“最小训练误差”作为决策树划分选择准则的缺陷。

答：最小训练误差可以理解为：在决策树中的模型算法期望找到针对所有训练集中具有最小错误率的一颗树，可以会造成对训练集数的过拟合现象，对于未知的数据的泛化能力较差。决策树的生成是使用贪心算法递归生成的，无法保证是全局最优树，是无法得到真正的最小化训练误差，得到的可能只是局部最优解。只有当决策树结构确定时，才可能确定其最小化训练误差。

4.3

试编程实现基于信息熵进行划分选择的决策树算法，并为表4.3中数据生成一棵决策树

答：使用python实现基于信息熵进行划分选择的决策树算法代码如下：

import pandas as pd
import numpy as np
import json

df = pd.DataFrame(pd.read_csv("西瓜数据集3.0.csv", encoding="gbk"))
df.drop(labels=["编号"], axis=1, inplace=True)  
df["好瓜"].replace(to_replace=["是", "否"], value=["好瓜", "坏瓜"], inplace=True)  
featureList = df.columns[:-1] 
featureValue = {}
for feature in featureList[:-2]:  
    featureValue[feature] = set(df[feature])  

T = {}  # 候选点集合
for feature in featureList[-2:]:  # 连续属性
    T1 = df[feature].sort_values()
    T2 = T1[:-1].reset_index(drop=True)
    T3 = T1[1:].reset_index(drop=True)  
    T[feature] = (T2+T3)/2

def Ent(D):  
    frequency = D["好瓜"].value_counts()/len(D["好瓜"])
    return -sum(pk*np.log2(pk) for pk in frequency)  
    

def split_discrete(D, feature):  
    splitD = []
     for Dv in D.groupby(by=feature, axis=0):
        splitD.append(Dv)
    return splitD

def split_continues(D, feature, splitValue):
    splitD = []
    splitD.append(D[D[feature] <= splitValue])
    splitD.append(D[D[feature] > splitValue])
    return splitD

def Gain_discrete(D, feature):
    gain = Ent(D) - sum(len(Dv[1])/len(D)*Ent(Dv[1]) for Dv in split_discrete(D, feature))
    return gain

def Gain_continues(D, feature):
    _max = 0
    splitValue = 0
    for t in T[feature].values:  # 尝试各个划分点，并取可以使增益最大的划分点
        temp = Ent(D) - sum(len(Dv)/len(D)*Ent(Dv) for Dv in split_continues(D, feature, t))
        if _max < temp:
            _max = temp
            splitValue = t
    return _max, splitValue

def chooseBestFeature(D, A):
    informationGain = {}
    for feature in A:
        if feature in ["密度", "含糖率"]:  # 密度和含糖率是连续属性
            ig, splitValue = Gain_continues(D, feature)
            informationGain[feature+"<=%.3f"%splitValue] = ig
        else:
            informationGain[feature] = Gain_discrete(D, feature)    
    informationGain = sorted(informationGain.items(), key=lambda ig:ig[1], reverse=True)
    return informationGain[0][0]


def countMajority(D):  # mode()求出现次数最多的元素，iloc取得对应的类：好瓜或坏瓜（是或否）
    return D["好瓜"].mode().iloc[0]

def treeGenerate(D, A):
    if len(split_discrete(D, "好瓜")) == 1: 
        return D["好瓜"].iloc[0]
    if len(A) == 0 or len(split_discrete(D, A.tolist())) == 1:
        return countMajority(D)
    bestFeature = chooseBestFeature(D, A)
    if "<=" in bestFeature:  # 连续属性
        bestFeature, splitValue = bestFeature.split("<=")
        myTree = {bestFeature+"<="+splitValue:{}}
        [D0, D1] = split_continues(D, bestFeature, float(splitValue))
        A0 = pd.Index(A)
        A1 = pd.Index(A)
        myTree[bestFeature+"<="+splitValue]["yes"] = treeGenerate(D0, A0)
        myTree[bestFeature+"<="+splitValue]["no"] = treeGenerate(D1, A1)
    else: 
        myTree = {bestFeature:{}}
        for bestFeatureValue, Dv in split_discrete(D, bestFeature):
            if len(Dv) == 0:
                return countMajority(D)
            else:
                A2 = pd.Index(A)
                A2 = A2.drop([bestFeature])
                Dv = Dv.drop(labels=[bestFeature], axis=1)
                myTree[bestFeature][bestFeatureValue] = treeGenerate(Dv, A2)
    return myTree

if __name__ == "__main__":
    myTree = treeGenerate(df, featureList)
    myTree = json.dumps(myTree, indent=2, ensure_ascii=False, separators=(',', ':'))
print(myTree)

实验结果如下图：

结语

文章仅作为个人学习笔记记录，记录从0到1的一个过程

希望对您有一点点帮助，如有错误欢迎小伙伴指正