机器学习算法系列（1）决策树

发表于 | 更新于 | 分类于 | 阅读次数：

决策树（decision tree）是一类常见的机器学习（分类）方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策树对新数据进行分析。

  • 决策树的模型与学习
  • 特征选择
  • 决策树的生成

1. 决策树的模型与学习

1.1 简单的例子：选西瓜的一棵决策树

一般，一颗决策树包含一个根节点（node），若干个内部结点（internal node）和若干个叶节点（leaf node）；叶节点对应于决策结果，其他每个结点对应于一个属性测试；每个结点包含的样本的集合根据属性测试的结果被划分到子节点中。

选择西瓜的决策树

在沿着决策树从上到下的遍历过程中，在每个结点都有一个测试。对每个结点上问题的不同测试输出导致不同的分支，最后会达到一个叶子结点。这一过程就是利用决策树进行分类的过程，利用若干个变量来判断属性的类别。

Photo by Sticker Mule on Unsplash

1.2 决策树模型

决策树（decision tree）是一类常见的机器学习（分类）方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策树对新数据进行分析。

决策树本质上是从训练数据集中归纳出一组分类规则，决策树学习通常包括三个步骤：特征选择、决策树生成和决策树修剪。

1.3 决策树和归纳算法

  • 决策树技术发现数据模式和规则的核心是归纳算法
  • 归纳是从特殊到一般的过程
  • 归纳推理从若干个事实中表征出的特征、特性和属性中，通过比较、总结、概括而得出一个规律性的结论
  • 归纳推理视图从对象的一部分或整体的特定的观察中获得一个完备且正确的描述，即从特殊事实到普遍性规律的结论
  • 归纳对于认识的发展和完善具有重要的意义。人类知识的增长主要来源于归纳学习，机器也是如此。

从特殊的训练样例中归纳出一般函数是机器学习的核心问题，从训练样例中进行学习的过程：

1
2
3
4
5
6
7
1. 训练集D={(x1,y1), (x2,y2),…,(xn,yn)}，属性集A={a1,a2,…,av}

2. 学习过程将进行对目标函数f的不断逼近，每一次逼近都叫做一个假设h

3. 假设需要以某种形式进行，如，y=ax+b。通过调整假设的表示，即应用不同算法，产生出假设的不同变形

4. 从不同的变形中选择最佳的组合

1.4 选择方法

使训练值与假设值预测出的值之间的误差平方和Err最小

1.5 决策树算法

  • 决策树相关的重要算法包括：ID3，C4.5，CART

  • 决策树算法的发展历程

    • Hunt,Marin和Stone 于1966年研制的CLS学习系统,用于学习单个概念。

    • 1979年, J.R. Quinlan 给出ID3算法,并在1983年和1986年对ID3进行了总结和简化,使其成为决策树学习算法的典型。

    • Schlimmer 和Fisher于1986年对ID3进行改造,在每个可能的决策树节点创建缓冲区,使决策树可以递增式生成,得到ID4算法。

    • 1993年,Quinlan 进一步发展了ID3算法,改进成C4.5算法。

    • 另一类决策树算法为CART,与C4.5不同的是,CART的决策树由二元逻辑问题生成,每个树节 点只有两个分枝,分别包括学习实例的正例与反例。

Photo by Andre Benz on Unsplash

2. 特征选择

决策的关键在于如何选择最优划分属性一般而言，随着划分过程不断进行，决策树分支结点所包含的样本尽可能属于同一类别，即“纯度”越来越高。通常特征选择的准则是信息增益（information gain）或信息增益比(gain ratio)。

2.1 信息熵（Entropy）

三十而立，四十而不惑，五十知天命…人生，就是一次熵不断变小的过程。

香农1948年提出信息论理论，在信息论和概率统计中，熵（entropy）是表示随机变量不确定性的度量，用来度量样本集合纯度最常用的一些指标。样本集合D中第k类样本所占比例为pk（k=1,2,…,|y|），则D的信息熵定义为：

熵越大，随机变量的不确定性越大。当D服从0,1分布时，熵与不确定性程度的关系：

熵与不确定性程度的关系

如图，当p为0或1时，熵值最小，随机变量完全没有不确定性，当p=0.5时，熵值达到最大值，随机变量的不确定性最大。

2.2 信息增益（Information gain）

假定离散属性a有V个可能的取值{a1,a2,…,aV}，使用a对样本集进行划分，则会产生V个分支结点，其中第v个分支结点包含了D中所有在属性a上取值为av的样本，记为Dv，于是可以计算出属性a对样本集D进行划分所获得的信息增益（information gain）：

信息增益表示得知属性a的信息而使得D的信息不确定性减少的程度，决策树学习中的信息增益等价于训练数据集中划分属性与类别的互信息（mutual information）。

  • 信息增益表示属性a使得数据集D的分类不确定性减少的程度

  • 对于数据集D而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益

  • 信息增益大的特征具有更强的分类能力

  • 信息增益指标可能会出现泛化能力不佳的情形，假如用编号作为划分指标，那么信息增益将达到最大值，显然，这样的决策树不能对新样本进行预测

2.3 信息增益率（Gain ratio）

著名的C4.5决策树算法不直接使用信息增益，而是使用信息增益率（gain ratio）来选择最优划分属性，增益率定义为：

IV(a)称为a属性的“固有值”(intrinsic value)，所以一般增益率准则对数目较少的属性有所偏好。如果av属性的数目越大，IV(a)相应也会变大，所以比较其增益就没有太大优势。举个例子，如果需要你选择一个特征来划分人群，身份证号码是一个完美的选择，但是我们并不能在实际中应用这个特征。选择信息增益率来做特征选择就是为了避免出现这种状况，我们不仅仅要考量特征对数据的划分能力，而且还需要考察特征本省的信息熵。

2.4 基尼指数（Gini index）

CART决策树使用基尼指数来选择划分属性，数据集D的纯度可以用基尼值来度量：

Gini(D)反映了从数据集中随机抽取两个样本，其类别标记不一致的概率，因此Gini(D)越小，数据集D的纯度越高

于是，属性集合A中，选择使得划分后基尼指数最小的属性作为最优划分属性

3. 决策树的生成

  • ID3算法

  • ID3算法-流程

  • ID3算法-小结

  • C4.5算法

3.1 决策树ID3算法

  • ID3算法是一种经典的决策树学习算法，由Quinlan与1979年提出。

  • ID3算法主要针对属性选择问题。是决策树学习方法中最具影响和最为典型的算法。

  • ID3采用信息增益度选择测试属性。

  • 当获取信息时，将不确定的内容转为确定的内容，因此信息伴随不确定性。

在决策树分类中，假定D是训练样本集合，|D|是训练样本数，离散属性a有V个可能的取值{a1,a2,…,aV}，使用a对样本集进行划分，则会产生V个分支结点，其中第v个分支结点包含了D中所有在属性a上取值为av的样本，记为Dv，于是可以计算出属性a对样本集D进行划分所获得的信息增益（information gain）：

信息增益表示得知属性a的信息而使得D的信息不确定性减少的程度。经验条件熵H(D|A)表示在特征A给定的条件下对数据集D进行分类的不确定性，它们的差，即信息增益。

3.2 决策树ID3算法-流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

输入： 训练数据集D，特征集A，阈值ε；

输出： 决策树T

（1） 若D中所有实例均属于同一类Ck，则T为单节点树，并将Ck>作为该节点的类标记，返回T；

（2） 若A=∅，则T为单节点树，并将D中实例树最大的类Ck作为该节点的类标记，返回T；

（3）否则，按照信息增益的计算方法，选择信息增益最大的特征Ag;

（4）如果的信息增益小于阈值，则置T为单节点树，并将D中实例数最大的类Ck作为该节点的类标记，返回T；

（5）否则，对Ag的每一可能值ai，依Ag=ai将D分割为若干非空子集Di，将中实例最大的类作为标记，构建子结点，由结点及其子节点构成树T，返回T；

（6）对第i个子结点，以Di</sub>为训练集，以A-{Ag}为特征集，递归地调用步（1）~步

（5），得到子树Ti，返回Ti

3.3 ID3算法-小结

ID3算法的基本思想是，以信息熵为度量，用于决策树结点的属性选择，每次优先选取信息量最多的属性，构建一棵熵值下降最快的决策树，到叶节点处的熵值为0

3.4 决策树C4.5生成算法

ID3算法只有树的生成，所以该算法容易生成的树很容易产生过拟合，从而泛化能力不佳。C4.5的算法过程与ID3类似，只是属性选择的指标换成了信息增益比。

4. Python 实现代码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
from math import log
import operator

def credataSet():
    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 = credataSet()

labels

    ['no surfacing', 'flippers']

feat = [example[1] for example in dataset]

set(feat)

    {0, 1}

#计算信息熵
def calEnt(dataset): 
    numEnteries = len(dataset) 
    # 新建一个空的字典，这种用法通常用于数据集中字段计数
    labelCounts = {} 
    for featVec in dataset:
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1 
    Ent = 0.0
    for key in labelCounts:
        # 先转换为浮点
        prob = float(labelCounts[key]) / numEnteries 
        Ent -= prob * log(prob, 2)
    return Ent

ent = calEnt(dataset)

# 按照指定特征划分数据集
# dataset：待划分的数据集，axis：划分数据集特征
# value：返回的特征的值
def splitDataSet(dataset, axis, value): 
    retDataSet = []
    for featVec in dataset:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

splitdata = splitDataSet(dataset, 0, 1)

splitdata

    [[1, 'yes'], [1, 'yes'], [0, 'no']]

def chooseBestFeatureToSplit(dataset):
    numFeatures = len(dataset[0]) - 1
    baseEntropy = calEnt(dataset)
    bestInfoGain = 0.0; bestFeature = -1 
    for i in range(numFeatures): 
        # 取每一个样本的第i+1个元素，featList = [1, 1, 0, 1, 1]
        # set(featList) = {0,1}，set是得到列表中唯一元素值的最快方法
        featList = [example[i] for example in dataset] 
        uniqueVals = set(featList) 
        newEntropy = 0.0
        for value in uniqueVals:
            # 遍历特征下属性值，对每一个属性值划分一次数据集
            subDataSet = splitDataSet(dataset, i, value) 
            prob = len(subDataSet)/float(len(dataset)) 
            newEntropy += prob * calEnt(subDataSet)
        # 计算两个特征各自的信息增益，并进行比较
        infoGain = baseEntropy - newEntropy 
        if (infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature

bestfeature = chooseBestFeatureToSplit(dataset)

majorityCnt(classList)函数使用分类名称的列表然后创建值为classList中唯一值的数据字典，字典对象存储了classList中每个类标签出现的频率，最后利用operator操作键值排序字典，并返回出现次数最多的分类名称。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys(): classCount[Vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

def createTree(dataset, labels):
    classList = [example[-1] for example in dataset]
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    # 如果数据的长度为1，那么意味着所有的特征都用完了，分类完毕并返回次数最多的分类名称
    if len(dataset[0]) == 1: 
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataset)
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}}
    # 当dataset的特征被选中为bestFeat后便不再作为候选划分特征，所以要删除掉
    del(labels[bestFeat]) 
    featValues = [example[bestFeat] for example in dataset]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataset, bestFeat, value), subLabels)
    return myTree

createTree(dataset, labels)

    {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

推荐阅读

  • 周志华.机器学习[M].2016年1月第一版.清华大学出版社.2016

  • 李航.统计学习方法[M].2012年3月第1版.清华大学出版社.2015

继续阅读机器学习算法系列笔记！

------本文结束，欢迎收藏本站、分享、评论或联系作者！------
相关文章
点击查看
赠人玫瑰 手有余香
0%