决策树算法基础原理分析

信息的不纯度(决定决策树分支的指标)

不纯度是在决策树中衡量特征分裂优异性的最主要的指标，用于衡量样本在根据某一特征的分类标准分裂后，样本是否被正确分类的准确程度。

主要有 3 种计算方式，分别对应了 3 类决策树：

决策树类别 不纯度计算方式
ID3 信息增益（Information Gain）
C4.5 信息增益率（Information Gain Ratio）
CART 基尼系数（Gini index）

  • 信息熵的计算
    信息熵的计算公式为：

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

    其中$ n $为样本D的类别数，$ p_i $为该样本所占样本总数的比例

  • 信息增益的计算
    信息增益的计算公式：

    $ g(D,A)=H(D)-H(D|A) $

    其中，$ H(D|A) $代表在以$ A $为标准分类后的所有样本的信息熵之和

  • 信息增益率
    信息增益率的计算公式：

    $$ IGR=\frac{g(D,A)}{H(A)} $$

    其中 $ H(A) $代表 $ A $

  • 基尼系数
    基尼系数的计算公式：

    $ Gini(p)=\displaystyle\sum_{i=1}^n p_i (1-p_i) = 1 - \displaystyle\sum_{i=1}^n p_i ^2 $

    其中$ n $为样本D的类别数，$ p_i $为该样本所占样本总数的比例
    基尼系数值越小，表示该分类方法贡献的信息度越高，即不纯度越小

特征的最佳切分点

特征的类型分为两种情况：

  • 离散型变量
  • 连续性变量
  1. 对于离散型变量：
    可分为二叉树与多叉树
  2. 对于连续性变量
    1. 首先将样本的某一连续变量的值去重后按照升序进行排列
    2. 计算两两相邻的平均值
    3. 遍历，将的每一个点都作为该连续变量的切分点，并计算其分裂的不纯度，获得长度为 n − 1 的不纯度集
    4. 其中最大的不纯度，其切分点即为最佳切分点
  3. 特征在决策树中决策的先后顺序
    决策的先后顺序，即为根据不同变量进行分裂的顺序。在找出每个变量的最佳分裂点后，可以计算出以该点分裂所能获得的信息度（信息增益/信息增益率/基尼系数…等），以最大信息度的变量放在最前面进行分裂，最小的放在最后面分裂。这样就确定了在对样本进行区分的时候，越早分裂的样本能以最佳的区分方法进行划分。

ID3, C4.5, CART 对比说明

类型 特点 劣势
ID3 多叉树；特征只用一次；健壮性较好，能训练属性值有缺失的情况 1.当特征取值类型较多时，信息增益会越大，容易造成过拟合；2. 只能用于分类；3. 只能处理离散变量；4. 对缺失值敏感
C4.5 多叉树；特征只用一次；使用信息增益比对特征值多的特征进行惩罚，减少过拟合；可以处理连续变量；可以处理缺失值 处理连续值只是将其离散化，形成多个离散值
CART 二叉树；特征使用多次；可以用于回归任务 -

决策树算法 python 代码实现

创建数据集

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

计算香农熵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 计算香农熵,分两步，第一步计算频率，第二部根据公式计算香农熵
def calcShannonEnt(dataSet):
  numEntries = len(dataSet)
  labelCounts = {}
  for feaVec in dataSet:
      currentLabel = feaVec[-1]
      if currentLabel not in labelCounts:
          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

划分数据集

1
2
3
4
5
6
7
8
9
# 划分数据集，将满足X[aixs]==value的值都划分到一起，返回一个划分好的集合（不包括用来划分的aixs属性，因为不需要）
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

选择划分的最佳属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 选择最好的属性进行划分，思路很简单就是对每个属性都划分下，看哪个好。这里使用到了一个set来选取列表中唯一的元素，这是一中很快的方法
def chooseBestFeatureToSplit(dataSet):
  numFeatures = len(dataSet[0]) - 1  # 因为数据集的最后一项是标签
  baseEntropy = calcShannonEnt(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 * calcShannonEnt(subDataSet)
      infoGain = baseEntropy - newEntropy
      if infoGain > bestInfoGain:
          bestInfoGain = infoGain
          bestFeature = i
  return bestFeature

采用多数表决的方式计算结点分类

1
2
3
4
5
6
7
8
9
# 因为我们递归构建决策树是根据属性的消耗进行计算的，所以可能会存在最后属性用完了，但是分类
# 还是没有算完，这时候就会采用多数表决的方式计算节点分类
def majorityCnt(classList):
  classCount = {}
  for vote in classList:
      if vote not in classCount.keys():
          classCount[vote] = 0
      classCount[vote] += 1
  return max(classCount)

基于递归构造决策树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 基于递归构建决策树。这里的label更多是对于分类特征的名字，为了更好看和后面的理解。
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

调用函数 构造主函数

1
2
3
4
5
6
7
8
9
10
11
def main():
  data, label = createDataSet()
  # t1 = time.clock()
  myTree = createTree(data, label)
  # t2 = time.clock()
  print(myTree)
  # print('execute for ',t2-t1)


if __name__ == '__main__':
  main()

完整源代码

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
#!/user/bin/env python3
# -*- coding: utf-8 -*-


import operator
from math import log
import time


def createDataSet():
  dataSet = [[1, 1, 'yes'],
             [1, 1, 'yes'],
             [1, 0, 'no'],
             [0, 1, 'no'],
             [0, 1, 'no']]
  labels = ['no surfaceing', 'flippers']
  return dataSet, labels


# 计算香农熵,分两步，第一步计算频率，第二部根据公式计算香农熵
def calcShannonEnt(dataSet):
  numEntries = len(dataSet)
  labelCounts = {}
  for feaVec in dataSet:
      currentLabel = feaVec[-1]
      if currentLabel not in labelCounts:
          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


# 划分数据集，将满足X[aixs]==value的值都划分到一起，返回一个划分好的集合（不包括用来划分的aixs属性，因为不需要）
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


# 选择最好的属性进行划分，思路很简单就是对每个属性都划分下，看哪个好。这里使用到了一个set来选取列表中唯一的元素，这是一中很快的方法
def chooseBestFeatureToSplit(dataSet):
  numFeatures = len(dataSet[0]) - 1  # 因为数据集的最后一项是标签
  baseEntropy = calcShannonEnt(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 * calcShannonEnt(subDataSet)
      infoGain = baseEntropy - newEntropy
      if infoGain > bestInfoGain:
          bestInfoGain = infoGain
          bestFeature = i
  return bestFeature


# 因为我们递归构建决策树是根据属性的消耗进行计算的，所以可能会存在最后属性用完了，但是分类
# 还是没有算完，这时候就会采用多数表决的方式计算节点分类
def majorityCnt(classList):
  classCount = {}
  for vote in classList:
      if vote not in classCount.keys():
          classCount[vote] = 0
      classCount[vote] += 1
  return max(classCount)


# 基于递归构建决策树。这里的label更多是对于分类特征的名字，为了更好看和后面的理解。
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


def main():
  data, label = createDataSet()
  # t1 = time.clock()
  myTree = createTree(data, label)
  # t2 = time.clock()
  print(myTree)
  # print('execute for ',t2-t1)


if __name__ == '__main__':
  main()

本文源代码参考自 机器学习——决策树 (Decision Tree)算法原理及 python 实现与python 决策树算法原理及基于 numpy 的代码实现