Social tag prediction

ABSTRACT

In this paper, we look at the "social tag prediction" problem. Given a set of objects, and a set of tags applied to those objects by users, can we predict whether a given tag could/should be applied to a particular object? We investigated this question using one of the largest crawls of the social bookmarking system del.icio.us gathered to date. For URLs in del.icio.us, we predicted tags based on page text, anchor text, surrounding hosts, and other tags applied to the URL. We found an entropy-based metric which captures the generality of a particular tag and informs an analysis of how well that tag can be predicted. We also found that tag-based association rules can produce very high-precision predictions as well as giving deeper understanding into the relationships between tags. Our results have implications for both the study of tagging systems as potential information retrieval tools, and for the design of such systems.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, ACM SIGMOD Record, v.22 n.2, p.207-216, June 1, 1993
• 2: M. Aurnhammer, P. Hanappe, and L. Steels. Integrating Collaborative Tagging and Emergent Semantics for Image Retrieval. Collaborative Web Tagging Workshop (WWW'06).
• 3: Soumen Chakrabarti , Byron Dom , Piotr Indyk, Enhanced hypertext categorization using hyperlinks, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.307-318, June 01-04, 1998, Seattle, Washington, United States
• 4: Ed H. Chi , Todd Mytkowicz, Understanding the efficiency of social tagging systems using information theory, Proceedings of the nineteenth ACM conference on Hypertext and hypermedia, June 19-21, 2008, Pittsburgh, PA, USA [doi>10.1145/1379092.1379110]
• 5: Evgeniy Gabrilovich , Shaul Markovitch, Text categorization with many redundant features: using aggressive feature selection to make SVMs competitive with C4.5, Proceedings of the twenty-first international conference on Machine learning, p.41, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015388]
• 6: Scott A. Golder , Bernardo A. Huberman, Usage patterns of collaborative tagging systems, Journal of Information Science, v.32 n.2, p.198-208, April 2006 [doi>10.1177/0165551506062337]
• 7: Taher H. Haveliwala , Aristides Gionis , Dan Klein , Piotr Indyk, Evaluating strategies for similarity search on the web, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511502]
• 8: Paul Heymann , Georgia Koutrika , Hector Garcia-Molina, Can social bookmarking improve web search?, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA [doi>10.1145/1341531.1341558]
• 9: Thorsten Joachims, A support vector method for multivariate performance measures, Proceedings of the 22nd international conference on Machine learning, p.377-384, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102399]
• 10: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 11: K. Jones and C. van Rijsbergen. Information Retrieval Test Collections. Journal of Documentation, 32(1):59--75, 1976.
• 12: K. Jones and C. van Rijsbergen. Information Retrieval Test Collections. Journal of Documentation, 32(1):59--75, 1976.
• 13: Gilad Mishne, AutoTag: a collaborative approach to automated tag assignment for weblog posts, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135961]
• 14: C. Schmitz, A. Hotho, R. Jaschke, and G. Stumme. Mining Association Rules in Folksonomies. IFCS'06.
• 15: E. Schwarzkopf, D. Heckmann, D. Dengler, and A. Kroner. Mining the Structure of Tag Spaces for User Modeling. Workshop on Data Mining for User Modeling (ICUM'07).
• 16: Shilad Sen , Shyong K. Lam , Al Mamunur Rashid , Dan Cosley , Dan Frankowski , Jeremy Osterhouse , F. Maxwell Harper , John Riedl, tagging, communities, vocabulary, evolution, Proceedings of the 2006 20th anniversary conference on Computer supported cooperative work, November 04-08, 2006, Banff, Alberta, Canada [doi>10.1145/1180875.1180904]
• 17: S. Sood, K. Hammond, S. Owsley, and L. Birnbaum. TagAssist: Automatic Tag Suggestion for Blog Posts. ICWSM'07.
• 18: Z. Xu, Y. Fu, J. Mao, and D. Su. Towards the Semantic Web: Collaborative Tag Suggestions. Collaborative Web Tagging Workshop (WWW'06).
• 19: Yiming Yang , Jan O. Pedersen, A Comparative Study on Feature Selection in Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.412-420, July 08-12, 1997
• 20: Yiming Yang , Seán Slattery , Rayid Ghani, A Study of Approaches to Hypertext Categorization, Journal of Intelligent Information Systems, v.18 n.2-3, p.219-241, March-May 2002 [doi>10.1023/A:1013685612819]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems
          Subjects: Human information processing

General Terms:
Design, Experimentation, Human Factors, Measurement

Keywords:
association rules, collaborative tagging, social bookmarking, text classification