孫瑜 王李冬

摘要：近年來，隨著移動互聯(lián)網(wǎng)應用的迅猛發(fā)展，用戶可以很方便地獲取個人位置信息，使用各種基于位置的服務（Locationbased Services，LBS），將自己的移動過程以軌跡的形式進行記錄。如何對產(chǎn)生的軌跡數(shù)據(jù)進行挖掘，已成為數(shù)據(jù)挖掘領域的一個研究熱點。在完成對大量的軌跡數(shù)據(jù)的存儲與處理之后，用戶軌跡的可視化對于用戶軌跡的分析無疑能夠提供一個直觀的研究環(huán)境，但是單純的可視化和軌跡交換并未充分發(fā)掘出軌跡中隱藏的知識。基于此，該文從用戶軌跡數(shù)據(jù)出發(fā)，進行用戶軌跡數(shù)據(jù)的挖掘分析并通過JAVA技術實現(xiàn)可視化。此外，該文通過計算兩個用戶之間的相似度為用戶推薦潛在的朋友，完成個性化朋友推薦。

關鍵詞：軌跡可視化;軌跡挖掘;基于位置的服務

中圖分類號：TP391 文獻標識碼：A

1研究背景

隨著移動互聯(lián)網(wǎng)的發(fā)展，記錄移動目標軌跡數(shù)據(jù)成為極其簡單的工作，大多數(shù)地理信息服務相關的公司和組織已經(jīng)積累了數(shù)量龐大GPS軌跡數(shù)據(jù)，但其大多數(shù)的數(shù)據(jù)都是簡單的采集，對于獲取的信息也沒有進行進一步處理，這些原始數(shù)據(jù)龐大且難以被理解。在大數(shù)據(jù)時代，如何挖掘海量信息，為用戶進行個性化的推薦，無論是對于學術研究還是商業(yè)應用都極具價值。

過去的幾年里，國內(nèi)的一些服務應用仍停留在根據(jù)用戶當前的GPS定點，推薦用戶周邊距離較近的商鋪等這些簡單的基于位置服務的應用，而沒有進一步深度挖掘用戶之前軌跡信息來為用戶提供更便利更智能的服務。目前國內(nèi)的軌跡挖掘研究也處于借鑒一些國外研究資料進行理論研究的階段，而局限于國內(nèi)的整體的軌跡數(shù)據(jù)信息環(huán)境。

國外的數(shù)據(jù)信息環(huán)境從規(guī)范性和共享性要優(yōu)于國內(nèi)，以Facebook、Twitter、Google+、MySpace等為代表的社交網(wǎng)絡服務在全球已累計超過20億的用戶，這些網(wǎng)站的位置服務功能每天都會產(chǎn)生數(shù)以億計的位置數(shù)據(jù)。這些位置數(shù)據(jù)包括時間、位置、速度等基礎信息，反映了用戶真實的移動軌跡。同樣的，國外的軌跡挖掘和位置服務的研究也先于國內(nèi)。過去幾年內(nèi)，已經(jīng)形成了一批以GPS軌跡為代表的個人地理位置信息的挖掘研究，類似于識別在每個位置的用戶特定活動，分析各位置之間的關系以及預測旅行者在這些位置之間的活動等。

Giannotti等人較早地提出了軌跡挖掘問題，Jeung等人利用航跡數(shù)據(jù)庫建立了基于密度的數(shù)據(jù)表示方法，而Lee等人提出了一種TraClass方法，該方法能從軌跡數(shù)據(jù)中通過劃分軌跡生成特征層級，并搜索了基于區(qū)域和基于軌跡的聚類方法。文獻基于一個統(tǒng)一的框架，提出了地點位置的坐標提取、用戶停留點檢測和用戶頻繁行為模式挖掘方法。文獻利用采集自LBSN的數(shù)據(jù)，建立地點和用戶偏好模型，根據(jù)用戶需求，在時空約束下生成旅游路線，形成旅游包推薦給用戶。文獻提取景點的開放時間、門票與GPS坐標等及旅游網(wǎng)站上對于景點的評價信息等，針對新手游客在陌生城市如何規(guī)劃旅游路線的問題，研究基于景點評分機制以及用戶多約束的旅游路線推薦問題。文獻以谷歌地球軟件為平臺，通過采集公眾上傳的VGI照片數(shù)據(jù)，在數(shù)據(jù)預處理的基礎上，運用核密度估計方法繪制城市熱點空間分布圖，研究市民對城市空間的偏好。文獻從移動空間信息服務關鍵技術探討基于路線推薦服務的研究方法，設計并編程實現(xiàn)了一個基于特定景區(qū)景點的滿足用戶時間需求的旅游路線推薦服務軟件。

本文先實現(xiàn)對數(shù)據(jù)軌跡的處理與優(yōu)化，之后再是完成基于地點位置的判定，實現(xiàn)數(shù)據(jù)點與地點直接的分析;最后，是在以上研究基礎之上對用戶軌跡的性質(zhì)進行分析，確定用戶的習慣與愛好，并且通過計算得到兩個用戶之間的相似度，為用戶推薦潛在的朋友，完成個性化朋友推薦。

2系統(tǒng)設計與實現(xiàn)

2.1用戶軌跡可視化與挖掘系統(tǒng)概述

隨著移動互聯(lián)網(wǎng)時代的到來，目標移動軌跡的數(shù)據(jù)獲取相對較簡單。就軌跡數(shù)據(jù)而言，經(jīng)度Longitude，緯度Latitude，時間戳Time都是其應具有的基本屬性，本文所提出的系統(tǒng)也是基于這個3個屬性。同時對于經(jīng)緯度，不難發(fā)現(xiàn)這個單位的定位相對較大。用戶軌跡的兩個地點的經(jīng)緯度之差理論上相對較小，這并不方便數(shù)據(jù)的處理與分析，所以我們對經(jīng)緯度數(shù)據(jù)Longitude和Latitude進行了相關的處理與優(yōu)化得到了X與Y。為了數(shù)據(jù)進行更好的存儲與管理，我們將軌跡數(shù)據(jù)用SQL2008數(shù)據(jù)庫進行存儲。

在系統(tǒng)的功能設計上，本文提出的系統(tǒng)實現(xiàn)了：

1）程序能夠從數(shù)據(jù)庫里讀取軌跡數(shù)據(jù)，將其可視化地顯示出來，不同用戶的軌跡數(shù)據(jù)應當能夠使用不同的顏色進行區(qū)分，如圖1。

2）同時能夠?qū)壽E數(shù)據(jù)進行一定程度的優(yōu)化，例如：用戶在一家小餐廳吃飯，他在餐廳內(nèi)點餐和進餐之間是有目標位置的移動，表現(xiàn)于幾個貼近或是部分重疊的點。如圖2，將這些多個點合并為一個點能夠既能保留數(shù)據(jù)的信息含義，抓住了用戶行為的重點，同時也減輕了數(shù)據(jù)量。

3）能夠?qū)壽E數(shù)據(jù)進行信息篩選，例如：挑選用戶停留長的點，過濾掉時間間隔短的點來直接查看軌跡的重點信息，如圖3所示。

4）能夠從數(shù)據(jù)庫里獲取地點區(qū)域點的信息，來判斷軌跡中的點是否進入了一些區(qū)域，即能夠分析用戶A的軌跡1去了圖書館和操場，用戶B的軌跡3去了水果店等。同時區(qū)域的圖形應能夠適應多種情況，包括一些特殊的凹多邊形，即一座學校的平面區(qū)域是一個復雜的圖形，不能簡單地當作一個圓形或矩形進行處理。以此來判定用戶的軌跡經(jīng)過以及停留了哪些地點，用戶停留了多長時間。

5）對用戶軌跡的性質(zhì)進行分析，確定用戶的習慣與愛好，并且可以通過計算得到兩個用戶之間的習慣興趣相似度，來為用戶推薦潛在的朋友，完成個性化朋友推薦。以上都還是用戶與地點的計算，興趣相似度的計算應該涉及用戶與興趣類型的計算，比如用戶甲常去A圖書館，用戶乙常去B圖書館，系統(tǒng)不應認為A圖書館不等同B圖書館就判定用戶甲和用戶乙之間沒有相似性，應清楚地分析到A圖書館和B圖書館的地點存在著相同的類型關聯(lián)，這會對甲和乙的相似度計算產(chǎn)生影響。

同時本系統(tǒng)對習慣興趣程度進行分析計算，就比如用戶甲10條軌跡中有8條軌跡都經(jīng)過了圖書館，每次的停留時間都超過了60分鐘，而用戶乙10條軌跡中只有1條軌跡經(jīng)過了圖書館，且停留時間僅為20分鐘，那么用戶甲和用戶乙在對“愛去圖書館”的程度上應該是有完全不同的定義。

2.2系統(tǒng)詳細設計方案與思路

2.2.1數(shù)據(jù)庫設計

以上為本文所提出的系統(tǒng)的數(shù)據(jù)庫設計，同時我們將數(shù)據(jù)庫相關的方法統(tǒng)一寫在了DataBaseAbout.java文件中，方便管理與調(diào)用。

2.2.2可視化處理

本系統(tǒng)使用了JAVA中的CUI來進行可視化設計，主要思想是一個控制窗口加上一個顯示窗口來完成系統(tǒng)的操作與顯示。數(shù)據(jù)的存儲思路則是先以num0數(shù)據(jù)表示每條線路點的個數(shù)，u[]數(shù)組表示每條軌跡線路所屬的用戶，count表示有多少條軌跡線路，再用二維數(shù)組x[]、y[][]、t[]表示每條線路的每個數(shù)據(jù)點的x、y、t屬性。

系統(tǒng)用public void paint（Graphics g）來實現(xiàn)圖形的繪畫，即通過g.setColor方法完成色彩設置，g.fillOval方法畫圓，g.draw-Line方法連線。同時，為了更加直觀地顯示，本系統(tǒng)添加了一個相應的地圖作為顯示背景，即使用InputStream stream=newFileInputStream（”bg.bmp”）; uuage image=ImagelO.read（stream）;注bg.bmp放在同項目文件夾中，否則請使用絕對地址。

2.2.3近距離點合并與停留時間篩選

近距離點合并的大致設計為在控制窗口點擊按鈕之后，輸入距離間隔閾值d，并傳遞其他相應參數(shù)調(diào)用Join.java中的f方法。在f方法中，將對每條線路的每個數(shù)據(jù)點進行與相鄰數(shù)據(jù)點的比較，若兩個數(shù)據(jù)點之間距離小于距離間隔閾值d，則兩點合并，時間戳取較早的數(shù)據(jù)點的時間。

停留時間篩選的大致原理同近距離點合并相同。

2.2.4數(shù)據(jù)點與地點的判定

用戶的某條軌跡是否進入某個地點區(qū)域，則應判斷該軌跡的每個數(shù)據(jù)點是否在這塊區(qū)域的多邊形圖形內(nèi)。本系統(tǒng)將點與多邊形的判斷寫在了PolygonCalculation.java中的function方法中，在通過循環(huán)傳遞不同的參數(shù)調(diào)用該方法，完成判斷。大致原理為：

判斷某點與多邊形位置關系，需要區(qū)分兩類多邊形：1）凸多邊形;2）凹多邊形。

為了區(qū)分兩類多邊形，需要計算給定點與多邊形各頂點連接形成邊各個夾角的銳角和，若銳角和小于2*Math.PI弧度，則該多變形為凸多邊形，否則為凹多邊形。（由于圓周率強制取float后的精度誤差，故弧度和total判斷時補足誤差0.000001，以減小誤差，（total +0.000001）< （float）《n-2）*Math.PI》。

根據(jù)給定點與兩類多邊形位置關系，其性質(zhì)不同：1）凸多邊形：點到多邊形各個定點形成的鄰邊的夾角之和為360度，則點在凸多邊形內(nèi);小于360度則在凸多邊形外。2）凹多邊形：若給定點為（a，b），做射線x=a（y>b），計算與多邊形交點個數(shù)，若交點個數(shù)為奇數(shù)個則在凹多邊形內(nèi)，否則在凹多邊形外。（注：點在多邊形邊線上情況不做討論。）