Inferring Good Maximally Redundant Classi cation Tests (GMRTs) as Formal Concepts is considered. Two kinds of classi cation subcontexts are de ned: attributive and object ones. The rules of forming and reducing subcontexts based on the notion of essential attributes and objects are given. They lead to the possibility of the inferring control. In particular, an improved Algorithm for Searching all GMRTs on the basis of attributive subtask is proposed. The hybrid attributive and object approaches are presented. Some computational aspects of algorithms are analyzed.
Good Test Analysis (GTA) deals with the formation of the best descriptions of a given object class (class of positive objects) against the objects which do not belong to this class (class of negative objects) on the basis of lattice theory. We assume that objects are described in terms of values of a given set U of attributes, see an example in Tab.1. The key notion of GTA is the notion of classi cation. To give a target classi cation of objects, we use an additional attribute KL 2= U . A target attribute partitions a given set of objects into disjoint classes the number of which is equal to the number of values of this attribute. In Tab.1, we have two classes: the objects in whose descriptions the target value k appears and all the other objects.
Denote by M the set of attribute values such that M = f[dom(attr); attr 2 U g, where dom(attr) is the set of all values of attr, i.e. a plain scaling in terms of [3]. Let G = G+ [ G be the set of objects, where G+ and G are the sets of positive and negative objects respectively. Let P (B); B M; be the set of all the objects in whose descriptions B appears. P (B) is called the interpretation of B in the power set 2G. If P (B) contains only G+ objects and the number of these objects is more than 2, then B is called a description of some positive objects or a diagnostic (classi cation) test for G+ [1]. The words diagnostic (classi cation) can be omitted in the paper.
Let us recall the de nition of a good test or good description for a subset of G+ (via partitions of objects). A subset B M of attribute values is a good test for a subset of positive objects if it is a test and no such subset C M exists, so that P (B) P (C) G+ [7].
Sec.2 is devoted to de ning a concept of good diagnostic (classi cation) test as a formal concept. Sec.3 gives the decomposition of good tests inferring based on two kinds of subcontexts of the initial classi cation context. Sec.4 is devoted to an analysis of algorithms based on using subcontexts including the evaluation of the number of sub-problems to be solved, the depth of recursion, the structure of sub-problems and their ordering, and some others. 2
Good Maximally Redundant Tests as Formal Concepts Assume that G = 1; N is the set of objects indices (objects, for short) and M = fm1; m2; : : : ; mj ; : : : mmg is the set of attributes values (values, for short). Each object is described by a set of values from M . The object descriptions are represented by rows of a table whose columns are associated with the attributes taking their values in M .
Let A G, B M . Denote by Bi, Bi M , i = 1; N the description of object with index i. The Galois connection between the ordered sets (2G; ) and (2M ; ) is de ned by the following mappings called derivation operators: for A G and B M , A0 = val(A) = fintersection of all Bij Bi M; i 2 Ag and B0 = obj(B) = fij i 2 G; B Big. Of course, we have obj(B) = fintersection of all obj(m)j obj(m) G; m 2 Bg.
There are two closure operators [9]: generalization of(B) = B00 = val(obj(B)) and generalization of(A) = A00 = obj(val(A)). A set A is closed if A = obj(val(A)). A set B is closed if B = val(obj(B)). For g 2 G and m 2 M , fgg0 is denoted by g0 and called object intent, and fmg0 is denoted by m0 and called value extent. Let us recall the main de nitions of GTA [7].
A Diagnostic Test (DT) for the positive examples G+ is a pair (A; B) such that B M , A = B0 6= ;, A G+, B 6 g0 8g 2 G . A diagnostic test (A; B) for G+ is maximally redundant if obj(B [ m) A for all m 2= B and m 2 M . A diagnostic test (A; B) for G+ is good if and only if any extension A = A [ i, i 2= A, i 2 G+ implies that (A ; val(A )) is not a test for G+.
In the paper, we deal with Good Maximally Redundant Tests (GMRTs). If a good test (A; B) for G+ is maximally redundant, then any extension B = B [ m; m 2= B; m 2 M implies that (obj(B ); B ) is not a good test for G+. Any object description d of g 2 G in a given classi cation context is a maximally redundant set of values because 8m 2= d, m 2 M; obj(d [ m) is equal to ;. GMRT can be regarded as a special type of hypothesis [4]
In Tab.1, ((1; 8), Blond Blue) is a GMRT for k(+), ((4; 6), Blond Hazel) is a DT for k( ) but not a good one, and ((3; 4; 6), Hazel) is a GMRT for k( ). 3
The Decomposition of Inferring GMRTs into Subtasks There are two possible kinds of subtasks of inferring GMRTs for a set G+ [8]: 1. given a set of values, where B M; obj(B) 6= ;; B is not included in any description of negative object, nd all GMRTs (obj(B ); B ) such that B B; 2. given a non-empty set of values X M such that (obj(X); X) is not a test for positive objects, nd all GMRTs (obj(Y ); Y ) such that X Y .
For solving these subtasks we need only form subcontexts of a given classi cation context. The rst subtask is useful to nd all GMRTs whose intents are contained in the description d of an object g. This subtask is considered in [2] for fast incremental concept formation, where the de nition of subcontexts is given.
We introduce the projection of a positive object description d on the set D+, i.e. descriptions of all positive objects. The proj(d) is Z = fzj z = d \ d 6= ;; d 2 D+ and (obj(z); z) is a test for G+g.
We also introduce a concept of value projection proj(m) of a given value m on a given set D+. The value projection is proj(m) = fdj m appears in d; d 2 D+g.
Algorithm Algorithm for Searching all GMRTs on the basis of attributive subtask (ASTRA), based on value projections, was advanced in [6]. Algoritm DIAGaRa, based on object projections, was proposed in [5]. In what follows, we are interested in using both kinds of subcontexts for inferring all GMRTs for a positive (or negative) class of objects. The following theorem gives the foundation of reducing subcontexts [6].
Theorem 1. Let X M; (obj(X); X) be a maximally redundant test for positive objects and obj(m) obj(X); m 2 M . Then m can not belong to any GMRT for positive objects di erent from (obj(X); X).
Consider some example of reducing subcontext (see Tab.1). Let splus(m) be obj(m) \ G+ or obj(m) \ G and SPLUS be fsplus(m)j m 2 M g. In Tab.1, we have SPLUS = obj(m) \ G = ff3; 4; 6g; f2; 3; 5g; f3; 4; 5g; f2; 5g; f4; 6g; f2; 6gg for values \Hazel, Brown, Tall, Blue, Blond, and Low" respectively.
We have val(obj(Hazel)) = Hazel, hence ((3; 4; 6); Hazel) is a DT for G . Then value \Blond" can be deleted from consideration, because splus(Blond) splus(Hazel). Delete values Blond and Hazel from consideration. After that the description of object 4 is included in the description of object 8 of G+ and the description of object 6 is included in the description of object 1 of G+. Delete objects 4 and 6. Then for values \Brown, Tall, Blue, and Low" respectively SPLUS = ff2; 3; 5g; f3; 5g; f2; 5g; f2gg. Now we have val(obj(Brown)) = Brown and ((2; 3; 5); Brown) is a test for G . All values are deleted and all GMRTs for G have been obtained.
The initial information for nding all the GMRTs contained in a positive object description is the projection of it on the current set D+. It is essential that the projection is a subset of object descriptions de ned on a certain restricted subset t of values. Let s be the subset of indices of objects whose descriptions produce the projection. In the projection, splus(m) = obj(m) \ s ; m 2 t .
Let STGOOD be the partially ordered set of elements s satisfying the condition that (s; val(s)) is a good test for D+. The basic recursive procedure for solving any kind of subtask consists of the following steps: 1. Check whether (s ; val(s ) is a test and if so, then s is stored in STGOOD if s corresponds to a good test at the current step; in this case, the subtask is over. Otherwise go to the next step. 2. The value m can be deleted from the projection if splus(m) s 2 STGOOD. s for some 3. For each value m in the projection, check whether (splus(m); val(splus(m)) is a test and if so, then value m is deleted from the projection and splus(m) is stored in STGOOD if it corresponds to a good test at the current step. 4. If at least one value has been deleted from the projection, then the reduction of the projection is necessary. The reduction consists in checking, for each element t of the projection, whether (obj(t); t) is not a test (as a result of previous eliminating values) and if so, this element is deleted from the projection. If, under reduction, at least one element has been deleted, then Step 2, Step 3, and Step 4 are repeated. 5. Check whether the subtask is over or not. The subtask is over when either the projection is empty or the intersection of all elements of the projection corresponds to a test (see, please, Step 1). If the subtask is not over, then the choice of an object (value) in this projection is selected and the new subtask is formed. The new subsets s and t are constructed and the basic algorithm runs recursively.
The algorithm of forming STGOOD is based on topological sorting of partially ordered sets. The set TGOOD of all the GMRTs is obtained as follows: TGOOD = ftgj tg = (s; val(s)); s 2 STGOODg.
Selecting and Ordering Subcontexts and Inferring GMRTs Algorithms for inferring GMRTs are constructed by the rules of selecting and ordering subcontexts of the main classi cation context. Before entering into the details, let us recall some extra de nitions. Let t be a set of values such that (obj(t); t) is a test for G+. We say that the value m 2 M; m 2 t is essential in t if (obj(t n m); (t n m)) is not a test for a given set of objects. Generally, we are interested in nding the maximal subset sbmax(t) t such that (obj(t); t) is a test but (obj(sbmax(t)); sbmax(t)) is not a test for a given set of positive objects. Then sbmin(t) = t n sbmax(t) is a minimal set of essential values in t. Let s G+, assume also that (s; val(s)) is not a test.
The object tj , j 2 s is said to be an essential in s if (snj; val(snj)) proves to be a test for a given set of positive objects. Generally, we are also interested in nding the maximal subset sbmax(s) s such that (s; val(s)) is not a test but (sbmax(s); val(sbmax(s)) is a test for a given set of positive objects. Then sbmin(s) = s n sbmax(s) is a minimal set of essential objects in s.
An Approach for Searching for Initial Content of STGOOD. In the beginning of inferring GMRTs, the set STGOOD is empty. Next we describe the procedure to obtain an initial content of it. This procedure extracts a quasimaximal subset s G+ which is the extent of a test for G+ (maybe not good).
We begin with the rst index i1 of s , then we take the next index i2 of s and evaluate the function to be test(fi1; i2g; val(fi1; i2g)). If the value of the function is true, then we take the next index i3 of s and evaluate the function to be test(fi1; i2; i3g; val(fi1; i2; i3g)). If the value of the function is false, then the index i2 of s is skipped and the function to be test(fi1; i3g; val(fi1; i3g))) is evaluated. We continue this process until we achieve the last index of s .
The complexity of this procedure is evaluated as the production of jjs jj by the complexity of the function to be test(). To obtain the initial content of STGOOD, we use the set SPLUS = fsplus(m)jm 2 M g and apply the procedure described above to each element of SPLUS.
The idea of using subcontexts in inferring GMRTs, described in Sec.3, can be presented in a pseudo-code form, see Fig.1. It presents a modi cation of ASTRA. DIAGARA and a hybrid approach can be easily formalized by the same way. The example below describes two general hybrid methods.
The initial part of GenAllGMRTs() is well discussed above. The abbreviation LEV stands for the List (set) of Essential Values. The function DelObj(M; G+) returns modi ed G and f lag. The variable f lag is necessary for switching attributive subtasks. The novelty of ASTRA-2 is mainly based on using LEV. There is the new function ChoiceOfSubtask(). It returns na := LEVj with the maximal 2splus(LEVj). MainContext, de ned FormSubTask(na; M; G+), consists of object descriptions. There is the auxiliary function kt(m) = true if (m0 2 G = f alse) and f alse otherwise.
To illustrate this procedure, we use the sets D+ and D represented in Tab.2 and 3 (our illustrative example). In these tables, M = fm1; : : : ; m26g. The set SPLUS0 for positive class of examples is in Tab.4. The initial content of 1.Algorithm FormSubTask() 2. i := 1; 3. GSUB := M n0a \ G+; 4. while i 2GSUB do 5. MSUB := MSUB [
(MainContext(GSUB(i)\M ));
STGOOD0 is f(
In these tables we denote subsets of values fm8; m9g, fm14; m15g by ma and
mb, respectively. Applying operation generalization of(s) = s00 = obj(val(s)) to
8s 2 STGOOD, we obtain STGOOD1 = f(
By Th.1, we can delete value m12 from consideration, see splus(m12) in Tab.4. The initial content of STGOOD allows to decrease the number of using the procedure to be test() and the number of putting extents of tests into STGOOD.
The number of subtasks to be solved. This number is determined by the number of essential values in the set M . The quasi-minimal subset of essential values in M can be found by a procedure analogous to the procedure applicable to search for the initial content of STGOOD. We begin with the rst value m1 of M , then we take the next value m2 of M and evaluate the function to be test(obj(fm1; m2g); fm1; m2g). If the value of the function is false, then we take the next value m3 of M and evaluate the function to be test(obj(fm1; m2; m3g); fm1; m2; m3g). If the value of the function is true, then value m2 of M is skipped and the function to be test(obj(fm1; m3g); fm1; m3g) is evaluated. We continue this process until we achieve the last value of M . The complexity of this procedure is evaluated as the production of jjM jj by the complexity of the function to be test(). In Tab.2,3 we have the following LEV : fm16; m18; m19; m20; m21; m22; m23; m24; m26g.
Proof. Assume that for an object description ti; i 2 G+; we have ti \ LEV = ;. Then ti M nLEV. But M nLEV is included at least in one of the negative object descriptions and, consequently, ti also possesses this property. But it contradicts to the fact that ti is a description of a positive object. tu Proposition 2. Assume that X false.
M . If X \ LEV = ;, then to be test(X) = Proposition 2 is the consequence of Proposition 1.
Note that the description of t14 = fm23; m24; m26g is closed because of objfm23; m24; m26g = f1; 2; 12; 14g and valf1; 2; 12; 14g = fm23; m24; m26g. We also know that s = f1; 2; 12; 14g is closed too (we obtained this result during generalization of elements of STGOOD. So (obj(fm23; m24; m26g), fm23; m24; m26g) is a maximally redundant test for positive objects and we can, consequently, delete t14 from consideration. As a result of deleting m12 and t14, we have the modi ed set SPLUS (Tab.5). splus(ma) ! f2; 8; 10g splus(m22) ! f2; 7; 8; 9; 11g splus(m13) ! f3; 8; 10g splus(m23) ! f1; 2; 5; 12; 13g splus(m16) ! f4; 9; 12g splus(m3) ! f3; 7; 8; 10; 11; 12g splus(m1) ! f1; 4; 11; 13g splus(m4) ! f2; 3; 4; 7; 10; 13g splus(m5) ! f1; 4; 7; 10g splus(m6) ! f1; 4; 5; 7; 8; 10g
splus(m7) ! f2; 3; 4; 6; 8; 11g splus(m18) ! f3; 9; 10; 13g splus(m24) ! f1; 2; 3; 4; 5; 7; 12g splus(m2) ! f1; 5; 10; 11; 12g splus(m20) ! f4; 6; 7; 8; 9; 10; 11; 12g splus(mb) ! f2; 3; 4; 7; 8g splus(m21) ! f1; 4; 6; 8; 9; 10; 11; 12g splus(m19) ! f3; 8; 9; 11; 13g splus(m26) ! f1; 2; 3; 4; 6; 7; 9; 10; 11; 12; 13g The main question is how we should approach the problem of selecting and ordering subtasks (subcontexts). Consider Tab.6 with auxiliary information. It is clear that if we shall have all the intents of GMRTs entering into descriptions of objects 1, 2, 3, 5, 7, 9, 10, 12, then the main task will be over because the remaining object descriptions (objects 4, 6, 8, 11) give, in their intersection, the intent of already an known test (see, please, the initial content of STGOOD). Thus we have to consider only the subcontexts of essential values associated with object descriptions 1, 2, 3, 5, 7, 9, 10, 12, 13. The number of such subcontexts is 39. But this estimation is not realistic.
We begin with ordering index of objects by the number of their entering in tests in STGOOD1, see Tab.7.
Then we continue with object descriptions t9 and t13. Now we should select the subcontexts (subtasks), based on proj(t m), where t is object description containing the smallest number of essential values and m is an essential value in t, entering in the smallest number of object descriptions. After solving each subtask, we have to correct the sets SPLUS, STGOOD, and auxiliary information. So, the rst sub-task is t9 m16. Solving this sub-task, we have not any new test, but we can delete m16 from t9 and then we solve the sub-task t9 m19. As a result, we introduce s = f9; 11g in STGOOD and delete t9 from consideration because of m16, m19 are the only essential values in this object description.
In the example (method 1), we have the following subtasks (Tab. 8).
Tab.10 shows the sets STGOOD and TGOOD. All subtasks did not require a recursion. A simpler method of ordering contexts is based on the basic recursive procedure for solving any kind of subtask described in the previous section. At each level of recursion, we can select the value entering into the greatest number of object descriptions; the object descriptions not containing this value generate the contexts to nd GMRTs whose intents are included in them. For our example, value m26 does not cover two object descriptions: t5 and t8. The initial context is associated with m26. The sequence of subtasks in the basic recursive procedure is in Tab.9 (method 2). We assume, in this example, that the GMRT intent of which is equal to t14 has been already obtained.
We consider only two possible ways of GMRTs construction based on decomposing the main classi cation context into subcontexts and ordering them by the use of essential values and objects. It is possible to use the two sets QT = ffi; jg G+j (fi; jg; val(fi; jg) is a test for G+g and QAT = ffi; jg G+j(fi; jg; val(fi; jg) is not a test for G+g for forming subcontexts and their ordering in the form of a tree structure. 5
In this paper, the decomposition of inferring good classi cation tests into subtasks of the rst and second kinds is presented. This decomposition allows, in principle, to transform the process of inferring good tests into a step by step reasoning process.
The rules of forming and reducing subcontexts are given, in this paper. Various possibilities of constructing algorithms for inferring GMRTs with the use of both subcontexts are considered depending on the nature of GMRTs features.
Context, N associated with
Extents of tests obtained
Values deleted
from context
1
2
3
4
5 m26; m22; not m24; (
Subtask is over; return to the previous context and delete m22
6 nmo2t6;mn23o;t nmo2t4;m22 (
Subtask is over; we have obtained all GMRTs whose intents contain m26
7 Context t5 (
Subtask is over; we have found all GMRTs whose intents are contained in t5
8 Context t8 m22 (
Subtask is over; return to the previous context and delete m22
9 Cwiotnhtoeuxtt mt822 (
Subtask is over; return to the previous context and delete m21; m20
11 Context t8 without (