Cybernetics and Information Technologies
Volume 6, No 2. Sofia, 2006, Bulgarian Academy of Sciences

The Two-Group Classification Problem Challenge Polynomial Heuristic Algorithms

Vassil G. Guliashki

Institute of Information Technologies, 1113 Sofia

Abstract: The paper presents a heuristic approach for development of polynomial-time algorithms, solving the two-group classification problem. The proposed algorithm ALS, based on this heuristic approach, has been tested on 200 test problems with 6 attributes and 150 training sample observations (75 per group), and with 10% to 30% overlapping of both groups in the training sample. The obtained results are compared with that one, obtained by means of three other heuristic algorithms, one exact algorithm and one statistical method on the same test problems. The computational complexity of ALS algorithm is very encouraging.

Keywords: Discriminant analysis, two-group classification, polynomial heuristic algorithms.