基于滑动窗口的手机定位数据个体停留区域识别算法
|
摘要
手机的普及使手机定位数据成为分析个体时空行为特征的新兴重要数据源之一,并被逐渐应用到人口管理、城市规划、交通分析和流行病防控等众多领域的研究中。从手机定位数据中识别个体的停留区域是众多基于手机定位数据研究的重要基础环节。然而,当前常用的手机定位数据定位精度相对较低,且往往存在定位震荡和定位漂移导致的数据噪声,这些因素增加了从手机定位数据中识别停留区域的难度。为了提高从手机定位数据中识别个体停留区域的准确性,本研究结合个体行为的时空连续性,提出了一种基于滑动窗口的增长聚类算法。实验结果显示,相较常用的ST-DBSCAN算法和SMo T算法,对于采样时间间隔稀疏的手机定位数据,本研究提出的滑动窗口聚类算法在准确率方面的提升幅度最大可以达到35%。由于隐私问题,当前研究和应用中使用的大规模手机定位数据集中的时间分辨率往往较低,因此,本研究提出的滑动窗口聚类算法具有较为广泛的应用场景,可增强基于手机用户停留区域的众多研究结果的可靠性,为手机定位数据的广泛合理应用提供关键技术支撑。
With the development and popularization of mobile phones, mobile phone location data have become an important source of data for analyzing individual mobility characteristics. With these location data, many studies can be performed at a fine spatiotemporal scale in fields such as population management, urban planning,transportation analysis and health intervention. Detection of individual stay areas is an important and basic step in many studies based on mobile phone location data. However, the sparse spatial and temporal resolution of raw mobile phone location data and data noise caused by location oscillation and location drift introduce great challenges in effectively detecting individual stay areas from raw mobile phone location data. Considering the spatiotemporal continuity of individual behavior, this study proposes an incremental clustering algorithm based on a moving window to improve the accuracy of detecting individual stay areas from mobile phone location data. Specifically, the proposed algorithm first sorts the raw records in chronological order. Then, the algorithm consecutively examines the adjacent records with a given distance threshold. Records that satisfy the rule will be added to the current cluster. For each unqualified record, the algorithm extracts a series of records within a moving window and calculates the spatial distance of these records as a criterion for clustering. The time interval between the unqualified record and the selected records should be less than a given time threshold, which is also the width of the moving window in this proposed algorithm. In this step, the algorithm treats some unqualified records as location drift records or location oscillation records based on the detection rules and aggregates them into the current cluster, and unqualified records that do not fit the detection rules are excluded from the current cluster and the algorithm creates a new cluster for the unqualified records. Finally, the algorithm calculates the location and temporal information of each valid cluster as the parameters of the corresponding stay area and constructs a stay area sequence for each mobile user. We compared the results of the proposed algorithm with those obtained using the ST-DBSCAN and SMo T algorithms. The experiment applied the three algorithms to a mobile phone location dataset in Shenzhen that is a type of Call Detail Records, and the results show that the proposed algorithm significantly improves the accuracy by up to 35% for detecting individual stay areas from sparse mobile phone location data compared to the other two algorithms. Due to privacy issues associated with the government or telecom operators, the temporal resolution of large-scale mobile phone location data used in recent research is usually sparse, and thus the proposed algorithm can be used to improve the effectiveness of detecting individual stay areas and to provide reliable results for many studies based on mobile phone location data.
With the development and popularization of mobile phones, mobile phone location data have become an important source of data for analyzing individual mobility characteristics. With these location data, many studies can be performed at a fine spatiotemporal scale in fields such as population management, urban planning,transportation analysis and health intervention. Detection of individual stay areas is an important and basic step in many studies based on mobile phone location data. However, the sparse spatial and temporal resolution of raw mobile phone location data and data noise caused by location oscillation and location drift introduce great challenges in effectively detecting individual stay areas from raw mobile phone location data. Considering the spatiotemporal continuity of individual behavior, this study proposes an incremental clustering algorithm based on a moving window to improve the accuracy of detecting individual stay areas from mobile phone location data. Specifically, the proposed algorithm first sorts the raw records in chronological order. Then, the algorithm consecutively examines the adjacent records with a given distance threshold. Records that satisfy the rule will be added to the current cluster. For each unqualified record, the algorithm extracts a series of records within a moving window and calculates the spatial distance of these records as a criterion for clustering. The time interval between the unqualified record and the selected records should be less than a given time threshold, which is also the width of the moving window in this proposed algorithm. In this step, the algorithm treats some unqualified records as location drift records or location oscillation records based on the detection rules and aggregates them into the current cluster, and unqualified records that do not fit the detection rules are excluded from the current cluster and the algorithm creates a new cluster for the unqualified records. Finally, the algorithm calculates the location and temporal information of each valid cluster as the parameters of the corresponding stay area and constructs a stay area sequence for each mobile user. We compared the results of the proposed algorithm with those obtained using the ST-DBSCAN and SMo T algorithms. The experiment applied the three algorithms to a mobile phone location dataset in Shenzhen that is a type of Call Detail Records, and the results show that the proposed algorithm significantly improves the accuracy by up to 35% for detecting individual stay areas from sparse mobile phone location data compared to the other two algorithms. Due to privacy issues associated with the government or telecom operators, the temporal resolution of large-scale mobile phone location data used in recent research is usually sparse, and thus the proposed algorithm can be used to improve the effectiveness of detecting individual stay areas and to provide reliable results for many studies based on mobile phone location data.
引文
[1]中国工业和信息化部.2017年通信运营业统计公报[EB/OL].[http://www.miit.gov.cn/n1146312/n1146904/n1648372/c6048643/content.html,2018-02-02.[Ministry of Industry and Information Technology of the People’s Republic of China.Statistical bulletin of communications operations in 2017[EB/OL].http://www.miit.gov.cn/n1146312/n1146904/n1648372/c6048643/content.html,2018-02-02.]
[2]Zheng Y.Trajectory data mining:An overview[J].ACM Transactions on Intelligent Systems and Technology,2015,6(3):29.
[3]Yue Y,Lan T,Yeh A G O,et al.Zooming into individuals to understand the collective:A review of trajectory-based travel behaviour studies[J].Travel Behaviour&Society,2014,1(2):69-78.
[4]刘瑜.社会感知视角下的若干人文地理学基本问题再思考[J].地理学报,2016,71(4):564-575.[Liu Y.Revisiting several basic geographical concepts:A social sensing perspective[J].Acta Geographica Sinica,2016,71(4):564-575.]
[5]郑宇.城市计算概述[J].武汉大学学报·信息科学版,2015,40(1):1-13.[Zheng Y.Introduction to urban computing[J].Geomatics and Information Science of Wuhan University,2015,40(1):1-13.]
[6]陆锋,刘康,陈洁.大数据时代的人类移动性研究[J].地球信息科学学报,2014,16(5):665-672.[Lu F,Liu K,Chen J.Research on human mobility in big data era[J].Journal of Geo-information Science,2014,16(5):665-672.]
[7]Schneider C M,Belik V,CouronnéT,et al.Unravelling daily human mobility motifs[J].Journal of the Royal Society Interface,2013,10(84):20130246.
[8]Phithakkitnukoon S,Horanont T,Lorenzo G D,et al.Activity-aware map:Identifying human daily activity pattern using mobile phone data[C].Human Behavior Understanding,First International Workshop,HBU 2010,Istanbul,Turkey,August 22,2010.Proceedings.DBLP,2010:14-25.
[9]Pei T,Sobolevsky S,Ratti C,et al.A new insight into land use classification based on aggregated mobile phone data[J].International Journal of Geographical Information Science,2014,28(9):1988-2007.
[10]尹凌,姜仁荣,赵志远,等.利用手机通话位置数据估计城市24h人口分布误差[J].地球信息科学学报,2017,19(6):763-771.[Yin L,Jiang R R,Zhao Z Y,et al.Exploring the bias of estimating 24-hour population distributions using call detail records[J].Journal of Geo-information Science,2017,19(6):763-771.]
[11]Calabrese F,Lorenzo G D,Liu L,et al.Estimating origindestination flows using mobile phone location data[J].IEEE Pervasive Computing,2011,10(4):36-44.
[12]Fang Z X,Yang X P,Xu Y,et al.Spatiotemporal model for assessing the stability of urban human convergence and divergence patterns[J].International Journal of Geographical Information Science,2017,31(11):2119-2141.
[13]Brdar S,Gavri?K,?ulibrk D,et al.Unveiling spatial epidemiology of HIV with mobile phone data[J].Scientific reports,2016,6:19342.
[14]Isdory A,Mureithi E W,Sumpter D J.The impact of human mobility on HIV transmission in kenya[J].Plos One,2015,10(11):e0142805.
[15]Mao L,Yin L,Song X Q,et al.Mapping intra-urban transmission risk of dengue fever with big hourly cellphone data[J].Acta Tropica,2016,162:188-195.
[16]Spaccapietra S,Parent C,Damiani M L,et al.A conceptual view on trajectories[J].Data&Knowledge Engineering,2008,65(1):126-146.
[17]Zheng Y,Chen Y K,Xie X,et al.Geo Life2.0:A LocationBased Social Networking Service[C].Tenth International Conference on Mobile Data Management:Systems,Services and Middleware.IEEE,2009:357-358.
[18]Zheng Y,Xie X,Ma W Y.Geo Life:A collaborative social networking service among user,location and trajectory[J].Bulletin of the Technical Committee on Data Engineering,2011,33(2):32-39.
[19]Bao J,Zheng Y,Wilkie D,et al.Recommendations in location-based social networks:A survey[J].Geoinformatica,2015,19(3):525-565.
[20]Lian D F,Xie X.Mining check-in history for personalized location naming[J].Acm Transactions on Intelligent Systems&Technology,2014,5(2):1-25.
[21]Ahas R,Laineste J,Aasa A,et al.The spatial accuracy of mobile positioning:Some experiences with geographical studies in Estonia[M].Location based services and telecartography.Springer Berlin Heidelberg,2007:445-460.
[22]Ahas R,Aasa A,Silm S,et al.Mobile positioning in space-time behaviour studies:social positioning method experiments in estonia[J].American Cartographer,2007,34(4):259-273.
[23]Vajakas T,Vajakas J,Lillemets R.Trajectory reconstruction from mobile positioning data using cell-to-cell travel time information[J].International Journal of Geographical Information Science,2015,29(11):1941-1954.
[24]Iovan C,Olteanu-Raimond A M,CouronnéT,et al.Moving and calling:Mobile phone data quality measurements and spatiotemporal uncertainty in human mobility studies[M].Geographic Information Science at the Heart of Europe.Springer,Cham,2013:247-265.
[25]Ester M,Kriegel H P,Xu X.A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise[C].International Conference on Knowledge Discovery and Data Mining.AAAI Press,1996:226-231.
[26]Birant D,Kut A.ST-DBSCAN:An algorithm for clustering spatial–temporal data[J].Data&Knowledge Engineering,2007,60(1):208-221.
[27]Palma A T,Bogorny V,Kuijpers B,et al.A clusteringbased approach for discovering interesting places in trajectories[C].ACM Symposium on Applied Computing.DBLP,2008:863-868.
[28]曹劲舟,涂伟,李清泉,等.基于大规模手机定位数据的群体活动时空特征分析[J].地球信息科学学报,2017,19(4):467-474.[Cao J Z,Tu W,Li Q Q,et al.Spatio-temporal analysis of aggregated human activities based on massive mobile phone tracking data[J].Journal of Geo-information Science,2017,19(4):467-474.]
[29]Alvares L O,Bogorny V,Kuijpers B,et al.A model for enriching trajectories with semantic geographical information[C].ACM International Symposium on Advances in Geographic Information Systems.ACM,2007:22.
[30]Horn C,Klampfl S,Cik M,et al.Detecting outliers in cell phone data:correcting trajectories to improve traffic modeling[J].Transportation Research Record:Journal of the Transportation Research Board,2014(2405):49-56.
[31]Kang J H.Extracting places from traces of locations[J].Acm Sigmobile Mobile Computing&Communications Review,2005,9(3):58-68.
[32]Widhalm P,Yang Y,Ulm M,et al.Discovering urban activity patterns in cell phone data[J].Transportation,2015,42(4):597-623.
[2]Zheng Y.Trajectory data mining:An overview[J].ACM Transactions on Intelligent Systems and Technology,2015,6(3):29.
[3]Yue Y,Lan T,Yeh A G O,et al.Zooming into individuals to understand the collective:A review of trajectory-based travel behaviour studies[J].Travel Behaviour&Society,2014,1(2):69-78.
[4]刘瑜.社会感知视角下的若干人文地理学基本问题再思考[J].地理学报,2016,71(4):564-575.[Liu Y.Revisiting several basic geographical concepts:A social sensing perspective[J].Acta Geographica Sinica,2016,71(4):564-575.]
[5]郑宇.城市计算概述[J].武汉大学学报·信息科学版,2015,40(1):1-13.[Zheng Y.Introduction to urban computing[J].Geomatics and Information Science of Wuhan University,2015,40(1):1-13.]
[6]陆锋,刘康,陈洁.大数据时代的人类移动性研究[J].地球信息科学学报,2014,16(5):665-672.[Lu F,Liu K,Chen J.Research on human mobility in big data era[J].Journal of Geo-information Science,2014,16(5):665-672.]
[7]Schneider C M,Belik V,CouronnéT,et al.Unravelling daily human mobility motifs[J].Journal of the Royal Society Interface,2013,10(84):20130246.
[8]Phithakkitnukoon S,Horanont T,Lorenzo G D,et al.Activity-aware map:Identifying human daily activity pattern using mobile phone data[C].Human Behavior Understanding,First International Workshop,HBU 2010,Istanbul,Turkey,August 22,2010.Proceedings.DBLP,2010:14-25.
[9]Pei T,Sobolevsky S,Ratti C,et al.A new insight into land use classification based on aggregated mobile phone data[J].International Journal of Geographical Information Science,2014,28(9):1988-2007.
[10]尹凌,姜仁荣,赵志远,等.利用手机通话位置数据估计城市24h人口分布误差[J].地球信息科学学报,2017,19(6):763-771.[Yin L,Jiang R R,Zhao Z Y,et al.Exploring the bias of estimating 24-hour population distributions using call detail records[J].Journal of Geo-information Science,2017,19(6):763-771.]
[11]Calabrese F,Lorenzo G D,Liu L,et al.Estimating origindestination flows using mobile phone location data[J].IEEE Pervasive Computing,2011,10(4):36-44.
[12]Fang Z X,Yang X P,Xu Y,et al.Spatiotemporal model for assessing the stability of urban human convergence and divergence patterns[J].International Journal of Geographical Information Science,2017,31(11):2119-2141.
[13]Brdar S,Gavri?K,?ulibrk D,et al.Unveiling spatial epidemiology of HIV with mobile phone data[J].Scientific reports,2016,6:19342.
[14]Isdory A,Mureithi E W,Sumpter D J.The impact of human mobility on HIV transmission in kenya[J].Plos One,2015,10(11):e0142805.
[15]Mao L,Yin L,Song X Q,et al.Mapping intra-urban transmission risk of dengue fever with big hourly cellphone data[J].Acta Tropica,2016,162:188-195.
[16]Spaccapietra S,Parent C,Damiani M L,et al.A conceptual view on trajectories[J].Data&Knowledge Engineering,2008,65(1):126-146.
[17]Zheng Y,Chen Y K,Xie X,et al.Geo Life2.0:A LocationBased Social Networking Service[C].Tenth International Conference on Mobile Data Management:Systems,Services and Middleware.IEEE,2009:357-358.
[18]Zheng Y,Xie X,Ma W Y.Geo Life:A collaborative social networking service among user,location and trajectory[J].Bulletin of the Technical Committee on Data Engineering,2011,33(2):32-39.
[19]Bao J,Zheng Y,Wilkie D,et al.Recommendations in location-based social networks:A survey[J].Geoinformatica,2015,19(3):525-565.
[20]Lian D F,Xie X.Mining check-in history for personalized location naming[J].Acm Transactions on Intelligent Systems&Technology,2014,5(2):1-25.
[21]Ahas R,Laineste J,Aasa A,et al.The spatial accuracy of mobile positioning:Some experiences with geographical studies in Estonia[M].Location based services and telecartography.Springer Berlin Heidelberg,2007:445-460.
[22]Ahas R,Aasa A,Silm S,et al.Mobile positioning in space-time behaviour studies:social positioning method experiments in estonia[J].American Cartographer,2007,34(4):259-273.
[23]Vajakas T,Vajakas J,Lillemets R.Trajectory reconstruction from mobile positioning data using cell-to-cell travel time information[J].International Journal of Geographical Information Science,2015,29(11):1941-1954.
[24]Iovan C,Olteanu-Raimond A M,CouronnéT,et al.Moving and calling:Mobile phone data quality measurements and spatiotemporal uncertainty in human mobility studies[M].Geographic Information Science at the Heart of Europe.Springer,Cham,2013:247-265.
[25]Ester M,Kriegel H P,Xu X.A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise[C].International Conference on Knowledge Discovery and Data Mining.AAAI Press,1996:226-231.
[26]Birant D,Kut A.ST-DBSCAN:An algorithm for clustering spatial–temporal data[J].Data&Knowledge Engineering,2007,60(1):208-221.
[27]Palma A T,Bogorny V,Kuijpers B,et al.A clusteringbased approach for discovering interesting places in trajectories[C].ACM Symposium on Applied Computing.DBLP,2008:863-868.
[28]曹劲舟,涂伟,李清泉,等.基于大规模手机定位数据的群体活动时空特征分析[J].地球信息科学学报,2017,19(4):467-474.[Cao J Z,Tu W,Li Q Q,et al.Spatio-temporal analysis of aggregated human activities based on massive mobile phone tracking data[J].Journal of Geo-information Science,2017,19(4):467-474.]
[29]Alvares L O,Bogorny V,Kuijpers B,et al.A model for enriching trajectories with semantic geographical information[C].ACM International Symposium on Advances in Geographic Information Systems.ACM,2007:22.
[30]Horn C,Klampfl S,Cik M,et al.Detecting outliers in cell phone data:correcting trajectories to improve traffic modeling[J].Transportation Research Record:Journal of the Transportation Research Board,2014(2405):49-56.
[31]Kang J H.Extracting places from traces of locations[J].Acm Sigmobile Mobile Computing&Communications Review,2005,9(3):58-68.
[32]Widhalm P,Yang Y,Ulm M,et al.Discovering urban activity patterns in cell phone data[J].Transportation,2015,42(4):597-623.