With the rising popularity of smart mobile devices, sensor data-based applications have become more and more popular. Their users record data during their daily routine or specifically for certain events. The application WideNoise Plus allows users to record sound samples and to annotate them with perceptions and tags. The app documents and maps the soundscape all over the world. The procedure of recording and including the assignment of tags, has to be as easy-to-use as possible. We therefore discuss the application of tag recommender algorithms in this particular scenario. We show, that this task is fundamentally different from the well-known tag recommendation problem in folksonomies as users do no longer tag fix resources but sensory data and impressions. The scenario requires efficient recommender algorithms that are able to run on a mobile device alone, since Internet connectivity is not always available. Therefore, we evaluate the performance of ten tag recommendation algorithms and discuss their applicability in the mobile sensing use-case.
H.3.3 [Information Storage and Retrieval]: Information Search and Retrieval; H.3.4 [Information Storage and Retrieval]: Systems and Software Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
RecSys ’13 Hong Kong, China Copyright 20XX ACM X-XXXXX-XX-X/XX/XX ...$15.00. Tag recommendation, cold-start problem, SensorFolkSonomy, item features, mobile sensing, citizen science
Mobile devices like smartphones and tablets have become
widely used and are still increasing in popularity. Their
embedded sensors like GPS, microphone, accelerometer, or
gyroscope enable multiple sensing applications [
Citizen science is such a field of urban sensing where a
large numbers of individuals contribute with small amounts
of information to a larger dataset to be analyzed by
researchers. Their goal is often to take part in the broadening
of knowledge about ourselves and our environment [
To obtain this goal, the EveryAware team offers the smartphone application WideNoise Plus – an application to measure and annotate samples from the soundscape using the build-in microphone. Its users can choose to record the average noise level in decibels (dB) over a time span of 5, 10, or 15 seconds. Further, they can state their perception about the recorded noise using four sliders (see Figure 1(a)). There is a slider to express whether they love or hate the noise, whether they perceive it as calm or hectic, whether they are alone or in a social situation, and whether the noise was natural or man-made. Finally, users can add keywords (i.e.,
(a) Perceptions view. (b) Tagging view. tags) to the record to describe it further (see Figure 1(b)). WideNoise Plus was originally developed by WideTag Inc. and was then transferred to EveryAware in 2011 and is available for iOS2 and Android3.
The workflow of taking measurements, choosing perception, and annotating tags must be as easy as possible, since often users are not experienced with mobile technologies or would be discouraged by too complex or time consuming procedures. We therefore deal with the task of recommending tags for records in order to assist users in selecting appropriate keywords.
This task of suggesting such tags is related to the
wellknown tag recommendation problem from tagging systems
(i.e., folksonomies) [
The contributions of the paper are: A formal definition of the tag recommendation problem for sensor data, the evaluation of ten recommender algorithms using real-world data from WideNoise Plus, and the discussion of their performance regarding their resource consumption and their suitability for mobile devices.
The remainder is structured as follows: We will give a 2https://itunes.apple.com/app/id657693514 3https://play.google.com/store/apps/details?id=eu. everyaware.widenoise.android short overview on the related work in the following Section 2. In Section 3 we formalize the task and establish the difference to classical tag recommendations. Further, we introduce proximity-, and perception-based strategies to produce tag recommendations. Next, we describe the experimental setup, including the dataset description in Section 4. The experiments’ results are presented and discussed in Section 5. Finally, we will conclude the paper and point to several aspects for future work. 2.
We will cover two areas of related work, which are relevant for our scenario. First we will introduce the current state of tag recommendation research and how it is applicable to our scenario. Then we will cover the specifics of urban sensing and discuss the motivation for users to tag.
The task of recommending suitable tags for a given
resource to a specific user has been subject to many studies.
A broad variety of solutions has been proposed so far. [
To our scenario only the popularity-based algorithms are
directly applicable as all others depend on a set of fixed
resources. Ubiquitous data as defined by [
The presence of location information enables the use of
spatial approaches. [
Finally, [
port. With their tags, the participants expressed and shared their frustration about the noise pollution caused by the airport.
As outlined in the introduction, there are some special conditions for mobile sensing that must be addressed when choosing recommender algorithms. WideNoise Plus is most often used outdoors without regard to Internet connectivity. Thus, the application must be able to produce recommendations only from data that has been stored on the device and the elements of the current record (the measured noise, the location, and the user’s perceptions). Furthermore, producing recommendations should only consume as little power and runtime as possible. Otherwise, the increased battery drain and long waiting time would discourage users from taking further measurement.
At the moment, it theoretically is still possible to store all relevant tagging information of all users of WideNoise Plus (approximately 150 KB) within the app on a smartphone. However, since the dataset is growing, algorithms that need only some (externally precomputed) subset or aggregation of the historic data are preferable to those that require the complete unprocessed data as their input.
In the following, we first formalize the tag recommendation task for the combination of sensor measurements and subjective perceptions. We then present each of the algorithms, which we will later use and compare. 3.1
Our tag recommendation task is closely related to that
of tagging systems where users assign tags to resources like
videos, photos, websites, or papers. Each of such systems
underlies a structure called a folksonomy. It can be
formalized as a quadruple F = (U, T, R, Y ) [
At first glance, the WideNoise Plus setting fits exactly this problem description. We can identify users and tags and use the different measurements as resources. However, the description does not cover the complexity of our scenario. Each record contains several attributes like the noise level, the location, a timestamp, and the perceptions entered by the user. While certainly in the tagging systems mentioned above the resources come with different attributes as well, in those cases – unlike the perceptions – the properties (e.g., the title of a paper, the content of a video) can be derived from the resource alone. They are the same for any user who has tagged the resource and they are (with the exception of updates) stable. It is therefore desirable, to exclude the perceptions from a resource and to model them as extra entities. Further, the sharing of resources can hardly be modelled in the same way as in folksonomies. Where in tagging systems, one of the key ideas is that users can see, discover, and copy other users’ resources, this is not the same for the WideNoise Plus scenario. While users can tag several noise levels at the same location and time, they do not share the same resources (i.e., measurements). Rather, each measurement is an individual resource and (within the boundaries of physics) almost any combination of sensor measurements is conceivable. For example on the (approximately) same location, the noise measurements of two users might differ due to different times of day or week, different seasons, different company, or events. Moreover, slight variations in the location (that must not even be measurable with GPS) can yield significantly different noise measurements, e.g., being inside a building or outside right next to it. Despite these difficulties, the properties and the perceptions are surely reasonable candidates for exploitation in recommendations. Therefore, we modify the above described notion of folksonomy to that of SensorFolkSonomy as follows.
Definition 1. Given a set of users U , a set of tags T , a set S of sensors with ranges Si, i = 1, ..., |S|, and a set P of perception categories with ranges Pj, j = 1, ..., |P| a SensorFolkSonomy is the 5-tuple S defined as
S := (U, T, S, P, Y ) Hereby, S = |iS=|1 Si and P = |jP=|1 Pj so that Y ⊆ U × T × S × P is the tag assignment relation. A record is a tuple (u, T(u,s,p), s, p), where u ∈ U , s ∈ S, p ∈ P and T(u,s,p) := {t ∈ T | (u, s, p, t) ∈ Y }, such that T(u,s,p) = ∅. In the definition, the symbol as usual denotes the Cartesian product, S is the space of all possible measurement combinations and P is the space of all possible perception combinations. The resulting records are similar to posts in regular folksonomies. The tag recommendation task for a SensorFolkSonomy is now to suggest tags given a user u, a vector of measurements s and a vector p of statements in each perception category.
According to our definition, a WideNoise Plus record can be modelled in the following way: It is recorded by a user u ∈ U who is identified by the unique ID of their mobile device. The unique ID of the mobile device is part of the record and we assume that different devices usually imply different users. The content of one record is given by a vector s ∈ S holding the measured noise level as well as the coordinates of the location. The user can annotate this reading with a freely chosen set of tags t ∈ T and choose values in 4 perception categories: feeling, disturbance, isolation, and artificiality (thus |P | = 4).
The task of tag recommendation is to recommend, for a given user u ∈ U , a given tuple of sensor measurements s ∈ S, and a given tuple of perceptions p ∈ P , a set T˜(u,s,p) ⊆ T of tags. In many cases, T˜(u,s,p) is computed by first generating a ranking on the set of tags according to some quality or relevance criterion, from which then the top k elements are selected. 3.2
We compare several approaches against each other in our experiments. We describe them in the remainder of this section and discuss their advantages and drawbacks regarding resource consumption as well as their suitability for the mobile environments. 3.2.1
A very simple recommendation method is to always suggest those tags t ∈ T that have been assigned the most often so far, i.e., where the set Tt := {(u, t, s, p) ∈ Y | u ∈ U, s ∈ S, p ∈ P } is largest. This yields a non-personalized recommender that will serve as a lower baseline in our comparison of algorithms.
The only input data that would have to be provided for the app are just those top most popular tags. Since also nothing has to be computed, the application would require only very little storage and almost no processing time at all. Therefore, this method would be the best-case in terms of resource requirements.
However, it is expected to be rather bad with regard to the quality of the recommendations, since it is just a static list of the same tags for each record. Table 1 shows the list of the current most popular tags. While there are some country specific tags like the Italian word “esterno” (outdoor scene), there are some international ones like “garden” or “car” that are likely to occur all over the world. Therefore, this recommendation strategy is considered an adequate baseline for our evaluations.
Another very simple recommendation method is to suggest those tags t ∈ T that have been used by the given user u ∈ U the most often so far, i.e. where the set Tu,t := {(u, t, s, p) | s ∈ S, p ∈ P } is largest. This yields a personalized recommender that recommends tags that are known to the user and in a language they understand.
It is also very suitable for the mobile devices, as only the user profile and no other training data has to be stored. Using the pre-ordered list of the user’s tags, the algorithm is similarly fast as the global most popular tag recommender. However, this algorithm has a severe cold start problem as it cannot produce tags for new users. 3.2.3
An approach that uses the location information provided by the location sensor s ∈ S is to recommend tags that have been used so far at the given location or nearby. Prox is thus a context-aware recommender that will recommend tags that likely describe the location like for example “airoplane noise”, which has been used near airports. Therefore, a proximitybased prediction is likely to have good performance.
The algorithm has stronger requirements than the previous ones. Either the whole dataset (all recordings in any location) must be stored on the device or an Internet connection is required beforehand in order to query for records that have been taken roughly near the user’s current location.
In our experiments we will use the k-Nearest-Neighbors algorithm [16, page 129–131] to find the nearby tags. This ensures that this approach always recommends tags even if they are taken from faraway places. For our experiments we manually choose a value of 42 for k, since this showed good results in a subset in the training data.
The distance between two locations can be calculated with a number of methods like the Manhattan, the Euclidean, or the great circle distance. The Manhattan distance is particularly is rather inaccurate although very easy to compute. The Euclidean distance is much better in terms of accuracy, but with the price of a higher computational effort. However, compared to the actual air-line distance, the accuracy is getting worse for locations further away from the equator. Finally, the great circle distance is very precise, but is the most expensive with regard to computations. We use the Euclidean distance (Prox-ED) and the great circle distance (Prox-GCD) due to its higher accuracy. 3.2.4
An approach that uses WideNoise Plus’s perception values p ∈ P is able to recommend tags t ∈ T that are associated with the same mood (e.g., “love”). This yields a contextaware recommender that will recommend tags that describe the user’s perception of the noise, location, etc. (e.g., “noisy plane spoiling peace”). There are four scales with a range from -5 to +5 each with steps of size 1 to express the corresponding perception (see Figure 1(a)): • Feeling: Ranges from “hate” to “love” and expresses whether the user enjoys the recorded noise or whether it was unpleasant. • Disturbance: Ranges from “hectic” to “calm” and expresses how disturbing the recorded noise was perceived by the user. • Isolation: Ranges from “alone” to “social” and expresses how much company the user had. • Artificiality: Ranges from “man-made” to “nature” and expresses whether the recorded noise was caused by humans, machines, or nature.
The method is suitable for mobile devices, as only an aggregated list of tags for each possible perception combination has to be stored. Using the pre-ordered lists of the perception’s tags, the algorithm has to combine those lists that are the most similar to the given perception setting. A perception vector p is considered similar to the current perception vector p if no perceptions differ more than a given threshold d, i.e. if ||p − p ||∞ ≤ d. In our experiments we will set the (initial) threshold to d = 1 and increase it by one in cases where no such measurement p exists and thus nothing could be recommended. 3.2.5
This approach, presented by [
It is thus suitable for mobile devices, as only the precomputed ranked list of tags of each cluster have to be stored. For each new record, the distance to all clusters has to be computed to select the ranked tag list of the cluster closest to the user.
In an offline preprocessing, the resources are clustered using k-Means and the most frequent tags for each cluster are determined. k-Means requires the number of cluster k as an input parameter as well as a distance computation function. For k we use the rule of thumb proposed by [14, page 365]: k ≈ Hereby, n refers to the number of resources to be clustered and the Euclidean distance is used as distance function. Clusters are represented by their centroids and in the recommendation phase, we use the Euclidean distance for distance calculation.
During our experiments we discovered that, in our scenario, it is better to choose the absolute tag frequency during clustering phase rather than the user frequency. We will present the result for user frequency (i.e., Clus-UF) and absolute tag frequency (i.e., Clus-AF) separately during our evaluation. 3.2.6
To improve performance, multiple recommenders can be combined in hybrid recommenders. Such a combination can improve the results by combining several aspects, e.g., to yield a location-based approach that also is influenced by the given perceptions.
The suitability for our scenario depends on the algorithms that are combined. In this paper we will analyze 3 combinations between most popular tag by user on the one hand and either the perception (Perc-MPTU), proximity (ProxED-MPTU), or clustering (Clus-ED-MPTU) approach on the other hand. We use most popular tag by user as it produces personalized recommendations with only little computational effort. In order to keep the computational effort small we chose the Euclidean distance-based versions of Perc and Prox.
All involved algorithms compute their individual rankings.
For a tag t ∈ T we compute a score as an unweighted
linear combination [
1 rank1 (t) +
1 rank2 (t) −1 Hereby, rank1 (t) and rank2 (t) are the positions of the tag t in the rankings of the two combined algorithms.
In this section we introduce the dataset of our analysis and how it was assembled as well as the metrics we use for the evaluation in Section 5. 0 ● 0 5
● ● ● 0 y 5 c n e u freq 20 g a t
The basis for our experiments is the full set of WideNoise Plus records with at least one tag, collected between December 14, 2011 and June 12, 2013. After the removal of records that had been submitted for testing by the developers, the collection consists of 5,434 reports collected by 546 users that contain 1,151 distinct tags and 9,255 tags in total. The following further preprocessing steps were applied to the tags: All tags have been lower-cased and some encoding issues have been resolved manually (e.g., we replaced “wrzburg” with “wu¨rzburg”).
Before we describe the experiments on tag recommendations, we observe a few statistical properties of the datasets. Figure 2 shows the distribution of the tag frequency. The distribution tends to be fat tailed.
Figure 3 shows the distribution of the number of tags assigned to one record. The maximum number of assigned tags is 8 and we therefore pick it as the maximum number of recommended tags in our experiments. On average, one WideNoise Plus record has 2.45 tags assigned to it.
Figure 4 shows the distribution of the number of tag assignments per user. The most active user assigned 2,461 tags and the average number of tag assignments per user is 33.92. However, we have a fat tail of users that made just one tagged records and then stopped using this feature.
We evaluate the different recommendation algorithms in an offline experiment. We split the full dataset into training and test data using a time split after 70 % of the records leaving 3,805 records for the train phase and 1,629 records for the evaluation phase. In that way, we stay close to the actual scenario: The WideNoise Plus app runs on a mobile device and must produce recommendations from the data on the device. While it is not possible to send training data 0 1 5 ● ● ● ● ● ● ● ● ● ● ●● ●● ●●●●●●●●●●●●●●● 20 user ●●●●●●●●●●●●●●●● ●●●●● ●●●●●●●●●●●●●●●●●●● ●●●●●● ●●●●●●●●● ●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●● 1 1 1 record by record to an application, it is very well conceivable, to update the app with training data in larger regular intervals. A consequence of this procedure is that the test data set contains users and tags that do not occur in the training data. Again, this is close to the real scenario, where often users take measurements over only a short time span and thus do not have large user profiles to be used for training. This closeness to the real-world scenario was the decisive element for a time split and against other methods like cross validation procedures, where random samples of the full data set are selected as test data.
The algorithms are trained and then used to produce a ranked list of recommendations T˜(u,s,p) for each record in the test dataset comprising the user u, the sensor measurements s (longitude, latitude and noise level) and the four perceptions p. To evaluate the performance we measure the predictive power of recommendations, i.e., for every record of the test data, precision, recall, and F1 measure are computed. For these three metrics, the number of recommended tags has to be set to some fix number k. To pay tribute to the size of mobile devices and following the findings above on the maximum number of assigned tags, we let k run from 1 through 8 and compute the score at each level. Thus, if T(u,s,p) is the set of tags that were actually assigned to the record and T˜(u,s,p) is the set of the top k recommended tags, then precision and recall are defined as follows [16, page 109]: Precision(u, s, p) = |T˜(u,s,p) ∩ T(u,s,p)| ˜ |T(u,s,p)| Recall(u, s, p) = |T˜(u,s,p) ∩ T(u,s,p)| |T(u,s,p)| The F1 measure is the harmonic mean of precision and recall:
Precision(u, s, p) · Recall(u, s, p)
F1(u, s, p) = 2 · Precision(u, s, p) + Recall(u, s, p)
In the experiments, we will compare not only different algorithms against each other, but also to a theoretical “perfect recommender”. This upper bound demonstrates, how much room for improvements is left for further, possibly more advances methods in future work. The bound is constructed by recommending those tags for a record that have actually been used for it as long as these tags occur in the training data. It is clear that no real algorithm – which of cause has no knowledge about the user’s actually chosen tags – can beat that upper bound (unless it can produce tags that have never been used before). 5.
In the evaluation we use the global most popular recommender as baseline. Every more sophisticated recommender should achieve better results than that. Additionally, we include the values for a perfect pseudo-recommender that predicts just those tags that are actually used and present in the train dataset. As described in Section 3.2.1, there are language specific tags in the list of the global popular tags (see Table 1). Further, besides the larger geographic areas, there are also tags that will occur only in certain particular areas like the tag “heathrow”, which would be relevant only around London. It is therefore to be expected, that the most popular baseline will achieve rather low results.
Figure 5 shows the results for precision and recall. The F1 measure results are shown in more detail in Figure 6 and Table 2. In the discussion, we focus on the scores that are obtained for the recommendation of two and three tags respectively, since the average amount of assigned tags in the dataset is 2.45. Compared to the baselines, we observe, that all algorithms successfully outperform the most popular tags recommender, but also – comparing to the theoretical upper bound – that there is plenty of room for improvements.
An interesting results is that the personalized MPTU approach yields a very good score. It is already better than the computationally intensive Perc approache, but slightly worse than Clus and Prox. It is very interesting that in comparison to the use of the Euclidean distance, the great circle yields almost the same results. For our scenario, this is good news, as similar recommendations are produced with less computational effort. The use of clustered locations (i.e., Clus) yields similar results as Prox-ED and Prox-GCD, but is computationally less expansive.
Looking at the hybridization results, we see that all algorithms profit from the merge with MPTU. Prox-ED benefits far more from MPTU than Clus-AF and achieves the best results among all investigated algorithms – approximately already half of the maximal possible score.
To evaluate the suitability for mobile devices we measured the runtime it took each recommender to predict the tags for the whole evaluation dataset. Figure 7 depicts the computation time for every algorithms5. The computational effort of the great circle distance is not acceptable considering the almost same performance. While Prox-ED-MPTU achieved the best recommendation quality, it requires a lot of computation time. Still one has to consider that the analysis was conducted on a relatively powerful computer and that the times will increase with a growing dataset. The runtimes can therefore only be used as indicators, since smartphones have much less computation power and would therefore take much longer. 5The evaluation was conducted on a Lenovo ThinkPad X220 with an Intel Core i7-2640M (2.80 GHz), 8 GB RAM, Windows 8 Professional 64-bit, and Gnu R 2.15.3 64-bit. 5 2
With the SensorFolkSonomy scenario we have introduced a new task for recommender systems. It requires new models and adaptations of known tag recommendation approaches. WideNoise Plus represents such a SensorFolkSonomy application, and we could compare several algorithms exploiting different aspects of the app’s records.
Our evaluations show that the best results are achieved by combining the recommendations of the most popular tag by user recommender and a location proximity-based approach. In future work we plan to evaluate the real runtimes of the algorithms on mobile devices and to adapt other recommendation algorithms to our scenario.
Besides that, there are some additional questions that we want to address concerning the cluster-based approach. Currently, we use k-Means to compute the cluster. It will be of interest to compare varying numbers of cluster or other cluster algorithms and evaluation their performance. Additionally, we will evaluate the performance of further hybrids using machine learning to find weighted combinations with more than two approaches involved.
Part of this research was funded by the European Union in the 7th Framework programme EveryAware project (FETOpen). 16.21 16.62