Introduction
Traditional Point-of-Interest (POI) recommendation systems primarily focus on relevance, often leading to "filter bubbles" where users are suggested a list of homogeneous locations based on their past behavior. For instance, a user who frequently visits malls might receive a list of ten different malls. While accurate, such recommendations lack the variety necessary for a rich urban experience. This paper addresses this limitation by introducing a framework that balances user relevance with Information Coverage, ensuring recommendations span a diverse set of location categories.
The Information Coverage Problem
Most existing POI recommenders operate on similarity: if a user has visited many restaurants, the system recommends more restaurants. However, real-world user behavior suggests a natural inclination toward exploration.
As shown in Figure 3, data analysis of Foursquare (Singapore) and Gowalla (Austin) datasets reveals an "exploration incline." In any given month, approximately 25-30% of a user's visited categories are entirely new to them. This empirical evidence validates the need for diversity-aware recommendation systems that can provide a "flavor" of the city by covering various categories like museums, parks, and cafes alongside preferred categories.
Methodology: The top-K LC-POI Framework
The authors propose a multi-objective optimization framework, top-K LC-POI, which utilizes a scoring function $\sigma(L)$ that combines two primary factors:
- Relevance ($R(L)$): Calculated using the User-Spatial-Temporal (UST) framework, accounting for user similarity and geographical influence.
- Information Coverage ($I(L)$): A novel metric measuring how well a set of POIs covers different location categories. To prevent ubiquitous categories (e.g., "Office") from dominating, the authors adapt TF-IDF logic, treating categories as "words" and cities as "documents" to prioritize unique local offerings.
Algorithmic Optimization
Maximizing both relevance and category diversity is an NP-hard combinatorial problem. However, the authors prove that the scoring function exhibits Monotone Submodularity—a property of "diminishing returns" where adding a POI to a smaller set increases the total score more than adding it to a larger set.
This mathematical property allows for the use of a Greedy Algorithm (GA) with a guaranteed approximation ratio of $(1 - 1/e)$. To ensure real-time performance, a Pruning Optimization (GA+PO) is introduced to discard POIs with low individual scores before the main search, significantly reducing computational overhead.
Experimental Evaluation
The framework was evaluated using real-world check-in data from Foursquare (Singapore) and Gowalla (Austin).
Key Results
- Diversity and Accuracy: The proposed Greedy Algorithm improved category diversity (Shannon entropy) by 35% on Foursquare and 13% on Gowalla compared to the baseline, while maintaining approximately 97% of the precision and recall of relevance-only methods.
- Efficiency: The pruning optimization proved critical for scalability.
As illustrated in Figure 6, the GA+PO approach drastically reduces computation time compared to the standard GA, making it suitable for practical deployment even as the number of requested recommendations ($K$) or the diversity weight ($\beta$) increases.
Conclusion
By formalizing Information Coverage and leveraging the property of submodularity, this work provides a robust solution for diversifying POI recommendations without sacrificing accuracy. The introduction of the pruning optimization ensures that these high-quality, diverse recommendations can be generated efficiently in real-time environments. Future work may explore automated parameter tuning to adapt to individual user's explorative tendencies.
Summary updated