李世明,張秉楨,杜 軍,朱海龍,付寶君

1(哈爾濱師范大學(xué) 計算機科學(xué)與信息工程學(xué)院,哈爾濱 150025)2(上海市信息安全綜合管理技術(shù)研究重點實驗室,上海 200240)

1 引 言

空間聚類算法[1]能夠在海量軌跡數(shù)據(jù)中利用空間關(guān)聯(lián)規(guī)則挖掘數(shù)據(jù)特征[2,3]為城市規(guī)劃、公共出行、居住熱區(qū)以及POI(Point of Interest)查詢等位置服務(wù)提供分析決策[4].空間聚類應(yīng)用廣泛,許多學(xué)者對其進(jìn)行研究并取得了成果,如Zheng 等[5,6]以GeoLife項目為基礎(chǔ)通過挖掘個體的活動規(guī)律來尋找各對象之間時空序列的相似性和活動模式;Xiaoyue等[7]利用共享自行車BikeShare系統(tǒng)的GPS數(shù)據(jù)挖掘用戶路線偏好信息及基礎(chǔ)交通網(wǎng)絡(luò)結(jié)構(gòu).此外,也有學(xué)者以軌跡數(shù)據(jù)為樣本取得空間聚類應(yīng)用研究成果:城市區(qū)域功能劃分[8]、道路交通路徑分析[9]、犯罪空間聚集態(tài)熱點分析[10]等.上述研究多以分析對象運動規(guī)律為主要研究內(nèi)容,對于城市聚居區(qū)域熱度分布的研究相對較少,而且該問題在基于POI查詢和基于位置服務(wù)應(yīng)用中具有很高的商業(yè)價值.熱區(qū)聚類研究常用算法有基于劃分的K-means算法[11]和FCM算法[12]、基于空間的DBSCAN算法[13]、基于網(wǎng)格的STING算法[14]、基于層次的CURE算法[15]、基于密度和網(wǎng)格的CLIQUE算法[16]等.對于CLIQUE算法而言,盡管效率較高,但對網(wǎng)格步長值、密度閾值二者的確定及聚類邊界精度值的控制不夠理想[17],諸多學(xué)者已在CLIQUE算法的基礎(chǔ)上進(jìn)行改進(jìn),如CAG-CLIQUE算法[18]采用邊界動態(tài)調(diào)整技術(shù)不斷修正網(wǎng)格步長來控制邊界精度、GDCAP算法[19]通過網(wǎng)格密度期望的積差選取密度閾值、A-Stream算法[20]使用數(shù)據(jù)平均密度與標(biāo)準(zhǔn)差的和來選取密度閾值等,以上算法降低了參數(shù)設(shè)定的難度并提高了聚類邊界的精度;但是,真實數(shù)據(jù)中存在的異常值會影響數(shù)學(xué)期望和標(biāo)準(zhǔn)差,會降低以上算法的自適應(yīng)效果[21].

本文提出的APS-CLIQUE算法是一種改進(jìn)的CLIQUE算法,它采用基于四分位數(shù)[22]思想的自適應(yīng)優(yōu)化邊界網(wǎng)格策略來解決自適應(yīng)過程中密度閾值參數(shù)選取的穩(wěn)健性、簇邊界識別的精準(zhǔn)性問題.以UCI中Iris標(biāo)準(zhǔn)數(shù)據(jù)集與成都市GPS數(shù)據(jù)集為樣本,分別對改進(jìn)前后的算法進(jìn)行大量對比實驗;然后將改進(jìn)后算法在百度地圖上的應(yīng)用結(jié)果與現(xiàn)實中公眾所知的城市居住熱區(qū)數(shù)據(jù)進(jìn)行對比;綜合上述實驗及數(shù)據(jù)分析表明,APS-CLIQUE算法在城市居住熱區(qū)分析中的應(yīng)用效果優(yōu)于改進(jìn)前的算法,能夠提高基于興趣點和位置服務(wù)的決策優(yōu)化服務(wù)質(zhì)量.

2 APS-CLIQUE算法

2.1 相關(guān)定義

CLIQUE算法通過給定的網(wǎng)格步長gs將數(shù)據(jù)對象直接投影到網(wǎng)格空間并計算網(wǎng)格密度,若網(wǎng)格密度大于給定的密度閾值τ則判定該網(wǎng)格為稠密網(wǎng)格,加入當(dāng)前聚類并搜索網(wǎng)格,直至相鄰網(wǎng)格全部為非稠密網(wǎng)格,結(jié)束本次循環(huán);重復(fù)上述操作直至找到所有聚類.

定義1.(網(wǎng)格單元)DS={D1,D2,D3,…,Dn}為n維數(shù)據(jù)集,將子空間Di擴大到與最大的子空間Dmax相等,根據(jù)網(wǎng)格步長gs將Di劃分為m個相等的區(qū)間,從而將Di分成m個互不相交的矩形單元,即網(wǎng)格單元g.

定義3.(單元格的有效性)若令vj表示gj的有效性,當(dāng)?x>0時(x為gj中數(shù)據(jù)的個數(shù))gj為有效,vj=0;否則無效,vj=1.

定義4.(上/下四分位距)在箱形圖中,第三四分位數(shù)Q3與第二四分位數(shù)Q2的差距為上四分位距,即:UIQR=Q3-Q2;第二四分位數(shù)Q2與第一四分位數(shù)Q1的差距為下四分位距,即:DIQR=Q2-Q1.

定義5.(邊界網(wǎng)格)給定閾值θ,在Di中,?g≠gd且?gd∈{g的相鄰單元格},若ρg>θ,則g為邊界單元格.

2.2 基于四分位數(shù)箱形模型的參數(shù)自適應(yīng)策略

以數(shù)據(jù)的統(tǒng)計特性和四分位數(shù)的特點[23]為基礎(chǔ)對密度閾值參數(shù)提出一種基于四分位數(shù)箱形模型自適應(yīng)策略算法.

該算法以網(wǎng)格加權(quán)和上四分位距為基礎(chǔ),提取Q2與Q3之間的數(shù)據(jù)來得到一個穩(wěn)健的區(qū)間,并將該區(qū)間內(nèi)所有數(shù)據(jù)的算術(shù)平均值作為自適應(yīng)的密度閾值參數(shù)ε.為排除數(shù)據(jù)網(wǎng)格中無效單元格對數(shù)據(jù)的干擾和影響,根據(jù)網(wǎng)格單元的有效性可以獲取有效單元格的集合gjSet,用式(1)表示,式中g(shù)j為數(shù)據(jù)集DS中任意單元格.

該算法以網(wǎng)格加權(quán)和上四分位距為基礎(chǔ),提取Q2與Q3之間的數(shù)據(jù)來得到一個穩(wěn)健的區(qū)間,并將該區(qū)間內(nèi)所有數(shù)據(jù)的算術(shù)平均值作為自適應(yīng)的密度閾值參數(shù)ε.為排除數(shù)據(jù)網(wǎng)格中無效單元格對數(shù)據(jù)的干擾和影響,根據(jù)網(wǎng)格單元的有效性可以獲取有效單元格的集合gjSet,用式(1)表示,式中g(shù)j為數(shù)據(jù)集DS中任意單元格.

gjSet={(vj·gj|gj∈DS)}

(1)

對gjSet進(jìn)行排序處理后得到gjSortSet數(shù)據(jù)集,并求出有效單元格數(shù)量sum(gjSortSet).Q1為gjSortSet的第一個元素,根據(jù)四分位數(shù)計算方法,如公式(2)、公式(3)所示求得Q2、Q3.

Q2=(sum(gjSortSet)+1)/2

(2)

Q3=3(sum(gjSortSet)+1)/4

(3)

以Q2為中點將四分位距離分成上下兩部分.通過計算上四分位間距集合內(nèi)的所有單元格中對象的算術(shù)平均值,可計算自適應(yīng)密度閾值ε,如公式(4)所示:

(4)

公式(4)中count(gj)函數(shù)返回gj單元格中數(shù)據(jù)對象的個數(shù)x.由四分位數(shù)特點可知,該策略無需預(yù)先約束數(shù)據(jù),通過四分位數(shù)降低形態(tài)兩端數(shù)據(jù)對計算結(jié)果的影響,可提高具有偏斜分布真實數(shù)據(jù)集的適用性;上四分位距內(nèi)算術(shù)平均值作用于有效單元格可排除數(shù)據(jù)樣本中權(quán)值為0的異常值,保證自適應(yīng)生成密度閾值的穩(wěn)健性;此外,APS-CLIQUE算法還對聚類邊界進(jìn)行了優(yōu)化處理.

2.3 增強聚類邊界精度

CLIQUE算法中聚類邊界存在問題:

1)邊界網(wǎng)格丟失,聚類時某單元格會被當(dāng)作噪音被摒棄;

2)錯誤合并簇,當(dāng)密度閾值較小時會將不同簇的網(wǎng)格誤識別為同簇網(wǎng)格.

為解決上述問題,本文引入邊界網(wǎng)格概念(定義5),提出一種簡單有效的增強簇邊界精度的算法,其邊界網(wǎng)格密度閾值θ可使用四分位數(shù)箱形模型下四分位距DIQR內(nèi)數(shù)據(jù)的算術(shù)平均值計算得來,如公式(5)所示:

(5)

CLIQUE算法在深度優(yōu)先遍歷識別稠密單元格時,使用公式(1)計算出當(dāng)前網(wǎng)格密度小于自適應(yīng)密度閾值后,使用公式(5)來識別是否為邊界網(wǎng)格.邊界網(wǎng)格加入當(dāng)前簇并回退到前置稠密單元格繼續(xù)進(jìn)行搜索,繼續(xù)進(jìn)行迭代,直到完成一個聚類簇.

APS-CLIQUE算法針對CLIQUE算法聚類邊界的單一判斷問題,通過DIQR的算術(shù)平均值識別出邊界網(wǎng)格并對聚類邊緣進(jìn)行細(xì)化,彌補丟失的信息,既解決CLIQUE算法聚類邊界問題又提高了聚類邊界精度.

2.4 APS-CLIQUE算法描述

APS-CLIQUE算法以CLIQUE為基礎(chǔ),預(yù)先通過四分位數(shù)箱形模型生成自適應(yīng)的密度閾值ε,并使用邊界網(wǎng)格密度閾值θ判定邊界網(wǎng)格以提高簇邊界精度,算法描述如下:

算法:APS-CLIQUE算法

輸入:DS,gs,ε,θ

輸出:APS-CLIQUE算法結(jié)果clusters

1.g=divideGrids(DS,gs); //將DS劃分為網(wǎng)格單元

2.Generateclustersand setclusterNo=0; //生成簇集合

3.fori=1tog.length

4.clusterNo++; //標(biāo)記一個新的聚類

5.ifg[i]==0then//判斷g[i]是否已經(jīng)被處理

6.ifdensity(g[i])>θthen//判斷g[i]是否為稠密單元格

7.cluster.add(g[i]);//將稠密單元格加入當(dāng)前聚類中

8. Recursively searchingg[i]; //遞歸搜索

9.elseifdensity(g[i])>θthen//判斷邊界單元格

10.cluster.add(g[i]);//加邊界單元格到當(dāng)前聚類

11. Recursively searchingg[--i]; //遞歸搜索

12.endif

13.g[i]= 1; //標(biāo)記g[i]為已處理

14.endif

15.clusters.add(cluster); //將簇加入到聚類結(jié)果集

16.endfor

17.returnclusters//返回聚類結(jié)果

CLIQUE算法采用DFS搜索算法,在k維空間下計算k-1維子空間,其時間復(fù)雜度為O(nd)(d為數(shù)據(jù)集維度);APS-CLIQUE算法初始化網(wǎng)格單元的數(shù)據(jù)信息,當(dāng)以自適應(yīng)生成策略計算時,其時間復(fù)雜度為O(n)(n為數(shù)據(jù)點映射后的網(wǎng)格數(shù)量);因已去除權(quán)值為0的空單元格,故時間復(fù)雜度不大于O(2n+nd),且整個算法的時間復(fù)雜度為O(nd).

3 實驗結(jié)果與分析

為檢驗APS-CLIQUE算法的聚類效果以及在居住熱區(qū)分布應(yīng)用檢測中的表現(xiàn),實驗基準(zhǔn)數(shù)據(jù)庫分別選取UCI標(biāo)準(zhǔn)數(shù)據(jù)庫Iris和成都市出租車軌跡數(shù)據(jù)集(簡稱數(shù)據(jù)集M)進(jìn)行對比實驗.Iris數(shù)據(jù)集包含150個樣本,每個樣本包含四個特征及樣本的類別;GPS軌跡數(shù)據(jù)集為成都市某出租車公司2014年5月上半月內(nèi)約3000萬條數(shù)據(jù),包含5個特征.實驗用計算機為內(nèi)存12.0 GB、Intel(R)Core(TM)i7-4700MQ CPU @2.40GHz,Windows 7 64位操作系統(tǒng);算法實現(xiàn)采用Java語言,數(shù)據(jù)可視化采用Python語言.

3.1 算法實驗

為了便于觀測,采用主成分分析法[24]對Iris數(shù)據(jù)集進(jìn)行降維處理得到數(shù)據(jù)集PCA-Iris,將數(shù)據(jù)投影到二維空間,其標(biāo)準(zhǔn)化空間分布如圖1所示.

圖1 PAC-Iris空間分布Fig.1 Spatial distribution of PAC-Iris

為了評估聚類算法的有效性和精準(zhǔn)性,采用Dunn指數(shù)[25]作為有效性評價指標(biāo),該指數(shù)是簇間距離和簇直徑的非線性組合,在聚類中,任意簇間最小距離越大,說明簇間分離度越高;任意簇內(nèi)的最大距離越小,說明簇內(nèi)緊密型越高;因此聚類模式越好,Dunn值越大.

在PCA-Iris數(shù)據(jù)集上進(jìn)行三組算法對比實驗,其中第1組實驗分別對CLIQUE算法的網(wǎng)格步長參數(shù)及密度閾值參數(shù)進(jìn)行人工調(diào)參,得到Dunn指數(shù)最優(yōu)的參數(shù)組.第2組實驗在第1組實驗得到的網(wǎng)格步長最優(yōu)值的情況下,使用根據(jù)公式(2)和公式(3)計算出Q2與Q3,再根據(jù)公式(4)計算出自適應(yīng)密度閾值ε=1.904,并傳入CLIQUE算法進(jìn)行聚類分析.第3組實驗使用APS-CLIQUE算法,生成6個簇,聚類效果如圖2所示.

圖2 APS-CLIQUE算法效果圖Fig.2 APS-CLIQUE algorithm renderings

分別計算三組七次實驗的Dunn指數(shù)并對參數(shù)及聚類效果進(jìn)行對比分析,結(jié)果如表1所示.

表1 三組實驗的聚類結(jié)果分析表
Table 1 Three sets of experimental clustering results analysis table

GroupAlgorithmMeshtepDensityThresholdClusters'NumberDunnValidityIndex1ClassicalCLIQUEAlgorithm0.502.130.0920.252.1100.0980.102.1140.0930.252.3130.0840.251.860.1052AlgorithmwithAdaptiveParameters0.251.90470.1103APS-CLIQUEAlgorithm0.251.90460.124

數(shù)據(jù)表明本文提出的APS-CLIQUE算法與傳統(tǒng)CLIQUE相比能夠準(zhǔn)確識別聚類并且提高簇邊界精度.

3.2 應(yīng)用實驗

3.2.1 數(shù)據(jù)處理

本實驗將居民工作日內(nèi)早高峰時段開始乘坐出租車的地理坐標(biāo)值簡單理解為居民居住地的坐標(biāo)值,從而將數(shù)據(jù)集M中所有數(shù)據(jù)的分布地理范圍看成市民居住區(qū)域,進(jìn)一步提取數(shù)據(jù)集M內(nèi)工作日內(nèi)早8:00-9:30時間段內(nèi)的數(shù)據(jù),其數(shù)據(jù)格式如表2所示(僅顯示部分?jǐn)?shù)據(jù)).

當(dāng)某一出租車在t0時刻到t1時刻的載客狀態(tài)由0變?yōu)?,則可以確定在t0到t1中的某一時刻t有乘客上車,且t時刻的坐標(biāo)未知.為了減小誤差,將t0時刻和t1時刻的坐標(biāo)的歐式距離的中點坐標(biāo)近似地看作乘客的上車點,處理所有數(shù)據(jù),得到新的數(shù)據(jù)集;由于忽略了車輛ID、時間等屬性,每行數(shù)據(jù)僅為乘客上車點的經(jīng)緯度坐標(biāo).

3.2.2 聚類結(jié)果分析

通過對數(shù)據(jù)集M數(shù)據(jù)處理后得到40418條只包含經(jīng)緯度的數(shù)據(jù)集N,其坐標(biāo)分布如圖3所示.

在數(shù)據(jù)集N上進(jìn)行兩組實驗:使用不同參數(shù)對CLIQUE算法進(jìn)行調(diào)優(yōu),與APS-CLIQUE算法進(jìn)行聚類效果和評價指標(biāo)值對比,其結(jié)果如表3所示.

表2 數(shù)據(jù)集M格式
Table 2 Format of data setM

IDLatitudeLongitudeCarryingStatePonitofTime13330.627502104.03184108:02:3213330.627519104.03192108:03:3213430.631976104.03836008:02:1413430.631983104.03857108:03:5313430.631994104.03870108:04:4113430.632017104.03742108:05:2113430.632025104.03801108:06:0313430.631982104.03822108:06:5413430.631926104.03843008:07:3213530.575224104.10437008:08:11

圖3 數(shù)據(jù)集N坐標(biāo)分布圖Fig.3 Coordinate distribution map of data set N

表3中實驗1～7為第一組實驗,使用原始CLIQUE算法;實驗8為第二組實驗,使用APS-CLIQUE算法.各實驗在不同規(guī)模的數(shù)據(jù)集下的實際運行時間如圖4所示.

表3 聚類結(jié)果對比

Table 3 Comparison of clustering results

GroupExperi-mentAlgorithmMeshStepDensityThresholdClusters'NumberDunnValidityIndex11234567CLIQUEAlgorithm1003.69585.36E-4753.612357.84E-4503.616339.28E-4253.618218.73E-4502.818849.47E-4502.3236710.06E-4501.428167.54E-428APS-CLIQUEAlgorithm532.18217211.94E-4

通過實驗結(jié)果對比分析,對于CLIQUE算法,在密度閾值不變的情況下,網(wǎng)格步長對于Dunn指數(shù)的影響較大;選取合適的網(wǎng)格步長后再調(diào)整密度閾值對Dunn指數(shù)進(jìn)行調(diào)優(yōu).

對于APS-CLIQUE算法,使用自適應(yīng)參數(shù)生成策略后Dunn指數(shù)要高于其他組實驗.在真實數(shù)據(jù)集中,不同算法實驗下Dunn系數(shù)的對比如圖5所示.

圖4 不同規(guī)模的數(shù)據(jù)在各算法下的實際運行時間Fig.4 Actual running time of data of different scales under different algorithms

在實際應(yīng)用中,數(shù)據(jù)不完全服從預(yù)先設(shè)定的分布.在成都市區(qū)中,存在大量沒有或僅有一個數(shù)據(jù)對象的區(qū)域,也存在數(shù)據(jù)對象密度非常高的區(qū)域,這些區(qū)域的存在對整體區(qū)域算數(shù)平均值影響較大.由公式(4)可知上四分位距排除了大量無數(shù)據(jù)單元格,降低了數(shù)據(jù)形態(tài)兩端對結(jié)果的干擾,當(dāng)密度閾值參數(shù)較大且波動幅度較小時密度較大的網(wǎng)格會被加入到聚類中,使得簇內(nèi)數(shù)據(jù)對象更加緊密,簇間分離度高,Dunn指數(shù)變大;同時根據(jù)公式(5)計算出邊界網(wǎng)格密度閾值,對聚類邊界進(jìn)行了優(yōu)化處理,聚類效果較好.

圖5 各實驗Dunn指數(shù)比較Fig.5 Comparing the Dunn validity index of each experiment

使用在線數(shù)據(jù)處理工具,通過百度地圖API將上傳的數(shù)據(jù)點標(biāo)注在地圖上,修正漂移后繪制居住熱區(qū)分析圖,局部放大后如圖6所示.

圖6 成都市居住熱區(qū)分析圖Fig.6 Analysis chart of residential hotspots in Chengdu

3.3 實驗總結(jié)

算法實驗使用UCI標(biāo)準(zhǔn)數(shù)據(jù)集,通過3組實驗逐步優(yōu)化了CLIQUE算法的參數(shù)值并驗證了APS-CLIQUE算法自適應(yīng)策略及聚類邊界精度優(yōu)化的有效性,其聚類效果優(yōu)于原始CLIQUE算法;為進(jìn)一步說明本算法對于現(xiàn)實世界數(shù)據(jù)聚類問題的性能和應(yīng)用,應(yīng)用實驗分別使用不同參數(shù)的CLIQUE算法和APS-CLIQUE算法對成都市出租車軌跡數(shù)據(jù)集M進(jìn)行多次實驗并根據(jù)Dunn指數(shù)評估聚類效果,比較不同實驗的運行時間以及評價指標(biāo),證明了APS-CLIQUE算法在真實數(shù)據(jù)集上同樣具有一定的優(yōu)越性.最后根據(jù)聚類結(jié)果繪制城市居住熱區(qū)分析圖,顯示效果與公眾已知的城市居住熱區(qū)基本相同.

4 結(jié)束語

APS-CLIQUE算法通過四分位數(shù)箱形模型計算自適應(yīng)密度閾值,可以有效地識別稠密單元格;通過計算邊界網(wǎng)格密度閾值,優(yōu)化聚類邊緣的識別算法,提高了聚類精度.實驗采用UCI標(biāo)準(zhǔn)數(shù)據(jù)集以及成都市出租車軌跡數(shù)據(jù)集,通過大量算法實驗和應(yīng)用實驗,分析APS-CLIQUE算法與傳統(tǒng)的CLIQUE算法的聚類效果以及時間復(fù)雜度,以Dunn指數(shù)作為評價指標(biāo)證明了以上兩種算法在聚類效果和聚類精度上均有較為明顯的提高,并直觀展示了成都市中心居住熱區(qū)分布.本算法的局限性是使用出租車GPS數(shù)據(jù),僅能代表部分用戶出行數(shù)據(jù),不能代表私家車出行、步行等更隱私的用戶行為數(shù)據(jù),并且只對二維數(shù)據(jù)進(jìn)行聚類分析.如果可以獲取更多的數(shù)據(jù)集并進(jìn)一步地增加居民的年齡、職業(yè)、收入等屬性,從高維數(shù)據(jù)中挖掘更多的與地理位置相關(guān)的數(shù)據(jù)特征,則可以更好地提供智能化的決策.