Boolean Factor Analysis of Multi-Relational Data

Abstract

The Boolean factor analysis is an established method for analysis and preprocessing of Boolean data. In the basic setting, this method is designed for finding factors, new variables, which may explain or describe the original input data. Many real-world data sets are more complex than a simple data table. For example almost every web database is composed from many data tables and relations between them. In this paper we present a new approach to the Boolean factor analysis, which is tailored for multi-relational data. We show our approach on simple examples and also propose future research topics.

Introduction

Many data sets are Boolean by nature, that is, they contain only 0s and 1s.

For example, any data recording the presence (or absence) of variables in observations are Boolean. Boolean data can be seen as a binary data table (or matrix or formal context) C, where the rows represent objects and the columns represent attributes of these objects. Between objects and attributes exists an incidence relation with meaning that an object i has an attribute j and this fact is represented by one in the Boolean table, i.e. Cij = 1. If an object i has not an attribute j, than Cij = 0.

Many real-word data sets are more complex that a simple data table. Usually,

they are composed from many data tables, which are interconnected by relations.

An example of such data can be found in almost every sector of human activity.

We call this kind of data multi-relational data. In this kind of data, this relations are crucial, because they represent additional information about the relationship between data tables and this information is important for understanding data as a whole.

The Boolean factor analysis (BFA) is used for many data mining purposes.

The basic task in the BFA is to find new variables, called factors, which may explain or describe original single input data. Finding factors is obviously an important step for understanding and managing data. Boolean nature of data is in this case beneficial especially from the standpoint of interpretability of the results. On the other hand BFA is suitable for single input Boolean data table with just one relation between objects and attributes. The main aim of this work c paper author(s), 2013. Published in Manuel Ojeda-Aciego, Jan Outrata (Eds.): CLA 2013, pp. 187{198, ISBN 978{2{7466{6566{8, Laboratory L3i, University of La Rochelle, 2013. Copying permitted only for private and academic purposes. is to present the BFA of multi-relational data, which takes into account relations between data tables and extract more detailed information from this complex data. 2

Preliminaries and basic notions

We assume familiarity with the basic notions of FCA [ 3 ]. In this work, we use the binary matrix terminology, because it is more convenient from our point of view. Consider an n × m object-attribute matrix C with entries Cij ∈ {0, 1} expressing whether an object i has an attribute j or not, i.e. C can be understood as a binary relation between objects and attributes. Because there is no danger of confusion we can consider this matrix as a formal context hX, Y, Ci, where X represents a set of n objects and Y represents a set of m attributes.

A formal concept of hX, Y, Ci is any pair hE, F i consisting of E ⊆ X (so

called extent) and F ⊆ Y (so-called intent) satisfying E↑ = F and F ↓ = E where E↑ = {y ∈ Y | for each x ∈ X : hx, yi ∈ C}, and F ↓ = {x ∈ X | for each y ∈ Y : hx, yi ∈ C}.

The goal of the BMF (the idea from [1, 6]) is to find decomposition

C = A ◦ B of I into a product of an n × k object-factor matrix A over {0, 1}, a k × m matrix B over {0, 1}, revealing thus k factors, i.e. new, possibly more fundamental attributes (or variables), which explain original m attributes. We want k < m and, in fact, k as small as possible in order to achieve parsimony: The n objects described by m attributes via C may then be described by k factors via

A, with B representing a relationship between the original attributes and the factors. This relation can be interpreted in the following way: an object i has an attribute j if and only if there exists a factor l such that i has l (or, l applies to i) and j is one of the particular manifestations of l.

The product ◦ in (1) is a Boolean matrix product, defined by

(1) (2)

The least k for which an exact decomposition C = A ◦ B exists is in the

Boolean matrix theory called the Boolean rank (or Schein rank).

An optimal decomposition of the Boolean matrix can be found via Formal concept analysis. In this approach, the factors are represented by formal concepts, see [ 2 ]. The aim is to decompose the matrix C into a product AF ◦ BF of where W denotes maximum (truth function of logical disjunction) and · is the usual product (truth function of logical conjunction). For example the following matrix can be decomposed into two Boolean matrices with k < m. (A ◦ B)ij = Wk

l=1 Ail · Blj ,

Boolean matrices constructed from a set F of formal concepts associated to C.

Let

F = {hA1, B1i , . . . , hAk, Bki} ⊆ B(X, Y, C), where B(X, Y, C) represents set of all formal concepts of context hX, Y, Ci. Denote by AF and BF the n × k and k × m binary matrices defined by (AF )il = 1 if i ∈ Al (BF )lj = 0 if i ∈/ Al 1 if j ∈ Bl 0 if j ∈/ Bl for l = 1, . . . , k. In other words, AF is composed from characteristic vectors Al.

Similarly for BF . The set of factors is a set F of formal concepts of hX, Y, Ci,

for which holds C = AF ◦ BF . For every C such a set always exists. For details see [ 2 ].

Interpretation factors as a formal concepts is very convenient for users and we follow this point of view in our work. Because a factor can be seen as a formal concept, we can consider the intent part (denoted by intent(F )) and the extent part (denoted by extent(F )) of the factor F .

3

Related work

The Boolean matrix factorization (or decomposition), also known as the Boolean factor analysis, has gained interest in the data mining community during the past few years.

In the literature, we can find a wide range of theoretical and application

papers about the Boolean factor analysis. The overview of the Boolean matrix theory can be found in [ 8 ]. A good overview from the BMF viewpoint is in e.g. [ 12 ]. For our work is the most important [ 2 ], where were first used formal concepts as factors.

Several heuristic algorithms for the BMF were proposed. In our work we

adopt algorithm GreConD [ 2 ] (originally called Algorithm 2), but there exist several different approaches, which use so-called “tiles” in Boolean data [ 4 ], hyper-rectangles [ 15 ] or which introduce some noise [ 12, 10 ] in Boolean data.

From wide range of applications papers let us mentioned only [13] and [14],

where the BMF is used for solving the Role mining problem.

In the literature, there can be found several methods for the latent factor

analysis of ordinal data and also of multi-relational data [ 9 ], but using these methods for Boolean data has proved to be inconvenient many times.

The BMF of multi-relational data is not directly mentioned in any previous

work. Indirectly, it is mentioned, in a very specific form, in [ 11 ] as Joint Subspace

Matrix Factorization, where there are two Boolean matrices, which both share

the same rows (or columns). The main aim is to find a set of shared factors (factors common for both matrices) and a set of specific factors (factors which are either in first or second matrix, not in both). This can be viewed as particular, very limited setting of our work.

From our point of view are also relevant works [5, 7]. These introduce the

Relational formal concept analysis (RCA), i.e. the Formal concept analysis on

multi-relational data. Our approach is different from the RCA. In our approach, we extract factors from each data table and connect these factors into more general factors. In RCA, they iteratively merge data tables into one in the following way: in each step they computed all formal concepts of one data table and these concepts are used as additional attributes for the merged data table.

After obtaining a final merged data table, all formal concepts are extracted. Let us mention that our approach delivers more informative results than a simple use of BMF on merged data table from RCA, moreover getting merged data table is computationally hard.

4

Boolean factor analysis of multi-relational data

In this section we describe our basic problem setting. We have two Boolean data tables C1 and C2, which are interconnected with relation RC1C2 . This relation is over the objects of first data table C1 and the attributes of second data table C2, i.e. it is an objects-attributes relation. In general, we can also define an objectsobjects relation or an attributes-attributes relation. Our goal is to find factors, which explain the original data and which take into account the relation RC1C2 between data tables.

Definition 1. Relation factor (pair factor) on data tables C1 and C2 is a pair DF1i, F2j E, where Fi1 ∈ F1 and F2j ∈ F2 (Fi denotes set of factors of data table Ci) and satisfying relation RC1C2 .

There are several ways how to define the meaning of “satisfying relation” from Definition 1. We will define the following three approaches (this definition holds for an object-attribute relation, other types of relations can be defined in similar way): – F1i and F2j form pair factor hF1i, F2j i if holds:

\ k∈extent(F1i)

Rk 6= ∅ and

\ k∈extent(F1i)

Rk ⊆ intent(F2j ), where Rk is a set of attributes, which are in relation with an object k. This approach we called narrow (it is analogy of the narrow operator in [ 7 ]). – F1i and F2j form pair factor hF1i, F2j i if holds:  

\ k∈extent(F1i) 



Rk ∩ intent(F1j ) 6= ∅.

We called this approach wide (it is analogy of the wide operator in [7]).

– for any α ∈ [ 0, 1 ], F1i and F2j form pair factor hF1i, F2j i if holds: Tk∈extent(F1i) Rk ∩ intent(F2j )

T k∈extent(F1i) Rk ≥ α.

We called it an α-approach.

Remark 1. It is obvious, that for α = 0 and replacing ≥ by >, we get the wide approach and for α = 1, we get the narrow one.

Lemma 1. For α1 > α2 holds, that a set of relation factors counted by α1 is a subset of a set of relation factors obtained with α2.

We demonstrate our approach to factorisation of mutli-relational Boolean data by a small illustrative example.

Example 1. Let us have two data tables CW (Table 1) and CM (Table 2). CW

represents women and their characteristics and CM represents men and their characteristics.

Moreover, we consider relation RCW CM (Table 3) between the objects of first

the data table and the attributes of the second data table. In this case, it could be a relation with meaning “woman looking for a man with the characteristics”.

Remark 2. Generally, nothing precludes the object-object relation (whose meaning might be “woman likes a man”) and the attribute-attribute relation (whose meaning might be “the characteristics of women are compatible with the characteristics of men in the second data table”).

Factors of data table CW are:

– F1W = h{Abby, Daphne}, {undergraduate, wants kids, is attractive}i – F2W = h{Becky, Daphne}, {athlete, wants kids}i – F3W = h{Abby, Claire, Daphne}, {undergraduate, is attractive}i

Factors of data table CM are:

– F1M = h{Ben, Carl}, {undergraduate, wants kids}i – F2M = h{Adam}, {athlete, is attractive}i – F3M = h{Adam, Carl}, {athlete}i – F4M = h{Dave}, {wants kids, is attractive}i

These factors were obtained via GreConD algorithm from [2]. We have two

sets of factors (formal concepts), first set FW = {F W1 , F W2 , F W3 } factorising data table CW and FM = {F M1 , F M2 , F M3 } factorising data table CM .

Now we use so far unused relation RCW CM , between CW and CM to joint

factors of CW with factors of CM into relational factors. For the above defined approaches we get results which are shown below. We write it as binary relations, j j j i.e F Wi and FM belongs to relational factor hF Wi , FM i iff F Wi and FM are in relation:

F W1 F W2 F W3 F W1 F W2 F W3 × × × × Narrow approach

F M1 F M2 F M3 F M4 0.6-approach F M1 F M2 F M3 F M4 ×

F W1 F W2 F W3 F W1 F W2 F W3 × × × × × Wide approach

F M1 F M2 F M3 F M4 0.5-approach F M1 F M2 F M3 F M4 ×

× × × × ×

The relational factor in form hF Wi , F Mj i can be interpreted in the following ways: – Women, who belong to extent of F Wi like men who belong to extent of F Mj .

Specifically in this example, we can interpret factor hF W1 , F M1 i, that Abby and Daphne should like Ben and Carl. – Women, who belong to extent of F Wi like men with characteristic in intent j . Specifically in this example, we can interpret factor hF W1 , F M1 i, that of FM

Abby and Daphne should like undergraduate men, who want kids.

– Women, with characteristic from intent F Wi like men who belong to extent F Mj . Specifically in this example, we can interpret factor hF W1 , F M1 i, that undergraduate, attractive women, who want kids should like Ben and Carl. – Women, with characteristic from intent F Wi like men with characteristic in j . Specifically in this example, we can interpret factor hF W1 , F M1 i, intent of FM that undergraduate, attractive women, who want kids should like undergraduate men, who want kids.

Interpretation of the relation between F Wi and F Mj is driven by used approach. If we obtain factor hF Wi , F Mj i by narrow approach, we can interpret relation between F Wi and F Mj : “women who belong to F Wi , like men from FjM completely”. For example factor hF W1 , F M1 i can be interpreted: “All undergraduate attractive women, who want kids, wants undergraduate men, who want kids.” If we obtain factor hF Wi , F Mj i by wide approach, we can interpret the relation j : “women who belong to F Wi , like something about the men between F Wi and FM from FjM ”. For example hF W2 , F M1 i can be interpreted: “All athlete woman, who want kids, like undergraduate men or man, who want kids.”

j If we get hF Wi , FM i by α-approach with value α, we interpret the relation j between F Wi and FM as: “women from F Wi , like men from FjM enough”, where α determines measurement of tolerance.

Remark 3. Not all factors from data tables CW or CM must be present in any

relational factor. It depends on the used relation. For example in Example 1 in narrow approach, the factors F M2 , F M3 , F M4 are not involved. In this case, we can add these simple factors to the set of relational factors and consider two types of factors. This factors are not pair factors, but classical factors from CW or CM .

Of course this depends on a particular application.

Remark 4. For one factor F1i from the data table C1, two factors from the data table C2 (for example F j1 and F2j2 ) can satisfy the relation. In this case we can 2 add factor hF1i, F2j1 &F2j2 i, where F2j1 &F2j2 means extent(F2j1 &F2j2 ) = extent(F2j1 ) ∪ extent(F2j2 ) intent(F2j1 &F2j2 ) = intent(F2j1 ) ∩ intent(F2j2 ), instead of hF1i, F2j1 i and h 1

F i, F2j2 i to the relation factor set (in the case, that we consider an object-attribute relation). For example, by using 0.5-approach in Example 1, we get relational factors h{Abby, Daphne}, {undergraduate, wants kids, is attractive}i,

h{Ben, Carl}, {undergraduate, wants kids}i and and h{Abby, Daphne}, {undergraduate, wants kids, is attractive}i,

h{Dave}, {wants kids, is attractive}i .

This factors can be replaced with factor

h{Abby, Daphne}, {undergraduate, wants kids, is attractive}i, h{Ben, Carl, Dave}, {wants kids}i .

Remark 5. Another, simpler approach to multi-relational data factorization is

such, that we do factorization of the relation RC1C2 . This is correct because we can imagine the relation between data tables C1 and C2 as another data table.

For each factor, we take the extent of this factor and compute concept in C1,

which contains this extent. Similarly for intents of factors and concepts in C2.

For example one of the factors of RCW CM from Example 1 is:

h{Becky, Daphne}, {athlete, wants kids}i.

Relational factor computed from this factor will be

h{Becky, Daphne}, {athlete, wants kids}i, h{Carl}, {athlete, undergraduate, wants kids}i .

This approach seems to be better in terms of that we get pair of concepts for

every factors, but we do not get an exact decomposition of data tables C1 and

C2. Moreover this approach can not be extended to n-ary relations.

4.1

n-tuple relational factors, n-ary relations

Above approaches can be generalized for more than two data tables. In this generalization, we do not get factor pairs, but generally factor n-tuples. Now we extend Definition 1 to general definition of relational factor.

Definition 2. Relation factor on data tables C1, C2, . . . Cn is a n-tuple F1i1 , F2i2 , . . . Fnin , where Fjij ∈ Fj where j ∈ {1, . . . , n} (Fj denotes set of factors of data table Cj ) and satisfying relations RClCl+1 or RCl+1Cl for l ∈ {1, . . . , n − 1}.

We considered only binary relations between data tables, for which holds,

that there exists only one relation interconnecting data tables Ci and Ci+1 for i ∈ {1, . . . , n − 1}. We left more general relations into the extended version of this paper. Let us mentioned, that this generalization of our approach is possible in the opposite of Remark 5. We show n-tuple relational factors on example.

Example 2. Let data table CP (Table 4) represents people and their characteris

tic, CR (Table 5) represents restaurants and their characteristics and CC (Table

6) represents which ingredients are included in national cuisines.

Adam Ben Carol Dale Emily Frank Gabby ltbgeea it food seum ttounm lbam lievo ievn srebh seeceh srhooummitsceohp irce febe rkpo ltrypou tsbbooahoom tun lrad itrbba isveonn iissedn rcon ltsea/paoodn ttoapo tsrypa ve fru shfi sea leg 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Relation RCPCC (Table 7) represents relationship “person likes ingredients”

and relation RCRCC (Table 8) represents relationship “restaurant cooks national cuisine”. In Tables 9, 10, 11, we can see factors of data tables CP, CR and CC, respectively. Restaurant 1 × Restaurant 2 × × Restaurant 3 Restaurant 4 Restaurant 5 × × × × × × ×

× × ×

× × × × × × ×

× × ×

One of the relational factors, which we get by 0.5-approach, is hFP1 , FC11, FR3 i and could be interpreted as “men would enjoy eating in luxury restaurants where F 3 , FC2 , FR1 i and could be interpreted the meals are cheap”. Another factor is h P as “women enjoy eating in ordinal cheap restaurants”.

Representation of connection between factors

We can represent the relational factors via graph (n-partite). See Figure 1, which

presents the results from the previous example. Each group of nodes (FPi , F Ci , F Ri) represents factors of a specific data table. Between two nodes, there is an edge iff factors representing nodes satisfy the input relation. Relational factor is path between nodes, which include at most one node from each group. For example,

FP2 , FC3 , FR1 is a relational factor because there is an edge between nodes FP2 and FC3 and between FC3 and FR1 .

FP5 FP4 FP3 FP2 FP1 FC17 FC16 FC15 FC14 FC13 FC12 FC11 FC10 FC9 FC8 FC7 FC6 FC5 FC4 FC3 FC2 FC1 F R3 F R2 F R1

Conclusion and Future Research

In this paper we present the new approach to BMF of multi-relational data, i.e.

data which are composed from many data tables and relations between them.

This approach, as opposed from to BMF, takes into account the relations and uses these relations to connect factors from individual data tables into one complex factor, which delivers more information than the simple factors.

A future research shall include the following topics: generalization multirelational Boolean factorization for ordinal data, especially data over residuated lattices. Design an effective algorithm for computing relational factors. Develop new approaches for connecting factors which utilize statistical methods and last but not least drive factor selection in the second data table, using information about factors in the first one and relation between them, for obtaining more relevant data.

Acknowledgment We acknowledge support by the Operational Program Education for Competitiveness Project No. CZ.1.07/2.3.00/20.0060 co-financed by the European Social Fund and Czech Ministry of Education.

References

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

2. Belohlavek R. , Vychodil V. : Discovery of optimal factors in binary data via a novel method of matrix decomposition . J. Comput. Syst. Sci . 76 ( 1 ): 3 - 20 , 2010 .

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

4. Geerts F. , Goethals B. , Mielika¨inen T.: Tiling databases , Proc. Discovery Science 2004 , pp. 278 - 289 .

5. Hacene M. R. , Huchard M. , Napoli A. , Valtechev P. : Relational concept analysis: mining concept lattices from multi-relational data . Ann. Math. Artif. Intell . 67 ( 1 )( 2013 ), 81 - 108 ,.

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

7. Huchard M. , Napoli A. , Rouane H. M. , Valtchev P.: A proposal for combining formal concept analysis and description logics for mining relational data . ICFCA 2007 .

8. Kim K.H. : Boolean Matrix Theory and Applications . Marcel Dekker, New York, 1982 .

9. Lippert , C. , Weber , S. H. , Huang , Y. , Tresp , V. , Schubert , M. , and Kriegel , H.- P.: Relation-prediction in multi- relational domains using matrix-factorization . In NIPS 2008 Workshop on Structured Input - Structured Output, NIPS , 2008 .

10. Lucchese C. , Orlando S. , Perego R. : Mining top-K patterns from binary datasets in presence of noise , SIAM DM 2010 , pp. 165 - 176 .

11. Miettinen P. : On Finding Joint Subspace Boolean Matrix Factorizations . Proc. SIAM International Conference on Data Mining (SDM2012) , pp. 954 - 965 , 2012 .

12. Miettinen P. , Mielika¨inen T., Gionis A. , Das G. , Mannila H. : The discrete basis problem , IEEE Trans. Knowledge and Data Eng . 20 ( 10 )( 2008 ), 1348 - 1362 .

13. Nau D.S. , Markowsky G. , Woodbury M.A. , Amos D .B.: A mathematical analysis of human leukocyte antigen serology . Math Bioscience 40 ( 1978 ), 243 - 270 .

14. Vaidya J. , Atluri V. , Guo Q. : The role mining problem: finding a minimal descriptive set of roles . In: Proc. SACMAT 2007 , pp. 175 - 184 , 2007 .

15. Xiang Y. , Jin R. , Fuhry D. , Dragan F. F. : Summarizing transactional databases with overlapped hyperrectangles , Data Mining and Knowledge Discovery 23 ( 2011 ), 215 - 251 .