前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >一文搞懂决策树

一文搞懂决策树

作者头像
somenzz
发布2020-11-25 10:17:01
5550
发布2020-11-25 10:17:01
举报
文章被收录于专栏:Python七号

阅读本文大概需要 6 分钟。

有一个房间,里面有 100 个人,每个人有 100 元。每过一会,每个有钱的人给随机的其他人 1 元,经过一段时间后,房间内的资金分配情况是怎样?

也许有人会认为最终大家的钱趋于平均数,其实不然,你可以使用自己熟悉的编程语言来实现,下图的结果是模拟 45 人初始为 45 元的结果,100 个人结果也是一样的。

这个结果和现实世界中的财富占比是一致的,我想,这大概就是运气吧。

不确定性才是客观世界的本质属性。换句话说,上帝还真就掷骰子。不确定性的世界只能使用概率模型来描述,通过概率模型来量化信息量,进而做出各种预测,来帮助决策。本文介绍机器学习中的决策树算法,如果你能看懂,我的目的就达到了。

先提出一个问题:如何让计算机生成一个树,根据眼睛、头发、身高来区分一个人是不是东方人?训练数据集如下所示:

为了让你有个直观的认识,这里先给出答案:

有了这个树,再依据眼睛、发色、身高来判断是否是东方人,就非常简单了,这个树就是决策树。

你肯定想知道,这是怎么做到的?

程序、算法都是人脑设计的,想弄明白电脑是如何做的,先思考人脑会如何解决这个问题。

为了创建决策树,我们先要选择一个节点作为根节点,有三个特征,该选哪个呢?理论上所有特征都可以作为根节点,但如果选择不恰当,会导致树有非常多的分叉,变得臃肿,决策时效率非常低下。最简化的情况是树只有一层,只使用一个特征就可以满足判断。因此选择根节点时要选择最有区分度的那个特征作为根节点,也就是说仅凭这个特征就可以判断出大多数结果,本例中眼睛这个特征就符合这个条件,如果眼睛是蓝色和黑色,可以直接判断结果,只有是棕色时,需要借助其他特征。

根节点确定之后,在剩余特征中选择最有区分度的特征作为子节点,本例子中就是头发。通过分析发现,仅使用眼睛、头发两个特征就可以将所有结果判断完毕,因此也就不需要身高加入决策树。

总结一下,就是选择最有区分度的特征作为根节点,次有区分度的作为子节点,再次之,直到特征用完。

人脑可以靠观察分析判断,电脑如何量化这种区分度呢?这里就要引用信息量,信息熵,信息增益这些概念,不用慌,这个其实好理解。

熵的本质,是一个系统内存的混乱程度,熵越大,代表越混乱,越无序。比如气体扩散后不可能自己缩回去,温度只能自发从高温传到低温,这些都是熵增的过程。而我们整理混乱的房间,系统性的学习知识,努力的工作,则是熵减的过程。

在生活中,信息的载体是消息,而不同的消息带来感觉也是不同的。比如,“中国男子足球队获得世界杯冠军”的信息显然要比“中国男子乒乓球队获得世界杯冠军”的信息量要大得多。究其原因,国足勇夺世界杯是小概率事件,发生的可能性微乎其微;而男乒夺冠已经让国人习以为常,丢掉冠军才是意外。因此,以不确定性来度量信息是一种合理的方式。不确定性越大的消息可能性越小,其提供的信息量就越大。

“熵”这个词来源于百科全书式的科学家约翰·冯诺伊曼,香农把它引申到信息论,用于量化信息量

信息量的单位为比特,假如中国男子足球队获得世界杯冠军的概率为 1/1000,则其信息量约为 10 比特,国乒夺冠概率为 1/2 的话,则其信息量仅为 1 比特,如果一件事情百分之百发生,那么信息量为 0 比特。

因此概率越小,其熵越大,说明信息量越大。

假如一个信息包含多个信源,求得这些信源信息量的数学期望,就可以得到信源熵(信息熵),上述例子中判断是否为东方人这一信息就包含头发,眼睛,身高这三个信源。

信息熵的差就是信息增益

例子一:一个盒子中分别有 5 个白球和 5 个黑球,随机取出一个球判断它的颜色?这个问题信息量多大呢?由于黑球和白球出现的概率都是1/2,那么就可以得到其信息熵为:

H(x1)= - (1/2*log2(1/2)+1/2*log2(1/2)) = 1

是的,这里的信息熵是 1 比特。

例子二:有黑白两个盒子,黑色装 5 个黑球,白色装 5 个白球,随意从这两个盒子取一个球,颜色不用判断了,这个问题的信息量有多大呢?

H(x2)= - (1/2*1*log2(1)+1/2*1*log2(1)) = 0

信息增益为 Gain(2) = H(x1) - H(x2) = 1-0=1

例子三:有黑白两个盒子,黑色装 4 个黑球 1 个白球,白色装 4 个白球 1 个黑球,随意从这两个盒子取一个球,判断颜色,这个问题的信息量有多大呢?

H(x3)= - (1/2*(1/5*log2(1/5)+4/5*log2(4/5))+1/2*(1/5*log2(1/5)+4/5*log2(4/5))) = 0.7219280948873623

信息增益为 Gain(3) = H(x1) - H(x3) = 1 -0.7219280948873623 = 0.2780719051126377

因为 Gain(2) > Gain(3) ,因此例子二的分法更有区分度。从概率上也能说明问题:从例子二的盒子中拿到黑球的概率是 100%,从例子三中拿到黑球的概率是 80%(4/5),从例子一中拿到黑球的概率是 50%。

同样的道理,我们计算眼睛、发色、身高三个特征的信息增益来选择最佳的特征。

第一步:计算训练数据集的总信息熵

数据共 11 条,有 6 条结果是 yes, 有 5 条结果是 no。 H(总)= -(6/11*log2(6/11)+5/11*log2(5/11)) = 0.9940302114769565

第二步:分别计算每个特征的信息熵和信息增益

先看眼睛,眼睛为 Black 的有 4 条,其中全部是东方人

H(eye=Black)=-1*log2(1) = 0

眼睛为 Blue 的有 4 条,其中全部不是东方人

H(eye=Blue)=-1*log2(1) = 0

眼睛为 Brown 的有 3 条,其中 2 个是东方人,1 个不是东方人: H(eye=Brown)=-(2/3*log2(2/3)+1/3*log2(1/3)) = 0.9182958340544896

总条数为 11 条,其中 eye = Black 的占 4 条,eye = Blue 的占 4 条,eye = Brown 的占 3 条,对三种颜色求期望可得到眼睛的信息熵为: H(eye)=4/11 * H(eye=Black) + 4/11*H(eye=Blue)+3/11*H(eye=Brown)=0+0+3/11*0.9182958340544896 = 0.2504443183784972

信息熵与概率的关系如下图所示:

可以看出,当概率 P(x) 越接近 0 或者 1 时,信息熵越小,其不确定性越小,即数据越纯信息熵越小,说明越有序。

因此眼睛这个特征的 信息增益 为 Gain(眼睛)= H(总)-H(eye) = 0.9940302114769565-0.2504443183784972 = 0.7435858930984593

信息增益越大,说明特征的信息熵越小,则说明该特征越有序,更有区分度。

我们在选择特征时,选择信息增益最大的特征,即,让数据尽量往更纯净的方向上变换,因此,信息增益是用来衡量数据变得更有序、更纯净的指标。

我们按第二步的方法求出所有特征的信息增益,并排序。

Gain(眼睛信息增益) = 0.7435858930984593

Gain(头发信息增益) = 0.4040097573248599

Gain(身高信息增益) = 0.00723448672483451

因此我们可以按照 眼睛-> 头发 -> 身高 的顺序来构建决策树。

第三步:构建决策树

眼睛做为根节点确认之后,发现眼睛的取值有 3 个,因此从眼睛出发,有 3 条线,分别为 Black、Bule、Brown,其中 Black 和 Bule 的结果都是一致的 yes 或 no,因此也可直接得出结论,不需要再有子节点。

当为眼睛 Brown 时结果有两个 yes 和 一个 no,此时需要借助具有第二区分度的特征 头发 来再次判断。

处理头发时,道理是一致的,编码时可以递归处理,最终发现不需要借助 身高 这个特征就可以将所有数据判断完毕,此时树构建完毕。

获取源代码

创建决策树的函数如下:

代码语言:javascript
复制
def createTree(dataSet, labels):
    """
    Desc:
        创建决策树
    Args:
        dataSet -- 要创建决策树的训练数据集
        labels -- 训练数据集中特征对应的含义的labels,不是目标变量
    Returns:
        myTree -- 创建完成的决策树
    """
    classList = [example[-1] for example in dataSet]
    # 如果数据集的最后一列的第一个值出现的次数=整个集合的数量,也就说只有一个类别,就只直接返回结果就行
    # 第一个停止条件:所有的类标签完全相同,则直接返回该类标签。
    # count() 函数是统计括号中的值在list中出现的次数
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    # 如果数据集只有1列,那么最初出现label次数最多的一类,作为结果
    # 第二个停止条件:使用完了所有特征,仍然不能将数据集划分成仅包含唯一类别的分组。
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)

    # 选择最优的列,得到最优列对应的label含义
    bestFeat = chooseBestFeatureToSplit(dataSet)
    # 获取label的名称
    bestFeatLabel = labels[bestFeat]
    # 初始化myTree
    myTree = {bestFeatLabel: {}}
    # 注:labels列表是可变对象,在PYTHON函数中作为参数时传址引用,能够被全局修改
    del(labels[bestFeat])
    # 取出最优列,然后它的branch做分类
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        # 求出剩余的标签label
        subLabels = labels[:]
        # 遍历当前选择特征包含的所有属性值,在每个数据集划分上递归调用函数createTree()
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
        # print('myTree', value, myTree)
    return myTree

本公众号后台回复「决策树」获取完整源码。如果有任何疑问欢迎加微信与我交流。

(完)

专注于Python技术分享

欢迎订阅、在看、转发

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-07-07,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Python七号 微信公众号,前往查看

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

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档