Metric learning-guided k nearest neighbor multilabel classifier

Multilabel classification deals with the problem where each instance belongs to multiple labels simultaneously. The algorithm based on large margin loss with k nearest neighbor constraints (LM-kNN) is one of the most prominent multilabel classification algorithms. However, due to the use of square hinge loss, LM-kNN needs to iteratively solve a constrained quadratic programming at a high computational cost. To address this issue, we propose a novel metric learning-guided k nearest neighbor approach (MLG-kNN) for multilabel classification. Specifically, we first transform the original instance into the label space by least square regression. Then, we learn a metric matrix in the label space, which makes the predictions of an instance in the learned metric space close to its true class values while far away from others. Since our MLG-kNN can be formulated as an unconstrained strictly (geodesically) convex optimization problem and yield a closed-form solution, the computational complexity is reduced. An analysis of generalization error bound indicates that our MLG-kNN converges to the optimal solutions. Experimental results verify that the proposed approach is more effective than the existing ones for multilabel classification across many benchmark datasets.