8.6 连续型特征变量下决策树实现#
在上一节内容中，我们详细介绍了如何基于ID3与C4.5的原理来一步一步从零开始实现决策树模型，不过由于原始的决策树模型均是针对离散型的特征变量，因此并不能对连续型的特征变量进行建模处理。在这节内容中将采用sklearn库中的做法来对连续型特征进行离散化处理，并以此来实现ID3与C4.5的建模过程。值得一提的是，在sklearn中不管输入的是离散型变量还是连续型变量，都会先对其以同样的方式来进行离散化处理，下面我们也将采用同样的做法来进行处理。
8.6.1 特征离散化实现#
由于在8.5节内容中我们已经详细介绍了对于离散型特征输入的ID3与C4.5的决策树实现过程，因此接下来只需要以之前的代码框架为基础，对其中部分判断逻辑进行修改即可。在实现这部分内容之前，先来介绍如何对特征进行离散化。本节所有实现代码可参见AllBooKCode/Chapter08/C04_id3_continuous.py 文件。
根据8.3.5节内容可知，连续型特征变量的离散化过程可以先对原始特征进行排序处理，然后取所有连续两个值的均值来离散化整个连续型特征变量。在清楚上述特征离散化的原理后，便可以来进一步对其编码实现，示例代码如下：
1 def _get_feature_values(self, data):
2 n_features = data.shape[1]
3 feature_values = {}
4 for i in range(n_features):
5 x_feature = sorted(set(data[:, i])) # 去重与排序
6 tmp_values = [x_feature[0]] # 左边插入最小值
7 for j in range(1, len(x_feature)):
8 tmp_values.append(round((x_feature[j - 1] + x_feature[j]) / 2, 4))
9 tmp_values.append(x_feature[-1]) # 右边插入最大值
10 feature_values[i] = tmp_values
11 return feature_values在上述代码中，第2行是得到特征的维度数量。第4~5行是遍历每一列特征维度并进行排序以及去重处理。第7~8行是计算得到两两相邻的特征值之间的平均值作为离散特征。第6、9行是为了方便后续决策树的实现，所以在离散化特征的两个端点分别加入了原始特征中的最小值和最大值。
最终，通过上述方法便可以得到离散化后的数据特征。例如对于如下测试数据来说
1 x = np.array([[3, 4, 5, 6, 7],
2 [2, 2, 3, 5, 8],
3 [3, 3, 8, 8, 9.]])
4 x = _get_feature_values(x)
5 print(x)
6 {0: [2.0, 2.5, 3.0], 1: [2.0, 2.5, 3.5, 4.0], 2: [3.0, 4.0, 6.5, 8.0],
7 3: [5.0, 5.5, 7.0, 8.0], 4: [7.0, 7.5, 8.5, 9.0]}在上述结果中，第6~7行便是原始输入特征离散化后的结果，其中key表示特征维度的ID，value表示该特征维度对应的离散化特征取值。
8.6.2 信息熵与条件熵实现#
在完成特征离散化的编码工作后，下一步便可以开始对第8.5.2中实现的代码进行修改以满足离散化特征的需求，信息熵计算代码的修改部分如下：
1 def _compute_entropy(self, y_class):
2 y_unique = np.unique(y_class)
3 if y_unique.shape[0] == 1: # 只有一个类别
4 return 0. # 熵为0
5 ety = 0.
6 for i in range(len(y_unique)): # 取每个类别
7 p = np.sum(np.abs(y_class - y_unique[i]) < 0.0001) / len(y_class)
8 ety += p * np.log2(p)
9 return -ety在上述代码中，第1行是定义一个方法来计算信息熵，主要用于ID3和C4.5中计算样本的信息熵，以及C4.5中特征的信息熵。第2行是计算得到当前输入有多少种类别（或特征取值）。第3~4行则是判断如果只有一个类别则信息熵为0。第6~8行是分别遍历每一个类别，然后计算信息熵。值得注意的是，因为同时要计算特征维度的信息熵，而特征是浮点型所以一般不会用==来判断两者是否相等。
进一步，可以编码完成条件熵的计算过程，示例代码如下：
1 def _compute_condition_entropy(self, X_feature, id, y_class):
2 f_unique = self.feature_values[id]
3 result = 0.
4 for i in range(len(f_unique) - 1): # 取每个特征类别
5 index_x = (f_unique[i] <= X_feature) & (X_feature <= f_unique[i + 1])
6 # 离散化后的特征则判断当前特征值是否存在于某个区间
7 p = np.sum(index_x) / len(y_class) # 取索引对应的标签
8 ety = self._compute_entropy(y_class[index_x]) # 计算标签对应的信息熵
9 result += p * ety # 计算条件熵
10 return result在上述代码中，第1行X_feature表示数据集中的某一列特征，id表示当前特征列对应的索引，y_class表示样本的类别标签。第2行是根据特征维度的id作为key从8.6.1节中离散化的结果中取到相应特征维度的取值情况。第4行开始是遍历每一个特征取值。第5行是根据取值区间判断结果来得到满足条件的特征值对应的索引。第7~9行是先计算样本对应的信息熵，然后再计算条件熵。
值得一提的是，因为特征被离散化后便形成了一个个的区间范围， 因此决策树在进行特征分裂时判断的其实是当前特征值属于哪个取值区间，然后再选择对应的节点。例如对于第8.3.5节中的示例来说，离散化结果便是将原始特征划分成了[0.35,0.65],[0.65,0.85],[0.85,1.05][1.05,1.65],[1.65,2.65],[2.65,3.85]这6个区间。此后对于任意新输入的特征$x$，决策树在预测时都是先判断其属于哪个区间，然后再进入到区间所对应的子节点中。
8.6.3 决策树构建实现#
在实现完信息熵和条件熵的计算过程后，下面再来封装一个方法来根据指定参数返回信息增益或者是信息增益比的结果来作为节点划分时的标准，示例代码如下：
1 def _split_criterion(self, ety, X_feature, id, y_class):
2 c_ety = self._compute_condition_entropy(X_feature, id, 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行的4个参数分别是传入的信息熵、对应的特征列、特征ID和样本标签。第2行是计算每个特征下的条件熵。第3行是计算对应特征下的信息增益。第4~8行是根据参数来返回对应的划分指标，其中第7行是计算特征对应的信息熵；第10行则是进行错误提示。
在做完前面的整个铺垫过程后，下面就可以正式的来递归构建生成决策树了。由于这部分代码整体上同第8.5.3节中对应部分的内容差别不大，因此我们下面就只介绍两者的差异之处，示例代码如下：
1 def _build_tree(self, data, f_ids):
2 # 此处省略 ......
3 node.feature_id = best_feature_id
4 feature_values = self.feature_values[best_feature_id] # 得到当前特征离散化后特征的取值情况
5 candidate_ids = copy.copy(f_ids)
6 candidate_ids.remove(best_feature_id) # 当前节点划分后的剩余特征集
7 for i in range(len(feature_values) - 1): # 依次遍历特征离散化后的每个取值情况
8 v = data[:, best_feature_id]
9 c = (feature_values[i] <= v) & (v <= feature_values[i + 1])
10 index = np.array([i for i in range(len(c)) if c[i] == True]) # 获取对应的索引
11 if len(index) == 0: # 如果当前特征取值范围没有样本，则继续
12 continue
13 node.children[str(feature_values[i + 1])] = self._build_tree(data[index], candidate_ids)
14 return node在上述代码中，第4行是取最佳划分特征中特征的取值情况。第5~6行是从一开始传入的特征列表f_ids中去除此时选中的最佳特征，而之所以要先复制是因为后续要依次遍历最佳特征中的每个特征取值并递归的构建决策树（第13行），而f_ids是一个列表，传入函数_build_tree时本质上是传入的地址，这就会导致每次递归操作都会改变其中的值，因此需要先进行复制。第7~13行是依次遍历特征离散化后的每个取值情况，然后根据当前特征维度的取值，来取对应的样本索引，并递归的进行节点划分；同时，由于离散化的特征值是浮点型，所以第13行将key转换成字符串来进行保存。