Explore the Structure of Social Tags by Subsumption Relations

Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 1011–1019, Beijing, August 2010 Explore the Structure of Social Tags by Subsumption Relations Xiance Si, Zhiyuan Liu, Maosong Sun Department of Computer Science and Technology State Key Lab on Intelligent Technology and Systems National Lab for Information Science and Technology Tsinghua University {sixiance,lzy.thu}@gmail.com, sms@tsinghua.edu.cn Abstract Thanks to its simplicity, social tagging system has accumulated huge amount of user contributed tags. However, user contributed tags lack explicit hierarchi- cal structure, while many tag-based ap- plications would benefit if such a struc- ture presents. In this work, we explore the structure of tags with a directed and easy-to-evaluate relation, named as the subsumption relation. We propose three methods to discover the subsumption rela- tion between tags. Specifically, the tagged document’s content is used to find the re- lations, which leads to better result. Be- sides relation discovery, we also propose a greedy algorithm to eliminate the re- dundant relations by constructing a Lay- ered Directed Acyclic Graph (Layered- DAG) of tags. We perform quantita- tive evaluations on two real world data sets. The results show that our methods outperform hierarchical clustering-based approach. Empirical study of the con- structed Layered-DAG and error analysis are also provided. 1 Introduction In this work, we aim at exploring the structure of social tags. Social tagging is widely used in Web- based services, in which a user could use any word to annotate an object. Thanks to its simplicity, ser- vices with social tagging features have attracted a lot of users and have accumulated huge amount of annotations. However, comparing to taxonomies, social tagging has an inherent shortcoming, that Figure 1: Examples of (a) flat tag cloud, (b) hier- archical clusters, and (c) subsumption relations. there is no explicit hierarchical relations between tags. Figure 1 (a) shows an example of the com- monly used flat tag cloud, in which only the pop- ularity of a tag is concerned. Kome et al. (2005) argued that implicit hierarchical relations exist in social tags. Previous literature shows that orga- nizing tags in hierarchical structures will help tag- based Information Retrieval applications (Begel- man et al., 2006; Brooks and Montanez, 2006). Hierarchical clustering could reveal the simi- larity relations of tags. Figure 1 (b) shows an example of a typical hierarchical clustering of tags. While clusters can capture similarity be- tween tags, problems still remain: First, clusters mix different relations, such as synonyms and hy- pernyms. Second, clusters also ignore the direc- tion of relations, for example, the direction in browser → firefox. Third, it is hard to evalu- ate the correctness of clustering. Specifically, it is hard to tell if two tags are similar or not. In practice, directed and easy-to-evaluate relations between tags are preferred, such as Figure 1 (c). In this work, we explore the structure of so- cial tags by discovering a directed and easy-to- evaluate relation between tags, named subsump- tion relation. A tag ta subsumes tb, if and only if wherever tb is …

Content truncated to 500 words