劉 萌，鄔群勇，邱端昇，孫 梅，張 強

福州大學(xué)福建省空間信息工程研究中心空間數(shù)據(jù)挖掘與信息共享教育部重點實驗室，福建 福州 350002

?

簽到位置數(shù)據(jù)的密度峰值快速搜索與聚類方法

劉 萌，鄔群勇，邱端昇，孫 梅，張 強

福州大學(xué)福建省空間信息工程研究中心空間數(shù)據(jù)挖掘與信息共享教育部重點實驗室，福建 福州 350002

位置簽到數(shù)據(jù)蘊含了城市居民活動變化。由于客戶端位置候選問題，不同的簽到行為以同一候選位置簽到時會產(chǎn)生位置重復(fù)現(xiàn)象。針對現(xiàn)有密度聚類方法在簽到數(shù)據(jù)聚類上存在的問題，以快速搜索和查找密度峰值聚類算法(CFSFDP)為基礎(chǔ)，提出了簽到位置數(shù)據(jù)的密度峰值快速搜索與聚類方法。首先，引入位置重復(fù)頻率來表達簽到位置重復(fù)，然后，對原始簽到位置數(shù)據(jù)點統(tǒng)計位置重復(fù)頻率并重新設(shè)計數(shù)據(jù)結(jié)構(gòu)，以新的空間點要素為研究對象尋找密度峰值點；最后，構(gòu)建了峰值點密度簇聚類算法，在點要素集聚類過程中考慮密度連通性來保證峰值密度簇的連續(xù)與完整。試驗表明，所提出的聚類方法有效避免了重復(fù)度較高的離群位置對象選為峰值并聚類的情況，并具有良好的空間適應(yīng)性。所提取的密度峰值點不僅可以用來表示熱區(qū)的中心，還能夠反映熱區(qū)的集中趨勢，進而可以幫助探索熱區(qū)的動態(tài)變化情況。

簽到位置數(shù)據(jù)；活動熱區(qū)；空間聚類；密度峰值聚類；位置重復(fù)頻率

位置簽到是基于位置的社交網(wǎng)絡(luò)(LBSN)中一個重要的功能，指的是利用具有位置服務(wù)(LBS)的設(shè)備記錄用戶當(dāng)前位置等信息并發(fā)布到社交網(wǎng)絡(luò)上的行為[1-3]。簽到的位置在形態(tài)上表現(xiàn)為點要素，在城市總體空間中具有分塊聚集的特征，一定程度上反映了城市居民的空間活動情況。分析和研究位置簽到所形成的熱點熱區(qū)是面向地理空間的居民移動性研究的重要組成[4]，可以幫助更好地把握城市空間結(jié)構(gòu)、探索城市的商圈及變化[5]進而能夠協(xié)助解決城市公共交通、資源配置、規(guī)劃決策等問題。

現(xiàn)有的位置簽到熱區(qū)研究方式主要包括標(biāo)準差橢圓法[6]與核密度分析法[1,7-8]。標(biāo)準差橢圓法僅能夠大略表示熱區(qū)所在的空間范圍與擴張方向；對于核密度分析法來說，由于要素的密度是由核密度函數(shù)計算而來，密度區(qū)外形往往過于平滑并趨于球狀，無法較為準確地反映簽到熱區(qū)的真實空間形態(tài)。空間聚類是空間數(shù)據(jù)挖掘與空間分析的重要手段之一[9]?；诿芏鹊木垲惸軌蜃詣犹蕹臻g分布較稀疏的對象，將局部空間密度較高的對象聚集為一類，發(fā)現(xiàn)任意形狀的簇[10-11]，可以較好地發(fā)現(xiàn)位置簽到數(shù)據(jù)所形成的活動熱區(qū)，并能體現(xiàn)其真實形態(tài)特征[12-13]?；诿芏鹊木垲惙ㄈ鏒BSCAN[14-15]、ADBSC[16]、LDBSC[9]以及格網(wǎng)密度法[17]都把密度簇內(nèi)部看成是密度均勻的，并且直接以對象間的空間距離作為相似性度量指標(biāo)來進行聚類，沒有考慮空間位置上的重復(fù)性問題。然而，現(xiàn)有的LBSN位置簽到普遍帶有位置候選功能，列出了當(dāng)前可能處于的候選位置讓用戶自行選擇。當(dāng)不同的簽到行為(不同用戶或不同時間的簽到)選擇同一候選位置進行簽到時就會產(chǎn)生簽到位置重復(fù)現(xiàn)象。這樣以來很可能將重復(fù)位置上的全部對象聚成一類，且錯誤地獲取密度峰值等重要信息，由此得到的聚類熱區(qū)很難反映其變化趨勢，在表達上難以到達較好的效果。

文獻[18]提出了快速搜索和查找密度峰值聚類算法(clustering by fast search and find of density peaks，CFSFDP)。該聚類方法先快速尋找密度峰值，然后進行密度聚類，具有效率高、結(jié)果穩(wěn)定的優(yōu)點，且在低維數(shù)據(jù)上表現(xiàn)效果良好[19]。本文在CFSFDP算法思想的基礎(chǔ)上，選擇新浪微博位置簽到數(shù)據(jù)為數(shù)據(jù)源，針對簽到位置的重復(fù)特性，圍繞密度峰值點搜索和基于密度峰值的聚類兩個方面提出了簽到位置數(shù)據(jù)的密度峰值快速搜索與聚類方法，一方面可以幫助更好地尋找城市活動熱區(qū)及熱區(qū)中心，另一方面也為LBSN位置簽到的聚類研究提供了一種方法。

1 研究區(qū)簽到位置數(shù)據(jù)分析

本研究選擇了福州市主城區(qū)作為研究區(qū)，其范圍覆蓋了福州市三環(huán)路內(nèi)部區(qū)域。數(shù)據(jù)來自于新浪微博API采集2015年8月1日至10月31日的新浪微博位置簽到原始文本，簽到總量115 191條，選取其中的簽到ID、簽到經(jīng)緯度信息來構(gòu)建簽到位置點對象。帶有位置的簽到72 354，重復(fù)率37.2%，最大重復(fù)數(shù)721條。數(shù)據(jù)位置分布如圖1所示，位置重復(fù)數(shù)量統(tǒng)計情況如圖2所示。在構(gòu)建空間點對象之前需要將經(jīng)緯度坐標(biāo)轉(zhuǎn)換成平面坐標(biāo)以方便計算對象間的空間距離，單位為米。

圖1 簽到對象的位置分布Fig.1 Location distribution of check-in points

2 簽到位置數(shù)據(jù)的密度峰值快速搜索與聚類方法

2.1 CFSFDP算法分析

CFSFDP算法基于對象的局部密度來搜索密度峰值并聚類，兼有密度聚類和譜聚類的特性。密度峰值點的最主要特征是其局部密度比包圍它的臨近點的局部密度都要大，并且距離其他密度峰值點都較遠[20-21]。在搜索密度峰值前首先需要計算每個對象pi的兩個量值：ρi和δi。

圖2 福州市主城區(qū)簽到位置重復(fù)數(shù)量統(tǒng)計圖Fig.2 Statistic of reduplication of check-in locations about Fuzhou

其中,ρi表示pi的局部密度，含義是數(shù)據(jù)集中到pi的距離小于或等于dc的對象個數(shù)。dc稱為截斷距離，為用戶給出的參數(shù)。ρi的具體表達如下

ρi=∑j≠iχ(dij-dc)

(1)

式中，dij表示第i與第j對象之間的空間距離；χ(x)計算方法為：若x<0，χ(x)=1；若x>=0，χ(x)=0。為避免不同的點對象具有相同局部密度而且能夠識別異形簇，一般采用指數(shù)核的形式來定義局部密度[21]，表達如下

(2)

δi的具體表達如下

(3)

式中，δi表示密度大于ρi的對象中與pi最近距離。若ρi為最大值，δi為距離pi最遠對象與pi間距離。

計算出全部ρi和δi后，根據(jù)CFSFDP對峰值點的定義，從決策圖上選擇橫縱坐標(biāo)都比較大的點作為密度峰值點。密度峰值搜索完成之后，根據(jù)參數(shù)dc來確定邊界區(qū)密度閾值，對余下對象按照閾值進行密度劃分從而實現(xiàn)去噪目的。最終所獲得的密度簇成員包含了密度峰值點和密度核心點兩大部分，靠近每個密度簇周圍的噪聲點稱之為簇的光暈(halo)[18]。

CFSFDP算法直接基于點對象的空間距離來搜索峰值點并聚類。對于存在位置重復(fù)的簽到對象，直接運用可能會產(chǎn)生如下效果：①位置重復(fù)數(shù)量較多的點及其臨近對象的局部密度較大，更容易被判斷成密度峰值點。理想的峰值點應(yīng)當(dāng)是被眾多低于其局部密度的點所包圍；但實際中，位置重復(fù)數(shù)量較多的對象有可能位于簇的邊緣，甚至其位置在空間上是離群的，從而降低了聚類簇的表達效果；②由于同一重復(fù)位置上對象的局部密度和δ值都是相同的，很有可能獲得一系列位置相同的峰值點。因此，在峰值點的搜索過程中必須考慮位置重復(fù)情況。作為密度峰值發(fā)現(xiàn)的第一步，首先需要對局部密度的概念進行修改。

2.2 考慮簽到位置重復(fù)的密度峰值點快速搜索

2.2.1 局部密度改進方案

為了保留位置重復(fù)信息，需要對原始對象的數(shù)據(jù)結(jié)構(gòu)進行修改。將重復(fù)的空間位置進行合并，并為之添加一個屬性：位置重復(fù)頻率dFreq，dFreq∈N+，用以表達該位置上原始對象的實際數(shù)量。經(jīng)過位置合并后，一種新型的空間點要素FPoint的數(shù)據(jù)結(jié)構(gòu)如下：

Class FPoint{

int PID, ∥點要素編號

doubleX, ∥墨卡托橫坐標(biāo)

doubleY, ∥墨卡托縱坐標(biāo)

int dFreq, ∥位置重復(fù)頻率(默認值1)

double density, ∥局部密度(ρ)

double delta, ∥高密度點最鄰近值(δ值)

int ptype, ∥要素種類(0--未分配；1--峰值；2--核心點；3--邊界點；-1--噪聲點)

intclusterid∥所屬簇的ID

}

FPoint對象間的空間密度關(guān)系由空間位置和位置重復(fù)頻率dFreq共同決定，其中dFreq作為要素密度關(guān)系表達的第三維，屬于縱向的量值，反映了該位置上簽到數(shù)量規(guī)模。為更準確表達簽到位置在城市空間中的密度分布情況，F(xiàn)Point對象的局部密度必須要考慮位置重復(fù)頻率的影響。本文將重復(fù)頻率作為一種影響因子，在局部密度的定義中以權(quán)重的形式單獨考慮，F(xiàn)Point對象FPi的局部密度ρi表達如下

ρi=df·ρd

(4)

式中，ρd是按照式(1)所算出的局部密度，僅與對象位置有關(guān)；df表示的是重復(fù)頻率dFreq在局部密度中占的權(quán)重。對于df，一種是直接將位置重復(fù)頻率作為權(quán)重值，由此計算出的局部密度記為ρdf。由于FPoint對象集合的dFreq極差一般很大，會導(dǎo)致ρdf之間的極差過大，容易將局部密度過大的邊緣點或離群點作為密度峰值，起不到預(yù)期效果。另一種是對dFreq+1取對數(shù)作為df，由此算出的局部密度記為ρdlnf，能夠很好地降低dFreq所造成的極差。具體表達如下

(5)

式中，dFreq表示當(dāng)前對象的位置重復(fù)頻率；dij表示第i與第j對象之間的空間距離；dc為截斷距離。

以上3種形式局部密度值的極差情況如表1所示。

表1 3種局部密度極差統(tǒng)計表

Tab.1 Statistic of range for three type of local density expressions

局部密度最大值最小值極差ρd1264.34721.6411262.7062ρdf621054.07961.641621052.4386ρflnf6660.61441.13786659.4766

由表可知，ρdf的極差是ρd的100倍以上，而ρflnf與ρd兩者間的極差沒有數(shù)量級的差別，因此采用式(5)來計算局部密度既能符合要求效果又相對理想。

2.2.2ρ0和δ0的確定

根據(jù)FPoint對象集，計算每個對象的ρi和δi，繪制如圖3所示的決策圖。決策圖可大致分為左右兩個部分，左半部分對象較集中分布較密，右半部分較稀疏。

圖3 FPoint對象集決策圖Fig.3 Decision graph of FPoint collection

密度峰值搜索本質(zhì)上就是從對象集中篩選出ρi和δi都很大的對象?，F(xiàn)有的部分研究[18，22-23]采用人為觀察的方式從決策圖上確定ρi和δi閾值來篩選出密度峰值點，選擇標(biāo)準很大程度上會受到使用者主觀因素的影響，容易將干擾對象誤判為峰值點。另一部分學(xué)者[24-27]則通過定義一個新的量值γi=ρi*δi，嘗試分析γ值的異常變化特征來自動提取出密度峰值。但是，γ值異常部分與正常部分的分界ε難以自動確定，如圖4所示。因此對于FPoint對象集，必須從ρi和δ本身的概率分布特征出發(fā)尋找各自潛在的規(guī)律，確定各自的閾值ρ0和δ0來實現(xiàn)密度峰值的準確提取。

圖4 γ值散點圖及異常分界ε位置Fig.4 Scatter diagram of γ values and its ε position

根據(jù)式(4)中對局部密度的定義，F(xiàn)Point對象的局部密度ρi由ρd和df兩個部分共同決定，只有ρd和df都較大時，F(xiàn)Point對象才能擁有較高的局部密度。在FPoint對象集決策圖中，核心點必然位于決策圖的右半部分，即密度較高但數(shù)量較為有限的區(qū)域。為了提取密度峰值應(yīng)當(dāng)首先求解ρ0，確定疏密兩部分的交界。

2.2.2.1 ρ0的確定

對FPoint對象的局部密度特征進行量化處理。以標(biāo)準正態(tài)函數(shù)為核對局部密度值進行核密度估計，核密度曲線如圖5所示。曲線以ρb處為界分成左右兩部分，其中右側(cè)區(qū)域擁有較大的局部密度但頻率普遍很小，與決策圖上所表現(xiàn)出的特征一致。由此得知，ρb即為ρ0，峰值點必然位于ρb右側(cè)區(qū)域。圖5中核密度分布曲線在形態(tài)上均不符合任何已知分布，但是經(jīng)觀察發(fā)現(xiàn)，ρb所在的區(qū)域曲線形態(tài)呈現(xiàn)兩大特征：①總體呈下降趨勢；②ρb左側(cè)下降趨勢較陡，右側(cè)總體平緩，ρb處于陡和緩的分界點上。ρ0確定過程如下：

圖5 局部密度的核密度曲線圖Fig.5 Kernel density diagram for local densities

(1) 設(shè)置斜率絕對值的閾值為kt，并對核密度曲線的橫縱坐標(biāo)進行歸一化處理；

(2) 計算核密度曲線中每個自變量處的斜率，記為ki，計算如下

(6)

式中，ρi表示第i個FPoint對象FPi經(jīng)過歸一化后的局部密度，kdi表示ρi經(jīng)過歸一化后的核密度值。

(3) 從右向左尋找第一個絕對值接近于kt的ki，其對應(yīng)的局部密度即為ρ0。

經(jīng)試驗發(fā)現(xiàn)， 對文所采用的數(shù)據(jù)集，kt取0.5左右可取得較理想的結(jié)果，可根據(jù)實際效果適當(dāng)調(diào)整。

2.2.2.2 δ0的確定

局部密度大于ρ0且δi較大的對象即為密度峰值點，從密度大于ρ0的對象中確定δ0即可獲取峰值目標(biāo)，記為{FPoint}ρ。從δ值的角度，{FPoint}ρ中包含了兩種類型的FPoint對象：密度簇的核心點，該類對象占{FPoint}ρ的絕大部分，其臨近對象為同一簇內(nèi)部的其他核心點或是密度峰值點，δ值很??；密度峰值點，根據(jù)峰值點的定義，其δ值較周圍對象明顯大得多，而且數(shù)量十分有限。綜上，通過δ的數(shù)量特征方可從{FPoint}ρ中確定峰值點。

根據(jù)以上結(jié)論，若在{FPoint}ρ中將密度峰值點視為δ值異常對象，通過異常檢查的方式可確定閾值δ0。本文中{FPoint}ρ中對象的δ值分布直方圖如圖6所示。

圖6 δ值分布直方圖及指數(shù)分布擬合曲線Fig.6 Histogram of δ values and its fitting curve

直方圖呈現(xiàn)出從高到低的階梯狀分布，并且在形態(tài)上可大略呈現(xiàn)指數(shù)分布的特征，可以采用極大似然估計的方式來獲取該指數(shù)分布的參數(shù)θ，即

(7)

設(shè){FPoint}ρ中δ值小于δ0的對象為正常部分，其發(fā)生概率為pt。根據(jù)指數(shù)分布的分布函數(shù)計算出δ0，表達如下

(8)

經(jīng)試驗發(fā)現(xiàn)，pt取99.5%左右可取得較理想的效果。

2.2.3 密度峰值搜索總體流程

(1) 構(gòu)建FPoint對象集合。對原始的簽到點對象，統(tǒng)計每個位置上的重復(fù)頻率dFreq。然后按照FPoint的數(shù)據(jù)結(jié)構(gòu)以各項屬性值構(gòu)建Fpoint對象集合{FPoint}n，其中第i個對象記為FPi。

(2) 逐個計算{FPoint}n中兩兩對象之間的歐氏距離dij構(gòu)造距離矩陣Dn×n。

(3) 根據(jù)dFreq屬性和Dn×n采用式(6)計算每個FPi的局部密度ρi并賦值給該對象density屬性。

(4) 根據(jù)density屬性和Dn×n采用式(3)計算出每個FPi的δi并賦值給該對象的delta屬性。

(5) 對{FPoint}n中所有對象以ρ為橫軸，δ為縱軸繪決策圖。根據(jù)2.2.2中的思路確定ρ0和δ0篩選出density大于ρ0且delta大于δ0的對象作為密度峰值點。

2.3 峰值點密度簇聚類算法

由于位置重復(fù)頻率dFreq的影響，F(xiàn)Point對象的局部密度分布在地圖空間中會產(chǎn)生如圖7效果：一部分緊靠密度峰值的對象由于dFreq值過低而使局部密度低于其周圍的對象，而那些處于簇邊緣甚至明顯偏離簇的點對象由于dFreq值過高而使局部密度高于其周圍的對象。從總體上看，對象密度區(qū)之間的密度邊界不明顯，出現(xiàn)相互混合、滲透現(xiàn)象。

圖7 簡單分類后的不同局部密度FPoint對象的空間分布Fig.7 Spatial distribution for FPoints with different local density by simple classification

這種情形下無法再使用CFSFDP中基于密度閾值的劃分方法來對FPoint對象進行聚類。因此，在獲取密度集群時必須考慮對象的密度連通性來保證簇的連續(xù)與邊界的完整，將遠離密度簇的位置離群點剔除。

針對不同局部密度FPoint對象的空間分布特征，對密度簇中的核心點、邊界點等概念進行定義。

點集T：表示已提取的全部密度峰值對象構(gòu)成的點集。

點集D：表示不含密度峰值點的所有FPoint對象所構(gòu)成的點集。

核心點：對于數(shù)據(jù)對象p∈D，如果p的局部密度ρp大于等于密度閾值ρt，則稱p為核心點。

邊界點：對于數(shù)據(jù)對象p∈D，如果p的局部密度ρp小于密度閾值ρt，但p位于某個核心點或峰值點的Eps鄰域內(nèi)，則稱p為邊界點

密度直達：對于對象p和q，若p在q的Eps鄰域內(nèi)，且p為核心點，q也為核心點或峰值點，則稱對象p是從對象q出發(fā)直接密度可達的，簡稱密度直達。

密度可達：對于點集D，當(dāng)存在一個對象鏈 p1、p2、p3、…、pn，其中p1=q，pn=p。對于pi∈D，如果在條件(Eps，ρt)下pi + 1從pi密度直達，則稱對象p從對象q在條件(Eps，ρt)下密度可達。

密度相連：如果數(shù)據(jù)集D中存在一個對象o，使得對象p和q是從o在(Eps，ρt)條件下密度可達的，那么稱對象p和q在(Eps，ρt)條件下密度相連。

簇和噪聲：由某一個密度峰值點開始，由該點及其密度可達的所有對象構(gòu)成一個簇。點簇的成員包括峰值點、核心點和邊界點。不屬于任何簇的對象稱為噪聲。

基于以上概念，峰值點密度簇的聚類算法流程如下：

(1) 任取點集T中的某一峰值點Pi，遍歷點集D，尋找在(Eps，ρt)條件下所有與Pi密度直達的核心點構(gòu)成初級核心點簇{C}1并從D中去除。

(2) 在點集D中，以(Eps，ρt)條件擴展核心簇{C}1，構(gòu)成核心點簇{C}2并從D中去除。即尋找與{C}1中每個核心點密度直達、密度可達和密度相連的所有核心點連同{C}1構(gòu)成Pi的最終核心點簇。

(3) 尋找Pi和核心點周圍所有的邊界點連同Pi構(gòu)成最終的峰值點密度簇{P}i

(4) 重復(fù)(1)～(3)直到對T中所有峰值點找完全部密度簇為止。

3 試驗分析

本文試驗環(huán)境為CPU2.5GHz、內(nèi)存8GB。對本文數(shù)據(jù)集統(tǒng)計位置重復(fù)頻率所構(gòu)建對象集記為{FPoint}。

3.1 參數(shù)選取

3.1.1 截斷距離dc的選取

dc為本方法中唯一需要用戶給出的參數(shù)。最佳的dc應(yīng)當(dāng)使得所有對象在dc鄰域內(nèi)鄰居數(shù)的均值占樣本總數(shù)n的t比例，t取1%～2%[18,26-27]。由于數(shù)據(jù)樣本總量較大，這種方式實現(xiàn)起來比較困難。一個可行的代替方案是：計算{FPoint}中兩兩對象之間的距離并升序排序，以排序后的樣本的第t·N個距離作為dc，N為排序后距離的總個數(shù)。經(jīng)多次試驗發(fā)現(xiàn)，t取1%時所獲得的dc可實現(xiàn)較好的效果。本文中，{FPoint}的dc設(shè)置為421.2m。

3.1.2 聚類參數(shù) ρt與Eps的選取

為了保證每個峰值點周圍都有足夠的核心點，在聚類之前可以將所有的點要素按照density字段采用Jenks自然斷裂點法進行分類。對聚類后的結(jié)果進行觀察，如果某個類別可以保證每個峰值點周圍都有足夠多的該類成員，就以該類別的下界作為密度閾值ρt。在確定ρt后，對于每個峰值點pi，記pi周圍局部密度大于ρt且距離pi最遠的對象與峰值點之間的距離為Epsi，取Epsi中的最小值作為參數(shù)Eps。

3.2 結(jié)果分析與討論

3.2.1 密度峰值搜索與聚類結(jié)果

以2.1中的思路對{FPoint}鎖定閾值ρ0和δ0來提取密度峰值，然后按照3.1中的方法設(shè)置聚類參數(shù)ρt與Eps，對象集的聚類結(jié)果如圖8所示。聚類結(jié)果顯示，從數(shù)據(jù)集內(nèi)搜索出了10個密度峰值點，以此確定了10個峰值密度簇，簇的外形完整連續(xù)，邊界清晰，可有效地表達城市熱區(qū)的形態(tài)及變化特征；從圖上還可以發(fā)現(xiàn)，由于考慮了位置重復(fù)情況，密度峰值點不一定位于簇的幾何密度中心，由此所表示的居民活動中心不僅更加真實而且一定程度上反映出熱區(qū)的空間集中趨勢。

圖8 密度峰值點和聚類簇分布圖Fig.8 Distribution of density peaks and clusters by our approach

3.2.2 聚類結(jié)果的比較

為了進一步體現(xiàn)本文方法在簽到位置聚類中相比現(xiàn)有方法的有效性，分別給出了CFSFDP的密度峰值提取和聚類結(jié)果以及不同參數(shù)的DBSCAN算法和ADBSC算法的聚類結(jié)果。其中圖9為相同截斷距離下的CFSFDP聚類結(jié)果；圖10為MinPts取150，Eps分別取90m和120m的DBSCAN聚類結(jié)果；圖11為k取5[16]，ε分別取10%和25%的ADBSC聚類結(jié)果。

圖9 CFSFDP峰值點和聚類簇分布圖 Fig.9 Distribution of density peaks and clusters by CFSFDP

圖10 不同參數(shù)下的DBSCAN聚類結(jié)果圖Fig.10 Clusters by DBSCAN with different parameters

對比圖8和圖9發(fā)現(xiàn)，CFSFDP算法所提取的密度峰值大多處于簇的幾何中心。在簇形表現(xiàn)上，大多數(shù)的簇外形近似于球狀，并且存在離群位置對象聚成一類的情況(圖9中的A、B處)。進一步觀察發(fā)現(xiàn)，這類離群位置上的簽到重復(fù)度很高，在CFSFDP中擁有極高的局部密度，由于位置離群造成δ也相對較大，滿足了密度峰值點的構(gòu)成條件，但峰值點周圍的簽到位置過于稀疏，點位過少，很難匯聚成邊界清晰外形完整的峰值密度簇，無法有效地表達活動熱區(qū)。此外，CFSFDP聚類出的某些密度簇還包含了離群點(圖9中的C處)或游離的子簇(圖9中的框選區(qū)域，其中D處在圖8中是一個完整的峰值密度簇)。

對比圖8和圖10，可看出DBSCAN算法所得密度簇的總數(shù)較多但絕大多數(shù)空間規(guī)模較小，在Eps參數(shù)較小時存在將一個完整的簇割裂的情況。結(jié)果中包含了大量由重復(fù)度較高的離群位置構(gòu)成的細碎密度簇，在熱區(qū)的表達上不具有代表性；ADBSC算法善于發(fā)現(xiàn)聚集程度不同的密度簇，但是對比圖8和圖11發(fā)現(xiàn)，不同參數(shù)條件下ADBSC算法所得到的密度簇空間規(guī)模都很小且不完整，顯得支離破碎，且存在一些密度簇的點位數(shù)量過少的情況。

圖11 不同參數(shù)下的ADBSC聚類結(jié)果圖Fig.11 Clusters by ADBSC with different parameters

3.2.3 分析與討論

聚類結(jié)果的比較表明，CFSFDP、DBSCAN以及ADBSC都存在將位置重復(fù)度較高的離群位置點集合聚成一類的情況。根本原因在于，以上方法中密度峰值點或核心點的選擇標(biāo)準直接由落入鄰域內(nèi)的目標(biāo)數(shù)量來決定，沒有單獨考慮當(dāng)前要素與目標(biāo)之間的位置重復(fù)性。本文聚類法引入位置重復(fù)頻率的概念，將位置重復(fù)造成的影響與自身空間位置屬性分隔開來，從而可以較好地避免以上情況。通過對簽到文本內(nèi)容的進一步觀察發(fā)現(xiàn)，位置離群數(shù)據(jù)中有相當(dāng)大的一部分為廣告類信息，這顯然不足以說明該位置擁有較高的居民活動量。綜合以上兩點可知，在帶有位置重復(fù)的簽到對象的聚類上，本文方法較以上三者更為合適，在不依賴于任何模型和先驗知識的前提下能夠探索出相對準確、合理的居民活動特征，在基于位置簽到的城市居民活動研究上更為實用。

同樣采用本文聚類方法，以廈門島為例，選擇相同時間段內(nèi)的新浪微博簽到記錄共計71 811條，位置重復(fù)率67.9%，簽到對象的位置分布如圖12所示，聚類結(jié)果如圖13所示。聚類結(jié)果顯示，所提取的8個峰值密度簇都具有連續(xù)和完整的外形，并且不存在離群位置選為峰值的情況；密度峰值點的空間分布能較好地體現(xiàn)出該地區(qū)從西南向東北方向延伸并沿四周邊界分布的城市空間結(jié)構(gòu)。結(jié)果表明，本文的聚類方法在不同空間結(jié)構(gòu)的城市區(qū)域上都能取得較為準確可靠的效果，具有良好的空間適應(yīng)性。

圖12 廈門島簽到對象的位置分布圖Fig.12 Location distribution of check-in points in Xiamen island

圖13 廈門島密度峰值點和聚類簇分布圖Fig.13 Distribution of density peaks and clusters by our approach for Xiamen island

本文聚類方法的不足之處主要體現(xiàn)在計算效率上。其中時間開銷主要集中在ρi和δi的計算上，復(fù)雜度達到O(n2)級別，相比于CFSFDP沒有明顯提升，一定程度上影響了海量簽到數(shù)據(jù)的處理能力。對于這一問題，可通過對{FPoint}建立合適的空間索引來提升鄰近對象的檢索效率，結(jié)合云計算方案來使整體計算效率大幅提高。此外，本方法僅考慮簽到記錄的空間位置屬性，沒有利用簽到文本或其他屬性信息來實現(xiàn)指定條件約束下的聚類研究，有待進一步研究。

4 結(jié) 論

基于密度的聚類算法，如DBSCAN、ADBSC、CFSFDP，以點對象間的空間距離作為相似性度指標(biāo)，對存在位置重復(fù)的LBSN簽到數(shù)據(jù)聚類時會將位置重復(fù)度較高的離群位置對象集合聚成一類，造成聚類錯誤。論文以CFSFDP為基礎(chǔ)，針對以上問題提出了簽到位置數(shù)據(jù)的密度峰值快速搜索與聚類方法，并以福州市新浪微博簽到數(shù)據(jù)為例進行了聚類試驗和分析，為位置簽到的聚類研究提供了新的方法。論文總結(jié)如下：

(1) 在CFSFDP“先找峰值后聚類”算法思想的基礎(chǔ)上，提出位置重復(fù)頻率的概念，借此對CFSFDP的局部密度重新定義，實現(xiàn)位置重復(fù)影響與自身空間位置屬性的分離；為保證搜索到的密度峰值相比傳統(tǒng)的觀察法和γ值法更加準確，論文通過研究概率分布特征的方式來確定局部密度和δ的合理閾值；針對局部密度的空間分布特性，論文提出的聚類方法考慮對象的密度連通性，保證峰值密度簇的連續(xù)與邊界的完整。

(2) 以新浪微博簽到數(shù)據(jù)為例，進行了試驗對比和分析，研究結(jié)果表明：論文提出的聚類方法所提取的密度峰值位置準確，簇形完整、連續(xù)，形狀任意，具有較好的空間適用性；密度峰值點可以反映熱區(qū)的集中趨勢，因此所發(fā)現(xiàn)的規(guī)律相比采用DBSCAN、ADBSC更加細致、豐富。

(3) 論文所提的聚類方法能夠從位置簽到數(shù)據(jù)中獲取更為準確、合理的城市活動熱區(qū)及熱區(qū)中心，且不依賴任何模型和先驗知識，在基于位置簽到的城市居民活動規(guī)律研究上更為實用。

對于論文聚類方法存在的不足之處，進一步的工作主要集中在兩個方面：①選擇合適的空間索引來提高鄰近對象的檢索效率；將算法遷移到云平臺來提高整體計算效率；②在提高計算效率的前提下考慮簽到文本內(nèi)容的約束，實現(xiàn)包含指定關(guān)鍵詞信息的簽到密度峰值及聚類簇的提取。

[1] 張子昂, 黃震方, 靳誠,等.基于微博簽到數(shù)據(jù)的景區(qū)旅游活動時空行為特征研究——以南京鐘山風(fēng)景名勝區(qū)為例[J]. 地理與地理信息科學(xué), 2015, 31(4): 121-126. ZHANG Ziang, HUANG Zhenfang, JIN Cheng, et al. Research on Spatial-Temporal Characteristics of Scenic Tourist Activity Based on Sina Microblog: a Case Study of Nanjing Zhongshan Mountain National Park[J]. Geography and Geo-Information Science, 2015, 31(4): 121-126.

[2] LIU Yu, SUI Zhengwei, KANG Chaogui, et al. Uncovering Patterns of Inter-urban Trip and Spatial Interaction from Social Media Check-in Data[J]. PLoS One, 2014, 9(1): e86026.

[3] LONG Xuelian, JIN Lei, JOSHI J. Exploring Trajectory-Driven Local Geographic Topics in Foursquare[C]∥Proceedings of the 2012 ACM Conference on Ubiquitous Computing. New York, NY: ACM, 2012: 927-934.

[4] 陸鋒, 劉康, 陳潔. 大數(shù)據(jù)時代的人類移動性研究[J]. 地球信息科學(xué)學(xué)報, 2014, 16(5): 665-672. LU Feng, LIU Kang, CHEN Jie. Research on Human Mobility in Big Data Era[J]. Journal of Geo-Information Science, 2014, 16(5): 665-672.

[5] 胡慶武, 王明, 李清泉. 利用位置簽到數(shù)據(jù)探索城市熱點與商圈[J]. 測繪學(xué)報, 2014, 43(3): 314-321. DOI: 10.13485/j.cnki.11-2089.2014.0045. HU Qingwu, WANG Ming, LI Qingquan. Urban Hotspot and Commercial Area Exploration with Check-in Data[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(3): 314-321. DOI: 10.13485/j.cnki.11-2089.2014.0045.

[6] 申悅, 柴彥威. 基于GPS數(shù)據(jù)的北京市郊區(qū)巨型社區(qū)居民日常活動空間[J]. 地理學(xué)報, 2013, 68(4): 506-516. SHEN Yue, CHAI Yanwei. Daily Activity Space of Suburban Mega-community Residents in Beijing Based on GPS Data[J]. Acta Geographica Sinica, 2013, 68(4): 506-516.

[7] 禹文豪, 艾廷華, 劉鵬程, 等. 設(shè)施POI分布熱點分析的網(wǎng)絡(luò)核密度估計方法[J]. 測繪學(xué)報, 2015, 44(12): 1378-1383. DOI: 10.11947/j.AGCS.2015.20140538. YU Wenhao,AI Tinghua,LIU Pengcheng, et al. Network Kernel Density Estimation for the Analysis of Facility POI Hotspots[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(12): 1378-1383. DOI: 10.11947/j.AGCS.2015.20140538.

[8] 王波, 甄峰, 張浩. 基于簽到數(shù)據(jù)的城市活動時空間動態(tài)變化及區(qū)劃研究[J]. 地理科學(xué), 2015, 35(2): 151-160. WANG Bo, ZHEN Feng, ZHANG Hao. The Dynamic Changes of Urban Space-time Activity and Activity Zoning Based on Check-in Data in Sina Web[J]. Scientia Geographica Sinica, 2015, 35(2): 151-160.

[9] 劉啟亮, 李光強, 鄧敏. 一種基于局部分布的空間聚類算法[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2010, 35(3): 373-377. LIU Qiliang, LI Guangqiang, DENG Min. A Local Distribution Based Spatial Clustering Algorithm[J]. Geomatics and Information Science of Wuhan University, 2010, 35(3): 373-377.

[10] 曾紹琴, 李光強, 廖志強. 空間聚類方法的分類[J]. 測繪科學(xué), 2012, 37(5): 103-106. ZENG Shaoqin, LI Guangqiang, LIAO Zhiqiang. A New Category of Spatial Clustering Methods[J]. Science of Surveying and Mapping, 2012, 37(5): 103-106.

[11] 柳盛, 吉根林. 空間聚類技術(shù)研究綜述[J]. 南京師范大學(xué)學(xué)報(工程技術(shù)版), 2010, 10(2): 57-62. LIU Sheng, JI Genlin. A Review of Researches on Spatial Clustering[J]. Journal of Nanjing Normal University (Engineering and Technology Edition), 2010, 10(2): 57-62.

[12] NASIBOV E N, ULUTAGAY G. Robustness of Density-based Clustering Methods with Various Neighborhood Relations[J]. Fuzzy Sets and Systems, 2009, 160(24): 3601-3615.

[13] BIRANT D, KUT A. ST-DBSCAN: an Algorithm for Clustering Spatial-temporal Data[J]. Data & Knowledge Engineering, 2007, 60(1): 208-221.

[14] LU Min, WANG Zuchao, LIANG Jie, et al. OD-Wheel: Visual Design to Explore OD Patterns of a Central Region[C]∥Proceedings of 2015 IEEE Pacific Visualization Symposium. Hangzhou: IEEE, 2015: 87-91.

[15] PAN Gang, QI Guande, WU Zhaohui, et al. Land-use Classification Using Taxi GPS Traces[J]. IEEE Transactions on Intelligent Transportation Systems, 2013, 14(1): 113-123.

[16] 李光強, 鄧敏, 劉啟亮, 等. 一種適應(yīng)局部密度變化的空間聚類方法[J]. 測繪學(xué)報, 2009, 38(3): 255-263. DOI: 10.3321/j.issn:1001-1595.2009.03.011. LI Guangqiang, DENG Min, LIU Qiliang, et al. A Spatial Clustering Method Adaptive to Local Density Change[J]. Acta Geodaetica et Cartographica Sinica, 2009, 38(3): 255-263. DOI: 10.3321/j.issn:1001-1595.2009.03.011.

[17] 周素紅, 郝新華, 柳林. 多中心化下的城市商業(yè)中心空間吸引衰減率驗證——深圳市浮動車GPS時空數(shù)據(jù)挖掘[J]. 地理學(xué)報, 2014, 69(12): 1810-1820. ZHOU Suhong, HAO Xinhua, LIU Lin. Validation of Spatial Decay Law Caused by Urban Commercial Center′s Mutual Attraction in Polycentric City: Spatio-temporal Data Mining of Floating Cars′ GPS Data in Shenzhen[J]. Acta Geographica Sinica, 2014, 69(12): 1810-1820.

[18] RODRIGUEZ A, LAIO A. Clustering by Fast Search and Find of Density Peaks[J]. Science, 2014, 344(6191): 1492-1496.

[19] 馬春來, 單洪, 馬濤, 等. 一種基于CFSFDP改進算法的重要地點識別方法研究[J]. 計算機應(yīng)用研究, 2017, 34(1): 136-140. MA Chunlai, SHAN Hong, MA Tao, et al. Research on Important Places Identification Method Based on Improved CFSFDP Algorithm[J]. Application Research of Computers, 2017, 34(1): 136-140.

[20] LIU Peiyu, LIU Yingying, HOU Xiuyan, et al. A Text Clustering Algorithm Based on Find of Density Peaks[C]∥Proceedings of the 7th International Conference on Information Technology in Medicine and Education. Huangshan: IEEE, 2015: 348-352.

[21] XIE Juanying,GAO Hongchao,XIE Weixin, et al. Robust Clustering by Detecting Density Peaks and Assigning Points Based on Fuzzy Weighted K-nearest Neighbors[J]. Information Sciences, 2016, 354: 19-40.

[22] DU Mingjing,DING Shifei,JIA Hongjie. Study on Density Peaks Clustering Based on k-Nearest Neighbors and Principal Component Analysis[J]. Knowledge-Based Systems, 2016, 99: 135-145.

[23] 謝娟英, 屈亞楠. 密度峰值優(yōu)化初始中心的K-medoids聚類算法[J]. 計算機科學(xué)與探索, 2016, 10(2): 230-247. XIE Juanying, QU Yanan. K-medoids Clustering Algorithms with Optimized Initial Seeds by Density Peaks[J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(2): 230-247.

[24] LIU Dongchang,CHENG Shifeng,YANG Yiping. Density Peaks Clustering Approach for Discovering Demand Hot Spots in City-scale Taxi Fleet Dataset[C]∥Proceedings of the 18th International Conference on Intelligent Transportation Systems. Las Palmas: IEEE, 2015.

[25] 馬春來, 單洪, 馬濤. 一種基于簇中心點自動選擇策略的密度峰值聚類算法[J]. 計算機科學(xué), 2016, 43(7): 255-258, 280. MA Chunlai, SHAN Hong, MA Tao. Improved Density Peaks Based Clustering Algorithm with Strategy Choosing Cluster Center Automatically[J]. Computer Science, 2016, 43(7): 255-258, 280.

[26] 沈忱, 祁昆侖, 劉文軒, 等. 基于FSFDP-BoV模型的遙感影像檢索[J]. 地理與地理信息科學(xué), 2016, 32(1): 55-59. SHEN Chen, QI Kunlun, LIU Wenxuan, et al. Remote Sensing Image Retrieval Research Based on FSFDP-BoV Model[J]. Geography and Geo-Information Science, 2016, 32(1): 55-59.

[27] 蔣禮青, 張明新, 鄭金龍, 等. 快速搜索與發(fā)現(xiàn)密度峰值聚類算法的優(yōu)化研究[J]. 計算機應(yīng)用研究, 2016, 33(11): 3251-3254. JIANG Liqing, ZHANG Mingxin, ZHENG Jinlong, et al. Optimization of Clustering by Fast Search and Find of Density Peaks[J]. Application Research of Computers, 2016, 33(11): 3251-3254.

(責(zé)任編輯：宋啟凡)

Fast Search the Density Peaks and Clustering Method for Check-in Data

LIU Meng,WU Qunyong,QIU Duansheng,SUN Mei,ZHANG Qiang

Spatial Information Research Center of Fujian, Fuzhou University, Key Laboratory of Spatial Data Mining & Information Sharing of MOE, Fuzhou 350002, China

Check-in data obtained from Location-based Social Network (LBSN) is a sort of crowd geographic data which will reveal daily activities of urban residents. Different check-in behaviors with the same check-in location will produce the phenomenon of location duplication because of location candidate function in LBSN system. The current density-based spatial clustering algorithms have the following problems: ①difficulty to find density peak point. ②clustering error caused by check-in point objects with duplicate positions. In order to solve these problems, we proposed a fast search density peaks and clustering method for check-in data, based on clustering by fast search and find of density peaks (CFSFDP). Firstly, position repetition frequency was introduced and calculated to illustrate the number of the check-in position duplications data. Secondly, a new type of point feature was constructed by adding position repetition frequency of the original check-in position data, which was used as study object to search density peaks. At last, clustering algorithm based on density peak point was constructed in which density connectivity was taken into account to ensure the continuity and integrity of density clusters. Taking check-in data obtained from Sina Microblog as an example, an experiment was designed and implemented. The results demonstrates：①Clustering method can effectively avoid the problem that the outlier location object with high repeatability is chosen as the peak and clustering, and has excellent spatial adaptability as well when comparing with check-in data from other area. ②Extracted density peak points can not only be used to represent the center of the hot zone, but also reflect the concentration trend of the hot zone, which can help to explore the dynamic change of the hot zone.

check-in data；hot zone；spatial clustering；density peaks clustering；position repetition

The National Science Foundation of China(No. 41471333)

LIU Meng(1990—), male, postgraduate, majors in spatial data mining and visualization.

WU Qunyong

劉萌，鄔群勇，邱端昇，等.簽到位置數(shù)據(jù)的密度峰值快速搜索與聚類方法[J].測繪學(xué)報，2017,46(4)：516-525.

10.11947/j.AGCS.2017.20160377. LIU Meng, WU Qunyong, QIU Duansheng,et al.Fast Search the Density Peaks and Clustering Method for Check-in Data[J]. Acta Geodaetica et Cartographica Sinica,2017,46(4):516-525. DOI:10.11947/j.AGCS.2017.20160377.

P208

A

1001-1595(2017)04-0516-10

國家自然科學(xué)基金(41471333)

2016-07-25

劉萌(1990—)，男，碩士生，主要研究方向為空間數(shù)據(jù)挖掘與可視化。

E-mail： montzzzt@sina.com

鄔群勇

E-mail： qywu.wu@fzu.edu.cn

frequency

修回日期： 2017-03-20