有限感知條件下的停車數據批量式修復研究①

張華成，鄒 萬，劉建明，鐘曉雄，楊 兵

(桂林電子科技大學 計算機與信息完全學院，桂林 541004)

1 引言

伴隨著汽車保有量的迅速增加，停車難問題已成為無法忽視的城市通病，因停車問題引發的糾紛屢見不鮮.無論是超大型城市，還是特大城市，甚至只有幾十萬、十幾萬人口的中小型城市，車輛迫切的停車需求與可用停車位不充足的矛盾都日益突出.因此，如何對城市中有停車需求的車輛進行宏觀的停車誘導，成為地方政府面臨的一大難題.為解決這個問題，降低停車時間成和經濟成本，智能停車系統[1]是最有效的辦法之一.而城市中所有停車場當前可用停車位都已知是智能停車系統能正常運行的前提.目前停車數據主要通過傳感器采集和與停車場直接合作的方式獲得，但因為停車場類型、產權的多樣性、經濟成本及安裝施工等原因的限制導致大范圍的停車場數據處于缺失狀態.其次，不同停車場以及不同轄區的系統以往都是獨立運行，必然存在數據兼容問題，而且由于缺乏統一標準，也不能實現數據共享，多種原因導致難以將所有停車數據加入到大系統中形成規模.因此，城市中相同數據形式的停車數據往往是非充分的[2].

考慮到直接獲得充分的停車場數據有足夠的挑戰性，本文希望在經濟時間成本可控范圍內對缺失數據的停車場進行數據修復.停車數據受時空兩個維度的綜合影響，不同停車場間的數據可能差異極大，如果直接將數據特征明顯不同的停車數據當成一個樣本集進行學習訓練，會得到無法解釋的生成數據.針對這個問題，本文使用K-means 聚類的方法按空間特征相似性將停車場劃分為多個簇，對每個簇單獨進行數據修補.通過可獲得的停車場公開數據量化各個停車場的影響力，對影響力高的停車場安裝傳感器以獲得真實數據，在此基礎上修復其余停車場的停車數據.因為不同地理位置、規模、收費標準等多種狀況對停車場的影響，不能簡單的用一般插值法的方式修復.因此本文采用數據增強技術，也就是通俗意義上的數據生成/修補技術.通過這種方法，能在有限感知條件下下獲取大量高仿真的停車數據.

2 相關工作

本文的停車數據為時序數據，目前時序數據修補領域的研究主要是一些插值法[3]，主要為3 類，基于拉格朗日插值法的數據修補方法、基于牛頓插值法的數據修補方法、基于分段線性插值法的數據修補方法[4]，其中基于分段線性插值法的數據修補方法效果較好.上述方法的特點是需要一定的先驗知識，常常被用于有一定歷史數據的修補領域中，然而由于經濟成本、安裝施工、經濟產權等原因，多數停車場歷史數據難以獲得，因此是用插值法在對停車場數據修補時會有較大局限性.

在機器學習中，處理數據缺失問題一般采用數據增強技術，也就是傳統意義上的數據生成或數據修復技術.數據生成目前已成為機器學習領域的研究熱點，其中優秀的生成模型有生成對抗網絡(Generative Adversarial Nets，GAN)[5]，該模型由一個生成網絡和判別網絡組成，在每一次迭代中，判別器的目的是區分真實數據和生成數據，而生成器則期望生成以假亂真的數據，在零和博弈的思想下，最終達到一個兩者都可接收的結果.由于GAN 在時序數據中訓練起來非常不穩定，因此直接使用GAN 可能會生成無意義的數據.目前一種高效的的生成方式是將在時序數據表現良好的LSTM 網絡與GAN 結合得到的循環生成式對抗網絡(Recurrent Generative Adversarial Networks，RGAN)[6]，該方法雖然能快速生成時序數據，但缺點是生成結果伴有明顯的抖動和相位差，針對生成數據震動較大這個不足，本文的解決思路是將時間序列升維，使用在二維數據有強大特征提取能力的深度卷積對抗生成網絡(Deep Convolution Generative Adversarial Networks，DCGAN)[7]提高生成數據的穩定性，實驗表明該方法使生成結果更加穩定，抖動減少.

3 系統模型

3.1 模型搭建

本文的停車數據指的是關于停車場的空車位的時間序列，考慮到不同停車場同一時刻可用停車位數量差異較大引起的數據難以訓練問題，本文將空車位的時間序列除以停車場的規模，轉換成空車率的時間序列.對于區域O中的n個停車場，表示為P={p1,p2,···,pi,···|i=1,2,···,n}則 停車場pi的空車率數據可表示為U=s為時間序列的長度.實驗將樣本點的停車數據作為訓練集，使用改進后的DCGAN 模型生成其余停車場的停車數據.改進后的生成器如圖1所示.

圖1 改進后的DCGAN 生成模型

圖1(a)描述的是，將100 維均勻分布的z投影到一個具有多個特征圖的小空間范圍的卷積中表示，用一系列步長為4 的卷積將這種高維的表示方式轉換為64×64 像素的圖像，注意不適用全連接層和池化層.另外，在生成器中引入正態性檢驗的過濾器，用來保證生成的曲線效果可以接受，如圖1(b)所示.其中，正態性過濾器使用的算法為D’Agostino-Pearson 檢驗，該方法是一種對分布的偏度和峰度進行綜合評定的方法[8].D值的公式如下：

在式(1)中，n為樣本總數，ri為停車場pi的的停車數據.得到D值后，通過D界值表確定P′的值，按照P′值判斷這組樣本是否符合正太性分布.如果P′小于設定的閾值?，則這組生成樣本不符合正態性檢驗，反之符合正態性檢驗，并保留這組生成樣本.

3.2 停車場的高維聚類

不同停車場的停車數據差異較大，這是因為停車場不可能單獨存在于地理空間中，一定會受周圍空間信息的影響，地理空間信息其實也就是地理興趣點(Point Of Interest，POI)，包括住宅、商場、學校、公交站等，不同POI 對停車場有不同的影響.比如某景區附近的停車場，其停車位在節假日使用率明顯高過工作日；住宅區附近的停車場車位占用率在下班時段明顯高于上班時段；商場周圍停車場的車位使用率在周末顯著上升.換句話說，附近空間信息相似的兩停車場其數據一定具有相似性，如圖2所示.

圖2 停車場間的拓撲關系

可以看到兩對停車場停車數據差異明顯；而對于兩對中的任何一對，對內停車數據卻很接近.因此本文根據停車場的各POI 數量，對每個停車場轉成高維向量的形式，通過對停車場高維向量的聚類實現將停車場按數據差異分類的目的.

以停車場為圓心、Rt為容忍度半徑的圓用Op表示.圓內的POI 會對停車場產生影響，圓外的POI 對停車場的影響不考慮.假設在區域Ω 內有n個停車場，如果城市中主要的POI 有h種，那么，對于任意一個停車場pi統計Rt內h種主要POI 的數量可構建一個h維的向量作其特征向量，記為vi，表示為用來表示停車場受地理空間的影響.考慮到停車場的經緯度也會對停車數據產生影響，將停車場pi的經緯度信息用一個2 維向量，記為μi.對于停車場pi的地理空間信息用(2+h)維向量esi=(ui,vi)唯一標定，則n個停車場的高維向量記為ES={es1,es2,···,esi,···|i=1,2,···,n}.基于K-means 的聚類算法更適合對高維向量進行聚類，在本文中，將對停車場高維聚類的公式為：

其中，C={C1,C2,···Cj,···|j=1,2,···,k}為聚類產生的k個簇，mj為簇Cj的質心，E為成簇Cj內樣本與簇均值向量mj的靠近程度，a0是經緯度2 維向量和POI 高維向量的權重.

3.3 一種停車場影響力評價算法

區域內的停車場間相互影響，具體表現為影響力越強的停車場吸引車輛停車的能力越強，當一個影響力強的停車場因為無空閑停車位而無法繼續停車時，車輛會向周圍影響力較弱的停車場進行疏散.換句話說，在一個區域內某個停車場的影響力越強的，則這個停車場越能代表這個區域的停車場.因此，如果對停車場按影響力進行排序，那么只要知道影響力較高的停車場的停車數據，就可以通過某種方式對其余停車場的數據進行修復.本節的目的是篩選出影響力較強的停車場.

基于一般的認知標準，與周圍其它停車場連通度越高的停車場往往表現出更高的影響力，因為人們更傾向于前往停車場較密集的區域，這樣會增加停車的成功率，當一個停車場由于某種原因無法停車時，可以輕松的向與之連通的停車場疏散.此外，相鄰停車場也會互相影響，具體表現在一個區域內影響力最強的停車場附近停車場評分會稍低，但明顯高于更遠處的停車場(類似于地理上的等高線).因此，實驗需要將停車場的拓撲關系用數學方式描述.假設有6 個停車場，它們的拓撲關系可用無向圖表示，如圖3所示.

圖3 停車場間的拓撲關系

對于圖3中任意兩個停車場pi和pj，如果存在連通關系，那么它們間的距離設為dij.上圖中的拓撲關系也可用矩陣的形式表示：

考慮到距離的數值差異較大難以計算，將pi和pj距離dij換成pi和pj的連通度，并做歸一化處理，用sij表示pi和pj的轉移概率，則新的矩陣也就是概率轉移矩陣如下：

一個連通度很高的停車場會存在多種無法停車的情況，比如私有停車場、收費過高的停車場.因此，除了考慮停車場的連通度之外，還需量化停車場的靜態信息.

根據我國相關的法律法規，任何一個合法經營的停車場都必須以公示牌的形式公開的展示該停車場的類型、收費標準、規模等信息，這些信息一定程度上代表了停車場相對于其它停車場的影響力.不難發現，不同的信息有著不同的深層含義，具體如下：

(1) 停車場類型：主要分為4 種，住宅、辦公、政府、商場.其中，住宅類型和政府類型的停車場開放程度最低，外來車輛很難進入，商場類型停車場開放程度最高.用1≥x≥0 來表示不同類型停車場的開放程度，當x=0 時不對外開放.

(2) 收費標準：不同收入階層能接受的收費區間不同，低收費的停車場能被大多數收入階層的人接受，而收費較高的停車場只吸引高收入階層的人.因此，收費標準可以表示停車場的受歡迎程度，用y≥0 表示停車場的收費標準，當y=0 時，停車場最受歡迎.

(3) 停車場規模：停車場的規?？梢员硎就＼噲龅姆漳芰?，顯然，規模越大的停車場無疑影響力越強，用z＞0 表示停車場的服務能力

通過式(5)來量化靜態信息對停車場影響力的影響，也就是對其評分[2]：

其中，SV表示停車場的評分值.i為停車場pi的編號，zi/||z||和yi/||y||的目的是對收費標準和停車場規模歸一化處理.用SV={SV1，SV2，…，SVi，…|i=1，2，…，n}表示區域O中的n個停車場的評分向量.

考慮到停車場的靜態信息和拓撲關系都對停車場的影響力有顯著影響，因此如何合理的統籌這兩部分，成為必須要解決的問題.本文的方法是在已知概率轉移矩陣M′的條件下，求解平穩狀態下向量SV的值，可表示為SV=M′.SV，顯然，SV是循環定義的，所以引入著名的冪迭代法求解平穩狀態下向量SV.將式(1)得到的評分向量作為初始評分向量SV0，與轉移概率矩陣M’作為冪迭代法的輸入，多次迭代不斷修正評分值SV，直到SVi和SVi+1的差值小于一個閾值θ時，迭代終止，并取SVi作為最終的評分向量.迭代公式如下：

實驗選取影響力較大的部分停車場為樣本點，來修復其余停車場的停車數據.由于停車數據受到人類社會的活動的影響，一定程度上停車數據是滿足正態分布的，可用式(1)中的D值檢驗證真實停車數據是否存在正態性，當數據存在明顯正態性時，則可根據二八定律[9]，也就是影響力最大的前20%的停車場基本包括該簇停車場全部的特征，停車數據因受多種復雜因素的影響，在服從同一分布的前提下必然含有一定的多樣性.一般數學方法生成的同分布數據極為相似，不滿足停車數據的特點，而這正是GAN 的優勢所在，因此本文基于GAN 的思想學習樣本數據分布并生成新的停車數據.與傳統大量部署傳感器獲得數據的方式相比，顯著降低了時間和經濟成本.

3.4 修復缺失停車數據

考慮到直接使用一維時間序列生成同簇數據時，其結果難免伴隨有明顯抖動[6].為了使生成數據的效果更平滑，需要對一維時間序列升維.本文解決方式是將其轉為二維曲線，并以圖像方式保存，如圖4所示.

圖4 一條真實的空車率曲線

將篩選出的二維曲線集做為學習樣本，采用基于圖1的DCGAN 模型中訓練.一條生成曲線如圖5所示.

圖5 一條生成的空車率曲線

從圖5可以看到，生成圖像伴隨有明顯的噪聲，因此需要對生成數據進行降噪處理.本文試驗中對生成圖像的處理包括如下3 步.

第一步，需要把產生的圖片灰度化.即將灰度化之前的RGB 值分別設為R1、G1和B1，相應的，灰度化后的值設為R2、G2和B2.用公式表示為：

第二步，將灰度化的做二值化處理.二值化處理方法為設定一個閾值γ，遍歷矩陣中每一個數值，如果該數值大于γ則設為255，若像素點值小于該閾值則設為0.

第三步，將異常值處理.下一節將提到.

3.5 異常值處理

圖5中異常值分為兩類，在曲線峰值處像素點過于密集，稱為毛刺點；在曲線外零星的像素點，稱為離群點.

對于毛刺點，實驗采用均值濾波的方法[10]，降低毛刺點處像素點的密度.均值濾波的公式如下所示.

其中，t代表時間軸和r為空車率；W表示濾波窗口，大小取默認的3×3；表示遍歷原圖像所有像素點；最后f′(t,r)表示濾波之后的新圖像.

對于離群點，實驗采用局部異常因子LOF 算法(Local Outlier Factor)[11]來尋找.思想是通過比較每個點q和其鄰域點的密度來判斷該點是否為離群點.設Nq(k) 表示以q為圓心，dk(q) 為半徑的圓，其中dk(q)為點q到第k遠點的距離.實驗中選k為3.尋找離群點用到的公式如下：

式(9)中，distk(q，o)表示可達距離，d(q，o)表示點q到點o的距離.當點o在Nq(k)圓內，則distk(q，o)等于dk(q)，當點o在圓Nq(k) 外，則distk(q，o) 等于d(q，o).

式(10)定義了局部可達密度lrdk(q)，可以理解為一個密度，密度越高，則認為越可能屬于同一簇，反之，越可能是離群點.其中|Nk(q)|描述的是q為圓心，鄰域為dk(o)點的個數.

因為密度的閾值難以選定，實驗引入局部離群因子來判定每個點q是否為離群點，如式(11)所示.其中，LOFk(q)描述的是點q在圓Nq(k)的局部可達密度lrdk(q)與點q的局部可達密度之比的平均數.如果這個比值越接近1，說明點q的鄰域點密度越接近，q和鄰域同屬一簇；如果這個比值越小于1，說明q的密度高于其鄰域點密度，q為正常點；如果這個比值越大于1，說明q的密度小于其鄰域點密度，q越可能是離群點.

4 仿真實驗

本實驗的目的是在有限感知的前提下，獲得足夠多的停車數據，為基于機器學習的停車誘導系統提供充足的數據支撐.目標區域停車場的靜態信息，通過百度地圖拓展包BMap 得到.本文的思路是篩選出樣本點，通過對樣本點安裝傳感器可以得到實時停車數據，基于這些樣本點來修復剩余的實時停車數據，達到實驗目的.而現實情況是沒有條件安裝這些傳感器，因此選擇已知2017年6月停車數據的深圳市羅湖區的392 個停車場來進行仿真實驗(實驗收據為采購獲得)，最后將修復的數據與測試數據對比來篩選出合理的生成數據.

4.1 樣本停車場的篩選

目標區域主要POI 分布如圖6所示.

圖6 深圳市羅湖區主要POI 分布

考慮到空間信息差異大的停車場間停車數據同樣差異過大，在篩選樣本停車場前需要將停車場進行聚類.實驗中，為方便計算，取容忍度Rt為310 米，在地圖中恰好約等于1′，對每個停車場統計其半徑310 米方位內POI 的7 維向量.結合其位置得到9 維向量.部分停車場的9 維向量如表1所示.

對392 個停車場進行高維聚類，結果如圖7所示.

表1 部分停車場的9 維向量

圖7 對停車場的聚類結果

可以看到停車場數量最多的簇為‘type0’，因此仿真實驗選取簇‘type0’的150 個停車場進行后續實驗.

‘type0’的150 個的停車曲線和正態性檢驗結果如圖8和表2所示.從圖8可以看到，有3 條數據明顯異常的噪聲數據，做剔除處理.對其余147 條數據在8928 個時刻檢驗使用式(1)其正態性，設閾值?為0.05.結果如表2所示.不滿足正態性的組數不足25%，可以認為整體是符合正態性的，因此停車數據適用于二八定律.

圖8 簇“type0”停車場的空車率數據

表2 樣本數據的正態性檢驗

第二步對150 個停車場進行編號，根據式(3)-式(6)及停車場間的空間拓撲關系，計算所有停車場的評分，并排序.如表3所示.

取θ為0.01，當迭代次數達到105 時，評分值趨于穩定，并全部保存.可以看到序號為74 和73 的停車場存在約等于，而最終的卻遠遠大于的情況.導致這種情況的原因是兩停車場的拓撲關系也就是連通度差異較大.具體來說，序號為74 的停車場與周圍停車場的連通度遠遠大于序號為73 的停車場，當車輛在74 號或73 號停車場無法停車時，處于74 號停車場的車輛更容易疏散到附近停車場.序號為39 和74 的停車場，存在和差異較大，而和卻比較接近，這還是由連通度差異較大導致的.74 號停車場連通度大于39 號停車場，一定程度上彌補了74 號停車場先天條件的不足.評分結果符合 公眾認知，可被接受.

表3 停車場評分的迭代過程

4.2 數據生成和處理

在深圳市羅湖區，對應簇‘type0’中147 個有數據的停車場，篩選出30 個樣本點，在此基礎上修復其余停車場的停車數據.實驗以2017年6月整月為時間跨度，每5 分鐘為時間間隔，可劃分出8928 個時間節點，并繪制空車率線圖像.一條真實的停車曲線如圖4所示.

使用DCGAN 為生成模型，設置隱層神經元為600個，批處理大小為1，學習率為0.004.在生成過程中，每一次迭代生成器都會學習樣本點在2017年6月的空車率數據，并盡可能生成與樣本點相似的數據.由于在DCGAN 生成模型中加了正態性檢驗過濾器，所以生成的數據一定是符合正態性的.DCGAN 的生成過程如圖9所示.

從圖9中可以看到隨著迭代次數的增加，生成圖像從模糊逐漸變得清晰，實驗取第800 次迭代的結果.圖5為最終得到的一條生成結果，從中可以看到生成的數據存在較多的噪聲，需要進行降噪處理.降噪的第一步是要進行灰度化處理，灰度化公式中的系數如表4所示.

具體二值化的做法是從圖5左上角遍歷每一個數值點，設定閾值γ為140，當像素點的像素值大于該閾值將該值重新設為255，當像素值小于該閾值時則設為0.最后對二值化后的圖像刪除毛刺點和離群點.圖10為圖5經過去噪的效果.

圖9 DCGAN 生成數據的過程.

圖10 圖5經過去噪處理的效果

從圖10中可以看到，生成數據一定程度的保留了原始空車率數據的概率分布信息，即可表示出時間和空車率的關系.另一方面，由于DCGAN 本身的特性，生成結果不僅和真實數據有相似的概率分布，且有一定的多樣性.因此，只要生成結果集足夠大，就會包含該簇所有停車場的空車率數據.

表4 式(7)的系數設置.

為了對比生成數據的效果，本文還復現了RGAN生成停車數據的實驗.設置隱層神經元50，批處理大小為1，學習率為0.03.使用與上文實驗相同的訓練集進行學習，生成過程如圖11所示.

在圖11中，Iteration 表示迭代次數.在迭代100 次時曲線無規律，隨著學習的進行，曲線漸漸變得平滑，當迭代次數達到4000 時，曲線趨于平穩，但仍有數據跳變的情況.本文實驗選取第4000 次迭代結果.

考慮到 GAN 網絡本身的缺陷，無論是本文基于 DCGAN的生成模型還是已有的基于RGAN 的生成模型，都難免會生成十分異常的輸出，因此需要對生成的數據進行評估，及時剔除明顯錯誤的生成數據.具體做法是在每一個時間節點計算生成數據與117 條真實數據誤差，當一條生成數據在85%的時間節點上與真實數據集的誤差都小于0.05，則保留這條數據，反之則丟棄.兩種方法耗時對比和生成數據結果對比如表5和圖12所示.

圖11 RGAN 生成數據的過程.

表5 兩種數據修補方法耗時對比.

從表5中，可以看到基于DCGAN 的停車場數據修補方法相較基于RGAN 的停車場數據修補方法耗時顯著降低.從圖12可以看出，一方面無論RGAN 生成模型還是DCGAN 生成模型，其生成數據和真實數據視覺上大致相似，因此兩種方法均存在一定合理性.另一方面RGAN 生成的數據出現了異常偏移和明顯抖動，而DCGAN 生成數據較RGAN 生成數據更為平滑.這可能是RGAN 網絡對樣本集學習過于充分而導致的泛化性能不強，且DCGAN 面向的二維數據比RGAN 處理的一維數據有更多的特征.考慮到停車數據受人類社會活動的影響，一般情況下其數據變化是一個循序漸進的過程(如圖12中的真實數據)，特殊情況下有出現短期大幅跳變的可能，比如體育場周邊的停車場，在有球賽的時其空車率會急促降低，但如果多數生成曲線均存在急劇抖動現象，會導致其與真實數據間的方差變大，因此需要曲線平滑.兩種生成數據與真實數據方差如表6所示.

圖12 真實數據和生成數據對比效果

表6 兩種修補方法生成數據的離散程度

因此就修補速度和生成數據直觀效果，基于DCGAN模型的修補方法均明顯優于基于RGAN 模型的修補方法，更符合公眾認知.

為了進一步比較兩種生成數據的質量，還需衡量生成數據與非樣本點的真實數據之間的誤差.本文引入均方根值(RMS)、均方根分誤差(RMSE)、平均絕對誤差(MAE)來描述這種誤差，并用卡方檢驗(Chisquare test)計算兩種生成數據和真實數據同分布的比例，設置卡方檢驗顯著性水平為0.05，在8928 個時間點上判斷生成數據和真實數據是否屬于同一分布，如果卡方檢驗的P值大于0.05，則此時刻的生成數據與真實數據屬于同一分布.兩種方法修復數據對比如表7所示.

表7 兩種數據修補方法效果對比

從表7可以看出，基于RGAN 的數據修補方法的誤差分析和正確率均稍好于基于DCGAN 的數據修補方法，這是因為RGAN 中的LSTM 對文本數據解釋性較好.因此，總結兩種方法的優缺點如表8所示.

表8 兩種生成方法的優缺點

5 結論

為了在降低經濟時間成本的前提下，獲得城市中的所有停車場的停車數據，本文提出了一種基于DCGAN生成模型來修復缺失數據的全新技術，可通過對樣本停車數據的學習訓練生成與之同分布的新數據，由于GAN 網絡生成數據多樣的特征，理論上只要新數據數量足夠大，就一定會包含該簇所有停車場的停車數據.其中要解決的細節問題主要由兩點組成.首先，不同地理信息的停車場數據差異巨大，這樣會導致生成數據可解釋性差.本文的方法是統計停車場周圍POI 的類型和數量將停車場映射為高維向量，使用K-means 算法將數據特征相似的停車場歸為一個簇，針對各個簇分別進行數據修復實驗；其次，為了降低成本，本文希望僅通過少量數據就能學習到足夠特征來生成同分布的新數據.對于任意一個簇，本文做法是利用PageRank算法的思想通過對停車場的公開信息和停車場間的連通度的迭代計算，算出各個停車場的影響力評分值，在驗證停車數據遵循二八定律的后，將影響力最大的20%停車場作為樣本停車場，通過安裝傳感器等方式獲取樣本停車場數據，以此為樣本修復該簇其余的停車場停車數據.

本文的方法目前還不能針對具體停車場進行點對點的修復.下一步主要研究方向是對特定停車場的數據進行修復.