譚文安,劉新樂

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

0 引言

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

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

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

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

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

1 算法介紹

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

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

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

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

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

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

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

1.2 基于DT的分類模型

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

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

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

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

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

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

1.3 基于集成學習的預測模型

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

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

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

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

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

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

(3) 組合特征。為了剔除誤導因素的影響,需要考慮更強的特征,如用戶預計到達的時間與實際到達時間的差異,如果兩次時間點之間的差異很大則強烈暗示用戶在尋找停車位時花費了較長時間,出現(xiàn)了停車難問題。另一方面,當一個位置出現(xiàn)停車難現(xiàn)象之后,車主往往只能選擇將車最終?？吭谀繕宋恢弥苓叺膮^(qū)域,因此停車位置距目標位置的距離也可以作為一個特征。

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

線性核

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

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

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

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

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

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

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

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

表1 普通SVM模型評價指標Tab.1 General SVM model evaluation indexs

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

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

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

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

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

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

3 結(jié) 論

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

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