資源描述：
《基于海量物流軌跡數(shù)據(jù)的分析挖掘系統(tǒng)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
武漢理工大學(xué)碩士學(xué)位論文AbstractIntheageoftheelectroniccommerce,theelectroniccommerce,logisticsindustry,logisticsvehiclesaremoreprosperitythanever.MoreandmorelogisticsvehiclesGPSdataareproduced.Thesedatacontainalotoftrafficinformationsuchasroadconditions,vehicles,andevensocialandeconomicdevelopment.Throughstatisticsandanalysisofvehicledrivingdistance,time,location,vehicleparkingcharacteristics,trajectorydataminingcanfindshippinglinecharacteristics,providelogisticscompanybasedonvehicleschedulingschemessuchastime,cost,andderivedaseriesofLBSapplication.TakingmassiveGPSdataasthedatasource,usingmassivetrajectorydataminingandrelatedtheoryofroadrecommending,composedbyonlineandofflinesystem,thispaperproposesandrealizesadesignframeworkofrouterecommendingsystemforlogisticsvehiclethroughestablishingclusteringmodelandanalyzingmassiveGPSdatatounderstandthedrivingruleoflogisticsvehicles.Thekeyapproachisdeepstudyingondatapreprocessing,stopsdetecting,routesegmenting,similarfreighttrajectoryclusteringandfreightlinesrecommending.Thespecificworkisasfollows:Asanecessaryworkintrajectorydatamining，istudythepretreatmentmethod,includingdatacleaning,dataofabnormaldetectionandexclusion,andwiththecharacteristicsofthissystemalltheGPSdatainanalysisandputforwardakindofanomalydetectionalgorithmbasedonthehistoricaltrajectorydata.Thealgorithmformassivedataprocessinghaslowtimecomplexity.Parkingpointsdetectionandpathintegralcanfindthatthepatternoflogisticsvehiclesandgoods.Inthispaper,onthebasisofnaivebayesalgorithm,iputforwardanewwayfortrajectorysegmentation,accordingtothelogisticsvehicleparkingandordinaryponitsusingthedifferentattributesoftimeandspacebetweenthemwhengoodsareloadedandunloaded.Iregulatefreighttrajectoriesclusteringsimilartothesamestartingpointandendpointofthetrajectory.thenprojectthemonthesamelatitude.Afterthatusingk-meansalgorithm,thecharacteristicoftrajectoryisanalyzed,andfinallygetII萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文logisticsvehiclegeneralmovementtracks.Intherecommendationofshippinglines,basedonthedifferenceofhistoricaltrajectorydataintime,distanceandcost,idesignanddrawthecorrespondingrecommendedrouteguidancewhichlogisticsdriveradoptsthroughreasonabledrivingscheme.Comparedwithtraditionalpretreatmentmethod.Thesetestsshowthatthemethodofpretreatmenttrajectoryisfaster,moreefficient,butsacrificingsomeprecision.Detectingparkingspotsandtracksegmentationachievegoodeffects.Inthecasesofmissingstopsofvehicletrajectoryanalysis,theresearchresultshaveveryimportanttheoreticalsignificance.Keywords:bayesianclassifier,trajectorydatamining,carving,abnormalpointfilter,k-meansclusteringIII萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文目錄摘要.................................................................................................................................IAbstract...............................................................................................................................II目錄................................................................................................................................IV第1章緒論.....................................................................................................................11.1課題來源..............................................................................................................11.2研究的背景和意義..............................................................................................11.3國內(nèi)外研究現(xiàn)狀..................................................................................................21.4論文內(nèi)容和組織結(jié)構(gòu)..........................................................................................4第2章軌跡數(shù)據(jù)挖掘技術(shù)研究.....................................................................................52.1軌跡數(shù)據(jù)挖掘介紹..............................................................................................52.1.1軌跡數(shù)據(jù)挖掘概念...................................................................................52.1.2軌跡數(shù)據(jù)挖掘內(nèi)容...................................................................................52.2軌跡數(shù)據(jù)挖掘流程..............................................................................................62.2.1數(shù)據(jù)來源和預(yù)處理...................................................................................62.2.2軌跡數(shù)據(jù)路徑分割和聚類分析...............................................................82.3基于歷史軌跡的線路推薦服務(wù)..........................................................................92.4本章小結(jié)............................................................................................................10第3章軌跡數(shù)據(jù)預(yù)處理和軌跡分割方法研究...........................................................113.1軌跡計算流程....................................................................................................113.2軌跡數(shù)據(jù)預(yù)處理................................................................................................123.2.1軌跡數(shù)據(jù)特征.........................................................................................123.2.2軌跡數(shù)據(jù)異常點檢測.............................................................................133.3停車點識別方法研究........................................................................................143.4軌跡分割方法研究............................................................................................173.4.1貝葉斯分類器概述.................................................................................173.4.2構(gòu)造停車點訓(xùn)練集.................................................................................183.4.3基于樸素貝葉斯分類器的停車點分類.................................................203.5本章小結(jié)............................................................................................................23IV萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文第4章海量軌跡數(shù)據(jù)聚類算法研究.............................................................................244.1軌跡聚類的意義和問題....................................................................................244.2軌跡表達和相似性度量....................................................................................254.2.1軌跡規(guī)則化.............................................................................................254.2.2軌跡相似性度量.....................................................................................304.3軌跡聚類............................................................................................................324.3.1常見聚類算法比較.................................................................................324.3.2基于-均值算法的軌跡聚類.................................................................334.4基于GPS數(shù)據(jù)的線路推薦方法.......................................................................354.5本章小結(jié)............................................................................................................37第5章系統(tǒng)驗證和結(jié)果分析.........................................................................................385.1實驗基礎(chǔ)和條件................................................................................................385.2系統(tǒng)實現(xiàn)與驗證................................................................................................385.2.1數(shù)據(jù)預(yù)處理.............................................................................................385.2.2停車點識別.............................................................................................395.2.3軌跡分割.................................................................................................425.2.4軌跡聚類..................................................................................................43第6章工作總結(jié)和展望.................................................................................................446.1本文工作總結(jié)....................................................................................................446.2下一步工作展望................................................................................................44致謝.................................................................................................................................46參考文獻...........................................................................................................................48作者在攻讀碩士學(xué)位期間發(fā)表的專利...........................................................................51V萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文第1章緒論1.1課題來源中科院深圳先進技術(shù)研究所和深圳市宇易通科技有限公司合作開發(fā)設(shè)計的一個易流云平臺系統(tǒng)，該平臺旨在為物流企業(yè)提供真實物流信息服務(wù)的真實運力服務(wù)。1.2研究的背景和意義當今社會屬于互聯(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ā)送當前位置，這些移動在全國各地路網(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è)、交通路1萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文徑規(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)角度多種、知識[3]表示困難等技術(shù)難點。軌跡數(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)當根據(jù)不同的需求采用不同的工具、方法以及理論。目前的軌跡數(shù)據(jù)挖掘研究工作中主要為軌跡聚類、軌跡分類、離群點檢測、興趣區(qū)域、隱私保護、位置推薦等方面。作為軌跡挖掘重要的一部分：異常軌跡檢測中，也已經(jīng)提出了許多算法。傳統(tǒng)的軌跡異常檢測中，通常是提取軌跡[4]某些特征，計算這些特征間的差值再進行加權(quán)得到軌跡間的距離?？酥Z爾通過將軌跡分解、降低維數(shù)得到若干個包含主要軌跡有用信息并且相互獨立的特征,如軌跡所包含的GPS點的數(shù)量、軌跡運動快慢、軌跡起始點的坐標位置、軌跡運動趨勢等。通過檢測的異常和正常軌跡數(shù)據(jù)路徑的距離不同，以確定其缺陷的異常信息，它的缺陷在于:由于軌跡內(nèi)部不同局部區(qū)域也存在特征上的差異,因2萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文[5]此上述方法只適用于特征單一或者長度較短的軌跡。伊利諾伊大學(xué)的Li建議構(gòu)建了一種軌跡異樣檢查框架ROAM。該框架將首先通過軌跡離散化分成一個個獨立的名為Motif的片段，該片段提取軌跡的某些特征信息構(gòu)成Motif特征空間，利用構(gòu)建的Motif中的屬性信息，這個分類器最終用于將不同軌跡數(shù)據(jù)分類從而獲取軌跡背后蘊藏的知識。為了克服傳統(tǒng)軌跡中無法針對軌跡較長或者特征較復(fù)雜進行有效的檢測。[6]劉良序首先通過不同軌跡間的相似程度的不同提出了部分相似、完全相似和離群軌跡的模型，將一段較長的軌跡分為若干獨立無關(guān)的軌跡段，利用之前定義的模型和概念，然后比較每一個分段之間的匹配程度，設(shè)定不同閾值來確定這些較長的軌跡是否相似，并且使用了R樹來來克服計算量過大的問題。也有一些科研人員通過數(shù)據(jù)挖掘中的密度聚類思想，密度越大的地方，軌跡越趨向于[7]正常軌跡，密度越小的地方軌跡越有可能為異常軌跡，譬如Liu。軌跡聚類是在相似的軌跡中找到不相似部分的過程。軌跡特征空間中不同密度代表不同軌跡在該屬性上相似程度的不同，并且特征空間中不同的屬性對[8]軌跡相似程度的影響也各不相同。不同軌跡從時間區(qū)間這個角度來看，其相似性也各有不同，本文從時間間隔出發(fā)，將不同聚類方法分為如下幾類，如表1-1所示。這些方法逐漸在相似的時間間隔從時間上的要求相似性，本地時間間隔相似，最后到?jīng)]有時間對應(yīng)的相似性下降。它反映了人們在時間和空間探索時空軌跡和軌跡相似性度量的多樣性。表1-1軌跡聚類方法分類列表相似性度量代表聚類方法[9][10]全區(qū)間時間相似歐式距離，最小外接矩形距離[11]全區(qū)間變換對應(yīng)相似動態(tài)時間規(guī)整[12]多子區(qū)間對應(yīng)相似最長公共子序列距離[13]單子區(qū)間對應(yīng)相似子軌跡聚類[14]單點對應(yīng)相似歷史最近距離[15]無時間區(qū)間對應(yīng)相似單向距離目前有關(guān)軌跡數(shù)據(jù)挖掘的研究主要關(guān)注在軌跡的時空特性上，已經(jīng)建立了一些關(guān)于軌跡數(shù)據(jù)建模、數(shù)據(jù)存儲、軌跡索引、軌跡查詢、軌跡挖掘方面，但3萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文[16]是有關(guān)軌跡的語義信息的理論研究卻并不多，Yan等人提出了面向軌跡數(shù)據(jù)語義信息分析與挖掘，獲取物體有關(guān)運動的未知知識，這些知識是軌跡挖掘更深層次的應(yīng)用。在目前云計算和大數(shù)據(jù)的時代下，只有對軌跡數(shù)據(jù)挖掘進行更深入分析和挖掘，研究物流系統(tǒng)模仿或者實現(xiàn)人類的在不同諸如天氣、實時路況等諸多客觀因素下的行為，具備模仿人的智能，學(xué)習(xí)推斷并自適應(yīng)解決出現(xiàn)在物流運輸、存儲的問題的能力，也就是當商品從出庫、車輛中轉(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ù)挖掘的展望。4萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文第2章軌跡數(shù)據(jù)挖掘技術(shù)研究2.1軌跡數(shù)據(jù)挖掘介紹2.1.1軌跡數(shù)據(jù)挖掘概念軌跡數(shù)據(jù)挖掘（TrajectoryDataMining）是數(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ù)[17]據(jù)庫、內(nèi)存數(shù)據(jù)庫、批處理數(shù)據(jù)處理框架、實時流計算框架等。一般而言，軌跡數(shù)據(jù)挖掘，是指從大量軌跡數(shù)據(jù)的集合C中發(fā)現(xiàn)隱含模式m和知識n的結(jié)果S。因此，軌跡數(shù)據(jù)挖掘的過程可以看作為一個函數(shù)：[18]￡:C→S（m,n），（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ū)分開來。5萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文軌跡數(shù)據(jù)挖掘異常點檢測軌跡聚類軌跡分類位置推薦圖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ī)劃效率，在當今越來越開放的網(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ù)的特征采用不同過濾算法。6萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文（1）挖掘數(shù)據(jù)來源軌跡數(shù)據(jù)挖掘來源通常是終端設(shè)備上產(chǎn)生的位置記錄，然后位置信息傳回數(shù)據(jù)中心以日志文件形式存放。本文采用的是數(shù)據(jù)中心的GPS日志記錄。表2-1是GPS日志的記錄表結(jié)構(gòu)。表2-1GPS日志記錄表結(jié)構(gòu)屬性域描述車輛編號車輛的唯一編號經(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-120: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)7萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文隱藏或者突發(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)異常軌跡，密度大的[19]區(qū)域的軌跡趨向于正常軌跡，密度小的區(qū)域的軌跡趨向于異常軌2.2.2軌跡數(shù)據(jù)路徑分割和聚類分析通過GPS設(shè)備獲取的軌跡數(shù)據(jù)只包含每一軌跡點的經(jīng)緯度和對應(yīng)的時刻信息，通過這些數(shù)據(jù)無法直接得到活動行為的特征信息，如停車時間、是否卸貨、物流的目的地、以及其他信息。要想獲取這些信息首先就必須進行停車點偵測，判斷是那些時刻是真實停車，還是GPS產(chǎn)生了漂移誤差，或是由于紅綠燈、交通擁堵造成的停車，或者是停車卸貨等一系列重要信息和知識。圖2-2為停留點偵測示意圖。軌跡分割是軌跡數(shù)據(jù)挖掘的基礎(chǔ)和前提，目前，軌跡分割算法有探索和機[20]器學(xué)習(xí)方法兩大類。探索性方法考慮移動對象停留和移動時的時空特征或定位設(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ò)，支持向量[21]機學(xué)習(xí)，聚類，貝葉斯網(wǎng)絡(luò)等。聚類的目的是嘗試將具有相似特征的軌跡劃分開來，凸顯不同軌跡間的相似性，為更深層次的研究打下基礎(chǔ)?？梢詫④壽E特征空間中不同屬性相互獨立8萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文[22]抽取出來，找到每一個被劃分的屬性與整體分布特征之間的關(guān)系。根據(jù)相似度量的不同，常見的基于距離軌跡聚類方法有基于歐氏距離、最長公共子序列距離、時間聚焦距離、歷史最近距離等。軌跡停留點點停留區(qū)域行駛路徑圖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)新增，變更，刪除，不準的狀況?；跉v史軌跡的路線推薦系統(tǒng)由于是考慮了實際需求，由于是司機駕駛的實際路徑結(jié)果，包含了司機對真實地理天氣和道路綜合考慮的結(jié)果，因此推薦的線路也更合理、更多樣，可以基于最少時間、最少費用，也可以最9萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文短路徑等?；跉v史軌跡的線路推薦服務(wù)的一般結(jié)構(gòu)如圖2-3所示。它是依賴聚類結(jié)果，包含基礎(chǔ)的數(shù)據(jù)處理并挖掘相關(guān)知識。包括數(shù)據(jù)采集、數(shù)據(jù)預(yù)處理、數(shù)據(jù)分析。GPS記錄日數(shù)軌軌推志預(yù)預(yù)處理跡跡薦用戶空間數(shù)據(jù)庫處后GPS分聚算理記錄割類法用戶信用級算算服務(wù)別法法器數(shù)據(jù)預(yù)處理模塊數(shù)據(jù)挖掘模塊推薦系統(tǒng)模塊理模塊圖2-3基于歷史軌跡的線路推薦服務(wù)一般結(jié)構(gòu)2.4本章小結(jié)本章細述了軌跡數(shù)據(jù)挖掘的基本流程：數(shù)據(jù)源的獲取，數(shù)據(jù)預(yù)處理，軌跡分割、軌跡聚類，推薦服務(wù)。對基于歷史軌跡的線路推薦服務(wù)系統(tǒng)做了分析，說明了使用的聚類算法和推薦算法，根據(jù)數(shù)據(jù)挖掘的知識完成貨運線路推薦功能。10萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文第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é)果可以用于物流貨運車輛的軌跡推薦。輸入數(shù)據(jù)預(yù)處理停車點識別軌跡分割輸出圖3-1軌跡計算流程圖11萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文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ù)的分析過程和算法提出了高的要[24]求。針對此問題，本文基于Hadoop分布式平臺以提升GPS并行處理的能力。（2）數(shù)據(jù)重復(fù)。造成數(shù)據(jù)重復(fù)的原因是多種多樣的,例如當車輛處于信號差的區(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í)幸恍┦清e誤的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ù)中的異常元素進行排除具有很重要的意義。12萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文3.2.2軌跡數(shù)據(jù)異常點檢測[25][26][27]目前關(guān)于軌跡異常點排除算法大多通過基于劃分、統(tǒng)計、密度等方法。基于統(tǒng)計的方法通常是使用一些數(shù)據(jù)在統(tǒng)計學(xué)上的分布特征，例如正態(tài)分布異常點檢測，如果某個數(shù)據(jù)對象偏離數(shù)據(jù)集均值到閾值則被歸為異常點。該方法依賴于數(shù)據(jù)的分布、異常點類型等，該方法有堅實的數(shù)理統(tǒ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ù)雜度高，當面臨本文所遇到的海量軌跡數(shù)據(jù)處理的時候難以適應(yīng)在實際生產(chǎn)中需要快速得到分析結(jié)果的應(yīng)用中。為了快速高效的檢測軌跡中異常點，本文采用了基于網(wǎng)格劃分的思想來對異常點進行檢測的思想。其算法過程如下：（1）將地圖區(qū)域按網(wǎng)格劃分。本文將GPS數(shù)據(jù)定義為一個二維平面中的一個點pi?{lonlati,i}，表示經(jīng)度，lati表示為緯度。以地球緯度和經(jīng)度作為坐標軸2??將包含地圖區(qū)域可以簡單映射為一個二維平面R{(lonlatlonRlat,)|??,R}。然后使用平行于坐標軸的直線把地圖劃分大小相等的網(wǎng)格R?{lon,lon,lat,lat}，其中l(wèi)on、lon、lat、lat分別為格子的imaxminmaxminmaxminmaxmin上邊界、下邊界、右邊界、左邊界，所劃分得到格子的集合S?{,RRR,...R,}R。123ii?12定義一個映射關(guān)系FR:?S，通過分別對經(jīng)緯度上下取整得R?{ceillon(),floorlonceillat(),(),floorlat()},其中l(wèi)on和lat的精度的不同將會iiiiiii影響格子的大小。（2）計算映射到網(wǎng)格軌跡數(shù)據(jù)點數(shù)量P。判斷P是否小于異常點閾值cntcntC，如果成立，則該網(wǎng)格內(nèi)的所有數(shù)據(jù)點判為異常點，否則非異常點。thre13萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文（3）對于非異常點的網(wǎng)格R，找到網(wǎng)格內(nèi)數(shù)量最大的網(wǎng)格作為第一個類G，i1計算網(wǎng)格內(nèi)部的中心點R?(R??...R)/n，然后找到歐式距離它最遠的網(wǎng)格點cn1作為第二個類G。2（4）計算其它網(wǎng)格到初始兩個類的網(wǎng)格的歐式距離d。如果網(wǎng)格距離小于ijD，則將該網(wǎng)格歸到此類，否則，將其定義為新類G。threi（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ù)雜度，當分類數(shù)越小時，數(shù)據(jù)越集中時時間復(fù)雜度越低。本算法的流程圖如圖3-2所示。3.3停車點識別方法研究軌跡分割就是首先將空間上離散的軌跡點劃分成停車點和移動點兩大類，并且停車點可以劃分為三種類型，第一種主要為在城市道路中由于紅綠燈等待造成的停車，一般這種停車時間較短，對于軌跡分割沒有意義。第二種由于司機加油、吃飯、交通擁堵造成的停車，這種停車時間一般較長，對于本文的軌跡分割有較大影響。第三種為停車卸貨，通過這個停車點可以識別出一趟貨運線路的起始點位置等信息。在充分考慮了GPS數(shù)據(jù)特征的情況下，我們可以依貨運車的速度信息來判斷是否停車，本文采用了基于速度的停車點算法。該算[28]法分為3個步驟，計算GPS點的速度，判斷疑似停車點，停車點點識別。（1）計算GPS點的速度由于GPS的定位精度較準，誤差一般在10m到50m之間，時間間隔一般為30s到60s之間。GPS點的速度可以由相鄰前后GPS點連成直線的平均速度來替代。如圖3-3GPS點速度計算示意圖。計算P點的速度公式為：4dd?3,44,5v?p4（3-1）???tt3,44,514萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文開始所有數(shù)據(jù)將地圖劃分為網(wǎng)格計算網(wǎng)格內(nèi)數(shù)據(jù)點個數(shù)否個數(shù)大于閾值Cthre是初始化類數(shù)K-3調(diào)整類數(shù)量計算對象到類的距離否距離大于閾值Dthre是歸類到已有類中沒有被分到任何類網(wǎng)網(wǎng)格內(nèi)數(shù)據(jù)為異常點格中的數(shù)據(jù)為異常點圖3-2軌跡異常檢測算法流程圖式3-1中d表示GPS點p和p之間的位置差?為p和p的時間間隔，vij,ijtij,ijpi為p時刻的速度。i圖3-3GPS點速度計算示意圖15萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文（2）判斷疑似停車點停車點的判斷需要靠速度閾值來判斷，可以設(shè)置一個速度上限v來判斷是max否停車，首先依據(jù)v將所有的GPS點劃分為兩類，疑似停車點和行駛點，并max且由于停車的時候不應(yīng)該只有一個點的速度小于v，至少應(yīng)當有若干個。形成max一個停車點候選區(qū)域。停車上限v可以設(shè)置為人步行的速度約為1m/s。該過程max如示意圖3-4所示。其中速度的單位m/s。停車點速度停車點p11.0疑似停車點p20.6疑似停車點停車區(qū)域p30疑似停車點p40疑似停車點p55GPS點分類行駛點合并停車點p610行駛點p12行駛點7p80疑似停車點停車區(qū)域p90疑似停車點p100疑似停車點圖3-4停車區(qū)域判斷示意圖（3）停車點識別通過前面計算得到的一系列疑似停車點，可以結(jié)合停車距離的閾值范圍，選擇停車時間最長的疑似停車點作為最終的停車位置。具體算法步驟如下：I.讀取軌跡中的第一個疑似停車點s，將其放入停車點序列Seq中。1II.判斷是否還有疑似停車點si(?2,3,4,5...)，如果有則計算這個點與上一i個停車點s的距離間隔d，如果d小于距離閾值d，則將該點放i?1ii?1,ii?1,max入停車序列Seq中，并重復(fù)步驟II，否則進入步驟III。III.計算Seq中的停留起始時間Seqstart.和結(jié)束時間Seqend.，如果停留時間小于時間閾值?，則清空Seq，如果大于?，則保留此次停車記錄。tmintmin通過停車點識別，可以找到物流貨運車的簡單行駛規(guī)律，例如停車地點，逗留時間，但是對于深層次的軌跡信息挖掘這是遠遠不夠的，只能通過對停車點更深層次的挖掘才能獲取貨運車輛一趟完整的貨運信息。16萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文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ù)挖掘中，當進行軌跡分割的時候就需要判斷哪些點屬于停車點，哪些點屬于卸貨點，這就是分類問題的一個典型應(yīng)用。數(shù)據(jù)分類過程可以分為兩步，第一步是學(xué)習(xí)，也就是構(gòu)造分類模型，第二部是分類，就是利用第一步產(chǎn)生的分類器對未知數(shù)據(jù)進行分類。第一步中，通過描述已經(jīng)帶有類型信息的數(shù)據(jù)集合來構(gòu)造分類器，這被稱為訓(xùn)練階段，例如，一個數(shù)據(jù)由向量X組成，其有n維屬性組成X?{,,...}xxxx,123n整個數(shù)據(jù)集由C?{,,...}xxxx組成。每一個數(shù)據(jù)X都已經(jīng)歸屬于特定的類屬性123nAAA,,,...A其中每一類屬性A都是離散值并且無序。由數(shù)據(jù)X組成的集合被123nii稱為訓(xùn)練集，并且每一份數(shù)據(jù)都是隨機抽樣生成。由于數(shù)據(jù)類型已知，這一步被稱為有監(jiān)督學(xué)習(xí)，與此對應(yīng)的是無監(jiān)督學(xué)習(xí)，數(shù)據(jù)集合中的數(shù)據(jù)類型未知。這一步分類過程可以視為學(xué)習(xí)一個這樣的映射或函數(shù)關(guān)系y?fx()，其中，x代表屬性，y代表類型，從這個角度來看我們希望獲取實際的這個映射關(guān)系f.通常，這種映射關(guān)系以分類規(guī)則、決策樹或者數(shù)學(xué)方程的形式展現(xiàn)。在停車點類型判斷中，這個映射關(guān)系就是一個可以判斷某一個停車點為卸貨點還是普通停車點，并且被用于對未知數(shù)據(jù)進行判斷。在第二步中利用第一步生成的分類器對數(shù)據(jù)進行分類，首先分類器的準確性是需要考慮的問題，如果使用訓(xùn)練集來評估準確性，顯然可以得到非常理想的結(jié)果,因為分類器傾向于擬合這些數(shù)據(jù)，因此必須考慮使用測試數(shù)據(jù)集來評估分類器的準確性，這些測試數(shù)據(jù)集和訓(xùn)練集之間是相互獨立的。分類器的準確性由測試數(shù)據(jù)集中有多大比例數(shù)據(jù)被正確分類決定，如果一個分類器的正確性在可以接受的范圍，該分類器便可以對未知數(shù)據(jù)集進行分類，否則得迭代生成新的分類器。因此分類器的質(zhì)量受到了訓(xùn)練集數(shù)量和質(zhì)量、數(shù)據(jù)特征空間選取等多方面影響。17萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文貝葉斯分類器是一種統(tǒng)計學(xué)分類器，它能預(yù)測給定數(shù)據(jù)屬于哪一種類型的概率，貝葉斯理論的基礎(chǔ)是貝葉斯公式。在該公式中X是數(shù)據(jù)本身，通常假設(shè)其有n維屬性，將H設(shè)為X屬于某一特定類型C的假設(shè)，在分類問題中，我們想要求出的是PHX(|),也就是已知X的情況下，它屬于類型C的概率大小，這種概率被稱為后驗概率，與此對應(yīng)的是先驗概率PH(),在軌跡數(shù)據(jù)停車點類型判斷中該概率即為所有停車點集合中卸貨點的概率。與此類似PHX(|)是已知假設(shè)H的情況下是X的概率。綜上貝葉斯公式即為PXHPH(|)()[29]PXH(|)?（3-2）PX()[30-31]樸素貝葉斯分類是一種十分簡單的分類算法，在不考慮類型之間的關(guān)系時候，它是一種最小錯誤率分類器。樸素貝葉斯分類器的基本思想是在待分類項已知的情況下，求解其歸屬每一種類型的后驗概率，具有最大后驗概率的類型時便可以將待分類項判定為該類，圖3-5即為樸素貝葉斯分類器流程圖。其基本流程：（1）由訓(xùn)練數(shù)據(jù)X?{,,...}xxxx組成的訓(xùn)練集，并且X的類型已知，x為123niX一個特征屬性。（2）設(shè)有n種類別的集合C?{,CCCC,...}。分類器判斷具有最大后驗概123n率的X歸屬類型，也就是X歸屬為C的條件為PCX(|)?PC(|X)，其中iij1??jm。3.4.2構(gòu)造停車點訓(xùn)練集貨運車輛停車有多種原因，例如紅綠燈、交通擁堵、司機休息交接、停車裝運貨物、停車卸載貨物等一系列人為和非人為因素。其中裝貨點和卸貨點是各家物流公司及司機綜合考慮了時間、距離、成本等要素的結(jié)果。對于后面的貨運線路優(yōu)化、推薦有重要指導(dǎo)作用。本文所使用的軌跡數(shù)據(jù)中不包含裝卸貨信息，因此缺乏足夠的裝卸貨的先驗知識和訓(xùn)練集。通過計算停車時間等或者行駛距離等方法來從一系列的停車點中識別出裝卸貨點，忽略了這些連續(xù)停車點之間相互的關(guān)聯(lián)關(guān)系。例如，假如有在一條歷史軌跡中存在相鄰兩個停車點。并且停車時間也相近，距離上一個停車點也經(jīng)歷了較長的距離和時間。分類器必須對這兩個停車點識別分類的時候，如果通過上述間隔時間和距離的判斷方法，則會將第一個停車點識別為裝卸貨點。18萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文準備工作階段確定特征屬性獲取訓(xùn)練樣本分對每個類別計算類器P（）對每個特征屬性訓(xùn)計算所有劃分的練條件概率階段對每個類別計算PCX(|)為最大iPC(|X)j應(yīng)用階段圖3-5樸素貝葉斯分類器流程圖為了解決上述問題，本文采用了數(shù)據(jù)挖掘和機器學(xué)習(xí)的方法來完成了算法設(shè)計。具體流程是從歷史軌跡中發(fā)現(xiàn)貨運車輛裝卸貨的時空特征，獲取車輛停車時間長度和停車點相鄰距離等先驗知識，有了足夠的先驗知識以后，就可以依據(jù)這些先驗知識預(yù)測車輛下一次停車裝卸貨時間和地點。先驗知識的準確度將會影響分類器的效果，具體到本文的軌跡數(shù)據(jù)該先驗知識可以從物流貨運車里程和停車時間觀測獲得。一般而言，同一類型物流貨運車裝卸貨一般所消耗的時間?和一次運輸所行駛的里程v一般為一個趨向于一個常數(shù)，這是因為物流貨運車司機駕駛習(xí)慣、所行駛的線路相對固定，有的車輛偏向于短途、有的偏向于長途等。本文首先使用停車點時間間隔和空間間隔的特征，找到確信的一趟貨運線路的起點或者終點，依據(jù)物流行業(yè)的經(jīng)驗，一輛車停車時間在2個小時以上基本可以判斷為裝卸貨，由于起點和終點在停車時間角度上基本上是一樣的，可以將這兩種停車時間看作一種類型。基于此本文提出了簡單停車點識別算法。具體算法步驟為依次讀取通過上文中停車點識別獲取的停車點信息，如果相鄰19萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文停車點的距離大于v,停車時間閾值?,則該停車點為起始點。算法描述如maxmax下，式中GPS數(shù)據(jù)點r?{,tlonlatodm,,},t表示GPS發(fā)射時刻，lon,lat表示iiiiiiii此時刻的經(jīng)緯度，odm表示此時刻物流車的總的行駛里程。停車點ivs?{lonlatodmttprevdis,,,,,},其prevdis相鄰兩次停車點的里程間隔，t為停iiiisiiisi車起始時刻，t為停車時長。rs代表停車點，cs代表普通停車點。本算法的本iiii質(zhì)是將每一個貨運車輛的停車點分為起止停車點或者普通停車點。本文提出的簡單停車點識別方法如算法3-1所示。停車時間設(shè)置足夠長的時候上述算法可以正確識別出起止停車點和普通停車點。然而對于相鄰距離較近的停車點或停車時間不夠長的點卻無法區(qū)分。對于剩余難以分類的停車點，本文采用了梯度下降法的算法來識別它們在停車時長的區(qū)別。經(jīng)過了簡單距離和時間的識別算法后，剩余的起止點構(gòu)成集合RS，其余的普通停車點構(gòu)成CS。由于每輛車行駛的路徑，司機駕駛習(xí)remainremain慣相對固定，所有最終真實的起止點時間?會收斂到?，所以當計算RS中maxremain的每次起止點停車時間與?的時候,如果?足夠小，那么?就是該輛車的起止停車點的停車時長。然而?顯然無法從原始軌跡中直接獲取，本文采用梯度下降法逐步將?減小，最終將起止點停車時間收斂至?。????||RSt（3-3）remainii本文提出算法如下算法3-2所示。該算法從函數(shù)Interval的初值?出發(fā)，并init考慮如下序列???,,,...,?使得?????，可以得到123optimumii?1?Interval()??Interval()??Interval()...??最終可以順利收斂到?。上述算法123optimum中IntervalVS({},)?的具體實現(xiàn)如算法3-3所示下。從算法3-3易看出當?初始值很大時，這樣起止點集合RS將為空，?為所initi有停車點時間長度之和，隨著?沿著?逐漸減小，其?也會隨之減小。然后下i?降到期望值附近以后可能會'之字型'下降，最終收斂到?。optimum綜上，本文首先通過簡單判斷方法依據(jù)停車時間長度?和停車點之間的間max隔v初步獲取了最可靠的起止停車點集合RS，然后使用梯度下降法完成了對maxi起止停車最優(yōu)時長?的計算，然后依據(jù)該最優(yōu)值去分析停車點類型，構(gòu)造訓(xùn)optimum練集。3.4.3基于樸素貝葉斯分類器的停車點分類樸素貝葉斯分類器是基于貝葉斯定理的一類分類器，貝葉斯定理如下20萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文dPY()?PXY(i|)1PYX(|)?（3-4）PX()式3-4中Y是類別變量，X?{,}xx是待分類的特征向量。具體到本文中；12X?{,}xx中的x?vsprevdis.,即停車點之間的距離，x?vst，即停車時長。121i2iiiY?{,yy}有兩種類別，y?0代表普通停車，y?0代表起止點停車。停車點1212分類問題可以描述為對某一類別X求其argmax((PY?yX|))，然后依據(jù)其概率i值判斷X的類別。InputVS?{vsvsvs,,...vs},一條軌跡中的停車點集合123nv,相鄰?fù)＼圏c的距離閾值max?,停車時間閾值maxOutputRS?{rsrsrs,,...rs}起止點集合123n1CS?{cscscs,,...cs}普通停車點集合123n2Procedureprevdis?,10,20,n?n?RS?nullCS,?nullfori?1;i?ni;??dovsprevdis..??vsodmprevdis;iiiifvsprevdisv.??andvst?thenimaxiiimaxprevids?vsodm.irs?vsni1RSaddrs:()n1nn1??11elsecs?vsni2CSaddcs:()n2nn2??21endifendforreturnVSRSCS{,,}算法3-1簡單停車點識別算法21萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文InputVS?{VS,...VS}多條軌跡中集合,?,停車時間長度?，為迭代步長1ninit?Output?最優(yōu)起止點停車時長,CS?{cscscs,,,...,cs}普通停車點集optimum123n2Procedurewhile???optimuminit???curoptimum???IntervalVS({},)1cur???IntervalVS({},??)2cur????IntervalVS({},??)3cur???argmin{,,}???optimun123endwhilereturn?optimum算法3-2復(fù)雜停車點識別算法InputVS?{VSVSVSVS,,...}多條軌跡中集合,?預(yù)測起止點停車時間長度123nOutput?起止點停車時間與預(yù)測時間的差值Procedure??nullfori?1;i?ni;??do{VSRSCS,,?NaiveMethodVSv(,,?)}iiiimaxmaxifRS?nulltheni????|VSallt.|iielse{RS,CS?removeVSRSCS(,,)}remainremainiii????||RStremainiiendifreturn?算法3-3函數(shù)IntervalVS({},)?具體實現(xiàn)22萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文在一個給定的訓(xùn)練集中，顯然PY()可以通過觀察或者計算得出，然而訓(xùn)練集的構(gòu)造需要一些簡單辦法難以區(qū)分的停車點，假設(shè)有n個起止停車點，n個pc普通停車點，n個簡單辦法難以區(qū)分的停車點，然后通過樸素貝葉斯方法識別h出來的n個起止停車點，普通停車點的概率為式3-5所示，起止停車點概率如r3-6所示n??nnchrPY()??y（3-5）1n??nnpchnn?prPY()??y（3-6）2n??nnpch由于x和x是連續(xù)型變量，可以設(shè)其為正態(tài)分布，因此122??()xi?ij212?ijPX(?xY|?y)?exp（3-7）iii2??ij其中?為X的均值，?為訓(xùn)練集中的方差，Xy?。ijiijij樸素貝葉斯是一種簡單的統(tǒng)計學(xué)概率的分類器，它的基礎(chǔ)理論是貝葉斯定理，假定類之間屬性是相互獨立的，分類效果極其穩(wěn)定，在本文的停車點判斷，停車時間長度和車輛行駛距離是相互獨立的。由于類條件密度的估計是基于所有的數(shù)據(jù)集，所以有很強的抗孤立噪聲的能力，若干個停車點的噪聲錯誤都最終被整個數(shù)據(jù)集平均化了。當一條軌跡中的所有起止點都被識別出來以后，以這些停車點位分割點，將軌跡進行分割，則就獲取了每輛車所有的運輸起始點和終點，為后續(xù)的軌跡聚類提供了數(shù)據(jù)支持。3.5本章小結(jié)本章主要介紹了軌跡計算的流程，一般而言其需要經(jīng)過數(shù)據(jù)預(yù)處理、停車點識別、軌跡分割，數(shù)據(jù)預(yù)處理是之間依據(jù)軌跡數(shù)據(jù)特征，對數(shù)據(jù)進行異常點檢測、去除重復(fù)、數(shù)據(jù)規(guī)范化等操作，重點介紹了一種基于網(wǎng)格的軌跡異常點檢測算法，該算法通過將軌跡點映射到不同區(qū)域中，然后網(wǎng)格內(nèi)數(shù)據(jù)點個數(shù)和對網(wǎng)格進行分類從而發(fā)現(xiàn)異常點。然后通過車輛速度進行停車點識別，得到了一系列可靠的停車點，然后基于該停車點，利用樸素貝葉斯分類器算法獲取貨運車輛起止卸貨停車點，完成了軌跡分割。23萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文第4章海量軌跡數(shù)據(jù)聚類算法研究4.1軌跡聚類的意義和問題海量軌跡數(shù)據(jù)中包含了經(jīng)緯度信息、時間標簽、速度、方向、海拔、里程等時空信息，有的還有參考停車啟動信息，以及隱藏在背后關(guān)于交通道路，司機對于實際地理位置信息等實際狀況判斷信息，深入挖掘這些信息對于提供LBS[32]服務(wù)將會有廣闊的應(yīng)用前景。例如在新浪微博、騰訊微博、微信等一系列LBS應(yīng)用中在百度地圖、新浪微博、微信、公交軟件等一系列LBS應(yīng)用中，用戶可以不斷的實時在地圖上顯示自己的位置和軌跡，朋友之間聚會時開啟實時位置共享便可以看到好友的實時位置信息，司機在行駛途中也可以廣播實時路況，這些信息都不僅生動展現(xiàn)了人們所處環(huán)境信息也幫助人們直觀了解了未知區(qū)域信息，更為重要的是這些信息是實時的。但是若只是簡單的分享位置信息、在[33]地圖上展現(xiàn)信息并不能充分的挖掘這些背后隱藏的知識。通過軌跡聚類的方式可以挖掘出軌跡中的頻繁模式，可以從海量的軌跡中蘊含的知識中發(fā)現(xiàn)有用的知識，這對于物流公司貨運線路推薦、車輛調(diào)度和管理十分有意義。目前，海量軌跡聚類研究的問題包括兩類。（1）怎樣表示軌跡之間的相異度以及相異度的大小。用通俗的話說，相異度就是兩個東西差別有多大，當車輛軌跡展示在地圖上的時候，我們可以通過直觀感受大體得到軌跡之間的相似程度，但是計算機沒有這種直觀能力，必須通過一些數(shù)學(xué)手段將我們?nèi)梭w直觀感受到的區(qū)別大小定量的表示出來。（2）依據(jù)軌跡數(shù)據(jù)的特征和軌跡分析的需求，提出面向應(yīng)用的軌跡特征概念和聚類方法。即在時空軌跡的定義、模型和表達方式的基礎(chǔ)之上，針對不同[34]的分析需求采取不同的聚類算法和策略。綜上，可以將軌跡聚類方法劃分為軌跡表達、相似性度量和聚類算法三個[35]步驟。本文提出了如圖4-1所示的軌跡聚類算法流程圖。軌跡表達包括軌跡定[36]義和線性插值兩部分。車輛軌跡數(shù)據(jù)是一系列的離散點序列連成的折線，可以d?看作為一個映射ft:?R,其中將物體在時刻tR?的位置映射到一個d維的空間，一般是二維或者三維空間。車輛在實際運行中其實際軌跡是連續(xù)的，但是采集并存儲在計算中的時候是離散化的，并且往往依據(jù)GPS采樣頻率的不同對軌跡進行線性插值，擴充軌跡語意表達。通過相似性度量可以確定軌跡之間的時空關(guān)系,設(shè)分別有兩條軌跡A??{,...,},aaaBbb{,...,}b，可以使用12nn1224萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文dAB(,)??fAB(,)R表示軌跡A和B的距離，也即是相異度，其中R為實數(shù)域。聚類與分類不同，分類問題中類型信息是已知的，而在聚類問題中，類型信息是未知的，聚類問題將一個完成的數(shù)據(jù)集合分為若干組，組內(nèi)有的數(shù)據(jù)盡可能的相似，組間的數(shù)據(jù)盡可能相異度越大。其中相異度由距離來表征。聚類是研究領(lǐng)域內(nèi)的一個重難點問題，他需要以下若干個條件（1）可擴展性（2）兼容各種數(shù)據(jù)格式（3）能夠容忍噪聲。其中每個組叫做一個簇。軌跡聚類依據(jù)分析挖掘目的的不同，基于不同的相似性度量，選擇不同基于密度、距離、統(tǒng)計等的聚類算法完成軌跡聚類從而發(fā)現(xiàn)常用軌跡模式。軌跡表達相似性度量軌聚軌跡類軌跡定義跡時空相似性聚結(jié)數(shù)線性插值類果圖4-1軌跡聚類算法流程圖4.2軌跡表達和相似性度量4.2.1軌跡規(guī)則化通常，在軌跡挖掘方法中，例如聚類算法中需要直接對數(shù)據(jù)進行加法、減法或矩陣運算等。然后軌跡數(shù)據(jù)是由一系列離散點組成，不同的軌跡有不同數(shù)量的軌跡點數(shù)據(jù)，因此直接對這些軌跡進行上述運算并不可行，一般而言，在軌跡挖掘方法中若需要對軌跡進行直接運算需要支持如下兩種操作。distXY(,)?distYX(,)|?XY?|（4-1）meanXY(,)?meanYX(,)|?XY?|/2（4-2）其中X和Y分別代表任意兩條軌跡。軌跡規(guī)則化可以將任意原始軌跡投影到統(tǒng)一的多維度空間以支持上述兩種運算。在前面的章節(jié)中，已經(jīng)提到過一條包含n個GPS點的軌跡可以描述為4-3?所示，式中nZ??和xy,[0,360]iiR?{(,),(,xyxy),...,(,xy)}（4-3）1122nn25萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文x表示緯度，y表示緯度軌跡起始點為(,)xy，終點為(,xy)，若不考慮軌ii11nn跡方向，可以將軌跡表述如下：?axb??x[,xx)1112?y??axb?x?[,xx)（4-4）2223??axb??x[x,x)33nn?1其中?yy?ii?1a??ixx??ii?1?b?y?axiiii??ab,?R（4-5）ii??nZ???xy,?[0,360]ii??in?[1,]緯度(,)xy(xy,)11nn??11(,xy)(,xy)2266(,xy)(,xy)55nn(,xy33)(,xy44)經(jīng)度度圖4-2為式4-4描述的軌跡圖該軌跡可以通過算法x將其投影到一個固定維數(shù)的特征空間中去。該算法???的定義如下，S:GPS點所在平面。SS:平面逆時針旋轉(zhuǎn)?度。f():xS平面內(nèi)的軌跡表達式。算法x的過程如下：（1）將平面坐標系統(tǒng)S分別旋轉(zhuǎn)??,構(gòu)????造兩個平面坐標系統(tǒng)：S和S。（2）將平面S內(nèi)的軌跡分別投射到S和S中。???（3）在S中獲取連續(xù)的j個抽樣點[,,...,xxx],計算y?f()x；同理在S中12nii'''''?獲取連續(xù)的j個抽樣點[,xx,...,x]，計算得到y(tǒng)?f()x。（4）經(jīng)過上述步12nii26萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文驟后得到軌跡。'''R?{,yy,...,yyy,,y,...,}（4-6）12jn12軌跡R可以看作為一個二維空間里面的曲線，屬于一個參數(shù)集合{,,}??j,??和可以視為在二維空間內(nèi)從兩個角度去觀測軌跡，j為軌跡的分辨率，j值越大，軌跡的表達越精確。圖4-3為通過算法4-1得到的軌跡圖。?Yx5x2x4x1x6xy35y4Yy6yy31y2圖4-3算法4-1得到的軌跡圖軌跡規(guī)則化預(yù)處理算法如算法4-1所示。本文提出的算法4-2如下所示。通過規(guī)則化后，軌跡R依然保留了軌跡的走向趨勢特征，這是因在上述的算法第三步過程中將原來處于平面S中的軌跡R轉(zhuǎn)換為RRRRRii?[(,xy),(,xy),...,(,xyxy),(x,其中yy)...(?f()x,，因此軌跡)]1122jj??j1j1j2j2jjA和軌B的距離可定義為：22iiAAAAdistAB(,)????fxy((,ii),(,xyii))fgxy((,ii),(,gxyii))（4-7）ii??11通過式4-7，顯然可以看出gxx(,)是一個常數(shù)，因此在計算軌跡A和B之ii間距離的時候可是簡化為：22iiABABdistAB(,)????fgy((i,yi))dy(i,yi)（4-8）ii??11AB其中d?fg*，從式4-8中可以看出軌跡A和軌跡B的區(qū)別在于yy和，ii其中02??ij，因此式4-6的軌跡保留了其軌跡走向特征。由于軌跡所在平面是二維空間，所以當需要描述二維空間中的一個物體形狀的時候需要從兩個角度??去觀測，所以本文將二維平面分別旋轉(zhuǎn)??,構(gòu)造兩個平面坐標系統(tǒng)S和S。27萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文此外??,大小的選取也十分重要，在軌跡規(guī)則化過程中，必須使規(guī)則化后的軌跡信息中包含全部原始軌跡中形狀和趨勢信息。如圖4-3中所示，一條完整的軌跡是一系列單向的GPS點組成，而軌跡的走向也反映到這些GPS點序列中，因此線性擬合這些折線可以獲取得到軌跡的走向趨勢信息。假若在原始平面中中。。線性擬合的直線與x軸之間的夾角為?，則??,分別為??45和?+135。Input:D,原始軌跡數(shù)據(jù)N,軌跡數(shù)據(jù)集中軌跡的條數(shù)M,單條軌跡數(shù)組Output：L，預(yù)處理后的軌跡數(shù)組Procedure:whilei?Ndowhilej?Mido[]ifx(??x)0then21a?(-)/(-)yyxx2121b??xa*y11elsea?0b?0endifaddabxxintoT{,,,}12jj??1endwhileaddTintoLii??1endwhile算法4-1軌跡規(guī)則化預(yù)處理算法通過上述將軌跡R規(guī)則化以后，所有的軌跡可以看作為被投影到一個維度為2j的空間中，因此它們可以像二維平面中的GPS點數(shù)據(jù)一樣運算。在現(xiàn)實世28萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文界中，當軌跡沒有受到噪聲等干擾時，大多數(shù)軌跡都是以一種或者多種模式反復(fù)出現(xiàn)，并且這些軌跡之間十分緊密。圖4-4為通過PCA方法將軌跡數(shù)據(jù)降到Input:D,原始軌跡數(shù)據(jù)，L,軌跡數(shù)據(jù)集，xR,經(jīng)度的右邊界N,軌跡數(shù)據(jù)集中軌跡的條數(shù)M,單條軌跡數(shù)組，xL,經(jīng)度的左邊界Output：R，規(guī)則化后的軌跡數(shù)組Procedure：?NM,?ZT?nulllistR?nulllistinterval??()xRxLwhilei?NdoaddxLintervali?*intoTendwhilei?0j?0z?0whilei?Ndocurrentroute?ithrouteasalistfromLwhilez?Ndosifcurrentsamplecurrentroutej?[][3]thenaddcurrentroute([0]*currentsamplecurrentroute?[1])intoRelsejj??1endifendwhilezz??1endwhilejj??1endwhile算法4-2軌跡規(guī)則化算法29萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文三維后的--83.4GPS數(shù)據(jù)分布圖，該圖上有2個區(qū)域的點緊密聚集在一起，這說明有兩地之間有兩條常行駛路線。-8833..4-83.4535--83.4--83.45--83.5--137.4-83.55--137.5-83.6190.42190.43190.45190.46190.47190.48190.44-圖4-4軌跡數(shù)據(jù)降到三維后的GPS數(shù)據(jù)分布圖4.2.2軌跡相似性度量在分類的過程中，同樣的輸入軌跡樣本采取不同的相似性度量準則的時候表征出來的相異度往往也不一樣，因此合理采用相異度計算準則非常重要，否則即使本應(yīng)該歸為一類的軌跡也會因為距離計算方法不當而導(dǎo)致巨大差異，直到影響后續(xù)的聚類效果。通常，在空間計算中，距離可以依據(jù)不同數(shù)據(jù)集的特征來選擇不同，但是不論何種計算方法，該方法必須滿足如下三種條件：（1）distab(,)?distba(,)；（2）distab(,)??distbc(,)distac(,)；（3）distab(,)0?。本文主要討論如下三種定義距離的方法。假設(shè)有兩條軌跡X和Y分別通過規(guī)則化后得到為[,,...]xxx和[,yy,...]y，12k12k并且定義yx?為軌跡第i個點之間的距離。ii(1)歐氏距離k2distXY(,)???i?1(xiiy)（4-9）多維空間中點與點之間的距離常用該方式計算，它表示其真實距離，在軌跡計算中，兩個點的歐式距離即為真實地理上的距離。在二維空間中的歐氏距30萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文離就是兩點之間的直線段距離。歐式距離看作軌跡的相似程度，通常在大多數(shù)情況下，距離越近就越軌跡就越相似,但是也有不適用情況，如圖4-5所示，如果使用歐式距離，軌跡A和軌跡B的距離顯然更大，切比雪夫距離可以很好的處理這種狀況，但是在大多數(shù)狀況下，歐氏距離依然是一個很好的選擇。ABC圖4-5歐式距離不適用情況示意圖（2）曼哈頓距離kdistXY(,)???|xiiy|（4-10）i?1曼哈頓距離是一種幾何學(xué)的歐幾里得距離，是一種新的衡量標準兩點之間的距離，它采用兩點的絕對笛卡爾坐標的差異。在實際應(yīng)用中，軌跡數(shù)據(jù)中通常存在噪聲，而這些噪聲往往屬于正態(tài)分布，因此曼哈頓距離可以有效的修正軌跡中存在的正態(tài)分布的噪聲所造成的誤差。如圖4-6為曼哈頓距離不適用情況示意圖，顯然軌跡A和B是不同的，但是它們之間的距離并不為零，可見曼哈頓距離并不使用所有情況。AB圖4-6為曼哈頓距離不適用情況示意圖（3）切比雪夫距離distXY(,)??max(|xy|)（4-11）iii切比雪夫距離是一種描述向量之間距離的方式，它用兩個向量之間坐標差異最大值表示。這中計算距離的方式有很好的抗噪聲性能，軌跡是否平行也有很好的距離表示性能。圖4-7為切比雪夫距離示意圖。31萬方數(shù)據(jù) 武漢理工大學(xué)碩士學(xué)位論文AdB圖4-7為切比雪夫距離示意圖以上三種距離定義方式，都能在一些場景下適用于軌跡間的距離定義，本文基于軌跡規(guī)則化的結(jié)果，采用了歐氏距離的定義距離方式，可以有效的消除類似圖4-5所示的誤差狀況。4.3軌跡聚類4.3.1常見聚類算法比較聚類是將一個集合分為若干個子集合的過程，每個子集都是一個簇，每一個簇內(nèi)的對象都是相似的，簇間的數(shù)據(jù)對象并不相似。關(guān)于聚類已經(jīng)有了很多不同的算法。聚類的過程是由聚類算法實現(xiàn)的，而不是人實現(xiàn)的，因此通過聚類算法可以發(fā)現(xiàn)未知的簇。在海量軌跡數(shù)據(jù)挖掘中，它可以發(fā)現(xiàn)常出現(xiàn)的軌跡模式。作為統(tǒng)計學(xué)的一個分支，聚類分析被廣泛的研究和應(yīng)用，聚類算法本身也必須滿足一些要求才能真正達到將數(shù)據(jù)聚類的效果，這些因素包括對于不同屬性數(shù)據(jù)類型必須有可擴展，可以抗噪聲，能發(fā)現(xiàn)不同聚類形狀的數(shù)據(jù)簇。有很多種聚類算法，這些方法之間很難有一個明確的界限，因為這些算法互相之[37]間有交疊的部分，通常有如下幾種聚類算法。分割方法：給定一個有n個數(shù)據(jù)對象的集合，將這個集合分割為k個部分，其中k
