一種用于居住熱區聚類的改進CLIQUE算法

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

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

1 引 言

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

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

2 APS-CLIQUE算法

2.1 相關定義

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

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

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

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

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

2.2 基于四分位數箱形模型的參數自適應策略

以數據的統計特性和四分位數的特點[23]為基礎對密度閾值參數提出一種基于四分位數箱形模型自適應策略算法.

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

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

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

(1)

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

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

(2)

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

(3)

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

(4)

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

2.3 增強聚類邊界精度

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

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

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

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

(5)

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

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

2.4 APS-CLIQUE算法描述

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

算法:APS-CLIQUE算法

輸入:DS,gs,ε,θ

輸出:APS-CLIQUE算法結果clusters

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

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

3.fori=1tog.length

4.clusterNo++; //標記一個新的聚類

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

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

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

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

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

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

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

12.endif

13.g[i]= 1; //標記g[i]為已處理

14.endif

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

16.endfor

17.returnclusters//返回聚類結果

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

3 實驗結果與分析

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

3.1 算法實驗

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

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

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

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

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

分別計算三組七次實驗的Dunn指數并對參數及聚類效果進行對比分析,結果如表1所示.

表1 三組實驗的聚類結果分析表
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

數據表明本文提出的APS-CLIQUE算法與傳統CLIQUE相比能夠準確識別聚類并且提高簇邊界精度.

3.2 應用實驗

3.2.1 數據處理

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

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

3.2.2 聚類結果分析

通過對數據集M數據處理后得到40418條只包含經緯度的數據集N,其坐標分布如圖3所示.

在數據集N上進行兩組實驗:使用不同參數對CLIQUE算法進行調優,與APS-CLIQUE算法進行聚類效果和評價指標值對比,其結果如表3所示.

表2 數據集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 數據集N坐標分布圖Fig.3 Coordinate distribution map of data set N

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

表3 聚類結果對比

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

通過實驗結果對比分析,對于CLIQUE算法,在密度閾值不變的情況下,網格步長對于Dunn指數的影響較大;選取合適的網格步長后再調整密度閾值對Dunn指數進行調優.

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

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

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

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

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

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

3.3 實驗總結

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

4 結束語

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