本文介绍了CART（Classification and Regression Tree）算法，包括其分类树和回归树的构建原理。文章通过信息增益、基尼系数、特征处理和剪枝策略，详细阐述了CART在处理连续和离散特征时的改进，并探讨了CART在回归问题上的应用。同时，文中提供了一个面试题，展示了如何使用基尼系数计算信息增益，以确定最佳划分特征。
CART分类树与回归树
前记
本篇文章不会大幅度去介绍CART是怎么来的，以及CART与其他不同的地方，但是会着重的讲解在面试过程中遇到的问题，知识点的话会简单点的温习一下,本文是按照博主学习CART的过程俩编写，本文假设读者已经知道了ID3已经C4.5算法，若写的有问题，请指出，谢谢.
1. 为什么会有CART
我们已经知道在ID3中，我们是使用信息增益去作为分类的基准的，在现场面试中，面试官曾要求我们计算信息增益，以及选择分类的基准.首先是具备以下知识：
1.1 面试题1：信息增益（information gain）
首先，我们需要熟悉信息论中熵的概念。熵度量了事物的不确定性，越不确定的事物，它的熵就越大。具体的，随机变量X的熵的表达式如下：
H ( x ) = − ∑ i = 1 n p i log p i H(x)=-\sum _{i=1}^{n}p_i\log{p_i} H(x)=−i=1∑npilogpi
熟悉了一个变量X的熵，很容易推广到多个个变量的联合熵，这里给出两个变量X和Y的联合熵表达式：
H ( X , Y ) = − ∑ i = 1 n P ( x i , y i ) log ( P ( x i , y i ) ) H(X,Y)=-\sum _{i=1}^{n}P(x_i,y_i)\log(P(x_i,y_i)) H(X,Y)=−i=1∑nP(xi,yi)log(P(xi,yi))
有了联合熵，又可以得到条件熵的表达式H(X|Y)，条件熵类似于条件概率,它度量了我们的X在知道Y以后剩下的不确定性。表达式如下：
H ( Y ∣ X ) = ∑ i = 1 n P i H ( Y ∣ X = X i ) H(Y|X)=\sum_{i=1}^n P_iH(Y|X=X_i) H(Y∣X)=i=1∑nPiH(Y∣X=Xi)
有了上面的推导，我们下面给出信息增益的概念以及计算公式：信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度，其定义如下：特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H（D）与特征A给定条件D下的经验条件熵H（D|A）之差，即
g ( D , A ) = H ( D ) − H ( D ∣ A ) g(D,A)=H(D)-H(D|A) g(D,A)=H(D)−H(D∣A)
有了上面的基础，那么可以开始本次的面试题了，给定特征，计算信息增益以及确定分类特征。
下面的示例是以李航博士的统计学习方法为例：
比如存在上面的数据集D，我们分析初始时，哪一个作为分类节点较为合适,分别以 A 1 , A 2 , A 3 , A 4 A_1,A_2,A_3,A_4 A1,A2,A3,A4表示年龄，有工作，有自己的房子和信贷情况，那么我们开始来计算每个特征的信息增益：
（1）计算D的熵：
H ( D ) = − 9 15 log 2 9 15 − 6 15 log 2 6 15 = 0.971 H(D)=-\frac{9}{15}\log_2\frac{9}{15}-\frac{6}{15}\log_2\frac{6}{15}=0.971 H(D)=−159log2159−156log2156=0.971
(2)对于特征 A 1 A_1 A1的信息增益，因为分为三类（青年：5( D 1 D_1 D1)，中年：5( D 2 D_2 D2)，老年：5( D 3 D_3 D3)），那么按照公式，我们首先得到总体的计算公式以及变换计算如下：
g ( D , A 1 )
最低0.47元/天 解锁文章
扫一扫
515
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
