精华内容
下载资源
问答
  • C4.5算法
    2021-06-05 13:45:50

    1实验目的:

    实现c4.5算法。要求:

    1.给定一个训练数据集,得到决策树并用图形显示该决策树。

    2. 用学习得到的决策树对测试集进行判决或分类,得到测试集上的分类错误率。

    2实验过程:

    1. 数据集

         本实验采用西瓜数据集2.0

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

      2.C4.5算法实现

       

    2.1定义函数:计算信息熵

    # 函数说明:计算给定数据集的经验熵(香农熵)
    def calcShannonEnt(dataSet):
        numEntires = len(dataSet)                       #返回数据集的行数
        labelCounts = {}                               #保存每个标签(Label)出现次数的字典
        for featVec in dataSet:                        #对每组特征向量进行统计
            currentLabel = featVec[-1]                 #提取标签(Label)信息
            if currentLabel not in labelCounts.keys(): #如果标签(Label)没有放入统计次数的字典,添加进去
                labelCounts[currentLabel] = 0
            labelCounts[currentLabel] += 1             #Label计数
        shannonEnt = 0.0                               #经验熵(香农熵)
        for key in labelCounts:                        #计算香农熵
            prob = float(labelCounts[key]) / numEntires#选择该标签(Label)的概率
            shannonEnt -= prob * log(prob, 2)          #利用公式计算
        return shannonEnt                              #返回经验熵(香农熵)
    

    2.2 定义函数:将数据集中某一特征所在的列去掉

    def splitDataSet(dataSet, axis, value):
        retDataSet = []                                #创建返回的数据集列表
        for featVec in dataSet:                        #遍历数据集
            if featVec[axis] == value:
                reducedFeatVec = featVec[:axis]        #去掉axis特征
                reducedFeatVec.extend(featVec[axis+1:])#将符合条件的添加到返回的数据集
                retDataSet.append(reducedFeatVec)
        return retDataSet                              #返回划分后的数据集

    2.3定义函数:计算信息增益率,并返回当前数据集的信息增益率最大的属性

    def chooseBestFeatureToSplit(dataSet,label):
        numFeatures = len(label)                  #特征数量
        baseEntropy = calcShannonEnt(dataSet)                 #计算数据集的香农熵
        bestInfoGainRatio = 0.0                                    #信息增益率
        bestFeature = -1                                      #最优特征的索引值
        
        for i in range(numFeatures):                          #遍历所有特征
            #获取dataSet的第i个所有特征
            featList = [example[i] for example in dataSet]
            uniqueVals = set(featList)                         #创建set集合{},元素不可重复
            newEntropy = 0.0                                   #经验条件熵
            IV = 1e-5
            for value in uniqueVals:                           #计算信息增益
                subDataSet = splitDataSet(dataSet, i, value)   #subDataSet划分后的子集
                prob = len(subDataSet) / float(len(dataSet))   #计算子集的概率
                newEntropy += prob * calcShannonEnt(subDataSet)#根据公式计算经验条件熵
                IV -= prob * log(prob,2)                       #计算IV
            infoGain = baseEntropy - newEntropy                #信息增益
            Gain_ratio = infoGain/IV                           #增益率
            # print("第%d个特征的增益为%.3f" % (i, infoGain))   #打印每个特征的信息增益
            if (Gain_ratio > bestInfoGainRatio):                      #计算信息增益
                bestInfoGainRatio = Gain_ratio                        #更新信息增益,找到最大的信息增益
                bestFeature = i                                #记录信息增益最大的特征的索引值
        return bestFeature                                     #返回信息增益最大的特征的索引值

    2.4定义函数:统计分类数组中类别最多的标签

    def majorityCnt(classList):
        classCount = {}
        for vote in classList:#统计classList中每个元素出现的次数
            if vote not in classCount.keys():
                classCount[vote] = 0
            classCount[vote] += 1
        sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True)#根据字典的值降序排序
        return sortedClassCount[0][0]#返回classList中出现次数最多的元素

    2.5定义函数:判断所有样本在所有属性上取值是否相同

    def isSame(dataSet):
        temp = dataSet[0]
        for data in dataSet:
            i =0
            while i < len(dataSet[0]):
                if temp[i] != data[i]:
                    return 0
                i = i+1
        return 1

    2.6定义函数:创建决策树

    def createTree(dataSet,label,featLabels,G,parentId,edge_name,dataSet_orgin,label_orgin):
        label2 = label[:]
        nowId = G.number_of_nodes()+1                          #记录递归栈中本层的节点编号
        classList = [example[-1] for example in dataSet]       #取分类标签(是否放贷:yes or no)
        if classList.count(classList[0]) == len(classList):    #如果类别完全相同则停止继续划分case1
            print("nowId1==",nowId,"parentId1==",parentId)
            G.add_node(nowId,label=classList[0],fontname="Microsoft YaHei", style="filled",color="#B4E7B7")
            print("edge_name1==",edge_name)
            G.add_edge(parentId,nowId,color="#B4DBFF", penwidth=1.5, fontsize=12,fontname="Microsoft YaHei", label=edge_name)
            return classList[0]
        
        if (len(label) == 0 or isSame(dataSet)):                               #case2:当前属性集为空或者所有样本在所有属性上取值相同,返回出现次数最多的类标签
            maxLabel = majorityCnt(classList)
            G.add_node(nowId,label=maxLabel,fontname="Microsoft YaHei", style="filled",color="#dddddd")
            G.add_edge(parentId,nowId,color="#B4DBFF", penwidth=1.5, fontsize=12,fontname="Microsoft YaHei", label=edge_name)
            return maxLabel
        bestFeat = chooseBestFeatureToSplit(dataSet,label)           #选择最优特征
        print('bestFeat==',bestFeat,'labels==',labels)
        bestFeatLabel = label[bestFeat]                       #最优特征的标签
        #先把这个最优特征的点加到图中
        print("nowId2==",nowId,"parentId2==",parentId)
        G.add_node(nowId,label=bestFeatLabel,fontname="Microsoft YaHei", style="filled",color="#1296db")
        if parentId != -1:
                print('edgename2==',edge_name)
                print("nowId3==",nowId,"parentId3==",parentId)
                G.add_edge(parentId,nowId,color="#B4DBFF", penwidth=1.5, fontsize=12,fontname="Microsoft YaHei", label=edge_name)
        print("bestFeatLabel",bestFeatLabel)
        
        featLabels.append(bestFeatLabel)
        myTree = {bestFeatLabel:{}}                            #根据最优特征的标签生成树
        del(label2[bestFeat])                                  #删除已经使用特征标签
        orginIndex = label_orgin.index(bestFeatLabel)                      #输出最优特征在原始数据集的位置
        featValues = [example[orginIndex] for example in dataSet_orgin]#得到训练集中所有最优特征的属性值
        uniqueVals = set(featValues)                           #去掉重复的属性值
        print("uniqueVals",uniqueVals)
        
        fatherDataSet = []
        for value in uniqueVals:                               #遍历特征,创建决策树。
            newDataSet = splitDataSet(dataSet, bestFeat, value)
            if newDataSet:
                for item in newDataSet:
                    fatherDataSet.append(item)
           
        for value in uniqueVals:                               #遍历特征,创建决策树。
            print("value==",value)
            newDataSet = splitDataSet(dataSet, bestFeat, value)
            if newDataSet:
                #print('newDataSet==',newDataSet)
                myTree[bestFeatLabel][value] = createTree(newDataSet,label2, featLabels,G,nowId,value,dataSet_orgin,label_orgin)
            else:
                #print('fatherDataSet==',fatherDataSet)
                classList = [example[-1] for example in fatherDataSet]
                mlabel = majorityCnt(classList)
                print("mlabel==",mlabel)
                nextId = G.number_of_nodes()+1 
                G.add_node(nextId,label=mlabel,fontname="Microsoft YaHei", style="filled",color="#B4E7B7")
                G.add_edge(nowId,nextId,color="#B4DBFF", penwidth=1.5, fontsize=12,fontname="Microsoft YaHei", label=value)
        return myTree
    

    2.7定义函数:测试模型

    def judge(node,data,labels):
        key=list(node.keys())[0]
        node = node[key]
        idx = labels.index(key)
        pred = None
        for key in node:
            if data[idx] == key:
                if isinstance(node[key],dict):
                    pred = judge(node[key],data,labels)
                else:
                    pred = node[key]
                
        return pred

    2.8划分数据集训练模型

    G = pgh.AGraph()
    #划分数据集
    np.random.shuffle(readyArr)
    offset = int(len(readyArr)*0.9)
    trainData = readyArr[:offset]
    testData = readyArr[offset:]
    featLabels = []
    Trees = createTree(trainData,labels,featLabels,G,-1,'0',trainData,labels)
    print(Trees)
    G.layout()
    G.draw(r'C:\Users\admin\OneDrive\anaconda\c45test.dot')

    2.9测试模型,并计算错误率

    errSum =0
    for data in testData:
        test_result = judge(Trees,data,labels)
        if test_result != data[-1]:
            errSum = errSum +1
    totalNum = len(testData)
    print("出错率为",float(errSum/totalNum))

    3实验总结:

    1. 在决策树生成过程中, 由于为了方便计算决策树分支的最优属性,所以会删除已经作为过最优属性的属性,当某个属性被用到后直接删除后,在后面再使用到该属性时会出现错误。因此,需要改正算法,思路是在递归时,只有在进入分类属性X下一层递归时才会删除当前分类属性X,当前分类属性X平行的节点则不会删除分类属性X.
    2. 分类到某分支时,会出现某属性A的某个取值v没有样本数据的情况,需要将该属性A当前样本的最多的分类作为v的分类。
    3. 另外,也采用sklearn进行训练,对比C4.5算法结果,发现不一样。通过阅读源码,得知sklearn 里面的决策树采用的是基尼指数,而C4.5决策树采用的是信息增益率来选择最优分类属性。

     

     

     

     

     

    更多相关内容
  • 本篇文章主要介绍了Python实现决策树C4.5算法的示例,详解的介绍了决策树C4.5算法的原理和实现代码,非常具有实用价值,需要的朋友可以参考下
  • 文章目录数据选取和数据情况利用C4.5算法分类离散化连续变量C4.5原理C4.5实现应用训练好的决策树分类 数据选取和数据情况 本次实验选取鸢尾花数据集(http://archive.ics.uci.edu/ml/datasets/Iris) 数据包含5列,...
  • C4.5算法java实现

    2017-04-07 10:51:49
    C4.5算法 java实现 详细 界面
  • 下面小编就为大家带来一篇python实现决策树C4.5算法详解(在ID3基础上改进)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • 本文为大家分享了决策树之C4.5算法,供大家参考,具体内容如下 1. C4.5算法简介   C4.5算法是用于生成决策树的一种经典算法,是ID3算法的一种延伸和优化。C4.5算法对ID3算法主要做了一下几点改进:   (1)...
  • 关于C4.5的MATLAB实现,包含数据集在内,可以实现西瓜数据集的分类,比较简陋,大家拿来做个参考吧~
  • 数据挖掘中的决策树C4.5算法的实现,用matlab实现
  • 里面的数据来自UCI库,机器学习C4.5算法完全采用C语言实现
  • 可以完美的实现用于统计学习的算法C4.5分类,完整的matlab程序
  • 数据挖掘算法之C4.5算法 C4.5算法是一种决策树,在ID3基础上实现,解决分类问题,属于监督学习,目标是根据已知的样本——每个样本具有多个不同的属性,属于某一类别,判断给出的元组的类别标签。 决策树的非叶节点...

    数据挖掘算法之C4.5算法

    C4.5算法是一种决策树,在ID3基础上实现,解决分类问题,属于监督学习,目标是根据已知的样本——每个样本具有多个不同的属性,属于某一类别,判断给出的元组的类别标签。
    决策树的非叶节点为属性,分支代表属性值,叶节点为类别标签。
    问题的关键在于如何确定节点——分裂点
    我们的类别预测是由不确定逐步到确定,分裂点应该是对预测结果确定性影响最大的属性,称为样本最优属性。
    信息熵:消除不确定性所需信息量的度量,信息熵越大表明事物随机性越强。

    在这里插入图片描述

    类别信息熵:所有样本中的各种类别出现的不确定性之和,计算方法为
    在这里插入图片描述
    pi为各类别占总样本数的比例
    属性信息熵info:在某一属性(条件)确定的条件下,各类别出现的不确定性之和,相当于剔除了一个不确定性因素,其他剩余属性的不确定性之和,计算方法为属性值占样本总数的比例×该属性值对应的信息熵
    在这里插入图片描述
    信息增益Gain:类别信息熵 - 属性信息熵,表示该属性对信息不确定性的减少程度,信息增益越大,说明该属性对预测结果确定性贡献越大,选择该属性能帮助我们更好更快的完成分类预测。
    ID3利用信息增益来选择分裂点,但是假如每个属性每个类别仅有一个样本,信息熵为0,那么信息增益就无法实现有效区分分裂点。因此C4.5进行改进,引进属性分裂信息度量和信息增益率的概念,利用信息增益率来判断。
    属性分裂信息度量H:计算属性熵,即各属性值占样本总比例qi×log2(qi)之和,表示属性本身的不确定性程度,属性熵越大,属性本身的不确定性越大。
    信息增益率IGR:IGR=Gain/H,表示属性本身的不确定性越大,对最终结果的不确定性减少就越小,消除了属性本身不确定性对预测结果的影响。

    明确判断分裂点的依据后,接下来是阐述算法思想及过程
    1、选择IGR最大的属性作为根节点
    2、判断分枝后类别标签是否一致,若一致,则执行3,不一致则执行4
    3、将相应的类别标签作为该分枝的叶节点输出
    4、继续选择剩余的IGR最大的属性作为分裂点
    5、重复2,直到所有分支都生成叶节点,结束

    剪枝
    在决策树创建时,不可避免的会存在不具有代表性的特例样本数据,剪枝就是为了减少这类数据对最终预测结果的影响,解决过拟合问题。剪枝的方法为统计度量,分为先剪枝和后剪枝。
    先剪枝:提前停止树的构造,即确定终止条件。如决策树的高度,错误率高于某值等
    后剪枝:在决策树构造完成之后根据频繁项集对子树进行合并。
    C4.5采用悲观剪枝法不需要新的数据,通过计算机实现时,表现为函数中的一个参数。

    实例:利用R语言通过C4.5算法完成下列预测

    在这里插入图片描述
    第一步:导入excel数据
    所用的包:CARN ——Packages xlsx #只能读取xlsx格式的文件

    install.package(xlsx)  #下载相关包
    library(xlsx)    #导入相关包
    Ex2<-read.xlsx(file="E:Ex2_DecisionTree_Sampledata.xlsx",1) #读Excel文件,注意file为文件路径,与其他编程语言不同,不需要分号,1为文件中第1个sheet表
    

    导出结果如图

    在这里插入图片描述
    第二步:数据预处理
    特别注意数据预处理的顺序,这里23之间顺序可以调换,但是4一定要放在最后,否则在执行第四步时会出现变量名称不一致的问题。
    1、去掉预测数据行

    Ex2 <- Ex2[-22,]
    

    2、将各属性值替换成数值型数据
    原因是在创建分类树的过程中,J48函数不支持string类型的数据
    在这里插入图片描述

    Ex2$buys_computer <- ifelse(Ex2$buys_computer == "yes",1,2) #这里用ifelse完成替换,左边为要替换的变量,右边参数1为判断条件,参数2是条件为真的替换值,参数2为条件为假的替换值,因为只有两个取值,故使用一个ifelse语句即可实现
    Ex2$age <- ifelse(Ex2$age == "<=30",1,ifelse(Ex2$age == "31…40",2,3))
    Ex2$income <- ifelse(Ex2$income == "high",1,ifelse(Ex2$income =="medium",2,3))
    Ex2$student <- ifelse(Ex2$student == "yes",1,2)
    Ex2$credit_rating <- ifelse(Ex2$credit_rating == "excellent",1,2)
    

    3、将要预测的变量定义为因子
    原因是帮助J48函数识别

    Ex2 <-data.frame(Ex2$age,Ex2$income,Ex2$student,Ex2$credit_rating,factor(Ex2$buys_computer)) #data.frame定义数据框的字段类型,factor()为因子转换函数
    

    4、划分训练集和测试集
    这里按照hold-out方法,2/3为训练集,1/3为测试集
    R语言中进行数据集划分的方法有很多种,这里选用caret包进行划分

    library(caret) #导入所需要的包
    index <- createDataPartition(y=Ex2$Ex2.age,p=2/3,list=FALSE) #这个函数参数的意义:第一个参数y:随机抽取的元组中的某一特定属性值,其中$前为数据表名,后为列名;第二个参数p:随机抽取的元组占总数据的比例,第三个参数list:数据的存储类型
    train <- Ex2[index,] #训练集,从Ex2取出包含index行的所有列
    test <- Ex2[-index,] #测试集,从Ex2去除包含index行的所有列
    

    第三步:创建分类树,并剪枝
    创建决策树的方法有很多,针对C4.5算法,这里运用的是RWeka中的J48函数,调用格式是J48(formula,data,subset,na.action,control=Weka_control(u=T,c=0.25,M=2,R=T,N=3,B=T),options=NULL)
    对相关参数的解释
    U——默认值为TURE,表示不剪枝。
    C——对剪枝过程设置的置信阈值。
    M——默认值为2,表示叶节点最小样本量。
    R——默认值为TURE,表示按错误率递减剪枝。
    N——默认值为3,表示在R=T的情况下,交叉验证的折叠次数。
    B——默认值为T,表示是否建立二叉树。

    library(RWeka) #导入所需要的数据包
    ctree<-J48(factor.Ex2.buys_computer.~.,data=train,control=Weka_control(M=2)) #参数1为待预测因子,其中.~的意思是作为被解释变量,参数2为数据集,参数3为决策树的有关要求
    

    此时,生成的决策树显示如下

    J48 pruned tree
    ------------------
    
    Ex2.income <= 1
    |   Ex2.age <= 1: 2 (2.0)
    |   Ex2.age > 1: 1 (3.0/1.0)
    Ex2.income > 1: 1 (10.0/1.0)
    
    Number of Leaves  :     3
    
    Size of the tree :      5
    

    还需将其可视化,生成树状图

    library(partykit) #用到partykit包
    plot(ctree,type="simple")
    

    在这里插入图片描述

    第四步:运用测试集对生成的决策树进行检验

    pretree<-predict(ctree,newdata=test)#参数1为带预测模型,参数2为测试集
    pretree #预测结果
    [1] 1 1 1 1 1 1 1
    Levels: 1 2
    test$factor.Ex2.buys_computer. #真实结果
    [1] 1 2 2 2 1 1 2
    Levels: 1 2
    

    准确率为42.8,说明模型并不是很理想,可能与选取的训练数据与测试数据有关,多做几次,选择正确率高的模型(这里就不再展示和记录)

    第五步:对要预测的数据进行预测
    这里由于一开始就把待预测数据删除掉,所以,需要重新提取待预测数据,将其赋值给Ex2(必须和之前预处理时的变量一致,因为生成的frame数据框的字段名带有变量名,否则predict函数不能识别)

    Ex2<-read.xlsx(file="E:Ex2_DecisionTree_Sampledata.xlsx",1)
    Ex2<-Ex2[22,]
    Ex2$age <- ifelse(Ex2$age == "<=30",1,ifelse(Ex2$age == "31…40",2,3))
    Ex2$income <- ifelse(Ex2$income == "high",1,ifelse(Ex2$income =="medium",2,3))
    Ex2$student <- ifelse(Ex2$student == "yes",1,2)
    Ex2$credit_rating <- ifelse(Ex2$credit_rating == "excellent",1,2)
    Ex2 <-data.frame(Ex2$age,Ex2$income,Ex2$student,Ex2$credit_rating,factor(Ex2$buys_computer))
    precom <- predict(ctree,newdata=Ex2)
    precom
    [1] 1
    Levels: 1 2
    

    预测结果为买电脑,到此结束~

    展开全文
  • 【资源内容】:Matlab实现决策树C4.5算法 【代码特点】:参数化编程、参数可方便更改、代码编程思路清晰、注释明细 【适用对象】:工科生、数学专业、信号处理专业学生等
  • C4.5算法在选择分裂属性时只考虑了每个条件属性和决策属性之间的关系,而没有考虑到条件属性间的相关性,直接影响构建树的准确率。提出一种基于Kendall和谐系数的C4.5决策树优化算法,用于解决条件属性之间相关性的...
  • C4.5算法源码 c语言实现

    热门讨论 2009-03-21 20:00:39
    c4.5算法实现 用c语言实现 经过调试 可直接使用 在vc下运行
  • 文章来源:http://blog.csdn.net/xuxurui007/article/details/18045943C4.5是机器学习算法中的另一个分类决策树算法,它是基于ID3算法进行改进后的一种重要算法,相比于ID3算法,改进有如下几个要点:用信息增益率来...

    文章来源:http://blog.csdn.net/xuxurui007/article/details/18045943

    C4.5是机器学习算法中的另一个分类决策树算法,它是基于ID3算法进行改进后的一种重要算法,相比于ID3算法,改进有如下几个要点:

    用信息增益率来选择属性。ID3选择属性用的是子树的信息增益,这里可以用很多方法来定义信息,ID3使用的是熵(entropy, 熵是一种不纯度度量准则),也就是熵的变化值,而C4.5用的是信息增益率。

    在决策树构造过程中进行剪枝,因为某些具有很少元素的结点可能会使构造的决策树过适应(Overfitting),如果不考虑这些结点可能会更好。

    对非离散数据也能处理。

    能够对不完整数据进行处理。

    首先,说明一下如何计算信息增益率。

    熟悉了ID3算法后,已经知道如何计算信息增益,计算公式如下所示(来自Wikipedia):

    uid-9162199-id-4880120.html

    或者,用另一个更加直观容易理解的公式计算:

    按照类标签对训练数据集D的属性集A进行划分,得到信息熵:

    uid-9162199-id-4880120.html

    按照属性集A中每个属性进行划分,得到一组信息熵:

    uid-9162199-id-4880120.html

    计算信息增益

    然后计算信息增益,即前者对后者做差,得到属性集合A一组信息增益:

    uid-9162199-id-4880120.html

    这样,信息增益就计算出来了。

    计算信息增益率

    下面看,计算信息增益率的公式,如下所示(来自Wikipedia):

    uid-9162199-id-4880120.html

    其中,IG表示信息增益,按照前面我们描述的过程来计算。而IV是我们现在需要计算的,它是一个用来考虑分裂信息的度量,分裂信息用来衡量属性分 裂数据的广度和均匀程序,计算公式如下所示(来自Wikipedia):

    uid-9162199-id-4880120.html

    简化一下,看下面这个公式更加直观:

    uid-9162199-id-4880120.html

    其中,V表示属性集合A中的一个属性的全部取值。

    我们以一个很典型被引用过多次的训练数据集D为例,来说明C4.5算法如何计算信息增益并选择决策结点。

    44c8c94a1f2906bb13bd8ec570bf28e0.png

    上面的训练集有4个属性,即属性集合A={OUTLOOK, TEMPERATURE, HUMIDITY, WINDY};而类标签有2个,即类标签集合C={Yes, No},分别表示适合户外运动和不适合户外运动,其实是一个二分类问题。

    我们已经计算过信息增益,这里直接列出来,如下所示:

    数据集D包含14个训练样本,其中属于类别“Yes”的有9个,属于类别“No”的有5个,则计算其信息熵:

    1

    Info(D) = -9/14 * log2(9/14) - 5/14 * log2(5/14) = 0.940

    下面对属性集中每个属性分别计算信息熵,如下所示:

    1

    Info(OUTLOOK) = 5/14 * [- 2/5 * log2(2/5) – 3/5 * log2(3/5)] + 4/14 * [ - 4/4 * log2(4/4) - 0/4 * log2(0/4)] + 5/14 * [ - 3/5 * log2(3/5) – 2/5 * log2(2/5)] = 0.694

    2

    Info(TEMPERATURE) = 4/14 * [- 2/4 * log2(2/4) – 2/4 * log2(2/4)] + 6/14 * [ - 4/6 * log2(4/6) - 2/6 * log2(2/6)] + 4/14 * [ - 3/4 * log2(3/4) – 1/4 * log2(1/4)] = 0.911

    3

    Info(HUMIDITY) = 7/14 * [- 3/7 * log2(3/7) – 4/7 * log2(4/7)] + 7/14 * [ - 6/7 * log2(6/7) - 1/7 * log2(1/7)] = 0.789

    4

    Info(WINDY) = 6/14 * [- 3/6 * log2(3/6) – 3/6 * log2(3/6)] + 8/14 * [ - 6/8 * log2(6/8) - 2/8 * log2(2/8)] = 0.892

    根据上面的数据,我们可以计算选择第一个根结点所依赖的信息增益值,计算如下所示:

    1

    Gain(OUTLOOK) = Info(D) - Info(OUTLOOK) = 0.940 - 0.694 = 0.246

    2

    Gain(TEMPERATURE) = Info(D) - Info(TEMPERATURE) = 0.940 - 0.911 = 0.029

    3

    Gain(HUMIDITY) = Info(D) - Info(HUMIDITY) = 0.940 - 0.789 = 0.151

    4

    Gain(WINDY) = Info(D) - Info(WINDY) = 0.940 - 0.892 = 0.048

    接下来,我们计算分裂信息度量H(V):

    OUTLOOK属性

    属性OUTLOOK有3个取值,其中Sunny有5个样本、Rainy有5个样本、Overcast有4个样本,则

    1

    H(OUTLOOK) = - 5/14 * log2(5/14) - 5/14 * log2(5/14) - 4/14 * log2(4/14) = 1.577406282852345

    TEMPERATURE属性

    属性TEMPERATURE有3个取值,其中Hot有4个样本、Mild有6个样本、Cool有4个样本,则

    1

    H(TEMPERATURE) = - 4/14 * log2(4/14) - 6/14 * log2(6/14) - 4/14 * log2(4/14) = 1.5566567074628228

    HUMIDITY属性

    属性HUMIDITY有2个取值,其中Normal有7个样本、High有7个样本,则

    1

    H(HUMIDITY) = - 7/14 * log2(7/14) - 7/14 * log2(7/14) = 1.0

    WINDY属性

    属性WINDY有2个取值,其中True有6个样本、False有8个样本,则

    1

    H(WINDY) = - 6/14 * log2(6/14) - 8/14 * log2(8/14) = 0.9852281360342516

    根据上面计算结果,我们可以计算信息增益率,如下所示:

    1

    IGR(OUTLOOK) = Info(OUTLOOK) / H(OUTLOOK) = 0.246/1.577406282852345 = 0.15595221261270145

    2

    IGR(TEMPERATURE) = Info(TEMPERATURE) / H(TEMPERATURE) = 0.029 / 1.5566567074628228 = 0.018629669509642094

    3

    IGR(HUMIDITY) = Info(HUMIDITY) / H(HUMIDITY) = 0.151/1.0 = 0.151

    4

    IGR(WINDY) = Info(WINDY) / H(WINDY) = 0.048/0.9852281360342516 = 0.048719680492692784

    根据计算得到的信息增益率进行选择属性集中的属性作为决策树结点,对该结点进行分裂。

    C4.5算法的优点是:产生的分类规则易于理解,准确率较高。

    C4.5算法的缺点是:在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。

    参考链接

    quote:

    展开全文
  • C4.5算法详解

    2021-03-29 15:10:12
    首先,C4.5是决策树算法的一种。决策树算法作为一种分类算法,目标就是将具有p维特征的n个样本分到c个类别中去。相当于做一个投影,c=f(n),将样本经过一种变换赋予一种类别标签...下面主要针对C4.5算法,我们用一个例

    本文转载自:https://blog.csdn.net/zjsghww/article/details/51638126

    首先,C4.5是决策树算法的一种。决策树算法作为一种分类算法,目标就是将具有p维特征的n个样本分到c个类别中去。相当于做一个投影,c=f(n),将样本经过一种变换赋予一种类别标签。决策树为了达到这一目的,可以把分类的过程表示成一棵树,每次通过选择一个特征pi来进行分叉。

    那么怎样选择分叉的特征呢?每一次分叉选择哪个特征对样本进行划分可以最快最准确的对样本分类呢?不同的决策树算法有着不同的特征选择方案。ID3用信息增益,C4.5用信息增益率,CART用gini系数。

    下面主要针对C4.5算法,我们用一个例子来计算一下。


                                                                                                                                                       
    上述数据集有四个属性,属性集合A={ 天气,温度,湿度,风速}, 类别标签有两个,类别集合L={进行,取消}。


    1. 计算类别信息熵

    类别信息熵表示的是所有样本中各种类别出现的不确定性之和。根据熵的概念,熵越大,不确定性就越大,把事情搞清楚所需要的信息量就越多。

    2. 计算每个属性的信息熵
    每个属性的信息熵相当于一种条件熵。他表示的是在某种属性的条件下,各种类别出现的不确定性之和。属性的信息熵越大,表示这个属性中拥有的样本类别越不“纯”。

    3. 计算信息增益

    信息增益的 = 熵 - 条件熵,在这里就是 类别信息熵 - 属性信息熵,它表示的是信息不确定性减少的程度。如果一个属性的信息增益越大,就表示用这个属性进行样本划分可以更好的减少划分后样本的不确定性,当然,选择该属性就可以更快更好地完成我们的分类目标。

    信息增益就是ID3算法的特征选择指标。


    但是我们假设这样的情况,每个属性中每种类别都只有一个样本,那这样属性信息熵就等于零,根据信息增益就无法选择出有效分类特征。所以,C4.5选择使用信息增益率对ID3进行改进。

    4.计算属性分裂信息度量

    用分裂信息度量来考虑某种属性进行分裂时分支的数量信息和尺寸信息,我们把这些信息称为属性的内在信息(instrisic information)。信息增益率用信息增益 / 内在信息,会导致属性的重要性随着内在信息的增大而减小(也就是说,如果这个属性本身不确定性就很大,那我就越不倾向于选取它),这样算是对单纯用信息增益有所补偿。


    5. 计算信息增益率

    (下面写错了。。应该是IGR = Gain / H )

    天气的信息增益率最高,选择天气为分裂属性。发现分裂了之后,天气是“阴”的条件下,类别是”纯“的,所以把它定义为叶子节点,选择不“纯”的结点继续分裂。
                                                         

                         

                                                             

    在子结点当中重复过程1~5。

    以天气=“雨”的子结点为例:

    1. 计算类别信息熵

    2. 计算每个属性的信息熵 


    3. 计算信息增益

    4.计算属性分裂信息度量

    5. 计算信息增益率

    (下面写错了。。应该是IGR = Gain / H )


    风速属性的信息增益率最高,所以选择风速作为分裂结点,分裂之后,发现子结点都是纯的,因此子节点均为叶子节点,分裂结束。
    至此,这个数据集上C4.5的计算过程就算完成了,一棵树也构建出来了。


    现在我们来总结一下C4.5的算法流程:

    展开全文
  • 决策树算法--C4.5算法

    千次阅读 2020-05-10 21:28:40
    C4.5算法是用于生成决策树的一种经典算法,是ID3算法的一种延伸和优化。C4.5算法对ID3算法进行了改进 ,改进点主要有: 用信息增益率来选择划分特征,克服了用信息增益选择的不足,但信息增益率对可取值数目较少的...
  • [Information Gain][equtation][equtation]: http://latex.codecogs.com/svg.latex?g_r(D,A)=H(D)-H(D|A)ID3算法在选择根节点和内部节点中的分支属性时,采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值...
  • 以已投入使用的健身俱乐部管理系统为背景,提出了用C4.5决策树分类算法对健身记录进行数据挖掘。通过该方法找出俱乐部在有效期内的会员的年龄段、性别、会员卡类型和参与健身时间段的规律,提取特定时间段内参与健身...
  • 融合GINI指数的C4.5算法的分类研究
  • Quinlan s C4.5 算法的实现-the implementation of C4.5 [教學文件]
  • 决策树C4.5算法

    千次阅读 2021-11-29 08:54:41
    C4.5算法在ID3算法上做了提升,使用信息增益比来构造决策树,且有剪枝功能防止过拟合,本模块将以C4.5算法介绍决策树的构造策略。 欠拟合:训练得到的模型在训练集集测试中表现就很差,准确度很低。 过拟合:训练...
  • 基于C4.5算法和AdaBoost算法的P2P流量识别方法,韩颜伦,李学明,针对目前互联网主要的四种P2P应用,提出一种基于C4.5算法和AdaBoost算法的P2P流量识别方法。C4.5算法根据最大信息增益率原则生成决策树��
  • 主要为大家详细介绍了python实现C4.5决策树算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • C4.5算法

    千次阅读 2017-05-07 13:44:45
    C4.5是另一个分类决策树算法,基于ID3算法进行改进,相比于ID3算法有如下几个要点: 用信息增益率来选择属性。ID3选择属性用的是子树的信息增益,ID3使用的是熵(entropy, 熵是一种不纯度度量准则),也就是熵的...
  • C4.5算法C4.5算法

    2007-12-10 13:17:48
    C4.5算法 C4.5算法 <br>C4.5算法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 55,871
精华内容 22,348
关键字:

C4.5算法