当前位置:   article > 正文

【数据挖掘】决策树C4.5算法Python实现_c4.5决策树手动实现

c4.5决策树手动实现

前言

文章内容为对数据挖掘实验作业的记录,如果您是为了作业而来看的这篇文章,还请不要无脑拷贝,本人编程能力较弱,代码写的并不优雅,注释尽可能写的详细了。
和上一篇文章ID3算法实现的过程基本一致,不同之处在于C4.5使用信息增益率作为选择标准,为了区别于上一种方式,这里对连续值的处理使用遍历来查找一个使信息增益率最优的值。

注意

程序可能要跑20-30分钟

决策树算法

决策树是一类常见的机器学习方法.以二分类任务为例,我们希望从给定训练数据集学得一个模型用以对新示例进行分类,这个把样本分类的任务,可看作对“当前样本属于正类吗?”这个问题的“决策”或“判定 ”过程。
一般的,一棵决策树包含一个根结点、若干个内部结点和若干个叶结点,叶结点对应于决策结果,其他每个结点则对应于一个属性测试;每个结点包含的样本集合根据属性测试的结果被划分到子结点中;根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列。决策树学习的目的是为了产生一棵泛化能力强,即处理未见示例能力强的决策树,其基本流程遵循简单且直观的“分而治之"策略。
在这里插入图片描述
根据决策树的算法思想,如何选择最优划分属性至关重要,随着划分过程的不断进行,我们希望决策树的分支结点所包含的样本尽可能属于同一类别。
根据不同的划分规则,目前常见的决策树算法有ID3算法和C4.5算法

C4.5算法

在这里插入图片描述
在这里插入图片描述
可以看到C4.5算法与ID3算法大致相同,不同的是C4.5算法使用了信息增益率对属性的决策顺序进行了调整。

决策树算法进行分类的具体步骤

根据以上对决策树算法以及ID3、C4.5算法的分析,我们可以大致得到使用决策树对数据进行分类的具体步骤
(1) 数据预处理
(2) 对数据进行划分,计算各个属性的信息增益(ID3)或信息增益率(C4.5)
(3) 选择较大的信息增益或信息增益率对应的划分点构建决策树
(4) 使用样本数据对构建的决策树进行测试,得到正确率最大的决策树对应的深度
(5) 对陌生的数据进行分类预测

导入库

import numpy as np
import pandas as pd
from math import log
import matplotlib.pyplot as plt
  • 1
  • 2
  • 3
  • 4

分析样本数据

# 从本地读取样本数据集,这里选择前两种癌症数据进行分析
BLCA = pd.read_csv(r'数据集/BLCA/rna.csv')
KIRC = pd.read_csv(r'数据集/KIRC/rna.csv')
print(BLCA.shape)
print(KIRC.shape)
  • 1
  • 2
  • 3
  • 4
  • 5
(3217, 400)
(3217, 489)
  • 1
  • 2
# 对数据进行转置,之后每行对应一个样本数据,每列对应一个属性
BLCASet = BLCA.T
BLCASet = BLCASet.iloc[1:,:].astype('float32')
KIRCSet = KIRC.T
KIRCSet = KIRCSet.iloc[1:,:].astype('float32')
  • 1
  • 2
  • 3
  • 4
  • 5
# 插入一列数据用来标识不同的类别
BLCASet.insert(loc=3217, column=3217, value='BLCA')
KIRCSet.insert(loc=3217, column=3217, value='KIRC')
  • 1
  • 2
  • 3
# 转为numpy类型方便处理
BLCASet = np.array(BLCASet)
KIRCSet = np.array(KIRCSet)
  • 1
  • 2
  • 3
# 将两种癌症样本数据进行合并
DataSet = np.vstack((BLCASet,KIRCSet))
  • 1
  • 2

计算各个属性对应的信息增益率

def I(s1, s2):
    '''
    计算信息熵
    '''
    t = s1+s2
    if t==0:
        return 0
    p1 = float(s1/t)
    p2 = float(s2/t)
    if p1==1 or p2==1:
        return 1
    if p1*p2!=0:
        return -p1*log(p1,2)-p2*log(p2,2)
    else:
        if p1==0:
            return -p2*log(p2,2)
        else:
            return -p1*log(p1,2)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
# 计算总熵
I_t = I(BLCASet.shape[0],KIRCSet.shape[0])
  • 1
  • 2
# 接下来为计算每种属性可能的最优信息增益率
row = DataSet.shape[0] # 获取数据集行数
col = DataSet.shape[1] # 获取数据集列数
divList = [] # 存储获得最大信息增益率的划分点
Gain = [] # 存储信息增益
Gain_Ratio = [] # 存储信息增益率
Sel = [] # 存储节点决策:0表示大于等于能确定、1表示小于能够确定
Dec = [] # 存储当前决策下能够确定的类别
S11 = []
S12 = []
S21 = []
S22 = []
for i in range(col-1):
    data = DataSet[:,i]
    divdata = set(data) # 去重
    divdata = list(divdata)
    for j in range(len(divdata)): # 遍历所有属性值,以每个属性取值为划分点进行划分
        div = divdata[j]
        s11 = 0
        s12 = 0
        s21 = 0
        s22 = 0
        for k in range(row): # 对每个所有数据进行统计
            if data[k]>=div:
                if DataSet[k][-1] == 'BLCA': #s11存储所有大于等于划分点且属于BLCA的样本
                    s11 = s11+1
                if DataSet[k][-1] == 'KIRC': #s12存储所有大于等于划分点且属于KIRC的样本
                    s12 = s12+1
            else:
                if DataSet[k][-1] == 'BLCA': #s21存储所有小于划分点且属于BLCA的样本
                    s21 = s21+1
                if DataSet[k][-1] == 'KIRC': #s22存储所有小于划分点且属于BLCA的样本
                    s22 = s22+1
        I1 = I(s11, s12) # I(s11,s12)
        I2 = I(s21, s22) # I(s21,s22)
        Ii = I(s11+s12, s21+s22) # 计算该属性的信息熵
        gain = I_t-((s11+s12)/len(data)*I1+(s21+s22)/len(data)*I2) # 该属性的信息增益
        gain_ratio = gain/Ii # 该属性在该划分下的信息增益率
        # 接下来为更新信息增益率,保存该属性所有属性值之下的最大信息增益率所对应的一些信息
        if j==0:
            divList.append(div)
            Gain.append(gain)
            Gain_Ratio.append(gain_ratio)
            if I1<I2:
                Sel.append(0)
                if s11>s12:
                    Dec.append('BLCA')
                else:
                    Dec.append('KIRC')
            else:
                Sel.append(1)
                if s21>s22:
                    Dec.append('BLCA')
                else:
                    Dec.append('KIRC')
            S11.append(s11)
            S12.append(s12)
            S21.append(s21)
            S22.append(s22)
        elif gain_ratio>Gain_Ratio[i]: # 当前信息增益率更优
            Gain_Ratio.pop()
            Gain_Ratio.append(gain_ratio)
            Gain.pop()
            Gain.append(gain)
            S11.pop()
            S11.append(s11)
            S12.pop()
            S12.append(s12)
            S21.pop()
            S21.append(s21)
            S22.pop()
            S22.append(s22)
            divList.pop()
            divList.append(div)
            if I1<I2:
                Sel.pop()
                Sel.append(0)
                if s11>s12:
                    Dec.pop()
                    Dec.append('BLCA')
                else:
                    Dec.pop()
                    Dec.append('KIRC')
            else:
                Sel.pop()
                Sel.append(1)
                if s21>s22:
                    Dec.pop()
                    Dec.append('BLCA')
                else:
                    Dec.pop()
                    Dec.append('KIRC')
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
# 按照Gain中值的降序,对其下标进行排序
indexList = np.argsort(Gain_Ratio)[::-1]
  • 1
  • 2

构建决策树

# 这里对data中的数据进行决策,判断其所属
def decisionTree(data, i):
    if i==len(data)-1:
        # print(f"第{i}层可以做决策")
        if Sel[indexList[i-1]]==0:
            if S11[indexList[i-1]]>=S12[indexList[i-1]]:
                return 'KIRC'
            else:
                return 'BLCA'
        else:
            if S21[indexList[i-1]]>=S22[indexList[i-1]]:
                return 'KIRC'
            else:
                return 'BLCA'
    elif Sel[indexList[i]]==0 and data[i]>=divList[indexList[i]]: # 大于等于可以决策
        # print(f"第{i}层可以做决策")
        return Dec[indexList[i]]
    elif Sel[indexList[i]]==1 and data[i]<divList[indexList[i]]: # 小于可以决策
        # print(f"第{i}层可以做决策")
        return Dec[indexList[i]]
    else:
        return decisionTree(data, i+1)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
# deep指定决策树的深度
deep = 5
data = np.array(DataSet[:,indexList[:deep]])
data = np.hstack((data,DataSet[:,-1].reshape(data.shape[0],1)))
  • 1
  • 2
  • 3
  • 4

计算决策树的正确率

total = data.shape[0]
corr = 0 
mis = 0
for i in range(0, total):
    res = decisionTree(data[i], 0)
    # print(res)
    if res == data[i][-1]:
        # print('正确')
        corr = corr + 1
    else:
        # print('错误')
        mis = mis + 1
print(f"{corr}/{total}")
print(f"深度为{deep}的决策树的正确率为{corr/total}")
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
876/887
深度为5的决策树的正确率为0.9875986471251409
  • 1
  • 2

决策树的可视化

# 接下来为绘图的代码,唯独这里不是这一块不是原创,不过好像网上用的好像都一样? 
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
decisionNode = dict(boxstyle = "sawtooth",fc="0.8")
leafNode = dict(boxstyle = "round4",fc="0.8")
arrow_args = dict(arrowstyle="<-")
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 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)
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.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()
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
# 分析绘制树的代码可以知道,我们首先需要提供用“字典”表示的树
# 编写一个递归构建树的函数
def genInTree(deep,i):
    if i==deep:
        if Sel[indexList[i]]==0:
            if S11[indexList[i-1]]>=S12[indexList[i-1]]:
                return {divList[indexList[i]]:{">=":"BLCA","<":"KIRC"}}
            else:
                return {divList[indexList[i]]:{">=":"KIRC","<":"BLCA"}}
        else:
            if S21[indexList[i-1]]>=S22[indexList[i-1]]:
                return {divList[indexList[i]]:{">=":"KIRC","<":"BLCA"}}
            else:
                return {divList[indexList[i]]:{">=":"BLCA","<":"KIRC"}}
    else:
        if Sel[indexList[i]]==0:
            return {divList[indexList[i]]:{">=":Dec[i],"<":genInTree(deep,i+1)}}
        else:
            return {divList[indexList[i]]:{">=":genInTree(deep,i+1),"<":Dec[i]}}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
# 上述函数的输出大概是这个样子
genInTree(6,0)
  • 1
  • 2
{0.7812503576278687: {'>=': 'BLCA',
  '<': {0.5096836686134338: {'>=': 'KIRC',
    '<': {0.22351205348968506: {'>=': 'BLCA',
      '<': {0.8123461008071899: {'>=': 'BLCA',
        '<': {0.9550216197967529: {'>=': 'BLCA',
          '<': {0.9345895648002625: {'>=': 'BLCA',
            '<': {-0.5671966075897217: {'>=': 'KIRC', '<': 'BLCA'}}}}}}}}}}}}}}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
# 其中deep为深度,也可以手动填
createPlot(genInTree(deep,0))
  • 1
  • 2

请添加图片描述

实验结论

两种算法这实验步骤上基本一致,区别在于在选择用作决策的属性时,ID3算法使用的是属性的信息增益,而C4.5算法使用的是属性的信息增益率。
同时,为了比较划分连续数据的方式给最终结果所带来的不同,两种算法在对连续值进行划分时我使用了不同的方式,ID3算法我就用该属性最大和最小值的均值作为划分点,而C4.5算法则使用遍历所有的属性值,最终找到最优信息增益率所对应的划分点。
实验之前,肯定会想第二种方式会得到更好的效果,但结果显示,两种方式的差别并不大,这印证了老师课上所说的:对连续值进行划分这个行为本身就会带来一定的信息增益。

写在最后

这学期真是挺忙的 >_<,可以说算是百忙之中抽出时间来写这个选修课作业了ಥ_ಥ

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/很楠不爱3/article/detail/711797
推荐阅读
相关标签
  

闽ICP备14008679号