=Paper=
{{Paper
|id=Vol-1252/cla2014_submission_22
|storemode=property
|title=Attributive and Object Subcontexts in Inferring Good Maximally Redundant Tests
|pdfUrl=https://ceur-ws.org/Vol-1252/cla2014_submission_22.pdf
|volume=Vol-1252
|dblpUrl=https://dblp.org/rec/conf/cla/NaidenovaP14
}}
==Attributive and Object Subcontexts in Inferring Good Maximally Redundant Tests==
https://ceur-ws.org/Vol-1252/cla2014_submission_22.pdf
Attributive and Object Subcontexts in Inferring
Good Maximally Redundant Tests
Xenia Naidenova1 and Vladimir Parkhomenko2
1
Military Medical Academy, Saint-Petersburg, Russia
ksennaid@gmail.com
2
St. Petersburg State Polytechnical University, Saint-Petersburg, Russia
parhomenko.v@gmail.com
Abstract. Inferring Good Maximally Redundant Classification Tests
(GMRTs) as Formal Concepts is considered. Two kinds of classification
subcontexts are defined: 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.
Keywords: good classification test, Galois lattice, essential attributes
and objects, implications, subcontexts
1 Introduction
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 classification. To
give a target classification of objects, we use an additional attribute KL ∈ / 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 = {∪dom(attr), attr ∈
U }, 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 (classification) test for G+ [1]. The words diagnostic (classification)
can be omitted in the paper.
Table 1. Motivating Example of classification
No Height Color of Hair Color of Eyes KL
1 Low Blond Blue k(+)
2 Low Brown Blue k(−)
3 Tall Brown Hazel k(−)
4 Tall Blond Hazel k(−)
5 Tall Brown Blue k(−)
6 Low Blond Hazel k(−)
7 Tall Red Blue k(+)
8 Tall Blond Blue k(+)
Let us recall the definition 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 defining a concept of good diagnostic (classification) test
as a formal concept. Sec.3 gives the decomposition of good tests inferring based
on two kinds of subcontexts of the initial classification 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 = {m1 , m2 , . . . , mj , . . . mm } 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 defined by the following mappings called derivation operators: for
A ⊆ G and B ⊆ M , A0 = val(A) = {intersection of all Bi | Bi ⊆ M, i ∈ A} and
B 0 = obj(B) = {i| i ∈ G, B ⊆ Bi }. Of course, we have obj(B) = {intersection of
all obj(m)| obj(m) ⊆ G, m ∈ B}.
There are two closure operators [9]: generalization of(B) = B 00 = 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 ∈ G and m ∈ M , {g}0 is denoted by
g 0 and called object intent, and {m}0 is denoted by m0 and called value extent.
Let us recall the main definitions of GTA [7].
A Diagnostic Test (DT) for the positive examples G+ is a pair (A, B) such
that B ⊆ M , A = B 0 6= ∅, A ⊆ G+ , B 6⊆ g 0 ∀g ∈ G− . A diagnostic test (A, B)
for G+ is maximally redundant if obj(B ∪ m) ⊂ A for all m ∈ / B and m ∈ M .
A diagnostic test (A, B) for G+ is good if and only if any extension A∗ = A ∪ i,
i∈/ A, i ∈ 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 ∈ / B, m ∈ M implies that (obj(B∗ ), B∗ ) is not a good test for G+ .
Any object description d of g ∈ G in a given classification context is a maximally
redundant set of values because ∀m ∈ / d, m ∈ 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, find 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, find all GMRTs (obj(Y ), Y ) such that X ⊂ Y .
For solving these subtasks we need only form subcontexts of a given classifi-
cation context. The first subtask is useful to find 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 definition 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 = {z| z =
d ∩ d∗ 6= ∅, d∗ ∈ D+ and (obj(z), z) is a test for 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) = {d| m appears in d, d ∈
D+ }.
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 pos-
itive objects and obj(m) ⊆ obj(X), m ∈ M . Then m can not belong to any
GMRT for positive objects different 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 {splus(m)| m ∈ M }. In Tab.1, we
have SPLUS = obj(m) ∩ G− = {{3, 4, 6}, {2, 3, 5}, {3, 4, 5}, {2, 5}, {4, 6}, {2, 6}}
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 = {{2, 3, 5}, {3, 5}, {2, 5}, {2}}. 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 finding 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 defined 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 ∈ t∗ .
Let STGOOD be the partially ordered set of elements s satisfying the con-
dition 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 for some
s ∈ STGOOD.
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 par-
tially ordered sets. The set TGOOD of all the GMRTs is obtained as follows:
TGOOD = {tg| tg = (s, val(s)), s ∈ STGOOD}.
4 Selecting and Ordering Subcontexts and Inferring
GMRTs
Algorithms for inferring GMRTs are constructed by the rules of selecting and
ordering subcontexts of the main classification context. Before entering into the
details, let us recall some extra definitions. Let t be a set of values such that
(obj(t), t) is a test for G+ . We say that the value m ∈ M, m ∈ t is essential
in t if (obj(t \ m), (t \ m)) is not a test for a given set of objects. Generally, we
are interested in finding 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 \ 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 ∈ s is said to be an essential in s if (s\j, val(s\j)) proves
to be a test for a given set of positive objects. Generally, we are also interested
in finding 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 \ 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 quasi-
maximal subset s∗ ⊆ G+ which is the extent of a test for G+ (maybe not good).
We begin with the first index i1 of s∗ , then we take the next index i2 of
s∗ and evaluate the function to be test({i1 , i2 }, val({i1 , i2 })). If the value of the
function is true, then we take the next index i3 of s∗ and evaluate the function
to be test({i1 , i2 , i3 }, val({i1 , i2 , i3 })). If the value of the function is false, then
the index i2 of s∗ is skipped and the function to be test({i1 , i3 }, val({i1 , i3 })))
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 ||s∗ ||
by the complexity of the function to be test(). To obtain the initial content of
STGOOD, we use the set SPLUS = {splus(m)|m ∈ M } 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 modification 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 modified G and f lag. The variable f lag is necessary for switching at-
tributive 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, defined FormSubTask(na, M, G+ ), con-
sists of object descriptions. There is the auxiliary function kt(m) = true if
(m0 ∈ 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 = {m1 , . . . , m26 }.
The set SPLUS0 for positive class of examples is in Tab.4. The initial content of
1.Algorithm GenAllGMRTs() 1.Algorithm DelVal()
Input: G, M 2. i := 1;
Output: STGOOD 3. f lag := 0;
2. begin 4. while i ≤ 2M do
3. Forming STGOOD ; 5. if Mi0 ⊆ G+ then
4. Forming and Ordering LEV ; 6. M := M \Mi ;
5. f lag:=1; 7. f lag := 1;
6. end 8. end
7. while true do 9. else if kt(Mi0 ∩ G+ ) then
8. while flag=1 do 10. j :=1 ;
9. M, f lag DelVal(M, G+ ); 11. while j ≤ 2STGOOD do
10. if flag=1 then 12. if STGOODj ⊆
11. return; Mi0 ∩ G+ then
12. end 13. STGOOD :=
13. G+ , f lag STGOOD\
DelObj(M, G+ ); STGOODj
14. end 14. end
15. if M 0 ⊆ G− or 15. end
G+ ⊆ STGOOD then 16. STGOOD :=
16. return STGOOD; STGOOD ∪ Mi0 ∩ G+ ;
17. end 17. M := M \Mi ;
18. MSUB :=∅; 18. f lag := 1;
19. GSUB :=∅;
19. return;
20. ChoiceOfSubtask;
20. end
21. MSUB , GSUB
FormSubTask(na, M, G+ ); (b) DelVal
22. GenAllGMRTs();
23. M :=M \Mna ;
24. G+ , f lag DelObj(M, G+ );
25. end
(a) GenAllGMRTs
1.Algorithm DelObj() 1.Algorithm FormSubTask()
2. i := 1; 2. i := 1;
0
3. f lag := 0; 3. GSUB := Mna ∩ G+ ;
4. while i ≤ 2G+ do 4. while i ≤ 2GSUB
do
5. if G+ (i) ⊆ M \LEV then 5. MSUB := MSUB ∪
6. G+ := G+ \G+ (i); (MainContext(GSUB (i)∩M ));
7. f lag := 1; 6. end
8. end 7. return;
9. end
10. return; (d) FormSubTask
(c) DelObj
Fig. 1. Algorithms of ASTRA-2
STGOOD0 is {(2,10), (3, 10), (3, 8), (4, 12), (1, 4, 7), (1, 5,12), (2, 7, 8), (3, 7,
12), (1, 2, 12, 14), (2, 3, 4, 7), (4, 6, 8, 11)}.
Table 2. The set D+ of positive object descriptions
G D+
1 m1 m2 m5 m6 m21 m23 m24 m26
2 m4 m7 m8 m9 m12 m14 m15 m22 m23 m24 m26
3 m3 m4 m7 m12 m13 m14 m15 m18 m19 m24 m26
4 m1 m4 m5 m6 m7 m12 m14 m15 m16 m20 m21 m24 m26
5 m2 m6 m23 m24
6 m7 m20 m21 m26
7 m3 m4 m5 m6 m12 m14 m15 m20 m22 m24 m26
8 m3 m6 m7 m8 m9 m13 m14 m15 m19 m20 m21 m22
9 m16 m18 m19 m20 m21 m22 m26
10 m2 m3 m4 m5 m6 m8 m9 m13 m18 m20 m21 m26
11 m1 m2 m3 m7 m19 m20 m21 m22 m26
12 m2 m3 m16 m20 m21 m23 m24 m26
13 m1 m4 m18 m19 m23 m26
14 m23 m24 m26
In these tables we denote subsets of values {m8 , m9 }, {m14 , m15 } by ma and
mb , respectively. Applying operation generalization of(s) = s00 = obj(val(s)) to
∀s ∈ STGOOD, we obtain STGOOD1 = {(2,10), (3, 10), (3, 8), (4, 7, 12), (1, 4,
7), (1, 5,12), (2, 7, 8), (3, 7, 12), (1, 2, 12, 14), (2, 3, 4, 7), (4, 6, 8, 11)}.
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 proce-
dure applicable to search for the initial content of STGOOD. We begin with
the first value m1 of M , then we take the next value m2 of M and evalu-
ate the function to be test(obj({m1 , m2 }), {m1 , m2 }). If the value of the func-
tion is false, then we take the next value m3 of M and evaluate the function
to be test(obj({m1 , m2 , m3 }), {m1 , m2 , m3 }). If the value of the function is true,
then value m2 of M is skipped and the function to be test(obj({m1, m3}), {m1,
m3}) 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 ||M || by the
complexity of the function to be test(). In Tab.2,3 we have the following LEV :
{m16 , m18 , m19 , m20 , m21 , m22 , m23 , m24 , m26 }.
Table 3. The set D− of negative object descriptions
G D− G D−
15 m3 m8 m16 m23 m24 32 m1 m2 m3 m7 m9 m13 m18
16 m7 m8 m9 m16 m18 33 m1 m5 m6 m8 m9 m19 m20 m22
17 m1 m21 m22 m24 m26 34 m2 m8 m9 m18 m20 m21 m22 m23 m26
18 m1 m7 m8 m9 m13 m16 35 m1 m2 m4 m5 m6 m7 m9 m13 m16
19 m2 m6 m7 m9 m21 m23 36 m1 m2 m6 m7 m8 m13 m16 m18
20 m19 m20 m21 m22 m24 37 m1 m2 m3 m4 m5 m6 m7 m12 m14 m15 m16
21 m1 m20 m21 m22 m23 m24 38 m1 m2 m3 m4 m5 m6 m9 m12 m13 m16
22 m1 m3 m6 m7 m9 m16 39 m1 m2 m3 m4 m5 m6 m14 m15 m19 m20 m23 m26
23 m2 m6 m8 m9 m14 m15 m16 40 m2 m3 m4 m5 m6 m7 m12 m13 m14 m15 m16
24 m1 m4 m5 m6 m7 m8 m16 41 m2 m3 m4 m5 m6 m7 m9 m12 m13 m14 m15 m19
25 m7 m13 m19 m20 m22 m26 42 m1 m2 m3 m4 m5 m6 m12 m16 m18 m19 m20 m21 m26
26 m1 m2 m3 m5 m6 m7 m16 43 m4 m5 m6 m7 m8 m9 m12 m13 m14 m15 m16
27 m1 m2 m3 m5 m6 m13 m18 44 m3 m4 m5 m6 m8 m9 m12 m13 m14 m15 m18 m19
28 m1 m3 m7 m13 m19 m21 45 m1 m2 m3 m4 m5 m6 m7 m8 m9 m12 m13 m14 m15
29 m1 m4 m5 m6 m7 m8 m13 m16 46 m1 m3 m4 m5 m6 m7 m12 m13 m14 m15 m16 m23 m24
30 m1 m2 m3 m6 m12 m14 m15 m16 47 m1 m2 m3 m4 m5 m6 m8 m9 m12 m14 m16 m18 m22
31 m1 m2 m5 m6 m14 m15 m16 m26 48 m2 m8 m9 m12 m14 m15 m16
Table 4. The set SPLUS0
splus(m), m ∈ M splus(m), m ∈ M
splus(ma ) → {2, 8, 10} splus(m22 ) → {2, 7, 8, 9, 11}
splus(m13 ) → {3, 8, 10} splus(m23 ) → {1, 2, 5, 12, 13, 14}
splus(m16 ) → {4, 9, 12} splus(m3 ) → {3, 7, 8, 10, 11, 12}
splus(m1 ) → {1, 4, 11, 13} splus(m4 ) → {2, 3, 4, 7, 10, 13}
splus(m5 ) → {1, 4, 7, 10} splus(m6 ) → {1, 4, 5, 7, 8, 10}
splus(m12 ) → {2, 3, 4, 7} splus(m7 ) → {2, 3, 4, 6, 8, 11}
splus(m18 ) → {3, 9, 10, 13} splus(m24 ) → {1, 2, 3, 4, 5, 7, 12, 14}
splus(m2 ) → {1, 5, 10, 11, 12} splus(m20 ) → {4, 6, 7, 8, 9, 10, 11, 12}
splus(mb ) → {2, 3, 4, 7, 8} splus(m21 ) → {1, 4, 6, 8, 9, 10, 11, 12}
splus(m19 ) → {3, 8, 9, 11, 13} splus(m26 ) → {1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 13, 14}
Proposition 1. Each essential value is included at least in one positive object
description.
Proof. Assume that for an object description ti , i ∈ G+ , we have ti ∩ LEV = ∅.
Then ti ⊆ M \LEV. But M \LEV 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. t
u
Proposition 2. Assume that X ⊆ M . If X ∩ LEV = ∅, then to be test(X) =
false.
Proposition 2 is the consequence of Proposition 1.
Note that the description of t14 = {m23 , m24 , m26 } is closed because of
obj{m23 , m24 , m26 } = {1, 2, 12, 14} and val{1, 2, 12, 14} = {m23 , m24 , m26 }. We
also know that s = {1, 2, 12, 14} is closed too (we obtained this result during
generalization of elements of STGOOD. So (obj({m23 , m24 , m26 }), {m23 , m24 ,
m26 }) is a maximally redundant test for positive objects and we can, conse-
quently, delete t14 from consideration. As a result of deleting m12 and t14 , we
have the modified set SPLUS (Tab.5).
Table 5. The set SPLUS1
splus(m), m ∈ M splus(m), m ∈ M
splus(ma ) → {2, 8, 10} splus(m22 ) → {2, 7, 8, 9, 11}
splus(m13 ) → {3, 8, 10} splus(m23 ) → {1, 2, 5, 12, 13}
splus(m16 ) → {4, 9, 12} splus(m3 ) → {3, 7, 8, 10, 11, 12}
splus(m1 ) → {1, 4, 11, 13} splus(m4 ) → {2, 3, 4, 7, 10, 13}
splus(m5 ) → {1, 4, 7, 10} splus(m6 ) → {1, 4, 5, 7, 8, 10}
splus(m7 ) → {2, 3, 4, 6, 8, 11}
splus(m18 ) → {3, 9, 10, 13} splus(m24 ) → {1, 2, 3, 4, 5, 7, 12}
splus(m2 ) → {1, 5, 10, 11, 12} splus(m20 ) → {4, 6, 7, 8, 9, 10, 11, 12}
splus(mb ) → {2, 3, 4, 7, 8} splus(m21 ) → {1, 4, 6, 8, 9, 10, 11, 12}
splus(m19 ) → {3, 8, 9, 11, 13} splus(m26 ) → {1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 13}
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.
Table 6. Auxiliary information
P
index of object m16 m18 m19 m20 m21 m22 m23 m24 m26 mij
1 × × × × 4
2 × × × × 4
3 × × × × 4
5 × × 2
7 × × × × 4
9 × × × × × × × 7
10 × × × × 4
12 × × × × × × 4
13 × × × × 4
4 × × × × ×
6 × × ×
8 × × × × ×
11 × × × × ×
P
di 2 4 3 4 4 3 5 6 8 39
We begin with ordering index of objects by the number of their entering in
tests in STGOOD1 , see Tab.7.
Table 7. Ordering index of objects in STGOOD1
Index of object 9 13 5 10 1 2 3 12 7
The number of entering in STGOOD1 0 0 1 2 3 4 4 4 5
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 sub-
task, we have to correct the sets SPLUS, STGOOD, and auxiliary information.
So, the first 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 = {9, 11} 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
Table 8. The sequence of subtasks (method 1)
N subcontext Extent of New Test Deleted values Deleted objects
1 t9 × m16
2 t9 × m19 (9, 11) t9
3 t13 × m18
4 t13 × m19 (13) m16 , m18 t13
5 t5 × m23 m23
6 t5 × m24 t5
7 t10 × m20 (8, 10)
8 t10 × m21
9 t10 × m26 ma , m13 , m4 , m5 t10
10 t1 × m21
11 t1 × m24 m1 , m2 t1
12 t2 × m22 (7, 8, 11) m22
13 t2 × m22
14 t2 × m24 t2
15 t3 × m19 (3, 11) m19
16 t3 × m24 m24 t12 , t7
17 t3 × m26 t3
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 find 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 de-
composing the main classification context into subcontexts and ordering them
by the use of essential values and objects. It is possible to use the two sets
QT = {{i, j} ⊆ G+ | ({i, j}, val({i, j}) is a test for G+ } and QAT = {{i, j} ⊆
G+ |({i, j}, val({i, j}) is not a test for G+ } for forming subcontexts and their or-
dering in the form of a tree structure.
5 Conclusion
In this paper, the decomposition of inferring good classification tests into sub-
tasks of the first 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. Vari-
ous possibilities of constructing algorithms for inferring GMRTs with the use of
both subcontexts are considered depending on the nature of GMRTs features.
Table 9. The sequence of subtasks (method 2)
Object descriptions
Context, Extents of tests Values deleted
N deleted
associated with obtained from context
from context
(2, 10), (3, 10),ma , m13 , mb , t10
1 m26
(2, 3, 4, 7), (1, 4, 7)m5 , m6
m3 , m20 , m23 , m1 ,
(3, 7, 12),
2 m26 , m24 m2 , m4 , m7 , m16 ,
(4, 7, 12)
m18 , m19 , m22
Subtask is over; return to the previous context and delete m24
m3 , m7 , m16 , m18 ,
3 m26 , not m24 , m23 (13)
m19 , m20 , m22
Subtask is over; return to the previous context, delete m23
m2 , m3 , m4 , m16 ,
4 m26 , not m24 , not m23
m18 m19 , m21
m26 , m22 , not m24 ,
5 (9,11), (7,11) t2 , t7
not m23
Subtask is over; return to the previous context and delete m22
m26 , not m24 , m2 , m3 , m4 , m16 , t7 , t 9 , t 2 , t 3
6 (3,11), (4,6,11)
not m23 , not m22 m18 , m19
Subtask is over; we have obtained all GMRTs whose intents contain m26
7 Context t5 (1,5,12) t5
Subtask is over; we have found all GMRTs whose intents are contained in t5 .
m3 , m20 , mb , m6 ,
8 Context t8 × m22 (7,8,11), (2,7,8)
ma , m13 , m19 , m21
Subtask is over; return to the previous context and delete m22
Context t8
9 (8,10) ma t2 , t7
without m22
Context t8 × m21
10 (4,6,8,11) m7 , m13 , m19 t6 , t10 , t11
without m22
Subtask is over; return to the previous context and delete m21 , m20
Context t8 without
11 (3, 8) t4 , t6 , t10 , t11
m22 , m21 , m20
Subtask is over; we have found all GMRTs whose intents are contained in t8 .
Table 10. The sets STGOOD and TGOOD
N STGOOD TGOOD N STGOOD TGOOD
1 13 m1 m4 m18 m19 m23 m26 9 2,7,8 mb m22
2 2,10 m4 ma m26 10 1,5,12 m2 m23 m24
3 3,10 m3 m4 m13 m18 m26 11 4,7,12 m20 m24 m26
4 8,10 m3 m6 ma m13 m20 m21 12 3,7,12 m3 m24 m26
5 9,11 m19 m20 m21 m22 m26 13 7,8,11 m3 m20 m22
6 3,11 m3 m7 m19 m26 14 2,3,4,7 m4 m12 mb m24 m26
7 3,8 m3 m7 m13 mb m19 15 4,6,8,11 m7 m20 m21
8 1,4,7 m5 m6 m24 m26 16 1,2,12,14 m23 m24 m26
References
1. Chegis, I., Yablonskii, S.: Logical methods of electric circuit control. Trudy Mian
SSSR 51, 270–360 (1958), (in Russian)
2. Ferré, S., Ridoux, O.: The use of associative concepts in the incremental building
of a logical context. In: Priss, U., Corbett, D., Angelova, G. (eds.) ICCS. Lecture
Notes in Computer Science, vol. 2393, pp. 299–313. Springer (2002)
3. Ganter, B., Wille, R.: Formal concept analysis: mathematical foundations. Springer,
Berlin (1999)
4. Ganter, B., Kuznetsov, S.O.: Formalizing hypotheses with concepts. In: Proceedings
of the Linguistic on Conceptual Structures: Logical Linguistic, and Computational
Issues. pp. 342–356. Springer-Verlag (2000)
5. Naidenova, X.A.: DIAGARA: An Incremental Algorithm for Inferring Implicative
Rules from Examples. Inf. Theories and Application 12 - 2, 171 – 196 (2005)
6. Naidenova, X.A., Plaksin, M.V., Shagalov, V.L.: Inductive Inferring All Good Clas-
sification Tests. In: Valkman, J. (ed.) ”Knowledge-Dialog-Solution”, Proceedings of
International Conference. vol. 1, pp. 79 – 84. Kiev Institute of Applied Informatics,
Kiev, Ukraine (1995)
7. Naidenova, X.A., Polegaeva, J.G.: An Algorithm of Finding the Best Diagnostic
Tests. In: Mintz, G., Lorents, E. (eds.) The 4-th All Union Conference ”Application
of Mathematical Logic Methods”. pp. 87 – 92 (1986), (in Russian)
8. Naidenova, X., Ermakov, A.: The decomposition of good diagnostic test inferring
algorithms. In: Alty, J., Mikulich, L., Zakrevskij, A. (eds.) ”Computer-Aided Design
of Discrete Devices” (CAD DD2001), Proceedings of the 4-th Inter. Conf., vol. 3,
pp. 61 – 68. Minsk (2001)
9. Ore, O.: Galois connections. Trans. Amer. Math. Soc 55, 494–513 (1944)