Nyoman Juniarta
email: nyoman.juniarta@loria.fr

Miguel Couceiro
email: miguel.couceiro@loria.fr

Amedeo Napoli
email: amedeo.napoli@loria.fr

Chedy Raïssi
email: chedy.raissi@loria.fr

Sequential Pattern Mining using FCA and Pattern Structures for Analyzing Visitor Trajectories in a Museum

Keywords: FCA, pattern structures, sequence clustering, sequential pattern mining

This paper presents our work on mining visitor trajectories in Hecht Museum (Haifa, Israel), within the framework of CrossCult European Project about cultural heritage. We present a theoretical and practical research work about the characterization of visitor trajectories and the mining of these trajectories as sequences. The mining process is based on two approaches in the framework of FCA, namely the mining of subsequences without any constraint and the mining of frequent contiguous subsequences. Both approaches are based on pattern structures. In parallel, a similarity measure allows us to build a hierarchical classification which is used for interpretation and characterization of the trajectories w.r.t. four well-known visiting styles.

Introduction

This paper is related to the CrossCult European Project about cultural heritage (http://www.crosscult.eu/). The general idea of CrossCult is to support the emergence of a European cultural heritage by allowing visitors in different locations (e.g. museum, city, archaeological site) to consider their visit at a European level by using adapted computer-based devices.

In this project, we are mainly interested in the analysis of visitor trajectories and recommendation. The trajectory of a visitor in a specific location is considered as a multi-dimensional sequence depending on a number of variables, such as space (e.g. paths, rooms, environment), time (e.g. hour, day, season, news), history and geography (e.g. town, region, country. . . ). Moreover, additional domain knowledge and general knowledge bases such as DBpedia, Freebase or YAGO can be reused to draw inferences and improve the quality of both analysis and recommendation.

Here, we have two main objectives, (i) the mining of visitor trajectories based on sequence mining, and (ii) the characterization of a trajectory in terms of the subsequences which are mined. We assume that the subsequences are related to the visiting styles, the visit content, and the environment. Thus subsequences can be used for analyzing the trajectory of a visitor and for making recommendations all along the visit. Moreover, the occurrences of some subsequences at a given moment within a trajectory can witness a change of behavior -which triggers in turn a change in the recommendations.

In the present paper, we discuss theoretical and practical work about the definition of visitor trajectories and the mining of these trajectories as sequences. The mining process is based on two approaches about sequence mining in Formal Concept Analysis (FCA [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]): MRGS for "Mining Rare General Subsequences" [START_REF] Codocedo | A proposition for sequence mining using pattern structures[END_REF] and MFCS for "Mining Frequent Contiguous Subsequences" [START_REF] Buzmakov | On mining complex sequential data by means of FCA and pattern structures[END_REF]. The first approach mines rare subsequences in a general way, i.e. gaps may appear in the subsequences, while the second approach searches for frequent subsequences without any gap (a kind of substrings). If the original paper about MRGS [START_REF] Codocedo | A proposition for sequence mining using pattern structures[END_REF] was interested in rare subsequences, this is no more the case here and we work on frequent subsequences as well. We also reuse the similarity measure sim ACS developed for analyzing the trajectories of patients between hospitals [START_REF] Egho | A contribution to the discovery of multidimensional patterns in healthcare trajectories[END_REF][START_REF] Egho | On measuring similarity for sequences of itemsets[END_REF]. This similarity measure allows us to build a hierarchical classification that will play a role of "reference classification". For analyzing and interpreting the trajectories of visitors, it is interesting to compare the outputs of MRGS and MFCS algorithms w.r.t. the clustering produced by sim ACS . Moreover, these outputs and the clustering as well are analyzed thanks to four theoretical visiting styles, namely "ant", "butterfly", "fish" and "grasshopper" [START_REF] Véron | Ethnographie de l'exposition[END_REF].

Several challenges are faced in this research work in the FCA framework: the mining of complex sequential data and dynamics in adapting two algorithms based on pattern structures, the analysis of the trajectories based on jumping emerging patterns and clustering. Here, data are not necessarily big but are rather complex and multidimensional and this should be taken into account.

The paper is organized as follows. Section 2 recalls the basic definitions about sequence mining that are useful for understanding the present work. Then, Sect. 3 presents the characteristics of the dataset that was used as a basis for the current work. In Sect. 5 and Sect. 6, we present first the application of clustering on data enabling to build classes of visitors, and then the application of two algorithms for mining interesting subsequences. Finally, in Sect. 7, an interpretation of the results and a discussion on the characterization of the visitor trajectories conclude the paper.

Sequence Mining

Basic Definitions

Pattern mining is the task of finding repeated occurrences in a dataset. For example, in a dataset about customer transactions, an objective can be to find a set of items that are frequently ordered in a single transaction. Another complex objective is to detect a set of items that are likely ordered within certain transactions. These specific tasks in pattern mining are related to sequential pattern mining. We recall below the most important definitions that we need in the following. Definition 1. A sequence is an ordered list s 1 s 2 . . . s m , where s i is an itemset {i 1 , . . . , i n }. Here, m is the size of a sequence. The length of a sequence is the total number of items, or |s i |.

For example, {a, b}{a, c, d} is a sequence with size 2, since it contains two itemsets. Its length is 5. Definition 2. A sequence s = s 1 s 2 . . . s m is a subsequence of s = s 1 s 2 . . . s n , denoted by s s , if there exist indices 1 ≤ i 1 < i 2 < . . . < i m ≤ n such that s j ⊆ s ij for all j = 1 . . . m and m ≤ n.

Therefore, the sequence {a}{d} is a subsequence of {a, b}{a, c, d} , while sequence {c}{d} is not.

One way of evaluating the quality of a subsequence is to compute the support of the subsequence. Given a user-defined threshold, the subsequence can be "frequent", i.e. the support is above the threshold, or "rare", i.e. the support is below the threshold. Definition 3. Let S be a sequential database. The support of a sequence s in S is: support(s, S) = |{s i ∈ S; s s i }| There exist algorithms which can retrieve all frequent sequences [START_REF] Han | Pre-fixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth[END_REF][START_REF] Ayres | Sequential pattern mining using a bitmap representation[END_REF]. A long sequence can have a combinatorial number of subsequences. Thus, if a long sequence is frequent, these algorithms return all of its subsequences. This leads to the retrieval of many uninteresting patterns. This issue has been studied in [START_REF] Yan | CloSpan: Mining: Closed sequential patterns in large datasets[END_REF][START_REF] Wang | BIDE: Efficient mining of frequent closed sequences[END_REF][START_REF] Gomariz | ClaSP: an efficient algorithm for mining frequent closed sequences[END_REF] by introducing the concept of "closed sequence". They narrow the output by disregarding sequences which have another supersequence with the same support (hence not closed).

Beside mining frequent sequences, another complex task is clustering. To achieve such a task, a distance or a similarity measure between two sequences has to be defined. The similarity measure sim ACS was proposed in [START_REF] Egho | On measuring similarity for sequences of itemsets[END_REF], which counts the number of all common subsequences (ACS). This measure is formulated as:

sim ACS (S i , S j ) = φ C (S i , S j ) max{φ D (S i ), φ D (S j )} (1)
where φ C (S i , S j ) is the number of all common distinct subsequences between S i and S j , while φ D (S i ) is the number of all distinct subsequences of S i .

In this paper, we reuse sim ACS with a restriction. Actually, we consider sequences whose itemsets include only one item. For simplicity, we omit the curly brackets to describe an itemset. Therefore we will write {a}{d}{e} as a, d, e .

Sequence Mining in FCA

In this section we briefly present the two algorithms that are adapted for mining the trajectories of visitors in a museum, namely MFCS [START_REF] Buzmakov | On mining complex sequential data by means of FCA and pattern structures[END_REF] and MRGS [START_REF] Codocedo | A proposition for sequence mining using pattern structures[END_REF]. The names of the algorithms are not used as such in the papers but here we use them by commodity. Both algorithms are original and very efficient, and among the few algorithms performing sequence mining in the framework of FCA.

MFCS was originally introduced for mining trajectories of patients in hospitals. The algorithm is based on pattern structures and projections, and stability as well. One important characteristic of MFCS is that it mines contiguous subsequences, or stated differently, subsequences without any gap between items. This is due to the fact that physicians are mainly interested in consecutive events when analyzing healthcare trajectories. In addition, but this is not needed in our framework, MFCS is able to take into account a partial ordering -given by domain knowledge for example -defined on the items composing the sequences.

MRGS is also a sequence miner based on pattern structures but with a different purpose. The objective of MRGS is to mine rare rather than frequent subsequences, and in particular long subsequences with special characteristics. The algorithm is based on a specific pattern structure of subsequences, where the similarity operation is based on the discovery of common close subsequences (SCCS operation illustrated in a next section). The SCCS operation is based on a directed graph of alignments (DAG of alignments) which guide the mining of common subsequences. The algorithm shows very good performances and is most probably one of the few algorithms whose objective is the mining of rare subsequences. In our framework, we adapted MRGS and the support threshold for comparison purposes with frequent subsequences. However, we will use in our context MRGS as a standard sequence miner and we will be interested in frequent subsequences.

The Dataset of Museum Visitors

The Museum

In the framework of the CrossCult project, we are working on a specific dataset about the trajectories of 254 visitors in Hecht Museum in Haifa, Israel [START_REF] Lanir | The influence of a locationaware mobile guide on museum visitors' behavior[END_REF]. In the raw dataset, a visitor trajectory contains a list of visited items, where each visit is composed of three elements namely "start time", "end time", and "item name". An example is presented in Table 1. A visitor can have visits with various time lengths. In order to obtain more meaningful results and to reduce the complexity, we only consider visits lasting at least 90 seconds, but this is a parameter that can be relaxed or more constrained. Thirty-eight trajectories have no visit more than this threshold, so they are ignored, leaving us with 216 trajectories. Moreover, we model each trajectory as a sequence of visited items. Therefore, for trajectory in Table 1, the corresponding sequence is Crafts and Arts, Wooden Tools . This preprocessing results in sequences of various size. Forty-five sequences have only one itemset, while three sequences have more than 15 itemsets. We group the museum items according to their location, so that we obtain 8 categories of items. Some of them are listed in Table 2. We convert the raw dataset into sequences of items, where each item is represented by its ID. We define the IDs such that we can infer the category of an item by its first digit. Therefore, we obtain a dataset of 216 sequences of visitor trajectories -named V 1 -V 216 -where each sequence is composed by a list of IDs, as illustrated in Table 3.

The Four Visiting Styles

In a seminal work about the typing of visitor styles in a museum [START_REF] Véron | Ethnographie de l'exposition[END_REF], four main behaviors have been detected and described, leading to different recommendations all along a visit [START_REF] Zancanaro | Analyzing museum visitors' behavior patterns[END_REF][START_REF] Kuflik | Analysis and prediction of museum visitors' behavioral pattern types[END_REF]. These four styles are summarized below:

-The ant denotes a visitor who will surely see all the works following their location order in the museum. Then the recommendation can be the following item, but depending also on some environmental factors such as the crowd in the museum, the accessibility of the item and the fatigue of the visitor. -The grasshopper denotes a visitor who will see only certain artworks, jumping from one to the other. Then, to encourage such a person to visit more items, the recommendation can be to visit items having a content similar to items already visited. -The butterfly denotes a visitor wanting to discover some and not all artworks, without having any exact preferences. Then, the recommendation is open and can be based on surprise (items which are very different one from the other). -The fish denotes a visitor who does not feel that much interested in the artworks and stays most of the time in the center of the rooms without any precise objective. Then the recommendation can be to visit the most famous items in the museum which are the closer to the current visitor location, for encouraging the visitor to continue the visit and gain more interest.

Indeed, a visitor can change his/her style during a visit and other elements may be of importance, e.g. crowd or fatigue of the visitor.

The Workflow for Analyzing the Trajectories

In the following, one objective is to map specific subsequences included in the visitor trajectories to each visiting style for characterizing more precisely the style and then making smarter recommendations. To identify the behavior of each visitor, we propose the following workflow:

1. Cluster the visitor trajectories and attach a label for each visitor (Sect. 5). 2. Create two concept lattices using MFCS and MRGS over the whole dataset (Sect. 6.1). 3. From the two lattices, find jumping emerging patterns (JEPs) for each label (Sect. 7.2). 4. Based on their JEPs, these labels are then mapped into four visiting styles that has been explained in Sect. 3.2.

The Clustering of Trajectories

In this first experiment, we reuse the sim ACS similarity measure for clustering the visitor trajectories. The idea is to check whether it is possible to distinguish the four visiting styles introduced in Section 3.2. We applied hierarchical clustering 1 based on sim ACS to build a distance matrix between individuals. From the resulting dendrogram, we retained 5 clusters denoted by "A", "B", "C", "D", and "E". Four of them are expected to match the four visiting patterns, namely ant, butterfly, fish, and grasshopper. The last cluster will gather all non-classified trajectories. These five clusters have various sizes. Cluster "A", "B", "C", "D", and "E" have 11, 11, 59, 102, and 33 visitors respectively. Actually, it is not easy to directly match the five clusters to corresponding visiting styles. For doing so, we will analyze the subsequences that can be attached to each cluster of trajectories. The benefit of the clustering is actually to provide a label among "A", "B", "C", "D", and "E" to the visitors. Thanks to these labels, we can perform a search for the so-called "jumping emerging patterns" and attach a characterization to the clusters based on the mined subsequences. [START_REF] Véron | Ethnographie de l'exposition[END_REF] The Mining of Trajectories Considered as Sequences 6.1 Mining Subsequences with MFCS and MRGS Below, we explain the application of the MFCS and MRGS algorithms to the museum dataset and the building of an associated concept lattice. Moreover, as will be discussed in the next section, the jumping sequential patterns which are mined will help us to characterize the visitor trajectories.

In MFCS and MRGS, pattern structures are used for mining sequences. The similarity operator ( ) between any two sets of sequences is defined as the set of closed common subsequences (SCCS) in the two input sequences. Then, given two sequences, say S 1 = 401,502,503 and S 2 = 401,503,502 , the similarity between these descriptions is: In parallel, the default similarity operator of MRGS can be modified to accommodate our needs, such that non-contiguous common subsequences can be mined: Then, based either on MFCS or MRGS, a concept has an extent including a set of trajectories and an intent including a set of common subsequences. Again, it should be noticed that, based on whether a subsequence is contiguous or not, the resulting concept lattices are different.

For example, the concepts corresponding to Table 3 are shown in Table 4. Notice that both algorithms obtain a concept whose extent is V 2 , V 3 , V 4 , albeit with different intent. Based on MRGS, the common subsequence of V 2 , V 3 , V 4 is 1, 402 , while according to MFCS, their common subsequences are 1 and 402 . This is because items 1 and 402 are not contiguous in V 3 and V 4 .

Jumping Emerging Patterns

FCA is a non supervised classification process that can be turned into a supervised process thanks to the adding of a target attribute in the context, generally corresponding to a target class. Then the idea is to search for the so-called "Jumping Emerging Patterns" (JEPs) [START_REF] Dong | Efficient mining of emerging patterns: Discovering trends and differences[END_REF]. We have already applied this approach in [START_REF] Asses | A Hybrid Classification Approach based on FCA and Emerging Patterns -An application for the classification of biological inhibitors[END_REF] for analyzing and characterizing clusters of biological inhibitors.

Here we adapt the same idea for characterizing this time the clusters of visitors discovered with the similarity measure sim ACS . More precisely, five clusters are discovered by classifying visitor trajectories with sim ACS . These same trajectories are then considered as sequences composed of subsequences. Then a set of characteristic subsequences is extracted and these subsequences are used as "attributes" in a formal context where objects are visitor trajectories. The resulting formal context is completed with an extra attribute corresponding to the "cluster information", i.e. the cluster in which the trajectory is classified according to sim ACS . A concept lattice can then be built from this completed context.

More interestingly, the cluster information is used for characterizing the concepts whose extents include trajectories of a single cluster. The intents -made of subsequences -of these particular concepts are JEPs, and as such they can be used to characterize the corresponding clusters. For example, if the extent of the concept ({V 103 , V 165 , V 188 }, { 4 , 1 , 306 , 701,707 }) includes visitors from cluster B only, then its intent is JEPs for that cluster.

Discussion

About Interesting Subsequences

The first part of Table 5 shows some interesting contiguous subsequences from 4677 concepts discovered by MFCS. Thirty-three persons are visiting three items contiguously in category 1 of items located near the entrance. This is interesting to be noticed, as visitors are likely to spend more time in rooms located near the entrance, because they are arriving, they have high interest, and they are not tired. Then items of importance could be placed near the entrance for getting sufficient interest from visitors.

Thirteen people visit an item in category 7 -this category corresponds to items in the room of "Ancient Ship" which is one of the most famous items in this museum -right after an item in category 1. This is a characteristic of grasshopper, because 1 and 7 are separated by many other categories. These visitors have a specific interest for the "Ancient Ship" in the museum, since they skip all the items located between entrance and "Ancient Ship" (both categories can be considered as "far" from each others).

From 8019 concepts obtained by MRGS, some subsequences are presented in the second part of Table 5. The subsequence 1,1 has a support of 69 with MFCS, and it has quite a similar support (66) with MRGS. Then we can draw the same conclusion, meaning that when a person visits two items in category 1, it is likely in continuation (to be compared with the preceding subsequence 1,1,1 ). Now, more interestingly, there are 38 persons visiting an item in category 3 after category 1, while much less persons [START_REF] Yan | CloSpan: Mining: Closed sequential patterns in large datasets[END_REF] are doing the opposite. A similar conclusion can also be drawn with pairs 4,7 (31) and 7,4 [START_REF] Gomariz | ClaSP: an efficient algorithm for mining frequent closed sequences[END_REF]. Based on such an observation, we can infer that visiting a museum is an "oriented activity"and that some directions are more preferred than others or "naturally followed", just as it is the case for the ordering of the rooms existing in the museum. By contrast, only a few visitors are quitting the "natural flow" and go "backward". Among these visitors, we can probably find visitors searching for more precision about preceding visited items.

Cluster Characterization

Now we are interested in characterizing the five clusters that were introduced in the previous section. For doing so, JEPs are searched in the two concept lattices obtained with MFCS and MRGS algorithms. Some of these concepts are listed in Table 6 and Table 7.

First, from both MFCS and MRGS, we cannot find any satisfying concept for JEP of cluster "E". This is because among all the concepts whose extent is exclusively from cluster "E", none of them has more than one visitor. If we consider the dataset, among 33 members of cluster "E", 32 of them visit less than 2 items during their whole visit. We can assume that they are visitors that are not really interested in visiting the museum. Therefore, we can quote safely label this cluster as fish.

Cluster "D" is more easily distinguishable. Based on subsequences of concept FD2-FD4, many visitors in this class skip some items. Also, in concept RD1 and RD2, some of them visit other items after item 701. This is not a natural direction, because items in category 7 are located farther from the entrance than items in category 4 or 5. We can interpret the visitors of this cluster as grasshopper, since they "jump" from one item to another.

Clusters "A", "B", and "C" are relatively similar to each other. The visitors associated to these clusters follow an ant behavior: a natural flow (based on RA1-RC1) and no "jump" (based on FA1-FC2). However, in FC3, three visitors visit 101, then 102, then back again to 101, indicating rather a butterfly behavior.

Conclusion

In this article, we have presented our experiments in mining visitor trajectories that are modeled as sequences of items. We incorporated a classification of museum items and built a concept lattice using pattern structures. We applied two sequence miners based on FCA to the visitor trajectories, namely MFCS and MRGS, to discover interesting contiguous and general subsequences.

Our result highlight some interesting patterns that may define visitor behaviors. This can help museum researchers to analyze and evaluate the placement of items and the visiting styles. Moreover, we have also studied the possibility of clustering the visitors based on a concept lattice. These clusters can be analyzed to build a recommendation system for future visitors, but we did not yet study this aspect until now.

In this paper, we only included in the sequences partial information about the museum. More interesting results can be obtained if other elements are taken into account, such as more general knowledge about history and geography, and duration and time of the visit. . . Furthermore, the selection of interesting concepts can be also guided by computing the stability of the concepts [START_REF] Kuznetsov | Concept stability for constructing taxonomies of web-site users[END_REF]. Finally, from a more dynamic point of view, ongoing information such as comments and state of the visitor during the visit could be also considered for analysis and in-line recommendation.

δ(S 1

 1 ) δ(S 2 ) = { 401,502,503 } { 401,503,502 } = { 401,502 , 401,503 } In the dataset, the items are grouped into categories and the SCCS calculation is performed, checking whether two items belong to the same category. Using the MFCS algorithm [3] it becomes: δ(S 1 ) δ(S 2 ) = { 401,502,503 } { 401,503,502 } = { 502 , 503 , 401,5,5 } It should be noticed that MFCS mines contiguous subsequences, i.e. in Definition 2, i k = i k-1 + 1 for all k ∈ {2, 3, . . . , m}.

δ(S 1 )

 1 δ(S 2 ) = { 401,502,503 } { 401,503,502 } = { 401,502 , 401,503 , 401,5,5 }

Table 1 :

 1 An example of one visitor trajectory

	Start	Finish	Item
	12:55:39 12:58:05 Crafts and Arts
	12:58:06 12:58:22 Religion and Cult
	12:58:22 12:58:27 Building Methods and Facilities
	12:58:29 13:05:09 Wooden Tools

Table 2 :

 2 Grouping of museum items

	Category Items and their ID
	1	Entrance Reuben Hecht (101), Symbols Jewish Menorah (102),
		Persian Cult (103), Jerusalem Photo (104)
	• • •	• • •
	8	Upper Floor Entrance (801), Coins (802), Seven Species (803),
		Oil Lamps (804), Weights (805), Temple Mount (806),
		Jerusalem (807), Greece Egypt (808), Cyprus (809), Gems (810)

Table 3 :

 3 Examples of visitor trajectories

	Visitor Trajectory
	V1	101, 101, 401, 704
	V2	102, 402, 808, 206, 808
	V3	302, 102, 201, 302, 705, 402, 802
	V4	104, 704, 602, 302, 402, 103

Table 4 :

 4 The concepts that are computed by of MFCS and MRGS from four visitors in Table3

	Extent	Intent (MFCS)	Intent (MRGS)
	V1	101,101,401,704
	V2	102,402,808,206,808
	V3	302,102,201,302,705,402,802
	V4	104,704,602,302,402,103
	V1,2	1,4	not present
	V1,4	1 , 4 , 704	1,1 , 1,4 , 1,704
	V2,3	2 , 102 , 402,8

Table 5 :

 5 Some interesting subsequences mined by MFCS (left) and MRGS (right)

			Subsequence Support
	Subsequence Support	1,3	38
	1,1,1	33	3,1	9
	1,7	13	4,7	31
	1,1	66	7,4	11
			1,1	69

Table 6 :

 6 Interesting concepts discovered by the MFCS algorithm

	Concept ID Extent	Intent	Support Cluster
	FA1	{V70, V107, V121, V133, V201, V202} { 1,1,402 , 103 , 2 }	6	A
	FA2	{V70, V93, V107, V121}	{ 402 , 103,104 }	4	A
	FB1	{V103, V165, V188}	{ 4 , 1 , 306 , 701,707 } 3	B
	FC1	{V4, V8, V28, V32, V84, V152}	{ 102 , 101,1,101 }	6	C
	FC2	{V53, V152, V169, V189, V190, V203} { 7 , 102,4 }	6	C
	FC3	{V4, V8, V32}	{ 101,102,101 }	3	C
	FD1	{V54, V105, V139, V168}	{ 202,4 }	4	D
	FD2	{V139, V168}	{ 202,405,701 }	2	D
	FD3	{V46, V47}	{ 101,602 }	2	D
	FD4	{V89, V163}	{ 602,203 }	2	D

Table 7 :

 7 Interesting concepts discovered by the MRGS algorithm

	Concept ID Extent	Intent	Support Cluster
	RA1	{V70, V107, V121, V133, { 1,1,402,2 , 1,1,4 ,	6	A
		V201, V202}	103,402,2 , 103,4 }
	RB1	{V142, V183, V192}	{ 102,1,1,1,1 , 102,103,1,1 ,	3	B
			1,1,1,1,1 , 1,103,1,1 }
	RC1	{V4, V8, V28, V84, V152} { 1,1,1,101 , 1,101,1,101 ,	5	C
			1,1,1,1 , 1,101,1,1 ,
			101,1,1,1 , 101,101,1,1 ,
			101,101,101 , 102,101 , 102,1 }
	RD1	{V71, V79}	{ 701,504 }	2	D
	RD2	{V97, V98}	{ 701,406 }	2	D

We used the hclust method from the R software[START_REF] Core | R: A Language and Environment for Statistical Computing[END_REF].


Mikael Escobar-Bach

Yuri Goegebeur

Armelle Guillou

Bias correction in conditional multivariate extremes

Keywords: Bias correction, conditional stable tail dependence function, stochastic convergence

come

Introduction

Most of the practical problems involving extreme events are inherently multivariate. Consequently, being able to estimate the extremal dependence between random variables is useful. To this aim, we can either use some extremal coefficients, that give a representative picture of the full dependency structure (see, e.g., [START_REF] Ledford | Modelling dependence within joint tail regions[END_REF], or functions, such as the spectral distribution function or the stable tail dependence function, that provide a full characterization of the extreme dependence between variables. We refer to [START_REF] Beirlant | Statistics of Extremes -Theory and Applications[END_REF] and de [START_REF] De Haan | Extreme value theory -An introduction[END_REF], and the references therein, for more details. In this paper, we will focus on the stable tail dependence function, which can be defined as follows.

For any arbitrary dimension d, let pY p1q , . . . , Y pdq q be a random vector with continuous marginal distribution functions F 1 , . . . , F d . The stable tail dependence function is defined for each y i P R `, i " 1, . . . , d, as lim tÑ8 tP ´1 ´F1 pY p1q q ď t ´1y 1 or . . . or 1 ´Fd pY pdq q ď t ´1y d ¯" Lpy 1 , . . . , y d q,

(1) provided that this limit exists. We refer to [START_REF] Huang | Statistics of bivariate extremes[END_REF], and de [START_REF] De Haan | Extreme value theory -An introduction[END_REF] for more details.

Several estimators for L have been proposed in the literature, see, e.g., [START_REF] Huang | Statistics of bivariate extremes[END_REF], [START_REF] Drees | Best attainable rates of convergence for estimators of the stable tail dependence function[END_REF], [START_REF] Fils-Villetard | Projection estimators of Pickands dependence functions[END_REF], [START_REF] Bücher | When uniform weak convergence fails: empirical processes for dependence functions and residuals via epi-and hypographs[END_REF], but as usual in the extreme value framework, the classical estimators are affected by bias, which often complicates their practical application. To solve this issue, [START_REF] Fougères | Bias correction in multivariate extremes[END_REF] and [START_REF] Beirlant | Bias-corrected estimation of stable tail dependence function[END_REF] have introduced bias-corrected estimators and they have established the main properties of their estimators as stochastic processes.

Taking care of the bias is important, but in practical applications, we are also often faced with the presence of covariates in addition to the random vector pY p1q , . . . , Y pdq q. It is thus important to be able to estimate the stable tail dependence function when random covariates X are present, i.e., to consider the regression situation with a multivariate response. In that case, we want to describe the extremal dependence between the variables pY p1q , . . . , Y pdq q given some observed value x for the covariate X P R p . Thus, the notion of conditional stable tail dependence function Lp¨|xq can be introduced and the classical framework (1) can be extended into lim tÑ8 tP ´1 ´F1 pY p1q |Xq ď t ´1y 1 or . . . or 1 ´Fd pY pdq |Xq ď t ´1y d |X " x ¯" Lpy 1 , . . . , y d |xq,

where F j p¨|xq, j " 1, . . . , d, denote the continuous conditional distribution function of Y pjq given X " x. To the best of our knowledge, the estimation of the conditional stable tail dependence function has only been studied very recently by Escobar-Bach et al. (2018b), where a local estimator was proposed and its weak convergence as a stochastic process was established. In related work, [START_REF] Gardes | Nonparametric estimation of the conditional tail copula[END_REF] introduced an estimator for the conditional tail copula and studied its finite dimensional convergence. However, being in the regression context, of course does not solve the bias problem of the estimator of Lp¨|xq. Thus, combining bias-correction and regression will be the subject of this paper. As far as we know, this topic is completely new in the literature.

The remainder of the paper is organized as follows. In Section 2, we introduce our bias-corrected estimator of the conditional stable tail dependence function and we establish its weak convergence as a stochastic process, the covariate being fixed. Then in Section 3, we illustrate the performance of this estimator on a small simulation study where we compare it with two alternatives, that are not asymptotically unbiased. Section 4 is devoted to a data analysis of air pollution measurements. All the proofs are postponed to Section 5.

Estimators and convergence results

Denote pY, Xq :" pY p1q , . . . , Y pdq , Xq, a random vector satisfying (2), and let pY 1 , X 1 q, . . . , pY n , X n q, be independent copies of pY, Xq, where X has density function f . We introduce a local estimator for L, based on an empirical version of the left-hand side of (2), for large values of t. As is usual in the extreme value context, we consider an intermediate sequence k " k n , i.e., k Ñ 8 as n Ñ 8 with k{n Ñ 0. Since the margins F j p¨|xq appearing in (2) are unknown in practice, we have to replace them by estimators such as the empirical kernel estimator p F n,j py|xq :"

ř n i"1 K c px ´Xi q1l tY pjq i ďyu ř n i"1 K c px ´Xi q , j " 1, . . . , d,
where K c p¨q :" Kp¨{cq{c p with K a density function on R p , and c :" c n is a positive non-random sequence satisfying c n Ñ 0 as n Ñ 8. Denote with y :" py 1 , . . . , y d q a vector of the positive quadrant

R d `. According to Escobar-Bach et al. (2018b) p L k py|xq :" 1 k ř n i"1 K h px ´Xi q 1l ! 1´p F n,1 pY p1q i |X i qď k n y 1 or ... or 1´p F n,d pY pdq i |X i qď k n y d ) 1 n ř n i"1 K h px ´Xi q
with h :" h n a positive non-random sequence satisfying h n Ñ 0 as n Ñ 8, is an estimator of the conditional stable tail dependence function Lpy|xq. Note that in p F n,j py|xq and p L k py|xq the same kernel function K has been used, but they can of course be taken different. As in Escobar-Bach et al. (2018b), the bandwidths for p F n,j and p L k are though different.

The aim of the paper is to propose an asymptotically unbiased estimator for Lp¨|xq. To the best of our knowledge this topic has not been considered previously in the literature in the regression context, on the contrary to the classical framework without covariates where we can mention the contributions of [START_REF] Fougères | Bias correction in multivariate extremes[END_REF] and [START_REF] Beirlant | Bias-corrected estimation of stable tail dependence function[END_REF].

The main results of the paper will be derived as stochastic weak convergence results for processes in y P rε, T s d , for any ε ą 0 and T ą ε, but with the covariate argument fixed, meaning that we will focus our study only around one reference position x 0 P IntpS X q, the interior of the support S X of f , assumed to be non-empty. To this aim, we need to introduce some conditions mentioned below and well-known in the extreme value framework. Let }.} be some norm on R p , and denote by B x pτ q the closed ball with respect to }.}, centered at x and radius τ ą 0. The event A t,y is defined for any t ě 0 and y P R d `as

A t,y :" ! 1 ´F1 pY p1q |X q ď t ´1y 1 or . . . or 1 ´Fd pY pdq |X q ď t ´1y d

) .

First order condition: The limit in (2) exists for all x P S X and y P R d `, and the convergence is uniform on r0, T s d ˆBx 0 pτ q for any T ą 0 and a τ ą 0.

Second order condition: For any x P S X there exist a positive function αp¨|xq such that αpt|xq Ñ 0 as t Ñ 8 and a non null function M p¨|xq such that for all y P R d lim tÑ8 1 αpt|xq ttP pA t,y |X " x q ´Lpy|xqu " M py|xq, uniformly on r0, T s d ˆBx 0 pτ q for any T ą 0 and a τ ą 0.

Third order condition: For any x P S X there exist a positive function βp¨|xq such that βpt|xq Ñ 0 as t Ñ 8 and a non null function N p¨|xq such that for all y P R d lim tÑ8

1 βpt|xq " tP pA t,y |X " x q ´Lpy|xq αpt|xq ´M py|xq

The latter assumption is common, and used already in, e.g., [START_REF] Giné | Rates of strong uniform consistency for multivariate kernel density estimators[END_REF] and Escobar-Bach et al. (2018a, 2018b), and allows to measure the discrepancy between the conditional distribution function F j p¨|xq and its empirical kernel version p F n,j p¨|xq.

2.1 Asymptotic result for p L k p¨|x 0 q under a third order condition Escobar-Bach et al. (2018b) have established the weak convergence of p L k py|x 0 q as a stochastic process in y P r0, T s d and for a fixed covariate position x 0 P R p , under the second order condition. In order to construct an asymptotically unbiased estimator for Lp¨|x 0 q, the third order condition is required and thus we need to know if under this new condition, a similar convergence result can be stated.

Theorem 2.1 Assume the third order condition, px, yq Ñ N py|xq continuous on B x 0 pτ q r0, T s d , with B x 0 pτ q Ă S X , and that there exists b ą 0 with f pxq ě b, @x P S X Ă R p and f bounded. Under pF m q, pDq, pLq, pAq, pBq, pMq, pKq, and assuming that there exists an ε ą 0 such that for n sufficiently large inf xPS X λptu P B 0 p1q : x ´cu P S X uq ą ε, where λ denotes the Lebesgue measure, consider sequences k Ñ 8, h Ñ 0 and c Ñ 0 as n Ñ 8 such that k{n Ñ 0 with ? kh p h minpη f ,η L ,ηαq ÝÑ 0, ? kh p αpn{k|x 0 q h minpη M ,η β q ÝÑ 0, ? kh p αpn{k|x 0 q ÝÑ 8, ?

kh p αpn{k|x 0 q βpn{k|x 0 q ÝÑ µ 1 px 0 q P R `, and for some q ą 1 and 0 ă η ă minpη F 1 , ..., η

F d q n c h p k max ˜c | log c| q nc p , c η ¸ÝÑ 0. ( 3
)
Then the process

! ? kh p ´p L k py|x 0 q ´Lpy|x 0 q ´α ´n k ˇˇx 0 ¯M py|x 0 q ´α ´n k ˇˇx 0 ¯β ´n k ˇˇx 0 ¯N py|x 0 q ¯, y P r0, T s d )
weakly converges in Dpr0, T s d q towards a tight centered Gaussian process tBpyq, y P r0, T s d u, for any T ą 0, with covariance structure given by Cov `Bpyq, Bpy 1 q ˘" }K} 2 2 f px 0 q `Lpy|x 0 q `Lpy 1 |x 0 q ´Lpy _ y 1 |x 0 q ˘, where y, y 1 P r0, T s d and }K} 2 :" b ş S K K 2 puqdu.

Smoothed estimator for Lp¨|x 0 q

Inspired by the homogeneity of Lp¨|x 0 q, consider now the rescaled statistic p L k,a py|x 0 q :" 1 a p L k pay|x 0 q for a positive scale parameter a. Our uncorrected (in terms of bias) estimator for Lp¨|x 0 q will be the following weighted version of the rescaled statistic, defined for any r ą 1 and ξ ą 0 as

q L k py|x 0 q :" ˜şr 1 p L ξ k,a py|x 0 qda r ´1 ¸1{ξ .
The weak convergence of this new estimator as a stochastic process is established in the following theorem.

Theorem 2.2 Under the assumptions of Theorem 2.1 together with ? kh p α 2 pn{k|x 0 q Ñ µ 2 px 0 q P R `, for any r ą 1 and ξ ą 0, we have

? kh p ! q L k py|x 0 q ´Lpy|x 0 q ´α ´n k ˇˇx 0 ¯M py|x 0 qcpr; ρq ´α ´n k ˇˇx 0 ¯β ´n k ˇˇx 0 ¯N py|x 0 qcpr; ρ `ρ1 q ´α2 pn{k|x 0 q 2 M 2 py|x 0 q
Lpy|x 0 q dpr, ξ; ρq

) d ÝÑ 1 r ´1 ż r 1 Bpayq a da,
in Dprε, T s d q, for every ε ą 0 and T ą ε, where B is defined in Theorem 2.1 and cpr; ρq :" r 1´ρ ´1 pr ´1qp1 ´ρq , dpr, ξ; ρq :" rcpr; 2ρq ´c2 pr; ρqspξ ´1q.

Based on this result, in order to construct an asymptotically unbiased estimator for Lp¨|x 0 q, we need now to estimate ρ and α k py|x 0 q :" αpn{k|x 0 qM py|x 0 q. This is the aim of the next section.

2.3 Estimation of ρ and αpn{k|x 0 qM py|x 0 q

Let pξ 1 , ξ 2 , ξ 3 , ξ 4 q P R 4 `, r 1 " r 2 ą 1 and s ą 0. We propose to estimate ρ by

q ρ k :" 1 ´1 log s log ¨ˆş r 1 1 p L ξ 1 k,a psy|x 0 qda r 1 ´1 ˙1{ξ 1 ´ˆş r 2 1 p L ξ 2 k,a psy|x 0 qda r 2 ´1 ˙1{ξ 2 ˆşr 1 1 p L ξ 3 k,a py|x 0 qda r 1 ´1 ˙1{ξ 3 ´ˆş r 2 1 p L ξ 4 k,a py|x 0 qda r 2 ´1 ˙1{ξ 4 ‹ ‹ ‹ ' . ( 4
)
Theorem 2.3 Under the assumptions of Theorem 2.1, and additionally assuming that M never vanishes except on the axes and that ? kh p α 2 pn{k|x 0 q Ñ µ 2 px 0 q P R `, for any pξ 1 , ξ 2 , ξ 3 , ξ 4 q P R 4 `, r 1 " r 2 ą 1 and s ą 0, we have

? kh p α ´n k ˇˇx 0 ¯"q ρ k ´ρ `αpn{k|x 0 q 2 log s M py|x 0 q Lpy|x 0 q
" s ´ρ dpr 1 , ξ 1 ; ρq ´dpr 2 , ξ 2 ; ρq cpr 1 ; ρq ´cpr 2 ; ρq ´dpr 1 , ξ 3 ; ρq ´dpr 2 , ξ 4 ; ρq cpr 1 ; ρq ´cpr 2 ; ρq  `β ´n k ˇˇx 0 ¯N py|x 0 q M py|x 0 q s ´ρ1 ´1 log s cpr 1 ; ρ `ρ1 q ´cpr 2 ; ρ `ρ1 q cpr 1 ; ρq ´cpr 2 ; ρq

+ d ÝÑ ´sρ´1 log s ! 1 r 1 ´1 ş r 1 1 Bpasyq a da ´1 r 2 ´1 ş r 2 1 Bpasyq a da ) ´1 log s ! 1 r 1 ´1 ş r 1 1 Bpayq a da ´1 r 2 ´1 ş r 2 1 Bpayq a da
) M py|x 0 q rcpr 1 ; ρq ´cpr 2 ; ρqs ,

in Dprε, T s d q, for every ε ą 0 and T ą ε, where B is defined in Theorem 2.1.

Let pξ 5 , ξ 6 q P R 2 `and r 3 " r 4 ą 1. To estimate α k py|x 0 q, we propose q α k py|x 0 q :"

ˆşr 3 1 p L ξ 5 k,a py|x 0 qda r 3 ´1 ˙1{ξ 5 ´ˆş r 4 1 p L ξ 6 k,a py|x 0 qda r 4 ´1 ˙1{ξ 6
cpr 3 ; q ρ k q ´cpr 4 ; q ρ k q .

(5)

In the sequel, we denote by c 1 pr; ρq the derivative of cpr; ρq with respect to ρ.

Theorem 2.4 Under the assumptions of Theorem 2.3, we have ¯N py|x 0 q M py|x 0 q 1 cpr 3 ; ρq ´cpr 4 ; ρq ˆ˜cpr 3 ; ρ `ρ1 q ´cpr 4 ; ρ `ρ1 q `rc 1 pr 3 ; ρq ´c1 pr 4 ; ρqsrcpr 1 ; ρ `ρ1 q ´cpr 2 ; ρ `ρ1 qs cpr 1 ; ρq ´cpr 2 ; ρq

? kh p α ´n k ˇˇx 0 ¯" q α k py|x 0 q αpn{k|x 0 qM py|x 0 q ´1 ´α ´n k ˇˇx 0 ¯M py|x 0 q Lpy|x 0 q 1 2rcpr 3 ;
s ρ 1 ´1 log s ¸+ d ÝÑ 1 cpr 3 ; ρq ´cpr 4 ; ρq 1 M py|x 0 q " 1 r 3 ´1 ż r 3 1 Bpayq a da ´1 r 4 ´1 ż r 4 1 Bpayq a da
´c1 pr 4 ; ρq ´c1 pr 3 ; ρq cpr 1 ; ρq ´cpr 2 ; ρq

" s ρ´1 log s ˆ1 r 1 ´1 ż r 1 1 Bpasyq a da ´1 r 2 ´1 ż r 2 1 Bpasyq a da 1 log s ˆ1 r 1 ´1 ż r 1 1 Bpayq a da ´1 r 2 ´1 ż r 2 1 Bpayq a da ˙*
in Dprε, T s d q, for every ε ą 0 and T ą ε, where B is defined in Theorem 2.1.

Bias correction of q

L k py|x 0 q

Now we have all the ingredients to construct an asymptotically unbiased estimator for Lp¨|x 0 q by removing from q L k py|x 0 q the bias term where αpn{k|x 0 qM py|x 0 q together with the second order rate parameter ρ have been estimated externally, using the same intermediate sequence k " k n , which is such that k " opkq. This idea has been originally proposed by Gomes and co-authors (see, e.g., [START_REF] Gomes | Tail index estimation for heavy-tailed models: accommodation of bias in weighted log-excesses[END_REF][START_REF] Caeiro | Reduced-bias tail index estimators under a third order framework[END_REF] in the univariate framework and has the advantage that the variance of the bias-corrected estimator and the uncorrected one is the same. Thus, we propose the following bias-corrected estimator for Lp¨|x 0 q L k,k py|x 0 q :" q L k py|x 0 q ´q α k py|x 0 qcpr; q

ρ k q ˆk k ˙q ρ k . ( 6
)
Theorem 2.5 Assume the third order condition, M never vanishes except on the axes, px, yq Ñ N py|xq continuous on B x 0 pτ q ˆr0, T s d , with B x 0 pτ q Ă S X , and that there exists b ą 0 with f pxq ě b, @x P S X Ă R p and f bounded. Under pF m q, pDq, pLq, pAq, pBq, pMq, pKq, and assuming that there exists an ε ą 0 such that for n sufficiently large inf xPS X λptu P B 0 p1q : x ´cu P S X uq ą ε, consider sequences k Ñ 8, h Ñ 0, c Ñ 0 as n Ñ 8 and k such that k " opkq, k{n Ñ 0, and with a kh p h minpη f ,η L ,ηαq ÝÑ 0, a kh p αpn{k|x 0 q h minpη M ,η β q ÝÑ 0, ? kh p αpn{k|x 0 q ÝÑ 8, a kh p αpn{k|x 0 q βpn{k|x 0 q ÝÑ µ 1 px 0 q P R àkh p α 2 pn{k|x 0 q ÝÑ µ 2 px 0 q P R ànd for some q ą 1 and 0 ă η ă minpη F 1 , ..., η

F d q n c h p k max ˜c | log c| q nc p , c η ¸ÝÑ 0.
Then we have

? kh p ! L k,k py|x 0 q ´Lpy|x 0 q ´α ´n k ˇˇx 0 ¯β ´n k ˇˇx 0 ¯N py|x 0 qcpr; ρ `ρ1 q ´α2 pn{k|x 0 q 2 M 2 py|x 0 q
Lpy|x 0 q dpr, ξ; ρq

) d ÝÑ 1 r ´1 ż r 1 Bpayq a da
in Dprε, T s d q, for every ε ą 0 and T ą ε, where B is defined in Theorem 2.1.

Note that this bias-corrected estimator L k,k p¨|x 0 q has the same asymptotic variance as the uncorrected estimator q L k p¨|x 0 q (see Theorem 2.2).

Simulation study

Our aim in this section is to illustrate the bias-correcting effect in the estimation of Lp¨|x 0 q. We focus on dimensions d " 2 and p " 1. We consider the two models studied in Escobar-Bach et al.

(2018b), which both satisfy our third order condition, together with Assumptions pDq, pLq, pAq, pBq, pMq and pF m q. In particular, these models are the following:

• Model 1: The bivariate Student distribution with density function

f pY p1q ,Y p2q q py 1 , y 2 q " ? 1 ´θ2 2π ˆ1 `y2 1 ´2θy 1 y 2 `y2 2 ν ˙´ν`2 2 , py 1 , y 2 q P R 2 ,
where θ is the Pearson correlation coefficient. The stable tail dependence function can be described as

Lpy 1 , y 2 |θq " y 1 F ν`1 ˜py 1 {y 2 q 1{ν ´θ ? 1 ´θ2 ? ν `1¸`y 2 F ν`1 ˜py 2 {y 1 q 1{ν ´θ ? 1 ´θ2 ? ν `1¸,
where F ν`1 is the distribution function of the univariate Student distribution with pν `1q degrees of freedom. Also

M py 1 , y 2 |θq " C 1 « y 2{ν`1 1 F ν`3 ˜py 1 {y 2 q 1{ν ´θ ? 1 ´θ2 ? ν `3¸`y 2{ν`1 2 F ν`3 ˜py 2 {y 1 q 1{ν ´θ ? 1 ´θ2 ? ν `3¸ff , N py 1 , y 2 |θq " C 2 « y 4{ν`1 1 F ν`5 ˜py 1 {y 2 q 1{ν ´θ ? 1 ´θ2 ? ν `5¸`y 4{ν`1 2 F ν`5 ˜py 2 {y 1 q 1{ν ´θ ? 1 ´θ2 ? ν `5¸ff , C 1 :" ´ν2{ν`1 π 1{ν pν `1q 2pν `2q ˜Γ `ν 2 Γ `ν`1 2 ˘¸2{ν , C 2 :" ν 4{ν`1 π 2{ν pν `1qpν `3q 8pν `4q ˜Γ `ν 2 Γ `ν`1 2 ˘¸4{ν , αpt|θq " t ´2{ν , βpt|θq " t ´2{ν .
We set θ " X, where X is uniformly distributed on r0, 1s. In the simulations, we use ν " 4, which corresponds to ρ " ρ 1 " ´1{2;

• Model 2: a particular case of the Archimax bivariate copulas introduced in Capéraà et al.

(2000) and also mentioned in [START_REF] Fougères | Bias correction in multivariate extremes[END_REF], namely:

Cpy 1 , y 2 |xq " 1 `Lpy ´1 1 ´1, y ´1 2 ´1|xq ( ´1 ,
where we use for L the asymmetric logistic stable tail dependence function defined by Lpy 1 , y 2 |xq " p1 ´t1 qy 1 `p1 ´t2 qy 2 `"pt 1 y 1 q θx `pt 2 y 2 q θx ı 1{θx , where 0 ď t 1 , t 2 ď 1, and θ x :" minp1{x, 100q, with the covariate X uniformly distributed on r0, 1s. The marginal distributions are taken to be unit Fréchet. For this model Hence ρ " ρ 1 " ´1. In the simulations, different values for the pair pt 1 , t 2 q have been tried but the results seem to be not too much influenced by them, thus we exhibit only the results in case pt 1 , t 2 q " p0.4, 0.6q which corresponds to an asymmetric tail dependence function.

M
For each model, we simulate 500 samples of size 1000, and we compare three estimators of Lp¨|x 0 q: the two uncorrected estimators, p L k p¨|x 0 q and its smoothed version q L k p¨|x 0 q, and our bias-corrected estimator L k,k p¨|x 0 q, for three positions x 0 " 0.3, 0.5 and 0.7. Concerning the kernel, we always use the bi-quadratic function Kpuq :" 15 16 p1 ´u2 q 2 1l tuPr´1,1su .

Each estimator requires the selection of some tuning parameters. This will be done as follows.

For the uncorrected estimator p L k p¨|x 0 q of Escobar-Bach et al. (2018b), we follow their approach, i.e., we use their cross-validation criterion for both bandwidth parameters c 1 and c 2 , corresponding to the marginals approximation, and for the sequence h, we use

h " minpc 1 , c 2 q | logpminpc 1 , c 2 qq| 1.1 k n ,
coming from condition (3), as described in their paper.

For the uncorrected smoothed estimator q L k p¨|x 0 q, the pair pr, ξq is selected in a data-driven way using the homogeneity of the function Lpy|x 0 q, namely, for all y and k pr ˚, ξ ˚q :" argmin pr,ξqPRˆE ÿ tPT ´q L k pty|x 0 q ´tq L k py|x 0 q ¯2 , where R :" t1.1, 1.2, . . . , 2u, E :" t1, 2, 3u and T :" t1{3, 2{3, 1, 4{3, 5{3u. The grids of values are selected after an extensive simulation study.

For the bias-corrected estimator L k,k p¨|x 0 q, also a data-driven method has been used for all the parameters involved. More precisely, L k,k p¨|x 0 q defined in ( 6) is based on the uncorrected smoothed estimator q L k p¨|x 0 q computed with pr ˚, ξ ˚q from which we remove the bias, based on estimates q α k p¨|x 0 q and q ρ k , derived according to the following algorithm:

Step 1. Let y ˚" p0.5, 0.5q, s " 0.4 and k " t0.99nu as suggested by [START_REF] Fougères | Bias correction in multivariate extremes[END_REF];

Step 2. Note that q ρ k is an estimate of ρ, and as such is independent of y. Define R :" tpr 1 , r 2 q P R 2 : r 1 ‰ r 2 u, Ξ :" tpξ 1 , ξ 2 , ξ 3 , ξ 4 q P E 4 : ξ 1 " ξ 3 , ξ 2 " ξ 4 u and denote q ρ k py ˚, r 1 , r 2 , ξ 1 , ξ 2 , ξ 3 , ξ 4 q :" q ρ k as in (4) for all pr 1 , r 2 q P R, pξ 1 , ξ 2 , ξ 3 , ξ 4 q P Ξ and y " y ˚. Then, find pr 1 , r 2 , ξ 1 , ξ 2 q the values of pq r 1 , q r 2 , q ξ 1 , q ξ 2 q P R ˆE2 minimizing the criterion

ÿ pr 1 ,r 2 ,ξ 1 ,ξ 2 qPRˆE 2 ´q ρ k ´y˚, q r 1 , q r 2 , q ξ 1 , q ξ 2 , q ξ 1 , q ξ 2 ¯´q ρ k py ˚, r 1 , r 2 , ξ 1 , ξ 2 , ξ 1 , ξ 2 q ¯2 .
The estimate q ρ k in ( 6) is finally computed as q ρ k py ˚, r 1 , r 2 , ξ 1 , ξ 2 , ξ 1 , ξ 2 q; Step 3. Let q α k p¨, r 3 , r 4 , ξ 5 , ξ 6 |x 0 q :" q α k p¨|x 0 q as defined in (5). We use the homogeneity of M p¨|x 0 q in order to select the parameters pr 3 , r 4 , ξ 5 , ξ 6 q. More precisely, q α k p¨|x 0 q in (6) is computed as q α k p¨, r 3 , r 4 , ξ 5 , ξ 5 |x 0 q where pr 3 , r 4 , ξ 5 q :" argmin pr 3 ,r 4 ,ξ 5 qPRˆE ÿ tPT ´q α k pty ˚, r 3 , r 4 , ξ 5 , ξ 5 |x 0 q ´t1´q ρ k q α k py ˚, r 3 , r 4 , ξ 5 , ξ 5 |x 0 q ¯2 .

In the latter, q ρ k is the value obtained in Step 2.

In Figure 1, we show the sample mean (left) and the empirical mean squared error (MSE, right) of p L k py|x 0 q (dotted line), q L k py|x 0 q (dashed line) and L k,k py|x 0 q (full line) as a function of k in case of Model 1 with x 0 " 0.3 and four possible values of y, corresponding to the different rows: from the top to the bottom, y " p0.2, 0.8q, p0.4, 0.6q, p0.6, 0.4q and p0.8, 0.2q, respectively. The horizontal line on the left panel represents the true value of Lpy|x 0 q. Figures 2 and 3 are constructed similarly, but for x 0 " 0.5 and 0.7, respectively, whereas Figures 4 to 6 concern Model 2 and the same values of x 0 and y. Based on these simulations, we can draw the following conclusions:

• Our estimator L k,k py|x 0 q clearly outperforms the two alternatives. In terms of bias, the sample means show very stable paths as a function of k, close to the true value. In terms of MSE, it is still competitive, almost always better than p L k py|x 0 q and q L k py|x 0 q, or otherwise at least similar, and again very stable as a function of k. Those are very nice features since in our case, the selection of k is not very crucial, while it is for p L k and q L k .

• For Model 2, the estimation is more difficult for y far away from the diagonal, whereas for Model 1, it does not depend on y. Also, the performance of our bias-corrected estimator L k,k py|x 0 q does not seem to depend on the position in the covariate space.

Application to air pollution data

In this section, we illustrate the practical applicability of our bias-corrected estimator on a dataset of air pollution measurements. We consider the data collected by the United States Environmental Protection Agency (EPA), publicly available at https:{{aqsdr1.epa.gov{aqsweb{aqstmp{airdata L k py|0.3q (dashed line), L k,k py|0.3q (full line) as a function of k for different values of y corresponding to each row: y " p0.2, 0.8q, p0.4, 0.6q, p0.6, 0.4q, p0.8, 0.2q. The horizontal line on the left panel corresponds to the true value of Lpy|0.3q. L k py|0.5q (dashed line), L k,k py|0.5q (full line) as a function of k for different values of y corresponding to each row: y " p0.2, 0.8q, p0.4, 0.6q, p0.6, 0.4q, p0.8, 0.2q. The horizontal line on the left panel corresponds to the true value of Lpy|0.5q. L k py|0.7q (dashed line), L k,k py|0.7q (full line) as a function of k for different values of y corresponding to each row: y " p0.2, 0.8q, p0.4, 0.6q, p0.6, 0.4q, p0.8, 0.2q. The horizontal line on the left panel corresponds to the true value of Lpy|0.7q. L k py|0.3q (dashed line), L k,k py|0.3q (full line) as a function of k for different values of y corresponding to each row: y " p0.2, 0.8q, p0.4, 0.6q, p0.6, 0.4q, p0.8, 0.2q. The horizontal line on the left panel corresponds to the true value of Lpy|0.3q. L k py|0.5q (dashed line), L k,k py|0.5q (full line) as a function of k for different values of y corresponding to each row: y " p0.2, 0.8q, p0.4, 0.6q, p0.6, 0.4q, p0.8, 0.2q. The horizontal line on the left panel corresponds to the true value of Lpy|0.5q. L k py|0.7q (dashed line), L k,k py|0.7q (full line) as a function of k for different values of y corresponding to each row: y " p0.2, 0.8q, p0.4, 0.6q, p0.6, 0.4q, p0.8, 0.2q. The horizontal line on the left panel corresponds to the true value of Lpy|0.7q.

{download files.html. The dataset contains daily measurements of, among others, maximum temperature, ground-level ozone, carbon monoxide and particulate matter concentrations, for the period 1999 to 2013, and this for stations spread over the U.S. Monitoring levels of these pollutants is of crucial importance, as extreme temperature and high levels of pollutants like ground-level ozone and particulate matter pose a major threat to human health. We estimate the stable tail dependence function for the variables temperature and ozone concentration, conditional on time and location, where the latter is expressed by latitude and longitude. In the estimation, the covariates are standardised to the interval r0, 1s, and the tuning parameters are selected with the algorithm described in Section 3. In order to keep the computational time requirements under control, the tuning parameters selected at steps 1. to 3. of the algorithm are computed with a random sampling of size r0.1ns where n " 127328 refers to the initial sample size. As kernel function K ˚, we use the following generalisation of the bi-quadratic kernel K :

K ˚px 1 , x 2 , x 3 q :" 3 ź i"1 Kpx i q,
where x 1 , x 2 , x 3 , refer to the covariates time, latitude and longitude, respectively, in standardised form. Note that K ˚has as support the unit ball with respect to the max-norm on R 3 .

We report here only the results at two different time points, January 15, 2007 and June 15, 2007, and for two locations, Fresno and Los Angeles (both in California). In Figure 7, we show the estimates mediant r L k pt, 1 ´t|xq, k " n{4, ¨¨¨, n{2u, with a range of k´values based on 25 equally spaced integers, where r L k is either L k,k (full line), p L k (dotted line) or q L k (dashed line), for the cities Fresno (top row) and Los Angeles (bottom row) on January 15, 2007 (first column) and June 15, 2007 (second column). For both stations, the bias-corrected estimate for the stable tail dependence function indicates a stronger extreme dependence between temperature and ozone concentration in winter than in summer. In winter the extreme dependence in Fresno is stronger than in Los Angeles. The results obtained with the uncorrected estimators p L k and q L k are typically similar to each other, and correspond more or less with the analysis reported in Escobar-Bach et al. (2018b). The estimate L k,k differs considerably from p L k and q L k for Fresno, winter and Los Angeles, summer. Note that in these cases, the bias-corrected estimate tends to be higher than the uncorrected estimates, indicating a weaker extremal dependence. This was also observed in the simulation experiment, where the bias-corrected estimator tends to be larger (and closer to the true value) than the uncorrected estimators. The observed discrepancy indicates that estimation of tail dependence between temperature and ozone concentration can suffer from bias, and therefore it is recommended to use the bias-corrected estimator in order to get a better estimate of the stable tail dependence function. since for n large enough x 0 ´hu P B x 0 pτ q. This leads to

n k P `An{k,y |X " x 0 ´hu ˘´Lpy|x 0 ´huq " α ´n k ˇˇx 0 ¯M py|x 0 ´huq `α ´n k ˇˇx 0 ¯β ´n k ˇˇx 0 ¯rN py|x 0 ´huq `op1qs `"α ´n k ˇˇx 0 ´hu ¯´α ´n k ˇˇx 0 ¯ı M py|x 0 ´huq `"α ´n k ˇˇx 0 ´hu ¯β ´n k ˇˇx 0 ´hu ¯´α ´n k ˇˇx 0 ¯β ´n k ˇˇx 0 ¯ı rN py|x 0 ´huq `op1qs " α ´n k ˇˇx 0 ¯M py|x 0 q `α ´n k ˇˇx 0 ¯β ´n k ˇˇx 0 ¯N py|x 0 q `O ´α ´n k ˇˇx 0 ¯hη M ^ηβ ¯`O ph ηα q `o ´α ´n k ˇˇx 0 ¯β ´n k ˇˇx 0 ¯¯,
where the error terms are all independent from y.

Proof of Theorem 2.2

Using Theorem 2.1, the homogeneity properties of the functions Lp¨|x 0 q, M p¨|x 0 q, N p¨|x 0 q, and the Skorohod representation (but keeping the same notation), we have

p L k,a py|x 0 q d " Lpy|x 0 q `α ´n k ˇˇx 0 ¯a´ρ M py|x 0 q `α ´n k ˇˇx 0 ¯β ´n k ˇˇx 0 ¯a´ρ´ρ 1 N py|x 0 q `1 ? kh p Bpayq a `1 a o ˆ1 ? kh p ˙,
where the o´term is almost surely and uniform in a and y. This implies that for any r ą 1 and ξ ą 0, under the assumptions of Theorem 2.2, we have by straightforward application of Taylor's theorem that

ş r 1 p L ξ k,a py|x 0 qda r ´1 d " L ξ py|x 0 q `α ´n k ˇˇx 0 ¯ξL ξ´1 py|x 0 qM py|x 0 qcpr; ρq `α ´n k ˇˇx 0 ¯β ´n k ˇˇx 0 ¯ξL ξ´1 py|x 0 qN py|x 0 qcpr; ρ `ρ1 q `α2 ´n k ˇˇx 0 ¯ξpξ ´1q 2 L ξ´2 py|x 0 qM 2 py|x 0 qcpr; 2ρq `1 ? kh p ξ r ´1 L ξ´1 py|x 0 q ż r 1 Bpayq a da `o ˆ1 ? kh p ˙.
Theorem 2.2 follows then from another application of Taylor's theorem.

Proof of Theorem 2.3

According to Theorem 2.2, using the homogeneity properties of the functions Lp¨|x 0 q, M p¨|x 0 q, N p¨|x 0 q, and the Skorohod representation, we have ˜şr 1 p L ξ k,a psy|x 0 qda r ´1 ¸1{ξ d " s Lpy|x 0 q `α ´n k ˇˇx 0 ¯s1´ρ M py|x 0 qcpr; ρq `α ´n k ˇˇx 0 ¯β ´n k ˇˇx 0 ¯s1´ρ´ρ 1 N py|x 0 qcpr; ρ `ρ1 q `α2 ´n k ˇˇx 0 ¯s1´2ρ 2 M 2 py|x 0 q Lpy|x 0 q dpr, ξ; ρq

`1 ? kh p 1 r ´1 ż r 1 Bpasyq a da `o ˆ1 ? kh p ˙.
Several Taylor series expansions allow us to achieve the proof of Theorem 2.3.

Proof of Theorem 2.4

Consider the decomposition q α k py|x 0 q " ˆşr 3 1 p L ξ 5 k,a py|x 0 qda r 3 ´1 ˙1{ξ 5 ´ˆş r 4 1 p L ξ 6 k,a py|x 0 qda r 4 ´1 ˙1{ξ 6 cpr 3 ; ρq ´cpr 4 ; ρq " 1 `rcpr 3 ; ρq ´cpr 3 ; q ρ k qs ´rcpr 4 ; ρq ´cpr 4 ; q ρ k qs cpr 3 ; q ρ k q ´cpr 4 ; q ρ k q * ": T 1 t1 `T2 u .

From Theorem 2.2

T 1 αpn{k|x 0 qM py|x 0 q d " 1

`β ´n k ˇˇx 0 ¯N py|x 0 q M py|x 0 q cpr 3 ; ρ `ρ1 q ´cpr 4 ; ρ `ρ1 q cpr 3 ; ρq ´cpr 4 ; ρq `α ´n k ˇˇx 0 ¯M py|x 0 q Lpy|x 0 q dpr 3 , ξ 5 ; ρq ´dpr 4 , ξ 6 ; ρq 2rcpr 3 ; ρq ´cpr 4 ; ρqs `1 ? kh p αpn{k|x 0 qM py|x 0 q Combining these results leads to Theorem 2.4.

Proof of Theorem 2.5

From Theorem 2.2, we have L k,k py|x 0 q d " Lpy|x 0 q `˜α ´n k ˇˇx 0 ¯M py|x 0 q ´q α k py|x 0 q ˆk k ˙q ρ k ¸cpr; ρq ´q α k py|x 0 q ˆk k ˙q ρ k `cpr; q ρ k q ´cpr; ρq ˘`α ´n k ˇˇx 0 ¯β ´n k ˇˇx 0 ¯N py|x 0 qcpr; ρ `ρ1 q `α2 pn{k|x 0 q 2 M 2 py|x 0 q Lpy|x 0 q dpr, ξ; ρq `1 ?

kh p 1 r ´1 ż r 1 Bpayq a da `o ˆ1 ? kh p ˙.
Now remark that, by the mean value theorem, for r ρ k an intermediate value between q ρ k and ρ α ´n k ˇˇx 0 ¯M py|x 0 q ´q α k py|x 0 q ˆk k ˙q ρ k " # α ´n k ˇˇx 0 ¯M py|x 0 q ´q α k py|x 0 q ˆk k ˙ρ+ ´q α k py|x 0 q ˆk k ˙r ρ k log k k `q ρ k ´ρ˘.

Using Theorems 2.3 and 2.4, we can thus deduce that α ´n k ˇˇx 0 ¯M py|x 0 q ´q α k py|x 0 q ˆk k ˙q Recall that αp.|x 0 q is regularly varying with index ρ ă 0, which means that αpy|x 0 q " y ρ α py|x 0 q where α p¨|x 0 q is a slowly varying function at infinity. Following the lines of proof of Theorem 2 in [START_REF] Beirlant | Bias-corrected estimation of stable tail dependence function[END_REF]

˙.

Consequently, since we have also by Theorem 2.3 q α k py|x 0 q ˆk k ˙q ρ k `cpr; q ρ k q ´cpr; ρq ˘" O

Figure 1 :

 1 Figure 1: Model 1: Mean (left) and MSE (right) of three estimators of Lpy|0.3q: p L k py|0.3q (dotted line), qL k py|0.3q (dashed line), L k,k py|0.3q (full line) as a function of k for different values of y corresponding to each row: y " p0.2, 0.8q, p0.4, 0.6q, p0.6, 0.4q, p0.8, 0.2q. The horizontal line on the left panel corresponds to the true value of Lpy|0.3q.

Figure 2 :

 2 Figure 2: Model 1: Mean (left) and MSE (right) of three estimators of Lpy|0.5q: p L k py|0.5q (dotted line), qL k py|0.5q (dashed line), L k,k py|0.5q (full line) as a function of k for different values of y corresponding to each row: y " p0.2, 0.8q, p0.4, 0.6q, p0.6, 0.4q, p0.8, 0.2q. The horizontal line on the left panel corresponds to the true value of Lpy|0.5q.

Figure 3 :

 3 Figure 3: Model 1: Mean (left) and MSE (right) of three estimators of Lpy|0.7q: p L k py|0.7q (dotted line), qL k py|0.7q (dashed line), L k,k py|0.7q (full line) as a function of k for different values of y corresponding to each row: y " p0.2, 0.8q, p0.4, 0.6q, p0.6, 0.4q, p0.8, 0.2q. The horizontal line on the left panel corresponds to the true value of Lpy|0.7q.

Figure 4 :

 4 Figure 4: Model 2: Mean (left) and MSE (right) of three estimators of Lpy|0.3q: p L k py|0.3q (dotted line), qL k py|0.3q (dashed line), L k,k py|0.3q (full line) as a function of k for different values of y corresponding to each row: y " p0.2, 0.8q, p0.4, 0.6q, p0.6, 0.4q, p0.8, 0.2q. The horizontal line on the left panel corresponds to the true value of Lpy|0.3q.

Figure 5 :

 5 Figure 5: Model 2: Mean (left) and MSE (right) of three estimators of Lpy|0.5q: p L k py|0.5q (dotted line), qL k py|0.5q (dashed line), L k,k py|0.5q (full line) as a function of k for different values of y corresponding to each row: y " p0.2, 0.8q, p0.4, 0.6q, p0.6, 0.4q, p0.8, 0.2q. The horizontal line on the left panel corresponds to the true value of Lpy|0.5q.

Figure 6 :

 6 Figure 6: Model 2: Mean (left) and MSE (right) of three estimators of Lpy|0.7q: p L k py|0.7q (dotted line), qL k py|0.7q (dashed line), L k,k py|0.7q (full line) as a function of k for different values of y corresponding to each row: y " p0.2, 0.8q, p0.4, 0.6q, p0.6, 0.4q, p0.8, 0.2q. The horizontal line on the left panel corresponds to the true value of Lpy|0.7q.

Figure 7 :

 7 Figure 7: Air pollution data : Estimates of mediant r L k pt, 1 ´t|xq, k " n{4, ¨¨¨n{2u, with a range of k´values based on 25 equally spaced integers, for Fresno (top) and Los Angeles (bottom) on January 15, 2007 (first column) and June 15, 2007 (second column).

  3 ; ρq ´cpr 4 ; ρq `o ˆ1 ? kh p αpn{k|x 0 q ȧnd 4 ; ρq ´c1 pr 3 ; ρqspq ρ k ´ρq cpr 3 ; ρq ´cpr 4 ; ρq p1 `op1qq.

  py 1 , y 2 |xq " y 2 1 B 1 Lpy 1 , y 2 |xq `y2 2 B 2 Lpy 1 , y 2 |xq ´L2 py 1 , y 2 |xq, N py 1 , y 2 |xq " B 1 Lpy 1 , y 2 |xqpy 3

		1 ´2Lpy 1 , y 2 |xqy 2 1 q `B2 Lpy 1 , y 2 |xqpy 3 2 ´2Lpy 1 , y 2 |xqy 2 2 q
	`1 2	B 11 Lpy 1 , y 2 |xqy 4 1 `1 2	B 22 Lpy 1 , y 2 |xqy 4 2 `B12 Lpy 1 , y 2 |xqy 2 1 y 2 2	`L3 py 1 , y 2 |xq,
	αpt|xq " t ´1,
	βpt|xq " t ´1.

  , this implies that α ´n k ˇˇx 0 ¯M py|x 0 q ´q α k py|x 0 q

	ˆk k	˙q ρ k d "	ˆk k	˙ρ α	ˆn k	ˇˇx 0	˙β ˆn k	ˇˇx 0	˙$ & %	αpn{k|x0q αpn{k|x0q βpn{k|x 0 q ´1	, . -	M py|x 0 q	kh p `o ˆ1 ?	"
			˜ˆk
			O	k	˙ρ α	ˆn k	ˇˇx 0	˙β ˆn k	kh p ˇˇx 0 ˙¸`o ˆ1 ?	"
			o ˆ1 ? kh p

Acknowledgement

This work was supported by a research grant (VKR023480) from VILLUM FONDEN. Computation/simulation for the work described in this paper was supported by the DeIC National HPC Centre, SDU.

Proofs

Proof of Theorem 2.1

We follow the lines of proof of Theorems 2.1 and 2.3 in Escobar-Bach et al. (2018b). The only difference lies in the fact that, under the third order condition, we have


Sequence Mining within Formal Concept Analysis for Analyzing Visitor Trajectories

Nyoman Juniarta, Miguel Couceiro, Amedeo Napoli, Chedy Raïssi Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France Email: firstname.lastname@loria.fr

Abstract-This paper presents our work about mining visitor trajectories, within the framework of CrossCult European Project about cultural heritage. We present a theoretical and practical research work about the characterization of visitor trajectories and the mining of these trajectories as sequences. The mining process is based on two approaches, namely the mining of subsequences without any constraint and the mining of frequent contiguous subsequences. Both approaches are defined within Formal Concept Analysis and its extension pattern structures. In parallel, a similarity measure allows us to build a hierarchical classification which is used for interpretation and characterization of the trajectories w.r.t. four well-known visiting styles in museum studies.

I. INTRODUCTION

This paper is related to the CrossCult European Project about cultural heritage (http://www.crosscult.eu/). The general idea of CrossCult is to support the emergence of a European cultural heritage by allowing visitors in different locations (e.g. museum, city, archaeological site) to consider their visit at a European level by using adapted computer-based devices.

In this project, we are mainly interested in the analysis of visitor trajectories and recommendation. The trajectory of a visitor in a specific location is considered as a multidimensional sequence depending on a number of variables, such as space (e.g. paths, rooms, environment), time (e.g. hour, day, season, news), history and geography (e.g. town, region, country. . . ). Moreover, additional domain knowledge and general knowledge bases such as DBpedia, Freebase, or YAGO can be reused to draw inferences and improve the quality of both analysis and recommendation.

Here, we have two main objectives, (i) the mining of visitor trajectories based on sequence mining, and (ii) the characterization of a trajectory in terms of the subsequences which are mined. We assume that the subsequences can be related to the visiting styles, the visit content, and the environment. Thus subsequences can be used for analyzing the trajectory of a visitor and for making recommendations all along the visit. Moreover, the occurrences of some subsequences at a given moment within a trajectory can witness a change of behavior -which in turn triggers a change in the recommendations.

In the present paper, we discuss theoretical and practical work about the definition of visitor trajectories and the mining of these trajectories as sequences. The mining process is based on two approaches about sequence mining in Formal Concept Analysis (FCA [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]): MRGS for "Mining Rare General Subsequences" [START_REF] Codocedo | A proposition for sequence mining using pattern structures[END_REF] and MFCS for "Mining Frequent Contiguous Subsequences" [START_REF] Buzmakov | On mining complex sequential data by means of FCA and pattern structures[END_REF]. The first approach mines rare subsequences in a general way, i.e. gaps may appear in the subsequences, while the second approach searches for frequent subsequences without any gap (a kind of substrings). We also reuse the similarity measure sim ACS developed for analyzing the trajectories of patients between hospitals [START_REF] Egho | A contribution to the discovery of multidimensional patterns in healthcare trajectories[END_REF], [START_REF] Egho | On measuring similarity for sequences of itemsets[END_REF]. If the original paper about MRGS [START_REF] Codocedo | A proposition for sequence mining using pattern structures[END_REF] was interested in rare subsequences, this is no more the case here and we work on frequent subsequences as well. This similarity measure allows us to build a hierarchical classification that will play a role of "reference classification". For analyzing and interpreting the trajectories of visitors, it is interesting to compare the outputs of MRGS and MFCS algorithms w.r.t. the clustering produced by sim ACS . Moreover, these outputs and the clustering are analyzed thanks to four theoretical visiting styles, namely "ant", "butterfly", "fish" and "grasshopper" [START_REF] Véron | Ethnographie de l'exposition[END_REF].

Several challenges are faced in this research work in the FCA framework: the mining of complex sequential data and dynamics in adapting two algorithms based on pattern structures, the analysis of the trajectories based on jumping emerging patterns and clustering. Here, data are not necessarily big but are rather complex and multidimensional, and this should be taken into account.

The paper is organized as follows. Section II recalls the basic definitions about sequence mining that are useful for understanding the present work. Then, Section III presents the characteristics of the dataset that was used as a basis for the current work. In Section V and Section VI, we present respectively the application of clustering on data enabling to build classes of visitors, and the application of two algorithms for mining interesting subsequences. Finally, an interpretation of the results and a discussion on the characterization of the visitor trajectories is given in Section VII.

II. THE MINING OF SEQUENCES

A. Basic Definitions

Pattern mining is the task of finding repeated occurrences in a dataset. For example, in a data about customer transactions, an objective can be to find a set of items that are frequently ordered in a single transaction. This specific task in pattern mining is related to sequential pattern mining. We recall below the basic definitions that we will need. Definition 1. A sequence is an ordered list s 1 s 2 . . . s m , where s i is an itemset {i 1 , . . . , i n }, and m is the size of a sequence. The length of a sequence is the total number of items, i.e.

|s i |. Therefore, the sequence {a}{d} is a subsequence of {a, b}{a, c, d} , while sequence {c}{d} is not.

One way of evaluating the quality of a subsequence is to compute the support of the subsequence. Given a user-defined threshold, the subsequence can be "frequent", i.e. the support is above the threshold. Definition 3. Let S be a database of sequences. The support of a sequence s in S is: support(s, S) = |{s i ∈ S; s s i }| There exist algorithms that can retrieve all frequent sequences [START_REF] Han | PrefixSpan: Mining sequential patterns efficiently by prefixprojected pattern growth[END_REF], [START_REF] Ayres | Sequential pattern mining using a bitmap representation[END_REF]. Beside mining frequent sequences, another complex task is finding homogeneous sequence groups (clustering). To achieve such a task, a distance or a similarity measure between two sequences has to be defined. The similarity measure sim ACS was proposed in [START_REF] Egho | On measuring similarity for sequences of itemsets[END_REF], which counts the number of all common subsequences (ACS), formulated as:

sim ACS (S i , S j ) = φ C (S i , S j ) max{φ D (S i ), φ D (S j )}
where φ C (S i , S j ) is the number of all common distinct subsequences between S i and S j , while φ D (S i ) is the number of all distinct subsequences of S i .

B. FCA and Pattern Structures

Formal concept analysis (FCA) is a mathematical framework based on lattice theory and used for classification, data analysis, and knowledge discovery [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]. From a formal context, FCA detects all formal concepts, and arranges them in a concept lattice. If an object g has an attribute m, then (g, m) ∈ I. An example of a formal context is shown in Table I. This table shows whether a visitor (V 1 -V 4 ) visits an item (102, 302, 402, or 704).

The Galois connection for a formal context (G, M, I) is defined as follows:

Definition 5. For a subset of objects A ⊆ G, A is the set of attributes that are possessed by all objects in A, i.e.:

A = {m ∈ M |∀g ∈ A, (g, m) ∈ I}, A ⊆ G
A formal concept (A, B) is a subconcept of (C, D) - denoted by (A, B) ≤ (C, D) -if A ⊆ C (or equivalently D ⊆ B).
A concept lattice can be formed using the ≤ relation which defines the order among concepts. For the context in Table I, the formal concepts and their corresponding lattice are shown in Fig. 1.

FCA is restricted to specific datasets where each attribute is binary (e.g. has only yes/no value). For more complex values (e.g. numbers, strings, trees, graphs. . . ), FCA is then generalized into pattern structures [START_REF] Ganter | Pattern structures and their projections[END_REF]. Definition 7. A pattern structure is a triple (G, (D, ), δ), where G is a set of objects, (D, ) is a complete meetsemilattice of descriptions, and δ : G → D maps an object to a description.

The operator is a similarity operation that returns the common elements between any two descriptions. A description can be a set, a sequence, or other complex structure. In the case of set as a description, corresponds to set intersection (∩), i.e. {a, b, c} {a, b, d} = {a, b}, and corresponds to subset inclusion (⊆). In the case of sequence as a description, is a set of common closed subsequences (SCCS) [START_REF] Codocedo | A proposition for sequence mining using pattern structures[END_REF]. Similarly, corresponds to subsequence inclusion ( ). Definition 8. The Galois connection for a pattern structure (G, (D, ), δ) is defined as:

A = g∈A δ(g), A ⊆ G d = {g ∈ G|d δ(g)}, d ∈ D
Finally, a pattern concept is similar to a standard formal concept: Examples of pattern concepts are shown in Table V. There are two definitions of for sequence, and will be explained in Section VI-A.

C. Sequence Mining in FCA

In this section we briefly present the two algorithms that are adapted for mining the trajectories of visitors in a museum, namely MFCS [START_REF] Buzmakov | On mining complex sequential data by means of FCA and pattern structures[END_REF] and MRGS [START_REF] Codocedo | A proposition for sequence mining using pattern structures[END_REF]. The names of the algorithms are not used as such in the papers but here we use them by commodity. Both algorithms are original and very efficient, and among the few algorithms performing sequence mining in the framework of FCA.

MFCS was originally introduced for mining trajectories of patients in hospitals. One important characteristic of MFCS is that it mines contiguous subsequences, or stated differently, subsequences without any gap between items. This is due to the fact that physicians are mainly interested in consecutive events when analyzing healthcare trajectories. In addition, but this is not needed in our framework, MFCS is able to take into account a partial ordering -given by domain knowledge for example -defined on the items composing the sequences.

MRGS is also a sequence miner based on pattern structures but with a different purpose. The objective of MRGS is to mine rare rather than frequent subsequences, and in particular long subsequences with special characteristics. The algorithm is based on a specific pattern structure of subsequences, where the similarity operation is based on the discovery of common close subsequences (SCCS operation is illustrated in a next section). The SCCS operation is based on a directed graph of alignments (DAG of alignments) which guides the mining of common subsequences. The algorithm shows very good performances and is most probably one of the few algorithms whose objective is the mining of rare subsequences. In our framework, we adapted MRGS and the support threshold for comparison purposes with frequent subsequences. However, in our context we will use MRGS as a standard sequence miner and we will be interested in frequent subsequences.

III. THE DATASET OF MUSEUM VISITORS

A. The Museum

In the framework of the CrossCult project, we are working on a specific dataset about the trajectories of 254 visitors in Hecht Museum in Haifa, Israel [START_REF] Lanir | The influence of a location-aware mobile guide on museum visitors' behavior[END_REF]. In the raw dataset, a visitor trajectory contains a list of visited items, where each visit is composed of three elements: "start time", "end time", and "item name". An example is presented in Table II. When modeling trajectories into sequences, in this paper we consider only the "item name", so every itemset contains only one item. For simplicity, we omit the curly brackets to describe an itemset. Therefore we will write {a}{d}{e} as a, d, e . A visitor can have visits with various time lengths. In order to obtain more meaningful results and to reduce the complexity, we only consider visits lasting at least 90 seconds, but this is a parameter than can be relaxed or more constrained. Thirty-eight trajectories have no visit more than this threshold, so they are ignored, leaving us with 216 trajectories. Moreover, we model each trajectory as a sequence of visited items. Therefore, for trajectory in Table II, the corresponding sequence is Crafts and Arts, Wooden Tools . This preprocessing results in sequences of various size. Forty-five sequences have only one itemset, while three sequences have more than 15 itemsets. We group the museum items according to their location, so that we obtain 8 categories of items. To illustrate the numbering of items, the first two categories and their items are listed in Table III. We convert the raw dataset into sequences of items, where each item is represented by its ID. We define the IDs such that we can infer the category of an item by its first digit. Therefore, we obtain a dataset of 216 sequences of visitor trajectories (named V 1 -V 216 ) where each sequence is composed by a list of IDs, as illustrated in Table IV.

MFCS and MRGS algorithms are suitable for our dataset, since we want to include the hierarchical information in the mining process. For example, given two sequences 102, 203 and 103, 204 , it is interesting to mine subsequence 1, 2 .

B. The Four Visiting Styles

In a seminal work about the typing of visitor styles in a museum [START_REF] Véron | Ethnographie de l'exposition[END_REF], four main behaviors have been detected and described, leading to different recommendations all along a visit [START_REF] Zancanaro | Analyzing museum visitors' behavior patterns[END_REF], [START_REF] Kuflik | Analysis and prediction of museum visitors' behavioral pattern types[END_REF]. These four styles are summarized below:

• The ant is a visitor who will surely see all the works following their location order in the museum. Then the recommendation can be the following item, but depending also on some environmental factors such as the crowd in the museum, the accessibility of the item and the fatigue of the visitor.

• The grasshopper is a visitor who will see only certain artworks, jumping from one to another. Then, to encourage such a person to visit more items, the recommendation can be to visit items having a content similar to items already visited.

• The butterfly is a visitor wanting to discover some and not all artworks, without having any exact preferences. Then, the recommendation is open and can be based on surprise (items which are very different one from the other).

• The fish is a visitor who does not feel that much interested in the artworks and stays most of the time in the center of the rooms without any precise objective.

Then the recommendation can be to visit the most famous items in the museum which are the closer to the current visitor location, for encouraging the visitor to continue the visit and gain more interest.

Indeed, a visitor can change his/her style during a visit and other elements may be of importance, e.g. crowd or fatigue of the visitor.

IV. WORKFLOW FOR ANALYZING THE TRAJECTORIES

In the following, one objective is to map specific subsequences included in the visitor trajectories to each visiting style for characterizing more precisely the style and then making smarter recommendations. To identify the behavior of each visitor, we propose the following workflow:

1) Cluster the visitor trajectories and assign a label for each visitor (Section V). 2) Create two concept lattices using MFCS and MRGS over the whole dataset (Section VI-A). 3) From the two lattices, find jumping emerging patterns (JEPs) for each label (Section VII-A). 4) Based on their JEPs, these labels are then mapped into four visiting styles as explained in Section III-B.

V. CLUSTERING OF TRAJECTORIES

In this first experiment, we reuse the sim ACS similarity measure for clustering the visitor trajectories. The idea is to check whether it is possible to distinguish the four visiting styles introduced above. We apply hierarchical clustering1 based on sim ACS to build a distance matrix between individuals. From the resulting dendrogram, we retained 5 clusters denoted by "A", "B", "C", "D", and "E". Four of them are expected to match the four visiting patterns, namely ant, butterfly, fish, and grasshopper. The last cluster will gather all non-classified trajectories. These five clusters have various sizes. Cluster "A", "B", "C", "D", and "E" have 11, 11, 59, 102, and 33 visitors respectively. Actually, it is not easy to directly match the five clusters to corresponding visiting styles. For doing so, we will analyze the subsequences that can be attached to each cluster of trajectories. The benefit of the clustering is actually to provide a label among "A", "B", "C", "D", and "E" to the visitors. Thanks to these labels, we can search the so-called "jumping emerging patterns" and attach a characterization to the clusters based on the mined subsequences.

A. Mining Subsequences with MFCS and MRGS

Below, we explain the application of the MFCS and MRGS algorithms to the museum dataset and the building of an associated concept lattice. Moreover, as discussed in Section VI-B, the mining of jumping sequential patterns will help us to characterize the visitor trajectories.

In MFCS and MRGS, pattern structures are used for mining sequences. The similarity operator ( ) between any two sets of sequences is defined as the set of closed common subsequences (SCCS) in the two input sequences. Then, given two sequences, say S 1 = 401,502,503 and S 2 = 401,503,502 , the similarity between these descriptions is:

δ(S 1 ) δ(S 2 ) = { 401,502,503 } { 401,503,502 } = { 401,502 , 401,503 }
In the dataset, the items are grouped into categories (indicated by their first digit) and the SCCS calculation is performed, checking whether two items belong to the same category. Using the MFCS algorithm it becomes:

δ(S 1 ) δ(S 2 ) = { 401,502,503 } { 401,503,502 } = { 502 , 503 , 401,5,5 }
It should be noticed that MFCS mines contiguous subsequences, i.e. in Definition 2, i k = i k-1 + 1 for all k ∈ {2, 3, . . . , m}. Furthermore, subsequence 401,5,5 can be regarded as a generalization, meaning that after item 401, the next two visited items are something in category 5.

In parallel, the default similarity operator of MRGS algorithm can be modified to accommodate our needs, such that non-contiguous common subsequences can be mined: Then, based either on MFCS or MRGS, a concept has an extent including a set of trajectories and an intent including a set of common subsequences. Again, it should be noticed that, based on whether a subsequence is contiguous or not, the obtained concepts are different.

For example, the concepts corresponding to Table IV are shown in Table V. Notice that both algorithms obtain a concept whose extent is V 2 , V 3 , V 4 , albeit with different intent. Based on MRGS, the common subsequence of V 2 , V 3 , V 4 is 1, 402 , while according to MFCS, their common subsequences are 1 and 402 . This is because items 1 and 402 are not contiguous in V 3 and V 4 .

B. Jumping Emerging Patterns

FCA is a non supervised classification process that can be turned into a supervised process thanks to the adding of a target attribute in the context, generally corresponding to a target class. Then the idea is to search for the so-called "Jumping Emerging Patterns" (JEPs) [START_REF] Dong | Efficient mining of emerging patterns: Discovering trends and differences[END_REF]. We have already applied this approach in [START_REF] Asses | A Hybrid Classification Approach based on FCA and Emerging Patterns -An application for the classification of biological inhibitors[END_REF] for analyzing and characterizing clusters of biological inhibitors. Here we adapt the same idea for characterizing this time the clusters of visitors discovered with the similarity measure sim ACS .

More precisely, five clusters are discovered by classifying visitor trajectories with sim ACS . These same trajectories are then considered as sequences composed of subsequences. Then a set of characteristic subsequences is extracted and these subsequences are used as "attributes" in a formal context where objects are visitor trajectories. The resulting formal context is completed with an extra attribute corresponding to the "cluster information", i.e. the cluster in which the trajectory is classified according to sim ACS . A concept lattice can then be built from this completed context.

More interestingly, the cluster information is used for characterizing the concepts whose extents include trajectories of a single cluster. The intents -made of subsequences -of these particular concepts are JEPs, and as such they can be used to characterize the corresponding clusters. For example, if the extent of the concept ({V 103 , V 165 , V 188 }, { 4 , 1 , 306 , 701,707 }) includes visitors from cluster B only, then its intent is a JEP for that cluster.

VII. DISCUSSION

A. Cluster Characterization

Now we are interested in characterizing the five clusters that were introduced in the previous section. For doing so, JEPs are searched in the two concept lattices obtained with MFCS and MRGS algorithms. Some of these concepts are listed in Table VI andTable VII. First, from both MFCS and MRGS, we cannot find any satisfying concept for JEP of cluster "E". This is because among all the concepts whose extent is exclusively from cluster "E", none of them has more than one visitor. If we consider the dataset, among 33 members of cluster "E", 32 of them visit less than 2 items during their whole visit. We can assume that these visitors are not really interested in visiting the museum. Therefore, we can "safely" label this cluster as fish.

Cluster "D" is more easily distinguishable. Based on subsequences of concept FD2-FD4, many visitors in this class skip some items. Also, in concept RD1 and RD2, some of them visit other items after item 701. This is not a natural direction, because items in category 7 are located farther from the entrance than items in category 4 or 5. We can interpret the visitors of this cluster as grasshopper, since they "jump" from one item to another.

Clusters "A", "B", and "C" are relatively similar to each other. The visitors associated to these clusters follow an ant behavior: a natural flow (based on RA1-RC1) and no "jump" (based on FA1-FC2). However, in FC3, three visitors visit 101, then 102, then back again to 101, indicating rather a butterfly behavior.

B. Conclusion

In this article, we have presented our experiments in mining visitor trajectories that are modeled as sequences of items. First, we clustered the trajectories according to their common subsequences. Then, we tried to validate the clusters as behaviors (ant, butterfly, fish, and grasshopper). This is done by applying two sequence miners based on FCA to the visitor trajectories, namely MFCS and MRGS, to discover characterizing contiguous and general subsequences in each cluster.

Our result highlights some interesting patterns that may define visitor behaviors. This can help museum researchers to analyze and evaluate the placement of items and the visiting styles. Moreover, we have also studied the possibility of clustering the visitors based on a concept lattice. These clusters can be analyzed to build a recommendation system for future visitors, but we did not yet study this aspect until now.

In this paper, we only included partial information about the museum in the sequences. More interesting results are expected if other elements are taken into account, such as more general knowledge about history and geography, as well as the duration and time of the visit. Furthermore, the selection of interesting concepts can be also guided by the "stability" of concepts [START_REF] Kuznetsov | Concept stability for constructing taxonomies of web-site users[END_REF]. Finally, from a more dynamic point of view, ongoing information such as comments and state of the visitor during the visit could be also considered for analysis and online recommendation.

Definition 4 .

 4 A formal context is a triple (G, M, I), where G is a set of objects, M is a set of attributes, and I is a binary relation between G and M , i.e. I ⊆ G × M .

Fig. 1 :

 1 Fig. 1: Concept lattice for the formal context in TableI

Definition 9 .

 9 A pattern concept is a pair (A, d), A ⊆ G and d ∈ D, where A = d and d = A.

δ(S 1

 1 ) δ(S 2 ) = { 401,502,503 } { 401,503,502 } = { 401,502 , 401,503 , 401,5,5 }

TABLE I :

 I A formal context for four visitors, with four items: 102, 302, 402, and 704 as an example. An × indicates that the visitor visits the item. Definition 2. A sequence s = s 1 s 2 . . . s m is a subsequence of sequence s = s 1 s 2 . . . s n , denoted by s s , if there exist indices 1 ≤ i 1 < i 2 < . . . < i m ≤ n such that s j ⊆ s ij for all j = 1 . . . m and m ≤ n.

		102	302	402	704
	V1				×
	V2	×		×
	V3	×	×	×
	V4		×	×	×

TABLE II :

 II An example of one visitor trajectory.

	Start time	End time	Item name
	12:55:39	12:58:05	Crafts and Arts
	12:58:06	12:58:22	Religion and Cult
	12:58:22	12:58:27	Building Methods and Facilities
	12:58:29	13:05:09	Wooden Tools

TABLE III :

 III Grouping of museum items.

	Category	Items and their ID
	1	Entrance Reuben Hecht (101),
		Symbols Jewish Menorah (102),
		Persian Cult (103), Jerusalem Photo (104)
	2	Religion and Cult (201), Everyday Pottery (202),
		Phoenician Writing (203), Burial Tradition (204),
		Building Methods and Facilities (205),
		Maritime Commerce (206), Imported Pottery (207),
		Crafts and Arts (208)

TABLE IV :

 IV Examples of visitor trajectories.

	Visitor	Trajectory
	V1	101, 101, 401, 704
	V2	102, 402, 808, 206, 808
	V3	302, 102, 201, 302, 705, 402, 802
	V4	104, 704, 602, 302, 402, 103

TABLE V :

 V The concepts that are computed by of MFCS and MRGS from four visitors in TableIV.

	Extent	Intent (MFCS)	Intent (MRGS)
	V1	101,101,401,704
	V2	102,402,808,206,808
	V3	302,102,201,302,705,402,802
	V4	104,704,602,302,402,103
	V1,2	1,4	not present
	V1,4	1 , 4 , 704	1,1 , 1,4 , 1,704
	V2,3	2 , 102 , 402,8	102,402,8 , 102,2,8
	V3,4	1 , 302 , 402 , 7	1,302,402 , 302,1 , 1,7,402
	V1,3,4	1 , 4 , 7	1,4 , 1,7
	V2,3,4	1 , 402	1,402
	V1,2,3,4	1 , 4	1,4

We use the hclust method from the R software[START_REF] Core | R: A Language and Environment for Statistical Computing[END_REF].VI. THE MINING OF TRAJECTORIES CONSIDERED AS SEQUENCES