Abstract
We present a problem of factor analysis of three-way binary data. Such data is described by a 3-dimensional binary matrix I, describing a relationship between objects, attributes, and conditions. The aim is to decompose I into three binary matrices, an object-factor matrix A, an attribute-factor matrix B, and a condition-factor matrix C, with a small number of factors. The difference from the various decomposition-based methods of analysis of three-way data consists in the composition operator and the constraint on A, B, and C to be binary. We present a theoretical analysis of the decompositions and show that optimal factors for such decompositions are provided by triadic concepts developed in formal concept analysis. Moreover, we present an illustrative example, propose a greedy algorithm for computing the decompositions.
Supported by grant no. P202/10/0262 of the Czech Science Foundation and by grant no. MSM 6198959214.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Belohlavek, R.: Optimal decompositions of matrices with grades. In: IEEE IS 2008, pp. 15-2–15-7 (2008)
Belohlavek, R.: Optimal triangular decompositions of matrices with entries from residuated lattices. Int. J. of Approximate Reasoning 50(8), 1250–1258 (2009)
Belohlavek, R., Vychodil, V.: Discovery of optimal factors in binary data via a novel method of matrix decomposition. J. Computer and System Sci. 76(1), 3–20 (2010)
Belohlavek, R., Vychodil, V.: Factor analysis of incidence data via novel decomposition of matrices. LNCS (LNAI), vol. 5548, pp. 83–97. Springer, Heidelberg (2009)
Cichocki, A., et al.: Nonnegative Matrix and Tensor Factorizations: Applications to Exploratory Multi-way Data Analysis and Blind Source Separation. J. Wiley, Chichester (2009)
Cormen, T.H., et al.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)
Frolov, A.A., et al.: Boolean factor analysis by Hopfield-like autoassociative memory. IEEE Trans. Neural Networks 18(3), 698–707 (2007)
Ganter, B., Wille, R.: Formal Concept Analysis. Mathematical Foundations. Springer, Berlin (1999)
Jäschke, R., Hotho, A., Schmitz, C., Ganter, B., Stumme, G.: TRIAS – An Algorithm for Mining Iceberg Tri-Lattices. In: Proc. ICDM 2006, pp. 907–911 (2006)
Kolda, T.G., Bader, B.W.: Tensor decompositions and applications. SIAM Review 51(3), 455–500 (2009)
Kuznetsov, S., Obiedkov, S.: Comparing performance of algorithms for generating concept lattices. J. Exp. Theor. Artif. Intelligence 14(2-3), 189–216 (2002)
Lee, D., Seung, H.: Learning the parts of objects by non-negative matrix factorization. Nature 401, 788–791 (1999)
Lehmann, F., Wille, R.: A triadic approach to formal concept analysis. In: Ellis, G., Rich, W., Levinson, R., Sowa, J.F. (eds.) ICCS 1995. LNCS, vol. 954, pp. 32–43. Springer, Heidelberg (1995)
Miettinen, P., Mielikäinen, T., Gionis, A., Das, G., Mannila, H.: The Discrete Basis Problem. In: Fürnkranz, J., Scheffer, T., Spiliopoulou, M. (eds.) PKDD 2006. LNCS (LNAI), vol. 4213, pp. 335–346. Springer, Heidelberg (2006)
Stockmeyer, L.J.: The set basis problem is NP-complete. IBM Research Report RC5431, Yorktown Heights, NY (1975)
Tatti, N., Mielikäinen, T., Gionis, A., Mannila, H.: What is the dimension of your binary data? In: Perner, P. (ed.) ICDM 2006. LNCS (LNAI), vol. 4065, pp. 603–612. Springer, Heidelberg (2006)
Wille, R.: The basic theorem of triadic concept analysis. Order 12, 149–158 (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Belohlavek, R., Vychodil, V. (2010). Factorizing Three-Way Binary Data with Triadic Formal Concepts. In: Setchi, R., Jordanov, I., Howlett, R.J., Jain, L.C. (eds) Knowledge-Based and Intelligent Information and Engineering Systems. KES 2010. Lecture Notes in Computer Science(), vol 6276. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15387-7_51
Download citation
DOI: https://doi.org/10.1007/978-3-642-15387-7_51
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15386-0
Online ISBN: 978-3-642-15387-7
eBook Packages: Computer ScienceComputer Science (R0)