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

劉 萌，鄔群勇，邱端昇，孫 梅，張 強(qiáng)

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

?

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

劉 萌，鄔群勇，邱端昇，孫 梅，張 強(qiáng)

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

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

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

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

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

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

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)建簽到位置點(diǎn)對(duì)象。帶有位置的簽到72 354，重復(fù)率37.2%，最大重復(fù)數(shù)721條。數(shù)據(jù)位置分布如圖1所示，位置重復(fù)數(shù)量統(tǒng)計(jì)情況如圖2所示。在構(gòu)建空間點(diǎn)對(duì)象之前需要將經(jīng)緯度坐標(biāo)轉(zhuǎn)換成平面坐標(biāo)以方便計(jì)算對(duì)象間的空間距離，單位為米。

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

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

2.1 CFSFDP算法分析

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

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

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

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

(1)

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

(2)

δi的具體表達(dá)如下

(3)

式中，δi表示密度大于ρi的對(duì)象中與pi最近距離。若ρi為最大值，δi為距離pi最遠(yuǎn)對(duì)象與pi間距離。

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

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

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

2.2.1 局部密度改進(jìn)方案

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

Class FPoint{

int PID, ∥點(diǎn)要素編號(hào)

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

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

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

double density, ∥局部密度(ρ)

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

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

intclusterid∥所屬簇的ID

}

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

ρi=df·ρd

(4)

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

(5)

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

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

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

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ù)量級(jí)的差別，因此采用式(5)來計(jì)算局部密度既能符合要求效果又相對(duì)理想。

2.2.2ρ0和δ0的確定

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

圖3 FPoint對(duì)象集決策圖Fig.3 Decision graph of FPoint collection

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

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

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

2.2.2.1 ρ0的確定

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

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

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

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

(6)

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

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

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

2.2.2.2 δ0的確定

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

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

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

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

(7)

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

(8)

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

2.2.3 密度峰值搜索總體流程

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

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

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

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

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

2.3 峰值點(diǎn)密度簇聚類算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 試驗(yàn)分析

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

3.1 參數(shù)選取

3.1.1 截?cái)嗑嚯xdc的選取

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2.3 分析與討論

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

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

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

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

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

4 結(jié) 論

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

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

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

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

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

[1] 張子昂, 黃震方, 靳誠(chéng),等.基于微博簽到數(shù)據(jù)的景區(qū)旅游活動(dòng)時(shí)空行為特征研究——以南京鐘山風(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ù)時(shí)代的人類移動(dòng)性研究[J]. 地球信息科學(xué)學(xué)報(bào), 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ù)探索城市熱點(diǎn)與商圈[J]. 測(cè)繪學(xué)報(bào), 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ū)居民日?；顒?dòng)空間[J]. 地理學(xué)報(bào), 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分布熱點(diǎn)分析的網(wǎng)絡(luò)核密度估計(jì)方法[J]. 測(cè)繪學(xué)報(bào), 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ù)的城市活動(dòng)時(shí)空間動(dòng)態(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] 劉啟亮, 李光強(qiáng), 鄧敏. 一種基于局部分布的空間聚類算法[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(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] 曾紹琴, 李光強(qiáng), 廖志強(qiáng). 空間聚類方法的分類[J]. 測(cè)繪科學(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é)報(bào)(工程技術(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] 李光強(qiáng), 鄧敏, 劉啟亮, 等. 一種適應(yīng)局部密度變化的空間聚類方法[J]. 測(cè)繪學(xué)報(bào), 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è)中心空間吸引衰減率驗(yàn)證——深圳市浮動(dòng)車GPS時(shí)空數(shù)據(jù)挖掘[J]. 地理學(xué)報(bào), 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ìn)算法的重要地點(diǎn)識(shí)別方法研究[J]. 計(jì)算機(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]. 計(jì)算機(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] 馬春來, 單洪, 馬濤. 一種基于簇中心點(diǎn)自動(dòng)選擇策略的密度峰值聚類算法[J]. 計(jì)算機(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]. 計(jì)算機(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].測(cè)繪學(xué)報(bào)，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

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

2016-07-25

劉萌(1990—)，男，碩士生，主要研究方向?yàn)榭臻g數(shù)據(jù)挖掘與可視化。

E-mail： montzzzt@sina.com

鄔群勇

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

frequency

修回日期： 2017-03-20