决策树

骑猪看日落 2022-05-17 00:55 324阅读 0赞

# 一、 决策树简介 #

决策树是一种特殊的树形结构，一般由节点和有向边组成。其中，节点表示特征、属性或者一个类。而有向边包含有判断条件。如图所示，决策树从根节点开始延伸，经过不同的判断条件后，到达不同的子节点。而上层子节点又可以作为父节点被进一步划分为下层子节点。一般情况下，我们从根节点输入数据，经过多次判断后，这些数据就会被分为不同的类别。这就构成了一颗简单的分类决策树。

![1.jpg][]

![2.jpg][]

# 二、 相关知识 #

请参考周志华《机器学习》第4章：决策树

注意，第75页有一行内容：信息熵的值越小，则样本集合的纯度越高。  
这怎么理解呢？可举几个例子来帮助理解  
例1：  
p1 = 1, p2 = 0, 则Ent(D) = - (1 \* log1 + 0 \* log0) = 0  
这表示样本集合里只有一种样本。纯度最高。

例2：  
p1 = p2 = 0.5，则Ent(D) = - (0.5 \* log0.5 + 0.5 \* log0.5) = - (-0.5 - 0.5) = 1  
样本集合中有两种样本，每种样本的纯度都是50%

例3：  
p1 = 0.5, p2 = p3 = 0.25，则Ent(D) = -(0.5 \* log0.5 + 0.25 \* log0.25 + 0.25 \* log0.25) = -(-0.5 - 0.5 - 0.5) = 1.5

例4：  
p1 = p2 = p3 = p4 = 0.25，则Ent(D) = 2

例5：  
p1 = p2 = p3 = p4 = 1/1024，则Ent(D) = 10

通过上面几个可以看出来，熵值越小，纯度越高，熵值越大，纯度越低。纯度范围为\[0, log|y|\]

# 三、 数据集 #

为了更好地理解程序，咱们只采用15行数据来实现决策树二分类。这些数据中，前6行是特征属性，最后一行是分类结果。

2,2,2,4,0,2,1
    2,2,2,2,0,1,0
    2,2,2,2,0,2,0
    2,2,2,2,1,0,0
    2,2,2,2,1,1,0
    2,2,2,2,1,2,0
    2,2,2,2,2,0,0
    2,2,2,2,2,1,0
    2,2,2,2,2,2,0
    2,2,2,4,0,0,0
    2,2,2,4,0,1,0
    2,2,2,4,0,2,1
    2,2,2,4,1,0,0
    2,2,2,4,1,1,0
    2,2,2,4,1,2,1

对于上面的十五行数据，咱们可以把前1/3（即前5行）数据做为测试集，把后2/3（即后10行）数据作为训练集。  
注意：这里是为了好理解，划分成前1/3和后2/3，更好的做法是随机挑选一部分作为测试集，剩余的部分作为训练集。

# 四、 算法思路 #

可直接查看周志华《机器学习》中的思路

![3.jpg][]

# 五、 实现过程 #

## （一）利用信息熵和信息增益 ##

信息熵越小越好，信息增益越大越好。  
信息熵的公式为：

![4.png][]

对于各属性，信息增益的公式为：

![5.png][]

因为D都是一样的，程序中可以省略掉D。用信息增益最大的属性作为节点划分，即要也上式最大，也即要求下式最小：

![6.png][]

实现代码：

def __get_info_entropy(label, attr):
        result = 0.0
        for this_attr in np.unique(attr):
            sub_label, entropy = label[np.where(attr == this_attr)[0]], 0.0
            for this_label in np.unique(sub_label):
                p = len(np.where(sub_label == this_label)[0]) / len(sub_label)
                entropy -= p * np.log2(p)
            result += len(sub_label) / len(label) * entropy
        print("result:", result)
        return result

# （二）划分属性 #

训练集的数据（后10行）为

2,2,2,2,1,2,0
    2,2,2,2,2,0,0
    2,2,2,2,2,1,0
    2,2,2,2,2,2,0
    2,2,2,4,0,0,0
    2,2,2,4,0,1,0
    2,2,2,4,0,2,1
    2,2,2,4,1,0,0
    2,2,2,4,1,1,0
    2,2,2,4,1,2,1

根据上面的代码，计算出的各属性的信息增益分别为：

第0个属性的信息增益为：0.7219280948873623
    第1个属性的信息增益为：0.7219280948873623
    第2个属性的信息增益为：0.7219280948873623
    第3个属性的信息增益为：0.5509775004326937
    第4个属性的信息增益为：0.6
    第5个属性的信息增益为：0.4

上述中最后一个值0.4最小，所以取该值所对应的第5列（从0开始计数）属性作为根结点。  
用第5列属性进行划分，属性0对应着分类0，属性1对应着分类0，属性2对应着分类0和1，此时树的结构是这样的：

![7.png][]

第二个属性如何计算呢？  
找出第5列属性的值为2所对应的类别。再找出这些类别对应的各列属性值（不包含第5列属性），得

2,2,2,2,1,0
    2,2,2,2,2,0
    2,2,2,4,0,1
    2,2,2,4,1,1

这里前五列表示属性0，1，2，3，4；最后一列表示分类。  
计算出的各属性的信息增益分别为：

第0个属性的信息增益为：1.0
    第1个属性的信息增益为：1.0
    第2个属性的信息增益为：1.0
    第3个属性的信息增益为：0.0
    第4个属性的信息增益为：0.5

则取第3个属性来划分。第3个属性取值为2时，分类为0；取值为4时，分类为1。  
此时的决策树为

![8.png][]

## （三）预测结果 ##

需要预测的五条数据为  
2,2,2,4,0,2,1  
2,2,2,2,0,1,0  
2,2,2,2,0,2,0  
2,2,2,2,1,0,0  
2,2,2,2,1,1,0  
前六列是特征属性，最后一列是实际结果，用来和预测结果做比较。  
第一条数据，第5个属性值是2，需要再判断第3个属性，第3个属性的值为4，根据决策树得出的预测分类为1，与实际结果吻合  
第二条数据，第5个属性值是1，根据决策树得出的预测分类为0，与实际结果吻合  
第三条数据，第5个属性值是2，需要再判断第3个属性，第3个属性的值为2，根据决策树得出的预测分类为0，与实际结果吻合  
第四条数据，第5个属性值是0，根据决策树得出的预测分类为0，与实际结果吻合  
第五条数据，第5个属性值是1，根据决策树得出的预测分类为0，与实际结果吻合

# 六、 完整代码 #

（1）DecisionTree.py

# 具有两种剪枝功能的简单决策树
    # 使用信息熵进行划分，剪枝时采用激进策略（即使剪枝后正确率相同，也会剪枝）
    import numpy as np
    
    
    class Tree:
        def __init__(self, label, attr, pruning=None):
            self.__root = None
            boundary = len(label) // 3
    
            if pruning is None:
                self.__root = self.__run_build(label[boundary:], attr[boundary:],
                                               np.array(range(len(attr.transpose()))), False)
                return
            if pruning == 'Pre':
                self.__root = self.__run_build(label[boundary:], attr[boundary:],
                                               np.array(range(len(attr.transpose()))),
                                               True, attr[0:boundary], label[0:boundary])
            elif pruning == 'Post':
                self.__root = self.__run_build(label[boundary:], attr[boundary:],
                                               np.array(range(len(attr.transpose()))), False)
                self.print_tree()
                self.__post_pruning(self.__root, attr[0:boundary], label[0:boundary])
            else:
                raise RuntimeError('未能识别的参数：%s' % pruning)
    
        @staticmethod
        # 返回使用特定属性划分下的信息熵之和
        # label: 类别标签
        # attr: 用于进行数据划分的属性
        def __get_info_entropy(label, attr):
            result = 0.0
            for this_attr in np.unique(attr):
                sub_label, entropy = label[np.where(attr == this_attr)[0]], 0.0
                for this_label in np.unique(sub_label):
                    p = len(np.where(sub_label == this_label)[0]) / len(sub_label)
                    entropy -= p * np.log2(p)
                result += len(sub_label) / len(label) * entropy
            return result
    
        # 递归构建一颗决策树
        # label: 维度为1 * N的数组。第i个元素表示第i行数据所对应的标签
        # attr: 维度为 N * M 的数组，每行表示一条数据的属性，列数随着决策树的构建而变化
        # attr_idx: 表示每个属性在原始属性集合中的索引，用于决策树的构建
        # pre_pruning: 表示是否进行预剪枝
        # check_attr: 在预剪枝时，用作测试数据的属性集合
        # check_label: 在预剪枝时，用作测试数据的验证标签
        def __run_build(self, label, attr, attr_idx, pre_pruning, check_attr=None, check_label=None):
            node, right_count = {}, None
            max_type = np.argmax(np.bincount(label))
            if len(np.unique(label)) == 1:
                # 如果所有样本属于同一类C，则将结点标记为C
                node['type'] = label[0]
                return node
            if attr is None or len(np.unique(attr, axis=0)) == 1:
                # 如果 attr 为空或者 attr 上所有元素取值一致，则将结点标记为样本数最多的类
                node['type'] = max_type
                return node
            attr_trans = np.transpose(attr) #每一行就是原先的属性列，转置是为了计算方便
            min_entropy, best_attr = np.inf, None
            # 获取各种划分模式下的信息熵之和（作用和信息增益类似）
            # 并以此为信息，找出最佳的划分属性
            if pre_pruning:
                right_count = len(np.where(check_label == max_type)[0])
            for this_attr in attr_trans:
                entropy = self.__get_info_entropy(label, this_attr)
                if entropy < min_entropy:
                    min_entropy = entropy
                    best_attr = this_attr
            # branch_attr_idx 表示用于划分的属性是属性集合中的第几个
            branch_attr_idx = np.where((attr_trans == best_attr).all(1))[0][0]
            if pre_pruning:
                sub_right_count = 0
                check_attr_trans = check_attr.transpose()
                # branch_attr_idx 表示本次划分依据的属性属于属性集中的哪一个
                for val in np.unique(best_attr):
                    # 按照预划分的特征进行划分，并统计划分后的正确率
                    # branch_data_idx 表示数据集中，被划分为 idx 的数据的索引
                    branch_data_idx = np.where(best_attr == val)[0]
                    # predict_label 表示一次划分以后，该分支数据的预测类别
                    print(label[branch_data_idx])
                    print(np.bincount(label[branch_data_idx]))
                    predict_label = np.argmax(np.bincount(label[branch_data_idx]))
                    # check_data_idx 表示验证集中，属性编号为 branch_attr_idx 的属性值等于 val 的项的索引
                    check_data_idx = np.where(check_attr_trans[branch_attr_idx] == val)[0]
                    # check_branch_label 表示按照当前特征划分以后，被分为某一类的数据的标签
                    check_branch_label = check_label[check_data_idx]
                    # 随后判断这些标签是否等于前面计算得到的类别，如果相等，则分类正确
                    sub_right_count += len(np.where(check_branch_label == predict_label)[0])
                if sub_right_count <= right_count:
                    # 如果划分后的正确率小于等于不划分的正确率，则剪枝
                    node['type'] = max_type
                    return node
            values = []
            for val in np.unique(best_attr):
                values.append(val)
                branch_data_idx = np.where(best_attr == val)[0]
                if len(branch_data_idx) == 0:
                    new_node = {
       'type': np.argmax(np.bincount(label))}
                else:
                    # 按照划分构造新数据，并开始递归
                    branch_label = label[branch_data_idx]
    
                    # 哪几行branch_attr对应着上面的branch_label数组
                    branch_attr = np.delete(attr_trans, branch_attr_idx, axis=0).transpose()[branch_data_idx]
                    new_node = self.__run_build(branch_label, branch_attr,
                                                np.delete(attr_idx, branch_attr_idx, axis=0),
                                                pre_pruning, check_attr, check_label)
                node[str(val)] = new_node
            node['attr'] = attr_idx[branch_attr_idx]
            node['type'] = max_type
            node['values'] = values
            return node
    
        # 后剪枝
        # node: 当前进行判断和剪枝操作的结点
        # check_attr: 用于验证的数据属性集
        # check_label: 用于验证的数据标签集
        def __post_pruning(self, node, check_attr, check_label):
            check_attr_trans = check_attr.transpose()
            if node.get('attr') is None:
                # attr 为 None 代表叶节点
                return len(np.where(check_label == node['type'])[0])
            sub_right_count = 0
            for val in node['values']:
                sub_node = node[str(val)]
                # 找到当前分支点中，数据属于 idx 这一分支的数据的索引
                idx = np.where(check_attr_trans[node['attr']] == val)[0]
                # 使用上述数据，从子节点开始新的递归
                sub_right_count += self.__post_pruning(sub_node, check_attr[idx], check_label[idx])
            if sub_right_count <= len(np.where(check_label == node['type'])[0]):
                for val in node['values']:
                    del node[str(val)]
                del node['values']
                del node['attr']
                return len(np.where(check_label == node['type'])[0])
            return sub_right_count
    
        # 根据构建的决策树预测结果
        # data: 用于预测的数据，维度为M
        # return: 预测结果
        def predict(self, data):
            node = self.__root
            while node.get('attr') is not None:
                attr = node['attr']
                node = node.get(str(data[attr]))
                if node is None:
                    return None
            return node.get('type')
    
        # 以文本形式（类JSON）打印出决策树
        def print_tree(self):
            print(self.__root)

（2）Main.py

import DecisionTree
    import numpy as np
    
    
    if __name__ == '__main__':
        print('正在准备数据并种树……')
        file = open('Data/car.data')
        lines = file.readlines()
        raw_data = np.zeros([len(lines), 7], np.int32)
        for idx in range(len(lines)):
            raw_data[idx] = np.array(lines[idx].split(','), np.int32)
        file.close()
        #np.random.shuffle(raw_data)
        data =  raw_data.transpose()[0:6].transpose()
        label = raw_data.transpose()[6]
        # tree_no_pruning = DecisionTree.Tree(label, data, None)
        # tree_no_pruning.print_tree()
        # tree_pre_pruning = DecisionTree.Tree(label, data, 'Pre')
        # tree_pre_pruning.print_tree()
        tree_post_pruning = DecisionTree.Tree(label, data, 'Post')
        tree_post_pruning.print_tree()
        test_count = len(label) // 3
        test_data, test_label = data[0:test_count], label[0:test_count]
        times_no_pruning, times_pre_pruning, times_post_pruning = 0, 0, 0
        print('正在检验结果（共 %d 条验证数据）' % test_count)
        for idx in range(test_count):
            # if tree_no_pruning.predict(test_data[idx]) == test_label[idx]:
            # times_no_pruning += 1
            # if tree_pre_pruning.predict(test_data[idx]) == test_label[idx]:
            # times_pre_pruning += 1
            if tree_post_pruning.predict(test_data[idx]) == test_label[idx]:
                times_post_pruning += 1
        #print('【未剪枝】：命中 %d 次，命中率 %.2f%%' % (times_no_pruning, times_no_pruning * 100 / test_count))
        #print('【预剪枝】：命中 %d 次，命中率 %.2f%%' % (times_pre_pruning, times_pre_pruning * 100 / test_count))
    print('【后剪枝】：命中 %d 次，命中率 %.2f%%' % (times_post_pruning, times_post_pruning * 100 / test_count))

运行结果：

正在准备数据并种树……
    决策树的结构为：
     {
       '0': {
       'type': 0}, '1': {
       'type': 0}, '2': {
       '2': {
       'type': 0}, '4': {
       'type': 1}, 'attr': 3, 'type': 0, 'values': [2, 4]}, 'attr': 5, 'type': 0, 'values': [0, 1, 2]}
    正在检验结果（共 5 条验证数据）
    【未剪枝】：命中 5 次，命中率 100.00%

# 七、参考资料 #

[https://blog.csdn.net/dapanbest/article/details/78281201][https_blog.csdn.net_dapanbest_article_details_78281201]

> 机器学习交流QQ群：658291732  
> TopCoder & Codeforces & AtCoder交流QQ群：648202993  
> 更多内容请关注微信公众号  
> ![wechat\_public\_header.jpg][wechat_public_header.jpg]

[1.jpg]: /images/20220517/51753417a25b4936b28c5ace78c09ed0.png
[2.jpg]: /images/20220517/64a309eb489c4b6592972f17d1919b50.png
[3.jpg]: /images/20220517/0eaa059dbd9e43a49d02dc36ed3997dd.png
[4.png]: /images/20220517/0a08f10302f34b7c9d4cccde83c7c148.png
[5.png]: /images/20220517/1039ff076cd44837b9e2aebebaef28be.png
[6.png]: /images/20220517/70992f949a3e40218300849b4c0408ca.png
[7.png]: /images/20220517/cb62f9d4ff6046e387f2289184834038.png
[8.png]: /images/20220517/ce4cc17898aa439fb55eb07c9d322f6c.png
[https_blog.csdn.net_dapanbest_article_details_78281201]: https://blog.csdn.net/dapanbest/article/details/78281201
[wechat_public_header.jpg]: /images/20220517/e7f696d6d67841b78243ff2ced84368b.png