if so return 類(lèi)標(biāo)簽
Else

from math import log
import operator
#生成樣本數(shù)據(jù)集
def createDataSet():
  dataSet = [[1,1,'yes'],
        [1,1,'yes'],
        [1,0,'no'],
        [0,1,'no'],
        [0,1,'no']]
  labels = ['no surfacing','flipper']
  return dataSet,labels
# 計(jì)算香農(nóng)熵 香農(nóng) 大神必須要膜拜啊，信息界的根目錄人物啊
# no surfacing 指的是 不浮出水面能否生存 1 標(biāo)識(shí) 是 0 指的是否
# flipper 指的是是否有腳
# yes no指的是否是魚(yú)類(lèi)
def calcShannonEnt(dataSet):
  numEntries = len(dataSet) # 用上面的createDataSet dataSet 這個(gè)值就是5
  #定義標(biāo)簽字典
  labelCounts = {}
  # 為所有可能的分類(lèi)創(chuàng)建字典
  for featVec in dataSet:
    currentLabel = featVec[-1] #這個(gè)-1指的是去取最后一個(gè)維度 對(duì)應(yīng)數(shù)據(jù)dataSet 這里取的是yes和no
    if currentLabel not in labelCounts.keys():
      # 如果當(dāng)前分類(lèi)標(biāo)簽不在 標(biāo)簽字典中
      labelCounts[currentLabel] = 0
    # 其他情況 分類(lèi)標(biāo)簽分類(lèi)加1
    labelCounts[currentLabel] += 1
  #定義香農(nóng)熵 以2為底數(shù)求對(duì)數(shù)
  shannonEnt = 0.0
  for key in labelCounts:
    #計(jì)算 yes 或者No 出現(xiàn)的概率
    pro = float(labelCounts[key])/numEntries
    # 計(jì)算香農(nóng)熵
    shannonEnt -= pro*log(pro,2)
  return shannonEnt
#dataSet是待劃分的數(shù)據(jù)集， 劃分?jǐn)?shù)據(jù)集的特征 axis 特征的返回值value
#最后是創(chuàng)建了一個(gè)新的列表對(duì)象
def splitDataSet(dataSet, axis , value):
  # 創(chuàng)建新list對(duì)象
  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ù)集劃分
def chooseBestFeatureToSplit(dataSet):
  # len(dataSet[0]）是計(jì)算這一行有多少列，即有多少個(gè)特征值
  numFeatures = len(dataSet[0])-1 # -1 是最后一個(gè)特征值就不要記錄在內(nèi)了，算baseEntrop的時(shí)候已經(jīng)算了最后一個(gè)特征值yes no
  baseEntropy = calcShannonEnt(dataSet)
  bestInfoGain = 0.0
  bestFeature = -1
  for i in range(numFeatures):
    #創(chuàng)建唯一的分類(lèi)標(biāo)簽列表 也就是說(shuō)提取dataSet每一行第i個(gè)值 就提取dat
    featList = [example[i] for example in dataSet]
    # 取出有幾種特征值
    uniqueVals = set(featList)
    newEntropy = 0.0
    for value in uniqueVals:
      #創(chuàng)建特征值的子數(shù)據(jù)集
      subDataSet = splitDataSet(dataSet,i, value)
      #計(jì)算該特征值數(shù)據(jù)對(duì)總數(shù)在數(shù)據(jù)對(duì)總數(shù)出現(xiàn)的概率
      pro = len(subDataSet)/float(len(dataSet))
      #計(jì)算分割出來(lái)的子集香農(nóng)熵
      newEntropy += pro*calcShannonEnt(subDataSet)
    #計(jì)算信息增益 得到最好的特征值 這個(gè)理論是這樣的g(D,A) = H(D)-H(D/A）
    infoGain = baseEntropy-newEntropy
    #取出最大的信息增益，此時(shí)特征值最大
    if(infoGain >bestInfoGain):
      bestInfoGain = infoGain
      bestFeature = i
  return bestFeature
'''
#構(gòu)建決策樹(shù)是根據(jù)特征值的消耗來(lái)計(jì)算的，如果后面的特征值已經(jīng)全部用完了
但是還沒(méi)有分出結(jié)果，這個(gè)時(shí)候就需要使用多數(shù)表決方式計(jì)算節(jié)點(diǎn)分類(lèi)
最后返回最大的分類(lèi)
'''
def majorityCnt(classList):
  # 分類(lèi)的字典
  classCount = {}
  for vote in range(classList):
    #如果不在 分類(lèi)字典中
    if vote not in classCount.keys(): classCount[vote] = 0
    classCount[vote] += 1
    # 根據(jù)出現(xiàn)的次數(shù)大到小排序
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
  return sortedClassCount[0][0]
#創(chuàng)建決策樹(shù)
def createTree(dataSet, labels):
  # 獲取數(shù)據(jù)樣本每組最后一組的特征值 這里是yes,no
  classList = [example[-1] for example in dataSet]
  # 如果說(shuō)這個(gè)classList 全部都是 yes 或者全部是no 那肯定子返回yes 或者no
  if(classList.count(classList[0]) == len(classList)):
    return classList[0]
  #如果遍歷完所有的特征返回出現(xiàn)次數(shù)最多的
  #是用消耗特征值的方式進(jìn)行構(gòu)造決策樹(shù)的，每次會(huì)消掉一個(gè)特征值
  if len(dataSet[0]) == 1:
    return majorityCnt(classList)
  #選擇最好的特征值
  bestFeat = chooseBestFeatureToSplit(dataSet)
  bestFeatLabel = labels[bestFeat]
  myTree = {bestFeatLabel:{}}
  # 刪除labels中的一特征值
  del(labels[bestFeat])
  #找到特征值那一列
  featValues = [example[bestFeat] for example in dataSet]
  uniqueVals = set(featValues)
  for value in uniqueVals:
    # labels列表的賦值
    subLabels = labels[:]
    myTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
  return myTree
dataSet,lables = createDataSet()
shannonEnt= calcShannonEnt(dataSet)
my = createTree(dataSet,lables)
print(my)