運營商大數(shù)據(jù)軌跡聚類優(yōu)化算法及其在疫情防控中的應(yīng)用

成 晨，程新洲，晁 昆，張 濤，曹麗娟，徐樂西，韓玉輝，張晴晴（中國聯(lián)通研究院，北京 100048）

1 概述

2019 年末，首例新型冠狀病毒肺炎在湖北省武漢市出現(xiàn)，并隨著2020年春運期間的大規(guī)模人群遷徙迅速傳播。經(jīng)過艱苦卓絕的努力，我國疫情防控阻擊戰(zhàn)取得重大戰(zhàn)略成果，目前已進入常態(tài)化的防疫階段。

針對抗疫阻擊戰(zhàn)，習(xí)近平總書記多次作出重要批示指示，強調(diào)要運用大數(shù)據(jù)等手段，加強疫情溯源和監(jiān)測。2020 年，工業(yè)和信息化部多次召開疫情防控大數(shù)據(jù)專家會商會，傳達國務(wù)院應(yīng)對新型冠狀病毒感染的肺炎疫情聯(lián)防聯(lián)控機制會議精神，研究部署大數(shù)據(jù)支撐服務(wù)疫情防控相關(guān)工作。

在疫情防控中，與感染者直接居住生活在一起、共同乘坐交通工具、乘電梯以及通過其他方式直接接觸的人員被稱為密切接觸者。與顯性密切接觸者（共同居住生活或工作的人）相比，隱性密切接觸者（無法通過現(xiàn)有實名制數(shù)據(jù)直接追溯到的接觸者）難以追溯和排查卻依然存在感染風(fēng)險。例如2020年1月19日，重慶市一名公交車乘客因為與一名患者相隔16 秒登上同輛公交車，而被確診為新冠肺炎患者；2020年1月22 日，湖南某城市一個感染者乘坐公交車同時傳染了13個人。

隨著疫情防控工作逐漸常態(tài)化，對隱性密切接觸者排查的精準(zhǔn)化需求逐漸提升。運用傳統(tǒng)的排查方法難以定位隱性接觸者，而運營商大數(shù)據(jù)以其獨特的優(yōu)勢在尋找隱性接觸者時可發(fā)揮重要作用。運營商是天然的大數(shù)據(jù)集中地，擁有百萬級的基站資源、億級出賬用戶數(shù)、PB 級日均數(shù)據(jù)生成及采集量，運營商大數(shù)據(jù)具備用戶規(guī)模巨大、覆蓋空間廣、時間連續(xù)性強的優(yōu)勢，可以全面立體地刻畫用戶特征，為找到隱性接觸者提供一定支撐。尋找乘坐共同的公共交通工具的隱性接觸者，可以抽象為軌跡聚類問題，現(xiàn)有軌跡聚類算法的核心思想是采用歐式距離作為損失函數(shù)，基于k-means 或基于密度的聚類算法進行軌跡聚類，而沒有充分地考慮各類噪聲數(shù)據(jù)對聚類結(jié)果的影響。另一方面，現(xiàn)有聚類方法多側(cè)重于數(shù)據(jù)清洗后的聚類算法實施過程，而沒有針對運營商OSS 域大數(shù)據(jù)從預(yù)處理到模型訓(xùn)練的完整過程。

2 數(shù)據(jù)預(yù)處理與模型構(gòu)建

2.1 OSS域數(shù)據(jù)預(yù)處理

運營商大數(shù)據(jù)主要分為兩大類：BSS 域數(shù)據(jù)和OSS 域數(shù)據(jù)。BSS 數(shù)據(jù)來自于業(yè)務(wù)支撐系統(tǒng)，主要涉及計費、營業(yè)情況、賬務(wù)和客戶服務(wù)資料。OSS數(shù)據(jù)來自于運營支撐系統(tǒng)，涉及核心網(wǎng)絡(luò)電路域、分組域、無線網(wǎng)絡(luò)基礎(chǔ)數(shù)據(jù)。本文所述的隱性接觸者的定位方法主要采用運營商OSS域大數(shù)據(jù)的XDR（X Detail Record）數(shù)據(jù)源的信令面數(shù)據(jù)，關(guān)聯(lián)工參獲得基站位置，即經(jīng)緯度信息，最終得到如下數(shù)據(jù)字段：imsi、開始時間、結(jié)束時間、基站經(jīng)度、基站緯度。

數(shù)據(jù)預(yù)處理流程如下。

a）確認(rèn)某一感染者的移動軌跡，獲取其近日所乘坐的公交車線路。

b）采集相同時間區(qū)間內(nèi)的全市OSS 域XDR 信令面數(shù)據(jù)，并關(guān)聯(lián)工參獲取位置信息。

c）數(shù)據(jù)去冗余，對于同一日的每個imsi，每5 min保留1條數(shù)據(jù)，即保留00：00：00，00：05：00，00：10：00，……，23：55：00 的數(shù)據(jù)，作為time_id。最終得到的數(shù)據(jù)包含如下字段：imsi、time_id、基站經(jīng)度、基站緯度。

2.2 用戶篩選與向量化

將特定時間范圍內(nèi)、特定地理范圍的用戶轉(zhuǎn)換為二維向量，方法為：

a）設(shè)感染者為I，在t1～tn的時間內(nèi)在某一公交車上。則按照第2.1 節(jié)所述，進行預(yù)處理，將其轉(zhuǎn)化為二維向量：I_msisdn=｛［t1，s1］，［t2，s2］，…，［tn，sn］｝，其中ti為time_id，si為一個二維數(shù)組［經(jīng)度，緯度］。

b）篩選（t1，tn）時間，在s1，s2，…，sn位置點中的任意2個或2個以上位置點出現(xiàn)過的所有用戶的msisdn。

c）將b）中所篩選得到的所有用戶的位置進行向量化，對于每一個用戶，將時空分布轉(zhuǎn)化為：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｝。例如，假設(shè)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 多目標(biāo)軌跡聚類算法

3.1 優(yōu)化損失函數(shù)

現(xiàn)有的k-means 聚類算法，采用歐式距離作為損失函數(shù)。但是移動網(wǎng)絡(luò)實際所產(chǎn)生的XDR 數(shù)據(jù)，可能存在有大量的離群點或噪聲點的問題。例如，由于工參上報錯誤，導(dǎo)致用戶所在小區(qū)的經(jīng)緯度上報錯誤，使得用戶所在的小區(qū)的實際位置和關(guān)聯(lián)到的小區(qū)經(jīng)緯度不一致，產(chǎn)生了大量的離群點。又如，由于乒乓效應(yīng)，用戶在相鄰小區(qū)間反復(fù)切換，使用戶經(jīng)緯度反復(fù)跳躍；或者由于越區(qū)覆蓋，不同用戶在同一位置，關(guān)聯(lián)得到的經(jīng)緯度卻不同，由此產(chǎn)生大量的噪聲點。

如果采用歐式聚類作為損失函數(shù)，則會導(dǎo)致聚類效果受到噪聲點和離群點的影響，效果不理想。因此引入Minkowski距離作為損失函數(shù)：

其中，p越小，則對抗離群點的效果越好；p越大，則對抗噪聲點的效果越好。

由于各個地域數(shù)據(jù)移動網(wǎng)絡(luò)建設(shè)水平不同、數(shù)據(jù)采集廠商不同，數(shù)據(jù)中的離群點以及噪聲點的占比無法明確。為了在節(jié)約計算資源的情況下，盡可能準(zhǔn)確地找到和感染者共同乘坐公共交通工具的用戶，設(shè)計p值的邊界作為損失函數(shù)的系數(shù)的最大值和最小值。

a）pmin=0.01，用于對抗離群點，例如工參錯誤帶來的誤差。

b）pmax=100，用于對抗噪聲點，例如乒乓效應(yīng)帶來的誤差。

3.2 基于多目標(biāo)函數(shù)的簇頭選擇算法

k-means 算法的核心思想是以樣本之間的距離衡量相似性，通過將樣本劃分為若干提前設(shè)定好數(shù)量的簇，使得簇內(nèi)各個樣本間距離最小，而簇間距離最大。k-means 算法選擇簇頭的方法的第1 步是隨機選擇k個節(jié)點作為初始化的簇頭選擇方案，然后再進行更新迭代簇頭位置。因此，若初始化簇頭選擇方案不合理，將會影響聚類效果。簇頭選擇問題是一個np-hard問題，傳統(tǒng)線性算法難以找到最優(yōu)解，因此引入群體智能算法解決該問題。另一方面，如3.1 小節(jié)所述，移動網(wǎng)絡(luò)實際所產(chǎn)生的XDR 數(shù)據(jù)，可能存在有大量的離群點或噪聲點的問題，因此需要引入Minkowski 距離作為損失函數(shù)，且應(yīng)根據(jù)現(xiàn)網(wǎng)數(shù)據(jù)特征選取不同的p值，從而形成不同的損失函數(shù)。因此，本文提出了一種群體智能算法——基于多目標(biāo)的鳥群覓食算法，并將其應(yīng)用于k-means算法的簇頭選擇過程中。

3.2.1 鳥群覓食算法

鳥群覓食算法（Particle Swarm Optimization，PSO）是群體智能算法中的一種，源于群居性生物通過自組織性的個體協(xié)作表現(xiàn)出的群體智能性，包括遺傳算法、蛙跳算法等。本文提出的鳥群覓食算法旨在通過模擬鳥群尋找食物的過程尋找最優(yōu)解，其過程為：通過每一次迭代，每只鳥通過飛行速度調(diào)整前進的距離和方向。其中，每只鳥的速度由它本身的運動過程中的最好適應(yīng)度的位置以及整個鳥群的最好適應(yīng)度的位置決定。算法步驟為：

設(shè)鳥群中有S只鳥，進行t次迭代，第i只鳥當(dāng)前的位置為Xi(t)=[Xi1(t),Xi2(t),...,XiM(t)]。速 度 為Vi(t)=[Vi1(t),Vi2(t),...,ViM(t)]。每次迭代中，基于適應(yīng)度值更新每只鳥的最好位置以及整個鳥群的最好位置。每只鳥的個體最好位置定義為局部最優(yōu)解，即它在歷次迭代中所經(jīng)歷的適應(yīng)度最大的位置，表示為Pi(t)=[Pi1(t),Pi2(t),...,PiM(t)]。整個鳥群的最好位置定義為全局最優(yōu)解，即目前整個鳥群搜索到的最好位置，表示為G(t)=[Pg1(t),Pg2(t),...,PgM(t)]，1≤g≤M。

每次迭代后，局部最優(yōu)解的更新方式為：

每只鳥的速度的更新方式為：

位置的更新方式為：

其中1 ≤i≤S,1 ≤j≤M，t為當(dāng)前進化次數(shù)，T為預(yù)設(shè)的最大進化次數(shù)，c1為其向局部最優(yōu)解運動的步長，c2為其向全局最優(yōu)解運動的步長，rand 服從［0，1］均勻分布，限制每只鳥的速度的變換范圍為Vij(t)∈[-。當(dāng)t0，則表示選擇節(jié)點作為簇頭；反之，則不選擇該節(jié)點作為簇頭。

3.2.2 多目標(biāo)鳥群覓食算法

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

首先引入多目標(biāo)鳥群覓食算法中的相關(guān)概念。

a）非支配解。假設(shè)多目標(biāo)場景的目標(biāo)為函數(shù)最大值，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 最優(yōu)解和最優(yōu)解集。若存在解z不被任何解支配，則稱其為Pareto 最優(yōu)解，所有的Pareto 最優(yōu)解組成了Pareto 最優(yōu)解集，該解集是算法進化的最終的目標(biāo)。

引入多目標(biāo)的鳥群覓食算法的步驟如下。

步驟1：初始化鳥群S，將每個向量Xi(t)的每一位隨機賦值為-1 或1，并初始化速度向量Vi(t)每一位為0，根據(jù)Xi(t)選擇簇頭初始化，然后按照k-means 算法的更新過程進行軌跡聚類。分別令損失函數(shù)中的參數(shù)p賦值為0.01 以及100，計算2 種損失函數(shù)所對應(yīng)的S集合的每個Xi(t)的適應(yīng)度值。

步驟2：得到S中每個Xi(t)的非支配解等級并將其排序，即：首先遍歷S中的每個解y1，得到每個y1 支配的解集Sy1以及被y1 支配的解的數(shù)量ny1。若ny1=0，則沒有任何一個解支配y1，則令y1的非支配等級為1。隨后，對于所有非支配等級為1 的解y1，遍歷Sy1中的每個解y2 以及被y2 支配的解的數(shù)量ny2，并令ny2=ny2-1，若ny2=0，則把解y2 放入集合Sy2，令Sy2中所有解的非支配等級為2。接著，對于所有非支配等級為2 的解y2，遍歷Sy2中的每個解y3 以及被y3 支配的解的數(shù)量ny3，并令ny3=ny3-1，若ny3=0，則把解y3 放入集合Sy3，令Sy3中所有解的非支配等級為3。按同樣的方法操作集合Sy3，得到非支配等級為4的集合，最終得到所有的解的非支配等級。

步驟3：計算每個解的擁擠度，針對非支配等級相同的解，按照擁擠度由小到大排列，把非支配等級為1的前M個解保存在集合Z中。

步驟5：混合S和Snew，并按照非支配等級對里面的解進行排序，對于非支配等級相同的解，按照擁擠度從小到大排列，把前M個解保存在集合Z中。

步驟6：若未達到最大進化次數(shù)，另S=Snew，返回第5步；否則，進化完成，Z集合中的每個解都是一種簇頭初始化方法，并得到對應(yīng)的軌跡聚類結(jié)果。

3.3 多目標(biāo)鳥群覓食算法性能測試

評價多目標(biāo)優(yōu)化問題，一般基于真實解與計算得出的解的距離（Generation Distance，GD）和分散度（Spacing，SP）2 個指標(biāo)。下面使用通用測試函數(shù)ZDT4函數(shù)評估算法性能，該函數(shù)可以有效評價算法是否容易陷入局部最優(yōu)解：

仿真參數(shù)設(shè)定為：迭代次數(shù)T=1 000，鳥群規(guī)模為100，c1=c2=0.01，仿真結(jié)果如圖1～圖3所示。

圖1 多目標(biāo)鳥群覓食算法求得的ZDT4最優(yōu)解和真正的Pare to最優(yōu)解對比圖

圖2 多目標(biāo)鳥群覓食算法求得的ZDT4函數(shù)最優(yōu)解

圖3 ZDT4函數(shù)真正的Pareto最優(yōu)解

由圖1 可知，多目標(biāo)鳥群覓食算法求得的支配解集與真實Pareto 最優(yōu)解集基本相同，可見該算法可以有效找到最優(yōu)解集。算法求出的非支配解集和真實Pareto 最優(yōu)解集見圖2 和圖3。計算得到GD=4.425×10-4，SP=0.004 105。2個值均較小，算法性能較好。

4 用軌跡聚類優(yōu)化算法獲取隱性接觸者

將多目標(biāo)鳥群覓食算法引入k-means 算法的簇頭選擇中，并將優(yōu)化的k-means聚類算法用于軌跡聚類，方法如下。

a）將I_msisdn=｛［t1，s1］，［t2，s2］，…，［tn，sn］｝進行分解，轉(zhuǎn)化為如下向量集合：

b）將a）中生成的所有I_msisdn 按照向量的長度，由長到短排列。對于每一個相同長度的I_msisdn，找到所有相同長度的p_msisdn，分別令p=10 以及p=0.1，作為損失函數(shù)。

c）用k-means 聚類算法，找到所有與I_msisdn 為同一聚類的用戶，作為潛在的隱性接觸者。

下面以某市某個感染者為例，假設(shè)有感染者I，其msisdn 為1565176××××，某日他乘坐公共交通工具時，時空軌跡如圖4所示。

圖4 感染者當(dāng)日軌跡

按照第2.2 節(jié)所述，將其時空軌跡向量化為I_msisdn，并將多目標(biāo)鳥群覓食算法引入k-means算法的簇頭選擇中，并將優(yōu)化的k-means 聚類算法用于軌跡聚類，按照第3.3 節(jié)所述方法進行軌跡聚類，共找到324名隱性密切接觸者，可用于向防疫部門報送。

5 總結(jié)

目前我國已進入常態(tài)化疫情防控階段，感染者的密切接觸者排查對防止疫情擴散有著至關(guān)重要的作用。傳統(tǒng)的密切接觸者排查方法在一定程度上難以找到隱性密切接觸者，給疫情防控工作帶來了一定的挑戰(zhàn)。而通過運營商大數(shù)據(jù)，可以獲取用戶的身份屬性、時空軌跡、常駐區(qū)域、業(yè)務(wù)偏好、交際圈子等多維度信息，從而在疫情聯(lián)防聯(lián)控、人口流動洞察、疫情態(tài)勢研判和決策等方面發(fā)揮重要的作用，特別是為隱性接觸者的排查提供強有力的支撐。本文在傳統(tǒng)kmeans 聚類算法的基礎(chǔ)上，針對不同地區(qū)運營商數(shù)據(jù)的特征引入了Minkowski 距離作為損失函數(shù)，提出基于多目標(biāo)函數(shù)的簇頭選擇算法，形成了多目標(biāo)軌跡聚類優(yōu)化算法。在此基礎(chǔ)上，構(gòu)建基于運營商大數(shù)據(jù)和多目標(biāo)函數(shù)的簇頭選擇算法的新冠肺炎疫情防控的密切接觸者排查方法體系，助力隱性接觸者的排查。