群组测试

群组测试（Group Testing）是一种通过组合检测来高效识别少数异常个体（如感染者、缺陷品）的统计方法。其核心思想是将多个样本混合后进行单次测试，根据结果推断每个样本的状态，从而在总体样本量较大且异常比例较低时大幅减少检测次数。该方法最初由Rosenblatt和Dorfman于二战时期提出，用于美军梅毒血液筛查，如今已成为计算机科学、生物信息学、通信工程等多个领域的重要工具。

基本模型

假设有 n 个物品，其中至多d个为“缺陷品”（阳性）。每次测试可以选择任意物品子集，并获得一个二进制结果：1表示该子集中至少包含一个缺陷品，0表示没有缺陷品。目标是设计一系列测试，以最少的测试次数确定所有缺陷品的具体身份。

分类

• 自适应群组测试：后续测试依赖先前测试结果，可动态调整策略。经典案例如二分搜索，适用于缺陷品数量较少时，最优测试次数为 $(O(d \log n))$。
• 非自适应群组测试：所有测试提前设计，可并行执行。通常用 $t \times n$ 的二进制矩阵表示，每行对应一个测试，每列对应一个物品。矩阵设计需满足分离性质（如disjunct或separable），以保证能从结果中唯一解码缺陷集合。所需测试次数一般多于自适应方法，但并行性更适合大规模应用。
• 组合群组测试：假设缺陷品数量严格不超过 d，设计确定性测试方案。
• 概率群组测试：假设每个物品独立以概率 p 为缺陷，旨在以高概率正确识别，通常可进一步减少测试次数。

计算机科学中的应用

1. 多重访问通信：在多用户信道中，识别活跃用户可视为群组测试问题，通过时隙分配减少冲突。
2. 数据压缩与稀疏恢复：压缩感知中，群组测试用于从少量线性测量中恢复稀疏信号。
3. DNA库筛选与测序：在生物信息学中，通过混合多个DNA样本进行测序，降低成本和耗时。
4. 软件测试与故障诊断：检测软件中罕见bug或硬件中故障组件，通过测试用例组合定位问题。
5. 网络安全：检测网络中的异常主机或恶意流量，通过聚合探测提高效率。
6. 数据流处理：在流式数据中识别频繁项或重元素，使用类群组测试的哈希技术。

关键结果

• 自适应群组测试的下界为 $\Omega(d \log(n/d))$，存在算法（如二分搜索、Sobel算法）达到 $O(d \log n)$。
• 非自适应群组测试：存在构造性方案使用 $O(d^2 \log n)$ 或 $O(d \log^2 n)$次测试，具体取决于矩阵设计（如使用纠错码、随机矩阵）。
• 当 d 很小（如常数）时，非自适应测试次数可接近 $O(\log n)$；当 d 较大时，通常需要更多测试。

现代发展

群组测试与稀疏信号处理、信息论、组合设计等密切相关。特别是压缩感知的兴起，使得群组测试在高效传感、图像处理、机器学习中得到新的应用。例如，在神经网络剪枝中，可通过群组测试快速识别重要权重。
总之，群组测试是一种高效利用资源的结构化检测方法，在计算机科学中广泛应用于需要从大量数据中提取稀疏信息的场景。其核心优势在于通过巧妙的组合设计，将问题规模从个体级别降低到组级别，从而实现指数级的速度提升或成本节约。