In this paper, we are interested in the analysis of sequential data and we propose an original framework based on Formal Concept Analysis (FCA). For that, we introduce sequential pattern structures, an original speci cation of pattern structures for dealing with sequential data. Pattern structures are used in FCA for dealing with complex data such as intervals or graphs. Here they are adapted to sequences. For that, we introduce a subsumption operation for sequence comparison, based on subsequence matching. Then, a projection, i.e. a kind of data reduction of sequential pattern structures, is suggested in order to increase the e ciency of the approach. Finally, we discuss an application to a dataset including patient trajectories (the motivation of this work), which is a sequential dataset and can be processed with the introduced framework. This research work provides a new and e cient extension of FCA to deal with complex (not binary) data, which can be an alternative to the analysis of sequential datasets.
Sequence data is largely present and used in many applications. Consequently, mining sequential patterns from sequence data has become an important and crucial data mining task. In the last two decades, the main emphasis has been on developing e cient mining algorithms and e ective pattern representations [1{5]. However, the problem with traditional sequential pattern mining algorithms (and generally with all pattern enumeration algorithms) is that they generate a large number of frequent sequences while few of them are truly relevant. Moreover, in some particular cases, only sequential patterns of a certain type are of interest and should be mined rst. Are we able to develop a framework for taking into account only patterns of required types? In addition, another drawback for these pattern enumeration algorithms is that they depend on a user selected support threshold, which is usually hard to be properly set by non-experts. How can one avoid the setting of support threshold while having optimal pattern analysis?
The above questions can be answered by addressing the problem of analyzing
sequential data with the formal concept analysis framework (FCA), an elegant
mathematical approach to data analysis [
In this paper, we develop a novel and e cient approach for working with sequential pattern structures in FCA. The rest of the paper is organized as follows. Section 1 introduces main de nitions of FCA and pattern structures. The next section de nes sequential pattern structures. Then, before concluding the results are presented and discussed in Section 3. 1
FCA [
De nition 1. A pattern structure is a triple (G; (D; u); ), where G is a set of objects, (D; u) is a complete meet-semilattice of descriptions and : G ! D maps an object to a description.
The lattice operation in the semilattice (u) corresponds to the similarity between two descriptions d1 and d2, i.e. the description which is common between d1 and d2. Standard FCA can be presented in terms of pattern structures in the following way. The set of objects G remains, while the semilattice of descriptions is (}(M ); \), where }(M ) is a powerset of M , and, thus, a description is a set of attributes, and the similarity operation corresponding to the set intersection, i.e. the similarity is the set of shared attributes. If x = fa; b; cg and y = fa; c; dg then x u y = x \ y = fa; cg. The mapping : G ! }(M ) is given by, (g) = fm 2 M j (g; m) 2 Ig, returning the describing set of attributes.
The Galois connection for a pattern structure (G; (D; u); ) between the set of objects and the semilattice of descriptions is de ned as follows: A := l (g);
g2A d := fg 2 G j d v (g)g; for A
G for d 2 D Given a set of objects A, A returns the description which is common to all objects in A. And given a description d, d is the set of all objects whose description subsumes d. The partial order on D (v) is de ned w.r.t. the similarity operation u: c v d , c u d = c, and c is subsumed by d.
De nition 2. A pattern concept of a pattern structure (G; (D; u); ) is a pair (A; d) where A G and d 2 D such that A = d and d = A, A is called the pattern extent and d is called the pattern intent.
As in the standard case of FCA, a pattern concept corresponds to the maximal set of objects A whose description subsumes the description d, while there is no e 2 D, subsuming d, i.e. d v e, describing every object in A. The set of all concepts can be partially ordered w.r.t. partial order on extents (dually, intent patterns, i.e v), within a concept lattice.
It is wroth mentioning, that the size of the concept lattice can be exponential
w.r.t. to the number of objects, and, thus, we need a special ranking method to
select the most interesting concepts for further analysis. Several such techniques
are considered in [
An example of pattern structures is given by Table 1a and described in the next sections, the corresponding lattice is depicted in Figure 1a. 2 2.1
Patient Trajectory p1 hfag ; fc; dg ; fb; ag ; fdgi p2 hfc; dg ; fb; dg ; fa; dgi p3 hfc; dg ; fbg ; fag ; fa; dgi (a) Sequential dataset.
Subsequences ss1 hfc; dg ; fbg ; fdgi ss5 ss2 hfdg ; fagi ss6 ss3 hfc; dg ; fbgi ss7 ss4 hfc; dg ; fbg ; fagi
Subsequences hfag ; fdgi hfa; dgi hfagi (b) Some common subsequences.
A medical trajectory of a patient is a sequence of hospitalizations, where every
hospitalization is described by a set of medical procedures the patient underwent.
An example of medical trajectories for three patients is given in Table 1a. Patient
p1 had four hospitalizations and during the second hospitalization he underwent
procedures c and d. Patients may have a di erent number of hospitalizations.
Hereafter we use the following notation, di erent sequences are enumerated in
superscript (p1), while elements of a sequence are enumerated in the subscript
(p12 = fc; dg). One important task is to nd the characteristic subsequences of
hospitalizations for patients to optimize hospitalization processes. For example,
we can nd a strange sequence and, thus, motivate the deeper analysis of the
problems behind or we can nd typical sequences that allow us to estimate the
treatment costs for a patient.
A sequence is constituted of elements from an alphabet. The classical
subsequence matching task requires no special properties of the alphabet. Several
generalization of the classical case were made by introducing subsequence
relation based on itemset alphabet [
De nition 3. A sequence t = ht1; :::; tki is a subsequence of a sequence s = hs1; :::; sni, denoted t s, i k n and there exist j1; ::jk such that 1 j1 < j2 < ::: < jk n and for all i 2 f1; 2; :::; kg, ti vE sji .
With complex sequences and such kind of subsequences the calculation procedures can be di cult, thus, to simplify the procedure, only \restricted" subsequences are considered, where only the order of consequent elements is taken into account, i.e. given a j1 in De nition 3, ji = ji 1 + 1 for all i 2 f2; 3; :::; kg. Such a restriction makes sens for our data, because a hospitalization is a discrete event and it is likely that the next hospitalization has a relation with the previous one, for example, hospitalizations for treating aftere ects of chemotherapy. Below the word \subsequence" refers to a \restricted" subsequence.
Based on De nition 3 and on the alphabet (}(P ); \), the sequence ss1 in Table 1b is a subsequence of p1 because if we set ji = i + 1 (De nition 3) then ss11 v p21 (fc; dg fc; dg), ss12 v p31 (fbg fb; ag) and ss13 v p41 (fdg fdg). 2.3
Using the previous de nitions, we can precisely de ne the sequential pattern
structure. For that, we make an analogy with the pattern structures for graphs [
However, the set of all possible subsequences can be rather large. Thus, it is more e cient and representable to keep a pattern d 2 D as a set of all maximal sequences d~, d~ = fs 2 d j @s 2 d : s sg . Below, every pattern is given only by the set of maximal sequences. For example, p2 u p3 = ss4; ss6 (see Tables 1a and 1b), i.e. ss4; ss6 is the set of maximal common subsequences between fp2g and fp3g, correspondingly ss4; ss6 u p1 = ss3; ss7 . Moreover, representing a pattern by the set of maximal sequences allows for an e cient implementation of the intersection \u" (see Section 3.1 for more details).
The sequential pattern structure for the example given by Subsection 2.1 is (G; (D; u); ), where G = p1; p2; p3 , (D; u) is the semilattice of sequential descriptions, and is the mapping associating an object in G to a description in D shown in Table 1a. Figure 1a shows the resulting lattice of sequential pattern concepts for this particular pattern structure (G; (D; u); ). 2.4
Pattern structures can be hard to process due to the usually large number of
concepts in the concept lattice and the complexity of the involved descriptions
and the similarity operation. Moreover, a given pattern structure can produce
a lattice with a lot of patterns which are not interesting for an expert. Can we
save computational time by deleting some unnecessary patterns? Projections of
pattern structures \simplify" to some degree the computation and allow one
to work with a reduced description. In fact, projections can be considered as
constraints (or lters) on patterns respecting certain mathematical properties.
These mathematical properties guarantee that the projection of a lattice is a
lattice where projected concepts have certain correspondence to original ones.
We introduce projections on sequential patterns, adapting them from [
A projection : D ! D is an operator, which is monotone (x v y )
(x) v (y)), contractive ( (x) v x) and idempotent ( ( (x)) = (x)). A
projection preserves the semilattice operation u as follows. Under a projection
, the pattern structure (G; (D; u); ) becomes the projected pattern structure
((G; (D; u); )) = (G; (D ; u ); ), where D = (D) = fd 2 D j 9d 2
D : (d ) = dg and 8x; y 2 D; x u y := (x u y). The concepts of a projected
pattern structure have a \similar" concept in the initial pattern structure [
One possible projection for sequential pattern structures comes from the following observation. In many cases it can be more interesting to analyze quite long common subsequences rather than small ones. For example, if we prefer common subsequences of length > 2, then between p1 and p2 in Table 1a there is only one maximal common subsequence, ss1 in Table 1b, while ss2 in Table 1b is too short to be considered as a common subsequence. Such kind of projections we call Minimal Length Projection (MLP) and depends on the parameter l, the minimal allowed length of the sequences in a pattern. The projected pattern concept lattice for MLP 3 is shown in Figure 1b. In the experimentation section we compare MLP projections with di erent value of the parameter. Projections are very useful, as they reduce the computational costs in a meaningful manner.
Nearly all state-of-the-art FCA algorithms can be adapted to process pattern
structures. We adapted AddIntent algorithm [
The experiments are carried out on an \Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz" computer with 8Gb of memory under the Ubuntu 12.04 operating system. The algorithms are not parallelized and are coded in C++.
First, the public available dataset from UCI repository on anonymous web data is used as a benchmark data set for scalability tests. This dataset contains around 106 transactions, and each transaction is a sequence based on \simple" alphabet, i.e. with no order on the elements. The overall time changes from 37279 seconds for the sequences of length M LP 5 upto 97042 seconds for the sequences of length M LP 3. For more details see the web-page.2
Our use-case data set comes from a French healthcare system [
Table 2 shows the nal times and the lattice sizes for di erent projections. The calculation time with projections changes from 3120 to 4510 seconds depending on the projection parameter. The lattice sizes for the di erent projections 2 http://www.loria.fr/~abuzmako/FCA4AI2013/experiment-uci.html changes from 105 to 5 105. Notice that the ratio for the lattice size is of 5 while the ratio for computation time is 1:5. Deletion of short sequences can dramatically change the lattice size, since the shorter a sequence is, the more probable it is a subsequence of a patient trajectory, but the computation of the semilattice operation is easily processed with shorter sequences. The calculation without projection takes a lot of time with relatively small lattice size (40 times more for the runtime and 6 times more for the lattice size w.r.t the projection l = 2). The reason for that is memory swapping to the hard disk. Thus, the best projection for that dataset is l = 2 as its computation time is reasonable and it preserves the most of the information among the other projections.
Table 3 shows some interesting concept intents and the sizes of the
corresponding extents. The concept are selected among the most stable ones [
In this paper, we present an approach for analyzing sequential datasets within the framework of pattern structures, an extension of FCA dealing with complex (non binary) data. Using pattern structures leads to the construction of a pattern concept lattice, which does not require the setting of a support threshold, as usually needed in sequential pattern mining. Another point worth to be noticed is that the use of projections gives a lot of exibility especially for mining and interpreting special kinds of patterns. The framework is tested on a real-life dataset recording patient trajectories in a healthcare system. Interesting patterns are extracted and then interpreted, showing the feasibility and usefulness of the approach. For the future work, it is important to more deeply investigate projections, their potentialities w.r.t. the types of patterns.
Acknowledgements: this research received funding from the Basic Research Program at the National Research University Higher School of Economics (Russia) and from the BioIntelligence project (France).