习题5.1
信息增益比公式： (g_R(Y, X_i) = frac{g(Y, X_i)}{H_{X_i}(Y)} = frac{H(Y) - H(Y|X_i)}{H_{X_i}(Y)})
其中， (H(Y) = -frac{9}{15} log_2 frac{9}{15} - frac{6}{15} log_2 frac{6}{15} = 0.971)
用 (X_1, X_2, X_3, X_4) 表示 年龄、有工作、有自己的房子、信贷情况。根据例 5.2 可得
(g(Y, X_1) = 0.083, g(Y, X_2) = 0.324, g(Y, X_3) = 0.420, g(Y, X_4) = 0.363)
接着，计算 (H_{X_i}(Y))
(H_{X_1}(Y) = -frac{5}{15} log_2 frac{5}{15} - frac{5}{15} log_2 frac{5}{15} - frac{5}{15} log_2 frac{5}{15} = 1.585)
(H_{X_2}(Y) = -frac{5}{15} log_2 frac{5}{15} - frac{10}{15} log_2 frac{10}{15} = 0.918)
(H_{X_3}(Y) = -frac{6}{15} log_2 frac{6}{15} - frac{9}{15} log_2 frac{9}{15} = 0.971)
(H_{X_4}(Y) = -frac{4}{15} log_2 frac{4}{15} - frac{5}{15} log_2 frac{5}{15} - frac{6}{15} log_2 frac{6}{15} = 1.566)
计算 (g_R(Y, X_i)) ，可得 (g_R(Y, X_1) = frac{g(Y, X_1)}{H_{X_1}(Y)} = frac{0.083}{1.585} = 0.052, g_R(Y, X_2) = frac{g(Y, X_2)}{H_{X_2}(Y)} = frac{0.324}{0.918} = 0.353, g_R(Y, X_3) = frac{g(Y, X_3)}{H_{X_3}(Y)} = frac{0.420}{0.971} = 0.433, g_R(Y, X_4) = frac{g(Y, X_4)}{H_{X_4}(Y)} = frac{0.363}{1.566} = 0.232)
信息增益比最大的是 (X_3) ，以该特征为分裂点，分为两个节点，数据集也分为两部分。
后续过程按照 C4.5 算法，以信息增益比生成决策树。
习题5.2
按照 CART 回归树生成方法生成。
计算过程略
习题5.3
假设 (alpha) 确定，存在不止一个最优子树。假设有两个最优子树 (T_a) 和 (T_b) ，对应要剪枝的内部节点为 (t_a) 和 (t_b) 。
因此，在 (alpha) 确定时，(C_{alpha}(T_a) = C_{alpha}(T_b)) 。并且 (C_{alpha}(t_a) le C_{alpha}(T_{t_a})) (C_{alpha}(t_b) le C_{alpha}(T_{t_b}))
那么，对于这样的最优子树，总可以进行进一步剪枝，使得损失函数变小（在 (T_a) 中剪 (t_b) ，在 (T_b) 中剪 (t_a) ）
因此，最优子树唯一。
习题5.4
将证明内容改为如下形式：
随着 (alpha) 不断增大，(0 = alpha_0 < alpha_1 < ... < alpha_n < + infty) ，在每个区间 ([alpha_i. alpha_{i+1})) 中，子树 (T_i) 是该区间最优的
当 (i=0) 时，可得原树 (T_0)是最优子树；当 (i = n) 时，以根节点组成的单节点树是最优的
剪枝前：(C_{alpha}(T_t) = C(T_t) + alpha|T_t|) ；剪枝后：(C_{alpha}(t) = C(t) + alpha)
因此，若要发生剪枝，必有 (C_{alpha}(t) - C_{alpha}(T_t) = C(t) + alpha -C(T_t) - alpha|T_t| le 0)
则 (alpha ge frac{C(t)-C(T_t)}{|T_t| -1}) 。令 (g(t) = frac{C(t)-C(T_t)}{|T_t| -1})
对于 (T_0) ，遍历所有的内部节点，并计算每个节点的 (g(t)) ，找到使 (g(t)) 最小的节点 (t) 并令该 (alpha_1 = g(t))，并对 (T_0) 进行剪枝，作为(T_1) 。
对于 (T_0) 而言，它是区间 ([alpha_0 , alpha_1)) 这个区间的最优子树。并且随着 (alpha) 增长到 (alpha_1) 时必须剪枝（要使整体损失最小），此时 (T_1) 是最优子树。并在以 (T_1) 为整体数，继续进行剪枝。
通过推演， (T_i) 是区间 ([alpha_i, alpha_{i+1})) 的最优子树，原结论可得证。
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
