Recursive Nearest Neighbor Graph Partitioning for Extreme Multi-Label Learning

Yukihiro TAGAMI  

IEICE TRANSACTIONS on Information and Systems   Vol.E102-D   No.3   pp.579-587
Publication Date: 2019/03/01
Publicized: 2018/11/30
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2018EDP7106
Type of Manuscript: PAPER
Category: Artificial Intelligence, Data Mining
extreme multi-label classification,  k-nearest neighbor graph,  tree-based classifier,  

Full Text: PDF(496.5KB)>>
Buy this Article

As the data size of Web-related multi-label classification problems continues to increase, the label space has also grown extremely large. For example, the number of labels appearing in Web page tagging and E-commerce recommendation tasks reaches hundreds of thousands or even millions. In this paper, we propose a graph partitioning tree (GPT), which is a novel approach for extreme multi-label learning. At an internal node of the tree, the GPT learns a linear separator to partition a feature space, considering approximate k-nearest neighbor graph of the label vectors. We also developed a simple sequential optimization procedure for learning the linear binary classifiers. Extensive experiments on large-scale real-world data sets showed that our method achieves better prediction accuracy than state-of-the-art tree-based methods, while maintaining fast prediction.