郑州网站制作报价,百度风云榜小说排行榜,流量网站制作,网推一手渠道决策树#xff08;decision tree#xff09;是一种基本的分类与回归方法。本章主要讨论用于分类的决策树。决策树模型呈树形结构#xff0c;在分类问题中#xff0c;表示基于特征对实例进行分类的过程。 以下是关于分类决策树的一些基本概念和特点#xff1a; 树形结构decision tree是一种基本的分类与回归方法。本章主要讨论用于分类的决策树。决策树模型呈树形结构在分类问题中表示基于特征对实例进行分类的过程。 以下是关于分类决策树的一些基本概念和特点 树形结构决策树模型呈现为一种树状结构其中包括根节点、内部节点和叶子节点。每个节点表示一个特征或属性每个边表示一个特征值或属性值的判断条件。从根节点开始通过遵循不同的条件路径最终到达叶子节点叶子节点代表了一个类别标签或回归值。if-then规则决策树可以看作是一组if-then规则的集合每个规则表示一个从根节点到叶子节点的路径其中包括特征条件和对应的类别标签。当新样本进入决策树时它会根据特征的条件依次遵循路径最终确定样本所属的类别。条件概率分布决策树也可以看作是定义在特征空间与类别空间上的条件概率分布。每个内部节点表示一个特征条件每个叶子节点表示一个类别并且沿着路径的条件概率决定了样本被分类到不同的类别。学习过程决策树的学习过程通常包括以下步骤 特征选择选择最佳的特征作为根节点以最大化分类效果。分裂节点将数据集根据选定的特征进行分割生成子节点。递归学习对每个子节点递归应用上述步骤直到达到停止条件例如达到最大深度、样本数量小于阈值等。剪枝可选在生成决策树后可以应用剪枝算法来减小过拟合风险。 优点决策树具有易于理解和解释的特点可以生成清晰的分类规则。它们适用于离散和连续特征对缺失值具有一定的容忍性且在某些情况下表现良好。缺点决策树容易过拟合训练数据因此需要进行剪枝等正则化方法。它们可能在处理复杂问题时产生过多的规则导致模型过于复杂。此外决策树对数据中的噪声和不稳定性敏感。 决策树是一种强大的机器学习工具适用于各种分类和回归任务。通过合适的参数调整和正则化方法可以改善其性能并减小过拟合的风险。在实际应用中决策树通常与集成学习方法如随机森林和梯度提升树相结合以进一步提高模型的性能。 它可以认为是if-then规则的集合也可以认为是定义在特征空间与类空间上的条件概率分布。 特征空间Feature Space和类空间Class Space是机器学习中常用的两个概念它们用于描述模型和数据的属性。 特征空间Feature Space 特征空间是指用来描述样本数据点的属性或特征的空间。每个样本可以在特征空间中表示为一个向量其中每个维度对应一个特征。在特征空间中每个维度表示一个特征而每个样本由这些特征的值组成。例如在文本分类任务中特征空间可能包括词汇表中的单词每个维度表示一个单词在文本中的出现次数或TF-IDF值。特征空间的维度取决于数据集中的特征数量可以是高维的包含许多特征或低维的包含较少的特征。 类空间Class Space 类空间是指用来描述样本所属类别或标签的空间。每个样本都被分配到类空间中的一个类别。在分类问题中类空间包括所有可能的类别或标签。每个样本在类空间中被分配到一个类别以表示其所属类别。类空间通常是离散的每个类别由一个唯一的标识符表示。例如二元分类问题中的类空间可能包括 “正类” 和 “负类” 两个类别。 在机器学习任务中特征空间和类空间之间的映射关系是模型的关键。机器学习模型的目标是学习如何从特征空间中的数据映射到类空间中的类别。决策树、支持向量机、神经网络等各种模型都是用来建立特征空间到类空间的映射关系并用于分类或回归任务。 总之特征空间描述了数据的特征属性而类空间描述了数据的类别或标签它们在机器学习中是重要的概念用于建模和解决各种问题。 其主要优点1.模型具有可读性2.分类速度快
阶段操作学习时利用训练数据根据损失函数最小化的原则建立决策树模型预测时对新的数据利用决策树模型进行分类
决策树学习通常包括3个步骤特征选择-决策树的生成-决策树的修剪
5.1决策树模型与学习
5.1.1决策树模型
定义5.1(决策树)分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directed edge)组成。结点有两种类型:内部结点(internalnode)和叶结点(leaf node)。内部结点表示一个特征或属性叶结点表示一个类。
5.1.2决策树与if-then规则
5.1.3决策树与条件概率分布
5.1.4决策树学习
决策树学习用损失函数表示这一目标。如下所述决策树学习的损失函数通常是正则化的极大似然函数。决策树学习的策略是以损失函数为目标函数的最小化。 当损失函数确定后学习问题就变为在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优决策树是NP完全问题所以现实中决策树学习算法通常采用启发式方法近似求解这一最优化问题这样得到的决策树是次最优(sub-optimal)的。 从所有可能的决策树中选择最优决策树是一个非常复杂的问题它属于NP完全问题这意味着在现实世界中找到确切的最优解可能需要大量时间甚至是不可行的。为了解决这个问题决策树学习算法通常采用一种称为启发式方法的策略。这就像在迷宫中找到出口你可能不会尝试每个可能的路径而是根据一些规则或经验选择下一步希望最终找到出口。在决策树学习中这些规则和经验可以是分裂节点的标准、剪枝策略、节点的排序等。使用这些启发式方法我们可以获得一个次最优sub-optimal的决策树这意味着它可能不是全局最优解但在实践中性能仍然很好。次最优的决策树通常能够很好地拟合训练数据并且具有较好的泛化性能可以用于对未见数据的分类或回归。 简而言之决策树学习算法面临一个非常复杂的优化问题通常无法找到全局最优解。因此它使用一些经验法则和启发式方法来近似求解这个问题最终得到一个次最优的决策树以在实际应用中表现良好。这类似于在实际问题中使用经验和直觉来做出决策而不是尝试每种可能的选择。 决策树学习算法包含特征选择、决策树的生成与决策树的剪枝过程。由于决策树表示一个条件概率分布所以深浅不同的决策树对应着不同复杂度的概率模型。决策树的生成对应于模型的局部选择决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优相对地决策树的剪枝则考虑全局最优。
决策学习常用的算法有ID3、C4.5与CART下面结合这些算法分别叙述决策树学习的特征选择、决策树的生成和剪枝过程。
5.2特征选择
5.2.1特征选择问题
通常特征选择的准则是信息增益或信息增益比
5.2.2信息增益
为了便于说明先给出熵与条件熵的定义 在信息论与概率统计中熵entropy是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量其概率分布为 P ( X x i ) p i , i 1 , 2 , . . . , n P(Xx_i)p_i,i1,2,...,n P(Xxi)pi,i1,2,...,n 则随机变量X的熵定义为若 p i 0 p_i0 pi0则定义 0 l o g 0 0 0log00 0log00 H ( X ) − ∑ i 1 n p i l o g p i H(X)-\sum\limits_{i1}^n p_i log p_i H(X)−i1∑npilogpi 由于熵只依赖于X的分布而与X的取值无关所以也可将X的熵记作H§即 H ( p ) − ∑ i 1 n p i l o g p i H(p)-\sum\limits_{i1}^n p_i log p_i H(p)−i1∑npilogpi 熵越大随机变量的不确定性就越大。从定义可验证 0 ≤ H ( p ) ≤ l o g n 0≤H(p)≤log n 0≤H(p)≤logn 它是信息熵的基本性质之一。这是信息熵 H ( p ) H(p) H(p) 的性质不需要再次证明。 设有随机变量 ( X , Y ) (X,Y) (X,Y)其联合概率分布为 P ( X x i , Y y j ) p i j , i 1 , 2 , . . . , n ; j 1 , 2 , . . . , m P(Xx_i,Yy_j)p_{ij},i1,2,...,n;j1,2,...,m P(Xxi,Yyj)pij,i1,2,...,n;j1,2,...,m 条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵conditional entropyH(Y|X)定义为X给定条件下Y的条件概率分布的熵对X的数学期望 H ( Y ∣ X ) ∑ i 1 n p i H ( Y ∣ X x i ) H(Y|X)\sum\limits_{i1}^n p_iH(Y|Xx_i) H(Y∣X)i1∑npiH(Y∣Xxi) 这里 p i P ( X x i ) , i 1 , 2 , . . . , n p_iP(Xx_i),i1,2,...,n piP(Xxi),i1,2,...,n 让我们通过一个简单的例子来计算条件熵。 假设我们有两个随机变量X和Y它们的联合分布如下 X/YY1Y2X10.20.1X20.30.4X30.10.2 首先我们需要计算条件概率分布 P ( Y ∣ X ) P(Y|X) P(Y∣X)然后根据这个分布计算条件熵 H ( Y ∣ X ) H(Y|X) H(Y∣X)。让我们按照步骤进行计算 步骤 1计算边际概率分布 P ( X ) P(X) P(X) 首先我们计算随机变量X的边际概率分布 P ( X ) P(X) P(X)即X取每个可能值的概率。 P ( X 1 ) 0.2 0.1 0.1 0.4 P(X1) 0.2 0.1 0.1 0.4 P(X1)0.20.10.10.4 P ( X 2 ) 0.3 0.4 0.2 0.9 P(X2) 0.3 0.4 0.2 0.9 P(X2)0.30.40.20.9 P ( X 3 ) 0.1 0.2 0.3 P(X3) 0.1 0.2 0.3 P(X3)0.10.20.3 步骤 2计算条件概率分布 P ( Y ∣ X ) P(Y|X) P(Y∣X) 接下来我们计算条件概率分布 P ( Y ∣ X ) P(Y|X) P(Y∣X)即在给定X的条件下Y的概率分布。我们可以使用条件概率的定义来计算它 P ( Y 1 ∣ X 1 ) P ( X 1 , Y 1 ) P ( X 1 ) 0.2 0.4 0.5 P(Y1|X1) \frac{P(X1, Y1)}{P(X1)} \frac{0.2}{0.4} 0.5 P(Y1∣X1)P(X1)P(X1,Y1)0.40.20.5 P ( Y 2 ∣ X 1 ) P ( X 1 , Y 2 ) P ( X 1 ) 0.1 0.4 0.25 P(Y2|X1) \frac{P(X1, Y2)}{P(X1)} \frac{0.1}{0.4} 0.25 P(Y2∣X1)P(X1)P(X1,Y2)0.40.10.25 P ( Y 1 ∣ X 2 ) P ( X 2 , Y 1 ) P ( X 2 ) 0.3 0.9 1 3 P(Y1|X2) \frac{P(X2, Y1)}{P(X2)} \frac{0.3}{0.9} \frac{1}{3} P(Y1∣X2)P(X2)P(X2,Y1)0.90.331 P ( Y 2 ∣ X 2 ) P ( X 2 , Y 2 ) P ( X 2 ) 0.4 0.9 ≈ 0.4444 P(Y2|X2) \frac{P(X2, Y2)}{P(X2)} \frac{0.4}{0.9} \approx 0.4444 P(Y2∣X2)P(X2)P(X2,Y2)0.90.4≈0.4444 P ( Y 1 ∣ X 3 ) P ( X 3 , Y 1 ) P ( X 3 ) 0.1 0.3 ≈ 0.3333 P(Y1|X3) \frac{P(X3, Y1)}{P(X3)} \frac{0.1}{0.3} \approx 0.3333 P(Y1∣X3)P(X3)P(X3,Y1)0.30.1≈0.3333 P ( Y 2 ∣ X 3 ) P ( X 3 , Y 2 ) P ( X 3 ) 0.2 0.3 ≈ 0.6667 P(Y2|X3) \frac{P(X3, Y2)}{P(X3)} \frac{0.2}{0.3} \approx 0.6667 P(Y2∣X3)P(X3)P(X3,Y2)0.30.2≈0.6667 步骤 3计算条件熵 H ( Y ∣ X ) H(Y|X) H(Y∣X) 现在我们可以使用条件熵的定义来计算 H ( Y ∣ X ) H(Y|X) H(Y∣X)根据公式 H ( Y ∣ X ) ∑ i 1 n P ( X x i ) H ( Y ∣ X x i ) H(Y|X) \sum_{i1}^n P(Xx_i) H(Y|Xx_i) H(Y∣X)i1∑nP(Xxi)H(Y∣Xxi) 代入我们计算得到的条件概率值 H ( Y ∣ X ) P ( X 1 ) ⋅ [ − ( 0.5 log 2 ( 0.5 ) 0.25 log 2 ( 0.25 ) ) ] P ( X 2 ) ⋅ [ − ( 1 3 log 2 ( 1 3 ) 0.4444 log 2 ( 0.4444 ) ) ] P ( X 3 ) ⋅ [ − ( 0.3333 log 2 ( 0.3333 ) 0.6667 log 2 ( 0.6667 ) ) ] H(Y|X) P(X1) \cdot [-(0.5 \log_2(0.5) 0.25 \log_2(0.25))] P(X2) \cdot [-(\frac{1}{3} \log_2(\frac{1}{3}) 0.4444 \log_2(0.4444))] P(X3) \cdot [-(0.3333 \log_2(0.3333) 0.6667 \log_2(0.6667))] H(Y∣X)P(X1)⋅[−(0.5log2(0.5)0.25log2(0.25))]P(X2)⋅[−(31log2(31)0.4444log2(0.4444))]P(X3)⋅[−(0.3333log2(0.3333)0.6667log2(0.6667))] 计算每个部分的值并求和 H ( Y ∣ X ) ≈ 0.8464 0.6492 0.6365 ≈ 2.1321 H(Y|X) \approx 0.8464 0.6492 0.6365 \approx 2.1321 H(Y∣X)≈0.84640.64920.6365≈2.1321 所以在给定随机变量X的条件下随机变量Y的条件熵 H ( Y ∣ X ) H(Y|X) H(Y∣X) 约为2.1321。 当熵和条件熵中的概率由数据估计特别是极大似然估计得到时所对应的熵与条件熵分别称为经验熵empirical entropy和经验条件熵empirical conditional entropy。此时若有0概率令0log00 经验熵和经验条件熵是信息论中的概念它们涉及到基于实际观测数据来估计随机变量的熵和条件熵。 经验熵Empirical Entropy 经验熵是指根据实际观测数据来估计一个随机变量的熵。通常情况下我们没有完全的先验知识无法直接知道随机变量的概率分布。因此我们可以使用观测到的数据来估计这个分布最常见的估计方法之一是极大似然估计。通过统计数据中每个事件或取值的频率我们可以估计随机变量的概率分布然后计算熵。这个估计得到的熵被称为经验熵。经验条件熵Empirical Conditional Entropy 经验条件熵是在已知另一个随机变量的条件下根据实际观测数据估计另一个随机变量的条件熵。与经验熵类似我们可以使用观测到的数据来估计条件概率分布然后计算条件熵。这个估计得到的条件熵被称为经验条件熵。 这两个概念的核心思想是当我们不知道真实的概率分布但有一些观测数据时我们可以基于数据来估计信息熵和条件熵以便在实际问题中应用信息论的概念。这对于机器学习、数据分析和模型建立等领域非常有用因为通常我们只能获得有限的数据而无法获得完整的概率分布信息。所以经验熵和经验条件熵允许我们在缺乏完整信息的情况下进行信息论分析。 信息增益information gain表示得知特征X的信息而使得类Y的信息不确定性减少的程度 定义5.2信息增益特征A对训练数据集D的信息增益 g ( D , A ) g(D,A) g(D,A)定义为集合D的经验熵 H ( D ) H(D) H(D)与特征A给定条件下D的经验条件熵 H ( D ∣ A ) H(D|A) H(D∣A)之差即 g ( D , A ) H ( D ) − H ( D ∣ A ) g(D,A)H(D)-H(D|A) g(D,A)H(D)−H(D∣A) 一般地熵H(Y)与条件熵H(Y|X)之差称为互信息mutual information。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
根据信息增益准则的特征选择方法是对训练数据集或子集D计算其每个特征的信息增益并比较它们的大小选择信息增益最大的特征。
5.2.3信息增益比
以信息增益作为划分训练数据集的特征存在偏向于选择取值较多的特征的问题。 以信息增益作为划分训练数据集的特征存在偏向于选择取值较多的特征的问题这是因为信息增益的计算方式使得在有更多取值的特征上产生更多的子分支从而可能导致信息增益偏向于选择取值较多的特征。让我更详细地解释这个问题。 信息增益的计算方式涉及到条件熵Conditional Entropy其计算公式为 H ( D ∣ A ) ∑ i 1 n ∣ D i ∣ ∣ D ∣ ⋅ H ( D i ) H(D|A) \sum_{i1}^n \frac{|D_i|}{|D|} \cdot H(D_i) H(D∣A)i1∑n∣D∣∣Di∣⋅H(Di)
其中 H ( D ∣ A ) H(D|A) H(D∣A) 是在特征 A A A 条件下数据集 D D D 的条件熵 D i D_i Di 是特征 A A A 的每个取值对应的子数据集 ∣ D i ∣ |D_i| ∣Di∣ 表示子数据集的大小 ∣ D ∣ |D| ∣D∣ 表示总数据集的大小。
注意到在计算条件熵时分母 ∣ D ∣ |D| ∣D∣ 是不变的但分子 ∣ D i ∣ |D_i| ∣Di∣ 取决于特征 A A A 的取值个数。如果特征 A A A 的取值较多那么就会有更多的 ∣ D i ∣ |D_i| ∣Di∣ 需要相加这会导致条件熵的计算中有更多的项。
这个问题的关键在于条件熵的值越低信息增益越高。因此如果特征 A A A 具有更多的取值它可能会导致更多的子分支每个子分支对应一个取值而每个子分支的条件熵通常较低因为数据更容易在这个子分支中进行分类。这会使得信息增益在计算时受到特征取值数量的影响偏向于选择取值较多的特征。
为了克服这个问题可以考虑使用一些改进的特征选择准则例如信息增益比Information Gain Ratio或基尼不纯度Gini impurity。这些准则在计算中会考虑到特征取值的数量以减轻信息增益对取值较多特征的偏向使得特征选择更加平衡。
5.3决策树的生成
5.3.1 ID3算法
5.3.2 C4.5的生成算法
5.4决策树的剪枝
5.5 CART算法
5.5.1 CART生成
5.5.2 CART剪枝
