BruceFan's Blog

Stay hungry, stay foolish

0%

决策树

发表于 Edited on

分类决策树模型是一种描述对实例进行分类的树形结构，决策树由结点和有向边组成，结点有两种类型：内部结点和叶结点。内部结点表示一个特征或属性，叶结点表示一个类。
用决策树分类，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分到叶结点的类中。决策树学习的目的是为了产生一个泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的分而治之（divide-and-conquer）策略。

决策树的构造

在构造决策树时，我们需要解决的第一个问题就是，当前数据集上哪个特征在划分数据分类时起决定性作用。为了找到决定性的特征，划分出最好的结果，我们必须评估每个特征。完成测试之后，原始数据集就被划分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上。如果某个分支下的数据属于同一类型，则已正确地划分数据分类。
下面我们将用ID3算法划分数据集（还有C4.5算法和CART算法，这里先不讨论）。每次划分数据集时我们只选取一个特征属性，那么就需要知道选哪些特征作为划分的参考属性。
下表中有5个海洋动物，特征包括不浮出水面是否可以生存，是否有脚蹼。我们可以将这些动物分成两类：鱼类和非鱼类。要决定用第一个特征还是第二个特征划分数据，需要用到量化的方法——信息增益。

序号 不浮出水面可以生存 有脚蹼 属于鱼类
1 是 是 是
2 是 是 是
3 是 否 否
4 否 是 否
5 否 是 否

信息增益

划分数据集的大原则是：将无序的数据变得更加有序。在划分数据集前后信息发生的变化称为信息增益（information gain），可以计算每个特征值划分数据集获得的信息增益，信息增益越大，说明划分之后的信息熵越小，即数据更加有序。所以信息增益最高的特征就是我们要选择的。
信息论中度量信息的方式称为熵（entropy），熵定义为信息的期望值。假定当前样本集合$D$中第$i$类样本所占的比例为$p_i$(i = 1,2,…,n)，则$D$的信息熵定义为

$$
H(D) = -\sum_{i=1}^n p_i log_2 p_i
$$

$H(D)$的值越小，则$D$越有序。
假定离散属性$a$有$K$个可能的取值{$a^1,a^2,…,a^K$}，用$a$对样本集$D$进行划分，则会产生$K$个分支结点，其中第$k$个分支结点包含了$D$中所有属性$a$的属性值为$a^k$的样本，记为$D^k$。根据上面信息熵公式可以算出$H(D^k)$，再考虑到各个分支所包含的样本数不同，给其赋予权重$|D^v|/|D|$，于是可以计算出属性$a$对样本集$D$进行划分的信息增益：

$$
G(D,a) = H(D)-\sum_{k=1}^K \frac{|D^k|}{|D|} H(D^k)
$$

划分数据集

下面用Python来计算信息熵，创建trees.py：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from math import log

def calcShannonEnt(dataSet):
    numEntries = len(dataSet) # 计算信息数目
    labelCounts = {}
    # 将信息保存到字典中
    for featVec in dataSet:
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    shannonEnt = 0.0
    for key in labelCounts:
        # 计算每种类别的概率
        prob = float(labelCounts[key])/numEntries
        shannonEnt -= prob * log(prob, 2)
    return shannonEnt

接下来在trees.py中创建简单鱼鉴定数据集：

1
2
3
4
5
6
7
8
9
10
11
12
def createDataSet():
    dataSet = [[1, 1, 'yes'],
            [1, 1, 'yes'],
            [1, 0, 'no'],
            [0, 1, 'no'],
            [0, 1, 'no']]
    labels = ['no surfacing', 'flippers']
    return dataSet, labels

myDat, labels = createDataSet()
print myDat
print calcShannonEnt(myDat)

运行结果：

1
2
3
$ python trees.py
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
0.970950594455

可以在数据集中添加数据来观察信息熵的变化情况。
另一种度量集合无需程序的方法是基尼不纯度（Gini impurity），简单地说就是从一个数据集中随机选取子项，度量其被错误分类到其他分组里的概率。本文对基尼不纯度也先不讨论。
接下来我们将对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分是最好的。

1
2
3
4
5
6
7
8
9
10
11
12
# 按照给定特征划分数据集
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

print splitDataSet(myDat, 0, 1)

运行结果：

1
2
3
4
$ python trees.py
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
0.970950594455
[[1, 'yes'], [1, 'yes'], [0, 'no']]

下面我们遍历整个数据集，计算按各个特征划分数据集的信息增益，找到最好的特征划分方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def chooseBestFeatureToSplit(dataSet):
    # 计算共有多少个特征
    numFeatures = len(dataSet[0]) - 1
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0; bestFeature = -1
    # 遍历所有的特征
    for i in range (numFeatures):
        # 特征i有哪些值
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)
        newEntropy = 0.0
        # 遍历所有的特征值
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)
            # 计算按特征i划分后各分支的权重
            prob = len(subDataSet) / float(len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet)
        infoGain = baseEntropy - newEntropy
        if (infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature

print chooseBestFeatureToSplit(myDat)

运行结果：

1
2
3
4
5
$ python trees.py
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
0.970950594455
[[1, 'yes'], [1, 'yes'], [0, 'no']]
0

递归构建决策树

构建决策树的流程是：获得原始数据集，然后基于最好的特征划分数据集，第一次划分之后，数据将被向下传递到树分支的下一个结点，下一个结点再次划分数据，因此可以采用递归方式。
递归结束的条件是：程序遍历完所有划分数据集的特征，或者每个分支下的所有实例都具有相同的分类。
如果数据集已经处理了所有属性，但是类标签依然不是唯一的，此时我们需要采用多数表决的方法决定该叶子结点的分类。

1
2
3
4
5
6
7
8
import operator
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]

创建决策树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}}
    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

print createTree(myDat, labels)

运行结果：

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

决策树最终以嵌套字典的方式表示，最左边是第一个划分特征，不浮出水面，0表示不是鱼类，1再以脚蹼划分。这棵树包含了3个叶子结点和2个判断结点。

reference
《机器学习实战》
《机器学习》
http://atlantic8.github.io/2017/03/02/Decision-Tree/