文章目录

一、决策树介绍

决策树是一种基于树结构来进行决策的分类算法，我们希望从给定的训练数据集学得一个模型（即决策树），用该模型对新样本分类。决策树可以非常直观展现分类的过程和结果，一旦模型构建成功，对新样本的分类效率也相当高。

最经典的决策树算法有ID3、C4.5、CART，其中ID3算法是最早被提出的，它可以处理离散属性样本的分类，C4.5和CART算法则可以处理更加复杂的分类问题。

利用信息增益选择最优划分属性

样本有多个属性，该先选哪个样本来划分数据集呢？原则是随着划分不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一分类，即“纯度”越来越高。先来学习一下“信息熵”和“信息增益”。
信息熵（information entropy）
样本集合D中第k类样本所占的比例（k=1,2,…,|Y|），|Y|为样本分类的个数，则D的信息熵为：
在这里插入图片描述

Ent(D)的值越小，则D的纯度越高。直观理解一下：假设样本集合有2个分类，每类样本的比例为1/2，Ent(D)=1；只有一个分类，Ent（D）= 0，显然后者比前者的纯度高。

信息增益（information gain）

使用属性a对样本集D进行划分所获得的“信息增益”的计算方法是，用样本集的总信息熵减去属性a的每个分支的信息熵与权重（该分支的样本数除以总样本数）的乘积，通常，信息增益越大，意味着用属性a进行划分所获得的“纯度提升”越大。因此，优先选择信息增益最大的属性来划分。设属性a有V个可能的取值，则属性a的信息增益为：
在这里插入图片描述

增益率（gain ratio）
基于信息增益的最优属性划分原则——信息增益准则
，对可取值数据较多的属性有所偏好。C 4.5 C4.5C4.5算法使用增益率代替信息增益来选择最优划分属性，增益率定义为：
在这里插入图片描述
其中
在这里插入图片描述
称为属性 a aa 的固有值。属性 a aa 的可能取值数目越多（即V VV越大），则 I V ( a ) IV(a)IV(a) 的值通常会越大。这在一定程度上消除了对可取值数据较多的属性的偏好。
  事实上，增益率准则对可取值数目较少的属性有所偏好，C 4.5 C4.5C4.5 算法并不是直接使用增益率准则，而是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
基尼指数（Gini index）
C A R T CARTCART 决策树算法使用基尼指数（Gini index）来选择划分属性。数据集 D DD 的纯度可用基尼值来度量：
在这里插入图片描述

G i n i ( D ) Gini(D)Gini(D) 反应了从数据集 D DD 中随机抽取两个样本，其类别标记不一致的概率。由此，G i n i ( D ) Gini(D)Gini(D) 越小，纯度越高。
  属性 a aa 的基尼指数定义为：
在这里插入图片描述
在候选属性集合 A AA 中，选择那个使得划分后基尼指数最小的属性作为最优化分属性。即
在这里插入图片描述

二、实现针对西瓜数据集的ID3算法代码，并输出可视化结果。

1、西瓜数据集

在这里插入图片描述

青绿 蜷缩 浊响 清晰 凹陷 硬滑 是
乌黑 蜷缩 沉闷 清晰 凹陷 硬滑 是
乌黑 蜷缩 浊响 清晰 凹陷 硬滑 是
青绿 蜷缩 沉闷 清晰 凹陷 硬滑 是
浅白 蜷缩 浊响 清晰 凹陷 硬滑 是
青绿 稍蜷 浊响 清晰 稍凹 软粘 是
乌黑 稍蜷 浊响 稍糊 稍凹 软粘 是
乌黑 稍蜷 浊响 清晰 稍凹 硬滑 是
乌黑 稍蜷 沉闷 稍糊 稍凹 硬滑 否
青绿 硬挺 清脆 清晰 平坦 软粘 否
浅白 硬挺 清脆 模糊 平坦 硬滑 否
浅白 蜷缩 浊响 模糊 平坦 软粘 否
青绿 稍蜷 浊响 稍糊 凹陷 硬滑 否
浅白 稍蜷 沉闷 稍糊 凹陷 硬滑 否
乌黑 稍蜷 浊响 清晰 稍凹 软粘 否
浅白 蜷缩 浊响 模糊 平坦 硬滑 否
青绿 蜷缩 沉闷 稍糊 稍凹 硬滑 否

2. 代码实现

（1）建立决策树

计算信息熵函数

#计算信息熵
def calcInformationEntropy(dataSet):
    #dataSet最后一列是类别，前面是特征
    dict = {}
    m = len(dataSet)
    for i in range(m):
        #.get()函数：如果没有这个key，就返回默认值；如果有这个key，就返回这个key的value
        dict[dataSet[i][-1]] = dict.get(dataSet[i][-1], 0) + 1;
    ent = 0
    for key in dict.keys():
        p = float(dict[key]) / m
        ent = ent - (p * np.math.log(p, 2))
    return ent

划分数据集函数

#划分数据集
#dataSet:数据集
#axis: 要划分的列下标
#value: 要划分的列的值
def splitDataSet(dataSet, axis, value):
    splitedDataSet = []
    for data in dataSet:
        if(data[axis] == value):
            reduceFeatureVec = data[: axis]
            reduceFeatureVec.extend(data[axis + 1 :])
            splitedDataSet.append(reduceFeatureVec)
    return splitedDataSet

计算信息增益函数

#计算信息增益,然后选择最优的特征进行划分数据集
#信息增益的计算公式：西瓜书P75
def chooseBestFeatureToSplit(dataSet):
    #计算整个集合的熵
    EntD = calcInformationEntropy(dataSet)
    mD = len(dataSet)  #行
    featureNumber = len(dataSet[0][:]) - 1 #列
    maxGain = -1000
    bestFeatureIndex = -1
    for i in range(featureNumber):
        #featureSet = set(dataSet[:][i])  #错误写法：dataSet[:][i]仍然是获取行
        featureCol = [x[i] for x in dataSet]   #取列表某列的方法！！
        featureSet = set(featureCol)
        splitedDataSet = []
        for av in featureSet:
            retDataSet = splitDataSet(dataSet, i, av)
            splitedDataSet.append(retDataSet)
        gain = EntD
        for ds in splitedDataSet:
            mDv = len(ds)
            gain = gain - (float(mDv) / mD) * calcInformationEntropy(ds)
        if(bestFeatureIndex == -1):
            maxGain = gain
            bestFeatureIndex = i
        elif(maxGain < gain):
            maxGain = gain
            bestFeatureIndex = i

    return bestFeatureIndex
    #当所有的特征划分完了之后，如果仍然有叶子节点中的数据不是同一个类别，
# 则把类别最多的作为这个叶子节点的标签
def majorityCnt(classList):
    dict = {}
    for label in classList:
        dict[label] = dict.get(label, 0) + 1
    sortedDict = sorted(dict, dict.items(), key = operator.itemgetter(1), reversed = True)
    return sortedDict[0][0]

递归构建决策树

#递归构建决策树
def createTree(dataSet, labels):
    classList = [x[-1] for x in dataSet]
#    if(len(set(classList)) == 1):
#        return classList[0]
    if(classList.count(classList[0]) == len(classList)):
        return classList[0]
    elif(len(dataSet[0]) == 1):  #所有的属性全部划分完毕
        return majorityCnt(classList)
    else:
        bestFeatureIndex = chooseBestFeatureToSplit(dataSet)
        bestFeatureLabel = labels[bestFeatureIndex]
        myTree = {bestFeatureLabel: {}}
        del(labels[bestFeatureIndex])  #使用完该属性之后，要删除
        featureList = [x[bestFeatureIndex] for x in dataSet]
        featureSet = set(featureList)
        for feature in featureSet:
            subLabels = labels[:]  #拷贝一份，防止label在递归的时候被修改  （list是传引用调用）
            tmpDataSet = splitDataSet(dataSet, bestFeatureIndex, feature)  #划分数据集
            myTree[bestFeatureLabel][feature] = createTree(tmpDataSet, subLabels)
        return myTree

读取数据

#读取西瓜数据集2.0
def readWatermelonDataSet():
    ifile = open("西瓜数据集.txt")
    featureName = ifile.readline()  #表头
    labels = (featureName.split(' ')[0]).split(',')
    lines = ifile.readlines()
    dataSet = []
    for line in lines:
        tmp = line.split('\n')[0]
        tmp = tmp.split(',')
        dataSet.append(tmp)

    return dataSet, labels

输出

melonDataSet, melonLabels = readWatermelonDataSet()
print(melonLabels)
melonBestFeature = chooseBestFeatureToSplit(melonDataSet)
tree = createTree(melonDataSet, melonLabels)
print(tree)

[‘色泽’, ‘根蒂’, ‘敲声’, ‘纹理’, ‘脐部’, ‘触感’, ‘好瓜’]
{‘纹理’: {‘稍糊’: {‘触感’: {‘软粘’: ‘是’, ‘硬滑’: ‘否’}}, ‘模糊’: ‘否’, ‘清晰’: {‘根蒂’: {‘蜷缩’: ‘是’, ‘稍蜷’: {‘色泽’: {‘乌黑’: {‘触感’: {‘软粘’: ‘否’, ‘硬滑’: ‘是’}}, ‘青绿’: ‘是’}}, ‘硬挺’: ‘否’}}}}

（2）绘制决策树

#使用Matlotlib绘制决策树
import matplotlib.pyplot as plt

#设置文本框和箭头格式
decisionNode = dict(boxstyle = "sawtooth", fc = "0.8")
leafNode = dict(boxstyle = "round4", fc = "0.8")
arrow_args = dict(arrowstyle = "<-")
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['font.family'] = 'sans-serif'

#画节点
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
    createPlot.ax1.annotate(nodeTxt, xy = parentPt,\
    xycoords = "axes fraction", xytext = centerPt, textcoords = 'axes fraction',\
    va = "center", ha = "center", bbox = nodeType, arrowprops = arrow_args)
    
#获取决策树的叶子节点数
def getNumLeafs(myTree):
    leafNumber = 0
    firstStr = list(myTree.keys())[0]
    secondDict = myTree[firstStr]
    for key in secondDict.keys():
        if(type(secondDict[key]).__name__ == 'dict'):
            leafNumber = leafNumber + getNumLeafs(secondDict[key])
        else:
            leafNumber += 1
    return leafNumber

#获取决策树的高度（递归）
def getTreeDepth(myTree):
    maxDepth = 0
    firstStr = list(myTree.keys())[0]
    secondDict = myTree[firstStr]
    for key in secondDict.keys():
        #test to see if the nodes are dictonaires, if not they are leaf nodes
        if type(secondDict[key]).__name__=='dict':
            thisDepth = 1 + getTreeDepth(secondDict[key])
        else:   thisDepth = 1
        if thisDepth > maxDepth: maxDepth = thisDepth
    return maxDepth

#在父子节点添加信息
def plotMidText(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):#if the first key tells you what feat was split on
    numLeafs = getNumLeafs(myTree)  #this determines the x width of this tree
    depth = getTreeDepth(myTree)
    firstStr = list(myTree.keys())[0]     #the text label for this node should be this
    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))        #recursion
        else:   #it's a leaf node print the leaf node
            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)    #no ticks
    #createPlot.ax1 = plt.subplot(111, frameon=False) #ticks for demo puropses
    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), '')
    plt.show()

输出结果：
在这里插入图片描述

三、C4.5方法建立决策树

相关数据：
在这里插入图片描述

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

导入相关库

#导入相关库
import pandas as pd
import graphviz 
from sklearn.model_selection import train_test_split
from sklearn import tree

导入数据

f = open('water.csv','r')
data = pd.read_csv(f)

x = data[["色泽","根蒂","敲声","纹理","脐部","触感"]].copy()
y = data['好瓜'].copy()
print(data)

将特征值数值化

#将特征值数值化
x = x.copy()
for i in ["色泽","根蒂","敲声","纹理","脐部","触感"]:
    for j in range(len(x)):
        if(x[i][j] == "青绿" or x[i][j] == "蜷缩" or data[i][j] == "浊响" \
           or x[i][j] == "清晰" or x[i][j] == "凹陷" or x[i][j] == "硬滑"):
            x[i][j] = 1
        elif(x[i][j] == "乌黑" or x[i][j] == "稍蜷" or data[i][j] == "沉闷" \
           or x[i][j] == "稍糊" or x[i][j] == "稍凹" or x[i][j] == "软粘"):
            x[i][j] = 2
        else:
            x[i][j] = 3
            
y = y.copy()
for i in range(len(y)):
    if(y[i] == "是"):
        y[i] = int(1)
    else:
        y[i] = int(-1)

将数据转换为DataFrame数据类型

#需要将数据x，y转化好格式，数据框dataframe，否则格式报错
x = pd.DataFrame(x).astype(int)
y = pd.DataFrame(y).astype(int)
print(x)
print(y)

在这里插入图片描述
将80%数据用于训练，20%数据用于测试

	x_train, x_test, y_train, y_test = train_test_split(x,y,test_size=0.2)
print(x_train)

在这里插入图片描述
建立模型并训练

sklearn.tree.DecisionTreeClassifier(criterion=’gini’,\
									 splitter=’best’, \
 									 max_depth=None, \
 									 min_samples_split=2, \
									 min_samples_leaf=1,\
								  	 min_weight_fraction_leaf=0.0, \
 									 max_features=None, \
 									 max_leaf_nodes=None, \
 									 min_impurity_decrease=0.0,\
 									 min_impurity_split=None, \
 									 class_weight=None, \
 									 presort=False)

可视化决策树

feature_name = ["色泽","根蒂","敲声","纹理","脐部","触感"]
dot_data = tree.export_graphviz(clf                          
                                ,feature_names= feature_name                                
                                ,class_names=["好瓜","坏瓜"]                                
                                ,filled=True                                
                                ,rounded=True
                                ,out_file =None  
                                ) 
graph = graphviz.Source(dot_data) 
graph

在这里插入图片描述

四、使用CART算法

只需要将DecisionTreeClassifier函数的参数criterion的值改为gini：

clf = tree.DecisionTreeClassifier(criterion="gini")  #实例化 
clf = clf.fit(x_train, y_train) 
score = clf.score(x_test, y_test)
print(score)

画决策树：

# 加上Graphviz2.38绝对路径
import os
os.environ["PATH"] += os.pathsep + 'D:/workspace/wrater'
    
feature_name = ["色泽","根蒂","敲声","纹理","脐部","触感"]
dot_data = tree.export_graphviz(clf ,feature_names= feature_name,class_names=["好瓜","坏瓜"],filled=True,rounded=True,out_file =None) 
graph = graphviz.Source(dot_data) 
graph

在这里插入图片描述

五、总结

决策树作为经典分类算法，具有计算复杂度低、结果直观、分类效率高等优点。
学习通过用sk-learn库对西瓜数据集，分别进行ID3、C4.5和CART的算法代码实现。
这次的西瓜数据集较小，测试集和训练集的划分对模型精度的影响较大。

六、参考链接

ID3算法流程
西瓜书中ID3决策树的实现
https://blog.csdn.net/leaf_zizi/article/details/82848682

点击阅读全文
# 决策树 # 机器学习 # python
Logo
华为开发者空间

华为开发者空间，是为全球开发者打造的专属开发空间，汇聚了华为优质开发资源及工具，致力于让每一位开发者拥有一台云主机，基于华为根生态开发、创新。

更多推荐

cover

开发者必备！基于开发者空间的 DeepSeek 模型 API 调用及参数调试攻略

avatar 华为开发者空间
cover

DeepSeek大模型Prompt工程深度实践（开发者空间Notebook版）

avatar 华为开发者空间
cover

HCDG城市行·阜阳站——AIGC大师班走进阜阳，技术赋能广电媒体，推动行业创新升级

avatar 华为开发者空间