A novel error-correcting output codes based on genetic programming and ternary digit operators

The key to the success of an Error-Correcting Output Code (ECOC) algorithm is the effective codematrix, which represents a set of class reassignment schemes for decomposing a multiclass problem into a set of binary class problems. This paper proposes a new method, which uses Ternary digit Operators based Genetic Programming (GP) to generate effective ECOC codematrix (TOGP-ECOC for short). In our GP, each terminal node stores a ternary digit string, representing a column and a related feature subset; each non-terminal node represents a ternary digit operator, which produces a new column based on its child nodes. In this way, each individual is interpreted as an ECOC codematrix along with a set of corresponding feature subsets, serving the solution for the multiclass classification task. When a new individual is produced, a legality checking process is carried out to verify whether the transformed codematrix follows the ECOC constraints. The illegal one is corrected according to different strategies. Besides, a local optimization algorithm is designed to prune redundant columns and improve the performance of each individual. Our experiments compared TOGP-ECOC with some well known ECOC algorithms on various data sets, and the results confirm the superiority of our algorithm. Our source code is available at: https://github.com/MLDMXM2017/TOGP-ECOC. (c) 2020 Elsevier Ltd. All rights reserved.