The purpose of this paper is to describe our approach to Tag Recommendation Task during ECML PKDD 2009 Challenge. The organizers supplied a training set of tagged webpages and publications from BibSonomy portal. Our goal was to build a model which can predict tags for new users bookmarking digital resources. Our strategy was based on an assumption that users tend to tag the same resources in various systems. Therefore, have we developed a tracking engine, which was adjusted to the profile of BibSonomy users in selection of RSS feeds and utilized the training data to optimize the list of tracked URLs. We had over 90 days to collect the data from the feeds, but this period did not overlap with the dates of posts from the training set. As a result we had to set manually parameters responsible for a trade-off between recall and accuracy of the model. We stored all downloaded feed entries in a searching engine. The recommendation was based on tags attached to the documents retrieved from the engine by means of typical information retrieval query.
The development of collaborative society that we experience in recent years can be
characterized by four principles: being open, peering, sharing and acting globally [
This paper describes our attempt to predict tags already chosen by BibSonomy users. This was the Task 1 in ECML PKDD 2009 Challenge. However, we believe that our system is better suited for the third Task, in which the Teams have an opportunity to deliver recommendations online. 2
The growing interest of research community in the field of social bookmarking was
fueled by last year’s ECML challenge, during which the evaluation measures were
standardized and benchmark data sets prepared. Thirteen solutions were submitted to
the tag spam detection task and only five to tag recommendation task. We were
inspired by the best teams in the Challenge, which relied on several external resources
[
We used cleaned dump dataset which consisted of three tables: bibtex (158 924 records), bookmark (263 004 records) and tas (1 401 104 records). The dump contained all public bookmarks and publication posts of BibSonomy until (but not including) 2009-01-01. Posts from the user dblp (a mirror of the DBLP Computer Science Bibliography) as well as all posts from users which have been flagged as spammers have been excluded. Furthermore, the tags were cleaned. Java method was used to remove all characters which were neither numbers nor letters and removed those tags, which were empty after cleansing or matched one of the tags imported, public, systemimported, nn, systemunfiled.
The tas table (Tag Assignments) was a fact table with information about who attached which tag to which resource/content. The bookmark table consisted of following columns (content_id, url_hash, url, description, extended description and date). The bibtex table was described by following dimensions (content_id, journal, volume, chapter, edition, month, day, booktitle, howPublished, institution, organization, publisher, address, school, series, bibteXKey, url, type, description, annote, note, pages, key, number, crossref, misc, bibtexAbstract, simhash0, simhash1, simhash2, entrytype, title, author, edition, year). 4
In this section we describe three main parts of our system. Firstly we focus on a selection of RSS feeds and the problems we encountered while downloading the posts. In the second part we define the vector space in which the posts were stored as well as main characteristics of deployed database. Finally we present the details of the tag recommendation algorithm. The algorithm is divided into four steps: searching of matching resources based on URL address, retrieval of the most similar cluster, selection of the post with highest overlap score and ranking of suggested tags. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Tag design blog tools software webdesign programming tutorial art reference video inspiration music web2.0 education photography 1.69% 1.29% 1.05% 0.96% 0.92% 0.89% 0.85% 0.75% 0.72% 0.72% 0.71% 0.66% 0.65% 0.63% 0.52% 27 13 10 54 4 5 44 83 33 3 25 7 17 587 166 4.1
Our strategy was to optimize a set of keywords that we were going to track in popular bookmarking systems as well as in a variety of domain portals. We analyzed distribution of most common tags in BibSonomy and Delicious and decided that tracking only the most recent posts would be biased (Table 1). We decided to enrich the most recent posts with a set of 100 most popular tags (out of 93 757 unique tags) in BibSonomy training data.
We had to face different problems in case of bookmarking systems and domain portals. We used Google Reader to search for top 10 domain portals and their RSS URLs for each chosen keyword. Because some feeds appeared in different searching results we end up with 734 feeds.
An example of feeds recommended by Google Reader for a keyword “linux” is presented in Table 2. Even though numerous feeds use the most recent RSS or Atom standard and we could easily parse the content of XML files, it is uncommon to fill in the category field by feed editors. We can see in the Table 2, that out of 10 sources: one did not contain proper URL, four did not deliver information about category, one marked each feed entry with the same category. 1 Relative frequency of a tag in a random collection of 603 750 downloaded from the Delicious. 2 Rank of a corresponding tag in the BibSonomy. On the other hand the problem with typical bookmarking systems is the fact that when we subscribe most recent posts for a given keyword we get only tags of a particular user who bookmarked the resource. As a consequence we need to crawl a service in order to find out about most typical tags for a given resource. The problem of 3 http://www.linuxinsider.com/perl/syndication/rssfull.pl 4 http://www.linux-mag.com/cache/rss20.xml 5 http://distrowatch.com/news/dw.xml 6 http://linuxtoday.com/backend/biglt.rss 7 http://rss.slashdot.org/Slashdot/slashdotLinux 8 http://www.linux.com/index.rss 9 http://www.howtoforge.com/node/feed 10 http://rssnewsapps.ziffdavis.com/eweeklinux.xml 11 http://www.linuxquestions.org/syndicate/lqlatest.xml 12 http://lxer.com/module/newswire/headlines.rss connection limits arises when we want to crawl every out of 100 entries downloaded for a given keyword. Because of this, we decided to verify if we can cluster tags based on their cooccurence score.
Table 3 contains 20 pairs of tags with highest symmetric Jaccard cooccurance
coefficient calculated as a division of number of posts with both tags by a number of
all posts with any of the tags.
We can see that “ccp” and “jrr” always appear together. Also “genetic”, “algorithms”
and “programming” create a cloud of tags. Four tags “emulationgames”,
“emulationvideogames”, “aaaemulationgames”, “classicemulatedremakeretrogames”
create another cloud. However, the Jaccard coefficient drops very fast below 20%
level and therefore we decided not to abandon the idea of tag clustering.
In order to recommend tags online we needed a fast engine that does not need to be
taught every time we get need posts from a scratch. The Beatca system (developed in
our Institute [
Each post is defined as a point in a multidimensional space in which coordinates represent frequency of a token appearing in a post’s title or description. Because some tokens are very common and others are present in only few posts we selected only the most informative tokens as coordinates in our vector space. The dictionary optimization was based on a entropy-like quality measure Q(ti) of a token ti: (1) where Nij is the number of occurrences of term ti in document dj, Nj is the number of documents that contains term ti and N is the total number of documents. We removed tokens with Q(ti) measure below 0.01 or above 0.95.
We implemented term frequency inverse document frequency weighting scheme. According to the scheme we divided term frequency in a single document by the number of documents in which the term appears. 4.3
Our tag recommendation consisted of four steps. If we had a positive result in the first step then we went directly to the final fourth step.
In the first step we checked if a post is present in the BibSonomy training set or an URL of the post is among downloaded RSS entries. If the answer was true then we selected all tags attached to these resources and moved to the Step Four. In the second step we retrieved a group (cluster) of documents that was the most similar to the post’s description or title field. The similarity was measured as a cosine of an angel between vectors x={x1,…,xn} and y={y1,…,yn} representing the resources in our database and the post (Eq. 2). For example, one of the posts had following title: “Attribute Grammar Based Programming and its Environment”. The query consisting of the first five informative tokens from the above title returned a cluster of four documents: 1. “A purely functional high order attribute grammar based system” from
Deliciuos.com; tagged with [lisp;rag;compilers] 2. “AspectAG 0.1.1 strong typed attribute grammar implemented using type-level programming” from Reedit.com; tagged with [haskell] 3. “A 2D game programming environment based around the Ruby programming language” from Dzone.com; tagged with [frameworks,games,ruby] 4. “Attribute grammar based language extension for Java” from CiteULike.org tagged with [metaprogramming] (2) A cluster of all the retrieved posts was transferred to the next step.
For all the posts retrieved in the second step we calculated normalized overlap score and chosen the post with the highest score. The overlap was defined as a maximum length of n-gram appearing in both posts. In order to compute the score we used all the words from title/description fields (not only the most informative tokens). The overlap score was divided by the length of title/description field of the candidate posts. For example, normalized overlap score between “Attribute Grammar Based Programming and its Environment” and “Attribute grammar based language extension for Java” equals to 3/7=0.42. The post with highest score was transferred to the final fourth step if the value of a score was greater than 0.6 threshold.
5
In the last step we ordered the tags of selected post according to their count in
BibSonomy training set. Top five tags were selected as predictions in the Challenge.
The F1-Measure common in Information Retrieval was used to evaluate the
recommendations. The precision and recall were first computed for each post in the
test data by comparing the recommended tags against the tags the user has originally
assigned to this post [
We must admit that the way we approached the problem needs substantial computing power and disc space. Unfortunately the quality of our tag recommendations was below an average and probably this direction of research in the field of tag recommending systems is not a promising one. However we believe that there are certain situations in which best tags are not a function of words contained in title of a post and in our future research we would like to focus on such examples. Despite of unsatisfactory result in the first Task of ECML PKDD 2009 Challenge we are going to verify our recommendations within the third online recommendation task.