决策树原理及Python实现
对一组数据利用决策树找出其最优的分类方法：
dataSet = [['长', '粗', '男'],
['短', '粗', '男'],
['短', '粗', '男'],
['长', '细', '女'],
['短', '细', '女'],
['短', '粗', '女'],
['长', '粗', '女'],
['长', '粗', '女']]
思路：在实际的生活中，第一个同学甲先根据头发判断，可以得到如下图的思路：
这便是一个简单的决策二叉树；在每一个分类的标准上按照不同的标准的再进行重新分类。
乙同学同时想到的是另外一种思路，先按照声音分类，然后按照头发进行分类：
再最后得到的结果中，我们如何取判定分类结果的好坏呢？
划分数据依据的一个标准就是减少数据不确定性的，因此可以用数据的不确定性来判定结果的好坏；
这里需要引入一个Claude Shannon定义的熵（Entropy）的概念：信息分布的不确定性可以用熵值来衡量，熵值越大代表不确定性越大，熵值由大变小代表信息分布的整齐，中间差值的变化表示信息增益。信息增益可以衡量某个特征对分类结果的影响大小。
Entropy的计算公式如下：
信息增益(information gain)，表示两个信息熵的差值
1；首先计算未分类前的熵总值，一共八位同学，3男，5女：
2；甲同学按照头发进行分类，得到的结果为：
甲同学的分类结果的熵值：H1=（4/8）*1+（4/8）*0.8113=0.9507
同理可以计算出乙同学分类结果：
乙同学分类结果的熵值为：H2=（6/8）*1+（2/8）*0=0.75
3；比较甲、乙两位同学的信息增益值：
因此乙同学的分类标准信息增益最大，分类结果也最具代表性
根据以上分析可得到一个简单的分析流程：
选中我们要分析的数据，以上面的数据为例
from math import log
import operator
def calcShannonEnt(dataSet): # 计算数据的熵(entropy)
numEntries=len(dataSet) # 数据条数
labelCounts={}
for featVec in dataSet:
currentLabel=featVec[-1] # 每行数据的最后一个字（类别）
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel]=0
labelCounts[currentLabel]+=1 # 统计有多少个类以及每个类的数量
shannonEnt=0
for key in labelCounts:
prob=float(labelCounts[key])/numEntries # 计算单个类的熵值
shannonEnt-=prob*log(prob,2) # 累加每个类的熵值
return shannonEnt
def createDataSet1(): # 创造示例数据
dataSet = [['长', '粗', '男'],
['短', '粗', '男'],
['短', '粗', '男'],
['长', '细', '女'],
['短', '细', '女'],
['短', '粗', '女'],
['长', '粗', '女'],
['长', '粗', '女']]
labels = ['头发','声音'] #两个特征
return dataSet,labels
def splitDataSet(dataSet,axis,value): # 按某个特征分类后的数据
retDataSet=[]
for featVec in dataSet:
if featVec[axis]==value:
reducedFeatVec =featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet
def chooseBestFeatureToSplit(dataSet): # 选择最优的分类特征
numFeatures = len(dataSet[0])-1
baseEntropy = calcShannonEnt(dataSet) # 原始的熵
bestInfoGain = 0
bestFeature = -1
for i in range(numFeatures):
featList = [example[i] for example in dataSet]
uniqueVals = set(featList)
newEntropy = 0
for value in uniqueVals:
subDataSet = splitDataSet(dataSet,i,value)
prob =len(subDataSet)/float(len(dataSet))
newEntropy +=prob*calcShannonEnt(subDataSet) # 按特征分类后的熵
infoGain = baseEntropy - newEntropy # 原始熵与按特征分类后的熵的差值
if (infoGain>bestInfoGain): # 若按某特征划分后，熵值减少的最大，则次特征为最优分类特征
bestInfoGain=infoGain
bestFeature = i
return bestFeature
def majorityCnt(classList): #按分类后类别数量排序，比如：最后分类为2男1女，则判定为男；
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):
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])
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
if __name__=='__main__':
dataSet, labels=createDataSet1() # 创造示列数据
print(createTree(dataSet, labels)) # 输出决策树模型结果
