树结构的实现

发表于 | 分类于

（本文会用到的所有代码都在这里）

由前文的诸多讨论可知，Tree 结构需要做到如下几点：

  • 定义好需要在各个 Node 上调用的“全局变量”
  • 做好数据预处理的工作、保证传给 Node 的数据是合乎要求的
  • 对各个 Node 进行合适的封装，做到：
    • 生成决策树时能够正确地调用它们的生成算法
    • 进行后剪枝时能够正确地调用它们的局部剪枝函数
  • 定义预测函数和评估函数以供用户调用

既然 Node 我们可以抽象出一个基类CvDNode，我们自然也能相应地对 Tree 结构抽象出一个基类CvDBase

下面先来看看如何搭建该基类的基本框架：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from copy import deepcopy
# 导入Node结构以进行封装
from c_CvDTree.Node import *
# 定义一个足够抽象的Tree结构的基类以适应我们Node结构的基类
class CvDBase:
    """
        初始化结构
        self.nodes：记录所有Node的列表
        self.roots：主要用于CART剪枝的属性，可先按下不表
（用于存储算法过程中产生的各个决策树）
            self.max_depth：记录决策树最大深度的属性
        self.root, self.feature_sets：根节点和记录可选特征维度的列表
            self.label_dic：和朴素贝叶斯里面相应的属性意义一致、是类别的转换字典
        self.prune_alpha, self.layers：主要用于ID3和C4.5剪枝的两个属性，可先按下不表
（self.prune_alpha是“惩罚因子”，self.layers则记录着每一“层”的Node）
        self.whether_continuous：记录着各个维度的特征是否连续的列表
    """
    def __init__(self, max_depth=None, node=None):
        self.nodes, self.layers, self.roots = [], [], []
        self.max_depth = max_depth
        self.root = node
        self.feature_sets = []
        self.label_dic = {}
        self.prune_alpha = 1
        self.whether_continuous = None
    def __str__(self):
        return "CvDTree ({})".format(self.root.height)
    __repr__ = __str__

回忆朴素贝叶斯的实现，可以知道在第二章的混合型朴素贝叶斯中、我们要求用户告诉程序哪些维度的特征是连续的；这里我们介绍一种非常简易却有一定合理性的做法、从而可以让程序在进行数据预处理时自动识别出连续特征对应的维度：

  • 将训练集中每个维度特征的所有可能的取值算出来，这一步可以用 Python 内置的数据结构set来完成
  • 如果第 i 维可能的取值个数比上训练集总样本数 N 大于某个阈值，亦即若： 那么就认为第 i 维的特征是连续型随机变量
    的具体取值需要视情况而定。一般来说在样本数 N 足够大时、可以取得比较小（比如取就是个不错的选择）；但是样本数 N 比较小时，我们可能需要将取得大一些（比如取）。具体应该取什么值还是要看具体的任务和数据，毕竟这种自动识别的方法还是过于朴素了

以上所叙述的数据预处理的实现如下（注：我们在朴素贝叶斯的实现里用到过的quantize_data方法中整合了如下代码中的核心部分）：

1
2
3
4
5
6
7
8
9
def feed_data(self, x, continuous_rate=0.2):
    # 利用set获取各个维度特征的所有可能取值
    self.feature_sets = [set(dimension) for dimension in x.T]
    data_len, data_dim = x.shape
    # 判断是否连续
    self.whether_continuous = np.array(
        [len(feat) >= continuous_rate * data_len for feat in self.feature_sets])
    self.root.feats = [i for i in range(x.shape[1])]
    self.root.feed_tree(self)

最后一行我们对根节点调用了feed_tree方法，该方法会做以下三件事：

  • 让决策树中所有的 Node 记录一下它们所属的 Tree 结构
  • 将自己记录在 Tree 中记录所有 Node 的列表nodes里
  • 根据 Tree 的相应属性更新记录连续特征的列表

实现的时候同样利用上了递归：

1
2
3
4
5
6
7
def feed_tree(self, tree):
    self.tree = tree
    self.tree.nodes.append(self)
    self.wc = tree.whether_continuous
    for child in self.children.values():
        if child is not None:
            child.feed_tree(tree)

注意：以上代码应定义在CvDNode里面

接下来就是对生成算法的封装了。考虑到第二节会讲到的剪枝算法、我们需要做的是：

  • 将类别向量数值化（和朴素贝叶斯里面的数值化类别向量的方法一样）
  • 将数据集切分成训练集和交叉验证集、同时处理好样本权重
  • 对根节点调用决策树的生成算法
  • 调用自己的剪枝算法

具体的代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# 参数alpha和剪枝有关、可按下不表
# cv_rate用于控制交叉验证集的大小，train_only则控制程序是否进行数据集的切分
def fit(self, x, y, alpha=None, sample_weight=None, eps=1e-8,
    cv_rate=0.2, train_only=False):
    # 数值化类别向量
    _dic = {c: i for i, c in enumerate(set(y))}
    y = np.array([_dic[yy] for yy in y])
    self.label_dic = {value: key for key, value in _dic.items()}
    x = np.array(x)
    # 根据特征个数定出alpha
    self.prune_alpha = alpha if alpha is not None else x.shape[1] / 2
    # 如果需要划分数据集的话
    if not train_only and self.root.is_cart:
        # 根据cv_rate将数据集随机分成训练集和交叉验证集
        # 实现的核心思想是利用下标来进行各种切分
        _train_num = int(len(x) * (1-cv_rate))
        _indices = np.random.permutation(np.arange(len(x)))
        _train_indices = _indices[:_train_num]
        _test_indices = _indices[_train_num:]
        if sample_weight is not None:
            # 注意对切分后的样本权重做归一化处理
            _train_weights = sample_weight[_train_indices]
            _test_weights = sample_weight[_test_indices]
            _train_weights /= np.sum(_train_weights)
            _test_weights /= np.sum(_test_weights)
        else:
            _train_weights = _test_weights = None
        x_train, y_train = x[_train_indices], y[_train_indices]
        x_cv, y_cv = x[_test_indices], y[_test_indices]
    else:
        x_train, y_train, _train_weights = x, y, sample_weight
        x_cv = y_cv = _test_weights = None
    self.feed_data(x_train)
    # 调用根节点的生成算法
    self.root.fit(x_train, y_train, _train_weights, eps)
    # 调用对Node剪枝算法的封装
    self.prune(x_cv, y_cv, _test_weights)

这里我们用到了np.random.permutation方法，它其实可以看成两行代码的缩写、亦即：

1
_indices = np.random.permutation(np.arange(n))

从效果上来说等价于

1
2
_indices = np.arange(n)
np.random.shuffle(_indices)

不过前者不仅写起来更便利、而且运行速度也要稍微快一点，是故我们选择了前一种方法来进行实现

除了fit这个函数以外，回忆 Node 中生成算法的实现过程、可知彼时我们调用了 Tree 的reduce_nodes方法来将被剪掉的 Node 从nodes中除去。该方法的实现如下：

1
2
3
4
def reduce_nodes(self):
    for i in range(len(self.nodes)-1, -1, -1):
        if self.nodes[i].pruned:
            self.nodes.pop(i)

注意：虽然该实现相当简单直观、不过其中却蕴含了一个具有普适意义的编程思想：如果要在遍历列表的同时进行当前列表元素的删除操作、就一定要从后往前遍历

观众老爷们能赏个脸么 ( σ'ω')σ