郝美薇,戴華林,郝 琨

(天津城建大學(xué) 計(jì)算機(jī)與信息工程學(xué)院,天津 300384) (*通信作者電子郵箱angelsamle@126.com)

基于密度的K-means算法在軌跡數(shù)據(jù)聚類中的優(yōu)化

郝美薇*,戴華林,郝 琨

(天津城建大學(xué) 計(jì)算機(jī)與信息工程學(xué)院,天津 300384) (*通信作者電子郵箱angelsamle@126.com)

針對(duì)傳統(tǒng)的K-means算法無法預(yù)先明確聚類數(shù)目,對(duì)初始聚類中心選取敏感且易受離群孤點(diǎn)影響導(dǎo)致聚類結(jié)果穩(wěn)定性和準(zhǔn)確性欠佳的問題,提出一種改進(jìn)的基于密度的K-means算法。該算法首先基于軌跡數(shù)據(jù)分布密度和增加軌跡數(shù)據(jù)關(guān)鍵點(diǎn)密度權(quán)值的方式選取高密度的軌跡數(shù)據(jù)點(diǎn)作為初始聚類中心進(jìn)行K-means聚類,然后結(jié)合聚類有效函數(shù)類內(nèi)類外劃分指標(biāo)對(duì)聚類結(jié)果進(jìn)行評(píng)價(jià),最后根據(jù)評(píng)價(jià)確定最佳聚類數(shù)目和最優(yōu)聚類劃分。理論研究與實(shí)驗(yàn)結(jié)果表明,該算法能夠更好地提取軌跡關(guān)鍵點(diǎn),保留關(guān)鍵路徑信息,且與傳統(tǒng)的K-means算法相比,聚類準(zhǔn)確性提高了28個(gè)百分點(diǎn),與具有噪聲的基于密度的聚類算法相比,聚類準(zhǔn)確性提高了17個(gè)百分點(diǎn)。所提算法在軌跡數(shù)據(jù)聚類中具有更好的穩(wěn)定性和準(zhǔn)確性。

K-means算法;基于密度;車輛活動(dòng)特征;密度權(quán)值;初始聚類中心;類內(nèi)類外劃分指標(biāo)

0 引言

伴隨著大數(shù)據(jù)時(shí)代的到來,在移動(dòng)定位服務(wù)的高速發(fā)展下,軌跡數(shù)據(jù)已經(jīng)成為了一項(xiàng)重要的數(shù)字資源。由于軌跡數(shù)據(jù)通常存在著數(shù)據(jù)量龐大、數(shù)據(jù)質(zhì)量較低的問題,因此如何對(duì)軌跡數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘和可視化分析獲取深層語義成為大數(shù)據(jù)分析的一大熱點(diǎn)問題。聚類算法作為對(duì)軌跡數(shù)據(jù)特征提取的有效技術(shù),被廣泛應(yīng)用于軌跡數(shù)據(jù)挖掘中。其中最有代表的軌跡數(shù)據(jù)聚類算法包括基于概率的聚類算法、基于劃分的聚類算法、基于密度的聚類算法、基于子軌跡的聚類算法和基于流場(chǎng)的聚類算法[1]。而在這些聚類算法中又以基于劃分和密度的聚類算法使用最為廣泛。

K-means算法[1]作為典型的基于劃分的聚類算法因其簡(jiǎn)單高效而被廣泛使用。但它需要使用者根據(jù)相關(guān)經(jīng)驗(yàn)或相關(guān)領(lǐng)域背景來確定聚類數(shù)目和初始聚類中心,且對(duì)初始聚類中心選擇敏感,易受數(shù)據(jù)輸入順序影響,導(dǎo)致其聚類結(jié)果準(zhǔn)確性和穩(wěn)定性欠佳。針對(duì)這些問題,許多學(xué)者提出了不同的改進(jìn)方案?；诿芏瓤紤]的改進(jìn)方案有:文獻(xiàn)[2]提出的聚類中心初始化算法(Cluster Center Initialization Algorithm, CCIA),通過樣本數(shù)據(jù)點(diǎn)的密度分布信息進(jìn)行聚類合并得到初始聚類中心;文獻(xiàn)[3]提出的構(gòu)建KD樹(K-Dimensional tree, KD-tree),通過選取密度較大且相互遠(yuǎn)離的樣本數(shù)據(jù)點(diǎn)作為初始聚類中心;文獻(xiàn)[4]提出的選取大于平均密度的樣本數(shù)據(jù)點(diǎn)作為初始聚類中心以及文獻(xiàn)[5]提出的選取高密度區(qū)域中距離全局樣本數(shù)據(jù)中心點(diǎn)最遠(yuǎn)的樣本數(shù)據(jù)作為初始聚類中心。這些算法不適用于數(shù)據(jù)分布較為均勻的樣本數(shù)據(jù)集,在根據(jù)密度篩選樣本數(shù)據(jù)時(shí)有的算法還需要加入其他參數(shù)進(jìn)行輔助判斷?；诰嚯x考慮的改進(jìn)方案有:文獻(xiàn)[6]提出的根據(jù)聚簇內(nèi)樣本距離小于聚簇間樣本距離動(dòng)態(tài)調(diào)整初始聚類中心選取;文獻(xiàn)[7] 算法根據(jù)每個(gè)樣本數(shù)據(jù)點(diǎn)到其聚類中心的距離給定一個(gè)特定加權(quán)系數(shù)進(jìn)行聚類;文獻(xiàn)[8]提出的在極小極大算法基礎(chǔ)上確定初始聚類中心并根據(jù)歐氏距離進(jìn)行分類。這些算法在面對(duì)較大規(guī)模的樣本數(shù)據(jù)集時(shí)會(huì)增加算法時(shí)間復(fù)雜度,降低運(yùn)算效率,且聚類結(jié)果易受到離群孤點(diǎn)的干擾。此外還有結(jié)合密度與距離的改進(jìn)方案：文獻(xiàn)[9]算法將樣本數(shù)據(jù)集分為若干小子集并加入質(zhì)心和權(quán)重兩個(gè)特征,在此基礎(chǔ)上進(jìn)行局部聚類,但在高維度的樣本數(shù)據(jù)集中計(jì)算復(fù)雜度會(huì)明顯增加;文獻(xiàn)[10]算法基于高密度且相互遠(yuǎn)離的原則根據(jù)平方誤差標(biāo)準(zhǔn)確定聚類數(shù)目選取初始聚類中心,但在較大規(guī)模的樣本數(shù)據(jù)集中算法效率明顯降低。

軌跡數(shù)據(jù)的數(shù)據(jù)量龐大,數(shù)據(jù)結(jié)構(gòu)較為復(fù)雜，而傳統(tǒng)的K-means算法無法預(yù)先明確聚類數(shù)目,對(duì)初始聚類中心選取敏感且易受離群孤點(diǎn)影響導(dǎo)致聚類結(jié)果穩(wěn)定性和準(zhǔn)確性欠佳。針對(duì)這一問題，本文提出了一種改進(jìn)的基于密度的K-means算法,通過標(biāo)準(zhǔn)差計(jì)算樣本軌跡數(shù)據(jù)點(diǎn)的分布密度,并以密度感知篩選出車輛活動(dòng)狀態(tài)為轉(zhuǎn)彎狀態(tài)的樣本軌跡數(shù)據(jù)點(diǎn)增加其密度權(quán)重,最終在聚類有效函數(shù)類內(nèi)類外劃分(Between-Within Proportion, BWP)指標(biāo)的干預(yù)下,選取高密度且相互遠(yuǎn)離的樣本數(shù)據(jù)點(diǎn)作為初始聚類中心并確定最佳聚類數(shù)目和聚類結(jié)果,獲取軌跡路徑中的關(guān)鍵點(diǎn)。該算法能夠自動(dòng)獲取聚類數(shù)目和初始聚類中心,具有較強(qiáng)的抗噪點(diǎn)干擾性,同時(shí)根據(jù)車輛活動(dòng)特征進(jìn)行篩選有效地提高了聚類結(jié)果即軌跡關(guān)鍵點(diǎn)的準(zhǔn)確性。

1 相關(guān)描述與定義

設(shè)軌跡數(shù)據(jù)點(diǎn)集P={p1,p2, …,pn}∈Rd*n,d=3,其中d代表軌跡數(shù)據(jù)樣本維度,本文中的軌跡數(shù)據(jù)維度為三維即空間的經(jīng)緯度坐標(biāo)兩個(gè)維度和時(shí)間維度;n代表軌跡數(shù)據(jù)樣本總數(shù)。

對(duì)本文算法中提出的一些重要概念進(jìn)行定義:

定義1 單個(gè)軌跡數(shù)據(jù)點(diǎn)的密度值。對(duì)于軌跡數(shù)據(jù)點(diǎn)中的任意一個(gè)樣本軌跡數(shù)據(jù)點(diǎn)pi的密度Densr(pi)[11]具體定義如下:

(1)

其中:r為給定的有效密度半徑;N為該半徑內(nèi)所包含的軌跡數(shù)據(jù)點(diǎn)的總數(shù);pj為以pi為圓心r為半徑的圓內(nèi)的第j個(gè)軌跡數(shù)據(jù)點(diǎn);Dist(pi,pj)為軌跡數(shù)據(jù)點(diǎn)pi和pj歐氏距離。

定義2 轉(zhuǎn)彎狀態(tài)的軌跡數(shù)據(jù)點(diǎn)權(quán)值密度值。在識(shí)別軌跡數(shù)據(jù)點(diǎn)的直行和轉(zhuǎn)彎狀態(tài)之后,需要通過增加相應(yīng)密度的權(quán)值提高該數(shù)據(jù)點(diǎn)的篩選概率,因此引入了轉(zhuǎn)彎狀態(tài)的軌跡數(shù)據(jù)點(diǎn)權(quán)值密度的概念。對(duì)于軌跡數(shù)據(jù)點(diǎn)中的任意一個(gè)樣本轉(zhuǎn)彎點(diǎn)pi的權(quán)值密度WDensr(pi)[7,11]具體定義如下:

WDensr(pi)=

(2)

定義3 軌跡數(shù)據(jù)點(diǎn)的平均距離。對(duì)于軌跡數(shù)據(jù)集而言，其軌跡數(shù)據(jù)點(diǎn)的平均距離avgDist[5]具體定義如下:

(3)

通過計(jì)算軌跡數(shù)據(jù)點(diǎn)間的平均距離,可以有效地反映軌跡數(shù)據(jù)集的整體離散程度,為更好地確定鄰域半徑提供有效依據(jù)。

定義4 鄰域半徑。鄰域半徑作為有效密度半徑時(shí)不僅直接參與密度值的計(jì)算,同時(shí)還決定了可能包含軌跡數(shù)據(jù)點(diǎn)的多少,合適的鄰域半徑對(duì)于密度計(jì)算結(jié)果至關(guān)重要,鄰域半徑γ具體定義如下:

(4)

鄰域半徑采用計(jì)算軌跡數(shù)據(jù)點(diǎn)距離的標(biāo)準(zhǔn)差方式來確定,由于標(biāo)準(zhǔn)差能夠有效反映變量與期望的偏差程度,因此通過計(jì)算距離的標(biāo)準(zhǔn)差可知標(biāo)準(zhǔn)差越小,鄰域半徑越小,所圈鄰域內(nèi)的軌跡數(shù)據(jù)點(diǎn)越緊密。

定義5 軌跡步長(zhǎng)。車輛軌跡數(shù)據(jù)通常都是采用均勻時(shí)間間隔進(jìn)行抽樣獲取的,軌跡步長(zhǎng)則是用來反映一段軌跡中由所采軌跡數(shù)據(jù)點(diǎn)分割后的每段軌跡的長(zhǎng)度,該長(zhǎng)度可以間接反映軌跡中車輛活動(dòng)的速度等屬性,軌跡步長(zhǎng)ε具體定義如下:

(5)

其中:m為樣本軌跡數(shù)據(jù)的條數(shù);Li為每條軌跡的長(zhǎng)度即通過將每條軌跡路徑按照時(shí)間序列順序連接后計(jì)算每段軌跡的長(zhǎng)度并求和;Pi為每條軌跡上的軌跡數(shù)據(jù)點(diǎn)總數(shù)。將求取的軌跡步長(zhǎng)作為有效密度半徑對(duì)數(shù)據(jù)點(diǎn)進(jìn)行密度計(jì)算幫助判斷其車輛活動(dòng)特征,通常軌跡步長(zhǎng)越短表明其當(dāng)時(shí)車輛速度較低,且所圈軌跡數(shù)據(jù)點(diǎn)密度可能越大,通常認(rèn)為車輛在轉(zhuǎn)彎過程中軌跡數(shù)據(jù)點(diǎn)具有高密度低速率的特性。

2 改進(jìn)的基于密度的K-means算法

2.1 基于密度的初始聚類中心的選取

傳統(tǒng)K-means算法對(duì)初始聚類中心都是隨機(jī)選取,易受到樣本數(shù)據(jù)集中離群孤點(diǎn)的影響導(dǎo)致算法陷入局部最優(yōu)解,從而直接影響聚類結(jié)果的準(zhǔn)確性和穩(wěn)定性。本文針對(duì)這一問題,提出了一種基于樣本軌跡數(shù)據(jù)分布密度和增加軌跡數(shù)據(jù)關(guān)鍵點(diǎn)密度權(quán)值的方式來選取高密度的軌跡數(shù)據(jù)點(diǎn)作為初始聚類中心。

本文主要作了以下兩點(diǎn)改進(jìn):1)通過計(jì)算軌跡數(shù)據(jù)集中各軌跡數(shù)據(jù)點(diǎn)的密度值,選取高密度的軌跡數(shù)據(jù)點(diǎn)作為初始點(diǎn),從而有效地減小軌跡數(shù)據(jù)集中離群孤點(diǎn)對(duì)于聚類結(jié)果的影響,防止算法過早收斂陷入局部最優(yōu)解;2)通過一種密度感知方法對(duì)車輛活動(dòng)特征比如直行轉(zhuǎn)彎狀態(tài)進(jìn)行分析,選擇轉(zhuǎn)彎狀態(tài)的軌跡數(shù)據(jù)點(diǎn)增加其密度權(quán)重,增大軌跡關(guān)鍵點(diǎn)篩選的概率,提高最終聚類結(jié)果的準(zhǔn)確性。

該算法首先選取軌跡數(shù)據(jù)中密度值較大的2K(K為聚類數(shù)目)個(gè)軌跡數(shù)據(jù)點(diǎn)作為初始聚類中心的核心對(duì)象,并篩選出其中為轉(zhuǎn)彎狀態(tài)的軌跡數(shù)據(jù)點(diǎn)增加其密度權(quán)重;然后按照其密度大小依次進(jìn)行聚類合并,同時(shí)重新計(jì)算聚類中心的密度值,選取K個(gè)密度值較大的聚類中心作為初始聚類中心;最后將未被聚類的軌跡數(shù)據(jù)點(diǎn)標(biāo)記為噪點(diǎn)從軌跡數(shù)據(jù)集中去除。

算法描述如下。

輸入 含有n個(gè)對(duì)象的軌跡數(shù)據(jù)集X，期望劃分的聚類數(shù)目K， 最小密度閾值minDen，鄰域半徑γ，軌跡步長(zhǎng)ε。

輸出 含有K個(gè)對(duì)象的初始聚類中心點(diǎn)集T，去除噪點(diǎn)的軌跡數(shù)據(jù)集P。

Begin:

1)令集合D={},D′={},W={},T={},P={}。

2)根據(jù)式(3)，式(4)計(jì)算鄰域半徑γ；根據(jù)式(5)計(jì)算軌跡步長(zhǎng)ε。

3)遍歷集合X中的每一個(gè)對(duì)象xi，給xi加入密度標(biāo)簽，取r=γ，根據(jù)式(1)計(jì)算xi初始密度值Densr(xi)。

5)遍歷集合X中的每一個(gè)對(duì)象xi。

5.1)取r=ε，根據(jù)式(1)計(jì)算xi密度值Densr(xi)。

5.2)如果Densr(xi)≥minDen，則將xi加入到集合D′中。

6)取集合D與集合D′中在空間維度和時(shí)間維度完全相同的對(duì)象加入集合W中。

7)遍歷集合W中的每一個(gè)對(duì)象xi，給xi加入轉(zhuǎn)彎標(biāo)簽，更新其密度標(biāo)簽，取r=γ，根據(jù)式(2)計(jì)算xi權(quán)值密度值WDensr(xi)。

Repeat:

8)取集合D中無中心點(diǎn)或邊界點(diǎn)標(biāo)簽的第一個(gè)對(duì)象di。

8.1)將di作為一個(gè)新聚簇的聚簇中心點(diǎn)，加入中心點(diǎn)標(biāo)簽，遍歷集合X中的每一個(gè)對(duì)象xi且xi≠di，如果xi是di的直接密度可達(dá)點(diǎn)且xi無中心點(diǎn)或邊界點(diǎn)標(biāo)簽，則給xi加入邊界點(diǎn)標(biāo)簽，納入該聚簇內(nèi)。

8.2)更新di密度標(biāo)簽，如果di有轉(zhuǎn)彎標(biāo)簽，則取r=γ，根據(jù)式(2)計(jì)算di權(quán)值密度值WDensr(di)；否則取r=γ，根據(jù)式(1)計(jì)算di密度值Densr(di)。

Until: 遍歷集合D中全部對(duì)象，即集合D中的每個(gè)對(duì)象都含有中心點(diǎn)或邊界點(diǎn)標(biāo)簽。

9)選取集合D中具有中心點(diǎn)標(biāo)簽且密度標(biāo)簽值較大的前K個(gè)對(duì)象加入集合T中。

10)遍歷集合X中的每一個(gè)對(duì)象xi，如果xi無中心點(diǎn)或邊界點(diǎn)標(biāo)簽，則給xi加入噪點(diǎn)標(biāo)簽；否則將xi加入集合P中。

11)輸出結(jié)果。

End

2.2 聚類數(shù)目K值的優(yōu)化選取

對(duì)于軌跡數(shù)據(jù)集這種數(shù)據(jù)結(jié)構(gòu)未知的樣本數(shù)據(jù),通常采用聚類有效函數(shù)的內(nèi)部度量方式對(duì)聚類結(jié)果進(jìn)行評(píng)價(jià)。內(nèi)部度量中公認(rèn)比較優(yōu)秀的指標(biāo)包括CH(Calinski-Harabasz)指標(biāo)[13]、DB(Davies-Bouldin)指標(biāo)[14]、Wint(Weighted inter-intra)指標(biāo)[15]、IGP(In-Group Proportion)指標(biāo)[16]等。然而這些指標(biāo)都存在一些自身的局限性,僅在其適用范圍內(nèi)針對(duì)一些特定的樣本數(shù)據(jù)集能夠取得較好的度量結(jié)果,對(duì)于超出適用范圍的樣本數(shù)據(jù)集,這些指標(biāo)的聚類有效性檢驗(yàn)通常并不理想,容易使算法陷入局部最優(yōu)解而無法獲取最優(yōu)聚類數(shù)目。

本文中為了選取一個(gè)高質(zhì)量的聚類結(jié)果要求每個(gè)聚類內(nèi)樣本盡可能地相似,不同聚類間樣本盡可能地不同,采用距離度量方式即使聚簇內(nèi)的樣本距離極小化,聚簇間的樣本距離極大化。本文算法選用了BWP指標(biāo)BWP(j,i)[17],即第j類第i個(gè)樣本數(shù)據(jù)的聚類離差距離bsw(j,i)與聚類距離baw(j,i)的比值來更好地反映聚簇內(nèi)緊密度與聚簇間分離度,具體描述為:

(6)

其中：b(j,i)為第j類第i個(gè)樣本數(shù)據(jù)的最小類間距離,即該樣本到其他每個(gè)聚簇內(nèi)的各個(gè)樣本平均距離的最小值。b(j,i)可描述為:

(7)

w(j,i)為第j類第i個(gè)樣本數(shù)據(jù)的類內(nèi)距離,即該樣本到其所屬聚簇內(nèi)的各個(gè)樣本的平均距離,具體描述為:

(8)

可以看出BWP(j,i)采用線性組合的方式來平衡最小類間距離b(j,i)和類內(nèi)距離w(j,i)并保證函數(shù)目標(biāo)一致。BWP(j,i)指標(biāo)的范圍為[-1,1]：當(dāng)BWP(j,i)近似為1時(shí)表示該樣本數(shù)據(jù)被聚類正確;近似為-1時(shí)表示該樣本數(shù)據(jù)被聚類錯(cuò)誤。

所有樣本數(shù)據(jù)集的平均BWP指標(biāo)越大,表明聚類結(jié)果質(zhì)量越高,聚簇內(nèi)樣本越緊密,聚簇間樣本越分離。因此平均BWP指標(biāo)最大時(shí)聚類結(jié)果所對(duì)應(yīng)的聚類數(shù)目Kopt值為最佳聚類數(shù)目K值,即

(9)

其中:N為樣本總數(shù)；nk為第k個(gè)聚簇內(nèi)的樣本數(shù)據(jù)總數(shù)。

2.3 基于密度和BWP指標(biāo)優(yōu)化的K-means算法

算法描述如下。

輸入 含有n個(gè)對(duì)象的軌跡數(shù)據(jù)集X,最小密度閾值minDen,鄰域半徑γ,軌跡步長(zhǎng)ε。

輸出 最佳聚類數(shù)目K,最佳聚類劃分集T。

Begin:

1) 令集合X={},T′={},T={},S={};

2.1) 根據(jù)基于密度的初始聚類中心的選取算法,選取k個(gè)初始聚類中心點(diǎn);

2.2) 根據(jù)改進(jìn)的K-means算法對(duì)去除噪聲后的軌跡數(shù)據(jù)樣本集進(jìn)行聚類,聚類結(jié)果放入集合T′中;

2.3) 根據(jù)式(6)計(jì)算T′中聚類結(jié)果的平均BWP值avgBWP,并將(k,avgBWP)放入集合S中;

2.4) 將集合T′放入集合X中,之后令T={};

3) 比較集合S中的各對(duì)象的avgBWP值,取最大的avgBWP所在對(duì)象Target并記錄該對(duì)象所在集合S中的下標(biāo)index;

4)k=Target對(duì)象的k值,T=Xindex,其中Xindex為集合X中第index個(gè)對(duì)象;

5) 輸出結(jié)果;

End

本文算法對(duì)于傳統(tǒng)K-means算法進(jìn)行了優(yōu)化,保證了初始聚類中心能夠在高密度的軌跡數(shù)據(jù)點(diǎn)中產(chǎn)生,相對(duì)于傳統(tǒng)算法中的隨機(jī)選取初始聚類中心能夠更好地防止算法過早收斂陷入局部最優(yōu)解中,有效提高聚類結(jié)果準(zhǔn)確性。此外提出的選取初始聚類中心的算法能夠粗略去除軌跡數(shù)據(jù)樣本中的噪點(diǎn),有利于提高聚類結(jié)果的準(zhǔn)確性,有效避免了傳統(tǒng)算法在選取初始聚類中心時(shí)反復(fù)迭代,在一定程度上提高了本文算法運(yùn)行效率。通過BWP指標(biāo)干預(yù),本文算法能夠自動(dòng)獲取最佳聚類數(shù)目K值,有效選取優(yōu)質(zhì)聚類結(jié)果,解決了對(duì)于軌跡數(shù)據(jù)樣本數(shù)據(jù)結(jié)構(gòu)未知時(shí)難以確定最佳聚類數(shù)目的難題,得到更為精準(zhǔn)的聚類結(jié)果劃分。

圖1 軌跡數(shù)據(jù)集Data1聚類結(jié)果質(zhì)量圖

圖2 軌跡數(shù)據(jù)集Data2聚類結(jié)果質(zhì)量圖

圖3 軌跡數(shù)據(jù)集Data3聚類結(jié)果質(zhì)量圖

圖4 軌跡數(shù)據(jù)集Data4聚類結(jié)果質(zhì)量圖

3 實(shí)驗(yàn)與分析

本文提出的改進(jìn)的基于密度的K-means算法驗(yàn)證實(shí)驗(yàn)主要分為兩大部分：一部分是采用本文算法對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行測(cè)試實(shí)驗(yàn),分析其聚類結(jié)果;另一部分是將本文算法與傳統(tǒng)的K-means算法和具有噪聲的基于密度的聚類(Density-Based Spatial Clustering of Applications with Noise, DBSCAN)算法進(jìn)行聚類結(jié)果和算法效率對(duì)比實(shí)驗(yàn),驗(yàn)證本文算法的穩(wěn)定性、準(zhǔn)確性和有效性。

3.1 實(shí)驗(yàn)平臺(tái)與實(shí)驗(yàn)數(shù)據(jù)

本文中實(shí)驗(yàn)分析選用Windows 7.0,Matlab2015b開發(fā)環(huán)境,基于百度地圖開發(fā)的地圖引擎,Intel Core i7 2.00 GHz CPU, 4.00 GB內(nèi)存作為實(shí)驗(yàn)平臺(tái);由數(shù)據(jù)堂提供的真實(shí)出租車GPS數(shù)據(jù),選取在2015年9月1日—10日的8:00—10:00，12:00—14:00，16:00—18:00，20:00—22:00共計(jì)四個(gè)時(shí)間段的北京市東城區(qū)的出租車GPS數(shù)據(jù)作為四組實(shí)驗(yàn)數(shù)據(jù),每個(gè)樣本實(shí)驗(yàn)數(shù)據(jù)包括車輛ID號(hào)、經(jīng)緯度坐標(biāo)點(diǎn)和時(shí)間信息。數(shù)據(jù)集詳細(xì)描述如表1所示。

表1 實(shí)驗(yàn)軌跡數(shù)據(jù)集

3.2 改進(jìn)的基于密度的K-means算法實(shí)驗(yàn)及分析

實(shí)驗(yàn)采用本文算法對(duì)四組實(shí)驗(yàn)數(shù)據(jù)進(jìn)行測(cè)試,并為了便于觀察聚類結(jié)果質(zhì)量將每一組數(shù)據(jù)所取的聚類數(shù)目與平均BWP值擬合成關(guān)系曲線圖,當(dāng)平均BWP值最大時(shí)對(duì)應(yīng)的K值為最佳聚類數(shù)目且此時(shí)所得軌跡數(shù)據(jù)聚類結(jié)果最優(yōu)。軌跡數(shù)據(jù)集Data1的K值選取范圍在區(qū)間[2,151]內(nèi),鄰域半徑γ=0.74,軌跡步長(zhǎng)ε=0.37,其聚類結(jié)果如圖1所示,當(dāng)K=75時(shí),對(duì)應(yīng)的平均BWP值avgBWP75=0.882 507最大且該值接近于1表明軌跡數(shù)據(jù)集被正確聚類;軌跡數(shù)據(jù)集Data2的K值選取范圍在區(qū)間[2,152]內(nèi),鄰域半徑γ=0.73,軌跡步長(zhǎng)ε=0.36,其聚類結(jié)果如圖2所示,當(dāng)K=83時(shí),對(duì)應(yīng)的平均BWP值avgBWP83=0.907 683最大且該值接近于1表明軌跡數(shù)據(jù)集被正確聚類;軌跡數(shù)據(jù)集Data3的K值選取范圍在區(qū)間[2,140]內(nèi),鄰域半徑γ=0.70,軌跡步長(zhǎng)ε=0.35,其聚類結(jié)果如圖3所示,當(dāng)K=62時(shí),對(duì)應(yīng)的平均BWP值avgBWP62=0.854 317最大且該值接近于1表明軌跡數(shù)據(jù)集被正確聚類;軌跡數(shù)據(jù)集Data4的K值選取范圍在區(qū)間[2,132]內(nèi),鄰域半徑γ=0.75,軌跡步長(zhǎng)ε=0.38,其聚類結(jié)果如圖4所示,當(dāng)K=60時(shí),對(duì)應(yīng)的平均BWP值avgBWP60=0.881 316最大且該值接近于1表明軌跡數(shù)據(jù)集被正確聚類。

3.3 三種聚類算法對(duì)比實(shí)驗(yàn)及分析

為了驗(yàn)證本文算法的高效性,將本文算法與傳統(tǒng)的K-means算法和DBSACN算法進(jìn)行對(duì)比實(shí)驗(yàn),主要包括聚類結(jié)果對(duì)比和算法效率對(duì)比兩部分。

聚類結(jié)果對(duì)比主要是對(duì)聚類結(jié)果準(zhǔn)確率、聚簇內(nèi)距離、聚簇間距離、最佳聚類數(shù)目、聚類迭代次數(shù)五個(gè)方面進(jìn)行分析。為了保證傳統(tǒng)K-means算法的合理有效性,每個(gè)數(shù)據(jù)集在使用傳統(tǒng)K-means算法進(jìn)行聚類實(shí)驗(yàn)時(shí)會(huì)重復(fù)實(shí)驗(yàn)50次并取平均值作為最終聚類結(jié)果。三種算法的對(duì)比分析結(jié)果如表2所示。

表2 三種算法的聚類結(jié)果對(duì)比

表3 三種算法的運(yùn)算時(shí)間對(duì)比 s

從表2中可以看出，本文算法的準(zhǔn)確率比傳統(tǒng)K-means算法提高了約28個(gè)百分點(diǎn)，比DBSCAN算法提高了約17個(gè)百分點(diǎn)。相對(duì)于傳統(tǒng)的K-means算法和DBSCAN算法其聚類迭代次數(shù)更少,表明本文算法對(duì)于初始聚類中心的選取合理有效。為了進(jìn)一步驗(yàn)證三種算法在軌跡數(shù)據(jù)集中的聚類效果,選取軌跡數(shù)據(jù)集Data4的聚類結(jié)果進(jìn)行熱力圖繪制效果如圖5～7所示。

對(duì)比圖5～7可以看出本文算法和DBSCAN算法在聚類劃分上相對(duì)于傳統(tǒng)K-means算法更為合理,能夠更好地突出軌跡分布中車流量較大的路徑點(diǎn)。此外,本文算法相對(duì)于其他兩個(gè)算法具有更好地抗噪點(diǎn)干擾能力,軌跡數(shù)據(jù)的聚類結(jié)果更貼合實(shí)際道路,能夠更好地提取實(shí)際軌跡信息。

實(shí)驗(yàn)結(jié)果表明，本文算法能夠正確地對(duì)軌跡數(shù)據(jù)集進(jìn)行聚類,有效提高了聚類結(jié)果的穩(wěn)定性和準(zhǔn)確性。聚類結(jié)果更加符合軌跡數(shù)據(jù)集的數(shù)據(jù)結(jié)構(gòu)特征,能夠準(zhǔn)確提取軌跡中的關(guān)鍵路徑點(diǎn),有效避免軌跡數(shù)據(jù)集中噪點(diǎn)對(duì)于聚類結(jié)果的影響。

圖5 本文算法實(shí)現(xiàn)的聚類結(jié)果熱力圖

圖6 基于DBSCAN算法實(shí)現(xiàn)的聚類結(jié)果熱力圖

圖7 基于傳統(tǒng)K-means算法實(shí)現(xiàn)的聚類結(jié)果熱力圖

算法效率對(duì)比主要是對(duì)不同軌跡數(shù)據(jù)集中一次聚類迭代CPU所要消耗的時(shí)間進(jìn)行對(duì)比,包括一次聚類迭代的最短時(shí)間、最長(zhǎng)時(shí)間和平均時(shí)間。三種算法的對(duì)比分析結(jié)果如表3所示。

從表3的實(shí)驗(yàn)結(jié)果可看出：本文算法在每次迭代時(shí)CPU所消耗的平均時(shí)間與DBSCAN算法相當(dāng),盡管在計(jì)算選取初始聚類中心時(shí)時(shí)間復(fù)雜度有所增加,但對(duì)于軌跡數(shù)據(jù)這種數(shù)據(jù)結(jié)構(gòu)較為復(fù)雜的樣本數(shù)據(jù)集能夠有效減少尋找初始聚類中心時(shí)的迭代次數(shù),在一定程度上提高聚類算法運(yùn)行效率。

4 結(jié)語

傳統(tǒng)K-means算法需要根據(jù)使用者的自身經(jīng)驗(yàn)或是相關(guān)知識(shí)背景實(shí)現(xiàn)確定聚類數(shù)目K值,并且由于通過隨機(jī)選取確定初始聚類中心容易受到數(shù)據(jù)輸入順序和數(shù)據(jù)噪點(diǎn)的影響致使算法過早收斂陷入局部最優(yōu)解,對(duì)于最終聚類結(jié)果的準(zhǔn)確性和穩(wěn)定性產(chǎn)生極大影響。針對(duì)以上問題,本文提出了一種改進(jìn)的基于密度的K-means算法,結(jié)合BWP指標(biāo)確定最佳聚類數(shù)目,將初始聚類中心選中在高密度的關(guān)鍵軌跡數(shù)據(jù)點(diǎn),保證得到聚簇內(nèi)緊密、聚簇間分散的高質(zhì)量聚類結(jié)果。實(shí)驗(yàn)結(jié)果顯示本文算法結(jié)果更為穩(wěn)定且準(zhǔn)確性更高,仿真結(jié)果也表明該算法能夠更好地提取出軌跡數(shù)據(jù)的關(guān)鍵點(diǎn)。本文算法在計(jì)算樣本間距和選取初始聚類中心時(shí),時(shí)間復(fù)雜度有所增加,將在今后的研究中提高該部分的計(jì)算效率。

References)

[1] 王祖超, 袁曉如.軌跡數(shù)據(jù)可視分析研究[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2015 27(1): 9-25. (WANG Z C, YUAN X R. Visual analysis of trajectory data[J]. Journal of Computer-Aided Design and Computer Graphics, 2015 27(1): 9-25.)

[2] KHAN S S, AHMAD A. Cluster center initialization algorithm forK-means clustering[J]. Expert Systems with Applications, 2004, 25(11): 1293-1302.

[3] REDMOND S J, HENEGHAN C. A method for initialising theK-means clustering algorithm using kd-trees[J]. Pattern Recognition Letters, 2007, 28(8): 965-973.

[4] FAN G L, LIU Y W, TONG J Q, et al. Application ofK-means algorithm to Web text mining based on average density optimization[J]. Journal of Digital Information Management, 2016, 14(1): 41.

[5] 何云斌, 劉雪嬌, 王知強(qiáng), 等.基于全局中心的高密度不唯一的K-means算法研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2016, 52(1): 48-54. (HE Y B, LIU X J, WANG Z Q, et al. ImprovedK-means algorithm based on global center and nonuniqueness high-density points[J]. Computer Engineering and Applications, 2016, 52(1): 48-54.)

[6] ZHU M, WANG W, HUANG J. Improved initial cluster center selection inK-means clustering[J]. Engineering Computations, 2014, 31(8): 1661-1667.

[7] ZHANG T, MA F. Improved roughk-means clustering algorithm based on weighted distance measure with Gaussian function[J]. International Journal of Computer Mathematics, 2015, 94(1): 1-17.

[8] 張淑清, 黃震坤, 馮銘.一種優(yōu)化的改進(jìn)k_means算法[J]. 微電子學(xué)與計(jì)算機(jī), 2015, 32(12): 36-39. (ZHANG S Q, HUANG Z K, FENG M. An optimizedK-means algorithm[J]. Microelectronics amp; Computer, 2015, 32(12): 36-39.)

[10] 張素潔, 趙懷慈.最優(yōu)聚類個(gè)數(shù)和初始聚類中心點(diǎn)選取算法研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2017, 34(6): 1-5. (ZHANG S J, ZHAO H C. Algorithm research of optimal cluster number and initial cluster center[J]. Application Research of Computers, 2017, 34(6): 1-5.)

[11] RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks [J]. Science, 2014, 344(6191): 1492.

[12] REZAEE M R, LELIEVELDT B P F, REIBER J H C. A new cluster validity index for the fuzzy c-mean[J]. Pattern Recognition Letters, 1998, 19(3/4): 237-246.

[13] CALINSKI T, HARABASZ J. A dendrite method for cluster analysis[J]. Communications in Statistics, 1974, 3(1): 1-27.

[14] DAVIES D L, BOULDIN D W. A cluster separation measure[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1979, 1(2): 224.

[15] DIMITRIADOU E, DOLNICAR S, WEINGESSEL A. An examination of indexes for determining the number of clusters in binary data sets[J]. Psychometrika, 2002, 67(1): 137-159.

[16] KAPP A V, TIBSHIRANI R. Are clusters found in one dataset present in another dataset?[J]. Biostatistics, 2007, 8(1): 9-31.

[17] 周世兵, 徐振源, 唐旭清.K-means算法最佳聚類數(shù)確定方法[J]. 計(jì)算機(jī)應(yīng)用, 2010,30(8): 1995-1998. (ZHOU S B, XU Z Y, TANG X Q. Method for determining optimal number of clusters inK-means clustering algorithm[J]. Journal of Computer Applications, 2010, 30(8): 1995-1998.)

Optimizationofdensity-basedK-meansalgorithmintrajectorydataclustering

HAO Meiwei*, DAI Hualin, HAO Kun

(CollegeofComputerandInformationEngineering,TianjinChengjianUniversity,Tianjin300384,China)

Since the traditionalK-means algorithm can hardly predefine the number of clusters, and performs sensitively to the initial clustering centers and outliers, which may result in unstable and inaccurate results, an improved density-basedK-means algorithm was proposed. Firstly, high-density trajectory data points were selected as the initial clustering centers to performK-means clustering by considering the density of the trajectory data distribution and increasing the weight of the density of important points. Secondly, the clustering results were evaluated by the Between-Within Proportion (BWP) index of cluster validity function. Finally, the optimal number of clusters and clustering were determined according to the clustering results evaluation. Theoretical researches and experimental results show that the improved algorithm can be better at extracting the trajectory key points and keeping the key path information. The accuracy of clustering results was 28 percentage points higher than that of the traditionalK-means algorithm and 17 percentage points higher than that of the Density-Based Spatial Clustering of Applications with Noise (DBSCAN) algorithm. The proposed algorithm has a better stability and a higher accuracy in trajectory data clustering.

K-means algorithm; density-based; characteristics of vehicle activity; weight of density; initial clustering center; Between-Within Proportion (BWP) index

2017- 04- 14;

2017- 06- 21。

國家自然科學(xué)基金資助項(xiàng)目(61571318)。

郝美薇(1993—),女,新疆烏魯木齊人,碩士研究生,主要研究方向:虛擬現(xiàn)實(shí)、大數(shù)據(jù); 戴華林(1974—),男,湖南武岡人,教授,博士,主要研究方向:虛擬現(xiàn)實(shí)、數(shù)字圖像處理; 郝琨(1979—),女,河北臨西人,副教授,博士,主要研究方向:網(wǎng)絡(luò)性能優(yōu)化、無線傳感網(wǎng)絡(luò)、大數(shù)據(jù)分析。

1001- 9081(2017)10- 2946- 06

10.11772/j.issn.1001- 9081.2017.10.2946

TP301.6

A

This work is partially supported by the National Natural Science Foundation of China (61571318).

HAOMeiwei, born in 1993, M. S. candidate. Her research interests include virtual reality, big data.

DAIHualin, born in 1974, Ph. D., professor. His research interests include virtual reality, digital image processing.

HAOKun, born in 1979, Ph. D., associate professor. Her research interests include network performance optimization, wireless sensor network, big data analysis.