本文選題：軌跡數(shù)據(jù) + 停留點(diǎn)��； 參考：《太原理工大學(xué)》2017年碩士論文

【摘要】：基于位置服務(wù)技術(shù)的高速發(fā)展和位置服務(wù)需求的快速增加,推動(dòng)智能定位設(shè)備和終端普及,產(chǎn)生大量包含豐富信息價(jià)值的軌跡數(shù)據(jù),使得軌跡數(shù)據(jù)挖掘成為當(dāng)前的研究熱點(diǎn)。動(dòng)態(tài)熱度路網(wǎng)構(gòu)建是軌跡數(shù)據(jù)挖掘的一個(gè)重要研究方向,是指在無(wú)路網(wǎng)背景下構(gòu)建一張邊熱度隨時(shí)間變化的路網(wǎng)圖,動(dòng)態(tài)熱度路網(wǎng)能反映移動(dòng)對(duì)象在地理區(qū)域的聚集程度和活動(dòng)規(guī)律,可用于城市交通管理、旅游景點(diǎn)路線推薦、商業(yè)廣告投放等領(lǐng)域。交匯口到交匯口的熱度路徑研究是動(dòng)態(tài)熱度路網(wǎng)的主流構(gòu)建類型,構(gòu)建過(guò)程分為兩個(gè)步驟:(1)靜態(tài)熱度路網(wǎng)構(gòu)建(2)動(dòng)態(tài)化熱度路網(wǎng)。獲取交匯口是靜態(tài)熱度路網(wǎng)構(gòu)建的關(guān)鍵環(huán)節(jié),獲取方法通常有兩種:相關(guān)性擴(kuò)展算法和部分?jǐn)U展算法。相關(guān)性擴(kuò)展算法需要對(duì)圓域內(nèi)全部軌跡點(diǎn)執(zhí)行擴(kuò)展計(jì)算,算法存在效率低的問題。部分?jǐn)U展算法沒有分析圓域內(nèi)點(diǎn)的類型,只對(duì)圓域內(nèi)滿足距離閾值條件的部分點(diǎn)擴(kuò)展,會(huì)遺漏部分交匯口信息,算法存在獲取交匯口數(shù)量少、精度低的問題。劃分時(shí)間段是動(dòng)態(tài)化熱度路網(wǎng)的關(guān)鍵環(huán)節(jié),劃分方法通常有三種:等間隔劃分法、基于距離的劃分法和平滑劃分法。等間隔劃分法劃分?jǐn)?shù)固定,邊熱度高峰和低谷值可能出現(xiàn)在同一時(shí)間段內(nèi),算法存在誤差大的問題�；诰嚯x的劃分法和平滑劃分法均以二分K-means算法為基礎(chǔ),劃分時(shí)間段需要迭代計(jì)算,算法存在時(shí)間代價(jià)高的問題,且算法需隨機(jī)指定初始聚類中心,多次指定迭代聚類中心,劃分結(jié)果容易受到離群點(diǎn)的影響,不能反映時(shí)間點(diǎn)的真實(shí)聚集情況,算法存在精度低的問題。同時(shí)基于距離的劃分法還存在劃分?jǐn)?shù)過(guò)多和劃分后各個(gè)子時(shí)間段離散的問題。針對(duì)獲取交匯口方法存在的問題,本文提出停留點(diǎn)擴(kuò)展算法StopExpanding,分析交匯口和停留點(diǎn)空間分布特性,利用交匯口處停留點(diǎn)分布密集的特性,僅根據(jù)停留點(diǎn)的相關(guān)性執(zhí)行擴(kuò)展計(jì)算,減少不相關(guān)點(diǎn)的遍歷從而實(shí)現(xiàn)交匯口快速獲取。針對(duì)劃分時(shí)間段方法存在的問題,本文提出密度聚類劃分時(shí)間段算法DbPartition,按照邊熱度隨時(shí)間的變化劃分時(shí)間段。首先尋找核心時(shí)間對(duì)象,然后將核心時(shí)間對(duì)象鄰域內(nèi)的點(diǎn)分配到不同類中,合并具有相同核心時(shí)間對(duì)象的類,各個(gè)類中的時(shí)間點(diǎn)分別構(gòu)成劃分后的各個(gè)子時(shí)間段,實(shí)現(xiàn)準(zhǔn)確、快速地劃分時(shí)間段。實(shí)驗(yàn)結(jié)果表明,在獲取交匯口過(guò)程中,StopExpanding算法與部分?jǐn)U展算法相比,平均運(yùn)行時(shí)間縮短15.8%;在劃分時(shí)間段過(guò)程中,DbPartition算法與平滑劃分法相比,平均精度提高11.7%,平均運(yùn)行時(shí)間縮短33%;使用StopExpanding和Db Partition組合的算法能提高動(dòng)態(tài)熱度路網(wǎng)構(gòu)建的效率。
[Abstract]:With the rapid development of location-based service technology and the rapid increase of demand for location-based services, intelligent positioning devices and terminals are popularized, and a large number of locus data containing rich information value are generated, which makes trajectory data mining become a hot research topic at present. The construction of dynamic heat network is an important research direction of track data mining. It refers to constructing a road map with the change of edge heat with time under the background of no road network. Dynamic heat network can reflect the aggregation degree and activity law of moving objects in geographical areas, and can be used in urban traffic management, route recommendation of tourist attractions, commercial advertising, and so on. The study on the heat path from intersection to intersection is the mainstream construction type of dynamic heat network. The construction process is divided into two steps: 1) static heat network construction 2) dynamic heat network. Acquisition of intersection is a key link in the construction of static heat network. There are usually two methods: correlation expansion algorithm and partial expansion algorithm. Correlation expansion algorithm needs to perform extended computation for all locus points in circle domain, and the algorithm has the problem of low efficiency. The partial expansion algorithm does not analyze the types of points in the circle domain, but only extends some points in the circle domain that meet the threshold condition of distance, and will omit the information of some intersection ports. The algorithm has the problem of obtaining fewer intersection ports and low precision. Time division is the key link of dynamic heat network. There are usually three methods: equal interval partition method, distance based partition method and smooth partition method. The equal-interval partition method has a fixed number of partitions, and the peak and trough values of edge heat may appear in the same time period, so the algorithm has the problem of large error. Both distance-based partitioning and smoothing partitioning are based on dichotomous K-means algorithm, which requires iterative computation to divide time periods, which has the problem of high time cost, and the algorithm needs to specify the initial clustering center at random and the iterative clustering center several times. The segmentation results are easy to be affected by outliers and can not reflect the real aggregation of time points. The algorithm has the problem of low precision. At the same time, the distance-based partitioning method also has the problems of excessive number of partitions and discrete subperiods after partitioning. In view of the problems existing in the method of obtaining intersection points, this paper proposes a stop-point expansion algorithm, StopExpanding. by analyzing the spatial distribution characteristics of intersection and stopover points, using the characteristics of dense distribution of entrances, the expansion calculation is carried out only according to the correlation between the entrances and the entrances. Reduce the traversal of irrelevant points to achieve fast access to the intersection. In order to solve the problem of time division, this paper proposes a density clustering time division algorithm, DbPartition. it divides time according to the change of edge heat with time. First, the core time objects are found, then the points in the neighborhood of the core time objects are assigned to different classes, and the classes with the same core time objects are merged. Divide the time period quickly. The experimental results show that the average running time of the StopExpanding algorithm is 15.8 shorter than that of the partial expansion algorithm, and the DbPartition algorithm is compared with the smooth partitioning algorithm in the process of obtaining the intersection. The average accuracy is increased by 11.7m, the average running time is shortened by 33%, and the efficiency of dynamic heat network construction can be improved by using the algorithm of combining StopExpanding and DB Partition.
【學(xué)位授予單位】：太原理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP311.13

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 吳俊偉;朱云龍;庫(kù)濤;陳翰寧;;基于路網(wǎng)探測(cè)的軌跡模式挖掘[J];信息與控制;2015年01期

2 吳俊偉;朱云龍;庫(kù)濤;王亮;;基于網(wǎng)格聚類的熱點(diǎn)路徑探測(cè)[J];吉林大學(xué)學(xué)報(bào)(工學(xué)版);2015年01期

3 龍其;葉晨;張亞英;;動(dòng)態(tài)路網(wǎng)中基于實(shí)時(shí)路況信息的分布式路徑生成算法[J];計(jì)算機(jī)科學(xué);2014年09期

4 李婷;裴韜;袁燁城;宋辭;王維一;楊格格;;人類活動(dòng)軌跡的分類、模式和應(yīng)用研究綜述[J];地理科學(xué)進(jìn)展;2014年07期

5 陳依嬌;楊愷希;;用于熱門路徑查詢的動(dòng)態(tài)熱度路網(wǎng)的構(gòu)建方法[J];微型電腦應(yīng)用;2014年06期

6 唐科萍;許方恒;沈才j;;基于位置服務(wù)的研究綜述[J];計(jì)算機(jī)應(yīng)用研究;2012年12期

7 張文濤;夏戰(zhàn)國(guó);張磊;夏士雄;;距離和屬性結(jié)合的軌跡數(shù)據(jù)公共子模式發(fā)現(xiàn)[J];計(jì)算機(jī)工程與設(shè)計(jì);2011年07期

8 周傲英;楊彬;金澈清;馬強(qiáng);;基于位置的服務(wù):架構(gòu)與進(jìn)展[J];計(jì)算機(jī)學(xué)報(bào);2011年07期

9 全永q，

本文編號(hào)：1781404