Clément Delion

Ludovic Journaux

Aurore Payen

Lucile Sautot

Emmanuel Chevigny

Pierre Curmi

NLDR methods for high dimensional NIRS dataset: application to vineyard soils characterization

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

NIRS is an ecient spectroscopic method for the quantication and characterization of soil components. Generally NIRS analyses are focusing on some regions of the spectrum as in [START_REF] Stenberg | Chapter ve-visible and near infrared spectroscopy in soil science[END_REF] while other studies are focussing on the all spectral signature treated by linear Principal Component Analysis (PCA) in order to identify biogenic structures [START_REF] Velasquez | This ped is my ped: visual separation and near infrared spectra allow determination of the origins of soil macroaggregates[END_REF]. Unfortunately, these high dimensional (HD) datasets are dicult to handle, as the information is often redundant and highly correlated with one another. Moreover, this HD dataset can suer from the curse of dimensionality [START_REF] Hughes | On the mean accuracy of statistical pattern recognizers[END_REF], like norm concentration and hubness. Thus, to improve the characterization performance and/or HD data visualization, it is well interesting to use NLDR techniques to transform HD data into a meaningful representation of reduced dimensionality. Some studies have tried to compare NLDR methods to linear methods, often for synthetic data such as the swissroll, but less for HD natural data. The aims of this paper is to nd the best NLDR method applied to the dataset in order to characterize vineyard soils. A double variability is analyzed: an interspecic due to dierent sites,and an intraspecic due to the samples. Thus, we will make a global analysis, then an analysis depending on soil depth. This paper is organized as follows.Section 2 presents the NIRS dataset sampling used on this context, the fractional metrics and an NLDR methods overview with a comparison based on a quality assessment. Section 3 presents and discusses experimental results. Section 4 draws the conclusions.

2 Materials and methods

Presentation of the NIRS dataset

NIRS dataset comes from four representative vineyard places of Burgundy: Aloxe Corton, Couchey, Maranges and Monthelie. Samples are extracted on surface and at dierent soil depths. For each sample (dried, screened and crushed), three NIRS acquisition are made with a FieldSpec 3 (ASD Inc.). Each spectrum scans wavelengths between 350 and 2500 nm. Therefore the dataset present a dimensionality of 2151. For each places numerous samples were taken. The gathered results are characterized by one of the four sites and the soil layer that is associated with them. Finally, we obtain 13 drillings in Aloxe Corton, 14 in Couchey, 11 in Maranges and 8 in Monthelie.

Overview of dierent methods of dimensional reduction

We select nine of DR methods based on their scale analysis, reecting the compromise based by NLDR methods between global structure and preservation of neighborhood at a local scale, and their distance or similarity. We retained 7 NLDR methods completed with to 2 linear methods: the Classical Multidimensional Scaling (CMDS) and the Non-metric Multidimensional Scaling (NMDS) [START_REF] Aldo | Nonlinear Dimensional Reduction[END_REF]. Non Linear Mapping (NLM): Sammon's mapping [START_REF] Aldo | Nonlinear Dimensional Reduction[END_REF] tries to preserve the neighborhood topology of data by minimizing dierences in distances between the HD space and the low-dimensiona (LD) space by the Sammon's space function. Curvilinear Component Analysis (CCA) [START_REF] Aldo | Nonlinear Dimensional Reduction[END_REF] tries to preserve pairwise distances, but gives priority to small distances by incorporating the divergence of Bregman in its stress function [START_REF] Sun | Curvilinear component analysis and bregman divergences[END_REF]. Stochastic Neighbor Embedding (SNE) [START_REF] Georey | Advances in neural information processing systems, chapter Stochastic neighbor embedding[END_REF] is a non-linear reduction method based on similarities between points, which converts pairwise distances into probabilities that represent similarities, where the most similar points have a higher probability, and then recalculates these probabilities in the LD space and minimizes the Kullback-Leibler (KL) divergence between two distributions. t-distributed Stochastic Neighbor Embedding (t-SNE) [START_REF] Van Der Maaten | Visualizing data using t-sne[END_REF] is similar to SNE, dierence is in the calculation of the probability distributions. The SNE uses a Gaussian distribution, while the t-SNE is based on a Student distribution. Neighbor Retrieval Visualizer (NeRV) [START_REF] Venna | Information retrieval perspective to nonlinear dimensionality reduction for data visualization[END_REF] is similar to the t-SNE. The main dierence is the minimization of two dual KL divergences, that are related to precision and recall, instead of a single KL divergence. The optimization of two functions, and not only one, allows a better optimization of the divergence. Jensen-Shannon Embedding (JSE) [START_REF] John A Lee | Type 1 and 2 mixtures of kullbackleibler divergences as cost functions in dimensionality reduction based on similarity preservation[END_REF] is based on the preservation of the neighborhood. Unlike previous methods JSE uses the Jensen-Shannon divergence instead of the KL divergence to measure the similarities between two probability distributions. Multiscale Jensen-Shannon Embedding (Ms. JSE) [START_REF] Lee | Multiscale stochastic neighbor embedding: Towards parameter-free dimensionality reduction[END_REF] is an improvement of JSE which overcomes the problematic of the neighborhood size by taking into account multiple sample sizes, thanks to a log scale.

Fractional distance transformation

Nearest neighbor research often rely on the use of the euclidean distance. Unfortunately when data represent a high dimensional features, the euclidean distances seem to concentrate and all distances between pairs of data elements seem to be very similar. Therefore, the pertinence of the euclidean distance has been questioned in dierent works, and fractional distance has been proposed in order to overcome the problem of concentration phenomenon or curse of dimensionality such as in [START_REF] François | The concentration of fractional distances[END_REF]. In order to test if fractional distance can improve NDLR result, we test it on our NIRS dataset.

Quality criterion used for an objective comparison

In order to compare dierent methods between them. We use the quality assessment criterion [START_REF] Aldo | Quality assessment of dimensionality reduction: rank-based criteria[END_REF]. An evaluation based on the performance of cost functions of NLDR methods is irrelevant, due to the variability of criterions used in cost functions (mean,variance, standard deviation...). Therefore, a k-neighborhood quality function is dene and we compare it to an average random projection. Then we compute the area under the curve (AU C) of representing the score which is a scale-independent quality criterion for comparing methods:

AU C = N -2 K=1 100 N -1 N -K N -2 K=1 |v K i ∩n K i | KN -K N -1 /K N -2 K=1 1/K
with K: number of neighbors, N : number of points, v: vector of K nearest neighbors of point i in HD space, n: vector of K nearest neighbors of pointi in LD space.

3 Results and discussion

Results on raw data and fractional distance

We rst compared the NLDR methods on the raw NIRS dataset with the quality criterion (gure 1). Ms. JSE seems the best method with 76.8% of improvement over a random projection. The CMDS (64.1%) gives also good results but is less eective according to the quality criterion. Even if CMDS is very successful at a global scale, Ms. JSE is better due to good representation of both global and local scales. MS JSE will be used in section 3.3 for soil characterization. The use of an other metric, like fractional distances, can conrm the choice of Ms. JSE as preferential NLDR method. Some studies introduce fractional distances as an alternative of Euclidean distances to analyze dataset. So this is a good basis to conrm the previous comparison. Ms. JSE is again the best method with an improvement of 73.9% over a random projection is obtain. Unfortunaltely, the results obtain show that the fractional distances give poorer results than Euclidean distances with all methods. The only exception is with the t-SNE which loses only 0.1%. Following the choice of Ms. JSE as the best approach, we specically project the NIRS data with this method (gure 2). Remember that the Aloxe Corton boreholes are numbered 1 to 13, those of Couchey from 14 to 27, those of Maranges from 28 to 38 and those of Monthelie from 39 to 46. The projection shows a data organization in clusters. We can observe that each cluster represent sampling place (it may be noted that boreholes of the same place are closed). Moreover, the analysis of the Maranges place clearly shows two clusters, representing two dierent types of soil on this site, which conrms the capability of Ms. JSE to discriminate dierent clusters and so soils characteristics.

Clustering on NIRS dataset depending on depth

In order to recognize dierent terroirs of Burgundy, we perfom a k-means algorithm on the same depth data points. We assumed that there were 5 clusters corresponding to terroirs. So we used the k-means method with 5 clusters as the input argument. Each gure has its own clusters at each depth. Thus, we are able to nely sign and visualize the composition of vineyard soils layers for each depth (gure 3).

Discussion

In this paper, we demonstrate the Ms. JSE eciency. But gure 1 shows that Ms. JSE has medium performances at a global scale. In fact, Ms. JSE is the best trade-o between local and global scale: we can tolerate medium performances at global scale because local performances are very high. In some cases that involve considerating global performances, CMDS, NMDS or NLM can therefore provide best results than Ms. JSE. Thus, the superiority of Ms. JSE is proved only for our application case and cannot be considered as a general statement. This paper explores the comparison and application of dierent NLDR methods on a high-dimensional dataset in order to characterize vineyard soils by their spectral signatures. We determine that Ms. JSE with Euclidean distances is the most suitable method for our biological dataset, thanks to a quality criterion based on the k-nearest neighbor algorithm. The global analysis shows dierent types of vineyard soils. Finally we try a clustering in an analysis by depth and highlight 5 clusters with the k-means algorithm. Then the determination of the spectral signature of a vineyard soil permits less analysis to determine its chemical composition.

Figure 1 :

 1 Figure 1: Comparison of DR methods with R N X functions on the raw NIRS dataset 3.2 Resulting projection of the data with Ms. JSE

Figure 2 :

 2 Figure 2: Results of Ms. JSE on NIRS dataset (R N X : 85.3%)

Figure 3 :

 3 Figure 3: Results on depth data with k-means clustering (K=5)


Lucile Sautot
email: lucile.sautot@u-bourgogne.fr

Sandro Bimonte
email: sandro.bimonte@irstea.fr

Ludovic Journaux
email: ludovic.journaux@agrosupdijon.fr

Bruno Faivre
email: bruno.faivre@u-bourgogne.fr

Mixed driven Refinement design of Multidimensional models based on Agglomerative Hierarchical Clustering

Keywords: Multidimensional design, Data Warehouse, OLAP, Data Mining

. Therefore, in this paper we propose a new mixed refinement design methodology where the classical data-driven approach is enhanced with data mining to create new dimensions hierarchies. A tool implementing our approach is also presented to validate our theoretical proposal.

INTRODUCTION

Data warehouses (DW) and OLAP systems are business intelligence technologies allowing the online analysis of huge volume of data. Warehoused data is organized according to the multidimensional model that defines the concepts of dimensions and facts. Dimensions represent analysis axes and they are organized in hierarchies. Facts are the analysis subjects and they are described by numerical indicators called measures. Warehoused data are then explored and aggregated using OLAP operators (e.g. Roll-up, Slice, etc.) [START_REF] Kimball | The Data Warehouse Toolkit: Practical Techniques for Building Dimensional Data Warehouses[END_REF].

The success of DW projects essentially depends on the design phase where functional requirements meet data sources [START_REF] Phipps | Automating data warehouse conceptual schema design and evaluation[END_REF]. Three main methodologies have been developed: userdriven, datadriven and mixed [START_REF] Romero | A survey of multidimensional modeling methodologies[END_REF]. User-driven approach puts decision-makers at the center of the design phase by providing them tools to define the multidimensional model exclusively according to their analysis needs. Usually, data driven methodology proposals deduce the multidimensional model from structured and semistructured [START_REF] Mahboubi | X-wacoda: an xml-based approach for warehousing and analyzing complex data[END_REF][START_REF] Jensen | Discovering multidimensional structure in relational data[END_REF] data sources exploit-ing metadata (e.g. foreign keys) and some empirical values. Finally, mixed approaches fusion the two previous described methods.

Hierarchies are crucial structures in DW since they allow aggregation of measures in order to provide a global and general analytic view of warehoused data. For that reasons, some works investigate definition of hierarchies by means of Data Mining (DM) algorithms [START_REF] Favre | A knowledge-driven data warehouse model for analysis evolution[END_REF][START_REF] Sautot | The hierarchical agglomerative clustering with gower index: a methodology for automatic design of olap cube in ecological data processing context[END_REF]. However, this design step is applied once the multidimensional model has been defined, and it takes into account only members of one dimension.

From our point of view, these methodologies present an important limitation since in real DW projects often those DM algorithms need data of different dimensions and facts. Thus, in this paper we present a framework for a mixed design of multidimensional models by integrating DM algorithms in a classical data driven-approach. This allows defining hierarchical structures, according to decisional users' requirements, that cannot be deduced by classical datadriven methods. This hierarchical organization of dimensional data is translated in a complex multi-factual multidimensional model in order to represent as well as possible semantic of data sources.

The paper is organized in the following way: Section 2 introduces related work; a retail case study and the motivation are presented in Section 3; our design method is detailed in Section 4 and its implementation is shown on Section 5.

RELATED WORK

Three types of approaches can be used to design a data warehouse: (i) Methods based on user specifications, or demand-driven approaches; (ii) Methods based on available data, or data-driven approaches; (iii) Mixed methods, or hybrid approaches. For example, [START_REF] Jovanovic | Ore: An iterative approach to the design and evolution of multi-dimensional schemas[END_REF] is an iterative demanddriven method where at each iteration, the system searches for the best data corresponding with the information required by the user in terms of dimensions or facts. Moreover, several other have proposed systems based on hybrid approach such as [START_REF] Romero | Automatic validation of requirements to support multidimensional design[END_REF] that propose to express functional requirements using SQL queries.

Relational data driven approaches deduce multidimensional structures (facts and dimensions) from conceptual [START_REF] Phipps | Automating data warehouse conceptual schema design and evaluation[END_REF] and/or logical models [START_REF] Carme | A modeldriven heuristic approach for detecting multidimensional facts in relational data sources[END_REF][START_REF] Jensen | Discovering multidimensional structure in relational data[END_REF]. In particular some works investigate automatic discovering facts using some heuristics [START_REF] Carme | A modeldriven heuristic approach for detecting multidimensional facts in relational data sources[END_REF]. About dimensions some works propose using logical database metadata such as foreign keys [START_REF] Jensen | Discovering multidimensional structure in relational data[END_REF] or some heuristics.

Other works use more complex algorithm to identify dimensions hierarchies. [START_REF] Nguyen | An object oriented multidimensional data model for olap[END_REF] propose a system to dynamically build hierarchies based on data from Twitter [START_REF] Nguyen | An object oriented multidimensional data model for olap[END_REF]. [START_REF] Messaoud | A new olap aggregation based on the ahc technique[END_REF] present a new OLAP operator named OPAC that allows to aggregate facts that refer to complex objects, such as images. This operator is based on hierarchical clustering algorithm. [START_REF] Favre | A knowledge-driven data warehouse model for analysis evolution[END_REF] provide a framework for automatic defining hierarchies according to user rules. In order to personalize the multidimensional schema, [START_REF] Bentayeb | K-means based approach for olap dimension updates[END_REF] propose to create new levels in a hierarchy with the K-means algorithm. [START_REF] Leonhardi | Augmenting olap exploration with dynamic advanced analytics[END_REF] propose to increase the OLAP cube exploration functionalities by providing the user data mining algorithms to analyze data. [START_REF] Ceci | Olap over continuous domains via density-based hierarchical clustering[END_REF] use a hierarchical clustering to integrate continuous variables as dimensions in an OLAP schema. In the same line, [START_REF] Sautot | The hierarchical agglomerative clustering with gower index: a methodology for automatic design of olap cube in ecological data processing context[END_REF] propose using Agglomerative Clustering for designing hierarchies, and the integration in a rapid prototyping methodology is presented in (Sautot et al., 2014a). However, all existing works define hierarchies using only either dimensional data (i.e. attributes of dimension members) or factual data (i.e. measures) (see Table 1). But, in a constellation schema, a dimension can be enriched with a hierarchy created by using other dimensions and facts. It means that the creation of a new hierarchy can involved a refinement of facts and dimensions in the entier constellation schema. We detail this issue in the following section, using a real application case from bird biodiversity.

MOTIVATION

In order to describe motivation of our new DW design methodology we present in this section a real case study concerning the bird biodiversity analysis [START_REF] Sautot | The hierarchical agglomerative clustering with gower index: a methodology for automatic design of olap cube in ecological data processing context[END_REF]. This dataset has been collected to analyze spatio-temporal changes in bird populations along the Loire River (France) and to identify local and global environmental factors that can explain these changes. Data sources are stored in a relational database (PostGIS). Applying the data driven algorithm proposed in [START_REF] Romero | Automatic validation of requirements to support multidimensional design[END_REF] we obtain the constellation schema depicted in Figure 1, which presents two facts as described in the following. Abundances is one fact, and can be analyzed according to three dimensions (an instance is shown on Table 3): (i) the species dimension, which stores species names and attributes, (ii) the time di-mension, which corresponds to the census years and (iii) the spatial dimension, which describes census points along the river. Using this model decisionmaker can answer to queries like: "What is the total of birds per year and census point?" or "What is the total of birds per year and altitude?". To complete bird census, the landscape and the river are described around each census point. Environment descriptions are represented by another fact, which is associated to the time dimension and the spatial dimension. With this model, it is possible to describe census points, for example a possible OLAP query is "What is the percentage of forest per census point in 2012?".

Note that descriptions of census points that are not dependent from time, such as altitude and geology, are used as spatial dimension levels, while other attributes are represented as measures of another fact (e.g. percentage of forest). Unfortunately, abundances for a specie have not meaning if not related to environmental data of census points. In this situation a drill-across operation is not adequate since it will hide the species dimension. Indeed, with the drill-across operators facts are joined only on common dimensions. Moreover, the multidimensional model of Figure 1 does not make possible to provide the decision-makers with OLAP queries aggregating abundance by classes of environmental variable (30% of forest, 50% of water, etc.), for example "What is the total of birds per year and group of census point with 30% of forest?" or "What is the total of birds per year and group of census point with 50% of water?", since environmental parameters do not appear as levels, but as measures, prohibiting group-by queries.

Therefore, in our case study, decision-makers need for a new design method that group census points (dimensional data) by environmental parameters (factual data) and year (dimensional data).

The multidimensional model allowing correct OLAP analysis should be the one shown on Figure 2 [START_REF] Miquel | Modeling multidimensional spatio-temporal data werehouses in a context of evolving specifications[END_REF]. This multidimensional schema presents only one fact and the spatial dimension is enriched with some levels representing group of environmental parameters for each year. Indeed, environmental parameters for census points in 2001 can be different from ones of 2002 implying that the same census point is not grouped in the same level on two different years as shown on Table 3.

For example, data describing agricultural activities around the census points, are available only for the 2002 census campaign. Therefore, it is important to take into this different classification when navigating on the temporal dimension during an OLAP analysis session. For example, the query "What is the total of birds in 2002 and in census points with the same environmental parameters?" has to use the environment type 2002 level, and "What is the total of birds in 2011 and in census points with the same environmental parameters?" has to use the environment type 2011 level. For example an OLAP query using the environment type 2002 level and the temporal member 2011 is not coherent since it associates the number of birds on 2011 in the past geographical-environmental configuration of 2002, leading to erroneous interpretation.

OUR PROPOSAL

In this section we introduce our framework for the refinement of multidimensional in a mixed approach. The main idea of our proposal is using an existing data driven methodology in a first step. Then, in our new design step, we collect user needs about hierarchies that are not been deduced in the multidimensional schema by means of the functional dependencies. These users' needs are expressed in the form of facts existing in the constellation multidimensional model. In particular, the main idea is to provide an algorithm that transforms the constellation multidimensional schema by eliminating a fact node and integrating factual data in an associated dimension used for creating new levels.

To perform this algorithm, we translate the multidimensional model in a multidimensional graph.

In the following section we describe the multidimensional graph definitions (Section 4.1), the main algorithm is detailed in Section 4.2 and the calculation of new versioned hierarchies is explained in Section 4.3.

Preliminaries

In this subsection, we present some preliminary definitions.

We represent a multidimensional model using a graph. Moreover, M G contains no alone node, isolated of another node, but can contain possibly disconnected sets of nodes if each sub-graph must contain at least one fact node.

Example. An example of multidimensional graph is shown on Figure 3. "Species" dimension, "Census points" dimension, "Years" dimension, "Abundances" fact and "Environments" fact are described in previous sections. "Sources" dimension represents agencies, which collect data. "Budget" fact represents the funds allowed by each agency for each year to collecting data. In our approach decision-maker want to enrich a dimension with some new hierarchies using some factual data. That dimension is called Target dimension Definition 2. Target dimension. The target dimension d t of a multidimensional graph M G is a dimension such as:

d t ∈ D | ∃( f 1 , d t ), ..., ( f u , d t ) with u ∈ [[2, n]]
This means that dt is associated at least to two facts since one has to be removed and used to create its new levels.

Example. An example of possible target dimension is the "census point" dimension (Figure 3).

Let us now formalize the fact node that is used to create levels. Definition 3. Source node. The source node of a M G with a target dimension

d t is a fact node f s ∈ { f 1 , ..., f u }.
Example. With "census point" dimension as target node, an example of possible source node is the fact node "Environments".

As we have said before our algorithm removes the source node from the graph. Therefore, a part of the structure of the graph is changed. Note that only nodes related to the source nodes are affected. We define this sub-graph in the following way Definition 4. Source-target multidimensional sub-graph.

Let M G a multidimensional graph with a target dimension d t and a source node f s then the Sourcetarget multidimensional sub-graph M G is a multidimensional graph such as:

M G =< D , F , A > with: F = { f i ∈ F | ∃( f i , d t )} D = {d i ∈ D | ∃( f s , d i )} A = ( f i , d j ) | f i ∈ F , d j ∈ D
M G contains thereby only fact nodes linked to d t and dimensional nodes linked to f s . In M G , all fact nodes are so linked to at least one dimensional node and all dimensional nodes are so linked to at least one fact node. There is no isolated node in this sub-graph. M G is so a well-formed multidimensional graph.

Example. An example of Source-target multidimensional sub-graph using the previous example is shown on Figure 3.

In order to formalize inputs of the agglomerative hierarchical clustering algorithm used for the creation of levels of the target dimension, we formalize factual data aggregated to a set of dimensions levels using the definition of instance fact node. Example. Let, Table 2 representing the instance fact node for the node "Environments", then Table 4 represents facts aggregated to the All member of the "Agencies" dimension: (I("Environments", "Agencies.ALL", "Years.1990", "Census points.*"))2

Algorithm

In this section we provide details and formalize our approach.

Removing a fact node from the multidimensional graph implies its redefinition. Thus, the main idea is in a first step to work on the source-target multidimensional graph exclusively, transform this subgraph adding levels to the target dimension and removing the source node, and then finally re-integrate the new sub-graph in the rest of original multidimensional graph.

Removing the source node implies to handle its associated dimensions. It is possible to distinguish three types of dimensions:

• The target dimension that will rest in the transformed sub-graph,

• the Non Context dimensions D nc , and

• the Context dimensions D c .
The Non context dimensions D nc are dimensions that are only associated to the source node fact. In order to remove one dimension it is possible to provide a classical Dice operator, which consists in aggregating fact data to the top dimension member. Let us note that in order to avoid summarazability problems (aggregation cannot be reused) [START_REF] Lenz | A formal framework of aggregation for the olap-oltp model[END_REF], in our approach we allow using only distributive and algebraic aggregation functions for the Dice operator.

Example. An example of Non contextual dimension is the "Agencies" node. In Table 4 is shown an example of the Dice operator on the Agencies dimension, which is a Non contextual dimension. Let Source-target multidimensional sub-graph M G =< D , F , A >, then the set of non contextual dimension D nc is

D nc = {d nc 1 , ..., d nc v } ⊂ D | ∀i ∈ [[1, v]]∃!(d nc i , f j ) | f j ∈ F Note that
D c ⊂ D | D c = D -(D nc ∪ {d t })
Example. An example of contextual dimension is the "Years" node. On Table 3, we present data from "Abundances" node: data are dependent of "Years" dimensional node.

Once we have defined non context and contex dimensions let us provide our algorithm supposing that we have only one context dimension.

The input of this algorithm is the multidimensional graph M G presented on Figure 3.

Begin of the Refinement Algorithm

1. Identify the Source-target multidimensional sub-graph M G .

2. Calculate a hierarchy for each instance of each context. This part of the algorithm is detailed in particular in the section 4.3.

3. Remove f s from M G .

4. Remove isolated nodes. The isolated nodes can be only dimensional nodes linked to f s . Then M G is well formed.

End of the Refinement Algorithm

The output of this algorithm is a multidimensional graph, presented on Figure 4. We note that f s has been removed and there are new hierarchies in the "census points" node. Moreover, M G remains a well-formed multidimensional graph and can be also implmented in a ROLAP architecture.

Automatic creation of hierarchies

In this section we describe how the is applied to create new levels of the target dimension.

A complete methodology to create new hierarchies in a multidimensional model with Hierarchical Agglomerative Clustering is presented in [START_REF] Sautot | The hierarchical agglomerative clustering with gower index: a methodology for automatic design of olap cube in ecological data processing context[END_REF]. The main idea of this methodology is to build a new hierarchy into a dimension by using data, which describe items at the lowest level of the hierarchy. In our case, items are census points and description data are factual data. We suggest to use the Hierarchical Agglomerative Clustering, due to the similarity between the output of the Hierarchical Agglomerative Clustering and a hierarchy into an OLAP dimension [START_REF] Messaoud | A new olap aggregation based on the ahc technique[END_REF].

Main steps of this algorithm are: (1) Calculation of distances between individuals; (2) Choice of the two nearest individuals. (3) Aggregation of the two nearest individuals in a cluster. The cluster is considered an individual. (4) Go back to the step 1 and loop while there is more than one individual.

In our approach the clustering (AHC) takes as inputs the instance of the source node f s evaluated on each member of the context dimension and dicing it non context dimensions.

Formally, the step 2 of our algorithm is the following: An example is presented on Figure 5. We note that two hierarchies for the spatial dimension have been

VALIDATION AND EXPERIMENTS

In this section we present the implementation our proposal. A semantic and performance evaluations are detailed in Sec 5.1 and 5.2 respectively.

The refinement tool implements our algorithm using Matlab. It allows defining graph using a simple visual interface as shown on Figure 7. The considered multidimensional graph is presented on the top part of the visual interface. On the bottom one, the algorithm ask inputs to users in a command window.

Semantic evaluation

In this section, we describe the added-value of our methodology from a design point of view (i.e. does the refinement methodology corresponds to decisionmakers needs?). For that goal two we have investigated two aspects: 1) Do dimensions and facts created using our methodology correspond to decisionmakers analysis needs?; 2) Do hierarchies created using our methodology improve analysis capabilities?

Therefore have decided to compare the result of our methodology with with one proposed in (Miquel et al., 2002a). Indeed, (Miquel et al., 2002a) propose a manually method to obtain a multi-version multidimensional schema,and when the time dimension is chosen as the context dimension our approach results a multi-version multidimensional schema. The result of this validation shows that the multidimensional schema produced with the manual methodology and our automatic methodology are equal.

Moreover, in order to validate the semantic correctness of using AHC for hierarchies definition, we have asked to ecologists of the project to choice between a spatial dimension with only one level, and a spatial dimension with a hierarchy created using AHC. When the number of created levels is not superior to 5, decision-makers prefer having hierarchies, since they can reveal interesting pattern such as agricultural profiles of census points. For example, data in the "Environments" fact table contains data that describe agriculture policies around each census point at each year. The data clustering according to these data can classify census points and allows decisionmakers analyzing impact of agricultural practices on bird biodiversity. For example, decision-makers can analyze biodiversity according to agricultural forest and grassland parameters of census points, by using this simple OLAP query: "What is the biodiversity value per group of census points (first level of the hierarchy obtained with clustering) in 2002 and 2003?". This query can reveal that for the same year, for example 2002, biodiversity is very affected by agricultural parameters since the aggregated biodiversity value for each group of census point is different.

Performance evaluation

In this section, we test time performance of our methodology in order to validate its feasibility from a project deployment process point of view.

In particular we study time performance related to: 1) refinement algorithm for facts and dimension design, and 2) hierarchy creation using AHC.

In order to test the first point, we have created a set of 200 simulated constellation schema using from 2 to 100 dimensions, since real usable multidimensional schema presents maximum between 3 and 10 dimensions [START_REF] Kimball | The Data Warehouse Toolkit: Practical Techniques for Building Dimensional Data Warehouses[END_REF]. Finally, the worst time execution is 15.23 s. The average execution time is equal to 11.7 s with a standard deviation equal to 1.17 s. These performances are satisfactory for are good for an off-line design phase.

In this paragraph, we study time performances of the AHC algorithm. In this paragraph, "classified items" are census points (which are members of the "census points" dimension, the target dimension) and "attributes" are aggregated facts from the "Environments" fact node (which is the source fact node). The AHC algorithm has been also implemented in Matlab and its performance has been also tested. Using our case study data, we perform 2090 tests, with a number of classified items (source node instances-Enverinments facts) between 10 and 190, and a number of attributes (source node attributes-Enverinments fact measures) between 10 and 100, and the average calculation time is equal to 0.072 s, with a standard deviation equal to 0.002 s. To complete our evaluation, we simulate a data set with 10,000 classified items and 150 attributes. In this case, the AHC calculates a hierarchy in 147.36 s, with a standard deviation equal to 4.03 , with a maximal calculation time equal to 214 s. All time performances are shown on Figure 6. This calculation time (approximately four minutes) is efficient for an off-line design phase.

CONCLUSION AND FUTURE WORK

Design data warehouses system is a complex and crucial task depending on available data sources and decisional requirements. Existing work do not exploit the semantics of data to automatically create complex hierarchies. Thus in this paper, we present a mixed multidimensional refinement methodology, that transform constellation schema to define hierarchy level using a hierarchical clustering algorithm. Our refinement methodology enriches a dimension with factual data, and considers the context of factual data. We present also the implementation of our method in a ROLAP architecture.

We perform the proposed methodology on a real application case from bird biodiversity. We have noted that actual automatic multidimensional design methodologies cannot produce a multidimensional schema, which covers all decision-maker needs due to the data complexity. Our methodology offers a solution to enrich dimensions with factual data and, by this way, to refine the multidimensional schema.

Our ongoing work is the extension of our methodology to simplify and reduce the number of created levels, using other DM algorithms such as SVM, etc., in order to provide decision-makers with easy OLAP exploration analysis and its implementation in a RO-LAP architecture.

Moreover, we are also working to integrate our approach in the rapid prototyping methodology proposed in (Sautot et al., 2014a), and extending to help decision-makers and DW experts choose the right DM algorithms and parameters of the refinement algorithm (source node, contextual dimensions, etc.). Future work concerns the usage of the formal evaluation framework Goal Question Metric [START_REF] Briand | An operational process for goal-driven definition of measures[END_REF] to evaluate our methodology.

Figure 1 :

 1 Figure 1: Bird biodiversity case study: Data-driven constellation schema

Definition 1 .

 1 Multidimensional graph. A multidimensional graph is a directed graph M G =< D, F, A > with: D = {d 1 , ..., d m }, dimensional nodes, which represent dimensions. F = { f 1 , ..., f n }, fact nodes representing facts. A = {a 1 , ..., a p } | ∀i ∈ [[1, p]], a i = ( f j , d k ), with j ∈ [[1, n]] and k ∈ [[1, m]], are arcs 1 , meaning that arcs are only directed from a fact node to a dimensional node.

Figure 3 :

 3 Figure 3: Multidimensional graph M G

Definition 5 .

 5 Instance fact node. Let M G a multidimensional graph. Let m i a member of the dimension d i . Then the instance fact node I( f , d 1 .m 1 , ..., d n .m n ) is the set of tuples representing facts of f aggregated to the dimensions members d 1 .m 1 , ..., d n .m n .

  in the previous formula, all dimensional nodes in D nc are only linked to f s . Indeed, all dimensional nodes in M G are linked to f s and dimensional nodes in D nc are linked to one (and only one) dimensional node. The Context dimensions D c are dimensions in M G that are associated to f s and another fact node f . With the future refined graph, users analyze facts in f according to d t . But, data used for calculating new hierarchies in d t come from f s and are thereby dependent of dimensions in D c . Therefore, we need to ensure that data used to create the hierarchy are coherent with data consulted by the user during their OLAP analysis. With this in mind, we offer a system that calculates hierarchies according a context, this context defining with D c . Formally, Definition 7. Contextual dimension. Let Source-target multidimensional sub-graph M G , then the set of contextual dimension D c is

Figure 4 :

 4 Figure 4: Refined multidimensional graph M G

  created for years 2002 and 2011.

Figure 5 :

 5 Figure 5: Contextual hierarchies of census points

Figure 6 :

 6 Figure 6: Execution times according the number of attributes and classified items

Table 2 :

 2 Factual data of "Environments" node

	Years Census	Agencies Percent	Percent
		Points		of	of
				Forest	Grass-
					land
	2002	1	LE2I	0.176	0.250
	2002	1	ONEMA	0.356	0.261
	2002	2	LE2I	0.311	0.420
	2002	2	ONEMA	0.255	0.574
	2011	1	LE2I	0.189	0.278
	2011	1	ONEMA	0.241	0.385
	2011	2	LE2I	0.322	0.568
	2011	2	ONEMA	0.257	0.575
	Table 3: Factual data of "Abundances" node
	Years Census	Species	Abundance
		points
	2002	1	Yellowhammer	1.5
	2002	1	Coal Tit		0.5
	2002	2	Yellowhammer	1.5
	2002	2	Coal Tit		0
	2011	1	Yellowhammer	1
	2011	1	Coal Tit		3
	2011	2	Yellowhammer	1
	2011	2	Coal Tit		2

Table 4 :

 4 Factual data of "Environments" node aggregated on "Agencies"

	Years Census	Percent	Percent
		Points	of	of
			Forest	Grass-
				land
	2002	1	0.266	0.256
	2002	2	0.283	0.497
	2011	1	0.215	0.332
	2011	2	0.290	0.572
	Formally,
	Definition 6. Non contextual dimension.

In this paper, the notation ( f i , d j ) represents the arc from fact node f i to dimensional node d j .

'*' means 'all members of the dimension'

ACKNOWLEDGMENTS

Data acquisition received financial support from the FEDER Loire, Etablissement Public Loire, DREAL de Bassin Centre, the Région Bourgogne (PARI, Projet Agrale 5) and the French Ministry of Agriculture. We also thank heartily Pr. John Aldo Lee, from the Catholic University of Leuven, for his help.