使用算法,笔者完成了多少个版本的ID3算法

正文对裁定树算法举办简易的统计和梳理,并对名牌的决定树算法ID3(Iterative
Dichotomiser
迭代二分器)举行落到实处,完毕利用Python语言,一句老梗,“人生苦短,小编用Python”,Python确实可以省很多言语方面的事,从而可以让我们注意于难点和消除难题的逻辑。

4.1 决策树(Decision Tree)的定义:

依据差其他数量,笔者完毕了七个本子的ID3算法,复杂度逐步提高:

是在已知各类境况爆发可能率的基础上,通过结合决策树来求取净现值的期望值超出等于零的可能率,评价项目风险,判断其可行性的决策分析方法,是直观运用可能率分析的一种图解法。由于那种决策分支画成图形很像一棵树的枝条,故称决策树。在机器学习中,决策树是三个估量模型,他意味着的是目的属性与对象值时期的一种炫耀关系。Entropy

系统的混杂程度,使用算法ID3,C4.5和C5.0生成树算法使用熵。这一度量是基于消息学理论中熵的定义。

4.2 划分选拔的主旨绪想:

4.2.1
音信增益:
是特色拔取中的贰个非同儿戏目标,它定义为1个特点可以为分类体系带来多少新闻,带来的音信越来越多,该特征越紧要。

图片 1

4.2.2熵:那么怎么样衡量八个特色为分类序列带来的音信有点吗:对一个特点而言,系统有它和没它时消息量将发生变化,而左右音讯量的差值就是以此天性给系统带来的音讯量。所谓信息量,其实就是熵。音讯熵可以衡量事物的不显然性,这些东西不引人侧目越大,音讯熵也越大

【补充】搜狐上有三个对音信熵的演说相比好https://www.zhihu.com/question/22178202/answer/499297861个事件的音讯量就是其一事件时有爆发的票房价值的负对数

【音信增益熵之间涉及】消息增益=熵-条件熵https://www.zhihu.com/question/22104055

【消息增益音讯增益率之间涉及】一些变种决策树的算法对私分的中央略有分化,如ID3采纳音信增益,c4.5施用音信增益比,他们的中间的不一致,如下:

https://www.zhihu.com/question/22928442

andy:离散数据利用新闻增益ID3与C4.5的界别并不大。但万一面对连连的数额(如体重、身高、年龄、距离等),或许每列数据没有强烈的系列之分(最极致的例子的该列全体数据都无比),在那种景况下,新闻增益率减轻了分割行为自身的震慑

4.2.3 基尼指数

Gini是从数据集随机抽七个样本,差距的票房价值。如若Gini越小,则数据集纯度越高。

4.3 剪枝处理:化解 “过拟合”的最主要手段

有关“过拟合”(数据集匹配的太好)和“欠拟合”(数据集匹配的不得了)之间的涉嫌:http://www.cnblogs.com/nxld/p/6058782.html

分为: 预剪枝和 后剪枝

4.3.1 预剪枝

释疑剪枝前,要求解释什么是泛化

泛化即是,机器学习模型学习到的定义在它地处学习的长河中时模型没有蒙受过的样本时候的呈现。

好的机器学习模型的模版目标是从难题领域内的练习多少到任意的数据上泛化品质特出。那让我们可以在现在对模型没有见过的数目开展预测。

预剪枝:树还一贯不练习成,可是用判断节点,要不要继续划分。那样的操作会提升分类的准度,然则会推动欠拟合的高危害。

4.3.1 后剪枝

后剪枝,是树已经形成了,然后剪枝的国策和预剪枝大约,也是一个个去尝试,在西瓜的例子中,就是判定这么些节点是还是不是替换后,是不是好瓜依旧坏瓜。比较他们剪枝前和剪枝后的精度。从书上的图可以观察,后剪枝分支更加多,欠拟合的危机小。但操练时间大过多。

4.4 三番五次与缺失值

眼下取值的都以离散的。在两次三番的数额上,要将“三番五次数学离散化技术”-二分法对连日属性进行处理。

以下这么些杂文对决策树的二分处领会释比较好。

http://www.docin.com/p-490493786.html

核心内容:

图片 2

4.4.1 延续值处理:西瓜数据上添加了“密度”和“含糖率”。

【注意】以前的多少是离散,如:稻草黄、浑浊、卷曲、是、否等。可是密度和含糖率,都以连连的数量,如0.45六 、0.258等。

下一场依据二分法结合音信增溢来测算新的树。

4.4.2 怎么着数据集有缺失如何是好?

关心2个问题:

1.什么在属性值缺失境况下开展品质拔取?(一言以蔽之 表头没有咋办)

诸如该节点是依照a属性划分,可是待分类样本a属性缺失,怎么办呢?假若a属性离散,有1,2二种取值,那么就把该样本分配到多个子节点中去,可是权重由1变为相应离散值个数占样本的比重。然后总结错误率的时候,注意,不是各个样本都以权重为1,存在分数。

2.给定划分的属性,若样本缺失,怎样分割?(一言以蔽之表头有了,表头里面的多寡没有怎么办)

假定你利用ID3算法,那么选取分类属性时,就要总计有所属性的熵增(音信增益,Gain)。假设拾个样本,属性是a,b,c。在统计a属性熵时意识,第⑨个样本的a属性缺失,那么就把第八个样本去掉,前七个样本组成新的样本集,在新样本集上按平常艺术计算a属性的熵增。然后结果乘0.9(新样本占raw样本的比重),就是a属性最后的熵。

4.5 多变量决策树

比较于ID③ 、C4.五 、CARAV4T那种单变量决策树(分支时只用叁本性格),多变量决策树在分层时用的是五个本性的加权组合,来个直观的图(以下),那一个是单变量决策树学习出来的撤并边界,这几个边界都是与坐标轴平行的,多变量决策树的分开边界是倾斜于坐标轴的。

算法分支(详情参见http://scikit-learn.org/stable/modules/tree.html)

ID3

采取可以得到最大消息增益(information
gain)的性子为数量划分归类,直到全体分叉为止而不对树的层面拓展任何决定。

等树生成之后,执行后剪枝。

音讯增益的机密难点是,比如有一个数码集含有1个特色是日期大概ID,则该特征会取得最大的消息增益,可是显然在认证数据中不会拿到其余的结果。C45的音讯增益比就是消除那么些难题的。

C45

挑选可以赢得最大音讯增益率(information gain
ratio)的风味来划分数据,并且像ID3一致举办后剪枝。

是ID3的接续版本并扩展了IDC的机能,比如特征数值允许一而再,在分拣的时候进行离散化。

音讯增益率:

“Gain ratio takes number and size of branches into account when choosing
an attribute, and corrects the information gain by taking the intrinsic
information of a split into account (i.e. how much info do we need to
tell which branch an instance belongs to).”

C50

那是最新的一个本子,是有认同的(proprietary
license)。比之C45,裁减了内存,使用更少的规则集,并且准确率更高。

CART

CAENCORET(Classification and Regression
Trees)分类回归树,它应用基尼不纯度(Gini Impurity)来决定分开。Gini
Impurity和information gain ratio的知晓和界别在此间:

http://stats.stackexchange.com/questions/94886/what-is-the-relationship-between-the-gini-score-and-the-log-likelihood-ratio。

它和C45基本上是接近的算法,主要分裂:1)它的叶节点不是有血有肉的分类,而是是二个函数f(),该函数定义了在该规范下的回归函数。2)CARAV4T是二叉树,而不是多叉树。

总结表

图片 3

图片 4

xgboost

最后以下文章对上述内容统计挺好的 http://www.cnblogs.com/bourneli/archive/2013/03/15/2961568.html

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

2.接连值和标称值混合且无缺失数据集

3.两次三番值和标称值混合,有缺失数据集

先是个算法参考了《机器学习实战》的绝半数以上代码,第壹 、七个算法基于后边的贯彻举行模块的加码。

决策树简介

决策树算法不用说我们应该都驾驭,是机器学习的一个名高天下算法,由澳大华雷斯资深总结机化学家罗丝Quinlan发表。

决策树是一种监督学习的分类算法,目标是读书出一颗决策树,该树中间节点是数量特征,叶子节点是种类,实际分类时根据树的布局,一步一步根据当下数量特征取值选用进入哪一颗子树,直到走到叶子节点,叶子节点的门类就是此决策树对此数据的读书结果。下图就是一颗简单的决策树:

图片 5此决定树用来判定三个负有纹理,触感,密度的西瓜是还是不是是“好瓜”。

当有那样贰个西瓜,纹理清晰,密度为0.333,触感硬滑,那么要你认清是还是不是是一个“好瓜”,这时如果经过决策树来判定,鲜明可以一直本着纹理->清晰->密度<=0.382->否,即此瓜不是“好瓜”,一次决定就好像此形成了。正因为决策树决策很便宜,并且准确率也较高,所以不时被用来做分类器,也是“机器学习十大算法”之一C4.5的大旨理想。

读书出一颗决策树首要考虑三个题材,即 依照数据集打造当前树应该采取哪一类天性作为树根,即划分标准? 

考虑最好的图景,一初叶采纳某些特征,就把数量集划分成功,即在该特征上取有个别值的全是一类。

考虑最坏的景况,不断采用特征,划分后的数目集总是一无可取,就二分拣职分以来,总是有正类有负类,一贯到特征全体用完了,划分的多少集合如故有正有负,那时只好用投票法,正类多就选正类作为叶子,否则选负类。

故而得出了相似结论:
随着划分的拓展,大家愿意选拔四个风味,使得子节点包涵的样书尽恐怕属于同一种类,即“纯度”越高越好。

依照“纯度”的正式各异,有三种算法:

1.ID3算法(Iterative
Dichotomiser
迭代二分器),也是本文要落到实处的算法,基于消息增益即音讯熵来度量纯度

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

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

ID3算法简介

新闻熵是消息论中的一个重中之重概念,也叫“香农熵”,香农先生的事迹比较很六人都听过,一人创制了一门理论,牛的尤其。香农理论中3个很关键的特色就是”熵“,即”音讯内容的不明确性“,香农在进展音信的定量测算的时候,显著地把音信量定义为私行不定性程度的回落。那就申明了她对新闻的明亮:消息是用来压缩自由不定性的东西。大概公布为香农逆定义:音信是有目共睹的扩充。那也表明了决策树以熵作为划分采用的心路标准的没错,即大家想更敏捷地从数量中取得更多新闻,我们就应当很快下降不分明性,即收缩”熵“。

消息熵定义为:

图片 6

D表示数据集,体系总数为|Y|,pk代表D中第k类样本所占的比重。根据其定义,Ent的值越小,音信纯度越高。Ent的界定是[0,log|Y|]

上边要采取有些属性进行划分,要依次考虑每一种属性,若是当前设想属性a,a的取值有|V|种,那么大家意在取a作为划分属性,划分到|V|个子节点后,全部子节点的新闻熵之和即划分后的消息熵能够有很大的削减,减小的最多的不得了属性就是我们选取的质量。

分开后的音讯熵定义为:

图片 7 

故此用属性a对样本集D进行划分的音讯增益就是原来的音信熵减去划分后的音讯熵:

图片 8

ID3算法就是这么每一回采取贰天性格对样本集举办私分,知道二种情况使那些进程截止:

(1)某个子节点样本全部属于一类

(2)属性都用完了,那时候如若实节点样本依旧不平等,那么只好少数听从多数了

图片 9(图片来自网络)

ID3算法落成(纯标称值)

假诺样本全部是标称值即离散值的话,会比较简单。

代码:

图片 10图片 11

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个本性,因为不须要了

choose贝斯特Feat(dataSet)    
 按照音讯增益,选用二个最好的习性

Vote(classList)      
 假使属性用完,序列仍不等同,投票决定

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


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

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

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

图片 12

 

是因为数量太少,没有安装测试数据以证实其准确度,但是小编前面会依照宫颈炎的事例举办准确度的测试的,下边进入下部分:

有再而三值的情景

有延续值的地方如 西瓜数据集3.0 

三特性质有很多样取值,大家自然不可以各个取值都做三个分段,那时候须要对连日属性举行离散化,有三种格局供采用,其中三种是:

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

2.C4.5选择的二分法,排序离散属性,取每多个的正中作为划分点的候选点,计算以逐个划分点划分数据集的消息增益,取最大的不胜划分点将屡次三番属性化为两类成为离散属性,用该属性举办分割的音信增益就是刚刚计算的最大新闻增益。公式如下:

图片 13

此处运用第三种,并在学习前对连接属性举办离散化。伸张处理的代码如下:

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,对数据集提前离散化,然后再开展学习,学习代码类似。输出的决策树如下:

图片 14

有缺失值的场馆

数量有缺失值是周边的景色,大家不佳直接丢掉那一个数量,因为这么会损失大批量多少,不划算,可是缺失值大家也手足无措判断它的取值。怎么办吧,办法依旧有的。

考虑七个难点: 

1.有缺失值时怎么样实行私分采纳

2.已采纳划分属性,有缺失值的样本划不分开,怎么着划分?

问题1:有缺失值时如何举办分割采纳**

宗旨考虑是拓展最优属性采用时,先只考虑无缺失值样本,然后再乘以相应比例,得到在全部样本集上的大概情形。连带考虑到第四个难题来说,考虑给每1个样本一个权重,此时每种样本不再总是被看做二个单独样本,那样方便第四个难点的解决:即若样本在属性a上的值缺失,那么将其当作是全数值都取,只可是取每种值的权重不同,各种值的权重参考该值在无缺失值样本中的比例,不难地说,比如在无缺失值样本集中,属性a取去五个值1和2,并且取1的权重和占总体权重和三分之一,而取2的权重和占2/3,那么依照该属性对样本集举办划分时,蒙受该属性上有缺失值的样本,那么大家认为该样本取值2的大概更大,于是将该样本的权重乘以2/3归到取值为2的样书集中继续开展分割构造决策树,而乘叁分一划到取值为1的范本集中继续社团。不知情我说清楚没有。

公式如下:

图片 15

其中,D~表示数据集D在属性a上无缺失值的样本,依据它来判定a属性的三六九等,rho(即‘lou’)表示属性a的无缺失值样本占全数样本的比重,p~_k表示无缺失值样本中第k类所占的比重,r~_v表示无缺失值样本在属性a上取值为v的样本所占的比例。

在划分样本时,即使有缺失值,则将样本划分到全体子节点,在属性a取值v的子节点上的权重为r~_v
* 原来的权重。

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

基于权重法修改后的ID3算法完结如下:

图片 16图片 17

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阿尔法

实验结果:

图片 18

在乳腺炎数据集上的测试与表现

有了算法,大家本来想做肯定的测试看一看算法的变现。那里本身采取了威斯康辛女性先天性无阴道的数码。

多少总共有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)))

陶冶出的决策树如下:

图片 19

最后的正确率可以看出:

图片 20

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

小编的柏哲病数据见:http://7xt9qk.com2.z0.glb.clouddn.com/breastcancer.txt

从这之后,决策树算法ID3的已毕竣事,下边考虑基于基尼指数和新闻增益率举办分割选拔,以及考虑完成剪枝进度,因为我们得以看到地方训练出的决策树还存在着众多冗余分支,是因为完结进度中,由于数据量太大,每种分支都不完全纯净,所以会创设往下的分支,不过分支投票的结果又是一律的,而且数据量再大,特征数再多的话,决策树会分外大非凡复杂,所以剪枝一般是必做的一步。剪枝分为先剪枝和后剪枝,如若细说的话可以写很多了。

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

lz初学机器学习不久,如有错漏之处请多原谅提出如故各位有何样想法或意见欢迎评论去报告作者:)

相关文章