Optimal decompositions of matrices with grades into binary and graded matrices. (English) Zbl 1213.68598

Summary: We study the problem of decomposition of object-attribute matrices whose entries contain degrees to which objects have attributes. The degrees are taken from a bounded partially ordered scale. Examples of such matrices are binary matrices, matrices with entries from a finite chain, or matrices with entries from the unit interval [0, 1]. We study the problem of decomposition of a given object-attribute matrix \(I\) with degrees into an object-factor matrix \(A\) with degrees and a binary factor-attribute matrix \(B\), with the number of factors as small as possible. We present a theorem which shows that decompositions which use particular formal concepts of \(I\) as factors for the decomposition are optimal in that the number of factors involved is the smallest possible. We show that the problem of computing an optimal decomposition is NP-hard and present two heuristic algorithms for its solution along with their experimental evaluation. For the first algorithm, we provide its approximation ratio. Experiments indicate that the second algorithm, which is considerably faster than the first one, delivers decompositions whose quality is comparable to the decompositions delivered by the first algorithm. We also present an illustrative example demonstrating a factor analysis interpretation of the decomposition studied in this paper.


68T30 Knowledge representation
03B52 Fuzzy logic; logic of vagueness
06A15 Galois correspondences, closure operators (in relation to ordered sets)
15A23 Factorization of matrices


Full Text: DOI Link


[1] Bartholomew, D.J., Knott, M.: Latent Variable Models and Factor Analysis, 2nd edn.. Arnold, London (1999) · Zbl 1066.62528
[2] Belohlavek, R.: Fuzzy Relational Systems: Foundations and Principles. Kluwer Academic, New York (2002)
[3] Belohlavek, R.: Concept lattices and order in fuzzy logic. Annals of Pure and Applied Logic 128(1–3), 277–298 (2004) · Zbl 1060.03040
[4] Belohlavek, R.: Optimal decompositions of matrices with grades. In: Proc. IEEE Intelligent Systems 2008, Varna, Bulgaria, pp. 15-2–15-7, ISBN 978-1-4244-1740-7 (2008) (extended version submitted to J. Log. Comput.)
[5] Belohlavek, R., Sklenar, V., Zacpal, J.: Crisply generated fuzzy concepts. In: Lecture Notes in Artificial Intelligence, vol. 3403, pp. 268–283 (2005)
[6] Belohlavek, R., Vychodil, V.: Discovery of optimal factors in Boolean factor analysis via novel method of binary matrix decomposition. J. Comput. Syst. Sci. 76(1), 3–20 (2010) · Zbl 1180.15026
[7] Belohlavek, R., Vychodil, V.: Factor analysis of incidence data via novel decomposition of matrices. In: Lecture Notes in Artificial Intelligence, vol. 5548, pp. 83–97 (2009) · Zbl 1248.68474
[8] Carpineto, C., Romano, G.: Concept Data Analysis. Theory and Applications. Wiley, New York (2004) · Zbl 1083.68117
[9] Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT, Cambridge (2001) · Zbl 1047.68161
[10] Ganter, B., Wille, R.: Formal Concept Analysis. Mathematical Foundations. Springer, Berlin (1999) · Zbl 0909.06001
[11] Hájek, P.: Metamathematics of Fuzzy Logic. Kluwer, Dordrecht (1998) · Zbl 0937.03030
[12] Harman, H.H.: Modern Factor Analysis, 2nd edn. The University of Chicago Press, Chicago (1970) · Zbl 0161.39805
[13] Klir, G.J., Yuan, B.: Fuzzy Sets and Fuzzy Logic. Theory and Applications. Prentice-Hall, Upper Saddle River (1995) · Zbl 0915.03001
[14] McDonald, R.P.: Factor Analysis and Related Methods. Lawrence Erlbaum Associates, Mahwah (1985)
[15] Mickey, M.R., Mundle, P., Engelman, L.: Boolean factor analysis. In: Dixon, W.J. (ed.) BMDP Statistical Software, pp. 538–545. University of California Press, Berkeley (1983)
[16] Miettinen, P., Mielikäinen, T., Gionis, A., Das, G., Mannila, H.: The discrete basis problem. In: Lecture Notes in Artificial Intelligence, vol. 4213, pp. 335–346 (2006)
[17] Nau, D.S.: Specificity covering: immunological and other applications, computational complexity and other mathematical properties, and a computer program. A.M. thesis, Technical Report CS–1976–7, Computer Sci. Dept., Duke Univ., Durham, N. C. (1976)
[18] Nau, D.S., Markowsky, G., Woodbury, M.A., Amos, D.B.: A mathematical analysis of human leukocyte antigen serology. Math. Biosci. 40, 243–270 (1978) · Zbl 0394.92007
[19] Stockmeyer, L.J.: The set basis problem is NP-complete. IBM Research Report RC5431, Yorktown Heights, NY (1975)
[20] Tatti, N., Mielikäinen, T., Gionis, A., Mannila, H.: What is the dimension of your binary data? In: The 2006 IEEE Conference on Data Mining (ICDM 2006), pp. 603–612. IEEE Computer Society, Washington (2006)
[21] Vaidya, J., Atluri, V., Guo, Q.: The Role Mining Problem: Finding a Minimal Descriptive Set of Roles. In: ACM Symposium on Access Control Models and Technologies, pp. 175–184 (2007)
[22] Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2003)
[23] Wille, R.: Restructuring lattice theory: an approach based on hierarchies of concepts. In: Rival, I. (ed.) Ordered Sets, pp. 445–470. Reidel, Dordrecht (1982) · Zbl 0491.06008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.