成 晨，程新洲，晁 昆，张 涛，曹丽娟，徐乐西，韩玉辉，张晴晴（中国联通研究院，北京 100048）

1 概述

2019 年末，首例新型冠状病毒肺炎在湖北省武汉市出现，并随着2020年春运期间的大规模人群迁徙迅速传播。经过艰苦卓绝的努力，我国疫情防控阻击战取得重大战略成果，目前已进入常态化的防疫阶段。

针对抗疫阻击战，习近平总书记多次作出重要批示指示，强调要运用大数据等手段，加强疫情溯源和监测。2020 年，工业和信息化部多次召开疫情防控大数据专家会商会，传达国务院应对新型冠状病毒感染的肺炎疫情联防联控机制会议精神，研究部署大数据支撑服务疫情防控相关工作。

在疫情防控中，与感染者直接居住生活在一起、共同乘坐交通工具、乘电梯以及通过其他方式直接接触的人员被称为密切接触者。与显性密切接触者（共同居住生活或工作的人）相比，隐性密切接触者（无法通过现有实名制数据直接追溯到的接触者）难以追溯和排查却依然存在感染风险。例如2020年1月19日，重庆市一名公交车乘客因为与一名患者相隔16 秒登上同辆公交车，而被确诊为新冠肺炎患者；2020年1月22 日，湖南某城市一个感染者乘坐公交车同时传染了13个人。

随着疫情防控工作逐渐常态化，对隐性密切接触者排查的精准化需求逐渐提升。运用传统的排查方法难以定位隐性接触者，而运营商大数据以其独特的优势在寻找隐性接触者时可发挥重要作用。运营商是天然的大数据集中地，拥有百万级的基站资源、亿级出账用户数、PB 级日均数据生成及采集量，运营商大数据具备用户规模巨大、覆盖空间广、时间连续性强的优势，可以全面立体地刻画用户特征，为找到隐性接触者提供一定支撑。寻找乘坐共同的公共交通工具的隐性接触者，可以抽象为轨迹聚类问题，现有轨迹聚类算法的核心思想是采用欧式距离作为损失函数，基于k-means 或基于密度的聚类算法进行轨迹聚类，而没有充分地考虑各类噪声数据对聚类结果的影响。另一方面，现有聚类方法多侧重于数据清洗后的聚类算法实施过程，而没有针对运营商OSS 域大数据从预处理到模型训练的完整过程。

2 数据预处理与模型构建

2.1 OSS域数据预处理

运营商大数据主要分为两大类：BSS 域数据和OSS 域数据。BSS 数据来自于业务支撑系统，主要涉及计费、营业情况、账务和客户服务资料。OSS数据来自于运营支撑系统，涉及核心网络电路域、分组域、无线网络基础数据。本文所述的隐性接触者的定位方法主要采用运营商OSS域大数据的XDR（X Detail Record）数据源的信令面数据，关联工参获得基站位置，即经纬度信息，最终得到如下数据字段：imsi、开始时间、结束时间、基站经度、基站纬度。

数据预处理流程如下。

a）确认某一感染者的移动轨迹，获取其近日所乘坐的公交车线路。

b）采集相同时间区间内的全市OSS 域XDR 信令面数据，并关联工参获取位置信息。

c）数据去冗余，对于同一日的每个imsi，每5 min保留1条数据，即保留00：00：00，00：05：00，00：10：00，……，23：55：00 的数据，作为time_id。最终得到的数据包含如下字段：imsi、time_id、基站经度、基站纬度。

2.2 用户筛选与向量化

将特定时间范围内、特定地理范围的用户转换为二维向量，方法为：

a）设感染者为I，在t1～tn的时间内在某一公交车上。则按照第2.1 节所述，进行预处理，将其转化为二维向量：I_msisdn=｛［t1，s1］，［t2，s2］，…，［tn，sn］｝，其中ti为time_id，si为一个二维数组［经度，纬度］。

b）筛选（t1，tn）时间，在s1，s2，…，sn位置点中的任意2个或2个以上位置点出现过的所有用户的msisdn。

c）将b）中所筛选得到的所有用户的位置进行向量化，对于每一个用户，将时空分布转化为：p_msisdn=｛［t1，s1］，［t2，s2］，［t3，s3］，［t4，s4］，［t5，s5］，［t6，s6］…｝。

d）找到每一个p_msisdn 的［t，s］第1 次和最后一次和I_msisdn 中的［t，s］重合点，分别为［tf，s］f和［tl，s］l，将p_msisdn 更 新：p_msisdn=｛［tf，s］f，［tf+1，sf+1］，［tf+2，sf+2］，……，［tl-1，sl-1］，［tl，s］l｝。例如，假设p_msisdn 的［t，s］第1次和最后一次和I_msisdn中的［t，s］重合点分别为［t3，s3］和［t（n-2），s（n-2）］，则更新p_msisdn 为｛［t3，s3］，［t4，s4］，［t5，s5］，［t6，s6］，……，［t（n-2），s（n-2）］｝。

3 多目标轨迹聚类算法

3.1 优化损失函数

现有的k-means 聚类算法，采用欧式距离作为损失函数。但是移动网络实际所产生的XDR 数据，可能存在有大量的离群点或噪声点的问题。例如，由于工参上报错误，导致用户所在小区的经纬度上报错误，使得用户所在的小区的实际位置和关联到的小区经纬度不一致，产生了大量的离群点。又如，由于乒乓效应，用户在相邻小区间反复切换，使用户经纬度反复跳跃；或者由于越区覆盖，不同用户在同一位置，关联得到的经纬度却不同，由此产生大量的噪声点。

如果采用欧式聚类作为损失函数，则会导致聚类效果受到噪声点和离群点的影响，效果不理想。因此引入Minkowski距离作为损失函数：

其中，p越小，则对抗离群点的效果越好；p越大，则对抗噪声点的效果越好。

由于各个地域数据移动网络建设水平不同、数据采集厂商不同，数据中的离群点以及噪声点的占比无法明确。为了在节约计算资源的情况下，尽可能准确地找到和感染者共同乘坐公共交通工具的用户，设计p值的边界作为损失函数的系数的最大值和最小值。

a）pmin=0.01，用于对抗离群点，例如工参错误带来的误差。

b）pmax=100，用于对抗噪声点，例如乒乓效应带来的误差。

3.2 基于多目标函数的簇头选择算法

k-means 算法的核心思想是以样本之间的距离衡量相似性，通过将样本划分为若干提前设定好数量的簇，使得簇内各个样本间距离最小，而簇间距离最大。k-means 算法选择簇头的方法的第1 步是随机选择k个节点作为初始化的簇头选择方案，然后再进行更新迭代簇头位置。因此，若初始化簇头选择方案不合理，将会影响聚类效果。簇头选择问题是一个np-hard问题，传统线性算法难以找到最优解，因此引入群体智能算法解决该问题。另一方面，如3.1 小节所述，移动网络实际所产生的XDR 数据，可能存在有大量的离群点或噪声点的问题，因此需要引入Minkowski 距离作为损失函数，且应根据现网数据特征选取不同的p值，从而形成不同的损失函数。因此，本文提出了一种群体智能算法——基于多目标的鸟群觅食算法，并将其应用于k-means算法的簇头选择过程中。

3.2.1 鸟群觅食算法

鸟群觅食算法（Particle Swarm Optimization，PSO）是群体智能算法中的一种，源于群居性生物通过自组织性的个体协作表现出的群体智能性，包括遗传算法、蛙跳算法等。本文提出的鸟群觅食算法旨在通过模拟鸟群寻找食物的过程寻找最优解，其过程为：通过每一次迭代，每只鸟通过飞行速度调整前进的距离和方向。其中，每只鸟的速度由它本身的运动过程中的最好适应度的位置以及整个鸟群的最好适应度的位置决定。算法步骤为：

设鸟群中有S只鸟，进行t次迭代，第i只鸟当前的位置为Xi(t)=[Xi1(t),Xi2(t),...,XiM(t)]。速 度 为Vi(t)=[Vi1(t),Vi2(t),...,ViM(t)]。每次迭代中，基于适应度值更新每只鸟的最好位置以及整个鸟群的最好位置。每只鸟的个体最好位置定义为局部最优解，即它在历次迭代中所经历的适应度最大的位置，表示为Pi(t)=[Pi1(t),Pi2(t),...,PiM(t)]。整个鸟群的最好位置定义为全局最优解，即目前整个鸟群搜索到的最好位置，表示为G(t)=[Pg1(t),Pg2(t),...,PgM(t)]，1≤g≤M。

每次迭代后，局部最优解的更新方式为：

每只鸟的速度的更新方式为：

位置的更新方式为：

其中1 ≤i≤S,1 ≤j≤M，t为当前进化次数，T为预设的最大进化次数，c1为其向局部最优解运动的步长，c2为其向全局最优解运动的步长，rand 服从［0，1］均匀分布，限制每只鸟的速度的变换范围为Vij(t)∈[-。当t0，则表示选择节点作为簇头；反之，则不选择该节点作为簇头。

3.2.2 多目标鸟群觅食算法

Surgical management is the preferred approach for cardiac liposarcoma, given its metastatic potential and the significant associated cardiorespiratory morbidity.

首先引入多目标鸟群觅食算法中的相关概念。

a）非支配解。假设多目标场景的目标为函数最大值，x和y是2 个解，S是解集，若fi(x)≥fi(y),(i=1,2,…m)恒成立且fi(x)=fi(y),(i=1,2,…m)不恒成立，则定义x为非支配解，y被x支配。

b）支配解。若fi(x)≤fi(y),(i=1,2,…m)恒成立且fi(x)=fi(y),(i=1,2,…m)不恒成立，则y支配x，y称为非支配解。

c）Pareto 最优解和最优解集。若存在解z不被任何解支配，则称其为Pareto 最优解，所有的Pareto 最优解组成了Pareto 最优解集，该解集是算法进化的最终的目标。

引入多目标的鸟群觅食算法的步骤如下。

步骤1：初始化鸟群S，将每个向量Xi(t)的每一位随机赋值为-1 或1，并初始化速度向量Vi(t)每一位为0，根据Xi(t)选择簇头初始化，然后按照k-means 算法的更新过程进行轨迹聚类。分别令损失函数中的参数p赋值为0.01 以及100，计算2 种损失函数所对应的S集合的每个Xi(t)的适应度值。

步骤2：得到S中每个Xi(t)的非支配解等级并将其排序，即：首先遍历S中的每个解y1，得到每个y1 支配的解集Sy1以及被y1 支配的解的数量ny1。若ny1=0，则没有任何一个解支配y1，则令y1的非支配等级为1。随后，对于所有非支配等级为1 的解y1，遍历Sy1中的每个解y2 以及被y2 支配的解的数量ny2，并令ny2=ny2-1，若ny2=0，则把解y2 放入集合Sy2，令Sy2中所有解的非支配等级为2。接着，对于所有非支配等级为2 的解y2，遍历Sy2中的每个解y3 以及被y3 支配的解的数量ny3，并令ny3=ny3-1，若ny3=0，则把解y3 放入集合Sy3，令Sy3中所有解的非支配等级为3。按同样的方法操作集合Sy3，得到非支配等级为4的集合，最终得到所有的解的非支配等级。

步骤3：计算每个解的拥挤度，针对非支配等级相同的解，按照拥挤度由小到大排列，把非支配等级为1的前M个解保存在集合Z中。

步骤5：混合S和Snew，并按照非支配等级对里面的解进行排序，对于非支配等级相同的解，按照拥挤度从小到大排列，把前M个解保存在集合Z中。

步骤6：若未达到最大进化次数，另S=Snew，返回第5步；否则，进化完成，Z集合中的每个解都是一种簇头初始化方法，并得到对应的轨迹聚类结果。

3.3 多目标鸟群觅食算法性能测试

评价多目标优化问题，一般基于真实解与计算得出的解的距离（Generation Distance，GD）和分散度（Spacing，SP）2 个指标。下面使用通用测试函数ZDT4函数评估算法性能，该函数可以有效评价算法是否容易陷入局部最优解：

仿真参数设定为：迭代次数T=1 000，鸟群规模为100，c1=c2=0.01，仿真结果如图1～图3所示。

图1 多目标鸟群觅食算法求得的ZDT4最优解和真正的Pare to最优解对比图

图2 多目标鸟群觅食算法求得的ZDT4函数最优解

图3 ZDT4函数真正的Pareto最优解

由图1 可知，多目标鸟群觅食算法求得的支配解集与真实Pareto 最优解集基本相同，可见该算法可以有效找到最优解集。算法求出的非支配解集和真实Pareto 最优解集见图2 和图3。计算得到GD=4.425×10-4，SP=0.004 105。2个值均较小，算法性能较好。

4 用轨迹聚类优化算法获取隐性接触者

将多目标鸟群觅食算法引入k-means 算法的簇头选择中，并将优化的k-means聚类算法用于轨迹聚类，方法如下。

a）将I_msisdn=｛［t1，s1］，［t2，s2］，…，［tn，sn］｝进行分解，转化为如下向量集合：

b）将a）中生成的所有I_msisdn 按照向量的长度，由长到短排列。对于每一个相同长度的I_msisdn，找到所有相同长度的p_msisdn，分别令p=10 以及p=0.1，作为损失函数。

c）用k-means 聚类算法，找到所有与I_msisdn 为同一聚类的用户，作为潜在的隐性接触者。

下面以某市某个感染者为例，假设有感染者I，其msisdn 为1565176××××，某日他乘坐公共交通工具时，时空轨迹如图4所示。

图4 感染者当日轨迹

按照第2.2 节所述，将其时空轨迹向量化为I_msisdn，并将多目标鸟群觅食算法引入k-means算法的簇头选择中，并将优化的k-means 聚类算法用于轨迹聚类，按照第3.3 节所述方法进行轨迹聚类，共找到324名隐性密切接触者，可用于向防疫部门报送。

5 总结

目前我国已进入常态化疫情防控阶段，感染者的密切接触者排查对防止疫情扩散有着至关重要的作用。传统的密切接触者排查方法在一定程度上难以找到隐性密切接触者，给疫情防控工作带来了一定的挑战。而通过运营商大数据，可以获取用户的身份属性、时空轨迹、常驻区域、业务偏好、交际圈子等多维度信息，从而在疫情联防联控、人口流动洞察、疫情态势研判和决策等方面发挥重要的作用，特别是为隐性接触者的排查提供强有力的支撑。本文在传统kmeans 聚类算法的基础上，针对不同地区运营商数据的特征引入了Minkowski 距离作为损失函数，提出基于多目标函数的簇头选择算法，形成了多目标轨迹聚类优化算法。在此基础上，构建基于运营商大数据和多目标函数的簇头选择算法的新冠肺炎疫情防控的密切接触者排查方法体系，助力隐性接触者的排查。