贷款申请决策树构建样本数据集与ID3算法实现

以下是一个贷款申请样本数据集，试根据以下数据构建一个决策树。/n/n| 序号 | 年龄 | 有工作 | 有自己的房子 | 信贷情况 | 是否获得贷款 | /n| --- | --- | --- | --- | --- | --- | /n| 1 | 青年 | 否 | 否 | 一般 | 否 | /n| 2 | 青年 | 否 | 否 | 好 | 否 | /n| 3 | 青年 | 是 | 否 | 好 | 是 | /n| 4 | 青年 | 是 | 是 | 一般 | 是 | /n| 5 | 青年 | 否 | 否 | 一般 | 否 | /n| 6 | 中年 | 否 | 否 | 一般 | 否 | /n| 7 | 中年 | 否 | 否 | 好 | 否 | /n| 8 | 中年 | 是 | 是 | 好 | 是 | /n| 9 | 中年 | 否 | 是 | 非常好 | 是 | /n| 10 | 中年 | 否 | 是 | 非常好 | 是 | /n| 11 | 老年 | 否 | 是 | 非常好 | 是 | /n| 12 | 老年 | 否 | 是 | 好 | 是 | /n| 13 | 老年 | 是 | 否 | 好 | 是 | /n| 14 | 老年 | 是 | 否 | 非常好 | 是 | /n| 15 | 老年 | 否 | 否 | 一般 | 否 | /n/n根据上述数据，可以使用ID3算法构建决策树，步骤如下：/n/n1. 计算所有样本的信息熵，以是否获得贷款作为分类标准。计算公式为：$Entropy = -/sum_{i=1}^{n}p_i/log_2p_i$，其中$p_i$为该分类下的样本占比。/n/n 获得贷款的样本数为9，未获得贷款的样本数为6，因此$p_1=9/15, p_2=6/15$，则信息熵为：/n /n $Entropy = -/frac{9}{15}/log_2/frac{9}{15}-/frac{6}{15}/log_2/frac{6}{15}=0.971$/n/n2. 对每个特征计算信息增益，选择信息增益最大的特征作为当前节点的划分特征。计算公式为：$IG(D,F)=Entropy(D)-/sum_{v/in V} /frac{|D_v|}{|D|}Entropy(D_v)$，其中$D$为样本集合，$F$为特征，$V$为特征$F$的取值集合，$D_v$为特征$F$取值为$v$的样本集合。/n/n 对年龄、有工作、有自己的房子和信贷情况依次计算信息增益。/n/n 对于年龄，可以将样本集划分为青年、中年和老年三个子集。计算：/n/n $IG(D, '年龄')=Entropy(D)-[/frac{5}{15}Entropy('青年')+/frac{5}{15}Entropy('中年')+/frac{5}{15}Entropy('老年')]$ /n /n 青年样本中有2个未获得贷款，3个获得贷款，因此$Entropy('青年')=-/frac{2}{5}/log_2/frac{2}{5}-/frac{3}{5}/log_2/frac{3}{5}=0.971$。/n /n 中年样本中有4个未获得贷款，1个获得贷款，因此$Entropy('中年')=-/frac{4}{5}/log_2/frac{4}{5}-/frac{1}{5}/log_2/frac{1}{5}=0.722$。/n /n 老年样本中有0个未获得贷款，5个获得贷款，因此$Entropy('老年')=-/frac{0}{5}/log_2/frac{0}{5}-/frac{5}{5}/log_2/frac{5}{5}=0$。/n /n 因此，年龄的信息增益为：/n /n $IG(D, '年龄')=0.971-[/frac{5}{15}/times0.971+/frac{5}{15}/times0.722+/frac{5}{15}/times0]=0.247$/n /n 对于有工作，可以将样本集划分为是和否两个子集。计算：/n/n $IG(D, '有工作')=Entropy(D)-[/frac{6}{15}Entropy('是')+/frac{9}{15}Entropy('否')]$ /n /n 是样本中有1个未获得贷款，5个获得贷款，因此$Entropy('是')=-/frac{1}{6}/log_2/frac{1}{6}-/frac{5}{6}/log_2/frac{5}{6}=0.65$。/n /n 否样本中有8个未获得贷款，1个获得贷款，因此$Entropy('否')=-/frac{8}{9}/log_2/frac{8}{9}-/frac{1}{9}/log_2/frac{1}{9}=0.503$。/n /n 因此，有工作的信息增益为：/n /n $IG(D, '有工作')=0.971-[/frac{6}{15}/times0.65+/frac{9}{15}/times0.503]=0.029$/n /n 对于有自己的房子，可以将样本集划分为是和否两个子集。计算：/n/n $IG(D, '有自己的房子')=Entropy(D)-[/frac{7}{15}Entropy('是')+/frac{8}{15}Entropy('否')]$ /n /n 是样本中有3个未获得贷款，4个获得贷款，因此$Entropy('是')=-/frac{3}{7}/log_2/frac{3}{7}-/frac{4}{7}/log_2/frac{4}{7}=0.985$。/n /n 否样本中有3个未获得贷款，5个获得贷款，因此$Entropy('否')=-/frac{3}{8}/log_2/frac{3}{8}-/frac{5}{8}/log_2/frac{5}{8}=0.954$。/n /n 因此，有自己的房子的信息增益为：/n /n $IG(D, '有自己的房子')=0.971-[/frac{7}{15}/times0.985+/frac{8}{15}/times0.954]=0.001$/n /n 对于信贷情况，可以将样本集划分为好、一般和非常好三个子集。计算：/n/n $IG(D, '信贷情况')=Entropy(D)-[/frac{6}{15}Entropy('好')+/frac{5}{15}Entropy('一般')+/frac{4}{15}Entropy('非常好')]$ /n /n 好样本中有1个未获得贷款，5个获得贷款，因此$Entropy('好')=-/frac{1}{6}/log_2/frac{1}{6}-/frac{5}{6}/log_2/frac{5}{6}=0.65$。/n /n 一般样本中有4个未获得贷款，1个获得贷款，因此$Entropy('一般')=-/frac{4}{5}/log_2/frac{4}{5}-/frac{1}{5}/log_2/frac{1}{5}=0.722$。/n /n 非常好样本中有4个未获得贷款，0个获得贷款，因此$Entropy('非常好')=-/frac{4}{4}/log_2/frac{4}{4}-/frac{0}{4}/log_2/frac{0}{4}=0$。/n /n 因此，信贷情况的信息增益为：/n /n $IG(D, '信贷情况')=0.971-[/frac{6}{15}/times0.65+/frac{5}{15}/times0.722+/frac{4}{15}/times0]=0.151$/n/n 可以发现，年龄的信息增益最大，因此选择年龄作为当前节点的划分特征。/n/n3. 对于年龄的每个取值，递归地构建子树。/n/n 对于青年子集，可以发现所有样本都属于同一类别（获得贷款），因此直接将该节点标记为“获得贷款”。/n /n 对于中年子集，可以发现4个未获得贷款、1个获得贷款，因此将该节点标记为“未获得贷款”。/n /n 对于老年子集，可以发现所有样本都属于同一类别（获得贷款），因此直接将该节点标记为“获得贷款”。/n /n 构建完子树后，得到以下决策树：/n /n /n 年龄/n / | // /n 青年 中年 老年/n | | |/n 获得 未获得 获得/n 贷款 贷款/n