ST-CFSFDP：快速搜索密度峰值的時(shí)空聚類算法

王培曉,張恒才,王海波,吳 升

1. 福州大學(xué)數(shù)字中國(guó)研究院(福建)，福建 福州 350002； 2. 中國(guó)科學(xué)院地理科學(xué)與資源研究所資源與環(huán)境信息系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100101； 3. 海西政務(wù)大數(shù)據(jù)應(yīng)用協(xié)同創(chuàng)新中心，福建 福州 350002； 4. 湖北工業(yè)大學(xué)經(jīng)濟(jì)與管理學(xué)院，湖北 武漢 430068

近年來(lái)，室內(nèi)外定位技術(shù)迅猛發(fā)展，如北斗、GPS、WiFi、藍(lán)牙、UWB(ultra-wideband)等，海量移動(dòng)終端不斷普及，如PDA、智能手機(jī)、平板電腦等，網(wǎng)絡(luò)技術(shù)不斷進(jìn)步，室內(nèi)外位置服務(wù)應(yīng)用不斷增多，如在線導(dǎo)航、基于位置的社交網(wǎng)絡(luò)、基于位置的廣告推送、商業(yè)物流調(diào)度與管理等，時(shí)空軌跡數(shù)據(jù)爆發(fā)式增長(zhǎng)[1-2]，為人類出行模式及人類移動(dòng)性、城市計(jì)算、社會(huì)計(jì)算、交通管理、城市規(guī)劃、人口流動(dòng)監(jiān)測(cè)、公共安全保障等研究提供了重要支撐[3-4]。

聚類算法是發(fā)現(xiàn)時(shí)空模式、探尋移動(dòng)規(guī)律的關(guān)鍵技術(shù)之一，旨在將實(shí)體劃分為一系列具有一定分布模式的簇集，同一簇集中的實(shí)體具有較大的相似度，不同簇集中的實(shí)體具有較大差別[5-8]，已廣泛應(yīng)用于犯罪熱點(diǎn)分析[9]、地震空間分布模式挖掘[10]、制圖自動(dòng)綜合[11]、遙感影像處理[12]、公共設(shè)施選址[13]、地價(jià)評(píng)估[14]、用戶停留區(qū)域識(shí)別[15]等研究。

目前，聚類算法大致分為[6,16]：基于劃分、基于層次、基于密度、基于格網(wǎng)的聚類算法。基于劃分聚類算法使用聚類中心(位于簇集中心附近的一個(gè)對(duì)象)來(lái)表示每個(gè)簇集，如經(jīng)典的k-means[17]算法和K-Medoid[18]算法，具有計(jì)算邏輯簡(jiǎn)單、運(yùn)算效率高等優(yōu)點(diǎn)；基于層次聚類算法使用逐步合并或分裂的策略來(lái)實(shí)現(xiàn)聚類，如改進(jìn)的CURE[19]算法，不僅能發(fā)現(xiàn)球形的空間簇集[20-21]，也能夠發(fā)現(xiàn)較為復(fù)雜結(jié)構(gòu)的空間簇集，但過多的超參數(shù)增加了算法的不確定性；基于密度聚類算法，如DBSCAN[22]將簇定義為密度相連的點(diǎn)的最大集合，但由于采用固定閾值聚類，難以適應(yīng)空間實(shí)體密度的變化[23]，OPTICS[22,24]算法為聚類分析生成一個(gè)增廣簇排序，解決了DBSCAN算法全局密度閾值的缺點(diǎn)；基于格網(wǎng)的聚類算法[25]其聚類效果依賴于網(wǎng)格的大小，如果網(wǎng)格劃分過細(xì)，則時(shí)間復(fù)雜度會(huì)顯著增加，如果網(wǎng)格劃分過粗，則聚類質(zhì)量難以得到保證。

此外，許多研究學(xué)者在經(jīng)典聚類算法基礎(chǔ)之上，提出了時(shí)空聚類算法，文獻(xiàn)[26—27]在基于密度聚類的基礎(chǔ)上提出了時(shí)空密度聚類ST-DBSCAN和ST-OPTICS算法，在時(shí)空密度聚類中，使用時(shí)間距離將空間鄰域擴(kuò)展到時(shí)空鄰域，從而尋找時(shí)空鄰域下密度相連的區(qū)域。文獻(xiàn)[10,28]采用時(shí)空距離(時(shí)間距離與空間距離的函數(shù))度量任意兩個(gè)時(shí)空事件的差異，后將時(shí)空距離應(yīng)用到傳統(tǒng)的聚類算法中挖掘時(shí)空事件的模式；文獻(xiàn)[29—30]在空間掃描統(tǒng)計(jì)的基礎(chǔ)上提出了時(shí)空掃描統(tǒng)計(jì)算法，通過滑動(dòng)掃描窗口(空間半徑和時(shí)間間隔定義的圓柱體)揭示時(shí)空事件隨時(shí)間聚類模式；文獻(xiàn)[31]通過窗口距離與時(shí)空最近鄰的概念重新定義了時(shí)空密度，從而提出了STSNN算法；文獻(xiàn)[32]從統(tǒng)計(jì)學(xué)的視角提出了WNN算法，將時(shí)空鄰域中的實(shí)體分為特征與噪聲兩個(gè)時(shí)空泊松點(diǎn)過程，使用密度相連(density-connective)的概念將特征分為多個(gè)簇集；文獻(xiàn)[33—34]分別在基于劃分和基于層次聚類基礎(chǔ)上提出了WKM和ST-AGNES算法，將其分別應(yīng)用于人類行為和用戶停留區(qū)域識(shí)別中，并取得了較好的聚類效果。

經(jīng)典的CFSFDP[35](clustering by fast search and find of density peaks)算法結(jié)合了基于劃分和基于密度聚類算法的優(yōu)點(diǎn)，不僅可以發(fā)現(xiàn)多密度任意形狀的簇集，還可以通過決策圖輔助識(shí)別聚類中心的個(gè)數(shù)。但該算法無(wú)法很好地應(yīng)用于時(shí)空數(shù)據(jù)聚類研究之中，究其原因在于CFSFDP算法未考慮時(shí)間約束，如圖1所示，并沒有正確識(shí)別簇集。如錯(cuò)誤地將簇集A(t5,t6,t7,t8)、C(t15,t16,t17,t18)合并為一個(gè)簇集，且并不能發(fā)現(xiàn)簇集之間的順序關(guān)系。此外，在單簇集中存在多個(gè)密度峰值點(diǎn)時(shí)，該算法將會(huì)產(chǎn)生錯(cuò)誤的時(shí)空聚類結(jié)果。

圖1 是否考慮時(shí)間約束的兩種聚類結(jié)果Fig.1 Comparison of clustering results with and without time constraints

鑒于此，本文提出一種快速搜索密度峰值的時(shí)空聚類算法(spatial-temporal clustering by fast search and find of density peaks，ST-CFSFDP)，在CFSFDP算法的基礎(chǔ)上引入了時(shí)間約束，修改了樣本屬性值的計(jì)算策略。采用模擬數(shù)據(jù)和真實(shí)數(shù)據(jù)案例進(jìn)行算法有效性的驗(yàn)證。模擬數(shù)據(jù)試驗(yàn)結(jié)果表明，與CFSFDP算法相比，ST-CFSFDP算法不僅可以克服單簇集中可能存在多密度峰值的不足，且可以區(qū)分并識(shí)別相同位置不同時(shí)間的簇集。以移動(dòng)對(duì)象軌跡中停留點(diǎn)識(shí)別為例，ST-CFSFDP算法較經(jīng)典的ST-DBCSAN、ST-OPTICS和ST-AGNES算法識(shí)別正確率分別可提高5.2%、4.2%和7.6%。

1 ST-CFSFDP算法

1.1 CFSFDP算法

ρi=∑jχ(dij-dc)

(1)

(2)

式中，dij為樣本點(diǎn)i和樣本點(diǎn)j之間的空間距離；dc是人為指定的超參數(shù)，稱為截?cái)嗑嚯x；χ(x)表示0～1函數(shù)，當(dāng)x<0時(shí)，χ(x)=1,當(dāng)x≥0時(shí)，χ(x)=0，即局部密度ρi表示落在以樣本點(diǎn)xi為圓心，截?cái)嗑嚯xdc為半徑的圓形區(qū)域中樣本點(diǎn)個(gè)數(shù)；δi表示局部密度大于xi的所有樣本點(diǎn)中，距離xi最近的樣本點(diǎn)與xi之間的距離,由于式(2)無(wú)法計(jì)算密度最大的樣本點(diǎn)，因此密度最大的樣本點(diǎn)δi=max (dij)。

CFSFDP算法通過各樣本點(diǎn)的局部密度ρi和距離δi確定聚類中心(ρi和δi均相對(duì)較大的樣本點(diǎn))。如圖2(a)所示，對(duì)于數(shù)據(jù)集X中每一個(gè)樣本點(diǎn)xi，計(jì)算其局部密度ρi和距離δi，生成相應(yīng)的三元組(ρi,δi,λi)，λi表示δi對(duì)應(yīng)的節(jié)點(diǎn)編號(hào)，用于非聚類中心樣本點(diǎn)的類別分配，使用ρi和δi構(gòu)造數(shù)據(jù)集X的決策圖(decision graph)，如圖2(b)所示。容易發(fā)現(xiàn)，標(biāo)號(hào)為①和⑩的樣本點(diǎn)同時(shí)具有較大的ρ值和δ值，因此被確定為數(shù)據(jù)集X的兩個(gè)聚類中心。為了更加方便地確定數(shù)據(jù)集X中的聚類中心，文獻(xiàn)[35]提出了一個(gè)綜合考慮ρ和δ的量γ。

γi=ρiδi

(3)

(4)

1.2 基于時(shí)空約束的ST-CFSFDP聚類算法

ST-CFSFDP算法首先在CFSFDP算法的基礎(chǔ)上引入了第2個(gè)超參數(shù)tc，針對(duì)時(shí)間序列數(shù)據(jù)集X，修改了ρ與δ的計(jì)算策略。其中時(shí)間約束下的局部密度ρ計(jì)算方法如式(5)所示

ρi=∑jχ(dij-dc,tij-tc)

(5)

(6)

式中，tqiqj表示樣本點(diǎn)xqi與樣本點(diǎn)xqj的時(shí)間距離，即修改后的δ根據(jù)樣本點(diǎn)的局部密度降序依次計(jì)算，即使單簇集中存在多個(gè)密度峰值，依舊僅有一個(gè)樣本點(diǎn)被選做聚類中心。然而當(dāng)單簇集的時(shí)間跨度過長(zhǎng)時(shí)，僅使用時(shí)間距離計(jì)算δ同樣會(huì)將單簇集分裂成多個(gè)小簇集。如圖4(b)所示，假設(shè)簇集C內(nèi)部的樣本點(diǎn)4、k具有較高的局部密度ρ，由于兩樣本點(diǎn)的時(shí)間跨度較大，兩點(diǎn)都將具有較大的δ，依據(jù)本文的計(jì)算策略γi=ρiδi，簇集C將產(chǎn)生兩個(gè)聚類中心。為解決這個(gè)問題，本文添加了聚類中心合并的過程，將識(shí)別的聚類中心按時(shí)間順序鏈接，分別計(jì)算相鄰兩聚類中心的距離，若小于距離鄰域dc，將相鄰兩個(gè)聚類中心合并，經(jīng)聚類中心合并后，聚類中心的個(gè)數(shù)將與簇集的個(gè)數(shù)一一對(duì)應(yīng)。

在ST-CFSFDP算法中，剩余樣本點(diǎn)的分配沿時(shí)間軸進(jìn)行。如圖5所示，針對(duì)時(shí)間順序分布的數(shù)據(jù)集X，首先識(shí)別數(shù)據(jù)集中的聚類中心(紅色樣本點(diǎn)為合并后的聚類中心)，然后每個(gè)聚類中心沿時(shí)間軸向前、后搜索本簇集中的剩余樣本點(diǎn)，以聚類中心CP2向前搜索為例，尋找CP2前一時(shí)刻的樣本點(diǎn)t15，計(jì)算樣本點(diǎn)與CP1和CP2的距離，如果距離CP2近，則將樣本點(diǎn)t15歸屬于CP2，否則聚類中心CP2向前搜索完畢，以同樣的策略向后搜索最終確定該簇集包含的所有樣本。所有聚類中心依次搜索完畢后，未被分配類別的樣本點(diǎn)為離群點(diǎn)，以圖5黃色樣本點(diǎn)為例，聚類中心CP2延時(shí)間軸向后搜索時(shí)，由于黃色樣本點(diǎn)OP1距離聚類中心CP3較近，因此聚類中心CP2向后搜索結(jié)束，當(dāng)聚類中心CP3延時(shí)間軸向前搜索時(shí)，黃色樣本點(diǎn)OP2距離聚類中心CP2較近，因此聚類中心CP3向前搜索結(jié)束，此時(shí)黃色樣本點(diǎn)OP1與OP2之間的樣本點(diǎn)為離群點(diǎn)。ST-CFSFDP算法整體實(shí)現(xiàn)流程如下。

算法 快速搜索密度峰值的時(shí)空聚類算法

輸入：序列數(shù)據(jù)sequence=={ti,pi},距離閾值disthr,時(shí)間閾值tthr

輸出：每一個(gè)樣本點(diǎn)的聚類類別labels={ci}

functionST_CFSFDP (sequence, disthr,tthr)

∥計(jì)算樣本點(diǎn)的空間距離矩陣

stDisMat=computeSpatialDisMat(sequence)

∥計(jì)算樣本點(diǎn)的時(shí)間距離矩陣

timeDisMat=computeTimeDisMat(sequence)

∥計(jì)算樣本點(diǎn)在時(shí)空約束下的局部密度

densityArr=computeDensity(stDisMat,disthr,

timeDisMat,tthr)

∥獲得局部密度降序排列的下標(biāo)序列

densitySortArr=argsort(densityArr)

∥初始化數(shù)組，用于存放每個(gè)軌跡點(diǎn)的屬性δ

closestDis=[]

fori=0→len(densitySortArr)do

∥獲得當(dāng)前樣本點(diǎn)的索引

node=densitySortArr[i]

∥獲得比當(dāng)前樣本點(diǎn)局部密度更大的索引集合

nodeIdArr=densitySortArr[i+1;]

∥計(jì)算每一個(gè)樣本點(diǎn)的屬性δ

closestDis[node]=compute(node, nodeIdArr,

stDisMat,timeDisMat)

endfor

∥計(jì)算每一個(gè)樣本點(diǎn)的屬性γ

gamma=closestDis*densityArr

∥通過決策圖得到聚類的數(shù)目

classNum=getNumFromDecisionGraph(gamma)

∥獲取樣本點(diǎn)的聚類類別

labels=extract_clustering(gamma,classNum,

stDisMat,timeDisMat)

returnlabels

endfunction

1.3 算法時(shí)間復(fù)雜度分析

ST-CFSFDP算法的時(shí)間復(fù)雜度定性描述了該算法的運(yùn)行時(shí)間。ST-CFSFDP算法的時(shí)間復(fù)雜度主要由兩部分組成：計(jì)算樣本點(diǎn)的局部密度ρ和距離δ，其中ρ和δ的計(jì)算都涉及樣本點(diǎn)之間的距離計(jì)算。在數(shù)據(jù)集規(guī)模為n的情況下，①計(jì)算任意兩個(gè)樣本點(diǎn)之間的距離，時(shí)間復(fù)雜度為O(n2)；②計(jì)算n個(gè)樣本點(diǎn)的局部密度δ，時(shí)間復(fù)雜度為O(n2)；③計(jì)算n個(gè)樣本點(diǎn)的距離δ，時(shí)間復(fù)雜度同樣為O(n2)。因此，ST-CFSFDP算法的時(shí)間復(fù)雜度為O(n2)。

圖2 數(shù)據(jù)集X及其決策圖Fig.2 Dataset X and its decision graph

圖3 遞減順序排列的γFig.3 The value of γ in decreasing order

圖4 CFSFDP算法改進(jìn)Fig.4 Improvement of CFSFDP algorithm

圖5 ST-CFSFDP算法剩余點(diǎn)分配Fig.5 Distribution of non-clustered center points of ST-CFSFDP algorithm

2 試驗(yàn)結(jié)果與討論

2.1 試驗(yàn)數(shù)據(jù)

為分析ST-CFSFDP算法的性能，分別采用模擬數(shù)據(jù)集和真實(shí)用戶軌跡進(jìn)行試驗(yàn)。采用模擬數(shù)據(jù)集進(jìn)行試驗(yàn)的主要目的是以二維圖形的方式直觀地展示聚類結(jié)果，采用真實(shí)用戶軌跡進(jìn)行試驗(yàn)的主要目的是使用相關(guān)指標(biāo)定量地評(píng)價(jià)聚類算法的性能。

本文共模擬4組數(shù)據(jù)量不同的時(shí)序數(shù)據(jù)集X。每組模擬數(shù)據(jù)集的生成過程如下：首先生成指定的具有時(shí)間約束的幾何形狀，然后根據(jù)指定的幾何形狀等時(shí)間間隔采樣而成，其中一組數(shù)據(jù)如圖6(a)、(b)所示。

真實(shí)數(shù)據(jù)來(lái)源于濟(jì)南市某廣場(chǎng)移動(dòng)用戶的WiFi定位數(shù)據(jù)。用戶移動(dòng)定位數(shù)據(jù)是一種典型的時(shí)空數(shù)據(jù)，在一定程度反映了用戶的個(gè)人生活習(xí)慣和日常行為模式。時(shí)空聚類算法常用于從用戶移動(dòng)定位數(shù)據(jù)識(shí)別用戶的停留區(qū)域，從而進(jìn)一步挖掘用戶的興趣愛好，因此本文將ST-CFSFDP算法應(yīng)用于停留區(qū)域識(shí)別并定量的評(píng)價(jià)該算法的性能。移動(dòng)用戶定位數(shù)據(jù)覆蓋廣場(chǎng)5個(gè)樓層，平均采樣為1～10 s不等，定位精度約為3 m。由于定位數(shù)據(jù)難以獲取用戶停留區(qū)域的標(biāo)注數(shù)據(jù)，因此本文采用爬蟲技術(shù)從百度地圖上獲取了該廣場(chǎng)的商鋪數(shù)據(jù)，借助商鋪數(shù)據(jù)標(biāo)注用戶軌跡中的停留信息。標(biāo)注過程如下：首先對(duì)商鋪數(shù)據(jù)與藍(lán)牙定位數(shù)據(jù)求交，然后統(tǒng)計(jì)某用戶在商鋪內(nèi)部的持續(xù)停留時(shí)間，若用戶在商鋪內(nèi)部的持續(xù)停留時(shí)間超過一定閾值，則將相應(yīng)的軌跡點(diǎn)標(biāo)注為停留點(diǎn)。依據(jù)上述規(guī)則，本文共標(biāo)注472條用戶軌跡(當(dāng)用戶軌跡中停留區(qū)域過少時(shí)，本文認(rèn)為該軌跡價(jià)值不高，刪除該軌跡)，軌跡點(diǎn)總記錄量為935 639個(gè)。經(jīng)標(biāo)注后的某用戶軌跡數(shù)據(jù)如表1所示，每條記錄包括用戶唯一標(biāo)識(shí)ID、記錄時(shí)間、用戶位置(X、Y坐標(biāo)及所在樓層ID)、停留的商鋪ID(-1代表用戶未停留)。

圖6 模擬數(shù)據(jù)集Fig.6 Simulated data sets

表1 單用戶軌跡數(shù)據(jù)實(shí)例

2.2 算法評(píng)價(jià)指標(biāo)及對(duì)比試驗(yàn)選擇

本文以準(zhǔn)確率(accuracy)和召回率(recall)作為停留區(qū)域識(shí)別的定量評(píng)價(jià)指標(biāo)。用戶停留區(qū)域可理解為時(shí)間約束下用戶軌跡中的簇集，進(jìn)一步可抽象為[36]S=(userID,Lng,Lat,arrT,levT)，(Lng,Lat)表示停留區(qū)域內(nèi)的某個(gè)點(diǎn)坐標(biāo)，其應(yīng)最大概率出現(xiàn)在停留區(qū)域內(nèi)部，一般為區(qū)域內(nèi)所有軌跡點(diǎn)的均值坐標(biāo)，本文為聚類中心坐標(biāo)；arrT表示用戶抵達(dá)停留區(qū)域的時(shí)間；levT表示用戶離開停留區(qū)域的時(shí)間。停留區(qū)域識(shí)別結(jié)果是否正確主要依賴3個(gè)方面：①識(shí)別的停留區(qū)域和標(biāo)注的停留區(qū)域數(shù)量是否一致；②識(shí)別的停留區(qū)域(Lng,Lat)坐標(biāo)是否處于標(biāo)注商鋪內(nèi)部；③識(shí)別的停留區(qū)域起止時(shí)間(arrT,levT)是否與標(biāo)注數(shù)據(jù)一致。結(jié)合上述3個(gè)方面，本文accuracy和recall計(jì)算方法如式(7)、式(8)所示。

(7)

(8)

式中，SClabel表示標(biāo)注的停留區(qū)域個(gè)數(shù)；SCalgorithm表示算法識(shí)別的停留區(qū)域個(gè)數(shù)；SCcorrect表示算法判斷正確的停留區(qū)域個(gè)數(shù)，本文采用SO和TO[15]兩個(gè)函數(shù)共同判斷某個(gè)停留區(qū)域是否識(shí)別正確(SO函數(shù)判斷識(shí)別結(jié)果和標(biāo)注數(shù)據(jù)在空間上是否鄰近，TO函數(shù)判斷識(shí)別結(jié)果和標(biāo)注數(shù)據(jù)在時(shí)間上是否重合)。本文將ST-DBSCAN、ST-OPTICS、ST-AGNES、ST-CFSFDP時(shí)空聚類算法進(jìn)行對(duì)比，探討4種時(shí)空聚類算法在不同閾值下準(zhǔn)確率和召回率的變化情況。

2.3 模擬數(shù)據(jù)集上的測(cè)試結(jié)果分析

CFSFDP與ST-CFSFDP算法在模擬數(shù)據(jù)集上的聚類結(jié)果如圖7(e)、7(f)所示：①對(duì)于區(qū)域A，由于存在兩個(gè)聚類中心，使用CFSFDP算法，分裂成兩個(gè)小簇集，產(chǎn)生了錯(cuò)誤的聚類結(jié)果，而使用ST-CFSFDP算法，依據(jù)改進(jìn)的屬性計(jì)算策略，只聚類成一個(gè)簇集，從而得到更合理的聚類結(jié)果；②對(duì)于區(qū)域B，由于CFSFDP算法未考慮數(shù)據(jù)的時(shí)間約束，因此只聚類出一個(gè)簇集，而ST-CFSFDP算法考慮數(shù)據(jù)的時(shí)間約束，所以可以聚類出相同位置但不同時(shí)間的兩個(gè)簇集；③對(duì)于區(qū)域C，使用ST-CFSFDP算法識(shí)別出兩個(gè)聚類中心，但僅產(chǎn)生一個(gè)簇集，原因是其中一個(gè)小簇集時(shí)間跨度過長(zhǎng)，在該簇集中識(shí)別出兩個(gè)聚類中心，但ST-CFSFDP算法最終會(huì)將這兩個(gè)聚類中心合并(相鄰聚類中心的距離小于距離閾值dc)，因此最終只產(chǎn)生一個(gè)簇集。綜上所述，與CFSFDP算法相比，ST-CFSFDP算法不僅克服了單簇集中可能存在多密度峰值的不足，且實(shí)現(xiàn)了考慮時(shí)間約束的時(shí)空聚類。ST-CFSFDP算法與ST-DBSCAN、ST-OPTICS、ST-AGNES算法的聚類結(jié)果如圖8所示，進(jìn)一步說(shuō)明ST-CFSFDP算法具有發(fā)現(xiàn)時(shí)空簇集的能力。

由上文分析可知，ST-CFSFDP算法具有良好的聚類性能，不僅解決了單簇集存在多密度峰值的問題，還能正確發(fā)現(xiàn)時(shí)空數(shù)據(jù)集的簇分布特征。進(jìn)一步分析算法的運(yùn)行時(shí)間，表2為兩種聚類算法在4組模擬數(shù)據(jù)集上運(yùn)行時(shí)間的對(duì)比。試驗(yàn)結(jié)果可以看出，ST-CFSFDP算法的時(shí)間開銷要略大于CFSFDP算法，這主要是因?yàn)镾T-CFSFDP算法在計(jì)算樣本點(diǎn)局部密度時(shí)增加了時(shí)間開銷。但是這兩種算法的時(shí)間復(fù)雜度的均為O(n2)。與ST-DBSCAN、ST-OPTICS、ST-AGNES算法的運(yùn)行時(shí)間相比，ST-CFSFDP的運(yùn)行時(shí)間較小，能夠較快地得到聚類的運(yùn)行結(jié)果。

表2 時(shí)空聚類算法運(yùn)行時(shí)間在模擬數(shù)據(jù)集對(duì)比分析

Tab.2 The running time of spatio-temporal clustering on simulated data sets

數(shù)據(jù)集X記錄數(shù)CFSFDPST-CFSFDPST-DBSCANST-OPTICSST-AGNES3140.00450.00480.0052 0.03120.003334540.21590.29820.80581.97230.232463630.68390.84203.122110.6710.7918156234.00945.879115.627626.5154.8917

2.4 真實(shí)數(shù)據(jù)集上的測(cè)試結(jié)果分析

為評(píng)價(jià)ST-CFSFDP算法性能，本文參考室內(nèi)房間寬度將初始距離閾值設(shè)置為1 m，并以0.5 m步長(zhǎng)遞增；初始時(shí)間閾值設(shè)置為50 s，以20 s步長(zhǎng)遞增；以啟發(fā)式的方法[22]設(shè)置ST-DBSCAN、ST-OPTICS算法中minPts參數(shù)，minPts=ln(N)，N為某用戶軌跡點(diǎn)數(shù)量。算法識(shí)別結(jié)果的準(zhǔn)確率對(duì)比如圖9所示。4種算法的識(shí)別準(zhǔn)確率變化趨勢(shì)在整體上較為相似，在時(shí)間閾值固定的情況下，準(zhǔn)確率均隨著距離閾值的增加呈現(xiàn)先增加后下降的趨勢(shì)。綜合4種算法在不同閾值下的表現(xiàn)可以發(fā)現(xiàn)：①ST-CFSFDP算法對(duì)參數(shù)敏感度低，ST-DBSCAN與ST-OPTICS算法對(duì)參數(shù)敏感度較高(準(zhǔn)確率隨著超參數(shù)的改變波動(dòng)較大)；②相較ST-DBSCAN、ST-OPTICS、ST-AGNES算法，ST-CFSFDP算法準(zhǔn)確率較高，在時(shí)間閾值90 s時(shí)最為明顯，ST-CFSFDP算法準(zhǔn)確率最高可達(dá)82.4%，與現(xiàn)有算法相比，最高可提升7.6%；③ST-DBSCAN、ST-OPTICS算法本質(zhì)上是一種算法，所以兩種算法的準(zhǔn)確率高度一致；④ST-AGNES算法隱含時(shí)間約束，僅需要距離閾值即可完成聚類，因此算法準(zhǔn)確率不受時(shí)間閾值的影響。

算法識(shí)別結(jié)果的召回率對(duì)比如圖10所示。4種算法的召回率均隨距離閾值增加呈現(xiàn)先增加后下降的趨勢(shì)，與算法準(zhǔn)確率一致。當(dāng)時(shí)間閾值為90 s時(shí)，4種算法的召回率較高，原因在于人工標(biāo)注時(shí)用戶的停留時(shí)間閾值與90 s較接近。在此閾值下4種算法將會(huì)得到較精確的識(shí)別結(jié)果。與此同時(shí)ST-CFSFDP算法的召回率略高于其余3種算法且準(zhǔn)確率與召回率波動(dòng)最小，原因?yàn)镾T-CFSFDP算法采用聚類中心作為用戶最可能的停留位置，而聚類中心作為局部范圍內(nèi)密度最大的點(diǎn)，受閾值影響較小。本文將4種算法最高準(zhǔn)確率相應(yīng)的運(yùn)行時(shí)間進(jìn)行對(duì)比，結(jié)果如表3所示。ST-CFSFDP算法與ST-AGNES算法相比，ST-CFSFDP算法的運(yùn)行時(shí)略高，但算法的識(shí)別正確率卻可提升7.6%；與ST-DBSCAN算法相比，ST-CFSFDP算法的運(yùn)行時(shí)間略有降低且識(shí)別準(zhǔn)確率提升了5.2%；與ST-OPTICS算法相比，ST-CFSFDP算法的運(yùn)行時(shí)間得到了大幅度提升且識(shí)別準(zhǔn)確率也有一定程度的提高。

表3 4種算法運(yùn)行時(shí)間對(duì)比分析

3 結(jié)論與展望

CFSFDP算法是一種新穎的空間聚類算法，通過計(jì)算樣本點(diǎn)的屬性值γ，能夠快速發(fā)現(xiàn)數(shù)據(jù)集中的密度峰值點(diǎn)。然而當(dāng)數(shù)據(jù)集的某簇集存在多密度峰值點(diǎn)時(shí)，該算法易產(chǎn)生錯(cuò)誤的聚類結(jié)果，且CFSFDP算法無(wú)法實(shí)現(xiàn)考慮時(shí)間約束的時(shí)空聚類。針對(duì)以上兩點(diǎn)不足，本文提出了時(shí)空聚類算法ST-CFSFDP。ST-CFSFDP算法在CFSFDP算法基礎(chǔ)上加入時(shí)間約束，并修改了樣本屬性值的計(jì)算策略。為驗(yàn)證算法的有效性，首先采用模擬數(shù)據(jù)進(jìn)行定性試驗(yàn)。結(jié)果表明，與原有的CFSFDP算法相比，ST-CFSFDP算法不僅可以克服單簇集中可能存在多密度峰值的不足，且可以區(qū)分并識(shí)別相同位置不同時(shí)間的簇集。最后本文將ST-CFSFDP算法應(yīng)用于用戶的停留區(qū)域識(shí)別，結(jié)果表明，ST-CFSFDP算法在時(shí)間閾值90 s、距離閾值5 m的識(shí)別正確率高達(dá)82.4%，較經(jīng)典的ST-DBCSAN、ST-OPTICS和ST-AGNES算法分別提高了5.2%、4.2%和7.6%。

本文尚在以下方面存在不足，需在后續(xù)工作中進(jìn)一步研究：受試驗(yàn)數(shù)據(jù)采樣間隔的限制，現(xiàn)有算法僅采用秒級(jí)時(shí)間粒度的數(shù)據(jù)進(jìn)行驗(yàn)證,當(dāng)定位數(shù)據(jù)的采樣間隔增大時(shí)，算法識(shí)別準(zhǔn)確率及可靠性需要進(jìn)一步探究。

致謝：感謝上海圖聚智能科技股份有限公司為本研究提供室內(nèi)定位軌跡試驗(yàn)數(shù)據(jù)!