Exploiting coding theory for classification: An LDPC-based strategy for multiclass-to-binary decomposition

A powerful strategy for the classification of multiple classes is to create a classifier ensemble that decomposes the polychotomy into several dichotomies. The central issue when designing a multiclass-to-binary decomposition scheme is the definition of both the coding matrix and the decoding algorithm. In this study, we propose a new classification system based on low-density parity-check codes, which is a very effective class of binary block codes. The main idea is to exploit the algebraic properties of the codes to generate the codewords for the coding matrix and to define two decoding approaches, which allow us to detect and recover possible errors or rejects produced by the dichotomizers. Experiments based on benchmark datasets demonstrated that the proposed approach provides a statistically significant improvement in terms of the classification performance compared with state-of-the-art decomposition strategies.