| 摘要: |
| 在时空数据中有一类表示用户在某一时间到达某一地点的数据——到达数据,到达数据可以是社交网站的签到数据、轨迹数据中的停留点及公共交通中乘客抵达的位置数据,这些数据的聚簇可以反映用户的聚集行为.基于到达数据,提出一类新的时空数据查询——时空异常聚簇发现.将到达数据进行周期性划分,通过时空聚类算法对一个时间段的数据进行聚类,比较不同时间段内聚簇的差异度,发现具有最大簇异常度的前k个簇.通过该查询发现的时空异常聚簇可以应用于城市安全管理、基于位置的服务和交通调度等方面.定义了异常簇查询模型,提出了针对任意形状聚簇的簇差异度度量,将异常簇查询转化为二分图最大匹配问题,对二分图构建与匹配进行了优化并提出了高效的查询算法.利用真实数据集进行了充分实验,验证了查询结果的实际意义,评估了所提出的各查询算法在不同参数设置下的查询效率. |
| 关键词: 到达数据 二分图最大匹配 聚类 时空异常聚簇 基于位置的服务 |
| DOI： |
| 分类号: |
| 基金项目:国家自然科学基金(61070024,61272180);教育部博士点基金(20120042110028);教育部-英特尔信息技术专项科研基金(MOE-INTEL-2012-06);本文部分工作是作者在访问中国人民大学萨师煊大数据研究中心时完成的,该中心获国家高等学校学科创新引智计划(111计划)资助 |
|
| Spatio-Temporal Abnormal Cluster Discovery in Arrival Data |
|
LIU Jun-Ling1,2, WEI Ru-Yu2, YU Ge1, SUN Huan-Liang2, YAO Cheng-Wei2
|
|
1.School of Information Science and Engineering, Northeastern University, Shenyang 110006, China;2.School of Information and Control Engineering, Shenyang Jianzhu University, Shenyang 110015, China
|
| Abstract: |
| Arrival data is a type of location related data which records the spots and time that users arrive. It can be the check-in data in the social network, stay points in the trajectory or the arrival locations of passengers in the public transport. The clusters of arrival data can reflect the aggregation behavior of users in a particular area. This paper presents a new spatio-temporal data query—Spatio-Temporal Abnormal Clusters Discovery. The new scheme partitions the arrival data into segments with equal timespan periodically. Then using spatio-temporal cluster algorithms, it clusters the data in every segment, and finds k most abnormal clusters by comparing the different degree of clusters. Finding abnormal clusters can be useful in areas such as urban safety management, location based service and transportation scheduling. This article defines the abnormal cluster query model, specifies the difference measurement for the clusters with arbitrary shape and transforms the query to the maximum matching problem of bipartite graphs. Algorithms are designed to improve the efficiency in constructing and matching of bipartite graphs. The experiments on the real datasets validate the application value of the query results and demonstrate the effectiveness of the query algorithm with different parameters. |
| Key words: arrival data bipartite graph maximum matching clustering spatio-temporal abnormal clusters location-based service |
