决策树原理实例（python代码实现）
决策数(Decision Tree)在机器学习中也是⽐较常见的⼀种算法，属于监督学习中的⼀种。看字⾯意思应该也⽐较容易理解，相⽐其他算法⽐如⽀持向量机(SVM)或神经⽹络，似乎决策树感觉“亲切”许多。
优点：计算复杂度不⾼，输出结果易于理解，对中间值的缺失值不敏感，可以处理不相关特征数据。
缺点：可能会产⽣过度匹配的问题。
使⽤数据类型：数值型和标称型。
简单介绍完毕，让我们来通过⼀个例⼦让决策树“原形毕露”。
⼀天，⽼师问了个问题，只根据头发和声⾳怎么判断⼀位同学的性别。
为了解决这个问题，同学们马上简单的统计了7位同学的相关特征，数据如下：
头发声⾳性别
长粗男
短粗男
短粗男
长细⼥
短细⼥
短粗⼥
长粗⼥
长粗⼥
机智的同学A想了想，先根据头发判断，若判断不出，再根据声⾳判断，于是画了⼀幅图，如下：
于是，⼀个简单、直观的决策树就这么出来了。头发长、声⾳粗就是男⽣；头发长、声⾳细就是⼥⽣；头发短、声⾳粗是男⽣；头发短、声⾳细是⼥⽣。
原来机器学习中决策树就这玩意，这也太简单了吧。。。
这时⼜蹦出个同学B，想先根据声⾳判断，然后再根据头发来判断，如是⼤⼿⼀挥也画了个决策树：
同学B的决策树：⾸先判断声⾳，声⾳细，就是⼥⽣；声⾳粗、头发长是男⽣；声⾳粗、头发长是⼥⽣。
那么问题来了：同学A和同学B谁的决策树好些？计算机做决策树的时候，⾯对多个特征，该如何选哪个特征为最佳的划分特征？
划分数据集的⼤原则是：将⽆序的数据变得更加有序。
我们可以使⽤多种⽅法划分数据集，但是每种⽅法都有各⾃的优缺点。于是我们这么想，如果我们能测量数据的复杂度，对⽐按不同特征分类后的数据复杂度，若按某⼀特征分类后复杂度减少的更多，那么这个特征即为最佳分类特征。
Claude Shannon 定义了熵（entropy）和信息增益(information gain)。
⽤熵来表⽰信息的复杂度，熵越⼤，则信息越复杂。公式如下：
信息增益(information gain)，表⽰两个信息熵的差值。
⾸先计算未分类前的熵，总共有8位同学，男⽣3位，⼥⽣5位。
熵（总）=-3/8log2(3/8)-5/8log2(5/8)=0.9544
接着分别计算同学A和同学B分类后信息熵。
同学A⾸先按头发分类，分类后的结果为：长头发中有1男3⼥。短头发中有2男2⼥。
熵（同学A长发）=-1/4log2(1/4)-3/4log2(3/4)=0.8113
熵（同学A短发）=-2/4log2(2/4)-2/4log2(2/4)=1
熵（同学A）=4/80.8113+4/81=0.9057
信息增益（同学A）=熵（总）-熵（同学A）=0.9544-0.9057=0.0487和安
同理，按同学B的⽅法，⾸先按声⾳特征来分，分类后的结果为：声⾳粗中有3男3⼥。声⾳细中有0男2⼥。
熵（同学B声⾳粗）=-3/6log2(3/6)-3/6log2(3/6)=1
熵（同学B声⾳粗）=-2/2log2(2/2)=0
熵（同学B）=6/81+2/8*0=0.75
信息增益（同学B）=熵（总）-熵（同学B）=0.9544-0.75=0.2087
按同学B的⽅法，先按声⾳特征分类，信息增益更⼤，区分样本的能⼒更强，更具有代表性。
以上就是决策树ID3算法的核⼼思想。
接下来⽤python代码来实现ID3算法：
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]
retDataSet.append(reducedFeatVec)
return retDataSet
def chooBestFeatureToSplit(dataSet): # 选择最优的分类特征
numFeatures = len(dataSet[0])-1
baEntropy = calcShannonEnt(dataSet) # 原始的熵
bestInfoGain = 0
bestFeature = -1
for i in range(numFeatures):
featList = [example[i] for example in dataSet]
uniqueVals = t(featList)
newEntropy = 0
for value in uniqueVals:
subDataSet = splitDataSet(dataSet,i,value)
prob =len(subDataSet)/float(len(dataSet))
newEntropy +=prob*calcShannonEnt(subDataSet) # 按特征分类后的熵
infoGain = baEntropy - 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),rever=True)
return sortedClassCount[0][0]
def createTree(dataSet,labels):
classList=[example[-1] for example in dataSet] # 类别：男或⼥
unt(classList[0])==len(classList):
return classList[0]
if len(dataSet[0])==1:
return majorityCnt(classList)
bestFeat=chooBestFeatureToSplit(dataSet) #选择最优特征
bestFeatLabel=labels[bestFeat]
myTree={bestFeatLabel:{}} #分类结果以字典形式保存
paralyzeddel(labels[bestFeat])
featValues=[example[bestFeat] for example in dataSet]
uniqueVals=t(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)) # 输出决策树模型结果
输出结果为：
{'声⾳': {'细': '⼥', '粗': {'头发': {'短': '男', '长': '⼥'}}}}
这个结果的意思是：⾸先按声⾳分类，声⾳细为⼥⽣；然后再按头发分类：声⾳粗，头发短为男⽣；声⾳粗，头发长为⼥⽣。
老子出生日期
这个结果也正是同学B的结果。
补充说明：判定分类结束的依据是，若按某特征分类后出现了最终类（男或⼥），则判定分类结束。使⽤这种⽅法，在数据⽐较⼤，特征⽐较多的情况下，很容易造成过拟合，于是需进⾏决策树枝剪，⼀般枝剪⽅法是当按某⼀特征分类后的熵⼩于设定值时，停⽌分类。
坐动车ID3算法存在的缺点：
1. ID3算法在选择根节点和内部节点中的分⽀属性时，采⽤信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多是属性，在有
些情况下这类属性可能不会提供太多有价值的信息。
2. ID3算法只能对描述属性为离散型属性的数据集构造决策树 。
为了改进决策树，⼜提出了ID4.5算法和CART算法。之后有时间会介绍这两种算法。
参考：
