决策树是如何进行特征选择的

Question

决策树是如何进行特征选择的？
决策树在构建过程中如何选择最优的划分特征？常见的特征选择准则有哪些（如信息增益、增益率、基尼不纯度）？

Answer 1

决策树在构建过程中进行特征选择是为了找到最有利于数据集划分的属性，从而形成具有高度预测能力的决策结构。特征选择的目标是使每个内部节点（非叶节点）所代表的子集在该特征下的纯度得到最大程度的提升，或者不确定性得到最大程度的降低。这样，沿着决策路径向下移动时，最终到达的叶节点包含的样本尽可能属于同一类别，从而提高整体分类或预测的准确性。以下是如何进行特征选择以及常用的特征选择准则的详细解释：

如何进行特征选择：

1. 遍历特征：

   • 对于当前节点的数据集，遍历所有可用特征。

2. 计算划分指标：

   • 对于每个特征，考虑其所有可能的取值（即候选分裂点），计算以这些取值为阈值进行划分时的划分指标。

3. 选择最优特征和分裂点：

   • 根据计算出的划分指标，选择使指标最优（如最大或最小，取决于具体准则）的特征及其对应的分裂点。
   • 这个特征及其分裂点将用于创建当前节点的两个子节点，每个子节点包含原数据集中根据该特征值划分的部分样本。

4. 递归构建：

   • 对每个生成的子节点，重复上述过程，直到达到停止条件（如节点包含的样本数低于某个阈值、节点纯度已足够高、没有更多特征可选等）。

常见的特征选择准则：

1. 信息增益 (Information Gain, IG):

• 定义：信息增益衡量的是使用某个特征进行划分前后，数据集的熵（不确定性）减少的程度。
• 公式：( IG(D, A) = H(D) - H(D|A) )，其中 ( D ) 是当前数据集，( A ) 是特征，( H(D) ) 是数据集 ( D ) 的熵，( H(D|A) ) 是在特征 ( A ) 上划分后各子集条件熵的加权平均。
• 选择原则：信息增益越大，说明使用该特征划分后数据集的纯度提升越多，因此选择信息增益最大的特征作为最优划分特征。

2. 信息增益比 (Information Gain Ratio, IGR):

• 定义：信息增益比是对信息增益的一种修正，考虑到某些特征可能有大量取值，导致信息增益较大但未必是最优划分标准。信息增益比是信息增益除以其固有的不确定性（即特征本身的熵）。
• 公式：( IGR(D, A) = \frac{IG(D, A)}{H(A)} )，其中 ( H(A) ) 是特征 ( A ) 的熵，反映了特征 ( A ) 的取值分布的不确定性。
• 选择原则：信息增益比最大的特征被选为最优划分特征，它既考虑了划分效果，又避免了对多取值特征的过度偏好。

3. 基尼不纯度 (Gini Impurity, GI):

• 定义：基尼不纯度是另一种衡量数据集不确定性的指标，它反映了从数据集中随机抽取一个样本，其类别被错误标记的概率。
• 公式：对于数据集 ( D )，基尼不纯度为 ( GI(D) = 1 - \sum_{k=1}^{K} p_k^2 )，其中 ( K ) 是类别总数，( p_k ) 是数据集中第 ( k ) 类样本所占的比例。
• 选择原则：在特征 ( A ) 上划分后，计算各子集的基尼不纯度并加权平均得到划分后的基尼指数。选择基尼指数最小的特征作为最优划分特征，这意味着该特征使得数据集划分后的混乱程度最低。

综上所述，决策树在构建过程中通过遍历特征、计算划分指标、选择最优特征及分裂点，并递归地重复这一过程来构建整个树结构。常见的特征选择准则包括信息增益、信息增益比和基尼不纯度，它们分别从不同角度衡量了特征在划分数据集时减少不确定性的能力。决策树算法会选择能使这些指标最优的特征作为每个内部节点的划分依据。