使用决策树预测隐形眼镜类型

说明:

将数据集文件 ‘lenses.txt’ 放在当前文件夹

from math import log import operator

熵的定义

""" 这部分是在用代码计算香农熵公式，即用代码写公式并计算结果 """ def calcShannonEnt(dataSet): #数据集行数 numEntries = len(dataSet) #创建空字典记录yes or no的次数 labelCounts = {} #开始用循环语句统计标签频数，该思路和KNN算法是一样的 #the the number of unique elements and their occurance for featVec in dataSet: currentLabel = featVec[-1] if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0 labelCounts[currentLabel] += 1 #初始值是0，然后根据公式，用循环语句开始计算 shannonEnt = 0.0 for key in labelCounts: #公式计算部分 prob = float(labelCounts[key])/numEntries shannonEnt -= 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 labels numFeatures = 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 entropy infoGain = baseEntropy - newEntropy #计算信息增益。compare this to the best gain so far if (infoGain > bestInfoGain): #更新信息增益，找到最大的信息增益。if better than current best, set to best bestInfoGain = infoGain #记录信息增益最大的特征的索引值 bestFeature = i return bestFeature

多数表决法决定该叶子节点的分类

#这个函数是在下一个函数里面第二个停止条件时候用上的 """ 代码与第2章classify0部分的投票表决代码非常类似 """ def majorityCnt(classList): classCount={} #统计classList中每个元素出现的次数 for vote in classList: if vote not in classCount.keys(): classCount[vote] = 0 classCount[vote] += 1 #最后利用operator操作键值排序字典，并返回出现次数最多的分类名称 sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) #返回classList中出现次数最多的元素 return sortedClassCount[0][0]

递归构建决策树

#核心程序，创建树 def createTree(dataSet, labels): #取出所有分类标签，yes or no classList = [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 labels subLabels = 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']