决策树在稀疏/非稀疏数据集上的验证准确率疑问与原理探究

实验背景 #

有观点提到决策树在存在稀疏特征时会过拟合数据，为验证这一点，设计了如下实验：在仅含单个feature属性和二分类标签y的数据集上拟合决策树，对比两种场景的平均验证准确率：

• 数据集稀疏（feature列多数值为0）
• 数据集非稀疏

实验代码 #

import random
import pandas as pd
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score


def accuracy_for_given_percentage_of_sparse_data(percentage_of_sparse_data):
    n = 1000  # size of the dataframe or number of datapoints

    number_of_sparse_datapoints = int(percentage_of_sparse_data * n)
    number_of_non_sparse_datapoints = n - number_of_sparse_datapoints

    average_accuracy = 0
    number_of_runs = 1000

    for run in range(0, number_of_runs):
        # Setting 0s as values of feature
        feature = [0 for i in range(0, number_of_sparse_datapoints)]

        # Setting some random non zero values for feature
        for i in range(0, number_of_non_sparse_datapoints):
            feature.append(random.randint(1, 50))

        # Generate the random binary class labels
        y = [random.randint(0, 1) for i in range(0, n)]

        d = {
            'feature': feature,
            'y': y
        }

        df = pd.DataFrame(data=d)
        clf = DecisionTreeClassifier(criterion="gini", splitter='best', class_weight='balanced')

        feature_cols = ['feature']
        X = df[feature_cols]
        y = df.y

        X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.33, random_state=42)

        # Train Decision Tree Classifer
        clf = clf.fit(X_train, y_train)

        average_accuracy += accuracy_score(y_test, clf.predict(X_test))

    return average_accuracy / number_of_runs


print("Average accuracy for sparse data: ", accuracy_for_given_percentage_of_sparse_data(0.9))
print("Average accuracy for non-sparse data: ", accuracy_for_given_percentage_of_sparse_data(0.1))

实验输出 #

Average accuracy for sparse data:  0.5015030303030307
Average accuracy for non-sparse data:  0.5009696969696967

问题解答 #

1. 两种场景准确率无明显差异的原因 #

实验的核心疏漏在于生成的特征与标签完全独立，不存在任何关联：

• 标签y是完全随机生成的，和feature的取值没有任何统计相关性。这种情况下，不管feature是否稀疏，决策树都无法从数据中学到有效的预测模式，训练时只能拟合噪声，而测试集的预测结果本质是随机猜测，准确率自然接近二分类的随机水平（0.5），因此两种场景不会有明显差异。
• 额外补充：即使设置了class_weight='balanced'，但由于数据本身无关联，该参数无法改变模型的随机预测本质；单特征的实验设计也限制了决策树的分裂空间，但核心问题还是特征与标签的独立性。

2. 决策树在稀疏特征下过拟合的数学直觉 #

决策树的核心目标是通过特征分裂最小化节点的不纯度（如Gini系数、熵），稀疏特征的特性会放大其过拟合风险：

• 稀疏特征的样本分布极端：大部分样本为0，仅少数样本为非零值。决策树在分裂时，会倾向于把这些少数非零样本单独划分为一个节点——只要这些样本的标签在训练集中恰好呈现一致（哪怕只是偶然的噪声），该节点的不纯度会被降到极低，符合决策树的优化目标。
• 但这种分裂是针对训练集的偶然情况拟合的，而非数据的真实模式。当测试集中出现非零值样本时，其标签可能和训练集的偶然情况不符，导致预测错误，体现为模型过拟合。
• 从数学角度看，稀疏特征的非零子集样本量极小，节点不纯度的计算容易被小样本的随机波动主导，决策树会过度拟合这些波动，而忽略整体数据的分布规律。

内容的提问来源于stack exchange，提问作者Deepak Tatyaji Ahire