决策树的信及熵的计量。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()

相关文章

Leave a Comment.