机器学习面试题 14：决策树
内容提要
决策树是一种分类与回归方法，以属性为结点、取值为分支。特征选择用信息熵衡量不确定性，信息增益表示划分前后熵的变化。ID3算法选择信息增益最大的属性递归建树；C4.5改进用信息增益率、剪枝、离散化及处理不完整数据；CART则用于回归与分类。
延伸解读
决策树的本质与适用场景
决策树是一种基于树结构的分类与回归方法，通过属性取值递归划分样本，最终叶节点给出类别。其核心优势在于可解释性强，能直观展示决策过程，适合需要理解模型逻辑的场景。但文章也指出，决策树容易过拟合，需通过剪枝等手段提升泛化能力。
从ID3到C4.5的改进动机
ID3算法以信息增益为准则选择属性，但存在偏向多值属性的问题。C4.5引入信息增益率来平衡，同时增加剪枝、连续属性离散化和处理不完整数据的能力。这些改进使C4.5在实际应用中更稳健，也体现了算法设计中对数据多样性和噪声的考虑。
特征选择的关键：信息熵与信息增益
信息熵衡量数据的不确定性，信息增益则反映划分前后熵的降低程度。选择信息增益最大的属性作为分裂节点，能最快降低不确定性，使子集更纯。但信息增益对取值多的属性有偏好，C4.5用信息增益率修正，提醒读者在应用时需注意属性取值分布的影响。
Q&A
什么是决策树？
决策树是一种基本的分类与回归方法，它用样本的属性作为结点，用属性的取值作为分支的树结构。根结点是所有样本中信息量最大的属性，中间结点是相应子集中信息量最大的属性，叶结点是样本的类别值。
决策树中信息熵和信息增益分别是什么？
信息熵用来衡量随机变量的不确定性，熵越大表示不确定性越大。信息增益是指信息划分前后的熵的变化，即原有信息熵与属性划分后信息熵（取期望值）的差值，它表示由于使用该属性分割样例而导致的期望熵降低。
ID3算法是如何构建决策树的？
ID3算法的基本思想是：首先找出最有判别力的属性，把样例分成多个子集，每个子集再选择最有判别力的属性进行划分，直到所有子集仅包含同一类型的数据为止。具体步骤包括：计算各属性的信息增益，选择信息增益最大的属性，按该属性的取值划分子集，对既含正例又含反例的子集递归调用建树算法，若子集仅含正例或反例则标记并返回。
C4.5算法对ID3算法做了哪些改进？
C4.5算法是ID3算法的改进，主要改进包括：用信息增益率来选择属性，克服了用信息增益选择属性偏向选择多值属性的不足；在构造树的过程中进行剪枝；对连续属性进行离散化；能够对不完整的数据进行处理。
信息增益率是如何计算的？
信息增益率是信息增益与信息熵的比例。设样本集S按离散属性F的c个不同的取值划分为c个子集，则这c个子集的信息熵为H(S)，信息增益率为信息增益Gain(S,F)除以H(S)，即Gain_ratio(S,F) = Gain(S,F) / H(S)。
决策树中特征选择的作用是什么？
特征选择是决策树构建的关键步骤，它通过选择最有判别力的属性来划分样本，使得划分后的子集尽可能纯净。信息熵和信息增益是常用的度量标准，信息增益越大表示该属性对分类的贡献越大。
