精华内容
下载资源
问答
  • ID3算法流程

    千次阅读 2019-07-25 11:30:52
    ID3是一棵多叉树,这一棵树采用递归的方式构造 第一步根节点的构造,遍历所有特征,找到那个使分类信息增益最大的特征,将其设置为根节点,并且讲这个feature删除掉 由于根节点已经将数据分叉,递归的方式寻找每个...

    git链接

    ID3是一棵多叉树,这一棵树采用递归的方式构造

    1. 第一步根节点的构造,遍历所有特征,找到那个使分类信息增益最大的特征,将其设置为根节点,并且讲这个feature删除掉
    2. 由于根节点已经将数据分叉,递归的方式寻找每个分枝的最优特征3
    3. id3采用信息增益来选取最优分裂特征
    #ID3算法
    def ID3_chooseBestFeatureToSplit(dataset):
        numFeatures=len(dataset[0])-1
        baseEnt=jisuanEnt(dataset)
        bestInfoGain=0.0
        bestFeature=-1
        for i in range(numFeatures): #遍历所有特征
            #for example in dataset:
                #featList=example[i]  
            featList=[example[i]for example in dataset]
            uniqueVals=set(featList) #将特征列表创建成为set集合,元素不可重复。创建唯一的分类标签列表
            newEnt=0.0
            for value in uniqueVals:     #计算每种划分方式的信息熵
                subdataset=splitdataset(dataset,i,value)
                p=len(subdataset)/float(len(dataset))
                newEnt+=p*jisuanEnt(subdataset)
            infoGain=baseEnt-newEnt
    #        print(u"ID3中第%d个特征的信息增益为:%.3f"%(i,infoGain))
            if (infoGain>bestInfoGain):
                bestInfoGain=infoGain    #计算最好的信息增益
                bestFeature=i
        return bestFeature   
    
    #利用ID3算法创建决策树
    def ID3_createTree(dataset,labels):
        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 = ID3_chooseBestFeatureToSplit(dataset)
        bestFeatLabel = labels[bestFeat]
    #    print(u"此时最优索引为:"+(bestFeatLabel))
        ID3Tree = {bestFeatLabel:{}}
        
    #    print(bestFeatLabel)
        
        del(labels[bestFeat])
        # 得到列表包括节点所有的属性值
        featValues = [example[bestFeat] for example in dataset]
        uniqueVals = set(featValues)
        for value in uniqueVals:
            subLabels = labels[:]
            #################################递归
            
            sub_dataset=splitdataset(dataset, bestFeat, value)
            ID3Tree[bestFeatLabel][value] = ID3_createTree(sub_dataset, subLabels)
            print(ID3Tree)
        return ID3Tree 
    
    展开全文
  • MP3的ID3解析

    千次阅读 2012-10-22 10:16:57
    其中:v1版的ID3在mp3文件的末尾128字节,以TAG三个字符开头,后面跟上歌曲信息。 v2版一般位于mp3的开头,可以存储歌词,该专辑的图片等大容量的信息。  但ID3并不是MP3标签的ISO国际标准,ID3的各种版本目前...

    其中:v1版的ID3在mp3文件的末尾128字节,以TAG三个字符开头,后面跟上歌曲信息。

    v2版一般位于mp3的开头,可以存储歌词,该专辑的图片等大容量的信息。

     但ID3并不是MP3标签的ISO国际标准,ID3的各种版本目前只是一个近乎事实上的标准,并没有人强迫播放器或者编码程序必须支持它。

    ID3V1大概有两个版本,由于ID3V1.0没有包括曲目序号的定义,所以Michael Mutschler在1997年进行了改进,引入了版本1.1。通过占用备注字段的最后两个字节,用一个00字节作标记,另一个字节改为序号,可以让ID3支持曲目编号了。一个字节的空间让ID3 V1.1支持最高到255的曲目序号,考虑到一张唱片超过256个曲目的可能性极小,这个改进还是相当合理的。但ID3V1只有128个字节可以使用,如果要在MP3中储存更多的信息,比如歌词,专辑图片等,显然是无法达到的,于是产生了ID3V2。ID3V2到现在一共有4个版本,但流行的播放软件一般只支持第3版,既ID3v2.3。由于ID3V1记录在MP3文件的末尾,ID3V2就只好记录在MP3文件的首部了。也正是由于这个原因,对ID3V2的操作比ID3V1要慢。而且ID3V2结构比ID3V1的结构要复杂得多,但比前者全面且可以伸缩和扩展。

    但我们只需要读出MP3的TITLE,所以只要解析IDV1就够了,这里不对IDV2做过多说明,其实我也没有深入研究IDV2。

    ID3V1的内容和每个标签占用的字节说明如下:

    char Header[3];    /*标签头必须是"TAG"否则认为没有标签*/
    char Title[30];    /*标题*/
    char Artist[30];   /*作者*/
    char Album[30];    /*专集*/
    char Year[4];    /*出品年代*/
    char Comment[30];   /*备注*/
    char Genre;    /*类型*/

    可以定义一个如下的结构来存储MP3信息:

    typedef struct _MP3INFO //MP3信息的结构
    {
     char Identify[3]; //TAG三个字母
     //这里可以用来鉴别是不是文件信息内容
     char Title[31];   //歌曲名,30个字节
     char Artist[31];  //歌手名,30个字节
     char Album[31];   //所属唱片,30个字节
     char Year[5];   //年,4个字节
     char Comment[29]; //注释,28个字节
     unsigned char reserved;  //保留位,1个字节
     unsigned char reserved2; //保留位,1个字节
     unsigned char reserved3; //保留位,1个字节
    } MP3INFO;
    代码可以简单如下:

     #include "stdlib.h"
    #include "stdio.h"
    #include "windows.h"
    #define MAX 128

    typedef struct _MP3INFO //MP3信息的结构
    {
     char Identify[3]; //TAG三个字母
     //这里可以用来鉴别是不是文件信息内容
     char Title[31];   //歌曲名,30个字节
     char Artist[31];  //歌手名,30个字节
     char Album[31];   //所属唱片,30个字节
     char Year[5];   //年,4个字节
     char Comment[29]; //注释,28个字节
     unsigned char reserved;  //保留位,1个字节
     unsigned char reserved2; //保留位,1个字节
     unsigned char reserved3; //保留位,1个字节
    } MP3INFO;

    int main(int argc, char* argv[])
    {
     FILE * fp;
     unsigned char mp3tag[128] = {0};
        MP3INFO mp3info;
     char oldname[MAX],newname[MAX],cmd[MAX];


     fp = fopen("G://mp3//Debug//5.mp3","rb");
     if (NULL==fp)
     {
      printf("open read file error!!");
      return 1;
     }
     fseek(fp,-128,SEEK_END);
     fread(&mp3tag,1,128,fp);
        if(!((mp3tag[0] == 'T'|| mp3tag[0] == 't')
      &&(mp3tag[1] == 'A'|| mp3tag[1] == 'a')
      &&(mp3tag[2] == 'G'|| mp3tag[0] == 'g')))
     {
         printf("mp3 file is error!!");
      fclose(fp) ;
      return 1;
     }

     memcpy((void *)mp3info.Identify,mp3tag,3); //获得tag
     memcpy((void *)mp3info.Title,mp3tag+3,30); //获得歌名
     memcpy((void *)mp3info.Artist,mp3tag+33,30); //获得作者
     memcpy((void *)mp3info.Album,mp3tag+63,30); //获得唱片名
     memcpy((void *)mp3info.Year,mp3tag+93,4); //获得年
     memcpy((void *)mp3info.Comment,mp3tag+97,28); //获得注释
     memcpy((void *)&mp3info.reserved,mp3tag+125,1); //获得保留
     memcpy((void *)&mp3info.reserved2,mp3tag+126,1);
     memcpy((void *)&mp3info.reserved3,mp3tag+127,1);
     fclose(fp);
     if (strlen(mp3info.Title) == 0)
     {
      printf("title is null/n");
      return 1;
     }
        strcpy(oldname,"5.mp3");
     sprintf(newname,"%s.mp3",mp3info.Title);
     sprintf(cmd,"rename G://mp3//Debug//%s %s",oldname,newname);
     printf("%s/n", cmd);
     system(cmd);


     return 0;
    }

    展开全文
  • 决策树算法——ID3算法(Python3实现)

    千次阅读 多人点赞 2018-07-19 16:57:30
    2、使用ID3算法递归构建决策树并使用决策树执行分类 2.1 ID3算法概述 2.2 递归终止的条件: 2.3 代码实现如下: 3、Matplotlib实现决策树可视化 4、决策树的存储与读取 5、决策树优点和缺点 1、数据集准备 ...

    目录

    1、数据集准备

    2、使用ID3算法递归构建决策树并使用决策树执行分类

    2.1 ID3算法概述

    2.2 递归终止的条件:

    2.3 代码实现如下:

    3、Matplotlib实现决策树可视化

    4、决策树的存储与读取

    5、决策树优点和缺点


    1、数据集准备

                                                                           贷款申请样本数据表

    1

    青年

    一般

    2

    青年

    3

    青年

    4

    青年

    一般

    5

    青年

    一般

    6

    中年

    一般

    7

    中年

    8

    中年

    9

    中年

    非常好

    10

    中年

    非常好

    11

    老年

    非常好

    12

    老年

    13

    老年

    14

    老年

    非常好

    15

    老年

    一般

    先对数据集进行属性标注:

    • 年龄:0代表青年,1代表中年,2代表老年;
    • 有工作:0代表否,1代表是;
    • 有自己的房子:0代表否,1代表是;
    • 信贷情况:0代表一般,1代表好,2代表非常好;
    • 类别(是否给贷款):no代表否,yes代表是。

    2、使用ID3算法递归构建决策树并使用决策树执行分类

    2.1 ID3算法概述

            ID3算法的核心是在决策树各个结点上对应信息增益准则选择特征,递归地构建决策树。

            具体方法是:从根结点(root node)开始,对结点计算所有可能的特征的信息增益,选择信息增益最大的特征作为结点的特征,由该特征的不同取值建立子节点;再对子结点递归地调用以上方法,构建决策树;直到所有特征的信息增益均很小或没有特征可以选择为止,最后得到一个决策树。ID3相当于用极大似然法进行概率模型的选择。

    2.2 递归终止的条件:

    (1)所有类的标签完全相同,则直接返回该类标签。

    (2)使用完所有即当前属性集为空,仍不能将数据集划分成仅包含唯一类别的分组,则挑选出现次数最多的类别作为返回值。

    2.3 代码实现如下:

    # -*- coding: UTF-8 -*-
    from math import log
    import operator
    
    
    
    """
    函数说明:创建测试数据集
    """
    def createDataSet():
        dataSet = [[0, 0, 0, 0, 'no'],         #数据集
                   [0, 0, 0, 1, 'no'],
                   [0, 1, 0, 1, 'yes'],
                   [0, 1, 1, 0, 'yes'],
                   [0, 0, 0, 0, 'no'],
                   [1, 0, 0, 0, 'no'],
                   [1, 0, 0, 1, 'no'],
                   [1, 1, 1, 1, 'yes'],
                   [1, 0, 1, 2, 'yes'],
                   [1, 0, 1, 2, 'yes'],
                   [2, 0, 1, 2, 'yes'],
                   [2, 0, 1, 1, 'yes'],
                   [2, 1, 0, 1, 'yes'],
                   [2, 1, 0, 2, 'yes'],
                   [2, 0, 0, 0, 'no']]
        labels = ['年龄', '有工作', '有自己的房子', '信贷情况']        #分类属性
        return dataSet, labels                           #返回数据集和分类属性
    
    
    """
    函数说明:计算给定数据集的经验熵(香农熵)
    Parameters:
        dataSet - 数据集
    Returns:
        shannonEnt - 经验熵(香农熵)
    """
    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                                #返回经验熵(香农熵)
    
    
    """
    函数说明:按照给定特征划分数据集
    Parameters:
        dataSet - 待划分的数据集
        axis - 划分数据集的特征
        value - 需要返回的特征的值
    """
    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                                   #返回划分后的数据集
    
    
    """
    函数说明:选择最优特征
    Parameters:
        dataSet - 数据集
    Returns:
        bestFeature - 信息增益最大的(最优)特征的索引值
    """
    def chooseBestFeatureToSplit(dataSet):
        numFeatures = len(dataSet[0]) - 1                     #特征数量
        baseEntropy = calcShannonEnt(dataSet)                 #计算数据集的香农熵
        bestInfoGain = 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                                   #经验条件熵
            for value in uniqueVals:                           #计算信息增益
                subDataSet = splitDataSet(dataSet, i, value)           #subDataSet划分后的子集
                prob = len(subDataSet) / float(len(dataSet))           #计算子集的概率
                newEntropy += prob * calcShannonEnt(subDataSet)        #根据公式计算经验条件熵
            infoGain = baseEntropy - newEntropy                        #信息增益
            print("第%d个特征的增益为%.3f" % (i, infoGain))             #打印每个特征的信息增益
            if (infoGain > bestInfoGain):                              #计算信息增益
                bestInfoGain = infoGain                                #更新信息增益,找到最大的信息增益
                bestFeature = i                                        #记录信息增益最大的特征的索引值
        return bestFeature                                             #返回信息增益最大的特征的索引值
    
    
    """
    函数说明:统计classList中出现此处最多的元素(类标签)
    Parameters:
        classList - 类标签列表
    Returns:
        sortedClassCount[0][0] - 出现此处最多的元素(类标签)
    """
    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中出现次数最多的元素
    
    
    """
    函数说明:递归构建决策树
    Parameters:
        dataSet - 训练数据集
        labels - 分类属性标签
        featLabels - 存储选择的最优特征标签
    Returns:
        myTree - 决策树
    """
    def createTree(dataSet, labels, featLabels):
        classList = [example[-1] for example in dataSet]               #取分类标签(是否放贷:yes or no)
        if classList.count(classList[0]) == len(classList):            #如果类别完全相同则停止继续划分
            return classList[0]
        if len(dataSet[0]) == 1:                                       #遍历完所有特征时返回出现次数最多的类标签
            return majorityCnt(classList)
        bestFeat = chooseBestFeatureToSplit(dataSet)                   #选择最优特征
        bestFeatLabel = labels[bestFeat]                               #最优特征的标签
        featLabels.append(bestFeatLabel)
        myTree = {bestFeatLabel:{}}                                    #根据最优特征的标签生成树
        del(labels[bestFeat])                                          #删除已经使用特征标签
        featValues = [example[bestFeat] for example in dataSet]        #得到训练集中所有最优特征的属性值
        uniqueVals = set(featValues)                                   #去掉重复的属性值
        for value in uniqueVals:
            subLabels=labels[:]
            #递归调用函数createTree(),遍历特征,创建决策树。
            myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels, featLabels)
        return myTree
    
    
    """
    函数说明:使用决策树执行分类
    Parameters:
        inputTree - 已经生成的决策树
        featLabels - 存储选择的最优特征标签
        testVec - 测试数据列表,顺序对应最优特征标签
    Returns:
        classLabel - 分类结果
    """
    def classify(inputTree, featLabels, testVec):
        firstStr = next(iter(inputTree))             #获取决策树结点
        secondDict = inputTree[firstStr]             #下一个字典
        featIndex = featLabels.index(firstStr)
        for key in secondDict.keys():
            if testVec[featIndex] == key:
                if type(secondDict[key]).__name__ == 'dict':
                    classLabel = classify(secondDict[key], featLabels, testVec)
                else:
                    classLabel = secondDict[key]
        return classLabel
    
    
    if __name__ == '__main__':
        dataSet, labels = createDataSet()
        featLabels = []
        myTree = createTree(dataSet, labels, featLabels)
        print(myTree)
        testVec = [0, 1]     # 测试数据
        result = classify(myTree, featLabels, testVec)
        if result == 'yes':
            print('放贷')
        if result == 'no':
            print('不放贷')

    结果如下:

    3、Matplotlib实现决策树可视化

    代码如下:

    import matplotlib.pyplot as plt
    from matplotlib.font_manager import FontProperties
    from matplotlib.font_manager import FontProperties
    import matplotlib.pyplot as plt
    
    
    #定义文本框和箭头格式
    decisionNode=dict(boxstyle='sawtooth',fc='0.8')
    leafNode=dict(boxstyle='round4',fc='0.8')
    arrow_args=dict(arrowstyle='<-')
    #设置中文字体
    font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=14)
    
    
    """
    函数说明:获取决策树叶子结点的数目
    Parameters:
        myTree - 决策树
    Returns:
        numLeafs - 决策树的叶子结点的数目
    """
    def getNumLeafs(myTree):
        numLeafs = 0                   #初始化叶子
        # python3中myTree.keys()返回的是dict_keys,不在是list,所以不能使用myTree.keys()[0]的方法获取结点属性,
        # 可以使用list(myTree.keys())[0]
        firstStr = next(iter(myTree))
        secondDict = myTree[firstStr]                      #获取下一组字典
        for key in secondDict.keys():
            if type(secondDict[key]).__name__=='dict':     #测试该结点是否为字典,如果不是字典,代表此结点为叶子结点
                numLeafs += getNumLeafs(secondDict[key])
            else:
                numLeafs +=1
        return numLeafs
    
    
    """
    函数说明:获取决策树的层数
    Parameters:
        myTree - 决策树
    Returns:
        maxDepth - 决策树的层数
    """
    def getTreeDepth(myTree):
        maxDepth = 0                                  #初始化决策树深度
        # python3中myTree.keys()返回的是dict_keys,不在是list,所以不能使用myTree.keys()[0]的方法获取结点属性,
        # 可以使用list(myTree.keys())[0]
        firstStr = next(iter(myTree))
        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
    
    
    """
    函数说明:绘制结点
    Parameters:
        nodeTxt - 结点名
        centerPt - 文本位置
        parentPt - 标注的箭头位置
        nodeType - 结点格式
    """
    def plotNode(nodeTxt, centerPt, parentPt, nodeType):
        arrow_args = dict(arrowstyle="<-")                                          #定义箭头格式
        font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=14)        #设置中文字体
        createPlot.ax1.annotate(nodeTxt, xy=parentPt,  xycoords='axes fraction',    #绘制结点
                                xytext=centerPt, textcoords='axes fraction',
                                va="center", ha="center", bbox=nodeType, arrowprops=arrow_args,fontproperties=font)
    
    
    """
    函数说明:标注有向边属性值
    Parameters:
        cntrPt、parentPt - 用于计算标注位置
        txtString - 标注的内容
    """
    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)
    
    
    """
    函数说明:绘制决策树
    Parameters:
        myTree - 决策树(字典)
        parentPt - 标注的内容
        nodeTxt - 结点名
    """
    def plotTree(myTree, parentPt, nodeTxt):
        decisionNode = dict(boxstyle="sawtooth", fc="0.8")                                    #设置结点格式
        leafNode = dict(boxstyle="round4", fc="0.8")                                          #设置叶结点格式
        numLeafs = getNumLeafs(myTree)                                                        #获取决策树叶结点数目,决定了树的宽度
        depth = getTreeDepth(myTree)                                                          #获取决策树层数
        firstStr = next(iter(myTree))                                                         #下个字典
        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                                   #y偏移
        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
    
    
    """
    函数说明:创建绘制面板
    Parameters:
        inTree - 决策树(字典)
    """
    def createPlot(inTree):
        fig = plt.figure(1, facecolor='white')                               #创建fig
        fig.clf()                                                            #清空fig
        axprops = dict(xticks=[], yticks=[])
        createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)          #去掉x、y轴
        plotTree.totalW = float(getNumLeafs(inTree))                         #获取决策树叶结点数目
        plotTree.totalD = float(getTreeDepth(inTree))                        #获取决策树层数
        plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0;           #x偏移
        plotTree(inTree, (0.5,1.0), '')                                      #绘制决策树
        plt.show()
    
    
    if __name__=='__main__':
        mytree={'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}
        createPlot(mytree)

    可视化结果:

     

    4、决策树的存储与读取

    代码如下:

    # -*- coding: UTF-8 -*-
    import pickle
    
    
    """
    函数说明:存储决策树
    Parameters:
        inputTree - 已经生成的决策树
        filename - 决策树的存储文件名
    """
    def storeTree(inputTree,filename):
        with open(filename,'wb') as fw:
            pickle.dump(inputTree,fw)
    
    
    """
    函数说明:读取决策树
    Parameters:
        filename - 决策树的存储文件名
    Returns:
        pickle.load(fr) - 决策树字典
    """
    def grabTree(filename):
        with open(filename,'rb') as fr:
            return pickle.load(fr)
    
    if __name__ == '__main__':
        myTree = {'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}
        storeTree(myTree, 'classifierStorage.txt')
        myTree01 = grabTree('classifierStorage.txt')
        print(myTree01)

    结果如下:

    5、决策树优点和缺点

    优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据

    缺点:可能会产生过度匹配问题(过拟合)

     

     

     

     

     

    展开全文
  • 决策树之 ID3 算法

    万次阅读 多人点赞 2016-07-06 13:05:54
    ID3 算法是构建决策树算法中一种非常重要的算法,可以说它是学习决策树算法的基础吧。比如,下一篇博客要说的 C4.5 决策树,就是基于 ID3 上的一个改进算法。还有 CART、随机森林算法,都是后面要讲解的。

    概述

    ID3 算法是构建决策树算法中一种非常重要的算法,可以说它是学习决策树算法的基础吧。比如,下一篇博客要说的 C4.5 决策树,就是基于 ID3 上的一个改进算法。还有 CART、随机森林算法,都是后面要讲解的。


    版权说明

    著作权归作者所有。
    商业转载请联系作者获得授权,非商业转载请注明出处。
    本文作者:Q-WHai
    发表日期: 2016年7月6日
    本文链接:https://qwhai.blog.csdn.net/article/details/51837983
    来源:CSDN
    更多内容:分类 >> 数据挖掘


    引言

    如果你是刚刚才接触到有关决策树的相关内容,那么你可能就会有一些疑问,什么是决策树?对于什么是决策树这个话题,如果站在编程的角度来类比,我想 if … else 是最贴切的了吧。就比如下面的这样的一棵最简单的决策树。
    这里写图片描述
    这是一棵是否出门打球的决策树,而决策的特征属性就是 Weather,如果天气状态为 Sunny、Overcast 则选择出门打球;如果下雨了那就只能待在家里了。
    如果上面的这棵决策树是按照我的选择来构建的,那么你的选择又会构建成一棵什么样的决策树呢?也就是说某一棵决策树只能代表某一种情况,可是我们是想拿构建好的决策树进行预测的,所以这时,就不能再只按照某一个人的意愿来构建决策树了。我们需要收集大量的训练数据,并使用这些训练数据进行构建决策树。


    基础知识

    数据挖掘的基础是数学,如果数学不太好,就一定要好好补补了(我也是数学不太好的那些人当中的一个)。ID3 算法当然也不例外地涉及了一些数学知识。主要的是两块内容:信息熵与信息增益。

    信息熵

    信息熵简介

    中学时期,我们都有学习过熵的概念,主要是在物理跟化学中。在物理学科中,熵是用来描述分子的混乱程度的,在化学学科中也是类似的,如果我没有记错的话,当时熵在化学中的应用主要是某一化合物的加热这一块,比如给水加热,会变化水蒸汽,这时熵就是增大的;还就是化合反应这一块。
    那么在本文的 ID3 算法中,或者说在数据挖掘中的信息熵要怎么理解或是怎么应用呢?这里不妨打个最简单的比方,我们说假设有两篇文章,分别为:Article_1 和 Article_2,它们的内容如下:
    Article_1

    信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵
    信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵
    信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵
    信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵信息熵
    

    Article_2

    信息论之父 C. E. Shannon 在 1948 年发表的论文“通信的数学理论( A Mathematical Theory of Communication )”中, Shannon 指出,任何信息都存在冗余,冗余大小与信息中每个符号(数字、字母或单词)的出现概率或者说不确定性有关。
    Shannon 借鉴了热力学的概念,把信息中排除了冗余后的平均信息量称为“信息熵”,并给出了计算信息熵的数学表达式。
    

    对于上面的这两篇文章,我们要怎么衡量其信息量呢?文章的字数么?显然不是的,第一篇文章的字数要比第二篇文章的字数要多,然而其包含的信息量却要小一些。于是,信息熵的概念就此被引出,结合上面对熵的描述,你也可以理解成信息熵就是信息的混乱程度。

    信息熵公式

    假如一个随机变量 X 的取值为 X = {x1,x1,...,xn{x_1, x_1, ..., x_n}x1,x1,...,xn},每一种取到的概率分别是 {p1,p1,...,pn{p_1, p_1, ..., p_n}p1,p1,...,pn},那么 X 的熵定义为
    H(x)=−∑i=1npilog2pi {H(x) = - \sum_{i=1}^{n}{p_i}{log_2}{p_i}} H(x)=i=1npilog2pi

    信息增益

    信息增益简介

    信息增益的功能是描述一个特征属性对于总体的重要性,怎么理解这句话呢?打个比方吧,比如我想出去打球,这里可能会受到天气、温度、心情等等的因素地影响。那么对于天气这个特征属性而言,有天气这个属性跟没有天气这个属性,总体的信息量(也就是信息熵)的变化就是信息增益了。
    可能这里还不太清楚信息增益在决策树的构建中产生了什么作用,这个问题我们留到 ID3 算法部分再详细说明。

    信息增益公式

    IG(S∣T)=Entropy(S)−∑value(T)∣Sv∣SEntropy(Sv) {IG(S|T) = Entropy(S) - \sum_{value(T)}{\frac{|S_v|}{S}}{Entropy(S_v)} } IG(ST)=Entropy(S)value(T)SSvEntropy(Sv)
    其中 S 为全部样本集合,value(T) 是属性 T 所有取值的集合,v 是 T 的其中一个属性值,Sv{S_v}Sv是 S 中属性 T 的值为 v 的样例集合,∣Sv∣{|S_v|}SvSv{S_v}Sv 中所含样例数。


    ID3

    决策树构建分析

    ID3 是数据挖掘中的一种非常重要的决策树构建算法,它是一种监督学习式的机器学习。由于这是一种监督学习,所以必然需要有一定数量的训练数据集,而每一条训练数据所形成的决策树都不一定是完全一样的。打个比方,假设有如下三条训练数据:

    Day OutLook Temperature Humidity Wind PlayTennis
    1 Sunny Hot High Weak No
    2 Sunny Hot High Strong No
    3 Rainy Mild High Weak Yes

    那么对于 OutLook 这一特征属性而言,就有两种不同的状态值:Sunny 和 Rainy。就算是对于同一个 OutLook 状态值时,其结果分类也是一样的,这样我们构建的决策的标准是什么呢?

    训练数据集

    假设我们如下训练数据集

    Day OutLook Temperature Humidity Wind PlayTennis
    1 Sunny Hot High Weak No
    2 Sunny Hot High Strong No
    3 Overcast Hot High Weak Yes
    4 Rainy Mild High Weak Yes
    5 Rainy Cool Normal Weak Yes
    6 Rainy Cool Normal Strong No
    7 Overcast Cool Normal Strong Yes
    8 Sunny Mild High Weak No
    9 Sunny Cool Normal Weak Yes
    10 Rainy Mild Normal Weak Yes
    11 Sunny Mild Normal Strong Yes
    12 Overcast Mild High Strong Yes
    13 Overcast Hot Normal Weak Yes
    14 Rainy Mild High Strong No

    决策树构建过程

    下面是我根据 ID3 构建决策树的算法步骤,绘制的决策树构建过程图。因为 ID3 其实是一个迭代的算法,这里我只绘制了一次迭代的过程,所以是一个局部示图。
    这里写图片描述
    当上面的局部过程中的最后一步计算出了最大信息增益之后,我们要将这个最大信息增益对应的特征属性进行移除,并将数据集切分成 N 个部分(其中 N 为分支状态数)。
    现在假设我们计算出当选择特征属性为 OutLook 的时候,其信息增益最大,那么原始数据就会被切分成如下 3 份:
    part_sunny

    Day Temperature Humidity Wind PlayTennis
    1 Hot High Weak No
    2 Hot High Strong No
    3 Mild High Weak No
    4 Cool Normal Weak Yes
    5 Mild Normal Strong Yes

    part_overcast

    Day Temperature Humidity Wind PlayTennis
    1 Hot High Weak Yes
    2 Cool Normal Strong Yes
    3 Mild High Strong Yes
    4 Hot Normal Weak Yes

    part_rainy

    Day Temperature Humidity Wind PlayTennis
    1 Mild High Weak Yes
    2 Cool Normal Weak Yes
    3 Cool Normal Strong No
    4 Mild Normal Weak Yes
    5 Mild High Strong No

    这样再把这 3 份数据分别当成上图中的 data 代入计算。通过这样循环地迭代,直到数据被全部计算完成。

    计算步骤

    如果上面信息熵跟信息增益的计算公式,让你看得有一些不是很懂,没关系。这里我会通过几个示例来分析一下计算过程,这样你就会更懂一些了。

    1. Entropy(S)
    2. Entropy(Ti{T_i}Ti)
    3. Entropy(S|T)
    4. IG(T)

    Entropy(S)

    对于最初始的 14 条记录,我们统计了结果分类,其中,Yes = 9,No = 5.
    这时当前信息的信息熵计算过程如下:
    $ {Entropy(S) = -\frac{9}{14} log_2\frac{9}{14} - \frac{5}{14} log_2\frac{5}{14} = 0.940286 } $

    Entropy(Ti{T_i}Ti)

    假设这时我们需要计算最初始的 14 条记录中,特征属性为 OutLook 的分支状态信息熵。首先需要做的是,统计 OutLook 特征属性下的结果分类分布。

    Sunny Overcast Rainy
    Yes 2 4 3
    No 3 0 2

    各个特征属性下的分支状态信息熵计算过程如下:
    $ {Entropy(Sunny) = -\frac{2}{5} log_2\frac{2}{5} - \frac{3}{5} log_2\frac{3}{5} = 0.970951 } $
    $ {Entropy(Overcast) = -\frac{4}{4} log_2\frac{4}{4} - \frac{0}{4} log_2\frac{0}{4} = 0 } $
    $ {Entropy(Rainy) = -\frac{3}{5} log_2\frac{3}{5} - \frac{2}{5} log_2\frac{2}{5} = 0.970951 } $

    Entropy(S|T)

    统计完各个分支状态的信息熵之后,就需求合并,也就是某一特征属性的信息熵了。
    $ {Entropy(S|OutLook) = {\frac{5}{14}*Entropy(Sunny)} + {\frac{4}{14}*Entropy(Overcast)} + {\frac{5}{14}*Entropy(Rainy)} = 0.693536 } $

    IG(T)

    我们还是拿上面的数据进行计算。也就是计算 IG(OutLook).
    $ {IG(OutLook) = Entropy(S) - Entropy(S|OutLook) = 0.940286 - 0.693536 = 0.24675} $

    决策树构建结果

    通过上面的训练数据集及 ID3 构建算法,我们构建了一棵如下的 ID3 决策树。
    这里写图片描述

    Ref

    • http://blog.csdn.net/acdreamers/article/details/44661149
    • http://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html

    GitHub download

    此处为本文的算法实现,采用的编程语言为 Java。算法也是在不断重构及优化,如果你对此感兴趣,欢迎 star.

    • https://github.com/MachineLeanring/MachineLearningID3

    征集

    如果你也需要使用ProcessOn这款在线绘图工具,可以使用如下邀请链接进行注册:
    https://www.processon.com/i/56205c2ee4b0f6ed10838a6d

    展开全文
  • MP3标签 ID3v1,ID3v2,APETAGEX

    万次阅读 2012-07-14 23:13:16
    根据帧性质的不同,文件大体分为四个部分:ID3v2标签帧、数据帧、APEV2标签帧、ID3v1标签帧,而只有数据帧才是必需的。  数据帧包含了歌曲的压缩数据。标签帧提供了歌曲的演唱者、歌名、专辑、年份等信息。  ID3...
  • 决策树算法:ID3

    万次阅读 多人点赞 2018-09-01 11:31:18
      目前常用的决策树算法有ID3算法、改进的C4.5,C5.0算法和CART算法   ID3算法的核心是在决策树各级节点上选择属性时,用信息增益作为属性的选择标准,使得在每一个非节点进行测试时,能获得关于被测试记录...
  • 决策树之ID3算法

    万次阅读 多人点赞 2015-03-27 00:32:39
    对于决策树来说,主要有两种算法:ID3算法和C4.5算法。C4.5算法是 对ID3算法的改进。今天主要先讲ID3算法,之后会讲C4.5算法和随机森林等。   Contents    1. 决策树的基本认识  2. ID3算法介绍  3. ...
  • 暑假在家学习Android,通过编写一个Mp3播放器学习MediaPalyer。在这里和大家分享一下代码...1、ID3V2 标签解析 只解析些常见的。{歌名、艺术家、专辑、头像} 新建一个Id3v2Info类 package com.aws.mp3; public
  • DeepID3 face recognition

    千次阅读 2016-08-07 23:03:09
    DeepID3 face recognition刚看完DeepID3[1],总结一下,还是先简单介绍一下网络结构吧。Network ArchitectureDeepID3有两种不同的结构,分别为DeepID3 net1,DeepID3 net2。相对DeepID2+[2],它的层数更多,网络更深...
  • 分类算法之决策树ID3详解

    万次阅读 多人点赞 2017-08-19 20:19:24
    回顾决策树的基本知识,其... 从上述三个问题出发,以实际的例子对ID3算法进行阐述。 先上问题吧,我们统计了14天的气象数据(指标包括outlook,temperature,humidity,windy),并已知这些天气是否打球(play)。如果
  • MP3 ID3文本使用的编码

    千次阅读 2013-02-18 16:43:02
    mp3文件使用的ID3分为ID3v1 和 ID3v2两个版本。ID3v2又分1,2,3,4这4个版本。据说支持最广泛的是ID3v2-3这个版本。 ID3v1保存在mp3尾部,固定为128字节,以TAG这三个字符开头。格式如下 char Header[3];...
  • Mp3(ID3v2)格式文件解析

    千次阅读 2016-08-04 10:58:47
    ID3v2版本的标签分析: 1、标签头 在文件的首部顺序记录 10 个字节的 ID3V2.3 的头部。数据结构如下:  char Header[3]; /*必须为"ID3"否则认为标签不存在*/  char Ver; /*版本号 ID3V2.3 就记录 ...
  • MATLAB简单实现ID3算法

    千次阅读 2019-03-13 15:56:24
    本文主要参考了Python实现ID3算法,对浅谈决策树算法以及matlab实现ID3算法中的代码作了少许改动,用Map代替Struct从而实现中文字符的存储。并且可以有多个分叉。 具体代码为: function shannonEnt = calShannonEnt...
  • ID3决策树程序实现

    万次阅读 2018-07-03 10:39:19
    原文地址:...决策树的原理相对简单,决策树算法有:ID3,C4.5,CART等算法。接下来将对ID3决策树算法进行程序实现,参考了《机器学习实战》一书。这篇博客也作为自己个人的学习笔记,以...
  • ID3算法(含实例)

    万次阅读 多人点赞 2018-08-27 17:38:46
    (1)ID3算法简介 (2)ID3算法节点分裂规则 (3)ID3算法实例 (4)剪枝 ------------------------------------------------------------------------------------------------------------------------- 一、...
  • ID3算法的理解及其优缺点

    千次阅读 2019-11-12 19:05:42
    决策树ID3算法1、定义2、理解3、ID3算法的过程3、ID3算法的优缺点优点缺点4、为什么倾向特征选项较多的特征 在机器学习决策树中,最常用的三种算法有三种:ID3,C4.5,CART。在这里我将我对ID3算法的理解说一下。 1...
  • jquery 选择多个id:$("#id1,#id2,#id3,#id4")

    万次阅读 2014-08-15 10:05:45
    $("#id1,#id2,#id3,#id4")
  • MP3 ID3 格式解析

    千次阅读 2007-05-08 23:19:00
    本文转自:http://zhangxiangya.diy.myrice.com/ mp3歌曲的信息所存放的位置:Mp3文件包含一个叫做ID3的标签。其实有两个标签,一个叫做ID3v1,另外一个叫做ID3v2。 ID3V1结构比
  • 决策树(一)--ID3

    千次阅读 2016-07-20 15:55:02
    对于决策树来说,主要有两种算法:ID3算法和C4.5算法。C4.5算法是 对ID3算法的改进。今天主要先讲ID3算法,之后会讲C4.5算法和随机森林等。   Contents    1. 决策树的基本认识  2. ID3算法介绍  3. 信息熵与...
  • ID3算法详解及python实现

    千次阅读 2017-08-27 16:45:39
    1970年代,一个叫昆兰的大牛找到了用信息论中的熵来度量决策树的决策选择过程,它的简洁和高效就引起了轰动,昆兰把这个算法叫做ID3。下面我们就看看ID3算法是怎么选择特征的。 首先,我们需
  • 前3个是标识位,其值为ID3,表示标签存在,如果前三个字节不是ID3,那就表示没有ID3V2的标签。然后一个字节是版本号,下一个字节为副版本号,再下一个是标志位。这三个字节都没太大用。最后4个字节是标签的大小,这...
  • 决策树ID3算法-matlab实现

    千次阅读 2016-12-29 21:21:51
    ID3_decision_tree.m%% 使用ID3决策树算法预测销量高低 clear ;%% 数据预处理 disp('正在进行数据预处理...'); [matrix,attributes_label,attributes] = id3_preprocess();%% 构造ID3决策树,其中id3()为自定义函数 ...
  • 浅谈决策树算法以及matlab实现ID3算法

    万次阅读 多人点赞 2016-02-27 00:04:10
    在20世纪70年代后期和80年代初期,机器学习研究者J.Ross Quinilan提出了ID3算法以后,决策树在机器学习、数据挖掘领域得到极大的发展。Quinilan后来又提出了C4.5,成为新的监督学习算法。1984年几位统计学家提出了...
  • id3算法

    千次阅读 2006-03-22 13:42:00
    From:http://www.cise.ufl.edu/~ddd/cap6635/Fall-97/Short-papers/2.htm The ID3 Algorithm Abstract This paper details the ID3 classification algorithm. Very simply, ID3 builds a decision tree
  • weka中ID3算法及可视化

    千次阅读 2017-05-09 12:05:22
    weka中ID3算法及可视化 最近看西瓜书看到决策树,想把数据集拿过来跑跑,具体我在博客中写了。但是遇到一个问题就是新版本weka(我用的是3.7.11和3.8.1)中均不再提供ID3算法,可能确实是ID3算法缺点太过明显,这个...
  • 机器学习笔记(4)——ID3决策树算法及其Python实现

    万次阅读 多人点赞 2018-09-27 16:07:37
    决策树是一种基于树结构来进行决策...最经典的决策树算法有ID3、C4.5、CART,其中ID3算法是最早被提出的,它可以处理离散属性样本的分类,C4.5和CART算法则可以处理更加复杂的分类问题,本文重点介绍ID3算法。 举个...
  • ID3D11DeviceContext接口

    千次阅读 2012-12-21 00:26:25
    这个ID3D11DeviceContext接口实现一个设备上下文生成渲染命令。   成员 ID3D11DeviceContext接口实现ID3D11DeviceChild.ID3D11DeviceContext也定义了一下成员函数:   成员 描述 Begin 标记...
  • weka使用ID3和C4.5算法 分类实验

    千次阅读 2018-01-17 21:23:31
    使用weka做分类任务并建立相应决策树(ID3算法和C4.5算法) weka安装 相关知识理论 2.1 决策树 2.2 ID3算法 2.3 C4.5算法 分类实验 3.1 数据处理 3.2 使用ID3算法 3.3 使用C4.5算法 3.4 ID3和C4.5的...
  • MP3 ID3v1 & ID3v2 &APEv2 标准总结

    千次阅读 2018-08-10 23:47:43
    MP3是現在相當流行的一種音樂格式,全名為Moving Picture Experts Group Audio Layer III(MPEG-1 Audio Layer 3)。MP3使用失真壓縮的方式大幅降低儲存音訊資料所需的空間,大大增加它的可攜性。不過,雖然MP3採用...
  • 决策树ID3详解(西瓜案例)

    千次阅读 热门讨论 2019-11-30 20:04:34
    一、决策树 决策树(decision tree)是一种基本的分类与回归方法。一般情况下,回归方法可以转换为分类方法,因此,...决策树主要算法有:ID3、C4.5、CART。以及进化后的C4.5算法C5.0、分类有极大提升的Tsallis等算...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 407,837
精华内容 163,134
关键字:

id3