决策树算法选购玩具车

家里的小毛头喜欢玩具车，为人父母自然少不了在某宝某东频频下单。

为了摸清小家伙选车的脾气，本文尝试用决策树（Decision Tree）推导看看。

决策树构造思路：

依次用每个特征对样本数据集进行划分，选择最佳特征创建分支节点，再对每一个分支节点中的样本数据子集重复此过程，直至每个节点包含的样本数据都属于同一个类别为止。

如何评价每个特征是否对于样本数据集进行了最佳划分呢？最简单的方式就是对划分所得的所有同质子集包含的样本个数进行加总，总数越大划分效果越好。

为简化起见，正例用“+”表示喜欢，反例用“-”表示不喜欢。

输入数据：

先进行第一轮划分，统计每个特征下同质子集中的样本总数，混合节点中的样本不计数。

金属材质 Yes对应1个正例+No对应3个反例=4

品牌 HotWheels对应3个反例=3

颜色 Blue对应2个反例=2

车型 没有同质子集，样本数=0

可见，金属材质为最佳特征，从而完成第一轮划分。

经过首轮划分，余下的数据集还有4个材质未知的样本需要处理，再重复划分一遍。

统计一下每个特征对应的同质子集样本总数：

品牌 HotWheels对应2个反例+Siku对应2个正例=4

颜色 Blue对应1个反例+Mix对应1个正例=2

车型 没有同质子集，样本数=0

显然品牌为第二轮划分最佳特征，至此所有8个样本数据划分完毕，构造决策树如图。

看起来还是金属小车更受小毛头欢迎，买其他材质的话最好还是选Siku系列的，嗯嗯。

为了让算法看起来更高级，可以把划分特征的评价标准从同质子集样本计数替换成高大上的信息熵(Entropy)。换句话说，数据越混乱越无序，熵也就越高。

设有随机变量(X, Y)，其联合概率分布为

条件熵H(YX)表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵H(YX)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望

其中

对于伯努利分布，熵H(p)随概率p的变化曲线是一条抛物线。

理论的东西看着不开心，代码跑一遍收工，ZZZzzz……

# -*-coding: utf-8 -*-

"""

Author:vincentqiao

"""

frommath import log

importoperator

defcalcShannonEnt(dataSet):

numEntries = len(dataSet)

labelCounts = {}

for featVec in dataSet:

currentLabel = featVec[-1]

if currentLabel not inlabelCounts.keys():

labelCounts[currentLabel] = 0

labelCounts[currentLabel] += 1

shannonEnt = 0.0

for key in labelCounts:

prob =float(labelCounts[key])/numEntries

shannonEnt -= prob * log(prob,2)

return shannonEnt

defcreateDataSet():

dataSet = [

['?','HW','Blue','Car','no'],

['N','HW','Red','Car','no'],

['?','SK','Red','Car','yes'],

['Y','SK','Mix','SUV','yes'],

['?','SK','Mix','Truck','yes'],

['N','SK','Blue','SUV','no'],

['N','SK','Mix','SUV','no'],

['?','HW','Red','Truck','no']

]

labels = ['Metal','Brand','Color','Model']

return dataSet, labels

defsplitDataSet(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

defchooseBestFeatureToSplit(dataSet):

numFeatures = len(dataSet[0]) - 1

baseEntropy = calcShannonEnt(dataSet)

bestInfoGain = 0.0; bestFeature = -1

for i in range(numFeatures):

featList = [example[i] for example indataSet]

uniqueVals = set(featList)

newEntropy = 0.0

for value in uniqueVals:

subDataSet = splitDataSet(dataSet,i, value)

prob =len(subDataSet)/float(len(dataSet))

newEntropy += prob *calcShannonEnt(subDataSet)

infoGain = baseEntropy - newEntropy

print("I=%s, Feature=%s,InfoGain=%s"%(i,labels[i],infoGain))

if (infoGain > bestInfoGain):

bestInfoGain = infoGain

bestFeature = i

print('BestFeature=%s'%(labels[bestFeature]))

return bestFeature

defmajorityCnt(classList):

classCount={}

for vote in classList:

if vote not in classCount.keys():

classCount[vote] = 0

classCount[vote] += 1

sortedClassCount =sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)

return sortedClassCount[0][0]

def createTree(dataSet,labels):

classList = [example[-1] for example indataSet]

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 = }

del(labels[bestFeat])

featValues = [example[bestFeat] for examplein dataSet]

uniqueVals = set(featValues)

for value in uniqueVals:

subLabels = labels[:]

myTree[bestFeatLabel][value] =createTree(splitDataSet\

(dataSet, bestFeat, value),subLabels)

return myTree

myDat,labels = createDataSet()

myTree =createTree(myDat,labels)

print(myTree)

输出结果

BestFeature=Metal

I=0,Feature=Brand, InfoGain=1.0

I=1,Feature=Color, InfoGain=0.5

I=2,Feature=Model, InfoGain=0.0

BestFeature=Brand

{'Metal':{'Y': 'yes', 'N': 'no', '?': {'Brand': {'SK': 'yes', 'HW': 'no'}}}}

参考：

李航《统计学习方法》

Patrick Winston MIT AI OpenCourse

Peter Harrington《机器学习实战》