#coding :utf-8'''2017.6.25 author :Erin    function: "decesion tree" ID3   '''import numpy as npimport pandas as pdfrom math import logimport 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 ,表示帶最后標簽列的數據集 計算給定數據集總的信息熵 {'是': 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 為底的對數 return entropy def split_data(data,feature_index,value): ''' 劃分數據集 feature_index：用于劃分特征的列數，例如“年齡” value:劃分后的屬性值：例如“青少年” ''' data_split=[]#劃分后的數據集 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_splitdef choose_best_to_split(data):  ''' 根據每個特征的信息增益，選擇最大的劃分數據集的索引特征 '''  count_feature=len(data[0])-1#特征個數4 #print(count_feature)#4 entropy=cal_entropy(data)#原數據總的信息熵 #print(entropy)#0.9402859586706309  max_info_gain=0.0#信息增益最大 split_fea_index = -1#信息增益最大，對應的索引號  for i in range(count_feature):    feature_list=[fe_index[i] for fe_index in data]#獲取該列所有特征值  #######################################  '''  print('feature_list')  ['青少年', '青少年', '中年', '老年', '老年', '老年', '中年', '青少年', '青少年', '老年',  '青少年', '中年', '中年', '老年']  0.3467680694480959 #對應上篇博客中的公式 =（1）*5/14  0.3467680694480959  0.6935361388961918  '''  # print(feature_list)  unqval=set(feature_list)#去除重復  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] 次數最多的類標簽 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): ''' 字典的鍵存放節點信息，分支及葉子節點存放值 ''' featname = featnames[:]    ################ classlist = [featvec[-1] for featvec in dataSet] #此節點的分類情況 if classlist.count(classlist[0]) == len(classlist): #全部屬于一類  return classlist[0] if len(dataSet[0]) == 1:   #分完了,沒有屬性了  return Vote(classlist)  #少數服從多數 # 選擇一個最優特征進行劃分 bestFeat = choose_best_to_split(dataSet) bestFeatname = featname[bestFeat] del(featname[bestFeat])  #防止下標不準 DecisionTree = {bestFeatname:{}} # 創建分支,先找出所有屬性值,即分支數 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): '計算決策樹的葉子數'  # 葉子數 numLeafs = 0 # 節點信息 sides = list(myTree.keys())  firstStr =sides[0] # 分支信息 secondDict = myTree[firstStr]  for key in secondDict.keys(): # 遍歷所有分支  # 子樹分支則遞歸計算  if type(secondDict[key]).__name__=='dict':   numLeafs += getNumLeafs(secondDict[key])  # 葉子分支則葉子數+1  else: numLeafs +=1   return numLeafs  def getTreeDepth(myTree): '計算決策樹的深度'  # 最大深度 maxDepth = 0 # 節點信息 sides = list(myTree.keys())  firstStr =sides[0] # 分支信息 secondDict = myTree[firstStr]  for key in secondDict.keys(): # 遍歷所有分支  # 子樹分支則遞歸計算  if type(secondDict[key]).__name__=='dict':   thisDepth = 1 + getTreeDepth(secondDict[key])  # 葉子分支則葉子數+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:  終端節點顯示內容#  centerPt: 終端節點坐標#  parentPt: 起始節點坐標#  nodeType: 終端節點樣式# 輸出：#  在圖形界面中顯示輸入參數指定樣式的線段(終端帶節點)# ==================================================def plotNode(nodeTxt, centerPt, parentPt, nodeType): '畫線(末端帶一個點)'   createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction', xytext=centerPt, textcoords='axes fraction', va="center", ha="center", bbox=nodeType, arrowprops=arrow_args ) # =================================================================# 輸入：#  cntrPt:  終端節點坐標#  parentPt: 起始節點坐標#  txtString: 待顯示文本內容# 輸出：#  在圖形界面指定位置(cntrPt和parentPt中間)顯示文本內容(txtString)# =================================================================def plotMidText(cntrPt, parentPt, txtString): '在指定位置添加文本'  # 中間位置坐標 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: 根節點坐標#  nodeTxt: 根節點坐標信息# 輸出：#  在圖形界面繪制決策樹# ===================================def plotTree(myTree, parentPt, nodeTxt): '繪制決策樹'  # 當前樹的葉子數 numLeafs = getNumLeafs(myTree) # 當前樹的節點信息 sides = list(myTree.keys())  firstStr =sides[0]  # 定位第一棵子樹的位置(這是蛋疼的一部分) cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff)  # 繪制當前節點到子樹節點(含子樹節點)的信息 plotMidText(cntrPt, parentPt, nodeTxt) plotNode(firstStr, cntrPt, parentPt, decisionNode)  # 獲取子樹信息 secondDict = myTree[firstStr] # 開始繪制子樹，縱坐標-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))   # 子樹繪制完畢，縱坐標+1。 plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD # ==============================# 輸入：#  myTree: 決策樹# 輸出：#  在圖形界面顯示決策樹# ==============================def createPlot(inTree): '顯示決策樹'  # 創建新的圖像并清空 - 無橫縱坐標 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))  # 當前繪制節點的坐標 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'}} '''