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

• We propose a multiclass-to-binary decomposition strategy founded on Coding Theory.
• We use Low-Density Parity-Check codes, a very effective family of binary block codes.
• Exploiting the algebraic properties of the code, we handle both coding and decoding.
• Two decoding rules are proposed that provide many advantages over known strategies.
• Several experiments are performed that show significant performance improvements.

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.