Document classification is a large body of search, many approaches were proposed for single label and multi-label classification. We focus on the multi-label classification more precisely those methods that transformation multi-label classification into single label classification. In this paper, we propose a novel problem transformation that leverage label dependency. We used Reuters-21578 corpus that is among the most used for text categorization and classification research. Results show that our approach improves the document classification at least by 8% regarding one-vs-all classification.