A HEURISTIC ALGORITHM OF EXTENSION MATRIX BASED ON ENTROPY
Qian Guo · Chinese Journal of Computers · 1998
Traditional extension matrix theory and corresponding heuristic algorithms are based on the consistency of positive and negative examples set. However, many overfitting rules will be produced under the noisy data in application to real-world domains. In this paper, from the view of statistics, the basic definitions of extension matrix theory are extended and a rule description method based on probability is given. In which, the conception induced from the training examples can classify the training examples with a high correct probability (maybe not completely correct), and will give a high predictive correct rate for new examples. The information-theoretic entropy measure and Laplace error rate evaluation functions are applied to the path search in extension matrix, and a heuristic algorithm ECA based on entropy is presented. ECA is also applied to several real-world domains such as sleep examples and handwritten digit recognition, and is compared with AE5 and AQ15. The experimental results show that ECA can produce more simple and efficient rules, and can solve the noisy problem in practical application effectively.