题目：按照 ID3 算法推出最终的决策树。可程序实现；也可以手工推出（要有手动推出过程）
关于ID3算法：老师上课有简单介绍过，这里推荐大家去看这个分类算法——决策树ID3算法，容易理解与上手。
解题过程：
在上面的样本中，属于yes的结果有6个，no有6个，于是可以算出训练集的熵为：
E
(
S
)
=
−
6
12
log
2
6
12
−
6
12
log
2
6
12
=
1.0
E(S)=-frac{6}{12}log_2frac{6}{12}-frac{6}{12}log_2frac{6}{12}=1.0
E(S)=−126log2126−126log2126=1.0
下面对各个属性计算对应的信息增益。
从上面可以看出顾客人数的信息增益最大，所以选择顾客人数作为根节点的测试属性，餐馆类型的信息增益为0，不能做出任何分类信息，产生第一次决策树，然后对每个叶节点再次利用上面的过程，生成最终的决策树。
具体实现：
语言：Python 工具：PyCharm
源代码：（仅供参考，水平有限，有错请指出）
import math as m
def createDataSet():
# choice: 0 no 1 yes
# hungry: 0 no 1 yes
# price: 0 low 1 mid 2 high
# types: 0 china 1 italy 2 france 3 fast
# peolpe: 0 nobody 1 some 2 full
# waitmin: 0 0-10 1 10-30 2 30-60 3 >60
dataSet = [[1, 1, 2, 2, 1, 0, 'yes'],
[1, 1, 0, 0, 2, 2, 'no'],
[0, 0, 0, 3, 1, 0, 'yes'],
[1, 1, 0, 0, 2, 1, 'yes'],
[1, 0, 2, 2, 2, 3, 'no'],
[0, 1, 1, 1, 1, 0, 'yes'],
[0, 0, 0, 3, 0, 0, 'no'],
[0, 1, 1, 0, 1, 0, 'yes'],
[0, 0, 0, 3, 2, 3, 'no'],
[1, 1, 2, 1, 2, 1, 'no'],
[1, 0, 0, 0, 0, 0, 'no'],
[0, 1, 0, 3, 2, 2, 'yes'],
]
return dataSet
# 计算数据集熵的函数
def calcShannonEnt(dataSet):
numEntries = len(dataSet) #获取数据的数目
labelCounts = {}
for featVec in dataSet:
currentLable = featVec[-1] #取得最后一列数据，做为标签
if currentLable not in labelCounts.keys(): #获取不同标签的数目
labelCounts[currentLable] = 0 #初始化当前新增标签
labelCounts[currentLable] += 1
#计算熵
Ent = 0.0
for feat in labelCounts:
prob = float(labelCounts[feat]) / numEntries
Ent -= prob * m.log(prob, 2)
#print ("信息熵: ", Ent)
return Ent
# 按照给定特征划分数据集
def splitDataSet(dataSet, axis, value):
# axis:给定特征 value:具体值--0、1、2
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value: # 每行中第axis个元素和value相等（去除第axis个数据）
reducedFeatVec = featVec[:axis]
reducedFeatVec.extend(featVec[axis + 1:])
retDataSet.append(reducedFeatVec)
return retDataSet # 返回分类后的新矩阵
# 根据熵，选择最优的划分方式
# 根据某一属性划分后，类标签熵越低，效果越好
def chooseBestFeatureToSplit(dataSet):
baseEntropy = calcShannonEnt(dataSet) # 计算数据集的初始熵
numFeatures = len(dataSet[0]) - 1 # 除结果外，其余都是特征
bestInfoGain = 0.0 # 最大信息增益
bestFeature = 0 # 最优特征
for i in range(0, numFeatures):
featList = [example[i] for example in dataSet] # 所有子列表（每行）的第i个元素，组成一个新的列表
# print(len(featList))
# 将dataSet中的数据先按行依次放入example中，然后取得example中的example[i]元素，放入列表featList中
# featList中是每种特征的详细数据
uniquevals = set(featList)
newEntorpy = 0.0 # 新熵
for value in uniquevals: # 数据集根据第i个属性进行划分，计算划分后数据集的熵
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet) / float(len(dataSet))
newEntorpy += prob * calcShannonEnt(subDataSet)
infoGain = baseEntropy - newEntorpy # 划分后的数据集，熵越小越好，即信息增益越大越好
if (infoGain > bestInfoGain):# 信息增益最大
bestInfoGain = infoGain# 确定最大增益
bestFeature = i# 确定最好特征
return bestFeature
# 训练算法
# 如果数据集已经处理了所有属性，但叶子结点中类标签依然不是唯一的，此时需要决定如何定义该叶子结点。这种情况下，采用多数表决方法，对该叶子结点进行分类
def majorityCnt(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 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[:]
subDataSet = splitDataSet(dataSet, bestFeat, value)
myTree[bestFeatLabel][value] = createTree(subDataSet, subLabels)
# print("myTree:", myTree)
return myTree
# 测试
if __name__ == '__main__':
dataSet = createDataSet()
labels = ['choice', 'hungry', 'price', 'types', 'people', 'waitmin']
labelsForCreateTree = labels[:]
Tree = createTree(dataSet, labelsForCreateTree)
print(Tree)
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）