汪 鵬，劉澤玲，王利琴,3+，董永峰

(1.河北工業(yè)大學(xué) 人工智能與數(shù)據(jù)科學(xué)學(xué)院，天津 300401；2.河北工業(yè)大學(xué) 河北省大數(shù)據(jù)計(jì)算重點(diǎn)實(shí)驗(yàn)室，天津 300401；3.河北工業(yè)大學(xué) 河北省數(shù)據(jù)驅(qū)動(dòng)工業(yè)智能工程研究中心，天津 300401)

0 引 言

在公交車(chē)載GPS設(shè)備定位過(guò)程中，GPS數(shù)據(jù)的誤差來(lái)源分為GPS定位系統(tǒng)的內(nèi)部原因和外部原因，內(nèi)部原因包括信號(hào)傳播途徑問(wèn)題、GPS衛(wèi)星相關(guān)問(wèn)題和用戶接受設(shè)備問(wèn)題。外部原因主要包括公交車(chē)自身行駛特性、城市道路路況和諸多隨機(jī)因素(天氣狀況、網(wǎng)絡(luò)延遲、行駛速度等)。這些誤差是GPS數(shù)據(jù)產(chǎn)生大量噪聲點(diǎn)的主要原因，降低了由GPS數(shù)據(jù)生成公交行駛路線的準(zhǔn)確度和可靠性，為減小噪聲點(diǎn)對(duì)生成路線的影響，提高生成路線的準(zhǔn)確度，需要剔除異常的GPS數(shù)據(jù)。

在數(shù)據(jù)點(diǎn)噪聲處理領(lǐng)域，相關(guān)學(xué)者在基于聚類(lèi)算法過(guò)濾噪聲點(diǎn)等方向提出大量的算法。Yang L等提出了基于自然近鄰的ENaN算法[1]，根據(jù)樣本點(diǎn)近鄰，尋找各數(shù)據(jù)點(diǎn)的反向最近鄰。ENaN根據(jù)樣本點(diǎn)是否具有反向最近鄰來(lái)判斷該點(diǎn)是否為噪聲點(diǎn)，雖然通過(guò)這種方法實(shí)現(xiàn)了聚類(lèi)效果，但對(duì)于噪聲量較大的數(shù)據(jù)集聚類(lèi)效果往往較差甚至無(wú)法完成聚類(lèi)過(guò)程；Hao SX等提出了一種基于噪聲的應(yīng)用空間密度聚類(lèi)(DBSCAN)和支持向量數(shù)據(jù)描述(SVDD)的噪聲數(shù)據(jù)檢測(cè)方法[2]；張靖等提出一種基于空間和時(shí)間密度的抗噪聲聚合算法(DBS&TCAN)[3]；李強(qiáng)等通過(guò)過(guò)濾低密度區(qū)域的方法優(yōu)化了DBSCAN算法[4]，在處理海量GPS軌跡數(shù)據(jù)時(shí)有效得到了稠密樣本點(diǎn)；Bryant A等提出的RNN-DBSCAN算法通過(guò)K最近鄰點(diǎn)的選擇實(shí)現(xiàn)了單個(gè)參數(shù)聚類(lèi)[5]，從而降低了聚類(lèi)的復(fù)雜度，并且提升了簇分布不均勻的數(shù)據(jù)集的聚類(lèi)效果；黃子赫等提出了BCS-DBSCAN聚類(lèi)算法，該算法可以對(duì)軌跡數(shù)據(jù)切分及并行化聚類(lèi)且能夠有效去除噪聲點(diǎn)提取最大密度簇心[6]。然而上訴方法均不適用于數(shù)據(jù)量較大的去噪處理。雖然DBSCAN在聚類(lèi)速度上具有優(yōu)勢(shì)并且對(duì)于有冗余點(diǎn)的數(shù)據(jù)集也可以很好的聚類(lèi)，但是，當(dāng)數(shù)據(jù)量龐大時(shí)，DBSCAN算法時(shí)間復(fù)雜度較高。

Eps和MinPts是DBSCAN算法中用來(lái)描述數(shù)據(jù)點(diǎn)分布密度的兩個(gè)全局參數(shù)，直接影響到聚類(lèi)效果，合理的取值會(huì)顯著提高聚類(lèi)效果，因此聚類(lèi)參數(shù)的自適應(yīng)調(diào)整成為了眾多學(xué)者研究的方向。Jian Hou等提出了一種基于DSets(優(yōu)勢(shì)集)和DBSCAN的無(wú)參數(shù)算法——Dsets-DBSCAN[7]；Ankush Sharma等提出了KNN-DBSCAN無(wú)參數(shù)密度聚類(lèi)[8]，將K近鄰學(xué)習(xí)與DBSCAN一起使用以實(shí)現(xiàn)無(wú)參數(shù)聚類(lèi)技術(shù)；蔣華等針對(duì)CURE算法聚類(lèi)過(guò)程中對(duì)噪音點(diǎn)敏感、聚類(lèi)效率欠佳問(wèn)題，提出了一種基于MeanShift核函數(shù)平移模型DBSCAN算法改進(jìn)的CURE算法[9]。其中基于路徑最短原則的密度自適應(yīng)參數(shù)的DBSCAN算法提高初步聚類(lèi)精度和可靠性。但上述算法只適用于數(shù)據(jù)集單一、參數(shù)相同的場(chǎng)景，而公交車(chē)GPS數(shù)據(jù)集包含不同線路的所有數(shù)據(jù)，不同線路具有不同的數(shù)據(jù)密度，因此需使用不同的參數(shù)。

本文對(duì)Eps和MinPts參數(shù)進(jìn)行動(dòng)態(tài)選擇，有效解決了在不同線路公交車(chē)GPS數(shù)據(jù)聚類(lèi)過(guò)程中，因固定輸入?yún)?shù)在不同線路的非普適性而導(dǎo)致的聚類(lèi)結(jié)果偏差較大、聚類(lèi)效果差的問(wèn)題。同時(shí)為提高DBSCAN算法執(zhí)行速度，本文提出一種基于像素格的PB-DBSCAN算法，該算法將聚類(lèi)過(guò)程中判斷數(shù)據(jù)點(diǎn)與其它數(shù)據(jù)點(diǎn)的關(guān)系改為判斷當(dāng)前像素格與相鄰像素格之間的關(guān)系，相較于傳統(tǒng)DBSCAN算法降低了時(shí)間復(fù)雜度，尤其在數(shù)據(jù)量較大時(shí)，算法效率有極大提升。

1 PB-DBSCAN算法

DBSCAN是Ester等提出的第一個(gè)基于密度的聚類(lèi)算法。該算法以數(shù)據(jù)集在空間分布上的稠密程度為依據(jù)進(jìn)行聚類(lèi)，將密度相連的點(diǎn)的最大集合定義為簇，DBSCAN對(duì)數(shù)據(jù)集的大小沒(méi)有限制且無(wú)需預(yù)先設(shè)定簇的數(shù)量，適合于對(duì)未知內(nèi)容的數(shù)據(jù)集進(jìn)行聚類(lèi)。

Eps和MinPts是DBSCAN算法的兩個(gè)全局參數(shù)，其中，Eps代表聚類(lèi)半徑，表示目標(biāo)點(diǎn)周?chē)徲驍?shù)據(jù)點(diǎn)數(shù)的搜索半徑，MinPts代表聚類(lèi)密度，用于判斷搜索區(qū)域是否滿足簇要求的最小點(diǎn)數(shù)。任選一個(gè)未被檢查過(guò)的點(diǎn)，檢查其Eps鄰域，若包含的點(diǎn)的數(shù)目不小于MinPts，則該點(diǎn)與其鄰域的點(diǎn)形成一個(gè)簇，標(biāo)記該點(diǎn)為核心點(diǎn)，然后以相同的方法處理該簇內(nèi)所有未被檢查的點(diǎn)，從而對(duì)簇進(jìn)行擴(kuò)展；若包含的點(diǎn)的數(shù)目小于MinPts，但該點(diǎn)本身在某一個(gè)簇內(nèi)，則該點(diǎn)標(biāo)記為邊緣點(diǎn)，否則該點(diǎn)被標(biāo)記為噪聲點(diǎn)。

圖1 像素格

1.1 構(gòu)建像素格

首先遍歷數(shù)據(jù)集中的所有點(diǎn)，找到這些點(diǎn)的橫縱坐標(biāo)的最大值和最小值，從而確定像素格空間X軸和Y軸值的范圍，然后再將X軸、Y軸等分，將整個(gè)像素格空間劃分為m行n列的小像素格

(1)

(2)

將每個(gè)GPS數(shù)據(jù)點(diǎn)根據(jù)其橫縱坐標(biāo)數(shù)值劃分到相應(yīng)的像素格單元中，如圖1所示。

1.2 確定核心點(diǎn)

遍歷所有的非空像素格，判斷當(dāng)前像素格內(nèi)的點(diǎn)數(shù)是否大于MinPts，如果是，則將該像素格內(nèi)的所有點(diǎn)標(biāo)記為核心點(diǎn)，否則遍歷該像素格內(nèi)的所有點(diǎn)，逐個(gè)判斷其是否為核心點(diǎn)。假設(shè)一個(gè)點(diǎn)p，屬于單元格C，則要確定點(diǎn)p是否是核心點(diǎn)，需要檢查p點(diǎn)所在像素格的相鄰像素格內(nèi)的點(diǎn)。將p點(diǎn)所在像素格的相鄰像素格表示為C′，NEps(C) 定義為像素格單元C及其相鄰的像素格單元C′的集合，如果C與C′之間存在兩點(diǎn)之間的距離小于Eps，那么C′為C的一個(gè)相鄰像素格，如式(3)所示，dist(C,C′) 表示C和C′內(nèi)任意數(shù)據(jù)點(diǎn)之間的最短距離

(3)

NEps(C)={C,C′|dist(C,C′)≤Eps}

(4)

如圖1陰影部分所示，NEps(C) 由和C相鄰的20個(gè)像素格組成。遍歷這些像素格中的每個(gè)點(diǎn)，計(jì)算其與點(diǎn)p之間的距離，直到所有的點(diǎn)都已遍歷，或點(diǎn)p的Eps鄰域內(nèi)點(diǎn)數(shù)大于等于MinPts，終止查找。

1.3 合并簇

對(duì)于兩個(gè)不同的像素格，如果分別位于兩個(gè)像素格的兩個(gè)點(diǎn)之間的距離小于等于Eps，那么這兩個(gè)點(diǎn)屬于同一個(gè)簇，如圖2所示，a為相鄰的兩個(gè)像素格，且均含有4個(gè)數(shù)據(jù)點(diǎn)，假設(shè)MinPts=3，那么a、b內(nèi)所有的點(diǎn)均為核心點(diǎn)，如果a、b之間的距離小于Eps，那么a、b內(nèi)所有的點(diǎn)屬于同一個(gè)簇。否則，劃分為各含有4個(gè)點(diǎn)的兩個(gè)簇。

圖2 合并簇

1.4 確定邊界點(diǎn)和離群噪點(diǎn)

遍歷所有非核心點(diǎn)，如果存在NEps(C) 中的核心點(diǎn)，假如最靠近點(diǎn)p的核心點(diǎn)屬于簇clusters_1，那么非核心點(diǎn)p可以認(rèn)定為簇clusters_1的一個(gè)邊界點(diǎn)。檢查完所有非核心點(diǎn)之后，既不是核心點(diǎn)又不是邊界點(diǎn)的數(shù)據(jù)會(huì)被標(biāo)記為噪聲點(diǎn)。

通過(guò)上面的4個(gè)步驟，可以實(shí)現(xiàn)GPS軌跡點(diǎn)的快速聚類(lèi)，并且標(biāo)記出數(shù)據(jù)集中的噪聲點(diǎn)，通過(guò)剔除噪聲點(diǎn)來(lái)完成GPS數(shù)據(jù)的去噪處理。

2 動(dòng)態(tài)參數(shù)選擇

在對(duì)不同線路GPS數(shù)據(jù)進(jìn)行聚類(lèi)的過(guò)程中，由于公交線路的多樣性，在Eps和MinPts的選取中，同一聚類(lèi)參數(shù)無(wú)法適應(yīng)所有的線路。不同線路根據(jù)同一聚類(lèi)參數(shù)聚類(lèi)得到的結(jié)果在公交行駛路線的后續(xù)起終點(diǎn)獲取中，會(huì)引起起點(diǎn)獲取不準(zhǔn)確、起點(diǎn)周?chē)肼朁c(diǎn)刪除不全等問(wèn)題，進(jìn)而影響由GPS數(shù)據(jù)點(diǎn)生成公交行駛路線的準(zhǔn)確度。因此本文提出一種動(dòng)態(tài)參數(shù)選擇的方法，使PB-DBSCAN算法在對(duì)包含多條線路GPS數(shù)據(jù)集去噪時(shí)實(shí)現(xiàn)參數(shù)的自適應(yīng)選取。

為實(shí)現(xiàn)動(dòng)態(tài)參數(shù)選擇，引入聚類(lèi)率ρ及最優(yōu)聚類(lèi)率區(qū)間 [ρmin，ρmax]，聚類(lèi)率如式(5)所示，反映了聚類(lèi)后樣本的數(shù)據(jù)量占原始數(shù)據(jù)量的比例。

定義1 假如聚類(lèi)后的所有GPS數(shù)據(jù)點(diǎn)個(gè)數(shù)為m，樣本總數(shù)據(jù)量為n，那么聚類(lèi)率ρ為

ρ=m/n

(5)

一般而言，聚類(lèi)率并不是越大或者越小越好。聚類(lèi)率過(guò)大，則是在聚類(lèi)參數(shù)選取過(guò)程中，聚類(lèi)密度過(guò)小或聚類(lèi)半徑過(guò)大，從而導(dǎo)致部分噪聲點(diǎn)未被剔除，聚類(lèi)后剩余的點(diǎn)數(shù)過(guò)多，聚類(lèi)效果較差。相反，如果聚類(lèi)率過(guò)小，則是在聚類(lèi)參數(shù)選取中，聚類(lèi)密度過(guò)大或聚類(lèi)半徑過(guò)小，從而導(dǎo)致部分核心點(diǎn)或邊緣點(diǎn)被剔除，聚類(lèi)后剩余點(diǎn)數(shù)過(guò)少，聚類(lèi)效果較差。因此提出最優(yōu)聚類(lèi)率區(qū)間。

定義2 最優(yōu)聚類(lèi)率區(qū)間：當(dāng)聚類(lèi)率落于該區(qū)間內(nèi)時(shí)，大部分噪聲點(diǎn)得到剔除，所得簇的數(shù)量和每個(gè)簇的大小能夠滿足GPS數(shù)據(jù)的下一步處理，不會(huì)影響后續(xù)處理的準(zhǔn)確性。

動(dòng)態(tài)參數(shù)選擇迭代過(guò)程的終止條件之一為迭代后計(jì)算所得聚類(lèi)率位于最優(yōu)聚類(lèi)區(qū)間內(nèi)，通過(guò)對(duì)數(shù)據(jù)集中不同線路GPS數(shù)據(jù)的探索性實(shí)驗(yàn)，得出最優(yōu)聚類(lèi)率區(qū)間為[0.45,0.55]。

通過(guò)對(duì)多條線路的探索性實(shí)驗(yàn)，得到滿足絕大部分線路聚類(lèi)效果要求時(shí)，最大迭代次數(shù)N為64。動(dòng)態(tài)參數(shù)選擇聚類(lèi)實(shí)現(xiàn)過(guò)程如圖3所示。

圖3 動(dòng)態(tài)參數(shù)選擇流程

(1)確定初始參數(shù)。Eps0和MinPts0。迭代次數(shù)n=0。其中Eps0和MinPts0為在分別對(duì)各線路進(jìn)行固定參數(shù)的預(yù)聚類(lèi)實(shí)驗(yàn)之后，得到的在多條線路下滿足聚類(lèi)率在聚類(lèi)區(qū)間內(nèi)或臨近聚類(lèi)區(qū)間的共同初始輸入?yún)?shù)；

(2)計(jì)算聚類(lèi)率。根據(jù)式(5)計(jì)算聚類(lèi)率ρ0，判斷ρ0是否落在最優(yōu)聚類(lèi)率區(qū)間 [ρmin，ρmax] 中；

(3)參數(shù)動(dòng)態(tài)選擇。如果ρ0落在最優(yōu)聚類(lèi)率區(qū)間 [ρmin，ρmax] 中，聚類(lèi)結(jié)束。否則，若ρ0>ρmax，則調(diào)大MinPts至原MinPts的1.1倍，調(diào)小Eps至原Eps的0.9倍；若ρ0<ρmin，則調(diào)小MinPts至原MinPts的0.9倍，調(diào)大Eps至原Eps的1.1倍。在調(diào)大或調(diào)小的倍數(shù)選擇中，為減少運(yùn)算次數(shù)，調(diào)大倍數(shù)應(yīng)越大越好，調(diào)小倍數(shù)應(yīng)越小越好，過(guò)大或過(guò)小會(huì)導(dǎo)致兩次迭代結(jié)果的聚類(lèi)率相差太大，甚至錯(cuò)過(guò)最優(yōu)聚類(lèi)率區(qū)間，所以經(jīng)過(guò)大量實(shí)驗(yàn)得出最優(yōu)的調(diào)大倍數(shù)為1.1倍，調(diào)小倍數(shù)為0.9倍。

(4)迭代。令n=n+1，循環(huán)(1)～(3)，直至n的大小等于最大迭代次數(shù)N或者聚類(lèi)率ρ位于最優(yōu)聚類(lèi)率區(qū)間，完成聚類(lèi)。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)及環(huán)境

數(shù)據(jù)采用河北省某市2018年1月-3月所有線路公交車(chē)的GPS數(shù)據(jù)，其中公交線路有223條，總數(shù)據(jù)量111 G，共818 251 686條數(shù)據(jù)。搭建偽分布式Hadoop集群存儲(chǔ)GPS數(shù)據(jù)，集群由一個(gè)主節(jié)點(diǎn)，4個(gè)從節(jié)點(diǎn)構(gòu)成，服務(wù)器搭載兩個(gè)8核處理器，32 G內(nèi)存，1 TB存儲(chǔ)空間。利用HIVE處理HDFS上的數(shù)據(jù)，HIVE是基于Hadoop靜態(tài)批處理的數(shù)據(jù)倉(cāng)庫(kù)工具，可以通過(guò)類(lèi)似SQL語(yǔ)句的HQL語(yǔ)句進(jìn)行數(shù)據(jù)庫(kù)的增刪改查等操作，易于掌握。HIVE還提供了內(nèi)置函數(shù)和Java API接口，開(kāi)發(fā)人員可以根據(jù)這些函數(shù)去實(shí)現(xiàn)復(fù)雜的業(yè)務(wù)邏輯。這些HIVE的操作底層均是轉(zhuǎn)為機(jī)器學(xué)習(xí)中的MapReduce任務(wù)去執(zhí)行，可以方便地實(shí)現(xiàn)海量數(shù)據(jù)的統(tǒng)計(jì)分析[10]。

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)采用F1值[11]及均方根標(biāo)準(zhǔn)偏差(root-mean-square standard deviation，RMSSTD)[12]。F1值是一種評(píng)價(jià)聚類(lèi)結(jié)果的綜合指標(biāo)，計(jì)算公式如式(8)所示。其中，正確率Precision為實(shí)驗(yàn)結(jié)果簇中噪聲點(diǎn)與簇中總數(shù)據(jù)點(diǎn)的點(diǎn)數(shù)比；召回率Recall為簇中非噪聲點(diǎn)的點(diǎn)數(shù)與總數(shù)據(jù)集非噪聲點(diǎn)的點(diǎn)數(shù)比。例如數(shù)據(jù)集總點(diǎn)數(shù)為N，聚類(lèi)后的簇中數(shù)據(jù)點(diǎn)為N′，總數(shù)據(jù)集的非噪聲點(diǎn)數(shù)為M，簇中非噪聲點(diǎn)數(shù)為M′，則

(6)

(7)

(8)

RMSSTD通過(guò)衡量聚結(jié)果的同質(zhì)性，即緊湊程度，來(lái)判斷聚類(lèi)效果的好壞。計(jì)算公式如式(9)所示

(9)

式中：Ci代表第i個(gè)簇，ci是該簇的中心，x∈Ci代表屬于第i個(gè)簇的一個(gè)樣本點(diǎn)，ni為第i個(gè)簇的樣本數(shù)量，P為樣本點(diǎn)對(duì)應(yīng)的向量維數(shù)(例如一個(gè)簇含有10個(gè)點(diǎn)，則該簇的向量維數(shù)即為10)。 ∑i(ni-1)=n-NC，其中n為樣本點(diǎn)的總數(shù)，NC為聚類(lèi)簇的個(gè)數(shù)，通常NC?n，因此∑i(ni-1) 的值接近點(diǎn)的總數(shù)，為一個(gè)常數(shù)。綜上，RMSSTD可以看作是經(jīng)過(guò)歸一化的標(biāo)準(zhǔn)差來(lái)衡量聚類(lèi)的效果好壞。

3.3 PB-DBSCAN較DBSCAN在聚類(lèi)效率上的提升

表1 PB-DBSCAN與DBSCAN聚類(lèi)性能比較

傳統(tǒng)的DBSCAN聚類(lèi)方法，假設(shè)數(shù)據(jù)集總數(shù)為n，兩個(gè)數(shù)據(jù)點(diǎn)計(jì)算一次距離所用時(shí)間為t，由于要遍歷所有點(diǎn)與未遍歷過(guò)的點(diǎn)之間的距離，可得所需總時(shí)間T=(n-1)t+(n-2)t+(n-3)t+…+t=n(n-1)t/2，所以傳統(tǒng)的DBSCAN聚類(lèi)方法的時(shí)間復(fù)雜度為O(n2)，PB-DBSCAN聚類(lèi)方法，假設(shè)數(shù)據(jù)集總數(shù)為n，分為k個(gè)像素格，兩個(gè)數(shù)據(jù)點(diǎn)計(jì)算一次距離所用時(shí)間為t，每次判斷每個(gè)像素格內(nèi)的點(diǎn)是否為核心點(diǎn)所用時(shí)間nkt，由于每個(gè)像素格的相鄰像素格數(shù)量為20，所以遍歷非核心點(diǎn)理論所需最大計(jì)算時(shí)間為20nt，可得所需總時(shí)間T=(20+k)nt，所以PB-DBSCAN聚類(lèi)方法的時(shí)間復(fù)雜度為O(n)。

3.4 動(dòng)態(tài)參數(shù)選擇較固定參數(shù)在聚類(lèi)性能上的提升

為驗(yàn)證動(dòng)態(tài)參數(shù)選擇聚類(lèi)方法相較于固定參數(shù)對(duì)聚類(lèi)結(jié)果性能上的提升，選取石家莊106路、108路、34路、55路、56路和68路在2018年1月12日的上行GPS數(shù)據(jù)，分別使用動(dòng)態(tài)參數(shù)的PB-DBSCAN算法和固定參數(shù)的PB-DBSCAN算法進(jìn)行聚類(lèi)，實(shí)驗(yàn)結(jié)果見(jiàn)表2。

表2 自適應(yīng)參數(shù)與固定參數(shù)聚類(lèi)性能比較

為體現(xiàn)不同線路的動(dòng)態(tài)參數(shù)選擇聚類(lèi)過(guò)程對(duì)初始參數(shù)的自適應(yīng)性，分別對(duì)這些線路進(jìn)行固定參數(shù)的預(yù)聚類(lèi)實(shí)驗(yàn)，得到在多條線路下滿足聚類(lèi)率在聚類(lèi)區(qū)間內(nèi)或臨近聚類(lèi)區(qū)間的共同初始輸入?yún)?shù)：Eps0=20和MinPts0=5。

從F1值評(píng)價(jià)指標(biāo)來(lái)看，在同一線路比較中，動(dòng)態(tài)選擇參數(shù)的F1值均大于固定參數(shù)，與固定參數(shù)相比，F(xiàn)1值平均提高了10%，在不同線路比較中，動(dòng)態(tài)選擇參數(shù)的F1值更加穩(wěn)定；從RMSSTD評(píng)價(jià)指標(biāo)來(lái)看，動(dòng)態(tài)選擇參數(shù)的RMSSTD值均小于固定參數(shù)，與固定參數(shù)相比，RMSSTD值平均降低了30%。說(shuō)明動(dòng)態(tài)參數(shù)選擇方法的聚類(lèi)過(guò)程相較于固定參數(shù)的聚類(lèi)過(guò)程具有良好的穩(wěn)定性與準(zhǔn)確性。

3.5 基于PB-DBSCAN及傳統(tǒng)DBSCAN公交GPS去噪的可視化比較

通過(guò)對(duì)石家莊68路公交車(chē)GPS數(shù)據(jù)的處理來(lái)分析驗(yàn)證基于PB-DBSCAN算法的有效性，并且與DBSCAN算法所得到的結(jié)果進(jìn)行可視化比較。圖4為PB-DBSCAN算法聚類(lèi)效果，圖5為DBSCAN算法聚類(lèi)效果。可以看出，在拐點(diǎn)處或點(diǎn)數(shù)過(guò)密集處，DBSCAN不能很好剔除噪聲點(diǎn)，導(dǎo)致最后所得公交線路有明顯折線，偏離實(shí)際線路，尤其拐點(diǎn)處更是有大量折線，不符合道路實(shí)際特征，而PB-DBSCAN所得的聚類(lèi)結(jié)果，由于噪聲點(diǎn)少，尤其在拐點(diǎn)處的去噪效果尤為明顯，沒(méi)有出現(xiàn)明顯的偏差，所得線路基本符合實(shí)際道路，因此，PB-DBSCAN聚類(lèi)效果明顯優(yōu)于DBSCAN。

圖4 基于PB-DBSCAN的線路生成

圖5 基于DBSCAN的線路生成

4 結(jié)束語(yǔ)

本文在DBSCAN算法的基礎(chǔ)上，提出了一種基于像素格的快速密度聚類(lèi)算法——PB-DBSCAN算法，通過(guò)將龐大的GPS數(shù)據(jù)集使用基于像素格的PB-DBSCAN進(jìn)行聚類(lèi)，時(shí)間復(fù)雜度由傳統(tǒng)DBSCAN的O(n2) 降為O(n)，提高了算法效率。同時(shí)本文通過(guò)動(dòng)態(tài)參數(shù)選擇方法，解決了單一的聚類(lèi)參數(shù)無(wú)法在保證聚類(lèi)準(zhǔn)確度的情況下對(duì)多個(gè)不同GPS數(shù)據(jù)集同時(shí)聚類(lèi)的問(wèn)題，F(xiàn)1值平均提高了10%，RMSSTD平均降低了30%。下一步的研究中，會(huì)對(duì)聚類(lèi)后的GPS數(shù)據(jù)進(jìn)行抽稀、擬合等操作，使其更好貼合實(shí)際道路，實(shí)現(xiàn)數(shù)據(jù)的價(jià)值。