基于支持向量聚類和模糊粗糙集的交通流數據修復方法

朱世超，王騁程，王超，劉隆，張潤芝,3，王浩,3

(1.山東高速基礎設施建設有限公司，濟南 250000；2.山東省交通規劃設計院集團有限公司，濟南 250000；3.山東高速濟濰高速公路有限公司，濟南 250000)

0 引言

環路檢測器與視頻、藍牙和裝有全球定位系統(Global Positioning System, GPS)設備的浮動車輛等傳統的交通數據收集方法相比，其檢測成本低的優勢在交通流量數據檢測中被廣泛使用。然而，這些技術檢測出來的數據可能會由于天氣因素、數據傳輸中的延遲和錯誤，以及數據丟失等因素的影響[1-4]而出現數據異常、缺失等情況。交通流數據的完整性是交通流預測、交通運行狀態分析和路網通行能力分析的基礎，交通數據的缺失必將影響分析結果的合理性及其在智能交通系統(Intelligent Transportation System, ITS)中應用的可行性[5]。因此，如何從龐大的交通大數據系統中獲得真實、準確的信息來反映交通狀態是研究者們目前面臨的重要問題。

為提高交通模型輸入數據的準確性，國內外學者建立了許多模型對交通數據進行預處理。當前，國外關于數據修復方面的研究可以歸納為4個方面，分別以傳統模型、統計相關模型、機器學習模型和粗糙集模型為基礎。傳統方法的結構簡單且易于計算，估計性能主要取決于交通流數據中的相似性特征，然而交通流的短期波動表現使得相似性并不顯著，因此傳統方法的估算性能常常不盡如人意；與傳統方法相比，統計模型通常以其合理的數學結構表現出良好的歸因性能，并且在交通流分析中具有清晰的可解釋性，因此被廣泛用于數據插補中；基于機器學習的插補方法在數據不完整的情況下由于其強大的學習能力而表現出較高的歸因或預測性能，也成為了一種典型的交通流缺失數據處理方法；以粗糙集模型為基礎的數據修復方法，其中模糊粗糙集(Fuzzy Rough Set, FRS)是在數據集不完整的情況下進行分類和預測的有效方法[6-9]。模糊粗糙集融合了粗糙集和模糊集的優勢，通常表現出較強的能力來表示原始數據集中的不確定性和模糊性。然而，無監督學習機制使得模糊粗糙集的學習能力相對有限，導致其應用的推算或預測結果可能并不理想。一些神經模糊推理系統是為分類而設計的，很少有方法可以使用該系統來估算缺失的數據[10-12]。

在國內方面，隨著交通智能化的不斷發展，數據質量的問題引發了越來越多研究人員的關注。國內相關學者認為，首先應該充分了解數據丟失的過程，然后根據數據丟失的形式采取對應的修復模型。針對不同情況的數據缺失，選擇不同的數據修復方法及模型可以更好地提高修復的準確度[13-14]。此外，交通流數據之間的空間相關性逐漸受到重視。鄒海翔等[15]利用插值法對交通數據進行空間建模，以空間距離作為度量基準對未知路段交通數據進行估計。一些學者同樣在探索使用基于粗糙集的修復方法以提高數據質量。于洪等[16]考慮具有不同丟失值的數據的相關性，結合粗糙集理論提出了一種基于時空權重的交通流數據的重構模型，利用北京二環高速公路的數據完成了仿真建模。

盡管目前大量工作側重于對丟失的交通流數據進行插補，但是如何快速準確地估計丟失值，尤其是在高丟失率下，仍然是在ITS應用中實現交通流精確預測和合理分析的挑戰。為了克服交通數據中強隨機性對插補性能的影響，將機器學習框架和交通流理論相結合被證明是提高插補精度的有效方法[17-18]。在神經網絡插補的應用中，訓練過程中的參數選擇和優化是實現較高插補性能的關鍵步驟[18-19]。當支持向量機(Support Vector Machine, SVM)模型用于缺少的流量估算時，也需要解決類似的問題[21-22]。與神經網絡相比，支持向量機具有更好的擬合性能和泛化能力。因此，本研究將支持向量聚類和模糊粗糙集相結合，并結合模糊神經網絡和遺傳算法建立了一個混合模型來估算丟失的交通流數據，結合粗糙集和神經模糊系統的混合模型可以在不完整的數據集下訓練模型，并可以估計缺失值的近似間隔。該混合模型結合粗糙集處理不確定性的優點和在神經模糊網絡中具有監督學習過程的強大學習能力，并增強了圖像識別中的聚類性能。因此，可以提高交通流數據中缺失值估算的準確性和穩定性。最后以高速公路的實測交通流數據為例對模型的性能進行驗證。

1 粗糙支持向量聚類分類模型

1.1 粗糙集

粗糙集理論提供了一種依靠模糊和不精確的數據推理的技術，由Pawlak[23]于1982年提出。從可用信息的角度來看，具有相同信息的對象是不可分辨的。由不可分辨的物體組成的基本集形成了知識的基本粒子。基本集合的聯合被稱為清晰集合，否則該集合被認為是粗糙的。

(1)

(2)

式中：X為研究的論域；x為X中的一個對象；[x]R表示所有與x不可分辨的對象所組成的集合；?為空集。

粗糙度是指上部和下部近似之間的差異，集合A的粗糙度是通過等價關系R來定義的，定義如下。

(3)

1.2 支持向量聚類

在支持向量聚類中[24]，用核函數變換實現將數據點從平面空間映射到高維的特征空間。在高維特征空間上，尋找囊括所有數據點的最小空間球體。然后將此球映射到平面空間，則它將形成一些可以包圍數據點的形狀。內核參數可以控制群集的數量。在這里，借助軟邊距公式來處理異常值。

為了定義公式，令{xi}?X是具有m個點的多維數據集，數據空間為xi∈Rd。使用從X到某個高維空間的非線性變換φ，尋找包含X的所有點的最小半徑R的球體。原始問題表達公式為

(4)

由于這是一個凸二次規劃問題，因此很容易解決它的Wolfe對偶形式

s.t. 0≤?i≤Ci=1,2,…,m；

(5)

式中：K(xi,xj)表示核函數，給出了高維空間中的點積φ(xi)·φ(xj);?i的值決定點φ(xi)是在球體內還是球體外；0

R={G(xi)：0

(6)

現在，由{x/G(x)=R}定義了包圍數據空間中點的輪廓。因此，借助核函數，避免了在高維空間中進行計算以及在數據空間中查找輪廓的反向映射。一旦找到這些輪廓，就按以下步驟完成聚類分配。根據觀察結果，其采用涉及G(x)的幾何方法：給定一對屬于不同聚類的點，連接其任何路徑都必須從特征空間的球體中退出。因此，可以通過將其連接在特征空間中的球面之中或之上的點xi和xj對之間定義鄰接矩陣M，將其連接到的路徑的圖像定義為

(7)

式中，y表示xi，xj連線上的點；?表示為對任意的屬于xi，xj連線上的點y。

將聚類定義為由M誘導的圖的連接部分，可以將球外的點(有界支持向量)分配給最接近的聚類。

1.3 粗糙支持向量聚類

在支持向量模型的基礎上，遵循粗糙集的概念，粗糙球體為具有下近似的內半徑(R)和上近似的外半徑(T)，并且T>R的球體。與支持向量聚類(Support Vector Clustering, SVC)中一樣，粗糙支持向量聚類(Rough Support Vector Clustering, RSVC)還通過使用內核函數來實現平面數據映射到高維空間。其試圖在高維空間中找到內外半徑最小的粗糙球體，將數據集中所有點的圖像封閉起來。現在，那些圖像位于較低近似范圍內的點是肯定屬于一個群集(群集的核心)的點，而圖像位于邊界區域(位于較高近似范圍內但不在較低近似范圍內的那些點)被稱為由多個群集(群集的軟核)共享。某些點被允許位于球外，被稱為離群值。

利用非線性變換方法，將數據從平面映射到某些高維空間，尋找內近似半徑(R)和外近似半徑(T)的最小封閉粗糙球體。原始問題表達公式為

0≤ξi≤T2-R2,ξi′≥0，i=1，2，…，m。

(8)

為了解決這個問題，找到在SVC中的Wolfe對偶形式，所以拉格朗日可以寫成

(9)

式中：αi≥0,βi≥0,λi≥0,ηi≥0 ，i=1，2，…，m。

應用KKT條件，可以得到

(10)

(11)

(12)

(13)

補充松弛條件為

(14)

λi(ξi-T2+R2)=0。

(15)

βiξi=0。

(16)

ηiξi′=0。

(17)

從以上等式可以將Wolfe對偶形式寫為

(18)

可以觀察到，當δ>1，采用RSVC公式；當δ=1時，其退化為原始SVC公式。 從公式(12)和公式(13)可以看出，αi的值決定了圖案xi是否落在較低近似值，邊界區域或特征空間粗糙球之外。

其來自表示點的圖像公式(12)—公式(18)。

(1)αi=0處于較低近似值。

第二步：查找圖形的連接組件。通過查找圖形的連接組件，給出每個簇的較低近似值。

第三步：尋找邊界區域。對于任何聚類j，對于xi∈下近似(Ci)和xk?下近似(Cj)：G(y)≤T，?y∈[xi,xk]，則xk?邊界區域(Ci)。

2 模糊神經網絡和遺傳算法數據補齊模型

2.1 模糊推理系統

模糊推理系統[25]基于模糊規則庫實現模糊推理。通常規則表示為

Rr：如果x是Ar,那么y是Br。

(19)

式中：x是對象或狀態；y=[y1,y2,…,ym]是輸出語言變量；Ar是規則r的前置部分使用的模糊集；Br是規則r后置中使用的模糊集；r=1,…,N；N是規則數；m是輸出語言變量的數。

假設ε=[ε1,ε2,…,εn]是描述任何對象或狀態的特征的向量，n是輸入語言變量的數量。將對象的隸屬函數及其特征等同起來，可以將規則(19)記為

Rr：如果ε是Ar,那么y是Br。

(20)

(21)

(22)

接下來枚舉幾組模糊蘊含

S-模糊蘊含：I(a,b)=S{N{a},b}；

R-模糊蘊含：I(a,b)=supz∈[0,1]{z|Г{a,z}≤b}；

QL-模糊蘊含：I(a,b)=S{N{a},Г{a,b}}；

D-模糊蘊含：I(a,b)=S{Г{N{a},N{b}},b}。

其中a,b∈[0,1]，Г是任何t-范數，S是任何t-范數，N是任何模糊否定。

2.2 模糊神經網絡

將模糊推理模型和神經網絡系統進行集計可以構成模糊神經網絡[21-22](Fuzzy Neural Network, FNN)，實際上是將常規的神經網絡模型輸入模糊的信號和權值，其結構如圖1所示。

圖1 標準模糊神經網絡結構Fig.1 Structure of a standard fuzzy neural network

將模糊推理系統與自適應神經網絡集計在一起，該組合系統更加可以發揮這2個模型的優勢，彌補了這2個模型的不足。該系統的框架如下。

第1層：通過計算輸入信號的隸屬函數的值來模糊輸入信息，一般模型使用的隸屬度函數是高斯函數，其計算公式為

(23)

式中：xa是節點a的輸入；高斯函數的形狀由參數c和b決定，c、b分別是隸屬函數形狀的中心值和寬度，被稱為前件參數。

第2層：強度釋放層。變量x與模糊集A的隸屬度定義為

μA(r)(X)=μa1(r)(x1)·μa2(r)(x2)…μaA(r)(xA)=∑a∈Aμa(r)(xa)。

(24)

式中，r是模糊規則。

第3層：對所有規則信息強度進行歸一化處理操作。在神經網絡的每個節點處根據模糊規則r下計算歸一化可信度

(25)

式中，R是規則庫。

第4層：計算在模糊規則r下的每個節點的輸出信號。第4層的每個輸出信號均是擁有自適應性質的節點，其輸出結果為

f(r)(X)=g(r)(X)·y(r)(X)。

(26)

y(r)(X)=pT·[1,X]T=[p0(r),p1(r),…,pA(r)]·[1,x1,…,xA]T。

(27)

其中，g(r)(X)是第3層歸一化可信度的輸出；p是第4層上每個節點的參數集，稱為后置參數。

第5層：計算所有信號的總輸出。該層是一個固定節點，其計算如下

(28)

2.3 模糊神經網絡和遺傳算法數據補齊

在利用粗糙支持向量聚類進行數據分類之后，獲得了各個分類的上下中心，然后結合模糊神經網絡和遺傳算法進行缺失數據的補齊，具體的修復步驟如下。

(1)使用模糊神經網絡訓練完整數據集，輸入數據組X，輸出的數據組為Y。

(3)使用遺傳算法獲得優化的參數c和m，最小化粗糙支持向量與模糊神經網絡兩者輸出之間的差異，使用帶有優化參數的支持向量補齊缺失。

(4)將結果與模糊神經網絡輸出的結果進行對比。

3 交通流數據修復模型

本研究建立的模型框架如圖2所示。該框架由3個模塊組成。首先，通過粗糙集和支持向量聚類相結合來進行交通流數據的分類，設定初始的上下c、m參數，利用加權因子法獲得缺失數據的補齊值。然后，利用模糊神經網絡進行數據的預測獲得的數據與前面的數據進行對比，然后利用遺傳算法優化參數，減小修復誤差，獲得最優參數。

4 實例分析

4.1 數據準備

本論文使用的交通流數據是高速公路上利用線圈探測器采集的交通量數據，共計120 d，時間是2011年1月至2011年4月。在圖3中顯示了1月3日至1月7日不同時間間隔(5、10、30、60 min)的交通流量數據分布。

根據缺失的位置的分布情況，可以將數據缺失形式分為隨機丟失、連續丟失和系統丟失，3種丟失形式的示意圖如圖4所示。

圖2 基于支持向量聚類和模糊粗糙集的交通流數據修復框架圖Fig.2 Framework of missing data imputation for traffic flow based on SVC and fuzzy rough set

圖3 在相鄰的5 d內以不同的時間間隔收集的流量數據折線圖Fig.3 Graphs of traffic data collected at different time intervals during the five adjacent days

4.2 粗糙支持向量聚類分類結果

利用建立的粗糙支持向量聚類模型進行交通流數據的分類，在數據以不同時間間隔收集的情況下獲得的分類結果如圖5所示。

在圖5中，交通流數據總共分成了3類，分別以橙色、藍色和粉色為中心，球形的上近似半徑和下近似半徑形成了輪廓包圍了這3個中心。可以通過設置每個分類的上下中心的權值，通過加權平均值法獲得初始缺失數據補齊值。

(a) 隨機丟失(a) Missing at random

(b) 連續丟失(b) Continuous data loss

(c) 系統丟失(c) Systematic data loss

圖5 粗糙支持向量聚類模型分類結果圖Fig.5 Classification results of the support vector clustering model with fuzzy rough sets

4.3 模糊神經網絡和遺傳算法數據補齊結果

在進行數據分類之后，結合模糊神經網絡和遺傳算法對缺失數據進行補齊，選取均方根誤差(RMSE)、相關系數(R)、相關精度(RA)3個結果評價指標，并選擇平均值法(MV)、回歸法(Regression)、基于KNN的模糊粗糙集方法(KNN-FRS)、自適應網絡的模糊推理系統(ANFIS)、支持向量機(SVM)和張量(Tensor)6個模型進行結果對比。在數據以5 min間隔收集，以不同丟失形式，不同丟失率的情況下，結果如圖6所示。

從圖6可以看出，在隨機丟失和連續丟失2種情況下(本研究中的數據丟失是對采集的完整數據集進行隨機丟失和連續丟失的模擬)，隨著數據丟失率的增加，模型的補齊結果的均方根誤差(RMSE)都增加，相關系數(R)和相對精度(RA)都減少，說明隨著數據丟失率的增加，模型的補齊效果減少。通過圖6(a)和圖6(b)可以看出，隨著丟失率增大，基于支持向量聚類和模糊粗糙集的交通流數據修復方法(FRS-SVR)的結果均小于其他6種方法，這說明就均方根誤差這一評價指標而言，本研究所建立的交通流丟失數據補齊模型的修復效果優于其他6種對比模型。通過圖6(c)和圖6(f)中關于指標相關系數和相對精度的結果可以看出，隨著數據丟失率的增加，基于支持向量聚類和模糊粗糙集的交通流數據修復方法(FRS-SVR)的結果從總體上來說均大于其他6種方法，這說明根據相關系數和相對精度這2個評價指標的表現，本研究所建立的交通流丟失數據補齊模型的修復效果優于其他6種對比模型。

圖6 在不同丟失類型的數據集中7種方法的性能表現Fig.6 Performance of seven methods in datasets with different missing strategies

5 結論

本研究將支持向量聚類和模糊粗糙集相結合，并結合模糊神經網絡和遺傳算法建立了一個混合模型來估算丟失的交通流數據。將模糊粗糙集和支持向量聚類結合，進行不同時間間隔收集的交通流數據的分類，然后結合模糊神經網絡和遺傳算法進行缺失數據的估計。利用某高速公路收集的交通流數據用于模型性能的驗證，并使用均方根誤差、相關系數和相關精度3個指標來評估插補精度。結果表明，研究中提出的支持向量聚類和模糊粗糙集模型的插補性能比其他6種對比方法的修復性能更高。這些結果驗證了所提出的方法的有效性，也呈現出一定的局限性。例如，隨著缺失率的增加，3個評價指標的惡化程度迅速增加，這意味著模型的補齊效果降低，模型的穩定性較差。在交通系統中，一旦受到比較嚴重的影響時，交通流數據極大可能存在大范圍的丟失。因此，應做出更大的努力來提高模型的穩定性，以滿足在數據存在系統丟失的情況。此外，本研究僅考慮隨機和連續丟失數據的情況，而沒有考慮在特殊情況下(如事故情況和天氣影響)丟失數據的情況。在這種情況下，流量檢測儀器可能會完全無法檢測與記錄數據，流量數據將存在系統丟失的情況。數據系統的缺失意味著一定時間內數據會完全丟失。系統缺失的數據補齊是未來需要進一步突破的挑戰。在未來，可以考慮多個檢測器之間的時空相關性以提高插補精度，進一步考慮道路網的交通流數據之間的關系，系統地補齊交通流丟失數據，為交通道路網系統的研究提供一定的數據支持，最終可為智能交通的發展奠定數據基礎。