Florence Le Ber

Peggy Cellier

Justine Reynaud

Kevin Dalleau

Lauréline Nevin

Quentin Brabant

Tatiana Makhalova

Alexandre Bazin

Guilherme Alves

Laurine Huber

Nacira Abbas

Claire Theobald

Giorgios Zervakis

Laura Zanella

In the beginning, I would like to thank my supervisor Amedeo Napoli for considering me capable enough of doing a thesis, and my rst co-supervisor Chedy Raïssi, who was substituted by my second co-supervisor Miguel Couceiro halfway through the thesis. All three of

Je dédie cette thèse à ma famille java-balinaise iii or transforming some variables. The next step is data mining tasks applied to the transformed data. First, the expected information matched with a specic data mining method (e.g. classication, clustering, regression, summarization, etc.). Having selected a method, an algorithm is determined and data mining process is executed. From this step, we can retain some signicant patterns discovered in the data. The last step is interpretation. Having the patterns extracted, we have to interpret them, by visualisation for example. The retained patterns are then reported to concerning parties, or used directly. We can also return to some previous steps to enhance the results.

In this thesis, we are interested in knowledge discovery method applied to complex data. More precisely, this thesis focuses on the data mining and data transformation steps in KDD. We had the opportunity to work on several types of complex data, namely numerical, sequential, and molecular datasets. In the data mining step, our objectives are to discover some biclusters in numerical data and to mine interesting patterns in sequential data. Formal concept analysis which itself can be considered as a KDD method [START_REF] Couceiro | Elements about exploratory, knowledge-based, hybrid, and explainable knowledge discovery[END_REF] is used for completing these objectives since it is naturally related to biclustering in the sense that both of them discover submatrices indicating some regularities. Furthermore, it was shown that FCA and its extension, pattern structures, are suitable for mining complex sequential datasets [START_REF] Buzmakov | On mining complex sequential data by means of FCA and pattern structures[END_REF][START_REF] Codocedo | A proposition for sequence mining using pattern structures[END_REF]. Concerning the data transformation step, our objective is to reduce the dimensionality of a molecular dataset by eliminating some features. This is performed by identifying some associations among features, which in turn can be used to decide which features are redundant and can be eliminated.

Contributions

As explained before, we worked on three kinds of complex data, which are gene expression data (numerical), visitor trajectory data (sequential), and antibacterial data (molecular). Several data mining methods based on FCA are used for discovering biclustering in gene expression data and for mining patterns in visitor trajectory data. In addition to data mining step, we worked on an important step in KDD which is feature selection using log-linear analysis to identify association among features/attributes. Therefore, this thesis can be summarized in three main contributions.

We begin by presenting biclustering and showing how FCA is well-adapted to support several important types of biclustering. Then we discuss how FCA and pattern structures can be applied to mine sequences, which are then used to characterize visitor in a trajectory dataset. Finally, we discuss the feature selection step when working on a complex data such as antibacterial data.

Each contribution is detailed as follows.

Biclustering

Biclustering with FCA is the rst contribution of this thesis, working with the gene expression data as numerical dataset. Biclustering is connected to clustering. The objective of clustering is to discover some groupings of objects in a dataset by looking at their similarity across all of their features/attributes. This may be problematic, since some objects may share similarity with other objects across a subset of features only, which is particularly observed in gene expression datasets. This problem leads to the emergence of biclustering in gene expression datasets [START_REF] Cheng | Biclustering of expression data[END_REF].

Given a matrix, formal concept analysis (FCA) is related to biclustering, in the sense that both methods try to nd submatrices having regularities within their cells. FCA is focused on a binary matrix, hence it only nds constant-value biclusters. To discover other types of biclusters (as dened in [START_REF] Madeira | Biclustering algorithms for biological data analysis: a survey[END_REF]), some extensions of FCA are proposed. Partition pattern structures (PPS) were applied to nd constant-column biclusters [START_REF] Codocedo | Lattice-based biclustering using partition pattern structures[END_REF]. In this thesis, the possibility of nding other bicluster types is studied by dening the corresponding similarity operator between any two sets of objects used in PPS. Furthermore, interval pattern structures (IPS) were applied to discover similar-column biclusters [START_REF] Kaytoue | Mining gene expression data with pattern structures in formal concept analysis[END_REF]. The potential of IPS is studied to discover other types of biclusters. Contrasting with PPS, IPS allows to nd less strict biclusters (e.g. similar column, similar row, non-exact additive biclustering, etc.) without scaling the numerical matrix. We applied our methods to the domain of bioinformatics, where the task of nding biclusters in a gene expression data matrix is still actively studied [START_REF] Henriques | BicPAM: Pattern-based biclustering for biomedical data analysis[END_REF][START_REF] Pio | A novel biclustering algorithm for the discovery of meaningful biological correlations between microRNAs and their target genes[END_REF][START_REF] Pontes | Biclustering on expression data: A review[END_REF].

Sequence mining

The second contribution is related to the CrossCult project (http://www.crosscult.eu/), a European Project about cultural heritage. The general idea of CrossCult is to support the emergence of a European cultural heritage by allowing visitors in dierent locations (e.g. museum, city, archaeological site) to attentively contemplate their visit at a European level by using adapted computer-based devices. One objective of this project is to develop a mobile application to stimulate the reection of history while users are visiting some cities or venues. This application registers the trajectory of each visitor while they interact with it, providing a kind of sequential dataset. A particular dataset is concerned with the trajectories of around 200 visitors in Hecht Museum in Haifa, Israel. Each trajectory is composed by sequence of visits, where each visit is represented by three components: start time, end time, and visited item. A novel method is then developed to understand these trajectories such that the visitor behaviors can be extracted according to four theoretical visiting patterns [START_REF] Kuik | Analysis and prediction of museum visitors' behavioral pattern types[END_REF]. This approach is composed of two independent steps: the clustering and the mining of trajectories. Given that the trajectory dataset can be regarded as a sequential dataset, a proper sequence clustering method is used where the distance between any two sequences is obtained from the number of their common subsequences [START_REF] Egho | On measuring similarity for sequences of itemsets[END_REF].

On the other hand, the mining of trajectory patterns is performed by two methods based on FCA [START_REF] Buzmakov | On mining complex sequential data by means of FCA and pattern structures[END_REF][START_REF] Codocedo | A proposition for sequence mining using pattern structures[END_REF]. These patterns are then used to nd the characteristic behavior of each cluster. This contribution may help the developer in providing recommendations to users/visitors for improving their visit and reections.

Feature selection

The third contribution of this thesis is related to numerical pattern mining, especially the problem of feature selection as a data transformation step in KDD. This work is part on a larger research of discovering new antibacterial drugs, by classifying chemical molecules into two classes: antibacterial and non-antibacterial. In this thesis, we work on feature selection over chemoinformatics datasets where it is important in several aspects of drug design [START_REF] Xu | Prediction of human disease-associated phosphorylation sites with combined feature selection approach and support vector machine[END_REF][START_REF] Yang | Development of in silico models for predicting p-glycoprotein inhibitors based on a two-step approach for feature selection and its application to chinese herbal medicine screening[END_REF]. Such datasets are usually represented as a matrix, where each row and column represents molecule and elements of the molecular structure respectively. Since a molecular structure has many properties, the matrix often has a high number of columns. This could increase the complexity and reduce the performance of any classication algorithm, causing the need of dimensionality reduction.

In feature selection, we start by the idea that a feature being highly correlated to another can be discarded, for obtaining a set of features that are not correlated. One way to detect correlation among attributes is given by log-linear analysis (LLA) [START_REF] Tabachnick | Using Multivariate Statistics[END_REF]. The basic LLA examines every pair of attributes, and this is not suitable for a dataset with large number of attributes. This restriction can be solved by considering a particular sub-class of LLA: decomposable models [START_REF] Petitjean | Scaling log-linear analysis to high-dimensional data[END_REF]. This avoids the calculation of correlation of every attribute pair, and therefore reducing the complexity of LLA. The result of this feature selection approach is then tested in antibacterial datasets. An evaluation is based on how well the selected features perform in the antibacterial nonantibacterial classication.

Thesis organization

This thesis is structured as follows.

• Chapter 1 presents the introduction of formal concept analysis and pattern structures, which will be used in the problem of sequence mining and biclustering.

The rest of this thesis is separated into two parts. The rst part constitutes the rst contribution about biclustering with three chapters as follows.

• Chapter 2 presents the problem of biclustering, the denition of current types of biclusters, and existing approaches to discover biclusters.

• Chapter 3 focuses on biclustering with partition pattern structures. First, a specic partition pattern structure which was applied to constant-column and similar-column biclustering is presented. Then, this approach is extended to other types of biclustering by adapting the description of each object and the similarity operation. This chapter is based on: N. Juniarta, V. Codocedo • Chapter 4 focuses on biclustering with interval pattern structures. Following the previous chapter, here we rst explain the specic interval pattern structure which was built for discovering similar-column biclustering. Then, using alignment, we show that this approach can be extended to discover other types of biclusters, especially the additive and multiplicative biclusters. This chapter is based on: N. Juniarta, M. Couceiro The second part represents the second contribution (about mining sequential dataset) and the third contribution (about feature selection) of this thesis. This part has two chapters as follows.

• Chapter 5 focuses on the task of describing visitor behaviors, using sequence clustering and FCA-based sequence mining. First, the formalization of sequence mining in FCA is presented. Then, combined with clustering of sequence using the count of all common subsequences, the characterization of visitor trajectories is described. This chapter is • Chapter 6 focuses on the numerical pattern mining domain, where we study the application of attribute relation discovery to solve the problem of feature selection. The attribute relation discovery is performed using LLA, which is explained rst. Then, we study the improvement of LLA based on chordal graph. Finally, we apply it to the antibacterial datasets and some publicly available datasets to understand the performance of the method. In this chapter, we introduce the formal concept analysis which will be used in the following chapters. First, we explain in Sect. 1.1 the basic denitions of order theory based on [START_REF] Ganter | Formal concept analysis: mathematical foundations[END_REF]. This theory is necessary to introduce the formal concept analysis in Sect. 1.2, and some algorithms for mining formal concepts in Sect. 1.3. In the end, pattern structures a generalization of formal concept analysis is presented in Sect. 1.4.

Order theory

A binary relation R between two sets M and N is a set of pairs (m, n) with m ∈ M and n ∈ N .

It can be written as mRn. Instead of two dierent sets, a binary relation can also be dened on a single set (M = N ), and it is called a binary relation on M . An order on M is a binary relation on that set that satises the following conditions for all x, y, z ∈ M : 1. xRx (reexivity), 2. xRy and x = y ⇒ not yRx (antisymmetry), 3. xRy and yRz ⇒ xRz (transitivity).

An order is often written as ≤. An ordered set is a pair (M, ≤), with ≤ is an order on M . This type of set is sometimes denoted as partially ordered set, since it is possible that not every pair of elements is comparable. This means that there may exist two dierent elements x and y that are incomparable, where x ≤ y and y ≤ x.

m 1 m 2 m 3 m 4 m 5 g 1 × × g 2 × × g 3 × × × × g 4 × × ×
Consider a set C, a subset of an ordered set (M, ≤). An element m ∈ M is a lower bound of C if ∀c ∈ C, m ≤ c. Dually, an element n ∈ M is an upper bound of C if ∀c ∈ C, c ≤ n. If there exists a single largest element among the set of all lower bounds of C, then this element is denoted the inmum of C. The supremum is dened dually.

If for any two elements x, y ∈ M , there exist the supremum (x ∨ y) and inmum (x ∧ y), then this ordered set is a lattice. Furthermore, if the supremum and inmum also exist for any X ⊆ M , then this ordered set is a complete lattice.

Formal concept analysis

Formal concept analysis (FCA) is a mathematical framework based on lattice theory and used for classication, 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 the order among them in a concept lattice.

A formal context K 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 . If an object g has an attribute m, then (g, m) ∈ I. A formal context can be represented as a matrix, an example is shown in Table 1. 1. In a formal context, FCA nds maximal rectangles. A rectangle is a submatrix whose cells are entirely ×. An example of such rectangle in Table 1.1 is the submatrix r 1 constructed by rows {g 3 , g 4 } and columns {m 2 , m 3 }. Furthermore, a rectangle is maximal if there is no other larger rectangle that can be created by adding rows or columns to the current rectangle. Therefore, the rectangle r 1 is not maximal, since another larger rectangle r 2 can be formed by adding m 4 to the rows of r 1 . On the other hand, the rectangle r 2 , having rows {g 3 , g 4 } and columns {m 2 , m 3 , m 4 }, is maximal.

A maximal rectangle corresponds to a formal concept in FCA. Its set of rows and set of columns are called its extent and its intent respectively. Formal concepts can be found by introducing derivation operators for any subset of objects and any subset of attributes:

:℘(G) → ℘(M ), :℘(M ) → ℘(G), (1.1) where ℘(G) and ℘(M ) represent the power set of G and M respectively. Given A ⊆ G and B ⊆ M , these operators are dened by:

A = {m ∈ M |∀g ∈ A, (g, m) ∈ I}, B = {g ∈ G|∀m ∈ B, (g, m) ∈ I}. (1.2)
In other words, A is the set of attributes that are shared by all objects in A, while B is the set of objects having all attributes in B. Therefore, these two operators form a Galois connection between ℘(G) and ℘(M ) [START_REF] Ganter | Formal concept analysis: mathematical foundations[END_REF]. 1.1. The number inside each node is the concept number. The set written above and below each node represents the concept's intent and extent respectively. The diagram is generated using Latviz [START_REF] Alam | Latviz: A new practical tool for performing interactive exploration over concept lattices[END_REF].

A formal concept is a pair (A, B) where A = B and B = A. In the previous example, the rectangle r 2 is a formal concept since {g 3 , g 4 } = {m 2 , m 3 , m 4 } and {m 2 , m 3 , m 4 } = {g 3 , g 4 }. This formal concept is written as ({g 3 , g 4 }, {m 2 , m 3 , m 4 }). The set of all formal concepts B(G, M, I) is partially ordered, given by relation ≤ K :

(A 1 , B 1 ) ≤ K (A 2 , B 2 ) ⇐⇒ A 1 ⊆ A 2 (dually B 2 ⊆ B 1 ). (1.3)
B(G, M, I) is a lattice, since for any two concepts, the supremum and the inmum always exist. Furthermore, it is also a complete lattice since there exist the supremum and inmum of any B ⊆ B(G, M, I).

The concept lattice of the formal context in Table 1.1 is depicted in a Hasse diagram in Fig. 1.1. This diagram reects the partial ordering of B(G, M, I). Concept number 5 (c 5 = ({g 3 }, {m 1 , m 2 , m 3 , m 4 })) is less than concept number 6 (c 6 = ({g 2 , g 3 , g 4 }, {m 3 })), written as c 5 ≤ K c 6 . Therefore, there is a path going down from c 6 to c 5 . Meanwhile, c 3 and c 7 is not comparable, since neither c 3 ≤ K c 7 nor c 7 ≤ K c 3 . Therefore, there is no path going entirely up or entirely down between these two concepts.

Formal concept miners

Various algorithms have been proposed to enumerate all formal concepts from a formal context and/or building the corresponding concept lattice. In this thesis, we used the Close by One and AddIntent algorithms since they can be easily adapted to pattern structures (will be explained later). We also explain here In-Close2 algorithm, which was used in the literature for FCA-based biclustering.

Close by One

Close by One (CbO) was proposed in [START_REF] Kuznetsov | A fast algorithm for computing all intersections of objects from an arbitrary semilattice[END_REF], and detailed here in Algo. 1. The time complexity of CbO is O(|G| 2 |M ||L|) [START_REF] Kuznetsov | Comparing performance of algorithms for generating concept lattices[END_REF], where L is the number of concepts. It starts from a single object, then adding objects one by one according to the lexicographical order of objects. When an object is added to a current set, the algorithm checks the set's closure (the (.) operation).

The process of concepts generation of the formal context in Table 1.1 is illustrated as a tree in Fig. 1.2. Each node which is not crossed corresponds to a formal concept. First, the set {g 1 } and its closure {g 1 } is checked, and kept as a concept ({g 1 }, {m 4 , m 5 }). Then, the next object is added to the previous closure, forming the set {g 1 , g 2 } with closure {g 1 , g 2 , g 3 , g 4 }. Since, there is no more object can be added to the preceding closure (line 12 of the algorithm), this branch is terminated.

The node with {g 1 , g 4 } is not kept as a concept, since it is not canonical. It tries to generate a concept ({g 1 , g 3 , g 4 }, {m 3 }), but this concept is already generated previously, from the node {g 1 , g 3 }. This checking is done in the line 10 of the algorithm. The closure of the set {g 1 , g 4 } is {g 1 , g 3 , g 4 }, containing g 3 that is lexicographically less than another object in the set (g 4 ).

1 CloseByOne:

2 L := ∅ 3 foreach g ∈ G do 4 Process({g}, g, (g , g )) 5 end 6 L is the set of concepts

AddIntent

The result of CbO is the set of concepts B(G, M, I). If the lattice of the concepts is also expected, then we need another approach. AddIntent [START_REF] Van Der Merwe | AddIntent: A new incremental algorithm for constructing concept lattices[END_REF] is an algorithm that enumerates the set of concepts and generates its lattice. This algorithm, shown in Algo. 23, is a bottomup approach. In general, each time an object is added, the algorithm calculates the possible intersections between the object's intent and the intents of all other concepts in the current lattice. Then, the algorithm generates new concepts based on these intersection and connects them accordingly to the existing concepts.

1 CreateLatticeIncrementally(G, M, I):

2 BottomConcept := (∅, M ) 3 L := BottomConcept 4 foreach g ∈ G do 5 ObjectConcept = AddIntent(g , BottomConcept, L) 6
Add g to the extent of ObjectConcept and all concepts above 7 end

Algorithm 2: The procedure to generate concept lattice, using AddIntent algorithm.

As shown in Algo. 2, AddIntent starts with a lattice with the bottom concept (∅, M ). Then, the algorithm calls AddIntent function (Algo. 3) for each object g ∈ G, with g as intent. The function rst looks for the GeneratorConcept (line 2) from which NewConcept may be generated.

The function GetMaximalConcept nds the most general concept whose intent ⊇ intent. The parents of NewConcept can be found among the parents of GeneratorConcept. For every parent of GeneratorConcept (line 8), the algorithm goes up until it nds a concept whose intent is a subset of intent (done recursively in line 910). This concept is added to NewParents after checking whether it is comparable to the existing NewParents (line 1324). After that, the NewConcept is added between any concept in NewParents and its GeneratorConcept.

An example of AddIntent concept generations is illustrated in Fig. 1.3, working with the formal context in Table 1.1. Consider Fig. 1.3c, which is the lattice after the addition of g 2 . The next object to be added is g 3 , with {g 3 } = {m 1 , m 2 , m 3 , m 4 } as intent. The GeneratorConcept for this object is c 0 , having two parents c 1 and c 3 . From c 1 , the algorithm nds c 2 as the new parents, and inserts a new concept c 4 between c 1 and c 2 . Then from c 3 , the algorithm nds c 3 and c 4 as the new parents, thus inserts a new concept c 5 between c 0 and both of c 3 and c 4 .

In-Close and In-Close2

In-Close2 algorithm [START_REF] Andrews | In-Close2, a high performance formal concept miner[END_REF] and its predecessor In-Close [START_REF] Andrews | In-Close, a fast algorithm for computing formal concepts[END_REF] are based on CbO. Both of them start from the pair (G, ∅) and adding attributes one by one to discover other concepts. To see the dierence between In-Close and CbO, here we will consider that In-Close start from the pair (∅, M ) and it adds objects one by one.

The running of In-Close algorithm is illustrated in Fig. 1.4. The algorithm starts from the top concept (∅, M ), and adds objects by their lexicographical order. Each time an object is added to the current extent A, the algorithm calculates the new intent A by doing the intersection.

There are three outcomes of the new intent: Consider the node where c 2 is generated in Fig. 1.4, after the addition of g 1 . The algorithm then separately adds g 2 , g 3 , and g 4 ; hence three branches in the gure. The new intent from the addition of g 2 is ∅, corresponding to O 1 . In this case, the algorithm stops exploring this branch. The new intent from the addition of g 3 is a proper subset of the previous intent {m 4 , m 5 }, corresponding to O 2 . Therefore, the new pair ({g 1 , g 3 }, {m 4 }) is accepted as a new concept c 3 . Then, the algorithm continues this branch, adding g 4 . The new intent is the same with the 1.3. Formal concept miners

1. O 1 : Emptyset,
c 0 m 1 , m 2 , m 3 , m 4 , m 5 ∅ c 1 m 4 , m 5 g 1 (a) c 0 m 1 , m 2 , m 3 , m 4 , m 5 ∅ c 1 m 4 , m 5 g 1 c 2 ∅ g 1 (b) c 0 m 1 , m 2 , m 3 , m 4 , m 5 ∅ c 1 m 4 , m 5 g 1 c 3 m 1 , m g 2 c 2 ∅ g 1 , g 2 (c) c 0 m 1 , m 2 , m 3 , m 4 , m 5 ∅ c 1 m 4 , m 5 g 1 c 3 m 1 , m 3 g 2 c 4 m 4 g 1 c 2 ∅ g 1 , g 2 (d) c 0 m 1 , m 2 , m 3 , m 4 , m 5 ∅ c 1 m 4 , m 5 g 1 c 5 m 1 , m 2 , m 3 , m 4 g 3 c 3 m 1 , m 3 g 2 , g 3 c 4 m 4 g 1 , g 3 c 2 ∅ g 1 , g 2 , g 3 (e) c 0 m 1 , m 2 , m 3 , m 4 , m 5 ∅ c 1 m 4 , m 5 g 1 c 5 m 1 , m 2 , m , m 4 g 3 c 3 m 1 , m g 2 , g 3 c 4 m 4 g 1 , g 3 c 6 m 3 g 2 , g 3 c 2 ∅ g 1 , g 2 , g 3 (f) c 0 m 1 , m 2 , m 3 , m 4 , m 5 ∅ c 1 m 4 , m 5 g 1 c 5 m 1 , m 2 , m 3 , m 4 g 3 c 3 m 1 , m 3 g 2 , g 3 c 7 m 2 , m 3 , m 4 g 3 , g 4 c 4 m 4 g 1 , g 3 , g 4 c 6 m 3 g 2 , g 3 , g 4 c 2 ∅ g 1 , g 2 , g 3 , g 4 (g)
Figure 1.3: The generation of formal concepts using AddIntent for the formal context in Table 1. 1, showing the steps after addition of g 1 (a) until the nal lattice (g). The gures (bc), (de), and (fg) correspond to the additions of g 2 , g 3 , and g 4 respectively.

Figure 1.4: Generations of concepts of the formal context in Table 1.1 using In-Close algorithm by object additions. The nodes are generated depth-rst. Each time a concept is generated, it is symbolized by c n = (A, B). The underlined object in an extent means that the object is added after the calculation from the nodes below. previous intent ({m 4 }), corresponding to O 3 . Therefore, the object g 4 is added to the previous extent, modifying the concept c 3 such that its extent is {g 1 , g 3 , g 4 }.

Moreover, before the acceptation of the new concept from O 2 , the algorithm checks whether the new intent is already generated. This is the case with the addition of g 4 to the concept c 1 . Although the new intent is a proper subset of the intent of c 1 , the pair ({g 1 , g 4 }, {m 4 }) is not accepted as a concept since the intent {m 4 } is already generated in c 3 .

If we compare the exploration of In-Close in Fig. 1.4 with the exploration of CbO in Fig. 1.2, we see some dierences. Although both algorithms add objects (or attributes) one by one using lexicographical order, they dier on how the concepts are generated. In CbO, a concept is generated by calculating the closure (.) of a set of objects. In In-Close, the intent of a concept is generated rst, then its extent is calculated recursively. On the other hand, in In-Close2 an improvement of In-Close combines depth-rst and breadth-rst approach when adding objects/attributes.

Pattern structures

As explained in the previous section, a formal context K is a triple (G, M, I) where I is a binary relation between G and M . This means that we can not have multi-valued relation as I. This limitation is relaxed in pattern structures [START_REF] Ganter | Pattern structures and their projections[END_REF], generalizations of FCA. In FCA, we can say that each object is described by a set of attributes. On the other hand, in pattern structures, each object can be described by a more complex structure, e.g. a list of interval [START_REF] Kaytoue | Mining gene expression data with pattern structures in formal concept analysis[END_REF], a sequence [START_REF] Buzmakov | On mining complex sequential data by means of FCA and pattern structures[END_REF][START_REF] Codocedo | A proposition for sequence mining using pattern structures[END_REF], a partition [START_REF] Codocedo | Lattice-based biclustering using partition pattern structures[END_REF], an RDF triple [START_REF] Alam | Exploratory knowledge discovery over web of data[END_REF], etc.

Instead of (G, M, I), a pattern structure is determined by the triple (G, (D, ), δ), where (D, ) is a meet-semilattice of descriptions D having as similarity operator, and δ : G → D maps an object to its description. Following Eq. 1.1, the derivation operators are dened for any subset of objects and any description:

: ℘(G) → D, : D → ℘(G).
Given A ⊆ G and d ∈ D, these operators comparable with Eq. 1.2 are dened by:

A = g∈A δ(g), d = {g ∈ G|d δ(g)}.
In other words, A is the similarity of descriptions of each object in A, while d is the set of objects whose description subsumes d. The subsumption order over these descriptions follows that:

d 1 d 2 = d 1 ⇔ d 1 d 2 .
(1.4) A pattern concept is a pair (A, d) where A = d and d = A.

Consider a standard FCA and the formal context in Table 1.1. In pattern structures, each object in this context has a set of attributes as description. For example, δ(g 1 ) = {m 4 , m 5 }. The in this case corresponds to the set intersection (∩). Therefore:

δ(g 2 ) δ(g 3 ) = δ(g 2 ) ∩ δ(g 3 ) = {m 1 , m 3 } ∩ {m 1 , m 2 , m 3 , m 4 } = {m 1 , m 3 }. ∅ {g 1 } = [5, 5][7, 7][4, 6] {g 1 } = {g 1 } {g 1 , g 2 } = [5, 6][7, 8][4, 6] {g 1 , g 2 } = {g 1 , g 2 , g 3 } {g 1 , g 3 } = [5, 6][7, 7][5, 6] {g 1 , g 3 } = {g 1 , g 3 } {g 2 } = [6, 6][8, 8][4, 4] {g 2 } = {g 2 } {g 2 , g 3 } = [6, 6][7, 8][4, 5] {g 2 , g 3 } = {g 2 , g 3 } {g 3 } = [6, 6][7, 7][5, 5] {g 3 } = {g 3 } Figure 1
.5: Generations of interval pattern concepts of the context in Table 1.2 using CbO algorithm. It is similar to Fig. 1.2, with dierences on derivation operators.

If A = {g 2 , g 3 , g 4 }, then A = δ(g 2 ) δ(g 3 ) δ(g 4 ) = {m 3 }, which is consistent with A in FCA.
The relation is subsumed by ( ) corresponds to subset relation (⊆) in FCA. In this case d is the set of objects whose description is a superset of d. Still in Table 1

.1, with d = {m 3 }, d = {m 3 } = {g 2 , g 3 , g 4 }, consistent with {m 3 } in FCA. Furthermore, since {g 2 , g 3 , g 4 } = {m 3 } and {m 3 } = {g 2 , g 3 , g 4 }, the pair ({g 2 , g 3 , g 4 }, {m 3 }) is a pattern concept, which corresponds to a formal concept in FCA.
Using pattern structures, not only a set of attributes, we can have a more complex description by dening the operator , as long as the set of description is a meet-semilattice. In other words, the set of descriptions must be a partially ordered set having an inmum for any two descriptions.

To enumerate all pattern concepts, CbO algorithm can be used by redening the operator and relation (.) , ∩, ⊆ to (.) , , respectively.

Other examples of pattern structures are interval pattern structures (IPS) [START_REF] Kaytoue | Mining gene expression data with pattern structures in formal concept analysis[END_REF]. In IPS, a description of an object is a list of attribute intervals. Consider a numerical context in Table 1.2.

The description of g 1 is δ(g 1 ) = [5, 5][7, 7][6, 6] . The similarity operator between two descriptions in IPS is dened as the list of smallest interval covering all the corresponding interval in the descriptions. For example, δ(g 1 ) δ(g 2 ) is [5, 6][7, 8][4, 6] . Following Eq. 1.4, larger interval is subsumed by smaller interval, e.g. [START_REF] Alizadeh | Distinct types of diuse large b-cell lymphoma identied by gene expression proling[END_REF]6] Biclustering is a simultaneous grouping of rows and columns in a matrix. It is related to FCA, in the sense that both methods discover submatrices having some regularities among their elements. In this chapter, we introduce the denitions of biclustering and some previous works.

These denitions will be used in the next chapters, i.e. biclustering with partition and interval pattern structures.

Clustering and biclustering

Before describing the denitions of biclustering, we rst revisit the clustering task. Clustering is a part of the data mining step in KDD, where we discover some patterns that tell us the possible existence of similarity among the objects. In general, this task groups a set of objects based on the attributes of each object. However, the precise denition of cluster depends on the algorithms [START_REF] Estivill-Castro | Why so many clustering algorithms: A position paper[END_REF]. For example, in k-means clustering, a cluster can be represented as a single vector that is called a centroid, where an object belongs to the nearest centroid. In hierarchical clustering [START_REF] Johnson | Hierarchical clustering schemes[END_REF], a cluster is a recursive partition of a larger set of objects into some smaller subsets.

In DBSCAN [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF], a cluster is a group of objects that are closely packed together.

In spite of various denitions of cluster, the majority of clustering algorithms group the objects based on all of the attributes together. On the other hand, biclustering is a unique type of clustering where an object can be grouped with another object even if they share a similarity across a subset of attributes only. In other words, biclustering is clustering of objects and attributes simultaneously [START_REF] Hartigan | Direct clustering of a data matrix[END_REF]. From this point of view, biclustering is naturally related to FCA and pattern structures, since a bicluster can be regarded as a concept. (f)

+ + -+ + + -+ --+ - + + -+ (g)

Basic denitions

We consider that a dataset is a matrix (G, M ) where G is a set of rows/objects and M is a set of columns/attributes. The value of m ∈ M for object g ∈ G is written as m(g). A submatrix constructed from a subset of rows A ⊆ G and a subset of columns B ⊆ M is denoted as (A, B).

The rst type of biclusters is constant-value, which is a submatrix having the same value for all of its elements. In a binary matrix, a formal concept corresponds to a constant-value bicluster. This bicluster is described in Def. 1.

Denition 1 (Constant-value bicluster). Given a dataset (G, M ), a pair (A, B)

(where A ⊆ G, B ⊆ M ) is a constant-value bicluster i ∀g ∈ A, ∀m ∈ B, m(g) = c
where c is a constant.

Other types of bicluster are formalized in the following denitions.

Denition 2 (Constant-column bicluster). Given a dataset (G, M ), a pair (A, B) (where A ⊆ G, B ⊆ M ) is a constant-column (CC) bicluster i ∀m ∈ B, ∀g, h ∈ A, m(g) = m(h).

An example of CC bicluster is illustrated in

A ⊆ G, B ⊆ M ) is an additive bicluster i ∀g, h ∈ A, ∀m, n ∈ B, m(g) -n(g) = m(h) -n(h); or a multiplicative bicluster i ∀g, h ∈ A, ∀m, n ∈ B, m(g)/n(g) = m(h)/n(h).
Order-preserving biclustering is another type of biclustering where the expected submatrix has a common permutation of columns for all rows. In the example (Table 2.1f ), there is a sequence of column: second < rst < third < fourth column, that is true for all rows. This type of bicluster is formalized as follows.

Denition 4 (Order-preserving bicluster). Given a dataset (G, M ), a pair (A, B) (where A ⊆ G, B ⊆ M ) is an order-preserving bicluster i there exists a sequence of columns (m 1 • • • m |B| ) for all m i ∈ B, such that m i (g) < m i+1 (g) for all g ∈ A.

Lastly, another type of biclustering that is studied in this thesis is coherent-sign-changes biclustering, illustrated in Table 2.1g. In this bicluster, each column is equal ( ) to each other: the rst, second, and fourth columns are identical, while the third column is opposite of the others. This bicluster is formalized in the following denitions.

Denition 5 (Column submatrix). In a binary dataset (G, M ) where G is a set of objects and M is a set of attributes, (A, m j ) is the column submatrix with A ⊆ G and m j ∈ M .

Denition 6 (Column submatrix equality). Given a set of objects A ⊆ G and two attributes m j , m k ∈ M . The submatrix (A, m j ) is equal to (A, m k ), denoted as (A, m j ) (A, m k ), i all rows in (A, m j ) are either entirely identical or entirely opposite to the corresponding rows in (A, m k ). This can be formally written as:

(A, m j ) (A, m k ) ⇐⇒∀g i ∈ A : m j (g i ) = m k (g i ) or ∀g i ∈ A : m j (g i ) = ¬m k (g i ).
Denition 7 (Coherent-sign-changes bicluster). Given a binary dataset (G, M ), a pair (A, B)

(where A ⊆ G, B ⊆ M ) is a coherent-sign-changes bicluster i ∀m j , m k ∈ B : (A, m j ) (A, m k ).

Previous works

Various authors have proposed comparative studies of biclustering in gene expression data [START_REF] Ignatov | Towards a unied taxonomy of biclustering methods[END_REF][START_REF] Madeira | Biclustering algorithms for biological data analysis: a survey[END_REF][START_REF] Padilha | A systematic comparative evaluation of biclustering techniques[END_REF]. In this section, we briey present certain existing methods in the literature that work with some/all the types of biclusters described in the previous section.

Probabilistic and numerical methods

In the numerical biclustering, a bicluster is a submatrix having minimal deviation of their elements. On the other hand, in the probabilistic approaches, biclustering is regarded as a task of nding a submatrix having low possibility to be observed, hence signicant. Some biclustering methods in this category are described below.

Cheng and Church

Cheng and Church [START_REF] Cheng | Biclustering of expression data[END_REF] was among the rst algorithms about biclustering. They work on genecondition expression matrix, where the value of each cell represents the expression level of the corresponding gene in the corresponding condition. Here a bicluster (A, B) is dened as a submatrix having mean squared residue less than a certain threshold δ. A mean squared residue is:

H(A, B) = 1 |A||B| g∈A,m∈B (m(g) -µ(g, B) -µ(A, m) + µ(A, B)) 2 , (2.1)
where µ(A, B) is the mean of a submatrix (A, B). The lowest mean square residue, where H(A, B) = 0 is obtained from a submatrix that corresponds to a constant-value, constantcolumn, constant-row, or additive bicluster. Consequently, if the mean square residue is not zero but is low enough, the submatrix can be regarded as a similar-value, similar-column, similarrow, or relaxed additive bicluster. This bicluster represents a group of genes having similar regulation under a set of conditions.

The authors describe several algorithms that discover a bicluster (A, B) having H(A, B) ≤ δ.

Generally, these algorithms nd biclusters by performing deletions and additions of rows and columns from the whole matrix (G, M ), until the condition H(A, B) ≤ δ is met. The basic method is by performing brute-force approach for each possible row/column addition/deletion, which is not ecient for a large data matrix. The rst algorithm proposed by the author is single node deletion, shown in Algo. 4. It starts from the original matrix (G, M ), and iteratively removes a row or a column that reduces the mean square residue the most. It stops when a submatrix with mean square residue ≤ δ is obtained.

1 Single Node Deletion((G, M ), δ): As the single node deletion removes a row/column one-by-one, it becomes expensive for a larger matrix. The authors also propose the multiple node deletion, where the matrix is signicantly reduced, before applying single node deletion.

2 A = G, B = M 3 while
Furthermore, given a bicluster with H(A, B) ≤ δ, the node addition algorithm was also presented to add rows/columns to obtain a larger bicluster. This algorithm is shown in Algo. 5.

It starts from a bicluster (A, B), then adds a column and a row such that the new mean square residue is not increasing. It also provides a way to add inverted rows (line 1012), which can be regarded as co-regulated genes receiving opposite regulations.

Double k-means

K-means is a method for clustering a set of objects based on their attributes into k cluster. It works by nding a centroid for each cluster, such that the sum of distances between every object and its nearest centroid is minimized. In a given data matrix, k-means can be considered as partitioning the set of rows. with some rows/columns added.

The adaptation of k-means modeling into the task of biclustering is studied in double kmeans [START_REF] Vichi | Double k-means clustering for simultaneous classication of objects and variables[END_REF], where the partitioning is performed on both rows and columns, creating disjoint blocks in the matrix. It implies that for any two rows, their column partitions is the same, although these rows may not be in the same row partition. This limitation is then relaxed in generalized double k-means [START_REF] Rocci | Two-mode multi-partitioning[END_REF], such that two row partitions may have dierent column partitions. Furthermore, the double k-means principle is also studied in creating diagonal coclustering (illustrated in Fig. 2.2) in a sparse matrix [START_REF] Laclau | Hard and fuzzy diagonal co-clustering for document-term partitioning[END_REF].

SAMBA SAMBA [START_REF] Tanay | Discovering statistically signicant biclusters in gene expression data[END_REF] is a numerical method to discover statistically signicant biclusters. It is also applied to gene expression data, by rst constructing a bipartite graph where the vertices on one side correspond to the conditions and the vertices on the other side correspond to the genes. An edge connects a gene g to a condition m if the expression level of g signicantly changes in m.

The task of biclustering is then performed as the task of nding heavy bicliques in the bipartite graph.

The weight of a subgraph H of a bipartite graph B is statistically dened by the probability of the occurrence of a subgraph as dense as H in B. Higher probability means low weight, since a heavy subgraph has a low probability to occur. This weighting scheme is used to discover maximum bounded biclique, where the algorithm supposes that the degree of every gene vertex is bounded.

OPSM

A method for order-preserving biclustering is studied using probabilistic model [START_REF] Ben-Dor | Discovering local structure in gene expression data: the order-preserving submatrix problem[END_REF] where the authors use the term OPSM (order-preserving submatrix). In a numerical dataset (G, M ), an

U (s, k) = |M | • • • (|M | -s + 1) |G| i=k n i 1 s! i 1 - 1 s! (n-i)
.

Non-negative matrix factorization

Non-negative matrix factorization (NMF) of a matrix X is the task of nding two factors of X, called F and G, where X, F , and G contain no negative element. It is formulated as X ≈ F G T , where X ∈ R p×n + , F ∈ R p×k + , and G ∈ R n×k + . Ding et al. [START_REF] Ding | On the equivalence of nonnegative matrix factorization and spectral clustering[END_REF] showed that if the factor G is orthogonal, the NMF:

min F ≥0,G≥0 ||X -F G T || 2 , s.t. G T G = I
is equivalent to K-means clustering. Furthermore, when both factors are orthogonal, the NMF:

min F ≥0,G≥0 ||X -F G T || 2 , s.t. F T F = I, G T G = I
corresponds to simultaneous K-means clustering of rows and columns of X, also known as coclustering in analyzing a dataset of textual documents.

The constraint that the factors should be orthogonal is also studied in non-negative matrix tri-factorization (NMTF) [START_REF] Ding | Orthogonal nonnegative matrix t-factorizations for clustering[END_REF]. This bi-orthogonal NMTF is able to simultaneuosly cluster documents and terms in various document-term binary matrices. The applications on text datasets are further studied by incorporating the semantic relationship among words [START_REF] Salah | Word co-occurrence regularized non-negative matrix trifactorization for text data co-clustering[END_REF], or the geometric structures of rows and columns [6].

FABIA FABIA, stands for Factor Analysis for Bicluster Acquisition [START_REF] Hochreiter | FABIA: Factor analysis for bicluster acquisition[END_REF], is a numerical method focused in nding multiplicative biclusters in a gene expression dataset. Here a bicluster is dened as a submatrix where the rows are similar to each other on the columns and vice versa. A multiplicative bicluster can be regarded as the result of matrix multiplication between a column matrix λ and a row matrix z T , as illustrated in Fig. 2.1. Therefore, biclustering is formulated as sparse matrix factorization. HOCCLUS HOCCLUS [START_REF] Pio | Hierarchical and overlapping co-clustering of mrna: mirna interactions[END_REF] is an algorithm that discover hierarchical and overlapping biclusters/co-clusters on mRNA:miRNA interaction datasets. Similar to SAMBA, HOCCLUS represents the interaction as a bipartite graph, with the vertices for mRNAs on one side and vertices for miRNAs on the other side. An edge connects an mRNA to an miRNA, with the interaction value as the edge's weight. HOCCLUS uses METIS [START_REF] Karypis | A fast and high quality multilevel scheme for partitioning irregular graphs[END_REF] to mine initial non-hierarchical and non-overlapping biclusters from the bipartite graph. From these initial biclusters, HOCCLUS generates hierarchical organization among them. Then the algorithm detects possible overlapping between two biclusters in a same hierarchical level by identifying objects in one bicluster that can be added to another bicluster. These overlaps are used to decide whether two biclusters should be merged.

× × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × ×
The METIS approach used in HOCCLUS can mine bicluster from a subgraph that is not biclique, giving the possibility that some biclusters from bicliques are not extracted. It also needs a number of biclusters as a user-dened parameter. HOCCLUS2 [START_REF] Pio | A novel biclustering algorithm for the discovery of meaningful biological correlations between microRNAs and their target genes[END_REF] is an improvement of HOCCLUS, where instead of METIS, a new approach is proposed to mine biclusters from overlapping bicliques without the needs of supplying the number of biclusters. In addition, a ranking of extracted biclusters is generated, based on their signicance. The biclusters from HOCCLUS2 (and some data from several other classication algorithms) are stored in a webbased database called ComiRNet [START_REF] Pio | ComiRNet: a web-based system for the analysis of miRNA-gene regulatory networks[END_REF].

CoClus

CoClus [START_REF] Ailem | Graph modularity maximization as an eective method for co-clustering text data[END_REF] is an algorithm that performs block diagonal clustering in text data. Block diagonal clustering simultaneously groups rows and columns by applying permutations on them, and as a result a block diagonal matrix (illustrated in Fig. 2.2) is produced. CoClus perform this block diagonal clustering by adapting and maximizing modularity criterion, which is originally a measure in graph clustering.

SBB

An algorithm called Similarity Based Biclustering (SBB) [START_REF] Hussain | Biclustering of human cancer microarray data using cosimilarity based co-clustering[END_REF] was proposed to discover similarvalue biclusters in human cancer microarray data. This method is based on the concept of co-similarity among genes and conditions. In a matrix A, where a xy is the element of A in row

x and column y, SBB uses χ-Sim that denes the similarity between two genes i and j as:

sr ij = k l a ik • a jl • sc kl ,
where sc kl is the similarity between two conditions k and l. This condition similarity, in turn, is formulated as:

sc kl = i j a ik • a jl • sr ij .
The matrices SR and SC are iteratively computed by updating SC (or SR respectively). These computations is related to biclustering since two genes i and j are similar if sr ij is high, meaning that they exhibits same kind of behavior under similar conditions (given by SC).

After the computation of SR and SC, these matrices are used as similarity measures to cluster rows and columns separately using hierarchical clustering. Then, a bicluster can be extracted from each pair of row cluster and column cluster. The utilization of hierarchical clustering in SBB means that the generated biclusters are not overlapping.

Pattern-based methods

In pattern-based biclusterings, a bicluster is regarded as samples sharing a common pattern.

These approaches generally compute neither similarity measure to group rows or columns nor signicance score of a bicluster. Some methods included in this approach are described below.

Object-attribute biclustering

Standard FCA where the context is a binary matrix discovers formal concepts which can be regarded as a constant-value bicluster. The problem that the number of concepts is large is studied in dense object-attribute (oa) biclustering [START_REF] Ignatov | Concept-based biclustering for internet advertisement[END_REF], applied to a dataset of internet advertisement.

From this dataset, a formal context (G, M, I) is created, with G is the set of rms, M is the set of advertising terms, and (g, m) ∈ I means that the rm g bought the term m. An oa-biclusters is dened as a submatrix (m , g ) where (g, m) ∈ I. This methods works on the notion of dense oa-bicluster, which is a submatrix (m , g

) whose density ρ = |I ∩ (m × g )|/(|m | • |g |) satises
a user-dened threshold. Therefore, oa-bicluster can be considered as a relaxation of formal concept, based on the fact that an oa-bicluster is a rectangle densely composed of 1s, while a formal concept is a rectangle fully composed of 1s.

BicPAM

BicPAM is a family of pattern-based biclustering, was rst proposed in [START_REF] Henriques | BicPAM: Pattern-based biclustering for biomedical data analysis[END_REF]. Working in a gene-condition expression matrix, it is able to discover constant, additive, multiplicative, or symmetrical biclusters. This approach can detect overlapping biclusters, and also handle missing values and noises.

The whole process of BicPAM can be summarized in three steps: mapping, mining, and closing. In mapping step, normalization and discretization were carried out. Normalization, which means having zero-mean value, allows for symmetries in biclusters. Discretization, although may cause loss of information, could address the noise problem, and to reduce the complexity since an exhaustive biclustering is expected. Three discretization options are studied: xed range, equal bin, or by statistically calculating cuto points. G m 1 m 2 m 3 m 4 m 5 g 1 -1 -3 -6 -6 -3

1 g 4 8 2
-6 -6

1 g 5 8 3
-6 -2

1 1 (a) G itemset g 1 {m -1 1 , m -3 2 , m -6 3 , m 5 4 , m 7 5 } g 2 {m -2 1 , m -4 2 , m 10 3 , m 4 4 , m 6 5 } g 3 {m 4 1 , m 1 2 , m -6 3 , m -3 4 , m 1 5 } g 4 {m 8 1 , m 2 2 , m -6 3 , m -6 4 , m 1 5 } g 5 {m 8 1 , m 3 2 , m -6 3 , m 1 4 , m 1 5 } (b)
1 5 g 4 8 2
-6 -6

1 g 5 8 3 -6 1 1 (a)
G m 1 m 2 m 3 m 4 m 5 g 1 -4 -1

3 g 4 9 3
-5 -5

2 g 5 8 3
-6

1 1 (b)
The mining step is the main part, where biclusters are discovered. Among other patternbased mining, BicPAM uses frequent itemsets as default. First, the algorithm decides whether alignments are needed, based on the type of bicluster. For constant-column biclustering, the alignment is not executed. Then, the mapped matrix is transformed into a kind of transaction database, where each object is represented by an itemset. This transformation is illustrated in Table 2.2. A constant-column bicluster can be found in a frequent itemset. From Table 2.2b, we can nd a frequent itemset {m -6 3 , m 1 5 } for example, supported by g 3 , g 4 , and g 5 . This itemset corresponds to bicluster ({g 3 , g 4 , g 5 }, {m 3 , m 5 }) in Table 2.2a. The itemset mining is executed using existing algorithms: F2G [START_REF] Henriques | F2G: Ecient discovery of full-patterns[END_REF], Charm [START_REF] Zaki | Ecient algorithms for mining closed itemsets and their lattice structure[END_REF], or AprioriTID [START_REF] Agrawal | Fast algorithms for mining association rules[END_REF] among others.

On the other hand, for additive, multiplicative, and symmetrical biclustering, BicPAM applies column alignments to the mapped matrix before transforming it into a transaction dataset (the alignment is the default option, BicPAM also proposes local normalization). The column alignments for additive biclustering are illustrated in Table 2.3. For a given column m j , the maximum value x is calculated. Then, for each row g i , the value x -m j (g i ) is added to all of its values.

Consider Table 2.3a, the result of alignment of m 1 from Table 2.2a. The maximum value of m 1 is 8. Therefore, for the whole row of g 1 , the value 8 -m 1 (g 1 ) = 8 -(-1) = 9 is added. This additive alignment of m 1 results in m 1 having a single value. Then, similar to constantcolumn biclustering, this aligned matrix is transformed into a transaction dataset, and frequent itemsets are mined. From Table 2.3a, an itemset {m 8 1 , m 6 2 , m 14 4 , m 16 5 } is found, supported by rows g 1 and g 2 . This itemset corresponds to the additive bicluster ({g 1 , g 2 }, {m 1 , m 2 , m 4 , m 5 }). The alignment, transformation to transaction dataset, and itemset mining are done for every column.

The column alignments for multiplicative biclustering, illustrated in Table 2.4, are similar to the additive alignments. Here the objective is having a column with constancy by multiplying each row. Consider the multiplicative alignment of m 1 in Table 2.2a. The least common multiple of all values in m 1 is 8, so each row is multiplied such that the values of m 1 are constant. This

G Sequence g 1 {m 3 }, {m 2 }, {m 1 }, {m 4 }, {m 5 } g 2 {m 2 }, {m 1 }, {m 4 }, {m 5 }, {m 3 } g 3 {m 3 }, {m 4 }, {m 2 , m 5 }, {m 1 } g 4 {m 3 , m 4 }, {m 5 }, {m 2 }, {m 1 } g 5 {m 3 }, {m 4 , m 5 }, {m 2 }, {m 1 } results in Table 2.4a.
The closing step is a post-processing step in BicPAM. The rst part of this step is extension of biclusters. It allows the enlargement of discovered biclusters under some homogeneity criteria.

The second part is bicluster merging, which combines some biclusters having many shared rows and columns. The last part is the ltering, where some biclusters that are contained in another larger biclusters are discarded. In this part, it is also possible to remove some rows or columns of a bicluster such that the resulting smaller bicluster is more homogeneous.

The authors of BicPAM also propose a pattern-based method for order-preserving biclustering, namely BicSPAM [START_REF] Henriques | BicSPAM: exible biclustering using sequential patterns[END_REF], based on the fact that order-preserving biclustering is related to sequential pattern mining. Similar to BicPAM, in BicSPAM a numerical matrix is transformed into transaction dataset. Here an object corresponds to a transaction which is a sequence of itemsets, illustrated in Table 2.5. A mining step in this table results in a sequence {m 2 }, {m 1 }, {m 4 }, {m 5 } for example, supported by rows g 1 and g 2 . This is then regarded as an order-preserving bicluster ({g 1 , g 2 }, {m 1 , m 2 , m 4 , m 5 }).

Furthermore, several other methods related to BicPAM were also proposed. BicNET [START_REF] Henriques | BicNET: Flexible module discovery in large-scale biological networks using biclustering[END_REF] is a biclustering approach for a biological networks, where the dataset can be represented as a bipartite graph. Bic2PAM [START_REF] Henriques | BiC2PAM: constraint-guided biclustering for biological data analysis with domain knowledge[END_REF] is a constrained biclustering, where background knowledge can be incorporated. In addition, these biclustering approaches are implemented in BicPAMS [START_REF] Henriques | BicPAMS: software for biological data analysis with pattern-based biclustering[END_REF].

Contiguous OPSM

Xue et al. [START_REF] Xue | A biclustering algorithm with coherent evolution on the contiguous columns facing time-series gene data[END_REF][START_REF] Xue | A new approach for the deep order preserving submatrix problem based on sequential pattern mining[END_REF] presented an algorithm to discover order-preserving biclusters (or OPSM:

order-preserving submatrix) from a gene expression data. This algorithm denes an OPSM as slightly dierent to Def. 4. Instead of any subset of columns, contiguous OPSM means that the expected bicluster should have columns that are contiguous in the original matrix. Then, similar

to BicSPAM [START_REF] Henriques | BicSPAM: exible biclustering using sequential patterns[END_REF], the problem of nding contiguous OPSM is translated as sequential pattern mining.

m 1 m 2 m 3 m 4 g 1 × × × + × = m 1 m 2 m 3 m 4 g 3 × × × g 1 × × × × g 4 × × × × g 4 × × × × g 6 × × ×

RIn-Close

RIn-Close [START_REF] Veroneze | Enumerating all maximal biclusters in numerical datasets[END_REF] is a family of algorithms that enumerates all maximal biclusters based on FCA.

A formal concept in FCA corresponds to a constant-value bicluster of ones in a binary matrix.

Therefore, In-Close2 algorithm [START_REF] Andrews | In-Close2, a high performance formal concept miner[END_REF], that enumerates all concepts in a formal context, can be regarded as an algorithm to discover constant-value biclusters. RIn-Close is an adaptation of this algorithm such that it can also discover constant-column, additive, and multiplicative biclusters.

RIn-Close_CVC_P and RIn-Close_CVC are the algorithms to mine constant-column and similar-column biclusters respectively. In the exploration tree of In-Close2, a child node is generated by intersecting the set of objects of the added attribute with the current extent. Consider InClose2 works for binary matrix, and a successor is generated by intersecting the extent of the current concept with the extent of the new attribute. On the other hand, RIn-Close_CVC_P works for numerical matrices, and it can generate many successors from the addition of a single attribute. It is designed to obtain constant-column biclusters. Consider Fig. 2.4 where the current node is a constant-column bicluster ({g

1 , g 3 , g 4 , g 6 }, {m 1 , m 2 , m 3 }). Then, the at- tribute m 4 is added, creating two new constant-column biclusters ({g 1 , g 4 }, {m 1 , m 2 , m 3 , m 4 }) and ({g 3 , g 6 }, {m 1 , m 2 , m 3 , m 4 }).
Furthermore, the RIn-Close_CVC_P can be relaxed such that the similar-column biclusters can be obtained. This relaxation is called RIn-Close_CVC. Similar to RIn-Close_CVC_P, this algorithm generates multiple successors from the addition of a single attribute. The dierence is that the successors generated by RIn-Close_CVC can have object overlaps among them, due to the nature of similar-column biclusters.

To discover additive and multiplicative biclusters, the algorithms RIn-Close_CHV_P and RIn-Close_CHV were proposed to mine perfect and non-perfect bicluster respectively. RIn-Close_CHV_P is similar to RIn-Close_CVC_P in the sense that they both generate multiple successors from the addition of a single attribute. The dierence lies in how an extent is constructed. Consider again Fig. 2.4. In RIn-Close_CVC_P, g 1 and g 4 are grouped together since they have the same value in m 4 . On the other hand, in RIn-Close_CHV_P, the algorithms looks at the dierence (additive or multiplicative) between the new attribute and the existing attributes. For example, in Fig. 2.5 where m 4 is added, g 1 and g 2 are grouped together

m 1 m 2 m 3 m 4 m 1 m 2 m 3 m 4 g 1 1 2 0 + 4 = g 1 1 2 0 4 g 2 3 4 2 6 g 2 3 4 2 6 g 3 2 3 1 4 g 3 2
m 4 (g 1 ) -m 1 (g 1 ) = m 4 (g 2 ) -m 1 (g 2 ).
RIn-Close_CHV was proposed to discover non-perfect additive or multiplicative biclusters.

From a numerical matrix, this algorithm creates an augmentation matrix and applies similarcolumn biclustering in the augmented matrix. The augmentation process was designed from the observation that in an additive bicluster, every pair of columns has a constant dierence. Therefore, by calculating the dierence of every column pair, we can nd some constant dierences that can be regarded as an additive bicluster.

Consider Table 2.6 as the numerical matrix where we want to discover additive biclusters.

RIn-Close_CHV rst generates the augmentation of this matrix, shown in Table 2.7, where the dierence for every pair of attributes in Table 2.6 is calculated. In this augmented matrix, a similar-column bicluster ({g 1 , g 2 , g 3 , g 4 }, {m 1 -m 2 , m 1 -m 4 , m 2 -m 4 }) can be obtained using RIn-Close_CVC. This corresponds to the additive bicluster ({g 1 , g 2 , g 3 , g 4 }, {m 1 , m 2 , m 4 }) in the original numerical matrix.

Conclusion

Currently, the literature about biclustering is signicantly rich. Biclustering is mainly used in biological domain, while there are also signicant number of applications in text mining and recommendation systems. However, in biological domain, many authors are interested to nd overlapping biclusters which reect, for example, that a condition can participate in regulating multiple sets of genes. Meanwhile in text mining domain where the term co-clustering is more frequent the biclustering is considered as simultaneous partitioning of rows and columns, Table 2.7: The augmentation of the matrix in Table 2.6.

m 1 -m 2 m 1 -m 3 m 1 -m 4 m 2 -m 3 m 2 -m 4 m 3 -m 4 g 1 -1 -2 -3 -1 -2 -1 g 2 -1 3 -3 4 -2 -6 g 3 -1 -4 -3 -3 -2 1 g 4 -1 0 -3 1 -2 -3
indicating the absence of overlaps.

In the biclustering with overlaps, the number of biclusters that exist in a matrix can be enormous. Many approaches then study the problem of nding signicant biclusters, which are submatrices fullling certain thresholds about their size, probability, density, cohesiveness, etc.

In Chapter 3 and 4 of this thesis, we examine the problem of bicluster enumeration, i.e.

retrieving all biclusters in a data matrix, using FCA. FCA is related to biclustering, in the sense that both of them discover a submatrix showing a regularity among its cells. Moreover, there exist several algorithms that deal with the task of concept enumeration in FCA, which can be adapted to enumerate biclusters. We consider this approach as pattern based, since it translates the biclustering task into pattern mining.

FCA is previously used in enumerating biclusters [START_REF] Veroneze | Enumerating all maximal biclusters in numerical datasets[END_REF] by modifying a concept enumeration algorithm. In this thesis, we extend FCA into pattern structures that deals with numerical matrix. In this way, we also study the potential of building a unied framework of discovering various types of biclusters in a binary and/or numerical matrix.

Chapter 3

Biclustering with partition pattern structures The task of constant-column biclustering was studied using partition pattern structures [START_REF] Codocedo | Lattice-based biclustering using partition pattern structures[END_REF],

an extension of FCA. In this chapter, we explore the possibility of extending this approach for other types of biclusters. First we revisit the basic denitions of partition pattern structures in Sect. 3.1 and its application to constant-column biclustering in Sect. 3.2. Then, we explain the usability of partition pattern structures to additive and multiplicative biclustering in Sect. 3.3, order-preserving biclustering in Sect. 3.4, and coherent-sign-changes biclustering in Sect. 3.5.

Lastly, we give the conclusion and some insights for future research in Sect. 3.6.

The pattern structures of partitions

Partition

In a given set S, a partition d is a splitting of S into components {c 1 , • • • , c n }, such that all components cover all elements in S and there is no overlap between any two components, or:

c i ∈d c i = S and c i ∩ c j = ∅ whenever i = j. {{1, 2, 3}} {{1, 2}, {3}} {{1, 3}, {2}} {{1}, {2.3}} {{1}, {2}, {3}} Figure 3.1:
The lattice of all possible partition of a set {1, 2, 3}.

c i ∈ d 1 c j ∈ d 2 c i ∩ c j {1, 2} {1, 3} {1} {1, 2} {2} {2} {3} {1, 3} {3} {3} {2} ∅ c i ∩ c j {{1}, {2}, {3}}
∀c j ∈ d 2 ∃c i ∈ d 1 , c j ⊆ c i . For example, d 1 = {{1, 2, 3}, {4}} is a coarsening of d 2 = {{1, 2}, {3}, {4}} since the component {1, 2, 3} in d 1 is the union of {1, 2} and {3} in d 2 .
Consequently, the partition d 2 is called a renement of d 1 .

The coarsening and renement among partitions give an order among them. A ner partition is subsumed by ( ) its coarser partition(s). In the previous example, d 2 d 1 . This makes D, the set of all possible partitions of a set S, is partially ordered, where its lattice can be depicted in a line diagram. For example, the lattice of all possible partitions of a set {1, 2, 3} is illustrated as the Hasse diagram in Fig. 3.1. Furthermore, the set D is a complete lattice, where the meet and join exist for all subsets of D. The meet ( ) of two partitions is their coarsest common renement. It is dened as the set of intersections of every pair c i ∈ d 1 and c j ∈ d 2 , formulated as: The join ( ) of two partitions is their nest common coarsening, dened as:

d 1 d 2 = c i ∩ c j . ( 3
d 1 d 2 =   p i ∩p j =∅ p i ∪ p j   + ,
where (.) + is an operator that conserves only the maximal components in d, i.e. the components 3.1. The pattern structures of partitions [START_REF] Codocedo | Lattice-based biclustering using partition pattern structures[END_REF].

c i ∈ d 1 c j ∈ d 2 c i ∪ c j {1, 2} {1, 3} {1, 2, 3} {1, 2} {2} {1, 2} {3} {1, 3} {1, 3} {3} {2} - c i ∪ c j {{1, 2, 3}, {1, 2}, {1, 3}} ( c i ∪ c j ) + {{1, 2, 3}}
m 1 m 2 m 3 m 4 m 5 g 1 1 1 1 1 6 g 2 1 1 1 1 6 g 3 1 1 1 6 6 g 4 8 8 1 6 6
that are not proper subsets of another component. It is dened as:

d + = {c i ∈ d| c ∈ d, c i ⊆ c}.
Using the previous example with d 1 and d 2 , the join of these two partitions is

d 1 d 2 = {{1, 2, 3}}, whose computation is illustrated in Fig. 3.3.
The subsumption relation where coarser partition subsumes ner partition can also be dened using the meet operator as:

d 2 d 1 ⇐⇒ d 2 d 1 = d 2 , (3.2)
meaning that if d 2 is the meet between d 1 and d 2 , then d 2 is a renement of d 1 .

Partition of objects

In a numerical matrix (G, M ), we can nd a partition of objects/rows based on their values across all attributes/columns or vice versa. For example, in Table 3.1, the set of objects are partitioned as {{g 1 , g 2 }, {g 3 , g 4 }} according to m 4 .

The partition of objects according to an attribute can be obtained using equivalence relation.

An equivalence relation for every g ∈ G w.r.t. an attribute is dened as follows:

[g i ] m j = {g k ∈ G|m j (g i ) = m j (g k )}. (3.3)
The [g i ] m j relation returns all objects in G whose value in m j is the same as g i 's value in m j . For example, in Table 3.

1 [g 1 ] m 4 = {g 1 , g 2 }.
A partition of objects according to an attribute can be obtained from the equivalence relation.

A function δ : M → D maps an attribute to an object partition as follows:

δ(m j ) = {[g i ] m j |∀g i ∈ G}. Therefore, in Table 3.1, δ(m 4 ) = {[g 1 ] m 4 , [g 2 ] m 4 , [g 3 ] m 4 , [g 4 ] m 4 }, which is equal to {{g 1 , g 2 }, {g 3 , g 4 }}. {m 1 , m 2 , m 3 , m 4 , m 5 } {{g 1 , g 2 }, {g 3 }, {g 4 }} {m 1 , m 2 , m 3 , m 5 } {{g 1 , g 2 , g 3 }, {g 4 }} {m 3 , m 4 , m 5 } {{g 1 , g 2 }, {g 3 , g 4 }} {m 3 , m 5 } {{g 1 , g 2 , g 3 , g 4 }} Figure 3.4:
The lattice of all partition pattern concepts of Table 3.1.

Partition pattern structures

As explained in Sect. 1.4, pattern structures are generalizations of FCA, where each object is described by a complex structure. A pattern structure is dened by the triple (G, (D, ), δ), where (D, ) is a lattice of descriptions D with as the similarity operator or the meet between two partitions, and δ : G → D maps an object to its description. Previously in Sect. 3.1 is

({m 3 , m 4 , m 5 }, {{g 1 , g 2 }, {g 3 , g 4 }}).
The set of all pp-concepts in a given matrix is a complete lattice. Following the ordering of formal concepts in Eq. 1.3, the order among pp-concepts is given by relation:

(B 1 , d 1 ) ≤ (B 2 , d 2 ) ⇐⇒ B 1 ⊆ B 2 (dually d 2 d 1 ).
The lattice of pp-concepts from Table 3.1 is illustrated as the Hasse diagram in Fig. 3.4.

Constant-column biclustering

In a matrix, a constant-column bicluster is a submatrix (A ⊆ G, B ⊆ M ) where each column has a constant value across all rows. An example of a constant-column bicluster in Table 3.1 is the submatrix ({g 3 , g 4 }, {m 3 , m 4 , m 5 }).

Additive and multiplicative biclustering

{m 3 , m 5 } {{g 1 , g 2 , g 3 , g 4 }} ({g 1 , g 2 , g 3 , g 4 }, {m 3 , m 5 }) yes {m 1 , m 2 , m 3 , m 5 } {{g 1 , g 2 , g 3 }, {g 4 }} ({g 1 , g 2 , g 3 }, {m 1 , m 2 , m 3 , m 5 }) yes ({g 4 }, {m 1 , m 2 , m 3 , m 5 }) no {m 3 , m 4 , m 5 } {{g 1 , g 2 }, {g 3 , g 4 }} ({g 1 , g 2 }, {m 3 , m 4 , m 5 }) no ({g 3 , g 4 }, {m 3 , m 4 , m 5 }) yes {m 1 , m 2 , m 3 , m 4 , m 5 } {{g 1 , g 2 }, {g 3 }, {g 4 }} ({g 1 , g 2 }, {m 1 , m 2 , m 3 , m 4 , m 5 }) yes ({g 3 }, {m 1 , m 2 , m 3 , m 4 , m 5 }) yes ({g 4 }, {m 1 , m 2 , m 3 , m 4 , m 5 })
yes Partition pattern structures was proposed in [START_REF] Codocedo | Lattice-based biclustering using partition pattern structures[END_REF] to discover constant-column biclusters in a numerical matrix. This is possible since the equivalence relation in Eq. • ({g 1 , g 2 }, {m 3 , m 4 , m 5 }), and

• ({g 3 , g 4 }, {m 3 , m 4 , m 5 }).
Therefore, in any pp-concept (B, d), any pair (c ∈ d, B) is a constant-column bicluster.

It should be noted that these biclusters are not necessarily maximal, means that they can be found inside another larger bicluster. The constant-column bicluster b 1 = ({g 1 , g 2 }, {m 3 , m 4 , m 5 }) for example, is not maximal since it is part of the bicluster b 2 = ({g 1 , g 2 }, {m 1 , m 2 , m 3 , m 4 , m 5 }).

However, this maximality can be veried by inspecting the concept lattice. Consider the concept lattice in Fig. 3.4. We can see that b 1 is found in the concept ({m 3 , m 4 , m 5 }, {{g 1 , g 2 }, {g 3 , g 4 }}), which is a descendant of the concept ({m 1 , m 2 , m 3 , m 4 , m 5 }, {{g 1 , g 2 }, {g 3 , g 4 }}). Since this higher concept also contains a bicluster with {g 1 , g 2 }, we can conclude that b 1 is not maximal. More formally, given two pp-concepts

(B 1 , d 1 ) and (B 2 , d 2 ) such that (B 1 , d 1 ) ≤ (B 2 , d 2 ), the bicluster (c ∈ d 1 , B 1 ) is maximal if c ∈ d 2 .
All pp-concepts and their corresponding biclusters are listed in Table 3.2.

In the subsequent sections in this chapter, we show that partition pattern structures can be adapted to discover other bicluster types.

Additive and multiplicative biclustering

For additive and multiplicative biclusters, we introduce the notion of marked objects. A marked object g * is an object g associated to a mark * , where * ∈ R.

Slightly dierent from partition pattern structures in Sect. 3.1.3, here the function δ : M → D maps an attribute to an object partition, which is composed by only one component with a mark for each object. For example, from Table 3.3: -6 -3

δ(m 1 ) = {{g -1 1 , g -2 2 , g
1 g 4 8 2
-6 -6

1 g 5 8 3
-6

1 1
Any two components are regarded as equal i the marks of their objects are coherent. For additive and multiplicative biclustering, two components are equal i the marks of one component can be obtained by adding (or multiplying, resp.) a unique value to all marks of the other components. For example: The similarity operator of any two components also depends on the bicluster that we want to discover. In general, this operator groups objects according to the coherency explained before.

{g 3 1 , g 7 2 } = {g 6 1 , g
For additive biclustering, the similarity operator is written as ∩ A . From two components c 1 and c 2 , ∩ A groups together all objects according to the dierence from both components. For example, if c 1 = {g 2 1 , g 3 2 , g 4 3 , g 5 4 } and c 2 = {g 5 1 , g 7 2 , g 7 3 , g 9 4 }, then c 1 ∩ A c 2 = {{g 2 1 , g 4 3 }, {g 3 2 , g 5 4 }}. This is because the marks of g 1 and g 3 in c 2 are their mark in c 1 plus 3, while the marks of g 2 and g 4 in c 2 are their mark in c 1 plus 4. The similarity operator for this bicluster is similar to Eq. 3.1, with the adjustment in the similarity between components:

d 1 d 2 = c i ∈d 1 ,c j ∈d 2 c i ∩ A c j . (3.5)
The component similarity operator for multiplicative biclustering (written as ∩ M ) is related to ∩ A . Here the objects are grouped according to the multiplicative dierence between two components. For example, if

c 1 = {g 2 1 , g 3 2 , g 4 3 , g 5 4 } and c 2 = {g 4 1 , g 9 2 , g 8 3 , g 15 4 }, then c 1 ∩ A c 2 = {{g 2 1 , g 4 3 }, {g 3 2 , g 5 4 }}
. This is because the mark of g 1 and g 3 in c 2 is twice of their mark in c 1 , while the mark of g 2 and g 4 in c 2 is three times of their mark in c 1 . The for this biclustering is:

d 1 d 2 = c i ∈d 1 ,c j ∈d 2 c i ∩ M c j . (3.6)
We can see in Eq. 3.5 and 3.6 that the operator for these three biclustering are similar, the dierence lies in the similarity between two components (∩ A and ∩ M ). For those types of biclustering, the order between any two partitions is also the same as Eq. 3.2 for constant-column biclustering:

d 1 d 2 ⇐⇒ d 1 d 2 = d 1 .
(3.7)

Order-preserving biclustering

Order-preserving (OP) biclustering was studied in gene expression data [START_REF] Ben-Dor | Discovering local structure in gene expression data: the order-preserving submatrix problem[END_REF][START_REF] Henriques | BicSPAM: exible biclustering using sequential patterns[END_REF][START_REF] Xue | A biclustering algorithm with coherent evolution on the contiguous columns facing time-series gene data[END_REF][START_REF] Xue | A new approach for the deep order preserving submatrix problem based on sequential pattern mining[END_REF]. This type of bicluster may represent a set of conditions which are dierent stages in the progress of a disease, and the expression levels of the genes show the same tendency (raising or falling) across these stages.

OP biclusters are also useful in the domain of recommendation systems. Given a user-item rating matrix, with U as the set of previous users and I as the set of items, one approach for producing a suggestion for a new user is by retrieving a set of similar users in U . From a dataset of item ratings, we can interpret u 1 ∈ U as similar to u 2 ∈ U if they have similar order of preference. For example, suppose that rating(u x , i y ) is the rating given by user u x ∈ U to item i y ∈ I. We can consider that u 1 is similar to u 2 if rating(u 1 , i 1 ) > rating(u 1 , i 2 ) and rating(u 2 , i 1 ) > rating(u 2 , i 2 ) (i.e. both of them prefer i 1 over i 2 ). Furthermore, their similarity is stronger if they give similar rating order over a larger set of items, e.g. if rating(u

1 , i 1 ) > rating(u 1 , i 2 ) > • • • > rating(u 1 , i 10 ) and rating(u 2 , i 1 ) > rating(u 2 , i 2 ) > • • • > rating(u 2 , i 10 ).

Pattern structures for OP biclustering

Consider the dataset given by Table 3.4, with the set of attributes G = {g 1 , g 2 , g 3 , g 4 , g 5 }. For the task of nding OP biclusters, we introduce the notation r x y as a pair of attributes m x and m y , x < y, and R is the set of all possible r x y . That is, from n attributes, there will be n 2 pairs. First, we introduce [g i ] r y x , an equivalence relation of an object w.r.t. a pair of attribute (instead of w.r.t a single attribute as in Eq. 3.3). It groups objects whose behavior in m x and m y is similar (either m x (g) > m y (g) or m x (g) < m y (g)), dened as:

[g i ] r x y = {g k ∈ G| arg max j (m j (g i )) = arg max j (m j (g k )), j ∈ {x, y}}.
({r 1 2 , r 1 3 , r 1 5 , r 2 3 , r 4 5 }, {{g 1 , g 3 }, {g 2 , g 4 }, {g 5 }}).
Example from Table 3.4:

[g 1 ] r 1 2 = [g 3 ] r 1 2 = {g 1 , g 3 }, [g 2 ] r 1 2 = [g 4 ] r 1 2 = [g 5 ] r 1 2 = {g 2 , g 4 , g 5 }.
Using this equivalence relation, we dene the function δ : R → D as:

δ(r x y ) = {[g i ] r x y |g i ∈ G}. (3.9)
In other words, δ maps a pair of attributes to a partition according to the pair's comparison. For example, δ(r 1 2 ) = {{g 1 , g 3 }, {g 2 , g 4 , g 5 }} because m 2 > m 1 for g 1 and g 3 ; and m 1 > m 2 for g 2 , g 4 , and g 5 . Some pairs and their partitions are listed in Table 3.5.

Given a set of attribute pairs R, a set of partitions D, and the mapping function δ, a partition pattern structure for nding OP biclusters is determined by the triple (R, (D, ), δ). A concept is a pair (B, d) such that B = d and d = B, where:

B = r∈B δ(r) B ⊆ R, d = {r ∈ R|d δ(r)} d ∈ D.
The meet and subsumption relation between two partitions follow Eq. 3.1 and Eq. 3.2 respectively.

Here, the extent of a concept is a set of attribute pairs. Consider the concept pc 1 with extent {r 1 2 , r 1 3 , r 1 5 , r 2 3 , r 4 5 } and intent {{g 1 , g 3 }, {g 5 }, {g 2 , g 4 }}. Its extent can be depicted as a graph, illustrated in Fig. 3.5, where a vertex represents an attribute in a pair r, and an edge connects two attributes m j and m k if there is r j k in the extent. For example, r 1 2 makes the connection between m 1 and m 2 .

An OP bicluster can be obtained from a clique of this extent graph. The clique is important to ensure the order preservation among attributes. This is because r x y and r x z only may mean that x < y and x < z, but we can not say the relation among y and z unless we have r y z . The set {m 1 , m 2 , m 3 }, {m 1 , m 5 }, or {m 4 , m 5 } is an example of clique in the extent graph in Fig. 3.5.

In a concept (B, d), any pair (c, q) is an OP bicluster where c ∈ d is a set of objects and q is a set of attributes that forms a clique in the graph of B. For example, from pc 1 which has 3 partition components and 3 cliques, we can obtain 9 OP biclusters. The biclusters having more than two columns are:

• ({g 1 , g 3 }, {m 1 , m 2 , m 3 }), which follows m 1 < m 2 < m 3 ; • ({g 2 , g 4 }, {m 1 , m 2 , m 3 }), which follows m 3 < m 2 < m 1 ; and • ({g 5 }, {m 1 , m 2 , m 3 }), which follows m 2 < m 1 < m 3 .

Experiments

OP biclustering is related to sequential pattern mining, and some approaches have studied sequential pattern mining algorithms for this biclustering [START_REF] Henriques | BicSPAM: exible biclustering using sequential patterns[END_REF][START_REF] Xue | A biclustering algorithm with coherent evolution on the contiguous columns facing time-series gene data[END_REF][START_REF] Xue | A new approach for the deep order preserving submatrix problem based on sequential pattern mining[END_REF]. FCA has been generalized to have a sequence of itemset as description of objects [START_REF] Buzmakov | On mining complex sequential data by means of FCA and pattern structures[END_REF][START_REF] Codocedo | A proposition for sequence mining using pattern structures[END_REF] (will be explained in this thesis later in Chapter 5).

In this thesis, we rst compare the runtime of the two methods for nding OP bicluster: partition pattern structure (pps) and sequence pattern structure (sps), both using AddIntent algorithm to generate all concepts and the corresponding lattice. Randomly generated matrices are used, where the value of each cell is between 1 and 100 following uniform distribution. We inspect the eect of the number of attributes on both methods, and we choose a small number of objects [START_REF] Ayres | Sequential pattern mining using a bitmap representation[END_REF].

The comparison of runtime are shown in Figure 3.6. It is shown that the execution time of partition-based mining of OP biclusters grows faster than sequence-based. Using partition pattern structure, from an m × n numerical matrix, a new m × n 2 matrix is generated to compare every pair of columns. The partition is then performed in the new matrix. In this second approach, an m × n matrix is converted to a set of m sequences, each of them has n items. The rst approach is more complex than the second, since the rst creates a larger matrix before applying partition pattern structure.

We tested the pps-based approach to breast cancer dataset [START_REF] Hedenfalk | Gene-expression proles in hereditary breast cancer[END_REF]. This dataset has 3226 rows (genes) and 21 columns (tissues). As shown in Table 3.6, these 21 tissues are composed by 7 brca1 mutations, 8 brca2 mutations, and 6 sporadic breast cancers. Since it has 21 columns, the pps-based approach will convert the dataset into a 3226 × 21 2 = 3226 × 210 matrix. In order to reduce the computational complexity, we introduce a parameter θ. In calculation of the intent of any partition pattern concept, any partition component having the number of elements less than θ is discarded. For example, with θ = 3, the partition {{a, b, c}, {d, e}} becomes {{a, b, c}}.

The number of concepts can be very large, so we provides the runtime until 10K concepts are obtained.

Table 3.6: The columns in the breast cancer dataset in [START_REF] Hedenfalk | Gene-expression proles in hereditary breast cancer[END_REF]. The result of experiment with varying θ is shown in Fig. 3.7. Here we see that in general, larger θ means more time to obtain 10K concepts. However, it does not necessarily mean that larger θ needs more time to nish the computation of the whole lattice. This is because lesser θ implies more concepts, hence faster to obtain 10K concepts. It can also be noted that for θ > 120

Column

(not shown in the gure), there are less than 10K concepts in the whole lattice.

We also tested the sps-based approach to the same dataset. Contrary to the previous experiment where we take only 10K concepts, here we calculate the runtime for the computation of the whole lattice. To reduce the computational time, we introduced the parameter , which is the minimal length of any sequence. Therefore, in calculating the intent of any sequence pattern concept, any sequence having length less than is discarded. For example, with = 3, an intent {a|b|c, a|d} becomes {a|b|c}.

The result of this experiment is shown in Fig. 3.8. With larger , the computational time is reduced, since we will have less concepts. This is useful compared to the majority of existing sequential pattern miners. To obtain sequential pattern with larger length, they usually need to lower the minimum support parameter. This results in more patterns, and consequently larger computational time.

Concerning the biclusters, we found that the bicluster of size 15 × 2 is the widest (having most columns) bicluster with more than 1 row. It follows the sequence of columns c 19 < c 20 < c 1 < c 17 < c 12 < c 21 < c 11 < c 9 < c 16 < c 14 < c 10 < c 7 < c 13 < c 5 < c 3 , which is present in gene #24638 and #291057. Regarding biclusters covering more than 2 rows, the widest biclusters are of size 10 × 3. They are statistically signicant because at a random 3226 × 21 matrix, we can only expect a bicluster covering 1 row (as 3226/10! < 1) exhibiting a certain ordering of 10 columns.

Biclustering with coherent sign changes

Gene expression data can be represented as a matrix, where rows and columns represent genes and experiments respectively. Each cell contains the numeric expression level of a given gene under a given experiment. In such data, we can say that an experiment aect a gene by either lowering or raising its expression, according to the gene's normal level. One may be interested in nding a subset of genes and a subset of experiments, such that the experiments aect the genes in a consistent way. In other words, any two experiments in the subset have always either the same eect or the opposite eect on every gene in the subset. In this thesis, this task corresponds to the mining of coherent-sign-changes (CSC) biclusters as dened in Def. 7. First, in Sect. 3.5.1 below we present some approaches for CSC biclustering using standard partition pattern structures. Then in Sect. 3.5.2 we discuss CSC biclustering using a new adaptation of partition pattern structures.

Using constant-column biclustering

In this subsection, we present two approaches of CSC biclustering using standard partition pattern structures (PPS) in Sect. 3.2. First, we describe how the problem can be solved via PPS-based constant-column biclustering. Second, we show that CSC biclusters can also be retrieved directly from PPS.

In the rst procedure, we scale a binary matrix into a new matrix where each column corresponds to a pair of attributes. Then, we perform PPS in this new matrix to obtain constantcolumn biclusters. We call this approach scaling-based, and we present it in Algorithm 6.

Input: A binary sign matrix S, with a set of columns C and a set of rows R Output: A set of CSC biclusters from S

c 1 c 2 c 3 c 4 r 1 --+ + r 2 + -+ + r 3 + + -+ r 4 -+ -- (a) c 1 c 2 c 1 c 3 c 1 c 4 c 2 c 3 c 2 c 4 c 3 c 4 0 1 1 1 1 0 1 0 0 1 1 0 0 1 0 1 0 1 1 0 0 1 1 0 (b)
({r 2 , r 4 }{c 1 c 2 , c 1 c 3 , c 1 c 4 }) ({r 2 , r 4 }{c 1 , c 2 , c 3 , c 4 }) ({r 1 , r 3 }{c 1 c 2 , c 1 c 3 }) ({r 1 , r 3 }{c 1 , c 2 , c 3 }) ({r 1 , r 2 , r 3 , r 4 }{c 2 c 3 }) ({r 1 , r 2 , r 3 , r 4 }{c 2 , c 3 }) ({r 1 , r 2 , r 4 }{c 2 c 3 , c 2 c 4 }) ({r 1 , r 2 , r 4 }{c 2 , c 3 , c 4 })
Table 3.8: Some constant-column biclusters from Table 3.7b and their corresponding CSC biclusters in Table 3.7a.

To avoid the combination of columns from a binary sign matrix, we may apply PPS directly into it. This is our second procedure (called PPS-based), where we retrieve CSC biclusters by examining the generated pp-concepts.

As explained in Section 3.1.3, a pp-concept is symbolized as (A, d) where A is a set of attributes and d is a set of partition component p. Moreover, any pair (p, A) is a constant-column bicluster.

Then, a CSC bicluster is either a single constant-column bicluster or any pair of constant-column biclusters that are contrasting to each other.

For example, consider again the matrix given in Table 3.7a and the pp-concept ({c 2 , c 3 , c 4 }, {{r 1 , r 2 }, {r 3 }, {r 4 }}). From this pp-concept, we have three constant-column biclusters: First, we inspect the eect of number of attributes in both approaches. The result is shown in Figure 3.9. With more attributes (>6), the execution time of PPS-based is higher than scalingbased although both approaches follow similar growth. As illustrated in Table 3.7b, scaling-based produce some matrices and executing PPS in each of them. Therefore, given 10 attributes, scaling-based applies PPS in matrices of 9, 8, 7,... and 1 attributes separately, while PPS-based applies PPS in a single matrix of 10 attributes. Even without the computation of contrasting constant-column biclusters, the runtime of PPS-based is still longer than scaling-based (not shown here). This result implies the exponential nature of PPS regarding the number of attributes.

• b x = ({r 1 , r 2 }, {c 2 , c 3 , c 4 }) • b y = ({r 3 }, {c 2 , c 3 , c 4 }) • b z = ({r 4 }, {c 2 , c 3 , c 4 })
Also, Figure 3.10 shows that the execution time of scaling-based is better than PPS-based with larger number of objects. Similar with the rst experiment, this also suggests that executing PPS in one m × n matrix needs more execution time than executing PPS in m × (n -1), m × (n -2), . . . m × 1 matrices separately. Therefore, scaling-based should be preferred over PPS-based.

Using pattern structures of signed partition

In the task of CSC bicluster discovery in a formal context (G, M, I), here we explore an approach based on an extension of partition pattern structures. Instead of partition of objects in G as described in Sect. 3.1.2, here we use partition of attributes in M . It is still similar to an object partition since an attribute partition covers every attribute in M and there is no overlapping between any two partition components.

M m 1 m 2 m 3 m 4 g 1 + + - - g 2 + + - - g 3 - - + - g 4 + + + + g 5 - - - -
To formally dene our signed partition, rst we dene the notion of signed attribute (comparable to marked objects in Sect. 3.3) and signed partition component as follows.

Denition 8 (Signed attribute). Let M be a set of attributes, m ∈ M be an attribute, and * ∈ {-, +} be a sign. A signed attribute m * is an attribute m having a sign * .

Denition 9 (Signed partition component). A signed partition component (or sp-component) c is a subset of M , where each attribute in c is associated to their corresponding sign * . Therefore,

c = {m * 1 , • • • , m * n }.
For example, m + 1 is a signed attribute where the sign + is given to m 1 , and {m + 1 , m - 2 , m + 4 } is a signed partition component. Since an sp-component contains not only attributes but also their associated sign, we dene the equality of two sp-components according to these two aspects as follows.

Denition 10 (SP-component equality). Any two sp-components are equal i both contain the same set of attributes, and they have either entirely same sign or entirely opposite sign.

Therefore, if we have

c 1 = {m + 1 , m - 2 , m + 4 }, c 2 = {m + 1 , m - 2 , m + 4 }, and c 3 = {m - 1 , m + 2 , m - 4 }, then c 1 = c 2 = c 3 . Denition 11 (Signed partition). A signed partition (or s-partition) d is a collection of sp- components, written as d = {c 1 , • • • , c n }, such that every attribute in M is present in exactly one sp-component. For example, given M = {m 1 , • • • , m 4 }, then {{m + 1 , m - 2 , m + 4 }, {m + 3
}} is a valid signed partition of M . The set of all possible s-partitions is denoted as D. This allows us to create an s-partition mapping δ : G → D which assigns an object to an s-partition over M . For an object m, δ(m) is an s-partition containing only one sp-component. This sp-component contains all attributes in M with the corresponding sign according to the object g. Example from Table 3.9:

δ(g 1 ) = δ(g 2 ) = {{m + 1 , m + 2 , m - 3 , m - 4 }} δ(g 3 ) = {{m - 1 , m - 2 , m + 3 , m - 4 }} δ(g 4 ) = {{m + 1 , m + 2 , m + 3 , m + 4 }} δ(g 5 ) = {{m - 1 , m - 2 , m - 3 , m - 4 }}.
Notice that since the sp-components in δ(g 4 ) and δ(g 5 ) contain the same attributes with entirely opposite sign, according to Def. 10 we have δ(g 4 ) = δ(g 5 ). This mapping is formulated as follows:

δ(g) = {{m * j j |m j ∈ M }} where * j = m j (g). (3.10)
For the task of CSC bicluster discovery, here we dene relations between any two s-partitions.

The set of all possible s-partitions D is a meet-semilattice where we can dene the meet of any two s-partitions.

First, we dene the notation m(c) as the sign of an attribute m in an sp-component c. For

example, if c = {m + 1 , m - 2 , m - 3 }, then m 1 (c) = +.
With this notation, we dene the similarity (∩ ± ) between any two sp-components as:

c 1 ∩ ± c 2 = {{m * j ∈ c 1 |m j (c 1 ) = m j (c 2 )}, {m * j ∈ c 1 |m j (c 1 ) = ¬m j (c 2 )}}, (3.11)
where * corresponds to the sign of m j in c 1 , i.e. m j (c 1 ).

In other words, the operator ∩ ± between c 1 and c 2 gives {c 12 , c 1|2 }. The c 12 represents all attributes who are present in c 1 and c 2 with the same sign, while c 1|2 represents all attributes who are present in c 1 and c 2 , but with opposite sign. The signs in the resulting sp-component are the same as those in the rst sp-component. Example:

if c x = {m + 1 , m - 2 , m - 3 , m - 4 } and c y = {m + 1 , m - 2 , m + 3 , m + 4 , m - 5 }, then c x ∩ ± c y = {{m + 1 , m - 2 }, {m - 3 , m - 4 }}.
Since the signs in c 1|2 follow the rst sp-component, the result of c 1 ∩ ± c 2 could be dierent to c 2 ∩ ± c 1 . This can be resolved by Def. 10 that ensures the commutativity of ∩ ± . For example:

c x ∩ ± c y = {{m + 1 , m - 2 }, {m - 3 , m - 4 }}, c y ∩ ± c x = {{m + 1 , m - 2 }, {m + 3 , m + 4 }}, c x ∩ ± c y = c y ∩ ± c x .
Having dened the similarity of any two sp-components, we can now dene the similarity of any two s-partitions. The similarity (or the meet) of two s-partitions

d 1 = {c 1 • • • c k } and d 2 = {c 1 • • • c n }, with k = |d 1 | and n = |d 2 |, is dened as: d 1 d 2 = {c i ∩ ± c j |∀c i ∈ d 1 , c j ∈ d 2 }, (3.12)
and the order between two s-partitions is given by:

d 1 d 2 ⇐⇒ d 1 d 2 = d 1 . (3.13)
Let C the set of all sp-components in M , and D is the set of all s-partitions in M . We have ∩ ± : C 2 → D and : D 2 → D. Example from Table 3.9:

δ(g 1 ) δ(g 3 ) = {{m + 1 , m + 2 , m - 3 , m - 4 }} {{m - 1 , m - 2 , m + 3 , m - 4 }} = {{m - 4 }, {m + 1 , m + 2 , m - 3 }}. Suppose that d 1 = {{m - 4 }, {m + 1 , m + 2 , m - 3 }}. Then d 1 δ(g 1 ), d 1 δ(g 2 )
, and d 1 δ(g 3 ). In order to dene a partial order among d ∈ D, the operator has to be commutative, idempotent, and associative. These properties are shown in the following propositions. Proposition 1. The operator is commutative, i.e.

d 1 d 2 = d 2 d 1 . Proof. Consider d 1 = {c 1 • • • c n } with n = |d 1 | and d 2 = {c 1 • • • c k } with k = |d 2 |. d 1 d 2 = d 2 d 1 {c i ∩ ± c j |∀c i ∈ d 1 , c j ∈ d 2 } = {c j ∩ ± c i |∀c i ∈ d 1 , c j ∈ d 2 }
It is previously stated that ∩ ± is also commutative. Therefore, both sides of the equation above are equal. Proposition 2. The operator is idempotent, i.e.

d 1 d 1 = d 1 . Proof. Consider d 1 = {c 1 • • • c n } with n = |d 1 |. d 1 d 1 = {c i ∩ ± c j |∀c i ∈ d 1 , c j ∈ d 1 }
Since there is no overlap among c i ∈ d 1 , then c i ∩ ± c j is an empty set for i = j. Therefore :

d 1 d 1 = {c i ∩ ± c j |∀c i , c j ∈ d 1 and i = j} = {c i ∩ ± c i |∀c i ∈ d 1 } = {c i |c i ∈ d 1 } = d 1 Proposition 3. The operator is associative, i.e. (d 1 d 2 ) d 3 = d 1 (d 2 d 3 ). Proof. Consider d 1 = {c 1 • • • c n } with n = |d 1 |, d 2 = {c 1 • • • c p } with p = |d 2 |, and d 3 = {c 1 • • • c q } with q = |d 3 |. (d 1 d 2 ) d 3 ={c i ∩ ± c j |∀c i ∈ d 1 , c j ∈ d 2 } d 3 ={c i ∩ ± c j ∩ ± c k |∀c i ∈ d 1 , c j ∈ d 2 , c k ∈ d 3 } =d 1 {c j ∩ ± c k |∀c j ∈ d 2 , c k ∈ d 3 } =d 1 (d 2 d 3 )
With the denition of similarity ( ) and the associated partial ordering ( ) between two s-partitions, we then dene the notion of signed partition pattern concept in the following subsection.

Let G a set of objects, M a set of attributes. The lattice of s-partitions of M is (D, ), where δ : G → D maps an object to an s-partition as dened in Eq. 3.10. A signed partition pattern structure is determined by the triple (G, (D, ), δ), where the derivation operators for A ⊆ G From an spp-concept (A, d), a CSC bicluster is any pair (A, c) where c ∈ d (we can ignore the attribute signs in c). All spp-concepts from Table 3.9 are listed in Table 3.10. In the concept ({g 1 , g 2 , g 3 }, {{m + 1 , m + 2 , m - 3 }, {m - 4 }}) for example, we can nd the CSC bicluster ({g 1 , g 2 , g 3 }, {m 1 , m 2 , m 3 }). Looking back to the original table, this CSC bicluster means that in A = {g 1 , g 2 , g 3 }, we have m 1 (A) m 2 (A) m 3 (A) (recall the denition of in Def. 6).

The order between any two spp-concepts is given by (

A 1 , d 1 ) ≤ (A 2 , d 2 ) ⇐⇒ A 1 ⊆ A 2 or d 2 d 1 .
Using this order, the lattice of all spp-concepts from Table 3.9 can be constructed and is shown in Figure 3.11. It should be noticed that the lattice is readable and interpretable only if its size is small. This lattice is useful not only for understanding the hierarchical structure among all biclusters, but also for detecting maximal biclusters. Table 3.10: All sign partition pattern concepts from Table 3.9 and their corresponding CSC biclusters.

Concept CSC bicluster

Extent Intent Objects Attributes

{g 1 , g 2 } {{m + 1 , m + 2 , m - 3 , m - 4 }} {g 1 , g 2 } {m 1 , m 2 , m 3 , m 4 } {g 3 } {{m - 1 , m - 2 , m + 3 , m - 4 }} {g 3 } {m 1 , m 2 , m 3 , m 4 } {g 4 , g 5 } {{m + 1 , m + 2 , m + 3 , m + 4 }} {g 4 , g 5 } {m 1 , m 2 , m 3 , m 4 } {g 1 , g 2 , g 3 } {{m + 1 , m + 2 , m - 3 }, {m - 4 }} {g 1 , g 2 , g 3 } {m 1 , m 2 , m 3 } {g 1 , g 2 , g 3 } {m 4 } {g 1 , g 2 , g 4 , g 5 } {{m + 1 , m + 2 }, {m + 3 , m + 4 }} {g 1 , g 2 , g 4 , g 5 } {m 1 , m 2 } {g 1 , g 2 , g 4 , g 5 } {m 3 , m 4 } {g 3 , g 4 , g 5 } {{m + 1 , m + 2 , m + 4 }, {m + 3 }} {g 3 , g 4 , g 5 } {m 1 , m 2 , m 4 } {g 3 , g 4 , g 5 } {m 3 } {g 1 , g 2 , g 3 , g 4 , g 5 } {{m + 1 , m + 2 }, {m + 3 }, {m + 4 }} {g 1 , g 2 , g 3 , g 4 , g 5 } {m 1 , m 2 } {g 1 , g 2 , g 3 , g 4 , g 5 } {m 3 } {g 1 , g 2 , g 3 , g 4 , g 5 } {m 4 }
The bicluster ({g 1 , g 2 , g 4 , g 5 }, {m 1 , m 2 }) from Table 3.9 is not maximal, since we can add g 3 that constructs another bicluster ({g 1 , g 2 , g 3 , g 4 , g 5 }, {m 1 , m 2 }). The non-maximal biclusters can be detected from the concept lattice [START_REF] Kaytoue | Biclustering numerical data in formal concept analysis[END_REF]. Consider two concepts (A CSC bicluster is a submatrix in a binary matrix. Therefore, given a numerical matrix, it is required to transform it into binary matrix. This can be done by scaling, for example by introducing a threshold, and each numerical value can be transformed to + orbased on whether it is above or below the threshold. In a gene expression data for example, a threshold can be the normal expression level for each gene. An expression that is above (or below) this normal level should be transformed to + (orrespectively).

In the task of mining formal concepts, the AddIntent can be used for any pattern structures by dening the meet ( ) and the order ( ) between any two descriptions. Having dened the meet in Eq. 3.12 and the order in Eq. 3.13, we then use AddIntent to mine spp-concepts in a binary matrix. Furthermore, this algorithm is also eective for building a concept lattice, which is needed in our case to detect the maximality of any CSC bicluster.

Experiments

As previously explained in Section 3.5.2, CSC biclusters can be found in any spp-concept. Therefore, from a binary matrix, we should retrieve all spp-concepts. To do that, we reuse the AddIntent source code in [START_REF] Codocedo | A proposition for sequence mining using pattern structures[END_REF] by modifying the denition and operators. This algorithm also allows us to build the lattice of all concepts. We can reduce the lattice by choosing a threshold θ that applies to the intent of a concept. This threshold denes the minimal size of an sp-component that an intent should have. Since the lattice construction is performed by a bottom-up ap-

∅ {g 1 , g 2 } {{m + 1 , m + 2 , m - 3 , m - 4 }} {g 3 } {{m - 1 , m - 2 , m + 3 , m - 4 }} {g 4 , g 5 } {{m + 1 , m + 2 , m + 3 , m + 4 }} {g 1 , g 2 , g 3 } {{m + 1 , m + 2 , m - 3 }, {m - 4 }} {g 1 , g 2 , g 4 , g 5 } {{m + 1 , m + 2 }, {m + 3 , m + 4 }} {g 3 , g 4 , g 5 } {{m + 1 , m + 2 , m + 4 }, {m + 3 }} {g 1 , g 2 , g 3 , g 4 , g 5 } {{m + 1 , m + 2 }, {m + 3 }, {m + 4 }} Figure 3
.11: Sign partition pattern lattice for pattern structure in Table 3.9.

proach, this threshold allows to prune the lattice. For example, with θ = 3, the lattice for Table 3.9 does not contain the concept ({g 1 , g 2 , g 4 , g 5 }, {{m + 1 , m + 2 }, {m + 3 , m + 4 }})since none of its sp-components has ≥ 3 attributesas shown in Figure 3.12.

We tested our method to lymphoma dataset provided in [START_REF] Alizadeh | Distinct types of diuse large b-cell lymphoma identied by gene expression proling[END_REF] and BicAT yeast dataset 1 . The lymphoma dataset contains the numerical expression levels of 4026 genes over 96 tissues, while the yeast contains 419 probesets and 70 conditions. The objective of CSC bicluster discovery in these datasets is to nd a subset of genes that behave in a consistent way over a subset of tissues. For this task, we convert them to binary by assigningand + for the values < 0 and ≥ 0 respectively. For lymphoma dataset, the number of concepts and runtime for dierent thresholds are listed in Table 3.11. We tested three thresholds: 70, 80, and 90. As shown here, higher θ can reduce the number of concepts, and consequently reduce the runtime.

For θ = 70, around 157K concepts are obtained. Among them, only 153K have extent size larger than 1. This means that there are 153K CSC biclusters having at least 70 columns and at least 2 rows. Furthermore, still with θ = 70, the largest extent size is 8, meaning that among the biclusters with ≥ 70 columns, there are no bicluster with > 8 rows.

Higher θ corresponds to higher number of columns in the biclusters and thus lower number of rows. With θ = 90, we see that among the biclusters with ≥ 90 rows, there are no bicluster with > 3 rows.

Furthermore, the eect of θ can also be seen for both datasets in Fig. 3.13 and 3.14. For each iteration of AddIntent algorithm, we calculate the number of concepts generated so far. With 1 http://www.tik.ee.ethz.ch/sop/bicat/

∅ {g 1 , g 2 } {{m + 1 , m + 2 , m - 3 , m - 4 }} {g 3 } {{m - 1 , m - 2 , m + 3 , m - 4 }} {g 4 , g 5 } {{m + 1 , m + 2 , m + 3 , m + 4 }} {g 1 , g 2 , g 3 } {{m + 1 , m + 2 , m - 3 }, {m - 4 }} {g 3 , g 4 , g 5 } {{m + 1 , m + 2 , m + 4 }, {m + 3 }} {g 1 , g 2 , g 3 , g 4 , g 5 } ∅ Figure 3
.12: Sign partition pattern lattice for pattern structure in Table 3.9 with θ = 3. smaller θ, we discard smaller number of concepts, thus higher number of remaining concepts. This high number of concepts in turn contributes to the higher runtime as previously seen in Table 3.11.

Conclusion

In this chapter we presented a unied approach based on partition pattern structure for discovering dierent types of biclusters in a given numerical matrix. Partition pattern structures are an extension of FCA, based on complex object descriptions and adapted similarity operators.

We showed that by designing a suitable object descriptions and associated similarity operators, we can extract the main types of biclusters from pattern concepts. However, for OP biclustering in this thesis, we do not consider yet the equality (the case with m i (g) = m j (g)). Another aspect that should be studied is the possibility of a matrix that has another sign in addition to + andfor CSC biclustering. This new sign can represent a missing value, or in the case of threshold-based transformation, a value that is equal to the threshold.

It can be resolved using tolerance relation introduced in [START_REF] Kaytoue | Embedding tolerance relations in formal concept analysis: an application in information fusion[END_REF], such that a value equal to the threshold should be regarded as similar to both + and -. In the case of missing value, it can be resolved by modifying the denition of attribute partition which permits an attribute to be not present in any sp-component. This modication may consequently require modications on the denition of meet and order between s-partitions.

Eventually, the CSC bicluster discovery can be applied in a domain besides gene expression data. Frequent gradual itemset mining was studied in [START_REF] Di-Jorio | Mining frequent gradual itemsets from large databases[END_REF] to extract gradual rules from a numerical table, e.g. a hotel price table with 3 attributes: m p for city population, m d for distance from city center, and m r for room price. We may nd an sp-component {m + p , m - d , m + r }. It is related to the rule saying the more/less m p , the less/more m d , then the more/less m r . Moreover, some studies ( [START_REF] Codocedo-Henríquez | Contributions à l'indexation et à la récupération d'information utilisant l'analyse formelle de concepts[END_REF][START_REF] Ignatov | Recommender system based on algorithm of bicluster analysis RecBi[END_REF]) show the benets of biclustering in the recommendation systems. In a usermovie rating matrix for example, a constant-column bicluster represents a set of users having the same interest across a set of movies. On the other hand, a CSC bicluster Previously in Chapter 3, we explore the adaptation of partition pattern structures to discover many types of biclusters. One limitation of this approach is that we need some discretization to obtain non-perfect biclusters. In this chapter, we show how to mitigate this limitation using interval pattern structures, which was proposed to discover similar-column biclusters in a numerical matrix. Here we extend this method such that it is also able to discover additive and multiplicative biclusters.

Interval pattern structures are a solution in the problem of scaling many-valued contexts, presented in Sect. 4.1. We revisit some denitions of interval pattern structures in Sect. 4.2 and its application in similar-column biclustering in Sect. 4.3. Then, we describe how it can be extended to additive and multiplicative biclustering in Sect. 4.4. We explain some modications of Close by One in order to enumerate interval pattern concepts in Sect. 4.5 and some experiments in Sect. 4.6. Lastly we conclude this chapter in Sect. 4.7.

Scaling of many-valued contexts

In standard FCA, the attributes M are binary, giving us the binary context (G, M, I). It can be considered that if m(g) = 1, then the object g has the attribute m. These attributes are called one-valued attributes, and the context is called one-valued context. In ordinal scaling, illustrated in Fig. 4.2, the values are ordered, and there is implication among values. For example in Fig. 4.2 left, a value very good is stronger than good, therefore very good implies good. A concept ({g 1 , g 2 , g 3 , g 4 }, {m 1 = good, m 2 = good}) in Fig. 4.2 right means that all objects have the value good in m 1 and m 2 , although this is not explicit in the multi-valued context in Fig. 4.2 left.

m 1 m 2 m 1 = a m 1 = b m 2 = a m 2 = b g 1 a b g 1 × × g 2 b b =⇒ g 2 × × g 3 a a g 3 × × g 4 a a g 4 × ×
Furthermore, if we have bipolar ordering where there are two extremities, an interordinal scaling should be applied to obtain a one-valued context. An example of this scaling is depicted in Fig. 4.3. An interordinal scaling can be considered as interval of values. In the one-valued context in Fig. 4.3 right, there is a concept:

({g 1 , g 2 }, {m 1 ≤ 1, m 1 ≤ 2, m 1 ≥ 1, m 2 ≤ 2, m 2 ≥ 1}), (4.1)
which reects an interval for each attribute. For g 1 and g 2 , the values of m 1 and m 2 are in the interval [START_REF] Agrawal | Fast algorithms for mining association rules[END_REF][START_REF] Agrawal | Fast algorithms for mining association rules[END_REF] and [START_REF] Agrawal | Fast algorithms for mining association rules[END_REF][START_REF] Ailem | Graph modularity maximization as an eective method for co-clustering text data[END_REF] respectively.

Interval pattern structures

Interval pattern structures (IPS) was introduced by Kaytoue et al. [START_REF] Kaytoue | Mining gene expression data with pattern structures in formal concept analysis[END_REF] to overcome some limitations of enumerating concepts in many-valued context using interordinal scaling. As depicted in Fig. 4.3, the interordinal attribute m 1 is scaled to four binary attributes. With larger range of values, the number of attributes in the scaled context can be signicantly increased. Furthermore, the representation of a concept from interordinal scaling is not ecient, since there are

Interval pattern structures

m 1 m 2 m 1 m 2 ≤ 1 ≤ 2 ≥ 1 ≥ 2 ≤ 1 ≤ 2 ≥ 1 ≥ 2 g 1 1 1 g 1 × × × × × × g 2 1 2 =⇒ g 2 × × × × × × g 3 2 1 g 3 × × × × × × g 4 2 2 g 4 × × × × × ×
d = [a 1 , b 1 ], [a 2 , b 2 ] • • • . In IPS, an interval [a 1 , b 1 ] is subsumed by another interval [a 2 , b 2 ] if [a 2 , b 2 ] is found within [a 1 , b 1 ]
. Accordingly, a vector d 1 is subsumed by another vector d 2 if every interval in d 1 is subsumed by the corresponding interval in d 2 .

The ordering among intervals makes the set of intervals I a meet-semilattice, i.e. there exists one greatest lower bound for any subset of I. The meet-semilattice of an example set of intervals is illustrated in Fig. 4

[a 1 , b 1 ] [a 2 , b 2 ] = [min(a 1 , a 2 ), max(b 1 , b 2 )]. (4.2)
For example, [1, 2] [5, 6] is [START_REF] Agrawal | Fast algorithms for mining association rules[END_REF]6]. The subsumption order among intervals can be dened with the meet operator. If an interval [a 2 , b 2 ] is found within [a 1 , b 1 ], then following Eq. 4.2 the meet between both of them is [a

1 , b 1 ]. Therefore: [a 1 , b 1 ] [a 2 , b 2 ] = [a 1 , b 1 ] ⇐⇒ [a 1 , b 1 ] [a 2 , b 2 ]. (4.3)
Consequently, the set of vectors of intervals is also a meet-semilattice. The meet of two vectors is the convex hull of each corresponding interval. Therefore, given

d 1 = [a 1 , b 1 ], • • • , [a n , b n ] and d 2 = [c 1 , d 1 ], • • • , [c n , d n ] : d 1 d 2 = [a i , b i ] [c i , d i ] i∈[1,n] . (4.4) For example, [1, 2][4, 6] [3, 4][8, 9] is [1, 4][4, 9]
. Furthermore, the subsumption order among vectors follows the subsumption order among intervals in Eq. 4.3, i.e.: An interval pattern structure is determined by the triple (G, (D, ), δ), where G is the set of objects, (D, ) is the lattice of all interval vectors, and δ : G → D maps an object to an interval vector. In a numerical matrix, an interval vector describes the values of every column.

d 1 d 2 = d 1 ⇐⇒ d 1 d 2 , (4.5)
For example, the description of g 1 denoted by δ(g 1 ) in Table 4

.1 is [1, 1][2, 2][2, 2][1, 1][6, 6] .
Given A ⊆ G and d ∈ D, A is the meet of all objects' interval vectors (dened in Eq. 4.4), while d is the set of objects whose interval vector subsumes d (dened in Eq. 4.5) or:

A = g∈A δ(g), d = {g ∈ G|d δ(g)}.
Following the denition of a concept of any pattern structure, an interval pattern concept is a pair (A, d), for A ⊆ G and d ∈ D, where A = d and d = A. Furthermore, the set of interval pattern concepts is partially ordered, and is a complete lattice. An interval pattern concept

(A 1 , d 1 ) is a subconcept of (A 2 , d 2 ) if A 1 ⊆ A 2 (dually d 2 d 1 )
. All interval pattern concepts from Table 4.1 are listed in Table 4.2.

Similar-column biclustering with IPS

A similar-column (SC) bicluster can be found in an interval pattern concept by introducing a parameter θ. This parameter acts as the maximum dierence between any two values to be considered as similar. For example, with θ = 1, the value 1 is similar to 2, but not similar to 3.

In calculating the similarity between any two descriptions, if the length of an interval is larger than θ, then the star sign ( * ) is put as the interval. From Table 4 From an interval pattern concept, an SC bicluster can be formed by the concept's extent and the set of columns where the interval is not * in the concept's intent. For example, from the 4.3. Similar-column biclustering with IPS

A d {g 1 } [1, 1][2, 2][2, 2][1, 1][6, 6] {g 2 } [2, 2][1, 1][1, 1][0, 0][6, 6] {g 3 } [2, 2][2, 2][1, 1][7, 7][6, 6] {g 4 } [8, 8][9, 9][2, 2][6, 6][7, 7] {g 1 , g 2 } [1, 2][1, 2][1, 2][0, 1][6, 6] {g 1 , g 3 } [1, 2][2, 2][1, 2][1, 7][6, 6] {g 1 , g 4 } [1, 8][2, 9][2, 2][1, 6][6, 7] {g 2 , g 3 } [2, 2][1, 2][1, 1][7, 7][6, 6] {g 2 , g 4 } [2, 8][1, 9][1, 2][0, 6][6, 7] {g 3 , g 4 } [2, 8][2, 9][1, 2][6, 7][6, 7] {g 1 , g 2 , g 3 } [1, 2][1, 2][1, 2][0, 7][6, 6] {g 1 , g 2 , g 4 } [1, 8][1, 9][1, 2][0, 6][6, 7] {g 1 , g 3 , g 4 } [1, 8][2, 9][1, 2][1, 7][6, 7] {g 2 , g 3 , g 4 } [2, 8][1, 9][1, 2][0, 7][6, 7] {g 1 , g 2 , g 3 , g 4 } [1, 8][1, 9][1, 2][0, 7][6, 7]

Extent

Intent

{g 1 } [1, 1][2, 2][2, 2][1, 1][6, 6] {g 2 } [2, 2][1, 1][1, 1][0, 0][6, 6] {g 3 } [2, 2][2, 2][1, 1][7, 7][6, 6] {g 4 } [8, 8][9, 9][2, 2][6, 6][7, 7] {g 1 , g 2 } [1, 2][1, 2][1, 2][0, 1][6, 6] {g 1 , g 3 } [1, 2][2, 2][1, 2] * [6, 6] {g 1 , g 4 } * * [2, 2] * [6, 7] {g 2 , g 3 } [2, 2][1, 2][1, 1] * [6, 6] {g 3 , g 4 } * * [1, 2][6, 7][6, 7] {g 1 , g 2 , g 3 } [1, 2][1, 2][1, 2] * [6, 6] {g 1 , g 2 , g 3 , g 4 } * * [1, 2] * [6, 7]
m 1 m 2 m 3 m 4 g 1 3 1 2 3 g 2 0.3 1 2 3 g 3 1 1 2 3 g 4 0.5 1 3 4 (b) concept ({g 1 , g 2 , g 3 }, [1, 2][1, 2][1, 2] * [6, 6] ), ({g 1 , g 2 , g 3 }, {m 2 , m 2 , m 3 , m 5 }) is an SC bicluster with θ = 1.
By using IPS with parameter θ, constant-column biclustering is a specic case of SC biclustering. It can be noticed that with θ = 0, we obtain intervals with length 0, and that corresponds to constant-column biclusters.

Additive and multiplicative biclustering

An additive bicluster is a submatrix where there is a constant (or similar) dierence between any two columns across all of its rows. Constant (or similar) column biclustering is a specic case of additive biclustering. Using this fact, we can obtain additive biclusters by aligning (similar to [START_REF] Henriques | BicPAM: Pattern-based biclustering for biomedical data analysis[END_REF]) each column, and then nd interval pattern concepts on the alignments. is an additive bicluster in the original matrix. This bicluster can be found by applying constantcolumn or similar-column biclustering to the column alignments. Table 4.4b shows the rst column alignment, can be seen by the consistency of the rst column (m 1 ). In this example, each object value is converted such that its m 1 value is equal to the value of m 1 in g 1 . This means that the values 0, -2, 2, and 3 are added to g 1 , g 2 , g 3 , and g 4 respectively. This alignment is repeated for every column. Table 4.4c is the alignment of m 2 , by adding 0, -3, -2, and -5 to g 1 , g 2 , g 3 , and g 4 respectively.

Constant-column (or similar-column) biclustering is applied to every column alignment to nd additive biclusters. In the second column alignment (Table 4.4c), we obtain ({g 1 , g 2 , g 3 }, {m 2 , m 3 , m 4 }) as a constant-column bicluster. This corresponds to the additive bicluster ({g 1 , g 2 , g 3 }, {m 2 , m 3 , m 4 }) in the original matrix (Table 4.4a).

Multiplicative biclusters can also be obtained using similar column alignment. In multiplicative column alignment, instead of adding values to each row, we multiply each row such that 4.5. Concept mining a column has a constant value. Table 4.5b shows the second column alignment of the original matrix in Table 4.5a. Here, a constant value is achieved for m 2 by multiplying g 1 , g 2 , g 3 , and g 4 by 1, 1 3 , 1 2 , and 1 2 respectively. Then, by applying IPS to each alignment, we can obtain the mul- tiplicative biclusters. For example, constant-column biclustering using IPS in Table 4.5b returns ({g 1 , g 2 , g 3 }, {m 2 , m 3 , m 4 }), which is the corresponding multiplicative bicluster in Table 4.5a.

Concept mining

Being a generalization of FCA, the mining of interval pattern concepts can be performed using some existing algorithms that generate a complete list of formal concepts. In this chapter, we use CloseByOne (CbO) [START_REF] Kuznetsov | Comparing performance of algorithms for generating concept lattices[END_REF] since it requires us to only dene the similarity ( ) and subsumption relation ( ) of any two descriptions.

In a given numerical matrix, we may obtain an exponential number of interval pattern concepts. To reduce the number of concepts, we should introduce some parameters that can lter out some uninteresting concepts.

The rst parameter, θ, is previously mentioned in Sect. 4.3. It limits the length of intervals, and later in Sect. 4.6 we demonstrate the eect of θ on the runtime and number of concepts.

The second parameter min_col is the minimum number of columns in the retrieved biclusters.

The number of columns in a bicluster corresponds to the number of non-star intervals in the concept's intent. For example, the concept with intent * * [2, 2] * [6,[START_REF] Andrews | In-Close, a fast algorithm for computing formal concepts[END_REF] gives us a bicluster with two columns (the third and the fth). To take into account the min_col parameter, it is necessary to modify the denition of similarity between any two descriptions. In addition to the denition of in Eq. 4.4, we verify if the number of non-star intervals in the description is less than min_col. If yes, then every interval is converted to * . In Table 4

Experiments

In this section, we report some experimental results to show the scalability of IPS in the task of biclustering. First, in Sect. 4.6.1 we study the eects of our parameters (θ, min_row, and min_col) to the runtime. Then, we compare our IPS-based biclustering method to other patternbased method (Sect. 4.6.2) and numerical method (Sec. 4.6.3).

Eects of parameters

We use the synthetic datasets provided by Henriques and Madeira [START_REF] Henriques | BicPAM: Pattern-based biclustering for biomedical data analysis[END_REF]. First, we investigate the eect of θ on the runtime and the number of concepts. The results are illustrated in Fig. 4.5.

The left gure conrms that the larger θ generates more interval pattern concepts, and generally longer runtime as it can be seen in the right gure. The θ = 0.4 requires longer runtime than θ = 0.5 to 0.9. This is normal since for similar number of concepts, the probability of smaller θ obtaining a concept is smaller than the larger θ. Using CbO with smaller θ, a candidate concept will have shorter intervals in its intent, hence smaller number of objects whose description subsumes this interval. For example, with smaller θ, algorithm may perform:

• • • → {g 1 , g 2 } = {g 1 , g 2 } → {g 1 , g 2 , g 3 } = {g 1 , g 2 , g 3 } → • • • ,
while larger θ may jump from {g 1 , g 2 } to larger set of objects:

• • • → {g 1 , g 2 } = {g 1 , • • • , g 4 } → {g 1 , • • • , g 5 } = {g 1 , • • • g 8 } → • • • .
The eect of min_col is shown in Fig. 4.6. Lesser min_col produces more concepts, and therefore longer runtime. Similarly, Fig. 4.7 shows that larger min_row generates more concepts, but not necessarily longer runtime. This is due to our approach of including min_row to CbO (see Algorithm 8) that prevents the calculation of Y until Z has at least min_row objects. For example, a concept with extent {g 1 , g 2 , • • • g 10 } may be generated when Z has 10 objects. Using smaller min_row, this concept may also be generated when Z has only 2 objects (if for example {g 1 , g 2 } = {g 1 , g 2 , • • • g 10 }).

Comparison with pattern-based method

In the previous experiments, the CbO algorithm was terminated until all interval pattern concepts were retrieved. In the following experiment, CbO is terminated until 500 concepts are found. We compare them to BicPAM [START_REF] Henriques | BicPAM: Pattern-based biclustering for biomedical data analysis[END_REF] that uses a discretization parameter (as a number of alphabet/items), while IPS uses the length of intervals as θ. Furthermore, still from Table 4.6, the runtime of IPS is not exactly correlated with θ (especially with θ = 2), similar to our previous experiment shown in Fig. 4.5. Overall, with similar runtime, biclustering with IPS can return similar number of biclusters without discretization.

Comparison with numerical method

In this subsection we are interested to compare IPS as a pattern-based method with a Cheng and Church (CC) algorithm [START_REF] Cheng | Biclustering of expression data[END_REF] as a numerical method in additive biclustering. CC algorithm nds a set of biclusters having MSR (mean squared residue) less than a user-dened threshold.

These biclusters correspond to constant, similar-row, similar-column, and additive biclusters.

We use BicAT Yeast dataset 2 , a data matrix containing the expression levels of 419 probesets over 70 conditions (hence a 419×70 numerical matrix). The BicAT Yeast dataset is also available in the biclust3 package of R, along with an implementation of CC algorithm which we use in our experiments.

The comparison is given in Table 4.7. The rst column of this table provides the largest MSR among all retrieved biclusters. Smaller MSR means that the additive bicluster has less noise. In CC, the largest MSR is given by user-dened parameter, while in IPS, it is the consequence of the parameter θ. Larger θ means that the intervals are wider, which are more prone to noise. Consequently, larger θ results in biclusters with larger MSR.

In the fourth column, the number of biclusters is given for each entry. For CC, this is the nal number of all biclusters that can be found, while for IPS, this is the number of biclusters found within the corresponding runtime. For example, in the rst entry, after nding 97 biclusters, CC can not nd any other possible biclusters, so it stops at 13.37 seconds. On the other hand, in the second entry, in 13.02 seconds IPS can nd 500 bicluster, but it could nd other biclusters with more runtime.

In general, with similar MSR, IPS can retrieve more biclusters in similar runtime. Furthermore, with similar MSR and runtime, CC can nd larger biclusters. This is because CC generally

Conclusion

In this chapter, we propose an alternative method of biclustering in numerical datasets. Discretization is a general preprocessing step while working with numerical values. Here we explore the possibility of working directly on numerical datasets without discretization. This can be achieved using interval pattern structures, where a bicluster can be found from any interval pattern concept. To lter the number of concepts (which can be very large) it is necessary to provide some parameters, like the length of intervals, minimum number of rows and columns, or even minimum number of biclusters. Our experiments show that these parameters can reduce the computation to a reasonable runtime.

We use the CbO algorithm, a formal concept generator that can be generalized to interval pattern structures. In-Close 2 [START_REF] Andrews | In-Close2, a high performance formal concept miner[END_REF] in particular is faster than CbO in formal concept mining, but its eciency in interval pattern concept mining should be studied. Another future research is to extend our FCA-based approach to other types of biclusters, e.g. coherent-evolution, coherent-sign-changes, etc. Furthermore, the existence of missing values and/or outliers should be considered in improving the proposed biclustering method.

Part II

Experiments in mining complex data Chapter 5

Sequence mining within FCA for analyzing visitor trajectories In this chapter we explore the application of FCA and pattern structures in analyzing visitor trajectories for CrossCult project. First, we describe the project in Sect. 5.1. Then, we explain some denitions of general sequence mining in Sect. 5.2 and sequence mining in FCA in Sect. 5.3.

The approach for analyzing visitor trajectories using FCA is explained in Sect. 5.55.7. Lastly, we end this chapter with some discussions and conclusions in Sect. 5.8.

CrossCult project

This chapter is focused on KDD in the framework of CrossCult (http://www.crosscult.eu/), a

European Project about cultural heritage. The general idea of CrossCult is to support the emergence of a European cultural heritage by allowing visitors in dierent locations (e.g. museum, city, archaeological site) to attentively think of their visit at a European level by using adapted computer-based devices.

The objectives of this project can be summarized as two groups: humanities and innovation.

In the rst group, the researchers investigate how historical facts are retained by an individual, such that an insight of how the same facts may be dierently interpreted by dierent person can be gained.

This thesis is a part of the second objective, which is the innovation. In this objective, a semantic knowledge base is created, which contains multi-level, cross-repository interconnection of venues and digital cultural heritage resources. Furthermore, some new technologies are developed for smart venues and cities. Particularly, we assess the impact of state-of-the-art technologies of geolocalization, content adaptation, and personalization in mobile applications.

In concretizing the history reection framework, the CrossCult technology platform is demonstrated to stimulate reection and reinterpretation of history. This is performed by using mobile tools and applications on real sites across Europe. These demonstrations are classied into four agship pilots:

• Pilot 1: Large multi-thematic venue. This pilot works in a specic venue having broad theme of collection, particularly the National Gallery in London, where the application provides new visitor experiences associated with exploring and searching gallery collections.

Some features on this pilot include a personalized guide through paintings and search for similar paintings.

• Pilot 2: Multiple small venues, which works on various related venues distributed in multiple cities. This pilot was applied in Chaves (Portugal), Ludo (Spain), Montegrotto Terme (Italy), and Epidaurus (Greece), where each of them has various Roman historic sites.

The visitors were expected to collectively engage in the discovery of unknown connections between these related sites.

• Pilot 3: One venue, non-typical transversal connections. Presented in Archaeological Museum of Tripolis (Greece), this agship pilot focuses on the life of women in ancient Greece by providing the hidden narratives between physical and digital objects in the museum.

• Pilot 4: Multiple cities, past & present interplay. As the name suggests, this pilot connects physical cultural heritages that shape the everyday spheres of life. It was presented in Tandil (Argentina), Luxembourg City, and Valletta by means of outdoor exhibition, treasure hunt, etc.

For each of these agship pilots, a mobile application was developed as the interaction tool between visitors as users and CrossCult team as knowledge provider. This application registers the trajectory of each visitor while interacting with them by various means. A map is provided in the application and visitors can explore the venue and read in their mobile phone the description of any point of interest. In certain venues, a maze is given in the application such that visitors solve and unlock paths by providing information about certain items. In addition to the simplicity for visitors to discover point of interests, the application also allows them to view objects on map and 360 degrees view of the eld location, share contents among their friends, rate contents, contribute personal stories and react on other's stories, etc. This leads the visitors to understand the multi-faceted perspective on the study of history and to reckon various possible interpretations of any historical items.

The mining of sequences

Pattern mining is the task of nding repeated occurrences in a dataset. For example, in a data about customer transactions, an objective can be to nd a set of items that are frequently ordered in a single transaction. This specic task in pattern mining is related to sequential pattern mining. We recall below the basic denitions that we will need.

Denition 12. 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 |.

Denition 13. 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 i j 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-dened threshold, the subsequence can be frequent, i.e. the support is above the threshold.

Denition 14. 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 | PrexSpan: Mining sequential patterns eciently by prex-projected pattern growth[END_REF][START_REF] Ayres | Sequential pattern mining using a bitmap representation[END_REF]. Beside mining frequent sequences, another complex task is nding homogeneous sequence groups (clustering). To achieve such a task, a distance or a similarity measure between two sequences has to be dened.

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 .

Sequence mining in FCA

In this section we briey 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 ecient, and among the few algorithms performing sequence mining in the framework of FCA.

Using the denition of subsequence Def. 13 as an order between two sequences, the set of sequences is partially ordered where a sequence subsumes their subsequences. Meanwhile the set of sequences is not a meet-semilattice, since there is no inmum (single largest element) for a certain subset. This is because two sequences can have two common subsequences which are not comparable to each other. Consider the set of sequences formed by the sequence {a}{b}{c} , {a}{c}{b} , and their subsequences. This set is partially ordered, whose Hasse diagram is depicted in Fig. 5.1. For {a}{b}{c} and {a}{c}{b} , {a}{b} and {a}{c} are their highest lower bounds, but there is no single largest element among them. Therefore, the notion of a set of closed sequences is used in sequence pattern structures.

Given a set of sequence S, its set of closed sequences is S + , and dened as:

S + = {s i ∈ S| ∃s j ∈ S : s i ≺ s j },
meaning that in S + there is no two sequences where one is a proper subsequence of another.

The set S + is the description d of an object in pattern structures. The d 1 is subsumed by d 2 if for every sequence in d 1 there exists its supersequence in d 2 , or:

d 1 d 2 ⇐⇒ ∀s i ∈ d 1 ∃s j ∈ d 2 : s i s j .
For example, { {a} , {b} } is subsumed by { {a}{b} , {a}{c} } The set of d, called D, is a meet-semilattice since there exists an inmum for every subset of D. The meet of d 1 ∈ D and d 2 ∈ D, written d 1 d 2 , is their set of common closed subsequences (SCCS), dened as:

d 1 d 2 = {s i ∩ s j |∀s i ∈ d 1 , ∀s j ∈ d 2 } + ,
where s i ∩ s j is the set of all common subsequences between s i and s j . For example, given

d 1 = { {a}{b}{c} } and d 2 = { {a}{c}{b} }, then d 1 d 2 = { {a}{b} , {a}{c} }.
As explained previously, there are two approaches of sequence mining using pattern structures: MFCS and MRGS. One dierence between them is their denition of ∩, the set of common subsequences. MFCS only considers contiguous subsequences, while MRGS considers all subsequences, contiguous or not.

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 dierently, 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 dened on the items composing the sequences.

MRGS is also a sequence miner based on pattern structures but with a dierent 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 specic pattern structure 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.

The dataset of museum visitors

5.4

The dataset of museum visitors

The museum

In the framework of the CrossCult project, we are working on a specic dataset about the trajectories of 254 visitors in Hecht Museum in Haifa, Israel [START_REF] Lanir | The inuence 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 5.1. When modeling trajectories into sequences, in this chapter we consider only the item name, such that every itemset contains only one item. For simplicity, we omit the curly brackets to describe an itemset.

Therefore for the remaining part of this chapter 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 5.1, the corresponding sequence is Crafts and Arts, Wooden Tools . This preprocessing results in sequences of various size. Forty-ve 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 rst two categories and their items are listed in Table 5.2. We convert the raw dataset into sequences of items, where each item is represented by its ID. We dene the IDs such that we can infer the category of an item by its rst 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 5.3.

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 .

Workow for analyzing the trajectories

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 dierent recommendations all along a visit [START_REF] Kuik | Analysis and prediction of museum visitors' behavioral pattern types[END_REF][START_REF] Zancanaro | Analyzing museum visitors' behavior patterns[END_REF].

These four styles are illustrated in Fig. 5.2 and 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 buttery 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 dierent one from the other).

• The sh 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.

Workow for analyzing the trajectories

In the following, one objective is to map specic 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 workow:

1. Cluster the visitor trajectories and assign a label for each visitor (Section 5.6).

2. Create two concept lattices using MFCS and MRGS over the whole dataset (Section 5.7.1).

3. From the two lattices, nd jumping emerging patterns (JEPs) for each label (Section 5.8.1).

4. Based on their JEPs, these labels are then mapped into four visiting styles as explained in Section 5.4.2.

Clustering of trajectories

In this rst 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 clustering 4 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, 4 We use the hclust method from the R software [START_REF] Core | R: A Language and Environment for Statistical Computing[END_REF].

and E. Four of them are expected to match the four visiting patterns, namely ant, buttery, sh, and grasshopper. The last cluster will gather all non-classied trajectories. These ve 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 ve clusters to corresponding visiting styles. For doing so, we will analyze the subsequences that can be attached to each cluster of trajectories.

The benet 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.

5.7

The mining of trajectories considered as sequences 5.7.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 discussed in Section 5.7.2, 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 dened 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: 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 dierent.

δ(S 1 ) δ(S 2 ) = { 401
For example, the concepts corresponding to Table 5.3 are shown in Table 5.4. Notice that both algorithms obtain a concept whose extent is V 2 , V 3 , V 4 , albeit with dierent 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 . FCA is a non supervised classication 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 | Ecient mining of emerging patterns: Discovering trends and dierences[END_REF]. This approach is already applied in [START_REF] Asses | A Hybrid Classication Approach based on FCA and Emerging Patterns -An application for the classication 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, ve 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 classied 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.

Discussion

Cluster characterization

Now we are interested in characterizing the ve 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 5.5 and Table 5.6. First, from both MFCS and MRGS, we cannot nd 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 sh. Cluster D is more easily distinguishable. Based on subsequences of concept FD2FD4, 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 ow (based on RA1RC1) and no jump" (based on FA1FC2). However, in FC3, three visitors visit 101, then 102, then back again to 101, indicating rather a buttery behavior.

Conclusion

In this chapter, 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, buttery, sh, 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 dene visitor behaviors. This can help museum researchers to analyze and evaluate the placement of items and the visiting styles.

Moreover, this analysis is useful to build a recommendation system for future visitors, but we

did not yet study this aspect.

In this thesis, 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 visitors during the visit could be also considered for analysis and on-line recommendation. susceptibility testing. With its overuse, many bacteria undergo evolution, mutation and selection, so they become resistant to those drugs [START_REF] Fernandes | The global challenge of new classes of antibacterial agents: an industry perspective[END_REF]. And because of the emergence of drug-resistant superbugs, like methicillin-resistant Staphylococcus aureus (MRSA), traditional antibiotics such as penicillin and its derivatives are becoming obsolete.

New antibiotics are desperately needed, but the amount of money being spent on the research and development of these drugs is woefully inadequate as major pharmaceutical companies have abandoned or cut back antibiotic research and development. Their decision is also supported by the fact that the investments required for developping new drugs keep increasing while the expected returns drop as the usability span of the newly developed drugs become shorter.

The unwillingness of many pharmaceutical companies leads the eective drug-discovery to be developed by the academic community, including the computer scientists. The convergence of computer science and computational chemistry has given rise to the new eld of chemoinformatics. Chemoinformatics combines various research areas and techniques, including machine learning, pattern recognition, molecular dynamics, quantum mechanics, and statistics. It is attracting growing attention and recognition as available computing power and data volumes keep increasing. By harnessing knowledge discovery techniques it aims to oer more ecient drug development methods so as to tackle the pressing challenge posed by drug resistant bacterial diseases.

Considering the millions of available chemicals spread among chemical providers, companies' collections and academic laboratories, the huge number of indexed chemical compounds is both a blessing and a curse. Indeed, the volume of these databases means that they certainly contain molecules that would provide ecient weapons against bacterial diseases but this is also what makes is so dicult to identify the promising candidates among scores of unsuitable chemical compounds. For that purpose, a learning procedure using a limited subset of well identied antibiotics and a large collection of chemical attributes can be used.

Structure and properties of molecules are a gold mine of information to characterize antibiotics. Not only physicochemical and chemical graph properties can be calculated from their structures, but also a large amount of information is obtained from dynamic structure changes and from the interaction between compounds and their targets. For eective use of a ood of information obtained from a large number of compounds, chemical information needs to be converted into meaningful and useful data. Any molecule can be represented by a set of numerical or categorical values, called descriptors, that characterize its physicochemical and topological properties. Such data can be calculated by a large variety of methods and vary in complexity of the encoded information and in the computer time for calculated them. Among such descriptors, some are related to the chemical graph while others are linked to a 3D representation. Consequently, for a given set of chemicals, we have to handle matrices with rows as the molecules IDs, and columns as the descriptors values.

In computer-aided drug design, considering the huge variety (several thousands) of molecular descriptors that are presently available for describing physico-chemical properties, the problem is how to achieve an optimal selection of appropriate sets in order to analyze, with highest accuracy, chemical diversity/similarity among large chemical libraries (several million of objects). Such optimally selected descriptors should provide the most ecient rules which can be used next to describe molecules with a common behavior. Such knowledge extraction phase would help to extract compounds presenting all the same required action. The diculty is therefore to achieve properly the reduction in size of the descriptor matrix (from several thousands to several hundreds) without losing important information.

The usual way for that is to look for possible correlations between the descriptors to avoid redundancies. But it has been proved that such basic statistical analysis is not really ecient 6.2. Feature selection new approaches are desired. Consequently, there is a need to design a method that can help us to understand the data better. This is the subject of Knowledge Discovery in Database (KDD), where computational theories and tools can help us in discovering knowledge from large datasets [START_REF] Fayyad | From data mining to knowledge discovery in databases[END_REF], in this case the molecular descriptors.

The present chapter is concerned with the task of dimensionality reduction, or feature selection, on a dicult problem for medicinal chemistry. Dimensionality reduction of the data space refers to the process of converting a set of data having large dimensions into data with lesser dimensions ensuring that it conveys similar information concisely. These techniques are typically used while solving machine learning problems to obtain better features for a classication or regression task and concern many research elds of life sciences (see for example very recent papers assessing the strong interest for this eld) [START_REF] Davoudi | Dimensionality reduction based on distance preservation to local mean for symmetric positive denite matrices and its application in braincomputer interfaces[END_REF][START_REF] Lee | Gene-gene interaction analysis for the accelerated failure time model using a unied model-based multifactor dimensionality reduction method[END_REF][START_REF] Prescott | Combining in silico evolution and nonlinear dimensionality reduction to redesign responses of signaling networks[END_REF][START_REF] Yang | Nonlinear dimensionality reduction methods for synthetic biology biobricks' visualization[END_REF][START_REF] Zhao | Unsupervised 2d dimensionality reduction with adaptive structure learning[END_REF]. Such reduction techniques, also related to feature selection methods, are of crucial importance in several aspects of drug design [START_REF] Ivanenkov | Computational mapping tools for drug discovery[END_REF][START_REF] Liu | A comparative study on feature selection methods for drug discovery[END_REF][START_REF] Reutlinger | Nonlinear dimensionality reduction and mapping of compound libraries for drug discovery[END_REF][START_REF] Tang | Prediction of cell-penetrating peptides with feature selection techniques[END_REF][START_REF] Xu | Prediction of human disease-associated phosphorylation sites with combined feature selection approach and support vector machine[END_REF][START_REF] Yang | Development of in silico models for predicting p-glycoprotein inhibitors based on a two-step approach for feature selection and its application to chinese herbal medicine screening[END_REF], especially in drug/non-drug classication [START_REF] Korkmaz | Drug/nondrug classication using support vector machines with various feature selection strategies[END_REF] adverse drug eects [START_REF] Liu | Analysis and prediction of drugdrug interaction by minimum redundancy maximum relevance and incremental feature selection[END_REF] and QSAR.

Feature selection

For discovering new antibiotics, we inspect a number of chemical molecules, to know which ones can characterize an antibiotic. To do that, it is necessary to look at the properties of each molecules, for example the number of atoms, the presence of certain atoms, the presence of rings, polarity, eccentricity, etc. All those properties sum up to thousands of attribute which means that we need a signicant amount of time and space.

In order to minimize the required time and space, before we mine the data, we should reduce the dimension of the data set, as a transformation step in Fig. 1. It is performed by combining some attributes into one, or by completely eliminating some of them.

Within the thousands attributes for each molecule, we can identify some redundancies. Percentage of H atoms correlates with number of H atoms and number of atoms, number of C atoms correlates with number of CR3X structure, and many more hidden correlations. Therefore, we can ignore an attribute if they can be represented with another attributes. The selected attributes should be able to dene the molecules without signicant loss of information.

Beside the redundancies, we should also ignore the attributes which is not descriptive. For example, if we have an attribute describing the number of phospanes of a molecule, but all molecules have no phospanes, this attribute clearly can't distinguish between antibacterial and non-antibacterial molecules.

Many algorithms have been proposed to do this feature selection task. As illustrated in Fig. 6.1, they can be classied into two categories [START_REF] John | Irrelevant features and the subset selection problem[END_REF]:

1. Filter model, where feature selection is executed independently before the data mining process. This model doesn't take into account the classication algorithm that will be used.

One common method is χ 2 , who assigns a score to each feature based on the dependencies between them and the class. The higher scores belong the more important features. We then do a feature selection by removing the features whose score is less than a threshold.

2. Wrapper model, means that feature selection process exists as a wrapper around the classication algorithm. This algorithm will become a part of an evaluation function. An example of this model is studied by Li and Yang [START_REF] Li | Using recursive classication to discover predictive features[END_REF]. They examined two wrapper models, recursive and non-recursive. At each iteration in recursive approach, a classier is trained, and feature weights are obtained. The feature with the smallest weight is then removed. The iteration stops when the desired number of features t is attained. On the other hand, in non-recursive approach, after all feature weights are calculated, t features are selected, and the rests are immediately discarded. They examined both approaches using three classiers: SVM, ridge regression, and Rocchio. Eventually, it is shown that ridge regression was the best choice, since it penalizes many redundant features eectively.

Log-linear analysis

This section describes log-linear analysis (LLA) and its graphical representation. LLA can nd any associations among attributes, allowing feature selection according to those associations.

Suppose that we have a data set W AR of certain molecules with three variables: molecular weight (W ), number of atoms (A) and ring perimeter (R). Relationship between two variables can be studied with two-way χ 2 test of association. However, if we have more than two variables, we need to do a multiway frequency analysis to study the two-and three-way associations. LLA is an extension of multiway frequency analysis, and tries to discover any statistical relationships between three or more non-continuous variables. It will create a model (like the one in Eq. 6.4)

to nd the log of expected frequencies.

For the W AR data set with contingency table in Table 6.1, LLA tries to answer some relationship questions. Is a molecule's weight related to its number of atoms? Is a molecule's number of atoms related to its ring perimeter? Is there a three-way relationship among molecular weight, number of atoms, and ring perimeter? By knowing ring perimeter of a molecule, can we predict its weight?

To do a multiway frequency analysis with LLA, we develop a linear model of the logarithm of expected cell frequencies. An example of such model is shown in Eq. 6.4, with each term representing an association. As the number of variables increases, the number of associations also increases. With three variables in data set W AR, we have seven possible associations: one three-way associations, three two-way associations, and three one-way associations. The model in Eq. 6.4 contains all possible associations. To keep the simplicity of a model, LLA tries to nd which association will be kept or removed. To do that, we should determine the signicance of an association by examining the goodness-of-t of the model containing it. Eventually, with thousands of variables, the number of possible associations will be so large that it would be impractical to test each association. This limitation can be solved by Chordalysis.

Goodness-of-t

The goodness-of-t of LLA measures the conformity between the expected and observed frequencies. With only two variables, there is one two-way association. To test the goodness-of-t of a two-way association, we can use χ 2 test:

i

(O i -E i ) 2 E i , (6.1)
where for each cell i of contingency table, O i is its observed frequency and E i is its expected frequency. The summation is done over all cells.

However, since there are multiway associations in LLA, we use G 2 test. This test can replace χ 2 test in measuring the conformity of observed and expected frequencies. G 2 statistic is distributed as χ 2 , so we can use χ 2 table to evaluate its signicance. This statistic has the equation:

2 i O i ln O i E i . ( 6
G 2 T = G 2 A + G 2 B + G 2 AB . (6.3)
This property is useful to test the residual frequency of a model, which will be shown in Section 6.3.2. For the computation detail of G 2 please refer to [START_REF] Tabachnick | Using Multivariate Statistics[END_REF].

Log-linear model

Log-linear model is represented as an equation to nd a logarithm of E (expected frequency of a combination of variables' values), e.g. the expected value of the cell light-small-wide in Table 6.1.

From data set W AR, we can generate a model that contains all possible associations. This is the saturated model, which can be written as:

ln E war = θ + λ W (w) + λ A (a) + λ R (r) + λ W A (wa) + λ W R (wr) + λ AR (ar) + λ W AR (war) (6.4)
where θ is a constant, and λ term represents an eect. Each λ has values as many as the number of levels, and these values sum to zero. For example, since we dene three levels of molecular weight: light, medium, and heavy, λ W (w) has three possible non-zero values: for light (λ W (lig)), medium (λ W (med)), and heavy (λ W (hvy)), with λ W (lig) + λ W (med) + λ W (hvy) = 0.

A log-linear model can be hierarchical or non-hierarchical. A hierarchical model can be represented by its highest-order association in square brackets. For example, a model [W A][R] contains λ W A (wa) and λ R (r), as well as λ W (w) and λ A (a).

The score of a model is obtained by calculating its G 2 and examining its signicance. Based on Eq. 6.3, G 2 of a model is obtained by subtracting the G 2 of each association from total G 2 , therefore revealing its residual frequency.

ln E war = θ + λ Ww + λ Aa + λ Rr + λ W Awa . This model has G 2 : G 2 [W A][R] = G 2 T -G 2 W A -G 2 A -G 2 W -G 2 R = 48
.09 -27.12 -0.16 -1.32 -13.25 = 6.24 (6.5) and df = 11 -2 -1 -2 -1 = 5. This residual is not statistically signicant (>0.05 in χ 2 table), so the model is good.

We then evaluate a more complex hierarchical model, [W A][W R] for example. Similar with the example in Eq. 6.5, we have G 2 [W A][W R] = 2.48 and its df = 3. This model is also good. Therefore, we must choose between

[W A][R] and [W A][W R].
Notice that both models are hierarchical, and

[P S][R] is a submodel of [W A][W R], i.e. we can nd all λ terms of [W A][R] in [W A][W R]. In this condition, the dierence between their G 2 s is itself a G 2 : G 2 di = G 2 [PS][R] -G 2 [PS][PR]
= 6.24 -2.48 = 3.76

with df = 5 -3 = 2. This dierence is not statistically signicant, so we can select a less complex model, [W A][R].

Graphical model

Consider the graph shown in Fig. 6.2, a graphical representation of a log-linear model. Its vertices are connected by an edge to each other because there are λ W (w), λ A (a), λ R (r), λ W A (wa), λ W R (wr), and λ AR (ar) in the model. Furthermore, because the graph between the three variables is complete, we can conclude that there is a three-way association between them, λ W AR (war).

Therefore, the model is a saturated one, as shown in Eq. 6.4. Therefore, a log-linear model is graphical if, whenever a model contains all two-way associations generated from a higher-order association, the model also contains the higher-order association. The model shown in Fig. 6.2 contains all two-way associations from λ W AR (war). Thus, it should also contains λ W AR (war).

W

Associated with each graph, we have maximal cliques and minimal separators, as illustrated in Fig. 6.3. A clique of graph G is a subset of vertices of G whose induced subgraph is complete, i.e. every two distinct vertices are connected by an edge. A maximal clique is a clique that is not a subset of another clique. A maximum clique is a clique with the largest number of vertices.

A separator of graph G is a subset of vertices of G whose removal will make G disconnected. A minimal separator is a separator which doesn't have another separator in its subsets. A separator with the smallest number of vertices is a minimum separator.

A minimal separator is also a property of a pair of vertices. A minimal (a, b)-separator is a subset of vertices whose removal make a disconnected from b, and such subset does not have another separator in its subsets.

Decomposable models

A graphical log-linear model is decomposable if its graph is decomposable. A decomposition of a graph D is a partition of its vertices V into three disjoint subsets (A, B, S), where: A graph is decomposable if it is complete or if it can be decomposed into another decomposable subgraphs. From this recursive denition, this means that all maximal prime subgraphs are cliques. Consequently, the graph in Fig. 6.4a is not decomposable, since two of its components (in Fig. 6.5) aren't decomposable.

Moreover, a graph is decomposable if and only if it is chordal. In a chordal graph, every cycle with length more than three has a chord, i.e. an edge that is not part of the cycle but connects two vertices of the cycle. The graph in Fig. 6.6a is chordal, but the graph in Fig. 6.6b is not, because its (A, B, D, E) cycle does not have any chord.

Decomposable models are the only log-linear models which have a closed-form maximum likelihood estimates [START_REF] Haberman | The analysis of frequency data: Statistical research monographs[END_REF]. Furthermore, a decomposable model has an advantage concerning its minimal separators and maximal cliques. They can be generated in linear time in a single pass, using Lexicographic Breadth First Search or using Maximum Cardinality Search [START_REF] Berry | A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph[END_REF]. 6 taken from http://www.stats.ox.ac.uk/∼steen/teaching/cimpa/decomp.pdf

Chordalysis

Chordalysis

There are two ways to select which associations to include in a log-linear model: backward elimination and forward selection. Backward elimination starts from a saturated model and eliminates non-signicant associations one by one. On the other hand, forward selection starts from an empty model and iteratively adds an association until the dierence is not signicant. The existing LLA considers all possible associations to determine which one to be added or removed. This becomes infeasible when the number of attributes increases, since the number of associations is exponential w.r.t. it.

Chordalysis tries to guide the existing LLA in selecting which associations are signicant enough to be included in the model [START_REF] Petitjean | A statistically ecient and scalable method for loglinear analysis of high-dimensional data[END_REF][START_REF] Petitjean | Scaling log-linear analysis to high-dimensional data[END_REF]. This method is focusing on decomposable log-linear models, whose G 2 can be calculated by inspecting the maximal cliques and minimal separators of the corresponding graph.

As a forward approach, Chordalysis starts with an empty graph as initial model. It has neither vertex nor edges. Then at the rst step of each iteration, the candidate models are generated. Each candidate M c diers from the current best model M * by a single edge only. This edge addition must keep the graph chordal. To nd such edges, we look at the connectivity between its two vertices. An edge (a, b) is eligible if:

• a and b are not connected (they belong to dierent connected components), or

• a and b are connected with all of its chordless paths are of length two.

Since an edge depicts an association between two variables, an addition of a single edge corresponds to an inclusion of a two-way (and possibly a higher order) association in the loglinear model. An example is illustrated in Fig. 6.7. Suppose that at a given iteration we have a best model [02] [START_REF] Berry | A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph[END_REF][23] [START_REF] Freitas | Advances in evolutionary computing[END_REF] (Fig. 6.7a) with equation:

ln E = θ + λ 0 + λ 1 + λ 2 + λ 3 + λ 4 + λ 0,2 + λ 1,2 + λ 2,3 + λ 3,4 (6.7)
An eligible candidate must be decomposable. Therefore, instead of generating all models which have a new edge, it only produces a fewer number of them which are chordal, e.g. [023] [12][34] in Fig. 6.7b with equation:

ln E = θ + λ 0 + λ 1 + λ 2 + λ 3 + λ 4 + λ 0,2 + λ 0,3 + λ 1,2 + λ 2,3 + λ 3,4 + λ 0,2,3 (6.8)
The models which aren't hierarchical are not selected, because their corresponding graph is not chordal (Fig. fact that the graph is chordal and diers by only one edge between iterations, the G 2 computation is scalable to thousand variables [START_REF] Petitjean | Scaling log-linear analysis to datasets with thousands of variables[END_REF]. After the score calculations, Chordalysis selects the best M c . Its score is then compared to the signicance threshold. If it is lower, then we replace M * with M c and continue to the next iteration. If not, then the current M * is the nal model because the G 2 dierence by adding an association is not signicant. The signicance threshold α is updated at each iteration so it doesn't accept a candidate too often. This update rule follows the layered critical values [START_REF] Webb | Layered critical values: a powerful direct-adjustment approach to discovering signicant patterns[END_REF]. At iteration i, where the current best model M * has L edges, the signicance threshold α i is α/(2 L .S i ), where S i is the search space, i.e. the number of chordal graphs that can be formed by adding a single edge to M * , and α is a p-value threshold (usually set to 0.05).

Having a graph representing associations among attributes, we then perform feature selection based on this graph. The attributes which are independent (have no association) are kept, because they can't be represented by another attribute. Then, basically we remove the attributes that have only one association. For example, if we encounter a connected component shown in Fig. 6.8b we keep only attribute d. This means that d can represent c, e, and f . But there is an exception for some of those one-association attributes. If a connected component has only 2

vertices, like the one in Fig. 6.8a, we randomly choose one attribute and discard the other.

Classication of antibacterials and non-antibacterials

The attributes that are selected using Chordalysis will be used in three machine learning method to classify dataset of antibacterials and non-antibacterials.

The rst method is Support Vector Machine (SVM) [START_REF] Cortes | Support-vector networks[END_REF]. Given a dataset of labelled points, 6.6. Evaluation of classier performance SVM builds a hyperplane that best separates the two labels. To deal with non-linearly separable dataset, SVM use a kernel to map points to higher dimension. The second method is random forest [START_REF] Breiman | Random forests[END_REF]. It constructs a family of decision trees which have dierent training set between each other. To classify data, each tree gives a classication (or vote), and random forest takes the majority vote. The third method is naive Bayes that is based on Bayes' theorem. When classifying a data D, naive Bayes calculates the posterior probability of each class given D. The classier then chooses the class that has higher posterior probability.

Evaluation of classier performance

To measure the goodness of each classier, we calculate the following classical measures:

• T P (true positive), the amount of antibacterial data that are classied as antibacterial,

• T N (true negative), the amount of non-antibacterial data that are classied as nonantibacterial,

• F P (false positive), the amount of non-antibacterial data that are classied as antibacterial,

• F N (false negative), the amount of antibacterial data that are classied as non-antibacterial, and we use ve metrics:

1. Accuracy (percentage of data that are correctly classied):

T P + F N T P + T N + F P + F N .

2. Precision (percentage of antibacterial-classied data that are truly antibacterial):

T P T P + F P .

3. Recall (percentage of truly antibacterial data that are classied as antibacterial):

T P T P + F N .

4. AUC (Area Under the ROC Curve) [START_REF] Brown | Receiver operating characteristics curves and related decision measures: A tutorial[END_REF]. The ROC (Receiving Operating Characteristic) curve is a graphical plot of recall and 1-CNF. CNF (Correct Negative Fraction) is dened by:

T N T N + F P .

This curve can be obtained by varying discrimination threshold.

5. f 1 score (harmonic mean of precision and recall), with formula: We focus on the task of reducing dimensionality, by selecting features among thousands of features. Chordalysis will nd some associations among variables, and from that we will remove all variables that can be represented by another.

Previous work

The aim of the previous work [START_REF] Hung | An experiment about the classication of antibacterial molecules[END_REF] was to evaluate the performance of six machine learning techniques for distinguishing between antibacterial and non-antibacterial molecules. Those six classication techniques are: Support Vector Machine (SVM) with linear kernel, random forest, logistic regression, gradient boosted trees, naive Bayes, and decision trees.

The dataset of antibacterial and non-antibacterial molecules were collected from antibacterials already in the market (152 molecules), as well as molecules from the MDDR database (2873 molecules with reported antibacterial properties and 52604 other drugs with no known antibacterial activity) and the Life Chemicals Inc. catalog (38907 molecules labeled as potential antibacterials, 52604 from other categories). The Dragon software [START_REF] Todeschini | Molecular Descriptors for Chemoinformatics[END_REF] was then used to dene 4885 attributes for each molecule. The values of those attributes were calculated using Corina [START_REF] Sadowski | Comparison of automatic three-dimensional model builders using 639 x-ray structures[END_REF].

Selection procedures were initially performed to reduce the initial set of attributes. Those with missing values were removed. Furthermore, if there were a group of attributes which were perfectly correlated, only one of them was kept. These two removal procedures resulted in 4532 attributes.

From this reduced data set, four lters were used independently to obtain a fewer number of attributes, considering their standard deviations and pair correlations. The parameters and results of these lters (called Filter 1, Filter 2, Filter 3, and Filter 4) are shown in Table 6.2.

Finally, we ended with 5 data sets: one non-ltered data set with 4532 attributes and four ltered data sets.

This previous work shows us that SVM has the highest precision, but its recall is low. The recall of random forest is much better than SVM, so it can be used in sacricing the high precision of SVM. In the next sections, we detail our work of applying Chordalysis to perform feature selection among hundreds of molecular descriptors. This includes which data set is used, which preprocessing is needed, and the results from our experiment.

Dataset

Our work is focused on 3025 antibacterial molecules, which is composed by 152 molecules from market and 2873 molecules from MDDR antibacterials. From those molecules, we dened 4885 attributes. Besides removing missing-valued attributes and perfectly correlated attributes, we Some of the attributes are continuous. Because LLA and Chordalysis work on discrete variables, these numerical attributes are preprocessed so that all of them become discrete. This preprocessing step is applied to attributes which have more than 10 distinct values. Equal-width discretization method is used, with 10 bins as desired output.

Result of Chordalysis Attribute selection

Chordalysis (available open-source at http://sourceforge.net/p/chordalysis/) was tested on 3769 attributes, using α = 0.05 as p-value threshold, and it found 1024 associations. The selection procedure explained in Sect. 6.4 results in 3171 selected attributes. From each lter of the previous work, we have four sets of selected attributes. As seen in Table 6.2, Filters 2, 3, and 4

gave us around 500 attributes each; those will be next referred to as S2, S3, and S4 respectively.

In order to compare Chordalysis-based feature selection, we let Chordalysis nd more associations without being limited by p-value threshold. After some experiments, we found that after 3613 associations were found, the selection procedure applied on the graph resulted in a set of 595 selected attributes. We call this set SC. Since S2, S3 and S4 are very similar, all three sets are referred to as S24.

All attributes are uniquely categorized within the Dragon software into 29 attribute families. Fig. 6.9 and 6.10 show how those families are distributed within the dierent sets, with weights in percentages for S24 being dened as the average value between S2, S3 and S4. Table 6.4

summarizes the results of Chordalysis-based selection, and also highlights the overlap between SC and S24.

2D atom pairs are by far the most prevalent family in all cases, accounting to 33, 63 and 20% of the total attributes population in the original, SC and S24 sets respectively. It is very clear that Chordalysis privileged this family, now twice as present in SC compared to the original set, while on the contrary, it is signicantly less important in S24.

The atom-centred fragments, CATS 2D and functional group counts families were not prevalent in the original set (2, 3, and 3% respectively), and become over-selected in all reduced sets, with CATS 2D being more prevalent in S24 compared to SC. These 3 sets account for 23% of SC, so with the addition of 2D atom pairs only 15% is remaining.

The relative diversity of the dierent sets can be compared by focusing on the number of families accounting for more than 5% of the total number of attributes and on their total weight (see Figure 8). Only the 4 aforementioned families obey these criteria in SC, totaling 85% of the set. There are 7 families with more in S24 (73%); 4 in the original set (56%). Therefore, three attribute families are seen signicantly more prevalent in S24 compared to the original set (26% / 15%), but are almost completely ltered out by Chordalysis: 2D autocorrelations, 3D-MoRSE and GETAWAY descriptors.

Apart from these families, there is a consensus between S24 and SC regarding the removal of some attribute families from the original set, with SC appearing more stringent than S24.

Indeed, the 2D matrix-based descriptors, edge adjacency indices and RDF descriptors account together for 22, <1 and 5% in the original, SC and S24 sets respectively. This suggests that those descriptors are not of much value for modeling the probability that a given chemical compound Eventually, it should be noticed that while SC size compared to the original set is 12%, only a single attribute family has been ltered less than 50%: drug-like indices. This is specic to SC (5 attributes are retained by S2, S3 and S4). There were only 27 residues of this kind in the original set, which is not signicant enough to determine that there could be a correlation between drug-likeness and antibacterial potency that would be most eciently selected by Chordalysis. C for SVM, we get the best result for C = 0.01.

Based on the values of all metrics used to evaluate classier performance, it appears that SVM and RF perform signicantly better than naive Bayes. The two best performing model SVM and random forest were then trained on the market antibacterials and Life Chemical antibacterials to test the MDDR data. We regarded a molecule as an antibacterial if it is classied as such in at least α percent of runs. The precision and recall of the two models are shown in Table 6.66.7. SVM has better recall on the majority of alphas, and it has higher precision for α ≥ 20.

Conclusions

Conclusions

In this chapter, we describe the application of the Chordalysis technique for molecular attribute set reduction. We show that it leads to improved performance when a machine learning technique is used next to discriminate between antibacterials and compounds with no antibacterial activity.

It is suggested that a two-step strategy, with a Chordalysis-rened attribute set being fed to a SVM classier could be highly ecient for antibacterials identication. An alternate techniques for selecting an optimal attribute set [START_REF] Tang | Feature selection for classication: A review[END_REF], such as recursive feature elimination [START_REF] Guyon | Gene selection for cancer classication using support vector machines[END_REF][START_REF] Xue | Eect of molecular descriptor feature selection in support vector machine classication of pharmacokinetic and toxicological properties of chemical agents[END_REF], RF variable importance [START_REF] Cano | Automatic selection of molecular descriptors using random forest: Application to drug discovery[END_REF], SVM variable selection [START_REF] Chang | LIBSVM: A library for support vector machines[END_REF], tabu search [START_REF] Tahir | Simultaneous feature selection and feature weighting using hybrid tabu search/k-nearest neighbor classier[END_REF][START_REF] Zhang | Feature selection using tabu search method[END_REF], and evolutionary algorithms [START_REF] Freitas | Advances in evolutionary computing[END_REF] should be further studied. In the process, precise clues on implementing new attributes that could be more ecient for our purpose (antibacterials selection) than the broad generic reference set of molecular attributes that is available in the Dragon software could be obtained. When we reach a state where no clear methodological improvement could be reached, we will apply the optimized methodology to mine chemical space for possible new antibacterials. A limited number of hits from this virtual screening process will be tested experimentally.

Only interesting results backed up by the resulting experimental data will validate the ongoing chemoinformatics approach.

ther by Chordalysis to deal with thousand attributes. We examined the application of Chordalysis in attribute selection by analyzing the resulting association graph. Since the graph informs us the correlation among attributes, we are able to determine which attributes can be represented by another, so they can be discarded, leaving only attributes which are roughly not correlated.

Perspectives

In Chapter 3 and 4, we present an approach of biclustering using partition pattern structures and interval pattern structures respectively. Given that pattern structures is a generalization of FCA, there exist various algorithms capable of enumerating formal concepts that can be adapted to enumerate pattern concepts, from which a set of biclusters can be discovered. Here we adapt CbO and AddIntent to perform pattern concept mining, given their exibility of generalizing similarity operator and subsumption relation needed in pattern structures. Another previous work about FCA-based biclustering [START_REF] Veroneze | Enumerating all maximal biclusters in numerical datasets[END_REF] uses the adaptation of In-Close to mine formal concepts, and it is interesting to adapt this algorithm to mine pattern concepts, and further to mine biclusters.

In Chapter 5, we analyze a dataset of visitor trajectories, such that we can extract some patterns and detect visitor behaviors. In doing that, we included only partial information about the museum in the sequences, which are the visited items. 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. Finally, this analysis can be incorporated to build recommendation systems, by including ongoing information such as comments and state of the visitors during their visit.

Lastly, in Chapter 6 we provide a thorough examination of feature selection using log-linear analysis. We explored the association graph generated from Chordalysis, which can be regarded as attribute correlation graph. Such graph can be mined with other methods, for example graph triangulation and tree decomposition. From a triangulated graph, we can obtain maximal cliques which groups a set of highly correlated attributes. Furthermore, with a tree decomposition on these cliques, we can decide the representatives of each clique, hence discarding other nonrepresentative attributes. Mots-clés: analyse de concepts formels, biclustering, extraction de motifs séquentiels, sélection d'attribut.

Abstract

Knowledge discovery in database (KDD) is a process which is applied to possibly large volumes of data for discovering patterns which can be signicant and useful. In this thesis, we are interested in data transformation and data mining in knowledge discovery applied to complex data, and we present several experiments related to dierent approaches and dierent data types.

The rst part of this thesis focuses on the task of biclustering using formal concept analysis (FCA) and pattern structures. FCA is naturally related to biclustering, where the objective is to simultaneously group rows and columns which verify some regularities. Related to FCA, pattern structures are its generalizations which work on more complex data. Partition pattern structures were proposed to discover constant-column biclustering, while interval pattern structures were studied in similar-column biclustering. Here we extend these approaches to enumerate other types of biclusters: additive, multiplicative, order-preserving, and coherent-sign-changes.

The second part of this thesis focuses on two experiments in mining complex data. First, we present a contribution related to the CrossCult project, where we analyze a dataset of visitor trajectories in a museum. We apply sequence clustering and FCA-based sequential pattern mining to discover patterns in the dataset and to classify these trajectories. This analysis can be used within CrossCult project to build recommendation systems for future visitors. Second, we present our work related to the task of antibacterial drug discovery. The dataset for this task is generally a numerical matrix with molecules as rows and features/attributes as columns.

The huge number of features makes it more complex for any classier to perform molecule classication. Here we study a feature selection approach based on log-linear analysis which discovers associations among features.

As a synthesis, this thesis presents a series of dierent experiments in the mining of complex real-world data.

Keywords: biclustering, feature selection, formal concept analysis, sequential pattern mining.

Figure 1 :

 1 Figure 1: Diagram of some basic steps in KDD.

  , M. Couceiro, A. Napoli, Biclustering Based on FCA and Partition Pattern Structures for Recommendation Systems at the Proceedings of the 2018 International Workshop What can FCA do for Articial Intelligence? @ 27th International Joint Conference on Articial Intelligence and the 23rd European Conference on Articial Intelligence, pp. 105116. N. Juniarta, M. Couceiro, A. Napoli, Application des Pattern Structures à la découverte de biclusters à changements de signes cohérents at Conference Francophone sur l'Extraction et la Gestion des Connaissances (EGC) 2019, pp. 285290. N. Juniarta, V. Codocedo, M. Couceiro, M. Kaytoue, A. Napoli Pattern Structures for Identifying Biclusters with Coherent Sign Changes at the Supplementary Proceedings of the 2019 International Conference on Formal Concept Analysis, pp. 315. N. Juniarta, M. Couceiro, A. Napoli, Order-preserving Biclustering Based on FCA and Pattern Structures. In A. Appice, M. Ceci, C. Loglisci, G. Manco, E. Masciari, Z.W. Ras (Eds), Complex Pattern Mining: New Challenges, Methods and Applications. Basel: Springer. (to be published) N. Juniarta, M. Couceiro, A. Napoli, A Unied Approach to Biclustering Based on Formal Concept Analysis at Conférence sur la Gestion de Données Principes, Technologies et Applications (BDA) 2019.

  , A. Napoli, A Unied Approach to Biclustering Based on Formal Concept Analysis and Interval Pattern Structures at the 2019 International Conference on Discovery Science, pp. 5160.

  based on: N. Juniarta, M. Couceiro, A. Napoli, C. Raïssi, Sequential Pattern Mining using FCA and Pattern Structures for Analyzing Visitor Trajectories in a Museum at the Proceedings of the 2018 International Conference on Concept Lattices and Their Applications, pp. 231242. N. Juniarta, M. Couceiro, A. Napoli, C. Raïssi, Sequence Mining within Formal Concept Analysis for Analyzing Visitor Trajectories at the 2018 International Workshop on Semantic and Social Media Adaptation and Personalization, pp. 1924.

1 Formal concept analysis and pattern structures Contents 1 . 1

 111 This chapter is based on: A. Ouali, N. Juniarta, B. Maigret, A. Napoli, A Feature Selection Method Based on Tree Decomposition of Correlation Graph at the 2019 Workshop on Advances in Managing and Mining Large Evolving Graphs @ European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases. Chapter Order theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Formal concept analysis . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Formal concept miners . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3.1 Close by One . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3.2 AddIntent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3.3 In-Close and In-Close2 . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4 Pattern structures . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

Figure 1 . 1 :

 11 Figure 1.1: Concept lattice of the formal context inTable 1.1. The number inside each node is

7 8 9 11 L 14 Y 15 X 1 :

 781114151 Process(A, g, (C, D)): 10 if {h|h ∈ C\A and h < g} = ∅ then := L ∪ {(C, D)} 12 foreach f ∈ {h|h ∈ G\C and g < h} do 13 Z := C ∪ {f } := D ∩ {f } := Y 16 Process(Z, f, (X, Y )) Close by One algorithm. The input is a formal context (G, M, I), while the output is the set of formal concepts B(G, M, I), denoted as L in the algorithm.

2. O 2 :

 2 A proper subset of the previous intent, 3. O 3 : Same as the previous intent.

  [START_REF] Andrews | In-Close, a fast algorithm for computing formal concepts[END_REF][START_REF] Andrews | In-Close2, a high performance formal concept miner[END_REF][4, 6] [5, 5][7, 8][5, 6] . Using CbO, the process of interval pattern concepts is illustrated in Fig. 1.5. More detail on IPS is provided in Chapter 4 of this thesis. Other complex structures, like partition and sequence, are explained in Chapter 3 and Chapter 5 respectively. 1.4. Pattern structures AddIntent(intent, GeneratorConcept, L): GeneratorConcept = GetMaximalConcept(intent, GeneratorConcept, L) if GeneratorConcept.Intent = intent then return GeneratorConcept end GeneratorParents := GetParents(GeneratorConcept, L) NewParents = ∅ foreach Candidate ∈ GeneratorParents do if Candidate.Intent ⊂ intent then Candidate := AddIntent(Candidate.Intent ∩ intent, Candidate, L) end addParent := true foreach Parent ∈ NewParents do if Candidate.Intent ⊆ Parent.Intent then addParent := false break end else if Parent.Intent ⊆ Candidate.Intent then Remove Parent from NewParents end end if addParent then Add Candidate to NewParents end end NewConcept := (GeneratorConcept.Extent, intent) L := L ∪ {NewConcept } foreach Parent ∈ NewParents do RemoveLink(Parent, GeneratorConcept, L) SetLink(Parent, NewConcept, L) end SetLink(NewConcept, GeneratorConcept, L) return NewConcept Algorithm 3: AddIntent algorithm.

Figure 2 . 2 :

 22 Figure 2.2: A binary block diagonal matrix.

Figure 2 . 3 :

 23 Figure 2.3: Generation of one successor by In-Close2.

m 1 m 2 m 3 m 4 m 1 m 2 m 3 m 4 Figure 2 . 4 :

 424 Figure 2.4: Generation of two successors by RIn-Close_CVC_P.

Fig. 2 . 3 ,

 23 Fig. 2.3, where the current node is a concept ({g 1 , g 3 , g 4 , g 6 }, {m 1 , m 2 , m 3 }). InClose2 generates at most one successor for every added attribute. By adding m 4 , InClose2 obtains the concept ({g 1 , g 4 }, {m 1 , m 2 , m 3 , m 4 }) as the successor.

Figure 2 . 5 :

 25 Figure 2.5: Generation of two successors by RIn-Close_CHV_P for additive biclustering.

m 1 m 2 m 3 m 4

 4 in m 4 have the same dierence with their corresponding values in m 1 , i.e.

Contents 3 . 1 41 3. 4 . 1 43 3. 5 46 3. 5 . 1

 3141414354651 The pattern structures of partitions . . . . . . . . . . . . . . . . . 35 3.1.1 Partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.1.2 Partition of objects . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.1.3 Partition pattern structures . . . . . . . . . . . . . . . . . . . . . . 38 3.2 Constant-column biclustering . . . . . . . . . . . . . . . . . . . . . 38 3.3 Additive and multiplicative biclustering . . . . . . . . . . . . . . 39 3.4 Order-preserving biclustering . . . . . . . . . . . . . . . . . . . . . Pattern structures for OP biclustering . . . . . . . . . . . . . . . . 41 3.4.2 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Biclustering with coherent sign changes . . . . . . . . . . . . . . Using constant-column biclustering . . . . . . . . . . . . . . . . . . 46 3.5.2 Using pattern structures of signed partition . . . . . . . . . . . . . 48 3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

Figure 3 . 2 :

 32 Figure 3.2: The calculation of d 1 d 2 where d 1 = {{1, 2}, {3}} and d 2 = {{1, 3}, {2}}.

. 1 )

 1 Consider the partitions d 1 = {{1, 2}, {3}} and d 2 = {{1, 3}, {2}}. The meet of these two partitions is {{1}, {2}, {3}}, illustrated in Fig.3.2.

Figure 3 . 3 :

 33 Figure 3.3: The calculation of d 1 d 2 where d 1 = {{1, 2}, {3}} and d 2 = {{1, 3}, {2}}. The ∪ between c i and c j is calculated only if c i ∩ c j = ∅.

  3.1.2, the function δ : M → D means that a partition of objects is the description of an attribute. Therefore, in (object) partition pattern structures, the triple is (M, (D, ), δ). Following Eq. 1.1, the derivation operators are dened for any subset of attributes and any description: : ℘(M ) → D, : D → ℘(M ). Given B ⊆ M and d ∈ D, these operators are dened by: B = m∈B δ(m), d = {m ∈ M |d δ(m)}.

(3. 4 )

 4 In other words, given subset of attributes B, B is the coarsest common renement of all object partitions of m ∈ B. Given an object partition d, d is the set of all attributes whose partition is a coarsening of d. Similar to FCA and other pattern structures, a partition pattern concept (or pp-concept) is a pair (B, d) where B = d and d = B. An example of pp-concept from Table

m 1 m 2 m 3 m 4 m 5 g 1 - 1

 11

  Figure 3.5: A graphical representation of the extent of

Figure 3 . 6 :

 36 Figure 3.6: Comparison of partition pattern structure (pps) and sequence pattern structure (sps) in the task of nding OP biclusters in matrices with 10 rows and varying number of columns.

Figure 3 . 7 :

 37 Figure 3.7: Runtime of pps-based approach with AddIntent and varying θ in obtaining 10K concepts, applied to the breast cancer dataset. Any partition component having elements less than θ is discarded.

Figure 3 . 8 :

 38 Figure 3.8: Runtime of sps-based approach with AddIntent and varying , applied to the breast cancer dataset. Any sequence having length less than is discarded.

1 9 set_of

 9 csc := ∅ 2 Scaling = new matrix /* a scaled matrix of S */ 3 foreach c a ∈ C do 4 foreach c b ∈ C, b > a do 5 new_column.elements ← XOR(c a , c b ) 6 new_column.title ← {c a , c b } 7 Scaling.add(new_column) 8 end _cc ← constant-column biclusters from Scaling 10 foreach cc_cluster ∈ set_of _cc do 11 /* cc_col is the columns of cc_cluster*/ 12 /* cc_row is the rows of cc_cluster */

Here b xAlgorithm 7 :a m 2 ×

 72 is contrasting to b z , because the sign in each column of b x (' -+ + ) is the opposite of those in b z (' + --). Therefore, ({r 1 , r 2 , r 4 }, {c 2 , c 3 , c 4 }) is a CSC bicluster. Meanwhile, b y is not contrasting to any other constant-column bicluster, thus b y itself is a CSC bicluster.ExperimentWe described two approaches of CSC biclustering: by constructing scaling matrices and performing constant-column biclustering and PPS on them (scaling-based ), or by applying PPS Input: A binary sign matrix S, with a set of columns C and a set of rows R Output: A set of CSC biclusters from S 1 csc := ∅ 2 pp_concepts ← PPS in S 3 foreach pp ∈ pp_concepts do 4 /* a pp is a pp-concept (A,d) 5 where A is the set of attributes 6 and d is partition of objects */ 7 foreach p a ∈ d do 8 foreach p b ∈ d, p a = p b do 9 if (p a , A) is contrasting with (p b , A) then 10 csc.add((p a ∪ p b , A)) 11 remove {p a , p b } from d PPS-based directly to the original matrix and searching CSC biclusters in each pp-concept (PPS-based ). In our experiment, we compare the execution time between the two approaches in some randomly generated numerical datasets. Therefore, given an m × n dataset, both methods preprocess it into n binary sign matrix.

Figure 3 . 9 :

 39 Figure 3.9: Comparison of scaling-based and PPS-based with number of objects = 20 and varying number of attributes.

Figure 3 . 10 :

 310 Figure 3.10: Comparison of scaling-based and PPS-based with number of attributes = 15 and varying number of objects.

  and d ∈ D are dened as: A = g∈A δ(g), (3.14) d = {g ∈ G|d δ(g)}.

(3. 15 )

 15 (A, d) is a signed partition pattern concept (or spp-concept) when A = d and d = A.

Figure 3 . 13 :

 313 Figure 3.13: Number of concepts generated until each iteration of AddIntent over lymphoma dataset.

Figure 3 . 14 : 1

 3141 Figure 3.14: Number of concepts generated until each iteration of AddIntent over BicAT yeast dataset.

Figure 4 . 1 :

 41 Figure 4.1: An example of nominal scaling.

  m

Figure 4 . 2 :

 42 Figure 4.2: An example of ordinal scaling.

Figure 4 . 3 :

 43 Figure 4.3: An example of interordinal scaling.

Figure 4 . 4 :

 44 Figure 4.4: The meet-semilattice of a set of intervals.

. 4 .

 4 The greatest lower bound or the meet ( ) of two intervals [a 1 , b 1 ] and [a 2 , b 2 ] is the smallest interval containing both [a 1 , b 1 ] and [a 2 , b 2 ]. This corresponds to the convex hull of the intervals, and dened as:

m 1 m 2 m 3 m 4

 4

9 12 L 16 Y 18 X 8 :

 1216188 Process(A, g, (C, D)): 10 if {h|h ∈ C\A and h < g} = ∅ then 11 if size(C) ≥ min_row then := h ∪ {(C, D)} 13 end 14 foreach f ∈ {h|h ∈ G\C and g < h} do 15 Z := C ∪ {f } := D ∩ {f } 17 if size(Z) < min_row then The introduction of min_row to CbO algorithm (line 1113 and 1722).

Figure 4 . 5 :

 45 Figure 4.5: Eect of θ on a 500 × 60 dataset with min_col = 20 and min_row = 1.

Figure 4 . 6 :

 46 Figure 4.6: Eect of min_col on a 500 × 60 dataset with θ = 1 and min_row = 5.

Figure 4 . 7 :

 47 Figure 4.7: Eect of min_row on a 500 × 60 dataset with θ = 1 and min_col = 6.

Table 4 . 6 :

 46 Comparison with BicPAM on 1000 × 100 dataset. For the IPS, the parameters min_row = 10 and min_col = 5 are used, with varying θ.

Contents 5 . 1 79 5. 5

 51795 CrossCult project . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 The mining of sequences . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Sequence mining in FCA . . . . . . . . . . . . . . . . . . . . . . . 5.4 The dataset of museum visitors . . . . . . . . . . . . . . . . . . . 5.4.1 The museum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5.4.2 The four visiting styles . . . . . . . . . . . . . . . . . . . . . . . . . Workow for analyzing the trajectories . . . . . . . . . . . . . . . 5.6 Clustering of trajectories . . . . . . . . . . . . . . . . . . . . . . . 5.7 The mining of trajectories considered as sequences . . . . . . . . 5.7.1 Mining subsequences with MFCS and MRGS . . . . . . . . . . . . . . . 80 5.7.2 Jumping emerging patterns . . . . . . . . . . . . . . . . . . . . . . 81 5.8 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.8.1 Cluster characterization . . . . . . . . . . . . . . . . . . . . . . . . 81 5.8.2 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

Figure 5 . 1 :

 51 Figure 5.1: Hasse diagram of {a}{b}{c} , {a}{c}{b} , and their subsequences.

Figure 6 . 1 :

 61 Figure 6.1: Two approaches of feature selection: lter model (a) and wrapper model (b).[START_REF] John | Irrelevant features and the subset selection problem[END_REF]

  For example, let's examine the model [W A][R]. This model has the equation:

Figure 6 . 4 :

 64 Figure 6.4: Decomposition of a graph D (a), into its two components (b) and (c).

Figure 6 . 5 :

 65 Figure 6.5: Maximal prime subgraphs of graph D in Fig. 6.4a.

Figure 6 . 6 :

 66 Figure 6.6: Examples of chordal (a) and non-chordal graph (b).

Figure 6 . 7 :Figure 6 . 8 :

 6768 Figure 6.7: An example of current best model (a). At each iteration, Chordalysis generates all possible candidates which dier only in one edge and are chordal. (b) is an available one, while (c) is not, because the addition of edge (1,4) won't keep the graph chordal.

2 1 precision + 1

 21 recall.

Figure 6 . 9 :

 69 Figure 6.9: The distribution of families in 4885 original attributes, 595 attributes of SC, and around 500 attributes of S24.

Figure 6 . 10 :

 610 Figure 6.10: Distribution of major attribute families in (a) the original set, (b) set SC, and (c) average of S2, S3, and S4. All values in percentages. Only sets weighting >5% are represented. Categories in green are the 4 most-represented in SC. Those in orange with description in italic are mostly ltered out of both SC and S24. Grey ones summarize remaining families (15% and <1%.

RésuméL

  'extraction de connaissances dans les bases de données (ECBD) est un processus qui s'applique à de (potentiellement larges) volumes de données pour découvrir des motifs qui peuvent être signiants et utiles. Dans cette thèse, on s'intéresse à deux étapes du processus d'ECBD, la transformation et la fouille, que nous appliquons à des données complexes. Nous présentons de nombreuses expérimentations s'appuyant sur des approches et des types de données variés.La première partie de cette thèse s'intéresse à la tâche de biclustering en s'appuyant sur l'analyse formelle de concepts (FCA) et aux pattern structures. FCA est naturellement liées au biclustering, dont l'objectif consiste à grouper simultanément un ensemble de lignes et de colonnes qui vérient certaines régularités. Les pattern structures sont une généralisation de la FCA qui permet de travailler avec des données plus complexes. Les partition pattern structures ont été proposées pour du biclustering à colonnes constantes tandis que les interval pattern structures ont été étudiées pour du biclustering à colonnes similaires. Nous proposons ici d'étendre ces approches an d'énumérer d'autres types de biclusters : additif, multiplicatif, préservant l'ordre, et changement de signes cohérents. Dans la seconde partie, nous nous intéressons à deux expériences de fouille de données complexes. Premièrement, nous présentons une contribution dans la quelle nous analysons les trajectoires des visiteurs d'un musée dans le cadre du projet CrossCult. Nous utilisons du clustering de séquences et de la fouille de motifs séquentiels basée sur l'analyse formelle de concepts pour découvrir des motifs dans les données et classier les trajectoires. Cette analyse peut ensuite être exploitée par un système de recommandation pour les futurs visiteurs. Deuxièmement, nous présentons un travail sur la découverte de médicaments antibactériens. Les jeux de données pour cette tâche, généralement des matrices numériques, décrivent des molécules par un certain nombre de variables/attributs. Le grand nombre de variables complexie la classication des molécules par les classieurs. Ici, nous étudions une approche de sélection de variables basée sur l'analyse log-linéaire qui découvre des associations entre variables. En somme, cette thèse présente diérentes expériences de fouille de données réelles et complexes.

Table 1 .

 1 1: A formal context with four objects and ve attributes.

Table 1 .

 1

		m 1 m 2 m 3
	g 1	5	7	6
	g 2	6	8	4
	g 3	6	7	5

2: A numerical context. Contents 2.1 Clustering and biclustering . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Basic denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3 Previous works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3.1 Probabilistic and numerical methods . . . . . . . . . . . . . . . . . 23 2.3.2 Pattern-based methods . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

Table 2 .

 2

	2 2 2 2	4 2 5 3	4.0 2.5 5.7 3.1	2 3 5 1	2 6 12 4
	2 2 2 2	4 2 5 3	3.9 2.4 5.6 3.0	5 6 8 4	1 3	6 2
	2 2 2 2	4 2 5 3	4.1 2.4 5.9 2.9	1 2 4 0	4 12 24 8
	2 2 2 2	4 2 5 3	4.1 2.6 5.8 2.9	4 5 7 3	3 9 18 6
	(a)	(b)	(c)	(d)	(e)
		2 1 3 4
		5 1 8 9
		6 5 7 11
		1 -9 2 9

1: Examples of some bicluster types: (a) constant-value, (b) constant-column, (c) similarcolumn, (d) additive, (e) multiplicative, (f ) order-preserving, (g) coherent-sign-changes.

Table 2

 2

	.1b. CC biclustering has more relaxed

  where T ⊆ M , |T | = s, and π = (t1 , t 2 , • • • , t s ) is a linear ordering of T . A pair (T, π) is supported by an object g if the permutation of T in g follows π, i.e. t 1 (g) < t 2 (g) < • • • < t s (g).The algorithm tries to nd some (T, π) that are statistically signicant. Similar to SAMBA, here statistically signicant means that a pair (T, π) has a low probability to be supported by high number of objects. This probability of observing a (T, π) with |T | = s supported by k objects is:

	1	1	2	3	4
	2	2	4	6	8
	3	× 1 2 3 4 = 3 6	9	12
	4	4	8	12	16
	5	5	10	15	20
	Figure 2.1: A multiplicative bicluster as matrix multiplication.
	OPSM is modeled as a pair (T, π),

Table 2 .

 2

	2: An example of the transformation from (a) matrix after mapping step to (b) transac-
	tion dataset.

Table 2 .

 2 3: Examples of additive alignment of Table 2.2a: the alignment of (a) m 1 and (b) m 2 .G m 1 m 2 m 3 m 4 m 5 g 1

		8	6	3	14	16
	g 2	8	6	20	14	16
	g 3	8	5

Table 2 .

 2 4: Examples of multiplicative alignment of Table 2.2a: the alignment of (a) m 1 and (b) m 2 .

	G m 1 m 2 m 3	m 4	m 5	G m 1 m 2 m 3	m 4	m 5
	g 1	8	24	48	-40 -56	g 1	4	12	24	-20 -28
	g 2	8	16	-40 -16 -24	g 2	6	12	-30 -12 -18
	g 3	8	2	-12 -6	2	g 3 48 12 -72 -36 12
	g 4	8	2	-6	-6	1	g 4 48 12 -36 -36	6
	g 5	8	3	-6	1	1	g 5 32 12 -24	4	4
				(a)						(b)

Table 2 .

 2 5: The sequence dataset, result of transformation of the matrix in Table 2.2a.

Table 2 .

 2

6: A numerical matrix having additive biclusters.

Table 3 .

 3

1: A numerical table

Table 3 .

 3 2: Partition pattern concepts from Table3.1 and their corresponding constant-column biclusters.

	Extent	Concept	Intent	Bicluster	Maximal

Table 3 .

 3 3: Running example for additive and multiplicative biclustering.

Table 3 .

 3

		4: Running example for order-
	preserving biclustering.
		m 1 m 2 m 3 m 4 m 5
	g 1	1	2	3	4	5
	g 2	4	2	1	5	3
	g 3	2	3	4	1	5
	g 4	5	4	2	3	1
	g 5	2	1	5	4	3

Table 3 .

 3 5: Some examples of pairs and their partitions over Table 3.4. , g 2 , g 3 , g 5 }, {g 4 }} Using the corresponding denition of for each type, we can follow Eq. 3.4 to obtain object partition concepts. In a concept (B, d) any pair (c ∈ d, B) is a bicluster, where we can omit the mark of each object. For example, in Table 3.3, ({m 1 , m 2 , m 4 , m 5 }, {{g -1 1 , g -2 2 }, {g 4 3 }, {g 8 4 }, {g 8 5 }}) is a concept for additive biclustering, and the pair ({g 1 , g 2 }, {m 1 , m 2 , m 4 , m 5 }) is an additive bicluster. Furthermore, ({m 1 , m 2 , m 4 }, {{g -1 }}) is a concept for multiplicative biclustering, and the pair ({g 3 , g 4 }, {m 1 , m 2 , m 4 }) is a multiplicative bicluster.

	Pair	Partition
	r 1 2 r 1 3 r 1 4 r 2 3 r 2 5	{{g 1 , g 3 }, {g 2 , g 4 , g 5 }} {{g 1 , g 3 , g 5 }, {g 2 , g 4 }} {{g 1 , g 2 , g 5 }, {g 3 , g 4 }} {{g 1 , g 3 , g 5 }, {g 2 , g 4 }} {{g 1

  Consider the binary sign matrix given in Table3.7a. This matrix can be scaled into three binary matrices in Table3.7b, where each pair of columns (c a , c b ) constitutes a new column. The new columns have value 1 if the pair's sign is dierent, and 0 if it is the same (a XOR operation).For example, the value in row r 2 column c 1 c 3 is 0 because in r 2 , both c 1 and c 3 are `-'. Then, we perform constant-column biclustering in each new binary matrix. A constant-column bicluster found in this new table corresponds with a CSC bicluster on the original table, as shown in Table3.8. The set of columns in a CSC bicluster is a union of attribute pairs in constant-column bicluster's columns.

	13	csc_col ← cc_col.title
	14	csc_row ← cc_row
	15	csc.add((csc_row, csc_col))
	16	end
	17	Scaling.clear()
	18 end
	19 return csc
		Algorithm 6: scaling-based

Table 3 .

 3 7: (a) A binary sign matrix and (b) its three scaling matrices.

	constant-column biclusters	CSC biclusters

Table 3 .

 3 9: Running example for coherent-sign-changes biclustering.

  1 , d 1 ) and (A 2 , d 2 ) such that (A 1 , d 1 ) ≤ (A 2 , d 2 ), and an sp-component c. The bicluster (A 1 , c) is maximal i c ∈ d 1 and c ∈ d 2 .

	For example, consider the concept p 1 = ({g 1 , g 2 , g 4 , g 5 }, {{m + 1 , m + 2 }, {m + 3 , m + 4 }}) and p 2 = ({g 1 , g 2 , g 3 , g 4 , g 5 }, {{m + 1 , m + 2 }, {m + 3 }, {m + 4 }}),

where p 1 ≤ p 2 . We see that the sp-component {m + 1 , m + 2 } is in the intent of both p 1 and p 2 . Therefore, the bicluster ({g 1 , g 2 , g 4 , g 5 }, {m 1 , m 2 }) from p 1 is not maximal.

Table 3 .

 3 11: Experiments on lymphoma dataset.

	θ	Runtime	Number of concepts	Largest extent size
		(minutes)	All	Extent size > 1
	70	229.4	157K	153K	8
	80	62.9	7K	2K	7
	90	62.1	4K	83	3

Table 4 .

 4 1: A numerical matrix, and a similar-column bicluster in gray. is subsumed by d 2 if each interval in d 1 is subsumed by the corresponding interval in d 2 .Interval pattern structures was originally proposed to obtain similar-column (SC) bicluster in gene expression dataset (GED). A GED is typically represented as a 2-D numerical matrix with genes as rows and conditions as columns, as shown in Table4.1. In this matrix, the submatrix ({g 1 , g 2 , g 3 }, {m 1 , m 2 , m 3 , m 5 }) is an SC bicluster, dened by the parameter θ = 1. It means that the range of values of each column in the submatrix has the length of at most 1.

	G m 1 m 2 m 3 m 4 m 5
	g 1	1	2	2	1	6
	g 2	2	1	1	0	6
	g 3	2	2	1	7	6
	g 4	8	9	2	6	7
	reecting that d 1

  .1, δ(g 2 ) δ(g 4 ) without θ is and any other interval is * . For example, suppose that we have two descriptionsd x = [1, 1][2, 3] and d y = [2, 2] * . Then, d x d y =[START_REF] Agrawal | Fast algorithms for mining association rules[END_REF][START_REF] Ailem | Graph modularity maximization as an eective method for co-clustering text data[END_REF] * . This also means that * is subsumed by any other interval. Therefore, the description of each object in Table4.1 subsumes * * [1, 2] *[6,[START_REF] Andrews | In-Close, a fast algorithm for computing formal concepts[END_REF] . With θ = 1, ({g 1 , g 2 , g 3 , g 4 }, * * [1, 2] *[6,[START_REF] Andrews | In-Close, a fast algorithm for computing formal concepts[END_REF] ) is an interval pattern concept. All interval pattern concepts with θ = 1 from Table4.1 are listed in Table 4.3.

	[2, 8][1, 9][1, 2][0, 6][6, 7] , and with θ = 1 is * * [1, 2] * [6, 7] .
	The similarity	between *

Table 4 .

 4 2: All interval pattern concepts from Table 4.1.

Table 4 .

 4 3: All interval pattern concepts with θ = 1 from Table4.1.

Table 4 .

 4 4: Example of additive column alignments. (a) Original table and the additive bicluster in gray, (b) alignment on m 1 , (c) alignment on m 2 .

Table 4 .

 4 5: Example of multiplicative column alignments. (a) Original table and the multiplicative bicluster in gray, (b) alignment on m 2 .

		m 1 m 2 m 3 m 4
	g 1	3	1	2	3
	g 2	1	3	6	9
	g 3	2	2	4	6
	g 4	1	2	6	8
			(a)

Table 4 .

 4 4 provides an example of column alignment for additive biclustering. The original matrix is shown in Table 4.4a, having 4 rows and 4 columns. The submatrix ({g 1 , g 2 , g 3 }, {m 2 , m 3 , m 4 })

  After the mapping step (normalization, discretization, and missing values and noise handling), BicPAM applies a pattern mining method (F2G[START_REF] Henriques | F2G: Ecient discovery of full-patterns[END_REF] as default), and the closing step (extension, merging, and ltering) is performed. Results in Table4.6 show a similar performance of both methods. It should be noted that the number of biclusters from BicPAM is lower due to the closing step.

Table 4 .

 4 7: Comparison of additive biclustering using Cheng and Church's algorithm (CC) and IPS-based algorithm. The size of a bicluster is dened as the number of its cells.

	MSR max.	Method & parameters	Runtime (s)	Number of biclusters	Size of biclusters max min
	0.001	CC	13.37	97	56	6
	0.001	IPS (θ = 0.1, r = 2, c = 10)	13.02	500	58	20
	0.01	CC	3.80	35	630	18
	0.009	IPS (θ = 0.3, r = 2, c = 10)	3.02	100	52	20
	0.02	CC	2.21	20	1275	30
	0.02	IPS (θ = 0.5, r = 4, c = 10)	2.52	75	110	40
	0.03	CC	1.43	16	2070	33
	0.03	IPS (θ = 1, r = 7, c = 10)	1.56	50	240	70
	0.04	CC	1.24	13	2821	39
	0.043	IPS (θ = 1.4, r = 10, c = 10)	2.14	50	430	310
	MSR = mean squared residue;

θ = maximum width of an interval; r = minimum number of rows in a bicluster = minimum extent size of a concept; c = minimum number of columns in a bicluster = minimum number of non-* intervals in a concept's intent.

nds the largest bicluster at the rst iteration. Then it masks the submatrix corresponding to this bicluster, so in the next iteration, another smaller bicluster is found. The iteration stops when the algorithm can not nd any more bicluster. Consequently, this also means that CC retrieves many small biclusters. These small biclusters can be discarded in IPS via the parameters min_row and min_col (in Table

4

.7, r and c respectively). Therefore, in the table, we can see that with similar MSR and runtime, the smallest bicluster found by IPS is still larger than the smallest bicluster found by CC.

Table 5 .

 5 1: An example of one visitor trajectory. subsequences, where the similarity operation is based on the discovery of SCCS. 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

	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

of

  ,502,503 } { 401,503,502 } = { 401,502 , 401,503 } It should be noticed that MFCS mines contiguous subsequences, i.e. in Denition 13, 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 category5. In parallel, the default similarity operator of MRGS algorithm can be modied to accommodate our needs, such that non-contiguous common subsequences can be mined:δ(S 1 ) δ(S 2 ) = { 401,502,503 } { 401,503,502 } = { 401,502 , 401,503 , 401,5,5 }

	In the dataset, the items are grouped into categories (indicated by their rst 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 }

Table 5 .

 5 4: The concepts that are computed by of MFCS and MRGS from four visitors in Table5.3.

	Extent	Intent (MFCS)	Intent (MRGS)
	V 1	101,101,401,704
	V 2	102,402,808,206,808
	V 3	302,102,201,302,705,402,802
	V 4	104,704,602,302,402,103
	V 1,2	1,4	not present
	V 1,4	1 , 4 , 704	1,1 , 1,4 , 1,704
	V 2,3	2 , 102 , 402,8	102,402,8 , 102,2,8
	V 3,4	1 , 302 , 402 , 7	1,302,402 , 302,1 , 1,7,402
	V 1,3,4	1 , 4 , 7	1,4 , 1,7
	V 2,3,4	1 , 402	1,402
	V 1,2,3,4	1 , 4	1,4
	5.7.2 Jumping emerging patterns

Table 5 .

 5 5: Interesting concepts discovered by the MFCS algorithm.{V 70 , V 107 , V 121 , V 133 , V 201 , V 202 } { 1,1,402 , 103 , 2 } , V 8 , V 28 , V 32 , V 84 , V 152 } { 102 , 101,1,101 } {V 53 , V 152 , V 169 , V 189 , V 190 , V 203 } { 7 , 102,4 }

	Concept ID	Extent	Intent	Support	Cluster
	FA1			6	A
	FA2	{V 70 , V 93 , V 107 , V 121 }	{ 402 , 103,104 }	4	A
	FB1	{V 103 , V 165 , V 188 }	{ 4 , 1 , 306 , 701,707 } 3	B
	FC1	{V 4 6	C
	FC2			6	C
	FC3	{V 4 , V 8 , V 32 }	{ 101,102,101 }	3	C
	FD1	{V 54 , V 105 , V 139 , V 168 }	{ 202,4 }	4	D
	FD2	{V 139 , V 168 }	{ 202,405,701 }	2	D
	FD3	{V 46 , V 47 }	{ 101,602 }	2	D
	FD4	{V 89 , V 163 }	{ 602,203 }	2	D

Table 6 .

 6 1: An example of contingency table of a dataset about molecular weight (W ), number of atoms (A) and ring perimeter (R)[START_REF] Tabachnick | Using Multivariate Statistics[END_REF].

	Molecular weight	Number of atoms	Ring perimeter Narrow Wide	Total
	Light	Small	15	15	30
		Large	10	15	25
		Total	25	30	55
	Medium	Small	10	30	40
		Large	5	10	15
		Total	15	40	55
	Heavy	Small	5	5	10
		Large	10	25	35
		Total	15	30	45

  .2)Moreover, G 2 statistic is used because of its additivity property, which is not present in χ 2 statistic. Therefore, in a two-way analysis of variable A and B, test of overall association G 2

	the sum of rst-order tests, G 2 A and G 2 B , and association test G 2 AB :	T is

  Figure 6.3: A graph with 6 vertices. Its maximal cliques are {1, 2, 3, 4}, {2, 4, 5}, and {5, 6}, with {1, 2, 3, 4} as the maximum clique. Its minimal separators are {2, 4} and {5}, with {5} as the minimum separator. The minimal (2, 6)-separator is {5}.

	A	R
	Figure 6.2: Graphical representation of log-linear model in Eq. 6.4.
	1	2
		5	6
	3	4

Meanwhile, if we exclude λ W AR (war):

ln E war = θ + λ W (w) + λ A (a) + λ R (r) + λ W A (wa) + λ W R (wr) + λ AR (ar) (6.6)

we can't use the graph in Fig.

6

.2 as its representation. The graph is complete, so it should have λ W AR (war). But the model in Eq. 6.6 doesn't have it. Actually, we can't draw a graph with λ W A (wa), λ W R (wr), and λ AR (ar) without including λ W AR (war). Consequently, the model in Eq. 6.6 is not graphical.

Table 6 .

 6 2: Attribute lters from previous work.

	Filter	Standard deviation	Pair correlation	# of selected attributes
	1	> 0.010	< 0.4	87
	2	> 0.010	< 0.8	576
	3	> 0.001	< 0.8	588
	4	> 0.100	< 0.8	524
	6.7 Experiments

Table 6 .

 6 3: Intersections of the sets of attributes from three lters and from Chordalysis.

	Set	S2	S3	S4
	SC (595 attr.)	153	154	146
	S2 (576 attr.)		569	497
	S3 (588 attr.)			496
	S4 (524 attr.)

Table 6 .

 6 4: Population of most relevant attribute families. Last column is the number of attributes present in all sets (SC, S2, S3 and S4). Percentages correspond to the number of retained attributes from the original set.

	Attribute family	Original set	SC	Overlap
	2D atom pairs	1596	373 (23%)	80
	2D matrix-based	550	2	1
	Edge adjacency ind.	324	2	1
	GATEWAY	273	7	1
	Functional group cnt.	154	66 (43%)	24
	CATS 2D	150	31 (21%)	19
	Atom-centered frag.	115	38 (33%)	10
	Drug-like indices	27	15 (56%)	1
	TOTAL	4885	595 (12%)	144 (3%)

Table 6 .

 6 5: Means and standard deviations of classiers' metrics on the test set. All data in percentages. Table 6.6: Precision and recall of random forest classier on the test set. All values in percentages.

	Metric	SVM (C = 0.01) Random Forest Naive Bayes
	Accuracy		97.0 ± 2.5		96.6 ± 1.5	55.7 ± 1.4
	Recall		98.9 ± 2.0		95.6 ± 1.5	21.2 ± 0.6
	Precision		95.9 ± 3.5		98.3 ± 2.2	93.7 ± 9.1
	AUC		99.3 ± 1.1		99.5 ± 0.4	65.3 ± 4.5
	f 1 score		97.3 ± 2.2		96.9 ± 1.3	34.5 ± 1.0
	α		4532 attributes	SC
			Precision	Recall	Precision	Recall
	10		10.0	71.2	11.6	65.4
	20		10.7	68.4	11.8	64.5
	30		11.8	65.4	12.2	63.5
	40		11.8	65.4	12.2	63.5
	50		12.3	64.3	12.3	63.0
	60		13.3	61.5	12.6	62.4
	70		14.1	60.1	12.8	61.8
	80		14.1	60.1	12.8	61.8
	90		15.1	59.1	13.0	61.2
	100	16.6	56.3	13.3	60.1
	would possess antibacterial properties.

Table 6 .

 6 3 lists the number of overlapping selected attributes from S2, S3 and S4 with SC.

Table 6 .

 6 4 summarizes SC-related data for most-relevant attribute families identied above, and highlights the number of consensus attributes i.e. attributes found in all sets.Training/testing strategy Using attributes in SC, we trained SVM, random forest, and naive Bayes on data from market antibacterials, MDDR antibacterials, Life Chemicals non-antibacterials, and MDDR nonantibacterials. After the training process, the three classiers are tested on Life Chemicals list of predicted antibacterials. The results are summarized in Table6.5. By tuning the parameter

Table 6 .

 6 7: Precision and recall of SVM classier on the test set. All values in percentages.

	α	4532 attributes	SC
		Precision	Recall	Precision	Recall
	10	21.3	16.4	11.1	82.7
	20	24.0	15.2	13.3	78.1
	30	25.9	12.8	17.0	71.9
	40	25.9	12.8	17.0	71.9
	50	26.6	12.5	19.0	69.9
	60	27.4	11.8	23.8	65.1
	70	27.9	11.4	27.2	62.4
	80	27.9	11.4	27.2	62.4
	90	27.7	10.0	31.8	58.7
	100	32.4	9.2	39.9	53.4

http://www.tik.ee.ethz.ch/sop/bicat/

https://CRAN.R-project.org/package=biclust

Remerciements

thank Région Grand Est and the CrossCult project,

In the task of biclustering, we explore the potential of enumerating biclusters in numerical datasets using FCA. One task of FCA is enumerating formal concepts, which is a set of objects and attributes having regularity among them. FCA is generalized into pattern structures, from which biclustering in numerical matrix is possible. Two previous works of FCA-based biclustering are the starting point for this part of the thesis. Partition pattern structures (PPS) and interval pattern structures (IPS) were proposed to mine constant and similar column biclusters. In this thesis we generalize these approaches to mine other bicluster types. First, we adapt the original PPS by modifying the similarity operator between two partitions, such that other bicluster types: additive, multiplicative, order-preserving, and coherent-sign-changes can also be found in a partition pattern concept. Second, we generalize IPS to perform non-perfect additive and multiplicative biclusterings, using column alignments. We show that PPS and IPS can be adapted to enumerate various types of biclusters, and by providing a parameter of expected bicluster size, we can perform this task in a reasonable runtime.

The second part of this thesis has two major axis. The rst is related to CrossCult project, a European Project whose general idea is to support the emergence of a European cultural heritage. One aspect of this project is to build a mobile application that registers, among others, the trajectory of each visitor while they interact with it, providing a kind of sequential dataset.

A particular dataset is concerned with the trajectories of around 200 visitors in Hecht Museum in Haifa, Israel. Each trajectory is composed by sequence of visited items. We develop a method to understand these trajectories such that the visitor behaviors can be extracted according to the four theoretical visiting patterns. This approach is composed of two independent steps: the clustering and the mining of trajectories. Given that the trajectory dataset can be regarded as a sequential dataset, a proper sequence clustering method is used where the distance between any two sequences is obtained from the number of their common subsequences. On the other hand, the mining of trajectory patterns is performed by two methods based on FCA. These patterns are then used to nd the characteristic behavior of each cluster. Our result highlights some interesting patterns that may dene visitor behaviors. This can help museum researchers to analyze and evaluate the placement of items and the visiting styles. Moreover, this analysis is useful to build a recommendation system for future visitors.

The second is related to mining associations among attributes in a numerical molecular dataset. These associations are used to perform attribute selection, which can reduce the complexity of the dataset. Such attribute associations can be found using log-linear analysis, and fur-