正文

决策树笔记：使用ID3算法

IP云
IP云V管理员/9 阅读
06/23
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

决策树笔记：使用ID3算法

决策树笔记：使用ID3算法

机器学习

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

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

什么是决策树

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

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

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

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

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

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

−∑pilog pi

信息熵公式的证明

这个公式的证明似乎没有什么用处，看看就好。通过阅读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.

例如



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

H(12,13,16)=H(12,12)+12H(23,13)

其中\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(sm)=A(s)+1s∗A(sm−1)∗s=>A(sm)=mA(s)

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

∀n,∃m,s.t.sm≤tn<sm+1

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

mn≤log tlog s<mn+1n，即：|log tlog s−mn|<1n→0

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

A(sm)<A(tn)<A(sm+1)=>mA(s)≤nA(t)<(m+1)A(s)

同除nA(s):

mn<A(t)A(s)<mn+1n=>|mn−A(t)A(s)|<1n→0

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

|A(t)A(s)−log tlog s|→0=>A(t)=K log t,K>0

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

假设有n组事件，第i组有ni个事件，选中第ni的概率为pi。注意此时事件总数是∑ni而不是n。

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

H总体=K log ∑ni=H(p1,...,pn)+K∑pi log ni=>H(p1,...,pn)=K(log∑ni−∑pi log ni)

由∑pi=1有：

log ∑ni=∑pi log∑ni=>H(p1,...,pn)=K(∑pilog∑ni−∑pi log ni)=−K∑pi logni∑ni=−K∑pi log pi

决策树的构造

如果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算法可用。挖坑待填