Research On Parallel Knowledge Discovery Algorithm Based On The Theory Of Formal Concept Analysis

Formal concept analysis is one of effective methods for knowledge representation and data mining. Concept lattice is the core data structure of the formal concept analysis,which can be used easily to establish causal relationships among information. Knowledge contained in the formal context is described concisely by concept lattice. Attribute reduction and association rule extraction are two important problems studied in the formal concept analysis.Attribute reduction can simplify the formal context and the concept lattice structure, which is advantageous to the discovery of important knowledge. Moreover, it is easy to find the association between the attributes of transactions based concept lattice so as to mining interesting rules. In the big data environment,it highlights the importance of parallel knowledge discovering algorithms in order to discover important knowledge used to guide applications in real-life. In this dissertation, studies are carried out on the parallel algorithms in attributes reduction, concept lattice construction, and association rules mining. The main research work and innovation are summarized as follows.1. A parallel concept generation algorithm is presented. We adopt the idea of divide and conquer so as to reduce attributes in parallel environment by dividing the discernibility matrix to some sub-discernibility matrix. Discemibility function of each sub-matrix is calculated firstly, and consequently the discernibility function of discernibility matrix is obtained.Experiments are carried out on several datasets which show that the algorithm is effective when dealing with big data.2. A parallel concept lattice construction algorithm based on the method of the concept partition is presented. Three types of concept partition methods are employed and analyzed,which is the extent cardinality partition, the intent cardinality partition, and a hybrid partition in both extent cardinality and intent cardinality. The purpose of the partition policy is to restrain the search scope when establishing parent-children relationships among concepts.Experimental results show that the hybrid partition in both extent cardinality and intent cardinality policy can improve the efficiency of lattice-construction. It concludes that proposed parallel algorithm for constructing concept lattice has a good performance.3. A parallel algorithm for mining association rules based on formal concept analysis is designed. The definition of rule concept lattice is presented firstly. Each node of rule concept lattice is consisted of the concept, cardinality of the child concept, and connotation. Rules with different parameters can be extracted from rule lattice in different turn. Experimental results show the proposed algorithm for extracting association rules has good performance in speed-up.4. A knowledge discovery system based on the formal concept analysis theory is constructed,in which the proposed attributes reduction, concept lattice construction and algorithm for mining association rules are integrated. Moreover, algorithms of traditional attributes reduction, concept lattice construction and association rules mining are integrated in the system so as to process small data sets and compare the results of the parallel algorithm with that of the serial algorithms. The results of attributes reduction, Hasse diagrams, and the results of association rules exacted may be displayed with good interactivity and practical value.