Temporal Concept Analysis Explained by Examples

Abstract

The purpose of this paper is to show by examples the advantages of Temporal Concept Analysis (TCA) - the theory of temporal phenomena described with tools of Formal Concept Analysis (FCA). TCA is developed in three main branches: rst the branch of Conceptual Time Systems with actual Objects and a Time relation (CTSOTs) where each temporal object is at each time granule at exactly one place; that gives rise to a rst notion of states, transitions and life tracks of an object. The second branch of TCA is centered around the notion of a Temporal Conceptual Semantic System (TCSS) which allows to introduce the notion of a distributed object which may occupy at each time granule a certain volume, called its trace. That leads to a clear mathematical distinction of the notions of particles and waves in physics. The third branch of TCA is based on the notion of a Temporal Relational Semantic System (TRSS); it uses the developments in Temporal Conceptual Semantic Systems for combining the conceptual graphs by J. Sowa and the concept graphs by R. Wille with conceptual scaling.

-

by means of (nested) line diagrams of concept lattices the observations should nally be represented by a formal context. For that purpose the transformation of a data table with arbitrary values (mathematically described as a many-valued context (G; M; W; I) ) into a formal context (G; N; J ) is necessary; this transformation is called conceptual scaling and can be done in a meaningful way by representing the values of a many-valued attribute m 2 M as formal concepts of a suitable formal context Sm := (Gm; Mm; Im) which is called a conceptual scale of m, if Gm contains all values of m. The derived context K = (G; N; J ) of a many-valued context (G; M; W; I) with respect to a family Sm := (Gm; Mm; Im) (m 2 M ) is de ned by N := f(m; n) j m 2 M; n 2 Mmg and gJ (m; n) () m(g)Imn for g 2 G and (m; n) 2 N . Any subset Q N is called a view. The subcontext KQ := (G; Q; J \ (G Q)) is called the Q part of the derived context. In the following, the concept lattice of a suitable Q part will play the role of a map into which relevant structures like traces of objects, transitions, and life tracks will be embedded (see Fig.1,2,3,6).

The three main branches of TCA are described in the following three sections just by their leading ideas and some examples. Hints to the mathematical de nitions in TCA will be given in these sections. 2

Conceptual Time Systems

The rst intuitive idea about the notion of a state, which was the beginning of TCA, came suddenly to my mind when I was standing alone under the bright sun of Crete on the ruins of the ancient palace of Minos in Knossos, and I vocalized:

The states are just the object concepts of suitable contexts.

That happened in May 1993 just after a conference in Chania (Crete) where I had many fruitful discussions with R.E. Kalman [ 3 ] on general systems. In my rst paper [ 11 ] on temporal conceptual systems the notion of a Conceptual Time System (CTS) and the notion of a state of a CTS was introduced. A simple example of such a temporal system is given in the following subsection. 2.1

A chemical process in a distillation column

In cooperation with a chemical engineer we investigated the temporal behavior of a distillation column. At each of 20 days 13 variables had been measured once. For 4 of these 13 variables the corresponding data table is indicated in Tab.1 by the measurement values at the rst and the last day. It is clear that there is a simple notion of a state of this distillation column at some day, namely the tuple of all the measurement values observed at this day, for example the state of the distillation column at day 1 is the quadruple (129; 616; 616; 119) (according to Table 1). As usual, the experts wish to talk a little bit coarser, for example about low, middle and high values of some variables. In close cooperation with the chemical engineers we developed conceptual scales for all of the variables. For re ux and energy1 the resulting state space together with the transitions of the distallation column is shown in Fig.1, which is called a transition diagram for this distillation process with respect to the chosen granularity.

It should be intuitively clear what Fig.1 represents. We do not repeat here the mathematical de nitions of a Conceptual Time System as introduced in [ 11 ]; we just describe it here in a data table language: the values in the rst column are denoted as time granules and interpreted as granules of time as for example a minute or a day; the set of the other columns is divided in two parts, the time part, which has in Table 1 just a single column, namely the column of day, while the other columns form the event part, which consists of the 4 columns of re ux, energy1, input, pressure. In this example, the time granules just denote the days, in general a time granule is described by its values in the time part, which might have several many-valued attributes, for example day, month, year.

We now focus on the re ux-energy1-part of the data table and show the derived context of this part in Tab.2. For example, at time granule 1 the distillation column has all three re ux-attributes in Tab.2, while it has only the rst two energy1-attributes, but not the last, since the energy1-value 616 is not <= 570. The two attributes at the top-concept of Fig.1 have been introduced to tell the reader of the diagram the range of observed values for re ux and energy1.

Now we discuss the role of the object concepts in a CTS. If g is a formal object (=time granule), then the intent of the object concept (g) is the set of all attributes which g has in the derived context - and this intent of (g) is a very nice description of the state of the CTS at the time granule g with respect to the chosen granularity. It is also good to know all time granules which have the attributes of g; they form the extent of (g). Therefore, the state of a CTS at time granule g is de ned as the object concept (g) in the derived context of the CTS (with respect to the chosen scales). That approves my intuitive state idea which I had at Knossos.

For example, state (1) has the intent consisting of all attributes in Table 2 but the last, namely \energy1 <= 570". The extent of (1) is the set f1; 3; 9; 10; 11; 12; 20g. The extent of an object concept (g) should clearly be distinguished from its contingent which is de ned as the set of all objects h such that (h) = (g).The contingent of an object concept (g) is shown in Fig.1 just below the concept node of (g). For example, the contingent of (1) is the set f1; 3; 9; 10; 12g.

We now focus on the arrows in Fig.1; they represent transitions. We have drawn an arrow from (g) to (g + 1) to denote the transition from day g to day g + 1 for 1 g 19. But we have to explain how the transitions are de ned in general. That was introduced by the author in [ 13 ]. It is clear from the example in Fig.1 that transitions should not be de ned as pairs of states (as it is done in Automata Theory), since the two arrows from state (1) to state (2) denote di erent transitions, one happens during the time step from the rst day to the second day, for short: 1 ! 2, the other one during 12 ! 13. Therefore, we describe the rst transition by the pair of pairs ((1; 2); ( (1); (2))) and in the same way the others. For the general de nition of a transition we extend the structure of a CTS by a given binary relation R on the set G of formal objects, since we interpreted the formal objects as time granules. (Later on, in Temporal Conceptual Semantic Systems we will use the concepts of the time scale as time granules.) The relation R is called the time relation. In nearly all practical applications with discrete time the time relation is the set of pairs (t, t+1) for t 2 f0; :::; n 1g. Since we do not like to assume any linearity of time, we just assume that R is a binary relation on the set G of time granules and interpret R as the set of observed time steps. Hence for a CTS with a time relation R any transition is of the form ((g; h); ( (g); (h))) where (g; h) 2 R. For more details the reader is referred to [ 13 ].

In Fig.1 we can follow the life track of the CTS with respect to the chosen view, if we start in state (1), go to state (2), and so on until we reach (20).

Fig.2 shows a nested transition diagram where the outer diagram represents the two variables re ux and energy1 (as in Fig.1), while the inner diagram represents the two variables input and pressure in a 5x4-grid.

From such diagrams the process can be understood quite well. A short and coarse description of that process might be:

During the rst two weeks the distillation column was mainly in states with low input and middle pressure - with the exceptions of day 10 (high pressure) and day 11 (low pressure) - while it moved during the last week to high input, small energy1, small pressure, and during the last three days also to small re ux.

Typically, in such applications the experts suggest rst a coarse granularity by a few "cuts" like "re ux 140". After having studied the concept lattice with a coarse granularity it is usually re ned, depending on the data and on the interest of the experts. That leads in a few steps to valuable visualizations of multidimensional processes.

The following example of the family of an anorectic young woman served as a motivation for me to develop temporal conceptual systems in which many objects may move, each with its own life track. Hence we need a more general notion of the state of an object of a system as opposed to the state of a system as in the previous example. 2.2

The development of the family of an anorectic young woman

The following example in Fig.3 describes the development of an anorectic young woman (SELF), her father, mother, and her self ideal (IDEAL) during a period of about two years. The underlying formal context was constructed by the psychoanalyst N. Spangenberg [6{8] on the basis of four repertory grid questionings taken about each half year from the beginning (time granule 1) until the end (time granule 4) of the psychoanalytic treatment of his patient. SELF1, the self at the beginning of the treatment, has the attributes \distrust", \reduced spontaneity", \pessimistic" and \self-accusation", SELF2 has only the attributes \pessimistic" and \self-accusation", SELF3 is in the same state as SELF1, and SELF4 reaches the state of IDEAL2,3,4 having none of the (negative) attributes. Indeed, the patient was healthy again at this time. It is remarkable that the life

Fig. 2: A chemical process represented in a nested transition diagram tracks of FATHER and MOTHER start from quite di erent states and end in similar states, the FATHER having all (negative) attributes of this context. For further information the reader is referred to [6{8].

Conceptual Time Systems with actual Objects and a Time relation (CTSOTs)

To have a simple mathematical notation for temporal systems in which many objects (for example persons) are moving the author has introduced in [ 14 ] the notion of a Conceptual Time System with actual Objects and a Time relation (CTSOT). The main idea is a straightforward generalization of a CTS by introducing a set P of persons or particles and a set G of time granules, and taking a subset of P G as the set of formal objects. For example, the pair (SELF,1) is taken as a formal object denoting the person SELF at time granule 1. Then the notion of a state of a person p at a time granule g can be introduced as the object concept of the formal object (p; g). Transitions and life tracks can be de ned in the same way as explained previously [13{16].

While the CTSOTs cover the wide range from particle systems in physics to discrete systems in Computer Science they are not general enough to cover also waves and other distributed objects and their states as for example the distributed state of an electron as represented by some cloud around the center of the electron. Such distributed objects also occur very often in workaday life, for example as a moving high pressure zone on a weather map. Such distributed objects, including waves, can be represented in Temporal Conceptual Semantic Systems which will be explained in the next section. 3

Temporal Conceptual Semantic Systems (TCSSs)

As opposed to CTSOTs where each object p is at each time granule g at exactly one place, namely at the object concept (p; g) (where is the object concept mapping of the chosen view) we now wish to represent also objects which are `distributed'. For that purpose, we should use neither the time granules (as in CTSs) nor the actual objects (p; g) (as in CTSOTs) as formal objects of the many-valued context of the temporal system. Instead, we take the row numbers of the data table as the formal objects; they can be interpreted as names of the statements represented by the information given in that row. 3.1

Basic Notions in TCSSs

Conceptual Semantic Systems have been introduced by the author in [ 15 ] for the purpose to represent distributed objects, like waves, in a natural way. The main idea was to represent the concepts in an application domain as formal concepts of formal contexts, called semantic scales. Since statements are often shortly described by a tuple of concepts of some application domain we represent each such statement as a tuple of formal concepts. These formal concepts (usually represented by their names) are then chosen as values in a many-valued context in such a way that each row, labeled by g, represents a statement which is denoted by the tuple (m(g))m2M where m(g) is a formal concept of the semantic scale of m. Since the formal objects of the many-valued context of a CSS are interpreted now as names of statements and not as time granules as in CTSs we need a new representation of time granules in TCSSs. As formal representations of time granules we take the formal concepts of the time scale of a speci ed many-valued time attribute. The time relation is de ned as a binary relation on the set of formal concepts of the time scale. Objects in a temporal system are mathematically represented in TCSSs as tuples of concepts of the semantic scales, as for example the tuple (High; Monday) denoting a high pressure zone at Monday in the next example. Such an object (which is not a formal object) may be distributed in the sense, that it has been observed at more than one places (=object concepts in the concept lattice of the Q part KQ of the chosen view Q). This set of object concepts (of the formal objects denoting row labels or statements) where an object has been observed is mathematically de ned as the trace of an object in KQ. The state of an object o at a time granule t is then de ned as the trace of the tuple (o; t). Transitions of an object o from time granule s to time granule t are de ned similarly as the transitions in CTSs. The technique of embedding many traces into the concept lattice of some suitable context KQ is the conceptual generalization of drawing a usual geographic map (see Fig.6). For the mathematical de nitions the reader is referred to [ 15, 19, 24 ].

Remark: In the de nition of a Conceptual Semantic System we do not explicitly represent the relational aspect of a statement as it is done in Conceptual Graphs [ 4, 5 ], in Power Context Families and Concept Graphs [ 10 ]. These relational structures have been combined with temporal CSSs by the author in Temporal Relational Semantic Systems [21{23] which will be discussed in section 4.

In the following section we use a moving high pressure zone as a typical example of a distributed temporal object in a TCSS. We explain this special TCSS starting with a data table and interpreting the values of the data table as formal concepts of suitable formal contexts. 3.2

A Moving High Pressure Zone

As a small example we construct a TCSS which yields a weather map with a moving high pressure zone over Germany. To keep the data table small we construct a map of Germany using a coarse grid of longitude and latitude coordinates into which we embed the (one-element-) traces of 15 towns. To represent a moving high pressure zone we assume that the pressure has been measured in some weather stations (WS) at two consecutive days, say Monday and Tuesday. The data are (partially) shown in Table 3 where the rows 1,...,15 show the latitude and longitude values of 15 German towns, the rows 16,...,25 show the pressure values (in hectopascal (hPa)) measured at certain days at weather stations located in some of the previously mentioned towns.

In Table 3 the row labels are called instances, and instance 1 denotes the statement that the place Berlin has latitude 52:5 and longitude 13:4; no time and no pressure is recorded in this line, shown by the sign \/" in the column for time and pressure. Instance 16 tells that Weather Station Dortmund has latitude 51:5 and longitude 7:5 and has reported at Monday a pressure of 1020 hectopascal.

The semantic scale for time is shown in Fig. 4 by a line diagram of its concept lattice. The values \Monday", \Tuesday", and \/" in Tab. 3 are interpreted as the object concepts of the corresponding formal objects. The single arrow in Fig. 4 represents the time relation as a binary relation on the set of all concepts of the speci ed time attribute.

The semantic scale Sp for pressure is de ned as a modi ed interordinal scale on the multiples of 10 in the interval [970; 1030]. Its concept lattice is shown in Fig.5.

In this interordinal scale for pressure we choose the attribute concept ( 1010) for the representation of the notion of \high pressure", and call this formal concept High. Combined with the formal concept Monday in the time scale we like to form the tuple (High, Monday) as our formal representation of such an abstract \object" like \the High at Monday".

Fig. 6: A Weather Map with a Moving High Pressure Zone

The movement of the selected high pressure zone is visualized in the weather map in Fig.6. Concerning the construction of this weather map we just mention the main steps: 1. Construction of a grid of latitude-longitude-values as a semiproduct of two ordinal scales for latitude and longitude. 2. Embedding the (oneelement) traces of towns using their latitude-longitude-values. 3. Embedding of the traces of the tuples (High, Monday) and (High, Tuesday) as visualized by ellipses in Fig.6. 4. Visualizing a (short) life track from the trace of (High, Monday) to the trace of (High, Tuesday).

The details of the construction of the weather map in Fig.6 can be seen in [ 19 ]. For another useful application of TCSSs in a biomedical study of disease processes in arthritic patients the reader is referred to [ 25 ]. 4

Temporal Relational Semantic Systems

A Temporal Relational Semantic System (TRSS) [21{23] is a relational extension of a Temporal Conceptual Semantic System (TCSS). The investigations of TRSSs are based on the theory of Conceptual Graphs as developed by J. Sowa [ 4, 5 ] and its FCA-version of Concept Graphs of a Power Context Family as introduced by R. Wille [ 10 ]. The main idea for the de nition of a TRSS is to write each relational statement (with a single relation term) into a line of a manyvalued context of a CSS and protocol the sequence of speaking this statement. A TRSS has a speci ed set of time attributes, a speci ed set of temporal objects, and for each temporal object its time relation [ 23 ]. Then states, transitions, and traces can be introduced as in a TCSS. 4.1

A tabular representation of a Temporal Relational Semantic

System

In the rows of Table 4 we represent some temporal and non-temporal statements: `from 2008 to 2009 Bob lived in England', `in May 2008 Bob lived in London', `in spring 2009 Alice lived in Berlin', `in spring 2009 Bob met Alice in Paris', and `Paris is the native town of Alice'. statement

The main information for reading the statements in the intended sequence is represented in Table 5, called the position table. For example, the rst position of .is the native town of. is the attribute LOCATION, its second position is the attribute PERSON1.

r from.to..lived in.

in...lived in.

in...met. in. .is the native town of.

For RSSs the notion of a trace of an object (as a tuple of concepts of the semantic scales) can be used to visualize information concerning several manyvalued attributes in the concept lattice of a suitable view. That is shown by some examples of relational trace diagrams in [ 22 ]. For TRSSs each relation, as for example the relation in...lived in. is formally represented as a formal concept of the scale for the relations; therefore the state of such a relation at a certain time granule can be de ned. That is clearly a powerful tool for the representation of temporal relational knowledge. 5

Conclusions

This paper has shown the leading ideas and some typical examples of several temporal conceptual systems: rst the CTSs, second the CTSOTs, third the TCCSs, and fourth the TRSSs. Future research should improve the actual computer programs [ 1 ] for the generation of powerful visualizations of temporal relational structures.

References

1. Becker , P. , Hereth Correia , J.: The ToscanaJ Suite for Implementing Conceptual Information Systems . In: Ganter, B. , Stumme , G. , Wille , R . (eds.): Formal Concept Analysis - Foundations and Applications. ICFCA 2003 . LNAI 3626 , pp. 324 { 348 . Springer, Heidelberg ( 2005 )

2. Ganter , B. , Wille , R.: Formal Concept Analysis: mathematical foundations . Springer, Heidelberg ( 1999 ); German version: Springer, Heidelberg ( 1996 )

3. Kalman , R.E. , Falb , P.L. , Arbib , M.A. : Topics in Mathematical System Theory . McGraw-Hill Book Company, New York ( 1969 )

4. Sowa , J.F. : Conceptual structures: information processing in mind and machine . Adison-Wesley , Reading ( 1984 )

5. Sowa , J.F. : Knowledge representation: logical, philosophical, and computational foundations . Brooks Cole Publ. Comp ., Paci c Grove, CA ( 2000 )

6. Spangenberg , N.: Familienkon ikte e gestorter Patientinnen: Eine empirische Untersuchung mit Hilfe der Repertory Grid-Technik. Habilitationsschrift am FB Humanmedizin der Justus-Liebig-Universitat Gie en , 1990 .

7. Spangenberg , N., K.E. Wol : Comparison of Biplot Analysis and Formal Concept Analysis in the case of a Repertory Grid . In: Classi cation, Data Analysis, and Knowledge Organization (eds .: H.H. Bock , P. Ihm), Springer, Heidelberg 1991 , 104 - 112 .

8. Spangenberg , N., K .E. Wol : Datenreduktion durch die Formale Begri sanalyse von Repertory Grids . In: Einfuhrung in die Repertory Grid-Technik, Band 2 , Klinische Forschung und Praxis. (eds.: J.W. Scheer , A. Catina) , Verlag Hans Huber , 1993 , 38 - 54 .

9. Wille , R.: Restructuring lattice theory: an approach based on hierarchies of concepts . In: Rival , I. (ed.): Ordered sets . pp. 445 { 470 , Reidel , Dordrecht-Boston ( 1982 ). Reprinted in: Ferre, S. , Rudolph , S. (eds.): Formal Concept Analysis . ICFCA 2009. LNAI 5548 , pp. 314 { 339 . Springer, Heidelberg ( 2009 )

10. Wille , R.: Conceptual Graphs and Formal Concept Analysis . In: Lukose, D. , Delugach , H. , Keeler , M. , Searle , L. , Sowa , J.F . (eds.): Conceptual Structures: Ful lling Peirce's Dream . ICCS 1997. LNAI 1257 , pp. 290 { 303 . Springer, Heidelberg ( 1997 )

11. Wol , K.E. : Concepts, States, and Systems . In: Dubois, D.M. (ed.): Computing Anticipatory Systems . American Institute of Physics, Conference Proceedings 517 , pp. 83 { 97 ( 2000 )

12. Wol , K.E. : Temporal Concept Analysis . In: Mephu Nguifo E. et al. (eds.): ICCS2001 International Workshop on Concept Lattices-Based Theory, Methods and Tools for Knowledge Discovery in Databases , pp. 91 { 107 . Stanford University, Palo Alto, CA ( 2001 )

13. Wol , K.E. : Transitions in Conceptual Time Systems . In: Dubois, D.M. (ed.): International Journal of Computing Anticipatory Systems , vol. 11 , pp. 398 { 412 . CHAOS ( 2002 )

14. Wol , K.E. : Interpretation of Automata in Temporal Concept Analysis . In: Priss, U. , Corbett , D. , Angelova , G . (eds.): Integration and Interfaces . ICCS 2002. LNAI 2393 , pp. 341 { 353 , Springer, Heidelberg ( 2002 )

15. Wol , K.E.: 'Particles' and 'Waves' as Understood by Temporal Concept Analysis . In: Wol , K.E. , Pfei er , H.D., Delugach , H.S. (eds.): Conceptual Structures at Work. ICCS 2004. LNAI 3127 , pp. 126 { 141 , Springer, Heidelberg ( 2004 )

16. Wol , K.E. : States, Transitions, and Life Tracks in Temporal Concept Analysis . In: Ganter, B. , Stumme , G. , Wille , R . (eds.): Formal Concept Analysis - Foundations and Applications. ICFCA 2003 . LNAI 3626 , pp. 127 { 148 , Springer, Heidelberg ( 2005 )

17. Wol , K.E. : States of Distributed Objects in Conceptual Semantic Systems . In: Dau, F. , Mugnier , M.-L. , Stumme , G . (eds.): Conceptual Structures: Common Semantics for Sharing Knowledge . ICCS 2005. LNAI 3596 , pp. 250 { 266 , Springer, Heidelberg ( 2005 )

18. Wol , K.E. : Conceptual Semantic Systems - Theory and Applications . In: Goncharov, S. , Downey , R. , Ono , H. (eds.): Mathematical Logic in Asia. pp. 287 { 300 , World Scienti c, New Jersey ( 2006 )

19. Wol , K.E. : Basic Notions in Temporal Conceptual Semantic Systems . In: Gely, A. , Kuznetsov , S.O. , Nourine , L. , Schmidt , S.E . (eds.): Contributions to ICFCA 2007 , pp. 97 { 120 . Clermont-Ferrand , France ( 2007 )

20. Wol , K.E. : Applications of Temporal Conceptual Semantic Systems . In: Zagoruiko, N.G. , Palchunov , D.E . (eds.): Knowledge - Ontology - Theory . Vol. 2 , pp. 3 { 16 . Russian Academy of Sciences. Sobolev Institute for Mathematics. Novosibirsk ( 2007 )

21. Wol , K.E. : Relational Semantic Systems, Power Context Families, and Concept Graphs . In: Wol , K.E. , Rudolph , S. , Ferre , S. (eds.): Contributions to ICFCA 2009 , pp. 63 { 78 . Verlag Allgemeine Wissenschaft, Darmstadt ( 2009 )

22. Wol , K.E. : Relational Scaling in Relational Semantic Systems . In: Rudolph, S. , Dau , F. , Kuznetsov , S.O . (eds.): Conceptual Structures: Leveraging Semantic Technologies . ICCS 2009. LNAI 5662 , pp. 307 { 320 . Springer-Verlag, Heidelberg ( 2009 )

23. Wol , K.E. : Temporal Relational Semantic Systems . In: Croitoru, M. , Ferre , S. , Lukose , D . (eds.): Conceptual Structures: From Information to Intelligence. ICCS 2010. LNAI 6208 , pp. 165 { 180 . Springer-Verlag, Heidelberg ( 2010 )

24. Wol , K.E. : Applications of Temporal Conceptual Semantic Systems . In: Wol , K.E. et al: Knowledge Processing and Data Analysis . LNAI 6581 , pp. 60 { 76 . Springer-Verlag, Heidelberg ( 2011 )

25. Wollbold , J. , Huber , R. , Kinne , R. , Wol , K.E. : Conceptual Representation of Gene Expression Processes . In: Wol , K.E. et al: Knowledge Processing and Data Analysis . LNAI 6581 , pp. 77 { 99 . Springer-Verlag, Heidelberg ( 2011 )