机器学习实战之决策树

时间:2023-02-13 00:17:53

机器学习实战之决策树

--  Illustrations by Cornelius Bierer --

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

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

机器学习实战之决策树

案例

决策树定义

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

决策树算法原理

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

机器学习实战之决策树

案例

首先,我们看什么是熵。简单来说,熵是描述事物的混乱程度的(也可以说是不确定性)。例如:中国足球进入世界杯,这个不确定性可能是0,所以熵可能就是0;6面的色子的不确定性比12面色子的要低,所以熵也会比其低。现在就来看熵的公式:H = -∑ni=1p(xi)log2p(xi) 那6面色子的熵:1/6*log21/6的6倍,也就是2.585 以此类推,那12面的熵就是:3.585 最后,我们计算下该案例的信息熵:不打球为5,打球为9,因此熵计算为:

 
  1. -(5/14 * log(5/14,2) + 9/14 * log(9/14,2))

  2. 0.940

信息增益

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

  • 晴天时:2/5打球,3/5不打球,熵为:

 
  1. -(2/5 * log(2/5,2) + 3/5 * log(3/5,2))

  2. 0.971

  • 阴天熵: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,同理可以求出其他特征的信息增益。

这里的天气信息增益最大,所以选择其为初始的划分依据。

选择完天气做为第一个划分依据后,能够正确分类的就结束划分,不能够正确分类的就继续算其余特征的信息增益,继续前面的操作,结果如图所示。

机器学习实战之决策树

结果

伪代码

所以决策树是一个递归算法,伪代码如下:

 
  1. def createBranch():

  2.    检测数据集中的所有数据的分类标签是否相同:

  3.        If so return 类标签

  4.        Else:

  5.            寻找划分数据集的最好特征(划分之后信息熵最小,也就是信息增益最大的特征)

  6.            划分数据集

  7.            创建分支节点

  8.                for 每个划分的子集

  9.                    调用函数 createBranch (创建分支的函数)并增加返回结果到分支节点中

  10.            return 分支节点

决策树之海洋生物分类

问题描述与数据

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

  • 在水中是否生存

  • 是否有脚蹼

机器学习实战之决策树

案例

这里需要我们自己手动构造数据:

 
  1. def creatDataSet():

  2.    dataSet = [

  3.        [1, 1, 'yes'],

  4.        [1, 1, 'yes'],

  5.        [1, 0, 'no'],

  6.        [0, 1, 'no'],

  7.        [0, 1, 'no']

  8.    ]

  9.    labels = ['no surfacing', 'flippers']

  10.    return dataSet, labels

这里的dataSet为数据,labels是两个特征的名称。

计算熵

这里我们定义一个计算数据集熵的函数:

 
  1. from math import log

  2. def calcshannon(dataSet):

  3.    num = len(dataSet)

  4.    labelCounts = {}

  5.    for featVec in dataSet:

  6.        currentLabel = featVec[-1]

  7.        if currentLabel not in labelCounts.keys():

  8.            labelCounts[currentLabel] = 0

  9.        labelCounts[currentLabel] += 1

  10.    shannon = 0.0

  11.    for key in labelCounts:

  12.        prob = float(labelCounts[key])/num

  13.        shannon -= prob * log(prob, 2)

  14.    return shannon

这个代码比较简单,就是对传入的数据,以最后一列(也就是分类label)求熵。

划分数据集

首先设置一个划分数据集的函数,参数为:待划分的数据,划分的特征和返回的特征值,该函数会在choose函数中被调用,用于计算最好的划分特征。

 
  1. def splitDataSet(dataSet, axis, value):

  2.    retDataSet = []

  3.    for featVec in dataSet:

  4.        if featVec[axis] == value:

  5.            reduce = featVec[:axis]

  6.            reduce.extend(featVec[axis+1:])

  7.            retDataSet.append(reduce)

  8.    return retDataSet

 
  1. def choose(dataSet):

  2.    numfeature = len(dataSet[0]) - 1

  3.    baseEntropy = calcshannon(dataSet)

  4.    bestinfogain = 0.0

  5.    bestfeature = -1

  6.    for i in range(numfeature):

  7.        featlist = [example[i] for example in dataSet]

  8.        vals = set(featlist)

  9.        newEntropy = 0.0

  10.        for value in vals:

  11.            subDataSet = splitDataSet(dataSet, i, value)

  12.            prob = len(subDataSet)/float(len(dataSet))

  13.            newEntropy += prob*calcshannon(subDataSet)

  14.        infoGain = baseEntropy - newEntropy

  15.        if (infoGain > bestinfogain):

  16.            bestinfogain = infoGain

  17.            bestfeature = i

  18.        return bestfeature

创建树

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

 
  1. import operator

  2. def majority(classList):

  3.    classCount = {}

  4.    for vote in classList:

  5.        if vote not in classCount.keys():

  6.            classCount[vote] = 0

  7.        classCount[vote] += 1

  8.    sortedcount = sorted(classCount.items(),  key=operator.itemgetter(1), reverse=True)

  9.    return sortedcount[0][0]

最后就是创建树的代码:

 
  1. def createTree(dataSet, labels):

  2.    classList = [example[-1] for example in dataSet]

  3.    if classList.count(classList[0]) == len(classList):

  4.        return classList[0]

  5.    if len(dataSet[0]) == 1:

  6.        return majority(classList)

  7.    bestFeat = choose(dataSet)

  8.    bestFeatLabel = labels[bestFeat]

  9.    myTree = {bestFeatLabel:{}}

  10.    del (labels[bestFeat])

  11.    Vals = [example[bestFeat] for example in dataSet]

  12.    uvals = set(Vals)

  13.    for value in uvals:

  14.        sublabels = labels[:]

  15.        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), sublabels)

  16.    return myTree

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

机器学习实战之决策树

结果

算法优缺点

  • 优点:利于理解

  • 缺点:容易过拟合


作者罗罗攀,Python中文社区专栏作者,《从零开始学网络爬虫》图书作者。专栏地址: http://www.jianshu.com/u/9104ebf5e177


机器学习实战之决策树

Python中文社区作为一个去中心化的全球技术社区,以成为全球20万Python中文开发者的精神部落为愿景,目前覆盖各大主流媒体和协作平台,与阿里、腾讯、百度、微软、亚马逊、开源中国、CSDN等业界知名公司和技术社区建立了广泛的联系,拥有来自十多个国家和地区数万名登记会员,会员来自以*部、工信部、清华大学、北京大学、北京邮电大学、中国人民银行、中科院、中金、华为、BAT、谷歌、微软等为代表的*机关、科研单位、金融机构以及海内外知名公司,全平台近20万开发者关注。

机器学习实战之决策树

▼ 点击下方阅读原文免费成为社区会员