到达数据中时空异常聚簇发现
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金(61070024,61272180);教育部博士点基金(20120042110028);教育部-英特尔信息技术专项科研基金(MOE-INTEL-2012-06);本文部分工作是作者在访问中国人民大学萨师煊大数据研究中心时完成的,该中心获国家高等学校学科创新引智计划(111计划)资助


Spatio-Temporal Abnormal Cluster Discovery in Arrival Data
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    在时空数据中有一类表示用户在某一时间到达某一地点的数据——到达数据,到达数据可以是社交网站的签到数据、轨迹数据中的停留点及公共交通中乘客抵达的位置数据,这些数据的聚簇可以反映用户的聚集行为.基于到达数据,提出一类新的时空数据查询——时空异常聚簇发现.将到达数据进行周期性划分,通过时空聚类算法对一个时间段的数据进行聚类,比较不同时间段内聚簇的差异度,发现具有最大簇异常度的前k个簇.通过该查询发现的时空异常聚簇可以应用于城市安全管理、基于位置的服务和交通调度等方面.定义了异常簇查询模型,提出了针对任意形状聚簇的簇差异度度量,将异常簇查询转化为二分图最大匹配问题,对二分图构建与匹配进行了优化并提出了高效的查询算法.利用真实数据集进行了充分实验,验证了查询结果的实际意义,评估了所提出的各查询算法在不同参数设置下的查询效率.

    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.

    参考文献
    相似文献
    引证文献
引用本文

刘俊岭,魏茹玉,于戈,孙焕良,姚承伟.到达数据中时空异常聚簇发现.软件学报,2014,25(S2):225-235

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2014-05-07
  • 最后修改日期:2014-08-19
  • 录用日期:
  • 在线发布日期: 2015-01-29
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号