机器学习__C.算法.pptx

**机器学习中的C4.5算法** C4.5算法是一种经典的决策树构建算法，由J.Ross Quinlan在ID3（Iterative Dichotomiser 3）算法的基础上发展而来。ID3算法主要依赖信息增益来进行特征选择，而C4.5则引入了信息增益率来克服ID3的一些缺陷。 ### ID3与C4.5的区别 ID3算法选择最优特征是基于信息增益，即属性划分前后的熵减少量。然而，ID3存在一个问题，即它倾向于选择具有多个取值的属性，即使这些属性的划分并不能带来有效的信息。为了解决这个问题，C4.5采用了信息增益率，它在信息增益基础上除以属性的“分裂信息”，即属性划分的熵，以此来规范信息增益，避免偏好那些具有大量取值的属性。 ### 信息增益与信息增益率 信息增益计算公式为：`Gain(D,a) = Ent(D) - Info_a(Dv)`，其中`Ent(D)`是数据集D的熵，`Info_a(Dv)`是根据属性a划分后的数据集Dv的条件熵。信息增益率则是信息增益除以属性a的分裂信息（IV(a)），可以防止过多地选择具有大量取值的属性。 ### C4.5算法流程 1. **节点纯度检查**：如果当前节点的所有样本属于同一类别，则设置为叶子节点，结束分裂。 2. **计算熵**：计算当前节点的熵，即基于类别分布的不纯度。 3. **计算信息增益**：对每个属性计算信息增益。 4. **计算信息增益率**：计算每个属性的信息增益率，即信息增益除以其分类信息度量（IV）。 5. **选择最佳属性**：选择信息增益率最高的属性作为分裂属性。 6. **处理连续值**：对于连续属性，C4.5采用排序并寻找分割点的方法。首先对属性值进行排序，然后在相邻值的中点寻找可能的分裂点。为了提高效率，通常只考虑导致类别变化的分割点。 7. **递归分裂**：对每个子集重复以上步骤，直到所有子集达到预设的纯度或满足停止条件（如最小样本数）。 ### 特点与局限性 - **C4.5是多叉决策树**：与ID3的二叉树不同，C4.5允许非二叉树结构，使得决策树更灵活。 - **仅适用于分类任务**：C4.5算法设计用于处理分类问题，不适合回归等其他类型的机器学习任务。 - **计算复杂性**：熵模型涉及大量的对数运算，连续值还需要排序，对于大规模数据集可能会消耗大量计算资源。 - **内存限制**：在构建决策树时，需要将数据集加载到内存中，对数据集大小有限制，无法处理超出内存容量的大数据集。 - **启发式选择**：C4.5在选择特征时，首先考虑信息增益高于平均值的特征，然后在这些特征中选取信息增益率最高的，以平衡信息增益和属性基数。 总结来说，C4.5算法在决策树构建中引入了信息增益率，解决了ID3算法的某些问题，提高了决策树的构建质量。但同时，它也存在计算复杂性和内存限制等问题，需要在实际应用中权衡。