决策树笔记：使用ID3算法

机器学习

---

先说一个偶然的想法：同样的一堆节点构成的二叉树，平衡树和非平衡树的区别，可以认为是“是否按照重要度逐渐降低”的顺序来分叉的。

其实这个也不一定局限于平衡树的解释。huffman编码就是这么干的：出现频率最高的编码一定是与root直接相连的，是层数最浅的。

什么是决策树

简单讲就是一棵多叉树，每个节点表示一个决策，它的不同分支表示依据决策结果划分的子类；子树要么仍然是决策数，要么是叶节点。叶节点表示原有label或某一个维度属性。

决策树算法，就是用训练数据构造一棵决策树，作为分类器，为测试数据使用。因此，决策树是一个学习的结果，是一个模型。

ID3算法是基于信息熵的决策树构造算法。假设你处于这样一个环境：你需要判断一个事物的类别，你只能通过问一系列问题来判断。显然，每次问的问题越有质量，就越容易得到答案。什么样的问题算有质量？能最大限度获取信息、使得你能缩小猜测范围，这样的问题是有质量的问题。这个过程持续进行，直到猜到该事物的分类。

在猜测过程中，所谓“尽可能缩小分类范围”，也就是每次得到尽可能多的信息。信息论中，使用信息熵表示不确定程度，信息熵越大，越不确定；信息熵越小，信息越多，事物越确定。因此，每一次决策都试图去获得最大的信息熵负增量，就是获得越多的信息。so，每一次决策时，我怎么知道信息熵是多少？

比如用于训练的向量形如$(a,b,c,label)$，那么我我依次用a、b、c属性节点做决策，看看使用这个属性后，我能得到信息熵负增量是多少。比较每一个决策点，选一个最大值作为本次决策节点。

设$p_i$表示事件i出现的概率，依据信息论可知，信息熵等于

$$-∑p_i log\ p_i$$

信息熵公式的证明

这个公式的证明似乎没有什么用处，看看就好。通过阅读Shannon那篇A Mathematical Theory of Communication的附录2不难推出。

考虑如下情形：你需要确定下一件发生的事件，然而你只知道每一个事件发生的概率：$p_1$,$p_2$,...,$p_n$。用$H$表示本次决策的熵。我们的决策基于如下3个假设：
1. $H$在$p_i$处连续
2. 若所有$p_i$相等，即$p_i$=$1\over n$，则$H$为n的严格增函数
3. 若某一个选择被打散，变为两次连续的选择，则原有$H$应等于各独立的$H$的权和。

个人认为假设3最重要，也很难翻译准确，原文如下：

If a choice be broken down into two successive choices, the original $H$ should be the weighted sum of the individual values of $H$.

例如

从左边的树状图转换到右边一个树状图，是后两个分支先合并在分离，原来的一次决策变为两次决策，才能确定后面两个节点：

$$H(\frac{1}{2},\frac{1}{3},\frac{1}{6})=H(\frac{1}{2},\frac{1}{2})+\frac{1}{2}H(\frac{2}{3},\frac{1}{3})$$
其中\frac{1}{2}表示这个分支的概率。这个假设能用来把平面式的数据塑造为树状、有层次的数据，在后面起到重要作用。

公式$A(s^m)=mA(s)$的证明

假设$A(n)=H(\frac{1}{n},\frac{1}{n},...,\frac{1}{n})$，怎样证明$A(s^m)=mA(s)$？

$A(s)$可以看作：root节点只有一层子节点，子节点一共有$s$个，每个子节点被选中的概率为$\frac{1}{s}$。

$A(s^m)$则可以看作：root节点只有一层子节点，子节点一共有$s^m$个，每个子节点被选中的概率都是$\frac{1}{s^m}$。

如果把对于任意一个$\frac{1}{s^m}$概率事件的确定，从原有的一步分解为两步：先做$\frac{1}{s}$再做$\frac{1}{s^{m-1}}$，那么熵值$H$的计算依据假设（3）即可计算：通过把$A(s^m)$的每$s^{m-1}$个连续的分支搓成一股，下一股则为$A(s^{m-1})$，得到：

$$A(s^m)=A(s)+\frac{1}{s}*A(s^{m-1})*s\\=>A(s^m)=mA(s)$$

公式$A(t)=K\ log\ t$的证明

$$\forall n, \exists m, s.t.s^m \le t^n \lt s^{m+1}$$
取对数并除以 $n\ log\ s$，有：
$$\frac{m}{n} \le \frac{log\ t}{log\ s} \lt \frac{m}{n} + \frac{1}{n}，\\即：|\frac{log\ t}{log\ s} - \frac{m}{n}| \lt \frac{1}{n} \to 0$$
由 假设2 $A(n)$对n严格增有：
$$A(s^m) \lt A(t^n) \lt A(s^{m+1}) \\=> mA(s) \le nA(t) \lt (m+1)A(s)$$
同除 $nA(s)$:
$$\frac{m}{n} \lt \frac{A(t)}{A(s)} \lt \frac{m}{n} + \frac{1}{n} \\=> |\frac{m}{n} - \frac{A(t)}{A(s)}| \lt \frac{1}{n} \to 0$$
由上面两个趋向于0的绝对值不等式有：
$$|\frac{A(t)}{A(s)}-\frac{log\ t}{log\ s}| \to 0 \\=> A(t)=K\ log\ t, K>0$$

信息熵公式$H(p_1,...,p_n)=-K\sum(p_i\ log\ p_i)$的证明

假设有$n$组事件，第$i$组有$n_i$个事件，选中第$n_i$的概率为$p_i$。注意此时事件总数是$\sum n_i$而不是$n$。
此时确定下一个事件，有假设3，可以先从$n$组事件中选出$n_i$这一组，然后再从这$n_i$个事件中选择一个。这第二次选择是等概率的。因此有：

$$H_{总体}=K\ log\ \sum n_i = H(p_1,...,p_n)+K\sum p_i\ log\ n_i \\=>H(p_1,...,p_n)=K(log\sum n_i - \sum p_i \ log\ n_i)$$
由 $\sum p_i=1$有：
$$log\ \sum n_i=\sum p_i\ log \sum n_i \\=> H(p1,...,pn)=K(\sum p_i\log \sum n_i - \sum p_i \ log\ n_i) \\= -K\sum p_i\ log \frac{n_i}{\sum n_i} \\=-K\sum p_i\ log\ p_i$$

决策树的构造

如果label只有一个，表示数据都是同一个类别的，那么不必构造。

如果使用完了所有特征，仍然不能将数据划分成仅包含唯一类别的分组，那么也要停止递归，转调用表决函数。

除此以外，首先将各维度进行比较，看选择哪一个维度进行分类能得到更多的信息熵。这样一来，会按照这一列重复元素作为同一个小组，这个小组递归地创建决策树。

为得到最大的信息熵负增量，要逐列计算信息熵。对每一列将重复元素作为一个小组，能算出这个小组的发生概率；累加这些概率与概率对数值的乘积，能算出该列的信息熵负增量。比较每一列的信息熵负增量，用类似打擂台的方式选出最大的那个，并记录对应的列序号。最后返回这个序号。

创建决策树：

 
 


  
  
def createTree(dataSet, labels):

  
  
    """

  
  
    创建决策树

  
  
    myTree变量存储这个结果

  
  
    myTree中某一层的一个节点，key是特征向量对应的label，val为属于key类和不属于key类的两个子树

  
  
    """

  
  
    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[:] #列表会按照引用方式传递，因此，为了保证不改变labels这个原始列表，使用新变量subLabels来作为参数

  
  
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)

  
  
    return myTree

 
 

选出最好的特征列序号：

 
 


  
  
def chooseBestFeatureToSplit(dataSet):

  
  
    """

  
  
    选择最好的数据集划分方式

  
  
    即：对除label外的每一列都进行计算，每一列能算出一个总的信息增量（信息熵增量的负值）。

  
  
    信息增量最多的那一列，就是最好的划分列。

  
  
    """

  
  
    numFeatures = len(dataSet[0])-1

  
  
    baseEntropy = calcShannonEnt(dataSet)

  
  
    bestInfoGain = 0.0

  
  
    bastFeature = -1

  
  
    for i in range(numFeatures):

  
  
        featList = [example[i] for example in dataSet]

  
  
        #取出dataSet的第i列

  
  


  
  
        uniqueVals = set(featList) #set是用来去除重复元素的

  
  
        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

 
 

切分数据：将指定列中与指定value相等的向量筛选出，并将其去除了指定列得到的子矩阵返回：

 
 


  
  


  
  
def splitDataSet(dataSet, axis, value):

  
  
    """

  
  
    扫描数据集（矩阵）的指定列（axis列），如果某个向量第axis列的值等于value

  
  
    那么将去除这个value后的向量存储起来

  
  
    每一行都这么处理，最后返回的是“axis列与value相等并且去除了axis列的矩阵”

  
  


  
  
    也就是：按照value划分了一个类，返回这个类

  
  
    """

  
  
    retDataSet=[]

  
  
    for featVec in dataSet:

  
  
        if featVec[axis] == value:

  
  
            reducedFeatVec = featVec[:axis]

  
  
            reducedFeatVec.extend(featVec[axis+1:])

  
  
            #reducedFeatVec:去除axis列后的向量

  
  


  
  
            retDataSet.append(reducedFeatVec)

  
  
    return retDataSet

 
 

反倒是计算信息熵的最核心代码最容易：

 
 


  
  
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  #书上此行少了一个indent。

  
  
    shannonEnt = 0.0

  
  
    for key in labelCounts:

  
  
        prob = float(labelCounts[key])/numEntries

  
  
        shannonEnt -= prob*log(prob,2)

  
  
    return shannonEnt

 
 

当决策树终于构建完毕，就需要用它来预测一个测试向量的分类了：

 
 


  
  
def classify(inputTree, featLabels, testVec):

  
  
    """

  
  
    使用决策树的分类函数

  
  
    """

  
  
    firstStr = inputTree.keys()[0]

  
  
    secondDict = inputTree[firstStr]

  
  
    featIndex = featLabels.index[firstStr]

  
  
    for key in secondDict.keys():

  
  
        if testVec[featIndex]==key:

  
  
            if type(secondDict[key]).__name__=='dict':

  
  
                classLabel = classify(secondDict[key], featLabels, testVec)

  
  
            else:

  
  
                classLabel=secondDict[key]

  
  
    return classLabel

 
 

算法中可替换部件

度量系统无序程度

除了信息熵，也可以用Gini不纯度来做。

数据划分

这里采用ID3算法。也可以用二分法。
还有C4.5和CART算法可用。挖坑待填