构建决策树需要解决的第一个问题就是：当前数据集上哪个特征在划分数据分类时起决定性作用。
下面的例子使用的是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
原文：http://www.cnblogs.com/weimusan/p/7499310.html