决策树笔记:使用ID3算法

决策树笔记:使用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. Hpi处连续
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.

例如
决策树笔记:使用ID3算法
从左边的树状图转换到右边一个树状图,是后两个分支先合并在分离,原来的一次决策变为两次决策,才能确定后面两个节点:

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再做1sm1,那么熵值H的计算依据假设(3)即可计算:通过把A(sm)的每sm1个连续的分支搓成一股,下一股则为A(sm1),得到:

A(sm)=A(s)+1sA(sm1)s=>A(sm)=mA(s)

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

n,m,s.t.smtn<sm+1

取对数并除以n log s,有:
mnlog tlog s<mn+1n|log tlog smn|<1n0

假设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=>|mnA(t)A(s)|<1n0

由上面两个趋向于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)+Kpi log ni=>H(p1,...,pn)=K(lognipi log ni)

pi=1有:
log ni=pi logni=>H(p1,...,pn)=K(pilognipi log ni)=Kpi lognini=Kpi 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]
  11. if len(dataSet[0])==1:
  12. #如果使用完了所有特征,仍然不能将数据集划分成仅包含唯一类别的分组,那么也要停止递归,转而调用表决函数
  13. return majorityCnt(classList)
  14. bestFeat = chooseBestFeatureToSplit(dataSet) #当前数据集选取的最好的特征
  15. bestFeatLabel = labels[bestFeat]
  16. myTree={bestFeatLabel:{}}
  17. del(labels[bestFeat])
  18. featValues=[example[bestFeat] for example in dataSet]
  19. uniqueVals = set(featValues)
  20. for value in uniqueVals:
  21. subLabels = labels[:] #列表会按照引用方式传递,因此,为了保证不改变labels这个原始列表,使用新变量subLabels来作为参数
  22. myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
  23. 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列
  14. uniqueVals = set(featList) #set是用来去除重复元素的
  15. newEntropy = 0.0
  16. for value in uniqueVals:
  17. subDataSet = splitDataSet(dataSet, i, value)
  18. prob = len(subDataSet)/float(len(dataSet))
  19. newEntropy += prob * calcShannonEnt(subDataSet)
  20. infoGain = baseEntropy - newEntropy
  21. if infoGain > bestInfoGain:
  22. bestInfoGain = infoGain
  23. bestFeature = i
  24. return bestFeature

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


  1. def splitDataSet(dataSet, axis, value):
  2. """
  3. 扫描数据集(矩阵)的指定列(axis列),如果某个向量第axis列的值等于value
  4. 那么将去除这个value后的向量存储起来
  5. 每一行都这么处理,最后返回的是“axis列与value相等并且去除了axis列的矩阵”
  6. 也就是:按照value划分了一个类,返回这个类
  7. """
  8. retDataSet=[]
  9. for featVec in dataSet:
  10. if featVec[axis] == value:
  11. reducedFeatVec = featVec[:axis]
  12. reducedFeatVec.extend(featVec[axis+1:])
  13. #reducedFeatVec:去除axis列后的向量
  14. retDataSet.append(reducedFeatVec)
  15. 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算法可用。挖坑待填

上一篇:简单使用Git和Github来管理自己的代码和读书笔记


下一篇:闪存很快,NVMe可以让它更快