构建决策树需要解决的第一个问题就是：当前数据集上哪个特征在划分数据分类时起决定性作用。

下面的例子使用的是ID3算法解决上面的问题，对数据进行分类。

计算给定数据集的香农熵

def calculateEntropy(dataSet):    numberEntries = len(dataSet)    labelCounts = {}    for featVector in dataSet:        currentLabel = featVector[-1]  # 取每行数据的类别 --> 最后一列        if currentLabel not in labelCounts.keys():            labelCounts[currentLabel] = 0        labelCounts[currentLabel] += 1    shannonEnt = 0.0    for key in labelCounts:        prob = float(labelCounts[key])/numberEntries  # 计算每个类别出现的概率        shannonEnt -= prob * log(prob,2)              # 计算香农熵    return shannonEnt

 下面是例子中用到的数据集，相对简单，但已经满足要求。

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 splitDataSet(dataSet,axis,value): # dataSet给定数据集 axis给定特征(索引)  axis给定特征的值    returnDataSet = []    for featureVec in dataSet:        if featureVec[axis] == value:            reducedFeatVec = featureVec[:axis]            reducedFeatVec.extend(featureVec[axis + 1:])            returnDataSet.append(reducedFeatVec)    return returnDataSet

 遍历整个数据集，循环计算香农熵，找到最好的特征划分方式

def chooseBestFeatureToSplit(dataSet):    numberFeatures = len(dataSet[0]) - 1    baseEntropy = calculateEntropy(dataSet)    bestInfoGain = 0.0    bestFeature = -1    for i in range(numberFeatures):  # 按照第i个特征进行划分的情况        # 使用列表推导式创建新的列表  保存第i个特征所有的特征值        featureList = [example[i] for example in dataSet]        uniqueVals = set(featureList) # 去除重复值        newEntropy = 0.0        for value in uniqueVals:  #第i个特征所有的特征值            subDataSet = splitDataSet(dataSet, i, value)            prob = len(subDataSet)/len(dataSet)            newEntropy += prob * calculateEntropy(subDataSet)        infoGain = baseEntropy - newEntropy        if (infoGain > bestInfoGain):            bestInfoGain = infoGain            bestFeature = i    return bestFeature

 如果数据集已经处理了所有的特征，但类标签并不是唯一的情况下，进行多数表决的方法决定该节点的分类，定义函数和代码如下：

def majorityCnt(classList):    classCount = {}    for vote in classList:        if vote not in classCount.keys():            classCount[vote] = 0        classCount[vote] += 1    sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse = True)    return sortedClassCount[0][0]

 下面是创建树的代码（递归）：

# 创建决策树def createTree(dataSet,labels):  # labels 保存所有的特征    classList = [example[-1] for example in dataSet]  # 保存所有类别数据    if classList.count(classList[0]) == len(classList):        return classList[0]             # 类别完全相同则停止划分    if len(dataSet[0]) == 1:        return  majorityCnt(classList)  # 遍历完所有特征时返回出现次数最多的类别    bestFeat = chooseBestFeatureToSplit(dataSet)    bestFeatLabel = labels[bestFeat]    myTree = {bestFeatLabel:{}}    del(labels[bestFeat])   # 将已经用过的特征从labels中删除    featValues = [example[bestFeat] for example in dataSet]  # 保存此次用于分类的特征的所有值    uniqueVals = set(featValues)  # 去除重复值    for value in uniqueVals:      # 遍历所有类别        subLabels = labels[:]        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)    return  myTree