Collaborative tagging applications allow users to annotate online resources. The result is a complex tapestry of interrelated users, resources and tags often called a folksonomy. Folksonomies present an attractive target for data mining applications such as tag recommenders. A challenge of tag recommendation remains the adaptation of traditional recommendation techniques originally designed to work with two dimensional data. To date the most successful recommenders have been graph based approaches which explicitly connects all three components of the folksonomy. In this paper we speculate that graph based tag recommendation can be improved by coupling it with item-based collaborative filtering. We motive this hypothesis with a discussion of informational channels in folksonomies and provide a theoretical explanation of the additive potential for item-based collaborative filtering. We then provided experimental results on hybrid tag recommenders built from graph models and other techniques based on popularity, user-based collaborative filtering and item-based collaborative filtering. We demonstrate that a hybrid recommender built from a graph based model and item-based collaborative filtering outperforms its constituent recommenders. Furthermore the inability of the other recommenders to improve upon the graph-based approach suggests that they offer information already included in the graph based model. These results confirm our conjecture. We provide extensive evaluation of the hybrids using data collected from three real world collaborative tagging applications.
Collaborative tagging has emerged as a popular method for organizing and sharing online content with user-defined keywords. Delicious1, Flickr2 and Last.fm3 are among the most popular destinations on the Web allowing users to annotate bookmarks, digital
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’09, October 22–25, 2008, New York City, New York. Copyright 2009 ACM 978-1-60558-093-7/08/10 ...$5.00. photographs and music respectively. Other less popular tagging applications serve niche communities enabling users to tag blogs, business documents or scholarly articles.
At the heart of collaborative tagging is the post; a user describes
a resource with a set of tags. A collection of posts results in a
complex network of interrelated users, resources and tags commonly
referred to as a folksonomy [
Despite the freedom users enjoy, the size of a folksonomy often hampers the userŠs exploration. Data mining applications such as recommenders can assist the user by reducing a burdensome number of items to a smaller collection related the user’s interests. In this work we focus on tag recommendation, the suggestion of tags during the annotation process.
Tag recommendation reduces the cognitive effort from generation to recognition. Users are therefore encouraged to tag more frequently, apply more tags to a resource, reuse common tags and use tags the user had not previously considered. User error is reduced by eliminating capitalization inconsistencies, punctuation errors, misspellings and other discrepancies. The final result is a cleaner denser dataset that is useful in its own right or for further data mining applications.
Despite the richness offered by folksonomies, they also present unique challenges for tag recommenders. Traditional recommendation strategies, often developed to work with two dimensional data, must be adapted to work with the three dimensional nature of folksonomies. Otherwise they risk disregarding potentially useful information. To date the most successful tag recommenders are graph-based models, which exploits the user-defined links between the users, resources and tags.
In this work we propose augmenting the graph based approach with item-based collaborative filtering. We offer a discussion of information channels in folksonomies to motivate this proposal. The graph based model covers the user-resource, user-tag, and resourcetag channels. Item-based collaborative filtering, on the other hand, focuses on tags previously applied by the user to resources similar to the query resource. It therefore includes resource-resource information not explicitly contained in the graph model. Additionally, the user-tag information utilized by item-based collaborative filtering is more oriented to query resource.
We construct hybrid tag recommenders composed of the graph models and other techniques including popularity models, userbased collaborative filtering and item-based collaborative filtering. The graph based recommender coupled with item-based collaborative filtering produces better results than either produce alone, strengthening our theory that that item-based collaborative filtering contains information that is absent in the graph based model. Moreover the other hybrids do not improve upon the graph based model suggesting that the information they contain are already adequately represented by the graph based approach.
The rest of this paper is organized as follows. In Section 2 we describe related works. A brief survey of the tag recommenders we employ in our experiments is given in Section 3. The use of hybrid recommenders is motivated in Section 4 where we discuss informational channels in folksonomies. Section 5 details how tag recommenders may be compounded to produce hybrid recommenders. Our experimental evaluation is presented in Section 6, including a description of our datasets, our methodology and a discussion of our findings. Finally in Section 7 we present our conclusions and lay a foundation for future work.
The term folksonomy was coined by [
In [
As collaborative tagging applications have gained in
popularity researchers have explored and characterized the tagging
phenomenon. In [
There have been many recent research investigations into
recommendation within folksonomies. Unlike traditional recommender
systems which have a two-dimensional relation between users and
items, tagging systems have a three dimensional relation between
users, tags and resources. Recommender systems can be used to
recommend each of the dimensions based on one or two of the other
dimensions. In [
In [
User-defined tags and co-occurrence are employed by [
Previously, in [
General criteria for a good tagging system including high
coverage of multiple channels, high popularity and least-effort are
presented in [
Here we first provide a model of folksonomies, then review several common recommendation techniques which we employ in our evaluation. A folksonomy can be described as a four-tuple:
D = hU; R; T ; Ai where, U is a set of users; R is a set of resources; T is a set of tags; and A is a set of annotations, represented as user-tag-resource triples:
A µ fhu; r; ti : u 2 U; r 2 R; t 2 T g
A folksonomy can, therefore, be viewed as a tripartite
hypergraph [
Aggregate projections of the data can be constructed, reducing
the dimensionality but sacrificing information [
Analogous two-dimensional projections can be constructed for UT in which the weights correspond to users and tags, and UR in which the weights correspond to users and resources.
Many authors have attempted to exploit the data model for recommendation in folksonomies. In traditional recommendation algorithms the input is often a user, u, and the output is a set of items, I. Tag recommendation differs in that the input is both a user and a resource. The output remains a set of items, in this case a set of recommended tags, Tr. Given a user-resource pair, the recommendation set is constructed by calculating a weight for each tag, w(u; r; t), and recommending the top n tags. 3.1
We consider two popularity based models which rely on the frequency a tag is used. PopRes ignores the user and relies on the popularity of a tag within the context of a particular resource. We define the resource based popularity measure as: w(u; r; t) =
jfa = hu; r; ti 2 A : u 2 U gj jfa = hu; r; ti 2 A : u 2 U; t 2 T gj
PopUser, on the other hand, ignores the resource and focuses on the frequency of a tag within the user profile. We define the user based popularity measure as:
Popularity based recommenders require little online computation. Models are built offline and can be incrementally updated. However both these models focus on a single channel of the folksonomy and may not incorporate otherwise relevant information into the recommendation.
User-based K-nearest neighbor is a commonly used
recommendation algorithm in Information Retrieval that can be modified for
use in folksonomies. Applications may model users by recency,
authority, linkage or vector space models. In this work we focus on
the vector space model [
KNN_UT models the user, u, as a vector over the set of tags
where the weight in each dimension corresponds to the occurrence
of the tag in the user profile as it is defined by the two dimensional
projection U T (u; t). Other methods may be used to model the
user, such as a vector over the set of resources or a combination
of tags and resources. Several techniques may be used to calculate
the similarity between vectors such as Jaccard similarity or cosine
similarity [
Using the similarity measure a neighborhood, N , of the k most similar users is constructed such that they have all previously annotated the query resource, r. A weight for each tag is calculated as: where d(n; r; t) is 1 if the neighbor, n, has annotated the query resource, r, with the tag t. Otherwise it is 0.
Traditional user-based collaborative filtering requires a comparison between the query user and every other user. However, since the adapted algorithm considers only those users that have annotated the query resource, the number of similarities to calculate is drastically reduced. The popularity of resources in folksonomies follows the power law and the great majority of resources will benefit from this reduced reduction in computation, while a few will require additional computational effort. As a result the algorithm scales well with large datasets.
However, since the algorithm relies on the collaboration of other users it may be the case that a tag cannot be recommended because it does not appear in a neighbor’s profile. While the personalization offered by user-based filtering is an important component for the recommender, it lacks the ability to reflect the habits and patterns of the larger crowd. 3.3
KNN_RT models resources as a vector over the tag space. Give a resource and a tag, we define the weight as the entry of the two dimensional projection, RT (r; t), the number of times r has been tagged with t. When a user selects a resource to annotate, the cosine similarity between it and every resource in the user profile is calculated. A neighborhood of the k most similar resources, S, is then constructed. We then define the item-based collaborative filtering measure as: where d(u; s; t) will equal 1 if the user has applied t to s and 0 otherwise. This recommender focuses entirely on the user’s tagging habits. Unlike the user-based filtering methods, it may be able to identify tags that are common to the user but rarely used by others. However, it lacks the ability to discover relevant tags from other users. Depending on the size of the user profile, this recommender will also scale well to larger datasets, particularly if the resourceresource similarity matrix if calculated offline.
FolkRank was proposed in [
If we regard the adjacency matrix of this graph, W , (normalized to be column-stochastic), a damping factor, d, and a preference vector, p, then we iteratively compute the PageRank vector, w, in the usual manner: w = dAw + (1 ¡ d)p.
However due to the symmetry inherent in the graph, this basic
PageRank may focus too heavily on the most popular elements.
The FolkRank vector is taken as a difference between two
computations of PageRank: one with and one without a preference vector.
Tag recommendations are generated by biasing the preference
vector towards the query user and resource [
PageRank has proven to be one of the top performing tag recommenders. However, it imposes steep computational costs. 4.
The model of a folksonomy suggests several informational channels which may be exploited by data mining applications such as tag recommenders. The relation between users, resources and tags generate a complex network of interrelated items as shown in Figure 1.
The channel between resources and tags reveals a highly descriptive model of the resources. The accumulation of many users’ opinions (often numbered in the thousands or millions) results in a richness which taxonomies are unable to approximate. Conversely the tags themselves are characterized by the resources to which they have been assigned.
As users annotate resource with tags they define their interests in as much as they describe a resource. The user-tag channel therefore reveals the users’ interests and provides opportunities for data mining algorithms to offer a high degree of personalization. Likewise a user may be defined by the resources which he has annotated as in the user-resource channel.
These primary channels can be used to produce secondary informational channels. The user-user channel can be constructed by modeling users as a vector of tags or as a vector of resources and applying a similarity measure such as cosine similarity. Many variations exist. However the result reveals a network of users that can be explored directly or incorporated into further data mining approaches. The resource-resource and tag-tag channels provide similar utility, presenting navigational opportunities for users to explore similar resources or neighborhoods of tags.
The success of tag recommenders hinge on their ability to incorporate all of these informational channels. A simple recommender such as PopRes focuses only on the tag-resource channel, whereas PopUser includes only the information between tags and users.
Collaborative filtering techniques include additional channels but increase the computational overhead. KNN_UT discovers a set of neighbors, thereby covering the user-user channel. It then focuses on tags those neighbors applied to the query resource covering the user-resource and resource-tag channels. FolkRank, on the other hand, explicitly defines the relation between users, resources and tags in its adjacency matrix. While FolkRank has proven to be among most effective tag recommenders, augmenting it with algorithms that incorporate complimentary informational channels may improve its performance.
The multiple informational channels of folksonomies present an attractive target for hybrid recommenders. Hybrids combine several recommenders together to produce a new recommender. The constituent recommenders are freed from the burden of the covering all the available informational channels and may instead focus on only a few. The hybrid then ties these recommenders together. A successful hybrid creates a synergistic blend of its constituent parts producing superior results that they could not achieve alone.
In this paper we focus on weighted hybrid recommenders [
Originally, these weights were used to select the top n items for the recommendation set. In this case, however, the weights are combined in a linear model as: w(u; r; t) = ¯ ¤ wa0(u; r; t) + ® ¤ wb0(u; r; t) (8) where ¯ = 1 ¡ ®. These coefficients are used to control the contribution of the two recommenders. When ® is set to 0, recommender a acts alone. In the case that ® is set to 0.5, each recommender contributes equally to the final weight. For each hybrid, ® must be empirically tuned to achieve the maximum synergy between the components. The tags are then resorted by the new weight, and the top n tags are recommended for the annotation. 6.
In this section we describe the methods used to gather and preprocess our datasets. Our testing methodology is outlined. We provide a discussion of how we tuned variables for each algorithm and describe the experiments on the weighted hybrid recommenders. Finally, we discuss our observations. 6.1
By P -core processing users, resources and tags are removed
from the dataset in order to produce a residual dataset that
guarantees each user, resource and tag occur in at least p posts [
By removing infrequent users, resources and tags noise in the data is reduced. Uncommon items whether they be tags used by only a few users, unpopular resources, or inactive users are eliminated from consideration. Because of their scarcity these are the very items likely to confound recommenders. Moreover by eliminating infrequent items the size of the dataset is dramatically reduced allowing the application of data mining techniques that might otherwise be computationally impractical. 6.1.2
Delicious
Delicious is a popular collaborative tagging application in which users annotate URLs. On 10/19/2008, 198 of the most popular tags were taken from the user interface. For each of these tags the 2,000 most recent annotations including the contributors of the annotations were collected. The social network for these contributors was explored recursively collecting 524,790 usernames.
From 10/20/2008 to 12/15/2008 the complete profiles of the users were collected. Each user profile consisted of a collection of annotations including the resource, tags and date of the original bookmark. The top 100 most prolific users were visually inspected; twelve were removed from the data because their annotation count was many orders of magnitude larger than other users and were therefore suspected to be Web-bots.
Due to memory and time constraints, 5% of the user profiles was randomly selected. Still this dataset remains far larger than either the following Bibsonomy or Citeulike datasets. Experiments on larger samplings reveal near identical trends for several of the tag recommendation strategies. Some tag recommendation techniques such as FolkRank are so computational intensive that larger samplings of the data are not feasible. In order to best compare the recommenders, the 5% sampling was used on all reported experiments. A P -core of 20 was taken from the sample and is reported in Table 1. 6.1.3
Citeulike
Citeulike is a popular online tool used by researchers to manage and discover scholarly references. They make their dataset freely available to download4. On 2/17/2009 the most recent snapshot was downloaded. The data contains anonymous user ids and posts for each user including resources, the date and time of the posting
and the tags applied to the resource. A P -core of 5 was taken. The characteristics of the dataset are described in Table 1. 6.1.4
Bibsonomy
This dataset was provided by Bibsonomy5 for use in the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD) 2009 Challenge. Bibsonomy was originally launched as a collaborative tagging application allowing users to organize and share scholarly references. It has since expanded its scope allowing users to annotate URLs.
The data includes all public bookmarks and publication posts of Bibsonomy until 2009-01-01. The data was cleaned by removing all characters which are neither numbers nor letters from tags. Additionally the system tags imported, public, systemimported, nn and systemunfiled where removed. A P -core of 5 was used. Table 1 relates the features of the dataset. 6.2
We have adopted the test methodology as described in [
For evaluation we adopt the common recall are precision measures as is common in Information Retrieval. Recall measures the percentage of items in the holdout set that appear in the recommendation set. It is a measure of completeness and is defined as: (9) (10) r = jTh \ Trj=jThj
Precision measures the percentage of items in the recommendation set that appear in the holdout set. It measures the exactness of the recommendation algorithm and is defined as:
p = jTh \ Trj=jTrj
For each evaluation metric the average value is calculated across all test cases. 6.3
Here we present our experimental results beginning with the tuning of variables. The experiments with user-based collaborative filtering require the tuning of k, the number of neighbors.
Figure 2 shows the relation between k and the evaluation metrics recall and precision for a recommendation set of size 5. The Delicious dataset was used for this experiment. As k increases so does recall and precision. However this improvement suffers from diminishing returns until a k of 50 offers little more benefit than a k of 20. This trend was observed for K-Nearest Neighbor experiments in the other two datasets as well. As such, all KNN_UT experiments were completed using a k of 20.
Item-based collaborative filtering also requires the tuning of k, in this case the number of similar resources in the user profile to include in the neighborhood. After empirical analysis we found 15 to produce the best performance on all datasets.
Figure 3 shows the tuning of ® for the hybrid recommenders. Each hybrid is a linear combination of FolkRank and one of the
other four recommenders. The left hand side of each graph shows the hybrid recommenders when ® is set to 0 in which case FolkRank dominates the hybrid. As ® increases more weight is given to the other recommenders until finally when ® reaches 1, FolkRank plays no part in the recommendation.
For all datasets, item-based collaborative filtering contributes to recall and precision of its hybrid. For example in the Delicious experiment when ® is set to 0:4, recall for a recommendation set of five tags is 6% higher than FolkRank achieves alone and 13% higher than KNN_RT achieves alone.
In the Delicious experiments, a hybrid built with PopUser offers a slight improvement, while it has a more dramatic improvement on Citeulike. These observations reveal that the personalization of the user-tag channel strongly incorporated into KNN_RT and PopUser offers information lacking in FolkRank. While PopUser boosts all of the user’s tags, KNN_RT focuses on tags related to the resource being annotated accounted for its increased performance. On the other hand PopRes does not appear to provide any additional benefit to FolkRank. Indeed, FolkRank contains this information in the utilization of the RT matrix.
These two results reveal that the weights given to the query resource and query user in the FolkRank algorithm achieve different results. The weight applied to the resource immediately activates tags strongly associated with the resource. The result is similar to that achieved in PopRes, hence PopRes offers little assistance to its hybrid. However, the weight applied to the query user disperses through the graph activating all of the user’s tags relevant or irrelevant to user’s present context. KNN_RT, on the other hand, focuses on tags applied to resources similar to the query. Hence, it includes the resource-resource channel missing in FolkRank. The hybrid is able to be personalized but also be more context specific.
KNN_UT does not appear to offer any additional information that FolkRank did not already contain, even though it includes userresource information in the neighborhood selection, user-resource information in the cosine similarity and resource-tag information in the recommendation step. This reveals that the way in which the informational channels is equally important. Additionally KNN_UT selects neighbors that are similar to the query user, utilizing the user-user channel. However, this channel does not appear to be beneficial to tag recommendation.
After analysis of the effect of ® on the hybrids we selected the best ® for the FolkRank-KNN_RT hybrid. For Delicious we used an ® of 0:4. For Citeulike and Bibsonomy used an ® of 0:5. Figures 4 through 6 compare tag recommenders along with the hybrid. Recall and precision are plotted for recommendation sets of size one through ten. For all datasets the hybrid outperforms its constituent parts.
We also observe a difference in the effect that constituent recommenders have across the datasets. Delicious users tag Web pages and their topics cover a wide array of topics. Citeulike users tag scholarly articles and often focus on their area of expertise. In fact we can see in Figures 4 and 5 the dramatic difference between PopRes and PopUser.
In Delicious PopRes outperforms PopUser, whereas in Citeulike the opposite is true. The user’s focus on a narrow subject area in Citeulike make the user-tag channel a informative predictor, whereas the topic variety in the profiles of Delicious users make the resource-tag channel more reliable.
This analysis is underscored by the success KNN_RT hybrid has on the Delicious datasets where PopUser hybrid fairs poorly. Because KNN_RT focuses on those tags applied to resources similar to the query resource it offers context appropriate tags. In Citeulike, where users have a narrow focus, this context provides little additional benefit and the PopUser hybrid performs nearly as well as the KNN_RT hybrid. Bibsonomy users tags both citations and web pages; its results fall between those of the other two datasets.
We have demonstrated that tag recommenders may be combined to form weighted hybrids that perform better than either performs alone. Moreover FolkRank one of the most successful tag recommenders to date can be augmented with item-based collaborative filtering to produce superior results. The resource-resource and personalized user-resource channels covered by item-based collaborative filtering compliment the channels utilized by FolkRank. The inability of other recommenders to improve upon FolkRank provides evidence that FolkRank sufficiently incorporates the informational channels covered by those recommenders.
Future work will involve investigating alternative hybrid tag recommenders. New recommenders that cover other informational channels will be considered. Finally, alternative methods for hybridizing recommenders will be explored. 8.
This work was supported in part by the National Science Foundation Cyber Trust program under Grant IIS-0430303 and a grant from the Department of Education, Graduate Assistance in the Area of National Need, P200A070536.