面向積水推測的機會式感知軌跡選擇

張偉杰，於志勇，黃昉菀，朱偉平

(福州大學 數學與計算機科學學院 福建 福州 350108)

0 引言

隨著感知技術和計算環(huán)境的成熟，大數據的應用領域越來越廣泛，城市計算[1]就是運用這類數據來解決城市中的各類問題，促進智慧城市[2]的發(fā)展。城市積水影響著城市居民的日常出行，阻礙了災害天氣下城市的正常運作。近年來，雖然政府加強城市排水系統(tǒng)的建設與優(yōu)化[3-4]，但是由于城市環(huán)境極其復雜，城市積水問題在全國各個城市尚未解決。城市積水如果未被及時發(fā)現并處理，就有可能損害城市排水系統(tǒng)，導致城市內澇甚至發(fā)生城市洪澇災害。因此，為了保障城市居民的日常出行不受影響，和維護災害天氣下城市的正常運作，及時發(fā)現城市何處積水尤為關鍵。

以往的城市積水監(jiān)測多是通過攝像頭觀測、人為反饋等方式，這種方式耗時耗力、覆蓋范圍小，且在災害天氣下風險性較高，又容易失效。但隨著傳感器、無線通訊技術的發(fā)展以及移動設備的普及，出現了一種新型的數據采集模型——群智感知[5]，可通過大量移動節(jié)點來收集數據并上傳，在感知平臺分析后得到大范圍的城市數據。群智感知因其成本低、部署靈活等優(yōu)勢，在空氣質量推測[6-7]、公共事件信息收集[7]等方面有了重要應用。但是在現實應用過程中，由于移動節(jié)點時空分布不均、設備故障等原因，移動節(jié)點可能會無法正常上傳數據，導致一些區(qū)域無法準確收集到信息。因此，如何通過已感知到的數據來推測出缺失的數據，是一個有價值且需要深入探討的問題。

目前城市積水問題的相關研究大多是基于災害天氣下進行的，而缺少針對非災害天氣下的城市積水推測。然而，非災害天氣下的城市積水推測與災害性天氣下的城市積水推測有較大差異。本文基于深圳市真實積水數據在不同天氣情況下的分析，并且考慮到目前城市都已經具備一定的排澇能力，且在非災害天氣下降雨量較低、日曬促使城市積水自然蒸發(fā)等因素，認為非災害天氣下城市積水的發(fā)生概率較低，可視為異常事件處理。而在災害天氣下，城市積水發(fā)生概率較高。

為了研究非災害性天氣下的積水推測問題，本文考慮了降雨以及歷史積水狀態(tài)，對積水監(jiān)測站點的積水狀態(tài)進行推測，同時為了進一步提高積水推測的準確度，引入了啟發(fā)式策略選擇公交車軌跡。本文的主要工作可以概括為：

1)闡述了在非災害天氣下的城市積水推測問題，并提出了一種結合選擇感知軌跡來實現城市積水推測的方式；

2)通過歷史積水數據，根據滑動雨量以及歷史積水狀態(tài)，采用孤立森林方法推測城市各個積水監(jiān)測站點的積水狀態(tài)；

3)采用了兩種軌跡選擇方式：隨機選擇和貪心選擇。在貪心選擇中，本文優(yōu)先選擇經過剩余積水監(jiān)測站點數量最多的軌跡。為了進一步提升推測精度，根據軌跡得到的真實記錄對孤立森林的推測結果進行修正。并在選擇軌跡后，根據軌跡得到的真實記錄使用壓縮感知實現積水推測；

4)為了驗證本文提出算法的有效性，采用了深圳市水務局積澇點水位數據、深圳市滑動雨量數據、深圳市公交線路軌跡數據進行驗證。實驗結果表明：與孤立森林算法來推測城市各處積水狀態(tài)相比，結合群智感知思想，選取公交車感知軌跡生成感知數據的方法能進一步提升推測準確度。

1 相關工作

隨著更多的城市積水相關數據被采集利用，城市積水問題的研究也越來越豐富。徐藝揚等[8]基于歷史數據及GIS空間分析，綜合研究了上海市的降雨、城市建設用地擴張、人口集聚分布、城市數字高程、基礎設施排水能力等因素對中心城區(qū)暴雨內澇發(fā)生的影響。Chen等[9]提出了一種低成本、實時的雷達方法，利用大規(guī)模的車輛軌跡數據和異構的道路環(huán)境感知數據來識別涵蓋了城市積水的道路障礙物。王慧軍等[10]提出了一種基于城市區(qū)域網格劃分的暴雨積水預警模型，采用了一種非結構化的網格劃分方法來建立城市積水預警模型。魏軍等[11]利用石家莊市高精度城市地理信息等基礎數據，將城市河網、路網、管網和社區(qū)的計算網格分層劃分，形成分區(qū)、分層和立體多重的內澇計算模式,構建了石家莊市暴雨內澇數學模型。

近年來孤立森林在異常監(jiān)測領域應用廣泛，Yao等[12]基于孤立森林的思想提出了一種新的異常檢測算法dForest(分布森林)。該方法將孤立森林中隨機生成的子樹改進為建立一組特殊的二叉樹，稱為分發(fā)樹。Puggini等[13]將孤立森林結合一種降維變量選擇方法應用于檢測發(fā)射光譜數據的異常檢測系統(tǒng)。Hou等[14]結合了Hadoop分布式存儲系統(tǒng)與孤立森林，將檢測模型構建和異常評價過程并行化，提高了檢測效率，擴大了應用范圍。

2 問題定義

為了更好地定義面向積水推測的機會式感知軌跡選擇問題，本文預先定義了一些符號。位置集合P={p1,p2,…,pk}，其中pk代表第k個網格的位置。時間集合D={d1,d2,…,di}，H={h1,h2,…,hj,…,h24}，dihj表示第i天的第j小時。公交車集合C={c1,c2,…,cq}，公交車線路軌跡集合M={m1,m2,…,mq}，mq為公交車q的軌跡，是由若干個位置組成的集合，mq?P。所選公交車感知到的若干個位置的積水數據Z={z1,z2,…,zq}。

每小時各個位置都存在三種數據狀態(tài)：感知結果為1，有積水；感知結果為0，無積水；感知結果為-1，即未被感知。公交車每小時都經過若干個位置，即公交車軌跡，下一小時也按相同順序經過同樣的位置。不同的公交車的軌跡不一樣，位置序列的長度也可能不一樣。同一輛公交車在不同小時的軌跡是一樣的。公交車在每小時開始發(fā)車時，決定是否開啟其感知設備參與感知任務。如果開啟，則該公交車該小時內經過的每一個有積水監(jiān)測站點的位置都被感知，返回結果1或0。如果未打開，則即使經過，位置仍然未被感知。本文實驗基于以下假設進行：各積水監(jiān)測站點的積水狀態(tài)在一小時內不會改變；公交車一小時內能經過該公交車線路上的所有位置；若公交車開啟感知設備，則只要經過積水監(jiān)測站點，所在網格就能采集到該積水監(jiān)測站點的積水狀態(tài)。由于F1score同時兼顧了分類模型的精確率和召回率，是模型精確率和召回率的調和平均，且最大值為1，最小值為0，因此本文采用F1score作為模型性能的度量。

F1score=2·(precision·recall)/(precision+recall)。

問題：在dihj開始時，給定公交車集合C，公交車線路軌跡集合M，在一定預算下選取N輛公交車來參與感知任務，得到感知數據Z，目標是在dihj結束時，根據dihj數據及歷史數據推測dihj所有未被感知位置的積水狀態(tài)，并根據感知數據Z提升推測準確度。

3 方法

3.1 積水推測

本文采用了孤立森林算法和壓縮感知作為推測積水的方法。孤立森林多應用于連續(xù)數據的無監(jiān)督異常檢測，與其他異常檢測算法不同的是，孤立森林將異常點孤立出來而不是描寫刻畫正常點。孤立森林由多棵孤立樹構成，孤立樹是一種隨機二叉樹，且孤立樹除了葉子節(jié)點外的所有節(jié)點都是有兩個孩子的內部節(jié)點[15]。孤立樹由以下算法構成。

算法1iTree(U,e,l)。

輸入：U為輸入數據，e為樹當前高度，l為樹限制高度。

輸出：一棵孤立樹。

步驟1 從U中隨機選取一個子集u′作為構建孤立樹的訓練集。

步驟2 在所有特征中選取一個特征作為孤立樹的根節(jié)點，再從該特征的取值范圍中隨機選取一個值。

步驟3 根據選出的值對u′中的所有數據進行分類，將小于該值的數據放入左子節(jié)點，大于等于該值的數據放入右子節(jié)點。

步驟4 遞歸執(zhí)行步驟2、3，直到構成的節(jié)點都為葉子節(jié)點或者達到限制的樹深度，又或者節(jié)點上所有數據的特征值都是相等的。

步驟5 返回構建的孤立樹。

孤立樹檢測異常的依據為：異常的樣本需要被劃分的次數較正常樣本來說比較少，即異常樣本能夠更快地被劃分到葉子節(jié)點，路徑較短；特征具有可區(qū)別(如極值)的樣本在分割過程中更容易被劃分。

在構建完t棵孤立樹后，讓每個樣本點xi遍歷所有孤立樹，可以計算得到在森林中的平均高度h(xi)，對所有樣本點的平均高度進行歸一化處理。異常值分數s的計算公式為

s(x,k)=2-E(h(x))/c(k)，c(k)=2H(k-1)-2(k-1)/k。

其中：E(h(x))是孤立森林的路徑長度h(x)的均值；H(k)=lnk+γ，γ是歐拉常數。

可以看出當E(h(x))趨近于0時，異常分數s越趨近于1，則樣本被判定為異常。當E(h(x))趨近于n-1時，異常分數s越趨近于0，則樣本被判定為正常。

非災害天氣下的城市積水問題可視為異常檢測問題進行處理，本文通過構建積水監(jiān)測站點的滑動雨量、dihj-1時刻的積水狀態(tài)、dihj-2至dihj-24各個時刻的積水狀態(tài)這25個特征。將148個積水監(jiān)測站點，在dihj時刻之前的積水數據作為訓練集訓練孤立森林，將dihj時刻所有站點的積水數據作為測試集，推測結果由孤立森林給出的異常值分數來確定。本文分別嘗試選擇1至10條軌跡，將對應生成的感知數據加入訓練集，但是模型的效果相較于未加入感知數據的模型更差，所以最終未將感知數據加入訓練集。

3.2 壓縮感知

壓縮感知[16]在恢復稀疏的時空數據中具有廣泛的應用。根據對2019年深圳市真實積水數據的分析，91.2%記錄的積水狀態(tài)為無積水，且存在部分時刻所有站點的積水狀態(tài)與相鄰時刻相同，因此依據積水數據構建出的真實矩陣可視為低秩矩陣，可通過壓縮感知進行壓縮和重構。但也由于非災害天氣下的城市積水發(fā)生較少，可能出現感知到的位置積水狀態(tài)都為無積水，即收集矩陣為零矩陣，在這種情況下壓縮感知效果會比較差。壓縮感知的具體步驟如下。

進一步可以轉化為

算法2Greedy(W,N)。

輸入：W為各軌跡經過含積水監(jiān)測站點的網格編號集，N為選擇的軌跡條數。

輸出：選擇的軌跡集T。

步驟1 初始化各軌跡經過含積水監(jiān)測站點的網格數量集K，W包含Len條軌跡。

步驟2 找到經過含積水監(jiān)測站點的網格數量最多的軌跡t。

步驟3 將該條軌跡加入T。

步驟4 刪除集合W中包含軌跡t經過的網格；更新K。

步驟5 循環(huán)執(zhí)行步驟2～4N次，返回選擇的軌跡集T。

3.3 軌跡選擇

考慮到選擇公交軌跡參與感知任務生成感知數據需要花費成本，因此在一定成本的限制下，為了提升選擇的軌跡對積水推測的效果，本文希望選擇的軌跡能夠覆蓋更多的積水監(jiān)測站點，以提供更充足的真實數據，結合孤立森林算法、壓縮感知算法，提升積水推測的準確度。在感知軌跡選擇階段，本文采用了隨機選擇和貪心選擇兩種方式。具體來說，在數據預處理階段，我們將公交線路軌跡及積水監(jiān)測站點等數據都映射至網格，并算出各條軌跡經過的積水監(jiān)測站點的數量；在通過貪心選擇算法選擇感知軌跡時，本文優(yōu)先選擇經過含積水監(jiān)測站點的網格數量最多的軌跡。

4 實驗

4.1 數據集描述

本文實驗數據來自深圳市政府數據開放平臺及深圳市氣象局。深圳市水務局積澇點水位原始數據字段包含水位編號、測站編碼、時間、水位；深圳市水務局積澇點水位數據共1 332 577條記錄，時間為2019年1月1日06:00到2020年2月22日16:00。深圳市水務局積澇點測站數據原始數據字段包含測站編碼、測站名稱、站點經度、站點維度；深圳市水務局積澇點測站數據共有170條記錄，即有170個積水監(jiān)測站點，站點的經緯度區(qū)間分別為[113.778 554,114.578 076]、[22.477 575,22.806 801]。深圳市公交線路軌跡數據原始數據字段包含記錄編號、創(chuàng)建時間、修改時間、緯度、軌跡編號、經度、組成順序；深圳市公交線路軌跡數據共有3 634條軌跡，4 057 364條記錄。由于深圳市滑動雨量數據為手動爬取，該數據集由時間為行、滑動雨量監(jiān)測站點ID為列的矩陣構成。深圳市滑動雨量監(jiān)測站點數據字段包含站點編號、站點名稱、區(qū)域編號、區(qū)域名稱、站點經度、站點緯度、站點高度、站點地址；深圳市滑動雨量監(jiān)測站點數據共205個降雨監(jiān)測站點，共8 450條記錄，經緯度區(qū)間分別為[113.767,115.129 021]、[22.4,22.97]。時間為2019年5月8日00:00到2020年5月31日23:00。

4.2 實驗數據預處理

本文選取了時間區(qū)間為2019年5月8日00：00到2020年5月31日23：00的數據進行實驗，并刪除了該時間區(qū)間內18個無數據或數據缺失過多的積水監(jiān)測站點數據。首先，由于深圳市水務局積澇點水位數據、深圳市滑動雨量數據都有一定程度的缺失，所以本文首先通過線性插值對數據集進行補全。線性插值通過一條穿過已知兩點的直線來近似表示原函數，因此給定兩點(xi,yi)，(xi+1,yi+1)，x在這兩點之間，y(x)的計算公式為

y(x)=yi+((yi+1-yi)/(xi+1-xi))*(x-xi)，

在通過線性插值補全后，深圳市水務局積澇點水位數據、深圳市滑動雨量數據中所有站點在任意時隙dihj都有對應數據。其次，由于深圳市水務局積澇點水位數據中各站點的記錄頻率不定，且本文實驗基于各積水監(jiān)測站點的積水狀態(tài)在一小時內不變的假設下實現。所以進行以下處理：以一小時作為一個時段，若站點在單個時段內有多條記錄，則保留記錄時間最晚的真實積水數值作為該時段的積水狀態(tài)；若單個時段內只有一條記錄，則該記錄的積水數值為該時段的積水狀態(tài)。如表1所示，由于5:00至6:00時段內有5:57、6:00時刻的記錄，且兩條記錄都為真實值，所以僅保留6:00記錄。6:00至7:00時段內有6:07、6:17、6:27、6:32、7:00這5條記錄，且7:00時刻的記錄值是線性插值得到的估計值，6:32時刻為該時段內記錄時間最晚的真實記錄，因此將6:32時刻的積水數值賦值給7:00時刻，然后刪除7:00時刻以外的記錄。7:00至8:00時段、8:00至9:00時段內都僅有一條記錄，因此該條記錄即為該時段的積水狀態(tài)。接而，由于本文研究非災害天氣下的城市何處積水問題，所以將積水數據數值化為0、1，即0代表該站點的積水狀態(tài)為無積水，1代表該站點的積水狀態(tài)為有積水。

表1 2019年5月27日5時至9時積水監(jiān)測站點48積水記錄Table 1 Water accumulation records of 48 water accumulation monitoring sites from 5 to 9 on May 27,2019

同時，本文對經緯度分別在[113.778 554,114.578 076]、[22.477 575，22.806 801]的深圳市區(qū)域進行劃分，將該區(qū)域劃分為3 200個網格，每個網格大小為1 km *1 km。將積水監(jiān)測站點根據經緯度映射至網格中。同一網格中有多個站點時，保留出現積水次數較多的站點。經過這一步的處理，共有148個網格中有積水監(jiān)測站點被保留。接著，將滑動雨量監(jiān)測站點根據經緯度映射至網格。當積水監(jiān)測站點所在網格有滑動雨量監(jiān)測站點時，將同網格滑動雨量監(jiān)測站點的滑動雨量作為該積水監(jiān)測站點的滑動雨量。對沒有同網格滑動雨量監(jiān)測站點與之匹配的積水監(jiān)測站點，本文考慮到降雨的區(qū)域性，將與積水監(jiān)測站點距離不超過3.5 km且相距最近的滑動雨量監(jiān)測站點的滑動雨量作為該積水監(jiān)測站點的滑動雨量。最后將由若干個經緯度點組成的公交線路軌跡也映射至網格。

4.3 實驗結果及分析

4.3.1孤立森林 本文為了驗證所提算法的有效性，分析了孤立森林、孤立森林結合隨機選擇、孤立森林結合貪心選擇實現積水推測的實驗結果。圖1展示了三種方法的實驗結果，其中橫坐標為0處對應孤立森林實現積水推測，其余部分對應兩種軌跡選擇方式與孤立森林結合實現積水推測。從圖1中箱形圖部分可以看出，孤立森林實現推測的三種方式的所有結果的上四分位數、上限都為重合且數值為1.0；隨著貪心選擇軌跡條數的增多，下限逐步提高，異常點個數逐步減少，且異常點減少的個數明顯優(yōu)于隨機選擇；圖1折線部分是對2019年5月9日至31日內每小時分別進行積水推測得到的F1score取均值的結果。從圖1中折線部分可以得到，不論是結合隨機選擇或貪心選擇實現積水推測的結果都優(yōu)于單獨使用孤立森林。隨著選擇軌跡條數的增多，推測的F1score也隨之提高，且貪心選擇對應的F1score的提升程度大于隨機選擇。綜上所述，孤立森林結合隨機選擇、孤立森林結合貪心選擇實現積水推測的效果優(yōu)于單獨使用孤立森林，且隨著選擇軌跡條數的增多，貪心選擇相較于隨機選擇更能提升積水推測的準確度。

圖1 孤立森林結合不同選擇方式實現積水推測Figure 1 Isolation forest combined with different options to realize urban ponding water estimation

4.3.2壓縮感知 本文為了驗證所提算法的有效性，分析了壓縮感知結合隨機選擇、壓縮感知結合貪心選擇進行實驗。圖2展示了兩種方法的實驗結果。從圖2箱形圖部分可以看出，貪心選擇2條軌跡對應的箱形圖的上四分位數、下四分位數、中位數、上限、下限都重合。隨著選擇軌跡條數的增多，貪心選擇對應的箱型圖的上限不斷提升。圖2折線部分是對2019年5月9日至31日內每小時分別進行積水推測得到的F1score取均值的結果，可以看出，隨著選擇軌跡條數的增多，貪心選擇和隨機選擇的F1score不斷提升，且貪心選擇的F1score提升效果優(yōu)于隨機選擇。貪心選擇4條軌跡的F1score明顯高于貪心選擇2條時，但在選擇條數繼續(xù)增多時，F1score提升不明顯，根據結果及數據分析，是由于在選擇軌跡條數增多時，由于未覆蓋的站點越來越少，貪心選擇的軌跡覆蓋的站點數也在減少，因此導致提升不明顯。綜上所述，基于壓縮感知實現積水推測時，貪心選擇對推測準確度的提升效果優(yōu)于隨機選擇，且隨著選擇軌跡條數的增多，準確度也隨之提升。

圖2 壓縮感知結合不同選擇方式實現積水推測Figure 2 Compressed sensing combined with different options to realize urban ponding water estimation

5 總結

本文通過網格化深圳市部分區(qū)域，并將積水監(jiān)測站點、滑動雨量監(jiān)測站點映射至網格來融合深圳市滑動雨量數據、深圳市水務局積澇水位數據。使用孤立森林算法，對深圳市148個積水監(jiān)測站點從2019年5月9日至31日每小時的積水狀態(tài)進行預推測。最后，結合群智感知思想選取公交車感知軌跡生成感知數據，以此提升了推測準確度。本文采用F1score作為模型的評價指標，實驗結果表明通過孤立森林算法推測城市積水是可行的，而貪心選擇公交車感知軌跡生成感知數據能夠提升推測準確度，且效果優(yōu)于隨機選擇。

在將來的工作中，本文計劃加入數字高程模型、不透水地面指數等特征來優(yōu)化模型。同時，也計劃在感知軌跡選擇階段采用主動學習方法，推測階段考慮用深度學習[17]的方法提升選擇軌跡生成的感知數據對推測準確度的作用。