Research On Formal Concept Analysis Methods And Applications Based On Topology Of Attribute Set

Formal concept analysis is a powerful tool for data analysis and knowledge acquisition in formal context proposed by German mathematician professor Wille in 1982.Nowadays,formal concept analysis has been widely used in information retrieval,knowledge mining,knowledge reasoning and many other fields.In formal concept analysis,the construction and application of concept lattices are always two important research directions.Based on high time complexity existing in the construction of concept lattices,this dissertation focuses on the study of formal concept analysis methods and applications based on the topological basis of attribute sets,aiming at reducing the concept enumeration space.This dissertation studies the construction of concept lattice based on attribute topology basis,frequent closed itemsets mining and min-max association rule mining based on attribute topology,object(attributes)oriented concept lattice rule extraction and attribute reduction,and the application of the concept lattice in the social network for mining k-equiconcept.The details are as follows:1.Mining frequent closed itemsets and mining mini-max association rules.Frequent closed itemsets are intents of concepts in concept lattices.Frequent closed itemsets and association rules mining based on concept lattices is an important research direction of formal concept analysis.Due to high time complexity of frequent closed itemsets mining,a method of frequent closed itemset mining based on topological basis of attribute sets is proposed.The existing algorithms enumerate frequently closed itemsets with items(attributes),with large enumeration space of frequent closed itemset.A TT-tree search space is constructed based on the properties of topological basis.Based on this space,both transaction space and attribute space can be searched simultaneously.And the space is smaller than the search space of the existing algorithm.The TT-Miner algorithm for frequent closed itemsets mining based on attribute topological basis is proposed.By adding attribute topological basis to existing frequent closed itemsets,frequent closed itemsets are enumerated.Compared with the traditional method of adding attribute,the algorithm proposed in this dissertation has higher generation efficiency.A new fast mining method based on TTTree for min-max association rules is proposed.2.The construction of concept lattice.How to construct the search space of concept for reducing the generation of repeated concepts is the key to construct efficient concept lattice generation algorithm.In this dissertation,the author discuss the relationship between the order of attributes and the size of the search space in the generation of concept lattice.Based on the properties of topological basis of attributes,arranging attributes in descending order of the cardinal number of topological basis can effectively reduce the search space of concepts and reduce the generation of repeated concepts.The algorithm for generating topological basis of attributes and the order mapping function on attribute set are given,and then the concept lattice generation method based on topological basis of attributes is proposed and the generation algorithm is designed.The experimental results show that the concept generation efficiency is higher than the existing algorithms.3.Decision rule acquisition and attribute reduction of object(attribute)oriented concept lattices.Based on the formal concept of object(attribute)oriented,the definition of object(attribute)oriented decision rules is proposed.In this study,the equivalence relation of conditional attribute concept lattice and decision attribute concept is constructed.By means of equivalent relation,the method of acquisition object(attribute)oriented decision rules is proposed.In this study,the definition of formal decision background attribute reduction with object(attribute)oriented decision rules is proposed,and a discriminant function is constructed based on the discriminant attributes of related concepts.4.Mining equiconcept in social networks based concept lattice.Social network is a special formal background with symmetrical structure in which both object set and attribute set are node set.This dissertation analyzes the shortcomings of the equiconcept generation method based on concept lattice construction in terms of efficiency.A new pruning strategy is proposed based on the properties of the equiconcept,and then a fast generating method of k-equiconcept in the social network is proposed.Experiments show that the generation speed of the equiconcept is much faster than that of the existing algorithms.To sum up,the formal concept analysis method based on topological basis of attributes has been deeply studied in this dissertation,and some research results have been obtained.These achievements have good prospects in the construction of concept lattices and the application of formal concept analysis.