建站之星怎么安装,wordpress企业主题,wordpress是免费的吗,网站备案拍照幕布一、背景与来源
决策树#xff08;Decision Tree#xff09;是一种常见的机器学习算法#xff0c;主要用于分类和回归问题。其概念来源于统计学和决策论#xff0c;能够直观地模拟人类的决策过程。最早的决策树算法之一是 1963 年由 Hunt 等人提出的#xff0c;该算法逐渐…一、背景与来源
决策树Decision Tree是一种常见的机器学习算法主要用于分类和回归问题。其概念来源于统计学和决策论能够直观地模拟人类的决策过程。最早的决策树算法之一是 1963 年由 Hunt 等人提出的该算法逐渐发展成为今天的多种改进版本如 ID3、C4.5、CART 等。
决策树的核心思想是通过递归地将数据集划分为多个子集形成树状结构。每个内部节点代表一个特征的决策每个叶子节点则是决策结果分类或回归值。
二、数学原理
决策树的构建主要基于“信息增益”Information Gain或“基尼不纯度”Gini Impurity等指标。其核心思想是逐步选择最佳的特征来划分数据集从而构建出能够最好地分类或回归的树。 信息增益表示某个特征对分类结果的不确定性的减少量公式为 信息增益 熵 ( D ) − ∑ i ∣ D i ∣ ∣ D ∣ ⋅ 熵 ( D i ) \text{信息增益} \text{熵}(D) - \sum_{i} \frac{|D_i|}{|D|} \cdot \text{熵}(D_i) 信息增益熵(D)−i∑∣D∣∣Di∣⋅熵(Di) 其中熵Entropy是衡量数据集混乱程度的指标定义为 熵 ( D ) − ∑ i 1 n p i log 2 ( p i ) \text{熵}(D) - \sum_{i1}^n p_i \log_2(p_i) 熵(D)−i1∑npilog2(pi) p i p_i pi 表示类别 i i i 的概率。 基尼不纯度基尼不纯度用于衡量一个数据集在某特征下的不纯度定义为 G ( D ) 1 − ∑ i 1 n p i 2 G(D) 1 - \sum_{i1}^{n} p_i^2 G(D)1−i1∑npi2 p i p_i pi 仍表示类别 i i i 的概率。基尼不纯度越低数据集越“纯”。
三、 决策树的构建流程
决策树的构建过程可以分为四个主要步骤按照递归的方式生成树的结构直到满足终止条件。构建决策树的核心是基于数据集的特征逐步选择最优特征来进行数据的划分从而产生不同的子集直至满足某个停止条件。
1. 选择最优特征
首先决策树通过选择具有最高信息增益或最小基尼不纯度的特征来划分数据。信息增益越大表示该特征越能有效减少不确定性从而更好地划分数据。
2. 划分数据集
选择一个特征后决策树会根据该特征的不同取值将数据集分成不同的子集。对于每一个子集递归重复选择最优特征来划分数据。
3. 递归生成子树
在每一次划分后决策树会对子集递归地继续进行相同的过程直到满足某些停止条件为止
终止条件 1当前节点的样本都属于同一个类别。此时不再需要进一步划分。终止条件 2属性集合为空或样本在所有属性上取值都相同。此时无法继续划分将此节点设置为叶子节点类别为当前子集中样本最多的类别。终止条件 3样本集为空。此时用父节点中最多的类别作为预测值。
4. 剪枝可选
为了防止决策树过拟合有时需要进行剪枝操作。剪枝的过程是去除不必要的分支保留重要的决策节点从而提高模型的泛化能力。
剪枝的原因
决策树是一种贪心算法倾向于不断细化树的每个分支直到所有数据都被分开。尽管这种方法能够在训练集上取得较好的准确率但它也容易导致模型过度复杂从而难以在新的数据上做出准确的预测。这就是过拟合现象。
为了解决这个问题剪枝通过去除那些对整体预测贡献较小的分支来简化决策树从而提升模型在新数据上的表现。
剪枝的两种方式
剪枝可以分为两种类型预剪枝和后剪枝。
(1) 预剪枝Pre-pruning
预剪枝是在构建决策树的过程中进行剪枝。具体做法是在划分节点时提前判断是否需要继续分裂。只有当进一步的分裂能够显著提升模型性能时才会进行划分否则将终止划分。这种方法可以减少树的高度防止生成过于复杂的决策树。
预剪枝的判断标准 信息增益阈值如果节点划分带来的信息增益低于某个设定的阈值则停止划分。样本数量当某个节点中的样本数少于某个设定的最小样本数时停止进一步划分。树的深度限制树的最大深度防止树过深导致过拟合。
优点预剪枝可以有效减少训练时间因为它避免了生成过于复杂的树。 缺点预剪枝有时会过早停止分裂导致模型的表现不如预期。
(2) 后剪枝Post-pruning
后剪枝是在生成完整的决策树之后再进行剪枝。该方法首先构建出一棵完整的决策树然后从底部开始回溯判断是否需要将某些子树替换为叶节点从而简化模型。
后剪枝的过程 从树的叶节点开始回溯计算每个非叶节点的误差率。如果将一个子树替换为叶节点后的误差率降低或变化不大则进行剪枝。重复这一过程直到不能进一步剪枝。
优点后剪枝在生成了完全拟合数据的决策树后再进行简化因此能够避免预剪枝过早停止分裂的问题。 缺点由于要先构建出一棵完整的决策树后剪枝的计算成本较高。
剪枝的具体方法
剪枝的目的是减少不必要的分支通常有几种常见的剪枝技术
(1) 基于误差的剪枝
在这种方法中使用 交叉验证 或独立的验证集来评估决策树中每个子树的表现。
具体来说剪枝的过程是先考虑将一个子树替换为叶节点计算这种简化后的误差。如果这个替换操作不会显著增加决策树在验证集上的预测误差那么就进行剪枝操作否则保留子树。
这种方法的优势在于它通过 独立数据集 的验证确保剪枝不会过度简化模型。
(2) 最小误差剪枝Minimal Error Pruning
最小误差剪枝的核心思想是对比子树和替换为叶节点后的误差率。如果将某个子树替换为叶节点能够减少整体误差率那么这个子树就可以被剪掉。
误差的衡量标准可以使用均方误差MSE或其他相关的损失函数。这种剪枝方法注重减少每一步操作的误差以提高模型的性能。
(3) 代价复杂度剪枝Cost Complexity Pruning
代价复杂度剪枝是CART算法中常用的一种剪枝方法。它通过引入一个代价函数来平衡决策树的复杂度与其对数据拟合的效果。代价复杂度剪枝的目标是最小化以下函数 R α ( T ) R ( T ) α × ∣ T ∣ R_{\alpha}(T) R(T) \alpha \times |T| Rα(T)R(T)α×∣T∣ 其中 R ( T ) R(T) R(T) 是子树 T T T 在训练集上的误差 ∣ T ∣ |T| ∣T∣ 是树的叶节点数即树的复杂度 α \alpha α 是惩罚参数用于控制误差和复杂度之间的平衡。
通过调节参数 α \alpha α可以找到最佳的剪枝程度即在保证模型预测能力的前提下尽可能地减少树的复杂度。较大的 α \alpha α 会倾向于生成较小的树而较小的 α \alpha α 则允许生成更复杂的树。
这种方法有效防止了决策树在训练集上过拟合同时保留了重要的结构信息。 实例分析使用 ID3 算法构建决策树
我们将通过一个实际的例子来解释决策树的构建过程。
数据集
假设我们有如下数据集包含了天气相关的信息以及是否适合进行户外活动的判断“Yes” or “No”。数据集有以下 4 个特征
天气Outlook有 3 种取值Sunny、Overcast、Rainy温度Temperature有 3 种取值Hot、Mild、Cool湿度Humidity有 2 种取值High、Normal风速Wind有 2 种取值Weak、Strong
数据表
IndexOutlookTemperatureHumidityWindPlay Tennis1SunnyHotHighWeakNo2SunnyHotHighStrongNo3OvercastHotHighWeakYes4RainyMildHighWeakYes5RainyCoolNormalWeakYes6RainyCoolNormalStrongNo7OvercastCoolNormalStrongYes8SunnyMildHighWeakNo9SunnyCoolNormalWeakYes10RainyMildNormalWeakYes11SunnyMildNormalStrongYes12OvercastMildHighStrongYes13OvercastHotNormalWeakYes14RainyMildHighStrongNo
目标是根据特征预测是否适合 “Play Tennis”即 “Yes” 或 “No”。 决策树构建步骤
Step 1计算熵Entropy
首先我们需要计算 整个数据集 的熵。熵是衡量数据集混乱程度的一个指标。它的公式如下 熵 ( D ) − ∑ i 1 n p i log 2 ( p i ) \text{熵}(D) -\sum_{i1}^n p_i \log_2(p_i) 熵(D)−i1∑npilog2(pi)
其中 p i p_i pi 表示数据集中每一类的概率。
在这个例子中数据集中有 9 个 “Yes” 和 5 个 “No”因此 p Yes 9 14 , p No 5 14 p_{\text{Yes}} \frac{9}{14}, \quad p_{\text{No}} \frac{5}{14} pYes149,pNo145
熵 H ( D ) H(D) H(D) 为 H ( D ) − ( 9 14 log 2 9 14 5 14 log 2 5 14 ) − ( 0.643 × log 2 0.643 0.357 × log 2 0.357 ) 0.940 H(D) -\left( \frac{9}{14} \log_2 \frac{9}{14} \frac{5}{14} \log_2 \frac{5}{14} \right) - \left( 0.643 \times \log_2 0.643 0.357 \times \log_2 0.357 \right) 0.940 H(D)−(149log2149145log2145)−(0.643×log20.6430.357×log20.357)0.940
Step 2计算每个特征的信息增益
1. 天气Outlook
有三种可能的取值Sunny、Overcast、Rainy。我们将根据这些取值划分数据集然后计算每个子集的熵并求出信息增益。 Sunny 类别3 个 “No”2 个 “Yes”熵 H ( S u n n y ) − ( 3 5 log 2 3 5 2 5 log 2 2 5 ) 0.971 H(Sunny) -\left( \frac{3}{5} \log_2 \frac{3}{5} \frac{2}{5} \log_2 \frac{2}{5} \right) 0.971 H(Sunny)−(53log25352log252)0.971 Overcast 类别4 个全是 “Yes”熵 H ( O v e r c a s t ) 0 纯数据集 H(Overcast) 0 \quad 纯数据集 H(Overcast)0纯数据集 Rainy 类别3 个 “Yes”2 个 “No”熵 H ( R a i n y ) − ( 3 5 log 2 3 5 2 5 log 2 2 5 ) 0.971 H(Rainy) -\left( \frac{3}{5} \log_2 \frac{3}{5} \frac{2}{5} \log_2 \frac{2}{5} \right) 0.971 H(Rainy)−(53log25352log252)0.971
加权平均熵 H ( Outlook ) 5 14 × 0.971 4 14 × 0 5 14 × 0.971 0.693 H(\text{Outlook}) \frac{5}{14} \times 0.971 \frac{4}{14} \times 0 \frac{5}{14} \times 0.971 0.693 H(Outlook)145×0.971144×0145×0.9710.693
信息增益 信息增益 ( O u t l o o k ) H ( D ) − H ( O u t l o o k ) 0.940 − 0.693 0.247 \text{信息增益}(Outlook) H(D) - H(Outlook) 0.940 - 0.693 0.247 信息增益(Outlook)H(D)−H(Outlook)0.940−0.6930.247
2. 温度Temperature
取值有Hot、Mild、Cool。我们对每个子集计算熵。 Hot 类别2 个 “No”1 个 “Yes”熵 H ( H o t ) − ( 2 3 log 2 2 3 1 3 log 2 1 3 ) 0.918 H(Hot) -\left( \frac{2}{3} \log_2 \frac{2}{3} \frac{1}{3} \log_2 \frac{1}{3} \right) 0.918 H(Hot)−(32log23231log231)0.918 Mild 类别2 个 “No”4 个 “Yes”熵 H ( M i l d ) − ( 2 6 log 2 2 6 4 6 log 2 4 6 ) 0.918 H(Mild) -\left( \frac{2}{6} \log_2 \frac{2}{6} \frac{4}{6} \log_2 \frac{4}{6} \right) 0.918 H(Mild)−(62log26264log264)0.918 Cool 类别1 个 “No”3 个 “Yes”熵 H ( C o o l ) − ( 1 4 log 2 1 4 3 4 log 2 3 4 ) 0.811 H(Cool) -\left( \frac{1}{4} \log_2 \frac{1}{4} \frac{3}{4} \log_2 \frac{3}{4} \right) 0.811 H(Cool)−(41log24143log243)0.811
加权平均熵 H ( Temperature ) 3 14 × 0.918 6 14 × 0.918 4 14 × 0.811 0.889 H(\text{Temperature}) \frac{3}{14} \times 0.918 \frac{6}{14} \times 0.918 \frac{4}{14} \times 0.811 0.889 H(Temperature)143×0.918146×0.918144×0.8110.889
信息增益 信息增益 ( Temperature ) 0.940 − 0.889 0.051 \text{信息增益}(\text{Temperature}) 0.940 - 0.889 0.051 信息增益(Temperature)0.940−0.8890.051
3. 湿度Humidity
取值有High、Normal。
High 类别4 个 “No”2 个 “Yes”熵$$ H(High) -\left( \frac{4}{6} \log_2 \frac{4}{6
} \frac{2}{6} \log_2 \frac{2}{6} \right) 0.918 $$
Normal 类别1 个 “No”6 个 “Yes”熵 H ( N o r m a l ) − ( 1 7 log 2 1 7 6 7 log 2 6 7 ) 0.592 H(Normal) -\left( \frac{1}{7} \log_2 \frac{1}{7} \frac{6}{7} \log_2 \frac{6}{7} \right) 0.592 H(Normal)−(71log27176log276)0.592
加权平均熵 H ( Humidity ) 6 14 × 0.918 7 14 × 0.592 0.788 H(\text{Humidity}) \frac{6}{14} \times 0.918 \frac{7}{14} \times 0.592 0.788 H(Humidity)146×0.918147×0.5920.788
信息增益 信息增益 ( Humidity ) 0.940 − 0.788 0.152 \text{信息增益}(\text{Humidity}) 0.940 - 0.788 0.152 信息增益(Humidity)0.940−0.7880.152
4. 风速Wind
取值有Weak、Strong。 Weak 类别2 个 “No”6 个 “Yes”熵 H ( W e a k ) − ( 2 8 log 2 2 8 6 8 log 2 6 8 ) 0.811 H(Weak) -\left( \frac{2}{8} \log_2 \frac{2}{8} \frac{6}{8} \log_2 \frac{6}{8} \right) 0.811 H(Weak)−(82log28286log286)0.811 Strong 类别3 个 “No”3 个 “Yes”熵 H ( S t r o n g ) − ( 3 6 log 2 3 6 3 6 log 2 3 6 ) 1.000 H(Strong) -\left( \frac{3}{6} \log_2 \frac{3}{6} \frac{3}{6} \log_2 \frac{3}{6} \right) 1.000 H(Strong)−(63log26363log263)1.000
加权平均熵 H ( Wind ) 8 14 × 0.811 6 14 × 1.000 0.892 H(\text{Wind}) \frac{8}{14} \times 0.811 \frac{6}{14} \times 1.000 0.892 H(Wind)148×0.811146×1.0000.892
信息增益 信息增益 ( Wind ) 0.940 − 0.892 0.048 \text{信息增益}(\text{Wind}) 0.940 - 0.892 0.048 信息增益(Wind)0.940−0.8920.048
Step 3选择最优特征
通过计算每个特征的信息增益我们得到
Outlook 的信息增益0.247Temperature 的信息增益0.051Humidity 的信息增益0.152Wind 的信息增益0.048
最优特征是 Outlook因为它具有最高的信息增益0.247。因此我们将 Outlook 作为根节点进行划分。
第一轮划分根节点Outlook
我们已经根据 Outlook 将数据集分为三个子集 Sunny 子集 IndexOutlookTemperatureHumidityWindPlay Tennis1SunnyHotHighWeakNo2SunnyHotHighStrongNo8SunnyMildHighWeakNo9SunnyCoolNormalWeakYes11SunnyMildNormalStrongYes Overcast 子集 IndexOutlookTemperatureHumidityWindPlay Tennis3OvercastHotHighWeakYes7OvercastCoolNormalStrongYes12OvercastMildHighStrongYes13OvercastHotNormalWeakYes Rainy 子集 IndexOutlookTemperatureHumidityWindPlay Tennis4RainyMildHighWeakYes5RainyCoolNormalWeakYes6RainyCoolNormalStrongNo10RainyMildNormalWeakYes14RainyMildHighStrongNo
对 Sunny 子集递归划分
对于 Sunny 子集我们需要重新计算剩余特征Temperature、Humidity、Wind的信息增益选择最优特征进行下一步划分。
Sunny 子集熵 类别3 个 “No”2 个 “Yes”总熵 H ( S u n n y ) − ( 3 5 log 2 3 5 2 5 log 2 2 5 ) 0.971 H(Sunny) -\left( \frac{3}{5} \log_2 \frac{3}{5} \frac{2}{5} \log_2 \frac{2}{5} \right) 0.971 H(Sunny)−(53log25352log252)0.971
1. 计算 Temperature 的信息增益
在 Sunny 子集中Temperature 有三个取值Hot、Mild、Cool。
Hot2 个 “No” 熵 H ( H o t ) − ( 2 2 log 2 2 2 ) 0 H(Hot) -\left( \frac{2}{2} \log_2 \frac{2}{2} \right) 0 H(Hot)−(22log222)0 Mild1 个 “No”1 个 “Yes” 熵 H ( M i l d ) − ( 1 2 log 2 1 2 1 2 log 2 1 2 ) 1 H(Mild) -\left( \frac{1}{2} \log_2 \frac{1}{2} \frac{1}{2} \log_2 \frac{1}{2} \right) 1 H(Mild)−(21log22121log221)1 Cool1 个 “Yes” 熵 H ( C o o l ) − ( 1 1 log 2 1 1 ) 0 H(Cool) -\left( \frac{1}{1} \log_2 \frac{1}{1} \right) 0 H(Cool)−(11log211)0
加权平均熵 H ( Temperature ) 2 5 × 0 2 5 × 1 1 5 × 0 0.4 H(\text{Temperature}) \frac{2}{5} \times 0 \frac{2}{5} \times 1 \frac{1}{5} \times 0 0.4 H(Temperature)52×052×151×00.4
信息增益 信息增益 ( Temperature ) 0.971 − 0.4 0.571 \text{信息增益}(\text{Temperature}) 0.971 - 0.4 0.571 信息增益(Temperature)0.971−0.40.571
2. 计算 Humidity 的信息增益
Humidity 有两个取值High 和 Normal。
High3 个 “No” 熵 H ( H i g h ) − ( 3 3 log 2 3 3 ) 0 H(High) -\left( \frac{3}{3} \log_2 \frac{3}{3} \right) 0 H(High)−(33log233)0 Normal2 个 “Yes” 熵 H ( N o r m a l ) − ( 2 2 log 2 2 2 ) 0 H(Normal) -\left( \frac{2}{2} \log_2 \frac{2}{2} \right) 0 H(Normal)−(22log222)0
加权平均熵 H ( Humidity ) 3 5 × 0 2 5 × 0 0 H(\text{Humidity}) \frac{3}{5} \times 0 \frac{2}{5} \times 0 0 H(Humidity)53×052×00
信息增益 信息增益 ( Humidity ) 0.971 − 0 0.971 \text{信息增益}(\text{Humidity}) 0.971 - 0 0.971 信息增益(Humidity)0.971−00.971
3. 计算 Wind 的信息增益
Wind 有两个取值Weak 和 Strong。
Weak2 个 “No”1 个 “Yes” 熵 H ( W e a k ) − ( 2 3 log 2 2 3 1 3 log 2 1 3 ) 0.918 H(Weak) -\left( \frac{2}{3} \log_2 \frac{2}{3} \frac{1}{3} \log_2 \frac{1}{3} \right) 0.918 H(Weak)−(32log23231log231)0.918 Strong1 个 “No”1 个 “Yes” 熵 H ( S t r o n g ) − ( 1 2 log 2 1 2 1 2 log 2 1 2 ) 1 H(Strong) -\left( \frac{1}{2} \log_2 \frac{1}{2} \frac{1}{2} \log_2 \frac{1}{2} \right) 1 H(Strong)−(21log22121log221)1
加权平均熵 H ( Wind ) 3 5 × 0.918 2 5 × 1 0.951 H(\text{Wind}) \frac{3}{5} \times 0.918 \frac{2}{5} \times 1 0.951 H(Wind)53×0.91852×10.951
信息增益 信息增益 ( Wind ) 0.971 − 0.951 0.020 \text{信息增益}(\text{Wind}) 0.971 - 0.951 0.020 信息增益(Wind)0.971−0.9510.020
选择最优特征
通过比较 Sunny 子集中各特征的信息增益Humidity 拥有最高的信息增益0.971因此选择 Humidity 作为划分标准。将 Sunny 子集按照 Humidity 划分成两个子集。
High 子集全部为 “No”直接作为叶节点标记为 “No”。Normal 子集全部为 “Yes”直接作为叶节点标记为 “Yes”。
此时Sunny 子集的递归过程结束节点结构如下
Outlook Sunny- Humidity High: No- Humidity Normal: Yes对 Overcast 子集递归划分
对于 Overcast 子集
IndexOutlookTemperatureHumidityWindPlay Tennis3OvercastHotHighWeakYes7OvercastCoolNormalStrongYes12OvercastMildHighStrongYes13OvercastHotNormalWeakYes
该子集中全部样本类别为 “Yes”因此直接返回 “Yes” 作为该节点的叶节点。
对 Rainy 子集递归划分
对于 Rainy 子集类似于对 Sunny 子集的划分依次计算剩余特征的熵和信息增益选择最优特征进行划分。最终的结构可能类似如下
Outlook Rainy- Wind Weak: Yes- Wind Strong: No递归终止条件
递归过程需要满足一定的条件来停止继续划分。当满足以下任何一个条件时递归过程会停止当前节点会被标记为叶节点。
终止条件 1同一类别
如果某个子集中的所有样本都属于同一个类别则无需继续划分该节点直接标记为该类别的叶节点。例如所有样本的类别都是 “Yes”则该节点为 “Yes” 类别的叶节点。
终止条件 2属性为空或样本在所有属性上的取值相同
如果子集中的样本在所有剩余属性上的取值相同无法进一步划分。此时无法区分不同类别直接返回该节点中多数类别作为该节点的预测类别。
举例说明
假设划分后的一个子集中所有样本在 Temperature、Humidity 和 Wind 属性上取值完全相同但类别不同。这种情况下因为没有其他属性可以进一步区分样本返回多数类别作为预测结果。
终止条件 3样本集合为空
如果划分过程中某一分支没有样本即子集为空则无法继续划分。此时应返回父节点中的多数类别作为该分支的预测结果
最终决策树结构
根据递归划分过程最终构建的决策树结构如下
Outlook
├── Sunny
│ ├── Humidity High: No
│ └── Humidity Normal: Yes
├── Overcast: Yes
└── Rainy├── Wind Weak: Yes└── Wind Strong: No根节点Outlook决策树首先根据 Outlook天气这个特征将数据集分成三个子集 如果 Outlook Sunny则进一步根据 Humidity 划分 Humidity High 时预测为 “No”。Humidity Normal 时预测为 “Yes”。 如果 Outlook Overcast预测为 “Yes”。因为所有样本都是 “Yes”。如果 Outlook Rainy则进一步根据 Wind 划分 Wind Weak 时预测为 “Yes”。Wind Strong 时预测为 “No”。
总结
通过递归划分特征决策树将复杂的分类问题逐步分解为简单的条件判断。我们使用信息增益选择最优特征直到满足停止条件。最终生成的决策树结构直观、易解释能够根据特征的不同取值来预测是否适合打网球。
决策树的构建过程清晰体现了数据集划分的逐步细化通过特征选择、子集划分与递归处理生成了一棵结构化的树来进行分类任务。这一模型不仅简洁直观也为实际应用中的分类问题提供了强有力的支持。
