Personalized and object-centered tag recommendation methods for Web 2.0 applications

https://doi.org/10.1016/j.ipm.2014.03.002Get rights and content

Highlights

  • We propose new heuristics for object-centered and personalized tag recommendation.

  • We also propose new learning-to-rank (L2R) based strategies for the same tasks.

  • They exploit tag co-occurrences, textual features, relevance metrics and user history.

  • Our solutions greatly outperform state-of-the-art methods on real datasets.

  • Tag personalization produces better descriptions of the objects.

Abstract

Several Web 2.0 applications allow users to assign keywords (or tags) to provide better organization and description of the shared content. Tag recommendation methods may assist users in this task, improving the quality of the available information and, thus, the effectiveness of various tag-based information retrieval services, such as searching, content recommendation and classification. This work addresses the tag recommendation problem from two perspectives. The first perspective, centered at the object, aims at suggesting relevant tags to a target object, jointly exploiting the following three dimensions: (i) tag co-occurrences, (ii) terms extracted from multiple textual features (e.g., title, description), and (iii) various metrics to estimate tag relevance. The second perspective, centered at both object and user, aims at performing personalized tag recommendation to a target object-user pair, exploiting, in addition to the three aforementioned dimensions, a metric that captures user interests.

In particular, we propose new heuristic methods that extend state-of-the-art strategies by including new metrics that estimate how accurately a candidate tag describes the target object. We also exploit three learning-to-rank (L2R) based techniques, namely, RankSVM, Genetic Programming (GP) and Random Forest (RF), for generating ranking functions that exploit multiple metrics as attributes to estimate the relevance of a tag to a given object or object-user pair. We evaluate the proposed methods using data from four popular Web 2.0 applications, namely, Bibsonomy, LastFM, YouTube and YahooVideo. Our new heuristics for object-centered tag recommendation provide improvements in precision over the best state-of-the-art alternative of 12% on average (up to 20% in any single dataset), while our new heuristics for personalized tag recommendation produce average gains in precision of 121% over the baseline. Similar performance gains are also achieved in terms of other metrics, notably recall, Normalized Discounted Cumulative Gain (NDCG) and Mean-Reciprocal Rank (MRR). Further improvements, for both object-centered (up to 23% in precision) and personalized tag recommendation (up to 13% in precision), can also be achieved with our new L2R-based strategies, which are flexible and can be easily extended to exploit other aspects of the tag recommendation problem. Finally, we also quantify the benefits of personalized tag recommendation to provide better descriptions of the target object when compared to object-centered recommendation by focusing only on the relevance of the suggested tags to the object. We find that our best personalized method outperforms the best object-centered strategy, with average gains in precision of 10%.

Introduction

Several Web 2.0 applications have reached unprecedented popularity mainly due to the strong stimuli and easiness for users to create their own content and share it with others, establishing online communities and social networks. Each page in a Web 2.0 application is composed by a main object, which can be stored in different media types (e.g., text, audio, image, video) as well as several other sources of information associated with the object, here referred to as its features. For instance, content features are sources of information that can be extracted from the object itself, such as the color histogram of an image. Textual features, on the other hand, are blocks of text typically assigned by users to the object, such as title, description, tags and several comments posted by users. Finally, there are also features related to the users, here referred to as user profile features, such as the user’s age, sex and tags frequently assigned by her.

Among all textual features, tags have become one of the main textual features in Web 2.0 applications, as they are often exploited to provide better organization and description of the content. Moreover, recent studies have shown that tags are one of the best textual features to be exploited by various tasks related to Information Retrieval (IR), such as automatic object classification (Figueiredo et al., 2013, Ramage et al., 2009), searching (Li, Guo, & Zhao, 2008), and content recommendation (Guy, Zwerdling, Ronen, Carmel, & Uziel, 2010).

In this context, tag recommendation services aim at assisting users in the task of assigning tags to a target object by suggesting keywords that are related to its content, thus improving the quality of the available information and ultimately the effectiveness of various IR services that rely on tags as main data source. The tag recommendation problem can be tackled from two perspectives. The first perspective, object-centered, aims at suggesting relevant tags to a target object, that is, suggesting tags that are related to the object’s content.

The second perspective, centered at both object and user, aims at performing personalized tag recommendation to a target object-user pair. Personalization is motivated by the fact that users typically have different interests, levels of expertise, or vocabulary biases, and may also have different purposes when choosing tags for a target object (e.g., content organization or content description). Moreover, even users with similar purposes may perceive the object’s content differently, particularly in case of multimedia objects (an effect known as the semantic gap). All these factors ultimately impact the user’s tag choices. Thus, personalized tag recommendation aims at suggesting tags that not only are related to the object’s content but also captures the user interests, profile and background, and thus might help services such as content organization. Moreover, as illustrated and further discussed in Sections 3 Tag recommendation: problem statement, 6.5.3 Benefits of personalization in tag recommendation, personalized tag recommendations may also provide, either in isolation or collectively (i.e., all personalized recommendations provided to all users who tagged an object) better and more complete descriptions of the object’s content, compared to object-centered recommendations, which, in turn, help improve services, such as search and content recommendation.

Many existing object-centered strategies exploit tag co-occurrence patterns in previous tag assignments in the collection, expanding an initial tag set Io of the target object o with other tags that frequently co-occur together with the tags in Io (Garg and Weber, 2008, Heymann et al., 2008, Menezes et al., 2010, Sigurbjörnsson and van Zwol, 2008). Other methods do not assume the existence of such tags in the target object, using, instead, terms extracted from other textual features (Lipczak et al., 2009, Wang et al., 2009, Zhang et al., 2009). However, various textual features, including tags, are created by the end users, and thus, may contain a lot of noise (e.g., misspellings or unrelated terms) (Figueiredo et al., 2013, Koutrika et al., 2008). Thus, it is important to filter such terms out of the list of recommendations or reduce their importance, favouring terms that are more “relevant” for the target object. By relevant, we mean terms that are good descriptors of the object’s content and/or that help discriminate it from others, for supporting services such as searching and classification, which typically use tags as data sources. With that in mind, some previous methods (Belém et al., 2010, Lipczak et al., 2009, Sigurbjörnsson and van Zwol, 2008, Wang et al., 2009) exploit metrics of relevance, such as Term Frequency (TF), either to filter out irrelevant candidates or to boost candidates with more potential. Thus, most existing object-centered methods exploit a subset of the following dimensions1: (i) tag co-occurrences with tags previously assigned to the target object, (ii) terms extracted from multiple textual features, and (iii) metrics of relevance. However, to our knowledge, they exploit at most two of these three dimensions.

In the context of personalized tag recommendation, most previous work exploits user profile features, specifically the history of tag assignments of all users of the application, known as folksonomy, or of a particular (target) user, known as her personomy. Collaborative filtering and FolkRank (Jäschke, Marinho, Hotho, Lars, & Gerd, 2007), as well as PITF – Pairwise Interactions Tensor Factorization (Rendle & Lars, 2010) – fall into this category. A few other efforts exploit multiple textual features along with the history of tag assignments (Lipczak et al., 2009) and tag co-occurrence patterns (Garg and Weber, 2008, Rae et al., 2010). However, to our knowledge, existing methods do not jointly exploit tag assignment history along with the three aforementioned dimensions, which may also be important for personalized recommendations.

Accordingly, we here address the tag recommendation from both object-centered and personalized perspectives, modeling it as a multiple candidate tag ranking problem. In other words, we develop functions that estimate the relevance of a candidate tag as a tag recommendation to a given object or to a given object-user pair, thus enabling us to rank the candidate tags according to such estimates, and recommend the most relevant ones as tags to the target object (for object-centered recommendation) or object-user pair (for personalized recommendation).

Unlike previous solutions, we here address the object-centered tag recommendation problem by jointly exploiting all three aforementioned dimensions.2 In other words, we extend traditional tag co-occurrence based approaches to include not only tags that have been previously assigned to the objects (including the target object), but also terms contained in other textual features, such as title and description. The contents of these textual features are used to extract candidate tags. We also exploit several heuristic metrics to try to capture the relevance of each such candidate as a recommendation for the target object. Specifically, we propose eight heuristic strategies for object-centered tag recommendation. Our heuristics extend two state-of-the-art techniques that exploit tag co-occurrences and some metrics of relevance (Menezes et al., 2010, Sigurbjörnsson and van Zwol, 2008) by including new metrics that try to capture how accurately a candidate tag describes the object’s content and by exploiting multiple textual features. They are simple, easy to compute, and quite efficient.

In order to address the personalized tag recommendation problem, we first analyze different strategies to extract tag co-occurrence patterns. Some of these strategies have never been proposed in previous work. More specifically, we define the tag sets exploited to compute co-occurrence patterns in two different ways: (1) all tags assigned to an object by different users and (2) all tags assigned to an object by the same user. While the first strategy benefits from a larger amount of tag relationships, the second one may be less susceptible to noise. In fact, we find that the two strategies produce quite different results, and the best strategy depends on the employed co-occurrence-based method. We then propose two new heuristics that extend our two best object-centered tag recommendation heuristics to include a metric that estimates the relevance of a candidate tag to the target user, named User Frequency (UF). UF is based on the history of tag assignments of the target user.

We note that, for both object-centered and personalized tag recommendation, a number of heuristics can be devised to combine multiple metrics of relevance into a final tag recommendation function. Finding the “best” heuristic is not an easy task due to the potential large size of the search space, which, in our case, consists of all possible tag recommendation functions that can be built using the suggested metrics. Thus, we also investigate the benefits of applying learning-to-rank (L2R) techniques for tag recommendation. We propose three L2R-based object-centered strategies: one exploits the traditional RankSVM method (Joachims, 2006), whereas the other two are based on Genetic Programming (GP) (Banzhaf, Nordin, Keller, & Francone, 1998) and Random Forest (RF) (Breiman, 2001). RankSVM, GP and RF are here treated as meta-heuristics to generate ranking functions that exploit all given metrics as attributes to accurately estimate the relevance of each given candidate tag. Our motivation to use L2R methods are threefold: (1) they can effectively exploit many attributes in the generation of ranking functions, (2) they can be easily extended to include more attributes, and (3) there is a strong theoretical background on learning methods, which has been recently extended for ranking problems (Qin, Liu, & Li, 2010). We also extend our three L2R-based strategies to perform personalized recommendation by including the aforementioned UF metric as an attribute.

We evaluate our object-centered and personalized tag recommendation strategies with real datasets collected from four popular Web 2.0 applications, namely, YouTube and YahooVideo, two video sharing sites, LastFM, an online radio station, and Bibsonomy, a bookmark and publication sharing system.3

In particular, we evaluate our object-centered tag recommendation strategies, comparing them against three state-of-the-art techniques, namely, Sum+, the best function proposed in Sigurbjörnsson and van Zwol (2008), LATRE (Menezes et al., 2010), and the winner of the ECML Discovery Challenge 2009 (Lipczak et al., 2009, Lipczak and Milios, 2011), here referred to as Co-occurrence and Text-based Tag RecommenderCTTR. Sum+ exploits co-occurrence of pre-assigned tags along with some tag frequency statistics. LATRE, in turn, is a more recent, efficient and effective method that exploits solely tag co-occurrence patterns. Our heuristics are extensions of these two methods. CTTR exploits the contents of textual features associated with the target object along with one metric of tag relevance, but does not consider the tags previously assigned to the target object.

Our results indicate that our object-centered heuristics produce improvements over the original techniques on which they are based of 36% in precision and 40% in recall on average across all datasets and heuristics, with gains on a single dataset reaching as much as 105% and 116%, respectively. Moreover, our best heuristic outperforms the best baseline, with average gains of 12% (up to 20%) in precision and 13% (up to 25%) in recall. This heuristic extends the LATRE baseline by incorporating a new metric that tries to capture the descriptive power of each candidate tag and by exploiting multiple textual features.

Further improvements over our best heuristics can also be achieved with our L2R-based strategies, with gains in precision and recall of up to 23% and 14% on average. In particular, our results show that Random Forest is the best of the three L2R techniques, with average gains in precision over the best of GP and RankSVM in each dataset of 7% (and reaching up to 10%). Similar performance gains are also achieved in terms of others metrics, notably Normalized Discounted Cumulative Gain (NDCG) and Mean-Reciprocal Rank (MRR) (Sigurbjörnsson & van Zwol, 2008).

We also evaluate our personalized tag recommendation strategies, comparing them against the state-of-the-art PITF personalized strategy (Rendle & Lars, 2010). We find that our best heuristic outperforms PITF by 121% in precision and 122% in recall, on average. Moreover, like for object-centered strategies, our L2R-based personalized tag recommendation methods also yield further improvements: the best L2R strategy – the RF-based method – provides gains of 10% on average (and up to 13%) in precision over our best heuristic. Once again, similar improvements in recall, NDCG and MRR were also achieved. In general, for both object-centered and personalized recommendation, we note that the L2R-based strategies provide a flexible framework that can be easily extended to include other attributes (i.e., tag relevance metrics) or to address other aspects of the tag recommendation problem. As a final result, we also quantify the benefits of personalized tag recommendations to produce better descriptions of the target object when compared to object-centered recommendations, by measuring the relevance of the suggested tags to the object only (i.e., disregarding their relevance to the target user). Comparing our best personalized and object-centered tag recommenders, both based on the RF technique, we find that the former outperforms the latter, with average gains in precision of 10%.

In sum, we here greatly extend our previous effort (Belém, Martins, Pontes, Almeida, & Gonçalves, 2011), by bringing the following main contributions: (1) the proposal of seven personalized tag recommendation solutions (four heuristics and three L2R-based approaches); (2) the analysis of new tag co-occurrence patterns not exploited in previous work; (3) an extended experimental evaluation, for both object-centered and personalized strategies, including data obtained from Bibsonomy, a standard dataset to evaluate tag recommendation (Benz et al., 2010, Lipczak and Milios, 2011), and new evaluation metrics; (4) the inclusion of new tag relevance metrics used as attributes in our L2R-based strategies, namely, Predictability (Pred) and, for personalized strategies, User Frequency (UF); (5) the application of the Random Forest technique to the tag recommendation problem, particularly in the context of personalized recommendation, producing results that are significantly superior to the results of previously evaluated L2R-based techniques; and (6) a quantitative assessment of the benefits of personalized tag recommendation to provide better descriptions of the target object.

The rest of this article is organized as follows. Section 2 discusses related work, whereas Section 3 describes how we model the tag recommendation problem. The main metrics used to estimate the relevance of a candidate tag are defined in Section 4, while our new tag recommendation techniques are introduced in Section 5. Section 6 presents our experimental evaluation and discusses the most representative results. Section 7 concludes the article and points out some directions for future work.

Section snippets

Related work

In this section, we review related efforts, starting by presenting existing tag recommendation methods in Section 2.1. We then discuss previous studies of Learning-to-Rank techniques in general and in the tag recommendation domain, specifically, in Section 2.2. Finally, in Section 2.3, we briefly review previous characterizations of tagging systems.

Tag recommendation: problem statement

A Web 2.0 object is a media instance (e.g., a text, an audio, a video, an image) in a given Web 2.0 application. There are various sources of information related to an object, here referred to as its features. In particular, textual features, one of our main sources of information, comprise the self-contained textual blocks that are associated with an object, usually with a well defined functionality (Figueiredo et al., 2013). The textual features here exploited are tags, title and description

Relevance metrics for tag recommendation

In this section, we present several metrics that can be used to estimate the relevance of a candidate for tag recommendation. They are used as attributes by our tag recommendation methods, particularly the L2R-based strategies. Some metrics, like Sum,Stability,TF and Entropy, have been previously applied to recommend tags (Heymann et al., 2008, Menezes et al., 2010, Sigurbjörnsson and van Zwol, 2008). Others, such as IFF and AFS, were proposed in our previous work (Belém et al., 2011) and are

Tag recommendation strategies

In this section, we present the tag recommendation strategies analyzed in this work. First, in Section 5.1, we describe state-of-the-art methods used here as baselines for object-centered and personalized tag recommendation. The object-centered baseline methods exploit a combination of at most two of the following dimensions: term co-occurrence with pre-assigned tags, multiple textual features and relevance metrics. The personalized baseline method is a matrix factorization approach that

Experimental evaluation

In this section, we first present the datasets used to evaluate the tag recommendation strategies (Section 6.1) as well as our evaluation methodology (Section 6.2) and metrics (Section 6.3). Next, we describe how we parameterized each strategy (Section 6.4), and discuss a set of representative results (Section 6.5).

Conclusions and future work

In this article, we proposed several new object-centered tag recommendation strategies that jointly exploit term co-occurrence with pre-assigned tags, multiple textual features and metrics of tag relevance. We also proposed personalized strategies, which exploit the aforementioned dimensions and the tag assignment history of the target user. Our strategies include several heuristics and learning-to-rank based methods. We compared our strategies against four state-of-the-art techniques, in

Acknowledgements

This research is partially funded by the Brazilian National Institute of Science and Technology for Web Research (MCT/CNPq/INCT Web Grant Number 573871/2008-6), and by the authors individual grants from CNPq, CAPES and FAPEMIG. We also would like to thank the reviewers for their comments and suggestions, which greatly contributed for this work.

References (63)

  • F. Figueiredo et al.

    Assessing the quality of textual features in social media

    Information Processing and Management: An International Journal

    (2013)
  • Y. Zhang et al.

    Auralist: Introducing serendipity into music recommendation

  • H. Abdi

    Bonferroni and Sidak corrections for multiple comparisons

    (2007)
  • R. Agrawal et al.

    Fast algorithms for mining association rules in large databases

  • J. Almeida et al.

    On the quality of information for Web 2.0 services

    IEEE Internet Computing

    (2010)
  • J.A Aslam et al.

    Document selection methodologies for efficient and effective learning-to-rank

  • R. Baeza-Yates et al.

    Modern information retrieval

    (2011)
  • W. Banzhaf et al.

    Genetic programming – An introduction on the automatic evolution of computer programs and its applications

    (1998)
  • F. Belém et al.

    Associative tag recommendation exploiting multiple textual features

  • F. Belém et al.

    Exploiting novelty and diversity in tag recommendation

  • F. Belém et al.

    Topic diversity in tag recommendation

  • F. Belém et al.

    Exploiting co-occurrence and information quality metrics to recommend tags in Web 2.0 applications

  • D. Benz et al.

    The social bookmark and publication management system BibSonomy

    The VLDB Journal

    (2010)
  • Bin Bi et al.

    Automatically generating descriptions for resources by tag modeling

  • L. Breiman

    Random forests

    Machine Learning

    (2001)
  • Cao, H., Xie, M., Xue, L., Liu, C., Teng, F., & Huang, Y. (2009). Social tag prediction based on supervised ranking...
  • F. Faria et al.

    Learning to rank for content-based image retrieval

  • W. Feng et al.

    Incorporating heterogeneous information for personalized tag recommendation in social tagging systems

  • Y. Freund et al.

    An efficient boosting algorithm for combining preferences

    Journal of Machine Learning Research

    (2003)
  • J. Friedman

    Greedy function approximation: A gradient boosting machine

    Annals of Statistics

    (2000)
  • N. Garg et al.

    Personalized, interactive tag recommendation for Flickr

  • Jonathan Gemmell et al.

    Hybrid tag recommendation for social annotation systems

  • G. Gomes et al.

    Is learning to rank worth it? A statistical analysis of learning to rank methods

    Journal of Information and Data Management

    (2013)
  • Z. Guan et al.

    Personalized tag recommendation using graph-based ranking on multi-type interrelated objects

  • I. Guy et al.

    Social media recommendation based on people and tags

  • P. Heymann et al.

    Social tag prediction

  • L. Hong et al.

    Learning to rank social update streams

  • R. Jäschke et al.

    Tag recommendations in folksonomies

  • T. Joachims

    Training linear SVMs in linear time

  • Katakis, I., Tsoumakas, G., & Vlahavas, I. (2008). Multilabel text classification for automated tag suggestion. In...
  • G. Koutrika et al.

    Combating spam in tagging systems: An evaluation

    ACM Transactions on the Web

    (2008)
  • Cited by (0)

    View full text