Modi cation of Good Tests in Dynamic Contexts: Application to Modeling Intellectual Development of Cadets

Abstract

An approach to incremental learning of Good Maximally Redundant Diagnostic Tests (GMRTs) is considered. GMRT is a special formal concept in Formal Concept Analysis. Mining GMRTs from data is based on Galois lattice construction. Four situations of learning GMRTs are considered: inserting an object (value) and deleting an object (value). An application to modeling intellectual development of cadets is proposed. We explore two datasets of female medical cadets. First dataset is formed at the moment of admission to academy, and another is formed at the end of second year of learning. Classi cation attribute (dynamics of cadets' intellectual development) is based on analysis of psychological questionnaire invented by M.M. Reshetnikov and B.V. Kulagin. Structural model attributes are based on MMPI questionnaire adopted by L.N. Sobchik.

Keywords

• good classi cation test
• formal concept
• concept lattice
• incremental learning
• dynamic formal context
• educational data mining
• intellectual development
• medical cadets

-

Good Maximally Redundant Diagnostic Tests (GMRTs) [ 11 ] can be considered as formal concepts with minimal by the inclusion relation intents, see, please also minimal hypotheses in [ 5 ]. Mining of GMRTs from data is based on constructing the Galois Lattice. The main motivation of incremental learning GMRTs is to provide an expert a way of step-by-step changing of the prediction model. This can be useful, for example, to evaluate an impact of attribute (object) to a prediction model, as well as to improve e ciency of inferring GMRTs (only a part of GMRTs should be recalculated instead of whole set in a batch inferring case).

Incremental learning to construct formal concepts (FCs) require incremental algorithms for Galois lattice generation. In this process, it is generally assumed that the data (objects, itemsets, or transactions) are added gradually but not deleted. Much attention has been paid in recent years to the problem of concept lattice incremental construction [ 6 ],[ 9 ],[ 16 ],[ 20 ]. An algorithm of incremental generating GMRTs has been considered in [ 14 ].

On the other hand, there is a practical demand to modify the concept lattice already constructed under dynamic data changes. In this case, it is necessary to consider the possibility of both adding and deleting the data (objects, attributes). This problem is not yet investigated su ciently. Deleting objects (and only objects) is considered in [ 2 ] and [ 21 ]. Algorithms RemoveObject and DeleteObject are proposed in rst and second papers, respectively. These algorithms have been essentially improved with respect to their computational complexity in [ 22 ]: in newly proposed algorithm FastDeletion, it is necessary to compare a modi ed concept only with one of its lower neighbours by the order relation in the concept lattice, whereas, in previous two algorithms, this comparison is performed with all of its lower neighbours.

However modifying the data or the formal classi cation contexts with the use of which a concept lattice has been constructed can be realized not only by adding or deleting objects but also by adding or deleting attributes. Such a modi cation of the concept lattice is even less explored than the problem of deleting objects. Of interest in this regard, the paper [ 8 ], in which the authors solve the problem of removing an incidence from a formal context.

All the four variants of changing formal contexts, i.e. adding (deleting) an object and adding (deleting) an attribute are considered in [ 2 ]. Recent publication on this topic [ 16 ] provides an e cient algorithm of modifying the formal contexts by adding objects, which may include, in their descriptions, some new attributes. Modi cation of the order relation in the concept lattice is also determined. A peculiarity of the proposed algorithm is that it de nes new and modi ed concepts without using previously built lattice but the only available data. New formal concept is a concept in new data with some of added objects to its object set (extent) and attribute set (intent) not equal to intent of any concept in the data before updating. Modi ed formal concept is a concept in new data with the same intent as some existing concept in the data before updating; and its extent is enlarged by some introduced objects. The algorithm proposed is based on algorithm Close-by-One (CbO) of generating formal concepts [ 10 ] and its next re nements FCbO [ 16 ], PFCbO [ 17 ].

As for removing objects, this process is reduced to adding objects. If description of an object is changed, then this object is removed from the formal context and after that it is treated as an introduced object with new description. Adding and removing attributes is seen as similar to adding and removing objects, but objects and attributes in the algorithm and formal context simply swap places. Updating GMRTs proposed in the present paper covers, likewise in [ 16 ], four cases adding/removing objects and adding/removing attributes (values of attributes). New and modi ed GMRTs (formal concepts) are determined. Modi cation algorithms are based on decomposition of formal classi cation context into attributive and objects sub-contexts and using a previously developed incremental algorithm for inferring GMRTs given in [ 14 ].

The paper is organized as follows: Sec. 2 gives the main de nitions of GMRTs. A decomposition of the formal classi cation contexts in two kinds of subcontexts is considered. Two kinds of corresponding sub-tasks are required for updating GMRTs in subcontexts. A dataset is described in Sec. 3. An application of four updating GMRTs cases is considered in Sec. 4. The application is supplied by illustrative examples using cadet dataset. 2

Basics of Good Test Analysis

Let G be the set of objects (object indices for short). Assume that objects are described by a set U of symbolic (numeric) attributes, and dom(attri) \ dom(attrj ) = ;; 8attri; attrj 2 U; i 6= j, where dom(attri) is the set of values of attri.

Let M = f[dom(attr); attr 2 U g; then one can construct : G ! D, where D = 2M is a set of all possible object descriptions. We denote a description of g 2 G by (g), and the sets of positive and negative object descriptions by D+ = f (g)j g 2 G+g and D = f (g)j g 2 G g, respectively. The Galois connection [ 15 ] between the ordered sets (2G; ) and (2M ; ), i.e. 2G ! 2M and 2M ! 2G, is de ned by the following mappings called derivation operators: for A G and B M , A0 = val(A) = fintersection of all (g)j g 2 Ag and B0 = obj(B) = fgj g 2 G; B (g)g. The notation ( )0 is from [ 3 ], see also similar notation ( ) in [ 4 ].

There are two closure operators: generalization of(B) = val(obj(B)) and generalization of(A) = 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 [ 3 ], subsets A and B are called concept extent and intent, respectively. All formal concepts form a Galois (concept) lattice. A triplet (G; M; I), where I is a binary relation between G and M , is a formal context K.

According to the goal attribute Cl we get some possible forms of the formal contexts: K := (G ; M; I ) and I := I \(G M ), where 2 f+; g (if necessary the value can be added to provide the unde ned objects) [ 5 ]. These contexts form a classi cation context K = K+ [ K .

De nition 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 = ; [ 12 ].

De nition 2. A diagnostic test (A; B) for G+ is maximally redundant if obj(B[ m) A for all m 2 M n B [ 12 ].

De nition 3. A diagnostic test (A; B) for G+ is good i any extension A = A [ i, i 2 G+ n A, implies that (A ; val(A )) is not a test for G+ [ 12 ].

In the paper, we deal with Diagnostic Tests, which are good and maximally redundant simultaneously (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+. In general case, a set B is not closed for

DT (A; B), consequently, DT is not obligatory a formal concept. GMRT can be regarded as a special type of a concept [ 12 ].

To transform inferring GMRTs into an incremental process, we introduced two kinds of subtasks [ 13 ]: 1. For a set G+, given a set of values B, 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. For a set G+, 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 to form subcontexts of a given classi cation context. The following notions of object and value projections are developed to form subcontexts.

De nition 4. The projection proj(d), d 2 D+ is denoted by Z = fzj z = (g) \ (g ) 6= ;; g 2 G+ and (obj(z); z) is a test for G+g, (g) 2 proj(d). De nition 5. The value projection proj(B) on a given set D+ is proj(B) = f (g) j B (g); g 2 G+g.

Let us consider four cases of incremental supervised learning GMRTs:

1. A new object becomes available over time. 2. Deleting an object from a classi cation context. 3. Adding a value (attribute) to a classi cation context. 4. Deleting a value (attribute) from a classi cation context.

In each case (stage of experiment in Sec.4) we obtain all the GMRTs in current K . 2.1

Adding an object to K

Suppose that each new object comes with the indication of its class membership. The following actions are necessary: 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, such that their intents included into the new object description. 3. 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).

Thus the following cognitive acts are performed: { Pattern recognition and generalization of knowledge (increasing the power of already existing inductive knowledge);

{ Increasing knowledge (inferring new knowledge); { Correcting knowledge (diagnostic reasoning).

The rst act modi es already existing tests. The second act is reduced to subtask of the rst kind. The third act can be reduced to subtasks both the rst and second kinds. Both of them are solved by any algorithm of GMRTs inferring.

Let STGOOD+ and STGOOD be the sets of all GMRT intents for positive and negative classes, respectively. Let s 2 STGOOD and Y = val(s). If Y tnew(+), where tnew(+) is the description of a new positive object, then s should be deleted from STGOOD .

For correcting the set of GMRTs for G , we have to nd all X M; Y X i.e. obj(X) obj(Y ); and (obj(X); X) is a GMRT for G . Thus obj(Y ) is a context for nding new tests for G .

We show that all new tests for G in this case are associated only with context obj(Y ): obj(X) obj(Y ) $ Y X. Assume that there exists a GMRT (with an intent Z) for G such that obj(Z) 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 incremental learning algorithm. 2.2

Deleting an object from K

Suppose that an object is deleted from K . The following actions are necessary: 1. Selecting the set GMRTsub of all GMRTs containing this object in the extents. 2. Modifying tests of GMRTsub by removing object from their extents; in this connection, we observe that this modifying does not lead to loss of property 'to be test for corresponding elements of GMRTsub'. 3. After modifying a test in GMRTsub, we have the following possibilities. Let Y be the intent of a test in GMRTsub and Y = val(obj(Y ) n i), where i is deleted object and Y = val(obj(Y ) [ i). If ((obj(Y ) n i) is included in the extent of an existing GMRTs, then this test ((obj(Y ) n i); Y ) has to be deleted; if Y = Y and ((obj(Y ) n i) is not included in the extent of any existing GMRT, then ((obj(Y ) n i); Y ) is a GMRT; if Y 6= Y , then ((obj(Y ) n i); Y ) is a new GMRT. 2.3

Adding a value (attribute) to K

Suppose that a new value m is added to the set M of attributes. The task of nding all GMRTs, intents of which contain m is reduced to the problem of the second kind. The subcontext for this problem is the set of all objects whose descriptions contain m . 2.4

Deleting a value (attribute) from K

Suppose that some value m is deleted from consideration. Let a GMRT (obj(X); X) be transformed into (obj(X n m); X n m). Then we have ((X n m) X) $ (obj(X) obj(X n m)). Consider two possibilities: obj(X n m) = obj(X) and obj(X) obj(X n m). In the rst case, (obj(X n m); X n m) is GMRT. In the second case, (obj(X n m); X n m) is not a test. However, obj(X n m) can contain extents of new GMRTs and these tests can be obtained by using subtasks of the rst or second kind. 3

Dataset Description 33 female medical cadets were involved in our experiment. First dataset was formed at the moment of admission to academy (2009 year), and another was formed at the end of second year of learning (2011 year). The datasets are without missing values. The cadets are the same in both datasets. Classi cation attribute (dynamics of cadets' intellectual development) is based on analysis of measuring methods called Analogy, Cubes, Syllogisms, and Verbal memory, see, please, [ 18 ].

For each person, the di erence of the estimates of each intellectual method has been calculated in two moments, taking into account the sign of the difference. Then these di erences are summarized for all intellectual methods. If the sign of sum is positive (plus), the dynamics is considered to be positive, if the sign of sum is negative (minus) and its number is greater than 2, then the dynamics is considered to be negative. If the sum is equal to 0 or not greater 2, then the dynamics was considered to be neutral (zero). See, please, transformation of Dyn-column into Cl-column in Tab. 2. Within 33 medical cadets we obtained 5, 10, and 18 persons with neutral, negative, and positive dynamics, respectively.

Structural model attributes are based on MMPI questionnaire adopted by L.N. Sobchik [ 19 ]. Each attribute value from MMPI questionnaire is transformed to T-scale value using special questionnaire keys and K correction scale, see, please, [ 19 ] for the further information. After that T-scaled values are transformed to the scale with ve values by means of rules given in Tab. 1. They respect L.N. Sobchik's representations of \normal" intervals. In Tab. 2 three abbreviations L, F, and K stands for Lie, Infrequency, and Defensiveness, respectively. They are validity scales. Ten other following scales are clinical: Hs (Hypochandriasis), D (Depression), Hy (Hysteria), Pd (Psychopathic Deviate), Mf (Masculinity/Feminity), Pa (Paranoia), Pt (Psychasthenia), Sc (Schizophrenia), Ma (Hypomania), and Si (Social Introversion).

For the further considerations, we include in training set only the persons with positive and negative dynamics of intellectual development.

Modi cation of Good Tests in Dynamic Contexts 57

Experiments and discussion of results

The aim of modeling is to obtain GMRTs allowing to distinguish Class 1 and Class 2 of persons characterised by positive and negative dynamics of intellectual development, respectively. Intents of GMRTs have been regarded as logical rules determining the membership of persons to one or another class.

Recognizing the class membership for new persons not belonging to training set is performed as follows: If (and only if) description of a person contains a logical rule of only one class, then the person can be assigned to this class; if description of a person contains logical rules of both Class 1 and Class 2, then we have the case of contradiction; if description of a person does not contains any logical rules, then we have the case of uncertainty. In two last cases, it is necessary to continue learning by adding new persons' descriptions or to change the classi cation context.

Incremental learning of GMRTs is partitioned into several stages (see, please, Tab. 3) in accordance with expert reasoning. First seven stages were conducted without attributes Hs, D, Sc, and Si. Stage 1: training set contains 6 rst persons of Class 1 and 6 rst persons of Class 2. The result of Stage 1 is in Tab.4.

Stage 2 is a pattern recognition one; the control set contains persons 7 and 8 of Class 2 and persons 7 { 17 of Class 1. All persons of Class 2 and 5 persons (8, 9, 13, 14, 17) of Class 1 have been recognized correctly. Persons 10, 11, 15 of Class 1 have been recognized as persons of Class 2, and persons 7, 12, 16 of Class 1 have been assigned to neither of these classes. During Stage 4, rule (L=5,K=5,Pd=4,Pa=4) for Class 2 val(13) for person 13 of Class 1. This rule is deleted. During Stage 5, rule (Hy=3,Pd=3,Ma=4) for Class 2 is deleted (this rule val(11) for person 11 of Class 1). During Stage 6, two rules were absorbed Rule No L F K Hy Pd Mf Pa Pt Ma Class Persons 1 2 3 1 2 3

4 4 by Rule (Pd=3,Pa=4) and some new rules for Class 1 were obtained. Stage 7: correcting the rules for Class 2. The result is in Tab. 5.

Let us suppose that an expert decides to change one attribute in the model obtained in the previous stage. The problem is how to choose a candidate for deleting and then a candidate for adding. The most simple way is to do what an expert wish to see, however we can propose to an expert some more criteria to take into account. Let us imagine that we get some sets of GMRTs after deleting or adding an attribute. According to a de nition of GTA we would recommend to maximize a total number of objects for a GMRT set (sum of rules' coverings) and minimize a total number of attributes for a GMRT set (sum of rules' lenghts ). Minimizing a number of GMRTs can be one more criterion. An expert can choose only one criterion or combine some of them to be satis ed with the result obtained.

Step 8: deleting attribute Pt. This attribute is chosen after a short analysis of the GMRT sets (obtained without F, L, K e.t.c.) discussed above. The total attribute lengths of all GMRTs, and the total object coverings in the case of Pt deleting is 53, and 72, respectively. The comparison of such numbers is not very useful. We formed and compared the average attribute lengths (per one rule) and the average object coverings (per one rule), e.g. 2.94, and, 4 for this case, respectively. As a result, Rule (L=3,F=3,Pt=4) is deleted, and attribute Pt is deleted from Rule 14 in Tab.5.

Step 9: adding attribute Hs. This choice is explained by one main criterion { a number of rules. In this case one gets 17 rules, i.e. this number is even decreased in comparison with previous stage. In other cases the number of rules is the same (adding Sc), and bigger (25 and 19 when we add D and Si, respectively). As a result of stage 9, we add Hs in Rules 1,3,4 for Class 1, and Rules 2,7,8,11,12 for Class 2. One new Rule (Hs=3,Hy=4) for Class 1 is obtained, and two Rules 3,15 are deleted.

The results obtained allow to characterized the persons of Class 1 and Class 2 psychologically: Class 2 (negative dynamics) is characterized by the MMPI pro les similar to \indepth" pro les and Class 1 (positive dynamics) is characterized by the MMPI pro les similar to \harmonious" pro les and pro les similar to \convex" pro les (by Sobchik de nition, [ 19 ]). However our expert recommended us to check rule's structure without 4th object in Class 2, which seems to be suspicious. The object has good description (psychological portrait) but bad results only in 4 questionnaires for evaluating intellectual development at second year of learning. Class labelling seems to be a mistake.

Step 10: deleting object 4 from Class 2. This classi cation context modi cation deeply changes the GMRTs set, but the rules number decrease to 16. For example deleting object 7, which also seems to be labelled by a mistake, leads to increasing the rules number to 18.

In the paper, we take into account only four user's criteria for adding (deleting) an attribute as follows: expert's preferences, total object coverings in extents, number of rules, and total lengths of attributes in intents. However one can try also to use such criteria as concepts stability, number of rules per one object, and many others. Another interesting problem is a choice of intervals to scale a data given in T-values into more expert-oriented ones. Sobchik's scales from Tab. 1 can be useful for cross-investigation comparisons but not so useful for pattern recognition and data mining purposes.

If K is given for one time period, we can use also another approach of K dynamics exploration. It is associated with concept stability, please, see de nition, for example in [ 1 ]. An application of this approach to investigation of students di culties during learning in high school is given in [ 7 ]. Stability shows how much the group depends on some of particular students. Intents of formal concepts are described by marks' on courses. Potential object removing should not change seriously well-studied (worse-studied) learning courses. An extensional stability index is proposed in this paper in a dual manner.

This static approach of K dynamics exploration for measuring potential object (attribute) removing is also completed in [ 7 ] by a dynamic mappings approach in two di erent time periods (G is not changing). However the problem setting (adding or removing attributes in K) in this paper is di erent from our problem setting (four cases of K modi cation). 5

Conclusion

Four situations of GMRTs modeling (adding/deleting and an object or an attibute) in dynamic context are given in the paper. An application to modeling dynamics of cadets intellectual development using GMRTs is developed. This approach allows us to work with cadet dataset in a dynamically changing way. Step-by-step expert decisions about modi cation of classi cation rules can be implemented on-the- y. This approach can be useful to academy psychologists, lecturers, and administrators for analysing dynamics of cadets intellectual development.

References

1. Buzmakov , A. , Kuznetsov , S.O. , Napoli , A. : Is Concept Stability a Measure for Pattern Selection? Procedia Computer Science 31 , 918 { 927 ( 2014 ), http: //linkinghub.elsevier.com/retrieve/pii/S1877050914005213

2. Carpineto , C. , Romano , G.: Concept Data Analysis: Theory and Applications . John Wiley & Sons, Ltd, Chichester, UK ( 2004 )

3. Ganter , B. , Wille , R.: Formal concept analysis: mathematical foundations . Springer, Berlin ( 1999 ), http://www.springer.com/gp/book/9783540627715

4. Ganter , B. , Kuznetsov , S.O. : Conceptual Structures: Broadening the Base: 9th International Conference on Conceptual Structures. ICCS 2001 Proceedings, LNCS , vol. 2120 , chap. Pattern Structures and Their Projections , pp. 129 { 142 . http: //dx.doi.org/10.1007/3-540-44583-8_ 10

5. Ganter , B. , Kuznetsov , S.O. : Conceptual Structures: Logical, Linguistic, and Computational Issues: 8th International Conference on Conceptual Structures. ICCS 2000 Proceedings, LNCS , vol. 1867 , chap. Formalizing Hypotheses with Concepts , pp. 342 { 356 . http://dx.doi.org/10.1007/10722280_ 24

6. Godin , R. , Missaoui , R. , Alaoui , H.: Incremental concept formation algorithms based on Galois (concept) lattices . Computational Intelligence 11 ( 2 ), 246 { 267 ( 1995 )

7. Ignatov , D. , Mamedova , S. , Romashkin , N. , Shamshurin , I. : What can closed sets of students and their marks say? In: EDM 2011 - Proceedings of the 4th International Conference on Educational Data Mining . pp. 223 { 228 ( 2011 )

8. Kauer , M. , Krupka , M. : Removing an incidence from a formal context . In: CEUR Workshop Proceedings . vol. 1252 , pp. 195 { 206 . CEUR-WS ( 2014 )

9. Kourie , D.G. , Obiedkov , S. , Watson , B.W. , van der Merwe, D.: An incremental algorithm to construct a lattice of set intersections . Science of Computer Programming 74 ( 3 ), 128 { 142 ( 2009 )

10. Kuznetsov , S.O.: A fast algorithm for computing all intersections of objects in a nite semilattice . Automatic Documentation and Mathematical Linguistics 27 ( 5 ), 11 { 21 ( 1993 )

11. Naidenova , X.A. , Polegaeva , J.G. : Model of human reasoning for deciphering forest's images and its implementation on computer . In: Theses of papers and reports of school-seminar "Semiotic aspects of the intellectual activity formalization" . Kutaisy, Georgia Soviet Socialist Republic ( 1985 ), (in Russian)

12. Naidenova , X. : Good classi cation tests as formal concepts . In: Domenach , F. , Ignatov , D. , Poelmans , J . (eds.) Formal Concept Analysis, Lecture Notes in Computer Science , vol. 7278 , pp. 211 { 226 . Springer Berlin Heidelberg, Leuven ( 2012 )

13. 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 )

14. Naidenova , X. , Parkhomenko , V. : An approach to incremental learning good classi cation tests . In: Cellier, P. , Distel , F. , Ganter , B . (eds.) Contributions to the 11th International Conference on Formal Concept Analysis , pp. 51 { 64 . Technische Universitat Dresden ( 2013 )

15. Ore , O. : Galois connections . Trans. Amer. Math. Soc 55 , 494 { 513 ( 1944 )

16. Outrata , J.: A lattice-free concept lattice update algorithm based on *CBO . In: CEUR Workshop Proceedings . vol. 1062 , pp. 261 { 274 . CEUR-WS ( 2013 )

17. Outrata , J. , Vychodil , V. : Fast algorithm for computing xpoints of Galois connections induced by object-attribute relational data . Information Sciences 185 ( 1 ), 114 { 127 ( 2012 )

18. Reshetnikov , M. , Kulagin , B. : Investigation of general level development of cognitive psychological processes ( 1987 ), (in Russian)

19. Sobchick , L. : Standardized multivariate method of personality investigation: a practical guide ( 2007 ), (in Russian)

20. Van Der Merwe , D. , Obiedkov , S. , Kourie , D.: AddIntent: A new incremental algorithm for constructing concept lattices . LNCS , vol. 2961 , pp. 372 { 385 . Springer Verlag ( 2004 )

21. Zhang , L. , Zhang , H., Shen , X. , Yin , L. : An incremental algorithm for removing object from concept lattice . Journal of Computational Information Systems 9 ( 9 ), 3363 { 3372 ( 2013 )

22. Zou , L. , Zhang , Z. , Long , J. , Zhang, H.: A fast incremental algorithm for deleting objects from a concept lattice . Knowledge-Based Systems 89 , 411 { 419 ( 2015 )