基于海量物流軌跡數(shù)據(jù)的分析挖掘系統(tǒng)論文(PDF 60頁).pdf

申請工學(xué)碩士學(xué)位論文 申請工學(xué)碩士學(xué)位論文 基于海量物流軌跡數(shù)據(jù)的分析 挖掘系統(tǒng) 培養(yǎng)單培養(yǎng)單位位 信息工程學(xué)院 信息工程學(xué)院 學(xué)科專業(yè)學(xué)科專業(yè) 通信與信息系統(tǒng) 通信與信息系統(tǒng) 研研 究究 生生 甘波甘波 指導(dǎo)教指導(dǎo)教師師 周云耀教授周云耀教授 2014 年 6 月 基 于 海 量 物 流 軌 跡 數(shù) 據(jù) 的 分 析 挖 掘 系 統(tǒng) 甘 波 武 漢 理 工 大 學(xué) 萬方數(shù)據(jù) 分類號分類號 密密 級級 公開公開 UDC 學(xué)校代碼學(xué)校代碼 10497 學(xué)學(xué) 位位 論論 文文 題 目 基于海量物流軌跡數(shù)據(jù)的分析挖掘系統(tǒng) 英 文 題 目 Analysis and Mining System Based on Massive Data 研究生姓名 甘波 姓名 周云耀 職稱 教授 學(xué)位 博士 單位名稱 武漢理工大學(xué)信息工程學(xué)院 郵編 430070 申請學(xué)位級別 碩士 學(xué)科專業(yè)名稱 通信與信息系統(tǒng) 論文提交日期 論文答辯日期 學(xué)位授予單位 武漢理工大學(xué) 學(xué)位授予日期 答辯委員會主席 劉泉 評閱人 劉泉 劉可文 2014 年 6 月 指導(dǎo)教師 萬方數(shù)據(jù) 獨獨 創(chuàng)創(chuàng) 性性 聲聲 明明 本人聲明 所呈交的論文是本人在導(dǎo)師指導(dǎo)下進行的研究工作及 取得的研究成果 盡這里所知 除了文中特別加以標注和致謝的地方 外 論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果 也不包含為 獲得武漢理工大學(xué)或其他教育機構(gòu)的學(xué)位或證書而使用過的材料 與 這里一同工作的同志對本研究所做的任何貢獻均已在論文中作了明 確的說明并表示了謝意 簽 名 日 期 學(xué)位論文使用授權(quán)書學(xué)位論文使用授權(quán)書 本人完全了解武漢理工大學(xué)有關(guān)保留 使用學(xué)位論文的規(guī)定 即 學(xué)校有權(quán)保留并向國家有關(guān)部門或機構(gòu)送交論文的復(fù)印件和電子版 允許論文被查閱和借閱 本人授權(quán)武漢理工大學(xué)可以將本學(xué)位論文的 全部內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢索 可以采用影印 縮印或其他復(fù)制 手段保存或匯編本學(xué)位論文 同時授權(quán)經(jīng)武漢理工大學(xué)認可的國家有 關(guān)機構(gòu)或論文數(shù)據(jù)庫使用或收錄本學(xué)位論文 并向社會公眾提供信息 服務(wù) 保密的論文在解密后應(yīng)遵守此規(guī)定 研究生 簽名 導(dǎo)師 簽名 日期 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 I 摘 要 電子商務(wù)盛行的今天 物流行業(yè)空前繁榮 物流車輛的海量 GPS 數(shù)據(jù)量也 越來越多 這些數(shù)據(jù)包含很多關(guān)于交通路況 車輛甚至社會經(jīng)濟發(fā)展等信息 軌跡數(shù)據(jù)挖掘主要通過統(tǒng)計和分析車輛行駛距離 停車時間 地理位置信息 車輛特征等發(fā)現(xiàn)貨運線路特征 為物流公司提供基于時間 成本等車輛調(diào)度方 案以及衍生出來的一系列 LBS 1 應(yīng)用提供服務(wù) 本文以海量 GPS 數(shù)據(jù)作為數(shù)據(jù)源 利用海量軌跡數(shù)據(jù)挖掘和道路推薦相關(guān) 理論 通過建立聚類模型和分析海量 GPS 數(shù)據(jù)來了解物流車輛行駛規(guī)律 提出 針對物流車輛貨運線路推薦系統(tǒng)的設(shè)計框架并實現(xiàn) 其中重點就是數(shù)據(jù)預(yù)處理 方法 停車點偵測和路徑分割方法 相似貨運軌跡聚類和貨運線路推薦四個方 面進行了深入研究 具體工作如下 1 作為軌跡數(shù)據(jù)挖掘的必要工作 研究了預(yù)處理方法 包括數(shù)據(jù)清洗 數(shù)據(jù)中的異常進行偵查和排除 并針對本系統(tǒng)所有的 GPS 數(shù)據(jù)進行了特征分析 和提出了一種基于歷史軌跡數(shù)據(jù)的異常點檢測算法 本文提出的算法在處理海 量軌跡數(shù)據(jù)時具有時間復(fù)雜度低的特點 2 停車點偵測和路徑分割可以發(fā)現(xiàn)物流車輛的上下貨的模式 本文依據(jù) 樸素貝葉斯算法提出一種新的基于歷史數(shù)據(jù)的路徑分割算法 根據(jù)物流車輛在 上下貨時的停車和普通停車在時空屬性上的不同 將軌跡進行分割 3 相似貨運軌跡聚類將相同起始點和終點的軌跡規(guī)則化后投射到同一緯 度然后分析軌跡特征 采用 K 均值聚類算法將這些規(guī)則化后的軌跡聚類 聚類 后的結(jié)果中可以發(fā)現(xiàn)物流車輛頻繁的行駛軌跡 4 貨運線路推薦方面 設(shè)計了基于歷史軌跡數(shù)據(jù)在時間 距離以及成本 的不同 得出相應(yīng)的推薦線路指導(dǎo)物流司機采用合理的行駛方案 經(jīng)測試表明 論文中使用的軌跡預(yù)處理方法與傳統(tǒng)預(yù)處理方法相比速度更 快 效率更高 但是犧牲了一些準確度 停車點偵測和軌跡分割達到了良好的 效果 研究成果對于缺失車輛卸貨點的軌跡分析有十分重要的理論意義 關(guān)鍵詞關(guān)鍵詞 貝葉斯分類器 軌跡數(shù)據(jù)挖掘 路徑分割 異常點過濾 K 均值聚類 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 II Abstract In the age of the electronic commerce the electronic commerce logistics industry logistics vehicles are more prosperity than ever More and more logistics vehicles GPS data are produced These data contain a lot of traffic information such as road conditions vehicles and even social and economic development Through statistics and analysis of vehicle driving distance time location vehicle parking characteristics trajectory data mining can find shipping line characteristics provide logistics company based on vehicle scheduling schemes such as time cost and derived a series of LBS application Taking massive GPS data as the data source using massive trajectory data mining and related theory of road recommending composed by online and offline system this paper proposes and realizes a designframework of route recommending system for logistics vehicle through establishing clustering model and analyzing massive GPS data to understand the driving rule of logistics vehicles The key approach is deep studying on data preprocessing stops detecting route segmenting similar freight trajectory clustering and freight lines recommending The specific work is as follows As a necessary work in trajectory data mining i study the pretreatment method including data cleaning data of abnormal detection and exclusion and with the characteristics of this system all the GPS data in analysis and put forward a kind of anomaly detection algorithm based on the historical trajectory data The algorithm for massive data processing has low time complexity Parking points detection and path integral can find that the pattern of logistics vehicles and goods In this paper on the basis of naive bayes algorithm i put forward a new way for trajectory segmentation according to the logistics vehicle parking and ordinary ponits using the different attributes of time and space between them when goods are loaded and unloaded I regulate freight trajectories clustering similar to the same starting point and end point of the trajectory then project them on the same latitude After that using k means algorithm the characteristic of trajectory is analyzed and finally get 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 III logistics vehicle general movement tracks In the recommendation of shipping lines based on the difference of historical trajectory data in time distance and cost i design and draw the corresponding recommended route guidance which logistics driver adopts through reasonable driving scheme Compared with traditional pretreatment method These tests show that the method of pretreatment trajectory is faster more efficient but sacrificing some precision Detecting parking spots and track segmentation achieve good effects In the cases of missing stops of vehicle trajectory analysis the research results have very important theoretical significance Keywords bayesian classifier trajectory data mining carving abnormal point filter k means clustering 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 IV 目 錄 摘 要 I Abstract II 目 錄 IV 第 1 章 緒論 1 1 1 課題來源 1 1 2 研究的背景和意義 1 1 3 國內(nèi)外研究現(xiàn)狀 2 1 4 論文內(nèi)容和組織結(jié)構(gòu) 4 第 2 章 軌跡數(shù)據(jù)挖掘技術(shù)研究 5 2 1 軌跡數(shù)據(jù)挖掘介紹 5 2 1 1 軌跡數(shù)據(jù)挖掘概念 5 2 1 2 軌跡數(shù)據(jù)挖掘內(nèi)容 5 2 2 軌跡數(shù)據(jù)挖掘流程 6 2 2 1 數(shù)據(jù)來源和預(yù)處理 6 2 2 2 軌跡數(shù)據(jù)路徑分割和聚類分析 8 2 3 基于歷史軌跡的線路推薦服務(wù) 9 2 4 本章小結(jié) 10 第 3 章 軌跡數(shù)據(jù)預(yù)處理和軌跡分割方法研究 11 3 1 軌跡計算流程 11 3 2 軌跡數(shù)據(jù)預(yù)處理 12 3 2 1 軌跡數(shù)據(jù)特征 12 3 2 2 軌跡數(shù)據(jù)異常點檢測 13 3 3 停車點識別方法研究 14 3 4 軌跡分割方法研究 17 3 4 1 貝葉斯分類器概述 17 3 4 2 構(gòu)造停車點訓(xùn)練集 18 3 4 3 基于樸素貝葉斯分類器的停車點分類 20 3 5 本章小結(jié) 23 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 V 第 4 章 海量軌跡數(shù)據(jù)聚類算法研究 24 4 1 軌跡聚類的意義和問題 24 4 2 軌跡表達和相似性度量 25 4 2 1 軌跡規(guī)則化 25 4 2 2 軌跡相似性度量 30 4 3 軌跡聚類 32 4 3 1 常見聚類算法比較 32 4 3 2 基于 均值算法的軌跡聚類 33 4 4 基于 GPS 數(shù)據(jù)的線路推薦方法 35 4 5 本章小結(jié) 37 第 5 章 系統(tǒng)驗證和結(jié)果分析 38 5 1 實驗基礎(chǔ)和條件 38 5 2 系統(tǒng)實現(xiàn)與驗證 38 5 2 1 數(shù)據(jù)預(yù)處理 38 5 2 2 停車點識別 39 5 2 3 軌跡分割 42 5 2 4 軌跡聚類 43 第 6 章 工作總結(jié)和展望 44 6 1 本文工作總結(jié) 44 6 2 下一步工作展望 44 致 謝 46 參考文獻 48 作者在攻讀碩士學(xué)位期間發(fā)表的專利 51 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 1 第 1 章 緒論 1 1 課題來源 中科院深圳先進技術(shù)研究所和深圳市宇易通科技有限公司合作開發(fā)設(shè)計的 一個易流云平臺系統(tǒng) 該平臺旨在為物流企業(yè)提供真實物流信息服務(wù)的真實運 力服務(wù) 1 2 研究的背景和意義 當(dāng)今社會屬于互聯(lián)網(wǎng)高速發(fā)展的時代 許多傳統(tǒng)行業(yè)都受到了劇烈的沖擊 其中電子商務(wù)逐漸興起 商業(yè)活動的網(wǎng)上交易呈爆發(fā)式增長 伴隨來的是物流 行業(yè)的蓬勃發(fā)展 為物流車輛軌跡數(shù)據(jù)挖掘提供了海量的數(shù)據(jù)源 軌跡數(shù)據(jù)挖 掘是數(shù)據(jù)挖掘在軌跡上面的新的應(yīng)用 它包括了軌跡數(shù)據(jù)存儲 軌跡數(shù)據(jù)預(yù)處 理 軌跡數(shù)據(jù)獲取和挖掘以及應(yīng)用 盡管有關(guān)于傳統(tǒng)的數(shù)據(jù)挖掘系統(tǒng)已經(jīng)有了 多年很成熟的理論和方法 但是由于軌跡數(shù)據(jù)的特殊性 依然有許多軌跡問題 需要深入研究 例如軌跡索引 查詢 模式挖掘 不確定性和隱私保護等 其 具體特點如下 1 數(shù)據(jù)海量性 物流車一般以 30s 的間隔向數(shù)據(jù)中心發(fā)送當(dāng)前位置 這 些移動在全國各地路網(wǎng)中的物流車輛每天生成的GPS數(shù)據(jù)都達到了GB 甚至TB 規(guī)模 并且還在不斷增長中 這既是發(fā)展數(shù)據(jù)挖掘的驅(qū)動力 也是對數(shù)據(jù)挖掘 的面臨的難題 2 數(shù)據(jù)稀疏性 雖然這些軌跡數(shù)據(jù)規(guī)模龐大 但是由于地理因素 如車 輛行駛在山區(qū) 雨雪天氣 設(shè)備故障等原因 并不能保證每一個路段都有完 整的 GPS 信息 甚至?xí)幸恍┦清e誤的 GPS 數(shù)據(jù) 3 數(shù)據(jù)復(fù)雜性 物流車輛在實際行駛過程中受到各方面主客觀等因素難 以簡單通過某個模型或者理論進行評估和預(yù)測 主要有下列因素 每個司機都 有自己的駕駛習(xí)慣 即使同一個司機在駕駛過程中也會針對不同客觀條件改變 自己的駕駛行為 例如天氣 實時路況 這些不確定性無疑增加了軌跡數(shù)據(jù)挖 掘的復(fù)雜性 4 數(shù)據(jù)豐富性 在海量的軌跡數(shù)據(jù)背后隱藏著全國實時路況信息 物流 運輸狀況信息和我國不同區(qū)域經(jīng)濟發(fā)展水平 對于我國道路基礎(chǔ)建設(shè) 交通路 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 2 徑規(guī)劃 物流車輛調(diào)度等提高我國物流行業(yè)水平具有重大意義 車輛軌跡是車輛的位置和時間的記錄序列 可以很容易的使用小型 GPS 記 錄儀 車內(nèi)導(dǎo)航設(shè)備 甚至手機獲取 作為軌跡數(shù)據(jù)挖掘中的重要研究對象 分析和挖掘這種數(shù)據(jù)類型可以應(yīng)用于城市熱點區(qū)域分析 智慧物流和交通規(guī)劃 等多個方面 2 不同的物流車輛軌跡通過分解在不同時間 空間等很多維度上以 后 既有相同或者類似的部分 也有不同的地方 通過分析和統(tǒng)計其相似性和 相異特征可以挖掘出軌跡數(shù)據(jù)背后包含的很多知識 在我國建設(shè)信息網(wǎng)絡(luò)技術(shù) 城市 交通 物流的背景下 這些知識作為寶貴的財富可以不斷推動我國向信 息化 智慧化城市 物流積極發(fā)展 降低運輸成本 提高經(jīng)濟效益 最終實現(xiàn) 物流業(yè)智能化 智慧化 1 3 國內(nèi)外研究現(xiàn)狀 軌跡數(shù)據(jù)中的知識模式發(fā)現(xiàn)和處理有很多不同的方式 可以首先通過不同 概念模型描述軌跡 然后在不同維度上的特征將軌跡分組 接著分析這些經(jīng)過 分組后的軌跡組內(nèi)和組間相似性和相異性 發(fā)現(xiàn)偏離正常數(shù)據(jù)的異常軌跡 針 對不同應(yīng)用場景調(diào)整軌跡分類策略等 最終達到發(fā)現(xiàn)獲取軌跡背后的知識 在 這一個過程中 經(jīng)常會遇到各種各樣難以克服的困難 譬如數(shù)據(jù)量巨大 數(shù)據(jù) 維數(shù)災(zāi)難 數(shù)據(jù)受到主客觀因素污染 數(shù)據(jù)不確定 知識發(fā)現(xiàn)角度多種 知識 表示困難等技術(shù)難點 3 軌跡數(shù)據(jù)挖掘發(fā)現(xiàn)的知識類型和所使用的方法密切相關(guān) 所發(fā)現(xiàn)的知識的 價值受到數(shù)據(jù)挖掘算法的影響 常用的軌跡數(shù)據(jù)挖掘技術(shù)有規(guī)則歸納 概念簇 集 關(guān)聯(lián)發(fā)現(xiàn)等 在實際軌跡數(shù)據(jù)挖掘應(yīng)用中 應(yīng)當(dāng)根據(jù)不同的需求采用不同 的工具 方法以及理論 目前的軌跡數(shù)據(jù)挖掘研究工作中主要為軌跡聚類 軌跡分類 離群點檢測 興趣區(qū)域 隱私保護 位置推薦等方面 作為軌跡挖掘重要的一部分 異常軌 跡檢測中 也已經(jīng)提出了許多算法 傳統(tǒng)的軌跡異常檢測中 通常是提取軌跡 某些特征 計算這些特征間的差值再進行加權(quán)得到軌跡間的距離 克諾爾 4 通過 將軌跡分解 降低維數(shù)得到若干個包含主要軌跡有用信息并且相互獨立的特征 如軌跡所包含的 GPS 點的數(shù)量 軌跡運動快慢 軌跡起始點的坐標位置 軌跡 運動趨勢等 通過檢測的異常和正常軌跡數(shù)據(jù)路徑的距離不同 以確定其缺陷 的異常信息 它的缺陷在于 由于軌跡內(nèi)部不同局部區(qū)域也存在特征上的差異 因 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 3 此上述方法只適用于特征單一或者長度較短的軌跡 伊利諾伊大學(xué)的 Li 5 建議構(gòu) 建了一種軌跡異樣檢查框架 ROAM 該框架將首先通過軌跡離散化分成一個個 獨立的名為 Motif 的片段 該片段提取軌跡的某些特征信息構(gòu)成 Motif 特征空間 利用構(gòu)建的 Motif 中的屬性信息 這個分類器最終用于將不同軌跡數(shù)據(jù)分類從而 獲取軌跡背后蘊藏的知識 為了克服傳統(tǒng)軌跡中無法針對軌跡較長或者特征較復(fù)雜進行有效的檢測 劉良序 6 首先通過不同軌跡間的相似程度的不同提出了部分相似 完全相似和離 群軌跡的模型 將一段較長的軌跡分為若干獨立無關(guān)的軌跡段 利用之前定義 的模型和概念 然后比較每一個分段之間的匹配程度 設(shè)定不同閾值來確定這 些較長的軌跡是否相似 并且使用了 R 樹來來克服計算量過大的問題 也有一 些科研人員通過數(shù)據(jù)挖掘中的密度聚類思想 密度越大的地方 軌跡越趨向于 正常軌跡 密度越小的地方軌跡越有可能為異常軌跡 譬如 Liu 7 軌跡聚類是在相似的軌跡中找到不相似部分的過程 軌跡特征空間中不同 密度代表不同軌跡在該屬性上相似程度的不同 并且特征空間中不同的屬性對 軌跡相似程度的影響也各不相同 8 不同軌跡從時間區(qū)間這個角度來看 其相似 性也各有不同 本文從時間間隔出發(fā) 將不同聚類方法分為如下幾類 如表 1 1 所示 這些方法逐漸在相似的時間間隔從時間上的要求相似性 本地時間間隔 相似 最后到?jīng)]有時間對應(yīng)的相似性下降 它反映了人們在時間和空間探索時 空軌跡和軌跡相似性度量的多樣性 表 1 1 軌跡聚類方法分類列表 相似性度量 代表聚類方法 全區(qū)間時間相似 歐式距離 9 最小外接矩形距離 10 全區(qū)間變換對應(yīng)相似 動態(tài)時間規(guī)整 11 多子區(qū)間對應(yīng)相似 最長公共子序列距離 12 單子區(qū)間對應(yīng)相似 子軌跡聚類 13 單點對應(yīng)相似 歷史最近距離 14 無時間區(qū)間對應(yīng)相似 單向距離 15 目前有關(guān)軌跡數(shù)據(jù)挖掘的研究主要關(guān)注在軌跡的時空特性上 已經(jīng)建立了 一些關(guān)于軌跡數(shù)據(jù)建模 數(shù)據(jù)存儲 軌跡索引 軌跡查詢 軌跡挖掘方面 但 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 4 是有關(guān)軌跡的語義信息的理論研究卻并不多 Yan 16 等人提出了面向軌跡數(shù)據(jù)語 義信息分析與挖掘 獲取物體有關(guān)運動的未知知識 這些知識是軌跡挖掘更深 層次的應(yīng)用 在目前云計算和大數(shù)據(jù)的時代下 只有對軌跡數(shù)據(jù)挖掘進行更深入分析和 挖掘 研究物流系統(tǒng)模仿或者實現(xiàn)人類的在不同諸如天氣 實時路況等諸多客 觀因素下的行為 具備模仿人的智能 學(xué)習(xí)推斷并自適應(yīng)解決出現(xiàn)在物流運輸 存儲的問題的能力 也就是當(dāng)商品從出庫 車輛中轉(zhuǎn)調(diào)度 行駛路線和時間一 系列問題作出合理正確的規(guī)劃 最終達到物流的智慧化 1 4 論文內(nèi)容和組織結(jié)構(gòu) 本文依據(jù)軌跡數(shù)據(jù)挖掘的一般流程 首先分析 GPS 數(shù)據(jù)特征 并提出針對 海量軌跡數(shù)據(jù)的預(yù)處理方法 接著提出采用貝葉斯分類器算法 并將此算法應(yīng) 用到的軌跡分割處理中 將不同車的不同軌跡提取出來 接著研究了軌跡聚類 的相關(guān)算法 提出將 K 均值的聚類算法運用到軌跡聚類中 最后針對以上算法 和系統(tǒng)進行了實驗 將以上結(jié)果應(yīng)用帶貨運線路推薦系統(tǒng)中 第一章中本文系統(tǒng)闡述了軌跡數(shù)據(jù)挖掘產(chǎn)生的原因和意義和一些已有的方 法和理論研究的發(fā)展和現(xiàn)狀 以及存在的問題 最后是論文的結(jié)構(gòu) 第二章主要闡述了軌跡挖掘概念 一般過程和方法 提出了一種基于歷史 軌跡數(shù)據(jù)的貨車運送線路推薦系統(tǒng) 第三章介紹了軌跡計算的一般流程 詳細分析了數(shù)據(jù)預(yù)處理 停車點識別 和軌跡分割的流程 提出了軌跡數(shù)據(jù)異常檢測算法 基于樸素貝葉斯分類器的 軌跡分割算法 完成了貨運車輛的起止點識別 從而為軌跡分割提供了依據(jù) 第四章詳細闡釋了貨運車輛軌跡聚類意義和存在的問題 分析了軌跡聚類 流程 首先將軌跡規(guī)則化 然后通過 K 均值算法將軌跡聚類獲取貨運線路常用 行駛路線 并提出了基于 GPS 數(shù)據(jù)的線路推薦方法 第五章對整個系統(tǒng)進行實現(xiàn)和驗證 利用 matlab 繪圖總結(jié)分析得出結(jié)論 第六章總結(jié)與展望 對于本文所做工作不足之處進行了總結(jié)和對未來軌跡 數(shù)據(jù)挖掘的展望 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 5 第 2 章 軌跡數(shù)據(jù)挖掘技術(shù)研究 2 1 軌跡數(shù)據(jù)挖掘介紹 2 1 1 軌跡數(shù)據(jù)挖掘概念 軌跡數(shù)據(jù)挖掘 Trajectory Data Mining 是數(shù)據(jù)挖掘技術(shù)中的一個重要的新 興領(lǐng)域 它的研究對象來源于越來越多可移動裝置上裝有 GPS 等定位設(shè)備并不 斷記錄人類或者車輛的運行軌跡 在傳統(tǒng)的數(shù)據(jù)挖掘過程和算法基礎(chǔ)上針對移 動軌跡數(shù)據(jù)特征 重點研究軌跡數(shù)據(jù)預(yù)處理 軌跡數(shù)據(jù)中的不確定性研究 軌 跡數(shù)據(jù)索引與存儲 軌跡模式發(fā)現(xiàn) 軌跡隱私保護以及基于位置信息的社會化 服務(wù) 是計算機技術(shù) 存儲技術(shù) 統(tǒng)計學(xué) 地理信息學(xué)和新技術(shù)等多學(xué)科的整 合 軌跡數(shù)據(jù)本身的海量性 復(fù)雜性也對傳統(tǒng)的數(shù)據(jù)挖掘算法提出了很多新的 挑戰(zhàn) 原有的數(shù)據(jù)挖掘?qū)ο笸鶖?shù)據(jù)量比起軌跡數(shù)據(jù)而言不大 為此很多新興 的數(shù)據(jù)庫存儲和索引技術(shù) 大數(shù)據(jù)處理解決方案也層出不窮不斷 例如空間數(shù) 據(jù)庫 內(nèi)存數(shù)據(jù)庫 批處理數(shù)據(jù)處理框架 實時流計算框架等 17 一般而言 軌跡數(shù)據(jù)挖掘 是指從大量軌跡數(shù)據(jù)的集合 C 中發(fā)現(xiàn)隱含模式 m 和知識 n 的結(jié)果 S 因此 軌跡數(shù)據(jù)挖掘的過程可以看作為一個函數(shù) C S m n 18 2 1 輸入是軌跡數(shù)據(jù) 輸出是隱含模式 m 和知識 n 通過使用某些技術(shù) 理論 從大量的軌跡數(shù)據(jù)提取模式 發(fā)現(xiàn)龐大知識的一個過程 2 1 2 軌跡數(shù)據(jù)挖掘內(nèi)容 軌跡數(shù)據(jù)挖掘目前的研究熱點集中于軌跡聚類 異常點檢測 軌跡分類 位置推薦等方面 如圖 2 1 所示 1 軌跡聚類 通過軌跡聚類的方式可以發(fā)現(xiàn)軌跡數(shù)據(jù)中的相似性和異常 特征 從而得到對于軌跡應(yīng)用中有益的模式 例如發(fā)現(xiàn)熱點區(qū) 通過大量物流 車輛的歷史軌跡可以找到收益最高的行駛路線 監(jiān)控物流貨運車司機駕駛行為 等 通過研究不同軌跡數(shù)據(jù)在時空等方面的特征 定義設(shè)計不同的準則去度量 軌跡的相似性 利用相似性的不同將軌跡區(qū)分開來 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 6 圖 2 1 軌跡數(shù)據(jù)挖掘熱點分類圖 2 異常點檢測 在數(shù)據(jù)挖掘領(lǐng)域 異常數(shù)據(jù)的識別是其中比較重要的一 部分 所謂的異常數(shù)據(jù)指的并非由隨機誤差造成的偏離大部分數(shù)據(jù)的特征的那 部分數(shù)據(jù) 異常數(shù)據(jù)就識別出數(shù)據(jù)集中的異常點 同時混雜在異常數(shù)據(jù)中的正 確數(shù)據(jù)也需要識別 它涉及怎么樣定義異常數(shù)據(jù)和尋求有效的算法來識別并剔 除掉這部分數(shù)據(jù) 3 軌跡分類 軌跡分類與軌跡聚類的目的相反 指的是通過統(tǒng)計和分析 不同軌跡間的時空特征 抽象出軌跡模型 并以此模型作為分類器 對目標軌 跡進行分類 這是一個不斷迭代的過程 并且出于不同的分類目的定義目標軌 跡模式 通過軌跡歷史模型 從而智能的將軌跡數(shù)據(jù)分類 4 位置服務(wù) 車輛的行駛軌跡不僅僅是車輛行駛路線的一種記錄 更是 反映了駕駛?cè)藛T針對駕駛活動期間客觀因素 例如天氣 實時路況 加油站等 地理位置信息的智能反應(yīng) 通過搜集 統(tǒng)計 分析這些歷史軌跡可以極大提高 車輛管理 監(jiān)控 調(diào)度 路徑規(guī)劃效率 在當(dāng)今越來越開放的網(wǎng)絡(luò)條件下 實 時共享位置信息 可以為公司和客戶提供精準且高效的物流配送服務(wù) 隨著這 些位置信息的不斷挖掘和共享 極大降低了物流行業(yè)中的溝通成本 降低中間 環(huán)節(jié)消耗 2 2 軌跡數(shù)據(jù)挖掘流程 2 2 1 數(shù)據(jù)來源和預(yù)處理 軌跡數(shù)據(jù)來源是移動設(shè)備所發(fā)出的位置信息 對于物流軌跡數(shù)據(jù)而言 通 常是 GPS 信息 預(yù)處理的過程首先是分析所獲取數(shù)據(jù)的總體特征 再依據(jù)數(shù)據(jù) 的特征采用不同過濾算法 軌跡數(shù)據(jù)挖掘 異常點檢測 軌跡聚類 軌跡分類 位置推薦 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 7 1 挖掘數(shù)據(jù)來源 軌跡數(shù)據(jù)挖掘來源通常是終端設(shè)備上產(chǎn)生的位置記錄 然后位置信息傳回 數(shù)據(jù)中心以日志文件形式存放 本文采用的是數(shù)據(jù)中心的 GPS 日志記錄 表 2 1 是 GPS 日志的記錄表結(jié)構(gòu) 表 2 1GPS 日志記錄表結(jié)構(gòu) 屬性域?qū)傩杂?描描 述述 車輛編號 車輛的唯一編號 經(jīng) 度 以度為單位的維度值乘以10的6次方 緯 度 以度為單位的維度值乘以10的6次方 里 程 0 1KM 速 度 KM H 方 向 0 359 正北為0 順時針 高 度 海拔高度 單位米 GPS時間 接收到GPS的時間 狀 態(tài) 0位 0 未定位 1 3D定位 一條典型的 GPS 日志記錄如下 其中各個字段之間用逗號隔開 車牌號碼已 經(jīng)被加密 XI081FB4GU 115045136 30511584 412698 62 75 0 13 12 1 20 5 48 1 2 軌跡數(shù)據(jù)特征分析 軌跡數(shù)據(jù)特征分析是指觀測軌跡記錄中所具有的包括空間屬性 數(shù)字特征 分布結(jié)構(gòu)等在內(nèi)的特征 是數(shù)據(jù)應(yīng)用的基礎(chǔ) 它包括很多方面的統(tǒng)計和分析 例如離散軌跡點隨著時間增長時候的方向信息 起止點最遠距離信息 最大時 間間距信息等一維數(shù)據(jù)信息 在這些一維數(shù)據(jù)的基礎(chǔ)上分析軌跡點的密度的稀 疏性 分布結(jié)構(gòu)的信息有利于發(fā)現(xiàn)熱點區(qū)域等 通過線性回歸的方式有利于常 見軌跡模式的發(fā)現(xiàn)和提取 不斷研究軌跡時間與時間 時間和空間 空間與空 間之間的關(guān)系 3 軌跡數(shù)據(jù)異常檢測 軌跡數(shù)據(jù)挖掘領(lǐng)域異常檢測一直是研究熱點 通過數(shù)據(jù)挖掘中的常規(guī)模式 析取可以發(fā)現(xiàn)大量軌跡數(shù)據(jù)時空特征以及背后的語義信息 但是有時候異常的 出現(xiàn)也包含很多重要信息 例如可以修正之前軌跡特征空間劃分的方式 發(fā)現(xiàn) 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 8 隱藏或者突發(fā)的信息等 所謂異常 有很多各種各樣的概念描述 概括而言指 的是這樣的一些數(shù)據(jù)具有整個數(shù)據(jù)集合中不同尋常的屬性和特征 異常與錯誤 不同 異常的產(chǎn)生并非人為原因造成 也并不是隨機因素影響 軌跡異常檢測 可以分為兩個過程實現(xiàn) 首先在軌跡數(shù)據(jù)特征分析的基礎(chǔ)之上發(fā)現(xiàn)和定義異常 特征 然后利用這些特征空間與軌跡數(shù)據(jù)集比對 找到符合這些異常特征的數(shù) 據(jù)集 不斷迭代修正異常特征空間 最終檢測出異常軌跡數(shù)據(jù) 目前關(guān)于異常 檢測有很多種方法 例如使用統(tǒng)計學(xué)知識對軌跡的時空分布特征統(tǒng)進行分析 找到不符合常規(guī)分布特征的數(shù)據(jù)集合 通過定義軌跡間距離的方式來發(fā)現(xiàn)異常 軌跡 關(guān)于距離的定義也有很多種 歐式距離 曼哈頓距離 漢明距離 切比 雪夫距離等 定義軌跡在時空屬性的密度特征也可以發(fā)現(xiàn)異常軌跡 密度大的 區(qū)域的軌跡趨向于正常軌跡 密度小的區(qū)域的軌跡趨向于異常軌 19 2 2 2 軌跡數(shù)據(jù)路徑分割和聚類分析 通過 GPS 設(shè)備獲取的軌跡數(shù)據(jù)只包含每一軌跡點的經(jīng)緯度和對應(yīng)的時刻信 息 通過這些數(shù)據(jù)無法直接得到活動行為的特征信息 如停車時間 是否卸貨 物流的目的地 以及其他信息 要想獲取這些信息首先就必須進行停車點偵測 判斷是那些時刻是真實停車 還是 GPS 產(chǎn)生了漂移誤差 或是由于紅綠燈 交 通擁堵造成的停車 或者是停車卸貨等一系列重要信息和知識 圖 2 2 為停留點 偵測示意圖 軌跡分割是軌跡數(shù)據(jù)挖掘的基礎(chǔ)和前提 目前 軌跡分割算法有探索和機 器學(xué)習(xí)方法兩大類 20 探索性方法考慮移動對象停留和移動時的時空特征或定 位設(shè)備的特征 作為已知經(jīng)驗 設(shè)計算法對軌跡原始數(shù)據(jù)進行處理和分析 機 器學(xué)習(xí)是人工智能的一個分支 目的是構(gòu)建一個可以從數(shù)據(jù)集中學(xué)習(xí)的系統(tǒng) 機器學(xué)習(xí)主要解決數(shù)據(jù)表示和泛化的問題 數(shù)據(jù)實例的表示和評估是所有機器 學(xué)習(xí)系統(tǒng)中的重要部分 機器學(xué)習(xí)系統(tǒng)對數(shù)據(jù)集泛化的能力是對未知數(shù)據(jù)分類 和計算的核心關(guān)鍵部分 通過機器學(xué)習(xí)的方式可以使軌跡數(shù)據(jù)挖掘更加智能 不僅能夠發(fā)現(xiàn)軌跡已有的特征 還能針對未知軌跡數(shù)據(jù)學(xué)習(xí)發(fā)現(xiàn)新的特征 機 器學(xué)習(xí)方法有很多種 決策樹學(xué)習(xí) 關(guān)聯(lián)規(guī)則學(xué)習(xí) 人工神經(jīng)網(wǎng)絡(luò) 支持向量 機學(xué)習(xí) 聚類 貝葉斯網(wǎng)絡(luò)等 21 聚類的目的是嘗試將具有相似特征的軌跡劃分開來 凸顯不同軌跡間的相 似性 為更深層次的研究打下基礎(chǔ) 可以將軌跡特征空間中不同屬性相互獨立 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 9 抽取出來 找到每一個被劃分的屬性與整體分布特征之間的關(guān)系 22 根據(jù)相似 度量的不同 常見的基于距離軌跡聚類方法有基于歐氏距離 最長公共子序列 距離 時間聚焦距離 歷史最近距離等 圖 2 2 停留點偵測示意圖 2 3 基于歷史軌跡的線路推薦服務(wù) 目前基于位置的服務(wù) LBS 已經(jīng)在市面上取得了大量應(yīng)用 例如旅游線路 分享 車輛調(diào)度和安保等 簡單的將軌跡展現(xiàn)在地圖或者其它的媒介上 統(tǒng)計 其行駛距離 時間 頻率 停車位置等難以發(fā)現(xiàn)軌跡中包含的司機駕駛習(xí)慣 交通道路信息 熱點區(qū)域以及路徑信息等 其實 軌跡記錄了駕駛?cè)藛T在真實 世界的活動 而這些活動將在一定程度上體現(xiàn)了駕駛時的各種環(huán)境因素 比如 交通路況 天氣 經(jīng)濟成本等 而傳統(tǒng)的路徑推薦系統(tǒng)主要是通過基于地圖的 最短路徑算法生成的推薦線路 通過這種的算法規(guī)劃得到的路徑由于沒有考慮 到實際中地理位置信息 例如停車場 加油站 貨運園區(qū)工廠以及道路限行 限速路段 監(jiān)控區(qū)域等 并且這些地理位置信息經(jīng)常出現(xiàn)新增 變更 刪除 不準的狀況 基于歷史軌跡的路線推薦系統(tǒng)由于是考慮了實際需求 由于是司 機駕駛的實際路徑結(jié)果 包含了司機對真實地理天氣和道路綜合考慮的結(jié)果 因此推薦的線路也更合理 更多樣 可以基于最少時間 最少費用 也可以最 行駛路徑 軌跡 停留點 停留區(qū)域 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 10 短路徑等 基于歷史軌跡的線路推薦服務(wù)的一般結(jié)構(gòu)如圖 2 3 所示 它是依賴聚類結(jié) 果 包含基礎(chǔ)的數(shù)據(jù)處理并挖掘相關(guān)知識 包括數(shù)據(jù)采集 數(shù)據(jù)預(yù)處理 數(shù)據(jù) 分析 圖 2 3 基于歷史軌跡的線路推薦服務(wù)一般結(jié)構(gòu) 2 4 本章小結(jié) 本章細述了軌跡數(shù)據(jù)挖掘的基本流程 數(shù)據(jù)源的獲取 數(shù)據(jù)預(yù)處理 軌跡 分割 軌跡聚類 推薦服務(wù) 對基于歷史軌跡的線路推薦服務(wù)系統(tǒng)做了分析 說明了使用的聚類算法和推薦算法 根據(jù)數(shù)據(jù)挖掘的知識完成貨運線路推薦功 能 推薦系統(tǒng)模塊 數(shù)據(jù)挖掘模塊數(shù)據(jù)預(yù)處理模塊 預(yù) 處 理 GPS 記錄日 推 薦 算 法 服務(wù) 用戶 空間數(shù)據(jù)庫 用戶信用級 軌 跡 分 割 算 軌 跡 聚 類 算 預(yù)處理 后 GPS 記錄 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 11 第 3 章 軌跡數(shù)據(jù)預(yù)處理和軌跡分割方法研究 3 1 軌跡計算流程 通過定位技術(shù)采集到的原始軌跡數(shù)據(jù)只是一系列的經(jīng)緯度 時間 速度等 信息 通過這些信息無法直接得到物流貨運車的活動行為的特征信息 例如運 送貨物的起始點 途經(jīng)哪些城市信息 以及更深層次的活動規(guī)律等 這些原始 的 GPS 數(shù)據(jù)必須經(jīng)過一系列的處理步驟 才能獲取到物流貨運車的送貨規(guī)律等 特征信息 23 如圖 3 1 為軌跡計算的流程圖 其中軌跡預(yù)處理包括數(shù)據(jù)規(guī)范化 異常點去除等 原始的 GPS 位置信息并不包含停車點信息 停車點識別指的是 從軌跡點中提取停車位置信息 上步中識別出來的停車點信息由于并不包含貨 運車輛的上下貨的位置信息 軌跡分割便是從軌跡中識別出一趟完整的貨運信 息 包括貨運的起點和終點等信息 這是本文的核心部分 最終得到的軌跡輸 出結(jié)果可以用于物流貨運車輛的軌跡推薦 圖 3 1 軌跡計算流程圖 數(shù)據(jù)預(yù)處理 停車點識別 軌跡分割 輸入 輸出 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 12 3 2 軌跡數(shù)據(jù)預(yù)處理 3 2 1 軌跡數(shù)據(jù)特征 使用車輛的海量 GPS 數(shù)據(jù)要面臨的首要問題 是如何發(fā)現(xiàn)和處理大量數(shù)據(jù) 中的異常元素 有很多客觀因素諸如天氣 實時路況 設(shè)備異常會使軌跡數(shù)據(jù) 發(fā)生異常 本文基于某物流公司每天實際的 GPS 數(shù)據(jù)進行了空間分析 包括時 間 速度和位置信息 得出的空間特征和規(guī)律如下 1 數(shù)據(jù)量大 本文中貨運車輛每周產(chǎn)生的數(shù)據(jù)記錄數(shù)約為 4 千萬條 詳 盡的數(shù)據(jù)對分析和挖掘有利 但對后續(xù)的數(shù)據(jù)的分析過程和算法提出了高的要 求 針對此問題 本文基于 Hadoop 分布式 24 平臺以提升 GPS 并行處理的能力 2 數(shù)據(jù)重復(fù) 造成數(shù)據(jù)重復(fù)的原因是多種多樣的 例如當(dāng)車輛處于信號差 的區(qū)域 山區(qū) 隧道等 或者設(shè)備本身異常或者故障導(dǎo)致重復(fù)發(fā)送相同 GPS 數(shù) 據(jù) 車輛停車時也可能會造成 GPS 數(shù)據(jù)發(fā)送重復(fù) 所以 因這對這些數(shù)據(jù)記錄 進行標注并刪除 這樣便可以有效的壓縮減少無效的數(shù)據(jù) 3 數(shù)據(jù)缺失 物流貨運車輛在其運行期間 GPS 接收機設(shè)定的接收時間間 隔一般為 30 秒到 1 分鐘之間 但是由于地理因素 如車輛行駛在山區(qū) 雨雪天 氣 設(shè)備故障等原因 并不能保證每一個路段都有完整的 GPS 信息 甚至?xí)?有一些是錯誤的 GPS 數(shù)據(jù) 這些缺失的數(shù)據(jù)對于獲取和分析軌跡行駛信息造成 的嚴重的影響 這些缺失的數(shù)據(jù)可以通過借助一些地理信息補回 4 GPS 漂移 在 GPS 設(shè)備定位過程中 所標識的位置和用戶實際位置有 一定的出入 常見的現(xiàn)象是實際軌跡和先漂移軌跡混雜在一起 車輛即使實際 原地位置不動的時候產(chǎn)生的經(jīng)緯度信息也是不斷變換的 有很多客觀原因會造 成這種現(xiàn)象 例如 GPS 設(shè)備在長期使用過程中并沒有初始化或者調(diào)校 造成實 際位置和顯示的位置之間有一定的誤差 設(shè)備實時搜到的衛(wèi)星數(shù)量 衛(wèi)星本身 的位置分布等 由于 CPU 處理速度或者算法不夠好 使得車輛在以較快速度行 駛時的 GPS 信號與車輛靜止時候相比較 經(jīng)緯度偏移 目前 GPS 設(shè)備在城市中 定位精度在 10 米左右 偏移在 50 米左右 由于城市道路密集和復(fù)雜 這些偏 移足能夠影響軌跡數(shù)據(jù)分析結(jié)果 使用包含重復(fù) 異常和錯誤的 GPS 數(shù)據(jù)會影響后續(xù)軌跡數(shù)據(jù)挖掘的結(jié)果和 效率 因此對海量 GPS 數(shù)據(jù)中的異常元素進行排除具有很重要的意義 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 13 3 2 2 軌跡數(shù)據(jù)異常點檢測 目前關(guān)于軌跡異常點排除算法大多通過基于劃分 25 統(tǒng)計 26 密度 27 等方 法 基于統(tǒng)計的方法通常是使用一些數(shù)據(jù)在統(tǒng)計學(xué)上的分布特征 例如正態(tài)分 布異常點檢測 如果某個數(shù)據(jù)對象偏離數(shù)據(jù)集均值到閾值則被歸為異常點 該 方法依賴于數(shù)據(jù)的分布 異常點類型等 該方法有堅實的數(shù)理統(tǒng)計理論支撐 然而當(dāng)缺少數(shù)據(jù)分布特征的參數(shù)時 通過一些方法確定分布來擬合也是十分復(fù) 雜低效的 使用劃分的方法是一種常見的聚類分析手段 它通過將所有數(shù)據(jù)聚 類成不同的簇 然后沒有歸類到任何簇的數(shù)據(jù)點則為異常點 該方法的時間和 空間復(fù)雜度低 發(fā)現(xiàn)的異常點可靠性高 例如常使用 K 均值聚類算法將軌跡聚 類 該方法存在的缺點是需要預(yù)先知道聚類數(shù) K 值 聚類中心選取不準可能導(dǎo) 致無法得到正確的分類結(jié)果 密度檢測方式是數(shù)據(jù)挖掘中的常用方法 軌跡數(shù) 據(jù)集中每一條軌跡被投射到不同維度上 然后比較每一塊區(qū)域內(nèi)的密度以及相 鄰區(qū)域大小 密度大的地方軌跡數(shù)據(jù)越趨向正常 密度越小的區(qū)域軌跡為異常 數(shù)據(jù)可能性較大 它存在一個很大的問題就是計算量大 每次必須計算每一點 的鄰域 造成速度慢 此外還有利用路網(wǎng)等 GIS 信息進行道路匹配的思想進行 的異常點檢測 該方法由于需要精確的知道路網(wǎng)信息 此外算法時間和空間復(fù) 雜度高 當(dāng)面臨本文所遇到的海量軌跡數(shù)據(jù)處理的時候難以適應(yīng)在實際生產(chǎn)中 需要快速得到分析結(jié)果的應(yīng)用中 為了快速高效的檢測軌跡中異常點 本文采用了基于網(wǎng)格劃分的思想來對 異常點進行檢測的思想 其算法過程如下 1 將地圖區(qū)域按網(wǎng)格劃分 本文將 GPS 數(shù)據(jù)定義為一個二維平面中的一 個點 iiiplon lat 表示經(jīng)度 ilat表示為緯度 以地球緯度和經(jīng)度作為坐標軸 將包含地圖區(qū)域可以簡單映射為一個二維平面 2 Rlon latlonR latR 然 后 使 用 平 行 于 坐 標 軸 的 直 線 把 地 圖 劃 分 大 小 相 等 的 網(wǎng) 格 maxminmaxmin i Rlonlonlatlat 其中 max lon min lon max lat min lat分別為格子的 上邊界 下邊界 右邊界 左邊界 所劃分得到格子的集合 1231 ii SR R RRR 定 義 一 個 映 射 關(guān) 系 2 F RS 通 過 分 別 對 經(jīng) 緯 度 上 下 取 整 得 iiiii Rceil lonfloor lonceil latfloor lat 其中 i lon和 i lat的精度的不同將會 影響格子的大小 2 計算映射到網(wǎng)格軌跡數(shù)據(jù)點數(shù)量 cnt P 判斷 cnt P是否小于異常點閾值 thre C 如果成立 則該網(wǎng)格內(nèi)的所有數(shù)據(jù)點判為異常點 否則非異常點 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 14 3 對于非異常點的網(wǎng)格 i R 找到網(wǎng)格內(nèi)數(shù)量最大的網(wǎng)格作為第一個類 1 G 計算網(wǎng)格內(nèi)部的中心點 1 cn RRRn 然后找到歐式距離它最遠的網(wǎng)格點 作為第二個類 2 G 4 計算其它網(wǎng)格到初始兩個類的網(wǎng)格的歐式距離 ij d 如果網(wǎng)格距離小于 thre D 則將該網(wǎng)格歸到此類 否則 將其定義為新類 i G 5 獲取沒有被歸類到任何類中的網(wǎng)格 該網(wǎng)格內(nèi)的點既可以被認為異常 點 本算法相比較傳統(tǒng)的劃分方法的異常點檢測有如下優(yōu)點 1 不必事先指 定分類數(shù) K 在不斷的分類迭代中獲取分類數(shù) 2 初始分類中心并不是隨機 生成的 有效避免了只能收斂到局部最優(yōu)的情況 3 可以有效且方便的檢測 出異常點 由于道路一般比較分散 尤其是貨運車輛所行駛的線路 不在網(wǎng)格 內(nèi)的數(shù)據(jù)點既可以判為異常點 4 時間復(fù)雜度低 由于對整個區(qū)域按照網(wǎng)格 劃分計算 所有其時間復(fù)雜度接近于線性復(fù)雜度 當(dāng)分類數(shù)越小時 數(shù)據(jù)越集 中時時間復(fù)雜度越低 本算法的流程圖如圖 3 2 所示 3 3 停車點識別方法研究 軌跡分割就是首先將空間上離散的軌跡點劃分成停車點和移動點兩大類 并且停車點可以劃分為三種類型 第一種主要為在城市道路中由于紅綠燈等待 造成的停車 一般這種停車時間較短 對于軌跡分割沒有意義 第二種由于司 機加油 吃飯 交通擁堵造成的停車 這種停車時間一般較長 對于本文的軌 跡分割有較大影響 第三種為停車卸貨 通過這個停車點可以識別出一趟貨運 線路的起始點位置等信息 在充分考慮了 GPS 數(shù)據(jù)特征的情況下 我們可以依 貨運車的速度信息來判斷是否停車 本文采用了基于速度的停車點算法 該算 法分為 3 個步驟 計算 GPS 點的速度 判斷疑似停車點 停車點點識別 28 1 計算 GPS 點的速度 由于 GPS 的定位精度較準 誤差一般在 10m 到 50m 之間 時間間隔一般為 30s 到 60s 之間 GPS 點的速度可以由相鄰前后 GPS 點連成直線的平均速度來替 代 如圖 3 3GPS 點速度計算示意圖 計算 4 P點的速度公式為 4 3 44 5 3 44 5 p tt dd v 3 1 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 15 圖 3 2 軌跡異常檢測算法流程圖 式3 1中 i j d表示GPS點 i p和 j p之間的位置差 i j t 為 i p和 j p的時間間隔 piv 為 i p時刻的速度 圖 3 3GPS 點速度計算示意圖 否 是 否 是 開始 所有數(shù)據(jù)將地 圖劃分為網(wǎng)格 個數(shù)大于閾值 thre C 初始化類數(shù)K 3 歸類到已有類中 距離大于閾值 thre D 調(diào)整類數(shù)量 網(wǎng)格內(nèi)數(shù)據(jù)為異常點 沒有被分到任何類網(wǎng) 格中的數(shù)據(jù)為異常點 計算網(wǎng)格內(nèi)數(shù)據(jù)點個數(shù) 計算對象到類 的距離 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 16 2 判斷疑似停車點 停車點的判斷需要靠速度閾值來判斷 可以設(shè)置一個速度上限 max v來判斷是 否停車 首先依據(jù) max v將所有的 GPS 點劃分為兩類 疑似停車點和行駛點 并 且由于停車的時候不應(yīng)該只有一個點的速度小于 max v 至少應(yīng)當(dāng)有若干個 形成 一個停車點候選區(qū)域 停車上限 max v可以設(shè)置為人步行的速度約為 1m s 該過程 如示意圖 3 4 所示 其中速度的單位 m s 停車區(qū)域 GPS 點分類 合并停車點 停車區(qū)域 圖 3 4 停車區(qū)域判斷示意圖 3 停車點識別 通過前面計算得到的一系列疑似停車點 可以結(jié)合停車距離的閾值范圍 選擇停車時間最長的疑似停車點作為最終的停車位置 具體算法步驟如下 I 讀取軌跡中的第一個疑似停車點 1 s 將其放入停車點序列Seq中 II 判斷是否還有疑似停車點 2 3 4 5 i s i 如果有則計算這個點與上一 個停車點 1i s 的距離間隔 1 ii d 如果 1 ii d 小于距離閾值 max d 則將該點放 入停車序列Seq中 并重復(fù)步驟II 否則進入步驟III III 計算Seq中的停留起始時間 Seqstart和結(jié)束時間 Seqend 如果停留時間 小于時間閾值 min t 則清空Seq 如果大于 min t 則保留此次停車記錄 通過停車點識別 可以找到物流貨運車的簡單行駛規(guī)律 例如停車地點 逗留時間 但是對于深層次的軌跡信息挖掘這是遠遠不夠的 只能通過對停車 點更深層次的挖掘才能獲取貨運車輛一趟完整的貨運信息 停車點 疑似停車點 疑似停車點 疑似停車點 疑似停車點 行駛點 行駛點 行駛點 疑似停車點 疑似停車點 疑似停車點 停車點 速度 1 p 1 0 2 p 0 6 3 p 0 4 p 0 5 p 5 6 p 10 7 p 12 8 p 0 9 p 0 10 p 0 萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文 17 3 4 軌跡分割方法研究 3 4 1 貝葉斯分類器概述 軌跡數(shù)據(jù)挖掘中 如何對軌跡數(shù)據(jù)集合分類是一個重要問題 準確的分類 是后續(xù)軌跡分析的基礎(chǔ) 分類是從數(shù)據(jù)集合中提取描述數(shù)據(jù)類中重要屬性的過 程 通過分類可以更深入了解數(shù)據(jù)特征 機器學(xué)習(xí)中已經(jīng)有很多種分類方法 例如模式識別和統(tǒng)計學(xué)方法 傳統(tǒng)的分類方法中都是基于較小的數(shù)據(jù)規(guī)模 近 年來隨著大數(shù)據(jù)越來越受到科研界的重視 逐漸發(fā)展出來一些針對海量數(shù)據(jù)分 類的技術(shù) 分類器可以用來判定一個未知的數(shù)據(jù)歸于哪一類 例如在軌跡數(shù)據(jù) 挖掘中 當(dāng)進行軌跡分割的時