"""在固定留出集上比较深度受限的分类树与小型随机森林。""" import json import matplotlib.pyplot as plt import numpy as np def make_data(values): # 穷举两路读数的组合,展平为每行一对观测。 a, b = np.meshgrid(values, values) readings = np.column_stack((a.ravel(), b.ravel())) # 第三列作为干扰特征。标签只由前两路的阈值组合产生。 noise = ((7 * np.arange(1, len(readings) + 1)) % 11) / 10 labels = ((readings[:, 0] >= 2.5) & (readings[:, 1] < 3.5)) | (readings[:, 1] >= 4.2) return np.column_stack((readings, noise)), labels.astype(int) def teaching_rng(seed): # 使用简单的整数递推保证两个语言实验抽到相同的训练行与候选列。 # 这是教学用随机序列。真实项目可以直接使用库提供的随机数生成器。 while True: seed = (48271 * seed) % 2147483647 yield seed def gini(labels): # 标签为 0/1,均值是正类比例 p,二分类基尼不纯度为 2p(1-p)。 share = labels.mean() return 2 * share * (1 - share) def fit_tree(x, y, depth, rng=None): # 叶节点保留多数类别;深度耗尽、样本不足或类别已纯时直接返回。 vote = int(y.mean() > 0.5) if depth == 0 or len(y) < 4 or gini(y) == 0: return vote features = list(range(x.shape[1])) if rng is not None: # 先排除随机抽到的一列,其余两列为这个节点的候选。 features.pop(next(rng) % len(features)) best_gain = 1e-12 best = None parent = gini(y) for j in features: values = np.unique(x[:, j]) # 只需比较相邻不同值之间的中点,同一区间内切分得到的成员相同。 for cut in (values[:-1] + values[1:]) / 2: left = x[:, j] <= cut n_left = int(left.sum()) if n_left < 2 or len(y) - n_left < 2: continue left_weight = n_left / len(y) # 以左右分支的样本占比加权,衡量切分减少了多少不纯度。 gain = parent - left_weight * gini(y[left]) - (1 - left_weight) * gini(y[~left]) if gain > best_gain + 1e-12: best_gain, best = gain, (j, float(cut), left) if best is None: return vote j, cut, left = best return j, cut, fit_tree(x[left], y[left], depth - 1, rng), fit_tree(x[~left], y[~left], depth - 1, rng) def predict(tree, x): # 整数代表叶子的类别;元组则记录特征、阈值与两棵子树。 if isinstance(tree, int): return np.full(len(x), tree, dtype=int) j, cut, left, right = tree choose_left = x[:, j] <= cut result = np.empty(len(x), dtype=int) result[choose_left] = predict(left, x[choose_left]) result[~choose_left] = predict(right, x[~choose_left]) return result def run(): x_train, y_train = make_data(np.arange(6)) x_test, y_test = make_data(np.arange(5) + 0.4) y_train[[7, 17]] = 1 - y_train[[7, 17]] # 两条合成错标,只发生在训练集 depth, tree_count = 3, 15 tree = fit_tree(x_train, y_train, depth) rng = teaching_rng(seed=23) forest = [] for _ in range(tree_count): # 有放回抽取等长训练表。同一个索引可在一棵树里重复出现。 sample = [next(rng) % len(x_train) for _ in range(len(x_train))] forest.append(fit_tree(x_train[sample], y_train[sample], depth, rng)) baseline = int(y_train.mean() > 0.5) tree_test = predict(tree, x_test) # 票表的轴是“树数 × 留出样本数”,沿树轴平均即每条记录的正类投票比例。 votes = np.array([predict(member, x_test) for member in forest]) vote_share = votes.mean(axis=0) forest_test = vote_share > 0.5 # 只在图上固定第三列,让前两列的决策区域可视。测试仍使用原始第三列。 a, b = np.meshgrid(np.linspace(0, 5, 100), np.linspace(0, 5, 100)) plane = np.column_stack((a.ravel(), b.ravel(), np.full(a.size, 0.5))) single_region = predict(tree, plane).reshape(a.shape) forest_region = (np.mean([predict(member, plane) for member in forest], axis=0) > 0.5).reshape(a.shape) fig, axes = plt.subplots(1, 3, figsize=(11, 3.6), layout="constrained") for ax, region, title in zip(axes, [single_region, forest_region], ["Single tree", "Forest vote"]): ax.contourf(a, b, region, levels=[-0.5, 0.5, 1.5], colors=["#dceafd", "#f9dfc8"]) for label, color in [(0, "C0"), (1, "C1")]: rows = x_train[y_train == label] ax.scatter(rows[:, 0], rows[:, 1], color=color, s=13) ax.set(xlabel="Sensor 1", ylabel="Sensor 2", title=title) feature, threshold = tree[:2] if feature == 0: axes[0].axvline(threshold, color="black", linestyle="--", label="Root split") elif feature == 1: axes[0].axhline(threshold, color="black", linestyle="--", label="Root split") if feature < 2: axes[0].legend(fontsize=8) count = np.arange(1, tree_count + 1) shown_test_row = 13 share_trace = np.cumsum(votes[:, shown_test_row - 1]) / count axes[2].plot(count, share_trace, "o-", markersize=3) axes[2].axhline(0.5, color="gray", linestyle="--") axes[2].set(xlabel="Trees included", ylabel="Positive vote fraction", ylim=(-0.03, 1.03), title=f"Held-out row {shown_test_row}") return { "training_rows": len(y_train), "test_rows": len(y_test), "root_feature": feature + 1, "root_threshold": threshold, "tree_count": tree_count, "max_depth": depth, "preview_row": shown_test_row, "test_accuracy": [float(np.mean(y_test == baseline)), float(np.mean(y_test == tree_test)), float(np.mean(y_test == forest_test))], "tree_test_predictions": tree_test.tolist(), "forest_test_predictions": forest_test.astype(int).tolist(), "forest_positive_votes": votes.sum(axis=0).tolist(), "preview_vote_trace": share_trace.tolist(), } if __name__ == "__main__": print("LAB_RESULT " + json.dumps(run(), allow_nan=False)) plt.show()