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

郝美薇,戴華林,郝 琨

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

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

郝美薇*,戴華林,郝 琨

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

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

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

0 引言

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

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

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

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

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

對本文算法中提出的一些重要概念進行定義:

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

(1)

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

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

WDensr(pi)=

(2)

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

(3)

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

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

(4)

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

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

(5)

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

2 改進的基于密度的K-means算法

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

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

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

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

算法描述如下。

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

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

Begin:

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

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

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

5)遍歷集合X中的每一個對象xi。

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

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

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

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

Repeat:

8)取集合D中無中心點或邊界點標簽的第一個對象di。

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

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

Until: 遍歷集合D中全部對象，即集合D中的每個對象都含有中心點或邊界點標簽。

9)選取集合D中具有中心點標簽且密度標簽值較大的前K個對象加入集合T中。

10)遍歷集合X中的每一個對象xi，如果xi無中心點或邊界點標簽，則給xi加入噪點標簽；否則將xi加入集合P中。

11)輸出結(jié)果。

End

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

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

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

(6)

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

(7)

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

(8)

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

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

(9)

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

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

算法描述如下。

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

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

Begin:

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

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

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

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

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

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

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

5) 輸出結(jié)果;

End

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

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

3.1 實驗平臺與實驗數(shù)據(jù)

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

表1 實驗軌跡數(shù)據(jù)集

3.2 改進的基于密度的K-means算法實驗及分析

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

3.3 三種聚類算法對比實驗及分析

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

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

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

表3 三種算法的運算時間對比 s

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

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

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

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

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

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

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

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

4 結(jié)語

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

References)

[1] 王祖超, 袁曉如.軌跡數(shù)據(jù)可視分析研究[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 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] 何云斌, 劉雪嬌, 王知強, 等.基于全局中心的高密度不唯一的K-means算法研究[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)化的改進k_means算法[J]. 微電子學(xué)與計算機, 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)聚類個數(shù)和初始聚類中心點選取算法研究[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]. 計算機應(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é)基金資助項目(61571318)。

郝美薇(1993—),女,新疆烏魯木齊人,碩士研究生,主要研究方向:虛擬現(xiàn)實、大數(shù)據(jù); 戴華林(1974—),男,湖南武岡人,教授,博士,主要研究方向:虛擬現(xiàn)實、數(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.