选择最佳划分的度量

对于连续属性，我们不可能像离散属性那样枚举所有可能的值作为分支。取而代之的是，我们将连续值排序，然后考虑一系列候选划分点，并找到一个能产生“最佳”子集的划分点。

衡量“最佳”划分的度量标准主要有三个，它们都旨在衡量划分后子集的“纯度”提升。

这是最经典的度量，用于ID3、C4.5等算法。

信息熵： 度量数据集 D 的不确定性（混乱程度）。
$Entropy(D) = -Σ (p_i * log₂(p_i))$
其中 $p_i$ 是数据集中第 i 类样本所占的比例。熵越高，数据越混乱。
信息增益： 使用属性 $A$ 在划分点 $t$ 进行划分后，数据集不确定性减少的程度。
$IG(D, A, t) = Entropy(D) - Σ (|D_v| / |D|) * Entropy(D_v)$
其中 $D_v$ 是划分后产生的子集（对于二分法，通常是两个子集： $D_left (A ≤ t) 和 D_right(A > t)$ 。
选择标准： 选择能带来最大信息增益的那个划分点 t。
$Best_split = argmax(IG(D, A, t))$

缺点： 信息增益倾向于选择取值较多的属性（即使这个属性与分类无关），因为它更容易产生“纯”的子集。

用于C4.5算法，以克服信息增益的缺点。

固有信息： 属性 A 在划分点 t 进行划分时本身产生的信息量。
$IV(D, A, t) = -Σ (|D_v| / |D|) * log₂(|D_v| / |D|)$
信息增益率：
$Gain_ratio(D, A, t) = IG(D, A, t) / IV(D, A, t)$
选择标准： 选择具有最高信息增益率的划分点。

作用： 固有信息 IV 会惩罚那些取值很多、划分得很细的属性，从而避免了模型过拟合。

CART（分类与回归树）算法使用基尼不纯度来构建二叉树。

基尼不纯度： 度量从数据集中随机抽取两个样本，其类别标签不一致的概率。基尼值越小，数据集越纯。
$Gini(D) = 1 - Σ (p_i)²$
基尼增益： 划分后基尼不纯度的减少量。通常我们直接计算划分后的加权基尼值，并寻找最小值。
$Gini_after_split = Σ (|D_v| / |D|) * Gini(D_v)$
选择标准： 选择能使划分后子集的加权基尼不纯度最小的那个划分点 t。
$Best_split = argmin(Gini_after_split)$

特点： 基尼不纯度的计算不涉及对数运算，因此计算效率通常比信息熵高。

假设我们有一个连续属性 A（例如“年龄”），和目标变量 y（例如“是否购买”）。

排序：
- 首先，根据属性 A 的值对数据集中的所有样本进行升序排序。
生成候选划分点：
- 通常，候选划分点取为连续值之间中点。例如，如果排序后的 A 值是 [10, 15, 20, 25]，那么候选划分点就是 (10+15)/2 = 12.5, (15+20)/2 = 17.5, (20+25)/2 = 22.5。
- 为什么是中点？ 因为对于任何在两个不同值 $a_i$ 和 $a_{i+1}$ 之间的阈值 t，其划分结果都是一样的。选择中点作为代表即可。
评估每个候选划分点：
- 对于每一个候选划分点 t，将数据集划分为两个子集：
  - $D_left$ : 满足 $A ≤ t$ 的样本
  - $D_right$ : 满足 $A > t$ 的样本
- 使用选定的度量标准（如信息增益、基尼增益等）计算这个划分的“得分”。
选择最佳划分点：
- 比较所有候选划分点的得分，选择得分最高的那个点作为属性 A 的最佳划分点。
- 同时记录下这个最佳得分。
与其他属性比较：
- 对数据集中的每一个属性（包括其他连续属性和离散属性）都重复步骤1-4，找到每个属性的最佳划分点及其得分。
- 最终，从所有属性中选出得分最高的那个属性，作为当前节点的划分标准。

假设我们有如下数据，要基于“年龄”预测“是否玩游戏”：

排序： 年龄已排序 [10, 15, 20, 25]。
候选点： 12.5, 17.5, 22.5。
评估：
- 划分点 t = 12.5：
  - D_left (A≤12.5): [10] -> 类别 [否]， Gini = 1 - (1² + 0²) = 0
  - D_right (A>12.5): [15,20,25] -> 类别 [否,是,是]， Gini = 1 - ((1/3)² + (2/3)²) = 1 - (1/9 + 4/9) = 4/9 ≈ 0.444
  - 加权基尼 = (1/4)0 + (3/4)(4/9) ≈ 0.333
- 划分点 t = 17.5：
  - D_left: [10,15] -> [否,否]， Gini = 0
  - D_right: [20,25] -> [是,是]， Gini = 0
  - 加权基尼 = (2/4)*0 + (2/4)*0 = 0 （这是一个完美划分！）
- 划分点 t = 22.5： …（计算过程略，其加权基尼值会大于0）
选择： 比较发现，划分点 t=17.5 的加权基尼值最小（为0），因此我们选择它作为“年龄”属性的最佳划分点。规则就是：如果年龄 ≤ 17.5，预测“否”；否则预测“是”。