1. 定义生成树

# -*- coding: utf-8 -*-
#生成树的函数

from numpy import *  
import numpy as np
import pandas as pd
from math import log  
import operator  

# 计算数据集的信息熵(Information Gain)增益函数(机器学习实战中信息熵叫香农熵)
def calcInfoEnt(dataSet):#本题中Label即好or坏瓜 #dataSet每一列是一个属性(列末是Label)
    numEntries = len(dataSet)    #每一行是一个样本
    labelCounts = {} #给所有可能的分类创建字典labelCounts
    for featVec in dataSet:    #按行循环：即rowVev取遍了数据集中的每一行
        currentLabel = featVec[-1]    #故featVec[-1]取遍每行最后一个值即Label
        if currentLabel not in labelCounts.keys():    #如果当前的Label在字典中还没有
            labelCounts[currentLabel] = 0    #则先赋值0来创建这个词
        labelCounts[currentLabel] += 1    #计数, 统计每类Label数量(这行不受if限制)
    InfoEnt = 0.0
    for key in labelCounts:    #遍历每类Label
        prob = float(labelCounts[key])/numEntries   #各类Label熵累加
        InfoEnt -= prob * log(prob,2)    #ID3用的信息熵增益公式
    return InfoEnt

### 对于离散特征: 取出该特征取值为value的所有样本
def splitDiscreteDataSet(dataSet, axis, value):    #dataSet是当前结点(待划分)集合,axis指示划分所依据的属性,value该属性用于划分的取值
    retDataSet = []     #为return Data Set分配一个列表用来储存
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]         #该特征之前的特征仍保留在样本dataSet中
            reducedFeatVec.extend(featVec[axis+1:]) #该特征之后的特征仍保留在样本dataSet中
            retDataSet.append(reducedFeatVec)        #把这个样本加到list中
    return retDataSet

### 对于连续特征: 返回特征取值大于value的所有样本(以value为阈值将集合分成两部分)
def splitContinuousDataSet(dataSet, axis, value): 
    retDataSetG = []        #将储存取值大于value的样本
    retDataSetL = []        #将储存取值小于value的样本  
    for featVec in dataSet:  
        if featVec[axis] > value:  
            reducedFeatVecG = featVec[:axis]
            reducedFeatVecG.extend(featVec[axis+1:])  
            retDataSetG.append(reducedFeatVecG)
        else:
            reducedFeatVecL = featVec[:axis]
            reducedFeatVecL.extend(featVec[axis+1:])  
            retDataSetL.append(reducedFeatVecL)
    return retDataSetG,retDataSetL        #返回两个集合, 是含2个元素的tuple形式

### 根据InfoGain选择当前最好的划分特征(以及对于连续变量还要选择以什么值划分)
def chooseBestFeatureToSplit(dataSet,labels):  
    numFeatures = len(dataSet[0])-1
    baseEntropy = calcInfoEnt(d