
Prikl. Diskr. Mat., 2019, Number 44, Pages 113–126
(Mi pdm665)




This article is cited in 1 scientific paper (total in 1 paper)
Computational Methods in Discrete Mathematics
Decompositional approach to research of formal contexts
V. V. Bykova^{a}, Ch. M. Mongush^{b} ^{a} Siberian Federal University, Krasnoyarsk, Russia
^{b} Tuvan State University, Kyzyl, Tuva, Russia
Abstract:
The problem of finding all formal concepts of a given formal context is investigated. The problem arises when data mining is presented in the form of a binary objectattribute matrix, i.e. a matrix the rows of which correspond to objects, and the columns correspond to features that take a value from the twoelement set $\{0, 1\}$. Here the value $1$ of the element of a matrix is interpreted as the presence of corresponding attribute to the object, and 0 is as its absence. Such a representation of a set of data allows to be used the algebraic approach of R. Wille and B. Ganter, known in the literature as Formal Concept Analysis. Within of this approach the initial objectattribute matrix is called the formal context, and any of its maximal full submatrix is a formal concept. In the problem of finding all formal concepts, it is required to find the set of all formal concepts for a given formal context. This problem belongs to combinatorial enumeration problems and is $#$Pcomplete. The high computational complexity of the problem is due to the fact that in the general case the number of formal concepts exponentially depends on the size of the initial formal context. Currently many algorithms have been developed to solve the problem, among them NextClosure, ClosebyOne, Norri. The execution time of these algorithms in the worst case exponentially depends on the dimension of the initial context, and therefore they are unsuitable for practical analysis of contexts of large dimension. We propose a decomposition method for solving the problem under consideration. In this method, some fragments of the initial context defined in a certain constructive way are called boxes. We prove that the division of context into boxes is “safety” relatively of the formal concepts. This means that the formal concepts are not lost and new formal concepts do not arise at decomposition. We prove that the number of boxes arising at each iteration of the decomposition is equal to the number of unit elements of the $0,1$matrix representing the initial formal context. We show how a partial order relation can be defined on a set of boxes. We also show that the number of boxes at each separate iteration of the decomposition process can be reduced by using constructing mutually disjoint chains of boxes. The results of computational experiments are given, indicating that the application of the proposed decomposition method allows significantly to increase the performance of algorithms for finding all formal concepts of a given context.
Keywords:
formal concept analysis, formal context decomposition.
DOI:
https://doi.org/10.17223/20710410/44/9
Full text:
PDF file (659 kB)
References:
PDF file
HTML file
Bibliographic databases:
UDC:
519.7
Citation:
V. V. Bykova, Ch. M. Mongush, “Decompositional approach to research of formal contexts”, Prikl. Diskr. Mat., 2019, no. 44, 113–126
Citation in format AMSBIB
\Bibitem{BykMon19}
\by V.~V.~Bykova, Ch.~M.~Mongush
\paper Decompositional approach to research of~formal~contexts
\jour Prikl. Diskr. Mat.
\yr 2019
\issue 44
\pages 113126
\mathnet{http://mi.mathnet.ru/pdm665}
\crossref{https://doi.org/10.17223/20710410/44/9}
\elib{https://elibrary.ru/item.asp?id=38555966}
Linking options:
http://mi.mathnet.ru/eng/pdm665 http://mi.mathnet.ru/eng/pdm/y2019/i2/p113
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
This publication is cited in the following articles:

Ch. M. Mongush, “Algoritm «bezopasnoi» dekompozitsii formalnogo konteksta”, PDM. Prilozhenie, 2019, no. 12, 227–232

Number of views: 
This page:  206  Full text:  58  References:  37 
