基于DBSCAN算法的浮動車數據預處理

張 昀，李小龍

(東華理工大學測繪工程學院，330013，南昌)

0 引言

浮動車一般是指行駛在城市道路上并安裝了車載GPS定位裝置的公交車或出租車。在浮動車行駛過程中，車載GPS會定期記錄該車輛的位置、方向和速度等信息，這些信息集合稱為浮動車數據。隨著城市里出租車數量的和運營里程的不斷增加，聚集了海量的浮動車數據。通過挖掘浮動車數據，可以得到城市道路特征和城市交通特征等信息[1]。

高質量數據是數據挖掘的重要保證，“臟數據”會導致輸出錯誤。因此，數據預處理已成為人們提高數據挖掘質量的主要研究方向之一。臟數據是指原始數據超出指定范圍或對于后續的應用毫無意義的數據，或者是數據有缺失[2]。原始浮動車數據的觀測誤差主要來源于多路徑效應、大氣延遲和衍射等方面。多路徑效應廣泛存在于各類復雜交通環境中，特別是在高樓聳立的城市經濟中心和交錯復雜的立交橋區域，高層建筑和立交橋都會成為反射物，干擾衛星信號的接收，產生衍射誤差[3]。另外，高壓電力線、電塔和避雷針對GPS信號也會有較大的影響[4]。上述誤差的存在將嚴重影響浮動車數據的質量，造成浮動車數據點軌跡漂移，從而降低數據挖掘的效果。因此，數據預處理方法研究意義重大，同時也面臨諸多挑戰[5-6]。

目前，關于浮動車數據預處理的方法有很多。王德浩[7]等將浮動車數據轉換為多分辨率軌跡圖像，然后使用數學形態濾波的方法對圖像進行去噪、平滑和增強處理。唐爐亮[8-9]等提出了以Delaunay三角網的三角形面積和邊長為約束條件進行浮動車數據清洗。汪宏宇[10]等提出基于小波閾值去除噪聲，并從閾值、閾值函數的選擇、小波基的選擇、小波分解層數4個方面來研究適合于浮動車數據的小波去噪算法。Liu[11]等提出一種新型時空粒子濾波器ST-PF，并將其與均值濾波器、中值濾波器、卡爾曼濾波器和原始粒子濾波器進行比較，結果表明，ST-PF在降低噪聲和提高地圖匹配性能方面更有效。Li[12]等通過自適應密度優化方法對浮動車數據進行預處理，以獲得高質量的浮動車數據。本文提出了一種基于DBSCAN算法的浮動車數據預處理方法，該算法是一種基于密度的空間聚類算法，能在具有噪聲的空間數據中發現任意形狀的簇，適用于像車道這樣的長條形。而且該算法運算速度快，精度高。

1 浮動車數據預處理

浮動車數據可在城市道路信息提取、交通分析、智慧城市研究等領域發揮重要作用。主要有以下3個方面的原因：1)覆蓋面廣，每天都有數萬輛出租車在城市的大街小巷上行駛，海量的浮動車數據布滿城市的每個車道，因此其產生的時空數據可以基本覆蓋整個城市；2)實時性強，道路上行駛的浮動車以40 s左右的頻率24 h不間斷采集數據，并實時上傳到交通管理中心；3)數據量大，例如武漢市有1.2萬多輛出租車每天可以產生4 000萬條數據[13-14]。由于采集環境和采集設備等限制，使得原始浮動車數據中含有大量噪聲，因此需要對其進行預處理，流程如圖1所示。

圖1 數據預處理流程圖

數據預處理主要是將原始浮動車數據中的經緯度越界數據、異常數據、重復數據、不完整數據和軌跡漂移點剔除，從而得到一個浮動車標準化數據集。本文根據研究內容對浮動車GPS數據制定了以下幾種處理數據的規則[15]。

1.1 剔除經緯度越界的數據

本文以武漢市為研究區域(該研究區域的地理位置是北緯N29°58′～31°22′，東經E113°41′～115°05′即一個矩形)，在數據庫中剔除超過武漢市城區范圍的數據。浮動車數據包括當前車輛位置的緯度和經度、載客狀態、時間、行車方向、速度等信息。先新建一個數據表并把數據按相應格式導入數據表中，然后在數據表中將超出經緯度范圍的數據剔除。圖2是浮動車數據在區域內道路上的分布圖，每個圓點代表某輛浮動車在某時刻的瞬時位置。

圖2 浮動車數據在區域內道路上的分布圖

1.2 剔除異常數據

出租車載客狀態分為“0”和“1”，其中“0”代表空載，“1”代表載客。異常數據包括以下3種情況：載客狀態非“0”和“1”的數據顯然是錯誤的，此類數據應該刪除；出租車全天空載，載客狀態全天為“0”，這類數據沒有研究意義，應過濾；出租車全天載客，載客狀態全天為“1”，通常，這種情況的出現幾率幾乎為零，可能是由于設備故障或者人為因素導致的，此類數據會影響后續的分析，會導致結論錯誤，應該刪除。

1.3 剔除重復數據

重復數據是指多條數據各個字段值完全相同的一類數據，這類數據往往只有一條具有研究意義，其他數據的出現都是錯誤的。在后續的數據挖掘和分析中，多條重復數據的存在會降低算法和模型的有效性，并影響研究結果，因此應該剔除此類數據。本文在數據庫中使用SQL語句對原始數據集中的重復數據進行剔除。

1.4 剔除不完整數據

原始浮動車數據的記錄中，可能存在缺失字段的記錄，比如某條數據記錄的速度值為空。在出租車GPS數據中ID、經緯度、時間、速度、載客狀態等其中任意一個字段或多個字段的缺失對后續的數據挖掘和分析都會產生影響。因此在數據預處理時，將缺失數據的記錄全部剔除。

1.5 剔除軌跡漂移點

當浮動車行駛在高樓大廈或立交橋附近時，或者車載GPS發生故障，都會導致GPS軌跡數據漂移。采取DBSCAN聚類算法找出軌跡漂移點并將其剔除。DBSCAN是一種基于密度的聚類算法[17-18]。該算法的聚類過程是將密度相連的點集合為簇，直到所有的數據都處理完畢，可以得到最后的聚類結果簇。DBSCAN算法可以在具有噪聲的空間數據集中找到任意形狀的聚類結果簇，并將每個樣本點分為核心點、邊界點和噪聲點[19]。因此，該算法近年來受到廣泛關注，并被應用到圖像處理和數據清洗(雙酚A生產數據清洗)等領域中[20]。本文以浮動車的緯度和經度數據作為樣本，找出浮動車數據中的漂移點。

采用DBSCAN算法對浮動車數據進行剔除軌跡漂移點處理，主要的參數為Eps和MinPts。Eps領域意指某點以Eps為半徑的領域。MinPts(領域密度閾值)是指某點Eps領域內點的數量。這2個參數對聚類效果影響很大，即使細微的變化，也會對結果產生很大的影響。當前，對這2個參數的選擇無有效依據，只能通過個人經驗或多次實驗來確定。如圖3所示，當MinPts=6，則點A為核心點，點B為邊界點,點C為噪聲點。其中對于浮動車數據分布密度高的區域， Eps鄰域包含的點數大于或等于MinPts值，而對于浮動車數據分布密度低的區域，Eps鄰域包含的點數小于MinPts值。由于DBSCAN算法能將這兩類點快速準確的區分開，因此本文采用DBSCAN算法剔除軌跡漂移點。該算法具有聚類速度快且能夠有效識別噪聲點、能發現任意形狀(非凸，互相包絡，長條形等)的空間聚類、不需要指定簇的個數等優點。

圖3 核心點、邊界點和噪聲點示意圖

2 實驗結果與討論

對采集到的武漢市浮動車數據進行篩選后，在研究區域內隨機選取了50條寬度不同的道路進行實驗。首先在數據庫中進行經緯度越界數據剔除、異常數據剔除、重復數據剔除、剔除不完整數據等處理。接著將處理后的數據可視化，如圖4所示，圖中單個點代表某輛出租車在某個時刻的位置，細的線條為道路中心線，粗的線條為道路邊界線，道路邊界線是參考百度地圖街景上與之相對應的車道寬度繪制出來的。從圖4中可以看出，浮動車數據基本服從高斯分布，越接近道路中心線的浮動車數據分布越密集，越往兩側分布越稀疏。這些浮動車數據的分布寬度明顯要大于車道的實際寬度，表明這些浮動車數據中存在大量漂移點。

將2條道路上的浮動車數據分別存入Excel表，在MATLAB中寫好的DBSCAN算法，設置參數，導入Excel表中的數據，運行程序。結果如圖5所示，圖5中“+”是核心點表示合格的浮動車數據，“·”是噪聲點表示浮動車數據中的軌跡漂移點。

(a) 道路1

(b) 道路2

(a) 道路1

(b) 道路2

將處理后得到的浮動車數據與原始的浮動車數據進行對比，如圖6所示，圖6中密集圓點代表清洗后被清除的浮動車數據點，散布圓點代表清洗后剩余的浮動車數據點。從圖6中可以明顯看出，經過DBSCAN算法清洗后的浮動車數據大部分都分布在道路邊界線以內，而清洗前的浮動車數據中有較多數據分布在道路邊界線以外。

(a) 道路1

(b) 道路2

為了進一步驗證算法的準確性，在50條道路中隨機選取了2條道路并分別計算這2條道路清洗前后的浮動車數據的擬合度和準確率。擬合度指的是回歸直線對觀測值的擬合程度。可決系數R2是度量擬合度的統計量，R2最大值為1，R2越接近1說明回歸直線對觀測值的擬合程度越好，反之越差。由于浮動車數據中含有漂移點，漂移點會導致浮動車數據分布較散，即擬合度較低。可決系數的公式如式(1)所示：

(1)

其中：SSR是指回歸平方和，SSE是指殘差平方和，SST是指總離差平方和。

準確率指在道路邊界線內的浮動車數據占道路上的浮動車數據的比例，準確率越高，表明道路上的浮動車數據中在道路邊界線內的浮動車數據占比越高，清洗效果越好。準確率的公式如式(2)所示：

(2)

道路1和道路2清洗前后的擬合度和準確率如表1所示。從表1可知道路1和道路2的浮動車數據清洗后的擬合度比清洗前有明顯提高，但準確率相比之前提高不明顯。原因是在浮動車數據預處理中的前幾步已經把大量低質量的浮動車數據剔除，而基于DBSCAN聚類算法剔除的漂移點相對較少。因此，可以證明本文提出的算法能夠有效清洗浮動車數據中的漂移點。

表1 道路1和道路2清洗前后的擬合度和準確率

參數的不同，對數據的聚類效果也會有差異。DBSCAN的參數有Eps和MinPts 2個，其中Eps可以通過epsilon函數計算出來，因此只需調整參數MinPts。

%epsilon函數的功能：

%[eps]=epsilon(x,MinPts)

%目的：求解DBSCAN估計領域半徑

%x- data matrix(m,n);m-精度，n-緯度

%MinPts - 鄰域密度閾值

[m,n]=size(x);

Eps=((prod(max(x)-min(x)) * MinPts * gamma (.5 *n+1))/(m*sqrt(pi.^n))).^(1/n)

圖7 不同的MinPts值對擬合度和準確率影響變化折線圖

圖7是不同的MinPts值對擬合度和準確率影響變化折線圖，圖7中橫坐標是MinPts的數值，縱坐標是擬合度和準確率的值。從圖7中可知，當MinPts值為1時，擬合度和準確率最高。當MinPts值為5和6時，擬合度和準確率最低而且相等。因此，選擇MinPts值為1對浮動車數據進行處理。隨著MinPts值的增大，一些漂移點被誤判為合格的浮動車數據，隨著合格的浮動車數據逐漸飽和，其擬合度和準確率將趨于穩定，不再發生改變。

3 總結與展望

分析了目前國內外浮動車數據預處理方法的基礎上，提出了一種基于DBSCAN密度聚類算法的浮動車數據預處理方法。實驗結果表明，該方法利用浮動車數據的空間分布特征成功剔除了浮動車數據中的大部分漂移點，且操作簡單，運算速度快，準確率高。然而，此方法對十字路口和復雜交通路口的預處理效果不夠理想。在未來的研究中將會對該方法做相應改進，并將進一步研究如何從浮動車數據中獲取當前道路的交通狀況和車道數量。