GENERAL AND INCREMENTAL ALGORITHMS OF RULE EXTRACTION BASED ON CONCEPT LATTICE

Abstract

Many researches have shown that concept lattice (Galois lattice) is an efficient tool for data analysis and rule extraction. It is convenient to model dependence and casualty,and provide a vivid and concise account of the relations among the variables in the universe of discourse.The paper proposes an algorithm that can extract rules from built lattice efficiently.The basic idea is to generate all non redundant rule of each single node by examining the number and content of their parent nodes.If the average number of descriptors of objects is K ,and the average number of parents of objects is d , the time complexity of algorithm is O(K d‖O‖) .When the number of descriptors of node is relatively large,the algorithm is better than the algorithm in Missaoui′s paper(1994) whose time complexity is O(2 K‖O‖ ).In particular when the amount of object is large and the size of conceptual clustering is big,that is ,most of nodes in lattice have relatively few parent nodes,the algorithm shows much better performance.The paper also improves an incremental concept formation algorithm based on concept lattice and applies it to the incremental rule generation.In the process of undating a concept lattice incrementally,the new method to find the parent node of a new node is given.These algorithms have been used in authors' KDD tools system.