聚類分析和支持向量機(jī)回歸的交通流預(yù)測

鄧晶 　張倩

中文摘要：本文以交通流數(shù)據(jù)為研究對象，主要對數(shù)據(jù)挖掘技術(shù)在交通流預(yù)測方面的應(yīng)用進(jìn)行了研究和探討。并基于研究內(nèi)容，提出了基于聚類分析和支持向量機(jī)回歸的交通流預(yù)測模型。并針對支持向量機(jī)參數(shù)選擇，提出了人工魚群算法使其快速尋找到最優(yōu)參數(shù)組合。最后，通過實(shí)驗(yàn)數(shù)據(jù)論證本文所提出的算法和模型。

關(guān)鍵詞：數(shù)據(jù)挖掘;交通流預(yù)測;聚類分析;支持向量機(jī);人工魚群算法

中圖分類號：TP18 ? ? ? ?文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2019）15-0013-04

Abstract： This paper takes traffic flow data as the research object， mainly studies and discusses the application of data mining technology in traffic flow prediction. Based on the research content， a traffic forecasting model based on clustering analysis and support vector machine regression is proposed. Aiming at the parameter selection of support vector machine， an artificial fish swarm algorithm is proposed to quickly find the optimal parameter combination. Finally， the algorithm and model proposed in this paper are demonstrated by experimental data.

Key words： data mining; Traffic flow forecasting; cluster analysis; Support Vector Machine; afsa

隨著城市規(guī)模和交通出行需求的不斷增長，人們對出行決策服務(wù)的需求越來越強(qiáng)烈。如何能夠?qū)崟r準(zhǔn)確地預(yù)測交通流成為交通管理和控制是否能有效實(shí)現(xiàn)的關(guān)鍵問題。傳統(tǒng)的交通流預(yù)測模型早已無法滿足實(shí)踐中高實(shí)時性、高精度的預(yù)測要求。目前，在智能交通流預(yù)測領(lǐng)域，主要采用基于非線性理論的預(yù)測模型、基于神經(jīng)網(wǎng)絡(luò)的預(yù)測模型、基于支持向量機(jī)的預(yù)測模型和多模型融合的預(yù)測模型等，以研究、開發(fā)和實(shí)現(xiàn)實(shí)時道路交通預(yù)測。支持向量機(jī)（SVM）是近十幾年出現(xiàn)的一種先進(jìn)的數(shù)據(jù)挖掘方法。由于交通流數(shù)據(jù)具有數(shù)據(jù)量大、維度高、非線性等特征，SVM采用結(jié)構(gòu)風(fēng)險最小化的學(xué)習(xí)方式可以實(shí)現(xiàn)在小樣本的學(xué)習(xí)環(huán)境下，采用凸優(yōu)化的學(xué)習(xí)方式，有效地避免過擬合和局部最優(yōu)，從而使交通流預(yù)測性能大大提高。對于樣本量較大的交通流數(shù)據(jù)，按照不同的屬性對數(shù)據(jù)進(jìn)行聚類分析，同一類別內(nèi)的數(shù)據(jù)相似度更高，且數(shù)據(jù)樣本量相對減小，使用支持向量機(jī)回歸進(jìn)行預(yù)測能夠獲得更好的預(yù)測效果。最后的實(shí)驗(yàn)數(shù)據(jù)也證明了這一點(diǎn)。

1 數(shù)據(jù)預(yù)處理

交通數(shù)據(jù)采集的途徑和方法有很多。在采集過程中不可避免的會產(chǎn)生一些問題。假如不對原始采集數(shù)據(jù)進(jìn)行預(yù)處理，檢查并清除問題數(shù)據(jù)，妥善處理好缺失值和異常值，必然會使研究結(jié)果產(chǎn)生很大偏差。

本文采用牛頓插值法對缺失數(shù)據(jù)進(jìn)行補(bǔ)值計算。采用合適的小波函數(shù)對數(shù)據(jù)進(jìn)行一定尺度的小波變換，通過信號重構(gòu)，去掉噪聲數(shù)據(jù)?？紤]到交通數(shù)據(jù)的特點(diǎn)，采用0均值標(biāo)準(zhǔn)化對數(shù)據(jù)進(jìn)行歸一化處理。

最后，從大量的交通流原始數(shù)據(jù)中選擇出特征集。數(shù)據(jù)特征選擇是從已知的特征集合中選擇一個子集，該子集可以全面有效地對數(shù)據(jù)進(jìn)行描述，后續(xù)的預(yù)測分析工作可以針對該子集進(jìn)行。選擇出優(yōu)良的特征數(shù)據(jù)，不僅可以降低數(shù)據(jù)計算量，提升效率，而且可以幫助研究者更深入的理解研究對象。

2 基于聚類分析和支持向量機(jī)回歸的交通流預(yù)測

交通流數(shù)據(jù)具有非線性、高維度的特性。支持向量機(jī)回歸算法在處理小樣本、非線性、高維度數(shù)據(jù)時，具有很好的預(yù)測效果。因此，我們采用支持向量機(jī)作為核心預(yù)測算法。但交通流數(shù)據(jù)樣本數(shù)量比較龐大，可能會導(dǎo)致支持向量機(jī)的訓(xùn)練速度緩慢，且預(yù)測容易產(chǎn)生偏差。針對這一問題，我們首先采用K-means++聚類算法將數(shù)據(jù)按照交通流量、天氣、節(jié)假日等屬性進(jìn)行聚類得到若干類別。同一類別內(nèi)的數(shù)據(jù)相似度高，數(shù)據(jù)規(guī)模也相對較小。然后，通過實(shí)時數(shù)據(jù)匹配相應(yīng)類的數(shù)據(jù)進(jìn)行樣本訓(xùn)練，再使用支持向量機(jī)進(jìn)行預(yù)測能夠獲得更好的預(yù)測效果。

在支持向量機(jī)模型參數(shù)的選擇的問題上，采用人工魚群算法對支持向量機(jī)回歸的參數(shù)進(jìn)行優(yōu)化，采用合適的參數(shù)能夠進(jìn)一步提高預(yù)測精度和推廣能力。

2.1交通流數(shù)據(jù)的聚類分析

傳統(tǒng)的K-means聚類算法需要人為確定初始聚類中心。不同的聚類中心可能會導(dǎo)致不同的聚類結(jié)果。在交通流數(shù)據(jù)聚類分析中，我們采用K-means++聚類算法，它的核心思想是選擇的初始聚類中心之間的距離要盡可能遠(yuǎn)。

2.3人工魚群算法優(yōu)化支持向量機(jī)參數(shù)

支持向量機(jī)回歸中參數(shù)的選擇對模型的預(yù)測效果有著十分重要的影響。即損失函數(shù)ε、懲罰因子C、高斯徑向基函數(shù)。如何組合這三個參數(shù)成了支持向量機(jī)回歸不可避免的問題。由于參數(shù)選擇的復(fù)雜性，目前還沒有確定的理論來指導(dǎo)，而群體智能算法在參數(shù)優(yōu)化問題上有很好的效果。本文使用群體智能化算法中的人工魚群算法對支持向量機(jī)的參數(shù)進(jìn)行尋優(yōu)。人工魚群算法對初值和參數(shù)不太敏感，具有自適應(yīng)搜索空間的能力，且魯棒性強(qiáng)，收斂速度快。更重要的是，能夠避免陷入局部極值而失去全局最優(yōu)。

在人工魚群算法中包括三種主要的算子：聚群算子、追尾算子和覓食算子。這三種算子是算法的核心，并且決定算法的性能和最優(yōu)解搜索的準(zhǔn)確度。

設(shè)Xi表示第i條人工魚的位置;Yi表示第i條人工魚的適應(yīng)度值。其中，Yi=f（Xi）;β表示擁擠度因子;try表示人工魚在覓食算子中的最大試探次數(shù)。

（1） 覓食算子

人工魚按式（6）隨機(jī)選擇當(dāng)前感知范圍內(nèi)的一個位置Xj，若Yi〉Yj，則按式（7）向該位置前進(jìn)一步，達(dá)到一個新位置Xnext。反之，則重新隨機(jī)選擇位置，判斷是否滿足前進(jìn)條件;這樣反復(fù)嘗試try次后，如仍不能滿足前進(jìn)條件，則在感知范圍內(nèi)隨機(jī)移動一步。

Xj = xi + rand * visual ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （6）

Xnext = Xi + rand * step * ? ? ? ? ? ? ? ? ? ? ?（7）

（2） 聚群算子

人工魚i以自身位置Xi為中心，其感知范圍內(nèi)的人工魚數(shù)目為nf，當(dāng)nf ≥1時，這些人工魚形成如式（8）的集合Si，按式（9）計算Si的中心位置Xcenter。如果Yenter< Yi且Ycenter/nf>β*Yi，表明伙伴中心有很多食物且不太擁擠，則按式（10）朝該中心方向移動一步;否則，執(zhí)行覓食算子。

Si = { xj∣〡xj - xi〡≤ visual } ? ? ? ? ? ? ? ? ? ? ?（8）

Xcenter = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（9）

Xnext = xi + rand * step * ? ? ? ? ? ? ? ? ? （10）

（3） 追尾算子

人工魚i根據(jù)當(dāng)前位置搜索其感知范圍內(nèi)所有伙伴中適應(yīng)度最小的伙伴位置Xmin，其適應(yīng)度為Ymin，如果Ymin< Yi，就Xmin為中心搜索其感知范圍內(nèi)的人工魚。數(shù)目為nf，且Ymin< Yi且Ymin/nf>β*Yi，表明該位置較優(yōu)且不太擁擠，則按式（11）向著適應(yīng)度最小伙伴位置Xmin的方向前進(jìn)一步。否則，執(zhí)行覓食算子。

Xnext = xi + rand * step * ? ? ? ? ? ? ? ? ? ? ? ? ? ?（11）

人工魚群算法中每條人工魚首先分別試探執(zhí)行聚群算子和追尾算子，通過目標(biāo)函數(shù)計算其適應(yīng)度是否得到改善。將適應(yīng)度改善較大的算子作為該條人工魚的更新算子;否則執(zhí)行覓食算子;若這條人工魚達(dá)到覓食算子的最大嘗試次數(shù)后，適應(yīng)度依舊沒有改變，則在自己周圍隨機(jī)移動一個位置。所有人工魚執(zhí)行上述操作后，最終人工魚群集結(jié)在幾個局部最優(yōu)解周圍，且全局最優(yōu)極值區(qū)域周圍也有較多人工魚集結(jié)。

該模型的詳細(xì)描述如下：

Step1：設(shè)置支持向量機(jī)回歸相關(guān)參數(shù)的取值范圍：包括損失函數(shù)ε、懲罰因子C、高斯徑向基函數(shù)δ。對人工魚群算法進(jìn)行參數(shù)設(shè)置。包括魚群的種群規(guī)模，種群迭代次數(shù)，種群的擁擠度因子，最多試探次數(shù)，人工魚的感知距離以及人工魚移動的步長等;

Step2：在聚類分析后得到的數(shù)據(jù)集中，選取部分測試數(shù)據(jù)，剩下的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)集用來進(jìn)行SVR的預(yù)測分析，從而判別SVR的預(yù)測效果;

Step3：人工魚群中的每條魚是SVR優(yōu)化參數(shù)組合（ε、C、δ），即損失函數(shù)、懲罰因子、高斯徑向基函數(shù)。根據(jù)setp1中的參數(shù)取值范圍初始化魚群位置。對所有人工魚并行尋優(yōu);

Step4：根據(jù)SVR運(yùn)用訓(xùn)練數(shù)據(jù)集得到的預(yù)測結(jié)果，通過計算預(yù)測值與實(shí)際值的均方根誤差，以此作為人工魚的目標(biāo)值。同時，比較每條人工魚目標(biāo)值的大小，將其中的最小值作為當(dāng)前魚群中的最優(yōu)，并保存當(dāng)前的最優(yōu)人工魚參數(shù)組合（ε、C、δ）;

Step5：每條人工魚分別模擬聚群行為和追尾行為，通過選擇游動后目標(biāo)值比較小的行為來確定實(shí)際執(zhí)行的行為。覓食行為是缺省行為;

Step6：在魚群中，每更新一次位置，都需要計算當(dāng)前魚群的最優(yōu)目標(biāo)值。如果其中一條魚對應(yīng)的目標(biāo)值小于目前保存的最優(yōu)目標(biāo)值，那么將其替代保存的最優(yōu)目標(biāo)值，同時保存最優(yōu)人工魚參數(shù)組合（ε、C、δ）。否則，最優(yōu)目標(biāo)值和參數(shù)組合保持不變;

Step7：判斷迭代次數(shù)是否達(dá)到最大迭代次數(shù)。如果達(dá)到，輸出人工魚參數(shù)組合（ε、C、δ）和最優(yōu)目標(biāo)值。否則，返回step5。

2.4基于K-means++聚類算法和支持向量機(jī)回歸交通流預(yù)測

本文研究的交通流數(shù)據(jù)包括交通流量、車速、占有率、日期、天氣、交通時間等，在分析各方面因素后，設(shè)計了一種基于基于K-means++聚類算法和支持向量機(jī)回歸的交通流預(yù)測模型。該模型的預(yù)測流程為：

Step1：對數(shù)據(jù)進(jìn)行預(yù)處理，得到相對完整準(zhǔn)確的交通流特征數(shù)據(jù);

Step2：將交通流特征數(shù)據(jù)按照交通流量、天氣、節(jié)假日等屬性進(jìn)行聚類得到若干類別，使得同一類別內(nèi)的數(shù)據(jù)相似度更高，每個類別數(shù)據(jù)的規(guī)模也相對小;

Step3：計算交通流實(shí)時數(shù)據(jù)與已經(jīng)生成的所有聚類簇的歐氏距離，匹配到相應(yīng)的簇中，使得簇內(nèi)的數(shù)據(jù)與預(yù)測當(dāng)天的特征相似度更高。將該簇內(nèi)的交通流數(shù)據(jù)作為訓(xùn)練樣本;

Step4：使用選取的訓(xùn)練樣本數(shù)據(jù)，應(yīng)用人工魚群算法對支持向量機(jī)參數(shù)尋優(yōu)，得到支持向量機(jī)最優(yōu)參數(shù)組合;

Step5：使用參數(shù)優(yōu)化后的支持向量機(jī)回歸模型進(jìn)行預(yù)測，得出預(yù)測結(jié)果;

3實(shí)驗(yàn)結(jié)果和分析

3.1數(shù)據(jù)來源與評價指標(biāo)

本文實(shí)驗(yàn)數(shù)據(jù)來源于美國加州交通局的PEMS系統(tǒng)。PEMS系統(tǒng)的數(shù)據(jù)是開源的，用于各類研究者學(xué)習(xí)和使用。在PEMS系統(tǒng)中，我們隨機(jī)選取一個時段的數(shù)據(jù)。該段數(shù)據(jù)已經(jīng)被處理成5分鐘一個間隔的交通流數(shù)據(jù)。包括車輛流數(shù)、車速及車道占有率等。另外，引入天氣因子，對天氣情況特征做出說明;引入時間類別，對普通工作日、節(jié)假日、重大節(jié)日等作出區(qū)分。

針對本文的最終目的是為了準(zhǔn)確地進(jìn)行回歸預(yù)測，我們引入了廣泛應(yīng)用于回歸問題的評價指標(biāo)，分別為平均絕對百分比誤差（MAPE）和均方跟誤差（RMSE）。其中，MAPE表征了預(yù)測值偏離實(shí)際值的程度。MAPE越小，表明預(yù)測值越接近于實(shí)際值，預(yù)測效果越好。RMSE表征了誤差大小以及誤差分布的離散程度。RMSE越小，誤差離散程度就越低，預(yù)測效果也就越好。

3.2 實(shí)驗(yàn)一：基于聚類分析和支持向量機(jī)回歸的交通流預(yù)測

3.2.1 聚類分析

本文抽取了2017年12月的交通流數(shù)據(jù)進(jìn)行聚類分析。12月一共有31天，將其中的2日、11日、18日的交通流數(shù)據(jù)抽出，作為測試樣本進(jìn)行驗(yàn)證。剩下的28天數(shù)據(jù)進(jìn)行聚類分析。根據(jù)最佳聚類數(shù)計算方法，即聚類數(shù)應(yīng)該在2到之間。為數(shù)據(jù)樣本數(shù)28。則最佳聚類數(shù)取值為2到5之間。對12月份28天交通流量歷史數(shù)據(jù)進(jìn)行聚類，采用輪廓系數(shù)來評價聚類效果，不同K值對應(yīng)的聚類結(jié)果和輪廓系數(shù)的實(shí)驗(yàn)數(shù)據(jù)如表1。

由上表可知，當(dāng)K=4時，聚類效果最好。即最佳聚類數(shù)K為4，聚類結(jié)果為四個簇。第一類為圣誕節(jié)及連接的周末;第二類是周末;第三類是工作日且天氣良好;第四類為普通工作日且天氣狀況差。由此可見，聚類后的每個類的特征都比較相似，類間特征差別比較明顯。之后將預(yù)測的日期匹配到相應(yīng)的聚類簇中，使用簇內(nèi)數(shù)據(jù)作為訓(xùn)練樣本，得到更好的預(yù)測效果。

3.2.2 支持向量機(jī)交通流預(yù)測

本文對2日、11日、18日部分時段進(jìn)行交通流預(yù)測。計算預(yù)測時段前三個小時的交通流量數(shù)據(jù)與四個簇類樣本中心的歐式距離，得到某一個聚類簇的歐式距離最小，并將其歸為一類。將這一簇內(nèi)的數(shù)據(jù)作為訓(xùn)練樣本數(shù)據(jù)集

以下以11日的預(yù)測為例，說明實(shí)驗(yàn)結(jié)果。

當(dāng)預(yù)測11日的交通流量時，計算得到與第三個聚類的歐式距離最小。選取第三個類中14天的數(shù)據(jù)為訓(xùn)練樣本。使用人工魚群算法計算得到最優(yōu)參數(shù)組合（ε、C、δ）=（0.74、69、0.26）。使用優(yōu)化的參數(shù)組合建立預(yù)測模型得到預(yù)測結(jié)果。與傳統(tǒng)的SVR預(yù)測結(jié)果和實(shí)際值的對比如圖1。

為了驗(yàn)證本文提出的預(yù)測算法，將其與傳統(tǒng)的支持向量機(jī)回歸算法、ARIMA預(yù)測算法、BP神經(jīng)網(wǎng)絡(luò)預(yù)測算法進(jìn)行對比。在相同的實(shí)驗(yàn)環(huán)境下，不同算法的MAPE和RMSE指標(biāo)如表2。

3.2.3 實(shí)驗(yàn)結(jié)果分析

由圖1可以看出，基于聚類分析和支持向量機(jī)回歸預(yù)測模型要優(yōu)于傳統(tǒng)的支持向量機(jī)模型。其預(yù)測曲線與原始實(shí)際值擬合的更好，變化趨勢也與原始實(shí)際值基本一致。這表明本文提出的預(yù)測模型使用聚類對數(shù)據(jù)區(qū)分后進(jìn)行訓(xùn)練，并對參數(shù)進(jìn)行優(yōu)化，可以有效地削弱隨機(jī)數(shù)據(jù)導(dǎo)致的誤差，從而有助于提升短期交通流預(yù)測的準(zhǔn)確性。

由表2可以看出，ARIMA算法預(yù)測精度最差。傳統(tǒng)的支持向量機(jī)和BP神經(jīng)網(wǎng)絡(luò)算法兩項指標(biāo)比較接近，預(yù)測精度基本相似。但支持向量機(jī)還是略勝一籌。兩種SVR預(yù)測模型都優(yōu)于兩種經(jīng)典的預(yù)測算法。而基于聚類分析和支持向量機(jī)回歸預(yù)測模型的兩項指標(biāo)又優(yōu)于傳統(tǒng)的SVR。其中MAPE降低了30.2%，RMSE降低了35.7%。

4 結(jié)束語

本文在對交通流數(shù)據(jù)進(jìn)行預(yù)處理后，通過聚類分析和支持向量機(jī)回歸算法建立預(yù)測模型，實(shí)現(xiàn)對非線性、高唯度交通流數(shù)據(jù)的有效預(yù)測。經(jīng)實(shí)驗(yàn)驗(yàn)證，優(yōu)于傳統(tǒng)的預(yù)測模型且更接近于實(shí)際交通流數(shù)據(jù)。

由于時間和水平有限，本文的研究內(nèi)容有待于進(jìn)一步拓展。主要有以下幾點(diǎn)：

由于影響交通流的因素很多，本文只考慮了其中重要的若干因素，需要考慮將更多的影響因子加入模型中。

人工魚群算法對SVR參數(shù)尋優(yōu)收斂速度較慢，可以研究其與其他尋優(yōu)算法結(jié)合，以達(dá)到更好的參數(shù)優(yōu)化效果。

參考文獻(xiàn)：

[1] 李青. 城市交通流預(yù)測關(guān)鍵技術(shù)研究[D]. 西南科技大學(xué)， 2015.

[2]王允森，蓋榮麗，孫一蘭. 基于牛頓迭代法的NURBS曲線插補(bǔ)算法[J].組合機(jī)床與自動化加工技術(shù)，2013（4）：13-17.

[3]丁世飛，齊炳娟，譚紅艷.支持向量機(jī)理論與算法研究綜述[J].電子科技大學(xué)學(xué)報，2011，40（1）：1-28.

[4] Son J，Jung I，Park K，et al . Tracking-by-Segmentation with Online Gradient boosting decision Tree[C]. IEEE Internatiomal Conference on Computer Vision .IEEE，2015： 3056-3064.

[5] Arthur D，Vassilvitskii S. k-means++：the advantages of careful seeding[C]Eighteenth Acm-Siam Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics，2007：1027-1035.

[6] EI-Sheimy N， Nassar S， Noureldin A . Wavelet de-noising for IMU alignment[J].IEEE Aerospace & Electronic System Magazine，2004，19（10）：32-39.

[7]朱連江，馬炳先，趙學(xué)泉. 基于輪廓系數(shù)的聚類有效性分析[J]. 計算機(jī)應(yīng)用，2010（s2）：139-141.

[8] 李曉磊，薛云燦，路飛，等. 基于人工魚群算法的參數(shù)估計方法[J]. 山東大學(xué)學(xué)報（工學(xué)版），2014，34（3）：84-87.

[9] Yao X ， Wang X， Zhang Y. Summary of feature selection algorithms [C]. International Conference on Advances in Multimedia Modeling. Spring-Verlag， 2012：452-462.

[10]譚滿春，馮牽斌，徐建閩. 基于ARIMA與人工神經(jīng)網(wǎng)絡(luò)組合模型的交通流預(yù)測[J]. 中國公路學(xué)報，2007，20（4）：118-121.

【通聯(lián)編輯：唐一東】