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

孫瑜 王李冬

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

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

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

1研究背景

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.2可視化處理

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

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

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

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

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

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

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

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

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

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