一種用于居住熱區(qū)聚類的改進(jìn)CLIQUE算法

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

1(哈爾濱師范大學(xué) 計(jì)算機(jī)科學(xué)與信息工程學(xué)院,哈爾濱 150025)2(上海市信息安全綜合管理技術(shù)研究重點(diǎn)實(shí)驗(yàn)室,上海 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é)者對(duì)其進(jìn)行研究并取得了成果,如Zheng 等[5,6]以GeoLife項(xiàng)目為基礎(chǔ)通過(guò)挖掘個(gè)體的活動(dòng)規(guī)律來(lái)尋找各對(duì)象之間時(shí)空序列的相似性和活動(dòng)模式;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)熱點(diǎn)分析[10]等.上述研究多以分析對(duì)象運(yùn)動(dòng)規(guī)律為主要研究?jī)?nèi)容,對(duì)于城市聚居區(qū)域熱度分布的研究相對(duì)較少,而且該問(wèn)題在基于POI查詢和基于位置服務(wù)應(yīng)用中具有很高的商業(yè)價(jià)值.熱區(qū)聚類研究常用算法有基于劃分的K-means算法[11]和FCM算法[12]、基于空間的DBSCAN算法[13]、基于網(wǎng)格的STING算法[14]、基于層次的CURE算法[15]、基于密度和網(wǎng)格的CLIQUE算法[16]等.對(duì)于CLIQUE算法而言,盡管效率較高,但對(duì)網(wǎng)格步長(zhǎng)值、密度閾值二者的確定及聚類邊界精度值的控制不夠理想[17],諸多學(xué)者已在CLIQUE算法的基礎(chǔ)上進(jìn)行改進(jìn),如CAG-CLIQUE算法[18]采用邊界動(dòng)態(tài)調(diào)整技術(shù)不斷修正網(wǎng)格步長(zhǎng)來(lái)控制邊界精度、GDCAP算法[19]通過(guò)網(wǎng)格密度期望的積差選取密度閾值、A-Stream算法[20]使用數(shù)據(jù)平均密度與標(biāo)準(zhǔn)差的和來(lái)選取密度閾值等,以上算法降低了參數(shù)設(shè)定的難度并提高了聚類邊界的精度;但是,真實(shí)數(shù)據(jù)中存在的異常值會(huì)影響數(shù)學(xué)期望和標(biāo)準(zhǔn)差,會(huì)降低以上算法的自適應(yīng)效果[21].

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

2 APS-CLIQUE算法

2.1 相關(guān)定義

CLIQUE算法通過(guò)給定的網(wǎng)格步長(zhǎng)gs將數(shù)據(jù)對(duì)象直接投影到網(wǎng)格空間并計(jì)算網(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擴(kuò)大到與最大的子空間Dmax相等,根據(jù)網(wǎng)格步長(zhǎng)gs將Di劃分為m個(gè)相等的區(qū)間,從而將Di分成m個(gè)互不相交的矩形單元,即網(wǎng)格單元g.

定義3.(單元格的有效性)若令vj表示gj的有效性,當(dāng)?x>0時(shí)(x為gj中數(shù)據(jù)的個(gè)數(shù))gj為有效,vj=0;否則無(wú)效,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)計(jì)特性和四分位數(shù)的特點(diǎn)[23]為基礎(chǔ)對(duì)密度閾值參數(shù)提出一種基于四分位數(shù)箱形模型自適應(yīng)策略算法.

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

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

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

(1)

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

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

(2)

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

(3)

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

(4)

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

2.3 增強(qiáng)聚類邊界精度

CLIQUE算法中聚類邊界存在問(wèn)題:

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

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

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

(5)

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

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

2.4 APS-CLIQUE算法描述

APS-CLIQUE算法以CLIQUE為基礎(chǔ),預(yù)先通過(guò)四分位數(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)記一個(gè)新的聚類

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

3 實(shí)驗(yàn)結(jié)果與分析

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

3.1 算法實(shí)驗(yàn)

為了便于觀測(cè),采用主成分分析法[24]對(duì)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

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

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

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

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

表1 三組實(shí)驗(yàn)的聚類結(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)確識(shí)別聚類并且提高簇邊界精度.

3.2 應(yīng)用實(shí)驗(yàn)

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

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

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

3.2.2 聚類結(jié)果分析

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

在數(shù)據(jù)集N上進(jìn)行兩組實(shí)驗(yàn):使用不同參數(shù)對(duì)CLIQUE算法進(jìn)行調(diào)優(yōu),與APS-CLIQUE算法進(jìn)行聚類效果和評(píng)價(jià)指標(biāo)值對(duì)比,其結(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中實(shí)驗(yàn)1～7為第一組實(shí)驗(yàn),使用原始CLIQUE算法;實(shí)驗(yàn)8為第二組實(shí)驗(yàn),使用APS-CLIQUE算法.各實(shí)驗(yàn)在不同規(guī)模的數(shù)據(jù)集下的實(shí)際運(yùn)行時(shí)間如圖4所示.

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

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

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

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

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

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

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

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

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

3.3 實(shí)驗(yàn)總結(jié)

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

4 結(jié)束語(yǔ)

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