Prikladnaya Diskretnaya Matematika
General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Prikl. Diskr. Mat.:

Personal entry:
Save password
Forgotten password?

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. 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.


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
\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

Linking options:

    SHARE: FaceBook Twitter Livejournal

    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  mathnet  crossref  elib
  • Прикладная дискретная математика
    Number of views:
    This page:207
    Full text:59

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021