基于集成學(xué)習(xí)的城市空間停車難度預(yù)測

譚文安,劉新樂

(上海第二工業(yè)大學(xué) 計算機(jī)與信息工程學(xué)院,上海201209)

0 引言

隨著我國機(jī)動車保有量逐年遞增,城市停車場建設(shè)已經(jīng)難以滿足機(jī)動車的增長速度,造成“一位難求”“繞樹三匝無枝可依”等停車難問題。許多駕駛?cè)藛T的出行時間浪費(fèi)在交通堵塞或?qū)ふ彝＼囄簧?這不但進(jìn)一步加劇擁堵,也造成出行效率低下與環(huán)境污染等問題。

針對這一日益嚴(yán)峻的城市問題,國內(nèi)外許多學(xué)者進(jìn)行了深入的研究與討論。所提出的解決方案主要分為：基于傳感器與通信網(wǎng)絡(luò)的城市停車誘導(dǎo)信息系統(tǒng)建設(shè)和基于統(tǒng)計理論和機(jī)器學(xué)習(xí)等數(shù)據(jù)驅(qū)動方法的預(yù)測模型研究。

停車誘導(dǎo)系統(tǒng)主要是在停車場的各出入口通過泊位信息采集設(shè)備實時檢測進(jìn)出車輛,采集停車場車位變化數(shù)據(jù),然后通過統(tǒng)一平臺如電子告示牌等將車位實時變化信息告知駕駛員。比如Hong等[1]提出了一個針對停車位管理服務(wù)的實時監(jiān)測系統(tǒng)。但是,該方法主要針對具有固定車位信息的城市停車場,而對于諸如路邊占道停車等開放空間的泊車情況卻缺乏支持。而后者由于地點(diǎn)分散、路況復(fù)雜、靈活度大、通信能力差、多采用人工收費(fèi)管理等原因,難以集中管理,不能很好地集成到現(xiàn)有的誘導(dǎo)系統(tǒng)中。

近年來伴隨著機(jī)器學(xué)習(xí)與深度學(xué)習(xí)的浪潮,基于數(shù)據(jù)驅(qū)動的停車位預(yù)測方法快速發(fā)展,并經(jīng)常作為停車誘導(dǎo)系統(tǒng)信息管理模塊來進(jìn)一步提高對于車位信息實時變化的處理能力。文獻(xiàn)[2-4]中研究了基于BP神經(jīng)網(wǎng)絡(luò)的城市停車需求預(yù)測模型。文獻(xiàn)[5-6]中研究了基于粒子群優(yōu)化算法與小波神經(jīng)網(wǎng)絡(luò)方法結(jié)合的停車場有效停車位預(yù)測問題。前者主要利用粒子群算法優(yōu)化小波神經(jīng)網(wǎng)絡(luò)的參數(shù),后者主要通過選擇小波函數(shù)重構(gòu)預(yù)測時間序列,然后采用小波神經(jīng)網(wǎng)絡(luò)進(jìn)行預(yù)測。龍東華等[7]提出了基于主成分分析的BP神經(jīng)網(wǎng)絡(luò)停車需求預(yù)測模型,利用主成分分析法研究了影響停車需求的各個特征,以此簡化了神經(jīng)網(wǎng)絡(luò)的輸入。孫敏等[8]研究了基于長、短時記憶網(wǎng)絡(luò)的停車位預(yù)測問題,可以在預(yù)測時間為中、長周期內(nèi)保持?jǐn)?shù)據(jù)變化特征。Vlahogiannia等[9]提出了一個傳感器網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)相結(jié)合的實時預(yù)測系統(tǒng)。這些基于神經(jīng)網(wǎng)絡(luò)模型的預(yù)測算法能夠充分利用深度模型對于非線性問題的強(qiáng)擬合能力來處理復(fù)雜參數(shù),限于神經(jīng)網(wǎng)絡(luò)自身的特點(diǎn),其也存在著諸如訓(xùn)練開銷大,可解釋性差等諸多問題。針對深度學(xué)習(xí)算法的諸多問題,也有學(xué)者研究利用傳統(tǒng)機(jī)器學(xué)習(xí)的方法進(jìn)行停車預(yù)測,Fan等[10]研究了支持向量回歸(support vector regression,SVR)分類方法預(yù)測停車位的問題;鄭喆等[11]研究了結(jié)合深度信念網(wǎng)絡(luò)模型和SVR分類方法構(gòu)建預(yù)測模型。同誘導(dǎo)系統(tǒng)一樣,當(dāng)前這些機(jī)器學(xué)習(xí)方法也主要針對停車場車位的預(yù)測問題,難以處理路邊占道停車等復(fù)雜情況。復(fù)雜的停車方式很難精確實時掌握目的地的車位信息;同時我們注意到大部分出行用戶更關(guān)注的是有沒有停車位可供使用,而非精確的停車位數(shù)量,因為停車位供需信息是實時變化的,在用戶前往途中往往就會發(fā)生變化。

本文從模糊預(yù)測的角度來預(yù)測目的地的停車難度,而非預(yù)測精確的車位數(shù)量。用戶根據(jù)給出的停車難度來規(guī)劃出行方式。將某一位置的停車難度劃分為“簡單”與“困難”兩個類別,建立一個基于集成學(xué)習(xí)的監(jiān)督分類算法,對任意位置的停車難度情況進(jìn)行預(yù)測,包括停車場與路邊停車的情況,因此實用性較強(qiáng)。另一方面,在訓(xùn)練模型時采用了非神經(jīng)網(wǎng)絡(luò)的機(jī)器學(xué)習(xí)方法,與深度模型相比,其訓(xùn)練效率更高,模型的可解釋性更好。

1 算法介紹

根據(jù)前文的描述,希望構(gòu)建一個基于集成學(xué)習(xí)方法的算法進(jìn)行停車難度預(yù)測。集成學(xué)習(xí)是指訓(xùn)練一組弱學(xué)習(xí)器,然后通過某種集成策略將各個子學(xué)習(xí)器進(jìn)行結(jié)合,以此獲得比單一學(xué)習(xí)器更加優(yōu)越的泛化性能[12]。使用支持向量機(jī)(support vector machine,SVM)[13]與決策樹(decision tree,DT)集成的方式訓(xùn)練該監(jiān)督分類模型。首先,這兩類算法的運(yùn)行機(jī)制很好理解,且對訓(xùn)練數(shù)據(jù)中的噪聲具有彈性。其次,SVM引入核方法后可以進(jìn)行非線性學(xué)習(xí),能夠較好地處理高維數(shù)據(jù)的情況,便于進(jìn)一步引入新的特征后保持算法的適應(yīng)性。同時,DT模型的結(jié)果可解釋性好,很容易直觀理解每個特定特征,也更容易驗證模型的行為是否合理。將二者集成可以獲得更穩(wěn)健的模型與更理想的預(yù)測效果。

1.1 基于SVM的停車難度二分類模型

將停車難度映射為“簡單”與“困難”,以此作為樣本數(shù)據(jù)對應(yīng)的類別空間(x,y),x是由停車預(yù)測相關(guān)特征組成的訓(xùn)練樣本,y是樣本對應(yīng)的標(biāo)簽(停車是否困難,即0或1),組成一個二元值。因此,給定樣本數(shù)據(jù) D={(x1,y1),(x2,y2),···,(xm,ym)},其中x∈Rn,y∈{0,1},m為樣本個數(shù),n為訓(xùn)練變量特征維數(shù),任務(wù)轉(zhuǎn)變?yōu)橛?xùn)練SVM二分類模型?？紤]到實際問題中由噪聲等因素引起的線性不可分情況,同時避免過擬合,通常可引入軟間隔SVM與正則化的概念,于是需要解決以下優(yōu)化問題：

式中：ω為分類超平面的系數(shù);b為偏置項;ξ為松弛變量;C為懲罰參數(shù),用于ξ與間隔最大化之間取得平衡。式(1)對應(yīng)的拉格朗日函數(shù)為：

式中,拉格朗日乘子 α,β滿足：αi≥ 0,βi≥ 0。式(2)分別對ω,b,ξi求偏導(dǎo),并令偏導(dǎo)為零將結(jié)果代回原式(1)消去ω,b,ξ,得到式(2)對應(yīng)的對偶問題：

考慮到實際問題中樣本在低維空間不可分的情況,式(2)中原有3個松弛變量,經(jīng)過求導(dǎo)代換為單變量的優(yōu)化問題。同時注意到式(3)中訓(xùn)練樣本x僅出現(xiàn)在一項之中,可以考慮映射將樣本數(shù)據(jù)映射到高維甚至無限維空間,如果仍滿足內(nèi)積特性,則可以實現(xiàn)非線性SVM學(xué)習(xí)。此時上述優(yōu)化問題可以轉(zhuǎn)化為：

式中：k(xi,xj)=?(xi)T?(xj),稱為核函數(shù)。常用的核有線性核、多項式核、高斯核等。引入核是為了避免討論具體的映射形式。

1.2 基于DT的分類模型

DT分類是一種具有樹形結(jié)構(gòu)的機(jī)器學(xué)習(xí)模型。根節(jié)點(diǎn)對應(yīng)全體訓(xùn)練樣本集合,訓(xùn)練時從根節(jié)點(diǎn)開始選擇某一特征對樣本進(jìn)行測試,并根據(jù)結(jié)果將樣本分配到子節(jié)點(diǎn)上,然后遞歸對子節(jié)點(diǎn)重復(fù)此“測試-分配”過程,直至滿足以下停止條件之一：①當(dāng)前節(jié)點(diǎn)樣本同屬一個類別;②當(dāng)前屬性集為空;③當(dāng)前節(jié)點(diǎn)為空節(jié)點(diǎn)。最終算法學(xué)得一組“if-then”規(guī)則集合,并用它來進(jìn)行預(yù)測。

DT學(xué)習(xí)的關(guān)鍵在于迭代過程中如何選擇最優(yōu)的屬性來對當(dāng)前節(jié)點(diǎn)進(jìn)行劃分,即如何定量地度量每個屬性對樣本集合的劃分效果。常用的算法如ID3算法選擇以信息增益為準(zhǔn)則,C4.5算法是在ID3的基礎(chǔ)上進(jìn)一步采用信息增益率,而CART則選擇計算基尼(Gini)指數(shù)。其中使用屬性A對集合S進(jìn)行劃分,對應(yīng)的信息增益可表示為：

式中：J表示由屬性A對集合S進(jìn)行劃分可能得到的子集數(shù)目,假定當(dāng)前集合中第k(k=1,2,···,K)類樣本所占比例為pk,則Entropy(S)=表示集合S的信息熵,其取值越小表示S的純度越高。因此在劃分時選擇信息增益最大的屬性,以此獲得純度更高的子集。為了防止由于信息增益偏好取值數(shù)目多對結(jié)果產(chǎn) 生不利的影響,考慮計算信息增益率。其中：

式中：SplitInfo(S,A)稱為屬性A的“固有值”,通常取值數(shù)目越多“固有值”越大;|Sj|表示分支j的樣本數(shù),從高于平均信息增益率的屬性中選擇信息增益率最大的特征對節(jié)點(diǎn)進(jìn)行劃分。

Gini指數(shù)可以表示為：

Gini(Sj)=1-表示集合Sj的不確定性,本文選擇Gini指數(shù)最小的屬性來劃分節(jié)點(diǎn)。

1.3 基于集成學(xué)習(xí)的預(yù)測模型

本研究在Bagging框架下將SVM與DT集成,每輪迭代中從初始訓(xùn)練集中采樣生成一個訓(xùn)練樣本集,然后在該采樣集上訓(xùn)練一個SVM模型,接著關(guān)注該SVM所誤分類的樣本,并將這些樣本記錄在另一個集合中,稱之為失誤集。當(dāng)失誤集的樣本數(shù)量累加到達(dá)某個閾值,比如當(dāng)與采樣集大小相同時,就用該樣本集合訓(xùn)練一個DT模型。經(jīng)過T輪訓(xùn)練,最終將得到T個SVM模型與P個DT模型。使用該模型進(jìn)行分類預(yù)測時,基于簡單的投票法集成T個SVM模型的分類結(jié)果,當(dāng)出現(xiàn)兩個類別收到同樣票數(shù)的情形時,則再次使用投票法取P個DT模型的結(jié)果作為輸出(若出現(xiàn)同樣的情況則隨機(jī)選擇一個類別輸出)。算法的主要框架如下：

最終輸出包括H(x)表示的SVM集成分類器和F(x)表示的DT集成分類器。

2 實驗與結(jié)果分析

停車位的供需變化與居民的出行變化情況息息相關(guān),因此收集了上海市區(qū)某地的停車相關(guān)統(tǒng)計數(shù)據(jù),選擇與居民的出行模式相關(guān)聯(lián)的特征來訓(xùn)練模型。主要包括：

(1) 時空特征。如：一天當(dāng)中的第幾個小時,星期幾,是否節(jié)假日;周邊一定范圍內(nèi)停車場的數(shù)目;目的地的空間屬性(商業(yè)區(qū),居民區(qū)等);交通情況(擁堵/暢通)。

(2) 行為特征。通過收集的用戶軌跡數(shù)據(jù)來標(biāo)記目的地位置的停車難度,主要評判的規(guī)則是監(jiān)測用戶在目的地周圍是否出現(xiàn)“巡游”“兜圈子”找停車位的情況,一旦出現(xiàn)將其標(biāo)記為“困難”,但是這樣也可能會誤判一些情況,比如在私人車位停車時不會發(fā)生上述“巡游”“兜圈子”現(xiàn)象,但顯然不應(yīng)以此就認(rèn)為該位置的車位充足。另一方面,對乘坐出租車或公共交通抵達(dá)的用戶,其行為軌跡看起來像是停車位充裕,其實不然,這些誤報都有可能誤導(dǎo)機(jī)器學(xué)習(xí)系統(tǒng)。

(3) 組合特征。為了剔除誤導(dǎo)因素的影響,需要考慮更強(qiáng)的特征,如用戶預(yù)計到達(dá)的時間與實際到達(dá)時間的差異,如果兩次時間點(diǎn)之間的差異很大則強(qiáng)烈暗示用戶在尋找停車位時花費(fèi)了較長時間,出現(xiàn)了停車難問題。另一方面,當(dāng)一個位置出現(xiàn)停車難現(xiàn)象之后,車主往往只能選擇將車最終停靠在目標(biāo)位置周邊的區(qū)域,因此停車位置距目標(biāo)位置的距離也可以作為一個特征。

利用Scikit-learn提供的SVM和DT工具,以及Tensor Flow和Keras提供的神經(jīng)網(wǎng)絡(luò)構(gòu)建工具來進(jìn)行模型訓(xùn)練。影響SVM模型性能的主要因素是核函數(shù),因此選擇不同的核函數(shù)訓(xùn)練多個SVM-DT模型,主要包括：

線性核

DT模型主要是為了糾正SVM的誤分類情況,因此訓(xùn)練時可適當(dāng)放寬參數(shù)約束,選擇默認(rèn)設(shè)置及選擇Gini指數(shù)與信息增益分別與SVM組合,結(jié)果如圖1和2所示。可以直觀地看到基于Gini指數(shù)的DT偏好特征X6,該特征對應(yīng)實際停車位置與目標(biāo)位置的實際距離,即泊車的空間分布特征。而基于信息增益的DT則更傾向于特征X7,該特征對應(yīng)周邊停車場個數(shù),即目的地的空間屬性特征。

使用常用的分類任務(wù)評價指標(biāo)來度量模型在測試樣本集合上的效果。對于二分類問題,用TP表示真實情況為正例而預(yù)測結(jié)果為正例的樣本數(shù),TN表示真實情況為反例而預(yù)測結(jié)果也為反例的樣本數(shù),FN表示真實情況為正例而預(yù)測結(jié)果為反例的樣本數(shù),FP表示真實情況為反例而預(yù)測結(jié)果卻為正例的樣本數(shù)。通用指標(biāo)包括準(zhǔn)確率,精度和召回率。

定義Acc表示分類正確的樣本數(shù)占樣本綜述的比例,計算式如下：

圖1 基于Gini指數(shù)的停車難度分類DT模型Fig.1 DT model of parking difficulty classification based on Gini cofficient

定義精度表示預(yù)測正確的正例占所有預(yù)測為正的比值,計算式如下：

定義召回率表示預(yù)測正確的正類與實際為正類的比值,公式如下：

圖2 基于信息增益的停車難度分類DT模型Fig.2 DT model of parking difficulty classification based on information gain

對每一個組合分別計算上述3個指標(biāo),模型評價指標(biāo)如表1～3所示?？梢灾庇^地看到線性核模型即可取得較好的預(yù)測準(zhǔn)確率。另一方面,為了對比分析,利用相同的訓(xùn)練數(shù)據(jù)訓(xùn)練了一個DT分類預(yù)測模型以及一個兩層全連接神經(jīng)網(wǎng)絡(luò)模型(FC),然后在相同測試集上分別計算模型正確率、精度和召回率,結(jié)果見表4。可以看出,SVM和DT集成的模型在分類性能方面優(yōu)于單一的SVM或DT模型;另一方面SVM-DT模型的性能與FC相比,具有更小的計算開銷和更少的超參數(shù)設(shè)置,這在訓(xùn)練時具有更強(qiáng)的實用意義。

表1 普通SVM模型評價指標(biāo)Tab.1 General SVM model evaluation indexs

表2 基于信息增益的SVM-DT模型評價指標(biāo)Tab.2 SVM-DT model evaluation indexs based on information gain

表3 基于Gini指數(shù)的SVM-DT模型評價指標(biāo)Tab.3 SVM-DT model evaluation indexs based on Gini coefficient

表4 不同模型的分類性能Tab.4 Classification performance of different models

利用訓(xùn)練好的SVM-DT預(yù)測模型,預(yù)測了1周的停車難度情況。訓(xùn)練時間從1天的零點(diǎn)開始,間隔時間為5 min,第1個5 min計為第1個時間片,以此類推,統(tǒng)計出周一至周日的各個時間片出現(xiàn)停車難現(xiàn)象的頻率,將真實數(shù)據(jù)與預(yù)測結(jié)果的統(tǒng)計情況進(jìn)行比較,結(jié)果如圖3、4所示。真實數(shù)據(jù)和預(yù)測結(jié)果均顯示停車難的現(xiàn)象集中出現(xiàn)在時間片70～110及 200～250,這兩處時間片基本對應(yīng)上午 6：00～9：00和下午 5：00～8：00,也正是城市早晚高峰的時段,由于上下班等因素導(dǎo)致機(jī)動車活躍數(shù)目激增,路況變得更加復(fù)雜,由此導(dǎo)致停車難現(xiàn)象出現(xiàn)的概率增大,通過預(yù)測模型可以較好地捕捉到這一特點(diǎn)。

圖3 1周時間實際停車情況統(tǒng)計柱狀圖Fig.3 Histogram of actual parking statistics during one week

圖4 1周時間停車情況預(yù)測柱狀圖Fig.4 Forecasting histogram of parking during one week

3 結(jié) 論

基于SVM與DT構(gòu)建了一個集成學(xué)習(xí)的監(jiān)督分類算法,該方法可以較準(zhǔn)確地預(yù)測任意位置的停車難度,包括停車場與路邊停車的情況,實用性較強(qiáng)。訓(xùn)練模型時采用了非神經(jīng)網(wǎng)絡(luò)的機(jī)器學(xué)習(xí)方法,相比深度模型來說訓(xùn)練效率更高,模型的可解釋性較好。該方法還可用于預(yù)測實時停車難度,具體做法是在訓(xùn)練數(shù)據(jù)中加入待預(yù)測點(diǎn)歷史停車難度信息,利用待預(yù)測時間點(diǎn)前一段時間的停車數(shù)據(jù)構(gòu)造時序特征及利用時間滑動窗口從序列數(shù)據(jù)建立角度訓(xùn)練模型。

進(jìn)一步的研究可以考慮結(jié)合眾包集體智慧的方式收集用戶反饋停車信息,并將其作為訓(xùn)練數(shù)據(jù),比如利用移動終端追蹤用戶軌跡信息等方式,以期模型的預(yù)測結(jié)果能夠作為輔助用戶出行的決策支持,幫助用戶合理規(guī)劃出行方式,進(jìn)而緩解停車難問題,營造智慧化的和諧城市。