Collaborative tagging systems are social data repositories, in which users manage resources using descriptive keywords (tags). An important element of collaborative tagging systems is the tag recommender, which proposes a set of tags to each newly posted resource. In this paper we discuss the potential role of three tag sources: resource content as well as resource and user profiles in the tag recommendation system. Our system compiles a set of resource specific tags, which includes tags related to the title and tags previously used to describe the same resource (resource profile). These tags are checked against user profile tags - a rich, but imprecise source of information about user interests. The result is a set of tags related both to the resource and user. Depending on the character of processed posts this set can be an extension of the common tag recommendation sources, namely resource title and resource profile. The system was submitted to ECML PKDD Discovery Challenge 2009 for “content-based” and “graph-based” recommendation tasks, in which it took the first and third place respectively.
The emergence of social data repositories made a fundamental change in the
way information is created, stored and perceived. Instead of a rigid hierarchy
of folders, collaborative tagging systems (e.g., BibSonomy1, del.icio.us2, Flickr3,
Technorati4) use a flexible folksonomy of tags. The folksonomy is created
collaboratively by system users. While adding a resource to the system, users are
asked to define a set of tags – keywords which describe it and relate it to other
resources gathered in the system. To ease this process, some folksonomy services
recommend a set of potentially appropriate tags. Proposing a tag
recommendation system was a task of ECML PKDD Discovery Challenge 20095. This paper
presents a tag recommendation system submitted to the challenge.
1 http://bibsonomy.org/help/about/
2 http://del.icio.us/about/
3 http://flickr.com/about/
4 http://technorati.com/about/
5 http://www.kde.cs.uni-kassel.de/ws/dc09/
1.1
Collaborative tagging systems allow users (ui ∈ U ) to store resources (rj ∈ R)
in the form of posts (pij ∈ P ). A post is a triple pij = (ui, rj , Tij ), where
Tij = {tk} is a set of tags assigned by the user to the resource. The data structure
constructed by the collaborative tagging system (referred to as folksonomy [
Tag recommendation s is a pair (t, l), where t is a tag and l is a recommendation score, which is supposed to reflect the likelihood of the tag t being chosen by a user as a proper tag. A tag recommendation system returns a set of tag recommendations S. In this paper we use the term tag recommendation set (or simply recommendation) not only to refer to the final set of tags returned to the user, but also to denote the results of intermediate tag recommendation steps. In section 5 we define a set of operations on tag recommendation sets, which are used by our tag recommendation system.
User profile is a set of tags used by the user prior to the post that is being
currently added to the system, Pu = {tk : ui = u, rj ∈ R, pij ∈ P, tk ∈ Tij }.
The user profile is usually referred to as personomy [
The off-line evaluation of a tag recommendation system for challenge purposes is a complex task. Tags added to the resource are highly dependent on the state of the system and previous decisions of the user. It is not possible to create a large, realistic test dataset of posts, hiding at the same time the tags used in these posts. A test dataset which is large enough to objectively measure the quality of a recommendation system must cover a long period of time. If the tags in test data are hidden we lose access to the information about the state of the system, especially newly joined users, which make the dataset not representative. To ease this problem, the organizers of ECML PKDD Discovery Challenge 2009 divided the recommendation task into two subtasks which simulate two complementary recommendation approaches.
The first task “content-based recommendation” focuses on the content of
a resource that is tagged. In this task we assume that information about the
resource and user profile is in most cases not available in the folksonomy. A
recommender based on resource content is especially important for new users,
which are in the early stage of building their profile. Although, as shown in
Section 3.1, the need of creating the recommendation based only on the content
is rare, the content based recommender can be a valuable starting point for
more complex recommenders that use information gathered in the folksonomy.
Such more complex recommenders are evaluated in the second task –
“graphbased recommendation”. The test set in this task contains only users, resources
and tags that were present at least twice in the training data. To obtain this
set the organizers extracted k-core of order 2 [
Most of the tag recommendation systems presented in the literature are
graphbased methods. It is a natural choice for folksonomies in which textual content
is hard to access. For example, a system by Sigurbj¨ornsson and van Zwol [
Even if a tag recommendation system extracts tags from the resource content,
usually it also uses the graph information. An example of a content-based
recommender is presented by Lee and Chun [
Finally, we would like to mention two somewhat similar systems which took
the first and second place in the ECML PKDD Discovery Challenge 2008. The
winning system was proposed by Tatu et al. [
All presented experiments and the evaluation of proposed tag recommendation
system were performed on a snapshot of BibSonomy [
According to the statistical information about the dataset presented on the Discovery Challenge website6 the BibSonomy snapshot matches the usual characteristics of folksonomies, including large disproportion between the number of unique resources and users (Table 1). Among the posts in the BibSonomy snapshot 90% contained unique resources. These resources cannot be found in any other post, hence it is not possible to deduce tag recommendation based on resource profile. At the same time 0.8% of the posts, corresponding to 3,167 posts, were entered by users with no previous posts in the system. Except those posts, every time a post is added, the system is able to use the user profile to recommend tags. Similar proportions can be observed for the CiteULike7 dataset.
BibSonomy CiteULike number of tags 1,401,104 4,927,383 number of unique tags 93,756 (7% of tags) 206,911 (4% of tags) number of bookmark posts 263,004 N/A number of unique bookmarks 235,328 (89% of posts) N/A number of BibTeX posts 158,924 1,610,011 number of unique BibTeX entries 143,050 (90% of posts) 1,390,747 (86% of posts) number of users 3,617 (1% of posts) 42,452 (3% of posts)
The disproportion between unique resources and users is ignored in the test data of “graph-based recommendation” task. All users and resources present in the dataset can be found in the training data at least twice. Despite this fact the differences in statistical characteristics of resource and user profiles should be taken into consideration while proposing a recommendation system for this task. The cumulative frequency distribution of resources shows that both for bookmark and BibTeX entries, even if we remove elements that occurred twice or less, most of the remaining elements still have a very small profile (Fig. 1). Looking at the same statistic for users we see that a significant fraction of them have over 100 posts in their profiles. Hence user profiles are likely to contain more 6 http://www.kde.cs.uni-kassel.de/ws/dc09/dataset 7 http://www.citeulike.org/ 1 10 s 100000 e tsen recnu 10000 lem cco rfeenubom trrehkoom i w 1000 100 10 1 ino 0.6 s i c reP 0.4 0.2 0 0 0.2 0.4 0.6 0.8
1 Recall 0 0.2 0.4 0.6 0.8
1 Recall potentially useful tags. To confirm this hypothesis we ran another experiment in which we simulated the test data of “graph-based recommendation” task and checked what is the precision and recall of basic recommenders that propose tags from resource/user profile sorted by frequency against real tags. To obtain a test set we divided the training data into training posts (entered before September 1, 2008) and test posts (entered later). We pruned them to be sure that all resources, users and tags occurred in the remaining part of the training set at least twice. Although this setting favours resource profiles, their overall recall is still lower than recall of the user profiles (Fig. 2). The fact that resource profiles are smaller makes them, however, a more precise source of tags. High recall of user profiles was observed by us repeatedly in many experiments. This is the reason why in our work we focused on user profiles, trying to increase the precision of this source of tags, while preserving reasonably high recall.
The presented recommendation system is the evolution of the work on the
system [
User C folksonomy prediction recommender social folksonomy recommender
tag tagging toread summerschool tagging
Resource profile Tags assigned to the resource by other folksonomy users are
not a good source of tag recommendations. One of the reasons is the sparsity of
8 http://www.kde.cs.uni-kassel.de/ws/rsdc08/
data; 90% of resources were added to the system only once. This fact significantly
limits the possible recall of this source of tags. The other issue is the personal
character of posts and tags, which hurts the precision of retrieved tags. Given
the example of two resources about the same concept, we see that users
cannot agree on tags describing it: tag recommendation, tag recommender, tagging
recommender (Table 2). The variety of tags attached by users creates, however,
another application of resource tag sets. Mining relations between tags attached
to the same resource can result in a graph of relations between tags. Using a
relationship graph the system can identify tags which are also potential
recomendations. The graph consists of general relations between tags and can be used
independently of the resources, which reduces the negative impact of data
sparsity. In our work we use two types of graphs. TagToTag graph is a directed graph
which captures the co-occurence of tags. The weight of an edge is analogous to the
confidence score (Eq. 2) in association rule mining [
Our tag recommendation system is a composition of six basic tag recommenders
(Fig. 3). The result of each recommender is a tag recommendation set with scores
in the range [
The process starts with the extraction of potential tags from the content of resource. For BibTeX posts the title of publication is used, for bookmarks the Algorithm 1: Tag recommendation system
Data: a resource r and user u Result: a tag recommendation set Sfinal begin /*Step 1 – Extraction of content based tags*/ W ordstitle ←− extractT itleW ords(r) Stitle ←− ∅ foreach w ∈ W ordstitle do
Stitle add makeT ag(w, getP riorU sef ullness(w)) removeLowQualityT ags(Stitle, 0.05) if isBookmark(r) then
W ordsURL ←− extractU rlW ords(r) SURL ←− ∅ foreach w ∈ W ordsURL do
SURL add makeT ag(w, getP riorU sef ullness(w)) removeLowQualityT ags(SURL, 0.05) rescoreLeadingP recision(Stitle, 0.2) rescoreLeadingP recision(SURL, 0.1) Scontent ←− mergeSumP rob(Stitle, SURL) /*Step 2 – Retrieval of resource related tags*/ ST itleT oT ag ←− ∅// related tags from TitleToTag graph ST agT oT ag ←− ∅// related tags from TagToTag graph SPr ←− getP rof ileRecommendationBasic(Pr) foreach sk ∈ Stitle do
Ssk,T itleT oT ag ←− ∅ foreach t ∈ getRelated(gT itleT oT ag, sk) do
Ssk,T itleT oT ag add makeT ag(t, sk.l ∗ conf idenceT itleT oT ag(sk.t, t)) foreach sk ∈ Scontent do
Ssk,T agT oT ag ←− ∅ foreach t ∈ getRelated(gT agT oT ag, sk) do
Ssk,T agT oT ag add makeT ag(t, sk.l ∗ conf idenceT agT oT ag(sk.t, t))
ST itleT oT ag ←− unionP rob(Ts1,T itleT oT ag, . . . , Tsn,T itleT oT ag) ST agT oT ag ←− unionP rob(Ts1,T agT oT ag, . . . , Tsn,T agT oT ag) Sr Related ←− unionP rob(ST itleT oT ag, ST agT oT ag, SPr ) /*Step 3 – Retrieval of resource and user related tags*/ SPu ←− getP rof ileRecommendationByDay(Pu) Sr,u Related ←− indersectionP rob(Sr Related, SPu ) /*Final recommendation*/ rescoreLeadingP recision(Stitle, 0.3) rescoreLeadingP recision(SPr , 0.3) rescoreLeadingP recision(Sr,u Related, 0.45) Sfinal ←− unionP rob(Stitle, SPr , Sr,u Related) title recommendation is combined with tags extracted from the resource URL. Each word extracted from the title (or URL) is scored based on the usage of this word in previous posts. The score is the ratio of the number of times the word was used in the title (or URL) and as a tag to the total number of occurrences of the word in the title (or URL). Low-frequency words (i.e., words that were used in the title less than 50 times) are assigned an arbitrary score 0.1 which is the estimated probability of using a low-frequency word as a tag. To improve precision, content based recommender tags with score lower than 0.05 are removed from the recommendation set. This step serves also as a language independent stop-words remover. Preliminary experiments indicated that the bookmark title is more precise source of tag recommendation than its URL. This observation should be reflected in the way both tag recommendation sets are merged for bookmark posts. We tested a few rescoring functions, the best results were observed for the leading precision rescorer (Eq. 3), which sets the average precision (based on training data) as the score of first tag l1 and modifies the scores of following tags li to preserve the proportion between all tag scores. Based on the tests on training data, the average precision of the title tag with the highest score is 0.2, while for URL it is 0.1.
li0 = avgP recisionAt1 ∗ li l1 (3) The result of title recommender is later used to propose title related tags in TitleToTag recommender. The related tags are extracted for each title word independently. The relation score, multiplied by the score of the word from the title recommender, becomes the score of the tag. This process produces a set of related tags for each title word. These sets are later merged, the scores of tags that can be found in more than one set are summed as they were probabilities of independent probabilistic events (Eq. 4). TagToTag recommender processes tags analogously, however, the input of this recommender is a complete content based tag recommendation set (title and URL for bookmarks). The aim of these recommenders is to produce a large, but likely not precise set of tags related to the resource. The third recommender that is able to produce a similar set is the resource recommender, which returns a set of tags from resource profile. The score of resource tag is the number of its occurrences divided by the number of occurrences of the resource. Although for most real posts this recommender would not return any tags, it plays a significant role in the “graph-based recommendation” task, where the resource of each tested post can be found in the system database at least twice. The scores of the results of three recommenders are summed in a probabilistic way (Eq. 4). This union of tags represents all the tags that are somehow related to the resource, and we refer to them as resource related tags.
lmerged = 1 −
Y i:ti=tmerged (1 − li) (4) 5.3
The user recommender produces a set of tags that were used by the user prior to the current post. Issues related to the construction of user profiles (i.e., import of posts, possible change of user interests) make a simple frequency value not a good score for user profile based recommendation. Tags most likely to be reused are the ones that were steadily assigned to posts while the user profile was built. To capture these tags we counted the number of separate days in which a tag was used by the user. To obtain the tag score we divided the number of days the tag was used by the total number of days in which the user was adding posts to the system. This approach allows a decrease in the importance of tags that were assigned by the user in a short period of time only; however, it only partially solves the problem of imported posts. For some of imported posts the system automatically produces low-quality tags and assigns time stamps copied from an external repository (e.g., importing web browser bookmarks, the system copies the time they were created). The combination of artificial tags and real time-stamps makes these posts very hard to detect. Removing such artificial posts is likely to improve the accuracy of the user profile recommender in a real recommendation system; however, it can have undesired consequences when applied to the challenge datasets. If the user imported posts before both training and test data were collected, it is possible that some of them can be found in both datasets. Hence we should train the system for tags from these posts, because it is possible that they can be found in test data as well. Even if we modify the frequency score the representation of user profile still contains tags related to various user interests. Checking the tags extracted from user profile against resource related tags allows us to extract tags that are particularly important for the processed posts. The intersection of both sets of tags produces tags related both to user as well as resource. The score of a tag is the product of scores from both source sets.
Finally the results of title recommender, resource recommender and the intersection of resource related tags and user profile are merged. As all three sets are results of independent recommenders, tags must be rescored to ensure that tags from more accurate recommenders will have higher score in the final tag recommendation set. Again the leading precision rescorer was used for the three input tag recommendation sets. The top ten tags of this set create the final recommendation set. The challenge organizers proposed to limit the recommendation set size to five tags, which seems to be a good number to be presented to a user, however, for evaluation purposes it is interesting to observe more tags. 6
This section presents the results of the off-line system evaluation based on the
available BibSonomy snapshot. The evaluation approach assumed that all and
only relevant tags were given by the user. Although this method simplifies the
problem, it is robust and objective. The quality metrics were precision and recall,
commonly used in recommender system evaluations [
To keep the list of correct tags secret during the contest the organizers kept strict division between training and test set. The test data contained posts entered to to BibSonomy between January 1, 2009 and June 30, 2009. Each post of which user, resource and all tags could be found in k-core of order 2 of training data was used as test post for the “graph-based recommendation” task. The remaining posts were used for the “content-based recommendation” task. Comparison of training and test data for both tasks is presented in Table 3.
As we decided to separate the processing of BibTeX and bookmark posts we present the results for two post types separately. The final recommendation is presented together with the intermediate steps of the system: tags extracted from the resource title (and URL), the most frequent tags from resource profile and user profile and the combination of resource related tags and user profile tags. As each tag from the tag recommendation set can be ranked by its score it is straightforward to present any selected number of recommended tags. The plots (Fig. 6.1) present consecutive results for the top n tags, where 1 ≤ n ≤ 10. For the “graph-based recommendation” task the tags that could not be found in training test - Task 1 test - Task 2 BibTex 158,924 26,104 (98.7% of test total) 347 (1.3% of test total) bookmark 263,004 16,898 (97.5% of test total) 431 (2.5% of test total) posts total 421,928 43,002 (98.2% of test total) 778 (1.8% of test total) the k-core of training data were removed from each recommendation set before calculating precision and recall.
title resource profile (frequency) user profile (day based frequency) user profile X resource related final recommendation title and URL resource profile (frequency) user profile (day based frequency) user profile X resource related
final recommendation
Fig. 4. Precision and recall of proposed tag recommendation system and intermediate steps. Test data was divided into BibTeX and bookmark part. As expected, precision and recall of the recommendation results in the “contentbased recommendation” task are mostly driven by the content tags. Low score of user profile recommenders for BibTeX data is likely caused by a large number of posts by users who started to use the system after the training set was built. According to the rules set by the organizers the precision score was averaged over all posts in the test set, even if a recommender returned no tags for some of them. Whenever a user profile was available the user based recommender obtained significantly better results than content based recommender only.
The results for the “graph-based recommendation” task show surprisingly high accuracy of resource profile tags (which was not observed to such a degree on training data). For the test dataset in this task the intersection of resource related tags and user profile has lower precision than resource profile tags. This is an unexpected result, comparing to the previous results on training dataset, where the intersection of resource related tags and user profile had comparable or higher precision and recall to resource profile. Despite this unexpected behaviour the tags from the user profile are able to increase the f1 score by 0.02 for tag recommendation set of size 5. The open question is how representative the results of this dataset are, considering the fact that less than 2% of test posts matched the conditions of this task.
For both tasks there is a noticeable difference between the results for both types of data. However, it is not clear if it is caused by some fundamental differences between BibTeX and bookmark posts, or the differences between the two particular test datasets used. It is important to notice that the high number of tested posts has no impact on the statistical validity of results. The way the test data was prepared makes it very dependent on the behavior of users in the period of time the data was collected.
Finally we present the results of the final recommendation for combined BibTeX and bookmark posts, which were submitted to the challenge (Table 4). The systems were ranked based on the f1 score (Eq. 5) for the tag recommendation set of size 5. Based on that criterion the presented tag recommendation system took the first place in the “content-based recommendation” task (out of 21 participants) and the third place in the “graph-based recommendation” task (again, out of 21 participants).
In creating the presented tag recommendation system we considered the title of a resource as a natural starting point of the recommendation process. We tried to extend the set by tags related to the title as well as tags present in the profiles of resource and user. Our main aim was to extract valuable tags from user profile which is a very rich but imprecise source of tags. Designing the system we mostly focused on the precision of the recommended tags. To avoid the risk of recommending tags less precise than tags extracted from the title we decided to leave it as the only recommendation whenever the user profile was unavailable. This was a frequent case in “content-based recommendation” task, which gives us hope that the system will be able to achieve even better results for the final “on-line recommendation” task. The system is now connected to BibSonomy and recommends tags to each newly added post in real time. This evaluation setting will give a realistic assessment of system quality.
In our future work on this project we plan to focus on tagging patterns of individual users which would allow us to tune the recommendation for each specific user. Discovering strong patterns, like user who uses author name and year of publication for each BibTeX post, can greatly increase the accuracy of recommender for this specific user. Another interesting issue is handling of multiword concepts (e.g., is a user going to use two tags “information” “retrieval” or one “information.retrieval”?). Finally, we hope that evaluation settings like “online recommendation” task would allow us to investigate short temporal patterns when a user adds a sequence of posts related to the same problem.