淘先锋技术网

首页 1 2 3 4 5 6 7

决策树分类算法（一）（信息熵，信息增益，基尼指数计算）

目录

例子：
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

一、信息量

在这里插入图片描述
:

I ( x ) = log ⁡ 2 1 p = − log ⁡ 2 p I(x)=\log_{2}{\frac{1}{p}}=-\log_{2}{p} I(x)=log2​p1​=−log2​p

假设中国足球队和巴西足球队曾经有过8次比赛，其中中国队胜1次。以U表示未来的中巴比赛中国队胜的事件，那么U的先验概率就是1/8，因此其信息量就是

I ( x ) = − log ⁡ 2 1 8 = 3 I(x)=-\log_{2}{\frac{1}{8}}=3 I(x)=−log2​81​=3

如果以 U ‾ \overline{U} U 表示巴西队胜，那么 U ‾ \overline{U} U的先验概率是 7 8 \frac{7}{8} 87​，其信息量就是

:

I ( U ‾ ) = − l o g 2 ( 7 8 ) = 0.19 I(\overline{U})=-log_{2}(\frac{7}{8})=0.19 I(U)=−log2​(87​)=0.19

二、信息熵

在这里插入图片描述
:

H ( X ) = E [ I ( x i ) ] = − ∑ i = 1 n p i × log ⁡ 2 p i H(X)=E[I(x_i)]=-\sum_{i=1}^{n}{p_i\times \log_2{p_i}} H(X)=E[I(xi​)]=−∑i=1n​pi​×log2​pi​

在这里插入图片描述

三、信息增益

样本集合的信息熵越大，说明各样本相对均衡，区别就越小，越不利于分类。
划分前后信息熵的减少量称为信息增益
G i n i ( A , F ( j ) = f ) = H ( A ) − H ( A , F ( j ) = f ) = H ( A ) − ( ∣ A 1 ∣ ∣ A ∣ H ( A 1 ) + ∣ A 2 ∣ ∣ A ∣ H ( A 2 ) ) , 其中 F ( j ) 是特征集 F 中第 j 个特征 f Gini(A,F^{(j)}=f)\\=H(A)-H(A,F^{(j)}=f)\\=H(A)-\biggl(\frac{\bigl|A_1\bigr|}{\big|A\big|}H(A_1)+\frac{\big|A_2\big|}{\big|A\big|}H(A_2)\biggr),\textcolor{Red}{其中F^{(j)}是特征集F中第j个特征f} Gini(A,F(j)=f)=H(A)−H(A,F(j)=f)=H(A)−( ​A ​ ​A1​ ​​H(A1​)+ ​A ​ ​A2​ ​​H(A2​)),其中F(j)是特征集F中第j个特征f

∵ 信息熵减少越多，说明区别越大，越有利于分类 \because 信息熵减少越多，说明区别越大，越有利于分类 ∵信息熵减少越多，说明区别越大，越有利于分类
∴ 所以信息增益大的，有利于分类 \therefore所以信息增益大的，有利于分类 ∴所以信息增益大的，有利于分类

在这里插入图片描述
解释：先把样本分为本科( 3 5 \frac{3}{5} 53​)和硕博( 2 5 \frac{2}{5} 52​)，然后3个本科里面2个不相亲，1个相亲( 2 3 × log ⁡ 2 2 3 + 1 3 × log ⁡ 2 1 3 \frac{2}{3}\times\log_{2}{\frac{2}{3}}+\frac{1}{3}\times\log_{2}{\frac{1}{3}} 32​×log2​32​+31​×log2​31​)，2个硕博里面都相亲 log ⁡ 2 1 \log_{2}{1} log2​1

:

H ( A 1 ) = − 2 3 × log ⁡ 2 2 3 − 1 3 × log ⁡ 2 1 3 H(A_1)=-\frac{2}{3}\times\log_{2}{\frac{2}{3}}-\frac{1}{3}\times\log_{2}{\frac{1}{3}} H(A1​)=−32​×log2​32​−31​×log2​31​

H ( A 2 ) = log ⁡ 2 1 H(A_2)=\log_{2}{1} H(A2​)=log2​1

H ( A , F ( 2 ) = 硕士 ) = 3 5 H ( A 1 ) + 2 5 H ( A 2 ) = 3 5 × ( − 2 3 × log ⁡ 2 2 3 − 1 3 × log ⁡ 2 1 3 ) + 2 5 × log ⁡ 2 1 = 0.551 H(A,F^{(2)}=硕士)=\frac{3}{5}H(A_1)+\frac{2}{5}H(A_2)=\frac{3}{5}\times(-\frac{2}{3}\times\log_{2}{\frac{2}{3}}-\frac{1}{3}\times\log_{2}{\frac{1}{3}})+\frac{2}{5}\times\log_{2}{1}=0.551 H(A,F(2)=硕士)=53​H(A1​)+52​H(A2​)=53​×(−32​×log2​32​−31​×log2​31​)+52​×log2​1=0.551

∵ 前面计算得到 H ( A ) = 0.971 ， H ( A , F ( 2 ) = 硕士 ) = 0.551 \because 前面计算得到H(A)=0.971，H(A,F^{(2)}=硕士)=0.551 ∵前面计算得到H(A)=0.971，H(A,F(2)=硕士)=0.551

∴ G i n i ( A , F ( 2 ) = 硕士 ) = H ( A ) − H ( A , F ( 2 ) = 硕士 ) = 0.97 − 0.551 = 0.42 \therefore Gini(A,F^{(2)}=硕士)\\=H(A)-H(A,F^{(2)}=硕士)\\=0.97-0.551=0.42 ∴Gini(A,F(2)=硕士)=H(A)−H(A,F(2)=硕士)=0.97−0.551=0.42

四、基尼指数

在这里插入图片描述
此概率的基尼分布指数为：

G i n i ( p ) = ∑ k = 1 K p k ( 1 − p k ) = 1 − ∑ k = 1 K p k 2 \textcolor{OrangeRed}{Gini(p)=\sum_{k=1}^{K}{p_k}{(1-p_k)}=1-\sum_{k=1}^{K}{p_{k}^2}} Gini(p)=∑k=1K​pk​(1−pk​)=1−∑k=1K​pk2​ ···························· 式 ( 4 − 1 ) 式(4-1) 式(4−1)

对于样本集A，其基尼指数为：
G i n i ( p ) = 1 − ∑ k = 1 K ( ∣ A k ∣ ∣ A ∣ ) 2 = 1 − ∑ k = 1 K ∣ A k ∣ 2 ∣ A ∣ 2 Gini(p)=1-\sum_{k=1}^{K}{(\frac{| A_k |}{|A|})^2}=1-\frac{\sum_{k=1}^{K}{|A_k|}^2}{|A|^2} Gini(p)=1−∑k=1K​(∣A∣∣Ak​∣​)2=1−∣A∣2∑k=1K​∣Ak​∣2​

在这里插入图片描述

在这里插入图片描述

书本原话：基尼指数也是一种不等性度量的指标，取值介于0-1之间，分类越不平衡，基尼指数就越小。
事实上，如果选择某一个特征来划分子集，其基尼指数越小，说明划分得越明确，划分的纯度越高！越有利于分类！！ \bold{事实上，如果选择某一个特征来划分子集，其基尼指数越小，说明划分得越明确，划分的纯度越高！越有利于分类！！} 事实上，如果选择某一个特征来划分子集，其基尼指数越小，说明划分得越明确，划分的纯度越高！越有利于分类！！

利用学历特征的决策值为“硕士”时划分样本集为两个子集，基尼指数为（结合式（4-1）和式（4-2））

G i n i ( A , F ( 2 ) = 硕士 ) = 3 5 × { 1 − [ ( 2 3 ) 2 + ( 1 3 ) 2 ] } + 2 5 × { 1 − ( 2 2 ) 2 } = 0.267 Gini(A,F^{(2)}=硕士)=\frac{3}{5}\times\lbrace 1-\lbrack (\frac{2}{3})^2+(\frac{1}{3})^2 \rbrack \rbrace+\frac{2}{5}\times\lbrace1-(\frac{2}{2})^2\rbrace=0.267 Gini(A,F(2)=硕士)=53​×{1−[(32​)2+(31​)2]}+52​×{1−(22​)2}=0.267

然后

G i n i ( A , F ( 0 ) = 30 岁 ) = 4 5 × { 1 − [ ( 3 4 ) 2 + ( 1 4 ) 2 ] } + 1 5 × { 1 − ( 1 1 ) 2 } = 0.3 Gini(A,F^{(0)}=30岁)=\frac{4}{5}\times\lbrace 1-\lbrack (\frac{3}{4})^2+(\frac{1}{4})^2 \rbrack \rbrace+\frac{1}{5}\times\lbrace1-(\frac{1}{1})^2\rbrace=0.3 Gini(A,F(0)=30岁)=54​×{1−[(43​)2+(41​)2]}+51​×{1−(11​)2}=0.3

五、建立决策树

思路 1 ：在样本集分裂时，要选择使分开后两个集合基尼指数最小的那个特征及其决策值作为分裂点。 \bold{思路1：在样本集分裂时，要选择使分开后两个集合基尼指数最小的那个特征及其决策值作为分裂点。} 思路1：在样本集分裂时，要选择使分开后两个集合基尼指数最小的那个特征及其决策值作为分裂点。
思路 2 ：在样本集分裂时，要选择使分开后两个集合信息增益数最大的那个特征及其决策值作为分裂点。 \bold{思路2：在样本集分裂时，要选择使分开后两个集合信息增益数最大的那个特征及其决策值作为分裂点。} 思路2：在样本集分裂时，要选择使分开后两个集合信息增益数最大的那个特征及其决策值作为分裂点。
案例一：相亲案例（本博客的内容，思路2）

编号年龄身高学历月收入是否相亲(标签)
135176本科20000否
228178硕士10000是
326172本科25000否
429173博士20000是
528174本科15000是

先选择样本中所有的特征 F ( i ) , i 从 0 到特征数减 1 ，也就是 i ∈ [ 0 , l e n ( F ) − 1 ] F^{(i)},i从0到特征数减1，也就是i\in[ 0 , len(F) - 1] F(i),i从0到特征数减1，也就是i∈[0,len(F)−1]，接着对该正在遍历的特征 F ( i ) F^{(i)} F(i)里面每个样本的每一个的这个特征值 F e a t u r e − v a l u e ( i ) Feature-value^{(i)} Feature−value(i)进行计算它的 信息增益 / 基尼指数 \bold{信息增益/基尼指数} 信息增益/基尼指数,比如我利用信息增益来划分区分度，因为 信息增益越大，说明划分得越明确，划分的纯度越高！越有利于分类！ \bold{信息增益越大，说明划分得越明确，划分的纯度越高！越有利于分类！} 信息增益越大，说明划分得越明确，划分的纯度越高！越有利于分类！,然后我用年龄这个特征，计算35岁，28岁，26岁，29岁，28岁的信息增益，发现28岁划分年龄样本时，28岁在年龄特征的信息增益最大，划分最明确，因此我用一个结果保存年龄的信息增益 c u r I n f o ← 0.32 ， b e s t I n f o ← 0.32 curInfo\gets0.32，bestInfo\gets0.32 curInfo←0.32，bestInfo←0.32然后遍历第二个特征，比如说是学历，然后计算本科，硕士，博士的信息增益，得到硕士的信息增益最大,curInfo=0.42，
∵ c u r I n f o 学历 = 0.42 > b e s t I n f o 年龄 = 0.32 ∴ b e s t I n f o ← c u r I n f o ∴ b e s t I n f o ← 0.42 ， 最后遍历完所有特征后，选择所有特征里面信息增益最大的那个特征，然后把 \because curInfo_{学历}=0.42>bestInfo_{年龄}=0.32 \\ \therefore bestInfo\gets curInfo \\ \therefore bestInfo \gets 0.42，\\最后遍历完所有特征后，选择所有特征里面信息增益最大的那个特征，然后把 ∵curInfo学历​=0.42>bestInfo年龄​=0.32∴bestInfo←curInfo∴bestInfo←0.42，最后遍历完所有特征后，选择所有特征里面信息增益最大的那个特征，然后把
样本根据当前信息增益最大的特征划分的样本，比如有左子集lson,右子集rson,其中当前节点是关于学历得特征（一开始计算得到学历的信息增益最大），就把本科划分到lson，硕博划分到rson，然后在左子树里面递归建树（只在本科里面进行下一步划分），在右子树里面递归建树（只在硕博里面进行下一步划分），最后完成建立分类树！

其中如果样本数越多，则分类树高度也更高，因为这是逐步细分的，比如我有一大堆的二维坐标， u = ( x , y ) ， x ∈ [ 0 , 100 ] , y ∈ [ 0 , 100 ] u=(x,y)，x\in[0,100],y\in[0,100] u=(x,y)，x∈[0,100],y∈[0,100],那么分类树可能会把这堆二维坐标划分为 x ∈ [ 0 , 50 ] , x ∈ ( 50 , 100 ] x\in[0,50],x\in(50,100] x∈[0,50],x∈(50,100],然后再次细分为 x ∈ [ 0 , 25 ] , x ∈ ( 25 , 50 ] , 至于实际上分类树怎么分类，取决于样本的基尼指数，分类树肯定先选择基尼指数小 / 信息增益更大的特征 x\in[0,25],x\in(25,50],至于实际上分类树怎么分类，取决于样本的基尼指数，分类树肯定先选择基尼指数小/信息增益更大的特征 x∈[0,25],x∈(25,50],至于实际上分类树怎么分类，取决于样本的基尼指数，分类树肯定先选择基尼指数小/信息增益更大的特征


案例二：贷款案例（b站一个up列举的例子，思路1）

编号有房者婚姻年收入拖欠贷款(标签)
1是单身125k否
2否已婚100k否
3否单身70k否
4是已婚120k否
5否离异95k是
6否已婚60k否
7是离异220k否
8否单身85k是
9否已婚75k否
10否单身90k是
A=是否拖欠贷款

G i n i ( A , F ( 0 ) = 是否有房 ) = 12 35 = 0.343 Gini(A,F^{(0)}={是否有房})=\frac{12}{35}=0.343 Gini(A,F(0)=是否有房)=3512​=0.343
G i n i ( A , F ( 1 ) = 是否婚姻 ) = 3 10 = 0.3 Gini(A,F^{(1)}={是否婚姻})=\frac{3}{10}=0.3 Gini(A,F(1)=是否婚姻)=103​=0.3
G i n i ( A , F ( 2 ) = 年薪 > 80 k ) = 12 35 = 0.343 Gini(A,F^{(2)}=年薪\gt{80k})=\frac{12}{35}=0.343 Gini(A,F(2)=年薪>80k)=3512​=0.343
是否结婚这个特征划分的子集的基尼指数最小，因此选择是否结婚来划分子集，建立根节点
然后发现已婚的的都不欠款，因此不需要再划分子集，然后单身和离异这部分的人可以继续划分，在这个 单身和离异这 6 个人当中 \bold{单身和离异这6个人当中} 单身和离异这6个人当中计算是否有房和年收入是否大于80k来建立决策树，
在这六个人当中,
G i n i ( A , F ( 0 ) = 房 ) = 1 4 Gini(A,F^{(0)}=房)=\frac{1}{4} Gini(A,F(0)=房)=41​
G i n i ( A , F ( 2 ) = 收入 ) = 2 5 Gini(A,F^{(2)}=收入)=\frac{2}{5} Gini(A,F(2)=收入)=52​
因此第二个特征选择较小者，第二个特征应该选择是否有房，因为只有三个特征，所以最后一个特征只能选择年收入是否大于80k来建立决策树
第五节内容来自下面这个视频链接！点击我->视频链接