节点结构的实现

发表于 | 分类于

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

在实现完计算各种信息量的函数之后，我们就可以着手实现决策树本身了。由前文的讨论可知、组成决策树主体的是一个个的 Node，所以我们接下来首先要实现的就是 Node 这个结构。而且由于我们所关心的 ID3、C4.5 和 CART 分类树的 Node 在大多数情况下表现一致、只有少数几个地方有所不同，因此我们可以写一个统一的 Node 结构的基类CvDNode来囊括我们所有关心的决策树生成算法，该基类需要实现如下功能：

  • 根据离散型特征划分数据（ID3、C4.5、CART）
  • 根据连续型特征划分数据（C4.5、CART）
  • 根据当前的数据判定所属的类别

虽然说起来显得轻巧，但这之中的抽象还是比较繁琐的

我们先看看这个基类的基本框架该如何搭建：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import numpy as np
# 导入之前定义的Cluster类以计算各种信息量
from c_Tree.Cluster import Cluster
# 定义一个足够抽象的基类以囊括所有我们关心的算法
class CvDNode:
    """
        初始化结构
        self._x, self._y：记录数据集的变量
        self.base, self.chaos：记录对数的底和当前的不确定性
        self.criterion, self.category：记录该Node计算信息增益的方法和所属的类别
        self.left_child, self.right_child：针对连续型特征和CART、记录该Node的左右子节点
        self._children, self.leafs：记录该Node的所有子节点和所有下属的叶节点
        self.sample_weight：记录样本权重
        self.wc：记录着各个维度的特征是否连续的列表（whether continuous的缩写）
        self.tree：记录着该Node所属的Tree
        self.feature_dim, self.tar, self.feats：记录该Node划分标准的相关信息。具体而言：
            self.feature_dim：记录着作为划分标准的特征所对应的维度
            self.tar：针对连续型特征和CART、记录二分标准
            self.feats：记录该Node能进行选择的、作为划分标准的特征的维度
        self.parent, self.is_root：记录该Node的父节点以及该Node是否为根节点
        self._depth, self.prev_feat：记录Node的深度和其父节点的划分标准
        self.is_cart：记录该Node是否使用了CART算法
        self.is_continuous：记录该Node选择的划分标准对应的特征是否连续
        self.pruned：记录该Node是否已被剪掉，后面实现局部剪枝算法时会用到
    """
    def __init__(self, tree=None, base=2, chaos=None,
               depth=0, parent=None, is_root=True, prev_feat="Root"):
        self._x = self._y = None
        self.base, self.chaos = base, chaos
        self.criterion = self.category = None
        self.left_child = self.right_child = None
        self._children, self.leafs = {}, {}
        self.sample_weight = None
        self.wc = None
        self.tree = tree
        # 如果传入了Tree的话就进行相应的初始化
        if tree is not None:
            # 由于数据预处理是由Tree完成的
            # 所以各个维度的特征是否是连续型随机变量也是由Tree记录的
            self.wc = tree.whether_continuous
            # 这里的nodes变量是Tree中记录所有Node的列表
            tree.nodes.append(self)
        self.feature_dim, self.tar, self.feats = None, None, []
        self.parent, self.is_root = parent, is_root
        self._depth, self.prev_feat = depth, prev_feat
        self.is_cart = self.is_continuous = self.pruned = False
    def __getitem__(self, item):
        if isinstance(item, str):
            return getattr(self, "_" + item)
    # 重载 __lt__ 方法，使得Node之间可以比较谁更小、进而方便调试和可视化
    def __lt__(self, other):
        return self.prev_feat < other.prev_feat
    
    # 重载 __str__ 和 __repr__ 方法，同样是为了方便调试和可视化
    def __str__(self):
        if self.category is None:
            return "CvDNode ({}) ({} -> {})".format(
                self._depth, self.prev_feat, self.feature_dim)
        return "CvDNode ({}) ({} -> class: {})".format(
            self._depth, self.prev_feat, self.tree.label_dic[self.category])
    __repr__ = __str__

可以看到，除了重载 getitem 方法以外、我们还重载 lt、str 和 repr 方法。这是因为决策树模型的结构比起朴素贝叶斯模型而言要复杂一些，为了开发过程中的调试和最后的可视化更加便利、通常来说最好让我们模型的表现更贴近内置类型的表现

然后我们需要定义几个 property 以使开发过程变得便利：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 定义children属性，主要是区分开连续+CART的情况和其余情况
# 有了该属性后，想要获得所有子节点时就不用分情况讨论了
@property
def children(self):
    return {
        "left": self.left_child, "right": self.right_child
    } if (self.is_cart or self.is_continuous) else self._children
# 递归定义height（高度）属性：
# 叶节点高度都定义为1、其余节点的高度定义为最高的子节点的高度+1
@property
def height(self):
    if self.category is not None:
        return 1
    return 1 + max([_child.height if _child is not None else 0
        for _child in self.children.values()])
# 定义info_dic（信息字典）属性，它记录了该Node的主要信息
# 在更新各个Node的叶节点时，被记录进各个self.leafs属性的就是该字典
@property
def info_dic(self):
    return {"chaos": self.chaos, "y": self._y}

以上就是CvDNode的基本框架，接下来就可以在这个框架的基础上实现决策树的各种生成算法了。首先需要指出的是，由于 Node 结构是会被 Tree 结构封装的、所以我们应该将数据预处理操作交给 Tree 来做。其次，由于我们实现的是抽象程度比较高的基类，所以我们要做比较完备的分情况讨论

注意：把 ID3、C4.5 和 CART 这三种算法分开实现是可行且高效的、此时各个部分的代码都会显得更加简洁可读一些；但这样做的话，整体的代码量就会不可避免地骤增。具体应当选择何种实现方案需要看具体的需求

我们先来看看实现生成算法所需要做的一些准备工作，比如定义停止继续生成的准则、定义停止后该 Node 的行为等

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
# 定义第一种停止准则：当特征维度为0或当前Node的数据的不确定性小于阈值时停止
# 同时，如果用户指定了决策树的最大深度，那么当该Node的深度太深时也停止
# 若满足了停止条件，该函数会返回True、否则会返回False
def stop1(self, eps):
    if (
        self._x.shape[1] == 0 or (self.chaos is not None and self.chaos <= eps)
        or (self.tree.max_depth is not None and self._depth >= self.tree.max_depth)
    ):
        # 调用处理停止情况的方法
        self._handle_terminate()
        return True
    return False
# 定义第二种停止准则，当最大信息增益仍然小于阈值时停止
def stop2(self, max_gain, eps):
    if max_gain <= eps:
        self._handle_terminate()
        return True
    return False
# 利用bincount方法定义根据数据生成该Node所属类别的方法
def get_category(self):
    return np.argmax(np.bincount(self._y))
# 定义处理停止情况的方法，核心思想就是把该Node转化为一个叶节点
def _handle_terminate(self):
    # 首先要生成该Node所属的类别
    self.category = self.get_category()
    # 然后一路回溯、更新父节点、父节点的父节点、……等等记录叶节点的属性leafs
    _parent = self.parent
    while _parent is not None:
        _parent.leafs[id(self)] = self.info_dic
        _parent = _parent.parent

接下来就要实现生成算法的核心了，我们可以将它分成三步以使逻辑清晰：

  • 定义一个方法使其能将一个有子节点的 Node 转化为叶节点（局部剪枝）
  • 定义一个方法使其能挑选出最好的划分标准
  • 定义一个方法使其能根据划分标准进行生成

我们先来看看如何进行局部剪枝：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def prune(self):
    # 调用相应方法进行计算该Node所属类别
    self.category = self.get_category()
    # 记录由于该Node转化为叶节点而被剪去的、下属的叶节点
    _pop_lst = [key for key in self.leafs]
    # 然后一路回溯、更新各个parent的属性leafs（使用id作为key以避免重复）
    _parent = self.parent
    while _parent is not None:
        for _k in _pop_lst:
            # 删去由于局部剪枝而被剪掉的叶节点
            _parent.leafs.pop(_k)
        _parent.leafs[id(self)] = self.info_dic
        _parent = _parent.parent
    # 调用mark_pruned方法将自己所有子节点、子节点的子节点……
    # 的pruned属性置为True，因为它们都被“剪掉”了
    self.mark_pruned()
    # 重置各个属性
    self.feature_dim = None
    self.left_child = self.right_child = None
    self._children = {}
    self.leafs = {}

第 16 行的 mark_pruned 方法用于给各个被局部剪枝剪掉的 Node 打上一个标记、从而今后 Tree 可以根据这些标记将被剪掉的 Node 从它记录所有 Node 的列表nodes中删去。该方法同样是通过递归实现的，代码十分简洁：

1
2
3
4
5
6
7
8
9
def mark_pruned(self):
    self.pruned = True
    # 遍历各个子节点
    for _child in self.children.values():
        # 如果当前的子节点不是None的话、递归调用mark_pruned方法
        #（连续型特征和CART算法有可能导致children中出现None，
        # 因为此时children由left_child和right_child组成，它们有可能是None）
        if _child is not None:
            _child.mark_pruned()

有了能够进行局部剪枝的方法后，我们就能实现拿来挑选最佳划分标准的方法了。开发时需要时刻注意分清楚二分（连续 / CART）和多分（其它）的情况

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
def fit(self, x, y, sample_weight, eps=1e-8):
    self._x, self._y = np.atleast_2d(x), np.array(y)
    self.sample_weight = sample_weight
    # 若满足第一种停止准则、则退出函数体
    if self.stop1(eps):
        return
    # 用该Node的数据实例化Cluster类以计算各种信息量
    _cluster = Cluster(self._x, self._y, sample_weight, self.base)
    # 对于根节点、我们需要额外算一下其数据的不确定性
    if self.is_root:
        if self.criterion == "gini":
            self.chaos = _cluster.gini()
        else:
            self.chaos = _cluster.ent()
    _max_gain, _chaos_lst = 0, []
    _max_feature = _max_tar = None
    # 遍历还能选择的特征
    for feat in self.feats:
        # 如果是连续型特征或是CART算法，需要额外计算二分标准的取值集合
        if self.wc[feat]:
            _samples = np.sort(self._x.T[feat])
            _set = (_samples[:-1] + _samples[1:]) * 0.5
        elif self.is_cart:
            _set = self.tree.feature_sets[feat]
        # 然后遍历这些二分标准并调用二类问题相关的、计算信息量的方法
        if self.is_cart or self.wc[feat]:
            for tar in _set:
                _tmp_gain, _tmp_chaos_lst = _cluster.bin_info_gain(
                    feat, tar, criterion=self.criterion,
                    get_chaos_lst=True, continuous=self.wc[feat])
                if _tmp_gain > _max_gain:
                    (_max_gain, _chaos_lst), _max_feature, _max_tar = (
                        _tmp_gain, _tmp_chaos_lst), feat, tar
        # 对于离散型特征的ID3和C4.5算法，调用普通的计算信息量的方法
        else:
            _tmp_gain, _tmp_chaos_lst = _cluster.info_gain(
                feat, self.criterion, True, self.tree.feature_sets[feat])
            if _tmp_gain > _max_gain:
                (_max_gain, _chaos_lst), _max_feature = (
                    _tmp_gain, _tmp_chaos_lst), feat
    # 若满足第二种停止准则、则退出函数体
    if self.stop2(_max_gain, eps):
        return
    # 更新相关的属性
    self.feature_dim = _max_feature
    if self.is_cart or self.wc[_max_feature]:
        self.tar = _max_tar
        # 调用根据划分标准进行生成的方法
        self._gen_children(_chaos_lst)
        # 如果该Node的左子节点和右子节点都是叶节点且所属类别一样
        # 那么就将它们合并、亦即进行局部剪枝
        if (self.left_child.category is not None and
                self.left_child.category == self.right_child.category):
            self.prune()
            # 调用Tree的相关方法，将被剪掉的、该Node的左右子节点
            # 从Tree的记录所有Node的列表nodes中除去
            self.tree.reduce_nodes()
    else:
        # 调用根据划分标准进行生成的方法
        self._gen_children(_chaos_lst)

根据划分标准进行生成的方法相当冗长、因为需要进行相当多的分情况讨论。它的实现用到了递归的思想，真正写起来就会发现其实并不困难、只不过会有些繁琐。囿于篇幅、我们略去它的实现细节，其算法描述则如下：

  • 根据划分标准将数据划分成若干份
  • 依次用这若干份数据实例化新 Node（新 Node 即是当前 Node 的子节点），同时将当前 Node 的相关信息传给新 Node。这里需要注意的是，如果划分标准是离散型特征的话：
    • 若算法是 ID3 或 C4.5，需将该特征对应的维度从新 Node 的self.feats属性中除去
    • 若算法是 CART，需要将二分标准从新 Node 的二分标准取值集合中除去
  • 最后对新 Node 调用fit方法、完成递归

我个人实现的版本可以参见这里

以上我们就实现了 Node 结构并在其上实现了决策树的生成算法，接下来我们要做的就是实现 Tree 结构来将各个 Node 封装起来

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