8.5 从零实现ID3与C4.5算法#
在前面几节内容中，我们详细介绍了ID3与C4.5决策树算法的原理与计算示例，并且还介绍了如何借助开源的sklearn框架来完成整个建模的搭建流程。在接下来的这节内容中将会详细地来介绍如何从零一步步地实现ID3与C4.5这两种决策树算法。
8.5.1 节点定义实现#
由ID3与C4.5决策树算法的原理可知，两者的唯一差别就是体现在对于特征划分标准的不同上，前者采用的信息增益，而后者则采用的是信息增益比来进行判断。因此，两者在代码实现时只需要将这部分内容单独抽象成一个函数即可，其它部分的代码可以保持不变。本节所有实现代码可参见AllBooKCode/Chapter08/C03_id3_categorical.py 文件。
在实现决策树之前，需要先来定义决策树中每个节点的组成成份。同时，参考图8-4中的节点信息，这里将决策树的节点定义为如下形式：
1 class Node(object):
2 def __init__(self, ):
3 self.sample_index = None # 保存当前节点中对应样本在数据集中的索引
4 self.values = None # 保存每个类别的数量
5 self.features = None # 保存当前节点状态时特征集中剩余特征
6 self.feature_id = -1 # 保存当前节点对应划分特征的id
7 self.label = None # 保存当前节点对应的类别标签（叶子节点才有）
8 self.n_samples = 0 # 保存当前节点对应的样本数量
9 self.children = {} # 保存当前节点对应的孩子节点
10 self.criterion_value = 0.
11 self.n_leaf = 0 # 以当前节点为根节点时其叶子节点的个数
12 self.leaf_costs = 0. 在上述代码中，第3行sample_index用来保存当前节点中对应样本在数据集中的索引，这样我们在需要的时候可以直接通过索引去取到对应的样本而不是保存到每个节点中，同时也方便根据索引来取对应的样本标签。第4行values用来保存每个类别的数量，例如[10,4,6]则表示第0、1、2这三个类别在当前节点中的数量分别是10、4和6，其作用是根据这一结果可以知道当前叶子节点所代表的类别。第5行features用于保存在当前节点状态时特征集中剩余特征维度（即还剩下哪些特征没有被用于前面的划分中），例如[0,2,3]则表示对于当前节点来说，其备选特征为第0、2和3个。第6行feature_id用于保存当前节点对应划分特征的id，因为在决策树预测阶段时需要知道当前节点是用哪个特征来进行划分的。第7行label用来保存当前节点对应的类别标签（叶子节点才有），不过这个可选，因为通过前面的values也能够得到当前叶子节点的所属类别。第8行n_samples用来保存当前节点对应的样本数量，用于分析观察。第9行children用来保存当前节点对应的所有孩子节点，因为利用ID3和C4.5生成的决策树为n叉树，所以我们这里定义了一个字典来进行存储，其中key为特征取值，value为对应的孩子节点，值得一提的是在sklearn框架中这部分均采用的是二叉树来进行实现。第10行criterion_value则是用来保存当前节点对应的信息熵。第11行是记录以当前节点为根节点时其叶子节点的个数。第12行是记录以当前节点为根节点时其所有叶子节点的损失和，这两行主要用于后续剪枝部分的代码实现。
同时，为了在打印输出构建好的决策树的能够更加方便，需要定义如下方法，示例代码如下：
1 def __str__(self):
2 return f"<======================>\n" \
3 f"当前节点所有样本的索引({self.sample_index})\n" \
4 f"当前节点的样本数量({self.n_samples})\n" \
5 f"当前节点每个类别的样本数({self.values})\n" \
6 f"当前节点对应的信息增益（比）({round(self.criterion_value, 3)})\n" \
7 f"当前节点状态时特征集中剩余特征({self.features})\n" \
8 f"当前节点状态时划分特征ID({self.feature_id})\n" \
9 f"当前节点对应的类别标签为({self.label})\n" \
10 f"当前节点为根节点对应孩子节点数为({self.n_leaf})\n" \
11 f"当前节点为根节点对应孩子节点损失为({self.leaf_costs})\n" \
12 f"当前节点对应的孩子为({self.children.keys()})"这里值得一提的是__str__方法是Python中每个类对象都有的一个方法，只是默认情况下没有进行实现。__str__方法的作用是在通过print函数打印类的实例化对象时输出的便是上面定义的信息，而不是默认情况下的对象内存地址。例如：
1 if __name__ == '__main__':
2 node = Node()
3 print(node)
4 # <======================>
5 # 当前节点所有样本的索引(None)
6 # 当前节点的样本数量(0)
7 # 当前节点每个类别的样本数(None)
8 # 当前节点对应的信息增益（比）(0.0)
9 # 当前节点状态时特征集中剩余特征(None)
10 ......8.5.2 信息熵与条件熵实现#
根据8.3节内容可知，无论是ID3还是C4.5生成算法都需要计算样本的信息熵、特征的信息熵（在C4.5中）以及在某一特征取值下的条件熵。同时，需要说明的是，在本节内容中我们是以离散型输入特征为例进行的实现，在下一节内容中再来介绍能够同时处理离散型和连续型特征的实现方式。
根据式(8-8)信息熵的计算公式可知，其对应的代码实现如下所示：
1 class DecisionTree(object):
2 def __init__(self, min_samples_split=2, criterion='id3',
3 epsilon=1e-5, alpha=0.):
4 self.root = None
5 self.min_samples_split = min_samples_split # 用来控制是否停止分裂
6 self.epsilon = epsilon # 用来控制是否停止分裂
7 self.criterion = criterion # 划分标注，ID3还是C4.5
8 self.alpha = alpha
9
10 def _compute_entropy(self, y_class):
11 y_unique = np.unique(y_class)
12 if y_unique.shape[0] == 1: # 只有一个类别
13 return 0. # 熵为0
14 ety = 0.
15 for i in range(len(y_unique)): # 取每个类别
16 p = np.sum(y_class == y_unique[i]) / len(y_class)
17 ety += p * np.log2(p)
18 return -ety在上述代码中，第2~8行是定义类DecisionTree的初始化函数，其中第4行是保存决策树的根节点，第5行用来指定节点中停止分裂的最少样本数，第6行用来指定节点停止分裂的最小阈值，第7行指定采用ID3还是C4.5进行特征划分，第8行是后续实现剪枝过程时的惩罚参数。第10行则是定义一个方法来计算信息熵，主要用于ID3和C4.5中计算样本的信息熵，以及C4.5中特征的信息熵。第11行是计算得到当前输入有多少种类别（或特征取值）。第12~13行则是判断如果只有一个类别则信息熵为0。第15~17行是分别遍历每一个类别，然后根据式(8-8)来计算信息熵。
进一步，在实现完信息熵的计算以后，可以根据式(8-9)来编码实现条件熵的计算，示例代码如下：
1 def _compute_condition_entropy(self, X_feature, y_class):
2 f_unique = np.unique(X_feature)
3 result = 0.
4 for i in range(len(f_unique)):
5 index_x = (X_feature == f_unique[i])
6 p = np.sum(index_x) / len(y_class)
7 ety = self._compute_entropy(y_class[index_x]
8 result += p * ety
9 return result在上述代码中，第1行X_feature表示数据集中的某一列特征，y_class表示样本的类别标签。第2行是计算得到特征维度中的取值情况。第4行开始遍历每一个特征取值。第5行是取当前特征类别对应的索引。第7~8行是先计算样本对应的信息熵，然后再计算条件熵。
到此，在实现信息熵与条件熵实现的计算过程后，对于8.3.2节中的计算过程便可以通过以下方式完成，示例代码如下：
1 def load_simple_data():
2 x = np.array([['0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1'],
3 ['1', '1', '1', '0', '1', '0', '0', '0', '0', '0', '1', '1', '1', '0', '0'],
4 ['T', 'S', 'S', 'T', 'T', 'T', 'D', 'T', 'T', 'D', 'D', 'T', 'T', 'S', 'S']])
5 y = np.array([1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1])
6 return x.transpose(), y
7
8 def test_compute():
9 x, y = load_simple_data()
10 dt = DecisionTree()
11 ety = dt._compute_entropy(y)
12 print(f"信息熵为{ety}")
13 for i in range(x.shape[1]):
14 print(f"条件熵为{dt._compute_condition_entropy(x[:, i], y)}")
15
16 if __name__ == '__main__':
17 test_compute()
18
19 # 信息熵为0.91829
20 # 条件熵为0.74967
21 # 条件熵为0.80945
22 # 条件熵为0.909038.5.3 决策树构建实现#
在实现完信息熵和条件熵的计算过程后，下面再来封装一个方法并根据指定参数返回信息增益或者是信息增益比的结果来作为节点划分时的标准，这部分示例代码如下：
1 def _split_criterion(self, ety, X_feature, y_class):
2 c_ety = self._compute_condition_entropy(X_feature, y_class)
3 info_gains = ety - c_ety # 计算信息增益
4 if self.criterion == "id3":
5 return info_gains
6 elif self.criterion == "c45":
7 f_ety = self._compute_entropy(X_feature)
8 return info_gains / f_ety
9 else:
10 raise ValueError(f"划分标准 self.criterion = {self.criterion}只能是 id3 和 c45 其中之一！")在上述代码中，第1行的3个参数分别是传入的信息熵、对应的特征列和样本标签。第2行是计算每个特征下的条件熵。第3行是计算对应特征下的信息增益。第4~8行是根据参数来返回对应的划分指标，其中第7行是计算特征对应的信息熵。第10行则是进行错误提示。
在做完前面的整个铺垫过程后，下面便可以正式以递归的方式构建生成决策树了。由于这部分代码较长这里分成两部分来进行介绍，第一部分示例代码如下：
1 def _build_tree(self, data, f_ids):
2 x_ids = np.array(data[:, -1], dtype=np.int).reshape(-1)
3 labels = self._y[x_ids]
4 node = Node()
5 node.sample_index = x_ids
6 node.n_samples = len(labels)
7 node.values = np.bincount(labels, minlength=self.n_classes)
8 node.features = f_ids
9 if self.root is None:
10 self.root = node
11 y_unique = np.unique(labels)
12 if y_unique.shape[0] == 1 or len(f_ids) < 1 \
13 or node.n_samples <= self.min_samples_split:
14 node.label = self._get_label(labels)
15 return node
16 ety = self._compute_entropy(labels)
17 node.criterion_value = ety在上述代码中，第1行中data表示当前节点中的所有样本点，f_ids表示当前节点中还要哪些特征是可用的（剩余特征）。第2行是得到每个样本在原始数据集中的索引，因此在调用_build_tree方法前需要在训练集的最后一列追加上样本的索引。第3行是根据样本索引取对应的类别标签。第4~8行是先定义当前节点并保存对应的节点信息。第9~10行是判断根节点是否为空，如果为空则将当前节点作为根节点。第11~15行是8.3.3节生成步骤中第(1)和(2)步的体现，同时还增加了最小样本数的判断条件。第14行是根据多数原则确定当前节点对应的类别。第16行是计算当前节点所有样本对应的信息熵。