谷歌笔记本（可选）
from google.colab import drive drive.mount("/content/drive")
output
Mounted at /content/drive
编写算法：决策树
from math import log import operator def calcShannonEnt(dataSet): numEntries = len(dataSet) labelCounts = {} for featVec in dataSet: currentLabel = featVec[-1] if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0 labelCounts[currentLabel] += 1 shannonEnt = 0 for key in labelCounts: prob = float(labelCounts[key]) / numEntries shannonEnt -= prob * log(prob, 2) return shannonEnt
这段代码是用于计算给定数据集的香农熵（Shannon Entropy）的Python实现。香农熵在信息论中是一个度量不确定性或信息混乱程度的重要概念，在机器学习领域，特别是在决策树算法中，用于评估特征对于划分数据集纯度的贡献。
1. `calcShannonEnt`函数接收一个名为dataSet的数据集作为输入，该数据集通常是由特征向量构成的列表，每个特征向量最后一个元素为其对应的类别标签。
2. 首先统计数据集中样本的数量：`numEntries = len(dataSet)`。
3. 初始化一个字典`labelCounts`，用于存储各类别标签出现的次数。通过遍历整个数据集，对每一个特征向量（featVec），提取其类别标签（currentLabel），并将其计数加到字典对应键值上。
4. 计算香农熵：初始化`shannonEnt`为0，然后遍历`labelCounts`字典，对于每个类别标签key，计算其概率（通过其出现次数除以总样本数得到），然后用公式 `- prob * log(prob, 2)` 计算其熵值，并累加到`shannonEnt`上。这里的log是以2为底的对数，因为熵的单位通常是比特（bits）。
5. 最后返回计算得出的香农熵值`shannonEnt`。
总结：这个函数的主要目的是衡量给定数据集中各类别的不确定性或分布均匀性，熵值越大表示不确定性越高，越需要进行划分以提高模型的纯度。
def splitDataSet(dataSet, axis, value): retDataSet = [] for featVec in dataSet: if featVec[axis] == value: reducedFeatVec = featVec[:axis] reducedFeatVec.extend(featVec[axis+1:]) retDataSet.append(reducedFeatVec) return retDataSet
def chooseBestFeatureToSplit(dataSet): numFeatures = len(dataSet[0]) - 1 # 2 baseEntropy = calcShannonEnt(dataSet) # 0.9709505944546686 bestInfoGain = 0 bestFeature = -1 for i in range(numFeatures): featList = [example[i] 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
这段代码是用于选择数据集中最佳特征进行划分的函数，通常在决策树构建过程中使用。其主要目的是通过计算信息增益（Information Gain）来确定最优分割特征。
1. numFeatures 计算特征的数量，等于数据集中每个样本向量元素的个数减1（因为最后一个元素通常是类别标签）。
2. 初始化基本熵（baseEntropy），通过调用之前定义的 calcShannonEnt(dataSet) 函数计算整个数据集的香农熵。
3. 初始化最佳信息增益（bestInfoGain）为0，以及最佳特征索引（bestFeature）为-1，分别用于存储找到的最大信息增益和对应的特征编号。
4. 遍历所有特征（i从0到numFeatures-1）：
a. 通过列表推导式提取出当前特征i的所有取值，存入featList。
b. 将featList中的唯一值转化为一个集合(uniqueVals)，这将作为当前特征可能的划分依据。
c. 对于uniqueVals中的每一个value，利用splitDataSet函数根据特征i和该value划分数据集得到subDataSet。
d. 计算划分后子数据集的概率（prob），即子数据集大小除以原数据集大小。
e. 计算划分后的子数据集的香农熵，并乘以对应概率得到加权平均熵（newEntropy）。
f. 使用公式计算信息增益：infoGain = baseEntropy - newEntropy。
g. 如果当前信息增益大于已记录的最佳信息增益，则更新bestInfoGain和bestFeature。
5. 循环结束后返回最佳特征索引（bestFeature）。这个特征就是当前能带来最大信息增益的特征，用于下一步决策树节点的划分。
def majorityCnt(classList): classCount={} for vote in classList: if vote not in classCount.keys(): classCount[vote] = 0 classCount[vote] += 1 sortedClassCount = sorted(classCount.items(), 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:{}} subLabels = labels[:] del(subLabels[bestFeat]) featValues = [example[bestFeat] for example in dataSet] uniqueVals = set(featValues) for value in uniqueVals: myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels) return myTree
这段代码是用于创建决策树的函数，名为`createTree`。它递归地构建决策树直到满足停止条件。
1. 首先计算数据集classList中最后一个元素（类别标签）的唯一值数量，如果所有样本的类别标签都相同，则说明当前节点下的样本已经足够纯，无需继续划分，直接返回这个唯一的类别标签作为叶子节点的预测结果。
2. 检查是否所有特征已经被用尽（即每个样本只有一个特征），如果是，则返回该节点下出现次数最多的类别标签（通过调用`majorityCnt(classList)`实现）。
3. 使用`chooseBestFeatureToSplit`函数选择最优特征进行划分，并获取其对应的标签名称（bestFeatLabel）。
4. 初始化一个新的字典结构myTree，以表示当前节点以及其子节点。字典的键为最优特征的标签，值为另一个字典，后续将填充各个特征取值对应的子树。
5. 创建一个子标签列表subLabels，它是原标签列表labels的一个副本，然后删除最优特征对应的标签，这样在构建子节点时不会重复考虑此特征。
6. 提取数据集中最优特征的所有取值并转化为一个集合uniqueVals。
7. 遍历uniqueVals中的每一个特征取值value：
a. 调用`splitDataSet(dataSet, bestFeat, value)`对数据集进行划分，得到该特征取值对应的新子数据集。
b. 以最优特征的取值value作为键，递归调用`createTree`生成对应的子树，并将其添加到myTree[bestFeatLabel]中。
8. 当所有子树构造完成后，返回整个决策树结构myTree。整个过程按照信息增益最大原则自顶向下构建决策树，直至达到终止条件。
准备数据：拆分数据集
fr = open('/content/drive/MyDrive/MachineLearning/机器学习/决策树/使用决策树预测隐形眼镜类型/lenses.txt')
lenses = [inst.strip().split('\t') for inst in fr.readlines()] lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate'] lensesTree = createTree(lenses, lensesLabels) lensesTree, lensesLabels
output ({'tearRate': {'normal': {'astigmatic': {'no': {'age': {'presbyopic': {'prescript': {'myope': 'no lenses', 'hyper': 'soft'}}, 'pre': 'soft', 'young': 'soft'}}, 'yes': {'prescript': {'myope': 'hard', 'hyper': {'age': {'presbyopic': 'no lenses', 'pre': 'no lenses', 'young': 'hard'}}}}}}, 'reduced': 'no lenses'}}, ['age', 'prescript', 'astigmatic', 'tearRate'])
测试算法：构造注解树
import matplotlib.pyplot as plt decisionNode = dict(boxstyle="sawtooth", fc="0.8") leafNode = dict(boxstyle="round4", fc="0.8") arrow_args = dict(arrowstyle="<-") def plotNode(nodeTxt, centerPt, parentPt, nodeType): createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction', xytext=centerPt, textcoords='axes fraction', va='center', ha='center', bbox=nodeType, arrowprops=arrow_args)
def getNumLeafs(myTree): numLeafs = 0 firstStr = list(myTree.keys())[0] secondDict = myTree[firstStr] for key in secondDict.keys(): if type(secondDict[key]).__name__ == 'dict': numLeafs += getNumLeafs(secondDict[key]) else: numLeafs += 1 return numLeafs
def getTreeDepth(myTree): maxDepth = 0 firstStr = list(myTree.keys())[0] secondDict = myTree[firstStr] for key in secondDict.keys(): if type(secondDict[key]).__name__=='dict': thisDepth = 1 + getTreeDepth(secondDict[key]) else: thisDepth = 1 if thisDepth > maxDepth: maxDepth = thisDepth return maxDepth
def plotMidText(cntrPt, parentPt, txtString): xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0] yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1] createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)
def plotTree(myTree, parentPt, nodeTxt): numLeafs = getNumLeafs(myTree) depth = getTreeDepth(myTree) firstStr = list(myTree.keys())[0] cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff) plotMidText(cntrPt, parentPt, nodeTxt) plotNode(firstStr, cntrPt, parentPt, decisionNode) secondDict = myTree[firstStr] plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD for key in secondDict.keys(): if type(secondDict[key]).__name__=='dict': plotTree(secondDict[key],cntrPt,str(key)) else: plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode) plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key)) plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD
def createPlot(inTree): fig = plt.figure(1, facecolor='white') fig.clf() axprops = dict(xticks=[], yticks=[]) createPlot.ax1 = plt.subplot(111, frameon=False, **axprops) plotTree.totalW = float(getNumLeafs(inTree)) plotTree.totalD = float(getTreeDepth(inTree)) plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0; plotTree(inTree, (0.5,1.0), '') plt.show()
createPlot(lensesTree)
output
使用算法：预测隐形眼镜类型
def classify(inputTree, featLabels, testVec): firstStr = list(inputTree.keys())[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
classify(lensesTree, lensesLabels, ['pre', 'myope', 'yes', 'normal'])
output
'hard'
