Formal Concept Analysis as a Framework for Business Intelligence Technologies II

Abstract

Formal concept analysis (FCA) with measures can be seen as a framework for Business Intelligence technologies. In this paper we introduce new ideas about an OLAP cube. We take a focus on a highdimensional OLAP cube reduction and on a hierarchy of attributes in an OLAP cube. This paper continues with results proposed in [9] and for more details we will refer on it. The paper is structured as follows: In "Preliminaries" the fundamentals of FCA with measures are described, the formal de nition of the OLAP cube is shown. "Compressing High-Dimensional OLAP Cube Using FCA With Measures" shows an e cient reduction of an OLAP space using FCA with measures. In "Attribute Hierarchy In OLAP And In FCA With Measures" we discuss di erent types of hierarchies in OLAP. This paper is supplemented with comprehensive examples. The nal part summarizes the results.

Introduction

De nition 1 (Measure of Object and Attribute [ 9 ] ). A Measure of the object is mapping : X ! R+ and a Measure of the attribute is mapping : Y ! R+. concept hA; Bi 2 B (X; Y; I) De nition 2 (Value of Extent and Intent [ 9 ] ). The Value of extent is mapping v : AB(X;Y;I) ! R+de ned as v (A) = (x), where is either x2A the symbol for the sum (the "sum" operation) or the symbol for cardinality jAj or the arbitrary aggregation function . A is an extent of the formal concept hA; Bi 2 B (X; Y; I). Similarly, the value of the intent is mapping w : BB(X;Y;I) ! R+ de ned as w (B) = (y), where B is an intent of the formal y2B

The Database table is a relation r on the relation scheme R = fA1; A2 : : : ; Ang de ned as a set of mappings ft1; t2 : : : ; tmg from R to D where D is a set of all D - domains of attributes A, n is the number of the columns and m the number of rows in a database table (see [ 4 ]). Domains in D are divided into the two groups: Hk 2 H- dimensions and Ms 2 M - measures, where k 2 [1; jHj], s 2 [1; jMj] and Ms R+).

De nition 3 (OLAP Cube space, OLAP Cube [ 9 ]). The space for the OLAP cube is a cartesian product C = LH1 LHk LHjHj , where L = f0; 1g. The OLAP cube is a mapping : C ! R+ and is de ned as m (h1; : : : ; hn) =

i=1 symbol stands for the sum operator , the cardinality operator jj or the arbitrary aggregation operator and jHj is the number of OLAP cube dimensions. ti(Ms) such that fti(Aj )g hj for all j 2 [1; jHj], where the 3

Compressing High-Dimensional OLAP Cube Using FCA With Measures In the previous paper [ 9 ] we have shown, that FCA with measures can be seen as a generalized OLAP. OLAP uses data which are organized in dimensions. As a direct consequence is, that the scaled attributes (using a nominal scale [ 1 ]) from one domain are mutually exclusive. FCA with values enables to analyze the data which are not organized in dimensions, thus those which are independent (see the example with cars and components taken from [ 9 ] shown in Table 4). This fact means, that we can work with a relational (binary) data as well. When the attributes with a binary domain are used, usually there is a relatively big amount of such attributes. It implies a high-dimensional OLAP cube. Recall from [ 9 ], that the size of an OLAP cube is (jH1j + 1) (jHjHjj + 1). The expression "+1" means, that using the domain H1 = fBM W; SKODA; F IAT g we consider such situation, when no attribute is selected. In a binary case we have two possibilities only (an attribute is selected or not), so a space of such cube will be 2jHj, where jHj is a number of domains (all domains are binary in this case). Hence, the space of the OLAP cube is exponential wrt. number of attributes. FCA with measures enables to compress such exponential space. Consider Y as a set of attributes in FCA. Number of formal concepts (which contains intents, closed sets of attributes) is usually signi cantly lower than a powerset 2Y , because a real dataset is usually sparse. Using FCA with measures we can replace OLAP cube with a concept lattice with values and we do not loose any information comparing to OLAP. This compression can be used also for the attributes with a many-valued domain. In Figure 1 the example of such compression is show. From the database table (i), OLAP cube is computed with the space (3 + 1) (2 + 1) = 12 cells (ii). In (iii) the formal context (using the nominal scaling) is shown and nally in (iv) the concept lattice is depicted. The concept lattice has only 10 concepts with the values (1 trivial concept is just technical, with no value). Two OLAP cube cells (in (ii) are highlighted using gray color) are missing in the compressed concept lattice. Consider the well known dataset "Mushroom", which contains 23 original attributes (22 + 1 class considered as an attribute) where a cardinality of the domains is between 2 and 12. Using a formula for the OLAP space we get 7; 36 1016 of cells in the OLAP cube. Comparing to the amount of the formal concepts, which is 2; 39 1005 we get the space reduced approximately by 1012. In the Table 1 we can see the original OLAP spaces comparing to the reduced ones using ve well-known datasets (see the highlighted items with a signi cant space compression).

TradeMark Country Price in 000 EUR

BMW Germany 30

BMW France 35

SKODA Germany 20

SKODA France 25

FIAT France 13

(i) Database

All trademarks

FIAT

SKODA

BMW

All countries France Germany 123 73 50 13 13 0 45 25 20 65 35 30 (ii) OLAP Cube y . A rranC BWM SODK ITFA reanGm creanF Price in 000 EUR Remark 1: Not the whole OLAP cube is presented to a user and also not the whole lattice with values is presented to user. The data are stored using the di erent way, but the presentation to user can be the same (e.g. using pivot tables, pivot charts or other repost).

Remark 2: Not the whole OLAP cube is materialized in a real application. However a compression ratio is calculated from the whole OLAP cube comparing to compressed one (e.g. see [13]).

In [13] there were presented another solution how to compress OLAP cube, thus using a Dwarf Cube. The authors of [13] claim, that a Petabyte 25-dimensional cube was shrunk this way to a 2.3GB Dwarf Cube. For a detailed description of Dwarf cube we refer to [13]. Here we only compare our approach using a toy example from [13]. In Table 2 data for OLAP are shown and in Table 3 a comparison of tuples is shown for two OLAP representations (Dwarf and FCA with measures). In Table 3 we can see, that Dwarf Cube contains more tuples than

Store Customer Product Price

S1 C2 P2 70 S1 C3 P1 40 S2 C1 P1 90 S2 C1 P2 50

Table 2. Data for OLAP concept lattice. But this is only a toy example. Our hypothesis is, that FCA with measures contains a minimal possible amount of all non-redundant tuples for the OLAP cube compression. A formal proof as well as an experimental study will be part of our future research.

Attribute Hierarchy In OLAP And In FCA Measures

With

In the paper [ 9 ] we claim, that FCA with measures is a generalization of OLAP cube. This claim however excludes the case, when a hierarchy of attributes in OLAP is de ned. Attributes in a dimension can be split into smaller parts, e.g. in the dimension Date we can consider the hierarchy Y ear > M onth. In FCA with measures we can consider the dimension "Date" and it can be nominally scaled into attributes Y ear and M onth as well. Consider the following Figure 2. When the original table (i) is scaled (ii) and formal concepts are computed, we get the concepts with the intent fJ ang and fF ebg. Such intents can generally be used e.g. for analyzing the seasonality, however using the hierarchy Y ear > M onth such intent is not interesting (in this case it is a total amount of all cars sold in January regardless of the year). All other formal concepts are reasonable (i.e. total amount in one year or total amount in one month of the particular year). There are two possibilities how to deal with such problem. The rst approach

Obj. Date

1 Jan, 2011 2 Feb, 2011 3 Jan, 2012 4 Feb, 2012

(i) Original data is just to scale the original data from (i) using a hierarchy (iii). Such scaling directly enables to avoid undesired formal concepts with intents such as fJ ang and fF ebg (Note: The undesired formal concept with the intent all attributes technically remains just to form a lattice).

Another option is to use AD formulas proposed in [11, 12]. An AD formula over a set Y of attributes is an expression A v B, where A; B Y . A v B is true in K Y if whenever A\K 6= ;, then B \K 6= ;. For a given set T of AD formulas over Y and a formal context hX; Y; Ii we get the concept lattice constrained by T , which is denoted by BT (X; Y; I). Such lattice consists of formal concepts of hX; Y; Ii in which all AD formulas from T are true. For more details we refer to [11, 12]. In our example we can use AD formula fJ an; F ebg v f2011; 2012g, which means: whenever we have a month in an intent of a formal concept (here J an or F eb), we need also to have a year in intent (here 2011 and 2012). In other words, a year is hierarchically higher than a month. Constraining the original concept lattice by AD formula, undesired formal concepts will be avoided. A formal concept analysis with measures using AD formula can be seen as a generalization of OLAP with hierarchies.

In [14] there were presented some types of a hierarchy used in OLAP cube, but not all types of a hierarchy can be de ned using AD formula. In this paper a preliminary results are presented (all examples of hierarchies are taken from [14]) : 1. simple hierarchies (represented by a tree) (a) symmetric hierarchy: fDepartment Ag w fCategory 1g , fDepartment Ag w fCategory 2g, fCategory 1g w fP roduct 1g, fCategory 1g w fP roduct 2g, fCategory 2g w fP roduct 3g, fCategory 2g w fP roduct 4g (b) asymmetric hierarchy: fbank Xg w fbranch 1g , fbank Xg w fbranch 2g, fbank Xg w fbranch 3g, fbranch 1g w fagency 11g, fbranch 1g w fagency 12g, fbranch 3g w fagency 31g, fbranch 3g w fagency 32g, fagency 11g w fAT M 111g, fagency 11g w fAT M 112g (c) generalized hierarchy: farea Ag w fbranch 1g, farea Ag w fbranch 2g, fbranch 1g w fclass 1g, fclass 1g w fprof ession Ag, fclass 1g w fprof ession Bg ,fprof ession Bg w fcustomer Xg, fprof ession Bg w fcustomer Y g, fbranch 1g w fsector 1g, fsector 1g w ftype Ag, fsector 1g w ftype Bg, ftype Bg w fcustomer Zg, ftype Bg w fcustomer Kg 2. non-strict hierarchy: fdivision Ag w fSection 1; Section 2; Section 3g, fSection 1; Section 2; Section 3g w femployee Xg This approach we can use also on for attributes which are not organized in dimensions by telling which group of independent attributes is more important than other group. In the example with cars (see the Tables 4 and 5) there are attributes Air Conditioning (AC), Airbag (AB), Antilock Braking System (ABS), Tempomat (T M P ), Extra Guarantee (EG) and Automatic Transmission (AT ).We can say, that fAB; ABSg are more important (because of security) than fAC; T M P; EG; AT g (which are used just for a higher comfort). AD formula in this case is fAB; ABSg v fAC; T M P; EG; AT g, which means, that we will care about values of formal concepts (e.g. the T otal P rice) only for such cars, which posses at least one of the security attributes AB or ABS (in the Table 5 labeled by ). ).

Car1 Car2 Car3 Car4 Car5 Car6 Car7 Car8 Car9 Car10 Car11 Car12 Car13 Car14 Car15 Car16 Car17 Car18 Car19 Car20

S P C B B M G T A A A T E A :1 :2 :3 :4 :5 :6 (X) = Price in EUR 16 000 12 000 14 000 16 000 12 000 12 000 12 000 14 000 16 000 12 000 12 000 14 000 16 000 16 000 14 000 12 000 12 000 16 000 16 000 14 000 FCA with measures as a new area is just on the beginning. Based on our preliminary research it appears, that FCA with measures can signi cantly reduce a space of OLAP cube. FCA with measures can also be used as a generalization of OLAP even di erent hierarchy of attributes is included. In the future research we will focus on the detailed experimental research, where we will compare other reducing techniques of an OLAP cube space with our approach. secure cars 11. Belohlavek R., Sklenar V.: Formal concept analysis constrained by attributedependency formulas. In: B. Ganter and R. Godin (Eds.): ICFCA 2005, Lect. Notes Comp. Sci. 3403, pp. 176{191, Springer-Verlag, Berlin/Heidelberg, 2005. 12. Belohlavek R., Vychodil V.: Formal concept analysis with background knowledge: attribute priorities. IEEE Trans. Systems, Man, and Cybernetics, Part C Volume 39 Issue 4, July 2009, pp. 399{409. DOI: 10.1109/TSMCC.2008.2012168. 13. Sismanis Y., Deligiannakis A., Roussopoulos N., Kotidis Y.: Dwarf: Shrinking the petacube Proceedings of the 2002 ACM SIGMOD international conference on Management of data, p.464-475 14. Malinowski E., Zimanyi E. : Hierarchies in a multidimensional model: From conceptual modeling to logical representation. Data & Knowledge Engineering 59.2 (2006): 348-377)

References

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

2. Codd E.F. , Codd S.B. , and Salley C.T.: Providing OLAP ( On-line Analytical Processing) to User-Analysts: An IT Mandate Codd & Date ( 1993 )

3. Wang Z. , Klir G. : Generalized measure theory , Springer, New York, 2009

4. Maier D.: The theory of relational databases , Computer Science Press, Rockville, 1983

5. Kuznetsov S. D. , Kudryavtsev A. : A mathematical model of the OLAP cubes , Programming and Computer Software , 2009 , Vol. 35 , No. 5 , pp. 257 { 265 . Pleiades Publishing , Ltd., 2009 .

6. Calvo T. , Kolesarova A. , Komorn kova M. , Mesiar R . Aggregation operators: Properties, classes and construction methods Aggregation Operators: New Trend and Applications , p. 3 - 106 , Eds: Calvo T., Mayor G. , Mesiar R. , Physica Verlag, (Heidelberg 2002 )

7. Belohlavek R. , Vychodil V. : Background Knowledge in Formal Concept Analysis: Constraints via Closure Operators . ACM SAC 2010 , 1113 { 1114 .

8. Belohlavek R. , Vychodil V. : Formal concept analysis with constraints by closure operators . In: H. Scharfe , P. Hitzler , and P. Ohrstrom (Eds.): Proc. ICCS 2006, Lecture Notes in Arti cial Intelligence 4068 , pp. 131 - 143 , Springer-Verlag, Berlin Heidelberg, 2006 .

9. Macko J. : Formal Concept Analysis as a Framework for Business Intelligence Technologies . In: F. Domenach , D.I. Ignatov , and J. Poelmans (Eds.): ICFCA 2012 , LNAI 7278, Springer, Heidelberg, 2012 , pp. 195 - 210 .

10. Kanovsky J. , Macko J.: ConSeQueL - SQL Preprocessor Using Formal Concept Analysis with Measures CUBIST 2012 workshop