决策树

目录
  1. 信息增益
  2. 划分数据集
  3. 递归构建决策树

信息增益

划分数据集的最大原则是：将无序数据变得更加有序。

在划分数据集之前之后信息发生的变化称为信息增益。

信息增益(熵)定义为信息的期望。如果待分类的事务可能划分在多个分类中，则符号$x_i$的信息定义为：

$l(x_i) = -\log_2p(x_i)$

为了计算熵，我们需要计算所有类别所有可能值包含的信息期望，通过下面公式得到：

$H = - \sum_{i=1}^np(x_i)\log_2p(x_i)$


其中n是分类的数目。

划分数据集

  • 目的：找到数据集的最佳划分
  • 依据：信息增益最大
  • 步骤：
    1. 对数据集中的每个特征（$x_i$）划分数据集；
    2. 计算每种划分划分方式的信息熵；
      1. 对$x_i$找出它的唯一分类标签（特征$x_i$的不同取值）列表；
      2. 使用列表中的每个值划分数据；（可能多余2个划分，ID3算法）
      3. 计算每个划分的信息；
      4. 把3中的信息相加，得到该划分方式的信息熵。
    3. 选出最好的信息增益，返回该特征。

递归构建决策树

  • 原理：

    得到原始数据集，然后基于最好的属性划分数据集；第一次划分之后，数据将被向下传递到树分支的下一个节点，在这个节点上，再次划分数据集。

  • 递归条件：

    1. 程序遍历完所有划分数据集的属性；
    2. 或每个分支下的说有实例都具有相同的分类。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def createTree(dataSet,labels):
    classList = [example[-1] for example in dataSet]
    if classList.count(classList[0]) == len(classList):
        return classList[0] #stop splitting when all of the classes are equal
    if len(dataSet[0]) == 1: #stop splitting when there are no more features in dataSet
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}}
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    subLabels = labels[:]       #copy all of labels, so trees don't mess up existing labels
    del(subLabels[bestFeat])
    for value in uniqueVals:
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
    return myTree
1
2
3
4
In [7]: myTree = trees.createTree(myDat, labels)

In [8]: myTree
Out[8]: {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

Matplotlib 绘制决策树

评论