外贸cms建站,电子政务网站模版,深圳企业网络推广运营技巧,app界面设计模板图ID3
ID3算法在特征选择时#xff0c;使用的指标是信息增益#xff08;Information Gain#xff09;#xff0c;信息增益是基于熵#xff08;entropy#xff09;的概念#xff0c;熵是用来衡量数据集中的不确定性或纯度的一个指标。当熵值高时#xff0c;数据集的不确定…ID3
ID3算法在特征选择时使用的指标是信息增益Information Gain信息增益是基于熵entropy的概念熵是用来衡量数据集中的不确定性或纯度的一个指标。当熵值高时数据集的不确定性大反之亦然。
信息增益的计算公式为 I G ( D , A ) E n t r o p y ( D ) − ∑ v ∈ V a l u e s ( A ) ∣ D v ∣ ∣ D ∣ ⋅ E n t r o p y ( D v ) IG(D, A) Entropy(D) - \sum_{v \in Values(A)} \frac{|D_v|}{|D|} \cdot Entropy(D_v) IG(D,A)Entropy(D)−v∈Values(A)∑∣D∣∣Dv∣⋅Entropy(Dv)
其中 I G ( D , A ) IG(D, A) IG(D,A) 是数据集 D D D 关于特征 A A A 的信息增益。 E n t r o p y ( D ) Entropy(D) Entropy(D) 是数据集 D D D 的熵。 V a l u e s ( A ) Values(A) Values(A) 是特征 A A A 所有可能的值。 D v D_v Dv 是数据集 D D D 中特征 A A A 取值为 v v v 的子集。 E n t r o p y ( D v ) Entropy(D_v) Entropy(Dv) 是子集 D v D_v Dv 的熵。
C4.5
信息增益倾向于选择具有更多值的属性。为了克服这个问题C4.5引入了信息增益比这个指标考虑了特征的内在信息并且对具有大量值的特征进行惩罚。
信息增益比的计算公式为 G a i n R a t i o ( D , A ) I G ( D , A ) S p l i t I n f o ( D , A ) GainRatio(D, A) \frac{IG(D, A)}{SplitInfo(D, A)} GainRatio(D,A)SplitInfo(D,A)IG(D,A) 其中 S p l i t I n f o ( D , A ) SplitInfo(D, A) SplitInfo(D,A) 是对特征 A A A 的分裂信息用于度量分裂的平均信息值或分裂的“广度”和“均匀性”其计算公式为 S p l i t I n f o ( D , A ) − ∑ v ∈ V a l u e s ( A ) ∣ D v ∣ ∣ D ∣ ⋅ log 2 ∣ D v ∣ ∣ D ∣ SplitInfo(D, A) - \sum_{v \in Values(A)} \frac{|D_v|}{|D|} \cdot \log_2 \frac{|D_v|}{|D|} SplitInfo(D,A)−v∈Values(A)∑∣D∣∣Dv∣⋅log2∣D∣∣Dv∣特征选择时C4.5选择信息增益比最高的特征进行分裂。使用信息增益比可以减少对多值特征的偏好使得生成的决策树更加平衡。
C4.5算法的其他特点 支持连续特征C4.5可以处理连续和离散特征连续特征的处理是通过将值排序并找到最佳分割点将其转换为离散值。
剪枝C4.5使用后剪枝方法来避免过拟合这意味着它首先生成一个完整的树然后删除那些对分类效果贡献不大的节点。
缺失值处理C4.5有一套内建的机制来处理缺失值允许它在不完整的数据集上工作。
C4.5是一个十分强大且广泛使用的决策树生成算法它的改进版本C5.0在速度和内存使用等方面有了进一步的优化。
CART
CART树是一种二叉树每个内部节点都对应于一个输入特征和一个阈值将数据集分为两个子集分别进入左子树和右子树。根据目标不同又可分为 分类树 和 回归树。
CART 分类树
对于分类问题CART树的建立过程包括
特征选择CART树使用基尼不纯度Gini impurity作为特征选择的标准。基尼不纯度是从一个数据集中随机选择两个样本它们的类标签不一致的概率。基尼不纯度最小的特征被用于分割。
基尼不纯度的计算公式为 G i n i ( p ) 1 − ∑ i 1 J p i 2 Gini(p) 1 - \sum_{i1}^{J}p_i^2 Gini(p)1−i1∑Jpi2 其中 p i p_i pi 是第 i i i 个类别的相对频率 J J J 是类别的总数。
树的构造从根节点开始递归地使用特征选择方法分割数据生成二叉树。每个内部节点代表一个特征和阈值的判断根据判断结果样本被分到左子树或右子树。这一过程持续进行直到满足停止条件比如节点中的样本数量少于预设的阈值或者节点的不纯度降至某个水平以下。
剪枝为了避免过拟合CART树在构造完成后会进行剪枝将一些子树替换为叶节点。剪枝过程基于成本复杂度剪枝Cost-Complexity Pruning这涉及到一个参数 α \alpha α被称为复杂度参数用于控制树的复杂度和拟合的程度。
CART 回归树
对于回归问题CART树的建立过程类似但是有两个主要区别
特征选择CART回归树在每个节点上选取特征和划分阈值以最小化两个子节点的平均平方误差Mean Squared Error, MSE或平均绝对误差Mean Absolute Error, MAE。
剪枝回归树的剪枝过程同样使用成本复杂度剪枝但是考虑的是平方误差与子树复杂度之间的平衡。
CART算法优点 简单直观易于理解和解释。 既能处理分类问题也能处理回归问题。 能够处理数值型和类别型特征。 通过剪枝可以有效防止过拟合。
CART算法缺点 对异常值敏感容易受到噪声影响。 贪心算法的本质使得CART并不一定能够找到全局最优解。 倾向于生成偏向于拥有更多水平的树因为二叉分割会导致不平衡的树结构。 CART树在许多领域都有应用如医学、金融、市场营销等并且它是许多集成学习方法例如随机森林和梯度提升树的基础。
