Recovery degree constrained equiconcept/pseudo-equiconcept reduction in symmetric formal contexts

International Journal of Approximate Reasoning. 2025. Vol. 187. Article 109541.

Junyu B., Fei H., Huilin F., Ling W., Shuanggen L., Kuznetsov S.

In Formal Concept Analysis (FCA), concept reduction serves as an important means of simplification. The application scenarios of concept reduction cover various aspects such as data mining, knowledge discovery, strategic decision-making, and rule learning. For symmetric formal contexts, a specialized class of concept reduction exists that can fully recover all knowledge. However, most existing concept reduction algorithms are designed to recover complete knowledge, which poses limitations in various real-world applications. To this end, this paper proposes a basic recovery degree-constrained equiconcept reduction algorithm, termed RdER, enabling knowledge recovery to a specified extent. Additionally, to reduce its running time, an evolutionary algorithm, termed RdER+, is further developed. Meanwhile, given the simplicity of pseudo-equiconcepts, we also develop a recovery degree-constrained pseudo-equiconcept reduction algorithm, termed RdPR. A large number of experiments have demonstrated that RdER+ and RdPR have significantly reduced the running time while maintaining a relatively low redundancy and ensuring the average recovery degree. Particularly, when the dimension reaches 17, the running speeds of RdER+ and RdPR are, on average, 150 times faster than that of RdER. Moreover, as the dimension continues to increase, this advantage in speed will become even more pronounced.

Keywords: FCA (Formal Concept Analysis), Pseudo-equiconcept reduction, Symmetric formal context, Equiconcept reduction, Recovery degree

Publication based on the results of: Complex language and semantic models in artificial intelligence (2025)