Title :
Information-based algorithm for reduction of knowledge
Author :
Duoqian, Miao ; Jue, Wang
Author_Institution :
Inst. of Autom., Acad. Sinica, Beijing, China
Abstract :
In Rough Set (RS) theory, it has been proved that finding the minimal reduct of an information system is an NP-complete problem. Because of this, it is hard to obtain the set of the most concise rules by existing algorithm in RS for reduction of knowledge. In this paper, an information-based algorithm for reduction of knowledge is proposed, and its time complexity is analyzed. Through an example, we show that the proposed algorithm is effective for dealing with relatively large-scale databases
Keywords :
computational complexity; database management systems; knowledge based systems; NP-complete problem; information system; information-based algorithm; knowledge reduction; large-scale databases; rough set theory; time complexity; Algorithm design and analysis; Automation; Databases; Entropy; Information analysis; Information systems; Large-scale systems; NP-complete problem; Probability distribution; Random variables; Tiles; Uncertainty;
Conference_Titel :
Intelligent Processing Systems, 1997. ICIPS '97. 1997 IEEE International Conference on
Conference_Location :
Beijing
Print_ISBN :
0-7803-4253-4
DOI :
10.1109/ICIPS.1997.669168
