With the rapid development of web2.0 technologies, tagging become much more important today to organize information and help users search the information they need with social bookmarking tools. In order to finish the second task of ECML PKDD challenge 2009, we propose a graph-based collaborative filtering tag recommendation system. We also refer to an algorithm called FolkRank, which is an adaptation of the famous Page Rank. We evaluate and compare these two approaches and show that a combination of these two methods will perform better results for our task.
Tagging is very useful for users to figure out other users with similar interests within a given category. Users with similar interests might post similar tags and similar resources might have similar tags posted to them. Collaborative filtering is widely used in automatic prediction system. The idea behind it is very simple: those who agreed in the past tend to agree again in the future. Traditional collaborative filtering systems have two steps. The first step is to look for users who share the same rating patterns with the active user whom the prediction is for. Then, the systems will use the ratings from those like-minded users found in the first step to calculate a prediction for the active user. Since all the tags, users and resources in the test data are also in the training file, we can make use of the history of users’ tag, also called personomy[3] and tags previously posted to the resource to recommend tags for a active post. This paper presents our proposed tag recommendation system, which is a combination of two methods: one is an adaption of item-based collaborative filtering, the other is FolkRank according to [4,5].
As we mentioned above, collaborative filtering performs well for automatic prediction. However, current widely used collaborative filtering systems are for predicting the ratings of some products or recommend some products to users. For example, the famous websites, Amazon.com1, Last.fm2, eBay3 apply this method to
their recommendation systems. Our first method considers the tags previously posted to the resource and users’ similarities to recommend tags. The second method is an application of the FolkRank algorithm in [4, 5].
These two methods have some common features. They both use the history of the user and tags previously posted to resource for recommendation. They are both suitable to the case that test data are in the training data. Both of them do not need to establish models in advance. But they are different to some extents. The first method just considers tags in the candidate set while the FolkRank will consider all the tags in the training data. Moreover, the first method focuses more on collaborative information while the second focuses on the graph information.
This paper is organized as follows: Section 2 introduces recent trends in the area of social bookmark tag recommendation systems. Section 3 describes our proposed system and the combination method in details. In Section 4, we present and evaluate our experimental results on the test data of ECML PKDD challenge 2009 and make some conclusions in Section 5. 2
Some researchers have already used some approaches based on collaborative information for tag recommendation systems. For example, AutoTag[7] and TagAssist[6] make use of information retrieval skills to recommend tags for weblog posts. They recommend tags based on the tags posted to the similar weblogs. Our first method is similar to these two approaches.
FolkRank in[4, 5] is a topic-specific ranking in folksonomies. The key idea of FolkRank algorithm is that a resource which is tagged with important tags by important users becomes important itself. In [5], the author compared the performance of some baseline methods and his FolkRank algorithm, and found that FolkRank outperformed other methods. His experimental results relied on a dense core of the training file and considering that our training data is a post-core two dataset, we decide to refer to this algorithm in our proposed tag recommendation system.
In the RSDC ’08 challenge, the participants [1, 2] who make use of resource’s similarities and users’ personomy outperformed other approaches. Consequently, we consider using the collaborative information of resource’s similarities and users’ personomy in our tag recommendation system.
First, we define notations used in this paper. We group the data in bookmark by its url_hash and data in bibtex by its simhash1. If some posts in bookmark of bibtex file have the same url_hash or simhash1, they are mapped to one resource r. For each resource rd , assuming a vector d of Td tags posted to this resource rd by the user ud . Then the training dataset can be represented as
D {(r1, t1, u1),..., (rD , tD , uD )} Our proposed collaborative filtering method for tag recommendation has two steps. First of all, for a given resource r and a given user u in the test dataset, we make use of the tags previously posted to the resource r in the training dataset and define them as the candidate set:
C(u, r) {ti | (r, ti , u ') D, u ' U} The second step is to score all the tags in the candidate set and recommend the tags with the highest scores. In our proposed tag recommendation system, we score the tags in the candidate set using the following equation for all tags t∈ C(u, r): P(t | r) Tr n(t, r) (1 Tr ) n(t, R) (1)
Tr Tr Tr | T | where n(t,r) is the number of times that tag t has been posted to the resource r and n(t,R) is the number of times that tag t has been posted in the training data. Tr is the number of tags posted to the resource r and λ is the Dirichlet smoothing factor and is commonly set according to the average document length, i.e. T /|R|
In order to take the users’ similarities into consideration, we change the equation (1) to the following equation: (1 Tr ) u'U ' (sim(u, u ') m(t, u, R)) (2)
Tr | T | where U′ = {u|(r, , u) ∈ D} for a given resource r, m(t,u,r) is the number of times tag t has been posted to the resource r by the user u. The similarity of users sim(u,u’) is define as follows,
P(t | r, u)
Tr T r u'U ' (sim(u, u ') m(t, u, r))
Tr sim(u, u ') tT
n(t, u) n(t, u ') tT tT
For a given user u and a given resource r, the set of recommended tags will be: T u, r : = argtn∈C u,r P(t|r, u) where n is the number of recommended tags. 3.3
FolkRank is a graph-based algorithm whose basic idea is to rank all the tags and pick out tags which are relatively important given a user u and a resource r. This algorithm is derived from the PageRank algorithm, which is used by the Google Internet search engine that assigns a numerical weighting to each element of a hyperlinked set of documents. The purpose of PageRank is to measure the hyperlink’s relative importance within the set. However, due to the structural differences between hyperlinks and our tag recommendation system, we cannot apply the PageRank to our tag recommendation system and a new FolkRank algorithm was introduced in [4, 5].
In order to apply a weight-spreading ranking scheme to recommend tags, we need to change the directed graph in PageRank to an undirected graph and change the corresponding ranking approach.
First, we convert the training dataset D into an undirected graph G = (V, E). V is the set of the nodes in the graph, which is composed of all the tags, resources and users in the training file, i.e. V = T ∪ R ∪ U. E is the set of the edges in the graph, which is defined as the co-occurrences of tags and users, users and resources, tags and resources. E = u. t , t, r , u, r {r, t, u} ∈ D} and each edge {u, t} ∈ E has a weight | r ∈ R r, t, u ∈ D |, each edge t, r ∈ E has a weight | u ∈ U|{r, t, u} ∈ D | and each edge u, r ∈ E has a weight | t ∈ T|{r, t, u} ∈ D | . After having the graph format of the posts, we can spread the weight like PageRank as follows: w dAw (1 d) p (3) where A is the adjacency matrix of G, p is the random surfer component, and d ∈ [0,1] is a constant which controls the influence of the random surfer.
Usually, p is set to the vector where all values equal to 1. But in order to recommend tags relevant to certain user and certain resource, we can change the p to express user preferences. In our tag recommendation system, each user, tag, and resource get a preference weight of 1 but the active user and resource for recommendation get a preference of 1+|U| and 1+|R| respectively.
The FolkRank algorithm has a differential approach to see the ranking around the topics defined in the preference vector. This approach is to compare the rankings with and without the preference vector p. Assuming that 0 is the ranking after iteration with d = 1 while 1 is the ranking after iteration with d =0.625, then the final weight will be = − 0. Details can be found in Algorithm 1.
Input: the graph information of the training file, i.e. G = (V, E) where V =T ∪ R ∪ U and E = u. t , t, r , u, r {r, t, u} ∈ D}, the adjacency matrix A, the given resource r and the given user u.
Output: the ranking w of all tags ∈ T begin //Initialize foreach t ∈ T, r ∈ R and u ∈ U do
w0[t] = w1[t]=1,w0[r]= w1[r]=2 and w0[u] = w1[u] =2 end foreach t ∈ T, r ∈ R and u ∈ U do
p[t]=p[r]=p[u]=1 end p[r] = 1+|R| p[u]= 1+|U| d = 0.625 //iteration for 1 repeat
w1 = dAw1 + (1 − d)p until convergence //iteration for 0 repeat
w0 = Aw0 until convergence w = w1 − w0 end
Algorithm 1: The FolkRank algorithm used in our tag recommendation system 3.4
We have proposed two different but similar methods for our tag recommendation system. Both are suitable to our case that the test data have already appeared in the training file, both make use of the similarity of users and resources, but the first method focuses more on the collaborative information while the second one focus more on the graph nodes and can spread the weight according to the co-occurrences. We hope to combine these two methods and get a better result.
We have tried some different approaches to combine these two methods. A simple method of combination is to multiply the scores of these two models and recommend tags with highest scores after combination. Details can be found in Algorithm 2.
Input: a given resource r and a given user u and the result of the two methods Output: the set of recommended tags T(u, r) begin //collaborative method the candidate set C u, r ← {t|(r, t, u′) ∈ D, u′ ∈ U} foreach t ∈ C do
score1[t] = P(t|r,u) in equation(2) end //FolkRank algorithm foreach t ∈ T do
score2[t] = w, the output of the algorithm 1 end //combination foreach t∈ T do
score[t] = score1[t]×score2[t] end
T u, r ≔ argmaxtn∈Tscore[t] end 4 4.1
Algorithm 2: the combination method used in our tag recommendation system We evaluate our experimental results using the evaluation methods provided by the organizers of ECML PKDD discovery challenge 2009. The training set and the test set are strictly divided and we use the post-core level 2 training file as our training dataset for our tag recommendation system.
The general statistical information of training data and test data can be found in the table 2 and table 3.
bookmark bibtex total
In table 4, we show the performance of collaborative filtering method on the test data provided by the organizers of ECML PKDD challenge 2009. From the table, we can see that this method has a highest f-measure of 30.002% when the number of recommended tags is 5.
In table 4, we show the performance of FolkRank algorithm on the test data. From the table, we can find that the first method performs a little bit better than FolkRank and FolkRank has a highest f-measure of 28.837% when the number of recommended tags is 4.
In table 4, we show the performance after the combination of the previous two methods. We are glad to see that the results after combination outperform these two methods. We have a 2% increase compared to the first method and a 4% increase compared to the second method. We have a highest f-measure of 32.622% when recommending 10 tags. The precision-recall plot in Fig.1 reveals the quality of our recommendation system.
In this paper, we describe our tag recommendation system for the second task in the ECML PKDD Challenge 2009. We exploit two different methods to recommend tags when tags, resources, users in the test data are also in the training file. The experimental results show that the combination of these two methods will gain a better result.
We need to further analyze the results to see which kind of information in the graph contributes more to the final ranking. Also, we can try to change the scoring scheme or expand the candidate set in our collaborative filtering method. Future work also includes some adaptations of PageRank for the tag recommendation system.