1 def chooseBestFeatureToSplit(dataSet):
 2     numFeatures = len(dataSet[0]) - 1
 3     baseEntropy = calcShannonEnt(dataSet)
 4     bestInfoGain = 0.0
 5     bestFeature = -1
 6     for i in range(numFeatures):
 7         #利用推导式提取出dataSet的第i列特征值
 8         featList = [example[i] for example in dataSet]
 9         uniqueVals = set(featList)
10         newEntropy = 0.0
11         for value in uniqueVals:
12             subDataSet = splitDataSet(dataSet, i, value)
13             prob = len(subDataSet)/float(len(dataSet))
14             newEntropy += prob * calcShannonEnt(subDataSet)
15         #比较信息熵的差值，取信息熵下降效果最明显的特征
16         infoGain = baseEntropy - newEntropy
17         if (infoGain > bestInfoGain):
18             bestInfoGain = infoGain
19             bestFeature = i
20     return bestFeature

 1 def createTree(dataSet,labels):
 2     classList = [example[-1] for example in dataSet]
 3     if (classList.count(classList[0]) == len(classList)): return classList[0]
 4     if (len(dataSet[0]) == 1): return majorityCnt(classList)
 5     bestFeat = chooseBestFeatureToSplit(dataSet)
 6     bestFeatLabel = labels[bestFeat]
 7     myTree = {bestFeatLabel:{}}
 8     del(labels[bestFeat])
 9     featValues = [example[bestFeat] for example in dataSet]
10     uniqueVals = set(featValues)
11     for value in uniqueVals:
12         subLabels = labels[:]
13         myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
14     return myTree