用戶軌跡挖掘與可視化系統(tǒng)的研究與設(shè)計(jì)

孫瑜 王李冬

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

關(guān)鍵詞：軌跡可視化;軌跡挖掘;基于位置的服務(wù)

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A

1研究背景

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

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

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

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

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

2系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

2.2系統(tǒng)詳細(xì)設(shè)計(jì)方案與思路

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

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

2.2.2可視化處理

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

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

2.2.3近距離點(diǎn)合并與停留時間篩選

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

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

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

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

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

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

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