Nowadays Web sites tend to be more and more social: users can upload any kind of information on collaborative platforms and can express their opinions about the content they enjoyed through textual feedbacks or reviews. These platforms allow users to annotate resources they like through freely chosen keywords (called tags). The main advantage of these tools is that they perfectly fit user needs, since the use of tags allows organizing the information in a way that closely follows the user mental model, making retrieval of information easier. However, the heterogeneity characterizing the communities causes some problems in the activity of social tagging: someone annotates resources with very specific tags, other people with generic ones, and so on. These drawbacks reduce the exploitation of collaborative tagging systems for retrieval and filtering tasks. Therefore, systems that assist the user in the task of tagging are required. The goal of these systems, called tag recommenders, is to suggest a set of relevant keywords for the resources to be annotated. This paper presents a tag recommender system called STaR (Social Tag Recommender system). Our system is based on two assumptions: 1) the more two or more resources are similar, the more they share common tags 2) a tag recommender should be able to exploit tags the user already used in order to extract useful keywords to label new resources. We also present an experimental evaluation carried out using a large dataset gathered from Bibsonomy.
H.3.1 [Information Storage and Retrieval]: Content Analysis and Indexing: Indexing methods; H.3.3 [Information Storage and Retrieval]: Information Search and Retrieval: 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.
Copyright 200X ACM X-XXXXX-XX-X/XX/XX ...$10.00.
1.
We are assisting to a transformation of the Web towards
a more user-centric vision called Web 2.0. By using Web 2.0
applications users are able to publish auto-produced
contents such as photos, videos, political opinions, reviews, hence
they are identified as Web prosumers: producers + consumers
of knowledge. Recently the research community has
thoroughly analyzed the dynamics of tagging, which is the act
of annotating resources with free labels, called tags. Many
argue that, thanks to the expressive power of folksonomies
[
Undoubtedly the power of tagging lies in the ability for
people to freely determine the appropriate tags for a
resource [
Since these problems are of hindrance to completely
exploit the expressive power of folksonomies, in the last years
many tools have been developed to assist the user in the
task of tagging and to aid at the same time the tag
convergence [
Clearly, the more these recommended tags match the user needs and her mental model, the more she will use them to annotate the resource. In this way we can rapidly speed up the tag convergence aiding at the same time in filtering the noise of the complete tag space.
This paper presents the tag recommender STaR. When developing the model, we tried to point out two concepts: • resources with similar content should be annotated with similar tags; • a tag recommender needs to take into account the previous tagging activity of users, increasing the weight of the tags already used to annotate similar resources.
In this work, we identify two main aspects in the tag recommendation task: first, each user has a typical manner to label resources; second, similar resources usually share common tags.
The paper is organized as follows. Section 2 analyzes related work. Section 3 explains the architecture of the system and how the recommendation approach is implemented. The experimental evaluation carried out is described in Section 4, while conclusions and future work are drawn in the last section. 2.
Usually the works in the tag recommendation area are broadly divided into three classes: content-based, collaborative and graph-based approaches.
In the content-based approach, exploiting some
Information Retrieval-related techniques, a system is able to
extract relevant unigrams or bigrams from the text. Brooks et.
al [
AutoTag [
TagAssist [
Marinho [
The problem of tag recommendation through graph-based
approaches has been firstly addressed by Ja¨schke et al. in [
In literature we can find also other methods (called hybrid ), which try to integrate two of more sources of knowledge (mainly, content and collaborative ones) in order to improve the quality of recommended tags.
Heymann et. al [
Lipczak in [
Finally, in [
Following the definition introduced in [
We can also define a tag assignment function tas: U × R → T .
So, a collaborative tagging system is a platform composed of users, resources and tags that allows users to freely assign tags to resources, while the tag recommendation task for a given user u ∈ U and a resource r ∈ R can be described as the generation of a set of tags tas(u, r) ⊆ T according to some relevance model. In our approach these tags are generated from a ranked set of candidate tags from which the top n elements are suggested to the user.
STaR (Social Tag Recommender) is a content-based tag
recommender system, developed at the University of Bari. The
inceptive idea behind STaR is to improve the model
implemented in systems like TagAssist [
Although we agree that similar resources usually share similar tags, in our opinion Mishne’s approach presents two important drawbacks: 1. the tag re-ranking formula simply performs a sum of the occurrences of each tag among all the folksonomies, without considering the similarity with the resource to be tagged. In this way tags often used to annotate resources with a low similarity level could be ranked first; 2. the proposed model does not take into account the previous tagging activity performed by users. If two users bookmarked the same resource, they will receive the same suggestions since the folksonomies built from similar resources are the same.
We will try to overcome these drawbacks, by proposing an approach firstly based on the analysis of similar resources capable also of leveraging the tags already selected by the user during her previous tagging activity, by putting them on the top of the tag rank. Figure 1 shows the general architecture of STaR. The recommendation process is performed in four steps, each of which is handled by a separate component. 3.1
Given a collection of resources (corpus) with some textual metadata (such as the title of the resource, the authors, the description, etc.), STaR firstly invokes the Indexer module in order to perform a preprocessing step on these data by exploiting Apache Lucene6. Obviously, the kind of metadata to be indexed is strictly dependant on the nature of the resources. For example, supposing to recommend tags for bookmarks, we could index the title of the web page and the extended description provided by users, while for BibteX entries, we could index the title of the publication and the abstract. Let U be the set of users and N the cardinality of this set, the indexing procedure is repeated N + 1 times: we build an index for each user (Personal Index ) storing the information on the resources she previously tagged and an index for the whole community (Social Index ) storing the information about all the tagged resources by merging the singles Personal Indexes.
Following the definitions presented above, given a user u ∈ U we define P ersonalIndex(u) as:
P ersonalIndex(u) = {r ∈ R|∃t ∈ T : tas(u, r) = t} (1) where tas is the tag assignment function tas: U × R → T which assigns tags to a resource annotated by a given user. SocialIndex represents the union of all the user personal indexes:
N SocialIndex = [ P ersonalIndex(ui) i=1 (2) 3.2
Next, STaR can take into account users requests in order to produce personalized tag recommendations for each resource. First, every user has to provide some information about the resource to be tagged, such as the title of the Web page or its URL, in order to crawl the textual metadata associated on it.
Next, if the system can identify the user since she has already posted other resources, it exploits data about her (language, the tags she uses more, the number of tags she usually uses to annotate resources, etc.) in order to refine the query to be submitted against both the Social and Personal indexes stored in Lucene. We used as query the title of the web page (for bookmarks) or the title of the publication (for BibTeX entries). Obviously before submitting the query we processed it by deleting not useful characters and punctuation.
In order to improve the performances of the Lucene Querying Engine we replaced the original Lucene Scoring function
with an Okapi BM25 implementation7. BM25 is nowadays
considered as one of the state-of-the art retrieval models by
the IR community [
Let D be a corpus of documents, d ∈ D, BM25 returns the top-k resources with the highest similarity value given a resource r (tokenized as a set of terms t1 . . . tm), and is defined as follows: sim(r, d) = r nti
Pim=1 k1((1−b)+b∗l)+ntri ∗ idf (ti) where ntri represents the occurrences of the term ti in the document d, l is the ratio between the length of the resource and the average length of resources in the corpus. Finally, k1 and b are two parameters typically set to 2.0 and 0.75 respectively, and idf (ti) represents the inverse document frequency of the term ti defined as follows: idf (ti) = log
N + df (ti) + 0.5
df (ti) + 0.5 where N is the number of resources in the collection and df (ti) is the number of resources in which the term ti occurs.
Given user u ∈ U and a resource r, Lucene returns the resources whose similarity with r is greater or equal than a threshold β. To perform this task Lucene uses both the PersonalIndex of the user u and the SocialIndex. More formally: P Res(u, q) = {r ∈ P ersonalIndex(u)|sim(q, r) ≥ β}
S Res(q) = {r ∈ SocialIndex|sim(q, r) ≥ β}
Figure 2 depicts an example of the retrieving step. In this case the target resource is represented by Gazzetta.it, one of the most famous Italian sport newspaper. Lucene queries the SocialIndex and returns as the most similar resources an online newspaper (Corrieredellosport.it) and the official web site of an Italian Football Club (Inter.it). The
The role of the Tag Extractor is to produce as output the list of the so-called ”candidate tags” (namely, the tags considered as ’relevant’ by the tag recommender). In this step the system gets the most similar resources returned by the Apache Lucene engine and builds their folksonomies (namely, the tags they have been annotated with). Next, it produces the list of candidate tags by computing for each tag from the folksonomy a score obtained by weighting the similarity score returned by Lucene with the normalized occurrence of the tag. If the Tag Extractor also gets the list of the most similar resources from the user PersonalIndex, it will produce two partial folksonomies that are merged, assigning a weight to each folksonomy in order to boost the tags previously used by the user.
Formally, for each query q (namely, the resource to be tagged), we can define a set of tags to recommend by building two sets: candT agsp and candT agss. These sets are defined as follows: candT agsp(u, q) = {t ∈ T |t = T AS(u, r) ∧ r ∈ P Res(u, q)} candT agss(q) = {t ∈ T |t = T AS(u, r) ∧ r ∈ S Res(q) ∧ u ∈ U }
In the same way we can compute the relevance of each tag with respect to the query q as: (5) (6) relp(t, u, q) = rels(t, q) =
Pr∈P Res(u,q) ntr ∗ sim(r, q)
nt Pr∈S Res(q) ntr ∗ sim(r, q) nt where ntr is the number of occurrences of the tag t in the annotation for resource r and nt is the sum of the occurrences of tag t among all similar resources.
Finally, the set of Candidate Tags can be defined as: candT ags(u, q) = candT agsp(u, q) ∪ candT agss(q) (7) where for each tag t the global relevance can be defined as: rel(t, q) = α ∗ relp(t, q) + (1 − α) ∗ rels(t, q) (8) where α (PersonalTagWeight) and (1−α) (SocialTagWeight) are the weights of the personal and social tags respectively.
Figure 3 depicts the procedure performed by the Tag Extractor : in this case we have a set of 4 Social Tags (Newspaper, Online, Football and Inter) and 3 Personal Tags (Sport, Newspaper and Tuttosport). These sets are then merged, building the set of Candidate Tags. This set contains 6 tags since the tag newspaper appears both in social and personal tags. The system associates a score to each tag that indicates its effectiveness for the target resource. Besides, the scores for the Candidate Tags are weighted again according to SocialTagWeight (α) and PersonalTagWeight (1 − α) values (in the example, 0.3 and 0.7 respectively), in order to boost the tags already used by the user in the final tag rank. Indeed, we can point out that the social tag ‘football’ gets the same score of the personal tag ‘tuttosport’, although its original weight was twice. 3.4
Finally, the last step of the recommendation process is performed by the Filter. It removes from the list of candidate tags the ones not matching specific conditions, such as a threshold for the relevance score computed by the Tag Extractor. Obviously, the value for the threshold and the maximum number of tags to be recommend is strictly dependent from the training data.
Formally, given a user u ∈ U , a query q and a threshold value γ, the goal of the filtering component is to build rec(u, q) defined as follows: rec(u, q) = {t ∈ candT ags(u, q)|rel(t, q) > γ}
We designed two different experimental sessions to evaluate the performance of the tag recommender. In the first session we performed a comparison between the original scoring function of Lucene and a novel BM25 implementation, while the second was carried out to tune the system parameters. 4.1
We designed the experimental evaluation by exploiting a dataset gathered from Bibsonomy. It contains 263,004 bookmark posts and 158,924 BibTeX entries submitted by 3,617 different users. For each of the 235,328 different URLs and the 143,050 different BibTeX entries were also provided some textual metadata (such as the title of the resource, the description, the abstract and so on).
We evaluated STaR by comparing the real tags (namely, the tags a user adopts to annotate an unseen resource) with the suggested ones. The accuracy was finally computed using classical IR metrics, such as Precision, Recall and F1Measure. Precision (Pr) is defined as the number of relevant recommended tags divided by the number of recommended tags. Recall (Re) is defined as the number of relevant recommended tags divided by the total number of relevant tags available. The F1-measure is computed by the following formula:
F 1 = (2 ∗ P r ∗ Re)
P r + Re (9) 4.2
Firstly, we tried to evaluate the predictive accuracy of STaR comparing difference scoring function (namely, the Lucene original one and the aforementioned BM25 implementation). We performed the same steps previously described, retrieving the most similar items using the two mentioned similarity functions and comparing the tags suggested by the system in both cases. Results are presented in Table 1.
In general, there is an improvement by adopting BM25 with respect to the Lucene original similarity function. We can note that BM25 improved the both the recall (+ 6,95% for bookmarks, +1,46% for BibTeXs entries) and the F1 measure (+ 2,86% for bookmarks, +0,17% for BibTeXs entries).
Next we designed a second experimental evaluation in order to compare the predictive accuracy of STaR with different combinations of system parameters. Namely: • the maximum number of similar documents retrieved by Lucene; • the value of α for the PersonalTagWeight and Social
TagWeight parameters; • the threshold γ to establish whether a tag is relevant; • which fields of the target resource use to compose the query; • the best scoring function between Lucene standard one and Okapi BM25.
First, tuning the number of similar documents to retrieve from the PersonalIndex and SocialIndex is very important, since a value too high can introduce noise in the retrieval process, while a value too low can exclude documents containing relevant tags. By analyzing the results returned by some test queries, we decided to set this value between 5 and 10, depending on the training data.
Next, we tried to estimate the values for PersonalTagWeight (PTW) and the SocialTagWeight (STW). An higher weight for the Personal Tags means that in the recommendation process the systems will weigh more the tags previously used by the target user, while an higher value for the Social Tags will give more importance to the tags used by the community (namely, the whole folksonomy) on the target resource. These parameters are biased by the user practice: if tags often used by the user are very different from those used from the community, the PTW should be higher than STW. We performed an empirical study since it is difficult to define the user behavior at run time. We tested the system setting the parameters with several combinations of values: i) PTW = 0.7 STW = 0.3; ii) PTW = 0.5 STW = 0.5; iii) PTW = 0.3 STW = 0.7.
Another parameter that can influence the system performance is the set of fields to use to compose the query. For each resource in the dataset there are many textual fields, such as title, abstract, description, extended description, etc. In this case we used as query the title of the webpage (for bookmarks) and the title of the publication (for BibTeX entries).
The last parameter we need to tune is the threshold to deem a tag as relevant (γ).We performed some tests suggesting both 4 and 5 tags and we decided to recommend only 4 tags since the fifth was usually noisy. We also fixed the threshold value between 0.20 and 0.25.
In order to carry out this experimental session we used the aforementioned dataset both as training and test set. We executed the test over 50, 000 bookmarks and 50, 000 BibTeXs. For each resource randomly chosen from the dataset and for each combination of parameters, we executed the following steps: • query preparation; • Lucene retrieval function invocation; • building of the set of Candidate Tags; • comparing the recommended tags with the real tags associated by the user; • computing of Precision, Recall, and F1-measure.
Analyzing the results (see Figure ??), it emerges that the approach we called user-based outperformed the other ones. In this configuration we set PTW to 1.0 and STW to 0, so we suggest only the tags already used by the user in tagging similar resources. No query was submitted against the SocialIndex. The first remark we can make is that each user has her own mental model and her own vocabulary: she usually prefers to tag resources with labels she already used. Instead, getting tags from the SocialIndex only (as proved by the results of the community-based approach) often introduces some noise in the recommendation process. The hybrid approaches outperformed the community-based one, but their predictive accuracy is still worse when compared with the user-based approach. Finally, all the approaches outperformed the F1-measure of the baseline. We computed the baseline recommending for each resource only its most popular tags. Obviously, for resources never tagged we could not suggest anything.
This analysis substantially confirms the results we
obtained from other studies performed in the area of the
tagbased recommendation [
Collaborative Tagging Systems are powerful tools, since they let users to organize the information in a way that perfectly fits their mental model. However, typical drawbacks of collaborative tagging systems represent an hindrance, since the complete tag space is too noisy to be exploited for retrieval and filtering task. So, systems that assist users in the task of tagging speeding up the tag convergence are more and more required. In this paper we presented STaR, a social tag recommender system. The idea behind our work was to discover similarity among resources in order to exploit communities and user tagging behavior. In this way our recommender system was able to suggest tags for users and items still not stored in the training set. The experimental sessions showed that users tend to reuse their own tags to annotate similar resources, so this kind of recommendation model could benefit from the use of the user personal tags before extracting the social tags of the community (we called this approach user-based). Next, we showed that the integration of a more effective scoring function (BM25) could also improve the overall accuracy of the system.
This approach has a main drawback, since it cannot suggest any tags when the set of similar items returned by Lucene is empty. So, we plan to extend the system in order to extract significant keywords from the textual content associated to a resource (title, description, etc.) that has not similar items, maybe exploiting structured data or domain ontologies. Furthermore, since tags usually suffer of typical Information Retrieval problem (namely, polysemy, synonymy, etc.) we will try to establish if the integration of Word Sense Disambiguation tools or a semantic representation of documents could improve the performance of recommender. Another issue to analyze is the application of our methodology in different domains such as multimedia environment. In this field discovering similarity among items just on the ground of textual content could be not sufficient. Finally, we will perform also some studies in the area of tag-based recommendation, investigating the integration of tag recommenders for recommendations tasks, since reaching more quickly the tag convergence could help to build better folksonomies and to produce more accurate recommendations. 6.