This paper proposes an efficient method to determine entire reducts of incomplete decision tables according to the relational database approach. In the complex case, this algorithm has exponential computational complexity. However, this algorithm has polynomial computational complexity in the different cases of databases. | Journal of Computer Science and Cybernetics 2023 313 321 DOI no 1813-9663 18680 A NOVEL ALGORITHM FOR FINDING ALL REDUCTS IN THE INCOMPLETE DECISION TABLE PHAM VIET ANH1 2 VU DUC THI3 NGUYEN NGOC CUONG4 1 GraduateUniversity of Science and Technology Vietnam Academy of Science and Technology Ha Noi Viet Nam 2 HaUI Institute of Technology Hanoi University of Industry Ha Noi Viet Nam 3 VNU Information Technology Institute Vietnam National University Ha Noi Viet Nam 4 General Department of Logistics and Engineering Ministry of Public Security Viet Nam Abstract. Attribute reduction or feature selection for decision tables is a fundamental problem of rough set theory. Currently many scientists are interested in and developing these issues. Unfor- tunately most studies focus mainly on the complete decision table. On incomplete decision tables researchers have proposed tolerance relations and designed attribute reduction algorithms based on different measures. However these algorithms only return a reduct and do not preserve information in the decision tables. This paper proposes an efficient method to determine entire reducts of incomplete decision tables according to the relational database approach. In the complex case this algorithm has exponential computational complexity. However this algorithm has polynomial computational complexity in the different cases of databases. Keywords. The reduct Rough set theory Tolerance relation Incomplete decision table. 1. INTRODUCTION Attribute reduction for decision information systems is the process of removing redundant attributes in the condition attribute set without affecting the classification of the objects. Based on the reduct set obtained the rule generation and classification accuracy achieve the highest efficiency. Up to now there have been many research works about attribute reduction algorithms according to rough set theory 13 . However these algorithms only determine a reduct based on an evaluation .
