Generating synthetic test matrices as a benchmark for the computational behavior of typical testor-finding algorithms

• Published in: Pattern recognition letters 2016-09, Vol.80, p.46-51
• Main Authors: Alba-Cabrera, Eduardo, Godoy-Calderon, Salvador, Ibarra-Fiallo, Julio
• Format: Article
• Language: English
• Subjects: Feature selection; Testor theory; Typical testor algorithms
• ISSN: 0167-8655; 1872-7344
• DOI: 10.1016/j.patrec.2016.04.020

•An algebra of basic matrices with typical testors known beforehand is proposed.•Three previous algorithms (BT, LEX and FastCTExt) are tested and analyzed.•Unconventional computational behavior of well-known algorithms is shown.•A new section highlighting a practical strategy was added as suggested by reviewers. Each typical testor-finding algorithm has a specific sensibility towards the number of rows, columns or typical testors within its input matrix. In this research a theoretical framework and a practical strategy for designing test matrices for typical testor-finding algorithms is presented. The core of the theoretical framework consists on a set of operators that allow the generation of basic matrices with controlled dimensions and for which the total number of typical testors is known in advance. After presenting the required theoretical foundation, and the logic for measuring a testor-finding algorithm’s computational behavior, the proposed strategy is used to assess the behavior of three well-known algorithms: BT, LEX, and FastCTExt. Unexpected behaviors, observed during the test experiments, are analyzed and discussed, revealing previously unknown characterizations of the tested algorithms that neither a complexity analysis, nor a random experimentation protocol could have revealed beforehand.