Analysis of co-movement pattern mining methods for recommendation Extended Abstract Sergio Torrijos Alejandro Bellogín Universidad Autónoma de Madrid Universidad Autónoma de Madrid Madrid, Spain Madrid, Spain sergio.torrijos@estudiante.uam.es alejandro.bellogin@uam.es ABSTRACT Location-Based Social Networks allow users to share the Points- of-Interest they visit, hence creating trajectories throughout their usual lives – even though they are also used by tourists to explore a city. There exist several algorithms in the trajectory pattern mining area able to discover and exploit interesting patterns from trajectory data, such as which objects tend to move together (co-movement), however, to the best of our knowledge, they have not been used with data coming from that type of systems. In this work, we analyse the extent to which these techniques can be applied to that type of data and under which circumstances they might be useful. 1 INTRODUCTION AND BACKGROUND The aim of Recommender Systems (RS) is to help users in finding relevant items, usually by filtering large catalogues and taking into ac- count the users’ preferences. Collaborative Filtering (CF) systems can be considered as the earliest and most widely deployed recommen- Figure 1: Check-ins collected from two users (one in blue and dation approach [9], suggesting interesting items to users based on the other in green) in the city of New York. Note that there are the preferences from “similar” or related people [14]; although other many more places in common in the center of Manhattan. types of recommendation algorithms exist, such as content-based in a more general context, moving objects, for instance, to cluster systems and social filtering, among the most popular ones [7, 13]. or identify them in order to track their positions or analyse their be- Because of the increasing number of users registered in Location- haviour [21]. Examples of applications and services could be animal Based Social Networks (LBSNs), where users share the venues, places, analysis, social recommendations, and traffic planning, where data or Points-of-Interest (POI) they visit; POI recommendation approaches would arrive from chips for animal telemetry, wearable devices, or have become particularly useful and several specific techniques have vehicles with GPS [6]. More specifically, many of these problems been proposed in recent years. In particular, such methods tend to are solved under the umbrella of discovering co-movement patterns, incorporate inherent properties of these systems, such as social, which refers to finding groups of objects travelling together for a geographical, or temporal information [11, 12]. certain period of time, hence exploiting both the temporal and spa- A recent trend in the literature is to exploit trajectory pattern min- tial dimensions. There exist several co-movement pattern methods, ing methods for recommendation. Some examples include creating such Flock, Convoy, Swarm, or ST-DBSCAN [6, 15]. They all impose recommenders for itineraries based on geo-tagged photos [3] and, different constraints on what a group or a co-movement is when in a more general context, exploiting the GPS trajectories left by the solving the problem, and hence they evidence different complexities, users to suggest interesting locations [4, 20]. However, there are still this is why parallel and scalable solutions are needed [6]. In the next several trajectory pattern mining methods that have not been used sections, we discuss some potential applications of these methods for recommendation yet. More specifically, in this extended abstract for recommendation and how to address the scalability issues. we discuss the possibility to integrate user mobility patterns for rec- ommendation, in particular, and as a first solution, to compute similar 2 EXPLOITING TRAJECTORY users (according to the detected trajectory patterns) as a straightfor- PATTERNS FOR RECOMMENDATION ward way to include such information into well-known recommen- A simple approach to exploit some of the most common trajectory dation algorithms. We do this by focusing on the techniques known pattern mining methods such as querying, indexing, or retrieval (i.e., as co-movement pattern methods and those derived by them. similarity metrics between trajectories) [5] is to perform some kind In fact, the literature on trajectory pattern mining provides sev- of filtering instead of a pure recommendation task, that is, to present eral methods to compute similarities either between trajectories or, the user the most similar trajectory(ies) with respect to her previous "Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons trajectories, her last query, or her inferred tastes. A paradigmatic License Attribution 4.0 International (CC BY 4.0)." example of this type of filtering is the well-known “customers who 1 Sergio Torrijos and Alejandro Bellogín bought this item also bought” from Amazon, where the recommen- Under this perspective, and considering the toy example shown dation is based on an item, and not on an entire user history [10]. in Figure 1, those two users may be found as very similar or not A straightforward extension from this paradigm is to use those depending on whether they tend to visit the same places at simi- similarities to obtain user neighbourhoods, and use those neighbours lar times. Hence, with this similarity function we impose a harder in a standard CF algorithm. By doing this, we would assume that constraint on the time dimension than other strategies. However, users are similar if their trajectories in the system are similar. Obvi- it would be very easy to tune such model so that interactions too ously, other factors such as weather, needs, or prices could make two far from each other are heavily penalised; we are working on these similar trajectories in the movement different in motivation; the con- kinds of explainable, but efficient, models at the moment. tribution of these additional aspects shall be further investigated in Finally, in this work we have mostly discussed how to integrate the future. We have performed some preliminary experiments with some pattern mining methods in a very specific recommendation this type of algorithm and the results are, so far, positive [16]. For this, task: that of recommending the next POI the user should visit, how- we use standard methods to compute trajectory similarities such as ever, it is left as future work to fit these (or other) methods into Dynamic Time Warping and Hausdorff distance [17], although some more complex tasks such as trip recommendation [2], successive kind of transformation is needed first to obtain trajectories from recommendation [19] and so on, where we believe they could bring the user’s interactions with the items (usually in the form of check- interesting insights and solutions to these problems. ins). Then, once a user 𝑢 is defined as a set of several trajectories (𝑥 𝑢1 ,···,𝑥𝑛𝑢 ), we would compute the following similarity by averaging REFERENCES the trajectory similarity values over all pairs for both users: [1] Alejandro Bellogín and Javier Parapar. 2012. Using graph partitioning techniques for neighbour selection in user-based collaborative filtering. In RecSys. ACM, 𝑛 𝑚 213–216. 1 ÕÕ [2] Igo Ramalho Brilhante, José Antônio Fernandes de Macêdo, Franco Maria Nardini, sim(𝑢,𝑣) = tsim(𝑥 𝑢𝑗 ,𝑥𝑘𝑣 ) (1) Raffaele Perego, and Chiara Renso. 2013. Where shall we go today?: planning 𝑛 ·𝑚 𝑗=1 touristic tours with tripbuilder. In CIKM. ACM, 757–762. 𝑘=1 [3] Guochen Cai, Kyungmi Lee, and Ickjai Lee. 2018. Itinerary recommender system with semantic trajectory pattern mining from geo-tagged photos. Expert Syst. where 𝑛 and 𝑚 correspond to the number of trajectories of users 𝑢 Appl. 94 (2018), 32–40. and 𝑣, respectively, and tsim(·,·) is any trajectory similarity function. [4] Jian Dai, Bin Yang, Chenjuan Guo, and Zhiming Ding. 2015. Personalized route rec- If we analyse the example shown in Figure 1, we argue that some ommendation using big trajectory data. In ICDE. IEEE Computer Society, 543–554. [5] Ke Deng, Kexin Xie, Kevin Zheng, and Xiaofang Zhou. 2011. Trajectory Indexing parts of each user trajectory are quite close to each other and, hence, and Retrieval. In Computing with Spatial Trajectories. Springer, 35–60. similar, whereas other parts are very distant to each other. [6] Qi Fan, Dongxiang Zhang, Huayu Wu, and Kian-Lee Tan. 2016. A General and Parallel Platform for Mining Co-Movement Patterns over Large-scale Trajectories. The next step is to explore more complex algorithms tailored at Proc. VLDB Endow. 10, 4 (2016), 313–324. finding objects that move together, such as Flock or Swarm [8], so [7] Ido Guy. 2015. Social Recommender Systems. In Recommender Systems Handbook. that users are clustered into groups that move in a similar way. Once Springer, 511–543. [8] Hoyoung Jeung, Man Lung Yiu, and Christian S. Jensen. 2011. Trajectory Pattern these clusters are available, nearest-neighbours algorithms can be Mining. In Computing with Spatial Trajectories. Springer, 143–177. used again for recommendation [1]. However, these methods are [9] Yehuda Koren and Robert M. Bell. 2015. Advances in Collaborative Filtering. In computationally very expensive and ad-hoc solutions are typically Recommender Systems Handbook. Springer, 77–118. [10] Greg Linden, Brent Smith, and Jeremy York. 2003. Amazon.com Recommendations: implemented to deal with real life trajectory databases [6]. Item-to-Item Collaborative Filtering. IEEE Internet Comput. 7, 1 (2003), 76–80. [11] Yiding Liu, Tuan-Anh Pham, Gao Cong, and Quan Yuan. 2017. An Experimental Evaluation of Point-of-interest Recommendation in Location-based Social 3 DISCUSSION AND FUTURE WORK Networks. PVLDB 10, 10 (2017), 1010–1021. [12] Yong Liu, Wei Wei, Aixin Sun, and Chunyan Miao. 2014. Exploiting Geographical So far, we have presented some recommendation applications where Neighborhood Characteristics for Location Recommendation. In CIKM. ACM, methods from the trajectory pattern mining area could be useful. 739–748. However, the inherent computational problem that most of these [13] Pasquale Lops, Marco de Gemmis, and Giovanni Semeraro. 2011. Content-based Recommender Systems: State of the Art and Trends. In Recommender Systems methods suffer still remains. Nonetheless, we want to shed light on Handbook. Springer, 73–105. this issue and bring the attention to two specific aspects of LBSN [14] Xia Ning, Christian Desrosiers, and George Karypis. 2015. A Comprehensive Survey of Neighborhood-Based Recommendation Methods. In Recommender recommendation that might alleviate, to some extent, this problem. Systems Handbook. Springer, 37–76. First, in LBSNs users typically interact with POIs or venues, hence [15] Omar Ernesto Cabrera Rosero and Andres Oswaldo Calderon Romero. 2018. FP- the data points are limited, in contrast with trajectory data where Flock: An algorithm to find frequent flock patterns in spatio-temporal databases. [16] Sergio Torrijos, Alejandro Bellogín, and Pablo Sánchez. 2020. Discovering Related the amount of points in the space is virtually infinite [18]; hence, the Users in Location-Based Social Networks. In User Modeling, Adaptation, and sparsity of the items could work in our favour. Personalization - 28th International Conference, UMAP 2020, Genoa, Italy, July Second, it is a well-known fact in recommendation that there is a 12-18, 2020. Proceedings (Lecture Notes in Computer Science). Springer. [17] Dong Xie, Feifei Li, and Jeff M. Phillips. 2017. Distributed Trajectory Similarity large popularity bias; this means that part of the user preferences are Search. Proc. VLDB Endow. 10, 11 (2017), 1478–1489. very easy to predict. Hence, simple methods that exploit this type of [18] Dongzhi Zhang, Kyungmi Lee, and Ickjai Lee. 2019. Mining hierarchical semantic periodic patterns from GPS-collected spatio-temporal trajectories. Expert Syst. pattern may work quite efficiently for recommendation; for instance, Appl. 122 (2019), 85–101. exploiting common visits within a temporal window. In this sense, [19] Shenglin Zhao, Tong Zhao, Haiqin Yang, Michael R. Lyu, and Irwin King. 2016. this strategy would be an adaptation of the frequently used overlap STELLAR: Spatial-Temporal Latent Ranking for Successive Point-of-Interest Recommendation. In AAAI. AAAI Press, 315–322. measure in classical recommendation scenarios but tailored for a [20] Yu Zheng, Lizhu Zhang, Xing Xie, and Wei-Ying Ma. 2009. Mining interesting domain where the temporal dimension is very important. Some pre- locations and travel sequences from GPS trajectories. In WWW. ACM, 791–800. liminary experiments with real-world data evidences our hypothesis [21] Yu Zheng and Xiaofang Zhou (Eds.). 2011. Computing with Spatial Trajectories. Springer. that this simple method is both efficient and effective [16]. 2