600字范文 > 决策树分类算法（一）（信息熵信息增益基尼指数计算）

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

时间：2019-10-07 06:54:48

一、信息量

I ( x ) = log ⁡ 2 1 p = − log ⁡ 2 p I(x)=\log_{2}{\frac{1}{p}}=-\log_{2}{p} I(x)=log2p1=−log2p

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

I ( x ) = − log ⁡ 2 1 8 = 3 I(x)=-\log_{2}{\frac{1}{8}}=3 I(x)=−log281=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=1npi×log2pi

三、信息增益

样本集合的信息熵越大，说明各样本相对均衡，区别就越小，越不利于分类。

划分前后信息熵的减少量称为信息增益

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×log232+31×log231)，2个硕博里面都相亲 log ⁡ 2 1 \log_{2}{1} log21

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×log232−31×log231

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

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)=硕士)=53H(A1)+52H(A2)=53×(−32×log232−31×log231)+52×log21=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=1Kpk(1−pk)=1−∑k=1Kpk2 ···························· 式 ( 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）

先选择样本中所有的特征 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）

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来建立决策树

第五节内容来自下面这个视频链接！点击我->视频链接

【数据挖掘】决策树零基础入门教程，手把手教你学决策树！

六、代码：信息熵，信息增益，基尼指数计算

splitInfo.py

# coding:UTF-8import mathdef sum_of_each_label(samples):'''统计样本集中每一类标签label出现的次数para samples：list,样本的列表，每样本也是一个列表，样本的最后一项为labelretrurn sum_of_each_label：dictionary,各类样本的数量'''labels = [sample[-1] for sample in samples] #sample是相亲的一个人的个人信息，最后一个代表是否相亲成功sum_of_each_label = dict([(i,labels.count(i)) for i in labels])#labels是列表，count(i)是计算i在列表labels里面出现的次数return sum_of_each_label#返回一个字典，# 字典内容如 0->2,1->3,表示0出现2次，1出现3次def info_entropy(samples):'''计算样本集的信息熵para samples：list,样本的列表，每样本也是一个列表，样本的最后一项为labelreturn infoEntropy:float,样本集的信息熵'''# 统计每类标签的数量label_counts = sum_of_each_label(samples)# 计算信息熵 infoEntropy = -∑(p * log(p))infoEntropy = 0.0sumOfSamples = len(samples)for label in label_counts:p = float(label_counts[label])/sumOfSamplesinfoEntropy -= p * math.log(p,2) return infoEntropy def split_samples(samples, f, fvalue):'''切分样本集para samples：list,样本的列表，每样本也是一个列表，样本的最后一项为label，其它项为特征para f: int,切分的特征，用样本中的特征次序表示para fvalue: float or int，切分特征的决策值output lsamples: list, 切分后的左子集output rsamples: list, 切分后的右子集''' lsamples = []rsamples = []for s in samples:#s是相亲的一个人的个人信息，f是切分特征if s[f] < fvalue:lsamples.append(s)else:rsamples.append(s)return lsamples, rsamples def info_gain(samples, f, fvalue):'''计算切分后的信息增益para samples：list,样本的列表，每样本也是一个列表，样本的最后一项为label，其它项为特征para f: int,切分的特征，用样本中的特征次序表示para fvalue: float or int，切分特征的决策值output : float, 切分后的信息增益'''lson, rson = split_samples(samples, f, fvalue)return info_entropy(samples) - (info_entropy(lson)*len(lson) + info_entropy(rson)*len(rson))/len(samples)def gini_index(samples):'''计算样本集的Gini指数para samples：list,样本的列表，每样本也是一个列表，样本的最后一项为label，其它项为特征output: float, 样本集的Gini指数'''sumOfSamples = len(samples) if sumOfSamples == 0:return 0 label_counts = sum_of_each_label(samples)gini = 0for label in label_counts:gini = gini + pow(label_counts[label], 2)return 1 - float(gini) / pow(sumOfSamples, 2)def gini_index_splited(samples, f, fvalue):'''计算切分后的基尼指数para samples：list,样本的列表，每样本也是一个列表，样本的最后一项为label，其它项为特征para f: int,切分的特征，用样本中的特征次序表示para fvalue: float or int，切分特征的决策值output : float, 切分后的基尼指数'''lson, rson = split_samples(samples, f, fvalue)return (gini_index(lson)*len(lson) + gini_index(rson)*len(rson))/len(samples)if __name__ == "__main__":# 表3-1 某人相亲数据，依次为年龄、身高、学历、月薪特征和是否相亲标签blind_date = [[35, 176, 0, 20000, 0],[28, 178, 1, 10000, 1],[26, 172, 0, 25000, 0],[29, 173, 2, 20000, 1],[28, 174, 0, 15000, 1]]# 计算集合的信息熵print(info_entropy(blind_date))# OUTPUT:0.9709505944546686# 计算集合的信息增益print(info_gain(blind_date,1,175)) # 按身高175切分# OUTPUT:0.01997309402197478print(info_gain(blind_date,2,1)) # 按学历是否硕士切分# OUTPUT:0.4199730940219748print(info_gain(blind_date,3,10000)) # 按月薪10000切分# OUTPUT:0.0# 计算集合的基尼指数print(gini_index(blind_date))# OUTPUT:0.48# 计算切分后的基尼指数print(gini_index_splited(blind_date,1,175)) # 按身高175切分# OUTPUT:0.4666666666666667print(gini_index_splited(blind_date,2,1)) # 按学历是否硕士切分# OUTPUT:0.26666666666666666print(gini_index_splited(blind_date,3,10000)) # 按月薪10000切分# OUTPUT:0.48print(gini_index_splited(blind_date,0,30)) # 按年龄30切分# OUTPUT:0.3

decision_bitree.py

# coding:UTF-8from splitInfo import info_entropy, gini_index, split_samples, sum_of_each_labelclass biTree_node:'''二叉树节点'''def __init__(self, f=-1, fvalue=None, leafLabel=None, l=None, r=None, splitInfo="gini"):'''类初始化函数para f: int,切分的特征，用样本中的特征次序表示para fvalue: float or int，切分特征的决策值para leafLable: int,叶节点的标签para l: biTree_node指针，内部节点的左子树para r: biTree_node指针，内部节点的右子树para splitInfo="gini": string, 切分的标准，可取值'infogain'和'gini'，分别表示信息增益和基尼指数'''self.f = fself.fvalue = fvalueself.leafLabel = leafLabelself.l = lself.r = rself.splitInfo = splitInfodef build_biTree(samples, splitInfo="gini"):'''构建树para samples：list,样本的列表，每样本也是一个列表，样本的最后一项为label，其它项为特征para splitInfo="gini": string, 切分的标准，可取值'infogain'和'gini'，分别表示信息增益和基尼指数return biTree_node:Class biTree_node,二叉决策树的根结点'''if len(samples) == 0:return biTree_node()if splitInfo != "gini" and splitInfo != "infogain":return biTree_node()bestInfo = 0.0bestF = NonebestFvalue = Nonebestlson = Nonebestrson = Noneif splitInfo == "gini":curInfo = gini_index(samples) # 当前集合的基尼指数else:curInfo = info_entropy(samples) # 当前集合的信息熵sumOfFeatures = len(samples[0]) - 1 # 样本中特征的个数for f in range(0, sumOfFeatures): # 遍历每个特征featureValues = [sample[f] for sample in samples]for fvalue in featureValues: # 遍历当前特征的每个值lson, rson = split_samples(samples, f, fvalue)if splitInfo == "gini":# 计算分裂后两个集合的基尼指数info = (gini_index(lson) * len(lson) + gini_index(rson) * len(rson)) / len(samples)else:# 计算分裂后两个集合的信息熵info = (info_entropy(lson) * len(lson) + info_entropy(rson) * len(rson)) / len(samples)gain = curInfo - info # 计算基尼指数减少量或信息增益# 能够找到最好的切分特征及其决策值，左、右子树为空说明是叶子节点if gain > bestInfo and len(lson) > 0 and len(rson) > 0:bestInfo = gainbestF = fbestFvalue = fvaluebestlson = lsonbestrson = rsonif bestInfo > 0.0:l = build_biTree(bestlson)r = build_biTree(bestrson)return biTree_node(f=bestF, fvalue=bestFvalue, l=l, r=r, splitInfo=splitInfo)else: # 如果bestInfo==0.0，说明没有切分方法使集合的基尼指数或信息熵下降了，说明这个sample样本里面非常纯了，#只有1类标签，要么全是0，要么全是1，要么全是相亲的，要么全都不相亲！label_counts = sum_of_each_label(samples)# 返回该集合中最多的类别作为叶子节点的标签return biTree_node(leafLabel=max(label_counts, key=label_counts.get), splitInfo=splitInfo)def predict(sample, tree):'''对样本sample进行预测para sample:list,需要预测的样本para tree:biTree_node,构建好的分类树return: biTree_node.leafLabel,所属的类别'''# 1、只是树根if tree.leafLabel != None:return tree.leafLabelelse:# 2、有左右子树sampleValue = sample[tree.f]branch = Noneif sampleValue >= tree.fvalue:branch = tree.relse:branch = tree.lreturn predict(sample, branch)def print_tree(tree, level='0'):'''简单打印一颗树的结构para tree:biTree_node,树的根结点para level='0':str, 节点在树中的位置，用一串字符串表示，0表示根节点，0L表示根节点的左孩子，0R表示根节点的右孩子 '''if tree.leafLabel != None:print('*' + level + '-' + str(tree.leafLabel)) # 叶子节点用*表示，并打印出标签else:print('+' + level + '-' + str(tree.f) + '-' + str(tree.fvalue)) # 中间节点用+表示，并打印出特征编号及其划分值print_tree(tree.l, level + 'L')print_tree(tree.r, level + 'R')if __name__ == "__main__":# 表3-1 某人相亲数据blind_date = [[35, 176, 0, 20000, 0],[28, 178, 1, 10000, 1],[26, 172, 0, 25000, 0],[29, 173, 2, 20000, 1],[28, 174, 0, 15000, 1]]print("信息增益二叉树：")tree = build_biTree(blind_date, splitInfo="infogain")print_tree(tree)print('信息增益二叉树对样本进行预测的结果：')test_sample = [[24, 178, 2, 17000],[27, 176, 0, 25000],[27, 176, 0, 10000]]for x in test_sample:print(predict(x, tree))print("基尼指数二叉树：")tree = build_biTree(blind_date, splitInfo="gini")print_tree(tree)print('基尼指数二叉树对样本进行预测的结果：')test_sample = [[24, 178, 2, 17000],[27, 176, 0, 25000],[27, 176, 0, 10000]]for x in test_sample:print(predict(x, tree))