Right time, right place: A collaborative approach for more accurate context-awareness in mobile apps and ads
The right information delivered at the right time can make apps and ads more appealing and relevant to customers: a traffic app that auto-updates for the work or home commute as appropriate; a restaurant that offers lunch coupons for people who work in the area but dinner coupons for people who live nearby. This level of customization requires taking into account a user's immediate context, something that is not easy to do. It requires both location data and a temporal framework that gives meaning to each location, identifying it as home, work, commute, or another place frequented by a user. But location data is often surprisingly sparse for any one user. To overcome sparsity and construct reliable weekly routines for individual users, researchers integrated global temporal patterns inferred from the entire data set with user-specific spatiotemporal data. The resulting method is entirely data-driven—requiring no labeling—and flexible to accommodate variations in a user's weekly schedule.
The location data needed for context-aware ads and apps is surprisingly sparse for any single user. For privacy and to conserve energy, most smart phone apps log users' locations only when the app is active. The result is that location data sets collected from apps comprise many users but few observations per user. This sparsity makes it difficult to know how a particular GPS position is relevant to a user, whether it represents a work place, home, a point along the morning or evening commute, or some other frequently visited destination. It's this contextual information that allows companies to customize their apps and ads for their customers' immediate or near-future locations. Local businesses especially benefit when they can accurately predict who is or will soon be in their area.
(It's not just companies that want context-aware apps and ads; there is evidence users do, too. Cisco found that half of customers surveyed would use coupons sent from a nearby store.)
Location data for any single user may be too sparse to understand when a user transitions between places, but the collection of data across all users represents much more information that can help illuminate broader patterns. To exploit this collective information, four researchers—Berk Kapicioglu, David S. Rosenberg, Robert Schapire, and Tony Jebara—developed a data-driven method that learns people's important places based on global temporal patterns inferred from the entire data set. They described this method in the paper Collaborative Place Models presented in July at the International Joint Conference on Artificial Intelligence.
Collaborative place models differ from previous methods that first label locations according to time of day and day of week. By assuming, for example, a 9-to-5 workday Monday through Friday, methods that rely on labeling might average positions between 8am and 6pm and call that home while averaging positions between 9 and 5 and calling that work. It's an intuitive approach but it lacks flexibility—not everyone has the same schedule—and it ignores the commute, which can be a significant amount of time for some people and a missed opportunity for those businesses located along the commute.
Rather than imposing a static temporal framework, collaborative place models learn the quantitative relationship between week-hours by inferring similarities across all users, relying on Bayesian estimation techniques to do so. With a global temporal framework thus set, the relevance of the sparser latitude-longitude GPS coordinates from individual users can then be determined from how they fit into the global temporal pattern. In this way, the model re-constructs a particular user's home-work-commuting schedule even though a user might have been observed only at Thursday 3pm and Monday 1pm.
To prove the concept, the researchers tested the model using two real-world data sets, a sparse one collected from a mobile ad exchange, and a dense data set from a cellular carrier. In both cases, the only inputs were user IDs, latitudes, longitudes, and time stamps. (Data was anonymized by removing all personal information.)
With data aggregated across all users, a strong, global temporal pattern emerged fairly quickly, one that contained within it several temporal clusters correlated with work, morning and evening commutes, leisure times after work, and sleeping at night. With the global pattern thus established, the individual spatiotemporal patterns of individual users became apparent even with few data points associated with each user.
The spatial extent of place types associated with temporal clusters were determined by replacing multiple observations logged during the same hour with their geometric median (computed using Weiszfeld's algorithm and by clustering nearby points using a Gaussian mixture model that is a subcomponent of the collaborative place model). This contrasts with the use of averaging in other place models to handle redundant observations and the noise that occurs from GPS errors and from having multiple cell towers covering the same location; by not averaging, the collaborative place model avoids the strange results sometimes caused by deviations in the regular routine, such as a late work evening or a night or weekend away from home.
Flexibility was built into the model by allowing users to have varying numbers of places or week hours. This flexibility turned out to be key; an early, simpler prototype that constrained users to have the same week-hour distribution performed worse than a baseline model.
The strong, well-defined pattern on the left results from combining global weekly patterns with spatiotemporal data of an individual user arbitrarily chosen from the dense dataset. The right distribution (for the same user) represents a previous baseline model that did not infer global patterns and so as not able to correctly identify important places.

In the end, data by itself was enough to reliably assess a user's spatiotemporal schedule. Without the need to label or average location places, the collaborative approach of combining global patterns with sparse user location data reduced the median distance error by 8% from a simpler non-collaborative baseline model.
-Linda Crane
Posted 12/1/2015