C++如何促成并利用决策树算法?

正文对裁决树算法举行不难的总括和梳理,并对有名的表决树算法ID3(Iterative
Dichotomiser
迭代二分器)进行落到实处,达成采纳Python语言,一句老梗,“人生苦短,小编用Python”,Python确实能够省很多语言方面包车型客车事,从而能够让我们注意于难点和缓解难点的逻辑。

依照差异的数据,小编达成了三个本子的ID3算法,复杂度稳步升级:

1.纯标称值无缺点和失误数据集

2.一而再值和标称值混合且无缺点和失误数据集

3.延续值和标称值混合,有缺点和失误数据集

率先个算法参考了《机器学习实战》的超越二分之一代码,第2 、多个算法基于前边的落实举办模块的增多。

决策树简介

仲裁树算法不用说我们应该都知晓,是机械学习的一个名牌算法,由澳大波尔多(Australia)知名计算机地管理学家RoseQuinlan宣布。

决策树是一种监督学习的归类算法,目标是读书出一颗决策树,该树中间节点是多少特征,叶子节点是项目,实际分类时依据树的布局,一步一步依照当前数量特征取值采纳进入哪一颗子树,直到走到叶子节点,叶子节点的体系就是此决策树对此数量的上学结果。下图就是一颗不难的决策树:

C++ 1此决定树用来判定3个兼有纹理,触感,密度的西瓜是不是是“好瓜”。

当有那般1个西瓜,纹理清晰,密度为0.333,触感硬滑,那么要你认清是不是是3个“好瓜”,那时即便因此决策树来判断,分明能够平昔本着纹理->清晰->密度<=0.382->否,即此瓜不是“好瓜”,三次表决就像此形成了。正因为决策树决策很有利,并且准确率也较高,所以时常被用来做分类器,也是“机器学习十大算法”之一C4.5的主干考虑。

上学出一颗决策树首要考虑三个标题,即 依据数据集构建当前树应该选拔哪一种性格作为树根,即划分标准? 

设想最好的景观,一开始步评选拔有些特征,就把多少集划分成功,即在该特征上取某些值的全是一类。

考虑最坏的情状,不断采纳特征,划分后的数据集总是一塌糊涂,就二分拣职务以来,总是有正类有负类,一直到特征全体用完了,划分的数码集合如故有正有负,这时只可以用投票法,正类多就选正类作为叶子,不然选负类。

于是得出了貌似结论:
随着划分的拓展,大家意在选取1个特征,使得子节点包涵的范本尽恐怕属于同一档次,即“纯度”越高越好。

基于“纯度”的正经各异,有三种算法:

1.ID3算法(Iterative
Dichotomiser
迭代二分器),也是本文要落实的算法,基于音信增益即新闻熵来衡量纯度

2.C4.5算法(Classifier
4.5),ID3 的后继算法,也是昆兰提议

3.CATiguanT算法(Classification
And Regression Tree),基于基尼指数衡量纯度。

ID3算法简介

音讯熵是音信论中的三个重中之重概念,也叫“香农熵”,香农先生的事迹对比很几个人都听过,一位开创了一门理论,牛的特别。香农理论中二个很关键的特色就是”熵“,即”音讯内容的不鲜明性“,香农在举办新闻的定量测算的时候,分明地把音信量定义为专擅不定性程度的压缩。那就表明了她对新闻的知道:新闻是用来压缩随意不定性的事物。或然公布为香农逆定义:音信是醒目标扩大。那也验证了决策树以熵作为划分选拔的心胸标准的不利,即大家想更连忙地从数额中收获越多音讯,大家就应有快速降低不分明性,即缩减”熵“。

音讯熵定义为:

C++ 2

D表示数据集,种类总数为|Y|,pk代表D中第k类样本所占的百分比。依据其定义,Ent的值越小,消息纯度越高。Ent的界定是[0,log|Y|]

上边要挑选某些属性举行分割,要每种考虑每一种属性,假使当前设想属性a,a的取值有|V|种,那么大家期待取a作为划分属性,划分到|V|个子节点后,全数子节点的音信熵之和即划分后的音讯熵能够有极大的回落,减小的最多的不胜属性就是大家挑选的性质。

划分后的音讯熵定义为:

C++ 3 

之所以用属性a对样本集D举办划分的音讯增益便是原来的音信熵减去划分后的新闻熵:

C++ 4

ID3算法正是那样每趟选拔1性子质对样本集进行分割,知道三种境况使这么些进程甘休:

(1)有个别子节点样本全体属于一类

(2)属性都用完了,这时候假诺实节点样本依旧差异,那么只好少数服从多数了

C++ 5(图片源于互连网)

ID3算法实现(纯标称值)

若是样本全体是标称值即离散值的话,会比较简单。

代码:

C++ 6C++ 7

from math import log
from operator import itemgetter
def createDataSet():            #创建数据集
    dataSet = [[1,1,'yes'],
               [1,1,'yes'],
               [1,0,'no'],
               [0,1,'no'],
               [0,1,'no']]
    featname = ['no surfacing', 'flippers']
    return dataSet,featname
def filetoDataSet(filename):
    fr = open(filename,'r')
    all_lines = fr.readlines()
    featname = all_lines[0].strip().split(',')[1:-1]
    print(featname)
    dataSet = []
    for line in all_lines[1:]:
        line = line.strip()
        lis = line.split(',')[1:]
        dataSet.append(lis)
    fr.close()
    return dataSet,featname
def calcEnt(dataSet):           #计算香农熵
    numEntries = len(dataSet)
    labelCounts = {}
    for featVec in dataSet:
        label = featVec[-1]
        if label not in labelCounts.keys():
            labelCounts[label] = 0
        labelCounts[label] += 1
    Ent = 0.0
    for key in labelCounts.keys():
        p_i = float(labelCounts[key]/numEntries)
        Ent -= p_i * log(p_i,2)
    return Ent
def splitDataSet(dataSet, axis, value):   #划分数据集,找出第axis个属性为value的数据
    returnSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            retVec = featVec[:axis]
            retVec.extend(featVec[axis+1:])
            returnSet.append(retVec)
    return returnSet
def chooseBestFeat(dataSet):
    numFeat = len(dataSet[0])-1
    Entropy = calcEnt(dataSet)
    DataSetlen = float(len(dataSet))
    bestGain = 0.0
    bestFeat = -1
    for i in range(numFeat):
        allvalue = [featVec[i] for featVec in dataSet]
        specvalue = set(allvalue)
        nowEntropy = 0.0
        for v in specvalue:
            Dv = splitDataSet(dataSet,i,v)
            p = len(Dv)/DataSetlen
            nowEntropy += p * calcEnt(Dv)
        if Entropy - nowEntropy > bestGain:
            bestGain = Entropy - nowEntropy
            bestFeat = i
    return bestFeat
def Vote(classList):
    classdic = {}
    for vote in classList:
        if vote not in classdic.keys():
            classdic[vote] = 0
        classdic[vote] += 1
    sortedclassDic = sorted(classdic.items(),key=itemgetter(1),reverse=True)
    return sortedclassDic[0][0]
def createDecisionTree(dataSet,featnames):
    featname = featnames[:]              ################
    classlist = [featvec[-1] for featvec in dataSet]  #此节点的分类情况
    if classlist.count(classlist[0]) == len(classlist):  #全部属于一类
        return classlist[0]
    if len(dataSet[0]) == 1:         #分完了,没有属性了
        return Vote(classlist)       #少数服从多数
    # 选择一个最优特征进行划分
    bestFeat = chooseBestFeat(dataSet)
    bestFeatname = featname[bestFeat]
    del(featname[bestFeat])     #防止下标不准
    DecisionTree = {bestFeatname:{}}
    # 创建分支,先找出所有属性值,即分支数
    allvalue = [vec[bestFeat] for vec in dataSet]
    specvalue = sorted(list(set(allvalue)))  #使有一定顺序
    for v in specvalue:
        copyfeatname = featname[:]
        DecisionTree[bestFeatname][v] = createDecisionTree(splitDataSet(dataSet,bestFeat,v),copyfeatname)
    return DecisionTree
if __name__ == '__main__':
    filename = "D:\\MLinAction\\Data\\西瓜2.0.txt"
    DataSet,featname = filetoDataSet(filename)
    #print(DataSet)
    #print(featname)
    Tree = createDecisionTree(DataSet,featname)
    print(Tree)

View Code

解释一下多少个函数:

filetoDataSet(filename)
 将文件中的数据整理成数据集

calcEnt(dataSet)    
总结香农熵

splitDataSet(dataSet, axis, value)    
划分数据集,选择出第axis个本性的取值为value的具备数据集,即D^v,并去掉第axis个属性,因为不要求了

chooseBestFeat(dataSet)    
 根据新闻增益,选取2个最好的习性

Vote(classList)      
 如果属性用完,连串仍分裂,投票决定

createDecisionTree(dataSet,featnames)    
递归创造决策树


用西瓜数据集2.0对算法举行测试,西瓜数据集见 西瓜数据集2.0,输出如下:

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

为了可以体现决策树的优越性即决定方便,那里依据matplotlib模块编写可视化函数treePlot,对转移的决策树举行可视化,可视化结果如下:

C++ 8

 

由于数量太少,没有安装测试数据以证实其准确度,不过自个儿背后会依照妊高征的例子进行准确度的测试的,上面进入下一些:

有一连值的情事

有接二连三值的境况如 西瓜数据集3.0 

叁天品质有很三种取值,大家必定不可能每种取值都做2个分层,那时候供给对一连属性进行离散化,有三种艺术供接纳,当中二种是:

1.对每一类别的数据集的延续值取平均值,再取各种的平均值的平均值作为划分点,将接连属性化为两类成为离散属性

2.C4.5运用的二分法,排序离散属性,取每五个的中心作为划分点的候选点,总括以每种划分点划分数据集的新闻增益,取最大的不行划分点将连续属性化为两类成为离散属性,用该属性举行划分的新闻增益正是刚刚总结的最大消息增益。公式如下:

C++ 9

那里运用第三种,并在就学前对连日属性进行离散化。扩充拍卖的代码如下:

def splitDataSet_for_dec(dataSet, axis, value, small):
    returnSet = []
    for featVec in dataSet:
        if (small and featVec[axis] <= value) or ((not small) and featVec[axis] > value):
            retVec = featVec[:axis]
            retVec.extend(featVec[axis+1:])
            returnSet.append(retVec)
    return returnSet
def DataSetPredo(filename,decreteindex):
    dataSet,featname = filetoDataSet(filename)
    Entropy = calcEnt(dataSet)
    DataSetlen = len(dataSet)
    for index in decreteindex:     #对每一个是连续值的属性下标
        for i in range(DataSetlen):
            dataSet[i][index] = float(dataSet[i][index])
        allvalue = [vec[index] for vec in dataSet]
        sortedallvalue = sorted(allvalue)
        T = []
        for i in range(len(allvalue)-1):        #划分点集合
            T.append(float(sortedallvalue[i]+sortedallvalue[i+1])/2.0)
        bestGain = 0.0
        bestpt = -1.0
        for pt in T:          #对每个划分点
            nowent = 0.0
            for small in range(2):   #化为正类负类
                Dt = splitDataSet_for_dec(dataSet, index, pt, small)
                p = len(Dt) / float(DataSetlen)
                nowent += p * calcEnt(Dt)
            if Entropy - nowent > bestGain:
                bestGain = Entropy-nowent
                bestpt = pt
        featname[index] = str(featname[index]+"<="+"%.3f"%bestpt)
        for i in range(DataSetlen):
            dataSet[i][index] = "是" if dataSet[i][index] <= bestpt else "否"
    return dataSet,featname

根本是预处理函数DataSetPredo,对数据集提前离散化,然后再展开学习,学习代码类似。输出的决策树如下:

C++ 10

有缺点和失误值的景色

数码有缺点和失误值是广阔的情状,大家倒霉直接甩掉这个数量,因为那样会损失多量数目,不划算,但是缺点和失误值大家也无法判断它的取值。如何做呢,办法照旧有的。

考虑多少个难点: 

1.有缺失值时怎么着开始展览私分选拔

2.已选拔划分属性,有缺失值的样本划不分开,怎么样分割?

C++,问题1:有缺点和失误值时怎么进展剪切选用**

骨干思维是开始展览最优待军属和烈属性选用时,先只考虑无缺失值样本,然后再乘以相应比例,得到在漫天样本集上的光景情形。连带考虑到首个问题来说,考虑给每多个样本2个权重,此时各种样本不再总是被视作2个独立样本,那样有利于第三个难题的化解:即若样本在属性a上的值缺点和失误,那么将其当作是全部值都取,只不过取每一种值的权重分化,种种值的权重参考该值在无缺点和失误值样本中的比例,不难地说,比如在无缺失值样本集中,属性a取去多个值1和2,并且取1的权重和占整个权重和三分之一,而取2的权重和占2/3,那么依据该属性对样本集进行剪切时,际遇该属性上有缺点和失误值的范本,那么大家觉得该样本取值2的只怕性更大,于是将该样本的权重乘以2/3归到取值为2的范本集中继续展开私分构造决策树,而乘三分一划到取值为1的样书集中继续组织。不知底自个儿说精通没有。

公式如下:

C++ 11

其中,D~表示数据集D在属性a上无缺点和失误值的样本,依照它来判定a属性的上下,rho(即‘lou’)表示属性a的无缺点和失误值样本占全数样本的百分比,p~_k表示无缺点和失误值样本中第k类所占的百分比,r~_v表示无缺点和失误值样本在属性a上取值为v的样书所占的比重。

在细分样本时,倘若有缺点和失误值,则将样本划分到全部子节点,在属性a取值v的子节点上的权重为r~_v
* 原来的权重。

更详实的解读参考《机器学习》P86-87。

依照权重法修改后的ID3算法完毕如下:

C++ 12C++ 13

from math import log
from operator import itemgetter

def filetoDataSet(filename):
    fr = open(filename,'r')
    all_lines = fr.readlines()
    featname = all_lines[0].strip().split(',')[1:-1]
    dataSet = []
    for line in all_lines[1:]:
        line = line.strip()
        lis = line.split(',')[1:]
        if lis[-1] == '2':
            lis[-1] = '良'
        else:
            lis[-1] = '恶'
        dataSet.append(lis)
    fr.close()
    return dataSet,featname

def calcEnt(dataSet, weight):           #计算权重香农熵
    labelCounts = {}
    i = 0
    for featVec in dataSet:
        label = featVec[-1]
        if label not in labelCounts.keys():
            labelCounts[label] = 0
        labelCounts[label] += weight[i]
        i += 1
    Ent = 0.0
    for key in labelCounts.keys():
        p_i = float(labelCounts[key]/sum(weight))
        Ent -= p_i * log(p_i,2)
    return Ent

def splitDataSet(dataSet, weight, axis, value, countmissvalue):   #划分数据集,找出第axis个属性为value的数据
    returnSet = []
    returnweight = []
    i = 0
    for featVec in dataSet:
        if featVec[axis] == '?' and (not countmissvalue):
            continue
        if countmissvalue and featVec[axis] == '?':
            retVec = featVec[:axis]
            retVec.extend(featVec[axis+1:])
            returnSet.append(retVec)
        if featVec[axis] == value:
            retVec = featVec[:axis]
            retVec.extend(featVec[axis+1:])
            returnSet.append(retVec)
            returnweight.append(weight[i])
        i += 1
    return returnSet,returnweight

def splitDataSet_for_dec(dataSet, axis, value, small, countmissvalue):
    returnSet = []
    for featVec in dataSet:
        if featVec[axis] == '?' and (not countmissvalue):
            continue
        if countmissvalue and featVec[axis] == '?':
            retVec = featVec[:axis]
            retVec.extend(featVec[axis+1:])
            returnSet.append(retVec)
        if (small and featVec[axis] <= value) or ((not small) and featVec[axis] > value):
            retVec = featVec[:axis]
            retVec.extend(featVec[axis+1:])
            returnSet.append(retVec)
    return returnSet

def DataSetPredo(filename,decreteindex):     #首先运行,权重不变为1
    dataSet,featname = filetoDataSet(filename)
    DataSetlen = len(dataSet)
    Entropy = calcEnt(dataSet,[1 for i in range(DataSetlen)])
    for index in decreteindex:     #对每一个是连续值的属性下标
        UnmissDatalen = 0
        for i in range(DataSetlen):      #字符串转浮点数
            if dataSet[i][index] != '?':
                UnmissDatalen += 1
                dataSet[i][index] = int(dataSet[i][index])
        allvalue = [vec[index] for vec in dataSet if vec[index] != '?']
        sortedallvalue = sorted(allvalue)
        T = []
        for i in range(len(allvalue)-1):        #划分点集合
            T.append(int(sortedallvalue[i]+sortedallvalue[i+1])/2.0)
        bestGain = 0.0
        bestpt = -1.0
        for pt in T:          #对每个划分点
            nowent = 0.0
            for small in range(2):   #化为正类(1)负类(0)
                Dt = splitDataSet_for_dec(dataSet, index, pt, small, False)
                p = len(Dt) / float(UnmissDatalen)
                nowent += p * calcEnt(Dt,[1.0 for i in range(len(Dt))])
            if Entropy - nowent > bestGain:
                bestGain = Entropy-nowent
                bestpt = pt
        featname[index] = str(featname[index]+"<="+"%d"%bestpt)
        for i in range(DataSetlen):
            if dataSet[i][index] != '?':
                dataSet[i][index] = "是" if dataSet[i][index] <= bestpt else "否"
    return dataSet,featname

def getUnmissDataSet(dataSet, weight, axis):
    returnSet = []
    returnweight = []
    tag = []
    i = 0
    for featVec in dataSet:
        if featVec[axis] == '?':
            tag.append(i)
        else:
            retVec = featVec[:axis]
            retVec.extend(featVec[axis+1:])
            returnSet.append(retVec)
        i += 1
    for i in range(len(weight)):
        if i not in tag:
            returnweight.append(weight[i])
    return returnSet,returnweight

def printlis(lis):
    for li in lis:
        print(li)

def chooseBestFeat(dataSet,weight,featname):
    numFeat = len(dataSet[0])-1
    DataSetWeight = sum(weight)
    bestGain = 0.0
    bestFeat = -1
    for i in range(numFeat):
        UnmissDataSet,Unmissweight = getUnmissDataSet(dataSet, weight, i)   #无缺失值数据集及其权重
        Entropy = calcEnt(UnmissDataSet,Unmissweight)      #Ent(D~)
        allvalue = [featVec[i] for featVec in dataSet if featVec[i] != '?']
        UnmissSumWeight = sum(Unmissweight)
        lou = UnmissSumWeight / DataSetWeight        #lou
        specvalue = set(allvalue)
        nowEntropy = 0.0
        for v in specvalue:      #该属性的几种取值
            Dv,weightVec_v = splitDataSet(dataSet,Unmissweight,i,v,False)   #返回 此属性为v的所有样本 以及 每个样本的权重
            p = sum(weightVec_v) / UnmissSumWeight          #r~_v = D~_v / D~
            nowEntropy += p * calcEnt(Dv,weightVec_v)
        if lou*(Entropy - nowEntropy) > bestGain:
            bestGain = Entropy - nowEntropy
            bestFeat = i
    return bestFeat

def Vote(classList,weight):
    classdic = {}
    i = 0
    for vote in classList:
        if vote not in classdic.keys():
            classdic[vote] = 0
        classdic[vote] += weight[i]
        i += 1
    sortedclassDic = sorted(classdic.items(),key=itemgetter(1),reverse=True)
    return sortedclassDic[0][0]

def splitDataSet_adjustWeight(dataSet,weight,axis,value,r_v):
    returnSet = []
    returnweight = []
    i = 0
    for featVec in dataSet:
        if featVec[axis] == '?':
            retVec = featVec[:axis]
            retVec.extend(featVec[axis+1:])
            returnSet.append(retVec)
            returnweight.append(weight[i] * r_v)
        elif featVec[axis] == value:
            retVec = featVec[:axis]
            retVec.extend(featVec[axis+1:])
            returnSet.append(retVec)
            returnweight.append(weight[i])
        i += 1
    return returnSet,returnweight

def createDecisionTree(dataSet,weight,featnames):
    featname = featnames[:]              ################
    classlist = [featvec[-1] for featvec in dataSet]  #此节点的分类情况
    if classlist.count(classlist[0]) == len(classlist):  #全部属于一类
        return classlist[0]
    if len(dataSet[0]) == 1:         #分完了,没有属性了
        return Vote(classlist,weight)       #少数服从多数
    # 选择一个最优特征进行划分
    bestFeat = chooseBestFeat(dataSet,weight,featname)
    bestFeatname = featname[bestFeat]
    del(featname[bestFeat])     #防止下标不准
    DecisionTree = {bestFeatname:{}}
    # 创建分支,先找出所有属性值,即分支数
    allvalue = [vec[bestFeat] for vec in dataSet if vec[bestFeat] != '?']
    specvalue = sorted(list(set(allvalue)))  #使有一定顺序
    UnmissDataSet,Unmissweight = getUnmissDataSet(dataSet, weight, bestFeat)   #无缺失值数据集及其权重
    UnmissSumWeight = sum(Unmissweight)      # D~
    for v in specvalue:
        copyfeatname = featname[:]
        Dv,weightVec_v = splitDataSet(dataSet,Unmissweight,bestFeat,v,False)   #返回 此属性为v的所有样本 以及 每个样本的权重
        r_v = sum(weightVec_v) / UnmissSumWeight          #r~_v = D~_v / D~
        sondataSet,sonweight = splitDataSet_adjustWeight(dataSet,weight,bestFeat,v,r_v)
        DecisionTree[bestFeatname][v] = createDecisionTree(sondataSet,sonweight,copyfeatname)
    return DecisionTree

if __name__ == '__main__':
    filename = "D:\\MLinAction\\Data\\breastcancer.txt"
    DataSet,featname = DataSetPredo(filename,[0,1,2,3,4,5,6,7,8])
    Tree = createDecisionTree(DataSet,[1.0 for i in range(len(DataSet))],featname)
    print(Tree)

View Code

有缺点和失误值的情形如 西瓜数据集2.0阿尔法

尝试结果:

C++ 14

在乳腺囊性增生病数据集上的测试与表现

有了算法,大家当然想做肯定的测试看一看算法的展现。那里笔者选用了威斯康辛女性乳房缺少症的数目。

数量总共有9列,每一列分别表示,以逗号分割

1 Sample
code number (病人ID)
2 Clump
Thickness 肿块厚度
3
Uniformity of Cell Size 细胞大小的均匀性
4
Uniformity of Cell Shape 细胞形状的均匀性
5
Marginal Adhesion 边缘粘
6 Single
Epithelial Cell Size 单上皮细胞的分寸
7 Bare
Nuclei 裸核
8 Bland
Chromatin 乏味染色体
9 Normal
Nucleoli 正常核
10
Mitoses 有丝不一样
11 Class:
2 for benign, 4 formalignant(恶性或良性分类)

[from
Toby]

累计700条左右的数量,选择最终80条作为测试集,前面作为演练集,实行学习。

运用分类器的代码如下:

import treesID3 as id3
import treePlot as tpl
import pickle

def classify(Tree, featnames, X):
    classLabel = "未知"
    root = list(Tree.keys())[0]
    firstGen = Tree[root]
    featindex = featnames.index(root)  #根节点的属性下标
    for key in firstGen.keys():   #根属性的取值,取哪个就走往哪颗子树
        if X[featindex] == key:
            if type(firstGen[key]) == type({}):
                classLabel = classify(firstGen[key],featnames,X)
            else:
                classLabel = firstGen[key]
    return classLabel

def StoreTree(Tree,filename):
    fw = open(filename,'wb')
    pickle.dump(Tree,fw)
    fw.close()

def ReadTree(filename):
    fr = open(filename,'rb')
    return pickle.load(fr)

if __name__ == '__main__':
    filename = "D:\\MLinAction\\Data\\breastcancer.txt"
    dataSet,featnames = id3.DataSetPredo(filename,[0,1,2,3,4,5,6,7,8])
    Tree = id3.createDecisionTree(dataSet[:620],[1.0 for i in range(len(dataSet))],featnames)
    tpl.createPlot(Tree)
    storetree = "D:\\MLinAction\\Data\\decTree.dect"
    StoreTree(Tree,storetree)
    #Tree = ReadTree(storetree)
    i = 1
    cnt = 0
    for lis in dataSet[620:]:
        judge = classify(Tree,featnames,lis[:-1])
        shouldbe = lis[-1]
        if judge == shouldbe:
            cnt += 1
        print("Test %d was classified %s, it's class is %s %s" %(i,judge,shouldbe,"=====" if judge==shouldbe else ""))
        i += 1
    print("The Tree's Accuracy is %.3f" % (cnt / float(i)))

磨练出的决策树如下:

C++ 15

末尾的正确率可以观望:

C++ 16

正确率约为96%左右,算是不差的分类器了。

自小编的阴道炎数据见:http://7xt9qk.com2.z0.glb.clouddn.com/breastcancer.txt

时至明日,决策树算法ID3的得以实现得了,上边考虑基于基尼指数和新闻增益率举办分割选拔,以及考虑达成剪枝进程,因为大家能够观望上边磨练出的决策树还设有着不少冗余分支,是因为完毕进度中,由于数据量太大,种种分支都不完全纯净,所以会成立往下的分支,不过分支投票的结果又是同一的,而且数据量再大,特征数再多的话,决策树会相当大13分复杂,所以剪枝一般是必做的一步。剪枝分为先剪枝和后剪枝,如若细说的话可以写很多了。

此文亦可见:这里
参考资料:《机器学习》《机器学习实战》通过本次实战也发现了这两本书中的一些荒唐之处。

lz初学机器学习不久,如有错漏之处请多包含建议照旧各位有啥想法或意见欢迎评论去报告小编:)