王鐵軍，趙禮劍，朱 熙

（國家測繪地理信息局 重慶測繪院，重慶 401121）

0 引 言

隨著定位技術(shù)的發(fā)展和成熟，以及智能移動(dòng)設(shè)備的應(yīng)用和普及，基于位置的服務(wù)（Location Based Service，LBS）得到了廣泛的應(yīng)用。該服務(wù)利用移動(dòng)互聯(lián)網(wǎng)技術(shù)為廣大移動(dòng)端用戶提供各類位置服務(wù)，以手機(jī)或者其他終端設(shè)備上傳的位置為基礎(chǔ)，在地理信息系統(tǒng)的支持下，向用戶提供生活、工作、社交、休閑娛樂等多種類型的基于位置的服務(wù)[1-2]，如距離較近的賓館、餐飲以及導(dǎo)航或交通擁堵情況等信息。基于位置的服務(wù)通常由LBS服務(wù)平臺（服務(wù)器端）和移動(dòng)端兩部分構(gòu)成。移動(dòng)端通過移動(dòng)通信網(wǎng)絡(luò)向LBS服務(wù)平臺發(fā)出服務(wù)請求，LBS服務(wù)平臺根據(jù)移動(dòng)端請求和其當(dāng)前位置進(jìn)行處理，并將處理結(jié)果返回給移動(dòng)端。LBS服務(wù)平臺記錄了用戶在請求服務(wù)時(shí)的位置及時(shí)間信息，這些信息具有動(dòng)態(tài)、海量、時(shí)空相關(guān)等主要特征。動(dòng)態(tài)特征是指移動(dòng)端處于一個(gè)不斷變化的狀態(tài)中，并非是停止不變的；海量特征指的是不同時(shí)間信息數(shù)據(jù)長期積累，數(shù)據(jù)量非常龐大；時(shí)空相關(guān)性是指位置數(shù)據(jù)在時(shí)間和空間上相互關(guān)聯(lián)。

本文利用數(shù)據(jù)挖掘的相關(guān)理論和方法，對LBS服務(wù)平臺記錄的移動(dòng)端用戶位置信息進(jìn)行聚類和關(guān)聯(lián)分析，提取出移動(dòng)端的常用位置信息，并進(jìn)一步解析出其他相關(guān)信息，從而提供更加智能化、適應(yīng)性更強(qiáng)的服務(wù)，達(dá)到變被動(dòng)為主動(dòng)的服務(wù)目的[3]。

1 常用位置數(shù)據(jù)挖掘方法

位置數(shù)據(jù)挖掘是從移動(dòng)端數(shù)據(jù)集中提煉隱含的、用戶感興趣的空間和非空間的模式、知識、規(guī)則以及相關(guān)特征的過程[4]，是數(shù)據(jù)挖掘研究的重要分支；其概念和含義與數(shù)據(jù)挖掘類似，即從不完全的、模糊的、隨機(jī)的、有噪聲的、海量位置數(shù)據(jù)中，提煉出隱含在數(shù)據(jù)中、人們之前也許不知道的、但又可能具有潛在有用知識的過程。常用的數(shù)據(jù)挖掘算法有：統(tǒng)計(jì)分析方法、時(shí)空聚類方法、計(jì)算幾何分析方法、遺傳算法、神經(jīng)網(wǎng)絡(luò)方法等[5-10]，各種算法都有特定的運(yùn)用環(huán)境。

對于位置挖掘來說，時(shí)空聚類方法是一種常用的方法，其優(yōu)勢在于將位置數(shù)據(jù)劃分為不同的類別，不需要在模型中輸入背景知識，就能夠自動(dòng)挖掘出數(shù)據(jù)本身的特征。目前常用的聚類方法有[11]：基于密度、基于距離、基于層次和基于柵格的方法?；诿芏鹊姆椒▽⒚芏容^大的區(qū)域劃為單獨(dú)的類，與其他聚類方法相比，此方法可以發(fā)現(xiàn)任意形狀的簇；基于距離的方法主要采用迭代法，根據(jù)點(diǎn)之間距離的遠(yuǎn)近決定某個(gè)點(diǎn)到底歸屬于哪個(gè)類別，距離是預(yù)先設(shè)定好的，不同的數(shù)據(jù)中，距離不同；基于層次的方法可以分為凝聚法和分裂法，其主要思想是自下而上合并比較小的類或者自上而下將比較大的類分割成比較小的類；基于柵格的方法主要通過劃分?jǐn)?shù)據(jù)的單元格來發(fā)現(xiàn)類。

DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪聲的基于密度的聚類方法）算法是一種典型的基于密度的聚類算法[12]，其核心思想是用某個(gè)點(diǎn)的鄰域內(nèi)的點(diǎn)數(shù)來衡量該點(diǎn)所在空間的密度，將具有足夠密度的區(qū)域劃分為簇，因此可以發(fā)現(xiàn)任意形狀的聚類簇，并且不需輸入要?jiǎng)澐值木垲悅€(gè)數(shù)。DBSCAN算法中有兩個(gè)重要參數(shù)：Eps和MinPts，前者為定義密度時(shí)的鄰域半徑，用于描述某一樣本鄰域的距離閾值，常用ε表示；后者為定義核心點(diǎn)時(shí)的閾值，用于描述樣本中距離為ε的鄰域中樣本個(gè)數(shù)，常用M表示。

對于數(shù)據(jù)集D=(X1,X2,…,Xm),利用DBSCAN算法進(jìn)行聚類分析步驟如下：

1）樣本聚類：利用公式（1）提取樣本集D中任意點(diǎn) Xj鄰域半徑ε范圍內(nèi)所有點(diǎn)，用Nε（Xj）表示。

2）密度計(jì)算：用ρ(Xj)表示點(diǎn)Xj的密度，計(jì)算方法見公式（2），密度是一個(gè)整數(shù)值，且與鄰域ε緊密相關(guān)。

3）核心對象判別：若ρ(Xj)≥M，則稱Xj為樣本D的核心對象。

4）密度直達(dá)：如果點(diǎn)Xi位于核心對象Xj的ε鄰域中，則稱Xi由Xj密度直達(dá)，反之則不一定成立。

5）密度可達(dá)：若樣本集D中存在核心對象p1，p2，p3,…,pt，t≥2，且pi+1由pi密度直達(dá)（i=1,2,…,t-1），則稱pt是從p1密度可達(dá)的。

6）密度相連：若樣本集D中存在核心對象p1，p2，p3，若p2和p3均可由p1密度可達(dá)，則稱p2和p3密度相連，密度相連具有對稱性。

2 基于隨機(jī)序列GPS數(shù)據(jù)集的移動(dòng)端常用位置挖掘

2.1 LBS系統(tǒng)位置數(shù)據(jù)分析

LBS服務(wù)器端提供的隨機(jī)序列GPS數(shù)據(jù)集具有范圍分布廣、數(shù)據(jù)量大、時(shí)間跨度長、離散度高等特點(diǎn)，且在數(shù)據(jù)中存在大量的冗余信息，給數(shù)據(jù)的挖掘帶來了極大的不便。因此在數(shù)據(jù)挖掘前，必須對數(shù)據(jù)進(jìn)行噪聲濾波，去除不必要的冗余，確保提取位置的準(zhǔn)確性。

2.2 常用位置挖掘?qū)嵤?/h3>

根據(jù)所獲取的數(shù)據(jù)集的特點(diǎn)，綜合應(yīng)用時(shí)空聚類和統(tǒng)計(jì)分析的方法處理隨機(jī)序列GPS數(shù)據(jù)集，同時(shí)結(jié)合電子地圖興趣點(diǎn)等相關(guān)數(shù)據(jù)進(jìn)行移動(dòng)端常用位置的提取，在此基礎(chǔ)上賦予用戶位置語義信息，從而形成基于隨機(jī)序列GPS數(shù)據(jù)集的移動(dòng)端常用位置挖掘方法。數(shù)據(jù)處理流程如圖1所示。

圖1 基于隨機(jī)序列GPS數(shù)據(jù)集的移動(dòng)端常用位置挖掘流程Fig.1 Flow of mobile location common mining based on random sequence GPS dataset

1）坐標(biāo)投影轉(zhuǎn)換：LBS服務(wù)平臺提供的移動(dòng)端位置信息用經(jīng)緯度表示，給距離量算、評估等帶來不便；為能直觀分析和統(tǒng)計(jì)，根據(jù)移動(dòng)用戶端的位置，選擇中央子午線，采用CGCS2000國家大地坐標(biāo)系橢球參數(shù)進(jìn)行高斯投影正算[13]，將經(jīng)緯度坐標(biāo)（B，L）轉(zhuǎn)換為高斯平面坐標(biāo)（x，y），方法見公式（3）。

式中， (B)為從赤道到投影點(diǎn)的子午線弧長，N為卯酉圈半徑，t=tan B，η2=e＇2B，e＇為參考橢球第二偏心率， =L-L0，L0為中央子午線經(jīng)度。

2）基于時(shí)間序列的冗余位置信息處理：移動(dòng)端在請求服務(wù)時(shí)上傳的位置信息由LBS服務(wù)器統(tǒng)一存儲，但部分時(shí)刻移動(dòng)端請求服務(wù)時(shí)上傳位置信息的頻率非常高，且位置信息基本一致，不僅增加了數(shù)據(jù)處理的工作量，還增大了數(shù)據(jù)處理的難度，對位置信息提取的準(zhǔn)確性造成了較大影響，因此在進(jìn)行位置信息提取前必須進(jìn)行冗余數(shù)據(jù)處理。以一定的時(shí)間間隔將待處理數(shù)據(jù)分成若干個(gè)時(shí)間段，對每一時(shí)間段內(nèi)的數(shù)據(jù)進(jìn)行聚類分析，對冗余位置數(shù)據(jù)進(jìn)行過濾。

3）基于聚集度的移動(dòng)端常用位置提?。簩^濾后的移動(dòng)端位置信息數(shù)據(jù)進(jìn)行綜合分析，采用層次化的DBSCAN算法進(jìn)行移動(dòng)端常用位置信息挖掘，提取移動(dòng)端的常用位置信息。

①密度值計(jì)算：掃描整個(gè)數(shù)據(jù)集，進(jìn)行鄰域半徑范圍內(nèi)的位置點(diǎn)聚類，求得任一點(diǎn)的密度值；

②核心對象提?。和ㄟ^密度值對比，提取核心對象；

③數(shù)據(jù)聚類：以核心對象為中心，標(biāo)記在鄰域范圍內(nèi)的所有點(diǎn)，聚類成簇；

④過濾聚類而成的簇，重復(fù)步驟①、②、③，尋找沒有被聚類的核心對象，對核心點(diǎn)進(jìn)行擴(kuò)充直到數(shù)據(jù)集中沒有新的核心對象為止；

⑤常用位置提?。禾崛〕鰜淼暮诵膶ο笤诓煌?、不同時(shí)間段出現(xiàn)的次數(shù)最多、密度最大，可以認(rèn)為是移動(dòng)端的常用位置。

4）常用位置提取結(jié)果分析及相應(yīng)信息賦予：結(jié)合電子地圖興趣點(diǎn)（POI）數(shù)據(jù)、提取的常用位置及周邊一定范圍內(nèi)的所有位置點(diǎn)的時(shí)間屬性信息等進(jìn)行常用位置相關(guān)信息賦予。如果常用位置及其周邊位置點(diǎn)的時(shí)間屬性為非工作時(shí)間段，且該常用位置位于居民小區(qū)及周邊，可以判斷該位置為移動(dòng)端的居住地點(diǎn)；如果位置點(diǎn)的時(shí)間屬性為工作時(shí)間段，且附近為辦公樓等相關(guān)區(qū)域，可以認(rèn)為該位置點(diǎn)為移動(dòng)端用戶的辦公地點(diǎn)；如果位置點(diǎn)的時(shí)間分布無規(guī)律，且經(jīng)常在周末或者節(jié)假日出現(xiàn)，則可以認(rèn)為該位置為常用娛樂休閑場所。

3 試驗(yàn)與結(jié)果分析

本文利用某LBS服務(wù)平臺提供的最近8個(gè)月的隨機(jī)序列GPS數(shù)據(jù)集進(jìn)行移動(dòng)端常用位置挖掘，該數(shù)據(jù)集包含上萬個(gè)用戶的共計(jì)400余萬條位置信息，在地理位置上覆蓋我國中西部大部分城市。

為方便研究和結(jié)果驗(yàn)證，選擇了3個(gè)移動(dòng)端用戶參與常用位置信息挖掘試驗(yàn)，每個(gè)試驗(yàn)用戶的位置信息都在3500條以上。以1 h為時(shí)間間隔進(jìn)行冗余數(shù)據(jù)處理，以30 m為鄰域半徑范圍進(jìn)行常用位置提取，每個(gè)移動(dòng)端用戶均提取了3個(gè)常用位置，提取的常用位置周邊的點(diǎn)數(shù)見表1。

表1 提取的常用位置周邊的點(diǎn)數(shù)Tab.1 Points extracted around common locations

從表1可以看出，提取的3個(gè)移動(dòng)端用戶最常用的3個(gè)位置在8個(gè)月內(nèi)登陸LBS服務(wù)器的次數(shù)均在200次以上；尤其是每個(gè)用戶的位置1，去除冗余數(shù)據(jù)后在同一位置登錄LBS的次數(shù)仍在470次以上，也就是說平均每天都會在該位置登陸LBS服務(wù)器兩次以上。

從時(shí)間屬性上看，在位置1和位置3登錄的基本上為非工作時(shí)段，在位置2登錄的基本上為工作時(shí)段。結(jié)合電子地圖興趣點(diǎn)數(shù)據(jù)和位置點(diǎn)時(shí)間屬性賦予相應(yīng)的語義信息，提取的3個(gè)移動(dòng)端的位置1均為居住地點(diǎn)，位置2均為辦公地點(diǎn)，位置3均為休閑地點(diǎn)。計(jì)算3個(gè)常用位置之間的距離見表2。

表2 提取的常用位置間的距離Tab.2 Distance between the extracted common locations

一般為方便工作和生活，會選擇在工作地點(diǎn)附近居住，到居住或者工作地點(diǎn)就近休閑娛樂。也就是說，居住地點(diǎn)、辦公地點(diǎn)、休閑地點(diǎn)三者之間不會出現(xiàn)都相距很遠(yuǎn)的情況，一般是兩者之間比較近，或者三者之間都比較近。從表2的常用點(diǎn)間距離來看，每個(gè)用戶至少有2個(gè)常用位置之間的距離比較近，說明了提取的位置是合理的。

為進(jìn)一步直觀地分析所提取的位置，將提取的用戶A的3個(gè)常用位置在地圖上進(jìn)行標(biāo)注，如圖2所示。

圖2 移動(dòng)端用戶A常用位置（圖中紅點(diǎn)）標(biāo)注Fig.2 Labeling of common locations(red points)for mobile end user A

圖2（另兩個(gè)用戶的情況類似，標(biāo)圖省略）進(jìn)一步說明了前面的位置及其語義信息（居住地點(diǎn)、辦公地點(diǎn)和休閑地點(diǎn)）提取是正確的。再和參與試驗(yàn)的移動(dòng)端用戶進(jìn)行核實(shí)，結(jié)果與實(shí)際情況基本一致，從而直接驗(yàn)證了本文研究方法的正確性和有效性。

4 結(jié)束語

本文針對LBS移動(dòng)端位置數(shù)據(jù)集的特點(diǎn)，基于DBSCAN算法設(shè)計(jì)了一種層次化的移動(dòng)端常用位置挖掘方法，能夠從LBS服務(wù)平臺記錄的移動(dòng)端位置數(shù)據(jù)集中挖掘出移動(dòng)端用戶的常用位置及其語義信息。該方法在坐標(biāo)投影轉(zhuǎn)換的基礎(chǔ)上基于時(shí)間序列去除冗余數(shù)據(jù)，然后采用基于密度的聚類算法對移動(dòng)端位置信息進(jìn)行聚類，提取移動(dòng)端用戶的常用位置，再利用位置點(diǎn)時(shí)間屬性、興趣點(diǎn)數(shù)據(jù)分析得出常用位置的語義信息。與現(xiàn)有的地點(diǎn)挖掘算法相比，該聚類算法能更好地適應(yīng)移動(dòng)端軌跡數(shù)據(jù)的不確定性，從而準(zhǔn)確、高效地挖掘出移動(dòng)用戶的常用位置及其他有價(jià)值的信息。

利用某LBS服務(wù)平臺提供的最近8個(gè)月的隨機(jī)序列GPS數(shù)據(jù)集進(jìn)行試驗(yàn)，并選擇了3個(gè)移動(dòng)端用戶進(jìn)行驗(yàn)證，通過常用位置間距離分析、在地圖上標(biāo)注直觀判斷等方法，說明挖掘的常用位置以及提取的語義信息正確；經(jīng)用戶驗(yàn)證與實(shí)際情況基本一致，進(jìn)一步證明了上述研究方法的有效性和研究結(jié)果的正確性。