Decompositional approach to research of~formal~contexts

V. V. Bykova ; Ch. M. Mongush

Prikladnaâ diskretnaâ matematika, no. 2 (2019), pp. 113-126.

Résumé

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.

Détail

Keywords: formal concept analysis
Mots-clés : formal context decomposition.

Bibliographie

[1] Birkhoff G., Lattice Theory, AMS, Providence, 1967, 423 pp. | MR | MR | Zbl

[2] Ganter B., Wille R., Formal Concept Analyses: Mathematical Foundations, Springer Science and Business Media, 2012, 314 pp. | MR

[3] Ganter B., Obiedkov S. A., Conceptual Exploration, Springer, Berlin–Heidelberg, 2016, 315 pp. | MR | Zbl

[4] Kuznetsov S. O., Obiedkov S. A., “Comparing Performance of Algorithms for Generating Concept Lattices”, J. Experimental and Theoretical Artificial Intelligence, 14:2 (2002), 189–216 | DOI | Zbl

[5] Simon A. A., “Best-of-Breed approach for designing a fast algorithm for computing fixpoints of Galois Connections”, Inform. Sci., 295:2 (2015), 633–649 | MR | Zbl

[6] Aslanyan L., Alipour D., Heidari M., “Comparative analysis of attack graphs”, Mathem. Problems of Computer Sci., 2013, no. 40, 85–95

[7] Heydari M., Morales L., Shields C. O., Sudborough I. H., “Computing Cross Associations for Attack Graphs and other Applications”, Proc. 40th Ann. Hawaii Intern. Conf. on System Sciences (Big Island, Hawaii, 2007), 270

[8] Li J., Liu G., Li H., Wong L., “Maximal biclique subgraphs and closed pattern pairs of the adjacency matrix: A one-to-one correspondence and mining algorithms”, J. IEEE Trans. Knowledge and Data Engineering, 19 (2007), 1625–1637 | DOI

[9] Bein D., Morales L., Bein W., et al., “Clustering and the biclique partition problem”, Proc. 41st Ann. Hawaii Intern. Conf. on System Sciences (Big Island, Hawaii, 2008), 475–483

[10] Garey M., Johnson D., Computers and Intractability, Freeman and Co, N.Y., 1979, 340 pp. | MR | Zbl

[11] Duginov O. I., “The complexity of the problems of covering a graph with the smallest number of complete bipartite graphs”, Proc. Institute of Mathematics, 22:1 (2014), 51–69 (in Russian) | Zbl

[12] Prisner E., “Bicliques in graphs I: bounds on their number”, Combinatorica, 20 (2000), 109–117 | DOI | MR | Zbl

[13] Wood D. R., “On the maximum number of cliques in a graph”, Graphs and Combinatorics, 2007, no. 23, 1–16 | MR | Zbl

[14] Moon J. W., Moser L., “On cliques in graphs”, J. Mathematics, 1965, no. 3, 23–28 | MR | Zbl

[15] Pottosina S., Pottosin Y., Sedliak B., “Finding maximal complete bipartite subgraphs in a graph”, J. Appl. Math., 1:1 (2008), 75–81 | MR

[16] Vania M. F. Dias, Celina M. H. de Figueiredo, Jayme L. S., “Generating bicliques of a graph in lexicographic order”, Theor. Comput. Sci., 337 (2005), 240–248 | DOI | MR | Zbl

[17] Dyukova E. V., Zhuravlev Yu. I., “Discrete analysis of feature descriptions in high-dimensional recognition tasks”, J. Comput. Mathem. and Mathem. Physics, 40:8 (2000), 1264–1278 (in Russian) | MR | Zbl

[18] Dyukova E. V., Inyakin A. S., “About classification procedures based on classroom construction”, J. Comput. Mathem. and Mathem. Physics, 43:12 (2003), 1884–1895 (in Russian) | MR | Zbl

[19] Bykova V. V., “Mathematical methods for analyzing recursive algorithms”, J. Siberian Federal University. Mathematics and Physics, 3:1 (2008), 372–384 (in Russian) | MR

[20] Harzheim E., Ordered Sets, Springer, New York, 2005, 390 pp. | MR | Zbl

[21] Mongush Ch. M., Bykova V. V., The program FCACorpus of conceptual modeling of Tuvan texts by the methods of the formal concepts analysis, Certificate of state registration of computer programs No 2018618907, issued by the Federal Service for Intellectual Property of the Russian Federation, 2018 (in Russian)