RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Prikl. Diskr. Mat.: Year: Volume: Issue: Page: Find

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

Computational Methods in Discrete Mathematics

Decompositional approach to research of formal contexts

V. V. Bykovaa, Ch. M. Mongushb

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 object-attribute matrix, i.e. a matrix the rows of which correspond to objects, and the columns correspond to features that take a value from the two-element 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 object-attribute 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 $#$P-complete. 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, Close-by-One, 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 113--126 \mathnet{http://mi.mathnet.ru/pdm665} \crossref{https://doi.org/10.17223/20710410/44/9} \elib{https://elibrary.ru/item.asp?id=38555966} 

• http://mi.mathnet.ru/eng/pdm665
• http://mi.mathnet.ru/eng/pdm/y2019/i2/p113

 SHARE:

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:
1. Ch. M. Mongush, “Algoritm «bezopasnoi» dekompozitsii formalnogo konteksta”, PDM. Prilozhenie, 2019, no. 12, 227–232
•  Number of views: This page: 207 Full text: 59 References: 37