Improving multiclass classification using neighborhood search in error correcting output codes

Error Correcting Output Code (ECOC) is an effective approach for multiclass classification problems. This method decomposes a multiclass problem to many binary sub-problems and makes a dichotomizer for each sub-problem. It then tries to classify samples by combining outputs of all dichotomizers. One of the main points in ECOC method is to construct an ensemble of independent binary classifiers. Many studies have been conducted to design an optimal ECOC matrix. However, most of these methods aim to construct an ECOC code Matrix without considering the relations between data to design an ensemble of binary classifiers. In this study, a new method is presented based on ECOC which improves the performance of sparse ECOC by considering the neighborhood of samples. The proposed method is evaluated using 16 UCI datasets. The results indicate that our method not only significantly improves the classification accuracy compared to other commonly used ECOC based methods, but it also can result in a lower number of classifiers in comparison with random dense ECOC with the same accuracy.