Social bookmarking is an effective way for sharing knowledge about a vast amount of resources on the World Wide Web. In many social bookmarking systems, users bookmark Web resources with a set of informal tags which they think are appropriate for describing them. Hence, automatic tag recommendation for social bookmarking systems could facilitate and boost the annotation process. For the tag recommendation task, we exploited three kinds of information sources, i.e., resource descriptions, previously annotated tags on the same resource, and previously annotated tags by the same person. A filtering method for removing inappropriate candidates and a weighting scheme for combining information from multiple sources were devised and deployed for ECML PKDD Discovery Challenge 2009. F-measure values of the proposed approach are 0.17975 for task #1 and 0.32039 for task #2, respectively.
Social bookmarking systems such as BibSonomy1 and Delicious2 have increasingly been used for sharing bookmarking information on the Web resource. Such systems are generally built on a set of collectively-annotated informal tags, comprising a folksonomy. A tag recommendation system could guide users during the bookmarking procedure by providing a suitable set of tags for a given resource. In this paper, we propose a simple but effective approach for tackling the tag recommendation problem. The gist of our method is to appropriately combine different information sources with pre-elimination of barely-used tags.
The candidate tags for recommendation can be extracted from the following information sources. First, resources themselves may have the annotated tags. For example, the title of a journal article is likely to include some of the annotated keywords. Second, the tags previously annotated by other users for the same resource could be a good candidate set. Third, previously annotated tags for other resources by the same user could also provide some information.3
The paper is organized as follows. In Section 2, the proposed tag recommendation method is detailed. Then, Section 3 shows the results of experimental evaluation on the training dataset, confirming the effectiveness of the proposed method. Performance of our method on the test dataset is briefly described in Section 4. Finally, concluding remarks are drawn in Section 5. 2
In this section, we detail the proposed tag recommendation method. First, the procedure for keyword extraction from resource descriptions with importance estimation and filtering is explained. Then, the keyword extraction and importance estimation method from previously annotated information is described. Finally, tag recommendation by combining multiple information sources is explained. 2.1
In our approach, candidate keywords are extracted from the columns url, description, and extended description of the table bookmark as well as the columns journal, booktitle, description, and title of the table bibtex. It should be noted here that the candidates extracted from different fields are processed separately. This means that even the same keywords could have multiple importance values according to the columns from which they are extracted.4
In order to estimate the importance of each keyword, its accuracy and frequency ratios are calculated as follows.
D: set of all documents (resources) such as bookmarks or BibTex references. EC(k, d): extraction count of keyword k in document d.
MC(k, d): matching count of keyword k with one of the tags of document d.5 TEC(d): extraction count of all the keywords in document d.
Accuracy Ratio, AR(k) = ∑ ∈ MC( , ) ⁄ ∑ ∈ EC( , ).
Frequency Ratio, FR(k) = ∑ ∈ EC( , ) ⁄ ∑ ∈ TEC( ). (1) (2) The accuracy and frequency ratios of each keyword are calculated across all the documents. 3 [1] also exploited these kinds of information sources for tag recommendation. We extend this approach by extracting keywords from not only resource title but also other resource descriptions. 4 It is because average importance values of keywords are different according to extracted columns. 5 MC(k, d) is equal to EC(k, d) if d is tagged with k, 0 otherwise. The keywords whose accuracy is lower than average are not considered for recommendation. This elimination procedure is implemented by the following criterion, which also penalizes frequent words.
TMC(d): sum of MC(k, d) across all the keywords in document d.
Limit Condition: AR(k) / (1 + FR(k)) > ∑ ∈ TMC( ) ⁄ ∑ ∈ TEC( ). (3)
Some keywords with high accuracy ratio values are shown in Table 1. It should be noted that there exist a large amount of keywords having high AR(k) values and the keywords in Table 1 are a sample from them.
nejm medscape freebox harum ldap shipyard
Extracted columns extended description extended description description description
url description
netbib guide media daily list engine
tool ontologies corpus Extracted columns url url url extended description extended description extended description description description description
ratio, AR(k) 0.0789 0.0778 0.0781 0.0602
ratio, FR(k)
Finally, each extracted keyword, satisfying Equation (3), is stored in d-keyword set (DS). The accuracy weight of each candidate is calculated by multiplying its accuracy ratio and extraction count from the present document as follows.
Accuracy Weight from Document Set, AWDS(k) = EC(k, d)ⅹAR(k). (4) The accuracy weight, AWDS(k), is calculated when recommending tags for a given document (resource) d. 2.2
Candidate keywords could be extracted from the previously annotated tags for the same resource. For the BibTex references, the field simhash1 of the table bibtex is adopted for the semantically-same resource detection. For the bookmarks, a pruning function, which has similar effect of the approach used in [2], was implemented and deployed in our experiments. These candidate keywords are stored in r-keyword set (RS). Their accuracy weight is calculated as follows.
D: set of all documents (resources) satisfying the same document condition with the present document d.
TC(k, d): 1 if document d has keyword k; 0 otherwise.
Accuracy Weight from Resource Set, AWRS(k) = ∑ ∈ TC( , ). (5)
Candidate keywords are also extracted from the previously annotated tags by the same person. These candidate keywords are stored in u-keyword set (US). Their accuracy weight is obtained as follows.
D: set of all documents (resources) which are previously tagged by user u. UC(k, d): 1 if document d has keyword k; 0 otherwise.
Accuracy Weight from User Set, AWUS(k) = ∑ ∈ UC( , ). (6) 2.3
The last step is to recommend appropriate tags from the three candidate keyword sets, i.e., d-keyword set (DS), r-keyword set (RS), and u-keyword set (US). Given a specific user and a document (resource) for tagging, these three candidate keyword sets are specified with accuracy weight for each candidate. Before unifying these candidates, the accuracy weights are normalized into [0, 1] as follows.
We also added tag frequency information, denoting how many times a tag was annotated during the training period. This tag frequency rate is calculated as follows. TFR(ek) = ∑ ∈ TagCount( , ) ⁄ ∑∈ ∑ ∈ TagCount (, ); 0 ≤ TFR( ) ≤ 1, where TagCount(t, d) denotes the number of occurrences of a tag t annotated for a document d. T and D denote the set of all tags and the set of all documents (resources), respectively.
The above four factors are linearly combined with appropriate coefficients. We have experimented with different coefficient values, trying to obtain nearly optimal results. First, we focused on the fact that the performance of extracted keywords from d-keyword set (DS) is higher than that from r-keyword or u-keyword sets (RS or US). Figure 1 compares the performance using each keyword set on the training dataset when the number of recommended tags is five.
Accordingly, we tried high coefficient values on NWDS(ek) and relatively low coefficient values on NWRS(ek) and NWUS(ek). However, this scheme does not produce better results than other schemes as shown in Figure 2. portal tag tech template
time youtube 0.0439 0.0410 0.0318 0.0620 0.1560 0.3217 0.1080 0.1194 0.0598 0.1911 0.0951 0.0877 extended description 0.1250 0.1237 0.1406 0.2023 0.0322 0.0319 In Figure 2, Uniform denotes the case of assigning an equal coefficient (0.3) to each keyword set and DS (RS or US) denotes the case of assigning 0.45 to DS (RS or US) and 0.25 to the other keyword sets. TFR(ek) was assigned 0.1 or 0.05 in the above cases. On the contrary to our expectation, the weighting scheme assigning high coefficient value to US showed the best performance.
The reason for this phenomenon is not clear but one possible clue is that performance of the candidates extracted from DS varies much according to extracted data columns. Such keywords are illustrated in Table 3. In Table 3, it is observed that even the same keyword from DS could have extremely different accuracy ratio values. For example, the keyword portal from extended description has much higher AR(k) value than the average, i.e., about 0.05964. However, the accuracy ratios of the same keyword from url or description are lower than the averages.
After several trials, we applied the following formula for the recommendation, which has shown fine results on the training dataset.
NWDS(ek)ⅹ.2 + NWRS(ek)ⅹ.35 + NWUS(ek)ⅹ.4 + TFR(ek)ⅹ.05.
(7)
To evaluate the proposed approach, we reserved the postings spanning the latest six months from the given training dataset like the real challenge. Hence, the training period is from January 1995 to June 2008 and the validation period is from July to December of 2008. The numbers of postings, resources, and users during these periods are shown in Tables 4 and 5. In this subsection, we present the effect of our keyword elimination method (Equation (3)). Note that Limit Condition is applied to the candidate keywords whose accuracy ratio is lower than average with some penalizing effect on frequently-occurred keywords. Figures 3 and 4 show the effect of candidate elimination on the Post-Core and Cleaned Dump datasets, respectively. The results are obtained when the number of recommended tags is five. On the both validation datasets (i.e., Post-Core and Cleaned Dump), the proposed elimination method increases precision and F-measure values regardless of the number of recommended tags (from one to ten, although the results are not shown here). In the case of the Cleaned Dump dataset, recall is also improved by our filtering method. Here, we append the final results of our method on the test dataset of ECML PKDD Discovery Challenge 2009. We applied a simple weighting scheme for combining different information sources and a candidate filtering method for tag recommendation. The proposed filtering method was shown to improve precision and F-measure for the tag recommendation task in all the cases of our experiments. It has also shown to be effective for improving recall in some cases. Future works include finding more optimal scheme for combining multiple information sources. Evolutionary algorithms would be a suitable methodology for this task.
This work was supported in part by the Seoul Development Institute through Seoul R&BD Program (GS070167C093112) and in part by the Ministry of Culture, Sports and Tourism of Korea through CT R&D Program (20912050011098503004).