اندازه گیری زمینه - آگاه تشابه خطوط سیر مبتنی بر الگوریتم MOPSO و نظریه فازی

نوع مقاله: مقاله پژوهشی

نویسندگان

1 استادیار،گروه نقشه برداری، دانشکده مهندسی عمران و حمل و نقل، دانشگاه اصفهان، اصفهان، ایران

2 دکتری سیستم های اطلاعات مکانی - دانشکده مهندسی نقشه برداری - دانشگاه صنعتی خواجه نصیرالدین طوسی

10.22131/sepehr.2018.32330

چکیده

در سالهای اخیر، مطالعه رفتار اشیاء نقطهای و تجزیه و تحلیل خطوطسیر آنها در علوم مختلف، بویژه در علوم اطلاعات مکانی[1]، مورد توجه بسیاری از محققان قرار گرفته است. مطالعاتمذکوربه درک صحیح الگوهای رفتاری-حرکتی این اشیاء کمک شایانی میکنند. نحوه حرکت اشیاء تا حد زیادی متأثر از زمینهای است که حرکت در آن صورت میپذیرد. به همین دلیل،تحلیل خطوط سیر اشیا صرفاً با در نظر گرفتن ابعاد مکانی و مکانی-زمانی به درستی شرایط حین حرکت را منعکس نمیکند و منجر به نتایج غیرواقعی میشود.با این حال، روشهای موجود اندازهگیری فاصله تنها قادر به اندازهگیری تشابه خطوط سیر در ابعاد مکانی و مکانی-زمانی هستند و معمولاً بعد زمینه را نادیده میگیرند. بنابراین، در این تحقیق، روشی نوین توسعه داده شده است، تا بتوان از طیف وسیعی از اطلاعات زمینهای کمی و کیفی داخلی و خارجی در کنار ابعاد مکانی-زمانی در فرآیند اندازهگیری تشابه خطوط سیر غیر هماندازه استفاده کرد. در توسعه روش مذکور، از سیستمهایاستنتاج فازی برای مدلسازی تشابه خطوط سیر با استفاده از انواع دادههای حرکتی و اطلاعات زمینهای بهره گرفته شده است. برای افزایش کارایی روش پیشنهادی از ساختار سلسله مراتبی مبتنی بر مسئله و تولید و تنظیم همزمان توابع عضویت و مجموعه قواعد از طریق یادگیری استفاده شده است. عملکرد این سیستم با اعمال آن برروی مجموعه خطوط سیر واقعی افراد پیادهودوچرخهسوار به همراه اطلاعات زمینهای آنها حین حرکت مورد ارزیابی قرار گرفته است. نتایج بیانگرکارآمدی روش پیشنهادی در اندازهگیری زمینه-آگاه خطوط سیر با اندازههای گوناگون و در ابعاد مختلف است.



[1]3-Geospatial Information Science
 

کلیدواژه‌ها


عنوان مقاله [English]

Context-Aware similarity measure of trajectories based on MOPSO algorithm and Fuzzy theory

نویسندگان [English]

  • behnam tashayo 1
  • Mohammad Sharif 2
1 Department of surveying, faculty of civil engineering and transportation, university of Isfahan, Isfahan, Iran
2 Department of Geospatial Information Systems, Faculty of Geodesy and Geomatics Engineering, Khajeh Nasir Toosi University of Technology
چکیده [English]

Extended Abstract
Introduction
With the developments in navigation, positioning, and tracking technologies, a large amount of moving point data (e.g., human, vehicle, animal) have been produced. Through moving an object in the course of time, a sequence of its position is recorded which is known as trajectory. Studying the behaviors of point objects and analyzing their trajectories have recently received great attentions among researchers in different fields of science, especially in geographic information science. Such studies contribute to better understanding of movement-behavior patterns of moving objects. Data mining, as one of the main approaches in geographic knowledge discovery, is normally used in moving databases to extract information from moving point objects’ trajectories. Analyzing the similarity of trajectories as one of the frequently used approaches in geographic data mining, is of great importance, which is normally performed by distance functions.
The way an object moves is highly influenced from the condition and situation (known as context) where movement takes place. Therefore, merely analyzing trajectories from their spatiotemporal dimension may not clearly reflect the conditions and situations (contexts) during the move, and may lead to unrealistic results. Accordingly, most of the present distance functions are only able to measure the similarity of trajectories at spatial and spatiotemporal dimensions and neglect the underlying context during the move. Therefore, developing a new trajectory similarity measure approach, capable of handling a wide range of context information in conjunction with spatiotemporal dimension becomes crucial.
 
Materials & Methods
According to the complexity and variety in the moving objects’ datasets, especially in their context parameters, in this research, a fuzzy model is developed which is able to exploit a wide range of internal and external context information in similarity measure process of multi-length trajectories. Specifically, a fuzzy inference system (FIS) is used for measuring the similarity between trajectories based on qualitative and quantitative context information. To enhance the effectiveness of the system, a subjective hierarchical fuzzy inference system (HFIS) is designed and the membership functions and rules are generated and adjusted based on learning. The HFIS controls the rules by dividing a FIS into several simple sub-systems that are hierarchically connected to each other. The Multi-Objective Particle Swarm Optimization (MOPSO) algorithm is used for defining and adjusting the FIS.
The performance of the system is assessed by applying it on real trajectories of pedestrians’ and cyclists’ datasets in the Central Park of Manhattan, New York, USA, while accounting contextual information. The movement parameters and context information were recorded in qualitative and quantitative formats. Two types of context information are used: 1) internal context (i.e., all of the properties that directly relate to the moving object, such as eagerness), and 2) external context (i.e., any factor that extrinsically influences the process of movement, such as slope). According to the nature of data, four models of spatial, spatiotemporal, spatiotemporal-internal context, and spatiotemporal-internal-external context are applied on the dataset to see the added value of each parameter.
 
Results & Discussion
The achievements of the implementations can be discussed from two main perspectives: 1) system performance, and 2) similarity results. From the system performance aspect, the control surface plots indicate the consistency of the rules in the developed fuzzy inference systems. In addition, the Pareto diagrams for both pedestrians’ and cyclists’ models cover the Pareto fronts in all four models in an appropriate manner.
From the similarity results aspect that are shown in boxplots, the commonalities between both pedestrians’ and cyclists’ trajectories are very high at the spatial dimension in the first model, while by adding the temporal dimension as the second model, the similarity range at the spatiotemporal dimension increases. This issue is directly related to the traversed paths and the elapsed times of the moving objects. By importing the internal contexts (i.e., speed, direction, length, eagerness) as the third model, the similarity range again increases but the median decreases. However, the distribution in the pedestrians’ similarity values is much more than the cyclists’ values. The fourth model is composed of all the previous parameters plus the external contexts (i.e., path difficulty and slope). The same as previous trends, the similarity range increases but the median decreases. Although the number of trajectories that share common characteristics are low when taking into account all the spatial, temporal, internal contexts, and external contexts in the implementation, the results become much more realistic and close to reality for both datasets.
In addition, to assess the influence of the internal and external contexts on the similarity output, a one-way analysis of variance (ANOVA) test, with a 95% confidence level, is applied on the results. Furthermore, a number of sensitivity analyses are applied on the datasets. The outcomes demonstrate meaningful influence of contexts on the similarity results of trajectories.
 
Conclusion
In this research a novel approach based on fuzzy systems is developed for multi-dimensional similarity measure of trajectories while accounting both internal and external context information. This approach enhances the previous similarity functions that only use spatial and temporal data. The developed models were applied on two real trajectory datasets, which were capable of handling both quantitative and qualitative information. The results indicate the effectiveness of the proposed context-aware similarity measure approach in revealing the commonalities between trajectories in multi dimensions.

کلیدواژه‌ها [English]

  • Trajectory
  • Similarity measure
  • Context-awareness
  • HFIS
  • Multi-objective optimization

1- شاعری، عباسپور؛ محمد، رحیم‌علی؛ 1393، مقایسه توابع فاصله اندازه‌گیری میزان شباهت در خطوط سیر مکانی، نشریه علمی پژوهشی علوم و فنون نقشه برداری، 4(3):201-221.

2- شریف، آل‌شیخ؛ محمد، علی‌اصغر؛ 1394، مروری بر فرآیند حرکت اشیاء نقطه‌ای و روش‌های اندازه‌گیری تشابه خطوط‌سیر آن‌ها، نشریه علمی ترویجی مهندسی نقشه برداری و اطلاعات مکانی، 7(1):41-54.

3- شریف، آل‌شیخ؛ محمد، علی‌اصغر؛ 1395، اندازه‌گیری تشابه خطوط سیر مبتنی بر داده‌های بافتی در فضای اقلیدسی محدود، نشریه علمی پژوهشی علوم و فنون نقشه برداری،5(4):113-125.

4- Abbaspour, R. A., M. Shaeri and A. Chehreghan (2017). "A method for similarity measurement in spatial trajectories." Spatial Information Research25(3): 491-500.

5- Benítez, A. D. and J. Casillas (2013). "Multi-objective genetic learning of serial hierarchical fuzzy systems for large-scale problems." Soft Computing17(1): 165-194.

Buchin, K., M. Buchin, M. Van Kreveld and J. Luo (2011). "Finding long and similar parts of trajectories." Computational Geometry44(9): 465-476.

6- Buchin, M., S. Dodge and B. Speckmann (2014). "Similarity of trajectories taking into account geographic context." Journal of Spatial Information Science(9): 101-124.

7- Dodge, S., P. Laube and R. Weibel (2012). "Movement similarity assessment using symbolic representation of trajectories." International Journal of Geographical Information Science26(9): 1563-1588.

8- Furtado, A. S., L. O. C. Alvares, N. Pelekis, Y. Theodoridis and V. Bogorny (2018). "Unveiling movement uncertainty for robust trajectory similarity analysis." International Journal of Geographical Information Science32(1): 140-168.

9- Furtado, A. S., L. L. Pilla and V. Bogorny (2018). "A branch and bound strategy for Fast Trajectory Similarity Measuring." Data & Knowledge Engineering.

10- Herrera, F., M. Lozano and J. L. Verdegay (1998). "Tackling real-coded genetic algorithms: Operators and tools for behavioural analysis." Artificial intelligence review12(4): 265-319.

11- Ilarri, S., D. Stojanovic and C. Ray (2015). "Semantic management of moving objects: A vision towards smart mobility." Expert Systems with Applications42(3): 1418-1435.

12- Laube, P. (2014). Computational Movement Analysis, Cham: Springer International Publishing.

13- Lin, D. (1998). An information-theoretic definition of similarity. ICML.

14- López, V., A. Fernández, M. J. del Jesus and F. Herrera (2013). "A hierarchical genetic fuzzy system based on genetic programming for addressing classification with highly imbalanced and borderline data-sets." Knowledge-Based Systems38: 85-104.

15- Magdy, N., T. Abdelkader and K. El-Bahnasy (2018). "A comparative study of similarity evaluation methods among trajectories of moving objects." Egyptian Informatics Journal.

16- Parent, C., S. Spaccapietra, C. Renso, G. Andrienko, G. Andrienko, V. Bogorny, M. L. Damiani, A. Gkoulalas-Divanis, J. Macedo, N. Pelekis, Y. Theodoridis and Z. Yan (2013). "Semantic trajectories modeling and analysis." ACM Computing Surveys45(4): 1-32.

17- Sharif, M. and A. A. Alesheikh (2017). "Context-awareness in Similarity Measures and Pattern Discoveries of Trajectories: A Context-based Dynamic Time Warping Method." GIScience & Remote Sensing54(3): 426-452.

18- Sharif, M., A. A. Alesheikh and B. Tashayo (2018). Similarity Measure of Trajectories Using Contextual Information and Fuzzy Approach. Adjunct Proceedings of the 14th International Conference on Location Based Services, ETH Zurich.

19- Spaccapietra, S., C. Parent and L. Spinsanti (2013). Trajectories and Their Representations. Mobility data : modeling, management, and understanding. C. Renso, S. Spaccapietra and E. Zima´ nyi. New York, USA, Cambridge University: 394.

20- Tashayo, B. and A. Alimohammadi (2016). "Modeling urban air pollution with optimized hierarchical fuzzy inference system." Environmental Science and Pollution Research23(19): 19417-19431.

21- Xia, Y., G.-Y. Wang, X. Zhang, G.-B. Kim and H.-Y. Bae (2010). Research of Spatio-temporal Similarity Measure on Network Constrained Trajectory Data. Rough Set and Knowledge Technology: in Proceedings 5th International Conference, RSKT 2010, Beijing, China, October 15-17, 2010. . J. Yu, S. Greco, P. Lingras, G. Wang and A. Skowron. Berlin, Heidelberg, Springer Berlin Heidelberg: 491-498.

22- Yuan, Y. and M. Raubal (2014). "Measuring similarity of mobile phone user trajectories– a Spatio-temporal Edit Distance method." International Journal of Geographical Information Science28(3): 496-520.

23- Zhang, C., J. Han, L. Shou, J. Lu and T. La Porta (2014). "Splitter: mining fine-grained sequential patterns in semantic trajectories." Proceedings of the VLDB Endowment7(9): 769-780.

24- Zhang, X., E. Onieva, A. Perallos, E. Osaba and V. C. S. Lee (2014). "Hierarchical fuzzy rule-based system optimized with genetic algorithms for short term traffic congestion prediction." Transportation Research Part C: Emerging Technologies43: 127-142.