|
其他章节答案请参考我的汇总统计学习方法答案汇总，都是自己写的。
1、根据表5.1所给的训练数据集，利用信息增益比（C4.5算法）生成决策树。
解： 下面先给出计算信息增益比的程序，并且输出最好的特征
import numpy as np
def info_ratio(D, Y, n):
'''
计算信息增益比
Parameters
----------
D : numpy array
训练数据集.
Returns
-------
最优特征.
'''
#下面开始修正数据集D和标签Y
for index in n:
s = np.shape(D)
if index == 0:
continue
for i in reversed(range(s[0])):
if D[i,index - 1] == 1:
D = np.delete(D, i, axis = 0)
Y = np.delete(Y, i, axis = 0)
s = np.shape(D)
#下面计算H(D)
#统计类别数
nums_class = len(list(set(Y)))
if nums_class == 1:
print('仅有一个类别，无需在进行分类')
return -2
H_D = 0
#这里时使用自然对数进行计算的
for i in range(nums_class):#i表示类别
nums_i = 0
for j in range(s[0]):
if Y[j] == i:
nums_i += 1
H_D += np.log(nums_i / s[0]) * (nums_i / s[0])
H_D = - H_D
#下面对特征数进行循环
infos_ = []
for A in range(s[1]):
if (A+1) in n:
infos_.append(0)
continue
#循环统计特征A的个数
list_A = list(set(D[:,A]))
nums_A = len(list_A) # 第A个特征的取值范围
H_D_A = 0
H_A_D = 0
for i in range(nums_A):
D_i = sum(np.array(D[:,A] == i, dtype = np.int32))
if D_i != 0:
H_A_D += - (D_i / s[0]) * np.log(D_i / s[0])
for c in range(nums_class):
D_i_k = sum(np.array(D[:, A] == i, dtype = np.int32) * np.array(Y == c, dtype = np.int32))
if D_i_k != 0:
H_D_A += - (D_i / s[0]) * (D_i_k / D_i) * np.log(D_i_k / D_i)
infos_.append((H_D - H_D_A) / H_A_D)
return infos_.index(max(infos_))
if __name__ == '__main__':
D = np.array([[0,0,0,0],
[0,0,0,1],
[0,1,0,1],
[0,1,1,0],
[0,0,0,0],
[1,0,0,0],
[1,0,0,1],
[1,1,1,1],
[1,0,1,2],
[1,0,1,2],
[2,0,1,2],
[2,0,1,1],
[2,1,0,1],
[2,1,0,2],
[2,0,0,0]])
Y = np.array([0,0,1,1,0,0,0,1,1,1,1,1,1,1,0])
n = [0]
for i in range(4):
best = info_ratio(D, Y, n) + 1
if best
=
C
(
3
)
−
C
(
1
)
−
C
(
2
)
2\alpha>=C(3) - C(1)-C(2)
2α>=C(3)−C(1)−C(2)，其中
C
(
3
)
C(3)
C(3)是节点3内的数据点的损失，比如可以是节点3内数据点的基尼指数或者是平方误差。 那么在决策树
T
2
T_{2}
T2中，可以将节点
1
,
2
1,2
1,2剪去得到新的树
T
2
′
{T_{2}}'
T2′，因为
2
α
>
=
C
(
3
)
−
C
(
1
)
−
C
(
2
)
2\alpha>=C(3) - C(1)-C(2)
2α>=C(3)−C(1)−C(2)，所以，会使得
C
α
(
T
2
)
>
=
C
α
(
T
2
′
)
C_{\alpha}(T_{2}) >= C_{\alpha}({T_{2}}')
Cα(T2)>=Cα(T2′),因而，我们得到一棵更小的决策树。矛盾。得证。
4、证明CART剪枝算法中求出的子树序列
{
T
0
,
T
1
,
.
.
.
,
T
n
}
\{T_{0},T_{1},...,T_{n}\}
{T0,T1,...,Tn}分别是区间
α
∈
[
α
i
,
α
i
+
1
)
\alpha \in[\alpha_{i},\alpha_{i+1})
α∈[αi,αi+1)的最优子树
T
α
T_{\alpha}
Tα,这里
i
=
0
,
1
,
.
.
.
,
n
,
0
=
α
0
<
α
1
<
.
.
.
.
<
α
n
<
+
∞
i = 0,1,...,n,0=\alpha_{0} |