Collaborative tagging applications allow users to annotate online resources, resulting in a complex three dimensional network of interrelated users, resources and tags often called a folksonom A pivotal challenge of these systems remains the inclusion of the varied information channels introduced by the multi-dimensional folksonomy into recommendation techniques. In this paper we propose a composite tag recommender based upon popularity and collaborative ltering. These recommenders were chosen based on their speed, memory requirements and ability to cover complimentary channels of the folksonomy. Alone these recommenders perform poorly; together they achieve a synergy which proves to be as e ective as state of the art tag recommenders.
Collaborative tagging has emerged as a popular method for organizing and sharing online content with user-de ned keywords. Delicious1, Flickr2 and Last.fm3 are among the most popular destinations on the Web allowing users to annotate bookmarks, digital photographs and music. 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 [
The rich tapestry of a folksonomy presents an enticing target for data mining techniques such as recommenders. Recommenders reduce a burdensome number of items to a manageable size correlated to the user's interests. Recommendation in folksonomies can include resources, tags or even other users. In this work
we focus on tag recommendation, the suggestion of tags during the annotation process.
Tag recommendation reduces the cognitive e ort from generation to recognition. Users are therefore encouraged to tag more frequently, apply more tags to a resource, reuse common tags and perhaps use tags the user had not previously considered. User error is reduced by eliminating capitalization inconsistencies, punctuation errors, misspellings and other discrepancies. The nal result is a cleaner denser dataset that is useful in its own right or for further data mining techniques.
Despite the richness folksonomies o er, they 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 exploit the links between users, resources and tags. However, this approach is computationally intense and ill suited for large scale implementation.
In this work we propose a composite tag recommender incorporating several distinct recommendation strategies. These recommenders are combined to generate a new hybrid. As such no single recommender is required to fully exploit the data structure of the folksonomy. Instead the recommenders may specialize in a single channel. The aggregation of these recommenders, none of which performs well on its own, produce a synergy allowing the composite recommender to outperform its constituent parts.
Our hybrid includes popularity models and item-based collaborative ltering techniques. Popularity based approaches include information garnered from the crowd with little computational cost. Item-based collaborative ltering focuses more closely on the user's pro le incorporating a degree of personalization.
We provide a through evaluation of the composite recommender and its constituent parts. Our experiments reveal that the composite model produces results far superior to the capabilities of their individual components. We further include a comparison with the highly e ective but computationally ine cient graph-based approach. We show that a low cost alternative can be constructed from less time consuming recommenders and perform nearly as well as the state or the art graph based approaches.
The rest of the paper is organized as follows. In Section 2 we discuss related work. In Section 3 we o er a model of folksonomies and describe tag recommendation. We further describe four recommendation algorithms. Informational channels in folksonomies are discussed in Section 4. We design a hybrid recommender in Section 5. Our experimental evaluation is presented in Section 6 including a discussion of the dataset, methodology and results. Finally we end the paper with a discussion of our conclusions and directions for future work in Section 7.
As collaborative tagging applications have gained in popularity researchers have
begun to explore and characterize the tagging phenomenon. In [
There have been several recent research investigations into recommendation
within folksonomies. Unlike traditional recommender systems which have a
twodimensional 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 [
Other researchers have studied tag recommendation in folksonomies. In [
General criteria for a good tagging system including high coverage of multiple
channels, high popularity and least-e ort are presented in [
Here we rst 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 hyper-graph [
Aggregate projections of the data can be constructed, reducing the
dimensionality but sacri cing information [
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 di ers 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 de ne the resource based popularity measure as: 3.2
KNN RT models resources as a vector over the tag space. As before the weights of the vectors may be calculated through a variety of means. Given a resource
PopUser, on the other hand, ignores the resource and focuses on the frequency of a tag within the user pro le. We de ne the user based popularity measure as: and a tag, we de ne 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 similarity between it and every resource in the user pro le is calculated. A neighborhood of the k most similar resources, S, is thus constructed. We then de ne the item-based collaborative ltering measure as: k where d(u; s; t) is 1 if the user has applied t to s and 0 otherwise. Like popUser, this recommender focuses strongly on the user's tagging practice. However this recommender includes an additional informational channel, identifying resources in the user pro le that are similar to the query resource. This technique therefore includes resource-to-resource information.
If the system waits to compute the similarity between resources until query time, this recommender will also scale well to larger datasets so long as user proles remain small. Alternatively similarities between resources can be computed o ine. Consequently the computation at query time is dramatically reduced and the algorithm becomes viable for large collaborative tagging implementations. (3) 3.3
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 di erence 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 [
We include this method as a benchmark as it has demonstrated to be an e ective method of generating tag recommendations. 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 de ne 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 o er a high degree of personalization. Likewise a user may be de ned 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 tags. 5
The most successful tag recommenders to date have included multiple informational channels. Folkrank explicitly includes the user-resource, user-tag and resource-tag channels in the graph model. Moreover since the algorithm calculates the Pagerank vector of the graph it implicitly includes the secondary channels of the folksonomy. The success Folkrank has achieved is due to its ability to incorporate multiple informational channels into a single tag recommender. However the success it has achieved is blunted by the computational e ort required to produce a recommendation; a new Pagerank vector is computed for each query.
Here we construct a hybrid recommender. The constituent parts by themselves perform poorly when compared to Folkrank. However, when aggregated into a single recommender they achieve a synergy which exploits several channels of the folksonomy while retaining their modest computational needs.
Our model includes PopRes, PopUser and KNN RT. We employ a weighted approach to combine the recommenders. First in order to ensure that weight assignments are on the same scale for each recommendation approach, we normalize the weights given to the tags by w(u; r; t) to 1 producing w0(u; r; t). We then combine the weights in a linear combination: such that weights + + = 1 and all values are positive. If then hybrid would rely mostly on PopRes. is set near 1
Tags promoted by PopRes will have a strong relevance to the resource, while tags promoted by PopUser will include tags in the user's pro le. PopRes alone will ignore personal tags that the user often users. PopUser, on the other hand, will ignore tags related to the context of the query resource. Together these recommenders can include both aspects in the recommendation set. Moreover by including KNN RT tags which the user has applied to resources similar to the query resource are promoted.
PopRes explicitly includes the resource-tag information. PopUser, on the other hand, includes user-tag information. Both these models are based on popularity and are single-minded in their approach ignoring all data except the informational channel to which they are employed. We use KNN RT to introduce more subtlety into the hybrid. It focuses heavily on the user-tag channel, but gives more weight to tags that have been applied to similar resources. Hence it also includes resource-tag information. Moreover by focusing exclusively on resources in the user pro le it includes the user-resource channel. Finally, KNN RT includes resource-resource information when it calculates the neighborhood of similar resources.
This hybrid does not include user-user information or tag-tag information. Additional recommenders could be included to cover these informational channels. However, we have built this hybrid with the goals of speed and simplicity. The two popularity based approaches are among the fastest and simplest recommendation algorithms. The item-based collaborative ltering recommender is used to tie together these approaches incorporating similarities among resources into the model while retaining its speed. In this section we describe the dataset used for experimentation. We then describe our experimental methodology and metrics. Finally we discuss the results of our experiments. The dataset was provided by Bibsonomy4 for 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 systemun led where removed.
Task 1 for the 2009 Challenge utilizes the complete dataset. Task 2
however focuses on the post-core at level 2 geared toward graph based approaches.
For the post-core all users, tags, and resources which appear in only one post
were removed. This process was repeated until convergence and produced a core
in which each user, tag, and resource occurs in at least two posts. Reducing a
dataset to its core was rst proposed in [
as:
Precision is another common metric that measures speci city and is de ned r = (jTh \ Trj)=jThj p = (jTh \ Trj)=jTrj
The tag recommendation algorithms accepts the user-resource pair and returns an ordered set of recommended tags, Tr. From the holdout set and recommendation set utility metrics were calculated. For each metric the average value was calculated across all test cases. Recall is a common metric of recommendation algorithms that measures coverage. It measures the percentage of items in the holdout set, Th, that appear in the recommendation set Tr. It is de ned as:
In order to conform to the evaluation methods of the ECML-PKDD 2009 Challenge, we use the F1-Measure common in Information Retrieval to evaluate the recommendations. We compute for each post the recall and precision for a recommendation set of ve tags. Then we average precision and recall over all posts in the test data and use the resulting precision and recall to compute the F1-Measure as: f 1 = (2 p r)=(p + r) (7) 6.4
Our approach required that several variables be tuned. For KNN RT, after extensive experimentation of k in increments of 1 we set k equal to 15. We observed that as k increased from 0 to 15 recall and precision both increased rapidly until it su ers from diminishing returns.
We evaluated the weights , and in :05 increments attempting every possible combination. Best results were found when = 0:35, = 0:15 and = 0:50. As such KNN RT accounts for 50% of the model, PopRes acounts for 35% and PopUser acounts for 15%.
KNN RT identi es resources in the user pro le most similar to the query resource and promotes the tags applied to these resources. This approach is most e ective when the user has generated a large user pro le. Since users often employ tags as an organizational tool they often reuse tags. Hence the success of KNN RT stems from its ability to identify which previously used tags are most appropiate given the context of the query resource.
PopRes, on the other hand, ignores the user pro le and concentrates on the popularity of a tag given the query resource. When the tags provided by KNN RT are insu cient, perhaps because the user has yet to build a deep user pro le or (5) (6) is tagging a resource dissimilar to items in the pro le, PopRes is able to provide relevant suggestions.
Finally PopUser promotes tags in the user pro le regardless of the similarity to the query resource. It may promote idiosyncratic, subjective or organizational tags that do not necessarily relate to the context of the query resource but are often applied by the user.
Our evaluation of the composite recommenders in Figures 2 and 3 reveals that PopRes, PopUser and KNN RT achieve only modest success when used alone. However when combined together as a hybrid recommender the three are able to cover multiple informational channels and produce a synergy allowing the hybrid to produce superior results.
Not only is the hybrid recommender able to outperform the baseline recommenders it is also able to outperform Folkrank, a highly e ective tag recommender. Moreover the hybrid retains the computationally e ciency of its parts making it suitable for deployment in large real work collaborative ltering applications. 7
In this paper we have introduced the idea of informational channels in folksonomies and have proposed a fast yet e ective tag recommender composed of three separate algorithms. The constituent recommenders were chosen for their speed and simplicity as well as their ability to cover complimentary informational channels. We have demonstrated that these recommenders while performing poorly alone, create a synergy when combined in a linear combination. The hybrid recommender is able to surpass the e ective graph based approaches while retaining the e ciency of its parts. Future work will include an examination of alternative hybrid recommenders and present work on other datasets. 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.