Research On Knowledge Discovery Based On Concept Lattice Model

This paper mainly focuses on knowledge discovery based on concept lattice, and extended concept lattice model. The main research work is to make use of concept lattice structure to solve the problem of mining association rules, classification rules, and functional dependencies from data. This paper also studies in detail the problem of building concept lattice, and two efficient algorithms are developed. Moreover, several extended model of concept lattice are presented to handle the problems in data processing, such as the missing value and the structured domain of attribute.The detail results follow:1)Based on the existing algorithms, we analyze the incremental procedure and the batch procedure for building concept lattice, and present two efficient algorithms, one is incremental, the other batch. The incremental algorithm use a tree structure to organize the set of concept nodes, and decrease the time needed to build concept lattice. The batch algorithm in this paper reduces the redundant computation in each node for generating its children by the presented definition of expansion-equivalence class, thereby improves the algorithm抯 efficiency. Experimental results manifest that the incremental algorithm in this paper is rather faster than the well-known Godin抯 algorithm.2)Based on the invariability (or approximate invariability) of function value, we give out the definitions of intent reduct (or approximate intent reduct) and intent core (or approximate intent core) of concept node, investigate their properties in detail, and prove that the problems of computing them can be transformed into the problem of computing the minimal cover of a family of sets. For the computation of the minimal covers of a family of sets, we propose several theorems to describe the principle, and develop corresponding algorithm elaborately.3)To discover association rules, we present a framework based on concept lattice. First, in the light of the requirement of mining association rules, the structure of concept node is simplified, and the corresponding building algorithm is developed. Then we give out the algorithms for extracting association rules from the lattice based on intent reduct, where two properties are exploited to remove the redundant rules. However, transaction database is sometimes not a simple set of transactions, there may exist some relation (such as timesequencing) between different transactions. To handle the timesequenceing betweenIIItransactions, we define interval base concept lattice as an extension to classical concept lattice. The interval base concept lattice can be used to discover tiniesequencing association rules, which is useful in prediction.4)To classify new objects with concept lattice structure, we develop two classification systems, LACS and LACS-2. In LACS, considering the characteristics of classification, we suggest two pruning strategies to confine the generation of concept nodes in the procedure of building concept lattice so that the number of nodes generated decreases greatly. The experimental results on MONK datasets manifest that the classification accuracy of LACS is much better than other well-known classification systems (such as 1D3, C4.5 and CN2). Based on LACS, we also develop LACS-2, which builds one concept lattice for each decision class, then classifies new objects by using all the constructed concept lattices. The classification strategy used in LACS-2 is rather flexible, which can solve successfully some problems that cannot be solved in LACS.5)By using non-order pair as the basic element, we give out the definitions of discernibility system and the indiscernibility context. Discernibility system can be used to unify the problems of computing reduct set in information system and computing relative reduct set in decision table. The indiscernibility lattice corresponding to indiscernibility context can be used to computing the reduct set of any subset of attributes in information system, and thus can serve as a framew...