用于可扩展统计可靠数据挖掘的Few-Shot重采样方法

# 面向可扩展统计可靠数据挖掘的少次重采样

来源：https://arxiv.org/html/2606.11235

Leonardo Pellegrina  
Department of Information Engineering, University of Padova  
Via Gradenigo 6b, Padova, Italy, 35129  
[email protected] (https://arxiv.org/html/2606.11235v1/mailto:[email protected])

Fabio Vandin  
Department of Information Engineering, University of Padova  
Via Gradenigo 6b, Padova, Italy, 35129  
[email protected] (https://arxiv.org/html/2606.11235v1/mailto:[email protected])

(2026)

###### 摘要

知识发现的关键步骤之一是评估数据挖掘结果。在诸多应用中，包括模式挖掘、图分析等，该步骤包含对结果统计显著性的评估，以避免仅因数据中的噪声或随机波动而产生虚假发现。虽然针对某些特定应用已开发了专门的方法，但基于重采样的方法被广泛使用，尤其适用于无法获得解析结果的复杂分析。然而，当前基于重采样的方法需要生成和分析数千个重采样数据集，因此对于大型数据集或计算密集型分析而言不切实际。在本文中，我们提出 **FewRS**，一种简单有效的基于重采样的方法，用于评估数据挖掘结果的统计显著性，并对错误发现的概率提供严格保证。我们的方法可应用于任何采用重采样方法的场景。**FewRS** 建立在我们对表示数据挖掘结果质量的检验统计量的上确界偏差的新颖界限推导之上。我们证明 **FewRS** 需要生成和分析极少数量的重采样数据集，从而实现高度可扩展且广泛适用的方法。我们在模式挖掘和网络分析等常见任务上测试了该方法。在所有情况下，我们的方法相比现有技术水平将运行时间减少多达两个数量级，同时保持高统计功效，使得大规模真实世界数据集的数据挖掘结果统计验证成为可能。

统计可靠数据挖掘，重采样，模式挖掘，图挖掘，可扩展算法，FWER

††期刊年份:2026  
††版权:cc  
††会议:第32届ACM SIGKDD知识发现与数据挖掘会议 V.2；2026年8月9–13日，韩国济州岛  
††书刊:第32届ACM SIGKDD知识发现与数据挖掘会议 V.2 (KDD ’26)，2026年8月9–13日，韩国济州岛  
††DOI:10.1145/3770855.3817752  
††ISBN:979-8-4007-2259-2/2026/08  
††CCS:信息系统 → 数据挖掘  
††CCS:数学计算 → 概率与统计

## 1. 引言

知识发现是一个复杂过程，包含多个步骤，其目标是从复杂且大型的数据集中提取有用信息。该过程的关键组成部分是挖掘步骤 (Han et al., 2022 (https://arxiv.org/html/2606.11235#bib.bib8); Leskovec et al., 2020 (https://arxiv.org/html/2606.11235#bib.bib7))，在此步骤中，对数据集进行分析，以提取模式或其他数据特征（例如聚类），为最终用户提供可操作的信息或为后续分析提供依据。挖掘步骤中的一个关键问题是如何避免无趣或虚假的结果 (Tan et al., 2016 (https://arxiv.org/html/2606.11235#bib.bib9))，这些结果并非提供有用知识，而是由于噪声或数据随机波动等因素造成。

避免虚假发现的常用方法是在统计假设检验框架内评估数据挖掘结果的统计显著性。在该框架中，数据挖掘分析由一种或多种*统计量*概括，即定量捕获感兴趣方面的得分。分析人员随后对生成数据的底层过程提出一个*零假设*，对应于结果不令人感兴趣的情况。通过将统计量与其在零假设下（即当零假设成立时）的分布进行比较来评估数据挖掘结果：与零分布偏差较大的结果不太可能由随机波动引起，因此被标记为*显著*；而在零假设下很可能出现的结果则被丢弃。

**示例：市场篮子分析。** 市场篮子分析中的一项常见任务是挖掘一组交易记录，每条记录对应一个顾客购买的商品，目的是识别经常一起购买的商品集合（或项集）。为避免无趣结果，我们希望丢弃那些销售频率可由单个商品频率解释的项集。因此，我们定义*零假设*：每个商品独立地以等于其在数据集中频率的概率放入交易中。（注意，在零假设下，由于商品独立放置，没有任何项集是有趣的。）作为检验统计量，我们选择大小为\(c\)且在数据集的至少\(\theta\)比例交易中出现的项集数目。假设统计量的值为\(s\)。那么结果的显著性由零假设下大于等于\(s\)个大小为\(c\)的项集在至少\(\theta\)比例交易中出现的概率给出。如果该概率（称为\(p\)-值）很小，则项集显著，否则不显著。

虽然统计假设检验框架无法证明数据挖掘结果的*有效性*，但它提供了避免虚假发现的正式保证，从而降低了将资源投入无效或无意义结果的风险。更详细地说，对于通过分析数据集\(\mathcal{D}\)计算的统计量\(A(\mathcal{D})\)，设\(p_A\)为其*\(p\)-值*，即在零假设下生成的数据集\(\mathcal{D}^0\)上计算的统计量\(A(\mathcal{D}^0)\)比\(A(\mathcal{D})\)更极端（例如更高）的概率。对于给定的*显著性阈值*\(\alpha \in (0,1]\)，当\(p_A \le \alpha\)时将结果标记为显著，保证了报告错误发现（即结果本不显著却被标记为显著）的概率不超过\(\alpha\)。

当执行由统计量\(A_1(\mathcal{D}), A_2(\mathcal{D}), \dots, A_k(\mathcal{D})\)描述的多个分析时，通常需要控制*族系错误率 (FWER)*，即至少出现一个错误发现的概率。针对这种*多重假设检验*场景，已有多种方法 (Bonferroni, 1936 (https://arxiv.org/html/2606.11235#bib.bib44); Holm, 1979 (https://arxiv.org/html/2606.11235#bib.bib35); Hochberg, 1988 (https://arxiv.org/html/2606.11235#bib.bib10))。本质上，这些方法需要计算一个*调整后*的显著阈值\(\alpha^*\)，该阈值取决于期望的FWER界\(\alpha\)和假设数量\(k\)。\(p\)-值低于\(\alpha^*\)的结果随后被标记为显著。

对于某些统计量和零假设，统计量\(A(\mathcal{D})\)的\(p\)-值\(p_A\)可以解析计算。例如，在市场篮子分析中，如果\(A(\mathcal{D})\)是某个项集在\(\mathcal{D}\)中的频率，且零假设如上述示例（每个商品独立放入交易），那么显然，来自零假设的数据集\(\mathcal{D}^0\)中该项集的频率\(A(\mathcal{D}^0)\)服从二项分布（其参数为项集中各商品频率的乘积与数据集交易数的乘积）。

已有多种方法专为特定数据挖掘任务设计，以识别显著结果，例如显著模式挖掘 (Webb, 2006 (https://arxiv.org/html/2606.11235#bib.bib42), 2007 (https://arxiv.org/html/2606.11235#bib.bib41), 2008 (https://arxiv.org/html/2606.11235#bib.bib40); Terada et al., 2013 (https://arxiv.org/html/2606.11235#bib.bib185); Minato et al., 2014 (https://arxiv.org/html/2606.11235#bib.bib39))，这些方法在零假设允许解析计算\(p\)-值时适用。然而，对于更复杂分析或零假设，无法利用解析结果。在此类场景中，基于重采样的方法 (Westfall and Young, 1993 (https://arxiv.org/html/2606.11235#bib.bib43)) 被广泛使用。这些方法通过将\(A(\mathcal{D})\)与零假设下统计量\(A(\mathcal{D}^0)\)的*经验分布*进行比较来评估结果统计显著性。后者通过生成大量*重采样数据集*（即根据零假设生成的数据集）获得。

**示例：网络极化。** 给定一个表示社交网络的图\(G\)，我们感兴趣的是使用众多可用度量之一作为检验统计量\(A(G)\)来研究其极化现象 (Conover et al., 2011 (https://arxiv.org/html/2606.11235#bib.bib272); Cinelli et al., 2021 (https://arxiv.org/html/2606.11235#bib.bib273); Garimella et al., 2018 (https://arxiv.org/html/2606.11235#bib.bib271); González-Bailón et al., 2023 (https://arxiv.org/html/2606.11235#bib.bib274); Preti et al., 2025b (https://arxiv.org/html/2606.11235#bib.bib6))。这些度量取决于图的结构和顶点的颜色，其中顶点颜色代表论点或辩论中的不同阵营或群体。零假设是图中的边与顶点颜色独立，但连接不同颜色顶点的边总数固定；此外，为捕捉真实网络的高度偏斜度序列，零假设中顶点的度序列是固定的。对于此示例，即使对于像顶点同色邻居比例的平均值这样简单的统计量，也无法解析计算\(p\)-值。然而，可以使用近期方法 (Fosdick et al., 2018 (https://arxiv.org/html/2606.11235#bib.bib266); Preti et al., 2025a (https://arxiv.org/html/2606.11235#bib.bib261)) 从零分布生成（独立的）重采样网络。

即使在可以解析计算\(p\)-值的多重假设检验场景中，基于重采样的方法也被广泛使用。事实上，当解析计算\(p\)-值可行时，可以通过重采样数据集准确估计*调整后*的显著阈值\(\alpha^*\) (Westfall and Young, 1993 (https://arxiv.org/html/2606.11235#bib.bib43))。与解析修正相比，基于重采样的方法具有更高的*统计功效*（即正确标记显著假设的能力）。这是因为它内在地考虑了假设之间的相关结构，而解析调整则受到最坏情况假设的影响。

鉴于其有用性和广泛适用性，已有多种方法利用重采样方案（见第2节 (https://arxiv.org/html/2606.11235#S2)）。然而，对于常见的\(\alpha\)值（即\(\alpha = 0.1\)或\(\alpha = 0.05\)），它们都需要生成*数千个*重采样数据集。对于复杂分析和/或大型数据集，挖掘甚至生成*单个*重采样数据集可能需要数小时或更长时间。事实上，这正是上述网络分析示例的情况。因此，当数据挖掘步骤或重采样过程计算密集时，当前可用的基于重采样的方法对于现代规模的数据集是不切实际的。

**我们的贡献。** 在本文中，我们专注于基于重采样的方法，用于评估数据挖掘结果的统计显著性。我们的贡献有四个方面。首先，我们提出 **FewRS**，一种简单有效的基于重采样的方法，用于评估数据挖掘结果的统计显著性，同时控制FWER。**FewRS** 采用少次重采样方法，即分析少量重采样数据集，从而形成高度可扩展的方法。**FewRS** 可以利用*任何*生成重采样数据集的程序，并且可应用于任何由统计量概括结果的数据挖掘分析。因此，我们的方法适用于广泛的数据挖掘任务和场景。其次，我们推导了表示数据挖掘结果质量的检验统计量的上确界偏差的新颖界限。这一结果对于使我们的方法实用至关重要，因为它意味着挖掘少量重采样数据集就足以识别统计显著的结果。第三，我们证明 **FewRS** 还对其统计功效（即正确报告显著假设的能力）提供了保证。值得注意的是，我们的分析不要求对显著模式的分布做任何假设。第四，我们对模式挖掘和网络分析等常见数据挖掘任务的若干分析进行了广泛的实证评估。在所有情况下，**FewRS** 相比现有技术水平将运行时间减少多达两个数量级，同时保持高统计功效，使得大规模真实世界数据集的数据挖掘结果统计验证成为可能。

## 2. 相关工作

我们的工作聚焦于高效的基于重采样的方法，用于评估数据挖掘结果的统计显著性。现在描述与我们最相关的工作，并引导读者参阅最近的综述和教程 (Hämäläinen and Webb, 2019 (https://arxiv.org/html/2606.11235#bib.bib196); Pellegrina et al., 2019a (https://arxiv.org/html/2606.11235#bib.bib195)) 以更广泛了解统计可靠的数据挖掘算法，以及Westfall and Young (1993 (https://arxiv.org/html/2606.11235#bib.bib43)) 的著作以了解基于重采样的方法。

Gionis et al. (2007 (https://arxiv.org/html/2606.11235#bib.bib267)) 引入了使用置换策略来评估数据挖掘结果。他们的方法专注于具有二元特征的数据集，表示为0-1矩阵，以及一个特定的零假设，其中随机数据集中的每一列和每一行必须与原始数据集具有相同数量的1。Kirsch et al. (2012 (https://arxiv.org/html/2606.11235#bib.bib184)) 引入了一种方法，用于识别一小组具有较小错误发现率 (FDR) (Benjamini and Hochberg, 1995 (https://arxiv.org/html/2606.11235#bib.bib45)) 的统计显著模式。他们的方法专门用于项集挖掘，并且针对零假设：商品独立放入交易，同时保持每个商品的期望频率。Dalleiger and Vreeken (2022 (https://arxiv.org/html/2606.11235#bib.bib1)) 专注于挖掘非冗余的统计显著模式集，同时控制FWER或FDR。他们的方法专门用于项集和最大熵零分布。

通用的基于重采样的方法 (Westfall and Young, 1993 (https://arxiv.org/html/2606.11235#bib.bib43)) 可用于评估数据挖掘结果的统计显著性，但其直接应用需要生成和挖掘大量重采样数据集。近期的许多工作致力于提供计算高效的置换执行程序。