和C5.0生成树算法使用熵,已毕接纳Python语言

正文对决策树算法举办简要的总计和梳理,并对名牌的裁定树算法ID3(Iterative
Dichotomiser
迭代二分器)举行落实,完毕应用Python语言,一句老梗,“人生苦短,作者用Python”,Python确实可以省很多言语方面的事,从而可以让大家注意于难题和化解难点的逻辑。

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

依照不一致的多少,小编已毕了多个版本的ID3算法,复杂度逐步升级:

是在已知各样状态时有暴发可能率的基础上,通过整合决策树来求取净现值的期望值超出等于零的几率,评价项目危机,判断其可行性的决策分析方法,是直观运用可能率分析的一种图解法。由于那种决策分支画成图形很像一棵树的枝干,故称决策树。在机器学习中,决策树是二个展望模型,他表示的是目的属性与目的值时期的一种炫耀关系。Entropy

系统的混乱程度,使用算法ID3,C4.5和C5.0生成树算法使用熵。这一度量是依照音信学理论中熵的概念。

4.2 划分采纳的要领:

4.2.1
音讯增益:
是特色采纳中的多个主要目标,它定义为二个特点能够为分类序列带来多少音信,带来的消息愈来愈多,该特征越首要。

永利集团娱乐官网 1

4.2.2熵:那么如何权衡1个特色为分类系列带来的音讯有点吧:对二个风味而言,系统有它和没它时新闻量将爆发变化,而前后音讯量的差值就是那些特点给系统带来的音信量。所谓音信量,其实就是熵。消息熵可以衡量事物的不分明性,那一个东西不显然越大,新闻熵也越大

【补充】和讯上有三个对音信熵的表明相比好https://www.zhihu.com/question/22178202/answer/49929786一个事件的音信量就是这一个事件暴发的可能率的负对数

【音信增益熵之间关系】新闻增益=熵-条件熵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 后剪枝

后剪枝,是树已经形成了,然后剪枝的方针和预剪枝差不离,也是3个个去品尝,在西瓜的例子中,就是判定这么些节点是不是替换后,是不是好瓜依然坏瓜。比较他们剪枝前和剪枝后的精度。从书上的图可以看出,后剪枝分支越多,欠拟合的高风险小。但操练时间大过多。

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属性缺失,那么就把第九个样本去掉,前8个样本组成新的样本集,在新样本集上按不奇怪艺术统计a属性的熵增。然后结果乘0.9(新样本占raw样本的比例),就是a属性最后的熵。

4.5 多变量决策树

相比较于ID③ 、C4.五 、CAXC60T那种单变量决策树(分支时只用贰特性能),多变量决策树在分层时用的是三特特性的加权组合,来个直观的图(以下),那几个是单变量决策树学习出来的分割边界,那么些边界都是与坐标轴平行的,多变量决策树的剪切边界是倾斜于坐标轴的。

算法分支(详情参见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

CA本田CR-VT(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)CA奇骏T是二叉树,而不是多叉树。

总结表

永利集团娱乐官网 3

永利集团娱乐官网 4

xgboost

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

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

2.老是值和标称值混合且无缺失数据集

3.接连值和标称值混合,有缺失数据集

率先个算法参考了《机器学习实战》的大部分代码,第③ 、多少个算法基于前面的落到实处举办模块的增多。

决策树简介

仲裁树算法不用说大家应该都知晓,是机械学习的一个老牌算法,由澳大雷克雅未克出名统计机数学家RoseQuinlan揭橥。

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

永利集团娱乐官网 5此决定树用来判定二个拥有纹理,触感,密度的西瓜是还是不是是“好瓜”。

当有这般1个西瓜,纹理清晰,密度为0.333,触感硬滑,那么要你判定是还是不是是1个“好瓜”,那时即使因此决策树来判定,分明可以一向本着纹理->清晰->密度<=0.382->否,即此瓜不是“好瓜”,五回表决就那样成功了。正因为决策树决策很有益,并且准确率也较高,所以时常被用来做分类器,也是“机器学习十大算法”之一C4.5的基本思维。

学学出一颗决策树主要考虑贰个难点,即 根据数据集创设当前树应该拔取哪一种天性作为树根,即划分标准? 

考虑最好的情景,一先河接纳有个别特征,就把数量集划分成功,即在该特征上取有个别值的全是一类。

设想最坏的景况,不断拔取特征,划分后的数码集总是一塌糊涂,就二分拣任务以来,总是有正类有负类,一向到特征全体用完了,划分的多少集合如故有正有负,那时只可以用投票法,正类多就选正类作为叶子,否则选负类。

因此得出了貌似结论:
随着划分的开展,大家期望拔取三特性情,使得子节点包涵的样本尽大概属于同一品种,即“纯度”越高越好。

依据“纯度”的正儿八经不一,有三种算法:

1.ID3算法(Iterative
Dichotomiser
迭代二分器),也是本文要兑现的算法,基于信息增益即信息熵来度量纯度

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

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

ID3算法简介

音讯熵是音信论中的七个非同儿戏概念,也叫“香农熵”,香农先生的事迹比较很三个人都听过,一位创造了一门理论,牛的可怜。香农理论中一个很要紧的性状就是”熵“,即”新闻内容的不显然性“,香农在开展音讯的定量测算的时候,明显地把音讯量定义为随意不定性程度的滑坡。那就标明了她对新闻的领会:音讯是用来压缩随意不定性的事物。或然发布为香农逆定义:音信是扎眼的充实。那也认证了决策树以熵作为划分采用的襟怀标准的正确,即大家想更高速地从数额中拿到更加多新闻,大家就应当很快下落不鲜明性,即缩减”熵“。

新闻熵定义为:

永利集团娱乐官网 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个属性,因为不必要了

chooseBestFeat(dataSet)    
 依据音讯增益,选用1个最好的性质

Vote(classList)      
 假若属性用完,系列仍不均等,投票决定

createDecisionTree(dataSet,featnames)    
递归成立决策树


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

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

为了能够展示决策树的优越性即决定方便,那里根据matplotlib模块编写可视化函数treePlot,对转移的决策树举办可视化,可视化结果如下:

永利集团娱乐官网 12

 

由于数量太少,没有安装测试数据以证实其准确度,可是自身背后会基于麦格综合征的例证进行准确度的测试的,上边进入下一些:

永利集团娱乐官网,有一而再值的情形

有连续值的情事如 西瓜数据集3.0 

2本性质有很各类取值,大家自然不可以各个取值都做多少个分层,那时候需求对连日属性举办离散化,有二种格局供采用,其中二种是:

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个样书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.0alpha

试行结果:

永利集团娱乐官网 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初学机器学习不久,如有错漏之处请多包括指出依旧各位有何样想法或意见欢迎评论去告诉本身:)

相关文章