A supervised learning approach to detect subsumption relations between tags in folksonomies

The lack of hierarchical relations in the tag space of social tagging systems may diminish the ability of users to find relevant resources. Many research works propose to overcome this problem by constructing hierarchies of tags automatically by means of heuristic algorithms. These hierarchies encode subsumption relations between pairs of tags and can be used for improving browsing and retrieval of resources. In this paper, we cast the problem of subsumption detection between pairs of tags as a pairwise classification problem. From the literature, we identified several similarity measures that are good indicators of subsumption, which are used as learning features. Under this setting, we observed severe class imbalance and class overlapping which motivated us to investigate and employ class imbalance techniques to overcome these problems. We conducted a comprehensive set of experiments on a large real-world dataset, showing that our approach outperforms the best performing heuristic-based baseline.