This paper presents a research work in the domains of sequential pattern mining and formal concept analysis. Using a combined method, we show how concept lattices and interestingness measures such as stability can improve the task of discovering knowledge in symbolic sequential data. We give example of a real medical application to illustrate how this approach can be useful to discover patterns of trajectories of care in a french medico-economical database.
indicates to what extent a pattern is frequent in a database. Many (sequential and non sequential) itemset mining methods use support as measure for nding interesting correlations in databases. However, the most relevant patterns may not be the most frequent ones. Moreover, discovering interesting patterns with low support leads generally to overwhelming results that need to be further processed in order to be analyzed by human experts.
Formal Concept Analysis (FCA) is a theory of data analysis introduced in
[
To our knowledge, there are no similar approaches to nd interesting sequential patterns. In this paper, we present an original experiment based on both multilevel and multidimensional sequential patterns and lattice-based classi cation. This experiment may be regarded from two points of view: on the one hand, it is based on multilevel and multidimensional sequential patterns search, and on the other hand, visualization and classi cation of extracted sequences is based on Formal Concept Analysis (FCA) techniques, organizing them into a lattice for analysis and interpretation. It has been motivated by the problem of mining care trajectories in a regional healthcare system, using data from the PMSI, the so called French hospital information system. The remaining of the paper is organized as follows. In Section 2, we present the problem of mining care trajectories. Section 3 presents the methods proposed in domains of multilevel and multidimensional sequential patterns and Formal Concept Analysis. In Section 4, we present some of the results we achieved. 2
The PMSI (Programme de Medicalisation des Systemes d' information) database is a national information system used in France to describe hospital activity with both an economical and medical point of view. The PMSI is based on the systematic collection of administrative and medical data. In this system, every hospitalization leads to the collection of administrative, demographical and medical data. This information is mainly used for billing and planning purposes. Its structure can be described (and voluntarily simpli ed) as follows: { Entities (attributes):
Patients (id, gender . . . ) Stays (id, hospital, principal diagnosis, . . . ) Associated Diagnoses (id)
Procedures (id, date,. . . ) { Relationships a patient has 1 or more stays a stay may have several procedures a stay may have several associated diagnoses
The collection of data is done with a minimum recordset using controlled vocabularies and classi cations. For example, all diagnoses are coded with the International Classi cation of Diseases (ICD10)1. Theses classi cations can be used as taxonomies to feed the process of multilevel sequential pattern mining as shown in gure 1.
ICD 10
Healthcare management and planning play a key role for improving the overall health level of the population. From a population point of view, even the best and state-of-the-art therapy is not e ective if it cannot be delivered in the right conditions. Actually, many determinants a ect the e ective delivery of healthcare services: availability of trained personnel, availability of equipment, security constraints, costs, proximity . . . . All of these should meet economics, demographics, and epidemiological needs in a given area. This issue is especially acute in the eld of cancer care where many institutions and professionals must cooperate to deliver high level, long term, and costly care. Therefore, it is crucial for healthcare managers and decision makers to be assisted by decision support systems that give strategic insights about the intrinsic behavior of the healthcare system.
On the one hand, healthcare systems can be considered as rich in data as
they produce massive amounts of data such as electronic medical records,
clinical trial data, hospital records, administrative data, and so on. On the other
hand, they can be regarded as poor in knowledge as these data are rarely
embedded into a strategic decision-support resource [
In this experiment, we have worked on four years (2006 { 2009) of the PMSI data of the Burgundy region related to patient su ering from lung cancer.
Sequential Pattern Mining
Let I be a nite set of items. A subset of I is called an itemset. A sequence
s = hs1s2 : : : ski (si I) is an ordered list of itemsets. A sequence s = hs1s2 : : : sni
is a subsequence of a sequence s0 = hs01s02 : : : s0mi if and only if 9i1; i2; : : : in such
that i1 i2 : : : in and s1 s0i1 ; s2 s0i2 : : : an s0in . We note s s0 and
also say that s0 contains s. Let D = fs1; s2 : : : sng be a database of sequences.
The support of a sequence s in D is the proportion of sequences of D containing
s. Given a minsup threshold, the problem of frequent sequential pattern
mining consists in nding the set FS of sequences whose support is not less than
minsup. Following the seminal work of Agrawal and Srikant [
Much work has been done in the area of single-dimensional sequential
patterns, i.e, all the items in a sequence have the same nature like the sequence
of products sold in a certain store. But in many cases, the information in a
sequence can be based on several dimensions. For example: a male patient had a
surgical operation in Hospital A and then received chemotherapy in Hospital B.
In this case, we have 3 dimensions: gender, type of treatment (chemotherapy,
surgery) and location (Hospitals A and B). Pinto et al [
Moreover, each dimension can be represented by di erent levels of granularity, using a taxonomy which de nes the hierarchical relations between items. Figure 2 shows an example of a diseases taxonomy. Including knowledge contained in the taxonomy leads to the problem of multilevel sequential pattern mining. Its interest resides in the capacity to extract more or less general/speci c sequential patterns and overcome problems of excessive granularity and low support. For example, using the diseases taxonomy in Figure 2, sequences such as hHeartDisease; BrainDisease > could be extracted while hArryth:; BrainDisease > and hMyoc:Inf:; BrainDisease > may have a too low support.
extraction of association rules and sequential patterns, their approach was not scalable
in a multidimensional context. Han et al [
The PMSI is a multidimensional database holding information coded with controled
vocabularies and taxonomies. Therefore, we relied on M3SP to extract multilevel and
multidimensional sequential patterns. Nevertheless, the M3SP paradigm is still the
search of frequent patterns. As our objective is to discover interesting patterns that
may be infrequent, we ran M3SP iteratively until very low support thresholds. (See
appendix for more details about M3SP and how we used it). This produced massive
amounts of patterns requiring further processing for a practical interpretation by a
domain expert. This next phase was conducted with a lattice-based classi cation of
sequential patterns described in the following section.
Introduced by Wille [
FCA starts with a formal context K = (G; M; I) where G is a set of objects, M is a set of attributes, and the binary relation I = G M speci es which objects have which attributes. Two operators, both denoted by 0, connect the power sets of objects 2G and attributes 2M as follows: 0 : 2G ! 2M; X0 = fm 2 Mj8g 2 X; gImg 0 : 2M ! 2G; Y0 = fg 2 Gj8m 2 Y; gImg The operator 0 is dually de ned on attributes. The pair of 0 operators induces a Galois connection between 2G and 2M. The composition operators 00 are closure operators: they are idempotent, extensive and monotonous. For any A G and B M, A00 and B00 are closed sets whenever A = A00 and B = B00.
A formal concept of the context K = (G; M; I) is a pair (A; B) G M where A0 = B and B0 = A. A is called the extent and B is called the intent. A concept (A1; B1) is a subconcept of a concept (A2; B2) if A1 A2 (which is equivalent to B2 B1) and we write (A1; B1) (A2; B2). The set B of all concepts of a formal context K together with the partial order relation forms a lattice and is called concept lattice of K. This lattice can be represented as a Hasse diagram providing a visual support for interpretation.
We use FCA to classify and lter the results of the sequential mining step. The formal context is built by taking patients as objects, and sequential patterns as attributes. A patient p, considered as a sequence, is related to a sequential pattern s if p contains s. Table 4 shows a formal context KP S representing the binary relation between the patients and the sequences. The cross indicates that the patient has passed completely in the sequence of the health facilities. Thus, we achieve a classi cation of patients according to their trajectories of care.
Seq1 Seq2 Seq3 Seq4 P1 x x x P2 x P3 x x x
P4 x
on particular objects of the extent. It indicates the probability of preserving concept intent while removing some objects of its extent. A stable concept continues to be a concept even if a few members stop being members. This means also that a stable concept is resistant to noise and will not collapse when some members are removed from its extent.
Patient healthcare trajectories The PMSI is a relational database holding informations for any hospitalization in France. We reconstituted patient care trajectories from PMSI data considering each stay as an itemset. The sequence of stays for a same patient de nes his care trajectory. In our experiment, itemsets could be made of various combinations of dimensions. Table 2 shows the trajectories of care obtained using two dimension (principal diagnosis, hospital ID). For example (C341,210780581) represents one hospitalization for a patient in the University Hospital of Dijon (coded as 210780581) treated for a lung cancer (C341). Our dataset contained 486 patients su ering from lung cancer and living in the French region of Burgundy.
Table 3 shows some of the patterns generated by M3SP with the data presented in Table 2 using taxonomies of Figure 1. Pattern 3 can be interpreted as follows: 36% of patients have a hospitalization in a private institution (CL), for any kind of principal diagnosis (ALL). Then, 3 hospitalizations follow with the same principal diagnosis (Z511 coding for chemotherapy). That kind of pattern demonstrates the interest of multilevel and multidimensional sequential pattern mining: though principal diagnosis are the same in the third last stays, hospitals can be di erent. Mining at the lowest level of granularity, without taxonomies, would generate many di erent patterns with lower support.
Institutions Principal Diagnosis, Institution All diagnoses Institutions, Medical Procedures
1529 4051 50546 293402
Lattice-based classi cation of sequential patterns We illustrate this approach with patterns representing the sequences of institutions that are frequent in the patients set. We built a formal context relating 486 patients and 1529 sequential patterns. These sequences are generated in the rst experimental by considering only one dimension (healthcare institutions). It is characterized with a taxonomy with two levels of granularity. We iteratively applied M3SP, decreasing threshold by one patient at each step. The resulting lattice has 10145 concepts organized on 48 di erent levels. Figure 3 shows the upper part of the lattice. Concepts intents are sets of one or more sequential patterns. From the lowest right concept, we can see that 37 patients support 3 sequential patterns: { at least one hospitalization in the hospital 690781810 { they were hospitalized at least once in a University Hospital (CHU/CHR) { they had at least 2 hospitalization, for simplicity, 2*(ALL) is the contraction of (ALL)(ALL).
The intent of top concept is h(ALL)i, because all patients have at least one hospitalization during their treatment. The intent of co-atoms (i.e. immediate descendant of top) is always a sequence of length one, holding items of high level of granularity. <{(All)}>
Nb=486 <{(CL)}> <{(All)}>
Nb=287 <2*{(All)}>
Nb=475 <{(CHU/CHR)}
> <{(All)}> Nb=259 <{(CH)}> <{(All)}> Nb=279 … <3*{(All)}>
Nb=459 <{(710780354)}> <{(CL)}> <{(All)}> Nb=12 <{(890000409)}> <{(CH)}> <{(All)}> Nb=457 <{(CHU/CHR)}> <2*{(All)}>
Nb=254 <{(CH)}> <2*{(All)}>
Nb=277 … <4*{(All)}>
Nb=445 <{(210780714)}> <{(CH)}> <2*{(All)}>
Nb=23 <{(710780354)}> <{(210780979)}> <{(CL)}> <{(All)}>
Nb=8 <{(710780958)}> <{(CH)}> <2*{(All)}>
Nb=32 <{(210780581)}> <{(CHU/CHR)}> <{(All)}>
Nb=156 <{(690781810)}> <{(CHU/CHR)}> <2*{(All)}>
Nb=37 … …
highlight the interesting properties of stability, we try to answer the question \is there a number of hospitalizations that characterizes care trajectories for lung cancer?". A basic scheme in lung cancer treatment consists generally in a sequence of 4 chemotherapy sessions possibly following a surgical operation. Due to noise in data or variability in practices, we may observe sequences of 4, 5, 6 or more stays in the PMSI database. Mining such data with an a priori xed support threshold may not discover the most interesting patterns. If the threshold is too high, we simply miss the good pattern. If it is too low, similar patterns, di ering only in length, with close values of support can be extracted. Figure 4 shows the power of stability in discriminating such patterns. The concept with intent h(CL)ih2 (ALL)i is the most frequent. It represents patients with at least a stay in a private organization, and at least 2 stays in hospital. Similar concepts have a relatively close support, and di er only in the total number of stays. The concept with 5 stays has the highest stability. This probably matches the basic treatment scheme of lung cancer. Our interpretation relies on the power of stability to point out noisy concepts. Actually, only a few patients in concept h(CL)ih2 (ALL)i have only 2 stays.
Another interesting feature of lattice-based classi cation of sequential patterns lies in its ability to characterize objects by several patterns. Let consider the minimal database of sequences D = fs1 = h(a)(b)(c)i; s2 = h(a)(c)(b)i : s3 = h(d)ig. With a 2/3 threshold, h(a)(b)i and h(a)(c)i are considered as frequent sequential patterns, but sequential pattern mining will give no information about the fact that all sequences containing the pattern h(a)(b)i contain also the pattern h(a)(c)i. However this information can be obtained by classifying sequential patterns with FCA.
In this paper we propose an original combination of sequential pattern mining and FCA to explore a database of multidimensional sequences. We show some interesting properties of concept lattices and stability index to classify and select interesting sequential patterns. This work is in a early step. Further developments can be made in several axes. First, other measures of interest could be investigated to qualify sequential patterns. Furthermore, connexions between FCA and the sequential mining problem could be explored in a more integrative approach, especially by studying closure operators on sequences. 7
The authors wish to thank the TRAJCAN project for its nancial support and Mrs. Catherine QUANTIN, the responsible of TRAJCAN project at university hospital of
The M3SP algorithm is able to extract sequential patterns characterized by several
dimensions with di erent levels of granularity for each dimension [
5b shows a dataset of hospitalizations relating patients (P) with attributes from three dimensions { T, the date of stay, { H, the healthcare setting in which the hospitalization takes place, { D, the disease of the patient.
for the disease D11 in hospital H11. Let us now assume that we want to extract all multidimensional sequences that deal with hospitals and diseases that are frequent in the patients set. Figure 5a displays a taxonomy for dimensions H and D. Pre-processing step M3SP considers three types of dimensions: a temporal dimension Dt, a set of analysis dimensions DA, and a set of reference dimensions DR. M3SP orders the dataset according to Dt. The tuples appearing in a sequence are de ned over the dimensions of DA. The support of the sequences is computed according to dimensions of DR. M3SP splits the dataset into blocks according to distinct tuple values over reference dimensions. The support of a given multidimensional sequence is the ratio of the number of blocks supporting the sequence over the total number of blocks. In our example, H (hospitals) and D (diseases) are the analysis dimensions, T is the temporal dimension and P (patients) is the only reference dimension. We obtain two blocks de ned by Patient1 and Patient2. as shown in table 5c.
MAF-item generation step In this step, M3SP generates all the Maximal Atomic Frequent items or MAF-items.
Speci city relation. Given two multidimensional items a = (d1; :::; dm) and a0 = (d01; :::; d0m), a0 is said to be more speci c than a, denoted by a 4I a0 , if for every i = 1; :::; m, d0i 2 di #. Where di # is the set of all direct specializations of di according to the dimension taxonomy of di. In our example, we have (H1; D1) 4I (H1; D11), because H1 2 H1 # and D1 2 D11 #.
MAF-item. An atomic item a is said to be a Maximal Atomic Frequent item, or a MAF-item, if a is frequent and if for every a0 such that a 4I a0 , the item a0 is not frequent. In our example, if we consider minsup = 100%, b = (H1; D1) is a MAF-item, because it is frequent and there is not another item as frequent and more speci c than b.
of the form (d1; d2)s, meaning that (d1; d2)s is an atomic item with support s as we show in Figure 5d. In this tree, MAF-items are displayed as boxed nodes. We note that all leaves are not necessarily MAF-items. For example, (H2; D21)100% is a leaf, but not a MAF-item. This is because (H2; D21)100% 4I (H21; D21)100% and (H21; D21) has been identi ed as being an MAF-item.
Sequence mining step Frequent sequences can be mined using any standard sequential pattern-mining algorithm (Pre xSpan in this work). Since in such algorithms, the dataset to be mined is a set-pairs of the form (id; seq), where id is a sequence identi er and seq is a sequence of itemsets, our example dataset is transformed as follows : { every MAF-item is associated with a unique identi er denoted by ID(a) (table
{ every block b is assigned a patient identi er ID(p), playing the role of the sequence identi ers in standard algorithms, { every block b transformed into a pair (ID(b); (b)), where (b) is a sequence. (table 5f)
Pre xSpan is run over table 5f. By considering a support threshold minsup =50%, table 5g displays all the frequent sequences in their transformed format as well in their multidimensional format in which identi ers are replaced with their actual values.
For example (H1; D1) is frequent according to minsup=50%, but another item, (H11; D11) is more speci c and still frequent. As a result, (H1; D1) is not a MAF-item and consenquently not used to build squences. Finaly the frequent sequence hf(H1; D1); (H21; D21)gi does not appear in the results of M3SP. However, tables 5 and 6 show the MAF-items set and the frequent sequences extracted by M3SP at a 100% threshold. It can be noticed that (H1; D1) is a MAF-item and that the sequence hf(H1; D1); (H21; D21)gi is generated.
for 0 may not always contain the set of sequences obtained for .
(H1; D1) (H21; D21)
hf(H1; D1)gi hf(H21; D21)gi hf(H1; D1); (H21; D21)gi / d a r P co T 1 2 c a o n o i t i 1 1 t
1 2 r D a
D D p
1 k 1 1 t c
1 2 n lo H
H H e B / .
) a c P (5 T 1 2 e r . } t 1 1
1 2 D 12 21 t
e D D D D S a t 1 1 2 1 a
1 2 1 2 D H .
H H H H ) b ( 5
e T 1 2 1 2 l
a 2 xo 2 2 a 2 's H t D y e
's m n 2 1 s 1 o io
H 2 n 2 2 n s D , * ( D , 1 e S m I I I s e c n e n e > > u )} )} q
e 1 1 2 2 S H H t ( ( n { { e < < u ) a ( 1 2 3 D I a ) ) ) m 1 2 1 M e 1 1 2 . -it‐ ,D ,D ,D ()e f 1 2 1 1 1 2 T . ) f ( T % n
0 a % m p 5 % 0 te S = 0 0 i x p 10 )1 ic fi u ) 1 e s 2 2 m r in
m o D D t P 0% ,2 ,2 ta 0 H H n 1 ( ( e ) u q ) ,* ,* 2 % fer b a t (* (H ,)*H21100% ,)D211200% ,)D2112100 .)(fereodT ()ςb ,)(()>13 ,)(()>23 fsreoadDm ( H H 5 < < n ( ( e a r r