Daniele Quercia ABSTRACTYahoo! Research Barcelona Rossano Schifanella Yahoo! Research Barcelona Universitá degli Studi di Torino Luca Maria Aiello Yahoo! Research Barcelona When providing directions to a place, web and mobile mapping services are all able to suggest the shortest route. At times, however, when visiting a friend, we do not necessarily take the fastest route but might enjoy alternatives that, for example, offer beautiful urban sceneries. We have recently started to work on a framework that automatically generates routes that are not only short but also emotionally pleasant (e.g., that are happy). To quantify the extent to which urban scenes are pleasing, this framework uses a crowd-sourcing web platform that shows two street scenes of a city and let users vote on which one looks more beautiful, quiet, and happy. Such crowd-sourced ground truth allows us to build a graph of locations, weighted by the pleasantness scores, upon which pleasant routes can be extracted. We have initially applied this framework in the context of London and have obtained promising preliminary results. 1 BEYOND SHORTEST PATHS: EMOTIONAL SHORTCUTS At times, we do not take the fastest route but enjoy alternatives that offer beautiful sceneries. When walking, one would prefer tiny streets with trees over large ones with cars. Web and mobile mapping services do not go beyond offering the route between two locations that is shortest. To capture which routes people find interesting and enjoyable, researchers have started to analyze the digital traces left behind by users of online services like Flickr or Foursquare. Early work on the problem of recommending routes in the city focused on finding efficient routes, mainly for people who either travel by car [1] or use public transports [2]. After that initial work, researchers moved to the problem of recommending distinctive parts of the city and interesting routes [3] [4]. The idea behind this later work is to use geo-referenced online content (e.g., Flickr pictures) to learn and recommend popular trajectories [5] [6]. De Choundry et al. [7] and El Ali et al. [8] both used Flickr data to mine popular spatio-temporal sequences of picture uploads and to then recommend the corresponding urban routes. As for algorithmic solutions, De Choundry et al. used an orienteering algorithm that maximizes the number of interesting locations visited; El Ali et al. used a sequence alignment algorithm borrowed from biology; and Meng et al. used ant colony optimization [9]. Most of this work has been tailored to touristic use cases, and only limited research effort has gone into methodologies for evaluating route recommenders in the wild [10]. More recently, given the popularity of mobile social-networking applications, researchers have been able to explore personalization strategies for tourists and residents alike. Cheng et al. used a Baeysian model to generate personalized travel recommendations, while Kurashima et al. used Markovian models [11]. Previous work has, however, not considered the role of emotions in the urban context when recommending routes and there has not been any work that considers people's emotional perceptions of urban spaces when recommending routes to them. Yet, psychogeography dates back to 1955. This was defined as 'the study of the precise laws and specific effects of the geographical environment, consciously organized or not, on the emotions and behavior of individuals' [12]. The psychogeographer 'is able both to identify and to distill the varied ambiances of the urban environment. Emotional zones that cannot be determined simply by architectural or economic conditions must be determined by following the aimless stroll (derive)' [13]. Mobile applications have been recently proposed to ease derives: these include Derive app, Serendipitor, Drift, and Random GPS (http://deriveapp.com/s/v2/, http://serendipitor.net/site/, http://www.brokencitylab.org/drift/, http://nogovoyages.com/random_gps.html). The goal of our work is to go beyond supporting derives and to propose a framework to automatically generate routes that are not only short but also emotionally pleasant: routes based on people's emotional experience of the city. To this end, we build a crowd-sourcing platform that shows two street scenes in London (out of hundreds), and a user votes on which one looks more beautiful, quiet, and happy (Section 2). We collect votes from more than 3.3K individuals and translate them into quantitative measures of urban perception (i.e., emotion scores). To then quantify location popularity in addition to beauty perception, we crawl all Foursquare venues for the entire city of London. The information collected can be combined and mapped on a graph of locations weighted with costs on its edges (walking distance between points) and gains on the nodes (value of beauty, happiness or quietness for that area) that could be used as input to algorithms of gain-maximization of graph trails (Section 3). 2 CROWDSOURCING PERCEPTIONS OF THE CITY We build a crowdsourcing web site on which visitors rate urban scenes along three qualities: beauty, quietness, and happy [14]. The site's goal is to learn the extent to which different city's locations are considered to be beautiful, quiet and make people happy. We choose those three qualities as proxies for well-studied attributes in the 1960s urban studies. A Why Quiet, Beauty, and Happy Our choice has to be thought in the context of 1960s urban studies by Kevin Lynch [15] and Jane Jacobs [16], and of later work by Christopher Alexander [17]. Quiet. In the noise of a city, it might be hard to find quiet places. That is why a variety of applications has been designed to discover such places in big cities. The Economist `Thinking Spaces' application allows the global community of Economist readers to create, share and explore the spaces where they think and get new ideas (http://thinkingspace.economist.com/). More recently, sound Artist Jason Sweeney proposed a platform where people crowdsource and geo-locate quiet spaces, share them with their social networks, and take audio and visual snapshots. It is called Stereopublic (http://www.stereopublic.net/) (Crowdsourcing the Quiet) and is 'an attempt to both promote `sonic health' in our cities and offer a public guide for those who crave a retreat from crowds' - both for those in need of quietness, but also for people with disabilities, like autism and schizophrenia. These efforts are best explained by the universal need for quiet spaces, and such a need has been widely discussed in the literature. In A Pattern Language [17], Alexander et al. argued for Quiet Backs (Pattern 59), for example: 'Any one who has to work in noise, in offices with people all around, needs to be able to pause and refresh himself with quiet in a more natural situation'. This book details 253 patterns and put them together to create a new language. These patterns are timeless entities (e.g., use of materials, presence of street cafe) that the authors believe must be present in order for an environment to be pleasing, comfortable, and make people satisfied with their lives. Each pattern is written as a set of problems and documented solutions. One of the suggested solutions for Pattern 59 is to 'give the buildings in the busy parts of town a quiet back behind them and away from the noise'. Beauty. In The Death and Life of Great American Cities, Jane Jacobs [16] offered a critique of 1950s urban planning policy and of modernism. She dedicated an entire chapter on Visual Order, borrowing from the work of her contemporary Kevin Lynch. She argued against urban renewal and separation of uses (i.e., residential, industrial, commercial), and against the transformation of town planning into a 'pseudo science' (as she did put it) with nothing to say on aesthetics. Therefore, to capture the importance of overall visual order and harmony, we resort to a question testing the concept of `beauty' as it is easy to grasp by people (as opposed to concepts such as `visual order' or `aesthetically pleasing') and is thus amenable to a crowd-sourcing game. This is in line with the literature on environmental aesthetics. In 1967, Peterson proposed a quantitative analysis of public perceptions of neighborhood visual appearance [18]. He did so by choosing ten variables that reflected visual appearance (e.g., preference for the scene, greenery, open space, safety, beauty) and having 140 individuals rate 23 pictures of urban scenes in the Chicago metropolitan area for each of those ten variables. He found that beauty and safety are approximately collinear with preference for a scene, suggesting that 'beauty of visual appearance is in fact synonymous with perception of visual pleasure and, hence, desirability of visual appearance' [18]. Happiness. Some of the 1960s urban studies tried to systematically relate well-being in the urban environment (i.e., happiness) to the desire for visual order, beauty, and aesthetics. In The Image of the City [15], Kevin Lynch illustrated what city planners should do to make the city's image more vivid and memorable to the city dwellers. Lynch reported that people understood their surroundings in consistent and predictable ways. He introduced a new criterion - imageability - positing that good imageability allows city dwellers to feel at home and increase their community well-being. Lynch suggested that people imagine a city (they form their mental maps of it) within a setting that is best described by five primary elements: paths, edges, nodes, landmarks, and districts. To provide a better visual order, Jane Jacobs proposed guidelines that would result into neighborhoods of mixed uses, short blocks, buildings of various ages and states of repair, and density [16]. Salvaging urban projects, she added, 'need, among other things, casual public characters, lively well-watched, continuously used public spaces, easier and more natural supervision of children, and normally city cross-use of their territory by people from outside it. In short, these projects need to take on the qualities of healthy city fabric' [16]. B Crowdsourcing Site How it works. The web game picks up two random locations from either Google Street View or Geograph (http://bit.ly/SebbCj), and ask users which one of the two is more beautiful, quiet, or happy. We chose those two picture sources to control for biases that might be introduced by the quality of pictures. Users can also opt for 'Can't Tell', if undecided on which picture to click on. With each selection the user is asked to guess the percentage of other people who shared their view, scoring points for correct guesses which can then be shared through social media. To avoid sparsity problems (too few answers per picture), a random scene is selected within a 300-meter radius from a subway station and within the bounding boxes of census areas. This results into 258 Google Street views and 310 Geograph images, all of which have ratings that are roughly normally distributed. The number of subway stations for which we have at least one rating is 242 (out of 273). By collecting a large number of responses across a large number of participants, we are now able to determine which urban scenes are perceived in which ways along the three qualities. Built-in Engagement. After performing two beta tests with our lab's colleagues, we have found that the game was not engaging enough. To increase the likelihood that external people would adopt the platform, we resort to some simple engagement strategies [19]. Those strategies include giving points, creating a sense of freshness and of purpose. Pictures are chosen randomly to create a sense of freshness and increase replay value [20]. To increase the sense of belonging to a community, users could post their scores on Facebook and Twitter after each round. Additionally, users' votes are used to rank the urban scenes, and top-ranked images are shown under three different pages on the site, each of which corresponds to beautiful, quiet, and happy scenes. We also offer personalized suggestions of pictures to each user based on the user's votes using an item-based collaborative filtering algorithm [21].  Resulting Ratings. We have made the final version of the platform publicly available and issued a press release in September 2012. Shortly after that, the site was featured in major newspapers and news sites, including BBC News. After 4 months, we collected data from as many as 3,301 participants: 36% connecting from London (IP addresses), 35% from the rest of UK, and 29% outside UK. A fraction of those participants (515) specified their personal details: the percentage of male-female for those participants is 66%-34%, and the average age is 38.1 years old. Upon processing 17,261 rounds of annotation (each of which annotates at most ten pairs of pictures), we rank pictures by their scores for beauty, quiet, and happiness, and those scores are based on the fraction of votes the pictures have received. The resulting distribution of answers for each picture has a median of 171 answers per scene for beauty, 12 for quiet, and 16 for happy. The mean values of answers for the three qualities are different as the default question is that on beauty, which thus preferentially attracts more votes, while the other two are accessible from a drop-down menu. Interestingly, despite the ordering has the happiness question last, that question has still attracted more votes than the question on quietness. To control for picture quality, we did not opt for Flickr images, as people often upload pictures of extremely different levels of quality. We instead use two kinds of pictures of which quality is comparable: Google Street View pictures captured by camera-mounted cars, and Geograph pictures provided by volunteers with the goal of mapping the whole Great Britain and Ireland in a crowdsourcing fashion. We use multiple images of the two types at the same locations. We find that user ratings are not correlated with objective measures of image quality: we find no correlation between images' ratings and their sharpness and contrast levels, both of which are used as proxy for quality [22]. Location Popularity. In addition to capturing the extent to which a location is pleasing, we quantify the location's popularity, i.e., whether it is visited by many people. We do so by resorting to Foursquare and crawling all the check-ins in the London area (in Foursquare jargon, check-ins reflect user visits). We consider the geo-referenced tweets collected by Cheng et al. [23], who collected Twitter updates (single tweets) that report Foursquare check-ins all over the world. We take the 224,533 check-ins that fall into Greater London. Those check-ins are posted by 8,735 users. 3 WALKING ON HAPPINESS GRAPHS An effective recommender of pleasant paths between a starting point a and a destination b should provide derives from the shortest path that pass through locations that are not only popular but also make one happy. The starting and destination points can be arbitrarily distant, but because the recommendation takes into account walking paths only, they will be within few kilometers in the practical case. Different locations in the city should be associated with scores that capture the likelihood that those locations will be visited and will be pleasant. This likelihood thus depends on whether a location both tends to be visited by people and makes them happy or, similarly, offers quiet or beautiful urban sceneries. To capture that, we define phappy, that measures the extent to which individuals visit locations that make them happy - same can be done for the quiet and beauty dimensions - and ppopularity that models how likely a certain location will be visited by many people [24]. We consider crowd-sourced happiness scores and popularity on Foursquare, appropriately normalized, to be reasonable proxies for phappy and ppopularity. Using Bayes' law, one could compute p(go|happy, popularity) and assign it to each location - this value could be interpreted as a gain that a person would obtain by visiting that location. One of the final steps of the framework is to connect all the locations in a full graph, with edges weighted on the walking distance between each pair of locations. A graph with costs and gains, together with source and destination nodes, can be processed by algorithms for gain-maximization of graph trails, such as the ones used for the orienteering problem [7], to obtain paths that deviate from the shortest one but offer a more pleasant experience. The cost on the edges assures that the paths will be finite and the additional walking length can be adjusted by appropriately weighting the cost function. Even though the general orienteering problem is NP-hard [7], good approximated algorithms with lower complexity have been developed (e.g., O(log2n), n number of nodes [25]). 4 CONCLUSION This work is at the crossroad of two emerging themes in research: web science and smart cities. The combination of the two opens up notable opportunities for future research [26]. By 2025, we will see another 1.2 billion people living in cities. The good news is that urbanization comes with enormous economic benefits [27]. The bad news is that those benefits will be only realized if we are able to manage the increased complexity that comes with larger cities. The `smart city' agenda is about using technological and computing advances to manage that complexity and create better cities. The goal of this work is to facilitate the exploration of aesthetically pleasing public environments by tapping into the invisible emotional layer of the city. Making such an exploration possible (using, for example, mobile applications) is relatively easy and cheap; seeing exactly what needs to be done is difficult and needs research. We have started to research how to rewire the paths people experience in the city by effectively creating emotional shortcuts, and those shortcuts promise to have important consequences on city dwellers' personal well-being [28]. In the future, we plan to instantiate our recommendation framework for the case of London and to evaluate the quality of recommended paths via extensive user studies. Also, we plan to be able to generalize the framework to any other city, loosening the dependency on the crowdsourced data we collected as emotional ground truth. REFERENCES [1] K.-P. Chang, L.-Y. Wei, M.-Y. Yeh, and W.-C. Peng, “Discovering personalized routes from trajectories,” in 3rd ACM SIGSPATIAL International Workshop on Location-Based Social Networks (LBSN), 2011. [2] B. Ludwig, B. Zenker, and J. Schrader, “Recommendation of personalized routes with public transport connections,” Communications in Computer and Information Science, vol. 53, 2009. [3] S. Van Canneyt, S. Schockaert, O. Van Laere, and B. Dhoedt, “Timedependent recommendation of tourist attractions using Flickr,” in Belgian/Netherlands Artificial Intelligence Conference (BNAIC), 2011. [4] F. S. Peregrino, D. Tom´as, P. Clough, and F. Llopis, “Mapping routes of sentiments,” Tech. Rep. [5] H. Yoon, Y. Zheng, X. Xie, and W. Woo, “Smart itinerary recommendation based on user-generated GPS trajectories,” in Proceedings of the 7th international conference on Ubiquitous intelligence and computing (UIC), 2010. [6] Hyoseok Yoon et al., “Social itinerary recommendation from user-generated digital trails,” Personal and Ubiquitous Computing, vol. 16, no. 5, 2012. [7] M. De Choudhury, M. Feldman, S. Amer-Yahia, N. Golbandi, R. Lempel, and C. Yu, “Automatic construction of travel itineraries using social breadcrumbs,” in 21st ACM conference on Hypertext and hypermedia (HT), 2010. [8] A. El Ali, S. N. van Sas, and F. Nack, “Photographer paths: sequence alignment of geotagged photos for exploration-based route planning,” in Conference on Computer supported cooperative work (CSCW), 2013. [9] X. Meng, X. Lin, and X. Wang, “Intention oriented itinerary recommendation by bridging physical trajectories and online social networks,” in Proceedings of the ACM SIGKDD International Workshop on Urban Computing (UrbComp), 2012. [10] J. Sch¨oning, B. Hecht, and N. Starosielski, “Evaluating automatically generated location-based stories for tourists,” in Proceedings of the conference on Human Factors in Computing Systems - Extended Abstracts (CHI), 2008. [11] T. Kurashima, T. Iwata, G. Irie, and K. Fujimura, “Travel route recommendation using geotags in photo sharing sites,” in Proceedings of the 19th ACM international conference on Information and knowledge management (CIKM), 2010. [12] G. Debord, “Introduction to a Critique of Urban Geography,” 1955. [13] M. Coverley, Psychogeography. Pocket Essentials, 2006. [14] D. Quercia, N. Ohare, and H. Cramer, “Aesthetic Capital: What Makes London Look Beautiful, Quiet, and Happy?” 2014. [15] K. Lynch, The Image of the City, ser. Urban Studies. MIT Press, 1960. [16] J. Jacobs, The Death and Life of Great American Cities. Random House, 1961. [17] C. Alexander, S. Ishikawa, and M. Silverstein, A Pattern Language: Towns, Buildings, Constructions. Oxford University Press, 1977. [18] G. L. Peterson, “A Model of Preference: Quantitative Analysis of the Perception of the Visual Appearance of Residential Neighborhoods,” Journal of Regional Science, vol. 7, no. 1, pp. 19–31, 1967. [19] K. Werbach, For the Win: How Game Thinking Can Revolutionize Your Business. Wharton Press, 2012. [20] L. Von Ahn and L. Dabbish, “Designing games with a purpose,” Communications of ACM, 2008. [21] G. Linden, B. Smith, and J. York, “Amazon.com recommendations: itemto-item collaborative filtering,” IEEE Internet Computing, vol. 7, no. 1, pp. 76–80, 2003. [22] C.-H. Yeh, Y.-C. Ho, B. A. Barsky, and M. Ouhyoung, “Personalized photograph ranking and selection system,” in International Conference on Multimedia (MM), 2010. [23] Z. Cheng, J. Caverlee, K. Lee, and D. Z. Sui, “Exploring millions of footprints in location sharing services.” in Proceedings of the 5th International AAAI Conference on Weblogs and Social Media (ICWSM), 2011. [24] D. Quercia, R. Schifanella, and L. M. Aiello, “The shortest path to happiness: Recommending beautiful, quiet, and happy routes in the city,” 2014. [25] C. Chekuri, N. Korula, and M. P´al, “Improved Algorithms for Orienteering and Related Problems,” in Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms (SODA), 2008. [26] D. Quercia, “Urban*: Crowdsourcing for the Good of London,” in Workshop Keynote at the 22nd International Conference on World Wide Web (WWW), 2013. [27] E. Glaeser, Triumph of the City: How Our Greatest Invention Makes Us Richer, Smarter, Greener, Healthier, and Happier. Penguin, 2011. [28] J. Porteous, Environmental Aesthetics: Ideas, Politics and Planning. Routledge, 1996.    |
E-Letter > STCSN E-Letter Vol.1 No.3 >