决策树的思想比较简单,不复杂,决策树,就是通过一个属性将数据进行划分,而这个属性的选择也就是决策树的关键,用什么样的属性分开的值尽可能属于同一个类别。

属性选择的方法很多,书中主要介绍了:通过信息增益、增益比率、以及基尼指数.

具体伪代码书中给出:

机器学习2决策树

本文采用了ID3算法划分数据集。该算法采用了一个叫信息增益的概念,关于信息论的部分,曾经写过一文http://www.cnblogs.com/fengbing/archive/2011/12/15/2288801.html中有部分阐述。

我的理解就是,信息是什么,怎么度量,也就是信息经过压缩之后还能代表本身的最小值,这个可以根据霍夫曼编码看出。

具体说明:

考虑用 0 和 1 组成的二进制数码为含有 n 个符号的某条信息编码,假设符号 Fn 在整条信息中重复出现的概率为 Pn,则该符号的熵也即表示该符号所需的位数位为:
En = - log2( Pn )
整条信息的熵也即表示整条信息所需的位数为:E = ∑En

举个例子,对下面这条只出现了 a b c 三个字符的字符串:
aabbaccbaa
字符串长度为 10,字符 a b c 分别出现了 5 3 2 次,则 a b c 在信息中出现的概率分别为 0.5 0.3 0.2,他们的熵分别为:
Ea = -log2(0.5) = 1
Eb = -log2(0.3) = 1.737
Ec = -log2(0.2) = 2.322
整条信息的熵也即表达整个字符串需要的位数为:
E = Ea * 5 + Eb * 3 + Ec * 2 = 14.855 位
回想一下如果用计算机中常用的 ASCII 编码,表示上面的字符串我们需要整整 80 位,这样我们就用较少的位数表示较频繁出现的符号。

而这个值不能再小了,再小就不能表示这个信息量了。而这个最小的信息量也就是这个信息的度量。

下面就来上代码

   1:  # -*- coding: utf-8 -*
   2:  from math import log
   3:   
   4:  def calcShannonEnt(dataSet):
   5:      numEntries = len(dataSet)#得到数据集总数
   6:      labelCounts = {}
   7:      for featVec in dataSet:
   8:          currentLabel = featVec[-1]#-1表示最后一列
   9:          #这边处理可能不好理解,初始不在字典中先设为0,再加1,以后再字典中就直接加1
  10:          #我们可能处理是if no in dictionary,设为1,else +1
  11:          if currentLabel not in labelCounts.keys():
  12:              labelCounts[currentLabel] = 0        
  13:          labelCounts[currentLabel] +=1
  14:      shannonEnt = 0.0
  15:      for key in labelCounts:
  16:          prob = float(labelCounts[key])/numEntries
  17:          shannonEnt -= prob*log(prob,2)
  18:      return shannonEnt
  19:   
  20:  def createDataSet():
  21:      dataSet = [[1, 1, 'yes'],
  22:                 [1, 1, 'yes'],
  23:                 [1, 0, 'no'],
  24:                 [0, 1, 'no'],
  25:                 [0, 1, 'no']]
  26:      labels = ['no surfacing','flippers']
  27:      return dataSet, labels

 

运行

   1:  >>> import tree
   2:  >>> myDat,labels = tree.createDataSet()
   3:  >>> myDat
   4:  [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
   5:  >>> tree.calcShannonEnt(myDat)
   6:  0.9709505944546686

这边求得的熵并不高,也就是说信息量不大,下面根据作者一样,我们增加分类,我们会发现熵变大,即信息量变大。

   1:  >>> myDat[0][-1]='maybe'
   2:  >>> myDat
   3:  [[1, 1, 'maybe'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
   4:  >>> tree.calcShannonEnt(myDat)
   5:  1.3709505944546687

通过信息增益的概念来构造决策树的方法有ID3,C4.5,C5.0还有通过基尼指数的CART算法。

书中没有介绍通过基尼指数的实现,目前也不实现,等书看完了后续对没有实现的算法再进行实现。

我们知道了信息熵,下面我们就开始划分数据集。

   1:  #axis第几个特征,value特征的值,以这个特征分类
   2:  def splitDataSet(dataSet,axis,value):
   3:      retDataSet = []
   4:      for featVec in dataSet:
   5:          if featVec[axis] == value:
   6:              reduceFeatVec = featVec[:axis]#featVec[:axis],axis=0时返回[]
   7:              reduceFeatVec.extend(featVec[axis+1:])
   8:              retDataSet.append(reduceFeatVec)
   9:      return retDataSet

得到的结果

   1:  >>> import tree
   2:  >>> myDat,labels = tree.createDataSet()
   3:  >>> tree.splitDataSet(myDat,0,1)
   4:  [[1, 'yes'], [1, 'yes'], [0, 'no']]

我们这边是以第一个特征值进行分类,下面我们要对所有的特征值进行分类,计算每个分类下的信息熵。

这样信息增益就是分裂前后的两个信息量的差机器学习2决策树

   1:  def chooseBestFeatureToSplit(dataSet):
   2:      numFeatures = len(dataSet[0]) - 1   #最后一个是类别,特征数是每一行数目减去1   
   3:      baseEntropy = calcShannonEnt(dataSet)#计算数据集原始信息熵
   4:      bestInfoGain = 0.0; bestFeature = -1
   5:      for i in range(numFeatures):       
   6:          featList = [example[i] for example in dataSet]#example[i]代表第i列的特征值,在for循环获取这一列的所有值
   7:          uniqueVals = set(featList) #set是一个无序不重复集跟其他语言一样,这样得到i这一列不同的特征值
   8:          newEntropy = 0.0
   9:          for value in uniqueVals:#根据不同的特征值分类计算所占百分比
  10:              subDataSet = splitDataSet(dataSet, i, value)
  11:              prob = len(subDataSet)/float(len(dataSet))
  12:              newEntropy += prob * calcShannonEnt(subDataSet)     
  13:          infoGain = baseEntropy - newEntropy #这是信息增益,是两个信息差   
  14:          if (infoGain > bestInfoGain):       
  15:              bestInfoGain = infoGain         
  16:              bestFeature = i
  17:      return bestFeature  

这个例子的第一步就是(3/5)*(-(2/3)*log(2/3)-(1/3)*log(1/3))+(2/5)*(-1*log1)

没有分类的时候直接计算-(2/5)*log(2/5)-(3/5)*log(3/5)

原始信息熵减去分裂之后的信息熵,就是信息增益,信息增益大的就选择这个特征进行分类。

我们打印出信息增益看出

   1:  num 0 infoGain 0.419973
   2:  num 1 infoGain 0.170951

所有以0也就是第一列的特征进行划分。

目前我们给出了第一次特征的划分,下面还要进行第二次的划分,甚至更多,决策树是一种树的形式,我们考虑采用的方式是递归处理。

递归处理要有一个结束条件。

1、遍历了所有的属性,或者每个分支下所有的实例都具有相同的分类。

2、可能会遇到最后没有属性可以划分这个样本子集的时候,我们采用投票原则,多的就为这个样本子集的类别标识,强制为叶子节点

具体代码:

   1:  def majorityCnt(classList):
   2:      classCount={}
   3:      for vote in classList:
   4:          if vote not in classCount.keys():
   5:              classCount[vote] = 0
   6:          classCount[vote] += 1
   7:      #这个sorted跟sort的区别前面提到,这个是重新建了一个数组,sort是在原有的基础上
   8:      sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
   9:      return sortedClassCount[0][0]
  10:   
  11:  def createTree(dataSet,labels):
  12:      classList = [example[-1] for example in dataSet]#得到分类这边是yes no
  13:      if classList.count(classList[0]) == len(classList): #这边说明都是同一个属性了,不好再分了
  14:          return classList[0]
  15:      if len(dataSet[0]) == 1: 
  16:          return majorityCnt(classList)
  17:      bestFeat = chooseBestFeatureToSplit(dataSet)
  18:      bestFeatLabel = labels[bestFeat]
  19:      myTree = {bestFeatLabel:{}}
  20:      del(labels[bestFeat])
  21:      featValues = [example[bestFeat] for example in dataSet]
  22:      uniqueVals = set(featValues)
  23:      for value in uniqueVals:#分类 递归
  24:          subLabels = labels[:]  #:表示全部     
  25:          myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
  26:      return myTree 

结果:

   1:  >>> import tree
   2:  >>> myDat,labels = tree.createDataSet()
   3:  >>> myTree =  tree.createTree(myDat,labels)
   4:  >>> myTree
   5:  {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

这边是采用字典的形式表示这个树形结构的,这个json字符串也有点像,不过决策树的优势在于它的图形表示,下面就通过之前用过的Matplotlib画图。

最终得到如下图:

机器学习2决策树

具体画图这边就不叙述了,没有细看。主要通过得到叶子数,得到数的深度。

下面还是一样,给出一个真实的例子,然后对模型进行正确性评估。

也就是知道这个决策树,我们给出一个特征属性,来判断这个的类别是什么

   1:   
   2:  def classify(inputTree,featLabels,testVec):
   3:      firstStr = inputTree.keys()[0]
   4:      secondDict = inputTree[firstStr]
   5:      featIndex = featLabels.index(firstStr)
   6:      key = testVec[featIndex]
   7:      valueOfFeat = secondDict[key]
   8:      if isinstance(valueOfFeat, dict): #判断valueOfFeat是不是字典类型,也就是判断是不是还有子集,有在进行递归判断
   9:          classLabel = classify(valueOfFeat, featLabels, testVec)
  10:      else: classLabel = valueOfFeat
  11:      return classLabel

测试:

   1:  >>> import tree
   2:  >>> import treePlotter
   3:  >>> myTree = treePlotter.retrieveTree(0)
   4:  >>> myData,labels = tree.createDataSet()
   5:  >>> tree.classify(myTree,labels,[1,0])
   6:  'no'

测试模型

另外我们创建好决策树之后就将其保存,这样要使用直接调用就好。

数据持久保存使用pickle模块,进行基本的数据序列和反序列化

   1:  #pickle模块实现了基本的数据序列和反序列化          
   2:  def storeTree(inputTree,filename):
   3:      import pickle
   4:      fw = open(filename,'w')
   5:      pickle.dump(inputTree,fw)
   6:      fw.close()
   7:      
   8:  def grabTree(filename):
   9:      import pickle
  10:      fr = open(filename)
  11:      return pickle.load(fr)

使用

   1:  >>> myTree = {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
   2:  >>> myTree
   3:  {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
   4:  >>> tree.storeTree(myTree,'classifierStorage.txt')
   5:  >>> tree.grabTree('classifierStorage.txt')
   6:  {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
   7:  >>> 

最后作者给出了隐形眼镜的测试,我这边也把其代码列出

   1:  >>> fr = open('lenses.txt')
   2:  >>> lenses = [inst.strip().split('\t') for inst in fr.readlines()]
   3:  >>> lensesLabels = ['age','prescript','astigmatic','tearRate']
   4:  >>> lensesTree = tree.createTree(lenses,lensesLabels)
   5:  >>> lensesTree
   6:  {'tearRate': {'reduced': 'no lenses', 'normal': {'astigmatic': {'yes': {'prescript': {'hyper': {'age': {'pre': 'no lenses', 'presbyopic': 'no lenses', 'young': 'hard'}}, 'myope': 'hard'}}, 'no': {'age': {'pre': 'soft', 'presbyopic': {'prescript': {'hyper': 'soft', 'myope': 'no lenses'}}, 'young': 'soft'}}}}}}
   7:  >>> import treePlotter
   8:  >>> treePlotter.createPlot(lensesTree)
 
最后给出图如下:
机器学习2决策树

这样基本的ID3算法就结束了,不过决策树远不止这么多。

决策树是一个很好的思想,因为其直观,效果也好,普通用户使用甚至可以得出几十年专家的水准。但是它也有很多问题,就关这个特征属性的选择问题,就有很多研究。

我们现在使用了信息增益,之后有C4.5算法采用信息增益比,在这本书的第九章有CART算法采用基尼指数,另外还有距离度量、基于统计的等等。

另外由于在真实世界中没有没有完善的数据,这数据有噪声,而我们刚刚的算法没有考虑这些问题。

还有属性之间是有关联的,这样划分出来的结果也会有问题,最终导致划分过细,而且最后的结果不易于理解。

于是有一些方案来解决这些问题。这个在这本书的第九章会给出一定的解决方案,这个ID3算法就到这边。