A graph approach for knowledge reduction in formal contexts

摘要

Knowledge reduction in formal concept analysis (FCA) is an important procedure for knowledge processing and data analysis. Currently, the knowledge reduction in FCA based on granular computing (GrC) provides another way to analyze and represent the structure of concept lattices. However, the granular reduction method is based on Boolean reasoning and thus is an NP-hard problem. It is therefore natural to develop some heuristic methods to deal with this problem especially for the large data. In this paper, a new framework based on graph theory is used to study the granular reduction in FCA. A graph representation for the granular reduction is first investigated. The results in this paper show that the granular reduction computation in FCA can be translated into a graph optimization problem. Two new heuristic graph-based algorithms for the granular reduction in formal contexts and formal decision contexts are then respectively presented. Furthermore, numerical experiments are conducted to evaluate the effectiveness of the proposed methods.