梁卓靈，元昌安，覃 曉，喬少杰，韓 楠，范勇強(qiáng)

（1．廣西大學(xué)，南寧 530004；2．南寧師范大學(xué)，南寧 530001；3．成都信息工程大學(xué)，成都 610225；4．成都市環(huán)境保護(hù)信息中心，成都 610015）

近年來(lái)，隨著GPS（global positioning system）設(shè)備、衛(wèi)星和無(wú)線電傳感網(wǎng)絡(luò)［1－2］等定位技術(shù)的快速發(fā)展，人們能更方便快捷地對(duì)全球范圍內(nèi)各類移動(dòng)對(duì)象進(jìn)行有效跟蹤，并由此采集到豐富的移動(dòng)軌跡數(shù)據(jù)［3］。熱點(diǎn)區(qū)域是移動(dòng)軌跡中隱含的重要信息，能夠表示移動(dòng)對(duì)象經(jīng)常出沒(méi)的、帶有重要語(yǔ)義信息的地區(qū)。提取熱點(diǎn)區(qū)域能為人類日常出行、觀光旅游等推薦個(gè)性化路線，也能為城市交通管理、道路規(guī)劃等提供輔助決策依據(jù)［4－6］。

在現(xiàn)有的研究工作中，主要使用空間聚類的方法來(lái)挖掘熱點(diǎn)區(qū)域。如Ashbrook等［7］采用K means算法挖掘軌跡數(shù)據(jù)中的重要地點(diǎn)，但它存在初始中心點(diǎn)選擇困難且影響結(jié)果等缺點(diǎn)，容易取得局部最優(yōu)解。呂紹仟等［8］提出基于軌跡結(jié)構(gòu)的框架（TS＿HS），以實(shí)現(xiàn)區(qū)分識(shí)別多密度的活動(dòng)熱點(diǎn)區(qū)域。鄭林江等［9］提出基于網(wǎng)格密度的熱點(diǎn)區(qū)域提取方法，便于處理大規(guī)模的空間數(shù)據(jù)，但其網(wǎng)格大小k和網(wǎng)格密度閾值γ都難以選取。還有利用DBSCAN算法［10］對(duì)用戶運(yùn)行速度較慢的區(qū)域進(jìn)行聚類，從而發(fā)現(xiàn)用戶的興趣區(qū)域，但是DBSCAN對(duì)參數(shù)的設(shè)定比較敏感，當(dāng)不同簇類的樣本集密度相差較大時(shí)，算法的聚類效果較差。

綜上所述，多數(shù)挖掘算法需要調(diào)試參數(shù)，且參數(shù)的選取對(duì)聚類結(jié)果有較大影響。為了更好地挖掘用戶出行的熱點(diǎn)區(qū)域，針對(duì)K means算法對(duì)初始值敏感易陷入局部最優(yōu)解，DBSCAN算法在密度不均勻數(shù)據(jù)集上聚類效果差［11］等問(wèn)題，本文提出基于改進(jìn)譜聚類的熱點(diǎn)區(qū)域挖掘算法（hot regionmining algorithm based on improved spectral clustering，ISCRM）。

1 基本概念

1．1 GPS軌跡及位置點(diǎn)

定義1 用戶位置點(diǎn)（user location point）。

由GPS設(shè)備記錄的用戶所處的位置點(diǎn)P定義為一個(gè)三元組，記為P＝（Lat，Lng，t）。其中Lat代表緯度坐標(biāo)，Lng代表經(jīng)度坐標(biāo)，t代表當(dāng)前時(shí)間戳。

定義2 GPS軌跡（GPS trajectory）。

一條GPS軌跡（trajectory）［12］是由一系列采樣時(shí)間間隔相等的用戶位置點(diǎn)Pi以時(shí)間順序連接而成，如軌跡Tra＝（P1，P2，Pi，…，Pn），其中Pi∈P，Pi＋1．t＞Pi．t，（1≤i＜n）。如圖1所示，用戶位置點(diǎn)序列（P1，P2，…，Pi，P8）即組成軌跡Tra1。

圖1 GPS軌跡及停留點(diǎn)示意圖

1．2 改進(jìn)的NJW 譜聚類算法

NJW（Ng Jordan Weiss）是譜聚類中的經(jīng)典算法［12］，其基本思想是：以每個(gè)樣本數(shù)據(jù)為頂點(diǎn)V，以樣本相似性為頂點(diǎn)間連接邊E賦權(quán)重W，由此得到基于樣本數(shù)據(jù)點(diǎn)及其相似性度量的無(wú)向加權(quán)圖G＝（V，E，W），從而將聚類問(wèn)題轉(zhuǎn)化為圖劃分問(wèn)題。

1）傳統(tǒng)NJW 算法在計(jì)算相似度矩陣W 時(shí)，一般用高斯核函數(shù)來(lái)度量?jī)蓴?shù)據(jù)點(diǎn)間的相似性，兩個(gè)樣本之間的相似度。其中 σi＝dist（xi，xT）是樣本點(diǎn)i到其第T個(gè)近鄰點(diǎn)的歐氏距離［15－16］。

2）針對(duì)傳統(tǒng)NJW 算法不能自動(dòng)確定聚類數(shù)目的問(wèn)題，改進(jìn)的NJW 算法［17］采用基于本征間隙的自動(dòng)譜聚類算法［18］來(lái)解決。即在計(jì)算規(guī)范Laplacian矩陣的特征值時(shí)，將其按從大到小的順序排列為λ1≥λ2≥…≥λn。然后根據(jù)矩陣的擾動(dòng)理論，計(jì)算本征間隙序列｛g1，g2，…，gn－1｜gi＝λi－λi＋1｝，求得相鄰特征值之間的差。在這系列差值中找到第一個(gè)極大值，則該值對(duì)應(yīng)的下標(biāo)就是聚類數(shù)目，即類別數(shù)k＝arg min｛gi－gj｜j＜i＞0＆＆gi－gi＋1＞0｝［19］。但尺度參數(shù)σ需要人為選取，且其無(wú)法準(zhǔn)確反映數(shù)據(jù)集樣本的真實(shí)分布。為此，改進(jìn)的NJW 譜聚類算法，借鑒Self Tuning［14］相關(guān)算法的思想，在計(jì)算相似度矩陣W 時(shí)使用針對(duì)樣本i的自適應(yīng)尺度

2 改進(jìn)譜聚類的熱點(diǎn)區(qū)域挖掘算法

經(jīng)典的熱點(diǎn)區(qū)域挖掘算法對(duì)參數(shù)的選取較為敏感，容易影響最終對(duì)熱點(diǎn)區(qū)域的挖掘效果。如采用K means算法，它對(duì)孤立點(diǎn)較為敏感，存在初始中心點(diǎn)選擇困難且影響結(jié)果等缺點(diǎn)，在非凸數(shù)據(jù)集上表現(xiàn)較差［20］；而采用DBSCAN算法，需要對(duì)掃描半徑Eps，最小樣本數(shù)閾值Min Pts聯(lián)合調(diào)參，當(dāng)不同簇類的樣本集密度相差較大時(shí)，難以選取合適的參數(shù)組合，算法的聚類效果較差。因此本文提出基于改進(jìn)譜聚類的熱點(diǎn)區(qū)域挖掘算法（hot region mining algorithm based on improved spectral clustering，ISCRM）。

ISCRM算法的主要思想是：首先，依據(jù)時(shí)間閾值和距離閾值從移動(dòng)軌跡數(shù)據(jù)中提取用戶停留點(diǎn)；其次，引入自適應(yīng)尺度參數(shù)σi，以用戶停留點(diǎn)為頂點(diǎn)集合，構(gòu)建停留點(diǎn)間相似矩陣及拉普拉斯矩陣；接著，自動(dòng)確定聚類數(shù)目k，計(jì)算拉普拉斯矩陣前k個(gè)最大特征值及其對(duì)應(yīng)的特征向量，構(gòu)建特征向量空間；最后再用K means算法對(duì)向量空間中的特征向量進(jìn)行聚類，獲得k個(gè)簇類及其簇類中心，從而得到熱點(diǎn)區(qū)域。為此，需對(duì)提取用戶停留點(diǎn)、構(gòu)造停留點(diǎn)集的相似性矩陣、拉普拉斯矩陣等步驟進(jìn)行設(shè)計(jì)。

2．1 提取用戶停留點(diǎn)

定義3 停留軌跡段（stay trajectory）。

停留軌跡段L是一系列位置點(diǎn)的集合，可定義為：L＝｛Pi｜i∈［m，n］，且Distance（Pm，Pn）≤Dthreh，｜Pn．t－Pm．t｜≥Tthreh，Pi．v＜max＿speed｝。其中，Distance（Pm，Pn）表示位置點(diǎn)Pm和Pn之間的距離，Dthreh表示指定的距離閾值，Pi．t表示位置點(diǎn)Pi的采樣時(shí)間，Tthreh表示指定的時(shí)間閾值，max＿speed是指定的用戶移動(dòng)最大速度閾值。

定義4 停留點(diǎn)（stay point）。

停留點(diǎn)s定義為一個(gè)三元組，記為：s＝（s．Lat，s．Lng，s．T）。其中，s．Lat，s．Lng分別是計(jì)算停留軌跡段L＝｛Pm，Pm＋1，…，Pn｝的平均緯度和平均經(jīng)度，也就是停留點(diǎn)的經(jīng)緯度坐標(biāo)，其計(jì)算公式如下：

s．T＝｜Pn．t－Pm．t｜代表用戶在停留點(diǎn)s處的停留時(shí)間。

如圖1所示，L1＝｛P3，P4，P5，P6｝等一系列點(diǎn)可組成停留軌跡段，圖1中紅色點(diǎn)即為從軌跡段中提取到的停留點(diǎn)位置。

停留點(diǎn)是指用戶停留時(shí)間較長(zhǎng)的地點(diǎn)，而熱點(diǎn)區(qū)域就是停留點(diǎn)聚集的地區(qū)。因此本文對(duì)熱點(diǎn)區(qū)域進(jìn)行挖掘，需從移動(dòng)軌跡數(shù)據(jù)中提取用戶出行的停留點(diǎn)。

算法1 停留點(diǎn)提取算法。

輸入：軌跡點(diǎn)列表（gps＿obj＿list），max＿time（時(shí)間閾值），max＿speed（速度閾值）

輸出：停留點(diǎn)列表

1）counts＝len（gps＿obj＿list）；／／獲取軌跡點(diǎn)對(duì)象數(shù)量

2）i＝0，j＝1； ／／設(shè)置i，j初始值

3）while i，j＜＝counts do／／遍歷列表（gps＿obj＿list）中的軌跡點(diǎn)

／／插入軌跡點(diǎn)i，j，保存在位置點(diǎn)小組L中

4） L←insert（point＿i，point＿j）

／／計(jì)算兩點(diǎn)間距離

5） ed＿distance＝get＿distance（point＿i，point＿j）；

6） t＿diff＝get＿timestamp（point＿i，point＿j）； ／／計(jì)算兩點(diǎn)間時(shí)間間隔

7） Mean＿speed＝ed＿distance／t＿diff； ／／計(jì)算軌跡點(diǎn)間的速度

8） if t＿diff＞max＿time＆＆Mean＿speed ＜max＿speed then

9） Cal＿means＿pos（s，L）；／／根據(jù)位置點(diǎn)小組L及公式（1）、公式（2），計(jì)算得停留點(diǎn)信息

10） Stay＿point＿list．a(chǎn)ppend（s）；／／并入停留點(diǎn)

11） i＝j(luò)；

12） end if

13） j＝j(luò)＋1；

14） if j＝＝counts then

／／如果j等于counts，即遍歷到最后一點(diǎn)

15） Cal＿means＿pos（s，L）；

／／計(jì)算得停留點(diǎn)信息

16） Stay＿point＿list．a(chǎn)ppend（s）；／／并入停留點(diǎn)

17） end if

18）end while

19）return stay＿point＿list／／返回停留點(diǎn)列表。

2．2 構(gòu)造停留點(diǎn)集的相似度矩陣

將用戶停留點(diǎn)集S構(gòu)造為無(wú)向加權(quán)圖SG＝（SG．V，SG．E，SG．W）。其中SG．V為圖頂點(diǎn)集合，指代各個(gè)停留點(diǎn)；SG．E為圖的邊集，是停留點(diǎn)之間關(guān)聯(lián)邊的集合；SG．W是權(quán)重集，是各停留點(diǎn)間的相似性的集合，邊上的權(quán)值wij表示停留點(diǎn)si和停留點(diǎn)sj之間的相似性。將加權(quán)圖進(jìn)行最優(yōu)切割，使各個(gè)子圖間的相似性小，子圖內(nèi)部的連接緊密，由此形成多個(gè)簇類。停留點(diǎn)無(wú)向加權(quán)圖見(jiàn)圖2。

圖2 停留點(diǎn)無(wú)向加權(quán)示意圖

如圖2所示，頂點(diǎn)集合S．V由｛s1，s2，…，s4｝等停留點(diǎn)組成，邊集S．E＝｛（si，sj），1≤i，j≤4｝，表示連接兩兩停留點(diǎn)的邊的集合。權(quán)重集S．W＝｛wij，1≤i，j≤4｝，表示停留點(diǎn)間的相似性集合。

在構(gòu)造停留點(diǎn)集的相似度矩陣W 時(shí)，停留點(diǎn)間的相似性wij通常用高斯核函數(shù)來(lái)定義，即：

式（3）中，dist（si，sj）表示兩點(diǎn)間的歐氏距離。其計(jì)算如下：

自適應(yīng)局部參數(shù) σi＝dist（si，sT），代表停留點(diǎn)si到它第T個(gè)近鄰點(diǎn)的歐氏距離，即sT為停留點(diǎn)si的第T個(gè)近鄰點(diǎn)。據(jù)文獻(xiàn)［12－13］選取的經(jīng)驗(yàn)值，以及本文停留點(diǎn)數(shù)據(jù)集的驗(yàn)證，T＝7。

2．3 計(jì)算停留點(diǎn)集的拉普拉斯矩陣

在給定的由用戶停留點(diǎn)構(gòu)成的無(wú)向圖中，一般非規(guī)范拉普拉斯矩陣定義為：

式（5）中：W 為相似度矩陣；D為圖的度矩陣。圖中與某頂點(diǎn)i連接的所有邊上的權(quán)重和即為該頂點(diǎn)的度，計(jì)算如下：

由于本文采用的是對(duì)稱規(guī)范化的拉普拉斯矩陣，因此需在式（6）基礎(chǔ)上進(jìn)一步規(guī)范化，有：

在構(gòu)造拉普拉斯矩陣后，需計(jì)算其特征值，將前k個(gè)最大特征值對(duì)應(yīng)的特征向量組成一個(gè)n行k列的特征矩陣Xn×k，對(duì)矩陣的每一行數(shù)據(jù)進(jìn)行聚類操作。在此之前，需對(duì)Xn×k中的行向量進(jìn)行歸一化，公式如下：

2．4 計(jì)算本征間隙估計(jì)類個(gè)數(shù)

傳統(tǒng)譜聚類算法無(wú)法確定聚類數(shù)目，本文采用基于本征間隙的自動(dòng)譜聚類算法解決。根據(jù)矩陣的擾動(dòng)理論，首先計(jì)算規(guī)范拉普拉斯矩陣的特征值，將其排列為λ1≥λ2≥…≥λn。特征值之間的差值可排列為本征間隙序列｛g1，g2，…，gn－1｜gi＝λi－λi＋1｝。

本征間隙序列中第一個(gè)極大值對(duì)應(yīng)的下標(biāo)即為聚類數(shù)目k，計(jì)算如下：

至此，已介紹了ISCRM算法的全部過(guò)程。下面給出ISCRM算法的具體描述。

算法2 ISCRM算法。輸入：軌跡數(shù)據(jù)集

輸出：聚類結(jié)果

Begin

Step 1 調(diào)用算法1提取軌跡數(shù)據(jù)中的用戶停留點(diǎn)；

Step 2 利用式（3）、式（4）構(gòu)造用戶停留點(diǎn)的相似度矩陣W；

Step 3 根據(jù)式（5）和式（6）計(jì)算非規(guī)范的拉普拉斯矩陣L，進(jìn)一步規(guī)范化，由式（7）獲得對(duì)稱規(guī)范化矩陣L sym；

Step 4 計(jì)算規(guī)范矩陣L sym的特征值，據(jù)特征值之差計(jì)算本征間隙序列，最后由式（9）計(jì)算得聚類數(shù)目k；

Step 5 取L sym前k個(gè)最大特征值對(duì)應(yīng)的特征向量組成特征矩陣Xn×k，據(jù)式（8）對(duì)Xn×k中的行向量進(jìn)行歸一化，得到矩陣Y；

Step 6 將矩陣Y中的每一行看做是空間中的一個(gè)點(diǎn)，使用K means算法對(duì)數(shù)據(jù)點(diǎn)進(jìn)行聚類。

End。

3 實(shí)驗(yàn)分析與比較

3．1 實(shí)驗(yàn)數(shù)據(jù)分析

實(shí)驗(yàn)中使用的數(shù)據(jù)來(lái)自微軟研究院Geolife項(xiàng)目，該項(xiàng)目共記錄了182位對(duì)象的戶外活動(dòng)軌跡，數(shù)據(jù)采集歷時(shí)超過(guò)5年（2007．04—2012．08）。該數(shù)據(jù)集包含17 621條軌跡，分布在30多個(gè)城市（大部分在北京創(chuàng)建）。

首先對(duì)軌跡點(diǎn)進(jìn)行提取，去除速度過(guò)大而導(dǎo)致異常的噪聲點(diǎn)［21］，并選取速度較小而駐留時(shí)間較長(zhǎng)的停留點(diǎn)［22］。在從移動(dòng)軌跡數(shù)據(jù)中提取用戶停留點(diǎn)時(shí)，需要設(shè)置時(shí)間閾值、速度閾值和距離閾值，本文參考文獻(xiàn)［23］對(duì)城市移動(dòng)對(duì)象的研究，為排除紅綠燈路口停留點(diǎn)設(shè)置時(shí)間閾值為120 s，為選取速度較小的移動(dòng)對(duì)象設(shè)置速度閾值為2 m／s，而距離閾值設(shè)置為200 m。不同的閾值取值會(huì)影響提取到的用戶停留點(diǎn)集，進(jìn)而影響到挖掘效果［24－25］，給定時(shí)間閾值，當(dāng)距離閾值和速度閾值越低時(shí)，提取到停留點(diǎn)數(shù)量也隨之減少，挖掘到的熱點(diǎn)區(qū)域較小且分散，當(dāng)距離閾值和速度閾值較高時(shí)，挖掘到的熱點(diǎn)區(qū)域較大且集中。

此處以北京和上海為例，設(shè)置閾值后提取停留點(diǎn)，調(diào)用百度地圖API對(duì)城市內(nèi)部分用戶停留點(diǎn)進(jìn)行可視化展示［26］。由于終端定位到的GPS點(diǎn)坐標(biāo)與百度地圖的坐標(biāo)不在同一個(gè)坐標(biāo)系，顯示到百度地圖上時(shí)其位置有較大偏差。通過(guò)使用百度地圖提供的轉(zhuǎn)換接口［27］，將停留點(diǎn)原始坐標(biāo)轉(zhuǎn)換為百度坐標(biāo)，保存在json文件中，然后找到百度地圖開(kāi)發(fā)文檔－加載海量點(diǎn)API進(jìn)行調(diào)用展示。效果如圖3所示，其中粉紅色的星型點(diǎn)即為用戶停留點(diǎn)分布地點(diǎn)。

從圖3（a）、（b）可以看出，由于大多數(shù)軌跡數(shù)據(jù)在北京市創(chuàng)建，因此上海地區(qū)分布的用戶停留點(diǎn)較稀疏，而北京地區(qū)的用戶停留點(diǎn)數(shù)量更密集。

圖3 用戶停留點(diǎn)的可視化展示示意圖

3．2 性能對(duì)比實(shí)驗(yàn)

為了說(shuō)明ISCRM算法的有效性，本節(jié)特將其與K means算法、DBSCAN算法進(jìn)行了性能對(duì)比分析。本次實(shí)驗(yàn)環(huán)境為：Win10 64bit操作系統(tǒng)，8GB內(nèi)存，CPU 2．60GHz；使用python語(yǔ)言在pycharm上實(shí)現(xiàn)。實(shí)驗(yàn)數(shù)據(jù)為從Geolife數(shù)據(jù)集中提取，共包含100個(gè)用戶的10 949個(gè)出行停留點(diǎn)數(shù)據(jù)。

3．2．1 實(shí)驗(yàn)1

對(duì)于用戶停留點(diǎn)數(shù)據(jù)集在未知實(shí)際類別信息的情況下，可以從簇內(nèi)的稠密程度和簇間的離散程度來(lái)評(píng)估聚類的效果，此處采用常見(jiàn)的評(píng)價(jià)指標(biāo)輪廓系數(shù)SC（silhouette coefficient），其計(jì)算式表達(dá)為

式（10）中：a代表樣本到同簇類其他樣本的距離平均值；b代表樣本到其他簇類樣本的距離均值。SC取值在［－1，1］。如果SC越接近1，說(shuō)明樣本所在簇越合理；若SC接近－1則說(shuō)明樣本點(diǎn)更應(yīng)該分到其他簇中。

本次實(shí)驗(yàn)中，K means算法和DBSCAN算法在一定區(qū)間內(nèi)選取不同的參數(shù)進(jìn)行聚類，發(fā)現(xiàn)K means算法及DBSCAN算法均易受參數(shù)選擇的影響，實(shí)驗(yàn)結(jié)果波動(dòng)較大；而ISCRM算法無(wú)需人工調(diào)試參數(shù)，可直接獲得最好結(jié)果。其中K means算法隨機(jī)選取k個(gè)初始中心，通過(guò)不斷迭代最終形成k個(gè)聚簇，而k個(gè)初始中心不同的選取將對(duì)聚類結(jié)果產(chǎn)生極大影響。本文算法通過(guò)自適應(yīng)局部參數(shù)σi構(gòu)建盡可能準(zhǔn)確反映樣本分布信息的相似度矩陣，并通過(guò)計(jì)算本征間隙估計(jì)的聚類數(shù)，把對(duì)原始數(shù)據(jù)集的聚類轉(zhuǎn)為對(duì)向量空間的k個(gè)特征向量進(jìn)行聚類，避免了對(duì)初始值設(shè)置的敏感性。另外根據(jù)矩陣擾動(dòng)理論，對(duì)于給定的數(shù)據(jù)集合包含k個(gè)彼此分離的簇類，規(guī)范拉普拉斯矩陣的特征值之間的差距由這k個(gè)簇類的空間分布決定。在理想情況下，前k個(gè)最大特征值應(yīng)等于1，而緊鄰的第k＋1個(gè)特征值則小于1，因此第k個(gè)和第k＋1個(gè)特征值之間的本征間隙即為極大值。所以計(jì)算本征間隙估計(jì)聚類數(shù)是具有理論依據(jù)的，得到的聚類數(shù)k具有一定準(zhǔn)確性，而在此基礎(chǔ)上選取的k個(gè)特征向量組成的特征空間，可有效反映原始數(shù)據(jù)集，與原數(shù)據(jù)空間構(gòu)造的k個(gè)簇類相對(duì)應(yīng)。

從運(yùn)行時(shí)間來(lái)看，K means算法耗費(fèi)時(shí)間最短，而ISCRM算法最長(zhǎng)；但在輪廓系數(shù)指標(biāo)中，K means算法及DBSCAN算法均不及ISCRM 算法高，且試驗(yàn)結(jié)果也不如ISCRM算法穩(wěn)定。對(duì)比表1中各聚類算法在停留點(diǎn)數(shù)據(jù)集上的表現(xiàn)，盡管K means和DBSCAN算法運(yùn)行時(shí)間較短，但在其繁瑣的參數(shù)選取環(huán)節(jié)上會(huì)耗費(fèi)額外的時(shí)間。而ISCRM算法依據(jù)自適應(yīng)局部參數(shù)σi描述樣本實(shí)際分布，以及自動(dòng)估計(jì)聚類數(shù)目，可獲得更貼近樣本真實(shí)分布的特征向量空間，并對(duì)特征空間進(jìn)行聚類，也在一定程度上加快了收斂速度。ISCRM算法通過(guò)自適應(yīng)調(diào)節(jié)參數(shù)直接獲得的結(jié)果輪廓系數(shù)最高，代表聚類結(jié)果最合理。

表1 停留點(diǎn)數(shù)據(jù)集上聚類結(jié)果

3．2．2 實(shí)驗(yàn)2

在實(shí)驗(yàn)1基礎(chǔ)上對(duì)數(shù)據(jù)集中的軌跡進(jìn)行處理，僅提取北京市內(nèi)的用戶出行停留點(diǎn)，利用3種算法分別對(duì)其聚類。為了方便檢測(cè)實(shí)驗(yàn)結(jié)果，采用python的matplotlib庫(kù)，以經(jīng)緯度為坐標(biāo)畫(huà)出用戶停留點(diǎn)的空間分布以及3種算法的聚類結(jié)果。圖4為北京市內(nèi)的用戶停留點(diǎn)分布圖，圖5和圖6直觀反映了K means算法和DBSCAN算法在不同參數(shù)條件下得到的聚類結(jié)果。ISCRM算法實(shí)驗(yàn)結(jié)果如圖7所示。

圖5 K means算法實(shí)驗(yàn)結(jié)果示意圖

圖6 DBSCAN算法實(shí)驗(yàn)結(jié)果示意圖

從圖5和圖6中的聚類結(jié)果可以看出，K means算法選取不同k值時(shí)，得到的簇類數(shù)也不同，其將中部距離較近的數(shù)據(jù)點(diǎn)分成了多個(gè)簇類，距離較遠(yuǎn)的數(shù)據(jù)點(diǎn)反而分到同個(gè)簇類，不適于非凸數(shù)據(jù)集，無(wú)法很好地劃分簇類；DBSCAN算法的聚類結(jié)果也易受參數(shù)選擇的影響，如果選用固定參數(shù)識(shí)別簇類，當(dāng)簇類的稀疏程度不同時(shí)，較稀的簇類可能被劃分為多個(gè)類，而密度較大且距離較近的簇類可能被合并成一個(gè)類，如圖6（a）、圖6（b）中部的一大塊區(qū)域被合并為一個(gè)簇類。

ISCRM算法進(jìn)行聚類時(shí)，其依賴于相似矩陣和拉普拉斯矩陣的構(gòu)建，利用自適應(yīng)局部參數(shù)來(lái)反映樣本數(shù)據(jù)集的真實(shí)分布，把聚類操作轉(zhuǎn)換為對(duì)圖分割操作，相比傳統(tǒng)方法更能適用于不同類型的樣本空間。圖7實(shí)驗(yàn)結(jié)果顯示，其通過(guò)自適應(yīng)聚類獲得7個(gè)簇類，相比前2個(gè)算法，其簇類分布最為均勻合理，不同簇間樣本點(diǎn)距離更遠(yuǎn)，同簇內(nèi)樣本點(diǎn)更為緊密。

圖7 ISCRM算法實(shí)驗(yàn)結(jié)果示意圖

3．3 熱點(diǎn)區(qū)域挖掘

為了更直觀展示聚類效果及用戶停留點(diǎn)的熱點(diǎn)區(qū)域，我們通過(guò)百度地圖API，將利用ISCRM算法得到的聚類結(jié)果直接投影在實(shí)際的地圖上。圖8為調(diào)用海量點(diǎn)API顯示用戶停留點(diǎn)聚類結(jié)果，圖9為調(diào)用熱力圖API展示用戶出行熱點(diǎn)區(qū)域的中心位置。

圖8 北京市內(nèi)用戶出行停留點(diǎn)聚類結(jié)果示意圖

圖9 北京市內(nèi)用戶出行熱點(diǎn)區(qū)域中心位置示意圖

通過(guò)計(jì)算，我們可獲得各簇類停留點(diǎn)個(gè)數(shù)以及各簇類中心點(diǎn)位置，設(shè)定簇類中心位置為熱點(diǎn)區(qū)域，簇類停留點(diǎn)個(gè)數(shù)即為熱點(diǎn)地區(qū)的熱度值，由此可得出北京市內(nèi)用戶出行的熱點(diǎn)區(qū)域，并根據(jù)區(qū)域內(nèi)的熱度值對(duì)這些熱點(diǎn)區(qū)域進(jìn)行由高到低的排列。分析圖8和圖9中的簇類中心及熱度值，我們發(fā)現(xiàn)熱度值排第一的區(qū)域?yàn)椋罕本┐髮W(xué)，清華大學(xué)，圓明園等地；熱度值排第二的區(qū)域?yàn)椋菏锥紟煼洞髮W(xué)，中國(guó)工商大學(xué)，北京動(dòng)物園等地；熱度值排第三的區(qū)域?yàn)椋褐醒胍魳?lè)學(xué)院，天安門(mén)，人民大會(huì)堂等地；熱度值排第四的區(qū)域?yàn)椋罕本┱?，夕照寺等地?/p>

縱觀圖中熱點(diǎn)區(qū)域分布，我們發(fā)現(xiàn)排在前列的熱點(diǎn)區(qū)域主要集中在大學(xué)城、公園及天安門(mén)、火車站一帶，這些區(qū)域在一天中都具有較大的人流量，以及較高的出行需求，是人們密集出行的重點(diǎn)區(qū)域。

4 結(jié)論

本文中主要提出了基于改進(jìn)譜聚類的熱點(diǎn)區(qū)域挖掘算法。其引入自適應(yīng)尺度參數(shù)σi以及計(jì)算聚類數(shù)目k的方法，以用戶出行停留點(diǎn)為頂點(diǎn)集合，構(gòu)建相似矩陣及拉普拉斯矩陣，再用K means算法進(jìn)行聚類。其中，利用自適應(yīng)尺度參數(shù)σi能更準(zhǔn)確反映停留點(diǎn)數(shù)據(jù)集的真實(shí)分布；且通過(guò)計(jì)算本征間隙來(lái)自動(dòng)確定聚類數(shù)目k，有效避免了因?yàn)閰?shù)選取而獲得不好結(jié)果的情況。該方法保留了譜聚類算法的優(yōu)勢(shì)，對(duì)比傳統(tǒng)方法，其對(duì)孤立點(diǎn)不敏感，適用于任意形狀的樣本空間，能夠準(zhǔn)確地獲得聚類結(jié)果。在性能對(duì)比試驗(yàn)中，該方法在對(duì)用戶出行停留點(diǎn)聚類問(wèn)題上，其聚類結(jié)果更合理，同簇類點(diǎn)更緊密。在對(duì)北京市內(nèi)用戶出行熱點(diǎn)區(qū)域的挖掘?qū)嶒?yàn)中，通過(guò)調(diào)用百度地圖API在實(shí)際地圖上展示了用戶停留點(diǎn)的聚類結(jié)果及聚類中心，成功識(shí)別出七大熱點(diǎn)區(qū)域，驗(yàn)證了本文所提方法的可行性。

未來(lái)的研究可以使用更大規(guī)模的數(shù)據(jù)量，通過(guò)文獻(xiàn)［24］提出的分布式并行化處理縮短運(yùn)行時(shí)間，更加詳盡地挖掘多個(gè)城市用戶頻繁活動(dòng)的熱點(diǎn)區(qū)域。