ID3决策树Python实现从信息熵到分类预测的5个核心函数解析决策树作为机器学习中最经典的算法之一其ID3实现版本以简洁高效著称。本文将深入剖析ID3算法的Python实现细节聚焦信息熵计算、特征选择、递归建树等核心环节。不同于常规教程我们将从代码层面解构算法本质通过函数级分析揭示决策树的工作机制。1. 信息熵计算决策树的纯度标尺信息熵是ID3算法最核心的概念它量化了数据集的混乱程度。在Python中我们通过calEnt函数实现这一计算from math import log def calEnt(dataSet): sampleCounts len(dataSet) labelCounts {} for sample in dataSet: label sample[-1] labelCounts[label] labelCounts.get(label, 0) 1 Ent 0.0 for key in labelCounts: prob float(labelCounts[key])/sampleCounts Ent - prob * log(prob, 2) return Ent该函数的关键变量说明变量名作用sampleCounts样本总数labelCounts类别计数字典prob类别概率信息熵的计算过程实际上是对概率分布的负对数期望计算。当所有样本属于同一类别时熵值为0表示完全纯净。2. 数据集划分特征空间的切分艺术splitDataSet函数实现了按特征值划分数据集的核心操作def splitDataSet(dataSet, index, value): retDataSet [] for sample in dataSet: if sample[index] value: reducedSample sample[:index] sample[index1:] retDataSet.append(reducedSample) return retDataSet这个函数实现了三个关键步骤遍历数据集寻找匹配特征值的样本去除已使用的特征列避免重复使用返回划分后的子集提示在递归建树过程中每次划分后特征维度会减少这正是删除已使用特征列的原因。3. 特征选择信息增益的最大化策略chooseBestFeatureToSplit函数实现了ID3算法的特征选择策略def chooseBestFeatureToSplit(dataSet): featureCounts len(dataSet[0]) - 1 baseEnt calEnt(dataSet) bestGain 0.0 bestFeature -1 for i in range(featureCounts): featValues {sample[i] for sample in dataSet} newEnt 0.0 for value in featValues: subDataSet splitDataSet(dataSet, i, value) prob len(subDataSet)/float(len(dataSet)) newEnt prob * calEnt(subDataSet) infoGain baseEnt - newEnt if infoGain bestGain: bestGain infoGain bestFeature i return bestFeature信息增益计算的关键公式信息增益 划分前熵 - ∑(子集熵×子集比例)基尼指数CART算法使用的替代指标增益率C4.5算法对ID3的改进4. 多数表决处理边界情况的优雅方案当特征用完但类别仍不纯时majorLabel函数提供了解决方案import operator def majorLabel(labelList): labelCounts {} for label in labelList: labelCounts[label] labelCounts.get(label, 0) 1 sortedLabels sorted(labelCounts.items(), keyoperator.itemgetter(1), reverseTrue) return sortedLabels[0][0]该函数的工作流程统计类别频率按频率降序排序返回最高频类别5. 递归建树决策树的骨架构建createTree函数实现了决策树的递归构建过程def createTree(dataSet, labels): classList [sample[-1] for sample in dataSet] # 终止条件1类别完全相同 if classList.count(classList[0]) len(classList): return classList[0] # 终止条件2无特征可用 if len(dataSet[0]) 1: return majorLabel(classList) # 选择最优特征 bestFeatIndex chooseBestFeatureToSplit(dataSet) bestFeatLabel labels[bestFeatIndex] # 构建树结构 myTree {bestFeatLabel: {}} del(labels[bestFeatIndex]) # 递归构建子树 featValues {sample[bestFeatIndex] for sample in dataSet} for value in featValues: subLabels labels[:] myTree[bestFeatLabel][value] createTree( splitDataSet(dataSet, bestFeatIndex, value), subLabels) return myTree递归终止的两种情形当前节点所有样本属于同一类别无剩余特征可供划分6. 分类预测决策树的应用实践完成树构建后我们通过classify函数实现预测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预测过程遵循树结构的递归查询获取当前节点特征根据测试数据特征值选择分支递归查询直到叶节点7. 实战演示西瓜数据集的完整应用让我们用经典的西瓜数据集演示完整流程# 创建数据集 def createDataSet(): dataSet [ [青绿,蜷缩,浊响,清晰,凹陷,硬滑,好瓜], [乌黑,蜷缩,沉闷,清晰,凹陷,硬滑,好瓜], # ...更多数据... ] labels [色泽,根蒂,敲声,纹理,脐部,触感] return dataSet, labels # 完整流程 dataSet, labels createDataSet() tree createTree(dataSet, labels[:]) print(classify(tree, labels, [青绿,蜷缩,浊响,清晰,凹陷,硬滑]))决策树的优势在可视化后尤为明显。通过以下方法可以绘制树形结构import matplotlib.pyplot as plt decisionNode dict(boxstylesawtooth, fc0.8) leafNode dict(boxstyleround4, fc0.8) def plotNode(nodeTxt, centerPt, parentPt, nodeType): createPlot.ax1.annotate(nodeTxt, xyparentPt, xycoordsaxes fraction, xytextcenterPt, textcoordsaxes fraction, vacenter, hacenter, bboxnodeType, arrowpropsarrow_args)在实际项目中ID3算法虽然简单直观但也有其局限性。它倾向于选择取值较多的特征且无法处理连续值特征。这些缺陷在后来的C4.5和CART算法中得到了改进。理解ID3的底层实现为我们学习更复杂的树算法奠定了坚实基础。