Extreme multi-label classification aims to learn a classifier that annotates an instance with a relevant subset of labels from an extremely large label set. Many existing solutions embed the label matrix to a low-dimensional linear subspace, or examine the relevance of a test instance to every label via a linear scan. In practice, however, those approaches can be computationally exorbitant. To alleviate this drawback, we propose a Block-wise Partitioning (BP) pretreatment that divides all instances into disjoint clusters, to each of which the most frequently tagged label subset is attached. One multi-label classifier is trained on one pair of instance and label clusters, and the label set of a test instance is predicted by first delivering it to the most appropriate instance cluster. Experiments on benchmark multi-label data sets reveal that BP pretreatment significantly reduces prediction time, and retains almost the same level of prediction accuracy.
@cite_16: This paper presents a novel multi-label classification framework for domains with large numbers of labels. Automatic image annotation is such a domain, as the available semantic concepts are typically hundreds. The proposed framework comprises an initial clustering phase that breaks the original training set into several disjoint clusters of data. It then trains a multi-label classifier from the data of each cluster. Given a new test instance, the framework first finds the nearest cluster and then applies the corresponding model. Empirical results using two clustering algorithms, four multi-label classification algorithms and three image annotation data sets suggest that the proposed approach can improve the performance and reduce the training time of standard multi-label classification algorithms, particularly in the case of large number of labels.
The second method, Clustering Based Multi-Label Classification (CBMLC), groups the training instances into a user-specified number of clusters, and trains a multi-label classification model for each cluster @cite_16 . The testing stage is identical to that of LPSR. There are several differences between CBMLC and our approach. First, our goal is to minimize the prediction time while CBMLC focuses on reducing the training time. Second, we formally form a clustering objective to achieve better prediction time using both features and labels, and expedite prediction by reducing label size, whereas CBMLC only takes features into consideration during the clustering step, and label size remains the same. Furthermore, our number of clusters is not user-specified.