張 昀，李小龍

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

0 引言

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

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

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

1 浮動(dòng)車數(shù)據(jù)預(yù)處理

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

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

數(shù)據(jù)預(yù)處理主要是將原始浮動(dòng)車數(shù)據(jù)中的經(jīng)緯度越界數(shù)據(jù)、異常數(shù)據(jù)、重復(fù)數(shù)據(jù)、不完整數(shù)據(jù)和軌跡漂移點(diǎn)剔除，從而得到一個(gè)浮動(dòng)車標(biāo)準(zhǔn)化數(shù)據(jù)集。本文根據(jù)研究內(nèi)容對浮動(dòng)車GPS數(shù)據(jù)制定了以下幾種處理數(shù)據(jù)的規(guī)則[15]。

1.1 剔除經(jīng)緯度越界的數(shù)據(jù)

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

圖2 浮動(dòng)車數(shù)據(jù)在區(qū)域內(nèi)道路上的分布圖

1.2 剔除異常數(shù)據(jù)

出租車載客狀態(tài)分為“0”和“1”，其中“0”代表空載，“1”代表載客。異常數(shù)據(jù)包括以下3種情況：載客狀態(tài)非“0”和“1”的數(shù)據(jù)顯然是錯(cuò)誤的，此類數(shù)據(jù)應(yīng)該刪除；出租車全天空載，載客狀態(tài)全天為“0”，這類數(shù)據(jù)沒有研究意義，應(yīng)過濾；出租車全天載客，載客狀態(tài)全天為“1”，通常，這種情況的出現(xiàn)幾率幾乎為零，可能是由于設(shè)備故障或者人為因素導(dǎo)致的，此類數(shù)據(jù)會(huì)影響后續(xù)的分析，會(huì)導(dǎo)致結(jié)論錯(cuò)誤，應(yīng)該刪除。

1.3 剔除重復(fù)數(shù)據(jù)

重復(fù)數(shù)據(jù)是指多條數(shù)據(jù)各個(gè)字段值完全相同的一類數(shù)據(jù)，這類數(shù)據(jù)往往只有一條具有研究意義，其他數(shù)據(jù)的出現(xiàn)都是錯(cuò)誤的。在后續(xù)的數(shù)據(jù)挖掘和分析中，多條重復(fù)數(shù)據(jù)的存在會(huì)降低算法和模型的有效性，并影響研究結(jié)果，因此應(yīng)該剔除此類數(shù)據(jù)。本文在數(shù)據(jù)庫中使用SQL語句對原始數(shù)據(jù)集中的重復(fù)數(shù)據(jù)進(jìn)行剔除。

1.4 剔除不完整數(shù)據(jù)

原始浮動(dòng)車數(shù)據(jù)的記錄中，可能存在缺失字段的記錄，比如某條數(shù)據(jù)記錄的速度值為空。在出租車GPS數(shù)據(jù)中ID、經(jīng)緯度、時(shí)間、速度、載客狀態(tài)等其中任意一個(gè)字段或多個(gè)字段的缺失對后續(xù)的數(shù)據(jù)挖掘和分析都會(huì)產(chǎn)生影響。因此在數(shù)據(jù)預(yù)處理時(shí)，將缺失數(shù)據(jù)的記錄全部剔除。

1.5 剔除軌跡漂移點(diǎn)

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

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

圖3 核心點(diǎn)、邊界點(diǎn)和噪聲點(diǎn)示意圖

2 實(shí)驗(yàn)結(jié)果與討論

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

將2條道路上的浮動(dòng)車數(shù)據(jù)分別存入Excel表，在MATLAB中寫好的DBSCAN算法，設(shè)置參數(shù)，導(dǎo)入Excel表中的數(shù)據(jù)，運(yùn)行程序。結(jié)果如圖5所示，圖5中“+”是核心點(diǎn)表示合格的浮動(dòng)車數(shù)據(jù)，“·”是噪聲點(diǎn)表示浮動(dòng)車數(shù)據(jù)中的軌跡漂移點(diǎn)。

(a) 道路1

(b) 道路2

(a) 道路1

(b) 道路2

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

(a) 道路1

(b) 道路2

為了進(jìn)一步驗(yàn)證算法的準(zhǔn)確性，在50條道路中隨機(jī)選取了2條道路并分別計(jì)算這2條道路清洗前后的浮動(dòng)車數(shù)據(jù)的擬合度和準(zhǔn)確率。擬合度指的是回歸直線對觀測值的擬合程度?？蓻Q系數(shù)R2是度量擬合度的統(tǒng)計(jì)量，R2最大值為1，R2越接近1說明回歸直線對觀測值的擬合程度越好，反之越差。由于浮動(dòng)車數(shù)據(jù)中含有漂移點(diǎn)，漂移點(diǎn)會(huì)導(dǎo)致浮動(dòng)車數(shù)據(jù)分布較散，即擬合度較低?？蓻Q系數(shù)的公式如式(1)所示：

(1)

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

準(zhǔn)確率指在道路邊界線內(nèi)的浮動(dòng)車數(shù)據(jù)占道路上的浮動(dòng)車數(shù)據(jù)的比例，準(zhǔn)確率越高，表明道路上的浮動(dòng)車數(shù)據(jù)中在道路邊界線內(nèi)的浮動(dòng)車數(shù)據(jù)占比越高，清洗效果越好。準(zhǔn)確率的公式如式(2)所示：

(2)

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

表1 道路1和道路2清洗前后的擬合度和準(zhǔn)確率

參數(shù)的不同，對數(shù)據(jù)的聚類效果也會(huì)有差異。DBSCAN的參數(shù)有Eps和MinPts 2個(gè)，其中Eps可以通過epsilon函數(shù)計(jì)算出來，因此只需調(diào)整參數(shù)MinPts。

%epsilon函數(shù)的功能：

%[eps]=epsilon(x,MinPts)

%目的：求解DBSCAN估計(jì)領(lǐng)域半徑

%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值對擬合度和準(zhǔn)確率影響變化折線圖

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

3 總結(jié)與展望

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