Optimal Decompositions of Matrices with Grades into Binary and Graded Matrices?

Abstract

The paper contributes to factor analysis of relational data. We study the problem of decomposition of object-attribute matrices with grades, i.e. 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 grades into an object-factor matrix A and a binary factorattribute matrix B, with the number of factors as small as possible. We present a theorem describing optimal decompositions. The theorem shows that decompositions which use as factors particular formal concepts associated to I are optimal in that the number of factors involved is the smallest possible. Furthermore, we present an approximation algorithm for finding those decompositions and illustrative examples.

-

Problem description in brief This paper presents results on optimal decompositions of matrices with grades. Examples of such matrices are binary (or Boolean) matrices, i.e. matrices which entries are 0 or 1. Other examples are matrices which contain numbers from the unit interval [ 0, 1 ] as their entries. In general we consider non-numerical matrices with entries from particular complete lattices L (binary matrices and matrices with entries from [ 0, 1 ] are particular examples with L = {0, 1} and L = [ 0, 1 ], respectively).

We consider the following problem. Let L be a partially ordered scale bounded from below and above by 0 and 1 (details specified later). Given an n × m matrix I with entries from L (i.e. Iij ∈ L), we want to decompose I into a product

I = A ◦ B of an n × k matrix A with entries from L (i.e. Ail ∈ L) and a k × m binary matrix B (i.e. Blj ∈ {0, 1}) with k as small as possible. The composition operation ◦ which we consider is defined by k (A ◦ B)ij = _ Ail ⊗ Blj , (1)

l=1 where ⊗ is defined by a ⊗ 1 = a and a ⊗ 0 = 0. Note that if L = {0, 1} then A ◦ B is the well-known Boolean product of binary matrices. Note also that if we allow Ail ∈ L and Blj ∈ L and if ⊗ is a t-norm then ◦ is the product of graded matrices well-known in fuzzy set theory, see e.g. [ 15 ], and that such decompositions were considered in [ 4, 7 ].

Factor analysis model For a decomposition I = A ◦ B given by (1), Iij can be interpreted as a degree to which there is a factor l such that l applies to object i and l is associated to attribute j (j is a particular manifestation of l). This way, a decomposition I = A ◦ B provides us with a factor analysis model (see [ 1, 13, 16 ] for references on factor analysis): A relationship between objects and original attributes given by I is described using a relationship between the objects and new variables, called factors, which is given by A, and a relationship between factors and the original attributes, which is given by B. Note that we assume that B is binary, i.e. that the relationship between factors and attributes is a yes-or-no relationship. This feature distinguishes our approach from those which we considered earlier.

Needless to say, one can consider decompositions I = A ◦ B given by (1), in which A is binary and B arbitrary. Obviously, using IT = BT ◦ AT , one can reduce this type of decomposition to the first type (A arbitrary, B binary). Therefore, we do not consider such case.

Contribution of the paper We present a theorem regarding optimal decompositions of a given matrix I which shows that decompositions which use as factors particular formal concepts, called crisply generated concepts, are optimal in that they involve the least number of factors among all decompositions of I. Furthermore, we present an approximation algorithm for finding those decompositions and provide illustrative examples.

Related and previous work The paper is a continuation of our previous work [ 4, 6, 7 ]. In particular, in [ 4, 7 ] we considered decompositions I = A ◦ B given by (1), in which both A and B were arbitrary, i.e. none of them was required to be binary.

Preliminaries from fuzzy logic We use standard notions of fuzzy logic and fuzzy sets, see e.g. [ 2, 12, 15 ]. In particular, we use complete residuated lattices as structures of truth degrees. Recall that a complete residuated lattice is an algebra L = hL, ∧, ∨, ⊗, →, 0, 1i such that hL, ∧, ∨, 0, 1i is a complete lattice, hL, ⊗, 1i is a commutative monoid, and ⊗ and → satisfy so-called adjointness condition, i.e. a ⊗ b ≤ c if and only if a ≤ b → c. We assume familiarity with examples and basic properties of residuated lattices. As an example, for L = [ 0, 1 ], a ⊗ b = max(0, a+b−1), a → b = min(1, 1−a+b), the algebra L = h[ 0, 1 ], ∧, ∨, ⊗, →, 0, 1i is a complete residuated lattice (so-called standard Lukasiewicz algebra). An Lset in a universe set U is a mapping A : U → L. 2 2.1

Optimal Decompositions

Composition as W-superposition of matrices We first observe that I = A ◦ B for n × k and k × m matrices A (graded) and B (binary) means that I is a W-superposition of particular rectangular matrices. Definition 1. Let K1, K2 ⊆ L. An n × m matrix J with entries from L is called (K1, K2)-rectangular iff there exist L-sets C in {1, . . . , n} and D in {1, . . . , m} with C(i) ∈ K1 and D(j) ∈ K2 such that J = C ⊗ D, i.e.

Jij = C(i) ⊗ D(j) (2) for 1 ≤ i ≤ n, 1 ≤ j ≤ m.

In particular, we need (L, {0, 1})-rectangular matrices and call these just “rectangular”. The term “rectangular” is inspired by the “shape” of such matrices. The following matrices are examples of ({0, 1}, {0, 1})-rectangular (J1) and ([ 0, 1 ], {0, 1})-rectangular (J2) matrices: Theorem 1. I = A ◦ B for n × k and k × m matrices A and B with Ail ∈ L and Blj ∈ {0, 1} iff I is a W-superposition of k (L, {0, 1})-rectangular matrices J1, . . . , Jk, i.e. iff

I = J1 ∨ J2 ∨ · · · ∨ Jk.

Proof. Denote by Jl the ◦-product A l ◦ Bl of the l-th column A l of A and the l-th row Bl of B, i.e. (Jl)ij = Ail ⊗ Blj . I = A ◦ B means Iij = (A ◦ B)ij , i.e. Iij = Wk

l=1(Ail ⊗ Blj ). Therefore, I = J1 ∨ J2 ∨ · · · ∨ Jk. Since B is a binary matrix, Jl are (L, {0, 1})-rectangular matrices. Example 1. To illustrate the content of Theorem 1, consider the following decomposition I = A ◦ B: Theorem 1 says that in order to find a decomposition I = A ◦ B, we need to find a suitable set of (L, {0, 1})-rectangular matrices Jl whose W-superposition gives I. We now describe decompositions of I which are optimal among all possible decompositions in that the number k of factors is the smallest possible one. The decompositions use so-called crisply generated formal concepts of I [ 5 ]. Preliminaries on crisply generated formal concepts This section presents preliminaries on formal concepts of data with fuzzy attributes, particularly on crisply generated formal concepts. The reader is referred, e.g., to [ 3, 5 ] for details.

Let X = {1, . . . , n} and Y = {1, . . . , m} be sets (of objects and attributes, respectively), I be an n × m matrix with entries from a support set L of a complete residuated lattice L. The degree Ixy ∈ L is interpreted as a degree to which object x has attribute y. Consider the operators ↑ : LX → LY and ↓ : LY → LX defined by

C↑(y) = Vx∈X (C(x) → Ixy),

D↓(x) = Vy∈Y (D(y) → Ixy), where → is the residuum of the complete residuated lattice L. That is, ↑ assigns an L-set C↑ in Y to a given L-set C in X, and ↓ assigns an L-set D↓ in X to a given L-set D in Y . C↑(y) can verbally be described as a degree to which “for each object x ∈ X: if x is from C then x has attribute y” (note that C↑(y) is just the degree of the last statement “for each · · · ” according to basic principles of first-order fuzzy logic, see [ 12 ]). Likewise, D↓(x) is the degree to which “for each attribute y ∈ Y : if y is from D then x has attribute y” is true. If L = {0, 1}, ↑ : LX → LY and ↓ : LY → LX coincide with the well-known concept-derivation operators of the basic setting of formal concept analysis [ 8, 11 ]. ↑ and ↓ form a fuzzy Galois connection [ 2 ] and the compound operators ↑↓ and ↓↑ form particular closure operators in X and Y [ 2 ]. A pair hC, Di consisting of an L-set C in X and an L-set D in Y is called a formal concept of I if C↑ = D and D↓ = C. C and D are called the extent and intent of hC, Di, respectively. The set of all formal concepts of I is denoted by B(X, Y, I). With a partial order ≤ defined by

hC1, D1i ≤ hC2, D2i iff C1 ⊆ C2 (iff D2 ⊆ D1) for hC1, D1i, hC2, D2i ∈ B(X, Y, I), B(X, Y, I) happens to be a complete lattice, so-called concept lattice associated to I [ 2, 3 ]. Note that C1 ⊆ C2 means that C1 is contained in C2, i.e. for each x ∈ X, C1(x) ≤ C2(x). For L = {0, 1}, B(X, Y, I) coincides with the ordinary concept lattice [ 11 ]. In [ 5 ], the following notion was introduced. A formal concept hC, Di ∈ B(X, Y, I) is called crisply generated if there is a crisp L-set Dc ∈ {0, 1}Y , i.e. for each y ∈ Y : Dc(y) = 0 or Dc(y) = 1, such that C = Dc↓ (and thus D = Dc↓↑). Let Bc(X, Y, I) denote the collection of all crisply generated formal concepts of I, i.e.

Bc(X, Y, I) = {hC, Di ∈ B(X, Y, I) | there is Dc ∈ {0, 1}Y : C = Dc↓}. We need the following characterization of crisply generated formal concepts. For L-sets C1, C2 ∈ LX and D1, D2 ∈ LY , we put hC1, D1i E hC2, D2i if for each x ∈ X, y ∈ Y we have C1(x) ≤ C2(x) and D1(y) ≤ D2(y).

Lemma 1 ([ 5 ]). hC, Di is a crisply generated formal concept iff hC, Di is maximal (w.r.t. E) such that (1) the rectangular matrix J defined by Jxy = C(x) ⊗ D(y) is contained in I (i.e. Jxy ≤ Ixy for all x, y) and (2) C(x) = VD(y)=1 Ixy. Remark 1. Note that condition (2) of Lemma 1 means that for the crisp L-set Dc ∈ {0, 1}Y corresponding to the 1-cut of D, which is defined by Dc(y) = 1 if D(y) = 1, 0 if D(y) < 1, (3) we have C = Dc↓.

Matrices AF and BF For convenience, we identify 1 × p vectors with entries from L with L-sets in {1, . . . , p} (the l-th coordinate of the vector = the degree to which l belongs to the L-set). Given a set

F = {hC1, D1i, . . . , hCk, Dki} of L-sets Cl and Dl in {1, . . . , n} and {1, . . . , m}, respectively, with values from L, define n × k and k × m matrices AF and BF by

(AF )il = (Cl)(i) and (BF )lj = (Dl)(j).

That is, the l-th column of AF is the transpose of the vector corresponding to Cl and the l-th row of BF is the vector corresponding to Dl. For F ⊆ B(X, Y, I), denote

Fc = {hC, Dci | hC, Di ∈ F }.

Note that Dc is defined by (3). We will show that sets Fc corresponding to sets F of crisply generated formal concepts are fundamental for decompositions we are looking for.

The first theorem says that for every I, there is a decomposition AFc ◦ BFc for some F ⊆ Bc(X, Y, I).

Theorem 2 (universality). For every I with entries from L there is F ⊆ Bc(X, Y, I) such that I = AFc ◦ BFc , i.e. I is a product of A with entries from L and B with entries from {0, 1}.

Proof. Denote for l ∈ {1, . . . , m}, hCl, Dli = h{1/l}↓, {1/l}↓↑i. Here, {1/l} is a singleton in {1, . . . , m}, i.e. and L-set defined by {1/l}(l) = 1 and {1/l}(j) = 0 for j 6= l. hCl, Dli are particular crisply generated formal concepts from B(X, Y, I) and we have

Iij = Wm

l=1 Cl(i) ⊗ Dl(j), see [ 2 ]. Putting thus F = {hCl, Dli | l = 1, . . . , m}, we get I = AFc ◦ BFc .

However, Theorem 2 and its proof yield only |F | = m, i.e. the number k = |F | of factors equals the number m of attributes. In general, better decompositions may exist, i.e. those with k < m. The next theorem shows that the decompositions which use crisply generated formal concepts of I as factors are optimal among all decompositions of I.

Theorem 3 (optimality). Let I = A ◦ B for n × k and k × m matrices A and B with Ail ∈ L, Blj ∈ {0, 1}. Then there exists a set F ⊆ Bc(X, Y, I) of crisply generated formal concepts of I such that for Fc we have

|Fc| ≤ k and for the n × |Fc| and |Fc| × m matrices AFc with entries from L and BFc with entries from {0, 1} we have

I = AFc ◦ BFc .

Proof. Sketch: Let I = A◦B for an n×k matrix A with entries from L and a k×m binary matrix B. Consider the corresponding rectangular matrices J1, . . . , Jk of which I is a W-superposition according to Theorem 1. Denoting now the Lsets in {1, . . . , n} and {1, . . . , m} corresponding to the l-th column of A and the l-th row of B by Gl and Hl, respectively, we have Jl = Gl ⊗ Hl. We have Gl ⊗ Hl ⊆ I and one can check that also H↓ l ⊗ Hl ⊆ I. The pair hHl↓, Hli satisfies condition (2) of Lemma 1 (see also Remark 1). Therefore, hH↓, Hli is contained l in a maximal (w.r.t. E defined in the paragraph preceding Lemma 1) hCl, Dli which is then, according to Lemma 1, a crisply generated formal concept of I. As a result, Cl ⊗ Dl ⊆ I. Therefore, for F = {hC1, D1i, . . . , hCk, Dki} we have |F | ≤ k. Because (Hl)j ∈ {0, 1} and because we may assume Hl ⊆ Dl, we get

Note that using the notation from the proof of Theorem 3, two distinct hGl, Hli’s may be contained in a single hCl, Dli, i.e. for hGl1 , Hl1 i 6= hGl2 , Hl2 i we can have hCl1 , Dl1 i = hCl2 , Dl2 i. As a consequence, we may have |F | < k. 3

Algorithm In this section, we present an approximation algorithm for computing a decomposition I = A ◦ B of an n × m matrix I with entries from L into an n × k matrix A with entries from L and a k × m binary matrix B with k as small as possible. Note that we do not provide the approximation factor for this algorithm.

Recall that for L = {0, 1} (i.e. the set of grades contains just 0 and 1), our problem becomes a problem of decomposition of binary matrices. In particular, if L = {0, 1}, we are given a binary matrix I and our aim is to find a decomposition I = A ◦ B into an n × k binary matrix A and a k × m binary matrix B with k as small as possible. This problem is NP-hard and its decision version is NPcomplete, see e.g. [ 17–19 ], and also [ 6 ].

Due to NP-hardness of a problem of decomposition of binary matrices which is a particular instance of our problem, we need to look for suitable approximation algorithms. In the following, we propose a greedy approximation algorithm inspired by the algorithms presented in [ 6 ] and [ 7 ]. Briefly, starting with empty Fc, the algorithm selects a crisply generated concept hC, Di of I that covers a large part of I which is still uncovered. For each such selected hC, Di, the corresponding hC, Dci, see (3), is added to Fc. For determining hC, Di, we use |D ⊕ j| which denotes the number of pairs hi, j0i of indices, for which Iij0 = IFc ∨ (D ∪ { 1/j})↓ ⊗ (D ∪ { 1/j})↓↑ ij0 . We refer to this approach as to Method 1. We also used Method 2 for which |D ⊕ j| takes into account also entries IFc ∨ (D ∪ { 1/j})↓ ⊗ (D ∪ { 1/j})↓↑ ij0 which are close to Iij0 but not necessarily equal (details will appear in a full version of this paper).

Note that if L = {0, 1}, our algorithm works the same way as the one from [ 6 ]. We performed several experiments with our algorithm. Due to limited scope, we present the following one. We generated 1,000 matrices I of dimension 15×15 over 5-element chain L with Lukasiewicz operations. Each matrix was generated as a product of a 15 × k matrix A and a k × 15 binary matrix B, so we knew the number of factors (its upper bound, in fact). Table 1 shows the numbers of factors (average value ± standard deviation) for decompositions of I obtained by our algorithm (both for Methods 1 and 2).

Algorithm 1 Find Factors

Input: I (matrix with entries from L) Output: Fc (set Fc for which I = AFc ◦ BFc ) set IFc to empty matrix ((IFc )ij = 0) while I 6= IFc do set D to ∅ set V to 0 while there is j such that D(j) < 1 and |D ⊕ j| > V do select j such that D(j) < 1 which maximizes |D ⊕ j| set D to (D ∪ { 1/j})↓↑ set V to |D ⊕ j| end while set C to D↓ add hC, Dci to Fc set IFc to IFc ∨ C ⊗ Dc end while In this section, we present an illustrative example regarding decompositions of a matrix with grades into a matrix with grades and a binary matrix.

In our example, we consider n users, m permissions, and a user-to-permission assignment. The assignment can be represented by an n × m matrix I with entries from a scale L = {0, r, w, 1}, with 0 representing “no permission”, r and w representing “permission to read” and “permission to write”, respectively, and 1 representing “full permission”. We define a partial order on L such that 0 is the least element, 1 is the greatest one, and elements r and w are incomparable, see Fig. 1.

Furthermore, we need to define operations of multiplication ⊗. We put x⊗y = x ∧ y, for all x, y ∈ L. The residuum is then determined by ⊗ (due to the requirement of adjointness, see Section 1) and is defined by x → y = 1 for x ≤ y, x → y = y for all x > y, and r → w = w, w → r = r.

We want to decompose I into a product of n × k matrix A and k × m matrix B where A and B represent a user-to-role and a role-to-permission relationship, respectively. Therefore, the factors we want to discover are to be interpreted as roles, such as “system administrator”, “standard user” or the like. Naturally, we expect A to be a binary matrix (i.e. Ail ∈ {0, 1}), assigning roles to users (a user has a given role or not), whereas B is graded matrix (i.e. Blj ∈ L). In order to be consistent with previous chapters, A should be graded and B should be binary matrix. Therefore, we use well-known fact that I = A ◦ B is equivalent to I−1 = B−1 ◦ A−1. That is, instead of I we decompose I−1.

As a particular example, we consider 9 users (or employees) and 5 file-types in some computer system (for instance, “documents”, “archive files” or “system files” could be some of these types). The user-to-permission relationship is described in the table thereunder. The data can be visualized using a rectangular grid, where , , , and represent permissions 0, r, w, and 1, respectively:

Alice

Bob Charles David Eve Frank George Henry Isaac i.e.,  1 1 0 

0 1 0  1 1 0  I = A ◦ B =  0111 1111 0100  ◦  0 1 0 

0 1 0 This decomposition can be displayed as:

As we obtained a 9 × 3 binary matrix A describing a user-to-role assignment and 3 × 5 matrix B describing a role-to-permission assignment. Therefore, we obtained 3 factors: role1, role2, role3. The first role (corresponding to the first row of matrix B) might be interpreted as “standard user”, the second one (the middle row of B) as “anonymous user” (“guest”), and the third one (the last row of B) as “system administrator”.

According to matrix A, we assign roles to users by: =

◦ Alice - role1, role2, Bob - role2, Charles - role1, role2, David - role2, Eve - all roles, Frank - role1, role2, George - role1, role2, Henry - role2,

Isaac - role2.

Next, we compute an approximate decomposition of I ≈ A ◦ B. By this we mean that we want the entries of I to by similar to the corresponding entries of A◦B to a degree which exceeds a given similarity threshold f . In our example we set f = 0.9. Details regarding such similarity will be presented in a full version of this paper. Let us just note that the similarity is based on the number of matrix entries which have equal values in I and A ◦ B. A graphical representation of an approximation decomposition computed by our algorithm depicted below.

We can see that the approximate decomposition involves the two factors corresponding to “standard user” and “anonymous user”, which were involved also in the exact decomposition. However, the factor corresponding to “system administrator” is no longer involved in the approximate decomposition. This can be seen as the result of our attempt, due to performing an approximate decomposition, to discover only a small number of factors (roles) which account for most of the data and, hence, are common. The role of “system administrator” is not common since the only user with this role is Eve. 5

Conclusions and Future Research We presented a theorem regarding optimal decomposition of a matrix with grades into a matrix with grades and a binary matrix. Furthermore, we proposed a greedy approximation algorithm for computing such decompositions and examples illustrating such decompositions.

Further issues and future research include the following items: – Independence of ⊗ and →. It can be shown that the decompositions of a graded matrix into a graded and a binary matrix do not depend, in a certain sense, on the operations ⊗ and → on the scale L of grades. We sticked to the framework which involves ⊗ and → to show how the problem addressed in this paper fits into the results developed earlier. Details will be presented in the full version of this paper. – Decompositions of matrices with grades into matrices with further constraints, different from the requirement of binarity of B. – Approximation algorithms for approximate and exact decompositions of matrices with grades. – Applications of the underlying factor analysis model and comparison to other models of factor analysis. – Role of decompositions in machine learning and data mining (esp. dimensionality reduction).

References

1. Bartholomew , D. J. , Knott M. : Latent Variable Models and Factor Analysis , 2nd Ed., London, Arnold, 1999 .

2. Belohlavek , R.: Fuzzy Relational Systems: Foundations and Principles . Kluwer, Academic/Plenum Publishers, New York, 2002 .

3. Belohlavek , R.: Concept lattices and order in fuzzy logic . Annals of Pure and Applied Logic 128 ( 1-3 )( 2004 ), 277 - 298 .

4. Belohlavek , R.: Optimal decompositions of matrices with grades . IEEE Intelligent Systems 2008 (to appear).

5. Belohlavek , R. , Sklenar , V. , Zacpal , J.: Crisply generated fuzzy concepts . In: B. Ganter and R . Godin (Eds.): ICFCA 2005, Lecture Notes in Artificial Intelligence 3403 , pp. 268 - 283 , Springer-Verlag, Berlin/Heidelberg, 2005 .

6. Belohlavek , R. , Vychodil , V. : Discovery of optimal factors in binary data via a novel method of matrix decomposition (to appear). Preliminary version appeared as: On Boolean factor analysis with formal concepts as factors . SCIS & ISIS 2006 , Int . Conf. Soft Computing and Intelligent Systems & Int. Symposium on Intelligent Systems, Sep 20-24 , 2006 , Tokyo, Japan, pp. 1054 - 1059 .

7. Belohlavek , R. , Vychodil , V. : Optimal decompositions of matrices with ordinal data (submitted).

8. Carpineto , C. , Romano , G.: Concept Data Analysis . Theory and Applications . J. Wiley, 2004 .

9. Cormen , T. H. , Leiserson , C. E. , Rivest , R. L. , Stein , C. : Introduction to Algorithms, 2nd Ed. MIT Press, 2001 .

10. Frolov , A. A. , Hu´sek, D. , Muraviev , I. P. , Polyakov , P. A. : Boolean factor analysis by Hopfield-like autoassociative memory . IEEE Transactions on Neural Networks Vol. 18 , No. 3, May 2007 , pp. 698 - 707 .

11. Ganter , B. , Wille , R.: Formal Concept Analysis . Mathematical Foundations . Springer, Berlin, 1999 .

12. H´ajek, P.: Metamathematics of Fuzzy Logic. Kluwer, Dordrecht, 1998 .

13. Harman , H. H. : Modern Factor Analysis , 2nd Ed. The Univ. Chicago Press, Chicago, 1970 .

14. Keprt , A. , Sn´aˇsel, V.: Binary factor analysis with help of formal concepts . In Proc. CLA 2004 , Ostrava, Czech Republic, 2004 , pp. 90 - 101 , ISBN 80-248-0597-9.

15. Klir , G. J. , Yuan , B. : Fuzzy Sets and Fuzzy Logic . Theory and Applications . Prentice-Hall, 1995 .

16. McDonald , R. P. : Factor Analysis and Related Methods . Lawrence Erlbaum Associates, Inc., 1985 .

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. Biosciences 40 ( 1978 ), 243 - 270 .

19. Stockmeyer , L. J.: The set basis problem is NP-complete . IBM Research Report RC5431 , Yorktown Heights, NY, 1975 .

20. Wille , R.: Restructuring lattice theory: an approach based on hierarchies of concepts . In: I. Rival (Ed.): Ordered Sets , 445 - 470 , Reidel, Dordrecht-Boston, 1982 .