作者：京东数科JUST团队-何华均
2020年，COVID-19（新冠疫情）席卷全球，对全球生命卫生安全构成了极大挑战。截至2020年11月2日， 全球累计确诊4681万人，累计死亡近120万人。在没有疫苗情况下，早发现、早报告、早隔离、早治疗是控制疫情的最有效方案。
如何通过大数据来快速找出你身边的高危人群，是亟待解决的问题。
京东数科智能城市在疫情期间，就成功通过大数据挖掘，帮北京市快速找到 500 余名高危的密切接触者，为宿迁市找到全市范围四分之一比例的新冠肺炎确诊人员；在全国范围内，帮广州、南京、成都等 18 个省市做了高危人群态势分析。在此过程中，我们提出了一种新颖的轨迹感染风险度量和高效的查询方案，这项工作已发布在这篇论文中。【He, Huajun & Li, Ruiyuan &Wang, Rubin & Bao, Jie & Zheng, Yu & Li, Tianrui. (2020). EfficientSuspected Infected Crowds Detection Based on Spatio-Temporal Trajectories.。】
一、问题背景致命病毒在人与人之间的传播一直是全球公共卫生面临的重要问题。从19世纪前半叶开始，由霍乱狐菌引发的霍乱夺取了无数人的生命，仅仅印度，在霍乱爆发之后的100年间，由其造成的死亡人数高达3800万人。在欧洲，仅在1831年间死亡人数高达90万人。2002年底，“非典”疫情爆发，其病死率近11％。从2019年底开始至今，一种新冠病毒（SARA-Cov-2）造成的疾病COVID-19席卷全球，对全球生命卫生安全构成了极大挑战。截至2020年11月2日，COVID-19 全球累计确诊4681万人，累计死亡近120万人。
在没有疫苗情况下，早发现、早报告、早隔离、早治疗是控制疫情的最有效方案。中国政府根据四早方案，果断采取封城、方舱隔离等措施，很快控制住了COVID-19的传播，保障了人民的安全。
因为COVID-19具有极高的传染性，它可以通过唾液等传播，并且几乎人人易感。因此，早发现病毒携带者并及时将其隔离，就能阻止他传播给其他人，进而有效地防止疫情大规模传播。
传统寻找病毒携带者主要通过以下两种方案：1）人工询问患者曾经去过的地方和接触的人群，然后让相关社区工作人员去核实和隔离密切接触者；2）通过患者的出行记录，如火车票，飞机票等，找到与患者同乘的人。但以上这两种做法十分依赖于患者的记忆，并且很难找全与患者有过一段近距离共处的陌生人。
随着移动互联网的高速发展，每时每刻都会产生大量的时空数据。这些时空数据记录着人的活动轨迹。因此，如果我们掌握了COVID-19患者在被隔离前的活动轨迹，那么我们就可以很清楚地知道他去过的地方，再通过时空范围查询就能找到跟患者有过近距离接触的人群。如图1所示，给定患者移动轨迹（如图1中红色轨迹），易感人群挖掘找出与这条轨迹有过密切接触的人群（如图1中蓝色人群）。
图1：易感人群示意图
现存轨迹度量，如DTW、EDR、Hausdorff等算法能计算轨迹的全局相似度[3]。但是，只要与患者在很小的时空范围内近距离接触就可能被感染，因此这些度量不适用于易感人群判断。此外，COVID-19潜伏期很长，甚至超过了14天，并且它在潜伏期也有传染性。然而，一座城市14天产生的轨迹数据量可能会十分庞大。因此，计算全城中所有与患者接触的人群需要巨大的计算量。
为此，我们提出了一种新颖的轨迹度量，它将轨迹分成若干传播子段，再计算各个子段与患者密切接触程度，最后我们将疑似人与患者所有传播子段的接触概率综合起来评价他被感染的概率。此外，我们利用JUST引擎管理防疫期间的海量轨迹，并设计了一种空间优化索引SFT，其将相近时空范围内的轨迹段聚集在一起，极大地加快了查询效率。
二、基本框架为了处理大量患者传播的易感人群，我们开发了一个快速查询的解决方案。如图2所示，我们系统的主要结构由三个部分组成：数据预处理，候选者提取和感染性探索。
图2：算法框架
数据预处理：如图2中最上面的方框所示，我们首先将轨迹的噪声位置过滤掉。之后，我们将轨迹分段。然后，我们使用XZ2T索引来组织轨迹段，再通过JUST[2]将它们存储到NoSQL数据库中。
候选者提取：候选者提取过程使用分段算法、SFT索引策略和时空查询接口。分段的目的是避免轨迹太长而带来的较大的内存和I/O开销。我们在所有待查询轨迹段上建立了SFT索引，其中具有类似时空范围的段被放置在SFT索引同一叶节点中。然后，我们通过扩展SFT每个叶节点的时空范围，再从数据库中提取候选片段。最后，我们从数据库中获得了粗粒度的候选对象，并且数据冗余度低且I / O消耗较小。
感染性探索:图2的最底部的框显示了感染性探索的过程。首先，我们修剪一些不可能是密切接触的候选人；然后，我们计算剩余疑似人群在患者可传播段的感染概率，再聚合属于同一轨迹的局部轨迹段的所有传染性，并计算出其轨迹的总体传染性。最后，我们过滤传染性低于感染阈值的轨迹。
三、数据预处理
由于用户轨迹数量巨大，造成传统数据库难以实现快速查询。因此，我们通过分布式数据库（如HBase），将海量轨迹数据用key-value的形式存储在具有多备份且安全的分布式集群上。然而，传统分布式并不直接支持轨迹数据，为此需要为轨迹数据设计特殊的行键结构，才能取得更佳查询效率。我们设计的XZ2T索引，能高效的管理类似轨迹这种多维时空数据。XZ2T索引按照固定时间跨度（如，年，月，日）将时间划分为若干不相交的区间，并通过XZ2索引将二维空间范围映射到一维整数域中，如图3所示，然后再组合时间分区号和空间编码值为存储键，再将其键和数据存储在分布式数据库中以备易感人群挖掘查询离线使用。
图3：表设计
四、候选者提取1、分段
首先，我们患者的轨迹分成若干个可传播片段，这些片段可以准确的表示患者曾经在那些地方活动过。然后，我们通过查询每个轨迹片段可能感染的时空范围，找到候选易感人群。我们从两个时间或者空间间隔超过一定值的轨迹点中间切断轨迹，形成轨迹段。如图4中，最大时间间隔为30分钟，最大空间间隔为50m。
图4：轨迹分段
2、SFT索引
在实际的使用场景中，患者的数据会批量增加，如果采用循环查询将花费大量的时间。为此，我们设计了空间优先时空索引SFT，其将相近时空范围内的轨迹段聚集在一起并一同查询疑似人群。这样的设计极大地减少了I/O开销和数据冗余。如图5所示，在SFT索引中，我们首先通过四叉树将轨迹段聚类在不同节点上，然后再在每一个叶子节点中建立一维R索引管理时间范围。
图5：SFT空间优先索引
3、ST Query
如图6所示，我们患者轨迹（蓝色轨迹）分成两条子段s1, s2，每条轨迹段会形成一个活动的空间（如图6中红色实线表示的矩形范围）和时间（如图6中q1.t和q3.t之间的时间范围）范围，我们将空间范围和时间范围扩张θd, θt得到受影响时空范围。最后，我们从数据库中提取出所有出现在患者影响时空范围内的人群，并根据用户ID聚合属于同一人的轨迹，进而得到疑似人群。并通过下面的具体实现第五节中描述的感染风险度量方案确定疑似人群的风险值。
图6：疑似人群查询
五、感染风险COVID-19患者会感染跟他有过密切接触的人。因此，被感染风险的影响因素与患者和正常人接触的时空距离远近有很重要的关系。所以，患者轨迹中的每一个轨迹点都能形成一个传播的时空范围。
1、时空关系度量
我们将轨迹点定义为l = (p, t)，其中p表示位置，t表示时刻。给定一个轨迹点位置l, 一个空间影响范围θd和一个时间影响范围θt.我们用STR（l, θd, θt.）来表示时空影响范围。如下：
其中dist表示空间距离，在位置l影响的时空范围STR（l, θd, θt.）内，我们通过公式（1）计算人群与该时空位置上的密切接触程度：
(1)
其中，st_dist(l, v)表示两个时空位置之间的距离。如公式（2）所示:
(2)
其中，λ属于[0, 1]区间，它用来控制空间和时间的偏好，和将空间距离和时间间隔归一化到[0,1]范围内。注意，如果一条轨迹与STR（l,θd, θt.）不相交，那么它在l处的时空接触可能为0。
2、轨迹感染风险
（1）局部轨迹段的感染风险
为了更精准的描述患者传播路径，需要将患者从潜伏期开始到被隔离期间的所有轨迹集中起来。但，由于GPS终端有些信号不稳定或者用户关闭了终端等原因，造成了患者在这段时间的轨迹并不一定是一直连续的。并且，患者所有时空点组成的一条轨迹具有较大的时空范围，这样会在时空查询时产生大量的冗余数据。因此，我们需要将轨迹分段，将长轨迹分割成较为合适的轨迹局部段。如图四所示，我们从两个时间或者空间间隔超过一定距离的轨迹点中间切断轨迹，形成轨迹段。
给定病毒携带者的局部轨迹段（s）和疑似感染人员的轨迹（T），我们通过公式（3）衡量疑似人员在携带者的局部轨迹段被感染的风险。公式（3）如下：
(3)
其中，l是轨迹段s中的一个时空位置，|s|代表s的时空位置数量。
（2）轨迹感染风险
一个病毒携带者的完整轨迹由多个局部轨迹段组成。因此，仅仅通过局部轨迹段的感染风险并不能完全反应疑似人员被感染风险。如，某个疑似人员虽然跟患者在各个轨迹局部段接触并不多，但是他多次出现在患者不同的局部轨迹段中，那么他也被感染的风险应该更大。因此，简单的做法通过将疑似人员在携带者各个局部段的被感染风险值相加作为最终感染风险。但是，如果病毒携带者在某一个轨迹局部段停留时间越长，那么他在该位置传播病毒的可能越大。因此，如公式（4），我们需要考虑给携带者的局部轨迹段加上权重来标记它可能的传播强度。如公式（5）中，我们用时间的相对占比来标记可能的强度。
(4)
(5)
3、剪枝策略
易感人群算法需要计算患者每个时空点与附近疑似人群的感染概率，因此需要大量的计算量。所有，我们提供了四种剪枝策略来减少计算量。剪枝策略的详细描述见[1]。
(6)
(7)
(8)
(9)
六、案例
图7：易感人群系统
我们基于本算法开发了易感人群查询系统。如图7所示，我们将手机等设备和应用产生的时空轨迹数据存储在JUST平台中，并利用JUST提供的轨迹预处理功能完成原始轨迹去噪和分段操作。然后我们将轨迹存储在JUST提供的轨迹表中。再将第五节设计的易感人群算法封装为DAL操作，让用户可以通过一条简单的SQL语句就能很快地完成易感人群查询。最后，对外输出易感人群名单支持上层应用。
该系统已经支持了北京、武汉、广州、南京、成都等多个省市。在疫情最关键的前几个月，我们帮北京市找到 500 余名高危的密切接触者；为宿迁市找到全市范围四分之一比例的新冠肺炎确诊人员；并协助其它团队完成高危人群态势分析。
参考文献：
[1] He, Huajun & Li, Ruiyuan &Wang, Rubin & Bao, Jie & Zheng, Yu & Li, Tianrui. (2020). EfficientSuspected Infected Crowds Detection Based on Spatio-Temporal Trajectories.
[2] http://just.urban-computing.com/
[3] https://mp.weixin.qq.com/s/95DJin1jHNntg1X9sp6R8Q
