A Research On Several Problems Of Attribute Reduction And Knowledge Acquisition In Formal Concept Analysis

Formal concept analysis,also known as concept lattice theory,was introduced by German mathematician Wille in 1982.It is a mathematical theory for expressing and dealing with concepts and concept hierarchies,and an effective mathematical tool for data analysis.Currently formal concept analysis has been successfully applied in various fields such as information retrieval,knowledge discovery,recommender systems,and software engineering.The construction of concept lattices,decision rule acquisition,and formal context attribute approximation are several important research problems in formal concept analysis.However,the theoretical research on formal concept analysis is not yet complete.For example,the complexity of algorithms for rule acquisition and attribute reduction of existing decision rules is high,and most of the attribute reduction algorithms based on decision rules are NP-hard;rule acquisition and attribute reduction methods for OW/OP-decision rules have not been studied;when the formal contexts change,such as multi-granularity formal contexts and dynamic formal contexts,the complexity for constructing Wille concept lattice and OE-concept lattice by traditional methods is high.All these problems limit the application of concept lattice theory in practical problems.In this paper,based on the above problems,the following research results are obtained.(1)Rule acquisition and attribute reduction based on formal decision context.The knowledge of the decision formal context is expressed as the decision rule,and the premise and conclusion of a decision rule are the formal concept of the conditional context and decision context,respectively.Based on WW/OO/PP-decision rules,relevant attribute reduction methods and algorithms have been studied,but these most of proposed algorithms are NP-hard.In this paper,based on a total order relation of attributes,a heuristic attribute reduction method is given by improving the discernibility conditions so that the number of concepts to be differentiated becomes less and thus compressing the size of the discernibility matrix.In addition,for OW/OPdecision rules,we analyze the semantics of non-redundant rules,classify the extents of the premise and conclusion of decision rules,and then give a rule acquisition method and design a corresponding rule acquisition algorithm.Through comparison and analysis,the complexity of the rule acquisition algorithm proposed in this paper is much lower than that of the existing related algorithms.Further,a decision form context attribute reduction method is given based on keeping the non-redundant OW/OP-decision rules.Based on the Wille concept lattice and dual concept lattice,this paper proposes DD/WD/DW-decision rules and gives the semantic interpretation of these decision rules.Based on these three types of decision rules,the extents of premise and conclusion of decision rules are divided into equivalence classes based on the semantics of decision rules,and the non-redundant decision rule acquisition method is obtained based on these equivalence classes.The discernibility conditions and discernibility matrix of concepts are given while keeping the non-redundant decision rules unchanged,the consistent set judgment theorem is proved and attribute reduction method of a formal context is given.(2)Construction method of Wille concept lattice and OE-concept lattice based on multigranularity formal contexts.Based on multi-granularity formal contexts,the transformation mechanism of Wille concepts/OE-concepts when the granularity of attributes changes is studied,and then the Wille concept lattice/OE-concept lattice construction algorithms are given by these transformation mechanisms.Finally,a comparison experiment is conducted.The experimental results show that the time of the OE-concept lattice construction algorithm proposed in this paper is lower than that of the traditional algorithm based on multi-granularity formal contexts.(3)Construction methods of OE-concept lattice in dynamic formal contexts.The dynamic formal context,i.e.,the formal context in which objects or attributes change.For the four cases of formal context,i.e.,object increase,object decrease,attribute increase and attribute decrease,this paper gives the transformation mechanism of OE-concepts in the original formal context into OE-concepts in the changed formal context,and further designs the construction algorithm of OE-concept lattice according to the transformation mechanism of OE-concepts for the two cases of adding attributes and deleting objects.Finally,the effectiveness of our proposed algorithm and its efficiency compared with existing OE-concept lattice construction algorithms are illustrated by experimental analysis.