Multi-label Classification with a Constrained Minimum Cut Model

Multi-label classification has received more attention recently in the fields of data mining and machine learning. Though many approaches have been proposed, the critical issue of how to combine single labels to form a multi-label remains challenging. In this work, we propose a novel multi-label classification approach that each label is represented by two exclusive events: the label is selected or not selected. Then a weighted graph is used to represent all the events and their correlations. The multi-label learning is transformed into finding a constrained minimum cut of the weighted graph. In the experiments, we compare the proposed approach with the state-of-the-art multi-label classifier ML-KNN, and the results show that the new approach is efficient in terms of all the popular metrics used to evaluate multi-label classification performance.