索引

1.问题引入2.信息增益1.计算公式：2.实例计算：3.信息增益率1.计算公式：2.实例计算：4.基尼系数1.计算公式：2.实例计算：5.参考文献6.python代码

1.问题引入

首先，我们引入需进行决策树算法学习的数据集DDD，如下，

特征A=[′年龄′，′有工作′,′有自己的房子′,′信贷情况′]A = ['年龄'，'有工作', '有自己的房子', '信贷情况']A=[′年龄′，′有工作′,′有自己的房子′,′信贷情况′]

类别Y=[′类别′]Y = ['类别']Y=[′类别′]

接着摆在我们面前的是首先选择哪个特征，其次选择哪个特征，…，最后选择哪个特征。（就是先选择好的特征，再选择坏的特征）

问题引入： 怎么知道特征的好坏呢？如果一个特征A能使得数据分出来的类别最好，那么他就是最好的特征。(就是提供的信息最为准确），因此我们引入信息增益来衡量提供的信息准确度。

2.信息增益

1.计算公式：

G(D，A)=H(D)−H(D∣A)G(D，A) = H(D) - H(D|A)G(D，A)=H(D)−H(D∣A)

解释:G(D，A)G(D，A)G(D，A)指的是特征AAA对数据集DDD的信息增益；

H(D)H(D)H(D)指数据集DDD的(经验)熵；

那么问题来了，什么是熵呢？熵表示的是随机变量不确定性的度量。熵越大，表示这个系统越紊乱，越难确定一个东西。

H(D∣A)H(D|A)H(D∣A)指的是AAA条件下，数据集DDD的(经验)条件熵。

经验条件熵是什么呢？例如：H(D|A)指的是特征A条件下，数据集D的不确定性。换句话说，就是只知道特征A来确定数据D的类别，同样的，熵越大，越紊乱，越难确定类别。

注：

1.H(D)=−∑i=0npilog2piH(D) = -\sum_{i=0}^{n}p_{i}log_{2}p_{i} H(D)=−i=0∑n​pi​log2​pi​

i=1，...n(n为类别Y的数量)i=1，...n (n为类别Y的数量)i=1，...n(n为类别Y的数量)

pi是每一类出现的概率，例如p′是′=是出现的次数总数=915p_{i}是每一类出现的概率，例如p_{'是'}= \frac{是出现的次数} {总数}= \frac{9} {15}pi​是每一类出现的概率，例如p′是′​=总数是出现的次数​=159​

2.H(D∣A)=∑i=0npiH(Y∣X=xi)H(D|A) = \sum_{i=0}^{n}p_{i}H(Y|X = x_{i})H(D∣A)=i=0∑n​pi​H(Y∣X=xi​)

i=1，...n(n为特征A取值的个数)i=1，...n (n为特征A取值的个数)i=1，...n(n为特征A取值的个数)

2.实例计算：

我们拿上述数据集D的特征A='年龄’为例计算其信息增益：

1.

H(D)=−∑i=0npilog2pi=−615log2615−915log2915=0.971H(D) = -\sum_{i=0}^{n}p_{i}log_{2}p_{i}=-\frac{6}{15}log_{2}\frac{6}{15} -\frac{9}{15}log_{2}\frac{9}{15}=0.971H(D)=−i=0∑n​pi​log2​pi​=−156​log2​156​−159​log2​159​=0.971

此处类别’否’为6个样本，类别’是’为9个样本；

2.

H(D∣′年龄′)=∑i=0npiH(Y∣X=xi)=p′青年′H(Y∣X=x′青年′)+p′中年′H(Y∣X=x′中年′)+p′老年′H(Y∣X=x′老年′)=515∗(−25log225−35log235)+515∗(−25log225−35log235)+515∗(−15log215−45log245)=0.888H(D|'年龄')=\sum_{i=0}^{n}p_{i}H(Y|X = x_{i})=p_{'青年'}H(Y|X = x_{'青年'})+p_{'中年'}H(Y|X = x_{'中年'})+ p_{'老年'}H(Y|X = x_{'老年'})=\frac{5}{15}*(-\frac{2}{5}log_{2}\frac{2}{5} -\frac{3}{5}log_{2}\frac{3}{5})+\frac{5}{15}*(-\frac{2}{5}log_{2}\frac{2}{5} -\frac{3}{5}log_{2}\frac{3}{5})+\frac{5}{15}*(-\frac{1} {5}log_{2}\frac{1}{5} -\frac{4}{5}log_{2}\frac{4}{5})=0.888H(D∣′年龄′)=i=0∑n​pi​H(Y∣X=xi​)=p′青年′​H(Y∣X=x′青年′​)+p′中年′​H(Y∣X=x′中年′​)+p′老年′​H(Y∣X=x′老年′​)=155​∗(−52​log2​52​−53​log2​53​)+155​∗(−52​log2​52​−53​log2​53​)+155​∗(−51​log2​51​−54​log2​54​)=0.888

3.

G(D，′年龄′)=H(D)−H(D∣′年龄′)=0.971−0.888=0.083G(D，'年龄') = H(D) - H(D|'年龄') =0.971-0.888=0.083G(D，′年龄′)=H(D)−H(D∣′年龄′)=0.971−0.888=0.083

同理：G(D，′有工作′)=0.324，G(D，′有自己的房子′)=0.420，G(D，′信贷情况′)=0.363G(D，'有工作')=0.324， G(D，'有自己的房子')=0.420，G(D，'信贷情况')=0.363G(D，′有工作′)=0.324，G(D，′有自己的房子′)=0.420，G(D，′信贷情况′)=0.363

比较各个特征的信息增益值，发现G(D，′有自己的房子′)=0.420G(D，'有自己的房子')=0.420G(D，′有自己的房子′)=0.420最大，即选择特征’有自己的房子’作为最优特征。

信息增益准则偏向选择对数目较多的特征，因此引入信息增益率准则

3.信息增益率

1.计算公式：

gR(D，A)=(H(D)−H(D∣A))/HA(D)g_{R}(D，A) =(H(D) - H(D|A))/H_{A}(D)gR​(D，A)=(H(D)−H(D∣A))/HA​(D)

注：HA(D)=−∑i=0npilog2pi，i=1，...n(n为特征A取值的个数)H_{A}(D)= -\sum_{i=0}^{n}p_{i}log_{2}p_{i}，i=1，...n (n为特征A取值的个数)HA​(D)=−i=0∑n​pi​log2​pi​，i=1，...n(n为特征A取值的个数)

2.实例计算：

我们还是拿上述数据集D的特征A='年龄’为例计算其信息增益率：

1.

H′年龄′(D)=(−515log2515−515log2515−515log2515)=1.58H_{'年龄'}(D)=(-\frac{5} {15}log_{2}\frac{5}{15} -\frac{5} {15}log_{2}\frac{5}{15}-\frac{5} {15}log_{2}\frac{5}{15})=1.58H′年龄′​(D)=(−155​log2​155​−155​log2​155​−155​log2​155​)=1.58

2.

gR(D，′年龄′)=(H(D)−H(D∣′年龄′))/H′年龄′(D)=0.083/1.585=0.052g_{R}(D，'年龄') =(H(D) - H(D|'年龄'))/H_{'年龄'}(D)=0.083/1.585=0.052gR​(D，′年龄′)=(H(D)−H(D∣′年龄′))/H′年龄′​(D)=0.083/1.585=0.052

同理：gR(D，′有工作′)=0.352，gR(D，′有自己的房子′)=0.433，gR(D，′信贷情况′)=0.232g_{R}(D，'有工作') =0.352，g_{R}(D，'有自己的房子') =0.433，g_{R}(D，'信贷情况') =0.232gR​(D，′有工作′)=0.352，gR​(D，′有自己的房子′)=0.433，gR​(D，′信贷情况′)=0.232

比较各个特征的信息增益率值，发现G(D，′有自己的房子′)=0.433G(D，'有自己的房子')=0.433G(D，′有自己的房子′)=0.433最大，即选择特征’有自己的房子’作为最优特征。

4.基尼系数

1.计算公式：

1.数据集D的纯度：

Gini(Di)=∑i=1npi(1−pi)=1−∑i=1npi2Gini(D^{i})=\sum_{i=1}^{n}p_{i}(1-p_{i})=1-\sum_{i=1}^{n}p_{i}^{2}Gini(Di)=i=1∑n​pi​(1−pi​)=1−i=1∑n​pi2​

n为样本的类别数n为样本的类别数n为样本的类别数

可以得出Gini(p)Gini(p)Gini(p)反应了在数据集中抽取两个样本，其类别不一样的概率；

随机抽取两个样本，如果他们根据某个特征分类，其分类类别一样，即该特征非常适合分类，(换句话说我们的目的是使同一个分支的类别一致)，因此Gini(p)Gini(p)Gini(p)越小越好。

2.特征A的基尼系数：

Gini(D，A)=∑i=1npiGini(Di)Gini(D， A)=\sum_{i=1}^{n}p_{i}Gini(D^{i})Gini(D，A)=i=1∑n​pi​Gini(Di)

n为样本的类别数n为样本的类别数n为样本的类别数

2.实例计算：

我们还是拿上述数据集D的特征A='年龄’为例计算其基尼系数：

Gini(D，′年龄′)=∑i=1npiGini(Di)=p青年∗(1−(25)2−(35)2)+p中年(1−(25)2−(35)2)+p老年∗(1−(15)2−(45)2)=0.427Gini(D， '年龄')=\sum_{i=1}^{n}p_{i}Gini(D^{i})=p_{青年}*(1-(\frac{2}{5})^{2}-(\frac{3}{5})^{2})+p_{中年}(1-(\frac{2}{5})^{2}-(\frac{3}{5})^{2})+p_{老年}*(1-(\frac{1}{5})^{2}-(\frac{4}{5})^{2})=0.427Gini(D，′年龄′)=i=1∑n​pi​Gini(Di)=p青年​∗(1−(52​)2−(53​)2)+p中年​(1−(52​)2−(53​)2)+p老年​∗(1−(51​)2−(54​)2)=0.427

同理：Gini(D，′有工作′)=0.320，Gini(D，′有自己的房子′)=0.267，Gini(D，′信贷情况′)=0.284Gini(D，'有工作') =0.320，Gini(D，'有自己的房子') =0.267，Gini(D，'信贷情况') =0.284Gini(D，′有工作′)=0.320，Gini(D，′有自己的房子′)=0.267，Gini(D，′信贷情况′)=0.284

5.参考文献

[1]李航.统计学习方法（第二版）[M].清华大学出版社:北京,:67.

[2]周志华.机器学习[M].清华大学出版社:北京,:73.

6.python代码

在这里插入代码片