基于密度聚類的簽到軌跡大數據分層預處理研究

文若晴 馬 昂 潘 曉* 楊偉偉

1(石家莊鐵道大學 河北 石家莊 050043)2(河北省高校人文社會科學重點研究基地(石家莊鐵道大學) 河北 石家莊 050043)

0 引 言

受數據獲取手段、數據傳輸、數據存儲等諸多因素的限制，數據“臟”的問題難以根治。數據質量優化的問題已成為分析數據、挖掘知識等研究的瓶頸,為研究人員帶來了新的挑戰。基于位置的社交網絡LBSN(Location based social networks)廣受歡迎，隨之產生的時空-文本等高維數據呈指數式增長[1]。通過簽到數據預處理技術，可以挖掘人類活動規律、興趣愛好和行為特征等信息，研究人員可以據此為用戶做推薦[2]。然而軌跡數據的數據量大、高維異構、多粒度性、不確定性、高冗余等特點[1]，不可避免地對數據分析工作造成了困擾，因此亟待有一套完整的針對軌跡數據的數據預處理流程和方法。我們分析了一組由知名移動社交網站四方(Foursquare)抓取的真實簽到數據集[3-4]。在分析過程中發現，簽到數據除了具有上述特點外，還具有同時簽到和時空跨度大等問題，導致不能直接使用現有的數據預處理流程和方法。

本文對于以上問題，提出了針對簽到數據的基于密度聚類的數據分層預處理框架，能夠使簽到軌跡更好地為后續的挖掘工作所使用。具體來說，首先，對數據集中的屬性值進行篩選，并濾除空數據，將簽到數據依照用戶編號和時間戳進行排列生成用戶的簽到軌跡；其次，通過平均化處理消除了簽到軌跡中存在的同時簽到數據；再次，學習基于熵的時間戳間隔閾值劃分簽到軌跡，解決了簽到軌跡時間跨度大的問題；最后，使用基于密度聚類的方法對簽到軌跡分層處理，解決了空間跨度大的問題。

1 相關工作

在軌跡數據上通用的數據預處理的典型流程包含異常點檢測，軌跡壓縮[5]以及軌跡分段等步驟。

軌跡數據的異常點檢測是為了找出由于傳感器錯誤或用戶特殊行為導致的軌跡中明顯不同的點，已經有許多的國內外學者對異常點檢測技術進行綜述，如Hodgw[6]、Chandola[7]、Aggarwal[8]、Zhang[9]及Gupta[10]等。典型檢測方法有：均值平滑異常點方法，該方法規定一個尺寸為n的滑動窗口，將待測量點的前n-1個點的均值作為該點的估計值。粒子濾波方法[11]，該方法首先初始化粒子xi(j),j=1,2,…,P，使得粒子具有0初始速度并且以高斯分布聚集在初始位置周圍，然后以動態模型P(xi|xi-1)來概率地模擬粒子在一個時間步長內的變化。再根據測量模型計算所有粒子的權重ωi(j)，權重越大則說明該粒子對測量的支持度越大。將這些重要粒子的權重歸一化后，選擇與歸一化后權重成比例的一組粒子重復進行初始化，最終計算這些重要粒子的權重和，得到被修正后的軌跡。基于啟發式的異常點檢測方法[12]，根據鄰近軌跡點間的距離或根據軌跡點的行進速度，判斷該距離或行進速度是否滿足距離閾值d或速度閾值v，找到軌跡中的異常點并刪除。異常點檢測方法也可以分為對靜態軌跡的檢測和對動態軌跡的檢測。對靜態軌跡的檢測可以對軌跡進行特征建模[13]，從而將軌跡片段與特征庫進行匹配，比較判決閾值。對動態軌跡的檢測通常是基于歷史軌跡挖掘所有的頻繁模式，從而據此識別異常軌跡，Lei等[14]提出的MT-MAD方法可用于海量航海船只軌跡數據的異常檢測，Zhu等[15]提出的TPRO方法可以應用于出租車軌跡數據，從而檢測是否有司機欺詐繞路的異常軌跡。本文采用一種基于統計的四分位異常點檢測方法處理簽到數據。

軌跡壓縮的目的是節省不必要的存儲空間、通信、計算開銷。現有的兩種軌跡壓縮策略為離線壓縮和在線壓縮。離線壓縮(批量模式)是在軌跡完全生成后，減小軌跡大小的方法。該方法通過丟棄具有可忽略誤差的點得到與原始軌跡近似的軌跡，這與計算機圖形學和制圖學研究領域的線簡化問題相似[16]。利用垂直的歐氏距離，以首尾軌跡點作為壓縮點，通過其連線與其他各個軌跡點的垂線距離，找到誤差最大的軌跡點作為壓縮點，并使用新的壓縮點集合遞歸上述方法，直到找到的最大誤差值小于指定的閾值則停止遞歸[17]。在線壓縮，即在對象移動時實時進行軌跡壓縮[18]。不同于離線壓縮方法，在線壓縮方法不需要得到整條軌跡，而是在軌跡増長的過程中，計算垂線距離，得到最大誤差值，當軌跡增長到出現某個最大誤差值超過指定閾值時，將尾軌跡點作為壓縮點，并將其作為新的首壓縮點，繼續尋找新的壓縮點，最終在軌跡完全生成后得到以所有壓縮點形成的壓縮軌跡。

軌跡分段的提出是由于整體軌跡的計算復雜性高，軌跡分段后能減小計算量，并且可以挖掘出更豐富的知識。現有的軌跡分段方法大致可分為三種：基于時間間隔的軌跡分段[19]，該方法根據給定的時間間隔經驗閾值劃分軌跡；基于軌跡形狀的軌跡分段，該方法通過軌跡中的轉向點來劃分軌跡，或使用線條簡化算法(如Douglas-Peucker算法)確定保持軌跡形狀的關鍵點；基于語義的軌跡劃分，該方法考慮數據的應用場景[20]或者不同的交通模式[21]，根據軌跡點的速度和加速度判斷移動物體的運動方式(步行/騎行/公交/駕車……)，從而據此劃分軌跡，旅游者的經驗和POI(Point Of Interest)停留點的學習也可以作為語義的一種，從而劃分原始軌跡[22-23]。本文采用基于時間間隔的軌跡分段方法，其中軌跡點間的時間間隔的劃分閾值通過基于熵的學習獲得。

2 簽到軌跡的生成

在本節中，我們對Foursquare數據集的格式與內容，以及簽到軌跡的生成方法進行介紹。

2.1 Foursquare數據集

Foursquare網站是目前流行的LBSN之一。本文使用的實驗數據集是微軟研究院發布的從Foursquare網站上抓取的真實簽到數據[3-4]。該數據集分別包括洛杉磯和紐約用戶的簽到數據，統計信息如表1所示。

表1 Foursquare數據集的統計信息

數據集中共包含5個文件:

(1) Venue(地點) Venue文件中描述的是用戶簽到地點的相關信息，文件中包括地點編號、名稱、創建時間、經緯度和地點類別編號，我們在生成簽到軌跡時使用了該文件中“地點編號”、“經度”和“緯度”，形式化地表示為關系venue(v_id,lat,lon)。

(2) Categories(類別) Categories文件是地點所屬類別的信息，包括類別編號和類別名稱。我們使用各個類別名稱，作為簽到位置的語義，形式化地表示為關系categories(c_id,c_name)。

(3) Tips Tips文件中記錄的是每個用戶的簽到數據。Tips文件中的一條記錄無時序地包含一個用戶的所有簽到數據，其中每一條簽到數據包含簽到時間、地點編號、地點類別編號等信息。其中一條簽到數據形式化地表示為關系tips(u_id,v_id,createdTime,c_id0,c_id1,…,c_idn)。

(4) User(用戶)和Friendship(朋友) 用戶文件包含用戶編號、名字、姓氏、頭像、性別和籍貫。朋友關系文件中存儲了用戶間的好友關系，包含u_id1和u_id2兩列。本文對簽到軌跡的預處理不涉及這兩個文件。

2.2 簽到數據特點

通過對上述數據集分析發現，簽到數據具備數據冗余、數據缺失、同時簽到、時空跨度大等特點。

(1) 數據冗余 數據冗余是指數據重復存儲的現象。例如，Foursquare數據集中的Venue文件記錄了洛杉磯和紐約用戶訪問過的地點編號、名稱、經緯度、地點類別等信息。Tips文件是用戶的簽到數據文件，包含用戶編號、地點編號、簽到文本、簽到時間與地點類別等信息。很明顯，兩個文件都重復存儲了地點類別信息，可能會導致數據的不一致。

(2) 數據缺失 數據集中存在值缺失的現象。例如，Venue文件中經度和緯度(longitude,latitude)兩列，如圖1所示，缺失值占0.87%。Users數據文件中的姓名、性別和家鄉等列缺失值占1.94%。

圖1 Venue文件中地點編號及其對應經緯度

(3) 同時簽到 簽到服務允許用戶同時在多個地點連續簽到。因此，存在用戶在相同時間在多個地點簽到的現象。如圖2所示，u_id是用戶編號，時間戳(createdTime)是從1970年1月1日00:00:00開始以秒計算的時間偏移量。圖2中共有5條簽到記錄，這5條記錄中地點編號(v_id)是不同的，但是后三條簽到數據的時間戳是相同的。用戶的實際位置可能僅是其中的某一個簽到地點，或是與簽到地點臨近的某一個點。

圖2 用戶169961的同時簽到數據

(4) 時空跨度大 簽到數據跨度大主要表現在時間和空間兩個方面。時間方面，數據集中包含了2008年5月6日05:47:27至2011年7月12日06:07:30的用戶簽到記錄。我們將同一用戶相鄰簽到數據的時間戳跨度分布進行統計，見表2(LA:洛杉磯NYC:紐約)。可以發現將近3/4的相鄰簽到數據時間跨度在半個月內，剩余1/4的相鄰簽到數據時間跨度在半個月至兩年半不等。

表2 相鄰簽到數據時間戳跨度分布表

空間方面，數據集中的簽到數據幾乎覆蓋全球，在以這些簽到數據中最小和最大的經緯度所形成的矩形范圍內，對角跨度約為398.20度，約4.4萬公里。而根據不同用戶形成的簽到軌跡的對角跨度分布不均，統計簽到軌跡空間跨度分布見表3。圖3中記錄了某用戶的27條簽到數據，圖中左側的簽到數據共3條與其余的簽到數據距離較遠。放大圖3中右側的簽到數據到圖4，其中有24條簽到數據，可以看到簽到軌跡中被圈出來的1條簽到數據與其余23條簽到數據不在同一個城市而且相距很遠。

表3 簽到軌跡空間跨度分布表

圖3 用戶100140的簽到軌跡(共27條簽到數據)

圖4 用戶100140的部分簽到軌跡(共24條簽到數據)

2.3 簽到軌跡

將關系categories、venue和tips，通過v_id連接得到簽到數據的經緯度信息，通過c_id連接得到簽到數據的文本信息以便于生成簽到軌跡后計算軌跡的文本相似性，可獲得用戶的一條簽到數據，定義如下。

定義1簽到數據。一條簽到數據p=(u_id,createdTime,lon,lat,c_name0,c_name1,…,c_namen)，其中，根據表1統計信息，n=0,1,…,18。

利用用戶簽到數據生成用戶簽到軌跡，即，將同一用戶的簽到數據按時間戳排序形成一個序列，以用戶編號命名該用戶的簽到軌跡，定義如下。

定義2簽到軌跡。一條簽到軌跡Tu_id=(u_id,loc_list,word_list),其中loc_list={(p1.lon,p1.lat),(p2.lon,p2.lat),…,(pm.lon,pm.lat)}是同一個用戶的所有簽到數據按時間順序排列的地理坐標對序列，且pi.createdTime-pi-1.createdTime≥0。簽到軌跡的word_list是所有簽到位置的類別名稱的并集，并以空格隔開形成的一個字符串。

3 簽到數據預處理

3.1 簽到數據預處理總流程

簽到數據的預處理主要包括：數據清理與數據轉換、簽到軌跡劃分、簽到軌跡分層，其流程見算法1。

算法1簽到數據預處理流程

輸入：原始簽到數據

輸出：分層的簽到軌跡集

1 選擇有用屬性，減少冗余

2 選擇完整信息，濾除含有缺失值的數據

3 生成簽到軌跡

4 FOR every簽到軌跡{

5 平均化同時簽到點

6 檢測并刪除每條軌跡的離群點

7 }END FOR

8 學習時間戳閾值，劃分簽到軌跡

9 計算簽到軌跡間的相似性，聚類并分層簽到軌跡

對于簽到數據因被存儲在多個文件所造成的數據冗余以及數據缺失的問題，首先進行初步數據清理，然后將簽到數據轉換為簽到軌跡，并對每一條軌跡中同時簽到數據和離群簽到數據進行清理。由于簽到軌跡數據時間、空間跨度大的特性，還要對簽到軌跡進行劃分和分層，采用基于熵的方法學習用于劃分簽到軌跡的時間間隔閾值，分層采用基于密度的DBSCAN聚類算法聚類簽到軌跡。

(1) 選擇有用屬性和完整信息 Foursquare數據集中存在數據冗余和缺失。對于冗余，選擇各個文件中的有用維度生成簽到軌跡，避免同一信息多處存儲；對于缺失值，選擇使用包含完整信息的數據。

(2) 生成簽到軌跡 將Tips文件中各用戶的簽到數據按簽到時間排序，并與venue連接得到簽到數據的經緯度信息、與categories連接得到簽到數據的文本信息，以方便后續計算簽到軌跡的時空和文本相似性。

(3) 平均化同時簽到 數據中存在很多如圖2所示的同時簽到數據。具有多條同時簽到數據的用戶可能只在其中一個地點或者都不是。為了使簽到軌跡更合理，本文將這些相同時間戳的簽到數據進行平均化處理。

具體來講，對于每一個用戶的簽到軌跡，若用戶的n個簽到數據的時間戳相同，則將這n個簽到數據的經度和緯度分別取均值，以得到的新經緯度作為該時間戳的簽到地點。對于n個簽到數據的文本，將其去重后以空格分隔合為一個字符串，作為該時間戳的文本。例如用戶169961在同一時刻對6個地點進行簽到，基本信息如表4所示，各個地點的經緯度都不相同。計算得到經度和緯度的平均值分別為-79.028 9和36.146 3，最終得到該用戶在這一時刻的簽到數據如表5所示。

表4 用戶169961的部分簽到數據

表5 用戶169961的部分簽到數據平均化結果

(4) 檢測并處理簽到軌跡離群點 根據統計知識，一個序列上如果有值在序列上所有值的上下四分位的1.5倍四分位距以外的范圍，這樣的值是離群的。將用戶簽到軌跡可視化后，我們發現用戶的軌跡存在如圖3、圖4的情況。對于這樣的簽到軌跡我們提出一種基于統計的四分位檢測離群簽到數據的方法處理用戶的簽到軌跡，算法基本思想是將每條待處理簽到軌跡的經度和緯度分別排序并計算分別的四分位數(Q1,Q2,Q3)、四分位距(IQR=Q3-Q1)和內限(Q3+1.5×IQR,Q1-1.5×IQR)，并分別找到并標注經度和緯度上的離群值，最后將簽到軌跡上被標注為離群的簽到數據刪除。

(5) 劃分簽到軌跡 簽到軌跡的相鄰簽到數據中約1/4的時間戳跨度分布在半個月至兩年半不等，這使得在原始簽到軌跡上直接計算的結果沒有意義。基于時間閾值的軌跡劃分將一條軌跡劃分為了幾條軌跡使相鄰簽到數據的時間戳跨度在一定合理范圍內。我們通過基于熵的方法學習適用于劃分簽到軌跡的時間間隔閾值，從而劃分簽到軌跡，具體方法見3.2節。

(6) 分層簽到軌跡 簽到軌跡分層用以解決簽到軌跡空間跨度大的問題。通過計算簽到軌跡間的相似性，對簽到軌跡根據軌跡的時空文本相似性進行聚類，并通過調整聚類參數，得到不同層次粒度的簽到軌跡集合。

3.2 基于熵的簽到軌跡劃分

軌跡劃分中最常用的方法是按時間閾值將軌跡分段，但該方法中時間間隔閾值難以確定，這也是簽到數據預處理流程中的一個難點。我們使用Cui[24]提出的基于熵的軌跡時間閾值學習方法，確定一個較客觀的軌跡劃分閾值，具體方法如下。

(1)

設t是時間間隔閾值，則小于t的間隔分布的熵的定義如下：

(2)

大于t的時間間隔分布的熵的定義如下：

(3)

簽到軌跡劃分的目標是在多個t中找到使得熵E1和熵E2的和最大的閾值θ，公式如下，當兩個連續的簽到軌跡時間間隔大于閾值θ時，則將劃分該簽到軌跡為兩條簽到軌跡。

(4)

4 基于密度聚類的簽到軌跡分層

在本節中，將對簽到軌跡的分層處理做詳細說明，包括對用戶簽到軌跡進行相似性定義和基于時空文本相似性的聚類方法。

4.1 簽到軌跡的時空-文本相似性

簽到軌跡相似性包含三個方面：空間、時序和關鍵字(即類別名稱)。離散弗雷歇距離是目前被廣泛用于計算不同多邊形軌跡曲線間距離的方法，它動態地考慮了軌跡點的時序和空間相似性，因此本文選用離散弗雷歇距離計算用戶簽到軌跡間的時空距離。同時，在關鍵字相似度方面，Jaccard系數是基于字符串語義相似性度量中常用的方法之一，其對于兩個用于計算相似性的向量的維度沒有限制。因此，本文結合二者優點提出了簽到軌跡的時空文本相似性度量方法。

定義3離散弗雷歇距離。設任兩條簽到軌跡T1、T2，T1有m個簽到點，T2有n個簽到點生成。T1和T2的離散弗雷歇距離為：

(5)

當m=0,n=0時，DFD計算方法如下：

DFD(T1.p0,T2.p0)=Dist(T1.p0,T2.p0)

(6)

當m>0,n=0時，DFD計算如下：

(7)

當m=0,n>0時，DFD計算如下：

(8)

式中：Dist(pi,pj)是任意兩個簽到數據pi與pj間的歐氏距離。

下面用一個簡單的例子解釋離散弗雷歇距離的定義。現有兩條簽到軌跡T1={(0,0),(1,0),(2,-10),(3,0),(4,0),(5,0)}，T2={(0,0),(1,0),(2,0),(3,0)}。軌跡T1和T2的DFD值根據定義3可以得到一個如圖5所示的二維矩陣，簽到軌跡T1和T2的離散弗雷歇距離為10。若兩條簽到軌跡的離散弗雷歇距離越大則說明它們在時空上距離越遠。

圖5 簽到軌跡T1和T2的DFD二維矩陣

定義4基于Jaccard系數的文本相似性。簽到軌跡T1和T2的類別集合的文本相似性定義如下：

(9)

可見SimJCD∈[0,1]，越接近于1表示兩條軌跡的文本方面越相似。

定義5簽到軌跡相似性。對于給定的兩條簽到軌跡T1、T2，簽到軌跡相似性形式化的表示為：

SOT(T1,T2)=α×SimDFD+(1-α)×SimJCD

(10)

(11)

式中：SimDFD是基于離散弗雷歇距離的時空相似性，SimDFD∈[0,1]，越趨近于1表示兩條軌跡的時空方面越相似；參數α∈[0,1]，為軌跡的時空相似性的權重。SOT∈[0,1]，越趨近于1，則兩條簽到軌跡在時空-文本方面越相似。在同一個用戶簽到軌跡集D內，不同的α，可以得到不同的SOT值和軌跡相似性矩陣M。

4.2 基于DBSCAN的簽到軌跡分層

4.1中已經得到簽到軌跡間的相似性，現在要據此對簽到軌跡進行聚類，從而得到分層的簽到軌跡簇。算法2的輸入包括簽到軌跡集D，任兩條用戶簽到軌跡的軌跡相似性矩陣M，最小簇軌跡數閾值MinTrs和聚簇半徑Eps。

如算法2所示，初始狀態下，任選一個未被訪問的簽到軌跡T，找出與T間的簽到軌跡相似性SOT大于等于閾值Eps的所有簽到軌跡，記為N。如果N中簽到軌跡數量小于閾值MinTrs,則T被標記作為噪聲舍棄(第2～6行)。如果N中簽到軌跡數量大于等于閾值MinTrs，則T與其N中的簽到軌跡形成一個簇c,并且T被標記為已訪問(第7～12行)。以相同的方法處理該簇內所有未被標記為已訪問的簽到軌跡，從而對簇進行擴展(第13～16行)。如果簇充分地被擴展，即簇內的所有簽到軌跡被標記為已訪問，則用同樣的算法去處理未被訪問的簽到軌跡。

算法2簽到軌跡的DBSCAN聚類

輸入：D,M,MinTrs,Eps

輸出：簇集合C

1 初始化簇集合C=null

2 FOR every沒有被訪問的軌跡T in D{

3 標記T為已訪問

4 N={T′|SOT(T,T′)≥Eps}

5 IF(Size(N)

6 將軌跡T標記為噪聲

7 } ELSE {

8 新建一個簇c加入到簇集合C中

9 擴展以T為核心對象的簇c{

10 將T加入到c中

11 FOR every T′ in N{

12 標記T′為已訪問

13 N′={T″|SOT(T′,T″)≥Eps}

14 IF(Size(N′)≥MinTrs){

15 N=N+N′

16 }

17 IF T′不是任何簇的成員{

18 將T′加入到簇c中

19 }

20 }ENDFOR

21 }

22 }

23 }ENDFOR

在一個給定的α下，通過對聚類參數MinTrs或Eps的調整可以改變簽到軌跡的層次粒度。逐漸減小參數Eps，形成的簇的層次范圍將逐漸擴大(由街區到城市到國家等)。若Eps較小,則有更多軌跡被認為是相似的，使得聚簇的結果可能是一個洲上的所有簽到軌跡，層次粒度很大。反之，高相似性要求使得很少有簽到軌跡被認為相似，甚至難以成簇。參數MinTrs的變化往往影響同一個層次內的簽到軌跡簇數，但隨著MinTrs的增大，簇的擴展效果被放大，使得簇的層次粒度提升。當尋找城市層次的相似簽到軌跡時，小的MinTrs會使得到的結果出現很多個簇，且一個簇中的簽到軌跡很少，反之由于沒有足夠多的簽到軌跡滿足Eps,將會無法成簇。Eps和MinTrs都對分層效果有一定的影響，好的分層結果需要通過對兩個參數進行多次調節。

5 實驗結果與分析

實驗運行于Inter(R) Core(TM) i7-7500U @ 2.7 GHz處理器、12 GB內存的Windows10計算機上。實驗程序采用Java語言進行編寫。由于基于時空-文本相似性的密度聚類的簽到軌跡分層方法主要完成了簽到軌跡中離群簽到數據的去除以及簽到軌跡的分層，所以實驗中對離群簽到數據和簽到軌跡分層分別進行了評價。

5.1 離群點檢測

在簽到數據預處理流程中，要進行兩次的離群點檢測：一次是在生成簽到軌跡后，對每一條簽到軌跡進行基于四分位的離群點檢測；另一次是在簽到軌跡分層階段，使用DBSCAN算法聚類時，在不同的參數下得到的噪聲軌跡。下式計算了簽到軌跡集中的離群率和分層處理過程的簽到軌跡離群率。

(12)

其中，一個簽到數據集生成的簽到軌跡是固定的，對于每條簽到軌跡檢測出的基于四分位的離群點也是不變的，因此針對一個簽到數據集，其基于四分位離群率是固定的。圖6展示了1 000條簽到軌跡的原始分布和經過基于四分位的離群簽到數據檢測過濾了離群簽到數據的簽到軌跡分布，不同深淺顏色點表示不同的簽到軌跡，整體可見經過處理的簽到軌跡集中少了很多孤立的點，該部分的離群率(即根據式(12)的前半部分計算所得)為13.76%，如圖7網狀陰影部分。分層階段中DBSCAN算法的參數變化時，得到的噪聲簽到軌跡數量也相應變化，該部分的離群率如圖7斜線陰影部分，一般情況下，滿足參數條件的簽到軌跡數并不多，因此由分層處理過程得到的離群率會較高。

(a) 未處理離群點的簽到軌跡

(b) 去除離群點后的簽到軌跡圖6 1 000條簽到軌跡分布圖

(a) α=0.1

(b) α=0.5

(c) α=0.9圖7 簽到軌跡數據預處理的離群率

5.2 軌跡分層

該部分對三個參數α,MinTrs和Eps進行調節，我們研究了不同參數在時空-文本的影響下對軌跡分層結果所帶來的變化，以下式計算簽到軌跡分層的平均跨度，從空間方面來評價分層效果。

(13)

圖8展示了不同參數(簽到軌跡的時空相似性權重α,最小簇軌跡數閾值MinTrs和聚簇半徑Eps)對簽到軌跡的平均空間跨度的影響，平均跨度越大，所劃分的層次就越高(如國家)，平均跨度越小，則所劃分的層次越低(如城市)。如圖8(a)所示,時空和文本的權重各占一半，聚簇的最小成簇軌跡數為3條，隨著聚簇半徑Eps逐漸減小，同一個簇內的簽到軌跡在時空-文本上越來越不相似，使得該條件下的平均空間跨度增大。但實際上當Eps分別為0.6和0.4時，所得到的簇中包含了一條本身空間跨度就十分大的簽到軌跡，使得在這兩個參數下的簇個數n只有一個，其平均空間跨度被高度影響。如圖8(b)所示，在時空和文本的權重各占一半，聚簇半徑Eps為0.5時，隨著最小簇軌跡數的增多，聚簇的最小范圍變大，簇的個數減少，使得平均空間跨度有增大的趨勢。如圖8(c)所示，當時空相似性占簽到軌跡相似性比重提高時，得到的簽到軌跡間的相似性不同，因此計算得出的平均空間跨度沒有相關性。

(a) α=0.5，MinTrs=3

(b) α=0.5，Eps=0.5

(c) MinTrs=3，Eps=0.5圖8 不同參數對簽到軌跡的平均空間跨度的影響

6 結 語

隨著定位技術的精準與社交軟件的普及，人們更加頻繁地在網絡上留下自己行走過或者停留過的地點痕跡，并賦予文本描述。然而，海量數據的質量問題是所有研究工作的重要前提。本文針對Foursquare簽到數據集提出了一套數據預處理流程和方法，對簽到軌跡進行基于四分位的離群簽到數據檢測，通過學習時間間隔閾值對簽到軌跡劃分解決了簽到軌跡時間跨度大的問題，通過基于簽到軌跡時空文本相似性的密度聚類方法對簽到軌跡進行了分層，解決了空間跨度大的問題。通過對聚類參數的調整可以將簽到軌跡集分層到洲、國家甚至城市，為將來更富有意義的簽到數據挖掘工作提供了便利。