ID3决策树Python实现：从信息熵到分类预测的5个核心函数解析

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

该函数的关键变量说明：

信息熵的计算过程实际上是对概率分布的负对数期望计算。当所有样本属于同一类别时，熵值为0，表示完全纯净。

2. 数据集划分：特征空间的切分艺术

splitDataSet函数实现了按特征值划分数据集的核心操作：

def splitDataSet(dataSet, index, value): retDataSet = [] for sample in dataSet: if sample[index] == value: reducedSample = sample[:index] + sample[index+1:] retDataSet.append(reducedSample) return retDataSet

这个函数实现了三个关键步骤：

1. 遍历数据集寻找匹配特征值的样本
2. 去除已使用的特征列（避免重复使用）
3. 返回划分后的子集

提示：在递归建树过程中，每次划分后特征维度会减少，这正是删除已使用特征列的原因。

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(), key=operator.itemgetter(1), reverse=True) return sortedLabels[0][0]

该函数的工作流程：

1. 统计类别频率
2. 按频率降序排序
3. 返回最高频类别

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

递归终止的两种情形：

1. 当前节点所有样本属于同一类别
2. 无剩余特征可供划分

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

预测过程遵循树结构的递归查询：

1. 获取当前节点特征
2. 根据测试数据特征值选择分支
3. 递归查询直到叶节点

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(boxstyle="sawtooth", fc="0.8") leafNode = dict(boxstyle="round4", fc="0.8") 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)

在实际项目中，ID3算法虽然简单直观，但也有其局限性。它倾向于选择取值较多的特征，且无法处理连续值特征。这些缺陷在后来的C4.5和CART算法中得到了改进。理解ID3的底层实现，为我们学习更复杂的树算法奠定了坚实基础。