python实现决策树的学科,决策树之音讯与熵的一个钱打二15个结

一、引言

后面提到的k-近邻算法是分类数据最简易最实用的算法。k-近邻算法是依照实例的上学,使用算法时我们不能够不有类似实际多少的演练样本数据。而且,k-近邻数据必须保证全体数据集,若是磨炼数据集的相当大,必须使用多量的蕴藏空间,其它k-近邻算法必须对数据集中的各样数据总结距离,那是相当耗时的。此外,对于数据的根底结构音讯,它也是无力回天的。

另一种分类算法正是“决策树算法”。对待八个数码,决策树使用多少个裁定判断分明最终的归类,举个小例子说澳优(Ausnutria Hyproca)下:给定三个动物,判断什么动物的归类,首先“它是哺乳类动物吧?”,若是或不是,“它是陆地动物吗?”,假如不是,“是空间动物呢?”……以此类推,最终看清动物的分类,鲜明动物。

正文实例为大家享受了python达成决策树的有血有肉代码,供大家参考,具体内容如下

贰 、音信与熵

熵代表3个系统的混杂程度,熵越大,系统越繁杂。对3个数额汇总数据的分类正是驱动该数据集熵减小的进度。

表决树算法就是3个私分数据集的历程。划分数据集的尺度正是:将冬天的数量变得更其平稳。大家倘诺获得的数码是卓有成效的新闻,处理信息的一种有效的法门正是行使消息论。

新闻增益:划分数据集前后消息的成形成为消息增益,获得音信增益最高的特征正是最棒的选用。那么怎么样计算音信增益?集合音讯的心路格局称为熵。

假诺看不知晓怎么着是新闻增益和熵,请不要焦躁——它们自诞生的那一天起,就已然会令世人12分费解。Crowder香农写消息论之后,John冯诺依曼提议使用“熵”这一个术语,因为我们都不清楚它是何等意思。

熵定义为音讯的只求值,在清晰那几个概念以前,先来探望新闻的定义。假设待分类的事务大概划分在多少个分类之中,则符号图片 1的音讯定义为:

图片 2=-log_2p(x_i))

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

负有类型享有只怕值包涵的音信期望值,就是计算机技术钻探所得的熵:

图片 4log_2p(x_i))

上面举贰个例子来行使一下上述的公式,并且把公式应用到实在的例子上。

算法优缺点:

三 、二个简练的例证

下表包罗八个海洋动物,特征包蕴:不浮出水面是还是不是足以生存,以及是还是不是有脚蹼。将那么些动物分为两类:鱼类和非鱼类。要钻探的标题正是依照第一个特点还是其次本性格划分数据。

  不浮出水面是否可以生存 是否又脚蹼 属于鱼类
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,代码依旧比较简单的,不过要先行说喜宝(Hipp)下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

熵越高,表明数据的混合度越高,增添数量类别能够观察熵的变迁。

接下去做些什么?别忘了初衷:根据第③本性情照旧其次个天性划分数据?那么些题指标答应就在于哪一种天性的分割熵更小一些。大家将对各个特征划分数据集的结果总计2回消息熵,然后判断依据哪个特征划分数据集是最佳的撤销合并情势。

第①编写三个函数用于依据给定特征划分数据集:

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结构同样,它的结果便是你要生成这些1个方可从根初步频频判断选拔到叶子节点的树,不过呢那里的if-else必然不会是让大家以为去设置的,大家要做的是提供一种艺术,总结机能够根据那种情势赢得大家所急需的决策树。这一个方法的重庆大学就在于如何从这么多的性子中精选出有价值的,并且依据最棒的顺序由根到叶选取。完毕了那个大家也就足以递归构造三个决策树了

2.音讯增益

细分数据集的最大条件是将冬天的数据变得越来越有序。既然那又牵涉到音讯的平稳冬日,冬辰难点,自然要想开想弄的消息熵了。那里大家总括用的也是信息熵(另一种情势是基尼不纯度)。公式如下:

多少须求满意的渴求:

1
数据必须是由列表成分结合的列表,而且具有的列白哦成分都要有所相同的数额长度
2 数据的结尾一列恐怕每种实例的尾声七个要素应是近年来实例的品类标签

函数:

calcShannonEnt(dataSet)

测算数据集的香农熵,分两步,第3步总结频率,第贰部依照公式总计香农熵

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.