爱博体育app表决树之音与熵的算计。python实现决策树的课程。

一、引言

前提到的k-近邻算法是分类数据极其简易不过有效的算法。k-近邻算法是根据实例的上,使用算法时我们亟须有相近实际数据的训练样本数据。而且,k-近邻数据必须保持全部数据集,如果训练数据集的雅充分,必须采取大量之存储空间,此外k-近邻算法必须对数码汇总之每个数据测算距离,这是蛮耗时的。另外,对于数据的底蕴结构信息,它也是无力回天的。

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

正文实例为大家享用了python实现决策树的现实性代码,供大家参考,具体内容如下

次、信息及熵

熵代表一个网的乱程度,熵越老,系统越来越乱。对一个数目汇总数据的分类就是使该数据集熵减小的长河。

核定树算法就是一个私分数据集的经过。划分数据集的准就是是:将无序的数量易得越来越有序。我们若得到的数是立竿见影的消息,处理信息的一律种植中之艺术就是运信息论。

消息增益:划分数据集前后信息之变更成为信息增益,获得信息增益最高的特色就是是绝好之抉择。那么如何算信息增益?集合信息的度方式称为熵。

如看无晓什么是信息增益和熵,请不要急——它们从出生的那么同样龙从,就定会教世人十分费解。克劳德香农写信息论之后,约翰冯诺依曼建议采取“熵”这个术语,因为大家都未知晓它是呀意思。

熵定义为信息的期值,在白纸黑字这个概念之前,先来探望信息的概念。如果急需分类的政工可能划分在多独分类中,则符号爱博体育app 1的信息定义为:

爱博体育app 2=-log_2p(x_i))

其中爱博体育app 3)是选取该分类的票房价值。

抱有品种享有可能价值包含的音讯要值,即是计量所得之熵:

爱博体育app 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类型,数据的末梢一项是数量的价签。看一下效能:

爱博体育app 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(),这点儿独主意效果相近,但是以处理多个列表时,这片单道是了不同之,这个大家就是机关百度时而。代码比较好明,一下子没有明了也没事,慢慢来,先看运行的法力,感性认识一下吧:

爱博体育app 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    

爱博体育app 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()

相关文章