A Graph-based Method For Attribute Reduction Of Concept Lattices And Its Application

As a useful mathematical tool for data analysis and knowledge discovery,concept lattice theory provides powerful techniques and methods for artificial intelligence.Attribute reduction is one of the hot issues in the research and application of concept lattice theory.However,many traditional attribute reduction methods have high time or space complexity and cannot effectively deal with the large-scale data set.For this reason,this thesis uses graph theory to study the granular reduction and the attribute reduction of formal decision contexts.We also design some effective algorithms for the large-scale data set.Finally,we further expand the application field of attribute reduction of concept lattices and discuss its application in the finite topological space.The main contents of this thesis are as follows:1?The equivalent characterization of the granular reduction problem based on graph theory is given for formal contexts.The relationship between the granular reduction in formal contexts and the minimal vertex cover of the corresponding graph is established.A graph-based granular reduction algorithm is formulated.At the same time,to overcome the limitation of the high space complexity,a local graph representation of the granular reduction in formal contexts is introduced.To obtain much smaller reduction,two effective local reduction algorithms are proposed.Finally,the effectiveness of the proposed method is verified by numerical experiments.2? The corresponding partial graph is derived when the formal decision context is regarded as a special union of formal contexts.Then the granular reduction problem of formal decision contexts is transformed into the vertex cover problem of its partial graph.Using the improved vertex cover method,a granular reduction algorithm based on graph theory is presented.To overcome the limitation of this algorithm in the face of largesample data,a local graph representation of the reduction problem in formal decision contexts is introduced,and a local granular reduction algorithm is presented.Finally,numerical experiments are used to examine the effectiveness of the proposed algorithm in terms of the storage space,granular reduction set and running time.3?The problem of attribute reduction in strong consistent formal decision contexts is discussed and two methods of simplifying discernibility matrix are proposed.Both methods avoid the construction of concept lattices.They not only need less storage space,but also have lower time complexity.Based on these two discernibility matrices,the graph representation and corresponding attribute reduction algorithms are given.Finally,the effectiveness of the proposed algorithm is verified by the large-scale data set.4?The minimal subbase problem in finite topological space is studied by using the attribute reduction method of strong formal decision contexts.By discussing the relationship between the minimal bases and minimal subbases of two types of topological spaces(I-type and II-type),the minimal subbase problem in II-type topological spaces is transformed into the minimal subbase problem in I-type topological spaces.The minimal base of the I-type topological space is then used to construct a special formal decision context,and the minimal subbase problem is thus transformed into the attribute reduction problem.On this basis,using the attribute reduction method of concept lattices,the method for finding the minimal subbases is given.We also verify the validity and scalability of the algorithm through large-scale data sets.