In this paper, we are interested in sequential data analysis using GALACTIC, a new library based on Formal Concept Analysis (FCA) for calculating a concept lattice from heterogeneous and complex data. Inspired by the pattern structure theory, data in GALACTIC are described by predicates according to their types and a system of plugins allows an easy integration of new characteristics and new descriptions. We present new ways to analyse interval-based sequences, where items persist in time. Here we address the question of mining relevant sequential patterns, describing a set of sequences, by maximal common subsequences, or shortest supersequences. Experimentation on two real sequential datasets shows the effectiveness of our plugins in term of size of the lattice and of running time.
Sequences appear in many areas: sequences of words in a text, trajectories,
surfing on the internet, or buying products in a supermarket. A sequence is a
succession hxii of symbols, sets or events. Sequence mining is a topic of data mining
which aims at finding frequent patterns in a dataset of sequences. Many
algorithms have been proposed for mining sequential patterns, such as GSP [
Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
Formal Concept Analysis (FCA) appears in 1982 [
In this article, we propose a new sequence mining approaches using the NextPriorityConcept algorithm, with descriptions and strategies dedicated to interval-based sequences. We propose two different descriptions that describe a subset of objects by subsequences or supersequences. We also propose five strategies of pattern exploration in order to generate a reduction of a cluster of interval-based sequences, i.e., its predecessors in the pattern lattice.
Section 2 introduces basic definitions related to interval sequence mining and a short description of the NextPriorityConcept algorithm. Section 3 will be dedicated to our new interval-based sequence descriptions and strategies. Experimental results are presented in Section 4. 2 2.1
A sequence s is a succession of itemsets from a dictionary Σ, often in the form of s =< Xi >i≤n, where Xi ⊆ Σ is a subset of items i.e., itemset. A temporal sequence is a sequence where each itemset Xi must have an associated timestamp ti. An Event (or Time frame) E, is a triple E = (t, t, X) where X ⊆ Σ is an itemset, t is the starting time and t is the ending time, t ≤ t. For better readability we refer to (t, t) by T .
Interval-based sequence. An interval-based sequence (or Time frame sequence) s = h(Ti, Xi)ii≤n is a list of events (or time frames), verifying ti < ti+1, thus an interval-based sequence is a list of separate intervals containing itemsets. The size of the interval-based sequence is the number of its time frames. We refer to the interval-based sequence by sequence.
Consider the example in Figure 1 for an alphabet Σ = {C, M, P, H} (where C stands for Castle, M for Museum, P for Public Garden and H for Historical Place), the sequences represent trajectories of visits of three tourists s1, s2 and s3. In this example, visitors may be in two or more different locations at the same interval as the intervals are large enough and we may don’t have the exact interval of each location.
8:00
Subinterval. For two intervals, T = (t, t) and T 0 = (t0, t0), we say that T is
subinterval T 0, if : t ≥ t0 and t ≤ t0 and we write T T 0, that corresponds
to the containing relation from Allen’s relations [
Projections. We introduce the projection operator Φ of a sequence s, over a given interval T , that selects all the itemsets of the sequence included in this interval : ΦT (s) = {X0 : T 0 T and (T 0, X0) ∈ s}. Dually, the projection operator Φ, over an itemset X ⊆ Σ selects all the intervals where the items of X may occur: ΦX (s) = {T 0 : X0 ⊆ X and (T 0, X0) ∈ s}. ΦΣ (s) represents a set of all the intervals in s.
Subsequence. A sequence s, is subsequence of another sequence s0, s b s0 if for all (T, X) ∈ s, there exists (T 0, X0) ∈ s0 such that T T 0 and X ⊆ X0.
We also say that s0 is supersequence of s.
Affix. A prefix/suffix of a sequence s = h(Ti, Xi)ii≤n according to a window w, is the subsequence of s composed by the first/last w time frames of s, prefix(s, w) = h(Ti, Xi)i1≤i≤w, suffix(s, w) = h(Ti, Xi)i(n−w)<i≤n. Cardinality. For a set of sequences A, an item x ∈ Σ and an interval T , the function card gives the number of sequences a ∈ A possessing the item x in the projection of a over T , x ∈ ΦT (a).
card(A, T, x) = |{a : x ∈ ΦT (a), a ∈ A}| (1) When card(A, T, x) is maximal, we denote card(A, T, x) by cardmax(A, T ).
We define cardmin(A, T ) in the same maner when card(A, T, x) is minimal. From example in Figure 1 we have, Φ(10:00,11:00)(s2) = {P, H}, the prefix of s1 is h(08:30, 11:00), P )i, and all three tourists were in the museum from 14:00 to 15:00, so h(14:00, 15:00), M )i is subsequence of s1, s2 and s3. For A = {s1, s2, s3} and T = (11:00, 12:00) card(A, T, P ) = cardmax(A, T ) = 2. 2.2
The NextPriorityConcept algorithm [
gorithm introduces the notion of description δ as an application to provide predicates describing a set of objects A ⊆ G. Each concept (A, δ(A)) is composed of a subset of objects A and a set of predicates δ(A) describing them. Such generic use of predicates makes it possible to consider heterogeneous data as input, i.e., numerical, discrete or more complex data. However, unlike classical pattern structures, predicates are not globally computed in a preprocessing step, but locally for each concept.
Concept lattice generation. The NextPriorityConcept algorithm is
inspired by Bordat’s algorithm[
Predecessors selection by specific strategies. The algorithm also introduces the notion of strategy σ to provide predicates (called selectors) describing candidates for an object reduction of a concept (A, δ(A)) i.e., predecessors of (A, δ(A)) in the pattern lattice. A selector proposes a way to refine the description δ(A) to a reduced set A0 ⊂ A of objects. Several strategies are possible to generate predecessors of a concept, going from the naive strategy classically used in FCA that considers all the possible predecessors, to strategies reducing the number of predecessors in order to obtain smaller lattices. Selectors are only used for the predecessors’ generation, they are not kept either in the description or in the final set of predicates. Therefore, choosing or testing several strategies at each iteration in a user-driven pattern discovery approach would be interesting.
The main result in [
A strategy σ is a mapping σ : 2G → 2P which defines a set of selectors σ(A) to select strict subset A0 of A as predecessor candidates of any concept (A, δ(A)) in the pattern lattice.
Predicates are computed using the subsequence relation in the form ”is subsequence of ” or ”is supersequence of”. For better readability, the sets δ(A) and σ(A) will be treated either as sets of predicates/selectors, or as sets of sequences, they can reciprocally be deduced from each other. 3.1
We define two descriptions for a subset A ⊆ G of sequences. The maximal
common time frame description MCTF refers to the classical maximal common
subsequence description [
8:00
δMCTF(A) = {h(T, X)i : ∀a ∈ A, X ⊆ ΦT (a)} δSSTF(A) = {h(T, X)i : ∀a ∈ A, ΦT (a) ⊆ X} (2) To compute the two descriptions of a set A of sequences, we iterate on the sequences of A, and update the resulting sequences of δ(A) with the common parts. Therefore the complexity of the description is cδMCT F = cδSST F = O(s |A| log(|A|)) ≤ O(s |G| log(|G|)) where s is the maximal size of the computed sequences. We have to ensure that the NextPriorityConcept algorithm generates a concept lattice. These descriptions must verify δ(A) v δ(A0) for A0 ⊆ A: Proposition 1 For A0 ⊆ A ⊆ G, we have the following two properties: Proof: Let A and A0 be two subsets of G such that A0 ⊆ A. 1. Let c ∈ δMCTF(A), i.e., c is a maximal subsequence of A. From A0 ⊆ A we can deduce that c is also a subsequence of sequences in A0, but c is not necessarily a maximal subsequence for A0. If c is a maximal subsequence in A0 then c ∈ δMCTF(A0). Otherwise, there exists c0 ∈ δMCTF(A0) such that c is a subsequence of c0. In these two cases, we can deduce that, δMCTF(A) v δMCTF(A0). 2. Let s ∈ δSSTF(A), i.e., s is the supersequence of all sequences in A. From A0 ⊆ A we can deduce that s is also a supersequence of sequences in A0 but not necessarily the shortest one. If s is a shortest supersequence in A0 then s ∈ δSSTF(A0). Otherwise, there exists s0 ∈ δSSTF(A0) such that s is supersequence of s0. We can deduce that, δSSTF(A) v δSSTF(A0).
Strategies are used by the NextPriorityConcept algorithm to refine each concept (A, δ(A)) into concepts with fewer objects (sequences) and more specific descriptions. It is important to clarify that a strategy must be used with a description composed of predicates of the same kind. Recall that MCTF description defines ”is subsequence of” predicates whereas SSTF description defines ”is supersequence of” predicates. We define one subseqeunce strategy for the MCTF description and four supersequence strategies for the SSTF description.
mented Minimum Cardinality strategy computes all the possible refinements of a concept (A, δMCTF(A)) by adding in the events of sequences of δMCTF any item with a minimal cardinality card(A, T, x) for each time frame T . More formally, σAMC is defined for A ⊆ G by:
σAMC(A) = {h(T, X)i : ∀a ∈ A, ΦT (a) ⊆ X and ∀x ∈ X card(A, T, x) = |A| ∨ card(A, T, x) = cardmin(A, T )} (4) The cost for this strategy is clearly equal to the cost of MCTF description, cσAMC = cδMCT F .
Figure 3, represents the generated Hasse diagram of sequences in Figure 1 using the MCTF description and the AMC strategy, where in each concept the symbol $ represents the identifier of the concept, and the symbol # represents the number of sequences inside the concept, i.e., its support. The concept $0 contains the description of the 3 visits. The concept $1 describes the two visits, s1 and s3 as they were in the Public Garden from 08:30 to 11:00 then in the Museum from 14:00 to 15:00.
Simple Time Frame strategy consists in simply generating selectors by deleting one item from each itemset on the SSTF description. More formally, σSTF is defined for a subset of sequences A ⊆ G, and the SSTF description, by:
σSTF(A, δSSTF) = {h(T, X\{x})i : ∀x ∈ X, (T, X) ∈ s, s ∈ δSSTF(A)} (5) To implement this strategy, we have to consider any item of any sequence of the description, thus a complexity cST F = O(s m cSST F ) ≤ O(s |Σ| cδSST F ) where σ δ m is the maximal number of items in any time frame in the sequences of the description.
$1: #2 s match ["[8.3;12):{'P'}", "[13;14):{'M', 'H'}", "[14;15):{'M', 'C', 'H'}", "[15;16):{'C', 'M'}"] $5:#1 ['s3'] $0:#3 $2: #2 s match ["[8.3;10):{'P'}", "[10;12): {'P', 'H'}", "[14;16):{'C', 'M'}"] $4:#1 ['s1'] $6:#1 ['s2'] $7:#0
$3: #2 s match ["[8.3;10):{'P'}", "[10;12):{'P', 'H'}", "[13;15):{'M', 'H'}", "[15;16): {'M'}"]
Figure 4 represents the generated Hasse diagram using the SSTF description and the STF strategy. Concepts $1, $2, and $3 contain descriptions of {s1, s3}, {s2, s3}, and {s1, s2}. Concept $2 shows that at least one of s2 or s3 visited P from 08:30 to 10:00, then H or P from 10:00 to 12:00, and finally C or M from 14:00 to 16:00. The strategy constructs a lattice with all concepts, hence it is time consuming. So, we thought about strategies that may reduce the size of the lattice, and the time complexity. The Bounds Time Frame strategy consists in deleting only the items of cardinalities minimal or maximal. The Window Affix Time Frame strategy uses a window parameter w and generates the prefix and suffix. The Alphabet Time Frame strategy, deletes one item of the alphabet from all the time frames. More Formally, these strategies are defined for a subset A of sequences and the description δSSTF by:
σBTF(A, c) = {h(T, X\{x})i : (T, X) ∈ s, card(A, T, x) = c, s ∈ δSSTF(A)} (6) (7)
In particular, we can consider σBTF(A, cardmax) and σBTF(A, cardmin)
σWATF(A, w) = {h(T, X)i : (T, X) ∈ s − prefix(s, w),
(T, X) ∈ s − suffix(s, w), s ∈ δSSTF(A)} Here the s − prefix(s, w) means s without time frames in prefix(s, w), same for s − prefix(s, w).
σATF(A) = {h(T, X\{x})i : ∀(T, X) ∈ s, ∀x ∈ Σ, s ∈ δSSTF(A)} (8) The cost of the BTF strategy is cBT F = O(s cδSST F ), as it must calculate the σ predicates of SSTF, then iterate on the resulting sequences. For the WATF strategy, cW AT F = cSST F , the w parameter is constant, so the cost is equal only to the σ δ cost of δSSTF. For the ATF strategy cAT F = O(s cδSST F ).
σ
The NextPriorityConcept allows a user-driven approach for the data analyst to choose strategies that respond the best to the specifications of the data. With the SSTF description, the data analyst have a choice of 4 strategies. The BTF strategy allows a generation of predecessors where frequent or nonfrequent events may not appear (maximum and minimum cardinalities). The WATF strategy focuses of events that appear first or last at the same interval. The ATF strategy focuses on clusters where some events may not appear. The use of these strategies reduces the time complexity of the lattice generation process and generate a smaller lattice than the STF strategy. 4
In this section, we experimentally evaluate our descriptions and strategies for mining interval sequences. Our approach is different from previous works. We are not mining all frequent interval-based sequences, but we use our strategies and descriptions to mine only the relevant ones. To experimentally assess the effectiveness of our descriptions and strategies, we use GALACTIC1 (GAlois LAttices, Concept Theory, Implicational systems and Closures), a development platform 1 https://galactic.univ-lr.fr of the NextPriorityConcept algorithm, which mixed with a system of plugins, makes it possible easy integration of new kinds of data (descriptions and strategies). We have implemented new plugins for sequences. Experiments were performed on an Intel Core i7 2.20GHz machine with 32GB main memory. We run our experiments on two real datasets: GeoLuciole dataset is issued from classical GPS trajectories of people’s deplacements in the city of La Rochelle in France. By matching the GPS coordinates to districts of the city, raw data are transformed into semantic sequences. The data have been collected by a specific application named GeoLuciole that we have developed for the DA3T2 project. The data contains only 15 trajectories with an average size of sequences equals to 23. Wine-City dataset is issued from the museum ”La cit´e du vin” in Bordeaux, France4, gathered from the visits over a period of one year (May 2016 to May 2017). The museum is a large ”open-space”, where visitors are free to explore the museum the way they want. The trajectories in this dataset are of size 9 on average.
Here we compare our two descriptions in terms of running time and lattice size. We use the MCTF description with the AMC strategy, and the SSTF description with the STF strategy. These two strategies generate all possibles subseqeunces/supersequences. Results for the Wine-City dataset are given in Table 1. We can observe that MCTF is far faster than SSTF. It generates a lattice of 149 concepts in about 2 minutes from 500 sequences, while the SSTF description, stops with 1024 concepts generated in about 30 minutes from only 10 sequences. These descriptions are two different ways of representing the data. The SSTF description is clearly richer than the MCTF description that is the classical maximal common subsequences description extended to intervals, but SSTF is not adapted to huge datasets.
data size 4 6 10 100 500 1000 # concepts 16 33 1024 σSTF(δSSTF) time(ms) 2878 11760 1927039 time/concept(ms) 179,87 356,36 1881,87 # concepts 6 σAMC(δMCTF) time(ms) 267 time/concept(ms) 44.5 2 System for the Analysis of Numerical Traces for the development of Tourist Territories (Dispositif d’Analyse des Traces num´eriques pour la valorisation des Territoires Touristiques) 3 It was planned to collect more data during the holidays on Mars and April, but unfortunately, this was impossible due to the world pandemic Covid-19 4 https://www.laciteduvin.com/en
We focus now on the SSTF description to compare the four strategies; STF, BTF, WATF and ATF. Recall that the STF strategy generates all possible supersequences whereas BTF, WATF and ATF focus on special supersequences (prefix, suffix, according to a window). Figure 5 shows the running time and the number of concepts generated using the Wine-City dataset. Compared to the STF strategy, we can clearly see that the other strategies are faster, and generate fewer concepts. The WATF strategy is the best in this example, especially with w = 1, with w = 2: the result approximates that of the BTF strategy. We run the BTF strategy with cardmin and cardmax: we observe that the running time is better, and we obtain fewer concepts with cardmin. The complexity of NextPriorityConcept depends on the size of the lattice, therefore a reduction to more relevant concepts also reduce the running time. Table 2 presents a comparaison between the four strategies of the SSTF description with the GeoLuciole dataset. The BTF, ATF and WATF strategies are compared to the STF in terms of compression ratio i.e., the ratio between the number of concepts obtained with the STF strategy by the number of concepts obtained with each of the other strategies. Table 2 shows the effectiveness of our strategies in reducing the number of concepts. We can also observe that the compression ratio is improved as we increase the size of the data for all strategies. ATF strategy performs better and generates fewer concepts compared to BTF. The compression ratio is low with the WATF strategy, because the size of sequences is close to the window, and thus as we raise the windows the number of concepts get closer to the STF strategy. The behaviour of WATF strategy is linked to the average size of the sequences. The data analyst can variate parameters such as the cardinality for BTF, or the window for WATF, to generate only relevant concepts. 5 Conclusion In this paper, we presented a sequence mining approach using the NextPriorityConcept algorithm. This algorithm allows a generic pattern computation through specific descriptions and strategies.
We presented two descriptions and five strategies for analysing interval-based sequences. The two descriptions represent two different approaches for representing a set of sequences. The first one MCTF is the classical maximal common dataset size σSTF # Concepts
128 672 16640 subsequences, whereas the second one SSTF provides a richer description of interval sequences. We presented one strategy for the MCTF description, and four strategies for the SSTF description that can be tested in a user-driven approach in order to generate fewer concepts and more relevant data. Therefore, we will focus on reducing the time complexity of our plugins, and create more configurable ones that respond the best to the particularity of the data we want to treat.