In this paper, we are interested in the analysis of sequential data and we propose an original framework based on FCA. For that, we introduce sequential pattern structures, an original specification of pattern structures for dealing with sequential data. Sequential pattern structures are given by a subsumption operation between set of sequences, based on subsequence matching. To avoid a huge number of resulting concepts, domain knowledge projections can be applied. The original definition of projections is revised in order to operate on sequential pattern structures in a meaningful way. Based on the introduced definition, several projections of sequential pattern structures involving domain or expert knowledge are defined and discussed. This projections are evaluated on a real dataset on care trajectories where every hospitalization is described by a heterogeneous tuple with different fields. The evaluation reveals interesting concepts and justify the usage of introduced projections of sequential pattern structures. This research work provides a new and efficient extension of FCA to deal with complex data, which can be an alternative to the analysis of sequential datasets.
Analysis of sequential data is a challenging task. In the last two decades, the
main emphasis has been on developing efficient mining algorithms with effective
pattern representations for sequences of itemsets [
We approach this problem with FCA and pattern structures [
The rest of the paper is organized as follows. In Section 1 we remind FCA, pattern structures and measures of concept interestingness. Section 2 states the problem of complex sequences analysis and introduces sequential pattern structures. In Section 3, first, the generalization of projections is defined, and, second, some projections specific to sequential pattern structures are introduced and analyzed. And finally before concluding the paper, we discuss an experimental evaluation in Section 4. 1
FCA [
Definition 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. Standard FCA can be presented in terms of pattern structures. In this case, G is the set of objects, the semilattice of descriptions is (℘(M ), u), where a description is a set of attributes, with the u operation corresponding to the set intersection (℘(M ) denotes the powerset of M ). If x = {a, b, c} and y = {a, c, d} then x u y = x ∩ y = {a, c}. The mapping δ : G → ℘(M ) is given by, δ(g) = {m ∈ M | (g, m) ∈ I}, and returns the description for a given object as a set of attributes.
The Galois connection for (G, (D, u), δ) is defined as follows:
A := l δ(g), g∈A d := {g ∈ G | d v δ(g)}, for A ⊆ G for d ∈ D
The Galois connection makes a correspondence between sets of objects and descriptions. 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. More precisely, the partial order (or the subsumption order) on D (v) is defined w.r.t. the similarity operation u: c v d ⇔ c u d = c, and c is subsumed by d.
Definition 2. A pattern concept of a pattern structure (G, (D, u), δ) is a pair (A, d) where A ⊆ G and d ∈ D such that A = d and d = A, A is called the concept extent and d is called the concept intent.
As in standard FCA, a pattern concept corresponds to the maximal set of objects A whose description subsumes the description d, where d is the maximal common description for objects 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. An example of a pattern structure is given and described in the next sections. It can be noticed that Table 1 defines a pattern structure, while the corresponding lattice is depicted in Figure 1.
It is worth 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 techniques are
considered in [
Definition 3. Given a concept c, the concept stability Stab(c) is the percent of subsets of the concept extent (denoted Ext(c)), whose description is equal to the concept intent (denoted Int(c)).
Stab(c) := |{s ∈ ℘(Ext(c)) | s = Int(c)}| |℘(Ext(c))| (1)
Stability measures how much the concept depends on the initial dataset. The larger the stability the more objects can be deleted from the context without affecting the intent of the concept, i.e. the intent of the most stable concepts are likely to be a characteristic pattern of a studied phenomena rather than an artifact of a data set.
After a brief general description of the analysis with pattern structures, the analysis of sequential data can be specified. 2 2.1
Imagine that we have medical trajectories of patients, i.e. sequences of hospitalizations, where every hospitalization is described by a hospital name and a set of procedures. An example of sequential data on medical trajectories with three patients is given in Table 1. There are a set of procedures P = {a, b, c, d}, a
Patient Trajectory
p1 h[H1, {a}]; [H1, {c, d}]; [H1, {a, b}]; [H1, {d}]i
p2 h[H2, {c, d}]; [H3, {b, d}]; [H3, {a, d}]i
p3 h[H4, {c, d}]; [H4, {b}]; [H4, {a}]; [H4, {a, d}]i
set of hospital names TH = {H1, H2, H3, H4, CL, CH, ∗}, where hospital names
are hierarchically organized (by the level of generality), H1 and H2 are central
hospitals (CH) and H3 and H4 are clinics (CL), and ∗ denotes the root of this
hierarchy. For the sake of simplicity, we use the u operator in order to denote
the least common ancestor in TH , i.e. H1 u H2 = CH. Every hospitalization is
described with one hospital name and may contain several procedures. The
procedure order in each hospitalization is not important in our case. For example,
the first hospitalization [H2, {c, d}] for the second patient (p2) was in hospital
H2 and during this hospitalization the patient underwent procedures c and d.
An important task is to find the “characteristic” sequences of procedures and
associated hospitals in order to improve hospitalization planning, optimize
clinical processes or detect anomalies. This sequences can be found by searching for
the most stable concepts in the lattice corresponding to a pattern structure.
A sequence is constituted of elements from an alphabet. The classical
subsequence matching task requires no special properties of the alphabet. Several
generalizations of the classical case were made by introducing a subsequence
relation based on itemset alphabet [
Definition 4. A sequence is an ordered list of e ∈ (E, uE ), such that e 6= ⊥E .
Here, ∀e ∈ E, ⊥E = ⊥E uE e. The bottom element is required by the lattice
structure but provide us with no useful information (it matches to any other
element), thus, it is excluded from the sequences. In the same way, in mining of
sequences of itemsets the empty itemset cannot be a proper element [
Subsequences ss1 h[CH, {c, d}]; [H1, {b}]; [∗, {d}]i ss3 h[CH, {}]; [∗, {d}]; [∗, {a}]i ss5 h[∗, {a}]i ss7 h[CL, {d}]; [CL, {}]i ss9 h[CH, {c, d}]i ss11 h[∗, {c, d}]; [∗, {b}]i
Subsequences ss2 h[CH, {c, d}]; [∗, {b}]; [∗, {d}]i ss4 h[∗, {c, d}]; [∗, {b}]i ss6 h[∗, {c, d}]; [CL, {b}]; [CL, {a}]i ss8 h[CL, {}]; [CL, {a, d}]i ss10 h[CL, {b}]; [CL, {a}]i ss12 h[∗, {a}]; [∗, {d}]i
With complex sequences and such kind of subsequences the computational procedure can be difficult, thus, to simplify the procedure, only “contiguous” subsequences are considered, where only the order of consequent elements is taken into account, i.e. given j1 in Definition 5, ji = ji−1+1 for all i ∈ {2, 3, ..., k}. 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 aftereffects of chemotherapy. Below the word “subsequence” refers to “contiguous” subsequence.
Example 1. In the running example (Section 2.1), the alphabet is E = TH ×℘(P ) with the similarity operation (h1, P1) u (h2, P2) = (h1 u h2, P1 ∩ P2), where h1, h2 ∈ TH are hospitals and P1, P2 ∈ ℘(P ) are sets of procedures. Thus, the sequence ss1 in Table 2 is a subsequence of p1 in Table 1 because if we set ji = i + 1 (Definition 5) then ss11 v pj11 (‘CH’ is an ancestor for H1 and {c, d} ⊆ {c, d}), ss12 v pj12 (the same hospital and {b} ⊆ {b, a}) and ss13 v pj13 (‘*’ is an ancestor for anything and {d} ⊆ {d}). 2.3
Meet-semilattice of Sequences
Using the previous definitions, we can precisely define the sequential pattern
structures that are used for representing and managing sequences. For that, we
make an analogy with pattern structures for graphs where the meet-semilattice
operation u respects subgraph isomorphism [
The set of all possible subsequences for a given sequence can be rather large. Thus, it is more efficient and readable to keep a pattern d ∈ D as a set of only maximal sequences d˜, d˜ = {s ∈ d | @s∗ ∈ d : s∗ ≥ s}. In the rest of the paper, every pattern is given only by the set of its maximal sequences. For example, p2 u p3 = ss6, ss7, ss8 (see Tables 1 and 2), i.e. ss6, ss7, ss8 is the set of all maximal sequences specifying the intersection result of two sets of sequences p2 and p3 , in the same way ss6, ss7, ss8 u p1 = ss4, ss5 . Note that representing a pattern by the set of all maximal sequences allows for an efficient implementation of the intersection “u” of two patterns. The next proposition is follows from this subsection and Definition 5.
Proposition 1. Given (G, (D, u), δ) and x, y ∈ D, x v y if and only if ∀sx ∈ x there is a sequence sy ∈ y, such that sx ≤ sy. 3
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 similarity
operation (make the parallel with the graph isomorphism problem). 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 avoiding the
construction of 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 filters) on
patterns respecting certain mathematical properties. These mathematical
properties ensure that the projection of a lattice is a lattice where projected concepts
have certain correspondence to original ones. Moreover, the stability measure
of projected concepts never decreases w.r.t the corresponding concepts. We
introduce projections on sequential patterns, revising them from [
Under a projection ψ, a pattern structure (G, (D, u), δ) becomes the
projected pattern structure ψ((G, (D, u), δ)) = (G, (Dψ, uψ), ψ ◦ δ), where Dψ =
ψ(D) = {d ∈ D | ∃d∗ ∈ D : ψ(d∗) = d} and ∀x, y ∈ D, x uψ y := ψ(x u y).
Note that in [
Proposition 2. Given a semilattice (D, u) and a projection ψ, for all x, y ∈ D ψ(x u y) = ψ(ψ(x) u y).
Proof. 1. ψ(x) v x, thus, x, y w (x u y) w (ψ(x) u y) w ψ(ψ(x) u y) 2. x v y ⇒ ψ(x) v ψ(y), thus, ψ(x u y) w ψ(ψ(x) u y) 3. ψ(x u y) u ψ(x) u y = ψ(x u y) u y = ψ(x u y), ψ(xuy)vψ(x) ψ(xuy)vy then (ψ(x) u y) w ψ(x u y) and ψ(ψ(x) u y) w ψ(ψ(x u y)) = ψ(x u y) 4. From (2) and (3) follows that ψ(x u y) = ψ(ψ(x) u y).
Corollary 1. X1 uψ X2 uψ · · · uψ XN = ψ(X1 u X2 u · · · u XN ) Corollary 2. Given a semilattice (D, u) and a projection ψ, (Dψ, uψ) is a semilattice, i.e. uψ is commutative, associative and idempotent.
The concepts of a pattern structure and a projected pattern structure are connected with the next proposition, following from Corollary 1: Proposition 3. An extent in ψ((G, (D, u), δ)) is an extent in (G, (D, u), δ). An intent in ψ((G, (D, u), δ)) is of the form ψ(d), where d is the intent of the concept with the same extent.
Moreover, preserving extents of some concepts, projections cannot decrease the stability of the projected concepts, i.e. if the projection preserves a stable concept, then its stability (Definition 3) can only increase.
Proposition 4. Given a pattern structure (G, (D, u), δ), its concept c and a projected pattern structure (G, (Dψ, uψ), ψ ◦ δ), and the projected concept c˜, if the concept extents are equal (Ext(c) = Ext(c˜)) then Stab(c) ≤ Stab(c˜). Proof. Concepts c and c˜ have the same extent. Thus, according to Definition 3, in order to prove the proposition statement, it is enough to prove that for any subset A ⊆ Ext(c), if A = Int(c) in the original pattern structure, then A = Int(c˜) in the projected one. It can be proven from contrary.
Suppose that ∃A ⊂ Ext(c) such that A = Int(c) in the original pattern structure and A 6= Int(c˜) in the projected one. Then there is a descendant concept d˜ of c˜ in the projected pattern structure such that A = Int(d˜) in the projected lattice. Then there is an original concept d for the projected concept d˜ with the same Ext(d). Then A w Int(d) A Int(c) and, so, A cannot be equal to Int(c) in the original lattice. Contradiction.
No we are going to present two projections of sequential pattern structures. The first projection comes from the following observation. In many cases it may be more interesting to analyze quite long subsequences rather than short one. This kind of projections is called Minimal Length Projection (MLP) and it depends on the minimal allowed length parameter l for the sequences in a pattern. The corresponding function ψ maps a pattern without short sequences to itself, and a sequence with short sequences to the pattern containing only long sequences, ψ(d) = {s ∈ d | length(s) > l}. Later, propositions 1 and 5 stay that MLP is coherent with Definition 6.
Example 3. If we prefer common subsequences of length ≥ 3, then between p2 and p3 in Table 1 there is only one maximal common subsequence, ss6 in Table 2, while ss7 and ss8 are too short to be considered. Figure 2a shows the lattice corresponding the projected pattern structure (Table 1) with patterns of length more or equal to 3.
Proposition 5. MLP is a monotone, contractive and idempotent function on the semilattice (D, u).
Proof. The contractivity and idempotentcy are quite clear from the definition. Remains the proof for monotonicity.
If X v Y where X and Y are sets of sequences then for every sequence x ∈ X there is a sequence y ∈ Y such that x ≤ y (Proposition 1). We should show that ψ(X) v ψ(Y ), or in other words for every sequence x ∈ ψ(X) there is a sequence y ∈ ψ(Y ), such that x ≤ y. Given x ∈ ψ(X), since ψ(X) is a subset of X and X v Y , then there is a sequence y ∈ Y such that x ≤ y, with |y| ≥ |x| ≥ l (l is a parameter of MLP), and thus, y ∈ ψ(Y ).
The second projection of a sequential pattern structure is connected to a projection of an alphabet semilattice, (E, uE ).
Example 4. An expert is interested in finding sequential patterns on how a patient changes hospitals, but he has little interest in procedures. Thus, any element of the alphabet lattice, containing a non-empty set of procedures can be projected to the element with the same hospital but with the empty set of procedures.
Example 5. An expert is interested in finding sequential patterns containing some information about the hospital in every hospitalization, and the corresponding procedures, i.e. hospital field in the patterns cannot be equal to the element “any hospital”, denoted ∗, e.g., ss5 is an invalid pattern, while ss6 is a valid pattern in Table 2. Thus, any element of the alphabet semilattice with ∗ hospital can be projected to the ⊥E . Figure 2b shows the lattice corresponding to the projected pattern structure (Table 1), where projection comes from the projection of the alphabet semilattice.
Below we formally define how the alphabet projection of a sequential pattern structure should be processed. Intuitively, every sequence in a pattern should be substituted with another sequence, by applying the alphabet projection to all its elements. However, the result can be an incorrect sequence, because ⊥E is forbidden to be in a sequence, thus, sequences in a pattern should be “developed” w.r.t. ⊥E , as it is explained below.
Definition 7. Given an alphabet (E, uE ), an alphabet projection ψ and a sequence s based on E, the projection of the sequence ψ(s) is the sequence s˜ such that, s˜i = ψ(si) (si is the i-th element of sequence s).
Here, it should be noted that s˜ can be incoherent with Definition 4, since it allows ⊥E to be an element. For simplicity, we allow this incoherence here. Definition 8. Given an alphabet (E, uE ), an alphabet projection ψ, and a pattern d ∈ D, an alphabet-projected pattern d˜ = ψ(d), is the set of sequences obtained by the following procedure. For every sequence s ∈ d, the projection of s is computed (Definition 7) and, then, the projection of the sequence is substituted by the set of its maximal subsequences containing no ⊥. All the resulting sequences constitute the set dˆ, and d˜ is the set of maximal sequences in dˆ. Example 6. {ss6} is an alphabet-projected pattern for the pattern {ss10}, where alphabet lattice projection is given in Example 5.
{h[CH, {c, d}]i} is an alphabet-projected pattern for the pattern {ss2}, where alphabet lattice projection is given by projecting every element with medical procedure b to the element with the same hospital and with the same set procedures excluding b. The projected sequence of sequence ss2 is h[CH, {c, d}]; [∗, {}]; [∗, {d}]i, but [∗, {}] = ⊥E , and, thus, in order to project the pattern {ss2} the projected sequence is substituted by its maximal subsequences, i.e. ψ({h[CH, {c, d}]; [∗, {b}]; [∗, {d}]i}) = {h[CH, {c, d}]i}.
Proposition 6. Considering an alphabet (E, uE ), the projection of an alphabet ψ, a sequential pattern structure (G, (D, u), δ), the procedure given by Definition 8 is monotone, contractive and idempotent.
Proof. This procedure is idempotent, since the projection of the alphabet is idempotent. It is contractive because for a pattern d, for any sequences s ∈ d, the projection of the sequence s˜ = ψ(s) is a subsequence of s. In the Definition 8 the projected sequences should be substituted by its maximal subsequences in order to avoid ⊥E , building the sets {s˜i}. Thus, s is a supersequence for any s˜i, and, so, the projected pattern d˜ = ψ(d) is subsumed by the pattern d.
Finally, we should show monotonicity. Given two patterns x, y ∈ D, such that x v y, i.e. ∀sx ∈ x, ∃sy ∈ y : sx ≤ sy, consider the projected sequence of sx, ψ(sx). As sx ≤ sy for some sy then for some j0 < j1 < j|sx| (see Definition 5) six vE sjyi (i ∈ 1, 2, ..., |sx|), then ψ(six) vE ψ(sjyi ) (by the monotonicity of the alphabet projection), i.e. projected sequence preserve the subsequence relation. Thus, the alphabet projection of the pattern preserve pattern subsumption relation, ψ(x) ≤ ψ(y) (Proposition 1), i.e. the alphabet projection is monotone. 4 4.1
Nearly all state-of-the-art FCA algorithms can be adapted to process pattern
structures. We adapted AddIntent algorithm [
Experiments and Discussion 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++.
The dataset considered here comes from a French healthcare system [
For this dataset the computation of the whole lattice is infeasible. However a medical expert is not interested in all possible patterns, but rather in patterns which answer his analysis question(s). First of all, the patterns of length 1 are unlikely to be of interest for him. Thus, we use the MLP projection of length 2 or 3 taking into account the small average length of the sequences in the dataset.
For the search of patterns containing only information about reasons and
medical procedures, we should project every alphabet element on the element
with the same reason and the same set of procedures, but substitute
hospitalization institution by the most general element in the corresponding taxonomy.
Moreover, we do not want to allow reason to be empty, i.e. all such elements
should be projected onto ⊥E . In this case computation takes 18 seconds
producing a lattice with around 34700 concepts. One of the stable concepts has
the following intent h[Cancer, {App.}]; [Ch.P rep, {}]; [Chemo, {}]i, specifying that a
cancer was found during the appendix removal surgery, followed by a
chemotherapy. This patterns highlight a discovered fact that acute appendicitis has been
shown to occur antecedent to cancer within three years because of a carcinoma
in colon or rectum [
To find patterns revealing dependences between hospitals and reasons all the procedures should be removed from each alphabet element and elements with most general hospital and/or with most general reason should be projected to ⊥E . The computation of the corresponding lattice takes 10 seconds, producing around 4200 concepts. h[Region Lorraine, Cancer]; [Clinic in Lorraine, Chemo]i is among stable concepts which is rather interesting, because the patients detected cancer somewhere in Region A but then went to exactly the same clinic for chemotherapy. It suggests that the department can lack from clinics for chemotherapy or the quality of the clinic is high.
In this paper, we present sequential pattern structures, an original specification of pattern structures able to deal with complex sequences. Projections of sequential pattern structures allow us to efficiently build concept lattices, by specifying expert demands. To be able to introduce interesting projections, their classical definition is extended. This extension allows us to introduce special projections for sequential pattern structures. The introduced projections are efficiently used for analysis of a dataset on care trajectories.
There are two main directions for future work. First, a study on properties of generalized projections within the overall framework of FCA should be carried out. Second, projections of sequential pattern structures can be deeper analyzed, for producing even more interesting and readable 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).