# -*- coding: cp936 -*-
from numpy import *
import operator
from math import log
import operator
def createDataSet():
  dataSet = [[1,1,'yes'],
    [1,1,'yes'],
    [1,0,'no'],
    [0,1,'no'],
    [0,1,'no']]
  labels = ['no surfacing','flippers']
  return dataSet, labels
def calcShannonEnt(dataSet):
  numEntries = len(dataSet)
  labelCounts = {} # a dictionary for feature
  for featVec in dataSet:
    currentLabel = featVec[-1]
    if currentLabel not in labelCounts.keys():
      labelCounts[currentLabel] = 0
    labelCounts[currentLabel] += 1
  shannonEnt = 0.0
  for key in labelCounts:
    #print(key)
    #print(labelCounts[key])
    prob = float(labelCounts[key])/numEntries
    #print(prob)
    shannonEnt -= prob * log(prob,2)
  return shannonEnt
#按照給定的特征劃分?jǐn)?shù)據(jù)集
#根據(jù)axis等于value的特征將數(shù)據(jù)提出
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
#選取特征，劃分?jǐn)?shù)據(jù)集，計(jì)算得出最好的劃分?jǐn)?shù)據(jù)集的特征
def chooseBestFeatureToSplit(dataSet):
  numFeatures = len(dataSet[0]) - 1 #剩下的是特征的個(gè)數(shù)
  baseEntropy = calcShannonEnt(dataSet)#計(jì)算數(shù)據(jù)集的熵，放到baseEntropy中
  bestInfoGain = 0.0;bestFeature = -1 #初始化熵增益
  for i in range(numFeatures):
    featList = [example[i] for example in dataSet] #featList存儲(chǔ)對(duì)應(yīng)特征所有可能得取值
    uniqueVals = set(featList)
    newEntropy = 0.0
    for value in uniqueVals:#下面是計(jì)算每種劃分方式的信息熵,特征i個(gè)，每個(gè)特征value個(gè)值
      subDataSet = splitDataSet(dataSet, i ,value)
      prob = len(subDataSet)/float(len(dataSet)) #特征樣本在總樣本中的權(quán)重
      newEntropy = prob * calcShannonEnt(subDataSet)
    infoGain = baseEntropy - newEntropy #計(jì)算i個(gè)特征的信息熵
    #print(i)
    #print(infoGain)
    if(infoGain > bestInfoGain):
      bestInfoGain = infoGain
      bestFeature = i
  return bestFeature
#如上面是決策樹所有的功能模塊
#得到原始數(shù)據(jù)集之后基于最好的屬性值進(jìn)行劃分，每一次劃分之后傳遞到樹分支的下一個(gè)節(jié)點(diǎn)
#遞歸結(jié)束的條件是程序遍歷完成所有的數(shù)據(jù)集屬性，或者是每一個(gè)分支下的所有實(shí)例都具有相同的分類
#如果所有實(shí)例具有相同的分類，則得到一個(gè)葉子節(jié)點(diǎn)或者終止快
#如果所有屬性都已經(jīng)被處理，但是類標(biāo)簽依然不是確定的，那么采用多數(shù)投票的方式
#返回出現(xiàn)次數(shù)最多的分類名稱
def majorityCnt(classList):
  classCount = {}
  for vote in classList:
    if vote not in classCount.keys():classCount[vote] = 0
    classCount[vote] += 1
  sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1), reverse=True)
  return sortedClassCount[0][0]
#創(chuàng)建決策樹
def createTree(dataSet,labels):
  classList = [example[-1] for example in dataSet]#將最后一行的數(shù)據(jù)放到classList中，所有的類別的值
  if classList.count(classList[0]) == len(classList): #類別完全相同不需要再劃分
    return classList[0]
  if len(dataSet[0]) == 1:#這里為什么是1呢？就是說特征數(shù)為1的時(shí)候
    return majorityCnt(classList)#就返回這個(gè)特征就行了，因?yàn)榫瓦@一個(gè)特征
  bestFeat = chooseBestFeatureToSplit(dataSet)
  print('the bestFeatue in creating is :')
  print(bestFeat)
  bestFeatLabel = labels[bestFeat]#運(yùn)行結(jié)果'no surfacing'
  myTree = {bestFeatLabel:{}}#嵌套字典,目前value是一個(gè)空字典
  del(labels[bestFeat])
  featValues = [example[bestFeat] for example in dataSet]#第0個(gè)特征對(duì)應(yīng)的取值
  uniqueVals = set(featValues)
  for value in uniqueVals: #根據(jù)當(dāng)前特征值的取值進(jìn)行下一級(jí)的劃分
    subLabels = labels[:]
    myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
  return myTree
#對(duì)上面簡單的數(shù)據(jù)進(jìn)行小測試
def testTree1():
  myDat,labels=createDataSet()
  val = calcShannonEnt(myDat)
  print 'The classify accuracy is: %.2f%%' % val
  retDataSet1 = splitDataSet(myDat,0,1)
  print (myDat)
  print(retDataSet1)
  retDataSet0 = splitDataSet(myDat,0,0)
  print (myDat)
  print(retDataSet0)
  bestfeature = chooseBestFeatureToSplit(myDat)
  print('the bestFeatue is :')
  print(bestfeature)
  tree = createTree(myDat,labels)
  print(tree)

>>> import TREE
>>> TREE.testTree1()
The classify accuracy is: 0.97%
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
[[1, 'yes'], [1, 'yes'], [0, 'no']]
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
[[1, 'no'], [1, 'no']]
the bestFeatue is :
0
the bestFeatue in creating is :
0
the bestFeatue in creating is :
0
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

def classify(inputTree,featLabels,testVec):
  firstStr = inputTree.keys()[0]
  secondDict = inputTree[firstStr]
  featIndex = featLabels.index(firstStr)
  key = testVec[featIndex]
  valueOfFeat = secondDict[key]
  if isinstance(valueOfFeat, dict):
    classLabel = classify(valueOfFeat, featLabels, testVec)
  else: classLabel = valueOfFeat
  return classLabel
def storeTree(inputTree,filename):
  import pickle
  fw = open(filename,'w')
  pickle.dump(inputTree,fw)
  fw.close()
def grabTree(filename):
  import pickle
  fr = open(filename)
  return pickle.load(fr)