The continuous growth of collaborative platforms we are recently witnessing made possible the passage from an `elitary' Web, written by few and read by many, towards the so-called Web 2.0, a more `user-centric' vision, where users become active contributors in Web dynamics. In this context, collaborative tagging systems are rapidly emerging: in these platforms users can annotate resources they like with freely chosen keyword (called tags) in order to make retrieval of information and serendipitous browsing more and more easier. However, as tags are handled in a simply syntactical way, collaborative tagging systems su er of typical Information Retrieval (IR) problems like polysemy and synonymy: so, in order to reduce the impact of these drawbacks and to aid at the same time the so-called tag convergence, systems that assist the user in the task of tagging are required. The goal of these systems (called tag recommenders) is to suggest a set of relevant keywords for the resources to be annotated by exploiting di erent approaches. In this paper we present a tag recommender developed for the ECML-PKDD 2009 Discovery Challenge. Our approach is based on two assumptions: rstly, if two or more resources share some common patterns (e.g. the same features in the textual description), we can exploit this information supposing that they could be annotated with similar tags. Furthermore, since each user has a typical manner to label resources, a tag recommender might exploit this information to weigh more the tags she already used to annotate similar resources.
The coming of Web 2.0 has changed the role of Internet users and the shape of services o ered by the World Wide Web. Since web sites tend to be more interactive and user-centric than in the past, users are shifting from passive consumers of information to active producers. By using Web 2.0 applications, users are able to easily publish content such as photos, videos, political opinions, reviews, so they are identi ed as Web prosumers : producers + consumers of knowledge. One of the forms of user-generated content (UGC) that has drawn more attention from the research community is tagging, which is the act of annotating resources of interests with free keywords, called tags, in order to help users in organizing, browsing and searching resources through the building of a sociallyconstructed classi cation schema, called folksonomy [18]. In contrast to systems where information about resources is only provided by a small set of experts, collaborative tagging systems take into account the way individuals conceive the information contained in a resource [19]. Well-known example of platforms that embed tagging activity are Flickr1 to share photos, YouTube2 to share videos, Del.icio.us3 to share bookmarks, Last.fm4 to share music listening habits and Bibsonomy5 to share bookmarks and lists of literature. Although these systems provide heterogeneous contents, they have a common core: once a user is logged in, she can post a new resource and choose some signi cant keywords to identify it. Besides, users can label resources previously posted from other users. This phenomenon represents a very important opportunity to categorize the resources on the web, otherwise hardly feasible. The act of tagging resources from di erent users is the social aspect of this activity; in this way tags create a connection among users and items. Users that label the same resource by using the same tags could have similar tastes and items labeled with the same tags could have common characteristics.
Many would argue that the power of tagging lies in the ability for people to
freely determine the appropriate tags for a resource without having to rely on a
prede ned lexicon or hierarchy [
In order to avoid these problems, in the last years many tools have been
developed to facilitate the user in the task of tagging and to aid the tag
convergence [
This paper presents STaR (Social Tag Recommender system), a tag recommender system developed for the ECML-PKDD 2009 Discovery Challenge. The idea behind our work is that folksonomies create connections among users and items, so we tried to point out two concepts: { Resources with similar content could be annotated with similar tags; { A tag recommender needs to take into account the previous tagging activity of users, by weighting more tags already used to annotate similar resources.
In this work we identify two main aspects in the tag recommendation task: rstly, each user has a typical manner to label resources (for example using personal tags such as `beautiful', `ugly', `pleasant', etc. which are not connected to the content of the item, or simply tagging using general tags like `politics', `sport', etc.); next, similar resources usually share common tags: when a user posts a resource r on the platform, our system takes into account how she (if she is already stored in the system) and the entire community previously tagged resources similar to r in order to suggest relevant tags. Next, we develop this model and we tested it on a dataset extracted from BibSonomy.
The paper is organized as follows. Section 2 analyzes related work. The general problem of tag recommendation is introduced in Section 3. Section 4 explains the architecture of the system and how the recommendation approach is implemented. The experimental section carried out is described in Section 5.1, while conclusions and future works are drawn in last section. 2
Previous work in the tag recommendation area can be broadly divided into three classes: content-based, collaborative and graph-based approaches.
In the content-based approach, a system exploits some textual source with
Information Retrieval-related techniques [
Finally, in [
STaR has been designed to participate at the ECML-PKDD 2009 Discovery Challenge6. In this section we will rstly introduce a formal model for recommendation in folksonomies, then we will analyze the speci c requirements of the task proposed for the Challenge.
3.1
A collaborative tagging system is a platform composed of users, resources and
tags that allows users to freely assign tags to resources. Following the de nition
introduced in [
We can also de ne a tag assignment function tas: U R ! T . The tag recommendation task for a given user u 2 U and a resource r 2 R can be nally described as the generation of a set of tags tas(u; r) T according to some relevance model. In our approach these tags are generated from a ranked set of candidate tags from which the top n elements are suggested to the user. 3.2
The 2009 edition of the Discovery Challenge consists of three recommendation tasks in the area of social bookmarking. We compete for the rst task, contentbased tag recommendation, whose goal is to exploit content-based recommendation approaches in order to provide a relevant set of tags to the user when she submits a new item (Bookmark or BibTeX entry) into Bibsonomy.
The organizers make available a training set with some examples of tag assignment: the dataset contains 263,004 bookmark posts and 158,924 BibTeX entries submitted by 3,617 di erent users. For each of the 235,328 di erent URLs and the 143,050 di erent BibTeX entries were also provided some textual metadata (such as the title of the resource, the description, the abstract and so on).
Each candidate recommender is evaluated by comparing the real tags (namely, the tags a user adopts to annotate an unseen resource) with the suggested ones. The accuracy is nally computed using classical IR metrics, such as Precision, Recall and F1-Measure (Section 5.1).
By analyzing the aforementioned requirements, we designed STaR thinking at a prediction task rather than a recommendation one. Consequently, we will try to emphasize the previous tagging activity of the user, also looking for connections and patterns among resources. All these decisions will be thoroughly analyzed in the next section describing the architecture of STaR. 4
STaR (Social Tag Recommender) is a content-based tag recommender system,
developed at the University of Bari. The inceptive idea behind STaR is to
improve the model implemented in systems like TagAssist [
We will try to overcome these drawbacks, by proposing an approach based on the analysis of similar resources capable also of weighting more the tags already selected by the user during her previous tagging activity. Figure 1 shows the general architecture of STaR. The recommendation process is performed in four steps, each of which is handled by a separate component.
Given a collection of resources (corpus), a preprocessing step is performed by the Indexer module, which exploits Apache Lucene7 to perform the indexing step. As regards bookmarks we indexed the title of the web page and the extended description provided by users. For the BibteX entries we indexed the title of the publication and the abstract. Let U be the set of users and N the cardinality of this set, the indexing procedure is repeated N + 1 times: we build an index for each user (Personal Index ) storing the information on her previously tagged resources and an index for the whole community (Social Index ) storing the information about all the resources previously tagged by the community.
Following the de nitions presented in Section 3.1, given a user u 2 U we de ne P ersonalIndex(u) as:
P ersonalIndex(u) = fr 2 Rj9t 2 T : tas(u; r) = tg where tas is the tag assignment function tas: U R ! T which assigns tags to a resource annotated by a given user. SocialIndex represents the union of all the user personal indexes:
N SocialIndex = [ P ersonalIndex(ui)
i=1 4.2
At the end of the preprocessing step STaR is able to take into account users
requests. Every user interacts with STaR by providing information about a
resource to be tagged. In the Query Processing step the system acquires data about
the user (her language, the tags she uses more, the number of tags she usually
uses to annotate resources, etc.) before processing (through the elimination of
not useful characters and punctuation) and submitting the query against the
SocialIndex stored in Lucene. If the user is recognized by the system since it has
previously tagged some other resources, the same query is submitted against
her own PersonalIndex, as well. We used as query the title of the web page
(for bookmarks) or the title of the publication (for BibTeX entries). In order
to improve the performances of the Lucene Querying Engine we replaced the
original Lucene Scoring function with an Okapi BM25 implementation8. BM25
is nowadays considered as one of the state-of-the art retrieval models by the IR
community [
Let D be a corpus of documents, d 2 D, BM25 returns the top-k resources with the highest similarity value given a resource r (tokenized as a set of terms t1 : : : tm), and is de ned as follows:
m sim(r; d) = X i=1 k1((1 b) + b ntri avlgeLnegnthgrthr ) + nr ti idf (ti) (3) where ntri represents the occurrences of the term ti in the document d, lengthr is the length of the resource r and avgLengthr is the average length of resources in the corpus. Finally, k1 and b are two parameters typically set to 2:0 and 0:75 respectively, and idf (ti) represents the inverse document frequency of the term ti de ned as follows: idf (ti) = log
N + df (ti) + 0:5
df (ti) + 0:5
(1) (2) (4) where N is the number of resources in the collection and df (ti) is the number of resources in which the term ti occurs.
Given user u 2 U and a resource r, Lucene returns the resources whose similarity with r is greater or equal than a threshold . To perform this task Lucene uses both the PersonalIndex of the user u and the SocialIndex. More formally:
P ersonalRes(u; q) = fr 2 P ersonalIndex(u)jsim(q; r) g SocialRes(q) = fr 2 SocialIndexjsim(q; r) g In the next step the Tag Extractor gets the most similar resources returned by the Apache Lucene engine and produces the set of candidate tags to be suggested, by computing for each tag a score obtained by weighting the similarity (5) (6) candT agss(q) = ft 2 T jt = T AS(u; r) ^ r 2 SocialRes(q) ^ u 2 U g In the same way we can compute the relevance of each tag with respect to the query q as: (7) (8) (9) (10) (11) (12) relp(t; u; q) =
P
t r2P ersonalRes(u;q) nr nt
sim(r; q) rels(t; q) =
P
t r2SocialRes(q) nr nt sim(r; q) where ntr is the number of occurrences of the tag t in the annotation for resource r and nt is the sum of the occurrences of tag t among all similar resources.
Finally, the set of Candidate Tags can be de ned as: score returned by Lucene with the normalized occurrence of the tag. If the Tag Extractor also gets the list of the most similar resources from the user PersonalIndex, it will produce two partial folksonomies that are merged, assigning a weight to each folksonomy in order to boost users' previously used tags.
Formally, for each query q (namely, the resource to be tagged), we can de ne a set of tags to recommend by building two sets: candT agsp and candT agss. These sets are de ned as follows: candT agsp(u; q) = ft 2 T jt = T AS(u; r) ^ r 2 P ersonalRes(u; q)g candT ags(u; q) = candT agsp(u; q) [ candT agss(q) where for each tag t the global relevance can be de ned as: rel(t; q) = relp(t; q) + (1 ) rels(t; q) where (PersonalTagWeight) and (1 ) (SocialTagWeight) are the weights of the personal and social tags respectively.
Figure 3 depicts the procedure performed by the Tag Extractor : in this case we have a set of 4 Social Tags (Newspaper, Online, Football and Inter) and 3 Personal Tags (Sport, Newspaper and Tuttosport). These sets are then merged, building the set of Candidate Tags. This set contains 6 tags since the tag newspaper appears both in social and personal tags. The system associates a score to each tag that indicates its e ectiveness for the target resource. Besides, the scores for the Candidate Tags are weighted again according to SocialTagWeight ( ) and PersonalTagWeight (1 ) values (in the example, 0:3 and 0:7 respectively), in order to boost the tags already used by the user in the nal tag rank. Indeed, we can point out that the social tag `football' gets the same score of the personal tag `tuttosport', although its original weight was twice. The Tag Extractor produces the set of the Candidate Tags, a ranked set of tags with their relevance scores. This set is exploited by the Filter, a component which performs the last step of the recommendation task, that is removing those tags not matching speci c conditions: we x a threshold for the relevance score between 0.20 to 0.25 and we return at most 5 tags. These parameters are strictly dependent from the training data.
Formally, given a user u 2 U , a query q and a threshold value , the goal of the ltering component is to build recommendation(u; q) de ned as follows: recommendation(u; q) = ft 2 candT ags(u; q)jrel(t; q) > g (13)
In the example in Figure 3, setting a threshold suggest the tags sport and newspaper. = 0:20, the system would 5 5.1
In this experiment we measure the performance of STaR in the Task 1 of the ECML-PKDD 2009 Discovery Challenge. This experimental evaluation was carried out according to the instructions provided from the organizers of the Challenge 2009. The test set was released 48 hours before the end of the competition. Every participant uploaded a le containing the tag predictions, and for each post only ve tags were considered. F1-Measure was used to evaluate the accuracy of recommendations, thus for each post Precision and Recall were computed by comparing the recommended tags with the true tags assigned by the users. The case of tags was ignored and all characters which are neither numbers nor letters were removed. Results are presented in Table 1.
STaR nished the ECML-PKDD Discovery Challenge 2009 with an overall F-measure of 13:55. As showed in the table above, exploiting only the rst recommended tag the system reaches almost 20% in precision. The value of the recall increases with the number of recommended tags reaching the 13.5% in the fourth and fth tag. In the future we will perform a more in-depth study in order to compare the predictive accuracy of STaR with di erent con gurations of parameters. 6
In this paper we presented STaR, a tag recommender designed and implemented to participate to the ECML-PKDD 2009 Discovery Challenge. The idea behind our work was to discover similarity among resources in order to exploit communities and user tagging behavior. In this way our recommender system was able to suggest tags for users and items still not stored in the training set. The experimental sessions showed that users tend to reuse their own tags to annotate similar resources, so this kind of recommendation model could bene t from the use of the user personal tags before extracting the social tags of the community (we called this approach user-based).
In the future we will implement a methodology to suggest tags when the set of similar items returned by Lucene is empty. The system should be able to extract signi cant keywords from the textual content associated to a resource (title, description, etc.) that has not similar items, maybe exploiting structured data or domain ontologies. Another issue to investigate is the application of our methodology in di erent domains such as multimedia environment. In this eld discovering similarity among items just on the ground of textual content could be not su cient. Finally, textual content su ers from syntactic problems like polysemy (a keyword with two or more meanings) and synonymy (two or more keywords with the same meaning). These problems hurt the performance of the recommender. We will try to establish if a semantic document indexing could improve the performance of the recommender. 18. Thomas Vander Wal. Folksonomy coinage and de nition. Website, Februar 2007.
http://vanderwal.net/folksonomy.html. 19. Harris Wu, Mohammad Zubair, and Kurt Maly. Harvesting social knowledge from folksonomies. In HYPERTEXT '06: Proceedings of the seventeenth conference on Hypertext and hypermedia, pages 111{114, New York, NY, USA, 2006. ACM Press.