信息论

熵是表示随机变量不确定性的度量，设X是一个取有限个值的离散随机变量，他的概率分布为:

$$ P(X=x_i)=p_i \quad\quad i=1,2,\cdots,n

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

$$ H(X)=-\sum_{i=1}^np_ilogp_i

$$ 设有随机变量(X,Y)，其联合概率分布为

$$ P(X=xi,Y=y_i)=p{i,j},\quad\quad i=1,2,\cdots,n;j = 1,2,\cdots,m

$$ 条件熵P(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵，定义为X给定条件下Y的条件概率分布熵对X的数学期望:

$$ H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i)

$$ 这里的$$p_i=P(X = x_i),i=1,2,\cdots,n$$ 信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的深度。 (信息增益)特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D,A)的差，即:

$$ g(D,A)=H(D)-H(D|A)

$$ 一般地，熵H(Y)和条件熵H(Y|X)之差称为互信息。决策树学习中的信息增益等价于训练数据集中类和特征的互信息。

根据信息增益准则的特征选择方法是:对训练数据集(或者子集)D.计算其每个特征的信息增益，并比较他们的大小，选择信息增益最大的特征。

输入:训练数据集D和特征Aa 输出:特征A对训练数据集D的信息增益g(D,A)

• 计算数据集D的经验熵

$$ H(D)=-\sum_{k=1}^K\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}

$$

• 计算特征A对数据集D的经验条件熵H(D|A)

$$ H(D|A)=\sum{i=1}^n\frac{|D_i|}{|D|}H(D_i)=-\sum{i=1}^n\frac{Di}{|D|}\sum{k=1}^k\frac{|D{ik}|}{|D_i|}log_2\frac{|D{ik}|}{|D_i|}

$$

• 计算信息增益 $$ g(D,A)=H(D)-H(D|A) $$ 信息增益值的大小是相对于训练数据集而言的，没有绝对意义。在分类问题困难时，也就是说在训练数据集的经验熵大的时候，信息增益值会偏大，单只信息增益值会偏小。使用信息增益比可以对这一问题进行矫正。

特征A对训练数据集D的信息增益比$$g_R(D,A)$$定义为信息增益g(D,A)和训练数据集D的经验熵H(D)的比:

$$ g_R(D,A) = \frac{g(D,A)}{G(D)}

$$ 例子: 对下表给出的训练数据集D，根据信息增益准则选择最优特征。

计算信息增益 计算经验熵(统计频率下的熵)

$$ H(D) = -\frac{9}{15}log_2\frac{9}{15}-\frac{6}{15}log_2\frac{6}{15}=0.971

$$ 假设$$A_1,A_2,A_3,A_4$$表示年龄，工作房子，信贷。

• 计算年龄的信息增益
  • H(D_1):年龄为青年的经验熵(青年数目为5，放贷数量2)
  • H(D_2):年龄为中年的经验熵(中年数目为5，放贷数量为3)
  • H(D_3):年龄为老年的经验熵（老年数目为5，放贷数量为4） $$ \begin{equation} \begin{split} H(D_1) = -\frac{2}{5}log_2\frac{2}{5}-\frac{3}{5}log_2\frac{3}{5}\ H(D_2) = -\frac{3}{5}log_2\frac{3}{5}-\frac{2}{5}log_2\frac{2}{5}\ H(D_3) = -\frac{4}{5}log_2\frac{4}{5}-\frac{1}{5}log_2\frac{1}{5} \end{split} \end{equation} $$ 信息增益:

$$ g(D,A_1)=H(D)-[\frac{5}{15}H(D_1)+\frac{5}{15}H(D_2)+\frac{5}{15}H(D_3)] = 0.083

$$ 同理计算结果如下:

$$g(D,A_2)=0.324$$

$$g(D,A_3)=0.420$$

$$g(D,A_4)=0.363$$ 计算代码如下:

import numpy as np
def info_shang(x):
    for i in x:
        if i == 0:
            return 0
        else:
            continue
    a = np.log2(x)
    return -a.dot(x)
def c_shang(x,y):
    return np.array(x).dot(y)
a = [9/15,6/15]
H_D = info_shang(a)
age = np.array([5/15,5/15.5/15])
# 青年条件下结果是有2，否有3，计算信息经验熵
age_n1 = [2/5,3/5]
age_n2 = [3/5,2/5]
age_n3 = [4/5,1/5]
# 计算三种不同年龄的经验熵
age_n_s = [info_shang(age_n1),info_shang(age_n2),info_shang(age_n3)]
age_rate = [5/15,5/15,5/15]
# 计算年龄下条件熵
H_DA = c_shang(age_n_s,age_rate)
# 计算不同工作的经验熵
work = [5/15,10/15]
work_n1= [5/5,0]
work_n2 = [4/10,6/10]
# 计算两种不同的工作情况下的经验熵
work_n_s = [info_shang(work_n1),info_shang(work_n2)]
H_DW = c_shang(work,work_n_s)
# 计算房子条件下的经验熵
house = [6/15,9/15]
house_n1 = [1,0]
house_n2 = [3/9,6/9]
house_n_s = [info_shang(house_n1),info_shang(house_n2)]
H_DH = c_shang(house_n_s,house)
# 计算信贷条件熵
xin = [5/15,6/15,4/15]
xin_ns_n1 = [1/5,4/5]
xin_ns_n2 = [4/6,2/6]
xin_ns_n3 = [1,0]
xin_n_s = [info_shang(xin_ns_n1),info_shang(xin_ns_n2),info_shang(xin_ns_n3)]
H_DX = c_shang(xin,xin_n_s)
print('经验熵:{:.3f}'.format(H_D))
print('年龄的信息增益:{:.3f}'.format(H_D-H_DA))
print('工作的信息增益:{:.3f}'.format(H_D-H_DW))
print('房子的信息增益:{:.3f}'.format(H_D-H_DH))
print('信贷的信息增益:{:.3f}'.format(H_D-H_DX))

ID3算法

还是上面的例子，通过上面的计算得到房子$$A_3$$的信息增益值最大，所以选择特征$$A_3$$作为根节点。他把训练数据集D划分为两个子集$$D_1$$($$A_3$$取是)和$$D_2$$($$A_3$$取值为否)。由于$$D_1$$只有同一类的样本点，所以它成为一个叶子节点，节点的标记类型为"是"。

对$$D_2$$则需要从特征$$A_1$$(年龄)$$A_2$$(有工作)$$，$$A_4$$（信贷情况）中选择新的特征。计算各个特征的信息增益:

$$ \begin{equation} \begin{split} g(D_2,A_1)=H(D_2)-H(D_2|A_1)=0.918-0.667=0.251\ g(D_2,A_2)=H(D_2)-H(D_2|A_2)=0.918\ g(D_2,A_4)=H(D_2)-H(D_2|A_4)=0.474\ \end{split} \end{equation}

$$ 选择信息增益最大的特征$$A_2$$（有工作）作为节点的特征。由于$$A_2$$包含两个可能取值，从这一节点引出两个子节点，对应"是"(有工作)的子节点 ，包含3个样本，他们属于同一类，所以这是一个叶节点，类标记为"是"；另一个对应"否"(无工作)的子节点，包含6个样本，他们也属于同一类，所以这也是一个叶子节点，类标记为"否"。

ID3算法只有树的生成，所以该算法生成的树容易产生过拟合。

C4.5算法

C4.5算法对ID3进行了改进，C4.5在生成的过程中，用信息增益比来选择特征。

输入:训练数据集D，特征集A，阈值$$\epsilon$$

输出:决策树T

1. 如果D中所有实例属于同一类$$C_k$$,则T为单节点数，并将$$C_k$$作为该节点的类，返回T
2. 如果$$A=\emptyset$$,则置T为单节点树，并将D中实例数最大的类$$C_k$$作为该节点的类，返回T
3. 否则计算A中各个特征对D的信息增益比，选择信息增益比最大的特征$$A_g$$
4. 如果$$A_g$$的信息增益比小于阈值$$\epsilon$$,则置T为单节点数，并将D中实例数最大的类$$C_k$$作为该节点的类，返回T
5. 否则，对$$A_g$$的每一个可能值$$a_i$$,依$$A_g = a_i$$将D分割为子集和若干非空$$D_i$$,将$$D_i$$中实例数最大的类作为标记，构建子节点，由节点和子节点构成树T,返回T
6. 对节点i，以$$D_i$$为训练集，以$$A-{A_g}$$为特征集，递归调用1-5得到子树，返回$T_i$ C4.5算法优点:
7. 避免数据过拟合
8. 决定决策树的深度
9. 减少错误剪枝
10. 规定前向剪枝
11. 处理连续属性
12. 选择一个合适的属性选中衡量
13. 处理训练数据和缺失的属性值
14. 处理不同代价的属性
15. 提高计算效率

    Classification and Regression Trees(CART or C&RT)

    分类回归树(CART)也是决策树算法中的一种，由特征选择，树的生成和剪枝组成，既可以用于分类，也可以用于回归。

CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树为二叉树，内部节点特征的取值为"是"和"否"，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间(特征空间)划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。

决策树生成：基于训练数据集生成决策树，生成的决策树尽量大

决策树剪枝: 用验证数据集对已经生成的数进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准

决策树的生成就是递归的构建二叉决策树的过程。对回归书用平方误差最小化准则，对分类树用基尼指数(Gini index)最小化准则，进行特征选择，生成二叉树。

假设X和Y分别是输入和输出变量，并且Y是连续变量，给定训练数据集:

$$ D = {(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)}

$$

考虑如何生成回归树。

最小二乘回归树生成算法

输入:训练数据集$$D$$ 输出：回归树$$f(x)$$ 在训练数据集所在的输入空间中，递归的将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树:

1. 选择最优切分变量j和且分界点s，求解

$$ \min{j,s}\left[\min{c1}\sum{xi\in R_i(j,s)}(y_i-c_1)^2+\min{c2}\sum{x_i\in R_2(j,s)}(y_i-c_2)^2\right] 遍历变量j，对固定的切分变量j扫描切分点s，选择使得上式达到最小值的对(j,s)

1. 用选定的对(j,s)划分区域并决定相应的输出值:

$$

R1(j,s)={x|x^{(j)}\leq s},R_2(j,s)={x|x^{(j)}>s}\ \hat{c}_m=\frac{1}{N_m}\sum{x_i\in R_m(j,s)}y_i,x\in R_m,m=1,2

$$

1. 继续对两个子区域调用1,2，直到满足停止条件
2. 将输入空间划分为M个区域$$R_1,R_2,\cdots,R_M$$,生成决策树:

$$ f(x) = \sum_{m=1}^M\hat{c}_mI(x\in R_m)

$$ 分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。

(基尼指数)分类问题中，假设有K个类，样本点属于第k类的概率为$$p_k$$，则概率分布的基尼指数定义为:

$$ Gini(p) = \sum{k=1}^Kp)k(1-p_k)=1-\sum{k=1}^KP_k^2

$$ 对于二分类问题，若样本点属于第1个类的概率是p，则概率分布的基尼指数为$$ Gini(p) = 2p(1-p)

$$ 对于给定的样本集，其基尼指数为:

$$ Gini(D)=1-\sum_{k=1}^K(\frac{|C_k|}{|D|})^2

$$ 这里$$C_k$$是D中属于k类的样子集，K是类的个数。

如果样本集合D根据特征A是否取某一可能值a被分割成$$D_1$$和$$D_2$$两部分，即:

$$ D_1 = {(x,y)\inD|A(x)=a},D_2 = D-D_1

$$ 在特征A的条件下，集合D的基尼指数定义为:

$$ Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{D}Gini(D_2)

$$ 基尼指数$$Gini(D)$$表示集合D的不确定性，基尼指数Gini(D,A)表示经A=a分割后集合D的不确定性。基尼指数值越大，样本集合的不确定性也就越大。

CART生成算法: 输入:训练数据集D，停止计算的条件 输出:CART决策树 根据训练数据集，从根节点开始，递归的对每个节点进行如下操作，构建二叉决策树:

• 设节点的训练数据集为D，计算现有特征对该数据集的基尼指数。此时，对每个特征A，对其可能取的每个值a，根据样本点对A=a的测试为“是”或“否”将D分割成$$D_1$$和$$D_2$$两部分。计算A=a的基尼指数。
• 在苏有可能的特征A以及他们所有可能的切分点a中，选择基尼指数最小的特征和对应的切分点作为最优特征和最优切分点，依最优特征和最优切分点，从现节点生成两个子节点，将训练数据集依特征分配到两个子节点中去。
• 对两个子节点递归调用1,2直到满足停止条件。
• 生成CART决策树 算法停止计算的条件是结点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值(样本基本属于同一类)，或者没有更多特征。

基尼指数关注的姆比爱变量里面最大的类，它试图找到一个划分把它和其他区分开来。

完美的系列划分将会得到k个纯粹的子节点，每一个节点对应目标变量的一个类别。 如果误分类代价因素被加入，基尼指数试图把代价最大的类别区分开来。

在终止条件被满足，划分停止后，下一步是剪枝:

• 给数剪枝就是减掉“弱枝”，弱枝指的是在验证数据上误分类率高的树枝
• 为数剪枝会增大训练数据上错误分类率，但精简的数会提高新纪录上的预测能力
• 剪掉的是最没有预测能力的枝