决策树笔记：使用ID3算法

决策树笔记：使用ID3算法

机器学习

---

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

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

什么是决策树

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

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

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

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

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

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

信息熵公式的证明

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

考虑如下情形：你需要确定下一件发生的事件，然而你只知道每一个事件发生的概率：p1,p2,...,pn。用H表示本次决策的熵。我们的决策基于如下3个假设：
1. H在pi处连续
2. 若所有pi相等，即pi=1n，则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.

例如

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

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

公式A(sm)=mA(s)的证明

假设A(n)=H(1n,1n,...,1n)，怎样证明A(sm)=mA(s)？

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

A(sm)则可以看作：root节点只有一层子节点，子节点一共有sm个，每个子节点被选中的概率都是1sm。

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

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

取对数并除以n log s，有：

由假设2A(n)对n严格增有：

同除nA(s):

由上面两个趋向于0的绝对值不等式有：

信息熵公式H(p1,...,pn)=−K∑(pi log pi)的证明

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

由∑pi=1有：

决策树的构造

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

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

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

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

创建决策树：

1. def createTree(dataSet, labels):
2. """
3. 创建决策树
4. myTree变量存储这个结果
5. myTree中某一层的一个节点，key是特征向量对应的label，val为属于key类和不属于key类的两个子树
6. """
7. classList = [example[-1] for example in dataSet]
8. if classList.count(classList[0])==len(classList):
9. #如果所有类标签完全相同，那么停止递归
10. return classList[0]
12. if len(dataSet[0])==1:
13. #如果使用完了所有特征，仍然不能将数据集划分成仅包含唯一类别的分组，那么也要停止递归，转而调用表决函数
14. return majorityCnt(classList)
16. bestFeat = chooseBestFeatureToSplit(dataSet) #当前数据集选取的最好的特征
17. bestFeatLabel = labels[bestFeat]
18. myTree={bestFeatLabel:{}}
19. del(labels[bestFeat])
20. featValues=[example[bestFeat] for example in dataSet]
21. uniqueVals = set(featValues)
22. for value in uniqueVals:
23. subLabels = labels[:] #列表会按照引用方式传递，因此，为了保证不改变labels这个原始列表，使用新变量subLabels来作为参数
24. myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
25. return myTree

选出最好的特征列序号：

1. def chooseBestFeatureToSplit(dataSet):
2. """
3. 选择最好的数据集划分方式
4. 即：对除label外的每一列都进行计算，每一列能算出一个总的信息增量（信息熵增量的负值）。
5. 信息增量最多的那一列，就是最好的划分列。
6. """
7. numFeatures = len(dataSet[0])-1
8. baseEntropy = calcShannonEnt(dataSet)
9. bestInfoGain = 0.0
10. bastFeature = -1
11. for i in range(numFeatures):
12. featList = [example[i] for example in dataSet]
13. #取出dataSet的第i列
15. uniqueVals = set(featList) #set是用来去除重复元素的
16. newEntropy = 0.0
17. for value in uniqueVals:
18. subDataSet = splitDataSet(dataSet, i, value)
19. prob = len(subDataSet)/float(len(dataSet))
20. newEntropy += prob * calcShannonEnt(subDataSet)
21. infoGain = baseEntropy - newEntropy
22. if infoGain > bestInfoGain:
23. bestInfoGain = infoGain
24. bestFeature = i
25. return bestFeature

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

2. def splitDataSet(dataSet, axis, value):
3. """
4. 扫描数据集（矩阵）的指定列（axis列），如果某个向量第axis列的值等于value
5. 那么将去除这个value后的向量存储起来
6. 每一行都这么处理，最后返回的是“axis列与value相等并且去除了axis列的矩阵”
8. 也就是：按照value划分了一个类，返回这个类
9. """
10. retDataSet=[]
11. for featVec in dataSet:
12. if featVec[axis] == value:
13. reducedFeatVec = featVec[:axis]
14. reducedFeatVec.extend(featVec[axis+1:])
15. #reducedFeatVec:去除axis列后的向量
17. retDataSet.append(reducedFeatVec)
18. return retDataSet

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

1. def calcShannonEnt(dataSet):
2. """
3. 计算信息熵
4. """
5. numEntries = len(dataSet)
6. labelCounts={}
7. for featVec in dataSet:
8. currentLabel = featVec[-1]
9. if currentLabel not in labelCounts.keys():
10. labelCounts[currentLabel]=0
11. labelCounts[currentLabel]+=1 #书上此行少了一个indent。
12. shannonEnt = 0.0
13. for key in labelCounts:
14. prob = float(labelCounts[key])/numEntries
15. shannonEnt -= prob*log(prob,2)
16. return shannonEnt

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

1. def classify(inputTree, featLabels, testVec):
2. """
3. 使用决策树的分类函数
4. """
5. firstStr = inputTree.keys()[0]
6. secondDict = inputTree[firstStr]
7. featIndex = featLabels.index[firstStr]
8. for key in secondDict.keys():
9. if testVec[featIndex]==key:
10. if type(secondDict[key]).__name__=='dict':
11. classLabel = classify(secondDict[key], featLabels, testVec)
12. else:
13. classLabel=secondDict[key]
14. return classLabel

算法中可替换部件

度量系统无序程度

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

数据划分

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