群组测试（Group testing）介绍

最近了解了群组测试 (Group testing) 的一些内容，在这里做个记录与分享。

问题引入

问题源于二战时期，美国需要通过血样检测美军是否携带梅毒，但是当时血液检测耗时耗钱，将每个士兵的血液都检查一遍效率很低。考虑到携带梅毒的总归是少数，Rosenblatt和Dorfman提出将全部待检测士兵的血样分组混合后再检测，如果混合后的血样没有病毒，可以推定整个组都没有病毒，如此便能够减少不必要的检测。

具体测试过程示例如下所示：

将以上问题标准化描述如下：

• 给定集合$N$，其中有$n$个个体，每个个体要么是正例患病个体 (Positive) 要么是负例正常个体 (Negative)，记其中正例个数为$d$。
• 目标：通过尽量少的测试次数，找出所有的负例。
• 方法：将个体首先进行分组，而后对有可能的组有阳性的组进行逐一筛查。

那么如何在资源有限的前提下，利用尽可能少的次数，来达到尽可能准的检测效果呢？

这类型 Group Testing 的方法是目前研究最多的，其本质上是一种已知压缩后的信息，对原始信息进行估计的一种方法，也就是压缩感知技术里面的重构（对下式而言，给定$\mathbf{x}$和$\mathbf{A}$，注意，这里的$\mathbf{A}$是一个非常“胖”的矩阵，也就是列数远远大于行数，这里求解$\mathbf{y}$的过程被称为压缩；给定$\mathbf{y}$和$\mathbf{A}$ ，求解$\mathbf{x}$的过程称为重构）。
$$\mathbf{y}=\mathbf{A}\mathbf{x},$$
此模型最早用于信号（图像）的还原与去噪，在很早就有用L0与L1惩罚项在计算机相关的期刊上发表，却比较少用在Group Testing中。

下图展现了在Group Testing中，x表示真实的人群，黑色表示阳性人群，白色表示阴性人群；A表示检测的矩阵，每一行表示一次检测，一次检测中，所有人均为阴性则最终输出为阴性，只要有一个人为阳性，则最终输出为阳性，最终的输出结果为y。

目前常用算法

目前处理这种问题的经典方法有如下几种（不同文章对不同方法的定义可能略有不同）：

1. SSS（Smallest satisfying set）

SSS（Smallest satisfying set）：遍历所有可能出现潜在观测结果的情形，取满足条件的最小集合。

以下图为例，共有7个个体，5次试验，则需要遍历总共$2^7=128$种情形，最终可能的集合为{2,4}与{2,4,7}，则SSS算法最终选出的集合为{2,4}。

2. COMP（Combinatorial orthogonal matching pursuit）

COMP（Combinatorial orthogonal matching pursuit）：找出所有结果判断为0的test情形，剔除掉这些相关的个体，剩下的个体集合即为算法所求。

同样以前面图为例，5次试验只有第一次与第三次实验输出结果为0，意味着{1,3,5,6}个体一定为阴性，那么算法最终得到的集合为{2,4,7}。

3. DD（Definite defectives）

DD（Definite defectives）：在剔除Test结果为0的所有样本后，关注剩下输出为阳性的且对应试验的只剩一个个体，这些试验个体的集合即为算法输出结果。

还是用前面的例子，在剔除了Test结果为0的所有样本后，第4,5次试验结果为阳性，且对应试验均只有一个个体进行试验（分别为第2,4个个体），因此算法最终输出结果为{2,4}。

4. SCOMP（Sequential COMP）

算法分为如下三个步骤：

1. 做一次DD算法，选出的所有个体的集合记为 $\hat{K}$；
2. 除去所有 $\hat{K}$中个体，剩下的输出为阳性的检测，记为unexplained test，选择这些unexplained test中出现次数最多的个体，加入$\hat{K}$中（若出现不同个体出现相同次数，则随机选择一个加入$\hat{K}$）；
3. 重复步骤2，直到没有一个test为unexplained ，则停止迭代。

我们以上图为例，说明 SCOMP 算法的迭代过程。通过前文所述的DD算法，得到初始 K ^ = { 2 , 4 } hat{K}={2,4} K^={2,4}.

而后进行步骤2，考虑（6）（7）（8）三个unexplained test，其输出均为1，且（a）（b）（c）三个个体均未在$\hat{K}$中。此时由于个体（b）同时出现在三个试验中，出现的次数最多，因此将个体（b）加入$\hat{K}$中，得到 K ^ = { 2 , 4 , b } hat{K}={2,4,b} K^={2,4,b}。

此时（6）与（8）由于均包含（b），因此不再为unexplained test。至此，没有一个试验为unexplained test，停止迭代。算法最终输出的集合为 { 2 , 4 , b } {2,4,b} {2,4,b}。

稀疏性方法

在Group Testing中，其原始信息x通常都是稀疏的，这就比较好的适用于添加L0与L1正则项进行优化。用正则项优化的目标函数如下所示（限制$x_i\ge 0$）：

需要注意的是，这里的$\mathbf{x}$，相当于Lasso传统表达式上的权重$\beta$，$\mathbf{A}$相当于样本矩阵$\mathbf{X}$。

此外，还可以考虑使用： ① Non-negative Orthogonal Matching Pursuit (NNOMP) ；② Sparse Bayesian Learning (SBL) 等稀疏性的方法，这里不再进行更多的阐述。

参考文献

1. 用数学策略提高冠状病毒检测效率
2. [Group testing]群组测试：毒药谜题
3. Group Testing: An Information Theory Perspective

最后

以上就是合适小土豆为你收集整理的群组测试（Group testing）介绍的全部内容，希望文章能够帮你解决群组测试（Group testing）介绍所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。