使用决策树预测隐形眼镜类型
说明:
将数据集文件 ‘lenses.txt’ 放在当前文件夹
from math import logimport operator
熵的定义
"""这部分是在用代码计算香农熵公式,即用代码写公式并计算结果"""def calcShannonEnt(dataSet):#数据集行数numEntries = len(dataSet)#创建空字典记录yes or no的次数labelCounts = {}#开始用循环语句统计标签频数,该思路和KNN算法是一样的#the the number of unique elements and their occurancefor featVec in dataSet:currentLabel = featVec[-1]if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0labelCounts[currentLabel] += 1#初始值是0,然后根据公式,用循环语句开始计算shannonEnt = 0.0for key in labelCounts:#公式计算部分prob = float(labelCounts[key])/numEntriesshannonEnt -= prob * log(prob, 2) return shannonEnt
划分数据集: 按照给定特征划分数据集
#这个函数后面用的上,先看懂代码。后一个函数会让你看懂它的真正作用。def splitDataSet(dataSet, axis, value):retDataSet = []for featVec in dataSet:if featVec[axis] == value:#去掉axis特征reducedFeatVec = featVec[:axis]reducedFeatVec.extend(featVec[axis+1:])retDataSet.append(reducedFeatVec)return retDataSet
选择最好的数据集划分方式
#该函数选取最优的特征,并返回最优特征的索引值def chooseBestFeatureToSplit(dataSet):#特征数量#the last column is used for the labelsnumFeatures = len(dataSet[0]) - 1 #计算数据集的香农熵baseEntropy = calcShannonEnt(dataSet)#信息增益bestInfoGain = 0.0#最优特征的索引值,-1是随便设置的值,便于后续更新值bestFeature = -1#遍历所有特征for i in range(numFeatures):#获取dataSet的第i个所有特征featList = [example[i] for example in dataSet]#创建set集合{},元素不可重复uniqueVals = set(featList)#经验条件熵newEntropy = 0.0#计算信息增益for value in uniqueVals:#subDataSet划分后的子集subDataSet = splitDataSet(dataSet, i, value)#计算子集的概率prob = len(subDataSet)/float(len(dataSet))#根据公式计算经验条件熵newEntropy += prob * calcShannonEnt(subDataSet)#信息增益。calculate the info gain; ie reduction in entropyinfoGain = baseEntropy - newEntropy #计算信息增益。compare this to the best gain so farif (infoGain > bestInfoGain): #更新信息增益,找到最大的信息增益。if better than current best, set to bestbestInfoGain = infoGain #记录信息增益最大的特征的索引值bestFeature = ireturn bestFeature
多数表决法决定该叶子节点的分类
#这个函数是在下一个函数里面第二个停止条件时候用上的"""代码与第2章classify0部分的投票表决代码非常类似"""def majorityCnt(classList):classCount={}#统计classList中每个元素出现的次数for vote in classList:if vote not in classCount.keys(): classCount[vote] = 0classCount[vote] += 1#最后利用operator操作键值排序字典,并返回出现次数最多的分类名称sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)#返回classList中出现次数最多的元素return sortedClassCount[0][0]
递归构建决策树
#核心程序,创建树def createTree(dataSet, labels):#取出所有分类标签,yes or noclassList = [example[-1] for example in dataSet]#如果类别完全相同,则停止继续划分。这是第一个停止条件。if classList.count(classList[0]) == len(classList):return classList[0]#stop splitting when there are no more features in dataSe#如果特征都遍历完了,还是没有划分的很纯净,那么就取数量多一点的那个类别。这是第二个停止条件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)#遍历特征,创建决策树。"""代码遍历当前选择特征包含的所有属性值,在每个数据集划分上递归调用函数,createTree(),得到的返回值将被插入到字典变量myTree中,因此函数终止执行时,字典中将会嵌套很多代表叶子节点信息的字典数据。"""for value in uniqueVals:#copy all of labels, so trees don't mess up existing labelssubLabels = labels[:] myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)return myTree
使用决策树执行分类
def classify(inputTree, featLabels, testVec):#获取决策树结点firstStr = list(inputTree)[0] #下一个字典secondDict = inputTree[firstStr] #返回节点特征的索引值featIndex = featLabels.index(firstStr) for key in secondDict.keys():if testVec[featIndex] == key:if type(secondDict[key]).__name__ == 'dict':classLabel = classify(secondDict[key], featLabels, testVec)else: classLabel = secondDict[key]return classLabel
使用决策树预测隐形眼镜类型
#打开文本数据fr = open('lenses.txt')#解析数据lenses = [inst.strip().split('\t') for inst in fr.readlines()]lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']#训练算法,根据creatTree函数建树lensesTree = createTree(lenses,lensesLabels)print(lensesTree)
{'tearRate': {'reduced': 'no lenses', 'normal': {'astigmatic': {'yes': {'prescript': {'myope': 'hard', 'hyper': {'age': {'pre': 'no lenses', 'presbyopic': 'no lenses', 'young': 'hard'}}}}, 'no': {'age': {'pre': 'soft', 'presbyopic': {'prescript': {'myope': 'no lenses', 'hyper': 'soft'}}, 'young': 'soft'}}}}}}
使用决策树模型进行预测
lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']classify(lensesTree, lensesLabels, lenses[0][:-1])
'no lenses'
对 lenses 数据集所有数据进行决策树分类预测
preds = []for i in range(len(lenses)):pred = classify(lensesTree, lensesLabels, lenses[i][:-1])preds.append(pred)print(preds)
['no lenses', 'soft', 'no lenses', 'hard', 'no lenses', 'soft', 'no lenses', 'hard', 'no lenses', 'soft', 'no lenses', 'hard', 'no lenses', 'soft', 'no lenses', 'no lenses', 'no lenses', 'no lenses', 'no lenses', 'hard', 'no lenses', 'soft', 'no lenses', 'no lenses']