A problem of incremental granular computing is considered in the tasks of classification reasoning. Objects, values of attributes, partitions of objects (classifications) and Good Maximally Redundant Tests (GMRTs) (special kind of formal concepts) are considered as granules. The paper deals with inferring GMRTs. They are good tests because they cover the largest possible number of objects w. r. t. inclusion relation on the set of all object subsets. Two kinds of classification subcontexts are defined: attributive and object ones. The context decomposition leads to a mode of incremental learning GMRTs. Four cases of incremental learning are proposed: adding a new object (attribute value) and deleting an object (attribute value). Some illustrative examples of four cases of incremental learning are given too.
Information granules are becoming important entities in data processing at the different levels of data abstraction. Information granules have also contributed to increasing the precision in data processing [9]. Application of information granules is one of the problem-solving methods based on decomposing a big problem into subtasks.
Several studies devoted to evolving information granules to adapt to changes in the streams of data are described in [12]. The process of forming information granules is often associated with the removal of some element of data or dealing with incomplete data [1]. Generally, we consider object, property, class of objects, and classification as the main granules of human classification reasoning.
The paper deals with inferring good classification (diagnostic) tests. Tests are good because they cover the largest possible number of objects w. r. t. the inclusion relation on the set of all object subsets.
Two kinds of classification subcontexts are defined: attributive and object ones. The context decomposition leads to a mode of incremental learning good Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). classification tests. Four cases of incremental learning are proposed: adding a new object (attribute value) and deleting an object (attribute value). Some heuristic rules allowing decreasing the computational complexity of inferring good tests are considered too.
In [7], it is considered the link between Good Test Analysis (GTA) and Formal Concept Analysis (FCA) [5]. To give a target classification of objects, we use an additional attribute KL6∈U . In Tab. 1, we have classification KL containing two classes: the objects in whose descriptions the target value k(+) appears and all the other objects.
The “atom” of plausible human reasoning is a concept. The concepts are represented by theirs names. We shall consider the following roles of names in reasonings: a name can be the name of object, the name of class of objects and the name of classification or collection of classes. With respect to the role of name in knowledge representation schemes, it can be the name of attribute or attribute’s value. A class of objects may contain only one object; hence the name of the object is a case of the name of a class. For example, fir-tree can be regarded as the name of a tree or the name of a class of trees. Each attribute genarates a classification of a given set of objects; hence the names of attributes can be the names of classifications and the attribute values can be the names of classes. In the knowledge bases, the sets of names for objects, classes and classifications must not intersect.
Let k be the name of an objects’ class, c be the name of a property of objects (value of an attribute), and g be the name of an object. Each class or property has only one maximal set of objects as its interpretation that is the set of objects belonging to this class or possessing this property: k→I(k) = {g : g≤k}, c→I(c) = {g : g≤c}, where the relation ’≤’ denotes ’is a’ relation and has causal nature (the dress is red, an apple is a fruit). Each object has only one corresponding set of all its properties:C(g) = {c : g≤c}. We shall say that C(g) is the description of object g. The link g→C(g) is also of causal nature. We shall say that C(k) = {∩C(g) : g≤k} is the description of class k, where C(k) is a collection of properties associated with each object of class k. The link k→C(k) is also of causal nature. Figure 1 illustrates the causal links between classes of objects, properties of objects, and objects.
Clearly, each description (a set of properties) has one and only one interpretation (the set of objects possessing this set of properties). But the same set of objects can be the interpretation of different descriptions (equivalent with respect to their interpretations). The equivalent descriptions of the same class are said to be the different names of this class. The task of inferring the equivalence relations between names of classes and properties underlies the processes of plausible reasoning.
The identity has the following logical content: class K is equivalent to property k ((K↔k)) if and only if the interpretations I(K), I(k) on the set of conceivable objects are equal I(K) = I(k). It is possible to define also the relationship of approximate identity between concepts: k approximates B (k≤B) if and only if the relation I(k)⊆I(K) is satisfied. We can consider instead of one property (concept) any subset of properties joined by the union ∪ operation: (c1∪c2∪ . . . ∪ci∪ . . . ∪cn)≤B.
k → c(k) k ← c(k)
Objects
Classes of objects
Properties of objects k : g ≤ k
c : g ≤ c g : g ≤ k
g : g ≤ c
Connection directed from ’Properties of objects’ to ’Classes of objects’ is constructed by learning from examples of objects and their classes. This connection is also of causal nature, it is expressed via the “if – then” rule: to say that “if tiger, then mammals” means to say that I(tiger) ⊆ I(mammals). 3 .
Let G = {1, 2,. . ., N} be the set of objects’ indices (objects, for short) and M = {m1, m2, . . ., mj, . . . mq} be 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 R the columns of which are associated with the attributes taking their values in M. Denote a description of g∈G by δ(g). Let D+ and G+ (D− = D/D+) and G− = G/G+) be the sets of positive or negative object descriptions and the set of indices of these objects, respectively. The definition of good tests is based on two mapping 2G → 2M, 2M → 2G. Let A ⊆ G, B ⊆ M. Denote by Bi, Bi ⊆ M, i = 1,. . ., N the description of object with index i. The relations 2G → 2M, 2M → 2G are: A0 = val(A) = {intersection of all Bi: Bi ⊆ M, i ∈ A} and B0 = obj(B) = {i: i ∈ G, B ⊆ Bi}.
These mapping are the Galois’s correspondences. Operations val(A), obj(B) are reasoning operations (derivation operations). We introduce two generalization operations: generalization of(B) = B00= val(obj(B); generalization of(A) = A00 = obj(val(A)). These operations are the closure operations [8]. 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, g0 is called object intent and m0 is called value extent. We illustrate the derivation and generalization operations (Tab. 1):
A = {4, 8}, val(A) = {x4 = 1, x8 = 2}; A00 = obj({x4 =1, x8 = 2}) = {4, 8} = A;
m = {x8 = 0}, obj ({x8 = 0}) = {5, 7, 12}; m00 = val({5, 7,12}) = {x1 = 2, x4 = 2, x5 = 1, x6 = 2, x8 = 0 }; B = {x4 = 3, x5 = 1}, obj({B}) = {3,9}; B00 = val({3, 9}) = {x1 = 2, x2 = 3, x3 = 1, x4 = 3, x5 = 1, x7 = 2, x8 = 2}.
Definition 1. A Diagnostic Test (DT) for G+ is a pair (A, B) such that B⊆M, A = obj(B)6=∅, A⊆G+, and obj(B)∩δ(g) = ∅, (∀g)g∈G−.
Definition 2. A Diagnostic Test (DT) for G+ is maximally redundant if obj(B∪m)⊂A for all m∈M \ B.
Definition 3. A Diagnostic Test (DT) for G+ is good iff any extension A∗ = A∪i, i∈G+\A, implies that (A∗, val(A∗)) is not a test for G+.
Note that the definition of tests for G+ does not differ from the definition of positive hypotheses given in [6] and [4] in the language of predicates. Definitions 2, 3, 4 remain true if G+ is replaced by G−. In what follows, we are interested in inferring GMRTs for positive class of objects. As far as Formal Concept Analysis development and application, the following surveys [11,10,3,2] can be seen
Some examples of formal concepts are in Tab. 1. Let us check if a pair (A,
B) = ((
1. to find all GMRTs intents of which are included in the description of an object; 2. to find all GMRTs into intents of which a given set of values is included. To solve these subtasks, we need to form subcontexts (projections) of a given classification context.
Definition 4. Let B⊆M . The object projection proj(B, G+) on G+ is proj(B, G+) = {δ(g) ∩ B|g∈G+, δ(g)∩B6=∅, and (obj(δ(g)∩B), δ(g)∩B) is a test for G+}.
An example of object projection proj(d2) on G+ is in Tab. 2.
We propose four cases of modifying classification contexts: adding/removing objects and adding/removing values of attributes. Modification of GMRTs is based on a decomposition of classification contexts into value and object subcontexts and inferring GMRTs in them. Let ST GOOD+ and ST GOOD− be the current sets of extents of GMRTs for positive and negative class of objects, respectively. We mean that the process in which a change of the classification context implies only updating the sets ST GOOD+ and ST GOOD−. The classification context can be changed as follows: a new object is added with the indication of its class membership; an object is deleted from G+ or G-; a value is introduced into the classification context; a value is deleted from the classification context. Updating ST GOOD+ and ST GOOD− is performed with the use of only subcontexts associated with added (deleted) object or value.
1. Checking whether it is possible to extend the extents of some existing GMRTs for the class to which a new object belongs (a class of positive objects, for certainty). 2. Inferring all GMRTs, intents of which are included into the new object description; for this goal, the first kind subtask is used. 3. Deleting GMRTs for positive class extents of which are included in the extent of any new GMRTs. 4. Checking the validity of GMRTs for negative objects, and, if it is necessary, modifying invalid GMRTs (test for negative objects is invalid if its intent is included in a new (positive) object description); for this goal, the second kind subtask is used.
Let s∈ST GOOD− and Y = val(s). If Y ⊆ tnew(+), then s should be deleted from ST GOOD− because (s, Y ) is invalid test for G−.
Proposition 1. obj(Y ) forms the subcontext for finding corrected tests for
Proof. Y ⊆X ↔ obj(X) ⊆ obj(Y ). Assume that there exists a GMRT (with intent Z) for G− such that obj(Z) 6⊂ and 6= obj(Y ). Then obj(Z) contains some objects not belonging to obj(Y ) and Z will be included in some descriptions of objects not belonging to obj(Y ) and, consequently, Z has been obtained at the previous steps of the incremental algorithm for finding all GMRTs for G−.
Consider an example of adding object in the process of inferring GMRTs for
the data in Tab. 1. Let us fix the classification context with 3 first objects from
G+ and all the objects of G−. For this current situation we have one GMRT for
G+, namely, ((
Case 2 Suppose that an object g is deleted from G+ (G−) The following actions are necessary: 1. ∀s, s∈ST GOOD+ (ST GOOD−), g∈s, delete g from s; in this connection, we observe that (s\g, val(s\g)) remains to be the test for G+ (G−). 2. We denote modified test (s\g, val((s\g)) by MT. We have the following possibilities: – the intent of MT has not changed; then MT is a GMRT for G+(G− ) in the modified context; – the intent of MT has changed and the extent of MT is included in the extent of an existing GMRT for G+(G−), then MT must be deleted; otherwise MT is a GMRT for G+(G−).
An example of deleting object. Let us fix the whole classification context (Tab. 1).
We have one GMRT for G- obtained in this context: ((
Case 3 Suppose that a new value m∗ is added to the classification context: m∗ appears in the descriptions of some positive and negative objects and M ::= m∗∪M . The task of finding all GMRTs for G+(G−) whose intents contain m∗ is reduced to the task of the second kind. The subcontext for this task is determined by the set of all objects whose descriptions contain m∗. As result, we obtain all the GMRTs (obj(Y ), Y ) for G+(G−) such that m∗∈Y . We can add a set of values if we want that all these values will be included simultaneously in the intents of GMRTs.
Case 4 Suppose that some value m is deleted from the classification context. Let a GMRT (obj(X), X) for G+(G−) be transformed into (obj(X\ m), X\ m). Then we have ((X\m) ⊂X) ↔ (obj(X) ⊆ obj(X\m)).
Consider two possibilities: obj(X\m) = obj(X) and obj(X) ⊂ obj(X\m). In the first case, (obj(X\m), X\m) is a GMRT for G+(G−). In the second case, (obj(X\m), X\m) is not a test. However, obj(X\m) can contain extents of new GMRTs for G+(G−) and these tests can be obtained by using the subtask of the second kind.
An example of deleting value x6 = 2. The GMRT for the negative class ((
Recognizing the class membership for a new object not belonging to training set is performed as follows: – If (and only if) description of object contains an intent of GMRT of only one class, then the object can be assigned to this class; – If description of an object does not contain any intent of GMRTs, then we have the case of uncertainty.
In two last cases, it is necessary to continue learning by adding new objects or to change the classification context. 6
The paper examines the relationship between an incremental model of good classification test inferring with granular computing. In the process of finding good tests, the following granules are highlighted: objects, attribute values, and object classes. The incremental test inferring is carried out as a process in which granules can be added and removed, changing the classification context. The decomposition of classification contexts into subcontexts is considered based on the selection of objects and values of attributes (granules). Thus, granules become active elements of test inferring and allow this process to be made data driving based on data selection.
The research was partially supported by Russian Foundation for Basic Research, research project No. 18-07-00098A. This research work was supported by the Academic Excellence Project 5-100 proposed by Peter the Great St. Petersburg Polytechnic University.