A sketch of classification reasoning is given in the paper. The key ideas of the reasoning are ideas of classification and its good approximations based on good diagnostic tests. Such good tests, which are maximally redundant (GMRTs), i.e. their subsets of attributes are closed, are considered. Classification reasoning embraces two interrelated processes: inductive inferring implicative assertions based on GMRTs and using these assertions in deductive steps of reasoning. A peculiarity of our inductive model of classification reasoning is the control and transformation of subcontexts during inductive phase of reasoning by the use of deductive reasoning rules, for example the rules prohibiting some pairs of attributive values.
Classification reasoning is a part of commonsense (plausible) reasoning based on two kinds of logical rules extracted from observable datasets (functional and implicative dependencies). The principle concepts of this reasoning are the concepts of classification and its good approximations. We assume that objects are described by a set U of symbolic or numeric attributes. To give a target classification of objects, we use an additional attribute KL not belonging to 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: KL+ (positive objects) and KL− (negative objects).
We concentrate on the case of object classification into two classes and task of concept formation [2,5]. The goal of this task is to describe/classify new objects according to description/classification of existing objects. Inferring good diagnostic tests (GDTs) is the formation of the best descriptions of a given object class KL+ against the objects not belonging to this class (KL−).
Let M = {∪dom(attr), attr ∈ U }, where dom(attr) is the set of all values of attr. Let X ⊆ M and G be the set of indices of objects considered (objects for short), G = G+ ∪ G−, where G+ and G− the sets of positive and negative objects, respectively. Denote by d(g) the description of object g ∈ G. Let P(X) = {g | g ∈ G, X ⊆ d(g)}. We call P(X) the interpretation of X in the power set 2G. If P(X) contains only positive objects and the number of these objects more than 2, then we call X a description of some positive objects and (P(X), X) a test for positive objects.
Let us define a good test or good description of objects.
Definition 1. A set X ⊆ M of attribute values is a good description of positive (negative) objects if and only if it is the description of these objects and no such subset Y ⊆ M exists, that P(X) ⊂ P(Y ) ⊆ G+.
It can be seen [15,11,1] that this problem is reduced to searching for causal dependencies in the form X → v, X ⊆ M, v is value of attribute KL for all positive (negative) objects.
Sec.2 describes an approach to classification reasoning based on implications. Sec.3 describes the definitions of Good Test Analysis. Sec.4 presents the decomposition of inferring good tests into two kinds of subtasks. An approach to selecting and ordering subcontexts is given in Subsec.5.1. Some situations of reducing the classification context are considered in Subsec.5.2. A set of examples illustrates all the considerations. 2
Classification reasoning based on GDTs embraces two interrelated processes: inductive inferring implicative assertions and using them for pattern recognition problems. We need the following three types of logical rules in order to realize classification reasoning (deductive and inductive): – INSTANCES or relationships between objects or facts really observed. Instance can be considered as a logical rule with the least degree of generalization. On the other hand, instances can serve as a source of training set of positive and negative examples for inductive inference of generalized rules. – RULES OF THE FIRST TYPE or logical assertions. These rules describe regular relationships between objects and their properties, between properties of different objects, between objects and their classes. The rules of the first type can be given explicitly by an expert or derived automatically from instances with the help of some learning process. These rules are represented, in the paper, in the form of implications. – RULES OF THE SECOND TYPE or commonsense reasoning rules with the help of which rules of the first type are used, updated, and inferred from data (instances). The rules of the second type embrace both inductive and deductive reasoning rules.
The rules of the first type can be represented with the use of only one class of logical statements based on implicative dependencies between names. Names are used for designating concepts, things, events, situations, or any evidences. They can be considered as attributes and attributes’ values in the formal representations of logical rules. 1. Implication: a, b, c → d. This rule means that if the values standing on the left side of rule are simultaneously true, then the value on the right side of rule is always true. 2. Interdiction or forbidden rule (a special case of implication): a, b, c → f alse (never). This rule interdicts a combination of values enumerated on the left side of rule. The rule of interdiction can be transformed into several implications such as a, b →not c; a, c →not b; b, c →not a. 3. Compatibility: a, b, c → VA where VA is the frequency of occurrence of rule.
The compatibility is equivalent to the following implications: a, b → c, VA ; a, c → b, VA; b, c → b, VA.
Generally, the compatibility rule represents the most common combination of values, which is characterized by an insignificant number of exceptions (contrary examples) from regularity. 4. Diagnostic rule: x, d → a; x, b →not a; d, b → f alse. For example, d and b can be two values of the same attribute. This rule works when the truth of ’x’ has been proven and it is necessary to determine whether ’a’ is true or not. If ’x&d’ is true, then ’a’ is true, if ’x&b’ is true, then ’a’ is f alse. 5. Rule of alternatives: a or b → true (always); a, b → f alse. This rule says that a and b cannot be simultaneously true, either a or b can be true but not both. This rule is a variant of interdiction.
Deductive steps of classification reasoning consist of inferring consequences from some observed facts with the use of implications (i.e. knowledge). For this goal, deductive rules of reasoning are applied the main forms of which are modus ponens, modus tollens, modus ponendo tollens, and modus tollendo ponens. Let x be a set of true values of some attributes observed simultaneously. Deductive reasoning rules of the second type are: 1. Using implication: Let r be an implication, left(r) be the left part of r and right(r) be the right part of r. If left(r) ⊆ x, then x can be extended by right(r) : x ← x ∪ right(r). Using implication is based on modus ponens: if A, then B; A; hence B. 2. Using interdiction: Let r be an implication y →not k. If left(r) ⊆ x, then k is the forbidden value for all extensions of x. Using interdiction is based on modus ponendo tollens: either A or B (A, B — alternatives); A; hence not B; either A or B; B; hence not A. 3. Using compatibility: Let r = ’a, b, c → k, VA’. If left(r) ⊆ x, then k can be used to extend x along with the calculated value VA for this extension (a special consideration is required for calculating VA). 4. Using diagnostic rules: Let r be a diagnostic rule such as ’x, d → a; x, b →not a’, where ’x’ is true, and ’a’, ’not a’ are hypotheses or possible values of some attribute. Using the diagnostic rule is based on modus ponens and modus ponendo tollens. There are several ways for refuting one of the hypotheses: – To infer either d or b by using existing knowledge; – To involve new known facts (extended context) and/or propositions for inferring (with the use of inductive reasoning rules of the second type) new implications for distinguishing between the hypotheses ’a’ and ’not a’; to apply the newly obtained rules; – To get the direct answer on whether d or b is true by involving an external source of knowledge. 5. Using rule of alternatives: Let ’a’ and ’b’ be two alternatives (mutually exclusive) hypotheses about the value of some attribute, and the truth of one of hypotheses has been established, then the second hypothesis is rejected. Using the rule is based on modus tollendo ponens: either A or B (A, B — alternatives); not A; hence B; either A or B; not B; hence A.
We can call the rules listed above the rules of “forward inference”. However, we have in natural classification reasoning so called “backward inference”. 6. Generating hypothesis or abduction rule. Let r be an implication y → k. We have “if k is true, then y may be true”. 7. Using modus tollens. Let r be an implication y → k. If ’not k’ is inferred, then ’not y’ is also inferred.
When applied, the above given rules generate the reasoning, which is not demonstrative. The purpose of it is to infer all possible hypotheses of the value of some objective attribute. It is essential that hypotheses do not contradict with knowledge (first-type rules) and the observable real situation, where the reasoning takes place (contextual knowledge). Inference of hypotheses is reduced to constructing all intrinsically consistent extensions of a set of values in which the number of involved attributes is maximum possible (there are no prohibited pairs of values in such extensions). All hypotheses have different admissibility determined by the quantity and “quality” of compatibility rules involved in reasoning.
A very simple structure of knowledge base (KB) and an example of applying the rules of second type for a pattern recognition problem can be found in [19]. The process of deductive reasoning can require inferring new rules of the first type from data when i) the result of reasoning contains several hypotheses and it is impossible to choose one and only one of them (uncertainty), and ii) it is impossible to infer any hypothesis.
Inductive steps of classification reasoning consist in using already known facts, observations and experimental results for inferring implications and their correcting. The main forms of induction have been formulated by J. Stuart Mill [12]. The formalization of these forms of induction has been offered by V.K. Finn [6]. For inferring GDTs, the Combined Similarity and Difference Method of the Mill are used and realized by means of inductive inference rules of the second type proposed in [13].
Deductive rules of the second type described above also work for inductive inferring implications since implications obtained are involved immediately to reduce the search space. In the paper, we shall illustrate using the forbidden and diagnostic rules of the second type for GDTs inferring. 3
Assume that G = 1, N be the set of objects and M = {m1, m2, . . . , mj , . . . mm} be the set of values. The object descriptions are represented by rows of a table, columns of which are associated with the attributes taking their values in M (see, please, Tab.1).
Denote by {Bg| Bg ⊆ M, g ∈ G} the description of an object. The Galois connection [21] between the ordered sets (2G, ⊆) and (2M , ⊆), i.e. 2G → 2M and 2M → 2G, is defined by the following mappings called derivation operators (see although different notations in [16,9]): for A ⊆ G and B ⊆ M , A0 = val(A) = {intersection of all Bg| Bg ⊆ M, g ∈ A} and B0 = obj(B) = {g| g ∈ G, B ⊆ Bg}. We consider obj(B) = {intersection of all obj(m)| obj(m) ⊆ G, m ∈ B}. In the Formal Concept Analysis, for g ∈ G and m ∈ M , {g}0 or simply g0 is called object intent, and {m}0 or simply m0 is called attribute extent [7].
There are two closure operators [16]: 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)) and a set B is closed if B = val(obj(B)). If A0 = B & B0 = A, then a pair (A, B) is called a formal concept, subsets A and B of which are called concept extent and intent, respectively.
A triple (G, M, I), where I is a binary relation G × M is called a formal context K. Let K := (G , M, I ) and I := I ∩ (G × M ), where ∈ {+, −} (one can add the value τ if there is an undefined object) [8]. K± := (G+ ∪ G−, M ∪ {KL}, I+ ∪ I− ∪ (G± × {KL})).
Definition 2. A Diagnostic (classification) Test (DT) for G+ is a pair (A, B) such that B ⊆ M , A = obj(B) 6= ∅, A ⊆ G+, and B 6⊆ val(g), ∀g ∈ G−. Equivalently, obj(B) ∩ G− = ∅.
Definition 3. A DT (A, B) for G+ is maximally redundant if obj(B ∪ m) ⊂ A for all m ∈/ B and m ∈ M .
Definition 4. A DT (A, B) for G+ is irredundant if any narrowing B∗ = B \ m, m ∈ B implies that (obj(B∗), B∗)) is not a test for G+. Definition 5. A DT (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+.
If a good test (A, B) for G+ is maximally redundant (GMRT), then any extension B∗ = B ∪ m, m ∈/ B, m ∈ M implies that (obj(B∗), B∗) is not a good test for G+. The relation GMRTs to the Formal Concept Analysis is considered in [17].
Any object description d(g), g ∈ G in a given classification context is a maximally redundant set of values because ∀m ∈/ d(g), m ∈ M, obj(d(g) ∪ m) is equal to ∅.
In Tab.1, ((
There are two kinds of subtasks for inferring GMRTs: 1. given a set of values B, where B ⊆ M, obj(B) 6= ∅, B 6⊆ d(g), ∀g ∈ G−, 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 to form subcontexts of a given classification context K±. In the first case, we have to include in subcontext all positive objects, the descriptions of which intersect B. The subtask is useful to find all GMRTs intents of which are contained in the description d(g) of an object g. This subtask is considered in [5] for fast incremental concept formation. The following notions of object and value projections are developed to form subcontexts [18].
Definition 6. The projection proj(d(g)), g ∈ G+ on the set D+, where D+ is the set of descriptions of all positive objects, is denoted by { | z z = d(g) ∩ d(g∗) 6= ∅, d(g∗) ∈ D+ & (obj(z), z) is a test for G+}. Note that d(g) ∈ proj(d(g)). Definition 7. The value projection on a given set D+ proj(B) is {d(g) | B ⊆ d(g), d(g) ∈ D+} or, equivalently, proj(B) = {d(g) | g ∈ (obj(B) ∩ G+)}.
The projections define the methods to construct two kinds of subcontexts of K±. The following theorem gives the foundation of reducing subcontexts [14]. Theorem 1. Let X ⊆ M, (obj(X), X) be a maximally redundant test for positive objects and obj(m) ⊆ obj(X), m ∈ M . Then m can not belong to any GMRT for positive objects different from (obj(X), X).
Let splus(m) be obj(m)∩G+ (obj(m)∩G−) and SPLUS={splus(m), m ∈ M }. Consider an example of reducing subcontext in Tab. 1.
For values Hazel, Brown, Tall, Blue, Blond, and Low, SPLUS={obj(m)∩G−} = {{3, 4, 6}, {2, 3, 5}, {3, 4, 5}, {2, 5}, {4, 6}, {2, 6}}.
We have val(obj(Hazel)) = Hazel, hence ((
It is essential that the projection is a subset of object descriptions defined on a certain restricted subset t∗ ⊆ M of values. Let s∗ be the subset of objects, descriptions of which produce the projection. In the projection, splus(m) = obj(m) ∩ s∗, m ∈ t∗.
Let STGOOD be the partially ordered set of elements s such that (s, val(s)) is a good test for D+.
Forming the Set STGOOD. The important part of our basic recursive algorithm is how to form the set STGOOD. Let L = (2S , ≤) be the set lattice [22]. The ordering determined in the set lattice coincides with the set-theoretical inclusion. Subset s1 is absorbed by subset s2, i.e. s1 ≤ s2, if and only if s1 ⊆ s2. Under formation of STGOOD, subset s ⊆ G+ is stored in STGOOD if and only if it is not absorbed by any element of this set. It is necessary also to delete from STGOOD all the elements that are absorbed by s if s is stored in STGOOD. Thus, when the algorithm is over, the set STGOOD contains all the collections of objects that are the extents of GMRTs and only such collections. The set TGOOD of all the GMRTs is obtained as follows: TGOOD = {tg| tg = (s, val(s)), s ∈ STGOOD}.
The basic recursive procedure for solving any kind of subtasks has been described in [20]. 5
Algorithms of GMRTs inferring are constructed by the rules of selecting and ordering subcontexts of the main classification context. Before entering into the details, we give some new definitions.
Definition 8. Let t be a set of values such that (obj(t), t) is a test for G+. 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.
Definition 9. Let s ⊆ G+, assume also that (s, val(s)) is not a test. The object g, g ∈ s is said to be an essential in s if (s \ g, val(s \ g)) proves to be a test for a given set of positive objects.
Generally, we are 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.
Finding quasi-maximal (minimal) subsets of objects and values is the key procedure behind searching for initial content of STGOOD and determining the number of subtasks to be solved. 5.1
Using the Diagnostic Rule of the Second Type 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 first object g1 of s∗, then we take the next object g2 of s∗ and evaluate the function to be test({g1, g2}, val({g1, g2})). If the value of the function is true, then we take the next object g3 of s∗ and evaluate the function to be test({g1, g2, g3}, val({g1, g2, g3})). If the value of the function to be test({g1, g2}, val({g1, g2})) is f alse, then the object g2 of s∗ is skipped and the function to be test({g1, g3}, val({g1, g3}))) is evaluated. We continue this process until we achieve the last object of s∗. This procedure can be considered as a realization of the diagnostic rule of the second type.
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 objects is in Tab.4. The initial content of STGOOD0
is {(
In what follows, 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 = {(
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.
As a result of this procedure, we have quasi-maximal subset sbmax(M ) of M , such that (obj(sbmax(M )), sbmax(M )) is not a test for positive examples. Then subset LEV = M \ sbmax(M ) is quasi-minimal subset of essential values in M . We have the following LEV : {m16, m18, m19, m20, m21, m22, m23, m24, m26}. Note, that searching for the number of subtasks to be solved is also based on using the diagnostic rule of the second type. G D+ 15 m3m8m16m23m24 32 m1m2m3m7m9m13m18 16 m7m8m9m16m18 33 m1m5m6m8m9m19m20m22 17 m1m21m22m24m26 34 m2m8m9m18m20m21m22m23m26 18 m1m7m8m9m13m16 35 m1m2m4m5m6m7m9m13m16 19 m2m6m7m9m21m23 36 m1m2m6m7m8m13m16m18 20 m19m20m21m22m24 37 m1m2m3m4m5m6m7m12m14m15m16 21 m1m20m21m22m23m24 38 m1m2m3m4m5m6m9m12m13m16 22 m1m3m6m7m9m16 39 m1m2m3m4m5m6m14m15m19m20m23m26 23 m2m6m8m9m14m15m16 40 m2m3m4m5m6m7m12m13m14m15m16 24 m1m4m5m6m7m8m16 41 m2m3m4m5m6m7m9m12m13m14m15m19 25 m7m13m19m20m22m26 42 m1m2m3m4m5m6m12m16m18m19m20m21m26 26 m1m2m3m5m6m7m16 43 m4m5m6m7m8m9m12m13m14m15m16 27 m1m2m3m5m6m13m18 44 m3m4m5m6m8m9m12m13m14m15m18m19 28 m1m3m7m13m19m21 45 m1m2m3m4m5m6m7m8m9m12m13m14m15 29 m1m4m5m6m7m8m13m16 46 m1m3m4m5m6m7m12m13m14m15m16m23m24 30 m1m2m3m6m12m14m15m16 47 m1m2m3m4m5m6m8m9m12m14m16m18m22 31 m1m2m5m6m14m15m16m26 48 m2m8m9m12m14m15m16 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 tg, g ∈ G+, we have tg ∩ LEV = ∅. Then tg ⊆ M \ LEV. But M \ LEV is included at least in one of the negative object descriptions and, consequently, tg also possesses this property. But it contradicts to the fact that tg is the description of a positive object. tu Proposition 2. Assume that X ⊆ M . If X ∩ LEV = ∅, then to be test(obj(X), X) = f alse.
Proposition 3. Let K± be a given classification context. For finding all GRMTs containing in K±, it is sufficient to solve this problem only for subcontexts associated with essential values in M (the set LEV).
Proposition 2 is the consequence of Proposition 1. The poof of Proposition 3 is obvious.
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, consequently, delete t14 from consideration. As a result of deleting m12 and t14, we have the modified set SPLUS (Tab.5). 5.2
Using the Rule of Alternative for Splitting Subcontexts Essentially, searching for GMRTs turns out a process of generating deductive reasoning rules of the first type, which are used immediately during this process. Now we shall give an example of constructing and using the rules of alternative (forbidden rules). 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} Form all the pairs of objects (i, j) ⊆ G+; form a set FR of forbidden pairs of objects, FR = {(i, j) : to be test((i, j), val(i, j)) is f alse} (Tab. 6); then the set of admissible pairs is ADM = {(i, j) : to be test((i, j), val(i, j)) is true} (Tab. 6).
Each forbidden pair (i, j) generates rule of alternative: j OR i → true(always); i, j → f alse. This rule says that i and j cannot simultaneously enter in any extent of GMRTs, either i or j but not both.
These rules of alternatives allow splitting any splus(m), m ∈ M into subsets not containing any forbidden pair of objects. An example is in Tab. 7.
As a result of splitting, we shall obtain the splitting tree, leaves of which
are subsets of objects not containing any prohibited object pairs. Subcontexts
for GMRTs inferring are leaves of the tree with the number of objects more or
equal to 4. So, in Tab. 7, we have only one subcontext (
An analysis of set ADM leads to using some inductive reasoning rules [19]. If element j enters in sq+1, then it must enter in q proper subsets of sq+1, where sq+1 is a set containing (q + 1) elements. If we observe that j enters in only one doublet (pair), then it cannot enter in any triplet. If we observe that j enters in only one triplet, then it cannot enter in any quadruplet and so on. If an element enters in two and only two doublets, it means that it will enter only in one triplet. If an element enters in three and only three doublets, it can enter in only one quadruplet.
This inductive reasoning is applicable to constructing triplets from doublets,
quadruplets from triplets and so on. In our example: Object 9 enters in one and
only one doublet, hence (
splus(m7) → {2, 3, 4, 6, 8, 11} splus(m18) ! f3; 10g splus(m24) → {1, 2, 3, 4, 7, 12} splus(m2) → {1, 10, 11, 12} splus(m20) → {4, 7, 8, 10, 11, 12} splus(mb) → {2, 3, 4, 7, 8} splus(m21) → {1, 4, 8, 9, 10, 11, 12} splus(m19) → {3, 8, 11} splus(m26) → {1, 2, 3, 4, 7, 10, 11, 12} We analyze triplets in SPLUS: splus(m ) = {2, 8, 10}, splus(m1) = {1, 4, 11}, ∗ splus(m19) = {3, 8, 11}, and splus(m13) = {3, 8, 10}. As a result, we obtain the extents of two new GMRTs {3, 11} and {8, 10}. After that, we can delete object 10. Then we can delete values m5, m2, and m4 after analyzing their modified splus. Now we split splus(m22), splus(m20), splus(m21), splus(m24), and splus(m26), because these values are the only remaining essential values in the set LEV. Tab. 9 shows the number of subtasks in splitting trees for these essential values and new obtained tests.
Some words about future investigations. The most important mathematical tasks worth solving are the following: 1. For irredundant splus(m) to determine whether it contains extents of new
GMRTs; 2. Optimization of selecting forbidden pairs of objects in order not to obtain repetition of subsets in splitting trees. 6
A sketch of classification reasoning is given in the paper. The key notions of the reasoning are notions of classification and its good approximations based on good diagnostic tests. The good diagnostic tests have the dual nature: they generate functional and implicative dependencies and, in the same time, sets of objects satisfying these dependencies. The dependencies are logical assertions on the base of which deductive phase of classification reasoning is realized.
In the paper, we deal only with GMRTs as value implications. An algorithm for inferring GMRTs from a set of data is given. A decomposition of the main task of inferring GMRTs into subtasks associated with the certain types of subcontexts is introduced.
There are various ways of using the proposed decompositions and extracted initial information about GMRTs, but we confine ourselves to the most important ideas allowing to obtain not only tests (and corresponding knowledge) but also, simultaneously, contexts inside of which these tests have been inferred. Currently, there is considerable interest in contextual information search and representation for using it to improve web search results or query expansion [3,4,10]. Classification reasoning can serve as a basic tool for constructing and using content-dependent knowledge in different problem domains and applications.