密度聚类划分时间段的动态热度路网构建

发布时间：2018-04-21 07:05

本文选题：轨迹数据 + 停留点　；参考：《太原理工大学》2017年硕士论文

【摘要】：基于位置服务技术的高速发展和位置服务需求的快速增加,推动智能定位设备和终端普及,产生大量包含丰富信息价值的轨迹数据,使得轨迹数据挖掘成为当前的研究热点。动态热度路网构建是轨迹数据挖掘的一个重要研究方向,是指在无路网背景下构建一张边热度随时间变化的路网图,动态热度路网能反映移动对象在地理区域的聚集程度和活动规律,可用于城市交通管理、旅游景点路线推荐、商业广告投放等领域。交汇口到交汇口的热度路径研究是动态热度路网的主流构建类型,构建过程分为两个步骤:(1)静态热度路网构建(2)动态化热度路网。获取交汇口是静态热度路网构建的关键环节,获取方法通常有两种:相关性扩展算法和部分扩展算法。相关性扩展算法需要对圆域内全部轨迹点执行扩展计算,算法存在效率低的问题。部分扩展算法没有分析圆域内点的类型,只对圆域内满足距离阈值条件的部分点扩展,会遗漏部分交汇口信息,算法存在获取交汇口数量少、精度低的问题。划分时间段是动态化热度路网的关键环节,划分方法通常有三种:等间隔划分法、基于距离的划分法和平滑划分法。等间隔划分法划分数固定,边热度高峰和低谷值可能出现在同一时间段内,算法存在误差大的问题。基于距离的划分法和平滑划分法均以二分K-means算法为基础,划分时间段需要迭代计算,算法存在时间代价高的问题,且算法需随机指定初始聚类中心,多次指定迭代聚类中心,划分结果容易受到离群点的影响,不能反映时间点的真实聚集情况,算法存在精度低的问题。同时基于距离的划分法还存在划分数过多和划分后各个子时间段离散的问题。针对获取交汇口方法存在的问题,本文提出停留点扩展算法StopExpanding,分析交汇口和停留点空间分布特性,利用交汇口处停留点分布密集的特性,仅根据停留点的相关性执行扩展计算,减少不相关点的遍历从而实现交汇口快速获取。针对划分时间段方法存在的问题,本文提出密度聚类划分时间段算法DbPartition,按照边热度随时间的变化划分时间段。首先寻找核心时间对象,然后将核心时间对象邻域内的点分配到不同类中,合并具有相同核心时间对象的类,各个类中的时间点分别构成划分后的各个子时间段,实现准确、快速地划分时间段。实验结果表明,在获取交汇口过程中,StopExpanding算法与部分扩展算法相比,平均运行时间缩短15.8%;在划分时间段过程中,DbPartition算法与平滑划分法相比,平均精度提高11.7%,平均运行时间缩短33%;使用StopExpanding和Db Partition组合的算法能提高动态热度路网构建的效率。
[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.
【学位授予单位】：太原理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.13

【参考文献】