决策树的信以及熵的测算。python实现决策树的课。

一、引言

事先涉嫌的k-近邻算法是分类数据极其简便不过可行的算法。k-近邻算法是基于实例的学习,使用算法时我们须产生近似实际数据的训练样本数据。而且,k-近邻数据必须维持全部数据集,如果训练数据集的深酷,必须以大量之囤空间,此外k-近邻算法必须对数据汇总的每个数据计算距离,这是可怜耗时的。另外,对于数据的根基结构信息,它为是心有余而力不足的。

其余一样种植分类算法就是“决策树算法”。对待一个数据,决策树下多个裁定判断确定最后之归类,举个稍例子说明一下:给得一个动物,判断什么动物之归类,首先“它是哺乳类动物吧?”,如果未是,“它是洲动物吗?”,如果无是,“是空间动物吧?”……以此类推,最终判断动物之归类,确定动物。

正文实例为大家大饱眼福了python实现决策树的切切实实代码,供大家参考,具体内容如下

老二、信息和熵

熵代表一个网的杂乱程度,熵越怪,系统越来越繁杂。对一个数量汇总数据的归类就是让该数额集熵减小的进程。

决定树算法就是一个细分数据集的进程。划分数据集的尺码就是是:将无序的多寡易得越来越平稳。我们若得到的数量是立竿见影之信息,处理信息的同等栽中之方式就是是行使信息论。

信息增益:划分数据集前后信息之扭转成为信息增益,获得信息增益最高的风味就是是无比好之挑。那么哪些计算信息增益?集合信息之胸襟方式称为熵。

假定看不理解什么是信增益和熵,请不要心急——它们从诞生的那么同样龙从,就尘埃落定会使世人十分费解。克劳德香农写信息论之后,约翰冯诺依曼建议用“熵”这个术语,因为大家还无明了其是呀意思。

熵定义为信之期值,在白纸黑字这个定义之前,先来瞧信息之概念。如果用分类的事务可能划分在差不多只分类中,则符号图片 1的音讯定义也:

图片 2=-log_2p(x_i))

其中图片 3)是选取该分类的票房价值。

负有品种有或价值包含的音要值,即是计量所得的熵:

图片 4log_2p(x_i))

下面举一个例子来行使一下上述之公式,并且将公式应用至实际的例子上。

算法优缺点:

其三、一个概括的事例

下表包含5只海洋动物,特征包括:不显露出水面是否可生活,以及是否发足。将这些动物分为两类:鱼类及非鱼类。要钻之问题就是根据第一独特点还是其次个特点划分数据。

  不浮出水面是否可以生存 是否又脚蹼 属于鱼类
1
2
3
4
5

优先为来计算香农熵的python代码,以全后续使用(一下有着代码都是python写的)

 1 def calcShannonEnt(dataSet):
 2     numEntries = len(dataSet)
 3     labelCounts = {}
 4     for featVec in dataSet:
 5         currentLabel = featVec[-1]
 6     if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0
 7     labelCounts[currentLabel] += 1
 8     shannonEnt = 0.0
 9     for key in labelCounts:
10         prob = float(labelCounts[key])/numEntries
11     shannonEnt -= prob * log(prob, 2)
12     return shannonEnt

 

只要了解python,代码还是比较简单的,不过如果先说明一下dataSet是怎么的数,怎样的数据结构。这即引出了底的代码,用来生成dataSet,这样您就能够再次好地打听代码中“currentLabel
= featVec[-1]”是怎么回事了。

1 def createDataSet():
2     dataSet = [[1, 1, 'yes'],
3            [1, 1, 'yes'],
4            [1, 0, 'no'],
5            [0, 1, 'no'],
6            [0, 1, 'no']]
7     labels = ['no surfacing', 'flippers']
8     return dataSet, labels

 

俺们所拍卖的数是形如dataSet这样的数据集,每个数据是list类型,数据的最后一件是数的标签。看一下功能:

图片 5

熵越强,说明数据的混合度越强,增加多少类好观察熵的变。

接通下去做来什么?别忘了初衷:依据第一独特性还是其次个特色划分数据?这个问题之回就是在于哪种特性的细分熵更粗部分。我们用对每个特征划分数据集的结果算同一蹩脚信息熵,然后判断仍谁特征划分数据集是最最好的划分方式。

第一编写一个函数用于按照给定特征划分数据集:

1 def splitDataSet(dataSet, axis, value):
2     retDataSet = []
3     for featVec in dataSet:
4         if featVec[axis] == value:
5         reducedFeatVec = featVec[:axis]
6         reducedFeatVec.extend(featVec[axis+1:])
7         retDataSet.append(reducedFeatVec)
8     return retDataSet

 

代码中行使了python中从带的简单单道:extend()、append(),这有限独艺术效果看似,但是当处理多个列表时,这点儿单方法是完全不同的,这个大家便机关百度转眼。代码比较好理解,一下子没有理解为没事,慢慢来,先看看运行的职能,感性认识一下吧:

图片 6

末段一个函数就是用来对每个特征划分数据集的结果算同一不成信息熵,然后判断仍哪个特征划分数据集是极端好之分割方式:

 1 def chooseBestFeatureToSplit(dataSet):
 2     numFeatures  = len(dataSet[0]) - 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]
 7         uniqueVals = set(featList)
 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    

图片 7

看得出,按照第一独性状划分获得的凡无限好之撤并,熵最小。

瑜:计算复杂度不强,输出结果好理解,对中值缺失不灵动,可以处理不系的风味数据

缺陷:可能会见出过度匹配的问题

适用数据类型:数值型和标称型

算法思想:

1.表决树构造的整构思:

决定树说白了便象是是if-else结构同样,它的结果就是是您要是杀成是一个足以由根开始频频判断选择到叶子节点的培育,但是呢这里的if-else必然不会见是深受咱们觉得去装的,我们如果开的是供平等种方式,计算机可以因这种方法取得我们所用之决策树。这个点子的根本就是在于如何自这样多之性状被摘来有价的,并且依照最好之一一由穷及叶选择。完成了这我们吧尽管足以递归构造一个核定树了

2.信息增益

分开数据集的无比特别条件是将无序的数额易得尤其有序。既然这同时拉到信息之稳步无序问题,自然要想开想抓的音熵了。这里我们计算用的也是信息熵(另一样种办法是基尼不纯度)。公式如下:

数据要满足的渴求:

1
数据要是由于列表元素结合的列表,而且具备的列白哦元素都如享有同等之数长度
2 数据的结尾一列或者每个实例的尾声一个因素应是当下实例的路标签

函数:

calcShannonEnt(dataSet)

计数据集的香农熵,分点儿步,第一步计算频率,第二统根据公式计算香农熵

splitDataSet(dataSet, aixs, value)

分数据集,将满足X[aixs]==value的价都划分到齐,返回一个瓜分好的集纳(不包用来分的aixs属性,因为无欲)

chooseBestFeature(dataSet)

挑选最好的习性进行分割,思路特别简短即是对每个属性都分下,看谁好。这里运用到了一个set来选列表中绝无仅有的要素,这是一中很快的章程

majorityCnt(classList)

为我们递归构建决策树是冲性之损耗进行测算的,所以可能会见存在最后属性用了了,但是分类还是无算了却,这时候就见面动用多数裁决的不二法门测算节点分类

createTree(dataSet, labels)

因递归构建决策树。这里的label更多是对于分类特征的讳,为了重新好看和后面的明亮。

#coding=utf-8
import operator
from math import log
import time

def createDataSet():
  dataSet=[[1,1,'yes'],
      [1,1,'yes'],
      [1,0,'no'],
      [0,1,'no'],
      [0,1,'no']]
  labels = ['no surfaceing','flippers']
  return dataSet, labels

#计算香农熵
def calcShannonEnt(dataSet):
  numEntries = len(dataSet)
  labelCounts = {}
  for feaVec in dataSet:
    currentLabel = feaVec[-1]
    if currentLabel not in labelCounts:
      labelCounts[currentLabel] = 0
    labelCounts[currentLabel] += 1
  shannonEnt = 0.0
  for key in labelCounts:
    prob = float(labelCounts[key])/numEntries
    shannonEnt -= prob * log(prob, 2)
  return shannonEnt

def splitDataSet(dataSet, axis, value):
  retDataSet = []
  for featVec in dataSet:
    if featVec[axis] == value:
      reducedFeatVec = featVec[:axis]
      reducedFeatVec.extend(featVec[axis+1:])
      retDataSet.append(reducedFeatVec)
  return retDataSet

def chooseBestFeatureToSplit(dataSet):
  numFeatures = len(dataSet[0]) - 1#因为数据集的最后一项是标签
  baseEntropy = calcShannonEnt(dataSet)
  bestInfoGain = 0.0
  bestFeature = -1
  for i in range(numFeatures):
    featList = [example[i] for example in dataSet]
    uniqueVals = set(featList)
    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

#因为我们递归构建决策树是根据属性的消耗进行计算的,所以可能会存在最后属性用完了,但是分类
#还是没有算完,这时候就会采用多数表决的方式计算节点分类
def majorityCnt(classList):
  classCount = {}
  for vote in classList:
    if vote not in classCount.keys():
      classCount[vote] = 0
    classCount[vote] += 1
  return max(classCount)     

def createTree(dataSet, labels):
  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[:]#为了不改变原始列表的内容复制了一下
    myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, 
                    bestFeat, value),subLabels)
  return myTree

def main():
  data,label = createDataSet()
  t1 = time.clock()
  myTree = createTree(data,label)
  t2 = time.clock()
  print myTree
  print 'execute for ',t2-t1
if __name__=='__main__':
  main()

相关文章