一種基於歷史軌跡數據挖掘的位置預測系統及方法
2023-10-08 18:12:59 2
專利名稱：一種基於歷史軌跡數據挖掘的位置預測系統及方法
技術領域：
本發明涉及數據挖掘技術領域，具體涉及一種基於歷史軌跡數據挖掘的位置預測系統及方法。
背景技術：
位置預測技術可為基於位置的服務(LBS，location-based service)提供支持，如智能導航、廣告投放、服務預約、地點提醒等。目前對用戶的位置預測主要集中在行動網路或無線網絡環境下，對用戶在環境中各類無線電信標(如移動基站、WiFi節點、RFID節點等)範圍內的運動情況進行分析，獲取用戶運動規律，進而進行位置預測。對於基於移動基站的位置預測技術，移動基站定位精度較低，難以滿足需要精確位置的位置服務要求；對於基於無線節點的位置預測技術，需要在環境中部署大量無線節點，且無線節點的位置要麼是未知的，要麼需要進行大量的位置標註工作。目前對用戶的短期精確位置的推算和預測主要基於GPS+航位推算的組合。然而此類方法通常用於GPS失效時的位置推算，只能對用戶短時間內的位置進行預測，GPS失效時間一旦過長，則預測效率大大降低，且該方法需要高精度的陀螺儀、加速度傳感器、角速度傳感器等硬體設備，成本較高，難以在手機等行動裝置上推廣。
發明內容
本發明為克服上述的不足之處，目的在於提供一種基於歷史軌跡數據挖掘的位置預測系統，該系統可運行在行動裝置上，為基於位置服務提供用戶的目的地和未來路徑信息，有效滿足各類基於位置服務(如基於位置的廣告、推薦、提醒等服務)的需求，解決了現有技術中存在的問題。本發明的另一目的在於提供一種基於軌跡挖掘的位置預測方法，該方法將位置預測問題分解為離線軌跡挖掘和在線模式匹配兩個子問題，離線軌跡挖掘主要使用數據挖掘技術對用戶的歷史軌跡數據進行處理和分析，在線模式匹配主要基於用戶在線運動情況和挖掘出的運動模式進行匹配和查找，有效滿足各類基於位置服務(如基於位置的廣告、推薦、提醒等服務)的需求，解決了現有技術中存在的問題。本發明通過以下技術方案達到上述目的一種基於歷史軌跡數據挖掘的位置預測系統，包括移動客戶端和伺服器端，客戶端安裝在行動裝置上，包括GPS軌跡數據採集和預處理模塊，運動模式挖掘準備模塊，在線位置預測模塊，客戶端通信模塊四個模塊，GPS軌跡數據採集和預處理模塊負責以一定的採樣頻率採集GPS位置點，記錄為GPS軌跡數據，並對軌跡數據進行清洗和分割預處理；運動模式挖掘準備模塊負責對候選起點與終點進行提取，然後對軌跡數據進行抽象化處理，最後通過客戶端通信模塊將起點與終點及抽象路徑數據傳送給伺服器端，並調用其運動模式挖掘算法；在線位置預測模塊負責將伺服器端返回的經挖掘的用戶運動模式進行建模，構造模式樹，並對用戶的目的地和未來路徑進行實時預測；客戶端通信模塊負責與伺服器端進行通信；伺服器端包括運動模式挖掘模塊和伺服器端通信模塊，運動模式挖掘模塊負責按照時間序列挖掘算法將客戶端上傳的路徑抽象數據進行挖掘，得到按照起點和終點數據進行組織的運動模式集；伺服器端通信模塊負責與客戶端通信模塊進行通信，接受客戶端的路徑抽象數據，將其傳送給運動模式挖掘模塊，並將挖掘結果返回給客戶端。作為優選，客戶端和伺服器端通過GPRS進行通信。一種基於歷史軌跡數據挖掘的位置預測方法，包括以下步驟1)在用戶的行動裝置上安置GPS接收器，以一定的採樣頻率採集GPS位置點，記錄為GPS軌跡數據，並保以保存；2)將GPS軌跡數據進行清洗，對時間連續的位置點根據其速度進行聚類，將速度小於閾值的連續位置點併入同一聚類，並濾掉其中不合理的位置點數據； 3)根據連續位置點的記錄時間間隔進行分割，若連續兩個位置點的記錄時間間隔大於閾值則將軌跡分割成兩條路徑；4)對每條路徑沿時間軸正向和反向分別對位置點進行聚類處理，將時間連續且距離較近的位置點併入同一聚類，找出路徑的前向聚類和後向聚類，然後對前向聚類集和後向聚類集中的聚類進行匹配，聚類中心點距離小於閾值則合併其成為一個候選起點或終佔.
^ \\\ 5)將指定區域劃分成邊長相等的正方形網格，將位置點由包含其的網格代替，並將路徑轉化為網格序列數據，然後對軌跡數據進行抽象化處理；6)通過客戶端通信模塊將起點與終點及抽象路徑數據傳送給伺服器端將抽象路徑數據傳送給伺服器端程序，並調用其運動模式挖掘算法對接收到的用戶路徑抽象數據進行挖掘，得到按照起點至終點進行組織的運動模式集，並將其組織成文件的形式返回；7)運用I^efixSpan序列模式挖掘算法，對運動模式進行建模，構造模式樹，模式樹包含所有運動模式及其採用不同起點和終點的概率；8)基於挖掘出的用戶運動模式及其在線運動數據，通過模式樹中進行匹配查找， 得到查找結果，對其目的地和未來路徑進行預測。作為優選，步驟1)所述的GPS接收器為行動裝置內置的GPS模塊或通過藍牙連接的外置GPS模塊。作為優選，步驟1)、步驟2)和步驟3)可以同步處理。作為優選，步驟6)所述的伺服器端只接收不包含任何具體地理位置信息的起點與終點及抽象路徑數據。作為優選，步驟7)所述的模式樹結果保留在系統內存中。本發明的有益效果1)通過對用戶歷史GPS軌跡數據的分析獲得其運動規律，並基於此進行在線位置預測，無需額外硬體設備，也不受環境基礎設施影響；2)對用戶的目的地和未來路徑進行聯合預測，並藉助目的地信息對用戶未來路徑進行連續預測，避免了路徑預測長度較短的缺點；3)針對用戶運動規律，引入運動模式元素連續性概念，擴展I^refixSpan算法用於挖掘用戶的運動模式，在保證運動模式真實可靠的前提下，提高了運動模式的長度；4)通過對運動模式建立後綴樹，把所有運動模式及其後綴模式索引到一棵共享前綴的分支上，使得後續模式匹配無需採用搜索算法查找匹配起點，提高了在線位置預測中模式匹配的速度。
圖1是基於軌跡挖掘的位置預測系統結構示意圖；圖2位置預測軟體總體架構圖；圖3運動模式挖掘準備流程圖；圖4在線位置預測流程圖；圖5伺服器端程序流程圖。
具體實施例以下結合附圖對本發明做進一步的說明實施例1 基於軌跡挖掘的位置預測系統，結構如圖1所示，包括移動客戶端和伺服器端，客戶端安裝在行動裝置上，包括GPS軌跡數據採集和預處理模塊，運動模式挖掘準備模塊，在線位置預測模塊，客戶端通信模塊四個模塊，GPS軌跡數據採集和預處理模塊負責以一定的採樣頻率採集GPS位置點，記錄為GPS軌跡數據，並對軌跡數據進行清洗和分割預處理；運動模式挖掘準備模塊負責對候選起點與終點進行提取，然後對軌跡數據進行抽象化處理，最後通過客戶端通信模塊將起點與終點及抽象路徑數據傳送給伺服器端，並調用其運動模式挖掘算法；在線位置預測模塊負責將伺服器端返回的經挖掘的用戶運動模式進行建模，構造模式樹，並對用戶的目的地和未來路徑進行實時預測；客戶端通信模塊負責與伺服器端進行通信；伺服器端包括運動模式挖掘模塊和伺服器端通信模塊，運動模式挖掘模塊負責按照時間序列挖掘算法將客戶端上傳的路徑抽象數據進行挖掘，得到按照起點和終點數據進行組織的運動模式集；伺服器端通信模塊負責與客戶端通信模塊進行通信，接受客戶端的路徑抽象數據，將其傳送給運動模式挖掘模塊，並將挖掘結果返回給客戶端；客戶端和伺服器端通過GPRS進行通信。實現的具體步驟如下使用前提用戶的行動裝置需具備GPS定位功能(需要內置或外置GPS接收器)， 且收集了一定量的GPS軌跡數據。步驟1 軌跡數據預處理。軌跡數據預處理過程包括軌跡數據清洗和路徑分割兩個部分。在軌跡數據清洗方面，由於GPS設備的定位不確定性，採集到的GPS軌跡包含離群點。對時間連續的位置點根據其速度進行聚類，將速度合理(速度小於某一閾值)的連續位置點併入同一聚類，當檢測到不合理速度，且當前聚類包含位置點較少則過濾掉其中的位置點數據。在路徑分割方面，根據連續位置點的記錄時間間隔進行分割，若連續兩個位置點的記錄時間間隔大於某個閾值則將軌跡分割成兩條路徑。步驟2 候選起點/終點提取。起點和終點為用戶經常離開和去往的地點，採用一種擴展的基於時間的聚類算法，對每條路徑，沿時間軸正向和反向分別對位置點進行聚類處理(將時間連續且距離較近的位置點併入同一聚類)，並找出路徑的第一個聚類(前向聚類)和最後一個聚類(後向聚類)，然後對前向聚類集和後向聚類集中的聚類進行匹配，聚類中心點距離小於某一閾值則合併其成為一個候選起點/終點。
步驟3 路徑抽象。基於空間劃分方法，首先將指定區域劃分成邊長相等的正方形網格，將位置點由包含其的網格代替，並將用戶路徑轉化為網格序列，然後根據經過每個網格的路徑的起點終點情況合併相關網格以構造區域，使得經過同一區域的路徑具有相似的起點和終點，最後將用戶路徑抽象為區域序列，稱為區域時間序列。步驟4 運動模式挖掘。運動模式用於描述用戶經常離開和去往的地點和行走的路徑以及兩者的關係。基於I^refixSpan序列模式挖掘算法，引入模式時間連續性概念，要求運動模式元素滿足時間連續性約束(由於運動模式元素為帶時間戳的區域，即相鄰區域的間隔時間小於某一閾值)，使得一方面運動模式元素滿足時間上的連續性，另一方面運動模式可以容忍軌跡數據中的幹擾，從而挖掘出更長的運動模式。5)步驟5 在線位置預測。基於挖掘出的用戶運動模式及其在線運動數據，對其目的地和未來路徑進行聯合預測。首先基於一種模式樹的數據結構對運動模式進行建模，運動模式通過其前綴在樹中進行索引，以便於模式查找。在給定用戶在線運動數據(包括起點和最近訪問的區域序列等信息)後，以用戶最近訪問的區域序列作為前綴在模式樹中進行匹配查找。得到查找結果(即匹配的運動模式)後，首先基於用戶起點和查找到的運動模式，根據概率模型預測用戶最有可能的目的地，然後基於用戶目的地和查找到的運動模式，根據概率模型預測用戶最有可能的未來路徑(即未來運動區域序列)，並以逼近目的地為原則，通過拼接未來路徑預測結果反覆預測以提高未來路徑預測長度。本發明包括兩部分程序客戶端程序和伺服器端程序。客戶端程序安裝在行動裝置上，主要分為四個模塊GPS軌跡數據採集和預處理模塊，運動模式挖掘準備模塊，在線位置預測模塊，以及與伺服器通信模塊；伺服器端程序主要功能為運動模式挖掘，這是由於一方面模式挖掘算法計算壓力較大，另一方面為保護用戶隱私，伺服器端程序只對抽象過的用戶路徑(不包含實際地理信息)進行處理。客戶端程序和伺服器端程序通過GPRS進行通信，其軟體總體架構如圖2所示。客戶端程序客戶端是本系統中直接面向用戶的部分，它完全運行在行動裝置上，下面分別對各個模塊進行詳細說明(1) GPS軌跡數據採集和預處理模塊該模塊適用於行動裝置內置的GPS模塊或通過藍牙連接的外置GPS模塊，以一定的採樣頻率採集GPS位置點，記錄為GPS軌跡數據，並進行持久化處理(如以文件的形式記錄在手機SD卡中)。另外，對軌跡數據進行的清洗和分割等預處理工作可與位置數據採樣同時進行，以節省後期軌跡數據處理所需時間。(2)運動模式挖掘準備模塊運動模式挖掘準備模塊工作流程如圖3所示，模塊包括候選起點/終點提取和路徑抽象兩方面的功能。運動模式挖掘準備模塊可由用戶顯示調用，也可在用戶收集到一定量新的軌跡數據後被系統自動調用。調用後該模塊以獨立的線程在後臺運行，首先對用戶的候選起點/終點進行提取，然後對用戶的軌跡數據進行抽象化處理，得到區域時間序列集，最後通過與伺服器通信模塊將抽象路徑數據傳送給伺服器端程序，並調用其運動模式挖掘算法。運動模式挖掘準備模塊負責對運行過程中獲得的信息，包括候選起點/終點、區域集、區域時間序列等信息進行持久化處理，也對伺服器端程序返回的運動模式進行持久化處理。(3)在線位置預測模塊在線位置預測模塊在用戶開始一段新的路程時，以一個獨立線程的形式在後臺與軌跡數據採集模塊同時運行，並對用戶的目的地和未來路徑進行實時預測。在線位置預測模塊工作流程如圖4所示1)啟動在線位置預測模塊，會首先對存儲在行動裝置上的用戶運動模式進行建模，構造模式樹，模式樹包含所有運動模式及其採用不同起點和終點的概率。模式樹構造在該模塊啟動後只進行一次，結果保留在系統內存中，便於在線運動數據更新後反覆使用。2)由於用戶運動行為可能會隨時發生變化，在線位置預測算法以一定的間隔被反覆調用(如5分鐘調用一次)，每次被調用後都會產生新的在線運動數據，這時需要重新在模式樹中進行匹配查找。由於用戶最近訪問的路徑對其未來運動有最重要的影響，為減少計算量，使用在線運動數據中的最近若干個訪問區域進行匹配查找。3)匹配查找會返回若干候選運動模式，根據候選運動模式中起點/終點支持情況 (即用戶採用該運動模式時的起點和終點及次數)和用戶起點信息預測其目的地。4)根據預測的目的地和候選運動模式中去往該目的地的概率對候選運動模式進行遍歷以預測其未來運動區域序列。5)為得到更長的預測路徑，在一輪預測結束後，若預測算法終止條件(預測出的未來路徑與目的地足夠接近，無法再預測出任何未來路徑，或是達到一個預定預測次數) 不滿足，則拼接在線運動數據中的最近訪問區域序列和預測得到的未來運動區域序列以得到新的在線運動數據，並重新開始匹配查找。目的地與未來路徑在線預測算法如表1所示，給定從用戶軌跡數據中挖掘出的路徑模式集PS，算法首先構建模式樹，並從在線運動數據0nline_data中獲得起點和最近路徑信息(第1-2行)，然後算法進行路徑模式匹配查找過程(第3-8行)。由於對於一個在線區域序列可能無法在模式樹中找到與其匹配的路徑模式。在這種情況下，我們縮短在線區域序列，去掉其最早一個區域元素(第9-10行)，並重新開始匹配過程直到找到匹配的路徑模式。路徑匹配過程必將完成，這是由於在最壞情況下，在線區域序列被縮短為單一活躍區域，則必可以在根節點的子節點中找到匹配入口。匹配路徑模式找到後，算法基於起點-終點和下一區域概率對模式樹進行深度查找以預測目的地和未來路徑(第12-14行)。
權利要求
1.一種基於歷史軌跡數據挖掘的位置預測系統，其特徵在於，包括移動客戶端和伺服器端，客戶端安裝在行動裝置上，包括GPS軌跡數據採集和預處理模塊，運動模式挖掘準備模塊，在線位置預測模塊，客戶端通信模塊四個模塊，GPS軌跡數據採集和預處理模塊負責以一定的採樣頻率採集GPS位置點，記錄為GPS軌跡數據，並對軌跡數據進行清洗和分割預處理；運動模式挖掘準備模塊負責對候選起點與終點進行提取，然後對軌跡數據進行抽象化處理，最後通過客戶端通信模塊將起點與終點及抽象路徑數據傳送給伺服器端，並調用其運動模式挖掘算法；在線位置預測模塊負責將伺服器端返回的經挖掘的用戶運動模式進行建模，構造模式樹，並對用戶的目的地和未來路徑進行實時預測；客戶端通信模塊負責與伺服器端進行通信；伺服器端包括運動模式挖掘模塊和伺服器端通信模塊，運動模式挖掘模塊負責按照時間序列挖掘算法將客戶端上傳的路徑抽象數據進行挖掘，得到按照起點和終點數據進行組織的運動模式集；伺服器端通信模塊負責與客戶端通信模塊進行通信，接受客戶端的路徑抽象數據，將其傳送給運動模式挖掘模塊，並將挖掘結果返回給客戶端。
2.根據權利要求1所述的一種基於歷史軌跡數據挖掘的位置預測系統，其特徵在於， 客戶端和伺服器端通過GPRS進行通信。
3.一種基於歷史軌跡數據挖掘的位置預測方法，其特徵在於，包括以下步驟1)在用戶的行動裝置上安置GPS接收器，以一定的採樣頻率採集GPS位置點，記錄為 GPS軌跡數據，並保以保存；2)將GPS軌跡數據進行清洗，對時間連續的位置點根據其速度進行聚類，將速度小於閾值的連續位置點併入同一聚類，並濾掉其中不合理的位置點數據；3)根據連續位置點的記錄時間間隔進行分割，若連續兩個位置點的記錄時間間隔大於閾值則將軌跡分割成兩條路徑；4)對每條路徑沿時間軸正向和反向分別對位置點進行聚類處理，將時間連續且距離較近的位置點併入同一聚類，找出路徑的前向聚類和後向聚類，然後對前向聚類集和後向聚類集中的聚類進行匹配，聚類中心點距離小於閾值則合併其成為一個候選起點或終點；5)將指定區域劃分成邊長相等的正方形網格，將位置點由包含其的網格代替，並將路徑轉化為網格序列數據，然後對軌跡數據進行抽象化處理；6)通過客戶端通信模塊將起點與終點及抽象路徑數據傳送給伺服器端將抽象路徑數據傳送給伺服器端程序，並調用其運動模式挖掘算法對接收到的用戶路徑抽象數據進行挖掘，得到按照起點至終點進行組織的運動模式集，並將其組織成文件的形式返回；7)運用ft~efiXSpan序列模式挖掘算法，對運動模式進行建模，構造模式樹，模式樹包含所有運動模式及其採用不同起點和終點的概率；8)基於挖掘出的用戶運動模式及其在線運動數據，通過模式樹中進行匹配查找，得到查找結果，對其目的地和未來路徑進行預測。
4.根據權利要求3所述的一種基於歷史軌跡數據挖掘的位置預測方法，其特徵在於， 步驟1)所述的GPS接收器為行動裝置內置的GPS模塊或通過藍牙連接的外置GPS模塊。
5.根據權利要求3所述的一種基於歷史軌跡數據挖掘的位置預測方法，其特徵在於， 步驟1)、步驟2、和步驟幻可以同步處理。
6.根據權利要求3所述的一種基於歷史軌跡數據挖掘的位置預測方法，其特徵在於， 步驟6)所述的伺服器端只接收不包含任何具體地理位置信息的起點與終點及抽象路徑數據。
7.根據權利要求3或4或5或6任一權利要求所述的一種基於歷史軌跡數據挖掘的位置預測方法，其特徵在於，步驟7)所述的模式樹結果保留在系統內存中。
全文摘要
本發明涉及數據挖掘技術領域，具體涉及一種基於歷史軌跡數據挖掘的位置預測系統及方法，該方法將位置預測問題分解為離線軌跡挖掘和在線模式匹配兩個子問題，離線軌跡挖掘主要使用數據挖掘技術對用戶的歷史軌跡數據進行處理和分析，在線模式匹配主要基於用戶在線運動情況和挖掘出的運動模式進行匹配和查找，有效滿足各類基於位置服務(如基於位置的廣告、推薦、提醒等服務)的需求，解決了現有技術中存在的問題。
文檔編號G06Q10/04GK102509170SQ201110308289
公開日2012年6月20日 申請日期2011年10月10日 優先權日2011年10月10日
發明者呂明琪, 潘士渠, 趙江奇, 陳嶺 申請人:浙江鴻程計算機系統有限公司