Algorithm for fragmentation and defragmentation of formal contexts
Abstract
Algorithm for fragmentation and defragmentation of formal contexts
Incoming article date: 13.10.2023A combinatorial problem - the problem of finding the set of all formal concepts of formal concepts is considered. The computational complexity of the problem is that the number of formal concepts depends exponentially on the size of the initial formal context. in the article to solve this problem, an algorithm for fragmentation and defragmentation of the formal context is given, based on the method of decomposing the formal context into fragments. The essence of the method is that the original formal context is divided into various fragments. The fragments have different sizes and a non-empty intersection. Each fragment is subsequently considered as a formal context and can again be subject to decomposition. As a result, a finite set of fragments is formed. Then formal concepts are found in each fragment and combined to form the desired set of all formal concepts of the formal context. The method is “non-distorting”: when dividing the context into fragments, new formal concepts are not formed and the sought-for concepts are not lost. The results of computational experiments are presented, showing the effectiveness of the developed algorithm.
Keywords: formal concepts analisys, fragmentation algorithm, formal context, object-attribute table, combinatorial problem, the problem of finding the set of all formal concepts