Python实现ID3【决策树】
本帖最后由 糖逗 于 2020-11-5 16:59 编辑参考书籍：《机器学习实战》
import numpy as np
import operator
import matplotlib.pyplot as plt
from math import log
def calcShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet:
currentLabel = featVec[-1]
if currentLabel not in labelCounts.keys():
labelCounts = 0
labelCounts += 1
shannonEnt = 0
for key in labelCounts:
prob = float(labelCounts) / numEntries
shannonEnt -= prob * log(prob, 2)#以2为底数
return shannonEnt
#根据特征划分数据集
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec == value:
reduceFeatVec = featVec[:axis]#不包括axis
reduceFeatVec.extend(featVec)
retDataSet.append(reduceFeatVec)
return retDataSet
#选择最好的数据集划分方式
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet) - 1
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0
bestFeature = -1
for i in range(numFeatures):#每个特征单独计算
featList = 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):
classCount = {}
for vote in classList:
if vote not in classCount.keys():
classCount = 0
classCount += 1
sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1),
reverse = True)
return sortedClassCount
#创建树的代码（递归）
def createTree(dataSet, labels):
classList = for example in dataSet]
if classList.count(classList) == len(classList):#count()方法用于统计某个元素在列表中出现的次数。
return classList
if len(dataSet) == 1:
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = labels
myTree = {bestFeatLabel:{}}
del(labels)
featValues = for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = labels[:]
myTree = createTree(splitDataSet(dataSet, bestFeat, value),
subLabels)
return myTree
def classify(inputTree, featLabels, testVec):
firstStr = list(inputTree.keys())
secondDict = inputTree
featIndex = featLabels.index(firstStr)
for key in secondDict.keys():
if testVec == key:
if type(secondDict).__name__ == "dict":#如果是字典的话，接着向下找
classLabel = classify(secondDict, featLabels, testVec)
else:
classLabel = secondDict
return classLabel
if __name__ == '__main__':
dataSet = [,
,
,
,
]
labels = ["no surfacing", "flippers"]
tree = createTree(dataSet, labels)
labels = ["no surfacing", "flippers"]#因为createTree阶段会删除labels中的值
res = classify(tree, labels, )
print(res)
{:10_327:}递归
页:
[1]