信息论与编码理论在新冠肺炎检测中的应用探讨.docx
《信息论与编码理论在新冠肺炎检测中的应用探讨.docx》由会员分享,可在线阅读,更多相关《信息论与编码理论在新冠肺炎检测中的应用探讨.docx(15页珍藏版)》请在冰点文库上搜索。
信息论与编码理论在新冠肺炎检测中的应用探讨
信息论与编码理论在新冠肺炎检测中的应用探讨
一、实验目的
1.信息论与编码理论中理论,探讨多样品混合检测的效率、可行性与可靠性。
2.给出具体的编码方案。
二、实验设备
MATLAB软件
三、背景介绍
根据武汉市新冠肺炎疫情防控指挥部涉疫大数据与流行病学调查组5月11日发布的文件,在武汉市全市范围内将开展全员新冠病毒核酸筛查“十天大会战”。
要求武汉市各区按十天期限,做好本辖区全员核酸筛查计划安排。
查询武汉市单日核酸检测能力,武汉市核酸检测机构55家,核酸采样点211个。
湖北省单日核酸检测最多时达8.9万人份,武汉市单日核酸检测最多时达6.3万人份。
根据武汉市统计局官方数据2018年,武汉市常住人口1108.1万人。
虽然5月5日,武汉市决定对教师、医务人员、公共交通工具服务人员、大型商场等公共场所服务人员、监所和养老机构人员等“五类人员”全面开展流调和核酸检测,对教师和医务人员还要进行血清抗体检测。
根据武汉市卫生健康委消息,截至4月29日24时,武汉市累计开展核酸检测103.44万人次,此次文件要求十天内,全员核酸检测将严重考验武汉市核酸检测能力。
以武汉现有的检测能力,在十天内是无论如何完成不了1100万的核酸检测,如何从技术手段上解决检测能力的问题就成了首要讨论的问题。
四、混检方案论证
1.混检原理
混检方法:
在样本检测工作中,为了降低检测成本的需求,提高检测速度,很多试剂公司推荐一种方案称为“混检”:
即将两个或以上的样本混合检测,一旦出现阳性结果,则再次分检,找出阳性样本。
这种检测方法,对于检测靶标数量较高的样本成功率较高,但对于靶标数量较低的样本漏检率高,且危害极大。
假定商品试剂盒的检测敏感性极高,在临床上将5份样本混合检测,出现阴性结果,则可以假定上述5份样本均为阴性。
若一旦出现阳性结果,则需进行分检,会出现至少1份,最多5份为阳性的结果。
在这种情况下,对阳性结果进行定点清理。
这是最为理想的状态。
但是,如果出现取样不均匀;或者样本没有进行充分保护,分检时出现靶标物降解以及提取试剂盒和扩增试剂盒的敏感性不高等因素,则有可能出现“混检”时的阳性,分检时阴性的结果。
生产实际中最为可怕的情况是第四种,即“混检”阴性,若分检则出现阳性(实际上并没有人这么去做)。
因为在实际检测工作中,一旦出现“混检”阴性的结果,则皆大欢喜,不再跟踪。
这样的假阴性结果危害极大,会导致定点清除工作的失败。
这种方法存在不足,我们考虑到如果试剂盒结果出现阳性或者假阴性或者假阳性的错误情况,需要再次进行每个样本的单独检测或者是在阴性的样本中抽查重新检测来排除错检和漏检的情况,这样导致检测效率的降低以及投入成本的增加。
基于上面出现的问题,我们可以通过信息论中学到的知识,采用不同的方法解决,对不同的方案进行比较,得到在理想的条件下,提高检测效率以及检测的准确度,同时降低检测成本的可靠方法。
2.方案使用数据以及基本变量定义
根据在网上获取的疫情数据,我们搜集到武汉本土疫情不再新增的最后数据。
并将这些数据细分到武汉市的每一个区的疫情数据统计。
数据截止日期为2020年2月29日,数据如下表所示
地区
感染新冠病毒人数
该地区总人数
感染病毒率
江岸区
4300
121万
0.355%
江汉区
7290
83万
0.878%
硚口区
7239
64万
1.131%
汉阳区
3579
89万
0.402%
武昌区
8224
134万
0.614%
青山区
2958
54万
0.548%
洪山区
4999
126万
0.397%
东西湖区
2588
51万
0.507%
蔡甸区
1974
57万
0.346%
江夏区
1661
82万
0.203%
黄陡区
1775
122万
0.145%
新州区
1018
105万
0.097%
合计
49122
1088万
0.451%
表4.2.1疫情数据统计
表2.2.1中的数据显示,武汉市每一个区的病毒感染率并不相同而且不具有任何的规律,最大值为1.131%,最小值为0.097%。
针对这种情况,我们可以对不同的区采用不同的方案进行分级检测,提高检测效率降成本同时准确性也不会降低保证安全。
根据表格的数据可以得到平均的感染率为0.451%,该值作为参考,用于对不同方案的优缺点评估。
在新冠疫情检测中,我们根据资料了解到:
核酸检测的费用是按照检测样本的数量来计算的,一个样本的检测需要启动一次检测仪器同时进行对结果的校准,这些都是检测的成本。
在大规模的检测中,多个样本作为一个样本检测就会节省成本。
武汉市核算检测价格为180人/人,一次检测的时间为6-8小时,在本文中采用6小时作为检测时间。
下面对一些变量作出基本的定义:
X
检测人数中感染的人数,X取值为0、1、......、N
Y
混合样本中是否检测出病毒,Y=1表示阳性,Y=0表示阴性
Z
检测所需要的次数,Z的取值为0、1、......、M
C
一次检测所花费的成本,为180元
T
一次检测所花费的时间,为6小时
表4.2.2变量定义
3.可行性分析
根据上文中提到的混检原理,下文进行对该方案的可行性分析
在可行性分析中,我们在一个试剂盒中混入5个采集的样本
图4.3.1混检、分检均为阴性
在图2.3.1中,混检为阴性,那么我们希望在对样本单独检测中均为阴性,分检的结果符合我们的预期。
图4.3.2混检阳性,分检存在阳性
同理,我们在混检中出现阳性,那么分检中至少有一个人出现阳性,图2.3.2中的结果可以看出符合预期。
图4.3.3混检阳性、分检阴性
当混检出现阳性时,为了安全起见,我们会牺牲效率对每一个样本进行单独检测,发现分检结果均为阴性,证明每个样本是安全的。
出现的问题可能在与在样本的采集或者是运输过程中出现疏漏导致,为了安全,混检出现阳性就要对样本单独检测,安全高于成本。
图4.3.4混检阴性,分检阳性
在分检出现阴性时,在混检的方法中我们默认改试剂盒中所有样本均为阴性,但是存在阳性的患者没有被检测出,会出现的很大的问题。
武汉市防疫部门和李兰娟院士的团队,对所有阴性的结果中重新抽取近1万份的样本进行重新的检验,检验结果均为阴性,而且武汉没有再次出现疫情也说明了这种情况的可能性极低。
通过杭州市混检阴性,分检阳性的统计概率为
,由概率可以得到这种情况的自信息量
=20.7,此信息的信息量很大说明这个事件具有存疑度,但是存疑度为
说明事件基本不可能发生。
根据上述的四种情况以及武汉在这次全民检测的实际结果中可以看出,混检的方案具有很高的可行性,准确性。
五.多人样本混检方案论证
1、理论基础
1)信息量
所谓信息量是指从N个相等可能事件中选出一个事件所需要的信息度量或含量,也就是在辩识N个事件中特定的一个事件的过程中所需要提问"是或否"的最少次数.
香农(C.E.Shannon)信息论应用概率来描述不确定性。
信息是用不确定性的量度定义的.一个消息的可能性愈小,其信息愈多;而消息的可能性愈大,则其信息愈少.事件出现的概率小,不确定性越多,信息量就大,反之则少。
信息量总的来说是指信息多少的量度。
1928年R.V.L.哈特莱首先提出信息定量化的初步设想,他将消息数的对数定义为信息量。
若信源有m种消息,且每个消息是以相等可能产生的,则该信源的信息量可表示为I=logm。
但对信息量作深入而系统研究,还是从1948年C.E.仙农的奠基性工作开始的。
在信息论中,认为信源输出的消息是随机的。
即在未收到消息之前,是不能肯定信源到底发送什么样的消息。
而通信的目的也就是要使接收者在接收到消息后,尽可能多的解除接收者对信源所存在的疑义(不定度),因此这个被解除的不定度实际上就是在通信中所要传送的信息量。
2)信息熵
信息是个很抽象的概念。
人们常常说信息很多,或者信息较少,但却很难说清楚信息到底有多少。
比如一本五十万字的中文书到底有多少信息量。
直到1948年,香农提出了“信息熵”的概念,才解决了对信息的量化度量问题。
信息熵这个词是C.E.Shannon(香农)从热力学中借用过来的。
热力学中的热熵是表示分子状态混乱程度的物理量。
香农用信息熵的概念来描述信源的不确定度。
信息论之父克劳德·艾尔伍德·香农第一次用数学语言阐明了概率与信息冗余度的关系。
通常,一个信源发送出什么符号是不确定的,衡量它可以根据其出现的概率来度量。
概率大,出现机会多,不确定性小;反之不确定性就大。
不确定性函数f是概率P的减函数;两个独立符号所产生的不确定性应等于各自不确定性之和,即f(P1,P2)=f(P1)+f(P2),这称为可加性。
同时满足这两个条件的函数f是对数函数,即f(P)=log1/p=-logp
在信源中,考虑的不是某一单个符号发生的不确定性,而是要考虑这个信源所有可能发生情况的平均不确定性。
若信源符号有n种取值:
U1…Ui…Un,对应概率为:
P1…Pi…Pn,且各种符号的出现彼此独立。
这时,信源的平均不确定性应当为单个符号不确定性-logPi的统计平均值(E),可称为信息熵,即H(U)=E[-logp_i]=∑_(i=1)^n▒〖p_ilogp_i〗,式中对数一般取2为底,单位为比特。
但是,也可以取其它对数底,采用其它相应的单位,它们间可用换底公式换算。
最简单的单符号信源仅取0和1两个元素,即二元信源,其概率为P和Q=1-P,该信源的熵即为如图1所示。
由图可见,离散信源的信息熵具有:
①非负性:
即收到一个信源符号所获得的信息量应为正值,H(U)≥0
②对称性:
即对称于P=0.5
③确定性:
H(1,0)=0,即P=0或P=1已是确定状态,所得信息量为零
④极值性:
因H(U)是P的上凸函数,且一阶导数在P=0.5时等于0,所以当P=0.5时,H(U)最大。
图5.1.1二元信源的熵
对连续信源,香农给出了形式上类似于离散信源的连续熵,虽然连续熵仍具有可加性,但不具有信息的非负性,已不同于离散信源。
不代表连续信源的信息量。
连续信源取值无限,信息量是无限大,而是一个有限的相对值,又称相对熵。
但是,在取两熵的差值为互信息时,它仍具有非负性。
这与力学中势能的定义相仿。
信息的基本作用就是消除人们对事物的不确定性。
多数粒子组合之后,在它似像非像的形态上押上有价值的数码,具体地说,这就是一个在博弈对局中信息混乱的现象。
香农指出,它的准确信息量应该是
-(p1*log(2,p1)+p2*log(2,p2)+ ... +p32*log(2,p32)),
其中,p1,p2, ...,p32分别是这32个球队夺冠的概率。
香农把它称为“信息熵”(Entropy),一般用符号H表示,单位是比特。
有兴趣的读者可以推算一下当32个球队夺冠概率相同时,对应的信息熵等于五比特。
有数学基础的读者还可以证明上面公式的值不可能大于五。
对于任意一个随机变量X(比如得冠军的球队),它的熵定义如下:
变量的不确定性越大,熵也就越大,把它搞清楚所需要的信息量也就越大。
信息熵是信息论中用于度量信息量的一个概念。
一个系统越是有序,信息熵就越低;
反之,一个系统越是混乱,信息熵就越高。
所以,信息熵也可以说是系统有序化程度的一个度量。
熵的概念源自热物理学。
假定有两种气体a、b,当两种气体完全混合时,可以达到热物理学中的稳定状态,此时熵最高。
如果要实现反向过程,即将a、b完全分离,在封闭的系统中是没有可能的。
只有外部干预(信息),也即系统外部加入某种有序化的东西(能量),使得a、b分离。
这时,系统进入另一种稳定状态,此时,信息熵最低。
热物理学证明,在一个封闭的系统中,熵总是增大,直至最大。
若要使系统的熵减少(使系统更加有序化),则必须有外部能量的干预。
信息熵的计算是非常复杂的。
而具有多重前置条件的信息,更是几乎不能计算的。
所以在现实世界中信息的价值大多是不能被计算出来的。
但因为信息熵和热力学熵的紧密相关性,所以信息熵是可以在衰减的过程中被测定出来的。
因此信息的价值是通过信息的传递体现出来的。
在没有引入附加价值(负熵)的情况下,传播得越广、流传时间越长的信息越有价值。
3)相对熵
相对熵(relativeentropy),又被称为Kullback-Leibler散度(Kullback-Leiblerdivergence)或信息散度(informationdivergence),是两个概率分布(probabilitydistribution)间差异的非对称性度量。
在在信息理论中,相对熵等价于两个概率分布的信息熵(Shannonentropy)的差值。
相对熵是一些优化算法,例如最大期望算法(Expectation-Maximizationalgorithm,EM)的损失函数。
此时参与计算的一个概率分布为真实分布,另一个为理论(拟合)分布,相对熵表示使用理论分布拟合真实分布时产生的信息损耗。
相对熵是两个随机分布之间距离的度量。
在统计学中,它对应的是似然比的对数期望(极大似然估计的损失函数值)。
相对熵度量当真实分布为p而假定分布为q时的无效性。
例如,已知随机变量的真实分布为p,可以构造平均描述长度为H(p)的码,但是如果使用针对分布q的编码,那么在平均意义上就需要H(p)+D(p||q)比特来描述这个随机变量。
条件相对熵(conditionalrelativeentropy):
对于联合概率密度函数p(x,y)和q(x,y),条件相对熵定义为条件概率密度函数p(y|x)和q(y|x)之间的平均相对熵,其中取平均是关于概率密度函数p(x)而言的
4)数学期望
在概率论和统计学中,数学期望(mean)(或均值,亦简称期望)是试验中每次可能结果的概率乘以其结果的总和,是最基本的数学特征之一。
它反映随机变量平均取值的大小。
需要注意的是,期望值并不一定等同于常识中的“期望”——“期望值”也许与每一个结果都不相等。
期望值是该变量输出值的平均数。
期望值并不一定包含于变量的输出值集合里。
大数定律规定,随着重复次数接近无穷大,数值的算术平均值几乎肯定地收敛于期望值。
5)纠错编码
纠错编码又称之为信道编码,它已成功地应用于各种通信系统中,在图像通信中也得到日益广泛的应用。
目前在数据传输中,主要有三种误码控制的方法,即自动请求重发(ARQ)、前向纠错(FEC)和混合纠错(HEC)方式。
在传输过程中发生错误后能在收端自行发现或纠正的码。
仅用来发现错误的码一般常称为检错码。
为使一种码具有检错或纠错能力,须对原码字增加多余的码元,以扩大码字之间的差别,即把原码字按某种规则变成有一定剩余度(见信源编码)的码字,并使每个码字的码之间有一定的关系。
关系的建立称为编码。
码字到达收端后,可以根据编码规则是否满足以判定有无错误。
当不能满足时,按一定规则确定错误所在位置并予以纠正。
纠错并恢复原码字的过程称为译码。
检错码与其他手段结合使用,可以纠错。
发表论文指出,只要采用适当的纠错码,就可在多类信道上传输消息。
自仙农的论文发表以来,人们经过持续不懈的努力已经找到多种好码,可以满足许多实用要求。
但在理论上,仍存在一些问题未能解决。
纠错码能够检错或纠错,主要是靠码字之间有较大的差别。
纠错码实现中最复杂的部分是译码,它是纠错码能否应用的关键。
纠错码传输的都是数字信号。
这既可用硬件实现,也可用软件实现。
2、性能分析
1)可行性
具体到多人样本混检方案中,方案可行最基本的就是要实现混检结果为阳性时,分检的样本中一定存在阳性样本。
且不可能出现混检结果为阴性,但实际上在单个样本中存在阳性样本。
所以我们把模型简化:
假设为5个样本进行混检。
这时对事件A:
混检结果为阴性,但实际的单个样本中存在阳性样本;计算其信息量。
可以简单的计算下其概率P=1/5×1/2×1/120×0.7%×1%≈5.8×(是以国内杭州市患病率为例)。
并且我们套用哈莱特的简单算法得出,A的信息量为一个很大的数值,可以很明显的知道事件A为存疑性很大的事件,基本上不可能发生事件A,即出现混检结果为阴性但单个样本中存在阳性样本的情况。
所以多人混检样本方案是可行的。
2)效率
由上面理论,计算出方案所建立的信息传输系统中其熵值的大小就可以知道系统的混乱度,知道整个系统的信息传输效率到底如何。
而在前面验证可行性中我们已经计算过事件的概率,套用到香农的公式中可以很快的算出我们建立的简单系统模型其熵值大小是趋近于0的。
所以我们简单的得出结论,多样本混检方案系统是稳定不混乱的,高效率的一个系统。
那么通过信息的熵值,我们就验证了方案的效率是很高的。
3)可靠性
那么套用相对熵计算公式,将方案中的分检于混检分别看作一个随机分布,通过相对熵的计算结果就可以知道两者间的距离,知晓两个随机分布间是否有很大差别,从而来论证方案结果的可靠性。
4)数学模型说明
为了简化数学问题的讨论,先来2条假设,这2条假设在报道中是成立的,有些假设在报告中没提,但是是近似成立的,或者说即不影响主要结论。
假设1如果512个人中有一个阳性,其它均为阴性,那么它们的混合液体为阳性。
为什么选512这个数字?
因为这个数字约为1000人的一半,是支持本方法的一个必须依据。
混合液体的人越多,肯定是检测误差肯定越大的。
报道中提到200~300人混检是可行的,但没有具体提到512人可行。
我们也可以将这一数字缩小到256,那么结果会稍加修改(变为9个盒子检测512人)。
主要部分还是正确的。
假设2武汉阳性人群的概率分布1/1000是总体均匀分布,我们就当绝对均匀分布处理。
如果不是,还是可以设计一些改进方法来解决,对结果影响不大。
方法一、分半混合检测
第1步:
将总液体对半平分为2组,每组500人混合,得到2份混合液体。
检其中1份,如果为阳性,则另一份必为阴性。
反之也成立,即检测到的是阴性,另一份必为阳性。
这是因为1000人中只有一人为阳性。
第1步花了1份试剂将1半的阴性排除。
保留阳性组512人。
第2步:
按第1步的方法,将阳性组的液体再对半分成两组,得到2组,都是250人。
用第1步的方法,可以再排除1半阴性。
保留阳性组256人。
...
按照前面的步骤,因为每次排除一半,所以只需10步,最终999人可以被排除在外。
所以最后的阳性被挑出来了。
上面的方法大体上完成了任务,但有个重要缺点,就是要分批测10次,还容易因为操作不当而出错。
更要命的时,每次检测可能要数小时,10轮检下来,时间太长。
虽然有这些缺点,但表明了理论上是可行的,所以我们可以找其它等价的方法,一轮就可以测出来。
方法二、编码法
为了使编码法更容易理解,我就假设用3支试剂测8个人,把阳性挑出来吧。
有了这个基础后,10支试剂就可以从1024个人中把1个阳性挑出来。
下面的图反映了编码法的原理,我们对7人进行编号,第8个人不管他,的确这个方法只能检测7个人,比我承诺的少检一个。
但当总人数很多时,少检一个不成为主要问题。
1)对被测人员编号,分别是1,2,3,4,5,6,7
2)将它们的待测液体混合为3份,每份要混入4个人的,具体哪个人混入哪个组,见绿色的盒子,第1个盒子混入的液体所对应被测者的编号是4,5,6,7;第2个盒子混入的液体编号是2,3,6,7;第3个盒子混入的液体编号是1,3,5,7。
至于为什么这样设计,往后看就清楚了。
3)拿3份试剂盒去测这三组混合液体(一次),所能得到的结果有多少种情况呢?
总共应该有8-1=7种,也就是左下方的编码矩阵中的7种,其中1表示阳性,0表示阴性。
图5.2.1混检实例
例如如果是编号1的人感染,它的液体只混入了最右边的盒子(称第3个盒子吧),所以只有这个组的结果为阳,其它两组的结果必为阴。
即得到的结果是0,0,1
如果是编号为2的人感染,它的液体只混入了中间的盒子(称第2个盒子吧),所以只有这个组的结果为阳,其它两组的结果必为阴。
即得到的结果是0,1,0
如果是编号为3的人感染,它的液体混入了中间的盒子(第2个盒子吧),最右边的盒子(第3个盒子吧)。
右边两个组的结果为阳,最左边第1个盒子的结果必为阴。
即得到的结果是0,1,1
以此类推,这7个人中任何一个人感染,这三个盒子检测出来的结果都是不同的,即7种结果编码了7个被测人员。
我们可以根据检测结果将被测人员给唯一的定位出来。
现在要回到一开始提出的混合液体的方法了。
我们简单观察一下编码矩阵,最左边的第1列的4,5,6,7行因为检测结果要为1,其它行结果要为0,所以将编号为4,5,6,7的被测人员的液体混入即可,这就得到了第1个盒子混哪些人的液体。
同样的道理,第2列则要求编号为2,3,6,7的待测人员的液体混入。
第3列要求编号为1,3,5,7的待测人员的液体混入。
注意到上面的编码矩阵其实就是从1到7的十进制数的二进制表示,那么这个方法很容易可以扩展到10份试剂10个混合组,可以编码1024-1=1023个待测人员。
我们再顺便观察一下,每个盒子混入的液体的份数都是8/2=4份,即总人数的一半。
如果是1024个份待测液体,那么意味着每个盒子混入512个样本液体。
至于这512个样本混合后检测结果还有多准,这是我不能回答的问题,应该是个医学与统计的问题。
不过,即合不是完全准,也可以设计更高级的编码矩阵那解决误检的问题。
另外,上面的编码方法不是唯一可行的,其实可以采用其它编码,只不过这种规则简单易理解。
还有,前面提到过一个问题,就是如果1024个人中如果有2个人感染,这就会发生误检,例如如果本来是第1个人和第2个人同时感染,因为它们的液体混入了第2个盒子和第3个盒子,造成检测的结果是0,1,1,那么检测后解码的结果是第3个人感染。
这就发生了误检。
对于这种情况,我们通过巧妙地设计编码矩阵,可以解决这一问题。
六、总结
对武汉全体市民进行核算检测是不可或缺的,但是要在短时间内实现千万人级别的核算检测,一一检测显而易见是不可能的,因此有专家提出了混检的方法。
这种检测方法能够得到实行可见是有其原因的,前面也证实了该检测方法在检测效率、可靠性、可行性上都有比较好的性能。
而另一方面,据国家卫健委介绍,核酸混检有两种模式:
一种是在采样时,将几个人如3人或5人分别采样后,放至同一采样管中,这种模式也叫做“混合采样”或称“混采”,北京多数情况下采用这种模式;
另一种则是在实验室检测时,将3人或5人的样本取相同体积混合在一起,也称“样本混合”。
从科学角度讲,第一种“混采”模式,不会影响核酸检测的敏感性,后一种将样本混合检测的模式,则对检测敏感性有一定的影响,但影响程度是已知的。
混检大幅提升了核酸检测能力,比如,现在北京的日检测能力是20多万,使用这种结合模式,可使日检测能力在不增加人力物力的情况下,就可以达到200多万。
需要强调的是,对于发热门诊有症状患者、密切接触者等高风险人群检测,还是应该采用单采单检。
对于低风险人群的筛查,则可以优先选择“混检”。
局限于具体实现的操作水平,可见每组检测的样本不宜过多,而实际中也多是采用10人一组的混检。
这样既保证了有较高的检测效率,同时也适用于具体的检测。
由此可见,理论中最优的检测组合不一定适用于实际,在实践中还得考虑实际的检测能力。
课本上的理论分析透了的同时,通过实验这样的实践途径可以让我们将理论与实际更好得结合起来,科学是改变生活的工具,它不能是空中楼阁,所以我们要懂得变通,不局限于理论,贴合实际才能更好地解决问题。