Multi-label classification with local pairwise and high-order label correlations using graph partitioning[Formula presented]

In multi-label learning problems, the class labels are correlated and the label correlations can be leveraged to improve the predictive performance of a classifier. Methods that consider high-order correlations in the label space, usually do not utilize pairwise correlations. In most of these methods, label correlations are considered as prior knowledge, which can be misleading in problems with noisy or missing labels. In such cases, learning the label correlation as part of the model training task is more effective. In this paper, a rule-based evolutionary multi-label classification method is proposed that incorporates the local label correlations through the high-order label subsets and pairwise dependencies. Graph structures are employed to model the label dependencies and the estimated label similarities are used to obtain more accurate label sets for the classification rules. To refine the high-order label relations, a novel hierarchical density-based clustering method is proposed to obtain a k-way partitioning for the label graphs based on their pairwise correlations. The effectiveness of the proposed method is experimented on multiple benchmark datasets from different domains and compared with several well-known multi-label classification algorithms. The proposed method has shown the highest average rank along multiple metrics and the results are consistently better than or similar to the compared methods with statistical significance.