Binary Decomposition for Multi-Class Classification Problems: Development and Applications

Binary decomposition of a multi-class classification problem is a widely used method in the field of machine learning, which involves using an ensemble of binary classifiers to undertake multi-class classification tasks. The motivation of binary decomposition lies in two main aspects. Firstly, some learning algorithms such as support vector machine can not achieve directly learning a multi-class classifier. Secondly, in some cases, the adoption of binary decomposition for training an ensemble of binary classifiers can even achieve better performance than the direct learning of a multi-class classifier. There are some existing methods that can be applied in achieving binary decomposition and have been proven to be effective. Some of these methods may also be applied in other tasks beyond classification. This paper presents a comprehensive review of the development and applications of binary decomposition methods. Specifically, these methods are put into two categories, namely, ordered and unordered decomposition, which each is introduced in terms of the essence and strategies of decomposition. These methods are also compared through theoretical analysis of their effectiveness and efficiency. On the basis of the comparative analysis, we suggest some future directions towards achieving further advances in binary decomposition.