机器学习实战之决策树

决策树的算法可谓是贴近我们的生活,通过下面的案例,你就会发现我们每天都在有意无意的使用着决策树算法(好厉害的样子)。

小明同学每天早上都要去学校,可步行、乘公交和坐隔壁老王叔叔的车(皮一下很开心)。这时,小明就开始做决策了:首先看天气,不下雨时就选择步行去学校;下雨时就看隔壁老王叔叔是否有空,有空就乘老王的车去学校,没空就选择乘公交去学校。如图所示。

案例

决策树定义

通过上述案例,就可以对决策树下定义了:上图就是决策树(嗯。。。有点敷衍)。决策树由结点和有向边组成。结点有两种类型:内部节点和叶节点,内部节点表示一个特征或属性(天气,是否有空),叶节点表示一个类(步行、乘公交和坐隔壁老王叔叔的车)。

决策树算法原理

那怎么通过决策树算法来构造这棵树呢?(难道是上帝之手么?)上述案例较简单,我们现在提出一个很经典的案例,如图所示,我们首先到底是通过天气、湿度还是风级来进行决策了?这里就要提出熵和信息增益。

案例

首先,我们看什么是熵。简单来说,熵是描述事物的混乱程度的(也可以说是不确定性)。例如:中国足球进入世界杯,这个不确定性可能是0,所以熵可能就是0;6面的色子的不确定性比12面色子的要低,所以熵也会比其低。现在就来看熵的公式:H = -∑<sup>n</sup><sub>i=1</sub>p(xi)log<sub>2</sub>p(xi)

那6面色子的熵:1/6*log<sub>2</sub>1/6的6倍,也就是2.585

以此类推,那12面的熵就是:3.585

最后,我们计算下该案例的信息熵:不打球为5,打球为9,因此熵计算为:

-(5/14 * log(5/14,2) + 9/14 * log(9/14,2))
0.940
信息增益

到底先按哪个特征划分数据集呢?我们有个原则,就是将无序的数据变得有序,换句话说,就是让熵变小,变的越小越好。而信息增益就是划分数据集前后熵的变化,这里就是要让信息增益越大越好。

我们以天气为例,计算划分后的信息增益:

  • 晴天时:2/5打球,3/5不打球,熵为:-(2/5 * log(2/5,2) + 3/5 * log(3/5,2)) 0.971def createBranch(): 检测数据集中的所有数据的分类标签是否相同: If so return 类标签 Else: 寻找划分数据集的最好特征(划分之后信息熵最小,也就是信息增益最大的特征) 划分数据集 创建分支节点 for 每个划分的子集 调用函数 createBranch (创建分支的函数)并增加返回结果到分支节点中 return 分支节点
  • 阴天熵:0
  • 雨天熵:0.971
    天气
    天气为晴天、阴天和雨天的概率为5/14,4/14和5/14,所以划分后的熵为:5/14 0.971+4/14 0+5/14 * 0.971得0.693,信息增益为0.940-0.693为0.247,同理可以求出其他特征的信息增益。 这里的天气信息增益最大,所以选择其为初始的划分依据。 选择完天气做为第一个划分依据后,能够正确分类的就结束划分,不能够正确分类的就继续算其余特征的信息增益,继续前面的操作,结果如图所示。
    结果
    伪代码所以决策树是一个递归算法,伪代码如下:

决策树之海洋生物分类

问题描述与数据

数据为判断是否为鱼类,有两个特征:

  • 在水中是否生存def creatDataSet(): dataSet = [ [1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no'] ] labels = ['no surfacing', 'flippers'] return dataSet, labels这里的dataSet为数据,labels是两个特征的名称。计算熵这里我们定义一个计算数据集熵的函数:from math import log def calcshannon(dataSet): num = len(dataSet) labelCounts = {} for featVec in dataSet: currentLabel = featVec[-1] if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0 labelCounts[currentLabel] += 1 shannon = 0.0 for key in labelCounts: prob = float(labelCounts[key])/num shannon -= prob * log(prob, 2) return shannon这个代码比较简单,就是对传入的数据,以最后一列(也就是分类label)求熵。划分数据集首先设置一个划分数据集的函数,参数为:待划分的数据,划分的特征和返回的特征值,该函数会在choose函数中被调用,用于计算最好的划分特征。def splitDataSet(dataSet, axis, value): retDataSet = [] for featVec in dataSet: if featVec[axis] == value: reduce = featVec[:axis] reduce.extend(featVec[axis+1:]) retDataSet.append(reduce) return retDataSet
  • 是否有脚蹼
    案例
    这里需要我们自己手动构造数据:
def choose(dataSet):
    numfeature = len(dataSet[0]) - 1
    baseEntropy = calcshannon(dataSet)
    bestinfogain = 0.0
    bestfeature = -1
    for i in range(numfeature):
        featlist = [example[i] for example in dataSet]
        vals = set(featlist)
        newEntropy = 0.0
        for value in vals:
            subDataSet = splitDataSet(dataSet, i, value)
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob*calcshannon(subDataSet)
        infoGain = baseEntropy - newEntropy
        if (infoGain > bestinfogain):
            bestinfogain = infoGain
            bestfeature = i
        return bestfeature
创建树

在所有特征使用完时,也没法对数据进行彻底的划分时,就需要使用多数表决来确定叶子节点的分类,代码如下,类似前文中KNN中的排序。

import operator
def majority(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote] = 0
        classCount[vote] += 1
    sortedcount = sorted(classCount.items(),  key=operator.itemgetter(1), reverse=True)
    return sortedcount[0][0]

最后就是创建树的代码:

def 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 majority(classList)
    bestFeat = choose(dataSet)
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}}
    del (labels[bestFeat])
    Vals = [example[bestFeat] for example in dataSet]
    uvals = set(Vals)
    for value in uvals:
        sublabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), sublabels)
    return myTree

这里有两个终止递归的条件:一是所有类别能正确的划分了,二是特征使用完成。

结果

算法优缺点

  • 优点:利于理解
  • 缺点:容易过拟合

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏杨熹的专栏

机器学习算法应用中常用技巧-1

参考:Udacity ML纳米学位 1. 取样 数据量很大的时候,想要先选取少量数据来观察一下细节。 indices = [100,200,300] # 把s...

3157
来自专栏AI派

【Github 5K星】BAT头条滴滴小米等笔试面经+深度学习/算法/NLP资源汇总!

最近,在GitHub上有位id为imhuay的热心人带头建立了一个关于国内知名互联网企业笔试和面试经验的资源库,光从名称上就能看出其内容有多丰富:《2018/2...

651
来自专栏Python中文社区

机器学习实战之决策树

决策树的算法可谓是贴近我们的生活,通过下面的案例,你就会发现我们每天都在有意无意的使用着决策树算法(好厉害的样子)。

982
来自专栏wym

分治算法概念

  分治算法的设计思想是,将一个难以直接诶解决的大问题,分割成一些规模较小的相同的问题,以便各个击破,分而治之。

712
来自专栏AILearning

【机器学习实战】第3章 决策树

第3章 决策树 <script type="text/javascript" src="http://cdn.mathjax.org/mathjax/late...

1875
来自专栏有趣的Python和你

机器学习实战之决策树

1115
来自专栏小鹏的专栏

机器学习算法应用中常用技巧-1

参考:Udacity ML纳米学位 1. 取样 数据量很大的时候,想要先选取少量数据来观察一下细节。 indices = [100,200,300] #...

1877
来自专栏机器学习算法全栈工程师

OpenCV从零基础---检测及分割图像的目标区域

作者:王抒伟 编辑:王抒伟 算了 爱看多久看多久 零 参考目录: 1.获取图片 2.转换灰度并去噪声 3.提取图像的梯度 4.我们继续去噪声 5.图像形态学...

1.6K9
来自专栏python读书笔记

《算法图解》note 9 动态规划1.动态规划定义2.与分治法及贪婪算法的区别3.动态规划的后续学习

1455
来自专栏贾老师の博客

启发式寻路算法

1963

扫码关注云+社区