基于前瞻性時空掃描統(tǒng)計量的蒙特卡羅重排掃描方法的研究*

高凌云志 ，宋肖肖 ，龍 華 ，杜慶治 ，張 琪 ，邵玉斌

（1.昆明理工大學 信息工程與自動化學院，云南 昆明 650500；2.昆明醫(yī)科大學 公共衛(wèi)生學院，云南 昆明 650500）

0 引 言

隨著輿情監(jiān)測系統(tǒng)的大量研究與嘗試性實施[1-2]，其中存在以報紙為數(shù)據(jù)源的輿情監(jiān)測方式。在傳統(tǒng)的監(jiān)測方式中，很難做到提前對可能出現(xiàn)爆發(fā)的區(qū)域做出預警判斷。在大量的預警模型中，一種基于前瞻性的時空掃描成為了應用與研究的熱點。它能夠使用歷史數(shù)據(jù)對數(shù)據(jù)源進行實時的數(shù)據(jù)分析，并能夠提前對疑似聚集點進行預警，從而使得在某區(qū)域出現(xiàn)輿情爆發(fā)前做出相應的判斷成為可能。在前瞻性時空掃描統(tǒng)計量的使用過程中，通過對掃描區(qū)域圓心、掃描半徑、掃描時間節(jié)點的改變，能夠使掃描圓柱體動態(tài)地掃描整個監(jiān)測區(qū)域。通過計算每次掃描區(qū)域的對數(shù)廣義似然比（Log Likelihood Ratio，LLR），可以得出掃描區(qū)域的異常程度。此時，通過蒙特卡羅法對掃描區(qū)域進行數(shù)據(jù)重排，來統(tǒng)計學檢驗掃描的異常區(qū)域，判斷其異常程度是否在合理范圍。實際上，采用蒙特卡羅重排方法，可以近似對異常點進行評估[3-4]。

綜上所述，在現(xiàn)有的基于前瞻性時空掃描模型中，沒有針對數(shù)據(jù)重排方法進行研究，使用的都是由Kulldorff M在SatScan[4]中提出的重排模型。本文評估異常區(qū)域時，在重排過程中，將采用全隨機重排和關聯(lián)重排兩種不同方法進行數(shù)據(jù)處理，從而得到不同的數(shù)據(jù)結(jié)果。通過使用不同的蒙特卡羅重排掃描的方法，研究和比對其對異常區(qū)域的評估所產(chǎn)生的具體影響，并通過實驗數(shù)據(jù)結(jié)合實際情況，探尋一種應用于前瞻性時空掃描中的不同需求的蒙特卡羅重排掃描方法。

1 前瞻性時空掃描模型

數(shù)據(jù)源由各地區(qū)日報中新聞文本和空間距離處理后形成的數(shù)據(jù)矩陣組成。新聞文本數(shù)據(jù)時空矩陣是分布于地理區(qū)域范圍內(nèi)各報刊網(wǎng)點在一個時間范圍內(nèi)的新聞文章中包含的詞語數(shù)結(jié)果，空間距離矩陣則表述了各報紙網(wǎng)點之間的空間關系。每一個報紙網(wǎng)點都會覆蓋本地區(qū)的新聞信息，如《南京日報》《青島日報》《北京日報》等，都會發(fā)表關于本地的新聞文本信息。

1.1 全域掃描模型框架設計

圖1為全域掃描模型的整體設計流程圖，判定是否獲取到排名前三的數(shù)據(jù)后，結(jié)束整個掃描過程。

1.2 前瞻性時空掃描實現(xiàn)方法

按照各地區(qū)報紙網(wǎng)點作為監(jiān)測點、使用報紙的ID號作為全區(qū)域中的區(qū)塊（z=1,…,Z）劃分，如湖北地區(qū)有《楚天都市報》《湖北日報》《三峽晚報》等。時間節(jié)點（d=1,…,D）可選取天、月、年，本文選取的時間節(jié)點以天為單位。對報紙中的每篇文章進行特征詞提取，如“爆炸”“升溫”“沖突”等。當選擇“爆炸”為監(jiān)測特征時，由此形成文本特征詞矩陣C=[Czd]，其中Czd表示報紙z某時間d所監(jiān)測的文本特征詞數(shù)量總和。在時空分析上，文本特征詞數(shù)量總和C可以通過時空矩陣各項求和得出，即：

圖1 掃描流程

設Cz和Cd是文本特征詞矩陣Czd分別沿列和行的累加和，稱為空間和時間上的邊緣累計和。使用空間和時間上的邊緣累計和及總文本特征詞數(shù)量來估計某區(qū)在某時間節(jié)點段上的期望文本特征詞數(shù)量 μzd：

并由文本特征詞數(shù)量平均值得到平均值矩陣，設為M=[μzd]。同時，按照與文本特征詞數(shù)量矩陣相關聯(lián)的方法生成距離矩陣，設為L，其中由于距離的對稱性，有Lij=Lji，Lii=0，i=1,…,Z。實際中，掃描區(qū)域往往為局部范圍。當距離不遠時，可采用平面近似距離算法。

掃描過程設為一個圓柱體A的移動過程，設圓柱體掃描模型A的底面圓心為掃描區(qū)域中的一個報紙網(wǎng)點ZA，半徑為RA，圓柱體的高表示時間范圍，則每一次掃描對于指定的ZA，需遍歷所有z=1,…,Z，選出滿足LzA,z＜RA的報紙網(wǎng)點。圓柱體掃描模型A中的時空文本特征數(shù)設為，圓柱體內(nèi)的文本特征數(shù)量期望值設為。假定一個報紙網(wǎng)點所在區(qū)域中的所有新聞信息是相互獨立的，則單位時段上，在半徑為RA范圍圓形內(nèi)的報紙網(wǎng)點中的文本特征詞數(shù)量服從泊松分布。通過判斷數(shù)據(jù)向量中的各數(shù)值服從泊松分布的程度，識別特征詞發(fā)生的獨立性程度。對于局部區(qū)域A內(nèi)，使用廣義辨識似然比[5-6]檢驗泊松分布：

廣義辨識似然比在實際計算中常常使用對數(shù)化的結(jié)果，稱為對數(shù)廣義似然比（LGLR）：

圖2為窗口范圍內(nèi)期望數(shù)為10例，全域總數(shù)分別為50、200和2 000時，窗口內(nèi)實際監(jiān)測文本特征數(shù)量從1到30變化時相應的對數(shù)似然比曲線。由圖1可知，全域總數(shù)對對數(shù)似然比曲線有影響，但變化不大。隨著全域的擴大，局部窗口上相同實際監(jiān)測文本特征數(shù)量一定時，其對數(shù)似然比有所減小。當實發(fā)數(shù)等于期望數(shù)時，對數(shù)似然比為0（見圖2，CA=μA=10）。所以，若只需對數(shù)似然比反映實發(fā)數(shù)的上偏情況，則要對似然比的計算作分段考慮，忽略實際文本特征數(shù)小于期望文本特征數(shù)的情況。

圖2 似然比影響趨勢

2 重排掃描實現(xiàn)方法

2.1 蒙特卡羅重排應用原理

雖然用對數(shù)似然比可以初步判識聚焦的可能性，但是對數(shù)似然比還與數(shù)據(jù)的統(tǒng)計分布特征有關。依據(jù)統(tǒng)計學對顯著性的定義，需要使用事件發(fā)生的概率估計來表述，即一個小概率事件如果發(fā)生了，則這個事件就被認為是顯著的。由于不能夠通過對數(shù)廣義似然比直接計算此疑似點SOP（Suspected Outburst Point）的概率估計，所以通過蒙特卡羅隨機方法對原文本特征矩陣重排后再進行掃描，計算相應的對數(shù)似然比下的概率估計值P。P可以通過原始掃描的疑似暴發(fā)點的對數(shù)廣義似然比在重排掃描后得到的大量重排疑似暴發(fā)點中的排序得到，其中Csop為原始掃描出的疑似暴發(fā)點的排名，Cre_all為全部重排疑似暴發(fā)點的總量。

重排方式分為兩種：全隨機重排和關聯(lián)重排。全隨機重排的物理意義在于，每一個監(jiān)測點所發(fā)布的新聞數(shù)據(jù)只與自己有關，每一個時間節(jié)點上的數(shù)據(jù)具有獨立性，重排過程中可隨意打亂，每一個監(jiān)測點打亂順序不同。關聯(lián)重排的物理意義在于，每一個監(jiān)測點發(fā)布的新聞數(shù)據(jù)與其他監(jiān)測點相關聯(lián)，在時間節(jié)點上的數(shù)據(jù)與其他監(jiān)測點具有關聯(lián)性，在一次重排過程中具有相同的隨機性。

2.2 全隨機重排

圖3為全隨機重排流程圖，對原監(jiān)測文本特征詞數(shù)量矩陣進行隨機重排，提取每一個監(jiān)測點所代表的行矩陣。為了使每一次的重排方法的起始規(guī)則相同，給定一個初始隨機種子randseed，并獲取初始隨機種子，以隨機種子為基礎，產(chǎn)生一個（0～N）范圍內(nèi)的隨機整數(shù)。本文選取0～10 000范圍內(nèi)的隨機整數(shù)，此時隨機數(shù)的產(chǎn)生概率為0.000 1。按照時間節(jié)點范圍Tmin～Tmax確定縮放比例，以保證每一次獲取到的隨機數(shù)都不會隨著重排過程而衰減。按照縮放后的隨機數(shù)，抽取行矩陣中對應時間節(jié)點上的監(jiān)測文本特征詞數(shù)量放置于末位，并以當前產(chǎn)生的隨機數(shù)修改初始隨機種子，作為下一次重排的初始隨機種子。此物理意義在于，認為每一個監(jiān)測點的每一個時間節(jié)點上的文本特征詞數(shù)量都是沒有關系的，即No.1報紙網(wǎng)點在某一天的監(jiān)測文本特征詞數(shù)量與其他報紙網(wǎng)點沒有關聯(lián)。每一次行矩陣的重排方法都是由不同的隨機種子所決定。

圖3 全隨機重排流程

2.2.1 疑似點同半徑掃描

在完成對所有行矩陣S=[Cz]的隨機重排后，得到新的監(jiān)測文本特征詞匯量矩陣C=[Czd]。對新的監(jiān)測文本特征詞數(shù)量矩陣按照時空掃描模型進行掃描，掃描過程中考慮疑似聚集點SOP的同半徑R情況下的掃描，即所有的掃描都按照固定半徑進行。它的物理意義在于，判斷相同掃描面積下，不同區(qū)域中暴發(fā)的估計值。

2.2.2 全域重復掃描

在完成對所有行矩陣S=[Cz]的隨機重排后，得到新的監(jiān)測文本特征詞數(shù)量矩陣Cre=[Czd]。對新的矩陣按照時空掃描模型進行掃描，掃描過程中使用第一次掃描原始監(jiān)測文本特征詞數(shù)量矩陣的參數(shù)，變換圓心、半徑、時間節(jié)點進行掃描。

2.3 關聯(lián)重排

圖4為關聯(lián)重排流程圖。關聯(lián)重排的方法，即認為在此區(qū)域內(nèi)的所有報紙中的監(jiān)測文本特征詞數(shù)量是相互關聯(lián)的，每一個時間節(jié)點上的文章都是相互作用、相互影響的。在重排每一個行矩陣時，將使用相同的隨機種子，即整個監(jiān)測文本特征詞數(shù)量矩陣C=[Czd]的重排按照每一列的方法同時移動。提取每一個報紙編號所代表的行矩陣，為了使每一次的重排方法的起始規(guī)則相同，給定一個初始隨機種子randseed，并獲取初始隨機種子。以隨機種子為基礎，產(chǎn)生一個0～10 000范圍內(nèi)的隨機整數(shù)，此時隨機數(shù)的產(chǎn)生概率為0.000 1。按照時間節(jié)點范圍Tmin～Tmax確定縮放比例，即監(jiān)測文本特征詞數(shù)量矩陣的列數(shù)，以保證每一次獲取到的隨機數(shù)都不會隨著重排過程而衰減。按照縮放后的隨機數(shù)，抽取行矩陣中的對應時間節(jié)點上的監(jiān)測文本特征詞數(shù)量，并放置于末位。下一次行矩陣重排時，使用與上一重排相同的隨機種子。在所有的行矩陣掃描完成后，得到新的文本特征矩陣Czd。按照兩種不同的掃描方法得到重排掃描后的最大疑似暴發(fā)點SOP。使用此種方法，直至循環(huán)重排N次，本文循環(huán)999次結(jié)束。使用與全隨機重排相同的方法，以同半徑和全域兩種方式進行掃描。

表1 紐約數(shù)據(jù)掃描對比

圖4 關聯(lián)重排流程

3 實驗驗證

使用SatScan中提供的紐約市2001年11月01日至24日的數(shù)據(jù)作為真實數(shù)據(jù)源，采用上述模型進行掃描驗證，實驗數(shù)據(jù)對比如表1所示。

表1中，行代表不同重排掃描的評估值，列代表不同重排掃描方法，表中數(shù)據(jù)為排序前三的疑似點。三個疑似暴發(fā)點相同，所有掃描圓心、半徑、掃描范圍全部一致，對數(shù)廣義似然比分別為3.845、3.164、2.137。由表1可以對比發(fā)現(xiàn)，提取掃描結(jié)果中排名前三的疑似暴發(fā)點進行對比，實驗共進行了7次不同方法的掃描。在使用相同的紐約數(shù)據(jù)情況下，掃描到的最大疑似暴發(fā)點SOP參數(shù)相同。表1中列舉了不同重排掃描方法下疑似暴發(fā)點的評估值P。在相同的掃描、重排方法下，重排掃描99次與999次實際相差不大。掃描復雜度上升了10倍的情況下，只提升了少量精度。所以，在大量的區(qū)域掃描重排中，可進行99次重排掃描，減少重排次數(shù)，提高效率。

橫向?qū)Ρ炔煌瑨呙柚嘏欧椒ㄏ碌脑u估值P可以發(fā)現(xiàn)，全隨機重排的敏感性更高。同時，在相同的重排模式下，同半徑掃描要比全域掃描敏感性高。

使用隨機泊松數(shù)據(jù)[7]進行驗證，隨機生成服從泊松分布的隨機數(shù)，當作每一個時間節(jié)點上的特征詞數(shù)，均值選擇λ=20，并隨機播撒到原矩陣中，修改原始數(shù)據(jù)源，形成服從泊松分布的模擬矩陣。對模擬數(shù)據(jù)進行不同方法的重排掃描，實驗數(shù)據(jù)對比如表2所示。

表2 泊松數(shù)據(jù)掃描對比

表2中，行代表不同重排掃描的評估值，列代表不同重排掃描方法，表中數(shù)據(jù)為排序前四的疑似點。四個疑似暴發(fā)點相同，所有掃描圓心、半徑、掃描范圍全部一致，對數(shù)廣義似然比分別為4.805、4.523、4.307、4.235。由表2數(shù)據(jù)對比可以發(fā)現(xiàn)，在泊松模擬數(shù)據(jù)源下，同半徑的掃描結(jié)果敏感性更高，同時關聯(lián)重排掃描結(jié)果與全隨機重排掃描結(jié)果大致相同。在全域掃描方法下，對于同樣的數(shù)據(jù)源，其敏感程度較低，表現(xiàn)為疑似暴發(fā)點的估計值P增長。與紐約數(shù)據(jù)實驗結(jié)果相同，在同半徑掃描方法下，簡化掃描復雜度的情況下，提高了敏感性。

4 結(jié) 語

在基于前瞻性時空掃描統(tǒng)計量的重排掃描中，同半徑的掃描方法要大于全域的掃描方法。由于掃描半徑的限定，在重排掃描過程中，可以在大量重排實驗中更加快速地專項比對疑似暴發(fā)點SOP的評估值P。同時，在某些比較敏感的地區(qū)如國家邊境地區(qū)，需要實施數(shù)據(jù)處理。掃描量較大時，可以通過非關聯(lián)性的同半徑重排方法進行掃描，以提高對疑似暴發(fā)點的敏感性，使其適應高靈敏度的需要。在非人口聚集區(qū)或掃描量不大的區(qū)域，不需要過于敏感時，可使用非關聯(lián)性全域重排的方法對此區(qū)域進行掃描，適當降低靈敏度，達到早期預警、快速發(fā)現(xiàn)的需要。