决策树算法

发表于 | 分类于

0、概述

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。
结点有两种类型：内部节点和叶节点，内部节点表示一个特征或属性，叶节点表示一个类。
分类的时候，从根节点开始，对实例的某一个特征进行测试，根据测试结果，将实例分配到其子结点；
此时，每一个子结点对应着该特征的一个取值。如此递归向下移动，直至达到叶结点，最后将实例分配到叶结点的类中。

1、介绍

1.1、工作原理

对训练数据进行建模，决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。
它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。

1.2、优点，缺点，适用范围

优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
缺点：可能会产生过渡匹配问题。
适用范围：数值型和标称型

1.3、一般流程

收集数据：可以使用任何方法。
准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化。
分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。
训练算法：构造树的数据结构。
测试算法：使用经验树计算错误率。
使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。

2、实现

2.1、伪代码

1
2
3
4
5
6
7
8
9
# 创建分支伪代码函数createBranch()如下所示：
   if so return 类标签;
   else
       寻找划分数据集的最好特征
       划分数据集
       创建分支节点
           for 每个划分的子集
               调用函数createBranch()并增加结果到分支节点中
       return 分支节点

2.2、信息增益

划分数据集的大原则是：将无序的数据变得更加有序。
决策树是通过什么来选择树根，树枝，叶子的呢？这里不得提到两个概念：信息增益和熵。
信息增益：在划分数据集之前之后信息发生的变化称为信息增益。
熵：集合信息的度量方式称为熵。
如果待分类的事务可能分在多个分类之中，则符号x${i}$的信息定义为：
$$
l(x{i}) = - \log2 p(x{i})
$$
其中p(x${i}$)是选择该分类的概率。
为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，公式如下：
$$
H = -\sum{i=1}^{n}p(x_{i})\log2 p(x{i})
$$

2.3、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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
def calcShannoEnt(dataSet):
    '''
    计算给定数据集的香农熵。注意是所有数据的集合，不是单个样本。
    1. get last current ShannoEnt
    :param dataSet:数据集
    :return: 计算结果
    '''
    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
    
def splitDataSet(dataSet,axis,value):
    '''
    按照给定特征划分数据集。最终获得一个子集。举个栗子：
    [[1,1,'yes']
     [1,1,'yes']
     [1,0,'no']
     [0,1,'no']
     [0,1,'no']]
     如果以第二例作为axis，特征值为1，得到下面的子集：
    [[1,'yes']
     [1,'yes']
     [0,'no']
     [0,'no']]
    1. find the value row
    2. del the value from the row
    3. return all the row as []
    :param dataSet:待划分的数据集
    :param axis:划分数据集的特征
    :param value: 需要split的特征值
    :return: 划分结果列表
    '''
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reduceFeatVec = featVec[:axis]
            reduceFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reduceFeatVec)
    return retDataSet
    
def chooseBestFeatureToSplit(dataSet):
    '''
    1.每个特征中的每个特征值分类
    2.计算划分后的香农熵，找出最大熵
    3.得出划分后香农熵最大的特征作为最好的分类特征
    :param dataSet:数据集
    :return:返回分类最好的特征
    '''
    numFeatures = len(dataSet[0]) - 1
    baseEntropy = calcShannoEnt(dataSet)
    bestInfoGain = 0.0;bestFeature = -1
    for i in range(numFeatures):
        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*calcShannoEnt(subDataSet)
        infoGain = baseEntropy - newEntropy
        if(infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature
    
def majorityCnt(classList):
    '''
    采用多数表决的方法决定叶结点的分类
    :param: 所有的 类标签 列表
    :return: 出现次数最多的类
    '''
    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):
    '''
    创建决策树
    :param: dataSet:训练数据集
    :return: 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)
    # 找到最好的Feature，函数名称感觉有点问题，跟ToSplit没有关系
    bestFeat = chooseBestFeatureToSplit(dataSet)
    # 找到对应的标签
    bestFeatLabel = labels[bestFeat]
    # 将当前最好的Feature放到决策树
    myTree = {bestFeatLabel:{}}
    del(labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    # 一个Feature里面有多个值，按不同的值进行构建树的分支
    for value in uniqueVals:
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
    return myTree

3、总结

决策树算法稍微有点复杂，后面还会涉及到剪枝。目前只接触到二叉树，也就是说一个特征值
要么是，要么否，不知道支不支持多分支，看算应该是支持多分支的，有待继续学习。深刻感
觉到理论的重要性，香农熵的概念是这个算法的核心，如果没有选择最优特征值的算法，无法
确定最优二叉树。
坚持原创技术分享，您的支持将鼓励我继续创作！