FoldCons: A Simple Way To Improve Tag Recommendation

Abstract

Tag recommendation is a major aspect of collaborative tagging systems. It aims to recommend tags to a user for tagging an item. In this paper we present a part of our work in progress which is a novel improvement of recommendations by re-ranking the output of a tag recommender. We mine association rules between candidates tags in order to determine a more consistent list of tags to recommend. Our method is an add-on one which leads to better recommendations as we show in this paper. It is easily parallelizable and morever it may be applied to a lot of tag recommenders. The experiments we did on five datasets with two kinds of tag recommender demonstrated the efficiency of our method.

Keywords

• eol>Tag Recommendation
• Association Rules Mining
• Social Network
• Factorization Models

1. INTRODUCTION

Social (i.e. collaborative) tagging is the practice of allowing users to annotate content. Users can organize, and search content with annotations called tags. Nowadays the growth in popularity of social media sites has made the area of recommender systems for social tagging systems an active and growing topic of research [ 5 ]. Tag recommenders aim to recommend the most suited tags to a user for tagging an item. They are a salient part of the web 2.0 where applications are user-centred.

In this paper, we propose a novel improvement of tag recommendation. We present F oldCons an add-on method which can fold more consistency in recommendations. Furthermore it is applicable on top of many tag recommenders and is very fast to compute. The main idea behind FoldCons is that the first of recommended tags computed by a tag recommender plays more important role than the rest. We may think that it is the most interesting tag since it has the highest score. Thus FoldCons relies on this first tag to sort the rest in order to achieve better consistency and improvement. Of course, the same reasoning can be used with the second tag, then the third one and so on.

To validate the efficiency of FoldCons who chose two kinds of tag recommender as candidates. One which proves itself is the pairwise interaction tensor factorization model (PITF) of Rendle and Schmidt-Thieme which wins the task 2 of ECML PKDD Discovery Challenge 2009 [ 8 ]. Currently one of the best tag recommenders in literature. The other is an adaptation of the network-aware search in online social bookmarking applications of [ 4, 7 ] to tag recommendation, we called STRec. It is a network-based tag recommender which considers the opinions of users’ neighbourhood. The experiments we did on five datasets with these two tag recommenders demonstrated the efficiency of FoldCons. The remainder of this paper is organized as follows. In Section 2 we present some preliminaries and describe briefly PITF and STRec. Section 3 details the FoldCons method. In Section 4, we present experimentations of our proposal. Finally Section 5 summarizes the related work while Section 6 concludes the paper.

2. PRELIMINARIES

A folksonomy is a system of classification that allows its users creating and managing tags to annotate and categorize content. It is related to the event of social tagging systems. A folksonomy can be defined as a collection of a set of users U , set of tags T , set of items I, and a ternary relation between them S U I T . A tagging triple (u; i; t) 2 S means that user u has tagged an item i with the tag t. A user can tag an item with one or more distinctive tags from T . We assume that a user can tag an item with a given tag at most once.

The interest of a tag t for a given user u and an item i is generally estimated by a score score(tju; i). Thus the purpose of a tag recommender is to compute the top-K highest scoring tags for a post (u; i) what represents its recommendations.

T op(u; i; K) = argKmax score(tju; i) t∈T (1) In the next subsections we describe how PITF and STRec model the scores of tags.

2.1 Factor Models for Tag Recommendation

Factorization models are known to be among the best performing models. They are a very successful class of models for recommender systems. For tag recommendation they outperform the other approaches like Folkrank and adapted Pagerank [ 9 ]. We chose the pairwise interaction tensor factorization model (PITF) of Rendle and Schmidt-Thieme in our experimentations due to its efficency [ 8 ]. It took the first place of the task 2 of ECML PKDD Discovery Challenge 2009 indeed.

PITF proposes to infer pairwise ranking constraints from S. The idea is that within a post (u; i), one can assume that a tag t is preferred over another tag t′ iff the tagging triple (u; i; t) has been observed and (u; i; t′) has not been observed. PITF captures the interactions between users and tags as well as between items and tags. Its model equation is given by: score(tju; i) = ∑ uˆu;f tˆtU;f + ∑ ˆii;f tˆt;f

I f f (2) Where Uˆ , Iˆ, TˆU and TˆI are feature matrices capturing the latent interactions. For more information regarding PITF see their paper [ 8 ].

2.2 A Network-based Tag Recommender

We also used STRec, an adaptation to tag recommendation of the network-aware search in online social bookmarking applications of [ 7 ]. We chose it as a candidate for networkbased tag recommenders. STRec is fast and efficient as presented in [ 4 ]. It considers that users form an undirected weighted graph G = (U; E; ) (i.e. the social network) where is a function that associates to each edge e = (u; v) 2 E a value in [0; 1], called the proximity between u and v. Its model score of a tag t for a post (u; i) is represented by score(tju; i) = h(f r(tju; i)) (3) where f r(tju; i) is the overall frequency of tag t for a user u and item i, and h a positive monotone function. In our case we took h as the identity function. They define the overall tag’s frequency function f r(tju; i) as a combination of a user-network-dependent component sf (tju; i) and an item-dependent one tf (t; i), and as follows: f r(tju; i) = tf (t; i) + (1 ) sf (tju; i) (4) The former component, tf (t; i), is the frequency of t for item i, i.e., the number of times the item was tagged with this tag. The latter component stands for social frequency, an measure that depends on the neighborhood of user u. The parameter allows to tune the relative importance of each component.

The scoring model of STRec does not take into account only the neighbors directly connected to the user. But it deals also with users indirectly connected to her, following a natural interpretation that user links (e.g., similarity) are, at least to some extent, transitive. Thus considering that each neighbour brings her own weight (proximity) to the score of a tag, the measure of tag’s social frequency is defined as follows: sf (tju; i) =

∑ v∈{U|(v;i;t)∈S} (u; v) (5) As one may notice, STRec does not regard the use of the tag by the user for tagging items (as for the item with the tag’s frequency) but it considers the opinions of the user’s neighbours instead.

3. FOLDING MORE CONSISTENCY IN REC

OMMENDATIONS

In this section, we present our add-on method for improving tag recommendation, we called F oldCons. Its functioning is to ask recommendations of a given tag recommender about a post (u; i), and improve them before to leave to the user the final top-K recommended tags. Therefore it asks for a number of tags greater than K. Then it re-ranks them and keeps the K first tags as the final recommendations. The sequel of this section details the FoldCons method besides introducing some defintions.

Definition 1. A tag's users list U (t) is the set of users who used the tag t. A tag's items list I(t) so is the set of items tagged by the tag t.

Definition 2. The pairwise con dence measure, P CM (t ! t′), is de ned between to tags t and t′. It determines to some extent the interest to use t′ in addition to t. PCM takes into account both users and items as de ned as follows P CM (t ! t′) = jU (t) \ U (t′)j + jI(t) \ I(t′)j jU (t)j jI(t)j (6) The pairwise confidence measure mines association rules between tags from two dimensions: users and items. This allows us to account the frequency of tags’ co-occurences both for the user and item of a post. Let us notice there we do not currently weight their contributions in the sum but it is a possibility.

3.1 FoldCons’ functioning

FoldCons works simply as an add-on tool which takes in entry tags from a tag recommender sorted by their scores and returns a short list of final recommended tags. Its challenge is to improve the recommendations it received by giving a better top-K.

Let us denote by D the list of recommended tags received from a given tag recommender. To simply we consider that D is sorted and its highest scoring tag is D[ 1 ]. Let us emphasize here we assign more attention to D[ 1 ] than the rest of tags in D due to the fact that it is the best choice given by the tag recommender. Therefore we fix it and compute the pairwaise confidence measures of all the tags compared to it. Then we sort D again with the new scoring function for each of its tags t

scoreP CM (tju; i) = (1 + P CM (D[ 1 ] ! t)) score(tju; i) Thus we introduce a certain consistency in the recommendations by taking account the tags which appear generally next to the first recommended tag in D from both the user’s point of view and the one of the item. This approach improves noticeably the quality of recommendations as shown in our experimentations. Morever, as PCM at best doubles the initial score of a tag (i.e. P CM (t ! t′) 2 [0; 1]), we can keep in entry only the tags whose scores exceed or equal the half-score of the last tag in the top-K of D. Indeed the other tags can not change the top-K.

3.2 Still ensuring better recommendations

Some tag recommenders are not both user and item-centred. STRec may be an example. Despite it takes into account the opinions of a user’s neighbourhood, it does not consider the user’s frequent used tags. In these cases we experimented that the application of FoldCons may slightly fall to improve the recommendations in the user or item-dimension. Thus we adapted FoldCons to these cases. Depending on the recommender we consider the user profile and/or the item one, we define below.

Definition 3. A user pro le T (u) is the set of all the tags used by user u to tag items. An item pro le T (i) so is the set of tags used to annotate item i.

We determine if FoldCons brings better recommendations by estimating its contribution. We take account of the number of common tags between the top-K recommended tags and the item and/or the user profile before and after its computation. The difference represents the contribution of FoldCons.The recommendations of FoldCons are considered better when its contributions are positive else the primarily list of tags D remains unchanged. This approach ensures, in almost all cases, that the recommendation quality does not decrease after application of FoldCons when recommenders are not both user and item-centred.

4. EXPERIMENTATIONS

Due to the length of short paper (four pages) we expose in this paper only the ability of FoldCons to improve recommendations. More results are available at [ 3 ]. We discussed there subjects like the pertinence of using just the first tag as reference and not another tag neither several tags at the same time.

4.1 Datasets

We chose five datasets from four online systems: del.icio.us1, Movielens2, Last.fm3, and BibSonomy4.

1http://www.del.icio.us.com 2http://www.grouplens.org 3http://www.lastfm.com 4http://www.bibsonomy.org

We take the ones of del.icio.us, movielens, and last.fm from HetRec 2011 [ 2 ] and the two other ones from Bibsonomy: a post-core at level 5 and a one at level 2 [ 1, 5 ]. We call them respectively Bibson5 and dc09). dc09 is the one of the task 2 of ECML PKDD Discovery Challenge 20095. This task was especially intended for methods relying on a graph structure of the training data only. The user, item, and tags of each post in the test data are all contained in the training data’s, a post-core at level 2.Let us remaind that a post-core at level p is a subset of a folksonomy with the property, that each user, tag and item has/occurs in at least p times.Table 1 presents the caracteristics of these datasets.

4.2 Evaluation Measures and Methodology

To evaluate our proposal, we used a variant of the leaveone-out hold-out estimation called LeavePostOut [ 5 ]. In all datasets except dc09, we picked randomly and for each user u, one item i, which he had tagged before. Thus we create a test set and a training one. The task of our recommender was then to predict the tags the user assigned to the item. Moreover we generate, for each training set, a social network by computing the Dice coefficient of common users’ tagged items. Let us notice that we fixed the parameter of STRec to 0.05 for all experimentations. We kept this value after a calibration over the dataset dc09. What is of course not necessary optimal for all the others. For Tagrec we keep the default parameters given by the authors but with 2,000 iterations6.

We used the F1-measure as performance measure.

4.3 Results

In this section we present the some results of our experimentations on the datasets. On each of them, we run STRec and Tagrec. Then we apply FoldCons on their proposed top-K tags. We call respectively by STRec++ and Tagrec++ the application of FoldCons on them. Let us notice that for STRec we specially apply the adapted FoldCons presented in Section 3.2. 4.3.1 Contribution of FoldCons The tables below show the gains brought by FoldCons when it is applied. We compute the top-5 to top-10 recommended tags and their F1-measures.

RELATED WORK

5http://www.kde.cs.uni-kassel.de/ws/dc09/

6http://www.informatik.uni-konstanz.de/rendle/software/tagrecommender/ Finding suited tags to put in the same recommendations is an important point for tag recommendation. Many approaches and methods can be used to achieve this point. We can cite the work of Lipczak which focused on content-based tag recommenders [ 6 ]. His approach consists in extracting basic tags from the content of items (e.g. the item title), then extending the set of potential recommendations by related tags proposed by a lexicon based on co-occurrences of tags within item’s posts.

Wang et al. did a similar work enough but first applied a TF-IDF algorithm on the description of the item content, in order to extract keywords of the item [ 10 ]. Based on the top keywords, they utilize association rules from history records in order to find the most probable tags to recommend. In addition, history information is also exploited to find the most appropriate recommendations.

Many others works could be cited. However due to the length of the paper we can not cite them and furthermore they are generally closed approaches. They are for the most part content-dependent. What is not the case of FoldCons which mines association rules directly on a primary list of candidate tags. Our experimentations showed the effectiveness of this method.

6. CONCLUSION

We proposed an add-on method to improve the recommendations of tag recommender. We mine association rules on top of their recommendations, then we sort them again thanks to their confidence scores compared to the first tag. Thus we introduce a certain consistency inside the recommendations by taking account of tags which appear generally next to the first candidate tag in the initial recommended list.

This method improves up to 5% the recommendations as shown by our experimentations when the users have not in average a small number of posts.

7. ACKNOWLEDGEMENTS

We would like to thank Steffen Rendle for his software tagrec we used in our experimentations.

References

[1] D. Benz , A. Hotho , R. Ja¨schke, B. Krause , F. Mitzlaff , C. Schmitz , and G. Stumme. The social bookmark and publication management system BibSonomy . The VLDB Journal , 19 ( 6 ): 849 - 875 , Dec. 2010 .

[2] I. Cantador , P. Brusilovsky , and T. Kuflik . 2nd workshop on information heterogeneity and fusion in recommender systems (hetrec 2011) . In Proceedings of the 5th ACM conference on Recommender systems, RecSys 2011 , New York, NY, USA, 2011 . ACM.

[3] M. Gueye , T. Abdessalem , and H. Naacke . Improving tag recommendation by folding in more consistency . CoRR, abs/1309 .7517, sep 2013 .

[4] M. Gueye , T. Abdessalem , and H. Naacke . Strec: An improved graph-based tag recommender . In Proceedings of the 5th ACM RecSys workshop on Recommender systems and the social web , RSWeb '13 , 2013 .

[5] R. Ja ¨schke, L. Marinho , A. Hotho , L. Schmidt-Thieme , and G. Stumme . Tag recommendations in social bookmarking systems . AI Commun ., 21 ( 4 ): 231 - 247 , Dec. 2008 .

[6] M. Lipczak . Tag recommendation for folksonomies oriented towards individual users . ECML PKDD discovery challenge , 84 , 2008 .

[7] S. Maniu , B. Cautis , and T. Abdessalem . Efficient top-k retrieval in online social tagging networks . CoRR, abs/1104.1605v5 , 2012 .

[8] S. Rendle and L. Schmidt-Thieme . Pairwise interaction tensor factorization for personalized tag recommendation . In WSDM '10: Proceedings of the third ACM international conference on Web search and data mining , pages 81 - 90 , New York, NY, USA, 2010 . ACM.

[9] P. Symeonidis , A. Nanopoulos , and Y. Manolopoulos . Tag recommendations based on tensor dimensionality reduction . In Proceedings of the 2008 ACM conference on Recommender systems, RecSys '08 , pages 43 - 50 , New York, NY, USA, 2008 . ACM.

[10] J. Wang , L. Hong , and B. D. Davison . Rsdc ' 09 : Tag recommendation using keywords and association rules . In F. Eisterlehner, A. Hotho , and R. Ja¨schke, editors, ECML PKDD Discovery Challenge 2009 (DC09) , volume 497 , pages 261 - 274 , Bled, Slovenia, September 2009 . CEUR Workshop Proceedings.