On the Use of F-transform on the Reduction of Concept Lattices

On the Use of F-transform on the Reduction of Concept Lattices Petra Hod´akov´a and Nicol´as Madrid University of Ostrava, Centre of Excellence IT4Innovations, Institute for Research and Applications of Fuzzy Modeling, 30. dubna 22, 701 03 Ostrava 1, Czech Republic {nicolas.madrid,petra.hodakova}@osu.cz Abstract. In this paper, we show that F-transform can be used to reduce relational databases. Subsequently, we show that the respective concept lattice is reduced significantly as well. Moreover, we present a clarifying example of the procedure. Keywords: F-transform, Fuzzy Sets, Fuzzy Concept Analysis, Knowledge Reduction. 1 Introduction Fuzzy Formal Concept Analysis deals with the processing of imprecise knowledge in information systems [2, 3]. In this theory, the information of a relational databases is represented in terms of a complete lattice where its elements are called concepts. However, despite the information represented by the concept lattice is valuable, the complexity and the size (which increases exponentially with respect to the size of the relational database) makes the use of this theory impractical in many applied tasks. For this reason, recent approaches have dealt with Knowledge Reduction in relational databases to simplify the formal concept analysis of them [1]. On the other hand, F-transforms [4] is a theoretical tool that has shown its e↵ectiveness on representing the information of signals (like temporal series, images, etc.) to a vector of few components. This paper applies F-transforms (based on residauted lattice) to Knowledge Reduction. Specifically, we begin by showing that objects (or attributes) in a relational database can be grouped in a new set of objects (or attributes). Then, we transfer the information of the original database to another where objects are given by the grouping previously mentioned. The transfer of information is given by F-transforms and therefore, there are two possible new relational databases. This paper has the following structure. In Section 2 we recall briefly the theories of fuzzy property-oriented concept lattices and F-transforms. Then, in Section 3 we describe the reduction of relational tables by means of F-Transforms. Moreover, we illustrate the consequences of the reduction in concept lattices with an example. Finally, in Section 4 we present conclusions and future work. L. K´oczy, J. Medina (Eds): ESCIM 2015. 978-84-608-2823-5 226 2 Petra Hod´akov´a and Nicol´as Madrid 2 Preliminaries 2.1 F-transforms on residuated lattices In this section, we briefly recall the basic definitions and the main principles of F-transforms based on operations of a residuated lattice [4]. Let (L, ,&,!) be a residuated lattice. A fuzzy partition of a finite set Uis a set of L-fuzzy sets on UA 1,...,Anfulfilling the covering property namely, for all x2Uthere exists k2{1,...,n}such that Ak(x)>0.The membership functions Ak(x), k=1,...,n are called the basic functions. Definition 1. Let f:U!Lbe a function and A1,...,An,withn|U|,be basic functions which form a fuzzy partition of U.Wesaythatthen-tupleofreal numbers F" n[f]=[F" 1,...,F" n]is the (direct) F"-transform of fw.r.t. A1,...,An if F" k=_ x2U (Ak(x)&f(x)).(1) Moreover, we say that the n-tuple of real numbers F# n[f]=[F# 1,...,F# n]is the (direct) F#-transform of fw.r.t. A1,...,Anif F# k=^ x2U (Ak(x)!f(x)).(2) The elements F" 1,...,F" nand F# 1,...,F# nare called components of the F"-transform and F#-transform, respectively. The following lemma ([4]) shows that the components of the F"-transform (F#-transform) are lower mean values (upper mean values) of an original function which give least (greatest) element to certain sets. Lemma 1. Let f:U!Lbe a function and A1,...,An,withn|U|,bebasic functions which form a fuzzy partition of U. Then the k-th component of the F"-transform is the least element of the set Sk={a2L|A k(x)(f(x)!a)for all x2U} and the k-th component of the F#-transform is the greatest element of the set Tk={a2L|A k(x)(a!f(x)) for all x2U} where k=1,...,n. 2.2 Fuzzy property-oriented concept lattices In this section we recall briefly a simplification of property-oriented concept lattices introduced in [2, 3]. So, because of the lack of space, here we restrict to residuated lattices instead of adjoin triples. The notion of fuzzy property-oriented context is defined below. 227 On the Use of F-transform on the Reduction of Concept Lattices 3 Definition 2. Let (L, ,&,!)be a residuated lattice. A context is a tuple (A, B, R)such that Aand Bare non-empty sets (usually interpreted as attributes and objects, respectively), Ris an L-fuzzy relation R:A⇥B!L. From now on, we fix a context (A, B, R). The mappings "⇧:LB!LAand #N:LA!LBare defined, for g2LBand f2LAas, g"⇧and f#N,where g"⇧(a)= _ b2B R(a, b)&g(b) f#N(b)= ^ a2A R(a, b)!f(a) It is not difficult to prove that ("⇧,#N) forms an isotone Galois connection (also known as adjunction) and, therefore, "⇧#N:LB!LBis a closure operator and #N"⇧:LA!LAis an interior operator. A concept is a pair of mappings hg,fi,withg2LB,f 2LA, such that g"⇧=fand f#N=g,whichwillbe called fuzzy property-oriented concept. In that case, gis called the extent and f, the intent of the concept. The set of all these concepts will be denoted as F⇧N. Definition 3. The associated fuzzy property-oriented concept lattice to the context (A, B, R)is defined as the set F⇧N={hg,fi2LB⇥LA|g"⇧=fand f#N=g} in which the ordering is defined by hg1,f 1ihg2,f 2ii↵g12g2(or equivalently f11f2). 3 Reducing the size of Relational Tables. Throughout this section we consider a frame (A, B, R) and a residuated lattice (L, ,&,!). The idea underlying in the reduct is the creation of two smaller relational tables R"and R#that keep as much information from Ras possible. In order to reduce the size of the table is needed to reduce either the number of attributes or the number of objects. In this paper we focus on objects. In this way, we define a new set of objects Bthat can be considered as a set of fuzzy sets that group objects according to certain attributes in A. For instance, consider a relational table where objects are people and attributes are physical features of them. Then, we could group people according to their high and then, to define the following set of “new” objects {B1=V erySmall, B2=QuiteSmall, B3= Medium, B4=QuiteTall, B5=VeryTall}. To conclude the reduction, we only need to define the relations R"and R#between the new set of objects and the original set of attributes. For such a task we consider direct F-transforms. In this framework, each basic function from the chosen fuzzy partition determines a new object and the value assigned to it by the direct F-transform determines the value of the relation. 228 4 Petra Hod´akov´a and Nicol´as Madrid To define the basic functions (and then also the set of new objects) let us consider firstly, a fuzzy partition of Lgiven by fuzzy sets {Lk:k2{1,...,n}} and secondly, a subset of attributes A✓A. Then the fuzzy partition B= {Bka :k2{1,...,n}and a2A}of Bis defined by Bka(b)=Lk(R(b, a)),b2B. (3) Note that the fuzzy partition Bgroups original objects in fuzzy sets according to their relation with attributes in A. Moreover, note the number of basic functions (i.e., the number of new objects) is k·|A|. So the size of the new set of objects depends on the number of attributes considered to define the partition. Once the fuzzy partition is fixed, we can define the following two L-fuzzy relational tables R"and R#between B={Bk,a:k2{1,...,n}and a2A}and Aas follows: R":B⇥A!L (Bk,a,a)7! _ b2B Bka(b)&R(a, b) R#:B⇥A!L (Bk,a,a)7! ^ b2B Bka(b)!R(a, b) (4) Note that original objects are used to define the values of the new ones. Finally, the reduction of the concept lattice given by the original frame (A, B, R) is the pair of concept lattices associated to the frames (A, B,R") and (A, B,R#). Below we show how the procedure works in a simple example. HighPower BigSpace HighConsume Expensive Sport F amiliar b11 0.2 1 0.8 1 0 b21 1 0.8 1 0.6 1 b30.6 0.8 0.4 0.6 0.2 0.6 b40.8 0.6 0.6 0.6 0.6 0.6 b50.6 0.4 0.2 0.6 0.2 0.2 b60 0.2 0 0.2 0 0 b70.8 0.2 0.8 0.8 0.8 0 b81 1 1 1 0 1 b90.6 1 0.4 0.6 0 1 b10 0.6 1 0.6 0.6 0 1 b11 0.6 0.6 0.4 0.4 0 0.6 b12 0.2 0.4 0.4 0.2 0 0.2 b13 0.8 0 0.8 1 0.8 0 Fig. 1. A car relational database. 229 On the Use of F-transform on the Reduction of Concept Lattices 5 Example 1. Let us consider the L-relational table in Figure 1 that relates types of cars (objects) with features (attributes). For the sake of simplicity, let Lbe the unit interval [0,1] represented by finite set L={0,0.2,0.4,0.6,0.8,1}, and the adjoint pair considered for the reduction and the construction of the concept lattice is the one given by the G¨odel connectives. Let us consider the partition {L1,L2}of Lgiven by: x0 0.2 0.4 0.6 0.8 1 L1(x) 0 0.2 0.4 0.6 0.8 1 x0 0.2 0.4 0.6 0.8 1 L2(x) 1 0.8 0.6 0.4 0.2 0 Now, for the sake of simplicity let us consider just the attribute Familiar 2A to make the reduct. Then, from Equation (3), we have that the partition of the set of objects Bwith respect to the attribute Familiar and the partition {L1,L2} of Lis given by the following two fuzzy sets b b1b2b3b4b5b6b7b8b9b10 b11 b12 b13 B1a(b) 0 1 0.6 0.6 0.2 0 0 1 1 1 0.6 0.2 0 b b1b2b3b4b5b6b7b8b9b10 b11 b12 b13 B2a(b) 1 0 0.4 0.4 0.8 1 1 0 0 0 0.4 0.8 1 Note that partitions B1aand B2aabove represent the fuzzy sets of cars that are familiar and non familiar, respectively. Thus, it has sense that the two new objects in the new tables are denoted by FamCars and NonFamCars.The new relational tables are given by F-transforms (4) as follows R"HighPower BigSpace HighConsume Expensive Sport FamCars 1 1 0.8 1 0.6 NonFamCars 1 0.4 1 1 1 R#HighPower BigSpace HighConsume Expensive Sport FamCars 0.6 1 0.4 0.6 0 NonFamCars 0 0 0 0 0 The tables above can be interpreted as follows. Tables R"and R#represent the possibility and necessity, respectively, of a familiar car (in some degree) to have a certain attribute. So R"(F amCars, a) and R#(FamCars, a)represent an upper and a lower bound, respectively, of the value R(b, a) for any familiar car b2B, i.e., R"(FamCars, a)B1a(b)&R(b, a) and R#(F amCar, a) B1a(b)!R(b, a). It is interesting to mention that from the interpretability above, we can infer from the tables R"and R#that a familiar car must have a big space because R"(FamCars, BigSpace)=R#(FamCars, BigSpace) = 1. Moreover, the familiar cars are quite powerful and expensive as well as R#(FamCars, HighPower)= R#(FamCars, Expensive)=0.6. The concept lattice of the original relational table of Example 1 has 302 concepts and it is given by the following Hasse diagram 230 6 Petra Hod´akov´a and Nicol´as Madrid However, the concept lattices of the tables reduced by our procedure have only 5 and 6 concepts, respectively. 4 Conclusion and Future Works In this paper we have presented the reduction of relational tables aimed to keep as much information from the original table as possible. Our future work is to apply the reduct based on the ordinary F-transforms and measure, determine and/or bound the information which is on one hand lost by the reduction and on the other hand kept by the reduction. Acknowledgments. The research was supported by the European Regional Development Fund by projects (CZ.1.05/1.1.00/02.0070) and (TIN12-39353C04-04). Aditionally, we want to thank Eloisa Ram´ırez-Poussa for her help. References 1. M E. Cornejo, J. Medina, E. Ram´ırez-Poussa. Attribute reduction in multi-adjoint concept lattices. Information Sciences, 294: 41-56, 2015. 2. J. Medina. Towards multi-adjoint property-oriented concept lattices. Lecture Notes in Artificial Intelligence, 6401:159–166, 2010. 3. J. Medina. Multi-adjoint property-oriented and object-oriented concept lattices. Information Sciences, 190:95–106, 2012. 4. I. Perfilieva. Fuzzy transforms: Theory and applications. Fuzzy Sets and Systems, 157: 993–1023, 2006. 231