#coding :utf-8
'''
2017.6.25 author :Erin 
   function: "decesion tree" ID3
   
'''
import numpy as np
import pandas as pd
from math import log
import operator 
def load_data():
 
 #data=np.array(data)
 data=[['teenager' ,'high', 'no' ,'same', 'no'],
   ['teenager', 'high', 'no', 'good', 'no'],
   ['middle_aged' ,'high', 'no', 'same', 'yes'],
   ['old_aged', 'middle', 'no' ,'same', 'yes'],
   ['old_aged', 'low', 'yes', 'same' ,'yes'],
   ['old_aged', 'low', 'yes', 'good', 'no'],
   ['middle_aged', 'low' ,'yes' ,'good', 'yes'],
   ['teenager' ,'middle' ,'no', 'same', 'no'],
   ['teenager', 'low' ,'yes' ,'same', 'yes'],
   ['old_aged' ,'middle', 'yes', 'same', 'yes'],
   ['teenager' ,'middle', 'yes', 'good', 'yes'],
   ['middle_aged' ,'middle', 'no', 'good', 'yes'],
   ['middle_aged', 'high', 'yes', 'same', 'yes'],
   ['old_aged', 'middle', 'no' ,'good' ,'no']]
 features=['age','input','student','level']
 return data,features
 
def cal_entropy(dataSet):
 '''
 輸入data ,表示帶最后標(biāo)簽列的數(shù)據(jù)集
 計(jì)算給定數(shù)據(jù)集總的信息熵
 {'是': 9, '否': 5}
 0.9402859586706309
 '''
 
 numEntries = len(dataSet)
 labelCounts = {}
 for featVec in dataSet:
  label = featVec[-1]
  if label not in labelCounts.keys():
   labelCounts[label] = 0
  labelCounts[label] += 1
 entropy = 0.0
 for key in labelCounts.keys():
  p_i = float(labelCounts[key]/numEntries)
  entropy -= p_i * log(p_i,2)#log(x,10)表示以10 為底的對數(shù)
 return entropy
 
def split_data(data,feature_index,value):
 '''
 劃分?jǐn)?shù)據(jù)集
 feature_index：用于劃分特征的列數(shù)，例如“年齡”
 value:劃分后的屬性值：例如“青少年”
 '''
 data_split=[]#劃分后的數(shù)據(jù)集
 for feature in data:
  if feature[feature_index]==value:
   reFeature=feature[:feature_index]
   reFeature.extend(feature[feature_index+1:])
   data_split.append(reFeature)
 return data_split
def choose_best_to_split(data):
 
 '''
 根據(jù)每個特征的信息增益，選擇最大的劃分?jǐn)?shù)據(jù)集的索引特征
 '''
 
 count_feature=len(data[0])-1#特征個數(shù)4
 #print(count_feature)#4
 entropy=cal_entropy(data)#原數(shù)據(jù)總的信息熵
 #print(entropy)#0.9402859586706309
 
 max_info_gain=0.0#信息增益最大
 split_fea_index = -1#信息增益最大，對應(yīng)的索引號
 
 for i in range(count_feature):
  
  feature_list=[fe_index[i] for fe_index in data]#獲取該列所有特征值
  #######################################
  '''
  print('feature_list')
  ['青少年', '青少年', '中年', '老年', '老年', '老年', '中年', '青少年', '青少年', '老年',
  '青少年', '中年', '中年', '老年']
  0.3467680694480959 #對應(yīng)上篇博客中的公式 =（1）*5/14
  0.3467680694480959
  0.6935361388961918
  '''
  # print(feature_list)
  unqval=set(feature_list)#去除重復(fù)
  Pro_entropy=0.0#特征的熵
  for value in unqval:#遍歷改特征下的所有屬性
   sub_data=split_data(data,i,value)
   pro=len(sub_data)/float(len(data))
   Pro_entropy+=pro*cal_entropy(sub_data)
   #print(Pro_entropy)
   
  info_gain=entropy-Pro_entropy
  if(info_gain>max_info_gain):
   max_info_gain=info_gain
   split_fea_index=i
 return split_fea_index
  
  
##################################################
def most_occur_label(labels):
 #sorted_label_count[0][0] 次數(shù)最多的類標(biāo)簽
 label_count={}
 for label in labels:
  if label not in label_count.keys():
   label_count[label]=0
  else:
   label_count[label]+=1
  sorted_label_count = sorted(label_count.items(),key = operator.itemgetter(1),reverse = True)
 return sorted_label_count[0][0]
def build_decesion_tree(dataSet,featnames):
 '''
 字典的鍵存放節(jié)點(diǎn)信息，分支及葉子節(jié)點(diǎn)存放值
 '''
 featname = featnames[:]    ################
 classlist = [featvec[-1] for featvec in dataSet] #此節(jié)點(diǎn)的分類情況
 if classlist.count(classlist[0]) == len(classlist): #全部屬于一類
  return classlist[0]
 if len(dataSet[0]) == 1:   #分完了,沒有屬性了
  return Vote(classlist)  #少數(shù)服從多數(shù)
 # 選擇一個最優(yōu)特征進(jìn)行劃分
 bestFeat = choose_best_to_split(dataSet)
 bestFeatname = featname[bestFeat]
 del(featname[bestFeat])  #防止下標(biāo)不準(zhǔn)
 DecisionTree = {bestFeatname:{}}
 # 創(chuàng)建分支,先找出所有屬性值,即分支數(shù)
 allvalue = [vec[bestFeat] for vec in dataSet]
 specvalue = sorted(list(set(allvalue))) #使有一定順序
 for v in specvalue:
  copyfeatname = featname[:]
  DecisionTree[bestFeatname][v] = build_decesion_tree(split_data(dataSet,bestFeat,v),copyfeatname)
 return DecisionTree

def getNumLeafs(myTree):
 '計(jì)算決策樹的葉子數(shù)'
 
 # 葉子數(shù)
 numLeafs = 0
 # 節(jié)點(diǎn)信息
 sides = list(myTree.keys()) 
 firstStr =sides[0]
 # 分支信息
 secondDict = myTree[firstStr]
 
 for key in secondDict.keys(): # 遍歷所有分支
  # 子樹分支則遞歸計(jì)算
  if type(secondDict[key]).__name__=='dict':
   numLeafs += getNumLeafs(secondDict[key])
  # 葉子分支則葉子數(shù)+1
  else: numLeafs +=1
  
 return numLeafs
 
 
def getTreeDepth(myTree):
 '計(jì)算決策樹的深度'
 
 # 最大深度
 maxDepth = 0
 # 節(jié)點(diǎn)信息
 sides = list(myTree.keys()) 
 firstStr =sides[0]
 # 分支信息
 secondDict = myTree[firstStr]
 
 for key in secondDict.keys(): # 遍歷所有分支
  # 子樹分支則遞歸計(jì)算
  if type(secondDict[key]).__name__=='dict':
   thisDepth = 1 + getTreeDepth(secondDict[key])
  # 葉子分支則葉子數(shù)+1
  else: thisDepth = 1
  
  # 更新最大深度
  if thisDepth > maxDepth: maxDepth = thisDepth
  
 return maxDepth
 
import matplotlib.pyplot as plt
 
decisionNode = dict(boxstyle="sawtooth", fc="0.8")
leafNode = dict(boxstyle="round4", fc="0.8")
arrow_args = dict(arrowstyle="<-")
 
# ==================================================
# 輸入：
#  nodeTxt:  終端節(jié)點(diǎn)顯示內(nèi)容
#  centerPt: 終端節(jié)點(diǎn)坐標(biāo)
#  parentPt: 起始節(jié)點(diǎn)坐標(biāo)
#  nodeType: 終端節(jié)點(diǎn)樣式
# 輸出：
#  在圖形界面中顯示輸入?yún)?shù)指定樣式的線段(終端帶節(jié)點(diǎn))
# ==================================================
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
 '畫線(末端帶一個點(diǎn))'
  
 createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction', xytext=centerPt, textcoords='axes fraction', va="center", ha="center", bbox=nodeType, arrowprops=arrow_args )
 
# =================================================================
# 輸入：
#  cntrPt:  終端節(jié)點(diǎn)坐標(biāo)
#  parentPt: 起始節(jié)點(diǎn)坐標(biāo)
#  txtString: 待顯示文本內(nèi)容
# 輸出：
#  在圖形界面指定位置(cntrPt和parentPt中間)顯示文本內(nèi)容(txtString)
# =================================================================
def plotMidText(cntrPt, parentPt, txtString):
 '在指定位置添加文本'
 
 # 中間位置坐標(biāo)
 xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]
 yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]
 
 createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)
 
# ===================================
# 輸入：
#  myTree: 決策樹
#  parentPt: 根節(jié)點(diǎn)坐標(biāo)
#  nodeTxt: 根節(jié)點(diǎn)坐標(biāo)信息
# 輸出：
#  在圖形界面繪制決策樹
# ===================================
def plotTree(myTree, parentPt, nodeTxt):
 '繪制決策樹'
 
 # 當(dāng)前樹的葉子數(shù)
 numLeafs = getNumLeafs(myTree)
 # 當(dāng)前樹的節(jié)點(diǎn)信息
 sides = list(myTree.keys()) 
 firstStr =sides[0]
 
 # 定位第一棵子樹的位置
 cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff)
 
 # 繪制當(dāng)前節(jié)點(diǎn)到子樹節(jié)點(diǎn)(含子樹節(jié)點(diǎn))的信息
 plotMidText(cntrPt, parentPt, nodeTxt)
 plotNode(firstStr, cntrPt, parentPt, decisionNode)
 
 # 獲取子樹信息
 secondDict = myTree[firstStr]
 # 開始繪制子樹，縱坐標(biāo)-1。  
 plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD
  
 for key in secondDict.keys(): # 遍歷所有分支
  # 子樹分支則遞歸
  if type(secondDict[key]).__name__=='dict':
   plotTree(secondDict[key],cntrPt,str(key))
  # 葉子分支則直接繪制
  else:
   plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW
   plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
   plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
  
 # 子樹繪制完畢，縱坐標(biāo)+1。
 plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD
 
# ==============================
# 輸入：
#  myTree: 決策樹
# 輸出：
#  在圖形界面顯示決策樹
# ==============================
def createPlot(inTree):
 '顯示決策樹'
 
 # 創(chuàng)建新的圖像并清空 - 無橫縱坐標(biāo)
 fig = plt.figure(1, facecolor='white')
 fig.clf()
 axprops = dict(xticks=[], yticks=[])
 createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)
 
 # 樹的總寬度 高度
 plotTree.totalW = float(getNumLeafs(inTree))
 plotTree.totalD = float(getTreeDepth(inTree))
 
 # 當(dāng)前繪制節(jié)點(diǎn)的坐標(biāo)
 plotTree.xOff = -0.5/plotTree.totalW; 
 plotTree.yOff = 1.0;
 
 # 繪制決策樹
 plotTree(inTree, (0.5,1.0), '')
 
 plt.show()
 
if __name__ == '__main__':
 data,features=load_data()
 split_fea_index=choose_best_to_split(data)
 newtree=build_decesion_tree(data,features)
 print(newtree)
 createPlot(newtree)
 '''
 {'age': {'old_aged': {'level': {'same': 'yes', 'good': 'no'}}, 'teenager': {'student': {'no': 'no', 'yes': 'yes'}}, 'middle_aged': 'yes'}}
 '''