决策树中的熵和基尼指数

发布日期:2019-01-03

决策树是一种很基本的分类与回归方法,但正如前面博文机器学习排序算法:RankNet to LambdaRank to LambdaMART中所讲的LambdaMART算法一样,这种最基本的算法却是很多经典、复杂、高效的机器学习算法的基础。关于什么是决策树,网上一搜就会有很多博客文章,所以本文并不想讨论这个话题。本文想讨论的是决策树中两个非常重要的决策指标:熵和基尼指数。熵和基尼指数都是用来定义随机变量的不确定性的指标。下面先介绍什么是随机变量的不确定性。

1. 随机变量的不确定性

什么是随机变量的不确定性?举个例子,比如一个班级有50个同学,每个同学都有且仅有一部智能手机,问:如果任意选择一位同学,他可能用什么品牌的手机?如果这个班的同学全部都用苹果手机,那这个问题很好回答,也即“从这个班中任意选取的一位同学用什么品牌的手机”这个随机变量是确定的,不确定性为0。但如果这个班级中$frac{1}{3}$的同学用小米手机,$frac{1}{3}$的同学用苹果手机,其余$frac{1}{3}$的同学用华为手机,这种情况下,这个变量的不确定性明显增大了。那接下来就需要考虑另外一个问题:什么情况下,这个变量的不确定性最大呢?直观来看,如果每个同学都使用不同品牌的手机时,这个变量的不确定性应该最大的。理解了随机变量的不确定性后,就更容易理解下面介绍的熵和基尼指数的定义。

2. 熵的定义及相关证明

在信息论与概率统计中,熵是最基础的概念,其表示随机变量不确定的度量。设$X$是一个取有限个值的离散随机变量,其概率分布为:

$$P(X=x_i)=p_i i=12...n$$

则随机变量$X$的熵定义为:

$$H(X)=-sum_{i=1}^{n}p_ilog{p_i}$$

为了使上式有意义,定义$0log{0}=0$。因为熵的定义只依赖于$X$的分布,而与$X$的取值无关,所以我们可以将熵看成是分布的函数:

$$H(p)=-sum_{i=1}^{n}p_ilog{p_i}$$

上面说到均匀分布的熵最大,但这只是直观的感觉,并没有证明。下面利用拉格朗日乘子法进行证明。根据拉格朗日乘子的可以将$H(p)$改写成:

$$H(p)=-sum_{i=1}^{n}p_ilog{p_i}+lambda left(sum_{i=1}^{n}p_i-1ight)$$

$H(p)$对每个$p_i$求导,得到:

$$frac{partial{H(p)}}{partial{p_i}}=-ln{p_i}-1+lambda=0i=12...n$$

由$-ln{p_i}-1+lambda=0$可以得到$p_i=e^{lambda-1} i=12...n$

所以可知$p_i$是只与$lambda$相关的值,每个$p_i$应该都相等,即$p_1=p_2=...=p_n=frac{1}{n}$,此时$H(p)$取得最大值$log{n}$。由此可知熵的值域是$[0log{n}]$。

3. 基尼指数的定义及相关证明

基尼指数是经典决策树CART用于分类问题时选择最优特征的指标。假设有$K$个类,样本点属于第$k$类的概率为$p_k$,则概率分布的基尼指数定义为:

$$G(p)=sum_{k=1}^{K}p_k(1-p_k)=1-sum_{k=1}^{K}p_k^2$$

满足条件$sum_{k=1}^{K}p_k=1$

正如上面所说,基尼指数同样可以描述一个随机变量的不确定性的程度,所以可以猜测:当$p_1=p_2=...=p_K=frac{1}{K}$时,$G(p)$取得最大值,此时随机变量最不确定。那么,如何进行证明?下面给出两种方法。

方法1:同样可以使用拉格朗日乘子法进行证明。根据拉格朗日乘子的性质,改写$G(p)$函数为:

$$G(p)=1-sum_{k=1}^{K}p_k^2+lambda left(sum_{k=1}^{K}p_k - 1ight)$$

$G(p)$对每个$p_i$求导,得到:

$$frac{partial{G(p)}}{partial{p_i}}=-2p_i+lambda=0i=12...K$$

由$-2p_i+lambda=0$可知$p_i$同样只与常数$lambda$相关,所以$p_1=p_2=...=p_K=frac{1}{K}$

$G(p)$的值域为$[01-frac{1}{K}]$。

方法2:构造$K$为空间中的两个点$P_1=[p_1p_2...p_K]^T$和$P_2=[frac{1}{K}frac{1}{K}...frac{1}{K}]^T$,其夹角为$heta$,所以:

$$cosheta=frac{P_1cdot P_2}{|P_1|cdot |P_2|}=frac{[p_1p_2...p_K]cdot [frac{1}{K}frac{1}{K}...frac{1}{K}]}{sqrt{p_1^2+p_2^2+...+p_K^2}cdot sqrt{frac{1}{K^2}+frac{1}{K^2}+...+frac{1}{K^2}}}leq{1}$$

所以:

$$sum_{k=1}^{K}p_k^2ge frac{(sum_{k=1}^{K}p_k)^2}{K}$$

于是:

$$G(p)leq 1-frac{(sum_{k=1}^{K}p_k)^2}{K}=1-frac{1}{K}$$

等号在$p_1=p_2=...=p_K=frac{1}{K}$时达到。