题目

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

基于信息熵进行划分选择的决策树算法，即ID3决策树学习算法

数据采用西瓜数据集3.0中所有离散属性数据

编号	色泽	根蒂	敲声	纹理	脐部	触感	好瓜
1	青绿	蜷缩	浊响	清晰	凹陷	硬滑	是
2	乌黑	蜷缩	沉闷	清晰	凹陷	硬滑	是
3	乌黑	蜷缩	浊响	清晰	凹陷	硬滑	是
4	青绿	蜷缩	沉闷	清晰	凹陷	硬滑	是
5	浅白	蜷缩	浊响	清晰	凹陷	硬滑	是
6	青绿	稍蜷	浊响	清晰	稍凹	软粘	是
7	乌黑	稍蜷	浊响	稍糊	稍凹	软粘	是
8	乌黑	稍蜷	浊响	清晰	稍凹	硬滑	是
9	乌黑	稍蜷	沉闷	稍糊	稍凹	硬滑	否
10	青绿	硬挺	清脆	清晰	平坦	软粘	否
11	浅白	硬挺	清脆	模糊	平坦	硬滑	否
12	浅白	蜷缩	浊响	模糊	平坦	软粘	否
13	青绿	稍蜷	浊响	稍糊	凹陷	硬滑	否
14	浅白	稍蜷	沉闷	稍糊	凹陷	硬滑	否
15	乌黑	稍蜷	浊响	清晰	稍凹	软粘	否
16	浅白	蜷缩	浊响	模糊	平坦	硬滑	否
17	青绿	蜷缩	沉闷	稍糊	稍凹	硬滑	否

 导入python库，并导入数据

import pandas as pd
import numpy as np
from math import log
import operator
import matplotlib.pyplot as plt
from matplotlib.font_manager import FontProperties
from sklearn.tree import DecisionTreeClassifier, plot_tree

data = pd.read_excel("西瓜数据集3.0.xlsx")

 编写函数，构建决策树

# 整理数据
def get_data(data):
    """
    该函数返回整理好的数据，及其属性（列名）

    Parameters
    -------
    data: 输入excel表格中得到的dataframe表格 
    
    Returns
    -------
    dataSet: numpy.ndarray类型，二维列表 一行对应一个样本的数据

    labels: 对应dataSet每一列的属性名称，即选取需要的列
    """

    # 将离散的属性值进行数字化，
	# 色泽： 青绿-0  乌黑-1  浅白-2
    # 根蒂： 蜷缩-0  稍蜷-1  硬挺-2
    # 敲声： 浊响-0  沉闷-1  清脆-2
    # 纹理： 清晰-0  稍糊-1  模糊-2
    # 脐部： 凹陷-0  稍凹-1  平坦-2
    # 触感： 硬滑-0  软粘-1
    # 好瓜： 否-0    是-1

    data['色泽'] = data["色泽"].replace({'青绿': 0, '乌黑': 1, '浅白': 2})
    data['根蒂'] = data["根蒂"].replace({'蜷缩': 0, '稍蜷': 1, '硬挺': 2})
    data['敲声'] = data["敲声"].replace({'浊响': 0, '沉闷': 1, '清脆': 2})
    data['纹理'] = data["纹理"].replace({'清晰': 0, '稍糊': 1, '模糊': 2})
    data['脐部'] = data["脐部"].replace({'凹陷': 0, '稍凹': 1, '平坦': 2})
    data['触感'] = data["触感"].replace({'硬滑': 0, '软粘': 1})
    data['好瓜'] = data["好瓜"].replace({'否': 0, '是': 1})
  

    labels = ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感', '好瓜']   # 选出需要的属性
    dataSet = data[labels].values

    return dataSet, labels

# 计算数据集的信息熵
def calcShannonEnt(dataSet):
    """
    该函数计算数据集的信息熵

    Parameters
    -------
    dataSet: numpy.ndarray类型，二维列表 一行对应一个样本的数据
    
    Returns
    -------
    shannonEnt: float类型，样本集合的信息熵
    """
    numEntries = len(dataSet) # 总样本个数
    labelCounts = {}  # 字典, 数据集中好瓜个数，坏瓜个数
    for featVec in dataSet:
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0  # 初始化 标签 （好瓜/坏瓜）
        labelCounts[currentLabel] += 1
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key]) / numEntries  # 好瓜/坏瓜比例
        shannonEnt -= prob*log(prob, 2)

    return shannonEnt

# 按照给定特征划分数据集
def splitDataSet(dataSet, axis, value):
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            # 对符合value的该样本，剔除axis轴，并储存
            # reducedFeatVec = featVec[:axis]   # 适用于list
            # reducedFeatVec.extend(featVec[axis+1:])
            reducedFeatVec = np.concatenate((featVec[:axis], featVec[axis+1:]))  # 适用于np.ndarray

            retDataSet.append(reducedFeatVec)
    return retDataSet

# 选择最好的数据集划分方式
def chooseBestFeatureToSplit(dataSet):
    """
    按信息熵，选出信息增益最大的属性，并将其作为划分属性

    Parameters
    -------
    dataSet: numpy.ndarray类型，二维列表 一行对应一个样本的数据
    
    Returns
    -------
    bestFeature: 信息增益最大的属性，后续将其作为决策树划分属性
    """
    numFeatures = len(dataSet[0]) - 1 # 最后一列，用作标签
    baseEntropy = calcShannonEnt(dataSet)  # 根节点的信息熵
    bestInfoGain = 0.0   # 初始化最大属性的信息增益
    bestFeature = -1     # 初始化最大属性的下标指针
    for i in range(numFeatures):   # 遍历各属性，并选出信息增益最大的属性
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList) # 集合，去重，即得到这一属性下的不同取值
        newEntropy = 0.0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value) # 每个属性下，不同取值的占比
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet) 
        infoGain = baseEntropy - newEntropy
        if (infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = i 
    return bestFeature

def majorityCnt(classList):
    """
    - 返回指定样本集合中，数量占优的标签 
    - 即，集合中有5个样本，4好瓜，1坏瓜，将该集合标记为好瓜
    - 如果决策树不划分，将该结点标记为叶节点，其类别标记为训练样例数最多的类别

    Parameters
    -------
    classList: 标签，一列， 好瓜/坏瓜
    
    Returns
    -------
    sortedClassCount[0][0]: 训练样例数最多的类别 (好瓜/坏瓜)
    """
    classCount = {}  # 统计好瓜/坏瓜个数
    for vote in classList: # 统计classList每个元素出现的次数
        if vote not in classCount.keys():classCount[vote] = 0 # 初始化
        classCount[vote] += 1 
        # classCount.items() 将字典classCount转换为一个包含（键，值）元组的列表
        # operator.itemgetter(1) 从可迭代对象（如元组）中提取索引为1的元素，即字典的值
        #                        比lambda表达式，效率略高
        # reverse=True 降序排列
        # sortedClassCount 排序后的元组列表， 按字典值，即样本个数降序排列
        sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse=True)
        return sortedClassCount[0][0]  

# 递归构建决策树
def createTree(dataSet, labels):
    """
    递归构建ID3决策树

    Parameters
    -------
    dataSet: numpy.ndarray类型，二维列表 一行对应一个样本的数据

    labels: 对应dataSet每一列的属性名称，即选取需要的列

    Returns
    -------
    myTree
    """
    classList = [example[-1] for example in dataSet] # 标签，一列， 好瓜/坏瓜
    if classList.count(classList[0]) == len(classList): # 当该样本集合中，标签一致
        return classList[0]                             # 不再划分，返回该标签
    if len(dataSet[0]) == 1:   # 该样本数据中，只有一列属性
        return majorityCnt(classList) # 将类别设定为该节点所含样本最多的类别
    bestFeat = chooseBestFeatureToSplit(dataSet)   # 选出信息增益最大的属性，对决策树进一步划分
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}}
    del(labels[bestFeat]) # 剔除已被选出的属性
    featValues = [example[bestFeat] for example in dataSet]  
    uniqueVals = set(featValues) # 信息增益最大的属性, 的去重不同取值
    for value in uniqueVals:
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree

展示生成的决策树 

mydata, labels = get_data(data)
print("数据：")
print(mydata)
print("数据各列对应属性名称：")
print(labels)

Ent1 = calcShannonEnt(mydata)
print(f"根节点的信息熵为：{Ent1}")

bestFeature = chooseBestFeatureToSplit(mydata)
print(f"根节点下，最好的划分属性的下标为：{bestFeature}")

myTree = createTree(mydata, labels)
print("生成决策树如下：")
print(myTree)

画图绘制决策树 

# 使用matplotlib注解绘制树形图
decisionNode = dict(boxstyle = 'sawtooth', fc = '0.8')  # 边框样式锯齿状， 填充颜色的灰度值为0.8
leafNode = dict(boxstyle = 'round4', fc = '0.8')
arrow_args = dict(arrowstyle = '<-')                    # 箭头样式

def plotNode(nodeTxt, centerPt, parentPt, nodeType):
    """ 
    绘制决策树的node结点，一个箭头，指向该结点

    Parameters
    -------
    nodeTxt: 节点文字

    centerPt: 箭头位置，连接结点方框 (x, y) 其中，(0,0)子图左下角，(1,1)子图右下角

    parentPt: 箭头起始线，连接父节点方框 (x, y)

    nodeType: 决策结点 or 叶节点

    Returns
    -------
    None
    """
    # anotate 在图形中添加注释文本，并可以选择绘制从一个点指向另一个点的箭头
    # xy 指定箭头指向的位置，是一个包含两个元素的元组（x, y)
    # xycoords 指定xy坐标的坐标系类型，'axes fraction' 使用相对子图坐标轴的比例坐标系统，(0,0)子图左下角，(1,1)子图右下角
    # xytext 指定注释文本的位置 (x, y)
    # textcoords 指定xytext坐标的坐标系类型，'axes fraction' 使用相对子图坐标轴的比例坐标系统，(0,0)子图左下角，(1,1)子图右下角
    # va 即vertical alignment，指定注释文本的垂直对齐方式
    # ha 即horizontal alignment， 指定注释文本的水平对齐方式
    # nodeType 设置注释文本的边框样式，是一个字典
    # arrowprops 设置箭头样式，是一个字典
    # fontproperties 设置字体，微软雅黑
    createPlot.ax1.annotate(nodeTxt, xy = parentPt, xycoords='axes fraction', \
                            xytext=centerPt, textcoords='axes fraction', \
                            va='center', ha='center', bbox=nodeType, arrowprops=arrow_args, \
                            fontproperties=FontProperties(fname=r"c:\windows\fonts\msyh.ttc", size=14))
    
def createPlot():
    fig = plt.figure(1, facecolor='white')  # 创建一个图形窗口，背景白色
    fig.clf()      # 清空fig画布，避免之前可能存在的绘图内容对当前绘图产生干扰
    # subplot(111) 等价 subplot(nrows=1, ncols=1, index=1) 即创建1行1列的子图布局，并操作当前这个布局中的第一个子图
    # frameon=False 子图不显示边框
    # createPlot.ax1 python中函数也是对象，可以给createPlot添加属性ax1
    createPlot.ax1 = plt.subplot(111, frameon=False)
    plotNode('a decision node', (0.5, 0.1), (0.1, 0.5), decisionNode)
    plotNode('a leaf node', (0.8, 0.1), (0.3, 0.8), leafNode)
    plt.show()

# 获取叶结点的数目
def getNumLeafs(myTree):
    """ 
    返回决策树叶结点的数目
    """
    numLeafs = 0
    firstStr = list(myTree.keys())[0]   # 父结点属性
    secondDict = myTree[firstStr]
    for key in secondDict.keys():
        if type(secondDict[key]).__name__ == 'dict':
            numLeafs += getNumLeafs(secondDict[key])
        else:                                         # 若结点不是字典形式，说明是叶结点
            numLeafs += 1
    return numLeafs

# 获取树的层数
def getTreeDepth(myTree):
    """ 
    返回决策树的深度
    """
    maxDepth = 0
    firstStr = list(myTree.keys())[0]   # 父结点属性
    secondDict = myTree[firstStr]
    for key in secondDict.keys():
        if type(secondDict[key]).__name__ == 'dict': 
            thisDepth = 1 + getTreeDepth(secondDict[key])
        else:                                        # 若结点不是字典形式，说明是叶结点
            thisDepth = 1 
        if thisDepth > maxDepth:
            maxDepth = thisDepth
    return maxDepth

先测试一下效果：

print("决策树如下：")
print(myTree)
print(f"该决策树叶结点的数目为：{getNumLeafs(myTree)}")
print(f"树的深度为：{getTreeDepth(myTree)}")

 继续实现绘制决策树的代码，主要以递归方式实现

def plotMidText(cntrPt, parentPt, txtString):
    """ 
    在两个点cntrPt和parentPt的中间位置，添加注释文本txtString
    """
    xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]
    yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]
    createPlot.ax1.text(xMid, yMid, txtString, va='center', ha='center', rotation=30)

def plotTree(myTree, parentPt, nodeTxt):
    """ 
    递归绘制决策树
    """
    numLeafs = getNumLeafs(myTree) # 决策树叶结点数目
    depth = getTreeDepth(myTree)   # 决策树深度
    firstStr = list(myTree.keys())[0] # 结点的文本
    cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff)
    plotMidText(cntrPt, parentPt, nodeTxt)
    plotNode(firstStr, cntrPt, parentPt, decisionNode)
    secondDict = myTree[firstStr]
    plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD
    for key in secondDict.keys():
        if type(secondDict[key]).__name__=='dict':
            plotTree(secondDict[key], cntrPt, str(key))  # 将分支属性，作为注释文本添加
        else:
            plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW
            plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
            plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
    plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD

def createPlot(inTree):
    fig = plt.figure(1, facecolor='white')
    fig.clf()
    axprops = dict(xticks=[], yticks=[])
    createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)
    # 初始化plotTree的各参数
    plotTree.totalW = float(getNumLeafs(inTree))  # 决策树总宽度，即叶结点数目
    plotTree.totalD = float(getTreeDepth(inTree)) # 决策树深度
    plotTree.xOff = -0.5/plotTree.totalW
    plotTree.yOff = 1.0
    plotTree(inTree, (0.5, 1.0), '')  # 根结点，无注释文本txtString
    plt.show()

效果如下：

与sklearn库的效果进行比较

两种决策树还是有一定区别的。

第一，对纹理清晰，根蒂、脐部、触感3个属性均取到最大信息增益，sklearn选取了触感进行划分

第二，ID3这次自己实现的方法应当属于比较陈旧的，每次选取当前最佳的特征分割数据，并按照该特征的所有可能取值切分子集，该特征在之后的算法执行过程中不再起作用。

这也导致了ID3自己实现的方法，只能运用于属性为离散值的情况 ，而这种切分方式可能过于迅速了，之前使用过的特征在新的子集中仍然有可能是最佳的特征。

sklearn中应该是直接使用了二元切分法，选取当前最佳的特征, 将数据集切分为两份，可以设定大于给定值，分为左子树，反之，分为右子树。

二元切分法，能够处理连续型变量。

X = mydata[:, :-1]
y = mydata[:, -1]

# 2. 构建ID3决策树模型
# 设置criterion='entropy'来模拟ID3算法
clf = DecisionTreeClassifier(criterion='entropy')

# 3. 训练模型
clf.fit(X, y)

# 4. 绘制决策树图片
plt.rcParams['font.family'] = 'Microsoft YaHei'
plt.figure(figsize=(12, 8))
plot_tree(clf, feature_names=['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']  , class_names=['坏瓜','好瓜'], filled=True)
plt.title("ID3 Decision Tree")
plt.show()

效果如下：