P5917. 用 CART 分类树预测客户是否购房

场次：2026年10月14日-AI方向 · 来源：CodeFun2000 P5917

题目描述

CART（Classification and Regression Trees）分类树通过二元切分，递归地把样本划入不纯度更低的子集。分裂特征和切分点由基尼指数（Gini Index）算出，得到一棵二叉树；离散取值和连续取值都可以参与分裂。本题用这棵 CART 分类树预测客户是否购房。根据训练集建出二叉决策树，每个节点按基尼指数选择特征和切分点，再对测试样本给出预测。

划分规则： 对每一个特征，把它所有可能的取值逐一当作切分点，当前节点的样本分成左子集和右子集：

左子集：特征值 = 切分点
右子集：特征值 ≠ 切分点

数据集说明

每条记录包含 4 个特征和 1 个标签，输入时全部写成整数枚举。

特征1： 年龄段（0：18-30岁；1：31-40岁；2：41-55岁；3：56岁及以上）
特征2： 婚姻状况（0：单身；1：恋爱；2：已婚）
特征3： 是否有房（0：无；1：有）
特征4： 是否有工作（0：无；1：有）
标签： 购房结果（0：否；1：是）

基尼指数计算公式

数据集里若有 (K) 个类别，(p_k) 表示第 (k) 类样本所占比例： [ Gini(D) = 1 - \sum_{k=1}^{K} p_k^2 ]

加权基尼指数 特征 (A) 以取值 (v) 为切分点时，(D) 被分成 (D_1(A=v)) 与 (D_2(A \neq v))： [ Gini(D, A, v) = \frac{|D_1|}{|D|} \times Gini(D_1) + \frac{|D_2|}{|D|} \times Gini(D_2) ]

预测规则

叶子节点输出该节点中人数最多的类别；若两个类别人数相同，输出编号较小的类别。

停止分裂条件

下面任一条件成立，节点即停止分裂：

节点内全部样本的标签相同
节点内的样本数小于 2
不存在使基尼指数降低的切分点

平局处理规则

按特征编号从小到大遍历（特征1 → 特征2 → 特征3 → 特征4）
对当前特征，按取值从小到大遍历全部可能切分点
计算各切分点的加权基尼指数，保留其中最小的切分
若若干特征的加权基尼指数同为最小，取编号较小的特征
若同一特征上若干取值的加权基尼指数同为最小，取较小取值作为切分点（左子集是该特征等于这个较小值的样本）

解答要求

时间限制：C/C++ 1000ms，其他语言 2000ms
内存限制：C/C++ 512MB，其他语言 1024MB

输入格式

第一行给出整数 (N)，表示训练集的客户人数（(4 \le N \le 20)）。随后 (N) 行，每行 5 个整数，依次是 4 个特征和 1 个标签，整数之间以空格分隔。第 (N+2) 行给出整数 (M)，表示待预测的样本人数（(1 \le M \le 10)）。随后 (M) 行，每行 4 个整数，依次是 4 个特征，整数之间以空格分隔。

输出格式

输出一行，共 (M) 个整数，依次为 (M) 个测试样本在所建 CART 树上的预测结果，整数之间以空格分隔。

示例

示例 1

输入：

输出：

0 1 0 1

说明：

根节点共 8 名客户，标签 0（否）与标签 1（是）各 4 人，所以 [ Gini(D) = 1 - (4/8)^2 - (4/8)^2 = 0.5 ]
选取加权基尼指数最小的切分。特征3（是否有房）取切分点 0 时，左子集 4 人标签全为 0，右子集 4 人标签全为 1，加权基尼指数为 0。取切分点 1 只是左右对调，加权基尼指数同样为 0。二者并列，按平局规则保留较小取值 0，左子集为「是否有房 = 0」。其余切分的加权基尼指数都大于 0。例如特征2（婚姻状况）取切分点 1 时，左子集 3 人里有 2 个 0、1 个 1，右子集 5 人里有 2 个 0、3 个 1，加权基尼指数为 (7/15)；特征4（是否有工作）取 0 或 1 时，两侧都是 2 个 0 与 2 个 1，加权基尼指数为 (1/2)。
左右子集的标签都已相同，停止分裂。左叶子预测 0，右叶子预测 1。
四个测试样本的特征3依次为 0、1、0、1。等于切分点的进入左子树，不等于的进入右子树，预测为 0 1 0 1。

解题思路

第一步：理解问题本质

CART 分类树是一棵二叉树，建树过程是递归的：对当前节点上的样本集合 $D$ ，找一个「最优切分」，把它分成左右两个子集，再对子集递归做同样的事，直到满足停止条件。

本题的切分方式很特别，必须先看清楚：

左子集：特征 $A$ 的取值恰好等于切分点 $v$ 的样本；
右子集：特征 $A$ 的取值不等于 $v$ 的样本。

注意这不是常见的有序阈值切分（ $A\le v$ 与 $A>v$ ），而是「等于某个值」与「其余」。所以取值是离散枚举，遍历顺序是「特征编号从小到大，同一特征内取值从小到大」。

衡量切分好坏的是基尼指数：

Gini(D)=1-\sum_{k=1}^{K}p_k^2

它表示「从 $D$ 里随机抽两个样本、类别不同」的概率：越纯的集合基尼越小，全是同一类时为 $0$ 。

一个切分把 $D$ 分成 $D_1$ 、 $D_2$ 后，用加权基尼指数评价：

Gini(D,A,v)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)

权重是子集人数占比，人数少的子集影响小。我们的目标是让这个值尽可能小。

三个停止条件对应三种「已经没必要再分」的情形：

节点内标签全相同——已经是纯节点，再分也不会更纯；
节点内样本数小于 $2$ ——一个样本分不出左右两边；
不存在使基尼指数降低的切分——再分只会更差或原地打转。

第二步：暴力解法

最直白的实现是：对每个候选 $(A,v)$ ，都把节点样本重新扫一遍，分别统计左右两侧每个类别的人数，再用浮点数算加权基尼。

def gini_float(labels):
    """按类别占比算基尼指数：1 - sum(p_k^2)。labels 是标签列表。"""
    total = len(labels)
    ratio_square_sum = 0.0
    for label in set(labels):
        p = labels.count(label) / total   # 每个类别都要重新数一遍
        ratio_square_sum += p * p
    return 1.0 - ratio_square_sum


def best_split_brute(rows):
    """rows 是当前节点上的样本，每行最后一位是标签。"""
    best = None
    for feature in range(4):
        # 候选取值直接取「全数据集」的所有取值
        for value in sorted(ALL_VALUES[feature]):
            left = [row for row in rows if row[feature] == value]
            right = [row for row in rows if row[feature] != value]
            score = (len(left) / len(rows) * gini_float([row[4] for row in left])
                     + len(right) / len(rows) * gini_float([row[4] for row in right]))
            if best is None or score < best[0]:
                best = (score, feature, value)
    return best

这份代码能算出正确答案，但有两处明显的浪费：

gini_float 对每个类别都调用一次 list.count，而 list.count 本身又要扫一遍列表，算一次基尼就是 $O(|D|\cdot K)$ ；每个候选还要算左右两个子集。
候选切分点取的是全数据集的取值。如果某个取值在当前节点里根本没出现，那么左子集为空、右子集等于全体，加权基尼与父节点完全相同——这种候选永远不可能被选中，纯粹在浪费时间。

第三步：优化解法——一次遍历统计左右计数

基尼指数只依赖各类别的人数，不依赖样本顺序。所以没必要为每个类别重扫列表，也没必要真的把左右子集构造出来：只要在遍历样本时把标签计数分别累加到 left_counts 和 right_counts 两个字典里即可。

同时，候选切分点只取当前节点中出现过的取值：

for feature in range(4):
    # 只枚举本节点真实出现过的取值
    for value in sorted({row[feature] for row in rows}):
        left_counts, right_counts = {}, {}
        for row in rows:
            if row[feature] == value:
                left_counts[row[4]] = left_counts.get(row[4], 0) + 1
            else:
                right_counts[row[4]] = right_counts.get(row[4], 0) + 1
        # 由计数直接算加权基尼，O(类别数) 而不是 O(样本数 * 类别数)
        score = weighted_gini(left_counts, right_counts, len(rows))

这样每个候选只需要 $O(|D|)$ 的时间，常数也小得多。对于本题 $N\le 20$ 的数据规模，这已经足够快。

第四步：最优解法 / 完整实现细节

算法框架定下来之后，剩下的都是「判分点」。本题最容易错的地方不是复杂度，而是平局和停止条件，它们的实现方式直接决定树长什么样。

1. 用精确分数比较基尼指数

基尼指数是有理数，例如 $\frac{7}{15}$ 、 $\frac{1}{2}$ 。如果用浮点数比较，「数学上相等」的两个候选可能因为舍入误差差出 $10^{-16}$ ，于是一个本该算平局的地方被判成了「后者更优」，平局规则就失效了。

所以用 fractions.Fraction 精确表示：

Gini(D)=1-\frac{\sum_k c_k^2}{(\sum_k c_k)^2}

代码里写成 1 - Fraction(sum(c*c), total*total)，全程不丢精度。

2. 只有严格下降才分裂

停止条件 3 要求「不存在使基尼指数降低的切分点」才停止。注意是降低，不是「不升高」。如果候选切分的加权基尼恰好等于父节点的基尼（最典型的情况是：某特征在节点内只有一个取值，左子集等于全体、右子集为空），它不算「更优」，不能分裂。

这条判断同时防止了无限递归：没有它，程序会在这种「原地切分」上反复调用自己。

3. 平局时保留先出现的候选

特征按 $1\to4$ 、取值按从小到大枚举；更新最优解时只用严格小于：

if best is None or score < best[0]:
    best = (score, feature, value)

这样一来，遇到同样小的候选时后面的不会覆盖前面的，最终留下的自然是「编号更小的特征、更小的取值」，正好就是题面的平局规则，不需要额外写比较逻辑。

4. 左子集一定非空，右子集可能为空

因为 $v$ 取自节点内出现过的取值，左子集至少有一个样本。但右子集可能是空集（节点内该特征全等于 $v$ ）。此时它的人数占比为 $0$ ，对加权基尼没有贡献，代码里 gini({}) 返回 $0$ 即可，不会出错。

5. 叶子输出与平票

叶子取人数最多的类别；人数相同时取编号较小的类别。把 (-人数, 类别编号) 作为排序键，min 一次就能得到正确结果。

6. 预测时沿树下降

从根开始：当前节点是切分节点就看样本在该特征上的取值，等于切分点走左子树，不等于走右子树；走到叶子就返回叶子的类别。

完整代码实现

import sys
from fractions import Fraction

FEATURES = 4   # 每条记录的特征个数，标签在它后面一位


def gini(counts):
    """按标签计数算基尼指数 Gini = 1 - sum(p_k^2)，用分数保证精确。"""
    total = sum(counts.values())
    if total == 0:
        return Fraction(0)      # 空集合没有不纯度，且它的权重也是 0
    square_sum = sum(count * count for count in counts.values())
    return 1 - Fraction(square_sum, total * total)


def majority_label(counts):
    """人数最多的标签；人数相同时取编号较小的标签。"""
    return min(counts, key=lambda label: (-counts[label], label))


def build(indices, rows):
    """递归建造 CART 分类树。

    节点表示：
    - ("leaf", 标签)
    - ("split", 特征下标, 切分点, 左子树, 右子树)
    """
    counts = {}
    for i in indices:
        label = rows[i][FEATURES]
        counts[label] = counts.get(label, 0) + 1

    # 停止条件 1、2：标签已纯，或样本数不足 2
    if len(indices) < 2 or len(counts) == 1:
        return ("leaf", majority_label(counts))

    total = len(indices)
    parent_gini = gini(counts)
    best = None    # (加权基尼, 特征下标, 切分点)

    for feature in range(FEATURES):
        # 候选只取本节点出现过的取值：没出现过的取值切不出样本，
        # 加权基尼与父节点相同，永远不可能更优
        for value in sorted({rows[i][feature] for i in indices}):
            left_counts, right_counts = {}, {}
            left_size = 0

            # 一次遍历同时统计左右两侧的标签计数
            for i in indices:
                label = rows[i][FEATURES]
                if rows[i][feature] == value:
                    left_counts[label] = left_counts.get(label, 0) + 1
                    left_size += 1
                else:
                    right_counts[label] = right_counts.get(label, 0) + 1
            right_size = total - left_size

            # 加权基尼指数：两侧按人数占比加权
            score = (Fraction(left_size, total) * gini(left_counts)
                     + Fraction(right_size, total) * gini(right_counts))

            # 只用严格更小更新：候选按特征升序、取值升序枚举，
            # 于是平局时留下的是编号更小的特征、更小的切分点
            if best is None or score < best[0]:
                best = (score, feature, value)

    # 停止条件 3：没有任何切分能让基尼指数严格下降
    if best is None or best[0] >= parent_gini:
        return ("leaf", majority_label(counts))

    _, feature, value = best
    left = [i for i in indices if rows[i][feature] == value]
    right = [i for i in indices if rows[i][feature] != value]
    return ("split", feature, value, build(left, rows), build(right, rows))


def predict(tree, sample):
    """沿树下降：等于切分点走左子树，否则走右子树。"""
    node = tree
    while node[0] == "split":
        _, feature, value, left, right = node
        node = left if sample[feature] == value else right
    return node[1]


def solve():
    tokens = sys.stdin.buffer.read().split()
    if not tokens:
        return

    pos = 0
    n = int(tokens[pos])
    pos += 1

    rows = []
    for _ in range(n):
        rows.append([int(tokens[pos + k]) for k in range(FEATURES + 1)])
        pos += FEATURES + 1

    m = int(tokens[pos])
    pos += 1

    tree = build(list(range(n)), rows)

    answers = []
    for _ in range(m):
        sample = [int(tokens[pos + k]) for k in range(FEATURES)]
        pos += FEATURES
        answers.append(str(predict(tree, sample)))

    print(" ".join(answers))


if __name__ == "__main__":
    solve()

NumPy 版本

以下版本使用 NumPy。只有在评测环境允许第三方库时才能提交；CodeFun2000 的普通 Python 环境不一定安装 NumPy。

import sys

import numpy as np

FEATURES = 4   # 每条记录的特征个数，标签在它后面一位


def majority_label(classes, counts):
    """人数最多的标签；人数相同时取编号较小的标签。

    np.argmax 返回第一个最大值的下标，而 np.unique 给出的 classes 是升序的，
    所以平票时自然落到编号较小的类别上。
    """
    return int(classes[np.argmax(counts)])


def build(indices, features, labels):
    """递归建造 CART 分类树。

    节点表示：
    - ("leaf", 标签)
    - ("split", 特征下标, 切分点, 左子树, 右子树)
    """
    size = indices.size
    node_labels = labels[indices]
    classes, inverse, counts = np.unique(
        node_labels, return_inverse=True, return_counts=True
    )

    # 停止条件 1、2：标签已纯，或样本数不足 2
    if size < 2 or classes.size == 1:
        return ("leaf", majority_label(classes, counts))

    # 标签独热矩阵 (n, K)：后面一次矩阵乘法就算出所有候选切分的左右计数
    onehot = np.zeros((size, classes.size), dtype=np.int64)
    onehot[np.arange(size), inverse] = 1

    parent_square = int(counts @ counts)        # 父节点各类人数的平方和
    node_features = features[indices]           # (n, 4)

    best = None                                 # 最优切分的 (分子, 分母)
    best_feature = -1
    best_value = None

    for feature in range(FEATURES):
        # 候选只取本节点出现过的取值，升序枚举 → 平局时留下较小的切分点
        values = np.unique(node_features[:, feature])
        equals = node_features[:, feature][None, :] == values[:, None]   # (V, n)

        # 一次矩阵乘法把 V 个候选切分的左右两侧类别计数全部算出来
        left_counts = equals.astype(np.int64) @ onehot                   # (V, K)
        right_counts = counts[None, :] - left_counts
        left_size = equals.sum(axis=1).astype(np.int64)                  # (V,)
        right_size = size - left_size

        left_square = (left_counts ** 2).sum(axis=1)
        right_square = (right_counts ** 2).sum(axis=1)

        # 加权基尼 = 1 - (sqL/nL + sqR/nR) / n，比较基尼等价于比较
        # term = sqL/nL + sqR/nR。为了不引入浮点误差，把 term 存成整数比 num/den
        both = (left_size > 0) & (right_size > 0)
        num = np.where(both, left_square * right_size + right_square * left_size, 0)
        den = np.where(both, left_size * right_size, 1)
        # 某一侧为空时 term 只剩另一侧那一项，分母就是该侧人数（等于全体人数）
        num = np.where(both, num, left_square + right_square)
        den = np.where(both, den, left_size + right_size)

        # 只用严格更大的 term 更新：候选按取值升序枚举，平局时先到者胜出
        for idx in range(values.size):
            if best is None or int(num[idx]) * best[1] > best[0] * int(den[idx]):
                best = (int(num[idx]), int(den[idx]))
                best_feature = feature
                best_value = int(values[idx])

    # 停止条件 3：没有任何切分能让加权基尼严格下降
    # term > parent_square / n  <=>  num * n > parent_square * den
    if best is None or best[0] * size <= parent_square * best[1]:
        return ("leaf", majority_label(classes, counts))

    left_mask = node_features[:, best_feature] == best_value
    return (
        "split",
        best_feature,
        best_value,
        build(indices[left_mask], features, labels),
        build(indices[~left_mask], features, labels),
    )


def predict(tree, sample):
    """沿树下降：等于切分点走左子树，否则走右子树。"""
    node = tree
    while node[0] == "split":
        _, feature, value, left, right = node
        node = left if sample[feature] == value else right
    return node[1]


def solve():
    tokens = sys.stdin.buffer.read().split()
    if not tokens:
        return

    pos = 0
    n = int(tokens[pos])
    pos += 1

    rows = np.array(
        tokens[pos:pos + n * (FEATURES + 1)], dtype=np.int64
    ).reshape(n, FEATURES + 1)
    pos += n * (FEATURES + 1)

    m = int(tokens[pos])
    pos += 1

    queries = np.array(tokens[pos:pos + m * FEATURES], dtype=np.int64).reshape(m, FEATURES)

    # 特征矩阵与标签分开存：建树时按列切特征、按行取标签都更直接
    features = rows[:, :FEATURES]
    labels = rows[:, FEATURES]

    tree = build(np.arange(n), features, labels)

    answers = [str(predict(tree, queries[i])) for i in range(m)]
    print(" ".join(answers))


if __name__ == "__main__":
    solve()

这一版和纯 Python 版的两处差别：

候选切分的左右计数交给 NumPy：equals 是 $V\times n$ 的布尔矩阵（第 $v$ 行表示「本节点中该特征取值等于第 $v$ 个候选值」），和标签独热矩阵相乘一次就得到 $V\times K$ 的左右计数，不必对每个候选重扫样本；
仍然不做浮点比较。纯 Python 版用 Fraction 保证平局判断正确，这里换成整数比：把 term = sqL/nL + sqR/nR（约掉分母后与加权基尼一一对应）记成一对整数 num/den，比较两个候选时交叉相乘 num_a * den_b 与 num_b * den_a，全是整数运算，结果精确。停止条件 $\text{term} > \text{parent}_{sq}/n$ 同样改写为 num * n > parent_square * den，一次除法都不做，平局规则（小特征、小取值）也就不会因为末位误差而失效。

示例推演

以样例 1 为例，训练集 8 条记录，标签 0（不购房）与标签 1（购房）各 4 条。

样本	年龄段	婚姻	有房	有工作	标签
1	0	0	0	0	0
2	1	1	0	1	0
3	2	2	0	0	0
4	3	1	0	1	0
5	0	1	1	0	1
6	1	2	1	1	1
7	2	0	1	0	1
8	3	2	1	1	1

第 1 步：根节点的基尼指数

Gini(D)=1-\left(\frac{4}{8}\right)^2-\left(\frac{4}{8}\right)^2=1-\frac12=\frac12

第 2 步：逐个特征找最优切分

特征1（年龄段），取值 0、1、2、3。这个特征上，每个取值恰好对应一个标签 0 与一个标签 1 的样本：

切分点	左子集（人数，0/1 分布）	右子集（人数，0/1 分布）	加权基尼
0	2 人，0:1 / 1:1	6 人，0:3 / 1:3	$\frac{2}{8}\times\frac12+\frac{6}{8}\times\frac12=\frac12$
1	2 人，0:1 / 1:1	6 人，0:3 / 1:3	$\frac12$
2	2 人，0:1 / 1:1	6 人，0:3 / 1:3	$\frac12$
3	2 人，0:1 / 1:1	6 人，0:3 / 1:3	$\frac12$

四个切分点都没有把两类分开，加权基尼与父节点一样，都是 $\frac12$ 。

特征2（婚姻状况），取值 0、1、2：

切分点	左子集	右子集	加权基尼
0	2 人，0:1 / 1:1	6 人，0:3 / 1:3	$\frac12$
1	3 人，0:2 / 1:1	5 人，0:2 / 1:3	$\frac{7}{15}$
2	3 人，0:1 / 1:2	5 人，0:3 / 1:2	$\frac{7}{15}$

特征3（是否有房），取值 0、1：

切分点	左子集	右子集	加权基尼
0	4 人，0:4 / 1:0	4 人，0:0 / 1:4	$0$
1	4 人，0:0 / 1:4	4 人，0:4 / 1:0	$0$

特征4（是否有工作），取值 0、1：两侧都是 2 个 0 与 2 个 1，两个切分点的加权基尼都是 $\frac12$ 。

第 3 步：按平局规则确定根节点

最小加权基尼是 $0$ ，只有特征3取到了。特征3的切分点 0 与 1 并列，按「取值较小者优先」取 0，于是根节点判断为「是否有房 = 0」：

左子集是样本 1～4，标签全为 0；
右子集是样本 5～8，标签全为 1。

第 4 步：左右子节点都停止分裂

左右两侧标签都已相同，满足停止条件 1，各自成为叶子。左叶子预测 0，右叶子预测 1。

第 5 步：预测 4 个测试样本

测试样本	是否有房	走哪边	预测
2 1 0 1	0	等于切分点 → 左	0
0 2 1 0	1	不等于切分点 → 右	1
3 0 0 0	0	等于切分点 → 左	0
1 1 1 1	1	不等于切分点 → 右	1

输出 0 1 0 1，与样例一致。

复杂度分析

解法	时间复杂度	空间复杂度	说明
暴力：每类别重扫 + 全局候选	$O(F\cdot V_{\text{all}}\cdot N^2\cdot K)$	$O(N)$	每个候选都要按类别重新数一遍，候选还包含节点里没有的取值
优化：一次遍历统计左右计数	$O(F\cdot V\cdot N^2)$	$O(N)$	每个候选 $O(N)$ 得到左右计数，候选只取节点内取值
最优：精确分数 + 严格下降剪枝	$O(F\cdot V\cdot N^2)$	$O(N)$	渐进复杂度相同，但用 `Fraction` 保证平局判断正确，且无意义的切分被剪掉

其中 $F=4$ 是特征数， $V$ 是节点内不同取值个数（ $V\le N$ ）， $K$ 是类别数（本题 $K=2$ ），树高不超过 $N$ 。本题 $N\le 20$ ，最坏也只是 $4\times20\times20\times20\approx3.2\times10^4$ 次基本操作，远低于 2 秒的限制。

空间上只需要保存样本表、当前节点的下标列表和树本身，都是 $O(N)$ 级别。

易错点总结

1. 切分是「等于 $v$ / 不等于 $v$ 」

不是常见的 $A\le v$ 与 $A>v$ 。左子集是「特征值恰好等于切分点」的样本，右子集是「其余所有样本」。把这两条规则写反，或者写成大小比较，树的结构会完全不同。

2. 必须「严格降低」才分裂

停止条件写的是「不存在使基尼指数降低的切分点」。当节点内某特征只有一个取值时，无论取什么切分点，左子集都是全体、右子集为空，加权基尼等于父节点。如果写成 score <= parent 就分裂，程序会在这类切分上无限递归。

3. 候选切分点取节点内出现过的取值

用全数据集的取值域也能得到同样的树（没出现过的取值只会得到「右子集 = 全体」，不可能更优），但会白白做很多无用计算。更重要的是，如果对空子集的处理写错（比如除以 $0$ ），就会直接崩溃。

4. 平局判断不能依赖浮点数

$\frac{7}{15}$ 、 $\frac{4}{9}$ 这类分数在二进制浮点里无法精确表示。两个数学上相等的加权基尼，浮点计算结果可能相差 $10^{-17}$ ，用 < 比较就会选出「错误的那一个」，而平局规则（小特征、小取值）也跟着失效。用 Fraction 精确比较可以彻底避免。

5. 平局时只保留先出现的候选

更新最优解要用严格小于 score < best[0]，不能用 <=。因为候选是按「特征升序、取值升序」枚举的，<= 会让后面的候选覆盖前面的，最终变成「大特征、大取值」，与题面规则相反。

6. 叶子平票取较小的标签

人数相同时，输出编号较小的类别。把 (-人数, 标签) 作为键取最小值即可，不要写成「取第一个出现的标签」——字典的遍历顺序并不可靠。

7. 预测时「不等于」走右子树

树里的切分点只记录了一个值 $v$ 。预测时样本在该特征上的取值只要不等于 $v$ ，无论比 $v$ 大还是小，都走右子树。

8. 停止条件是「样本数小于 2」

一个样本的节点无法分成左右两个非空子集，必须停止。注意是 < 2，一个样本就要停。另外标签全相同的判断要放在切分之前，否则纯节点还会继续尝试切分。

9. 输出格式

$M$ 个预测结果输出在同一行，用单个空格分隔，不要每个结果一行。

扩展思考

换成有序切分：如果特征是连续值，CART 会用 $A\le v$ 与 $A>v$ 切分，候选点是相邻取值的中点。此时每个特征的候选数从「不同取值个数」变成「不同取值个数 $-1$ 」，而枚举顺序要按取值升序。
回归树：把基尼指数换成均方误差 $\frac{1}{|D|}\sum (y_i-\bar y)^2$ ，其余框架（递归、停止条件、平局规则）完全一样。CART 的名字里同时包含分类与回归，原因就在这里。
多分类：基尼公式本身就支持 $K$ 个类别，代码里的计数用字典实现，不需要改动。只有「平票取小标签」这一条在类别数变多时仍然成立。
剪枝：本题的停止条件只保证训练集上的纯度，容易过拟合。实际使用时会先让树长深，再用验证集做代价复杂度剪枝（CCP）。
随机森林：单棵树对方差敏感，把「随机抽特征 + 随机抽样本」重复很多次再投票，就是随机森林。本题的 best split 逻辑正是森林里每棵树的核心。
手算与程序的一致性：题面给出的 $7/15$ 、 $1/2$ 都是精确分数。自己实现时如果发现某个候选的加权基尼与手算结果有微小差异，多半是浮点误差，而不是公式写错。

P5917. 用 CART 分类树预测客户是否购房

题目描述

数据集说明

基尼指数计算公式

预测规则

停止分裂条件

平局处理规则

解答要求

输入格式

输出格式

示例

示例 1

解题思路

第一步：理解问题本质

第二步：暴力解法

第三步：优化解法——一次遍历统计左右计数

第四步：最优解法 / 完整实现细节

完整代码实现

NumPy 版本

示例推演

第 1 步：根节点的基尼指数

第 2 步：逐个特征找最优切分

第 3 步：按平局规则确定根节点

第 4 步：左右子节点都停止分裂

第 5 步：预测 4 个测试样本

复杂度分析

易错点总结

1. 切分是「等于 $v$ / 不等于 $v$ 」

2. 必须「严格降低」才分裂

3. 候选切分点取节点内出现过的取值

4. 平局判断不能依赖浮点数

5. 平局时只保留先出现的候选

6. 叶子平票取较小的标签

7. 预测时「不等于」走右子树

8. 停止条件是「样本数小于 2」

9. 输出格式

扩展思考

相关题目

自测

题目描述​

数据集说明​

基尼指数计算公式​

预测规则​

停止分裂条件​

平局处理规则​

解答要求​

输入格式​

输出格式​

示例​

示例 1​

解题思路​

第一步：理解问题本质​

第二步：暴力解法​

第三步：优化解法——一次遍历统计左右计数​

第四步：最优解法 / 完整实现细节​

完整代码实现​

NumPy 版本​

示例推演​

第 1 步：根节点的基尼指数​

第 2 步：逐个特征找最优切分​

第 3 步：按平局规则确定根节点​

第 4 步：左右子节点都停止分裂​

第 5 步：预测 4 个测试样本​

复杂度分析​

易错点总结​

1. 切分是「等于 vvv / 不等于 vvv」​

2. 必须「严格降低」才分裂​

3. 候选切分点取节点内出现过的取值​

4. 平局判断不能依赖浮点数​

5. 平局时只保留先出现的候选​

6. 叶子平票取较小的标签​

7. 预测时「不等于」走右子树​

8. 停止条件是「样本数小于 2」​

9. 输出格式​

扩展思考​

相关题目​

自测​

题目描述

数据集说明

基尼指数计算公式

预测规则

停止分裂条件

平局处理规则

解答要求

输入格式

输出格式

示例

示例 1

解题思路

第一步：理解问题本质

第二步：暴力解法

第三步：优化解法——一次遍历统计左右计数

第四步：最优解法 / 完整实现细节

完整代码实现

NumPy 版本

示例推演

第 1 步：根节点的基尼指数

第 2 步：逐个特征找最优切分

第 3 步：按平局规则确定根节点

第 4 步：左右子节点都停止分裂

第 5 步：预测 4 个测试样本

复杂度分析

易错点总结

1. 切分是「等于 $v$ / 不等于 $v$ 」

2. 必须「严格降低」才分裂

3. 候选切分点取节点内出现过的取值

4. 平局判断不能依赖浮点数

5. 平局时只保留先出现的候选

6. 叶子平票取较小的标签

7. 预测时「不等于」走右子树

8. 停止条件是「样本数小于 2」

9. 输出格式

扩展思考

相关题目

自测