一種基于信息量的時空深度掃描模型

龍 華，王 美，楊 威，邵玉斌

(昆明理工大學 信息工程與自動化學院，昆明 650500)

E-mail：longhua@kmust.edu.cn

1 引 言

空間和時空掃描模型在預測預警模型中一直備受關注，自kulldorff[1，2]提出相應模型后，被廣泛用于流行病[3-5]、生態學[6]，犯罪學[7，8]等諸多領域中.在時空掃描模型中，每個掃描窗口為一個集群對象，模型定義底面為掃描覆蓋區域，高度為時間閾值的圓柱體為掃描窗口，根據窗口內外統計的發生與未發生事件得到似然函數，引入蒙特卡洛方法基于似然函數檢測得到集群評估統計的顯著性[9]，在最大掃描范圍和最大掃描時間閾值內，不斷迭代空間和時間得到各圓柱體窗口的顯著性，從而獲取到較高風險聚集區域.對時空掃描模型課題的研究中，決定掃描窗口的掃描半徑、掃描時間閾值和掃描窗口形狀，決定掃描統計量的測試統計量假設分布以及次級掃描區域即除了最大似然比對應區域以外的掃描區域處理等均是討論的熱點問題[10].

掃描窗口問題的討論中，Patil和Taillie[11]創新性的采用上層設置的概念減小窗口大小使得能檢測任意形狀的簇，提升集群檢測能力，Duczmal和Assun??o[12]則采用模擬退火方法，基于圖的算法連通子圖空間找到似然比局部最大的區域，Kulldorff[13]和Christiansen[14]討論了使用橢圓形窗口替代經典模型中圓形掃描窗口，并證明在特定數據集中有一定的優勢；測試統計量假設分布的討論中，較有代表性的是2014年Can?ado[15]提出了零膨脹掃描統計量(zero-inflated Poisson ZIP)，在該模型中當數據集包含大量零時，為了提高掃描結果中的空間精確度和空間召回率，將零分為符合泊松分布的抽樣零和獨立隨機變量得到的結構零，對該模型的有效性檢驗可查閱Allévius 和H?hle[16]于2019做的模擬研究實驗，此外還有測試統計量符合超幾何分布的情況等.在前述方法模型中均會涉及一個問題，即掃描過程會產生成千上萬相互重疊的重要集群，這類集群會模糊較風險區域的判斷，傳統時空掃描以及前面提到的改進模型均按Satscan層次結構將其直接刪除，只報告不相交不重復的集群，但很明顯該方法會損失很多對信息量更有貢獻的集群[17].

為了充分利用潛在集群的信息，Gangnon[18]使用加權平均似然比檢驗統計量，將重疊集群用似然比加權合并，該方法只適合集群相對較少的情況，集群較多時會合并成較大而無實際報告意義的集群，李小洲和王勁峰[19]用優化選擇格網點間隔方法和多重排序算法，以達到減少候選聚集區域的遺漏，并在較短的時間內刪除所有的重復候選聚集的目的，該方法刪除的是完全重復的集群，仍然留下大量交集較大的集群模糊較風險區域的判斷，同樣不能達到很好處理次級區域的效果，Gangnon與李小洲各自所提方法總的來說都存在不能量化分析實際效果的問題，直到2016年Han和Junhee[17]提出使用基尼系數--一種量化分析次級區域的方法來確定最優的集群，如當一個大的集群里面包含幾個小的集群時，比較大的集群根據觀察數據和預期數據得到的基尼系數與其包含的小集群同樣方法計算得到的基尼系數，選擇報告基尼系數較大的區域，減小信息量的損失，從所舉例子可知其使用對象導致Han和Junhee所提方法有一定的局限性，Han和Junhee所提方法是在保持傳統方法使用層次結構刪除掃描重復窗口的情況下，再次使用基尼系數做判斷，所以分析的過程中會存在很多問題，如文獻[19]說的他們只考慮了緊湊的簇所以顯示結果良好，但實際使用中并不理想，如文獻[20]提出的基于基尼系數分析時在即使單個較大的群集確實有一定意義的情況下，往往會導致報告的是多個較小的群集.

為了充分利用潛在集群的信息，同時不出現Han和Junhee誤報告的問題，我們提出一種基于信息量的時空深度掃描模型IN-scan model，引入信息量I(p,G)，p為統計值，G為基尼系數，從信息量的角度出發量化每一個掃描集群，在不做刪除重復掃描區域，充分利用有效信息的情況下，報告出較有意義的集群.

2 時空掃描模型相關概念

2.1 置信度

時空掃描模型，主要是找出聚集性較高，即置信度(1-p)較大的集群，模型中似然函數值反應一個窗口為聚集域的可能性，即最可能的聚集域是最大化對數似然比對應的掃描窗口，此時測試統計量T=maxZLog(LR(z)).假設我們研究區域是Z，z表示某個掃描窗口，其似然比表示如下：

(1)

其中，cz和μz分別表示掃描窗口z內的觀察案例和預期案例，C=∑z∈Zcz和N=∑z∈Zμz分別表示掃描區域Z內的總觀察案例和總預期案例，在模型中如果只對較高可能為聚集域的掃描分析感興趣則使用如公式1中的指示函數I(cz>μz)，若考慮的是較不可能為聚集域的使用I(cz<μz)，若二者均考慮則刪除指示函數，在本文的研究中僅考慮第一種情況.

得到各掃描域的似然比值，還需要對其進一步分析屬于非隨機的置信度(1-p)，求解p值目前有兩個方法一個是測試統計量T看做近似服從于極值分布[21]做計算，一個是采用蒙特卡羅(Monte Carlo)假設檢驗方法求解，因為T真實服從的分布還有待研究，故文中選后者方法.使用Monte Carlo計算得到p=rank(LLR)/(M+1)，LLR為真實數據集掃描域計算得到的似然比，M個隨機數據集是根據真實數據集采用重排算法得到的，M個隨機數據集對應計算得到M個LLR′，將真實的LLR與M個LLR′放在一起由大到小排序返回排序值rank(LLR)，由此計算得到p值.p值越小對應聚集域屬于非隨機的置信度越大.后面提到的pi表示第i個掃描窗口對應的統計值.

2.2 LR-scan 模型

LR-scan模型是使用了對數似然比為測試統計量并引入了Junhee提出的基尼系數判別方法的最新時空掃描模型，該模型首先是根據置信度得到最大的聚集域對重復域進行一次刪除，然后根據基尼系數對重復域進行再一次篩選.該方法依然存在信息浪費與報導有偏差問題，故本文提出IN-scan模型.

LR-scan模型已于SaTScan中更新，SaTScan是用于時空掃描統計分析的一個開源軟件，其集成了很多時空掃描的方法.當前，LR-scan 模型是最新添加的方法，因此文中也將LR-scan方法稱為最新SaTScan方法.

3 基于信息量的時空深度掃描模型

時空掃描方法屬于預警模型，集群置信度越大越容易報警，即其區域內發生事件的概率越大.在IN-scan 模型中，我們將每個集群的置信度視為集群內事件發生的概率，進而計算事件均值和基尼系數，然后根據求得的p和G計算信息量.圖1是我們提出模型的結構，首先與LR-scan 模型一致以對數似然比為測試統計量進行掃描計算，但IN-scan不對掃描結果進行刪除，而是對其求均值，以進行二次以信息量為測試統計量的掃描計算，然后依次報導較風險的聚集域.本節將給出各個參數的計算方法.

圖1 基于信息量的時空深度掃描模型結構Fig.1 IN-scan model structure

模型特點為：

1)只考慮較高可能發生性事件，故始終有地點i觀察案件數oi大于等于預測案件數μi；

2)使用均值數據，n′i和μ′i；

3)于L中二次掃描，測試統計量使用信息量I(p,G).

3.1 事件均值計算

假設圖2中3個集群的掃描條件均一樣，且掃描時間也一致，此時結合表1記錄以地點A為例有：nA1=nA2=nA3=nA，μA1=μA2=μA3=μA,加入事件發生的概率，計算地點A數據的均值：

(2)

地點B和C與A分析一致.這樣計算完成后相當于把cluster1、cluster2、cluster3的信息映射到掃描區域L中，二次掃描時只用分析L中的數據即可，見方法介紹模塊.

圖2 均值分析-聚集域分布圖Fig.2 Mean analysis-aggregation area distribution map

表1 均值分析-聚集域記錄Table 1 Mean analysis-aggregation area recording

3.2 基于事件均值計算的基尼系數

基尼系數[22]是洛倫茲曲線的一個度量值，洛倫茲曲線[23]主要用于經濟領域，如圖3所示基尼系數G=S1/(S1+S2),G越大說明收入分配越不平等.Han和Junhee首次將G用于時空掃描模型中，其橫縱軸分別表示觀察到案例的累加

圖3 聚集域基尼系數顯示圖Fig.3 Aggregation area of Gini coefficient

百分比和預期案例的累積百分比，G=0時，即說明該集群無顯著性，而G越大，對應掃描域的置信度(1-p)越大，Han使用G是為了報告出更有意義的集群，在我們的研究模型中，研究G亦是為了報告出能提供更多信息量I的集群.

在對IN-scan model模型的研分析中，由于我們使用的是均值數據，地點i觀察案件數n′i與預測案件數μ′i能綜合反映i點的風險度，此時地點i與地點j信息相對獨立，所以在掃描區域L中進行二次掃描時，測試統計值信息量I(p,G)中的G我們使用掃描域內的n′從小到大排序后計算得到，見圖3，假設掃描域為table1中的cluster3，掃描時間為1天，此時若n′c>n′B>n′A，見圖4中t=1的G顯示圖，圖中陰影部分占下三角的面積百分比即為G值，t=2和t=3類似分析，從圖3中可看出就基尼系數來說，cluster3掃描時間為1天時G較大.在IN-scan model中，結合p與G值計算各條件下的集群的信息量，報告I最大的集群.

圖4 t=1的G顯示圖Fig.4 G display of t=1

在考慮全部潛在集群的分析中，計算基尼系數時，使用事件均值計算可減小誤差，如圖5是基于Satscan樣本數據集紐約市醫院記錄的發燒案例，在Satscan和我們最終模擬實驗中知道圖中兩個掃描區域是以171為中心的窗口較異常優先報告，當直接使用觀測值計算基尼系數時，見表2，169對應的基尼系數明顯高于171對應的值，在傳統模型中由于使用層次結構的方法提前刪除了169對應窗口，所以不會報告，說明在不做刪除重復掃描區域的情況下，直接使用觀測結果和基尼系數做判斷會產生誤差，基于此問題，我們充分利用有效信息，對各掃描點做均值后再次掃描計算基尼系數，比較出基尼系數較大的窗口，表3是使用提出方法實驗的結果，可看出能正確比較出171對應窗口.考慮到基尼系數和顯著性統計值，均能反應信息量的大小且相互影響，所以我們將引入信息量I(p,G)分析最終結果.

圖5 相交窗口分析Fig.5 Intersection of windows with center 169 and 171

3.3 基于p和G的信息量計算

在很多領域信息量都是作為選優條件的評估指標，如地質學[24]和工程學[25]，尤其在預警領域，很多時候會由于信息量較少導致大量的假預警報告，所以更應該考慮信息量因素，信息量表達式為I(x)=-log2p(x)，其中p(x)表示事件x發生的概率，p(x)越小信息量I越大.對于我們模型來說I∝(1/p)，I∝G，所以有：

表2 Han和Junhee方法重疊圓分析結果Table 2 Analysis result of the intersecting windows by Han and Junhee

表3 使用均值方法重疊圓分析結果Table 3 Analysis result of the intersecting windows with mean value

備注：表中center:掃描中心點，r (Km):掃描半徑(單位是千米)，ids:掃描窗口包含的地點集合，observed:掃描窗口內總的觀察案例數，expected:掃描窗口內總的期望案例數，p：顯著性統計值，G：基尼系數.

I(p,G)=-logp-log(1-G)p∈(0,1],G∈[0,1)

(3)

顯著性統計值p越小，基尼系數G越大，信息量I越大.集群I越大,越優先報警.

4 評估方法

為了評估基于信息量的時空深度掃描模型的空間精度，結合機器學習中的評估方法[26]以及2012年Neil[27]提出的空間精確度SP和空間召回率SR，文中使用F-Score作為模型評估指標.此處若Z*表示檢測到的聚集空間區域，ZT表示真實爆發區域，則有：

(4)

|Z*|和|ZT|分別是Z*和ZT包含的地點數，若向集群中多添加地點將有利于召回率同時精確率會有所下降，若從檢測的區域移除地點會造成以召回率為代價提高精確率結果，故需要同時權衡SP和SR.在模型中我們不希望|Z*|很大，導致SP很小，但SR很大的情況，SP和SR同樣重要，故評估參數F-Score表達式如下：

(5)

5 實驗與分析

時空掃描統計方法應用于多領域，2008年Vadrevu[28]和Tuia應用時空掃描方法監測火災風險區域取得一定成效，本次實驗中我們將采用舊金山的火災數據展開討論.實驗數據集來自舊金山地區數據協調網站DataSF1提供的“Fire Department Service”火災記錄公開數據集，數據集中包含舊金山18年和19年上半年共四萬余條火災記錄數據，且網站在實時更新中，考慮實驗的回顧性驗證所以實驗數據集隨機提取2018年1月和3月的火災事件進行研究.圖6是數據集中舊金山火災發生的地點標記圖.

圖6 舊金山火災觀測地點圖Fig.6 San Francisco fire observed sites

5.1 結果與討論

本節中用IN-scan表示我們提出的基于信息量的時空深度掃描模型，LR-scan表示現有最新時空掃描模型，實驗中使用IN-scan與LR-scan的掃描結果比較，說明新模型的有效性.首先選取時間2018年1月8號-14號的數據進行分析，掃描半徑設置為r=5Km，最大掃描時間t=3day，首先基于似然比測試統計量不刪除重復窗口進行掃描，并使用蒙特卡羅計算掃描得到的每個掃描窗口的置信度，表4中輸出前5個掃描結果.最大掃描時間為3天，故實驗結果中包括掃描時間分別為1天、2天和3天的情況，實驗中會分開計算，這里以分析t=1為例，如表4中第一個模塊中最大似然比對應包含掃描區域為12，獲取以12為圓心的所有同心圓包含的地點集合D12，之后獲取以D12包含的地點為掃描中心的所有窗口，然后按照事件均值求解方法算出各地點的均值，計算結果見表5，表中obaerves和expected是地點的觀測值和預期值，obaerves-mean和expected-mean是地點的觀測值均值和預期值均值，表中有觀測值不一定有觀測期望值，如locations 2 觀測值為2，但觀測期望值為0，是因為包含有地點2的全部窗口置信度都為0導致，也有觀測值很小，但觀測期望值很大，如locations 12，因為地點12自身的觀測值很大，包含有地點12的窗口置信度多數偏高，故觀測期望值很大.基于期望值求取各窗口的基尼系數，使用基尼系數和置信度隨之求取各窗口的信息量，表6即為表4中第一個掃描窗口計算得到的信息量I，在計算結果中留下最大信息量對應窗口，同時取剩下的第一個集群重復分析取出信息量最大的窗口，如此循環直到I=0停止.

表4 1.8-1.14，r=5Km前五個掃描結果Table 4 Top five scan results from 1.8-1.14，r=5K

表5 1.8-1.14 t=1 均值表Table 5 Mean values from 1.8-1.14，t=1

表6 地點12，t=1信息量計算Table 6 Information calculation of location 12，t=1

實驗選取2018年1月8號-14號與2018年3月8號-14號做掃描對比實驗，首先確定真實爆發區域ZT.實驗最終比較的是模型對異常地點檢測的準確性和回歸率，因為我們考慮的是短期爆發事件，故文中爆發定義為掃描時間后對應的第一周內發生事件，見圖7可得1.15-1.21爆發地點集[1，2，3，7，8，10，11，12，13，14，16，20，23，24，25，26，27，29，32，34]，3.15-3.21爆發地點集為[1，2，3，5，6，7，10，12，13，15，17，20，21，25，33，39].對比結果見表7-表9.

表7 1.8-1.14，r=5 km掃描結果比較Table 7 F-Score comparison from 1.8-1.14，r=5 km

表8 3.8-3.14，r=5 km掃描結果比較Table 8 F-Score comparison from 3.8-3.14，r=5 km

表9 3.8-3.14，r=3 km掃描結果比較Table 9 F-Score comparison from 3.8-3.14，r=3 km

表7掃描時間1月8號-14號，掃描半徑為5km，運用評估模塊的計算方法，得到相比LR-scan，IN-scan的F-Score提高14%；為了驗證方法的有效性使用時間段3月8號-14號，掃描半徑為5km進行掃描，見表8相比LR-scan，IN-scan的F-Score提高18%；實驗3選取同一時間段3月8號-14號，但不同掃描半徑(3km)進行掃描，見表9相比LR-scan，IN-scan的F-Score提高12.6%.總體比較，IN-scan模型較現時空掃描模型F-Score性能評估值提升10%以上.

圖7 1.15-21與3.15-21火災爆發統計圖Fig.7 Fire outbreak statistics comparisonbetween 1.15-21 and 3.15-21

5.2 結果分析

從實驗結果來看，現存在的時空掃描方法中對掃描過程產生的大量重復域直接進行刪除確實存在一定的缺陷，或是留下了置信度大但信息量很小的聚集域，或是剔除了置信度小但信息量大的聚集域，即使向LR-scan模型加入了基尼系數進行第二次判斷也不能避免此類問題，一定程度上會加重該問題，因為LR-scan模型中進行基尼系數計算時，往往會報告多個較小的群集，而該類集群往往是置信度大但信息量較小.可見我們提出的IN-scan模型在綜合處理權衡聚集域的置信度與信息量上有一定優勢.

6 總結與展望

在時空掃描方法中，每次掃描都會產生成千上萬大量有重復的集群，現有研究方法會按Satscan層次結構刪除此類集群，或者用似然比加權集群分析.每個集群都會對應一個置信度，都能得到直觀反應他們異常度的基尼系數值，故不應該直接刪除或合并，所以為了充分利用掃描域提供的信息，量化分析選取報警區域，我們提出了一種基于信息量的時空深度掃描模型，深度是因為進行了二次掃描，基于信息量是因為我們利用每個聚集域的觀測值均值和預期值均值計算得到基尼系數G和基于似然比掃描的得到的統計值p得到信息量IN展開比較報告較有意義的集群，經過實驗對比，確實有一定有效性.

另外本文介紹的IN-scan模型具有很強的穩定性.現有模型中當存在多個集群時需要使用適用于多個集群的估計方法進行進一步分析，而IN-scan模型可以對重復的多個群集進行分析，直接計算相交群集中的事件所包含案例.就目前的研究來說，我們僅考慮單個事件類型，而忽略了事件間的內部結構差異造成的影響等，即考慮多元變量問題，這是我們下一個主要研究的方向.