机器学习笔记3-id3算法决策树程序解析，Python笔试面试题_决策树id3算法代码

def majorityCnt(classList):

‘’’

在一个列表中返回最多的值

‘’’

classCount = {}

for vote in classList:

if vote not in classCount.keys():

classCount[vote] = 0

classCount[vote] += 1

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

return sortedClassCount[0][0]

def createTree(dataSet,labels):

‘’’

构建决策树

决策树递归过程:开始一直无法理解迭代过程中有一个if-return语句,如果直接满足条件不是直接会退出程序吗?

在网上找到一个非常好的答案帮我解决了这个问题,一句话就是return之前需要将程序运行完毕,例如如下函数

def fact(n):

if n==1:

return 1

return n * fact(n - 1)

迭代过程如下:

===> fact(5)

===> 5 * fact(4)

===> 5 * (4 * fact(3))

===> 5 * (4 * (3 * fact(2)))

===> 5 * (4 * (3 * (2 * fact(1))))

在return之前,n * fact(n - 1)必须要计算完毕

本程序中的createTree(dataSet,labels)函数与之类似,在return之前,myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)必须计算完毕

设dataSet为create为:

[[1,1,‘yes’],    lebels为[‘no surfacing’,‘flippers’]

[1,1,‘yes’],

[1,0,‘no’ ],

[0,1,‘no’ ],

[0,1,‘no’ ]]

第一次迭代有两个分支1:MyTree[‘no surfacing’][0] = createTree([[1,‘no’],[1,‘no’])

2:MyTree[‘no surfacing’][1] = createTree([[1,‘yes’],[1,‘yes’],[0,‘no’])

分支1进入一次迭代直接满足条件classList.count(classList[0]) == len(classList),直接等于’no’

分支2进入一次迭代后有两个分支2_1:MyTree[‘no surfacing’][1][‘flippers’][0] = createTree([[‘no’]])

2_1:MyTree[‘no surfacing’][1][‘flippers’][1] = createTree([[‘yes’],['yes]])

2_1,2_2满足第一条语,2_1返回’no’,2_2返回’yes’,最后计算结果

MyTree[‘no surfacing’][0] = ‘no’

MyTree[‘no surfacing’][1][‘flippers’][0] = ‘no’

MyTree[‘no surfacing’][1][‘flippers’][1] = ‘yes’

即{‘no surfacing’{0:‘no’,1:{‘flippers’:{0:‘no’,1:‘yes’}}}}

‘’’

#dataSet的’yes’ or 'no’集合,在本书中的测试例子中第一次迭代时classList = [‘yes’,‘yes’,‘no’,‘no’]

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

def classify(inputTree,featLabels,testVec):

‘’’

利用决策树对给定的特征值的对象进行分类

‘’’

#树的一号决策点,测试决策树中是’no surfacing’

firstStr = list(inputTree.keys())[0]

#测试决策树中是{0:‘no’,1:{‘flippers’:{0:‘no’,1:‘yes’}}}

secoundDict = inputTree[firstStr]

#返回’no sufacing’在标签列表中的位置

featIndex = featLabels.index(firstStr)

#进入循环,如果到达叶节点,返回分类,如果没有到达,迭代

for key in secoundDict.keys():

if testVec[featIndex] == key:

if type(secoundDict[key]).__name__ == ‘dict’:

classLabel = classify(secoundDict[key],featLabels,testVec)

else:classLabel = secoundDict[key]

return classLabel

def storeTree(inputTree,filename):

‘’’

用于将构造好的决策树存储到文件中

‘’’

fw = open(filename,‘wb’)

pickle.dump(inputTree,fw)

fw.close()

def grabTree(filename):

‘’’

用于获取文件中存储的决策树

最后

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/847530