决策树中的相关概念

• 这里不是将决策树的构建过程，而是回头审视着其中出现的一些数学上某些概念。

决策树处理，可能的结果：

决策树的目标

• 由特征来进行分支。
• 寻找出一组分支结构。
• 从概率角度出发，将实例分配到条件概率（分类依据的特征就是条件）最大那一类中。
• 从所有的决策树中选择最优的决策树是一个NP完全问题。
• 通常采用启发式算法（只选取当前用来分类最好的特征）求解决策树，得到次最优解。
• 实际操作上：选取当前最好的特征，并根据该特征对数据集进行划分，分成小的数据集；在对各个小的数据集，再选取最优的特征，递归以上的操作，直至全部分类完毕。
• 为了方式过拟合，不需要分支到很细化，进行剪枝操作（预剪枝，后剪枝）。

随机变量

• 随机变量本质上就是一个函数，将一个事件映射到数值。随机变量就是“数值化”的实验结果。
• 根据不同的实验结果的差异，随机变量的值也就随机产生。
• 举个例子：实验结果是描述性的词汇，用文字信息来进行描述很繁琐（太low了），最主要的就是没法进行数值分析。那么必然要从文字信息映射到数值信息，这样随机变量就产生了。
  • 比如”晴天“用1表示，阴天用”0“表示；抛硬币，”正面“映射到”1“，反面映射到”0“。等等

熵（entropy）

信息熵(Information Entropy)

• 熵（entropy）用来衡量随机变量的不确定性。

• 变量的不确定性越大，熵值也越大。（这个和物理上描述系统的熵很相似，同样描述混乱度（不确定性））。
  $物理上：S=kln(\Omega)$物理上：S=kln(Ω)

• 数学上的定义：

  • 设$X$X是一个取有限个值的离散随机变量，其概率分布为：
    $P(X=x_i)=p_i,i=1,2,\cdots,n$P(X=xi​)=pi​,i=1,2,⋯,n
    则随机变量$X$X的熵定义为：
    $H(X)=-\sum_{i=1}^{n}(p_i *log (p_i))$H(X)=−i=1∑n​(pi​∗log(pi​))

  • 注：

    • 通常，上式中的对数为$2$2为底时，熵的单位为$bit$bit（比特）；以自然对数$e$e为底，熵的单位为$nat$nat（纳特）。

举个栗子

• 设有一个随机变量$X$X只有两个取值$0$0或$1$1。则$X$X的分布为：
  $P(X=1)=p,P(X=0)=1-p,p \in [0,1]$P(X=1)=p,P(X=0)=1−p,p∈[0,1]

  • $p$p值也可是实验中事件出现的频率。

• 熵：
  $H(X)=-\sum_{i=1}^{n}(p_i *log (p_i))=-(p*log_2(p)+(1-p)*log_2(1-p))$H(X)=−i=1∑n​(pi​∗log(pi​))=−(p∗log2​(p)+(1−p)∗log2​(1−p))

• 熵$H(X)$H(X)与概率$P$P的曲线如下图所示：

  

• 用解析法求上述$H(X)$H(X)，得到在$p=\frac{1}{2}$p=21​时，取得最大值。

  • $p=\frac{1}{2}$p=21​，$H(X)$H(X)值最大，此时不确定性最高。因为$0,1$0,1选择的概率是一样的，最平均，选取的不确定性最大。

条件熵（Conditional entropy）

• 如果$H(Y|X=x)$H(Y∣X=x)是随机变量$Y$Y在随机变量$X$X在特定$x$x条件下的熵，那么$H(Y|X)$H(Y∣X)就是$H(Y|X)$H(Y∣X)在$X$X取遍所有可能$x$x后平均的的结果。说白就是将分类后的构成的各个子系统的熵之和，作为该分类下系统的熵。

• 条件熵$H(Y|X)$H(Y∣X)表示在已知在随机变量$X$X的条件下，随机变量$Y$Y的不确定性：
  $H(Y|X)=\sum_{x \in X}(p(x)H(Y|x))\\=-\sum_{x \in X}p(x)\sum_{y \in Y}p(y|x)log(p(y|x))$H(Y∣X)=x∈X∑​(p(x)H(Y∣x))=−x∈X∑​p(x)y∈Y∑​p(y∣x)log(p(y∣x))

到这里计算就够了，但是可以再往下推导：
$=-\sum_{x \in X}\sum_{y \in Y}(p(x)*p(y|x)*log(p(y|x)))\\=-\sum_{x \in X}\sum_{y \in Y}(p(x,y)*log(p(y|x)))\\=-\sum_{x \in X,y \in Y}(p(x,y)*log(p(y|x)))\\=-\sum_{x \in X,y \in Y}(p(x,y)*log(\frac{p(x,y)}{p(x)})\\= \sum_{x \in X,y \in Y}(p(x,y)*log(\frac{p(x)}{p(x,y)})$=−x∈X∑​y∈Y∑​(p(x)∗p(y∣x)∗log(p(y∣x)))=−x∈X∑​y∈Y∑​(p(x,y)∗log(p(y∣x)))=−x∈X,y∈Y∑​(p(x,y)∗log(p(y∣x)))=−x∈X,y∈Y∑​(p(x,y)∗log(p(x)p(x,y)​)=x∈X,y∈Y∑​(p(x,y)∗log(p(x,y)p(x)​)

举个栗子

1. 设随机变量$Y={嫁，不嫁}$Y=嫁，不嫁，初始状态$H(Y)$H(Y):

$H(Y)=-(\frac{6}{12}\log_2(\frac{6}{12})+\frac{6}{12}log_2{\frac{6}{12}})=1.0$H(Y)=−(126​log2​(126​)+126​log2​126​)=1.0

2. 引入随机变量$X(长相)={帅，不帅}$X(长相)=帅，不帅。

   • $p(x=帅)=\frac{4}{12}=\frac{1}{3}$p(x=帅)=124​=31​，$p(x=不帅)=\frac{2}{3}$p(x=不帅)=32​；

   • $H(Y|x=帅)=-(p(y=嫁|x=帅)*log_2(p(y=嫁|x=帅))+p(y=不嫁|x=帅)*log_2(p(y=不嫁|x=帅))\\ =-(\frac{5}{8}log_2\frac{5}{8}+\frac{3}{8}log_2{\frac{3}{8}})\doteq0.954$H(Y∣x=帅)=−(p(y=嫁∣x=帅)∗log2​(p(y=嫁∣x=帅))+p(y=不嫁∣x=帅)∗log2​(p(y=不嫁∣x=帅))=−(85​log2​85​+83​log2​83​)≐0.954

   • 同理：
     $H(Y|x=不帅)=-(\frac{3}{4}log_2\frac{3}{4}+\frac{1}{4}\log_2{\frac{1}{4}})\doteq 0.811$H(Y∣x=不帅)=−(43​log2​43​+41​log2​41​)≐0.811

   • 所以，条件熵$H(Y|X=长相)$H(Y∣X=长相)
     $H(Y|X=长相)=p(x=帅)H(Y|x=帅)+p(x=不帅)H(Y|x=不帅)\\=\frac{1}{3}*0.954+\frac{2}{3}*0.811\doteq 0.859$H(Y∣X=长相)=p(x=帅)H(Y∣x=帅)+p(x=不帅)H(Y∣x=不帅)=31​∗0.954+32​∗0.811≐0.859

3. 显然$0.859<1$0.859<1，说明熵减小了，系统的不稳定性降低了，分类效果比之间好了。

• 所以，引入熵的概念和条件熵（将分类视为一种条件）的概念后，使得系统的熵减小最快的分类方法，（最快使得系统稳定，更纯），就是最好的分类方法（以熵减小的角度出发）。

信息增益(Information Gain)（ID3算法）

• 特征$A$A对数据集$D$D的信息增益：表示为$Gain(D,A)$Gain(D,A)，定义为集合$D$D的经验熵减去在特征$A$A给定下的$D$D的经验条件熵$H(D,A)$H(D,A)，即
  $g(D,A)=H(D)-H(D,A)$g(D,A)=H(D)−H(D,A)

• 思考：我们希望这个差值是大还是小呢？换句话说，这个差值的大小对于选择分类的特征的优劣有什么反应吗？

  • 一个系统越确定（越稳定），分类效果越明显，其熵值越小。
  • 假设原始系统的熵值为$H(D)=h$H(D)=h。在引入某一个特征$A$A后，使得系统完美分类，此时条件熵$H(D|A)=0$H(D∣A)=0。根据信息增益的定义$g(D,A)=H(D)-H(D,A)$g(D,A)=H(D)−H(D,A)，此时信息增益$g=h$g=h。
    • 所以信息增益越大，说明引入的特征对于分类效果越明显。

• 结论：

  1. 信息增益值越大，说明选择用于分类的特征越好，正是算法当前所需要的特征。
  2. 在递归选择过程中，总是选择能是信息增益值更大的特征。
  3. 信息增益值越大，整个系统的熵值减小的就越快，系统的不稳定性就越来越小。

• 缺点：信息增益偏向取值较多的特征

• 原因：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较 偏向取值较多的特征

信息增益率(Information Gain Ratio)，（C4.5算法）

• 用信息增益作为评判划分属性的方法其实是有一定的缺陷的，书上说，信息增益准则对那些属性的取值比较多的属性有所偏好，也就是说，采用信息增益作为判定方法，会倾向于去选择属性取值比较多的属性。

• 信息增益率$g_{R}(D,A)$gR​(D,A)：

  信息增益比 = 惩罚参数 * 信息增益

$g_{R}(D,A)=\frac{g(D,A)}{H_A(D)}=\frac{1}{H_A(D)}g(D,A)$gR​(D,A)=HA​(D)g(D,A)​=HA​(D)1​g(D,A)

其中，惩罚系数为$\frac{1}{H_A(D)}$HA​(D)1​。

$H_A{D}$HA​D的计算：
$H_A(D)=-\sum_{i=1}^{n}\frac{|D_i|}{|D|}log(\frac{|D_i|}{|D|})$HA​(D)=−i=1∑n​∣D∣∣Di​∣​log(∣D∣∣Di​∣​)
举例说明：

• 如上面的将$长相$长相为分类的特征
  $H_A(D)=h_{长相}(D)=-(\frac{4}{12}log_2\frac{4}{12}+ \frac{8}{12}log_2{\frac{8}{12}})$HA​(D)=h长相​(D)=−(124​log2​124​+128​log2​128​)

缺点：信息增益比偏向取值较少的特征

原因： 当特征取值较少时$H_A(D)$HA​(D)的值较小，因此其倒数较大，因而信息增益比较大。因而偏向取值较少的特征。

举例说明：
$P=-(\frac{1}{3}log_2{\frac{1}{3}}+\frac{1}{3}log_2{\frac{1}{3}}+\frac{1}{3}log_2{\frac{1}{3}}) >-(\frac{1}{2}log_2\frac{1}{2}+\frac{1}{2}log_2\frac{1}{2})=S$P=−(31​log2​31​+31​log2​31​+31​log2​31​)>−(21​log2​21​+21​log2​21​)=S
所以：
$\frac{1}{P}<\frac{1}{S}$P1​<S1​
因为原则总是选择信息增益率大的，所以信息增益比偏向取值较少的特征，这样会其值更大些。

基尼指数（Gini），（CART，分类回归树）

• 基尼指数，又称基尼不纯度，表示在样本集合中一个随机选中的样本被分错的概率。
• Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。我们希望它的值越小越好（纯度越高）。

假设几个有$k$k个类别，则：
$Gini(D)=1-\sum_{k=1}^{K}(\frac{|C_k|}{|D|})^2$Gini(D)=1−k=1∑K​(∣D∣∣Ck​∣​)2
给定特征划分后的$Gini(D,A)$Gini(D,A)：
$Gini(D,A)=\sum_{i=1}^{n}\frac{|D_i|}{|D|}gini(D_i)$Gini(D,A)=i=1∑n​∣D∣∣Di​∣​gini(Di​)
特殊的，假定根据特征$A$A分类后，将数据分成了两类$D_1,D_2$D1​,D2​:
$Gini(D,A)=\frac{|D_1|}{|D|}gini(D_1)+\frac{|D_2|}{|D|}gini(D_2)$Gini(D,A)=∣D∣∣D1​∣​gini(D1​)+∣D∣∣D2​∣​gini(D2​)
其他：

使用numpy生成等差数列：np.linespace();生成等比数列：np.logspace()

参考：

1. https://zh.wikipedia.org/zh-hans/%E5%86%B3%E7%AD%96%E6%A0%91%E5%AD%A6%E4%B9%A0
2. https://zhuanlan.zhihu.com/p/26703300
3. https://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html
4. https://www.cnblogs.com/muzixi/p/6566803.html
5. https://blog.****.net/moakun/article/details/83217455
6. 这是一个连接
7. https://blog.****.net/xwd18280820053/article/details/70739368