A Tool-Based Set Theoretic Framework for Concept Approximation Zoltán Csajbók1 and Tamás Mihálydeák2 1 Department of Health Informatics, Faculty of Health, University of Debrecen, Sóstói út 2-4, H-4400 Nyı́regyháza, Hungary csajbok.zoltan@foh.unideb.hu 2 Department of Computer Science, Faculty of Informatics, University of Debrecen Egyetem tér 1, H-4032 Debrecen, Hungary mihalydeak.tamas@inf.unideb.hu Abstract. Modelling positive and negative knowledge has a long-stand- ing tradition in Formal Concept Analysis. To approximate concepts we propose a tool-based set theoretic partial approximation framework in which positive features and their negative counterparts of observed ob- jects can be approximated simultaneously. Key words: Concept approximation, positive-negative knowledge, rough set theory, partial approximation framework 1 Introduction Modelling of learning from positive and negative examples has a long-standing tradition in machine learning, for a brief historical survey see, e.g. [16]. A possible model in terms of Formal Concept Analysis was described in [10, 15]. The idea of knowing negatively was introduced explicitly by M. Minsky in [19]. Negative knowledge has a number of beneficial effects in professional con- texts which are discussed in detailed, e.g. in [12, 19]. The adjectives ‘positive’ and ‘negative’ do not imply a valuation per se. ‘Positive’ knowledge is not good, ad- vantageous or benign, whereas ‘negative’ knowledge is not bad, disadvantageous or malign in and of itself. Both positive and negative knowledge have procedural [19] and declarative aspects [23]. A procedural aspect of positive and negative knowledge can be para- phrased as ‘to know what to do’ and ‘to know what not to do’ resp., whereas a declarative aspect as ‘to know what one knows’ and ‘to know what one does not know’ resp. In addition, both positive and negative knowledge have two different degrees of knowing or not-knowing. Positive knowledge is informed (uninformed) when one is (not) aware of his/her own relevant knowledge. Negative knowledge is informed (uninformed) when one is (not) aware of his/her own lack of rele- vant knowledge. Our discussion deals with the declarative aspect of positive and negative knowledge and informed way of knowing/not-knowing. 54 Z. Csajbók et al. In our approach, first, we consider a class of objects which is modelled as an abstract set, called the universe of discourse. We assume that a concept is defined over the universe as a subset. In real life the concepts are usually ex- pressed in natural language and so their exact definition cannot be given. The concept approximation is a fundamental problem in artificial intelligence in order to be able to solve real-world problems [17, 22, 31]. A possible way to approx- imate concepts is to induce their approximations from available experimental (observed, measured) data which is also modelled as subsets over the universe [29–31]. Concepts are generally rough, whereas measurements are always crisp. It is also assumed that we have some well-defined, decidable features with which an observed object possesses or not. These features assign crisp subsets within the universe. In other words, we model an object of interest as a member of an abstract set, called the universe, and its property ‘it possesses a feature’ as ‘it is the element of a crisp subset of the universe’. In practice, a concept, of course, cannot be specified completely over the universe. Instead, two relevant sample groups of objects can be established de- termined by our currently available and necessarily constrained knowledge: a group of which members characteristically possess some features concerning the concept in question, and another group of which members do not substantially possess the same features. Both groups correspond two crisp subsets of the uni- verse. They are disjoint, and, in general, the union of them does not add up to the whole universe. For obvious reasons, the former can be marked with the adjective positive and called the positive sample set, whereas the latter with negative and called the negative sample set. Moreover, in real life, a feature of objects cannot be observed directly as well. We need tools at our disposal with which we are able to measure one or more constituents of a feature which are called properties. For instance, let us say that we observe velocity (feature) of cars (objects). Velocity is a vector quantity with speed and direction. They are two properties of velocity which can be measured simultaneously and both of them can be expressed numerically. And so, a car is modelled as a member of an abstract set, the universe, and its velocity as it is a member of intersection of two subsets of cars with given speed and given direction (tools) which were measured at the same time. It is assumed that we are able to judge easily and unambiguously whether an object possesses a property ascertained by a tool or not. It is expected that tools can be used simply and quickly. The objects classified by a tool can be modelled as a crisp subset of the universe. With a slight abuse of terminology, this subset is also simply called tool. Different tools form different subsets, but they are not necessarily disjoint. Intersections of not disjoint tools are also viewed as tools. The complement of a tool is not necessarily a tool at the same time. In practice, there are properties which can be measured but their counterparts cannot. For instance, a given disease can be diagnosed but the health cannot be measured. These significant facts confirm the partial nature of our approach. A Tool-Based Set Theoretic Framework for Concept Approximation 55 Let us distinguish two types of tools: positive and negative ones. It is a natural assumption that a subset cannot be positive and negative tool simultaneously. To manage the problem outlined above we need an approximation framework. It may be built on the rough set theory because it provides a powerful foundation to reveal and discover important structures in data and classify complex objects [27, 28]. The rough set theory was introduced by the Polish mathematician, Z. Pawlak in the early 1980s [24, 25]. It can be seen as a new mathematical approach to vagueness [14]. According to Pawlak’s idea, the vagueness of a subset within the universe U is defined by the difference of its upper and lower approximations with respect to a partition of U . Using partitions, however, is a very strict requirement. Our starting point is an arbitrary family of subsets of U which does not cover the universe necessarily. The lower and upper approximations are straightforward point-free generalizations of Pawlak’s ones [2–6]. We apply them to build a set theoretic tool-based partial approximation framework in which positive features and their negative counterparts of any clump of observed objects can be approximated simultaneously. The rest of the paper is organized as follows. Section 2 sums up the most im- portant features of rough set theory and partial approximation spaces. Classical rough set theory and formal concept analysis use similar structures to represent information which is briefly described in Section 3. In Section 4 we will propose a tool-based set theoretical framework for concept approximation based on partial approximation spaces. Its main notions are illustrated in Section 5. Finally, in Section 6, we conclude the paper. 2 Partial Approximation of Sets First, we summarize the most important concepts and properties of rough set theory [13, 25]. Let U be a nonempty set and ε be an equivalence relation on U . Let U/ε denote the partition of U generated by ε. Members of the partition are called ε-elementary sets. X ⊆ U is ε-definable, if it is a union of ε-elementary sets, otherwise ε-undefinable. By definition, the empty set is considered to be an ε-definable set. The pair hU, εi is called a Pawlakean approximation space. The lower and upper ε-approximations of X ⊆ U can be defined as follows. The lower ε-approximation of X is3 [ ε(X) = {Y | Y ∈ U/ε, Y ⊆ X}, and the upper ε-approximation of X is [ ε(X) = {Y | Y ∈ U/ε, Y ∩ X 6= ∅}. The set Bε (X) = ε(X)\ε(X) is the ε-boundary of X. X is ε-crisp, if Bε (X) = ∅, otherwise X is ε-rough. 3 If A ⊆ 2U , we define A = {x |S∃A ∈ A(x ∈ T S T A)}, and A = {x | ∀A ∈ A(x ∈ A)}. If A is an empty family of sets, ∅ = ∅ and ∅ = U. 56 Z. Csajbók et al. Let DU/ε denote the family of ε-definable subsets of U . Clearly, ε(X), ε(X) ∈ DU/ε , and the maps ε, ε : 2U → DU/ε are monotone, total and many-to-one. It can easily be seen ([25], Proposition 2.2, points 1, 9, 10) that the map ε is contractive and ε is extensive, i.e. ∀X ∈ 2U (ε(X) ⊆ X ⊆ ε(X)). In other words, X is bounded by its lower and upper approximations. Now, let us turn to the theory of partial approximation of sets [2, 4, 5]. Its most fundamental notion is the base system. Definition 1. Let B ⊆ 2U be a nonempty family of nonempty subsets of U . B is called the base system, its members are the B-sets. An extension of the base system is specified by the next definition. Definition 2. A nonempty subset X ⊆S U is B-definable if there exists a family of sets D ⊆ B in such a way that X = D, otherwise X is B-undefinable. The empty set is considered to be a B-definable set. Let DB denote the family of B-definable sets of U . Note that neither the base system B nor DB covers the universe necessarily. Let us define the lower and upper approximations of sets based on partial covering of the universe. Definition 3. Let B ⊆ 2U be a base system and X be any subset of U . The lower B-approximation of X (Fig. 1) is [ C[B (X) = {Y | Y ∈ B, Y ∩ X = Y }, the upper B-approximation of X (Fig. 2) is [ C]B (X) = {Y | Y ∈ B, Y ∩ X 6= ∅}. Remark 1. In Definition 3, the members of the base system may be seen as the elements of the lattice 2U , and instead of set theoretic operations may be used lattice operations. In this way, point-free generalizations of Pawlakean lower and upper approximations can be obtained. Clearly, C[B (X), C]B (X) ∈ DB , and the maps C[B , C]B : 2U → DB are total, monotone and in general many-to-one. Fig. 1. Lower Fig. 2. Upper Fig. 3. Lower and approximation approximation upper approximations A Tool-Based Set Theoretic Framework for Concept Approximation 57 Proposition 1 ([6], Proposition 4.8). Let B ⊆ 2U be a base system. Then 1. ∀X ∈ 2U (C[B (X) ⊆ C]B (X)); 2. ∀X ∈ 2U (C[B (X) ⊆ X)—that is, C[B is contractive; 3. ∀X ∈ 2U (X ⊆ C]B (X)) if and only if B = U —that is, C]B is extensive if S and only if B covers the universe. Using the previous notations, the notion of the partial approximation space can be introduced. Definition 4. The ordered quadruple hU, DB , C[B , C]B i is called the (weak) par- tial B-approximation space. Let (P, ≤P ) and (Q, ≤Q ) be two posets. Definition 5. The pair of maps f : P → Q and g : Q → P forms a (regular) Galois connection between P and Q, in notation G(P, f, g, Q), if ∀p ∈ P ∀q ∈ Q (f (p) ≤Q q ⇔ p ≤P g(q)). If P = Q, G(P, f, g, P ) is called a Galois connection on P . Remark 2. Here we adopted the definition of Galois connection in which the maps are monotone. It is also called monotone or covariant form. For more details on Galois connections, see, e.g. [8]. Note that since Galois connections are not necessarily symmetric, the order of the maps is important. It is well known fact ([13], Proposition 138) that upper and lower ε-approx- imations form a Galois connection G(2U , ε, ε, 2U ) on (2U , ⊆). Next theorem shows the conditions under which upper and lower B-approximations also form a Galois connection. Theorem 1 ([6], Theorem 4.14). Let hU, B, C[B , C]B i be a partial B-approxi- mation space. The upper and lower B-approximations form a Galois connection G(2U , C]B , C[B , 2U ) on (2U , ⊆) if and only if the base system B is a partition of U. According to Proposition 1, point 3, X ⊆ C]B (X) if and only if the base system B covers the universe. Definition 6. A subset X ⊆ U is B-approximatable if X ⊆ C]B (X), otherwise it is said that X has a B-approximation gap. A B-approximation gap may be interpreted so that our knowledge about the universe encoded in the base system is incomplete and not enough to approxi- mate X. Definition 7. Let h2U , DB , C[B , C]B i be a partial B-approximation space, and X be any subset of U . The partial upper B-approximation of X is  ] ] CB (X), if X is B-approximatable; ∂CB (X) = (1) undefined, otherwise. 58 Z. Csajbók et al. There exists at least one nonempty B ∈ B B-set by Definition 2. Then B ⊆ C]B (B) according to Definition 3. Hence, ∂C]B is defined on at least one nonempty subset of U . Notice that C[B (X) ⊆ X ⊆ ∂C]B (X) holds provided X is B-approximatable. As Theorem 1 shows, the upper and lower B-approximations form a Galois connection on (2U , ⊆) if and only if the base system B is a partition of U . The question naturally arises whether the Galois connection could be generalized so that the maps ∂C]B and C[B may form a Galois connection in any sense. Moreover, if the answer is yes, then what conditions have to be fulfilled by a partial B-approximation space so that ∂C]B and C[B form a Galois connection of this special type. Recall that C[B is a total and ∂C]B is a partial map on 2U . To answer this question, first of all, we need a suitable modified notion of Galois connections. Definition 8 ([18], Definition 2.2.2). The pair of maps f : P → Q and g : Q → P forms a partial Galois connection between P and Q, denoted by ∂G(P, ∂f, g, Q), if 1. f : P → Q is a monotone partial map, 2. g : Q → P is a monotone total map, 3. f (g(q)) exists for all q ∈ Q, and 4. ∀p ∈ P and ∀q ∈ Q such that f (p) is defined, f (p) ≤Q q ⇔ p ≤P g(q). Remark 3. In [18], A. Miné actually introduced the concept of F-partial Galois connection ∂G(P, ∂f, g, Q) between the concrete domain P and the abstract domain Q, where F is a set of concrete operators. We apply this notion in the simplest form when P = Q = 2U and F = ∅. It is allowed by Miné’s definition. Theorem 2 ([6], Theorem 4.22). Let hU, B, C[B , C]B i be a partial B-approxi- mation space. The partial upper B-approximation and the lower B-approximation form a partial Galois connection ∂G(2U , ∂C]B , C[B , 2U ) on (2U , ⊆) if and only if the B- sets are pairwise disjoint. A natural question is how we can form a base system from an arbitrary one of which members are pairwise disjoint. In practice, this problem can be reduced to finite base systems. A possible way to construct such a base system is the following. First, let us form an intersection structure from an arbitrary finite base system. Formally,Ta nonempty family S ⊆ 2U is an intersection structure if ∀S0 (6= ∅) ⊆ S ( S0 ∈ S), i.e. it is closed under intersection but does not contain U necessarily [7]. Let us take an arbitrary finite base system B and create its intersection structure IS(B) as the smallest set which satisfies the following two properties: 1. B ⊆ IS(B). 2. If B0 ⊆ IS(B), then B0 ∈ IS(B). T A Tool-Based Set Theoretic Framework for Concept Approximation 59 Having given the intersection structure IS(B), we can create a family of sets ISΠ (B) of which members are pairwise disjoint. ISΠ (B) is the smallest family of sets which satisfies the following property: If u ∈ U and B0 = {B : B ∈ B ∧ u ∈ B}, then B0 ∈ ISΠ (B). T 3 Rough Set Theory and Formal Concept Analysis Let G and M denote a set of objects and a finite set of attributes, respectively. Note that the formal concept analysis allows that G and M to be empty sets, but the rough set theory does not. 3.1 Information Systems First, we reformulate the rough set theory [9, 24]. Let S = hG, M, Vm∈M , f i be an information system, where G and M as before, S Vm is a nonempty set of values of attribute m ∈ M , and f : G×M → V = m∈M Vm is an information function with ∀g ∈ G ∀m ∈ M (f (g, m) ∈ Vm ). Informally, f (g, m) represents the value which object g takes at attribute m. The information system is often represented by a table, as shown in Table 1. It is an information table containing a shortened student grade history from an information technology course held for hospital nurses at the Faculty of Health, University of Debrecen. It contains 20 students and their results in three home- work assignments, and one final examination. Table 1. Information system Table 2. Information system of a shortened student grade history of a shortened student grade history (complete) (partial) Final Final exam Student Hw1 Hw2 Hw3 exam Student Hw1 Hw2 Hw3 S1 1 1 1 1 S1 1 1 1 1 S2 1 1 2 2 S2 1 1 2 2 S3 1 1 1 1 S3 1 1 1 1 S4 1 2 1 1 S4 2 1 S5 1 1 1 1 S5 1 1 1 1 S6 1 1 2 1 S6 1 1 2 1 S7 4 1 3 1 S7 1 3 1 S8 2 4 1 2 S8 2 4 1 2 S9 1 3 1 2 S9 1 3 1 2 S 10 1 1 3 1 S 10 1 1 3 1 S 11 2 1 1 2 S 11 2 1 1 2 S 12 1 1 1 1 S 12 1 1 1 1 S 13 1 2 1 1 S 13 1 2 1 1 S 14 1 1 2 3 S 14 1 1 2 3 S 15 4 3 3 4 S 15 4 3 3 4 S 16 2 1 1 4 S 16 2 1 1 4 S 17 2 2 2 4 S 17 4 S 18 4 4 3 3 S 18 4 4 3 3 S 19 4 3 3 2 S 19 4 3 3 2 S 20 S 20 4 4 3 4 4 4 3 4 60 Z. Csajbók et al. With each N ⊆ M we associate an equivalence relation EN ⊆ G × G by (g1 , g2 ) ∈ EN if ∀n ∈ N (f (g1 , n) = f (g2 , n)). If g ∈ G, then [g]EN is the equivalence class of EN containing g. Let G/N denote the set of equivalence classes generated by EN . A concept X ⊆ G is EN -definable or EN -exact if X is a union of some equivalence classes, otherwise X is EN -undefinable or EN -inexact. Lower and upper EN -approximations of X are: [ EN (X) = {[g]EN ∈ G/N | [g]EN ⊆ X}, [ EN (X) = {[g]EN ∈ G/N | [g]EN ∩ X 6= ∅}. 3.2 Formal Context In formal concept analysis a formal context is a triple hG, M, Ri [11], where G and M as above and R ⊆ G × M is a binary relation. Choosing  1, if (g, m) ∈ R; ∀m ∈ M (Vm = {0, 1}) and f (g, m) = , 0, otherwise we may transform information systems into formal contexts. For instance, Table 3 shows a formal context representation of the same example shown in Table 1. Table 3. Formal context Table 4. Incomplete formal context of a shortened student grade history of a shortened student grade history Homework1 Homework2 Homework3 Final Homework1 Homework2 Homework3 Final Student 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 exam Student 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 exam S1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 S1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 S2 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 2 S2 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 2 S3 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 S3 1 0 0 0 0 1 S4 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 S4 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 S5 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 S5 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 S6 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 S6 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 S7 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 S7 1 0 0 0 0 0 0 1 0 0 1 S8 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 2 S8 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 2 S9 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 2 S9 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 2 S 10 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 S 10 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 S 11 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 2 S 11 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 2 S 12 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 S 12 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 S 13 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 S 13 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 S 14 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 3 S 14 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 3 S 15 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 4 S 15 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 4 S 16 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 4 S 16 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 4 S 17 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 4 S 17 4 S 18 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 3 S 18 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 3 S 19 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 2 S 19 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 2 S20 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 4 S 20 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 4 A Tool-Based Set Theoretic Framework for Concept Approximation 61 Given the formal context hG, M, Ri we define AB = {m ∈ M | ∀g ∈ A ((g, m) ∈ R)}, for A ⊆ G, B C = {g ∈ G | ∀m ∈ B((g, m) ∈ R)}, for B ⊆ M, called the polars of A, B, respectively [26]. Informally, AB is the set of attributes common to all the objects in A, B C is the set of all objects which possess all of the attributes in B. Given A ⊆ G and B ⊆ M we have A × B ⊆ R ⇔ A ⊆ B C ⇔ AB ⊇ B. The pair (A, B) is called a formal concept if A = B C and AB = B. Formal concepts are usually ordered by inclusion on the first co-ordinate and/or reverse inclusion on the second: (A1 , B1 )  (A2 , B2 ) ⇔ A1 ⊆ A2 and B1 ⊇ B2 ⇔ A1 ⊆ A2 ⇔ B1 ⊇ B2 . Formal concepts with this ordering form a concept hierarchy for the context hG, M, Ri and denoted by B(G, M, R). The fundamental theorem of formal con- cept analysis states that B(G, M, R) with the ordering  is a complete lattice called the concept lattice [11]. 4 A Tool-Based Set Theoretic Approximation Framework Let U be any nonempty set. Let A+ , A− ⊆ U be two nonempty subsets of U in such a way that A+ ∩ A− = ∅. A+ and A− are called the positive and negative reference set, respectively. The adjectives positive and negative claim nothing else but that the sets A+ and A− are well separated. In general, the constraint A+ ∩ A− = ∅ is the only requirement for A+ and − A . Of course, additional relations between them may be supposed. Furthermore, let T+ and T− ⊆ 2U be two nonempty finite families of subsets of U . The members of T+ are called positive or T+ -tools, whereas the members of T− are called negative or T− -tools. Requirements for positive and negatives tools are the following: (T1) For each subset T + ∈ T+ (resp., T − ∈ T− ) it is easy to decide whether an element of U belongs to T + (resp., T − ) or not. (T2) Sets in T+ are not necessarily pairwise disjoint, neither are those in T− . (T3) T+ ∩ T−S= ∅. (T4) Neither T+ nor T− covers U necessarily. S (T5) It is assumed that ∀T1+ , T2+ ∈ T+ (T1+ ∩ T2+ ∈ T+ ), and ∀T1− , T2− ∈ T− (T1− ∩ T2− ∈ T− ), i.e. the T+ and T− are closed under intersection. 62 Z. Csajbók et al. Positive (resp., negative) tools provide an opportunity to locate or approxi- mate the positive (resp., negative) reference set. Positive and negative tools together also yield useful information about the reference sets. To do this, we can use the following three partial approximation spaces relaying on T+ and T− : hU, DT+ , C[T+ , C]T+ i, hU, DT− , C[T− , C]T− i, hU, DT+ ∪T− , C[T+ ∪T− , C]T+ ∪T− i. Within these spaces, any clump of observed objects can be approximated with the help of the lower and upper T+ (T− -,T+ ∪ T− -)-approximations. 5 An Illustrative Example To illustrate our framework let us see a simple example. We want to approxi- mately estimate the achievement of students and their results in the final ex- amination in higher education [20, 21]. We have at our disposal an information table (Table 5) containing the student grade history (5 = excellent, 4 = good, 3 = fair, 2 = pass, 1 = fail). Table 5. Information table with student grade history Final Student Hw1 Hw2 Hw3 exam Positive tools: + S1 1 1 1 1 THw1=4 = {S7 , S15 , S18 , S19 , S20 } S2 1 1 2 2 + THw2=4 = {S8 , S18 , S20 } S3 1 1 1 1 + S4 1 2 1 1 THw1=4∧Hw2=4 = {S18 , S20 } S5 1 1 1 1 Negative tools: S6 1 1 2 1 − S7 4 1 3 1 THw1=1 = S8 2 4 1 2 {S1 , S2 , S3 , S4 , S5 , S6 , S9 , S10 , S12 , S13 , S14 } S9 1 3 1 2 − THw2=1 = S 10 1 1 3 1 {S1 , S2 , S3 , S5 , S6 , S7 , S10 , S11 , S12 , S14 , S16 } S 11 2 1 1 2 − S 12 1 1 1 1 THw3=1 = S 13 1 2 1 1 {S1 , S3 , S4 , S5 , S8 , S9 , S11 , S12 , S13 , S16 } S 14 1 1 2 3 − THw1=1∧Hw2=1 = S 15 4 3 3 4 {S1 , S2 , S3 , S5 , S6 , S10 , S12 , S14 } S 16 2 1 1 4 − S 17 2 2 2 4 THw1=1∧Hw3=1 = {S1 , S3 , S4 , S5 , S9 , S12 , S13 } − S 18 4 4 3 3 THw1=2∧Hw3=1 = {S1 , S3 , S5 , S11 , S12 , S16 } S 19 4 3 3 2 − S 20 4 4 3 4 THw1=1∧Hw2=1∧Hw3=1 = {S1 , S3 , S5 , S12 } Of course, there is no way to accurately measure the achievement of students and their success or failure on the final exam. Moreover, students cannot exactly appreciate ‘what they know’ or ‘what they do not know’. However, with the A Tool-Based Set Theoretic Framework for Concept Approximation 63 apparatus of partial approximation spaces, we can analyze student grade history contained in Table 5 in order to understand how the results in assignments approximately relate to success or failure on the final exam. For the sake of simplicity, students’ success and failure on homework assign- ments or the final exam are measured by grade 4 and grade 1, respectively. Based on these prerequisites, the positive tools (Fig. 4) and negative tools (Fig. 5) are the following (see also Table 5): + + + T+ = {THw1=4 , THw2=4 , THw1=4∧Hw2=4 }, − − − − − T− = {THw1=1 , THw2=1 , THw3=1 , THw1=1∧Hw2=1 , THw1=1∧Hw3=1 , − − THw1=2∧Hw3=1 , THw1=1∧Hw2=1∧Hw3=1 } + THw2=4 U U + S17 S15 S18 S19 S20 THw1=4 S18 S15 S8 THw2=1 ¡ S19 S20 S7 S14 S7 THw1=1 ¡ S2 S6 S1 S3 S4 S5 S9 S10 S2 S6 S11 S12 S10 S14 S16 S13 THw3=1 ¡ S1 S3 S5 S12 S11 S16 S9 S4 S13 S17 S8 Fig. 4. Positive tools (homework = 4). Fig. 5. Negative tools (homework = 1). hU, DT+ , C[T+ , C]T+ i partial hU, DT− , C[T− , C]T− i partial approximation space approximation space Students who have successful final exams can be evaluated with both positive and negative tools (Fig. 6, Fig. 7): – C[T+ (XF inal exam=4 ) = ∅ Informally: there is no combination of successful homework in which case the final exam surely succeeds. – C]T+ (XF inal exam=4 ) = THw1=4 + + ∪ THw2=4 + ∪ THw1=4∧Hw2=4 Informally: if one of the Homework 1, 2 or both of the two succeed, the final exam possibly succeeds. – C[T− (XF inal exam=4 ) = ∅ Informally: there is no combination of failed homework in which case the final exam surely succeeds. – C]T− (XF inal exam=4 ) = THw3=1 − Informally: if the Homework 3 fails, the final exam may succeed. 64 Z. Csajbók et al. + THw2=4 U XF inal exam=4 S15 U S17 S20 + THw1=4 S18 S18 S19 S15 S8 THw2=1 ¡ S7 S19 S20 S14 S7 THw1=1 ¡ S2 S6 S1 S3 S4 S5 S9 S10 S2 S6 S11 S12 S10 S14 S16 S13 THw3=1 ¡ S1 S3 S5 S12 S11 S16 S9 S4 S13 S17 S8 XF inal exam=4 Fig. 6. Evaluation of successful final Fig. 7. Evaluation of successful final exams with positive tools exams with negative tools Students who have failed their final exams can also be evaluated with both positive and negative tools (Fig. 8, Fig. 9): – C[T+ (XF inal exam=1 ) = ∅ Informally: there is no combination of successful homework in which case the final exam surely fails. – C]T+ (XF inal exam=1 ) = THw1=4 + Informally: if the only Homework 1 succeeds, the final exam possibly fails (because, e.g., Homework 1 is the simplest part of the course). − – C[T− (XF inal exam=1 ) = THw1=1∧Hw2=1∧Hw3=1 Informally: If all homework S fail, the final exam surely fails. – C]T− (XF inal exam=1 ) = T− Informally: if at least one homework fails, the final exam possibly fails. + THw2=4 U XF inal exam=1 U + S17 S15 S18 S19 S20 THw1=4 S18 S8 THw2=1 ¡ S7 S19 S14 S7 THw1=1 ¡ S2 S6 S11 S14 S10 S2 S1 S3 S4 S5 S15 S16 S9 S6 S12 S13 S17 THw3=1 ¡ S1 S3 S5 S12 S11 S16 S10 S20 S9 S4 S13 S8 XF inal exam=1 Fig. 8. Evaluation of failed final exams Fig. 9. Evaluation of failed final exams with positive tools with negative tools A Tool-Based Set Theoretic Framework for Concept Approximation 65 Evaluations can also be carried out over positive and negative tools together: – C[T+ ∪T− (XF inal exam=4 ) = ∅ (see Fig. 10) informally means that there is no combination of successful or failed homework in which case the final exam surely succeeds. – C]T+ ∪T− (XF inal exam=4 ) (see Fig. 10) informally means that if one of the Homework 1, 2 or both of the two succeed, in addition, even if one of the Homework 1, 3 or both of the two fail, then the final exam possibly succeed. – C[T+ ∪T− (XF inal exam=1 ) (see Fig. 11) informally means that if at least one homework fails, the final exam surely fails. – C]T+ ∪T− (XF inal exam=1 ) (see Fig. 11) informally means that if at least one homework fails, the final exam possibly fails even if the Homework 1 succeeds. + THw2=4 U + C[T+ ∪T− (XF inal exam=4 ) = ∅ THw1=4 S18 S19 S15 S20 S8 C]T+ ∪T− (XF inal exam=4 ) THw2=1 ¡ S7 + + S1 S3 S4 = THw1=4 ∪ THw2=4 S5 S9 + S2 S6 S11 S12 ∪ THw1=4∧Hw2=4 S10 S14 − − S16 S13 ∪ THw2=1 ∪ THw3=1 − S17 ∪ THw2=1∧Hw3=1 THw3=1 ¡ XF inal exam=4 Fig. 10. Evaluation of successful final exams with positive and negative tools + C[T+ ∪T− (XF inal exam=1 ) THw1=4 U − = THw1=1∧Hw2=1∧Hw3=1 S17 S15 S18 S19 S20 ¡ THw2=1 S7 C]T+ ∪T− (XF inal exam=1 ) ¡ S14 − − − THw1=1 S2 S6 = THw1=1 ∪ THw2=1 ∪ THw3=1 − S10 ∪ THw1=1∧Hw2=1 − ¡ ∪ THw1=1∧Hw3=1 THw3=1 S1 S3 S5 S12 S11 S16 − S13 ∪ THw2=1∧Hw3=1 S9 S4 S8 − ∪ THw1=1∧Hw2=1∧Hw3=1 + ∪ THw1=4 XF inal exam=1 Fig. 11. Evaluation of failed final exams with positive and negative tools 66 Z. Csajbók et al. 6 Conclusion We have presented in this paper a tool-based set theoretic framework for concept approximation relying on partial approximation spaces. Positive features and their substantially negative features of observed objects can simultaneously be approximated with the help of this framework. We have drawn up a simplified example to demonstrate our approach. We have analyzed a student grade history and we have been able to evaluate the students’ achievement, exploring ‘what they know’ and/or ‘what they do not know’, and understand how the results in homework assignments approximately relate to success or failure on the final exam. Of course, a more subtle definition of the notions of ‘success’ and ‘failure’ could result in a more subtle evaluation. A refined evaluation process can form a basis for quality insurance in higher education properly building in the hierarchy of quality management. Acknowledgement The author would like to express his gratitude to the anonymous referees for reading the paper carefully and their insightful comments and suggestions. References 1. Proceedings of the International Multiconference on Computer Science and Infor- mation Technology, IMCSIT 2009, Mragowo, Poland, 12-14 October 2009. Polskie Towarzystwo Informatyczne - IEEE Computer Society Press (2009) 2. Csajbók, Z.: Partial approximative set theory: A generalization of the rough set theory. In: Martin, T., Muda, A.K., Abraham, A., Prade, H., Laurent, A., Laurent, D., Sans, V. (eds.) Proceedings of SoCPaR 2010, December 7-10, 2010., Cergy Pontoise / Paris, France. pp. 51–56. IEEE (2010) 3. Csajbók, Z., Mihálydeák, T.: A general tool-based approximation framework based on partial approximation of sets. In: Kuznetsov, S.O., et al. (eds.) Proceedings of RSFDGrC 2011, June 25-27, 2011, Moscow, Russia. LNAI, vol. 6743, pp. 52–59. Springer-Verlag Berlin Heidelberg (2011) 4. Csajbók, Z., Mihálydeák, T.: On the general set theoretical framework of set ap- proximation. pp. 12–15 (2011), Proceedings of RST 2011, 14-16 September 2011, Milan, Italy (2011) 5. Csajbók, Z., Mihálydeák, T.: Partial approximative set theory: A generalization of the rough set theory. International Journal of Computer Information Systems and Industrial Management Applications 4, 437–444 (2012) 6. Csajbók, Z.: Approximation of sets based on partial covering. Theoretical Com- puter Science 412(42), 5820–5833 (2011) 7. Davey, B.A., Priestley, H.A.: Introduction to Lattices and Order. Cambridge Uni- versity Press, Cambridge (2002) 8. Denecke, K., Erné, M., Wismath, S. (eds.): Galois Connections and Applications. Kluwer Academic Publishers (2004) 9. Düntsch, I., Gediga, G.: Statistical evaluation of rough set dependency analysis. International Journal of Human-Computer Studies 46(5), 589–604 (1997) A Tool-Based Set Theoretic Framework for Concept Approximation 67 10. Ganter, B., Kuznetsov, S.O.: Formalizing hypotheses with concepts. In: Mineau, G., Ganter, B. (eds.) Proc. 8th Int. Conf. on Conceptual Structures, ICCC’2000. Lecture Notes in Artificial Intelligence, vol. 1867, pp. 342–356. Springer, Berlin (2000) 11. Ganter, B., Wille, R.: Formal concept analysis: Mathematical foundations. Springer, Berlin-Heidelberg (1999) 12. Gartmeier, M., Bauer, J., Gruber, H., Heid, H.: Negative knowledge: Understand- ing professional learning and expertise. Vocations and Learning: Studies in Voca- tional and Professional 1(2), 87–103 (2008) 13. Järvinen, J.: Lattice theory for rough sets. In: Peters, J.F., Skowron, A., Düntsch, I., Grzymala-Busse, J.W., Orlowska, E., Polkowski, L. (eds.) Transactions on Rough Sets VI, LNCS, vol. 4374, pp. 400–498. Springer-Verlag (2007) 14. Keefe, R.: Theories of Vagueness. Cambridge Studies in Philosophy, Cambridge University Press, Cambridge, UK (2000) 15. Kuznetsov, S.O.: Machine learning and formal concept analysis. In: Eklund, P.W. (ed.) Concept Lattices, Second International Conference on Formal Concept Anal- ysis, ICFCA 2004, Sydney, Australia, February 23-26, 2004, Proceedings. Lecture Notes in Computer Science, vol. 2961, pp. 287–312. Springer-Verlag, Berlin Hei- delberg (2004) 16. Kuznetsov, S.O.: Galois connections in data analysis: Contributions from the soviet era and modern russian research. In: Ganter, B., Stumme, G., Wille, R. (eds.) Formal Concept Analysis, Foundations and Applications. LNAI, vol. 3626, pp. 196–225. Springer (2005) 17. Marek, V.W., Truszczyński, M.: Approximation schemes in logic and artificial in- telligence. In: Peters, J.F., Skowron, A., Rybinski, H. (eds.) Transactions on Rough Sets IX. LNCS, vol. 5390, pp. 135–144. Springer-Verlag (2008) 18. Miné, A.: Weakly Relational Numerical Abstract Domains. Ph.D. thesis, École Polytechnique, Palaiseau, France (December 2004) 19. Minsky, M.: Negative expertise. International Journal of Expert Systems 7(1), 13– 19 (1994) 20. Narli, S., Ozelik, Z.A.: Data mining in topology education: Rough set data analysis. International Journal of the Physical Sciences 5(9), 1428–1437 (2010) 21. Narli, S., Yorek, N., Sahin, M., Usak, M.: Can we make definite categorization of student attitudes? a rough set approach to investigate students implicit attitudinal typologies toward living things. Journal of Science Education and Technology 19, 456–469 (2010) 22. Pagliani, P., Chakraborty, M.: A Geometry of Approximation: Rough Set Theory Logic, Algebra and Topology of Conceptual Patterns (Trends in Logic). Springer Publishing Company, Incorporated (2008) 23. Parviainen, J., Eriksson, M.: Negative knowledge, expertise and organisations. In- ternational Journal of Management Concepts and Philosophy 2(2), 140–153 (2006) 24. Pawlak, Z.: Rough sets. International Journal of Computer and Information Sci- ences 11(5), 341–356 (1982) 25. Pawlak, Z.: Rough Sets: Theoretical Aspects of Reasoning about Data. Kluwer Academic Publishers, Dordrecht (1991) 26. Priestley, H.A.: Ordered sets and complete lattices: A primer for computer science. In: Backhouse, R.C., Crole, R.L., Gibbons, J. (eds.) Algebraic and Coalgebraic Methods in the Mathematics of Program Construction. LNCS, vol. 2297, pp. 21– 78. Springer (2000) 27. Revett, K., Gorunescu, F., Salem, A.B.M.: Feature selection in parkinson’s disease: A rough sets approach. In: IMCSIT [1], pp. 425–428 68 Z. Csajbók et al. 28. Salem, A.B.M., Revett, K., El-Dahshan, E.S.A.: Machine learning in electrocar- diogram diagnosis. In: IMCSIT [1], pp. 429–433 29. Skowron, A.: Rough sets in perception-based computing. In: Pal, S.K., Bandy- opadhyay, S., Biswas, S. (eds.) Pattern Recognition and Machine Intelligence, First International Conference, PReMI 2005, Kolkata, India, December 20-22, 2005, Pro- ceedings. LNCS, vol. 3776, pp. 21–29. Springer (2005) 30. Skowron, A., Stepaniuk, J., Swiniarski, R.: Approximation spaces in rough-granular computing. Fundamenta Informaticae 100(1–4), 141–157 (2010) 31. Zadeh, L.A.: A new direction in AI: Toward a computational theory of perceptions. AI Magazine 22(1), 73–84 (2001)