---

  在《机器学习》第四章学习了决策树算法，对此很感兴趣。我决定用Python编写一个决策树生成程序，数据集就是西瓜书上的表4.1 西瓜数据集2.0

与表4.3 西瓜数据集3.0，下载链接：西瓜数据集3.0.xlsx

西瓜数据集3.0只是比西瓜数据集2.0多了两栏“密度”与“含糖率”的属性，其他属性取值一致。

关于具体的决策树算法的逻辑，则主要参考西瓜书的图4.2 决策树学习基本算法

1 载入数据

  首先要把Excel表格里面的数据集载入到程序中，对应操作在之前的博客《利用Python将录取信息Excel表格转成可视化图形》中都有介绍，在此不再赘述，实现代码如下：
首先导入必要的包：

#coding=utf8
import xlrd
import numpy as np

# 数据集路径
DATASET_PATH = 'C:/Users/Desktop/西瓜数据集.xlsx'
# 载入数据集文件
DataFile = xlrd.open_workbook(DATASET_PATH)
# 载入第一个表格
table = DataFile.sheets()[0]

# 将表格信息转化为字典
def Read_Excel(excel):
    for rows in range(1, excel.nrows):
        dict_ = {'编号':'', '色泽':'', '根蒂':'', '敲声':'', '纹理':'',\
                 '脐部':'', '触感':'', '密度':'', '含糖率':'', '好瓜':''}
        dict_['编号'] = table.cell_value(rows, 0)
        dict_['色泽'] = table.cell_value(rows, 1)
        dict_['根蒂'] = table.cell_value(rows, 2)
        dict_['敲声'] = table.cell_value(rows, 3)
        dict_['纹理'] = table.cell_value(rows, 4)
        dict_['脐部'] = table.cell_value(rows, 5)
        dict_['触感'] = table.cell_value(rows, 6)
        dict_['密度'] = table.cell_value(rows, 7)
        dict_['含糖率'] = table.cell_value(rows, 8)
        dict_['好瓜'] = table.cell_value(rows, 9)
        dataset.append(dict_)
    return dataset

print(Read_Excel(table))

结果是一个table，其中又包含着dict

然后我们再建立一个dict用以表示属性

attributesdict = {'色泽':['青绿', '乌黑', '浅白'], '根蒂':['蜷缩', '稍蜷', '硬挺'], '敲声':['浊响', '沉闷', '清脆'],\
                  '纹理':['清晰', '稍糊', '模糊'], '脐部':['凹陷', '稍凹', '平坦'], '触感':['硬滑', '软粘']}

2 判断是否需要选择最优划分属性

  根据上述逻辑图，我们知道在第8步-选择最优划分属性之前需要先对数据进行筛查。即判断数据集中样本是否全属于同一类别，以及属性集是否为空或样本在属性上的取值是否都相同。若上述条件有一个满足，那后续就没有进行属性划分的必要了。这里逻辑比较清晰。

# 生成结点
DecisionTree = {'node':''}
SIMILARMARK_NUM = 0 # 属于同一类别（标签）的样本的数量
SIMILARCOLOR_NUM = 0 # 属于同一颜色的样本的数量
SIMILARROOT_NUM = 0 # 属于同一根蒂的样本的数量
SIMILARVOICE_NUM = 0 # 属于同一敲声的样本的数量
SIMILARTEXTURE_NUM = 0 # 属于同一纹理的样本的数量
SIMILARUMBILICAL_NUM = 0 # 属于同一脐部的样本的数量
SIMILARTOUCH_NUM = 0 # 属于同一触感的样本的数量
SIMILARDENSITY_NUM = 0 # 属于同一密度的样本的数量
SIMILARSUGAR_NUM = 0 # 属于同一含糖率的样本的数量
# 若只有一个数据，则直接标记为叶结点
if len(data) == 1:
    if data[0]['好瓜'] == '是':
        return '好瓜'
    else:
        return '坏瓜'
for i in range(len(data)-1):
    # 若所有样本属于同一类别，则将结点标记为叶结点
    if data[i]['好瓜'] == data[i+1]['好瓜']:
        SIMILARMARK_NUM += 1
        if SIMILARMARK_NUM == len(data)-1:
            if data[i]['好瓜'] == '是':
                return '好瓜'
            else:
                return '坏瓜'
    if '色泽' in list(data[i].keys()) and data[i]['色泽'] == data[i+1]['色泽']:
        SIMILARCOLOR_NUM += 1
    if '根蒂' in list(data[i].keys()) and data[i]['根蒂'] == data[i+1]['根蒂']:
        SIMILARROOT_NUM += 1
    if '敲声' in list(data[i].keys()) and data[i]['敲声'] == data[i+1]['敲声']:
        SIMILARVOICE_NUM += 1
    if '纹理' in list(data[i].keys()) and data[i]['纹理'] == data[i+1]['纹理']:
        SIMILARTEXTURE_NUM += 1
    if '脐部' in list(data[i].keys()) and data[i]['脐部'] == data[i+1]['脐部']:
        SIMILARUMBILICAL_NUM += 1
    if '触感' in list(data[i].keys()) and data[i]['触感'] == data[i+1]['触感']:
        SIMILARTOUCH_NUM += 1
    if '密度' in list(data[i].keys()) and data[i]['密度'] == data[i+1]['密度']:
        SIMILARDENSITY_NUM += 1
    if '含糖率' in list(data[i].keys()) and data[i]['含糖率'] == data[i+1]['含糖率']:
        SIMILARSUGAR_NUM += 1
# 若样本在所有属性上取值相同，则将结点标记为叶结点
if SIMILARCOLOR_NUM == SIMILARROOT_NUM == SIMILARVOICE_NUM == SIMILARTEXTURE_NUM ==\
   SIMILARUMBILICAL_NUM == SIMILARTOUCH_NUM == SIMILARDENSITY_NUM == SIMILARSUGAR_NUM == len(data)-1:
    if goodmelon_num < badmelon_num:
        return '坏瓜'
    else:
        return '好瓜'

3 选择最优划分属性

  这个部分是重点但不是难点，我在此选择的划分依据是信息增益。根据上述信息增益的计算公式
$$Ent(D)=-\sum _{k=1}^{|\gamma |}{p}_{k}lo{g}_2{p}_k$$

$$Gain(D,a)=Ent(D)-\sum _{\nu =1}^V\frac{|D^{\nu }|}{|D|}Ent(D^{\nu })$$

我们可以构造两个函数，分别用于计算信息熵与信息增益

# 计算信息熵
def Calculate_Entropy(GOODMELON_NUM, BADMELON_NUM, TOTAL_NUM):
    if TOTAL_NUM != 0:
        GOODMELON_RATIO = GOODMELON_NUM / TOTAL_NUM
        BADMELON_RATIO = BADMELON_NUM / TOTAL_NUM
        if GOODMELON_RATIO == 0:
            Ent = -(BADMELON_RATIO*np.log2(BADMELON_RATIO))
        if BADMELON_RATIO == 0:
            Ent = -(GOODMELON_RATIO*np.log2(GOODMELON_RATIO))
        if GOODMELON_RATIO != 0 and BADMELON_RATIO != 0:
            Ent = -(GOODMELON_RATIO*np.log2(GOODMELON_RATIO) + BADMELON_RATIO*np.log2(BADMELON_RATIO))
    else:
        Ent = 0
    return Ent

Calculate_Entropy()函数接收好瓜与坏瓜的数量和西瓜的总数，返回信息熵。

  对于信息增益的计算需要注意，之前谈到当遇到连续属性时，我们不能直接根据连续属性的可取值来对结点进行划分。我们应该先将连续属性的取值从小到大进行排序，然后分别计算两个相邻取值的中值。最后再计算分别取这些中值为划分点时的最大信息增益。
T a = { a i + a i + 1 2 ∣ 1 ≤ i ≤ n − 1 } T_a=\{\frac{a^i+a^{i+1}}{2}|1≤i≤n-1\} Ta​={2ai+ai+1​∣1≤i≤n−1}

$$Gain(D,a)=ma{x}_{t\in T_a}Gain(D,a,t)$$

= m a x t ∈ T a E n t ( D ) − ∑ λ ∈ { − , + } ∣ D t λ ∣ ∣ D ∣ E n t ( D t λ ) =max_{t\in T_a}Ent(D)-\sum_{\lambda\in \{-,+\}}\frac{|D_t^{\lambda}|}{|D|}Ent(D_t^{\lambda}) =maxt∈Ta​​Ent(D)−λ∈{−,+}∑​∣D∣∣Dtλ​∣​Ent(Dtλ​)

  我们首先构造一个函数对连续取值进行排序并计算其中值，其中使用冒泡排序算法进行排序。

# 对数据进行排序并计算其中值
def Get_MidValue(data, class_name):
    sort = []
    midvalue = []
    # 取出所有密度值
    for i in range(len(data)):
        sort.append(data[i][class_name])
    # 冒泡排序
    for x in range(len(sort)):
        for y in range(x, len(sort)):
            if sort[x] > sort[y]:
                temp = sort[x]
                sort[x] = sort[y]
                sort[y] = temp
    # 求中间值
    for i in range(len(sort)-1):
        midvalue.append(round(((sort[i]+sort[i+1])/2), 3))
    return midvalue

这个Get_MidValue()函数接收西瓜数据集与我们需要进行排序的连续属性的名称。然后返回中值列表。

  现在有了信息熵计算函数与中值计算函数，我们就可以编写信息增益计算函数了，其中对于连续属性与离散属性有着不同的计算方法。
  首先对于连续属性的计算来说，我们先获取中值列表，也就是候选划分点集合。然后对于该集合中每一个划分点依次统计数据集中某一属性的每一个取值中好瓜、坏瓜的数量以及总数等信息，随后就是计算信息熵与信息增益。最后选出信息增益最大的那个值与其对应划分点。

# 若属性为连续取值
if class_name == '密度' or class_name == '含糖率':
    Gains = []
    # 获取所有候选划分点
    midvalues = Get_MidValue(data, class_name)
    for midvalue in midvalues:
        GOODMELON_NUM = 0
        BADMELON_NUM = 0
        TOTAL_NUM = 0
        CLASS1_GOODMELON_NUM = 0
        CLASS1_BADMELON_NUM = 0
        CLASS1_NUM = 0
        CLASS2_GOODMELON_NUM = 0
        CLASS2_BADMELON_NUM = 0
        CLASS2_NUM = 0
        for i in data:
            TOTAL_NUM += 1
            if i[class_name] > midvalue:
                CLASS1_NUM += 1
                if i['好瓜'] == '是':
                    GOODMELON_NUM += 1
                    CLASS1_GOODMELON_NUM += 1
                else:
                    BADMELON_NUM += 1
                    CLASS1_BADMELON_NUM += 1
            else:
                CLASS2_NUM += 1
                if i['好瓜'] == '是':
                    GOODMELON_NUM += 1
                    CLASS2_GOODMELON_NUM += 1
                else:
                    BADMELON_NUM += 1
                    CLASS2_BADMELON_NUM += 1
        # 计算总信息熵
        GOODMELON_RATIO = GOODMELON_NUM / TOTAL_NUM
        BADMELON_RATIO = BADMELON_NUM / TOTAL_NUM
        if GOODMELON_RATIO == 0:
            Ent_D = -(BADMELON_RATIO * np.log2(BADMELON_RATIO))
        if BADMELON_RATIO == 0:
            Ent_D = -(GOODMELON_RATIO * np.log2(GOODMELON_RATIO))
        if GOODMELON_RATIO != 0 and BADMELON_RATIO != 0:
            Ent_D = -(GOODMELON_RATIO * np.log2(GOODMELON_RATIO) + BADMELON_RATIO*np.log2(BADMELON_RATIO))
        # 计算属性为第一种取值的信息熵
        Ent_D1 = Calculate_Entropy(CLASS1_GOODMELON_NUM, CLASS1_BADMELON_NUM, CLASS1_NUM)
        # 计算第二种取值的信息熵
        Ent_D2 = Calculate_Entropy(CLASS2_GOODMELON_NUM, CLASS2_BADMELON_NUM, CLASS2_NUM)
        # 计算信息增益
        Gain = Ent_D-((CLASS1_NUM/TOTAL_NUM) * Ent_D1 + (CLASS2_NUM/TOTAL_NUM) * Ent_D2)
        # 记录信息增益
        Gains.append(round(Gain, 3))
    temp = 0
    for i in range(len(Gains)):
        if Gains[i] > temp:
            temp = Gains[i]
            mark = i
    return GOODMELON_NUM, BADMELON_NUM, Gains[mark], midvalues[mark]

  离散属性信息增益的计算相比连续属性更为简单，依次对每个离散取值进行信息熵计算，最后再计算信息增益即可。

# 若属性为离散取值
else:
    if class_name in list(attributesdict.keys()):
        GOODMELON_NUM = 0
        BADMELON_NUM = 0
        TOTAL_NUM = 0
        CLASS1_GOODMELON_NUM = 0
        CLASS1_BADMELON_NUM = 0
        CLASS1_NUM = 0
        CLASS2_GOODMELON_NUM = 0
        CLASS2_BADMELON_NUM = 0
        CLASS2_NUM = 0
        CLASS3_GOODMELON_NUM = 0
        CLASS3_BADMELON_NUM = 0
        CLASS3_NUM = 0
        for i in data:
            TOTAL_NUM += 1
            if i[class_name] == attributesdict[class_name][0]:
                CLASS1_NUM += 1
                if i['好瓜'] == '是':
                    GOODMELON_NUM += 1
                    CLASS1_GOODMELON_NUM += 1
                else:
                    BADMELON_NUM += 1
                    CLASS1_BADMELON_NUM += 1
            elif i[class_name] == attributesdict[class_name][1]:
                CLASS2_NUM += 1
                if i['好瓜'] == '是':
                    GOODMELON_NUM += 1
                    CLASS2_GOODMELON_NUM += 1
                else:
                    BADMELON_NUM += 1
                    CLASS2_BADMELON_NUM += 1
            elif len(attributesdict[class_name]) == 3:
                if i[class_name] == attributesdict[class_name][2]:
                    CLASS3_NUM += 1
                    if i['好瓜'] == '是':
                        GOODMELON_NUM += 1
                        CLASS3_GOODMELON_NUM += 1
                    else:
                        BADMELON_NUM += 1
                        CLASS3_BADMELON_NUM += 1
        # 计算总信息熵
        GOODMELON_RATIO = GOODMELON_NUM / TOTAL_NUM
        BADMELON_RATIO = BADMELON_NUM / TOTAL_NUM
        if GOODMELON_RATIO == 0 and BADMELON_RATIO == 0:
            return GOODMELON_NUM, BADMELON_NUM, 0
        elif BADMELON_RATIO == 0 and GOODMELON_RATIO != 0:
            Ent_D = -(GOODMELON_RATIO*np.log2(GOODMELON_RATIO))
        elif GOODMELON_RATIO == 0 and BADMELON_RATIO != 0:
            Ent_D = -(BADMELON_RATIO*np.log2(BADMELON_RATIO))
        else:
            Ent_D = -(GOODMELON_RATIO*np.log2(GOODMELON_RATIO) + BADMELON_RATIO*np.log2(BADMELON_RATIO))
        # 计算属性为第一种取值的信息熵
        Ent_D1 = Calculate_Entropy(CLASS1_GOODMELON_NUM, CLASS1_BADMELON_NUM, CLASS1_NUM)
        # 计算第二种取值的信息熵
        Ent_D2 = Calculate_Entropy(CLASS2_GOODMELON_NUM, CLASS2_BADMELON_NUM, CLASS2_NUM)
        # 计算第三种取值的信息熵
        Ent_D3 = Calculate_Entropy(CLASS3_GOODMELON_NUM, CLASS3_BADMELON_NUM, CLASS3_NUM)
        # 计算信息增益
        Gain = Ent_D - ((CLASS1_NUM/TOTAL_NUM)*Ent_D1+(CLASS2_NUM/TOTAL_NUM)*Ent_D2+(CLASS3_NUM/TOTAL_NUM)*Ent_D3)
        return GOODMELON_NUM, BADMELON_NUM, round(Gain, 3)

  有了针对单个属性的信息增益计算函数之后，我们就可以对属性集合中所有属性都计算信息增益，然后取其中增益最大的那个属性作为最优划分属性

# 选择最优划分属性
InformationGains = {}
for attribute in list(new_attributes_dict.keys()):
    InformationGains[attribute] = Calculate_InformationGain(data, attribute)
temp = 0
# 找到信息增益最大的那个属性
for i in list(InformationGains.keys()):
    if InformationGains[i][2] > temp:
        temp = InformationGains[i][2]
        best_att = i

4 枝繁叶茂

  这里虽然不是重点，但对我来说是难点。这几天主要的精力都花在这个部分的bug的修改上面。
  基于上述，我们已经获取到了最优划分属性。接下来就是对该属性进行展开，即对该属性的每一个取值继续划分最优划分属性，不断“长出新枝桠”。

  首先我们需要新建一个空“分枝”，即最优划分属性。然后再决定该分枝是分枝结点还是叶结点，即需不需要再进一步计算最优划分属性。而对于连续属性来说，我们需要先用二分法对其进行再赋值，使其取值都是"0"、“1”

# 二分法更新连续值属性的取值
if best_att == '密度' or best_att == '含糖率':
    for i in range(len(data)):
        if data[i][best_att] > InformationGains[best_att][3]:
            data[i][best_att] = '0'
        else:
            data[i][best_att] = '1'
    # 构造新的分枝
    for value in new_attributes_dict[best_att]:
        if value == '0':
            value = '大于' + str(InformationGains[best_att][3])
        else:
            value = '小于' + str(InformationGains[best_att][3])
        DecisionTree[best_att][best_att+value] = ''
# 离散取值变量只需要新建分枝
else:
    for value in new_attributes_dict[best_att]:
        DecisionTree[best_att][best_att+value] = ''

  新建空分枝后，我们需要对该属性下的每一个取值进行展开。不过在展开之前，我们需要把数据集中在该属性上取这个特定值的那部分数据拎出来传递给下一次计算，而不能将完整的数据集传下去

# 获取属性的可能取值
for value in list(DecisionTree[best_att].keys()):
    value = value.replace(best_att, '')
    # 取出在该属性下的特定取值的数据
    new_data = []
    for item in data:
        # 连续属性
        if best_att == '密度' or best_att == '含糖率':
            if (value == '大于' + str(InformationGains[best_att][3]) and item[best_att] == '0') or\
            value == '小于' + str(InformationGains[best_att][3]) and item[best_att] == '1':
                new_data.append(item)
        # 离散属性
        elif item[best_att] == value:
            new_data.append(item)
    # 若样本在某可能取值下为空，则标记为叶结点，其类别为D中样本最多的类
    if new_data == []:
        if goodmelon_num < badmelon_num:
            DecisionTree[best_att][best_att+value] = '坏瓜'
        else:
            DecisionTree[best_att][best_att+value] = '好瓜'
    # 数据中含有该属性的可能取值，即对该取值进行展开
    else:
        if best_att in list(new_attributes_dict.keys()):
            new_attributes_dict.pop(best_att)
        # 若所有属性都已划分
        if new_attributes_dict == {}:
            if goodmelon_num < badmelon_num:
                DecisionTree[best_att][best_att+value] = '坏瓜'
            else:
                DecisionTree[best_att][best_att+value] = '好瓜'
        # 以符合属性取值的新数据与新的属性表构造分枝
        DecisionTree[best_att][best_att+value] = TreeGenerate(8, 9, new_data, new_attributes_dict)
        # 重新补充属性，防止后续for循环缺失属性
        if best_att == '色泽':
            new_attributes_dict['色泽'] = ['青绿', '乌黑', '浅白']
        if best_att == '根蒂':
            new_attributes_dict['根蒂'] = ['蜷缩', '稍蜷', '硬挺']
        if best_att == '敲声':
            new_attributes_dict['敲声'] = ['浊响', '沉闷', '清脆']
        if best_att == '纹理':
            new_attributes_dict['纹理'] = ['清晰', '稍糊', '模糊']
        if best_att == '脐部':
            new_attributes_dict['脐部'] = ['凹陷', '稍凹', '平坦']
        if best_att == '触感':
            new_attributes_dict['触感'] = ['硬滑', '软粘']
return DecisionTree[best_att]

  值得注意的是，每次循环都要将之前滤除掉最优划分属性的属性集合再次给它添加上去。因为上层属性当中每个新的取值都应该还可以选取到其他属性作为最优划分属性，否则某一根树枝中滤除掉的属性在树干的其他树枝中也不可选择。

5 高耸入云

  至此，我们的决策树生成程序就完成了，完整代码如下

#coding=utf8
import xlrd
import numpy as np

# 数据集路径
DATASET_PATH = 'C:/Users/Desktop/西瓜数据集.xlsx'
# 载入数据集文件
DataFile = xlrd.open_workbook(DATASET_PATH)
# 载入第一个表格
table = DataFile.sheets()[0]

dataset = []
# 属性和其离散取值数量（连续属性用二分法进行离散取值）
attributesdict = {'色泽':['青绿', '乌黑', '浅白'], '根蒂':['蜷缩', '稍蜷', '硬挺'], '敲声':['浊响', '沉闷', '清脆'],\
                  '纹理':['清晰', '稍糊', '模糊'], '脐部':['凹陷', '稍凹', '平坦'], '触感':['硬滑', '软粘']}

# 将表格信息转化为字典
def Read_Excel(excel):
    for rows in range(1, excel.nrows):
        dict_ = {'编号':'', '色泽':'', '根蒂':'', '敲声':'', '纹理':'',\
                 '脐部':'', '触感':'', '密度':'', '含糖率':'', '好瓜':''}
        dict_['编号'] = table.cell_value(rows, 0)
        dict_['色泽'] = table.cell_value(rows, 1)
        dict_['根蒂'] = table.cell_value(rows, 2)
        dict_['敲声'] = table.cell_value(rows, 3)
        dict_['纹理'] = table.cell_value(rows, 4)
        dict_['脐部'] = table.cell_value(rows, 5)
        dict_['触感'] = table.cell_value(rows, 6)
        dict_['密度'] = table.cell_value(rows, 7)
        dict_['含糖率'] = table.cell_value(rows, 8)
        dict_['好瓜'] = table.cell_value(rows, 9)
        dataset.append(dict_)
    return dataset

# 对数据进行排序并计算其中值
def Get_MidValue(data, class_name):
    sort = []
    midvalue = []
    # 取出所有密度值
    for i in range(len(data)):
        sort.append(data[i][class_name])
    # 冒泡排序
    for x in range(len(sort)):
        for y in range(x, len(sort)):
            if sort[x] > sort[y]:
                temp = sort[x]
                sort[x] = sort[y]
                sort[y] = temp
    # 求中间值
    for i in range(len(sort)-1):
        midvalue.append(round(((sort[i]+sort[i+1])/2), 3))
    return midvalue


# 计算信息熵
def Calculate_Entropy(GOODMELON_NUM, BADMELON_NUM, TOTAL_NUM):
    if TOTAL_NUM != 0:
        GOODMELON_RATIO = GOODMELON_NUM / TOTAL_NUM
        BADMELON_RATIO = BADMELON_NUM / TOTAL_NUM
        if GOODMELON_RATIO == 0:
            Ent = -(BADMELON_RATIO*np.log2(BADMELON_RATIO))
        if BADMELON_RATIO == 0:
            Ent = -(GOODMELON_RATIO*np.log2(GOODMELON_RATIO))
        if GOODMELON_RATIO != 0 and BADMELON_RATIO != 0:
            Ent = -(GOODMELON_RATIO*np.log2(GOODMELON_RATIO) + BADMELON_RATIO*np.log2(BADMELON_RATIO))
    else:
        Ent = 0
    return Ent


# 计算信息增益，输入数据与希望计算信息增益的属性名称
def Calculate_InformationGain(data, class_name):
    # 若属性为连续取值
    if class_name == '密度' or class_name == '含糖率':
        Gains = []
        # 获取所有候选划分点
        midvalues = Get_MidValue(data, class_name)
        for midvalue in midvalues:
            GOODMELON_NUM = 0
            BADMELON_NUM = 0
            TOTAL_NUM = 0
            CLASS1_GOODMELON_NUM = 0
            CLASS1_BADMELON_NUM = 0
            CLASS1_NUM = 0
            CLASS2_GOODMELON_NUM = 0
            CLASS2_BADMELON_NUM = 0
            CLASS2_NUM = 0
            for i in data:
                TOTAL_NUM += 1
                if i[class_name] > midvalue:
                    CLASS1_NUM += 1
                    if i['好瓜'] == '是':
                        GOODMELON_NUM += 1
                        CLASS1_GOODMELON_NUM += 1
                    else:
                        BADMELON_NUM += 1
                        CLASS1_BADMELON_NUM += 1
                else:
                    CLASS2_NUM += 1
                    if i['好瓜'] == '是':
                        GOODMELON_NUM += 1
                        CLASS2_GOODMELON_NUM += 1
                    else:
                        BADMELON_NUM += 1
                        CLASS2_BADMELON_NUM += 1
            # 计算总信息熵
            GOODMELON_RATIO = GOODMELON_NUM / TOTAL_NUM
            BADMELON_RATIO = BADMELON_NUM / TOTAL_NUM
            if GOODMELON_RATIO == 0:
                Ent_D = -(BADMELON_RATIO * np.log2(BADMELON_RATIO))
            if BADMELON_RATIO == 0:
                Ent_D = -(GOODMELON_RATIO * np.log2(GOODMELON_RATIO))
            if GOODMELON_RATIO != 0 and BADMELON_RATIO != 0:
                Ent_D = -(GOODMELON_RATIO * np.log2(GOODMELON_RATIO) + BADMELON_RATIO*np.log2(BADMELON_RATIO))
            # 计算属性为第一种取值的信息熵
            Ent_D1 = Calculate_Entropy(CLASS1_GOODMELON_NUM, CLASS1_BADMELON_NUM, CLASS1_NUM)
            # 计算第二种取值的信息熵
            Ent_D2 = Calculate_Entropy(CLASS2_GOODMELON_NUM, CLASS2_BADMELON_NUM, CLASS2_NUM)
            # 计算信息增益
            Gain = Ent_D-((CLASS1_NUM/TOTAL_NUM) * Ent_D1 + (CLASS2_NUM/TOTAL_NUM) * Ent_D2)
            # 记录信息增益
            Gains.append(round(Gain, 3))
        temp = 0
        for i in range(len(Gains)):
            if Gains[i] > temp:
                temp = Gains[i]
                mark = i
        return GOODMELON_NUM, BADMELON_NUM, Gains[mark], midvalues[mark]
    # 若属性为离散取值
    else:
        if class_name in list(attributesdict.keys()):
            GOODMELON_NUM = 0
            BADMELON_NUM = 0
            TOTAL_NUM = 0
            CLASS1_GOODMELON_NUM = 0
            CLASS1_BADMELON_NUM = 0
            CLASS1_NUM = 0
            CLASS2_GOODMELON_NUM = 0
            CLASS2_BADMELON_NUM = 0
            CLASS2_NUM = 0
            CLASS3_GOODMELON_NUM = 0
            CLASS3_BADMELON_NUM = 0
            CLASS3_NUM = 0
            for i in data:
                TOTAL_NUM += 1
                if i[class_name] == attributesdict[class_name][0]:
                    CLASS1_NUM += 1
                    if i['好瓜'] == '是':
                        GOODMELON_NUM += 1
                        CLASS1_GOODMELON_NUM += 1
                    else:
                        BADMELON_NUM += 1
                        CLASS1_BADMELON_NUM += 1
                elif i[class_name] == attributesdict[class_name][1]:
                    CLASS2_NUM += 1
                    if i['好瓜'] == '是':
                        GOODMELON_NUM += 1
                        CLASS2_GOODMELON_NUM += 1
                    else:
                        BADMELON_NUM += 1
                        CLASS2_BADMELON_NUM += 1
                elif len(attributesdict[class_name]) == 3:
                    if i[class_name] == attributesdict[class_name][2]:
                        CLASS3_NUM += 1
                        if i['好瓜'] == '是':
                            GOODMELON_NUM += 1
                            CLASS3_GOODMELON_NUM += 1
                        else:
                            BADMELON_NUM += 1
                            CLASS3_BADMELON_NUM += 1
            # 计算总信息熵
            GOODMELON_RATIO = GOODMELON_NUM / TOTAL_NUM
            BADMELON_RATIO = BADMELON_NUM / TOTAL_NUM
            if GOODMELON_RATIO == 0 and BADMELON_RATIO == 0:
                return GOODMELON_NUM, BADMELON_NUM, 0
            elif BADMELON_RATIO == 0 and GOODMELON_RATIO != 0:
                Ent_D = -(GOODMELON_RATIO*np.log2(GOODMELON_RATIO))
            elif GOODMELON_RATIO == 0 and BADMELON_RATIO != 0:
                Ent_D = -(BADMELON_RATIO*np.log2(BADMELON_RATIO))
            else:
                Ent_D = -(GOODMELON_RATIO*np.log2(GOODMELON_RATIO) + BADMELON_RATIO*np.log2(BADMELON_RATIO))
            # 计算属性为第一种取值的信息熵
            Ent_D1 = Calculate_Entropy(CLASS1_GOODMELON_NUM, CLASS1_BADMELON_NUM, CLASS1_NUM)
            # 计算第二种取值的信息熵
            Ent_D2 = Calculate_Entropy(CLASS2_GOODMELON_NUM, CLASS2_BADMELON_NUM, CLASS2_NUM)
            # 计算第三种取值的信息熵
            Ent_D3 = Calculate_Entropy(CLASS3_GOODMELON_NUM, CLASS3_BADMELON_NUM, CLASS3_NUM)
            # 计算信息增益
            Gain = Ent_D - ((CLASS1_NUM/TOTAL_NUM)*Ent_D1+(CLASS2_NUM/TOTAL_NUM)*Ent_D2+(CLASS3_NUM/TOTAL_NUM)*Ent_D3)
            return GOODMELON_NUM, BADMELON_NUM, round(Gain, 3)


# 生成决策树
def TreeGenerate(goodmelon_num, badmelon_num, data, attributes_dict):
    new_attributes_dict = attributes_dict
    # 生成结点
    DecisionTree = {'node':''}
    SIMILARMARK_NUM = 0 # 属于同一类别（标签）的样本的数量
    SIMILARCOLOR_NUM = 0 # 属于同一颜色的样本的数量
    SIMILARROOT_NUM = 0 # 属于同一根蒂的样本的数量
    SIMILARVOICE_NUM = 0 # 属于同一敲声的样本的数量
    SIMILARTEXTURE_NUM = 0 # 属于同一纹理的样本的数量
    SIMILARUMBILICAL_NUM = 0 # 属于同一脐部的样本的数量
    SIMILARTOUCH_NUM = 0 # 属于同一触感的样本的数量
    SIMILARDENSITY_NUM = 0 # 属于同一密度的样本的数量
    SIMILARSUGAR_NUM = 0 # 属于同一含糖率的样本的数量
    # 若只有一个数据，则直接标记为叶结点
    if len(data) == 1:
        if data[0]['好瓜'] == '是':
            return '好瓜'
        else:
            return '坏瓜'
    for i in range(len(data)-1):
        # 若所有样本属于同一类别，则将结点标记为叶结点
        if data[i]['好瓜'] == data[i+1]['好瓜']:
            SIMILARMARK_NUM += 1
            if SIMILARMARK_NUM == len(data)-1:
                if data[i]['好瓜'] == '是':
                    return '好瓜'
                else:
                    return '坏瓜'
        if '色泽' in list(data[i].keys()) and data[i]['色泽'] == data[i+1]['色泽']:
            SIMILARCOLOR_NUM += 1
        if '根蒂' in list(data[i].keys()) and data[i]['根蒂'] == data[i+1]['根蒂']:
            SIMILARROOT_NUM += 1
        if '敲声' in list(data[i].keys()) and data[i]['敲声'] == data[i+1]['敲声']:
            SIMILARVOICE_NUM += 1
        if '纹理' in list(data[i].keys()) and data[i]['纹理'] == data[i+1]['纹理']:
            SIMILARTEXTURE_NUM += 1
        if '脐部' in list(data[i].keys()) and data[i]['脐部'] == data[i+1]['脐部']:
            SIMILARUMBILICAL_NUM += 1
        if '触感' in list(data[i].keys()) and data[i]['触感'] == data[i+1]['触感']:
            SIMILARTOUCH_NUM += 1
        if '密度' in list(data[i].keys()) and data[i]['密度'] == data[i+1]['密度']:
            SIMILARDENSITY_NUM += 1
        if '含糖率' in list(data[i].keys()) and data[i]['含糖率'] == data[i+1]['含糖率']:
            SIMILARSUGAR_NUM += 1
    # 若样本在所有属性上取值相同，则将结点标记为叶结点
    if SIMILARCOLOR_NUM == SIMILARROOT_NUM == SIMILARVOICE_NUM == SIMILARTEXTURE_NUM ==\
       SIMILARUMBILICAL_NUM == SIMILARTOUCH_NUM == SIMILARDENSITY_NUM == SIMILARSUGAR_NUM == len(data)-1:
        if goodmelon_num < badmelon_num:
            return '坏瓜'
        else:
            return '好瓜'

    # 选择最优划分属性
    InformationGains = {}
    for attribute in list(new_attributes_dict.keys()):
        InformationGains[attribute] = Calculate_InformationGain(data, attribute)
    temp = 0
    # 找到信息增益最大的那个属性
    for i in list(InformationGains.keys()):
        if InformationGains[i][2] > temp:
            temp = InformationGains[i][2]
            best_att = i
    DecisionTree[best_att] = DecisionTree.pop('node')
    DecisionTree[best_att] = {}
    
    # 二分法更新连续值属性的取值
    if best_att == '密度' or best_att == '含糖率':
        for i in range(len(data)):
            if data[i][best_att] > InformationGains[best_att][3]:
                data[i][best_att] = '0'
            else:
                data[i][best_att] = '1'
        # 构造新的分枝
        for value in new_attributes_dict[best_att]:
            if value == '0':
                value = '大于' + str(InformationGains[best_att][3])
            else:
                value = '小于' + str(InformationGains[best_att][3])
            DecisionTree[best_att][best_att+value] = ''
    # 离散取值变量只需要新建分枝
    else:
        for value in new_attributes_dict[best_att]:
            DecisionTree[best_att][best_att+value] = ''
    # 获取属性的可能取值
    for value in list(DecisionTree[best_att].keys()):
        value = value.replace(best_att, '')
        # 取出在该属性下的特定取值的数据
        new_data = []
        for item in data:
            # 连续属性
            if best_att == '密度' or best_att == '含糖率':
                if (value == '大于' + str(InformationGains[best_att][3]) and item[best_att] == '0') or\
                value == '小于' + str(InformationGains[best_att][3]) and item[best_att] == '1':
                    new_data.append(item)
            # 离散属性
            elif item[best_att] == value:
                new_data.append(item)
        # 若样本在某可能取值下为空，则标记为叶结点，其类别为D中样本最多的类
        if new_data == []:
            if goodmelon_num < badmelon_num:
                DecisionTree[best_att][best_att+value] = '坏瓜'
            else:
                DecisionTree[best_att][best_att+value] = '好瓜'
        # 数据中含有该属性的可能取值，即对该取值进行展开
        else:
            if best_att in list(new_attributes_dict.keys()):
                new_attributes_dict.pop(best_att)
            # 若所有属性都已划分
            if new_attributes_dict == {}:
                if goodmelon_num < badmelon_num:
                    DecisionTree[best_att][best_att+value] = '坏瓜'
                else:
                    DecisionTree[best_att][best_att+value] = '好瓜'
            # 以符合属性取值的新数据与新的属性表构造分枝
            DecisionTree[best_att][best_att+value] = TreeGenerate(8, 9, new_data, new_attributes_dict)
            # 重新补充属性，防止后续for循环缺失属性
            if best_att == '色泽':
                new_attributes_dict['色泽'] = ['青绿', '乌黑', '浅白']
            if best_att == '根蒂':
                new_attributes_dict['根蒂'] = ['蜷缩', '稍蜷', '硬挺']
            if best_att == '敲声':
                new_attributes_dict['敲声'] = ['浊响', '沉闷', '清脆']
            if best_att == '纹理':
                new_attributes_dict['纹理'] = ['清晰', '稍糊', '模糊']
            if best_att == '脐部':
                new_attributes_dict['脐部'] = ['凹陷', '稍凹', '平坦']
            if best_att == '触感':
                new_attributes_dict['触感'] = ['硬滑', '软粘']
    return DecisionTree[best_att]


Read_Excel(table)
print(TreeGenerate(8, 9, dataset, attributesdict))

程序运行结果

与书上的结果一致（浅白一栏应为坏瓜）

当把“密度”和“含糖率”也纳入属性集合中，即

attributesdict = {'色泽':['青绿', '乌黑', '浅白'], '根蒂':['蜷缩', '稍蜷', '硬挺'], '敲声':['浊响', '沉闷', '清脆'],\
                  '纹理':['清晰', '稍糊', '模糊'], '脐部':['凹陷', '稍凹', '平坦'], '触感':['硬滑', '软粘'],\
                  '密度':['0', '1'], '含糖率':['0', '1']}

则结果为

与书上的结果一致

提供完整代码与数据集文件的下载链接：西瓜3.0决策树.zip