2.连续值和标称值混合且无缺失数据集,使用算法

有缺失值的情景

数码有缺点和失误值是广阔的景观,大家不佳直接丢掉这一个多少,因为这么会损失大量数码,不划算,然而缺点和失误值大家也心慌意乱料定它的取值。如何做吧,办法依然有个别。

思虑七个难题: 

1.有缺点和失误值时怎么进展划分接纳

二.已摘取划分属性,有缺点和失误值的样本划不分开,怎么着划分?

问题1:有缺失值时怎么开始展览剪切采取**

骨干思维是实行最优待军属和烈士家属性选用时,先只怀想无缺点和失误值样本,然后再乘以相应比例,获得在全体样本集上的大意意况。连带思索到第2个难点来讲,思念给每3个样本一个权重,此时各类样本不再总是被看成叁个单独样本,那样便于第2个难题的消除:即若样本在属性a上的值缺点和失误,那么将其用作是全体值都取,只但是取每种值的权重不均等,各类值的权重参考该值在无缺点和失误值样本中的比例,轻松地说,比如在无缺点和失误值样本集中,属性a取去七个值壹和二,并且取一的权重和占总体权重和1/三,而取2的权重和占2/叁,那么依照该属性对样本集进行划分时,遭受该属性上有缺点和失误值的范本,那么大家感觉该样本取值2的只怕性越来越大,于是将该样本的权重乘以2/三归到取值为二的样本集中继续实行划分构造决策树,而乘1/3划到取值为一的样本集中继续组织。不清楚自身说知道未有。

公式如下:

图片 1

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

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

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

依照权重法修改后的ID三算法完结如下:

图片 2图片 3

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

有缺点和失误值的景况如 夏瓜数据集二.0阿尔法

施行结果:

图片 4

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

二.总是值和标称值混合且无缺点和失误数据集

是在已知种种场馆时有发生可能率的基础上,通过整合决策树来求取净现实价值的期望值超过等于零的概率,评价项目风险,推断其大方向的决策分析方法,是直观运用可能率分析的壹种图解法。由于这种决策分支画成图形很像一棵树的枝干,故称决策树。在机器学习中,决策树是二个猜想模型,他意味着的是目的属性与目的值时期的一种炫彩关系。Entropy

系统的紊乱程度,使用算法ID3,C4.5和C5.0生成树算法使用熵。这一衡量是基于音讯学理论中熵的定义。

4.二 划分选拔的要领:

四.二.一音信增益:是特色选拔中的一个器重指标,它定义为3个表征可认为分类种类带来多少消息,带来的新闻更加多,该特征越首要。

图片 5

4.2.2熵:那么哪些权衡三个特征为分类体系带来的新闻有点啊:对1个性格来说,系统有它和没它时音信量将发生变化,而上下新闻量的差值正是那个性子给系统带来的消息量。所谓消息量,其实正是熵。新闻熵能够衡量事物的不明显性,那些事物不显眼越大,消息熵也越大

【补充】搜狐上有四个对音信熵的表达相比好https://www.zhihu.com/question/22178202/answer/499297861个事变的消息量正是其一事件产生的概率的负对数

【音讯增益熵之间关系】音讯增益=熵-条件熵https://www.zhihu.com/question/22104055

【消息增益音信增益率之间关系】一些变种决策树的算法对私分的中央观念略有不相同,如ID三选择消息增益,c4.伍施用新闻增益比,他们的里边的区分,如下:

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

andy:离散数据运用消息增益ID三与C四.5的界别并非常的小。但假若面对连连的数码(如体重、身高、年龄、距离等),只怕每列数据尚未明显的项目之分(最极致的例证的该列全部数据都无比),在那种景色下,消息增益率减轻了分割行为本人的震慑

四.2.三 基尼指数

Gini是从数据集随机抽三个样本,不雷同的概率。要是Gini越小,则数据集纯度越高。

4.3 剪枝处理:化解 “过拟合”的重要手腕

关于“过拟合”(数据集相配的太好)和“欠拟合”(数据集相称的倒霉)之间的涉嫌:http://www.cnblogs.com/nxld/p/6058782.html

分为: 预剪枝和 后剪枝

4.3.1 预剪枝

讲授剪枝前,须求解释如何是泛化

泛化便是,机器学习模型学习到的定义在它地处学习的长河中时模型没有碰到过的范本时候的显示。

好的机械学习模型的模板目的是从难点领域内的磨练多少到任意的数据上泛化品质优异。那让我们能够在现在对模型未有见过的数目开始展览展望。

预剪枝:树还从未磨炼成,但是用推断节点,要不要继续划分。那样的操作会进步分类的准度,可是会拉动欠拟合的风险。

4.3.1 后剪枝

后剪枝,是树已经变成了,然后剪枝的安排和预剪枝大致,也是一个个去品尝,在青门绿玉房的事例中,正是判别那一个节点是不是替换后,是还是不是好瓜依旧坏瓜。相比较他们剪枝前和剪枝后的精度。从书上的图能够观察,后剪枝分支更加多,欠拟合的危机小。但练习时间大过多。

四.肆 一而再与缺点和失误值

此时此刻取值的都以离散的。在两次三番的多少上,要将“延续数学离散化技艺”-二分法对连年属性进行拍卖。

以下这一个杂文对决策树的二分处明白释相比较好。

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

核心内容:

图片 6

四.肆.一 一连值处理:西瓜数据上加多了“密度”和“含糖率”。

【注意】以前的多少是离散,如:水泥灰、浑浊、卷曲、是、否等。但是密度和含糖率,都以连接的数据,如0.45陆、0.25八等。

下一场根据二分法结合新闻增溢来计量新的树。

四.四.二 如何数据集有缺点和失误咋做?

关心2个问题:

一.怎么在属性值缺点和失误情况下进行质量选拔?(简单的讲 表头未有怎么做)

比如说该节点是依照a属性划分,不过待分类样本a属性缺点和失误,如何是好呢?若是a属性离散,有一,二两种取值,那么就把该样本分配到七个子节点中去,可是权重由壹变为相应离散值个数占样本的比重。然后计算错误率的时候,注意,不是各样样本都以权重为一,存在分数。

二.给定划分的属性,若样本缺点和失误,怎样划分?(一句话来讲表头有了,表头里面包车型大巴数量尚未如何是好)

假使你采纳ID叁算法,那么选用分类属性时,将在总括有所属性的熵增(新闻增益,Gain)。借使11个样本,属性是a,b,c。在总计a属性熵时意识,第十二个样本的a属性缺点和失误,那么就把第1一个样本去掉,前七个样本组成新的样本集,在新样本集上按常规情势计算a属性的熵增。然后结果乘0.玖(新样本占raw样本的比例),正是a属性最后的熵。

四.伍 多变量决策树

相对来说于ID三、C④.5、CART那种单变量决策树(分支时只用伍本性质),多变量决策树在分层时用的是多个属性的加权组合,来个直观的图(以下),那么些是单变量决策树学习出来的细分边界,那个边界都是与坐标轴平行的,多变量决策树的剪切边界是倾斜于坐标轴的。

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

ID3

挑选能够获得最大消息增益(information
gain)的特色为多少划分归类,直到全部瓜分截至而不对树的规模实行别的决定。

等树生成之后,实践后剪枝。

新闻增益的暧昧难点是,比如有三个数据集含有八个表征是日期恐怕ID,则该特征会赢得最大的新闻增益,不过明显在证实数据中不会获取其余的结果。C45的音讯增益比正是缓解那些主题素材的。

C45

选取能够获得最大音信增益率(information gain
ratio)的特点来划分数据,并且像ID3均等举行后剪枝。

是ID三的后续版本并扩充了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)。比之C四5,减弱了内部存款和储蓄器,使用更加少的规则集,并且准确率越来越高。

CART

CART(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基本上是相仿的算法,主要不相同:一)它的叶节点不是切实可行的分类,而是是2个函数f(),该函数定义了在该原则下的回归函数。二)CART是二叉树,而不是多叉树。

总结表

图片 7

图片 8

xgboost

终极以下文章对以上内容计算挺好的 http://www.cnblogs.com/bourneli/archive/2013/03/15/2961568.html

先是个算法参考了《机器学习实战》的绝大多数代码,第三、四个算法基于前边的兑现实行模块的加码。

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

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

在宫颈息肉数据集上的测试与表现

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

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

1 Sample
code number (病人ID)
2 Clump
Thickness 肿块厚度
3Uniformity of Cell Size 细胞大小的均匀性
四Uniformity of Cell Shape 细胞形状的均匀性
5
Marginal Adhesion 边缘粘
陆 Single
Epithelial Cell Size 单上皮细胞的轻重
7 Bare
Nuclei 裸核
8 Bland
Chromatin 乏味染色体
9 Normal
Nucleoli 正常核
十Mitoses 有丝区别
11 Class:
二 for benign, 四 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)))

教练出的决策树如下:

图片 9

终极的正确率能够看看:

图片 10

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

自个儿的过敏性阴道炎数据见:http://7xt9qk.com2.z0.glb.clouddn.com/breastcancer.txt

由来,决策树算法ID三的兑现得了,上边考虑基于基尼指数和音讯增益率举行剪切选拔,以及思索达成剪枝进程,因为大家能够见见下面陶冶出的决策树还存在着大多冗余分支,是因为达成过程中,由于数据量太大,每一个分支都不完全纯净,所以会创设往下的支行,可是分支投票的结果又是同样的,而且数据量再大,特征数再多的话,决策树会十分的大万分复杂,所以剪枝一般是必做的一步。剪枝分为先剪枝和后剪枝,假如细说的话能够写大多了。

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

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

ID3算法实现(纯标称值)

若果样本全体是标称值即离散值的话,会比较轻巧。

代码:

图片 11图片 12

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)    
 依照音讯增益,选拔二个最棒的性质

Vote(classList)      
 假使属性用完,体系仍不平等,投票决定

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


用夏瓜数据集2.0对算法举行测试,青门绿玉房数据集见 西瓜数据集2.0,输出如下:

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

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

图片 13

 

鉴于数量太少,未有安装测试数据以验证其准确度,不过本身背后会依照乳腺增生的例子进行准确度的测试的,上边进入下部分:

ID叁算法简要介绍

音讯熵是新闻论中的贰个重大约念,也叫“香农熵”,香农先生的事迹相比较好些个人都听过,一人开创了一门理论,牛的老大。香农理论中一个很关键的特点正是”熵“,即”音讯内容的不鲜明性“,香农在进展新闻的定量测算的时候,显著地把音信量定义为私自不定性程度的压缩。那就评释了她对音信的知道:新闻是用来压缩自由不定性的事物。大概公布为香农逆定义:音讯是鲜明的扩张。那也证实了决策树以熵作为划分接纳的心胸标准的科学,即大家想更迅捷地从数额中获取越多音讯,大家就活该相当慢降低不分明性,即缩减”熵“。

音信熵定义为:

图片 14

D表示数据集,种类总量为|Y|,pk表示D中第k类样本所占的比例。依照其定义,Ent的值越小,音讯纯度越高。Ent的限量是[0,log|Y|]

上边要选择某些属性举办私分,要挨个思考每一种属性,假诺当前怀想属性a,a的取值有|V|种,那么大家愿意取a作为划分属性,划分到|V|个子节点后,全数子节点的音讯熵之和即划分后的新闻熵能够有十分大的缩减,减小的最多的不得了属性就是大家采纳的属性。

分开后的音讯熵定义为:

图片 15 

据此用属性a对样本集D进行剪切的音信增益就是本来的消息熵减去划分后的新闻熵:

图片 16

ID三算法就是那样每趟接纳一性情质对样本集进行分割,知道二种景况使那么些进度结束:

(一)有些子节点样本全体属于壹类

(二)属性都用完了,那时候若是实节点样本照旧不雷同,那么只可以少数服从好些个了

图片 17(图片来源网络)

本文对裁决树算法进行简短的下结论和梳理,并对名牌的裁定树算法ID三(Iterative
Dichotomiser
迭代二分器)进行落到实处,达成应用Python语言,一句老梗,“人生苦短,作者用Python”,Python确实能够省大多言语方面包车型地铁事,从而得以让大家注意于难点和平解决决难点的逻辑。

决策树简单介绍

仲裁树算法不用说我们应该都知晓,是机械学习的叁个盛名算法,由澳洲老牌计算机地艺术学家RoseQuinlan发布。

决策树是①种监督学习的归类算法,目标是学习出一颗决策树,该树中间节点是多少特征,叶子节点是项目,实际分类时依据树的布局,一步一步根据如今数量特征取值选拔进入哪一颗子树,直到走到叶子节点,叶子节点的品类就是此决策树对此数据的就学结果。下图正是一颗轻便的决策树:

图片 18此决定树用来判定3个独具纹理,触感,密度的西瓜是还是不是是“好瓜”。

当有那样3个夏瓜,纹理清晰,密度为0.333,触感硬滑,那么要你认清是不是是三个“好瓜”,那时假诺由此决策树来判别,分明能够直接本着纹理->清晰->密度<=0.38二->否,即此瓜不是“好瓜”,三次决定就那样形成了。正因为决策树决策很便宜,并且准确率也较高,所以平常被用来做分类器,也是“机器学习10大算法”之壹C肆.5的基本思维。

读书出1颗决策树主要考虑多少个主题素材,即 根据数量集创设当前树应该选拔哪个种类属性作为树根,即划分标准? 

想念最棒的事态,1开首选拔某些特征,就把多少集划分成功,即在该特征上取有个别值的全是一类。

思量最坏的景观,不断选取特征,划分后的多寡集总是一无可取,就二分拣职责以来,总是有正类有负类,一向到特征全体用完了,划分的数目集合还是有正有负,那时只可以用投票法,正类多就选正类作为叶子,不然选负类。

据此得出了相似结论:
随着划分的拓展,我们盼望采用四个特点,使得子节点包括的样书尽或许属于同1连串,即“纯度”越高越好。

依照“纯度”的正经不一,有几种算法:

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

二.C四.5算法(Classifier
4.5),ID3 的后继算法,也是昆兰建议

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

据书上说分歧的数目,作者完毕了八个版本的ID三算法,复杂度稳步升高:

有一连值的事态

有一而再值的状态如 西瓜数据集3.0 

一个性格有很各类取值,我们明确不可能每种取值都做3个拨出,那时候要求对连日属性进行离散化,有两种格局供选拔,在那之中三种是:

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

2.C4.5用到的二分法,排序离散属性,取每五个的当心作为划分点的候选点,计算以每种划分点划分数据集的音讯增益,取最大的不得了划分点将一而再属性化为两类成为离散属性,用该属性举办私分的音信增益正是刚刚计算的最大音讯增益。公式如下:

图片 19

此地运用第二种,并在攻读前对连接属性实行离散化。扩充处理的代码如下:

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

图片 20

相关文章

网站地图xml地图