python达成决策树的学科,决策树之新闻与熵的计量必威体育

一、引言

事先涉嫌的k-近邻算法是分类数据最轻松易行最可行的算法。k-近邻算法是根据实例的上学,使用算法时大家务必有类似实际多少的练习样本数据。并且,k-近邻数据必须保障全体数据集,假如操练数据集的极大,必须使用多量的积攒空间,别的k-近邻算法必须对数据汇总的每个数据测算距离,那是不行耗费时间的。其他,对于数据的功底结构消息,它也是无力回天的。

另一种分类算法就是“决策树算法”。对待叁个数额,决策树使用两个裁定决断鲜明最终的归类,举个小例子说多美滋下:给定三个动物,判别什么动物的分类,首先“它是哺乳类动物呢?”,假设不是,“它是陆地动物吧?”,如若不是,“是空间动物吗?”……就那样类推,最终判别动物的分类,明确动物。

本文实例为大家大快朵颐了python达成决策树的求实代码,供我们参考,具体内容如下

二、音信与熵

熵代表三个种类的混乱程度,熵越大,系统越繁杂。对叁个多少聚集数据的分类正是驱动该数据集熵减小的经过。

核定树算法正是三个分开数据集的经过。划分数据集的规格正是:将冬日的数码变得更其有序。大家假诺获得的数额是有效的音讯,处理音信的一种有效的方法正是行使音讯论。

音讯增益:划分数据集前后消息的变通成为消息增益,获得消息增益最高的风味正是最佳的选料。那么什么样总括新闻增益?集结消息的气量格局称为熵。

假定看不了然如何是新闻增益和熵,请不要焦急——它们自诞生的那一天起,就尘埃落定会令世人十三分费解。Crowder香农写新闻论之后,John冯诺依曼提出使用“熵”那些术语,因为我们都不精晓它是怎么着意思。

熵定义为信息的希望值,在清晰这一个概念在此以前,先来看看消息的定义。假设待分类的作业大概划分在多少个分类之中,则符号必威体育 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,代码依旧相比较轻易的,可是要前期说美素佳儿(Friso)下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必然不会是让我们以为去设置的,大家要做的是提供一种方式,Computer能够凭仗这种方法赢得大家所供给的决策树。这几个方法的主要就在于如何从这么多的特征中选用出有价值的,况且依据最棒的相继由根到叶选拔。完毕了这么些我们也就能够递归构造二个决策树了

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.