任务描述 本关任务：编写一个使用决策树算法进行信息增益计算及结点划分的程序。 相关知识 为了完成本关任务，你需要掌握：1.决策树模型，2.决策树模型用于分类，3.决策树信息熵构建。 决策树模型 决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度，使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。
决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点，其中内部结点表示一个特征或属性，叶结点表示一个类。一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点。叶结点对应于决策结果，其他每个结点则对应于一个属性测试。每个结点包含的样本集合根据属性测试的结果被划分到子结点中，根结点包含样本全集，从根结点到每个叶结点的路径对应了一个判定测试序列。在下图中，圆和方框分别表示内部结点和叶结点。决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。下图为决策树的示意图：

决策树根据任务的不同可以分为回归树和分类树，在本次课程中，我们主要实现分类树的构建。 决策树分类器 决策树算法分类和人类在进行决策时的处理机制类似，依据对一系列属性取值的判定得出最终决策。决策树是一棵树结构，其每个非叶子节点表示一个特征属性上的测试，每个分支表示这个特征属性在某个值域上的输出，而每个叶子节点对应于最终决策结果。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点对应的类别作为决策结果。
决策树学习的目的是产生一棵泛化性能强，即处理未见示例能力强的决策树。其基本流程遵循“分而治之”的策略，算法伪代码如下图所示： 1. 输入：训练集D={(x_1,y_1),(x_2,y_2),⋯,(x_m,y_m)}; 2.      属性集A={a_1,a_2,⋯,a_d}. 3. 过程：函数TreeGenerate(D,A) 4. 1: 生成节点node 5. 2: if  D中样本全属于同一类别C then 6. 3:    将node标记为C类叶节点；return 7. 4: end if 8. 5: if  A=∅ or D中样本在A上取值相同 then 9. 6:    将node标记为叶节点，其类别标记为D中样本数最多的类；return 10. 7: end if 11. 8: 从A中选择最优 划分属性a_*; 12. 9: for a_*的每一个取值a_*^v do 13. 10:    为node生成一个分支；令D_v表示D中在a_*上取值为a_*^v的样本子集； 14. 11:    if D_v=∅ then 15. 12:       将分支节点标记为叶节点，其类别标记为D中样本最多的类；return 16. 13:    else 17. 14:       以TreeGenerate(D_v,A\{a_*})为分支节点 18. 15:    end if 19. 16: end for 20. 输出：以node为根节点的一棵决策树  上述算法最关键的是第8行，即如何选择最优划分，选择的标准是什么。一般而言，随着划分的不断进行，决策树每个分支包含的样本会越来越属于同一类，即节点的“纯度”越来越高。但是为了得到一棵泛化性能强的决策树，根据“奥卡姆剃刀”原则：越是小型的决策树越优于大型的决策树，我们希望最终得到的决策树规模越小越好。因此我们选择划分后能够将样本“纯度提升”最大的那个属性作为最优划分。
当我们选择一个属性进行划分后，信息的纯度将增加，信息的不确定性将随之减少。我们用信息增益来度量样本纯度的提升。假设离散属性a有V个可能的取值{a1,a2,⋯,aV}{a1,a2,⋯,aV}，若使用a来对样本集D进行划分，则会产生V个分支节点，其中第v个分支节点包含了D中所有在属性a上取值为avav的样本，记为DvDv。因此我们可以将信息增益的公式记为如下：

因此，信息增益越大，则意味着使用属性a进行划分获得的“纯度提升”越大。著名的ID3决策树算法就是以信息增益为准则来选择划分属性。 信息增益的计算 我们使用鸢尾花的数据来完成相关计算。首先是数据导入，这里使用sklearn中的数据： 1. import numpy as np 2. from sklearn import datasets 3. d=datasets.load_iris() 4. x=d.data[:,2:] 5. y=d.target   然后是信息熵计算的方法： 1. #定义二分类问题的信息熵计算函数np.sum(-p*np.log(p)) 2. def entropy(p): 3.     return -p*np.log(p)-(1-p)*np.log(1-p)  然后，就可以根据信息熵对数据进行实现划分，从而实现决策树信息熵构建，下面为主要的参考代码： 1. # 根据最有划分属性和值进行划分的函数 2. def split(x,y,d,value): 3.     index_a=(x[:,d]<=value) 4.     index_b=(x[:,d]>value) 5.     return x[index_a],x[index_b],y[index_a],y[index_b] 6.  7.  8. from collections import Counter 9. # 信息熵的计算,可参考上述公式和代码编写 10. def entropy(y): 11.     pass 12.  13. #  计算最优划分属性best_d和值best_v 14. def try_spit(x,y): 15.     best_entropy=float("inf") 16.     best_d,best_v=-1,-1 17.     for d in range(x.shape[1]): 18.         sorted_index=np.argsort(x[:,d]) 19.         for i in range(1,len(x)): 20.             if x[sorted_index[i-1],d] != x[sorted_index[i],d]: 21.                 v=(x[sorted_index[i-1],d]+x[sorted_index[i],d])/2 22.                 x_l,x_r,y_l,y_r=split(x,y,d,v) 23.                 e=entropy(y_l)+entropy(y_r) 24.                 if e<best_entropy: 25.                     best_entropy,best_d,best_v=e,d,v 26.     return best_entropy,best_d,best_v   编程要求 根据提示，在右侧编辑器补充代码，实现决策树信息熵构建，包括： 1. 划分的函数 2. 信息熵计算的函数 3. 最优划分属性和最优值计算的函数 4. 进行划分，并打印划分后的信息熵值  测试说明 平台会对你编写的代码进行测试： 预期输出： 提示：
 参照示例完成任务    开始你的任务吧，祝你成功！

import numpy as np
from sklearn import datasets
from collections import Counter

#######Begin#######
# 划分函数
def split(x,y,d,value):
    index_a = (x[:,d] <= value)
    index_b = (x[:,d] > value)
    return x[index_a], x[index_b], y[index_a], y[index_b]
#######End#########

#######Begin#######
# 信息熵的计算
def entropy(y):
    counter = Counter(y)
    res = 0.0
    for num in counter.values():
        p = num / len(y)
        res += -p * np.log(p)
    return res
#######End#########

#######Begin#######
# 计算最优划分属性和值的函数
def try_spit(x,y):
    best_entropy = float('inf')
    best_d, best_v = -1, -1
    for d in range(x.shape[1]):
        sorted_index = np.argsort(x[:,d])
        for i in range(1, len(x)):
            if x[sorted_index[i-1], d] != x[sorted_index[i], d]:
                v = (x[sorted_index[i-1], d] + x[sorted_index[i], d]) / 2
                x_l, x_r, y_l, y_r = split(x, y, d, v)
                e = entropy(y_l) + entropy(y_r)
                if e < best_entropy:
                    best_entropy = e
                    best_d = d
                    best_v = v
    return best_entropy, best_d, best_v
#######End#########

# 加载数据
d = datasets.load_iris()
x = d.data[:, 2:]
y = d.target

# 计算出最优划分属性和最优值
best_entropy, best_d, best_v = try_spit(x, y)

# 使用最优划分属性和值进行划分
x_l, x_r, y_l, y_r = split(x, y, best_d, best_v)

# 打印结果
print("叶子结点的熵值：")
print(entropy(y_l))
print("分支结点的熵值：")
print(entropy(y_r))