Marc Grossouvre
email: marcgrossouvre@urbs.fr

Didier Rullière
email: drulliere@emse.fr

Jonathan Villot
email: jonathan.villot@emse.fr

Predicting missing Energy Performance Certificates: Spatial interpolation of mixture distributions

Keywords: climate governance, energy efficiency, multi-scale processes, areal data, change of support

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

Introduction

Classifying the EPC prediction problem in research

Energy Performance Certificates are delivered in many countries around the world to assess the energy efficiency of buildings. Various approaches can be found in the European Union, Turkey, the UK, the USA... An Energy Performance Certificate (EPC) is defined in France as an energy consumption associated with a qualitative labelling letter ranging from A to G as shown in Figure 1. Energy consumptions associated with dwellings, identified by their addresses, are inventoried in a database released in open access and mapped in Figure 2. A second database matches each address with a land plot.

Finally, a third database gives the living area of every dwelling, be it house or apartment, together with the land plot where they are located, and a few other technical specifications. However, the exact location of these dwellings on each land plot is not certain. From these datasets, decision-makers such as municipalities, would like to infer the EPC (energy consumption and label) of buildings that have not been observed in order to identify targets for energy retrofit incentives. This problem is referred to as the EPC prediction problem in the present paper.

In the literature, this problem can be approached from an engineering perspective, from a data management perspective or from a geostatistics point of view.

From an engineering perspective, heat engineers have physical models that compute an energy balance in order to find a given building's energy consumption. These models require a large number of technical features and may be used to design a refurbishment (improvement) strategy [START_REF] Baker | Future Proofing a Building Design using History Matching Inspired Level-set Techniques[END_REF]. To work at a larger scale, heat engineers define typologies of buildings, compute a distribution of these types on a given territory, and therefore infer a distribution of EPC labels. This approach has proven to be efficient [START_REF] Ballarini | Energy refurbishment of the Italian residential building stock: energy and cost analysis through the application of the building typology[END_REF]. However, the lack of knowledge about the detailed technical features of each building is a strong limitation for a prediction at the building level. Some feature reduction efforts have been made [START_REF] Ali | A data-driven approach to optimize urban scale energy retrofit decisions for residential buildings[END_REF], but the remaining features are still problematic to infer and require extra efforts [START_REF] Schetelat | Urban data imputation using multi-output multi-class classification[END_REF]. The present work considers an alternative approach wherein detailed technical knowledge of each building is relinquished, and instead leverages the geolocated nature of EPC information. From a data management perspective, the EPC prediction problem requires a process to combine datasets from multiple sources available at multiple scales, which is known as data fusion [START_REF] Smith | Unified Geostatistical Modeling for Data Fusion and Spatial Heteroskedasticity with R Package ramps[END_REF]. These types of problems are becoming increasingly complex due to the growing amount of data available, whether it be ecological, social, or institutional. These datasets relate to space units of varying shapes, dimensions, and cardinality. And in some cases, it may be difficult to determine the exact position of an observed object. This is the case with buildings, since many governments lack a detailed map of the building stock in their country. Property tax is typically based on intrinsic factors such as surface area and number of bedrooms, but not extrinsic factors such as the floor number or window orientation (see Table 1). As a result of this uncertainty, large-scale studies on housing stock have to rely on an abstract concept of dwelling. This idea of dwelling can refer to a house or an apartment; it is not clearly delimited but it is described by a set of features such as an area or a number of bedrooms.

These features are gathered in a table with one dwelling per row, meaning that the dwelling is the smallest unit of information. Similarly, the smallest unit of information for a table with one EPC per row is a part of a building. It is not clearly defined as an object in a 3- dimensional space, but it has features that describe it (see Table 2). And to predict the EPC of buildings, one also has to define buildings. In the same way, data fusion requires defining the smallest units of information, also known as granules for each dataset: "Informally, a granule of a variable X is a clump of values of X that are drawn together by indistinguishability, equivalence, similarity, proximity, or functionality. For example, an interval is a granule." [START_REF] Zadeh | Toward a generalized theory of uncertainty (GTU)--an outline[END_REF]. The field of study that focuses on representing, constructing, and processing these information granules is called Granular Computing [START_REF] Pedrycz | Granular computing : analysis and design of intelligent systems[END_REF]. Assuming that an appropriate data fusion process is implemented, dwellings, EPC observations, and complete buildings are represented in the same data model. It remains to define a relevant predictive model. Granular computing is multidisciplinary, but since we are dealing with geo-localized information, the natural field of research is geostatistics, which has been defined as "dealing with spatial processes indexed over continuous space" (Cressie, 1993, p7).

From a geostatistics perspective, the irreducible uncertainty about granules' positions (dwellings, buildings, etc.) in their underlying space restricts the use of traditional spatial interpolation models such as Kriging as well as more recent models such as those proposed by [START_REF] Roksvåg | A Two-Field Geostatistical Model Combining Point and Areal Observations-A Case Study of Annual Runoff Predictions in the Voss Area[END_REF], although the latter efficiently combines point and areal observations. This work aims to overcome the latter limitation and develop a comprehensive framework capable of handling data with uncertainty about the position of observed objects while still allowing for the definition of an optimal linear predictor for spatial interpolation of EPC values. As is first presented below, the literature shows that the problems to solve have already been identified and that several solutions have been proposed with their benefits and shortcomings.

The limits of systematic averaging for spatial interpolation

Gaussian Process Regression [START_REF] Williams | Gaussian Processes for Regression[END_REF], also known as Kriging, is one of the major spatial interpolation approaches [START_REF] Comber | Spatial interpolation using areal features: A review of methods and opportunities using new forms of data with coded illustrations[END_REF]. Kriging theory relies on the assumption that points close to each other are more likely to have similar features. It achieves the Best Linear Unbiased Predictor (BLUP) in the least squares sense for point spatial interpolation. However, the EPC prediction problem deals with observations that are not point observations but areal observations. Areal interpolation, as defined by [START_REF] Lam | Spatial Interpolation Methods: A Review[END_REF], involves "the transformation of data from one set of boundaries to another". Lam also used the terms source zone and target zone.

For the EPC prediction problem, source zones are dwellings and buildings' parts that are observed, while target zones are whole buildings, including those for which no part has been observed. Spatial or areal interpolation research is based on the assumption that granules close to each other are more likely to have similar features. This is reasonably understandable for temperatures that are continuously defined over space, but it may be more challenging to observe and model when dealing with areal data where granules can be of various sizes and shapes, sometimes uncertainly defined. [START_REF] Gotway | Combining Incompatible Spatial Data[END_REF] highlighted the terms used to describe areal interpolation and its challenges; this terminology includes block Kriging, multi-scale and multiresolution modelling, the ecological inference problem, the modifiable areal unit problem (MAUP), the scaling problem, the change of support problem, and the reduction of variance problem. Below are the aspects of this work that are more relevant for solving the EPC prediction problem.

Block Kriging is a derivative of Kriging designed for handling areal data.

It distinguishes point-to-area, area-to-point, and area-to-area predictions. It assumes that a feature at block (granule) level is the average of the block's point features. Point-to-area prediction produces an estimate "identical to that obtained by averaging the point estimates produced by [Kriging]" [START_REF] Isaaks | An Introduction to Applied Geostatistics[END_REF][START_REF] Cressie | Statistics for spatial data revised edition. Wiley series in probability and mathematical statistics[END_REF]. [START_REF] Kyriakidis | A Geostatistical Framework For Area-To-Point Spatial Interpolation[END_REF] described a complete Kriging model for area-to-point prediction, proved that it is an optimal predictor, and sketched area-to-area prediction. [START_REF] Goovaerts | Kriging and Semivariogram Deconvolution in the Presence of Irregular Geographical Units[END_REF] studied in depth the problem of estimating the variogram, that is to say, measuring the similarity between 2 points at different distances, for block Kriging. He showed that averaging reduces the sill of the variogram and tried to tackle this bias. Moreover, while point estimates obtained by Kriging are optimal, area-to-area Kriging may not be the optimal predictor for the average value over the block.

A known issue resulting from systematic averaging in areal Kriging models arises in scenarios such as analysing crop yields, where the set of agricultural fields to aggregate for a certain type of crop varies from year to year. It states that correlations between features at areal level are heavily dependent on the aggregation process, making it difficult to compare correlations between different years. This is the Modifiable Areal Unit Problem (MAUP) for which a measuring approach has been recently proposed [START_REF] Briz-Redon | A Bayesian shared-effects modeling framework to quantify the modifiable areal unit problem[END_REF]. While the MAUP refers to the correlation between aggregated features, the ecological inference problem is a result of the correlations at the individual level being different from the correlations of the averaged features at the ecological (group) level. A lack of information about the individuals' positions leads to a bias when the averaged information about individuals distributed into areal units is cross-classified by other individual (point-level) variables (sex, race). According to [START_REF] Gotway | Combining Incompatible Spatial Data[END_REF], "The smoothing effect that results from averaging is the underlying cause of both the scale problem in the MAUP and aggregation bias in ecological studies." Apart from correlations, the variance itself is affected by systematic averaging. Indeed, the average of identical random variables has a smaller variance than the variance of the individuals themselves. The specific issue of variance reduction at the block level was partially addressed in [START_REF] Li | A simple kriging method incorporating multiscale measurements in geochemical survey[END_REF] using rectangular blocks at multiple scales.

Despite its limitations, the averaging method has proven to be effective for interpolating areal data. For example, [START_REF] Poggio | Downscaling and correction of regional climate models outputs with a hybrid geostatistical approach[END_REF] downscaled climate models and predicted soil wetness using Kriging on the residuals of a generalized additive model [START_REF] Wood | Generalized Additive Models: An Introduction with R, Second Edition[END_REF]. Area-to-point Kriging, also called disaggregation, has also been implemented by [START_REF] Kerry | A comparison of multiple indicator kriging and area-to-point Poisson kriging for mapping patterns of herbivore species abundance in Kruger National Park, South Africa[END_REF]; [START_REF] Truong | Bayesian Area-to-Point Kriging using Expert Knowledge as Informative Priors[END_REF]; [START_REF] Yoo | Area-to-point Kriging with inequality-type data[END_REF]. Additionally, areato-area Kriging (block Kriging) has been used effectively by [START_REF] Zhang | Uncertainty in Upscaling In Situ Soil Moisture Observations to Multiscale Pixel Estimations with Kriging at the Field Level[END_REF] and has been apply to downscaling by [START_REF] Jin | Geographically Weighted Area-to-Point Regression Kriging for Spatial Downscaling in Remote Sensing[END_REF] as well as [START_REF] Pereira | Downscaling of ASTER Thermal Images Based on Geographically Weighted Regression Kriging[END_REF]. The satellite imaging field has also notably benefited from this framework, as in the pan-sharpening process, which is "a technique to combine the fine spatial resolution panchromatic (PAN) band with the coarse spatial resolution multispectral bands of the same satellite to create a fine spatial resolution multispectral image" [START_REF] Wang | Area-to-point regression kriging for pan-sharpening[END_REF]. In this process, points are weighted according to their distance from the centroid of the satellite pixel when computing the average value.

Both the MAUP and the ecological inference problem belong to a family of problems related to the combination of different types of granules in the same model, e.g. observing dwellings and predicting buildings. These problems are gathered in the change of support problems family. Another particular change of support problem known as spatial misalignment arises when a given feature is observed at multiple scales, including point level.

Systematic averaging makes points and areas different objects with different different correlation structures and therefore different predictors. The classification of problems such as "area-to-point" or "area-to-area" reflects this categorization. To address spatial misalignment, a Bayesian framework that can be iterated both with point observations and block observations has been proposed by [START_REF] Moraga | A geostatistical model for combined analysis of point-level and area-level data using INLA and SPDE[END_REF]. However, this model is still based on averaging at areal level for features that are continuously defined over the territory. Like other models derived from Kriging, it considers blocks to be connected surface areas in R 2 that need to be discretized [START_REF] Goovaerts | Kriging and Semivariogram Deconvolution in the Presence of Irregular Geographical Units[END_REF], which can distort reality for features that are not continuously defined over the space. Such is the case of populations of individuals that are discrete points heterogeneously located within a block, such as a county or census tract.

Beyond systematic averaging

A way to try and overcome change of support problems is to define a new data model for which features at areal level do not require systematic averaging. In this regard, [START_REF] Godoy | An unified framework for point-level, areal, and mixed spatial data: the Hausdorff-Gaussian Process[END_REF] defined a Gaussian random field on the class B D of closed subsets of a certain domain D ∈ R n . Distances between elements of B D are measured with the Hausdorff distance, and the correlation structure between features is based on this distance together with a Matérn kernel. Eventually, a Bayesian framework is used to fit the model with respiratory cancer data, yielding encouraging results. This model seems very general and will probably find other fields of application. However, it is not interpretable in the sense that there is no obvious link between the feature at the areal level and the feature at the point level, therefore eluding the question of consistency. In other words, it is not known whether the aggregation of cancer incidence predictions at a small scale would give the prediction of cancer incidence at a larger scale. Beside this limitation, the Hausdorff-Gaussian process does not solve the problem of position uncertainty that is found in the EPC prediction problem.

In this paper, a new model is proposed where learning and prediction can be made from both aggregated and point support data. An object category called grain is introduced to express this new approach, consistent with research realities where it may be desirable to complete large aggregated open datasets with local observations and predict at various scales. Grains containing a continuous or discrete set of points are treated identically. As is detailed above, a weighted average is the standard aggregation approach.

In this respect, the MAUP is related to determining a covariance model for points from which the covariance between blocks and the covariance between points and blocks are derived. Weights for averaging are assumed to be fully determined for a given block; they are not regarded as a probability distribution for a block, thereby ignoring some related statistics and other potential sources of stochastic dependence between blocks. The present paper proposes a method of incorporating a mixture distribution to address this issue.

Kriging has already been developed for features that are mixtures at the point level [START_REF] Lin | Combining a finite mixture distribution model with indicator kriging to delineate and map the spatial patterns of soil heavy metal pollution in Chunghua County, central Taiwan[END_REF], but Lin et al. make no assumption about the distribution of features at the areal level. Instead, we assume the aggregation of information at the areal level to be a mixture. Averaging a large number of random variables results in a variance reduction, whereas mixing a large number of random variables does not tend to reduce the variance. We will show that this approach effectively manages position uncertainty. However, one drawback is that mixtures of Gaussian random variables are generally not Gaussian, which means that the usual Gaussian process interpretations and conditioning will no longer hold.

The present study proposes a new model for processing granular data, as detailed in Section 2. In Subsection 2.1, a suitable data model is established, while in Subsection 2.2, we define the feature variables' means and covariances. Moreover, a Best Linear Unbiased Predictor is derived in Subsection 2.3. We illustrate the model with examples in Section 3, starting with simulated rounded positions in Subsection 3.1, followed by simulated areal data with varying area sizes in Subsection 3.2. Subsection 3.3 focuses on presenting the EPC prediction problem with real data. Finally, in Section 4, we discuss the pros and cons of the new model.

Prediction model

This work is motivated by the will to handle data that is released in open format by public or private institutions. The goal is to use institutional data, such as the distribution of salaries at the municipality level, to estimate the distribution of salaries at a smaller scale, such as a district in a city, while also including known salaries at specific locations. To achieve this, we propose here a general Kriging approach that extends the traditional Simple or Ordinary Kriging and coKriging techniques. The model will explain some variables (such as the energy consumption, the salary, etc.) using some explanatory variables (such as the location, the construction year, etc.). The former will be referred to as output variables and the latter as input variables. Let us consider a space (input space, sometimes known as study space) over which is defined a field of multidimensional random variables (output variables, features of interest) such as sociological variables, assumed to be defined and potentially observed for both points in the input space and for geographic areas, such as cities, regions, or countries. These areas are referred to as "grains". The model predicts output variables at unobserved points or grains, based on the assumption that the dependence between outputs depends on the relative positions of the inputs. No assumption is made regarding the shape of the grains, which can even overlap partially or completely.

Data model

Let us define the structure of the input space.

Definition 1 (Inputs). Let d be a positive integer. A territory and grains inside this territory are defined as follows:

• A territory is a subset χ of R d ; • A point is any element x ∈ χ ; • A grain is any non-empty subset g ⊆ χ .
It is common in some application fields to use a different terminology to talk about grains: blocks, pixels, or areas for instance. In the above definition, there is no constraint on grains, contrary to pixels that are usually forming a regular grid known as a raster. A set of grains does not have to cover the whole territory, and its elements might overlap. Moreover, a grain is not necessarily a connected set, contrary to blocks. And an area is usually seen as associated with a surface area (a set of strictly positive measure) whereas a grain may be a finite set of points.

For instance, suppose that the points are represented as pairs of latitude and longitude coordinates in an appropriate coordinate reference system. In this case, χ could be defined as the set of all latitude-longitude pairs that fall within a specific country, yielding d = 2 and χ ⊂ R 2 . A grain may correspond, for example, to a specific city, to a specific land plot, or to a specific building's footprint. Previous Kriging models refer to blocks or areas for sets of points that are disjoint (see, for instance, [START_REF] Kyriakidis | A Geostatistical Framework For Area-To-Point Spatial Interpolation[END_REF].

When dealing with geographic data, a set of grains is usually the minimum scale at which information is available; that is to say, the data granularity.

For instance, it may be the set of land plots, the set of cities, the set of buildings' footprints, etc. However, considered grains may have non-empty intersections and may come from different datasets, at different scales, such as land plots and census tracts. Definition 1 is general enough to include such sets of grains. Data that describe population or buildings are not continuously defined over a territory, as opposed to temperature or pollutant concentration. Census data are anonymized at the census tract level before being released. For instance, in a census table describing dwellings, a row describes a dwelling that exists on a certain census tract, but we don't know exactly where it is on this tract. Then dwellings' surface area is neither continuous nor clearly geo-localized. Definition 2 below unifies output features that are continuously defined over a territory and output features that are not.

An originality of this work is to consider a set of random locations that model the uncertainty of explanatory variables over each considered grain.

Let {X g , g ∈ G} be a given sequence of random variables that are random locations, or more generally, random explanatory variables. Their joint distri-bution is assumed to be known. As an example, for non-overlapping grains, one can choose a sequence of independent uniform random variables over each grain, but any other joint distribution, possibly dependent, can be chosen. Definition 2 associates output variables with these random explanatory variables.

Definition 2 (Outputs). Let G be a set of grains. We assume that for each grain g ∈ G, there is a random variable X g with values the points of g. Output variables are defined over points and grains of G as follows:

• Y is a p-dimensional multivariate random field over χ such that:

∀x ∈ χ, Y(x) := (Y 1 (x), . . . , Y p (x)) ⊤ ∈ R p • For each g ∈ G, a p-dimensional real random vector Y(g) is defined to be the value of Y at a random location X g ∈ g: ∀g ∈ G, Y(g) := Y(X g ) ∈ R p Defined accordingly, Y(g) is a mixture distribution.
For a given set of grains G, the set of random variables {X g : g ∈ G}, is assumed to be defined and known, and the dependence structure between those random variables is supposed to be known. Furthermore, these random variables are assumed to be independent from the random field Y.

Example 1. The importance of X g should be stressed here. For instance, if one studies the distribution of capital owned by citizens of a given municipality, P (X g = x) gives the probability of a citizen x to be observed.

P (Y (X g ) = y
) is the probability to observe y when a citizen picked randomly according to X g unveils his capital:

P (Y (g) = A) = P (Y (X g ) = A) = x∈g P (X g = x)P (Y (x) = A) .
It is clear that individuals are not distributed regularly (along a grid for instance) in the grain. However, in this example, it makes sense to consider that ∀x ∈ g, P (X g = x) = 1/ [g] where [g] is the cardinality of g. This means that the contribution of all citizens are equally valued in Y (g).

Let us now suppose that the outputs are partially known on a set of grains. For (i 1 , . . . , i n ) ∈ {1, . . . , p} n and g 1 , . . . , g n ∈ G the following n random variables are known:

Y = (Y 1 , . . . , Y n ) ⊤ with Y j = Y i j (g j ) for j ∈ {1, . . . , n}
As an example, if ℓ observations of the whole random vector Y(g h ) are conducted for h ∈ {1, . . . , ℓ}, then n = ℓ • p and the vector of observations is:

Y = (Y 1 (X g 1 ), . . . , Y p (X g 1 ), . . . , Y 1 (X g ℓ ), . . . , Y p (X g ℓ )) ⊤ . (1)
If some observations are incomplete, that is to say some components of Y g j are missing for some j, then Y will be a subvector of Y given in Equation

(1). It means that there may be missing data in the outputs' observations.

Mean and covariances of output variables

The originality of the present work is that for a grain g, Y(g) is defined to be Y(X g ), the value of Y at a random location X g ∈ g. If the random field {Y(x) : x ∈ χ} and the joint distribution of {X g ∈ χ : g ∈ G} are known, then the joint distribution of {Y(g) : g ∈ G} can be deduced. And, if one only knows the moments of order one and cross moments of order two of {Y (x) : x ∈ χ} together with the joint distribution of {X g ∈ χ : g ∈ G},

then one can expect to be able to deduce expectation and cross covariances of {Y(g) : g ∈ G}.

In the rest of the paper, we assume that the first two moments of {Y(x) : x ∈ χ}, {X g ∈ χ : g ∈ G} and {Y(g) : g ∈ G} exist. In the following proposition, we show that we can indeed deduce the moments of grains' outputs.

Proposition 1 (Mean and covariance of Y(g)). From Definition 2, we derive the following results:

(i) For any grain g ∈ G and any index i ∈ {1, . . . , p}, assuming that for all x ∈ g we know

µ i (x) := E [Y i (x)] = E [Y i (g)|X g = x],
we have:

µ i (g) := E [Y i (g)] = E [µ i (X g )]
(ii) For any two grains g, g ′ in G and any two indices i, j ∈ {1, . . . , p}, assuming that for all x ∈ g, x ′ ∈ g ′ we know

k i,j (x, x ′ ) := Cov [Y i (x), Y j (x ′ )],
we have:

k i,j (g, g ′ ) := Cov [Y i (g), Y j (g ′ )] = E [k i,j (X g , X g ′ )]+Cov [µ i (X g ), µ j (X g ′ )]
In particular,

k i,i (g, g) = Cov [Y i (g), Y i (g)] = V [Y i (g)] = E [k i,i (X g , X g )] + V [µ i (X g )] .
Proof. (i) is a direct application of the conditional expectation formula

E [V ] = E [E [V |U ]] where Y i (x) is the result of conditioning Y i (g) with X g .
(ii) is derived from the conditional covariance formula:

Cov [U, V ] = E [Cov [U, V |W ]] + Cov [E [U |W ], E [V |W ]]
after conditioning by the joint random vector (X g , X g ′ ) (random variable

X g ). Note that Cov [µ i (X g ), µ j (X g ′ )] = 0 when µ i (x) is constant over g or g ′
or when X g and X g ′ are independent. Also note that this framework yields the expected result that if a grain is restricted to a point, then the output variables associated with this grain are the same as those associated with the underlying point.

Example 2. For two distinct and finite grains g and g ′ of cardinalities

[g] , [g ′ ], assuming in this example that X g and X g ′ are independent uniform random variables, we get:

µ i (g) = 1 [g] x∈g µ i (x) k i,j (g, g ′ ) = 1 [g] [g ′ ] (x,x ′ )∈g×g ′ Cov [Y i (x), Y j (x ′ )] k i,j (g, g) = 1 [g] x∈g Cov [Y i (x), Y j (x)]
Remark 1 (Comparison with average -block-to-block covariances). Previous models using the concept of blocks define Ȳi (g

) := E [Y i (X g )|{Y i (x), x ∈ g}] = g Y i (x)dF g (x)
, with F g the cumulative distribution function (cdf ) of the, possibly discrete, random variable X g , i ∈ {1, . . . , p}. One can check that with this setting, the mean of the mixture Y i (g) and the average Ȳi (g) are identical:

E [Y i (g)] = Ȳi (g) .
Regarding the covariances, when X g and X g ′ are two independent random variables, one can check that

E [k i,j (X g , X g ′ )] = Cov Ȳi (g), Ȳj (g ′ ) However, E [k i,j (X g , X g )] ̸ = Cov Ȳi (g), Ȳj (g)
because the independence assumption does not hold any more. As a consequence, V [Y i (g)] ̸ = V Ȳi (g) , even in the specific case where ∀i, j, g, g ′ , Cov [µ i (X g ), µ j (X g ′ )] = 0. The difference between a mixture and an average is retrieved here:

V [Y i (g)] ≥ V Ȳi (g) .

Best unbiased linear predictor

A Gaussian Process is a collection of random output variables indexed over points in the input space of explanatory variables, typically denoted as Y (.). An observation is therefore a random variable Y (x) evaluated at a given point x, and the covariance between Y (x) and Y (x ′ ) is a function of (x, x ′ ). But we rather consider here an uncertainty on the explanatory variable, meaning that an observation is modelled as a random field Y (.) evaluated at a random location X g over a given gain g. Thus, one observes a mixture of Gaussian random variables that are not Gaussian any more.

Moreover the covariance between Y (X g ) and Y (X g ′ ) depends on the joint random variables (X g , X g ′ ).

In the previous subsection, some assumptions have been made that are sufficient to be able to compute the covariance between two observations. In the present subsection, it is proved that, given the above defined framework and a learning set of observations, a best linear predictor can be inferred to predict the output features associated with a grain g ⊂ χ that has not been observed, given a learning set of observations. Note that the problem amounts to predicting any component of the output variable and that the specific covariance structure resulting from the uncertainty on the explanatory variable requires the development of a new software package, as usual packages such as DiceKriging can not fit such a model.

Let Y be the vector of observations forming the learning set, and let g ⊂ χ be a grain such that for some i ∈ {1, . . . , p}, Y i (g) is to be predicted.

Denote:

µ := E [Y] ∈ R n K := Cov Y j , Y j ′ j,j ′ ∈{1,...,n} ∈ S + n (R) h i (g) := Cov Y j , Y i (g) j∈{1,...,n} ∈ R n
where S + n (R) is the set of semi-definite positive, n × n, real matrices.

In the following, K is assumed to be invertible.

With a given set of weights α(g) = (α 1 (g), . . . , α n (g)) ∈ R n , is associated a linear predictor M α(g) :

M α(g) = n j=1 α j (g)Y j = α(g) ⊤ Y .
The optimal weights α i (g), provided that they exist and are unique, are defined to be those minimizing a quadratic error over all unbiased linear predictors:

α i (g) ∈ arg min α∈R n E Y i (g) -α ⊤ Y 2
Given the optimal predictor M i (g), the prediction error and the Kriging (co)variance are denoted as:

ϵ i (g) := Y i (g) -M i (g) c i,j (g, g ′ ) := E [ϵ i (g) ϵ j (g ′ )]
(2)

v i (g) := c i,i (g, g) (3)
The following proposition gives an optimal predictor that can be computed under the minimal assumptions of Proposition 1. Given the first two moments of random variables {X g : g ∈ G}, all components of µ, K, and

h i (x) can be computed.
Proposition 2 (Mixture Kriging prediction). Given a set of observations Y, for any g, g ′ ⊂ χ, and in particular for a single point g = {x}, for any i ∈ {1, . . . , p}, the weights α i (g) yielding the best linear unbiased predictor (BLUP) of Y i (g) and the associated cross errors are as follows:

(i) Simple Mixture Kriging. If µ = (0, . . . , 0) ⊤ and µ i (g) = 0 then

α i (g) = K -1 h i (g) (4)
c i,j (g, g ′ ) = k i,j (g, g ′ ) -h i (g) ⊤ K -1 h j (g ′ )
(ii) Ordinary Mixture Kriging. If µ ̸ = (0, . . . , 0) ⊤ then the condition for unbiasedness writes µ i (g) = α i (g) ⊤ µ and

α i (g) = K -1 h i (g) + λ i (g)µ (5)
where

λ i (g) = µ i (g) -µ ⊤ K -1 h i (g) µ ⊤ K -1 µ c i,j (g, g ′ ) = k i,j (g, g ′ ) -h i (g) ⊤ K -1 h j (g ′ ) + λ i (g)λ j (g)µ ⊤ K -1 µ
Proof of Proposition 2 is given in Supplementary material Appendix A.

Proposition 2 is presented as an algorithm in pseudo-language for Simple Mixture Kriging in Algorithm 1.

Assume that {Y(x) : x ∈ χ} is a vector-valued Gaussian random field and that each X g is Dirac distributed for all grains. This last condition holds in particular when each grain is restricted to one singleton point. In this Gaussian case, one retrieves Simple Kriging and Ordinary Kriging predictors, as defined, for example, in [START_REF] Rasmussen | Gaussian processes for machine learning[END_REF]. In this sense, the Mixture Kriging results presented here can be seen as a generalization of the Kriging interpolation.

The above Proposition 2 is valid to predict a single component Y i (g) of the output variable Y(g), but it can be extended to the prediction of Y(g): the best linear unbiased predictor of

Y(g) = (Y 1 (g) . . . Y p (g)) ⊤ for the quadratic error E [||Y(g) -AY|| 2 2 ] is M A(g) = A(g)Y
where A(g) is the matrix of which the i-th row is equal to α i (g) ⊤ given by Proposition 2.

Particular cases

In this subsection, two important particular cases are explored. The first one considers the Ordinary Mixture Kriging situation, where the output variable's expectation is the same everywhere. An estimator of this constant expectation is derived. The second particular case considers Mixture Kriging with noisy observations and shows that a nugget effect can be introduced the same way as for Kriging.

Particular case 1 (Constant mean µ = µ 0 (1, . . . , 1) ⊤ ). Regarding Ordinary Mixture Kriging, assuming that all random variables Y i (g) have the same unknown expectation µ 0 , and setting 1 n = (1, . . . , 1) ⊤ , Equation (5) simplifies into:

α i (g) = K -1 h i (g) + 1 -1 n ⊤ K -1 h i (g) 1 n ⊤ K -1 1 n 1 n ,
and setting m(g) :=

1 n ⊤ K -1 Y 1 n ⊤ K -1 1 n , M i (g) becomes: M i (g) = m(g) + h i (g) ⊤ K -1 (Y -1 n m(g)) ,
therefore m(g) is an unbiased estimator of µ 0 . m can be compared with usual sample mean for independent observations Y = 1n ⊤ Y 1n ⊤ 1n .

Particular case 2 (Noisy observations). Let us consider the case where, for a given x ∈ χ, we can only observe Ỹi (x) = Y i (x) + e i (x) where e i (x) is independent from any Y j (x ′ ). We denote the resulting noisy output variables, observations and covariances as follows:

Ỹi (g) := Ỹi (X g ) = Y i (g) + e i (g) Ỹ j := Ỹi j (X g j ) = Y j + e j η i,j (x, x ′ ) := Cov [e i (x), e j (x ′ )]
Algorithm 1: Simple Mixture Kriging predictor presented as an algorithm in pseudo-language. Data:

It is assumed that all grains are discretized and that for any grain g, X g is uniform. A single output random field Y (.) is observed.

G: A list of n observed grains G i , i ∈ {1, . . . ,
if i = j then K i,i = 1 [ G i ] x∈ G i k(x, x) + ϵ else K i,j = K j,i = 1 [ G i ]×[ G j ] x∈ G i ,x ′ ∈ G j k(x, x ′ ) Fill h: for i ∈ {1, . . . , n} do h i = 1 [ G i ] x∈ G i ,x ′ ∈g 0 k(x, x ′ ) Get results: α = K -1 h M = α ⊤ Y v = x∈g 0 k(x, x) -h ⊤ K -1 h
in the study space) to the nearest units. Let us consider a one-dimensional, centred Gaussian random field Y (x), x ∈ [1, 10] of constant variance. Let us assume that this field is observed at some points for which coordinates are rounded to the nearest unit, i.e., for 2 input values x 1 , x 2 ∈ ]0.5, 1.5], Using the geoR package in the R language, we simulate a 1-dimensional random field realization with a Gaussian covariance kernel. The specific parameters are detailed in Table 3. x is discretized between 0 and 10 with step 0.05. We pick 8 points for observations as listed in Table 4. These observations are plotted on Figure 3. Observations {o1, o2, o6} form the learning set, observations {o4, o5, o7} form the validation set, and observations {o3, o8} form the test set. These sets of observations are deliberately very small so as to represent the Mixture Kriging's behavior in a readable graphic. computed on all points in [0, 10]. The variance of the prediction error is also predicted using the formula given in Proposition 2.

Regarding Mixture Kriging (Figure 3 3). The ribbon shows an interval of radius twice the root square of the estimated prediction error variance. Left: Kriging model. Triangular points show observations. Right: Mixture Kriging. Horizontal line segments show observations. See Table 4 for more details about observations.

the prediction error value represented by the ribbon's height is important as compared with the predicted values. This means that if the underlying output is also noisy, error can quickly increase. This is the reason why, in real life, one needs much more observations to learn from, see Subsection 3.3.

Unidimensional case: grains of varying size

Imagine a company that wants to measure some performance indicator for manufactured objects that are produced according to certain design specifications. The design is denoted as x; it belongs to a set χ of permissible values, and Y(x) is the performance indicator. For instance, Y can measure the lift of an aircraft wing depending on some shape parameter x. Because of some unavoidable manufacturing precision issues, the manufactured object's characteristics do not match the design's specifications exactly. This uncertainty about the manufactured object induces some uncertainty about the performance indicator. Thus, the constructed design can be viewed as a random vector X gx , taking values in some tolerance set g x ⊂ χ around the design

x ∈ χ. When testing some designs x 1 , . . . , x n , the industry observes performances Y(g 1 ), . . . , Y(g n ). Measuring both the expectation and the variance of Y(x) for each permissible design x ∈ χ is one method to find the best design, but this can be costly, so fitting an interpolation model with the set of k observations is preferable. In this setting, for the sake of simplicity, we assume that Y(x) is conditioned by observations {y(x i ) = sin(x 2 i ) : i ∈ {1, . . . , n}}.

In this case, we assume that the precision associated with a design x i is an interval centred on x. The real characteristic of the object having performance y(x i ) is a random value in this grain, which is assumed to be uniform on all points of the grain.

We compare 3 models:

• P 1 : The manufactured object is produced exactly according to the design, the precision interval is restricted to a point.

• P 2 : The precision is the same for all designs, the associated interval is of fixed measure.

• P 3 : The larger is x, the larger is the uncertainty about the manufactured object, which means that intervals' measures are growing with the design x.

All three models have a null nugget effect and a Gaussian kernel having for variance parameter the overall variance of y on χ = [0, 4]. The range parameter is optimized by minimizing the mean squared error between y and point predictions on χ (see Table 4). When grains are restricted to points (Figure 5 top), we get the usual results on Simple Kriging, in particular, predicted values are exactly interpolating observations. When grains are intervals of the same size (Figure 5 middle), predicted values are not interpolating any more; predicted error is not null on the grains but far from the grains, it is smaller than in the previous case. In the bottom figure, the greater is x, the greater the uncertainty about the manufactured object as compared to design. The predicted error (ribbon) is increasing with the grain diameter. Overall, it is important to note that the Mixture Kriging model accounts for the randomness of input values without any nugget effect. This eliminates the adverse consequences of a nugget effect that could otherwise shrink mean predictions towards zero.

In the previous example, a very small set of observations was enough to make very good predictions. In the present one, the situation is different because observations are not drawn from a Gaussian random field but from a deterministic function. This underlying function is modelled as a noisy random field. Therefore, the Kriging error is greater than in the previous case. A potential extension of this illustration would be to optimize both the range and the nugget effect, but the purpose here is to visualize the effect of the uncertainty on the input and not the output. Let us now address the EPC prediction problem, keeping in mind that an Energy Performance Certificate (EPC) is given as an energy consumption in kW h/m 2 /year. The observed distribution of this energy consumption is provided in Figure 6. One considers a model for which χ is a city viewed as a 2-dimensional space with latitude and longitude as coordinates after proper projection, G is the set of plots, and a point in χ is associated with a given floor square meter of a building on the plot. A floor square meter is regarded here as a granule and not as a set of points in χ. This would not make sense since, for a multi-storey building, there are more floor square meters than the building's footprint area. x ∈ χ is therefore a reference point for this floor square meter the same way a point would be used to locate a citizen in a city (see Example 1). Y (x) is the areal energy consumption in x, typically the EPC of the dwelling to which belongs the floor square meter represented by x. Then an EPC in the database is the observed energy efficiency rating associated with one unknown point among those located on the plot indicated by the address. Therefore, for a certain plot g, this EPC is an observation of Y (X g ).

EPC is given as a numeric energy consumption per square meter and per year. This energy consumption is associated with a letter ranging from A to G. A and B label the most energy-saving dwellings (less than 90kW h/m 2 /year). F and G label the most consuming dwellings (more than 330kW h/m 2 /year). We want to model a situation where we observe EPC with uncertainty on the location of the observed dwelling on the land plot, where it lies, and where the observed dwelling can not be distinguished among all the dwellings of this land plot. We also want to predict an EPC numeric value at the whole land plot level, that is, for the set of dwellings it contains.

As can be seen in Figure 6, observations are strongly unbalanced, meaning that labels A, B, F, and G are rarely observed while labels C, D, and E are very common. As a result, labels A, B, F, and G are difficult to predict, although they are more interesting for decision-makers. Therefore, we introduce the Balanced Accuracy (BA) criterion. It is an asymmetric performance measure that focuses on good results [START_REF] Gösgens | Good Classification Measures and How to Find Them[END_REF] and it gives the same weight to each class. Denoting n ℓ the number of observations with label ℓ and n l,ℓ the number of predictions l with true label ℓ (true predictions of label ℓ), the balanced accuracy is given by the formula:

BA = 1 7 ℓ∈{A,...,G} n l,ℓ n ℓ
Given a real random variable X and F X its cdf, supposed to be invertible.

Let H(X) Let us consider the model M 1 such that:

:= F -1 N • F X (X)
• χ is the territory of an urban area in the French city of Angers in a 3-dimensional space where coordinates represent the image through H of the construction year, the latitude, and the longitude.

• A random field Y (x) is defined on χ. It represents the image through H of the energy consumption per square meter and per year at x.

• A grain g is defined as a set of points in a 3-dimensional space χ. A grain represents a land plot. Each point represents a square meter of living area. It has 3 coordinates. G denotes the set of all grains.

• For any grain g ∈ G, the random variable X g is the uniform law on the points of g. It represents the uncertainty on the observations' location. On g, the output variable is defined as: Y (g) = Y (X g ). By construction, Y is centred.

• A vector of observations of n distinct grains is given and denoted as Y.

Construction year (percentiles) 0% -10% 10% -20% 20% -30% 30% -40% 40% -50% 50% -60% 60% -70% 70% -80% 80% -90% 90% -100%

Leaflet | © OpenStreetMap contributors, CC-BY-SA G is mapped in Figure 7. Note that the grains seem to be disjoint, but they are not due to overlaps in the construction year dimension. The set of observations is represented in Figure 8.

For this model, the following assumptions are made:

• For any two distinct grains g, g ′ , random variable X g is independent from X g ′ .

• For any two points x, x ′ , the covariance between Y (x) and Y (x ′ ) is following a Matérn 3 /2 model: The Mixture Kriging predictor described in subsection 2.3 is used to predict energy consumption at the plot level. It can be proved that, without the nugget effect, the mean prediction, in the case of a 1-dimensional output, does not depend on σ 2 (the proof is simply deduced from the fact that for an invertible matrix A, we have (λA) -1 = λ -1 A -1 ). σ 2 is therefore set to 1. Θ is chosen so as to maximize the BA criterion of the predicted labels derived from the predicted energy consumptions. BA is computed using leave-one-out cross-validation. Note that the leave-one-out cross-validation predictor that is derived from Proposition 2 is also linear and optimal for quadratic error. A code has been developed in the R language to implement Mixture Kriging.

Cov [Y (x), Y (x ′ )] = σ 2 1 + 3 i=1 |x i -x ′ i | θ i exp - 3 i=1 |x i -x ′ i | θ i where U = (σ 2 , θ 1 , θ 2 , θ 3 ) ∈]0, 1]×]0, +∞[ 3
So as to assess the effect of balanced accuracy on the optimum, we also consider a model M 1 ′ , which is the same as M 1 except that parameters are assessed optimizing the accuracy. The accuracy is the total number of labels correctly predicted divided by the number of predictions.

Let us now consider the Kriging model M 2 to compare performances with the Mixture Kriging model M 1. M 2 has the same properties as M 1 presented above, except that:

• Grains are singletons. A grain g = {x 1 , ..., x q } is replaced by a point x of coordinates the minimum construction year and the mean latitude and longitude values. Note that it is assumed that the year of construction of the eldest building portion is the most meaningful information for prediction. This makes sense, especially because the oldest part of a building is usually also the largest one.

• A nugget effect σ 2 e has to be introduced so as to have a smooth predictor:

V [Y (x)] = σ 2 + σ 2 e .
For M 2, the Kriging predictor is used. Other parameters are left as default.

V = (σ 2 , θ 1 , θ 2 , θ 3 , σ 2
With regards to the optimal parameters in Table 5, length scale parameters are smaller in M 1 than in M 2, meaning that M 1 prediction is influenced by fewer neighbours than M 2. The nugget effect found for M 2 is small. As for the optimal performances in Table 6, M 1 reaches a larger BA than M 2 by 37%. However, M 1 has lower performances on other indicators with a difference of approximately 10%. The range of all 365 mean predictions with M 1 is 150% larger than with M 2. These figures are better understood by examining the confusion matrices in Tables 7 and8. Indeed, the percentage of large errors (represented by the red area) is 3% with model M 1 and 0.5% with model M 2. We know that large errors have an important impact on cators are very similar, let alone the smaller variance of M 1 ′ 's predictions.

Optimizing parameters based on Balanced Accuracy forces the model to predict more often labels A, B, F, and G so that the distribution of predicted labels is very close to the distribution of observed labels as can be seen in Table 10. In our case, the confusion matrices show that this effect is positive for labels A and B, as more true A or B are predicted as A or B. But the effect of balanced accuracy does not bring benefits for labels F and G, on the contrary, it has a tendency to predict more F and G where the true label is D or E. A possible explanation for this moderate benefit of introducing the balanced accuracy is that we are missing some information. The moderate size of observations (365 individuals) makes it difficult for a model to discriminate between rare labels and frequent labels. For instance, there are only 2 observed G labels. One can expect a model learning from a larger number of observations to perform better. Moreover, in an area where buildings are old for instance, our model cannot distinguish a building that has never been renovated from the others. It may be useful in further studies to introduce more variables, such as a comfort level. However, as discussed below, the proposed model is quite heavy in terms of computation resources; therefore, scaling up or adding variable has an important computational cost.

Discussion and conclusion

Since the discovery of Kriging, the issue of learning from and predicting areal data has been a concern. Proposed models have mainly assumed that the output variable at the areal level is the mean of the point outputs, which has proven helpful in various fields such as mining, climatology, or satellite imaging, where averaging makes sense for interpretation and where blocks tend to have similar shapes and sizes. However, in other fields such as agriculture or social studies, blocks can have varying shapes or sizes, and averaging is not always the most meaningful interpretation. In these cases, problems like the Modifiable Areal Unit Problem (MAUP), the ecological inference problem, and the variance reduction due to averaging can become challenging to solve. Over the past few decades, researchers have been developing methods to assess and/or correct the MAUP effect (Briz-Redon, 2022). Modifying territory partitioning [START_REF] Li | A simple kriging method incorporating multiscale measurements in geochemical survey[END_REF] is also an effective solution for addressing variance reduction problems, but it is not always possible. Both Kriging and block-Kriging incorporate uncertainties on input and/or output values through the addition of a nugget effect to variances, thereby simulating the addition of a white noise to the output variables. This transformation smooths predicted values but also shrinks them; the range between minimal and maximal predicted values is reduced, thus degrading the prediction quality of values that are particularly large or particularly small.

The availability of new datasets with uncertainty on the inputs (uncertain positions) and where averaging is not a meaningful interpretation has driven us to seek a novel method of spatial interpolation. We have introduced a new element in the model that is a random input value. It has been found

that resulting mixture distributions can be interpolated optimally, and the resulting Best Linear Unbiased Predictor (BLUP) requires only the first 2 moments of the prior random field and a spatial covariance function. This model can learn from and predict outputs associated with grains of any shape, size, or cardinality. Even single points are acceptable. The term "grain" has been introduced to describe these objects.

The new model called Mixture Kriging is still consistent with Kriging in the sense that Kriging is a special case of Mixture Kriging where grains are restricted to singletons. However, Mixture Kriging generates a mean prediction range that is not impacted by the grain's shape or size under usual conditions. As a consequence, there is no reduction in the mean prediction's range due to this factor. If the output variable's variance is the same everywhere at point level, then it is also the same as the output variable's variance at grain level, meaning that there is no variance reduction either. Similarly, if the covariance between the output variable of interest and another output variable is the same everywhere at the point level, then it will also be the same as the covariance at the grain level, regardless of the grain's shape.

This implies that this model has no measurable MAUP effect in the sense of [START_REF] Briz-Redon | A Bayesian shared-effects modeling framework to quantify the modifiable areal unit problem[END_REF].

Without any MAUP effect, the Mixture Kriging approach is able to handle multi-scale data. We hope that this can help handling datasets coming The main computational distinction between block-to-block Kriging and Mixture Kriging lies in the method of computing the observations variance and the covariance between covariates associated with the same grain. This results mainly in the diagonal of the observations covariance matrix being greater than what is found with Kriging. This is precisely the sought effect when introducing supplementary noise on the outputs (nugget effect) in Kriging for smoothing predictions. This explains why Mixture Kriging has smooth predictions but with limited shrinkage, hence a good performance with Balanced Accuracy. In practical applications, Mixture Kriging is therefore designed to handle data with uncertainty on the input values without introducing the nugget effect.

Regarding computational differences, it should also be noted that Mixture Kriging (like block-to-block Kriging) has a higher computational cost than Kriging, this cost is growing like the squared value of the density of points in the grains. This is an important limitation of the model. For instance, in the models M 1, M 1 ′ and M 2 presented in Subsection 3.3, there are 395 observations. The Kriging model M 2 requires 365 × 366/2 = 66, 795 covariances to be computed. But the Mixture Kriging models M 1 and M 1 ′ require to compute 3, 770, 500, 618 point-to-point covariance in order to compute the 66, 795 covariances between grains. Scaling up the model may, therefore, be difficult. This computational complexity is highly dependent on the definition of the random position X g for each grain and on its discretization. For the above models, X g is supposed to be uniform for all grains, and the number of discretized points is the number of square meters of living space on the grain. But any new model based on Mixture Kriging requires an appropriate definition of these random variables, depending both on the grains' geometries and on the studied output variable(s). Another limitation of the model is the difficulty of assessing its parameters, especially the range. It is difficult to compute a variogram because there is no natural definition of a distance between grains. Estimating the range is also possible by minimizing an error measure, but this process requires computing numerous different models, which is costly, as mentioned above.

Keeping in mind its limitations, this new approach opens the way for implementing Mixture Kriging models with new datasets that have been impossible to fit in the usual Kriging framework or with usual Kriging software packages. In particular, datasets that inform about granules that are uncertainly defined, such as dwellings, buildings, streets, human persons, and households. It can also be used for datasets informing about granules, which should have deterministic shapes or positions in the input space, but come with numerical uncertainty such as measure precision, rounding effect, observations' aggregations, or observations' anonymization. Moreover, the model can handle multivariate outputs, even if some output components are missing in the observations. Encouraging results have been found when studying the prediction of Energy Performance Certificates (EPC). Results show that Mixture Kriging can be useful to improve the prediction of values far from the average and, in our case, to improve the detection of energy-saving homes.

Future studies should test the upscaling feasibility of the already developed model and the benefits of using covariates. We also study the possibility of developing a similar model with Universal Kriging.

Figure 1 :

 1 Figure 1: Prescribed vignette appearing on the French energy performance certificate up to 2021. Label A refers to energy-efficient dwellings, and label G refers to energy-intensive dwellings.

Figure 2 :

 2 Figure 2: Map of French inventoried EPCs over a neighborhood of Lyon city. This image is a screen capture of the French National Observatory of Buildings (Observatoire National des Bâtiments -ONB), released with the consent of the rights holders U.R.B.S. SAS. address area (m 2 ) walls ... energy consumption EPC 161 rue du Chateau 83 bricks ... 210 D 02089 BILLY

  the observer sees the same value x1 = x2 = 1. For a Kriging model, these are multiple observations of the same point, and it is necessary to introduce a nugget effect in the model for the observations' covariance matrix to be invertible. This nugget effect simulates an uncertainty on the output values, while the uncertainty is really on the input values. It rather makes sense to describe those input values as random positions x1,g and x2,g in g = ]0.5, 1.5] instead of deterministic x1 = x2 = 1. Then, we can model the observed objects as mixture distributions and fit a Mixture Kriging model. Let us compare both approaches.

Figure 3 :

 3 Figure 3: Rounded inputs. Left and right: The dashed line shows the underlying simulated random field. The solid line labelled "predictions" shows the fitted model mean prediction (see Table3). The ribbon shows an interval of radius twice the root square of the estimated prediction error variance. Left: Kriging model. Triangular points show observations. Right: Mixture Kriging. Horizontal line segments show observations. See Table4for more details about observations.

Figure 4 :Figure 5 :

 45 Figure4: Properties of models P 1 , P 2 , P 3 . Range is an optimal value so as to minimize mean squared error.

Figure 6 :

 6 Figure 6: Bar plot of EPC labels frequencies among all EPCs collected in France between 2014 and 2021. Classes A, B, F, G are rare while classes C, D and E are frequent.

  where F N is the standard Gaussian distribution cdf. H is invertible, and H(X) follows a standard Gaussian distribution by the probability integral transform theorem. Using H we normalize input and output variables.

Figure 7 :

 7 Figure 7: An urban area in Angers: latitude is the vertical dimension, longitude is the horizontal dimension, and construction year is given by the colour. The side of the square is 1km. Construction years range from 1340 (first percentile) to 2019 (last percentile).

  Figure 8: Left: Map of the 365 observations. Right: Map of all predicted values (labels derived from Mixture Kriging means). Each colour represents a label associated with a numeric value. See also Figure 1. σ 2 is called the variance coefficient, and Θ = (θ 1 , θ 2 , θ 3 ) are the length scale coefficients. Note that no nugget effect is required because the model takes into account the spatial uncertainty of the input by construction.

  e ) is chosen so as to maximize BA, the same way as for M 1 . The standard R package DiceKriging is used for prediction.There are 365 observations on the given territory. The best parameters are estimated by optimizing the performance indicator, Balanced Accuracy or Accuracy, computed by leave-one-out cross validation. All models M 1, M 1 ′ and M 2 are optimized with the genetic algorithm provided by R package ga parametrized with population size 50, elitism 5, maximum number of iterations 100, maximum number of iterations without improvement 100.

  from multiple sources in the same model. This model can potentially be used to fit ecological data or social data. For instance, on a global scale, the Intergovernmental Panel on Climate Change (IPCC) studies planetary boundaries on water based on gridded data, but for the study of specific territories, studies are commonly done on watersheds. The Mixture Kriging model has the ability to combine these two scales of study in the same model to benefit from both global and local studies.

Table 1 :

 1 Structure of the dwellings table from the French Ministry of Finance. The actual table comprises 118 features. Geographic position is identified by a land plot ID.

	dwelling ID	address	area (m 2 ) bedrooms ...	land plot ID
	024830065432 161 rue du Chateau	83	3	... 024830000C0057
		02089 BILLY

Table 2 :

 2 Structure of the observed EPCs table. Geographic positions are indicated by addresses.

  n}, each grain being a table with its points coordinates. Y: Observed values Y i , i ∈ {1, . . . , n}, a numeric vector of same length as G.

k(., .) : Covariance kernel, a function that takes 2 points and returns a positive real number. g 0 : An unobserved grain to be predicted i.e. a table with its points coordinates. ϵ : A positive real number giving the nugget effect.

Result:

Optimal weights α for g 0 . Conditional expectation M of Y (g 0 ). Kriging variance v = V [Y (g 0 ) -M ] (variance of the prediction error). begin Fill K: for (i, j) ∈ {1, . . . , n} × {1, . . . , n}, i ≥ j do

Table 3 :

 3 Parameters and performances of fitted models in the case of observations with rounded inputs. Note that the nugget effect for Kriging is the result of an optimization process. For Mixture Kriging, nugget is null by design. Validation MSE: Mean Squared Error on validation set. Total MSE: Mean Squared Error on the complete interval [0, 10].

	Underlying field	Model properties		Validation Total
	Variance Range	Model	Variance Nugget Range	MSE	MSE
	1	4	Kriging	1	10 -9	4	0.037	1.14
	1	4	Mixture Kriging	1	0	4	0.027	1.18
	The Kriging model (Figure 3 left) has repeated observations for x = 1
	and x = 3. The learning set is used to fit a family of models with the same
	kernel parameters as those used for simulation plus a nugget effect among
	(10 -i ) i∈{1,...,10} . The nugget effect yielding the smallest mean squared error
	(MSE) on the test set is selected. A new model is fitted with both learning
	and test sets using the same kernel and the previously selected nugget ef-

fect. This model is applied to compute a validation MSE and a total MSE

Table 4 :

 4 Observations of the simulated Gaussian random field.

Table 7 :

 7 Confusion matrix of M 1 predictions.

	True values	Predicted values					True values	Predicted values
		A	B	C	D	E	F	G		A	B	C	D	E	F	G
	A	2	1	3	2	2	0	0	A	1	0	3	5	1	0	0
	B	1	3	1	9	2	2	0	B	0	2	1	11	4	0	0
	C	1	3	25	26	15	4	0	C	0	1	13	48	12	0	0
	D	3	5	21	80	33	5	1	D	2	1	19	94	32	0	0
	E	4	2	12	36	36	5	1	E	0	1	9	56	30	0	0
	F	0	3	2	4	5	3	0	F	1	0	2	11	3	0	0
	G	0	0	0	1	1	0	0	G	0	0	1	1	0	0	0
									Table 8: Confusion matrix of M 2 predic-
									tions.
	True values	Predicted values
		A	B	C	D	E	F	G
	A	0	2	2	5	1	0	0
	B	1	0	3	9	3	2	0
	C	2	2	23	29	14	4	0
	D	1	6	17	91	28	2	3
	E	1	6	14	31	36	6	2
	F	1	0	3	8	2	3	0
	G	0	0	1	0	1	0	0

Table 9 :

 9 Confusion matrix of M 1 ′ predictions

		True Predicted
	A	10	11
	B	18	17
	C	74	64
	D	148	158
	E	96	94
	F	17	19
	G	2	2

Table 10 :

 10 Distribution of labels in M 1

Acknowledgements

The authors acknowledge support from the URBS enterprise, www.urbs. fr. They thank in particular Maximilien Brossard for careful reading and constructive comments.

This research was jointly supported by Mines Saint-Etienne graduate engineering school and research institute (https://www.mines-stetienne.

fr/en/), URBS enterprise (https://www.imope.fr/) and French National Agency for Research and Technology (https://www.anrt.asso.fr/fr).

Then the covariance between 2 grains' outputs is: ki,j (g, g ′ ) := Cov Ỹi (g), Ỹj (g ′ ) = k i,j (g, g ′ ) + E [η i,j (X g , X g ′ )]

Therefore the observations covariance matrix writes: K := Cov Ỹ j , Ỹ j ′ j,j ′ ∈{1,...,n} K = K + Cov e j , e j ′ j,j ′ ∈{1,...,n}

And the covariance vector between the observations and a new grain writes: hi (g) := Cov Y j + e j , Y i (g) + e i (g) j∈{1,...,n} hi (g) = h i (g) + E η i j ,i (X g j , X g ) j∈{1,...,n} hi (g) = h i (g) + h e,i (g) Typically, we can assume that E [η i,j (X g , X g ′ )] = 1 {i=j} 1 {g=g ′ } η i,i (g, g). In which case K e is a diagonal matrix and h e,i (g) is null as long as g is not among the observed grains.

Contrary to Gaussian Process Regression, the prediction cross error c i,j (g, g ′ ) defined in Equation ( 2) is usually not equal to the conditional covariance E [Cov [Y i (g), Y j (g ′ )|Y]]. However, under certain assumptions, one can prove that if M i (g) = E [Y i (g)|Y], then the cross error can also be viewed as a conditional expectation:

given in Supplementary material Appendix B.

Illustration

Unidimensional case: rounded inputs

A common issue when feeding geo-statistical models with real data is the precision of the input data and its impact on a model's performance. Usual applications of Kriging take this uncertainty into account when increasing output variables' variances by a value that is known as the nugget effect (e.g. [START_REF] Rocas | Nonintrusive uncertainty quantification for automotive crash problems with VPS/Pamcrash[END_REF]. Precision being a typical case of input data uncertainty, the example below simulates the effect of rounding input values (coordinates MAE and RMSE. However, the percentage of true labels A and B that are predicted as A or B is 25% with M 1 and 10% with M 2. For labels F and G, these figures are 16% and 0% respectively. This information is valuable for decision-makers seeking to identify energy-efficient and/or energy-intensive dwellings.

These results suggest that Mixture Kriging (M 1, M 1 ′ ) predictions have an improved range as compared to Kriging (M 2): the range of mean predictions by Mixture Kriging is greater than by Kriging. This allows better predictions for extreme labels A, B, F, and G. Despite having fewer parameters (ϵ 2 and σ 2 are regarded as constants), Mixture Kriging improves the BA, although it also leads to more frequent large errors. Mixture Kriging accounts for uncertainty in the input data, eliminating the need to add a nugget effect. In this example, it avoids grouping predictions near the mean value (shrinkage) and yields a better BA as compared to Kriging that requires the introduction of a nugget effect.

Among Mixture Kriging models, as expected, M 1 has a better Balanced Accuracy than M 1 ′ , and M 1 ′ has a better Accuracy than M 1. Other indi-

Appendix A. Proof of Proposition 2 (supplementary material)

This proof employs a classical statistical approach to compute a Best Linear Unbiased Predictor using a family of observed random variables that are not necessarily Gaussian but have known first and second moments.

It is interesting for the understanding of the problem to give it a geometrical approach. Let us denote F i (g) the set of linear unbiased predictors of Y i (g) given an observation vector Y. With previous notations, it means that:

And similarly, we denote:

the feature space generated by observations)

One can note that F 0 is a subspace of F of dimension dim(F ) -1. Moreover F 0 + F i (g) = F i (g), meaning that F i (g) is an affine subspace of F having F 0 for underlying vector space (see Figure A.9). But it also means that the sets of unbiased linear predictors for each output variable are parallel:

Now, given that we are minimizing the quadratic error between Y i (g) and M i (g), which can be seen as the distance between Y i (g) and M i (g) in H, the optimization process is geometrically a projection of Y i (g) on F i (g). This approach is illustrated in Figure A.9. Proof. For given i ∈ {1, . . . , p} and g ⊆ χ, let M α = α ⊤ Y be a linear predictor of Y i (g), where α = (α 1 , . . . , α n ) is a vector of weights, and denote the associated error v i (g, α)

By differentiation over each component of α,

Without constraints, this value should be null at any extremum, and thus the optimal vector of weights is

Since K is symmetric positive, this only extremum is a minimum.

(ii) If µ ̸ = (0, . . . , 0) ⊤ then the condition for unbiasedness writes µ i (g) = α ⊤ µ by linearity of expectation.

v i (g, α) rewrites again:

ii

We introduce the Lagrangian operator:

We are minimizing a quadratic function over a single affine equality constraint. A necessary optimality condition is:

that is to say: 2Kα -2h i (g) -2λµ = 0 , and therefore the optimal weights are

The unbiasedness condition is:

Therefore this only solution is a minimum of v i (g, α).

Let us consider now the cross-errors:

Due to unbiasedness condition, it means that:

Which rewrites:

iii Note that equation (A.1) is true for any linear unbiased predictor.

Which, in the case of simple Mixture Kriging, simplifies into:

And in the case of ordinary Mixture Kriging:

The expressions of v i (g) = c i,i (g, g) in both cases follow immediately.

Appendix B. Cross-errors and conditional covariances (supplementary material)

It is well known that the best predictor of Y i (g) is also the conditional variable E [Y i (g)|Y]. However, this best predictor is not necessarily linear, especially in non Gaussian cases. The following proposition proves that if the Best Linear Unbiased Predictor is the best overall predictor then the error covariances can also be seen as conditional covariances.

Proposition 3 (Cross-errors and conditional covariances). Consider the assumption

Under assumption (A), cross errors for both Simple Mixture Kriging and Ordinary Mixture Kriging are:

does not depend on Y, as it is the case for conditional Gaussian vectors, Equation (B.1) simplifies:

Assumption (A) holds for example when {Y(x) : x ∈ χ} is a vectorvalued Gaussian random field and when each X g is Dirac distributed.

Proof. The proof uses a classical approach on orthogonality of Best Linear Unbiased Predictors. It is presented here in three steps. The proof can be simplified in the Simple Mixture Kriging setting.

• First, given the notations introduced in Appendix A, let δ ∈ F 0 be a non-zero vector and β a real number.

We have:

The minimum value of this polynomial expression is reached for:

Since the only optimal point is M i (g), M β 0 i (g) = M i (g) and therefore β 0 = 0. As a consequence, as both E [ϵ i (g)] = 0 and E [δ] = 0:

2) From a geometrical point of view it is equivalent to say that the inner product of the error and any vector of F 0 , such as the difference of any linear unbiased predictors of Y j (g ′ ), is null. This approach can be found for example in [START_REF] Aldworth | Spatial prediction, spatial sampling, and measurement error[END_REF], section 4.5.1. page 122, in the case of ordinary Kriging on a stationary process.

• Now, let δ and δ ′ be any two vectors of F 0 . As a consequence of the previous result in Equation (B.2), we have:

• On the other hand, using the conditional covariance formula, we have:

Given a Y, the random variables δ, δ ′ , M i (g) and M j (g ′ ) are constant, so that the first term is

Furthermore, we have assumed in Assumption (A) that


Nicolas Sidere
email: nicolas.sidere@univ-tours.fr

Pierre Heroux
email: pierre.heroux@univ-rouen.fr

Jean-Yves Ramel
email: jean-yves.ramel@univ-tours.fr

A vectorial representation for the indexation of structural informations

Keywords:

This article presents a vectorial representation of structured data to reduce the complexity of dissimilarity computations in an information retrieval context. This representation enables, via a computation of an adapted measure, to approximate the distance between structural representations in both context of distance between graphs and searching occurrences of subgraphs. Preliminary results show that the proposed representation offers comparable performance with those of the literature.

Introduction

The evolution of digitization techniques, the easiness of broadcasting by the way of the Internet and the wish to keep and access digitized collections of documents put the themes of indexation and retrieval in the heart of many research axes. With the diversity of thematics (preserving old books, archiving administrative data, automatic reading, ...) the amount of data generated grows up and up. This contributes to the multiplication of works in this domain. If some solutions come out, these are often restricted to a specific application domain or corpus. Many uses a keyword-based indexing extracted by optical recognition characters systems which are inefficient on particular documents (old books archives, graphical documents, ...) or with a manual annotation limited by the size of the corpus or by the subjectivity of the user. So, one can see a certain interest in a new querying modalities. Consequently, the nature of works are more and more aimed to a new characterization of documents with indices such as structure. This is the point we intend to study in this article. According to the situation, the structure analyses can be used in many ways :

the layout description. For example, the layout of a phone book, which is quite significant. -the logical organization (title, section, paragraph, ...) can be used to differenciate some documents, a newspaper from a novel for example. -the frequency of the same element, in a technical drawing with several occurences of a symbol.

The document retrieval consists in measuring how a structural description is relevant with respect to the user's need, which can be expressed with a structural representation of the request too. The purpose is to return k documents ranked according to their relevance. In fact, as the notion of structure of a document can be expressed by different ways according to the user, it is quite important that the user has the final choice. Most of the times, this information is represented by graphs. Many methods can be found to label a graph to obtain this representation. Nevertheless, the computation of a graph-to-graph distance reveals to be a NP-Complex problem. This complexity grows in an exponential way with the number of nodes.

Our work aims at reducing this complexity. An interesting approach consist in extracting a numerical characteristic vector which embeds a part of the graph topological information. The comparison of two graphs is reduced to a more simple computation of a distance between two vectors in an euclidean space. More, an information retrieval context where the documents are described by structural informations, indexing can be done offline. Some works have already been done :

-A first method is presented in [START_REF] Lopresti | A fast technique for comparing graph representations with applications to performance evaluation[END_REF]. This representation is based on vertex degrees. The simplicity of the description combined with a comparison of two graphs reduced to a linear time allow to find topologically similar graphs in the most of cases. -In the second approach presented in [START_REF] Barbu | Clustering document images using a bag of symbols representation[END_REF] where the representation of a document is focused on occurent elements (subgraphs). The document is described with a bag of symbol representation. A rich knowledge is necessary to enable the final identification.

The characterization of a graph by a vector gives, in the case presented above, advantages, but also drawbacks. For example, the description proposed by Lopresti and Wilfong ( [START_REF] Lopresti | A fast technique for comparing graph representations with applications to performance evaluation[END_REF]) is not bijective. Thus, two non-isomorphic graphs can have the same vectorial description for which the distance is null. This ambiguity is due to the vector construction method. It is only based on the vertex degree. Several configurations from the same set of nodes with different graphs but the same signature may occur. We think that this description does integrate the informations on the graph topology in a superficial way.

Barbu's approach need a rich knowledge of the domain, that does not allow to treat a document set with a huge heterogenieity. So, we can notice that the relevance of the results are dependant of the graph vector characteritics.

Our approach relies on these works. The idea is to build a lexicon with model graphs differenciated by their topology and their size. The vector will be built according to the occurences of these figures present in the target graph. All the problematic is on the choice of the lexicon, which must answer to the genericity problem but also needs to be performant and cute in results

In the next section we present the lexicon that we chose and how it can be built. The section 3 shows the construction process of a vectorial representation of a graph. Section 4 presents two distances operator using this vectorial description, both distances correspond to two different cases of use. Section 5 presents the first experiments showing that the representation offers performance equivalent to Lopresti and Wilfong in a context of classification. Finally, Section 6 evaluates and sets out a number of prospects for the continuation of this work.

The lexicon construction

As said before, the lexicon is the basement of the construction of our graph vectorial signature. So, the lexicon content is quite determining in the relevance of the vectorial representation. We have seen ( [START_REF] Barbu | Clustering document images using a bag of symbols representation[END_REF]) that it is possible to build it from the n most frequent subgraphs of the database, for example. Nevetheless, this is only possible when the base presents a high homogeneity. The frequency is revealing a certain semantic. Thus, in the work of Barbu, subgraphs are frequently associated with graphic symbols, entities which carry meaning in a technical documentation.

Unfortunately, there are many cases where these assumptions are not verified. For example, old books are different depending on the author, publisher, date ... Therefore, to keep a generic nature, it is preferred to use a lexicon totally independent from the database content. However, this lexicon must be sufficiently comprehensive to ensure that these terms can afford to discriminate a graph from another.

We have therefore decided to take as a baseline the non-isomorphic graphs network presented in [START_REF] Jaromczyk | Relative neighborhood graphs and their relatives Proceedings of the IEEE[END_REF]. The network presents all graphs composed of n edges up to N ( N is the maximum number of edges). This network is built iteratively from a graph made up of a single vertex. At each iteration, it is possible to construct a graph of rank n adding an edge to a graph of rank n -1 with the ability to add a vertex if needed. All solutions are being considered which makes the network complete. A graph with rank n built from a graph with rank n -1 is called successor. Conversely, the graph of n -1 is called predecessor. A graph of this network may have several successors. Similarly, several graphs with rank n -1 can rise to a single successor. Ways of construction of this non-isomorphic graph network can be stored to build all predecessors and successors of a graph.

Thereafter, the term pattern will refer to a subgraph element of the nonisomorphic graph network. So, the lexicon is composed of all patterns until the defined rank.

For example, the figure 1 shows the non-isomorphic graph network until the fourth rank giving a lexicon of 11 patterns. The dotted arrows indicate the path of construction of the network, the arrows are directed from the predecessors towards the successors. We can notice that the number of patterns increases exponentially with the rank. The size of the lexicon is a parameter to determine according to several criteria. Indeed, the complexity of the transformation to a vectorial representation is directly dependent of the number of patterns. However, the more the size of the lexicon increases, the bigger the patterns it integrates are. The vectorial representation then integrates more information on topology. Therefore, it is necessary to find a trade-off between expressiveness and complexity.

The construction of the vectorial representation

The construction of the vector consists on determining the frequency for each patterns of the lexicon in the graph to describe. The dimension of the vector is the size of the lexicon. Its construction can become very costly in time. However, the indexing phase, which is to build the vectorial representation of all graphs of the base, can be done offline. The complexity of construction of the vector is only critical when processing the query graph. Indeed, this graph can be obtained from a sample presented by a user. The extraction method of representation will be the same that is used for the base and may be costly.

The lexicon is sorted in the order of the subgraphs network, the first value of the vector describing a graph is then the number of vertices, the second the number of edges, the third the number of subgraphs with two edges, ... The search for patterns may be different depending on constraints. The recording (or not) of patterns that share one or several components (vertices or edges) directly influences the vectorial representation of a same graph. The use of this type of constraints can be justified by the need to find a bijection between the graph and its vectorial representation. Indeed, for the vectorial description to be closest to the graph, a pattern discovered in a graph must be removed from it. Elements (edges or vertices) can not belong to another occurrence of the same pattern. However, the complexity of the extraction of the vectorial representation with these constraints increases. Following the case, it is not necessary to apply such constraints. We give details on this point in the next section As a didactic example, the figure 2 represents the vectorial description associated with a undirected and unlabelled graph (Fig. 2(a)) for a lexicon of size 6 (order maximum of patterns : 3) without constraints (Fig. 2(b)) with edge-disjoint constraint (Fig. 2(c)) and vertex-disjoint constraint (Fig. 2(d)).

In the next section, we present two ways to use the vectorial description. We will show the advantage of being able to decline the representation according to the selected use case.

Examples of measure depending on the case of use

A computation of distances in a grah space can quantify the difference between two graphs. However, the complexity related to the computation of the distance between graphs prohibits its use in a case of seeking information where the purpose is to order all documents of the basis (or the k nearest) depending on their proximity to a query. The vectorial representation that we propose will enable to approximate this distance by a dissimilarity measure between structural representations of documents on the one hand, and a request expressed by the same structural mean, on the other. Even if the extraction of this vectorial representation requires a important cost, this task of indexing can be done offline and can be tolerated.

The various dimensions of the vectorial representation that we offer presents a certain redundancy. Indeed, if a pattern of order n is counted, all its predecessors are also included in the statement. This redundancy is the integration of a degree of robustness we wished to provide in our presentation. It seemed appropriate to take into consideration the disturbances that could infer on structural representations often extracted automatically : appearance or disappearance of vertices or edges. Thus, if two identical graphs have strictly identical vectorial descriptions, two graphs which one is a noisy version of the other have at least some patterns below in common.

Finally, we justify our proposal of vectorial description by the fact that it can be used in two cases of use. In the first practice, it is to find in the indexed graph database the nearest to the query graph. A second application is to find graphs of the database containing the largest number of occurrences of the query graph. Both following subsections introduced measures on our vectorial description and applying to these two cases of use.

Measuring dissimilarity graph to graph

In this case of use, the purpose is to find, among a graph database, those closest to a query graph. The graphs in the database and the query graph are represented by a vectorial features. The distances between graphs of the database on the one hand and the query graph on the other hand is approximated by a dissimilarity measure. This measure of dissimilarity corresponds to the distance between the vectorial representations of graphs. This problem has already been raised in the literature. We have chosen to use a Euclidean distance. In a dimensions space, the distance is expressed in this form:

D(G 1 , G 2 ) = N i=1 (k 1i -k 2i ) 2
with G 1 and G 2 two graphs to compare, k i1 and k i2 the occurrences of the pattern i in G 1 and G 2 .

Depending on the application framework, this measure can evolve. In technical document retrieval, for example, experts can provide a priori knowledge on semantics of symbols present in the document. This can "punish"or "prime" the presence or absence of a symbol. Of course, our approach can be expanded to all types of documents where sufficient knowledge allows to consider the relevance of patterns. That is rendered by weighting α i each pattern i.

D(G 1 , G 2 ) = N i=1 α i (k 1i -k 2i ) 2
The weights α i can then be determined by optimization algorithms or artificial learning depending on case of use. Similarly, if that vectorial representation is used on a uniforme database, it is possible to apply feature selection methods aiming at the reduction of dimensionality. The purpose of this reduction of the vector is to improve performance by removing aberrant or unnecessary patterns. It is also possible to combine patterns. There are several methods in literature, such as principal components analysis or feature selection.

In this case, the use of representations without constraints give a redundancy of the information in order to increase the precision of the vectorial representation.

Finding occurences of a query graph

Other applications do not need to measure a distance between two vectors to quantify the similarities between them, but investigate the presence and number of occurrences of the query graph in a graph, even in a pre-indexed database.

For example, finding a specific electrical component in a plan is a possible application. Here, the aim is to find the number u of occurrences of the query graph S in the graph G.

V G is the vectorial representation of G and V S for S. There is v Gi (respectively v Si ) the occurences number of the pattern i in G ( respectively in S).

V G =    v G1 . . . v GN    V S =    v S1 . . . v SN    So, ∀i ∈ N, 1 ≤ i ≤ N, v Gi ≥ u.v Si
In other words, a graph G includes u occurrences of a query graph S, then each subgraph S is present in G u times at least. This scheme may be applied to all subgraphs of S and particularly on the patterns of the lexicon. Thus, for all i dimensions of the vectorial representation.

∀i ∈ N, 1 ≤ i ≤ N, u ≤ u i = v Gi v Si avec v Si = 0 Consequently, u ≤ min i/vSi =0 v Gi v Si
Then, the quantity min i/vSi =0 vGi vSi can be used to approximate u, the occurences number of S in G.

It is noteworthy that in this case of use, a vectorial representation extracted with tight constraints, as we have seen in the third paragraph, must be used. Indeed, research occurrences of a subgraph often needs that all occurrences must be fully present in the graph. They can not share edges or node. The choice of constraint depends on the context and then requires an a priori knowledge of an expert.

Experiments

We describe in this section the first experiments on the vectorial description of graphs we conducted. During these tests, our vectorial description of graph is compared to the vectorial description proposed by Wilfong and Lopresti.

For both descriptions, we have limited the size of the vector to dimension 6. Thus, the vectorial description Lopresti and Wilfong graphs are in the vertices of degree 1 to 6 and our description are the patterns with 3 edges or less.

Both descriptions are compared on a classification task by nearest neighbours using the technique known as "leave one out", ie that each element is ranked considering all others belong to the learning database.

The first comparison was made on synthetic graphs. In this database, each class is associated to a random generating model with two parameters that are n the number of vertices of the graph and d the average degree of vertices. 20 classes have been generated for n taking values among 5, 10, 20, 50 and 100 and d taking values 0.2, 0.5, 1 and 2. Thus, 20 graphs were generated for each class, making a database of 400 graphs.

The rate of correct classification using the description of Lopresti and Wilfong reached 99.45 %. The few confusions are between classes of graphs C (n = 5, d = 0.2) and C (n = 5, d = 0.5). The classification using the proposed description given strictly identical results, the same confusion occuring on the same elements.

In a second experiment, graphs correspond to structural representations of symbols from GREC competition (recognition of symbols). We used classes of symbols which have been alterated by rotation and vectorial bending. The structural representations are adjacency regions graphs corresponding to the black and white connected components. The classes contain between 5 and 19 elements per class, the total number of elements of the database rise to 88. Figure 3 shows examples of symbols from the database. Good recognition rate achieved in the first experimentation should be put into perspective considering that generative models of random graphs as they are defined clearly distinguish the classes. Indeed, classes could be classified without any confusion by considering only the number of vertices and the number of edges.

The smaller rate classification observed on the application of recognition of symbols must be relativised because the structural representations which are used are not labelled and they only reflect the topology of the adjacency regions graphs without qualifying the nature of the region. In one case as in others, it is interesting to note that the rate classification obtained with the two vectorial descriptions are comparable. This indicates that the description we propose can be used in a search for nearest neighbour.

Conclusions

In this article, we have presented a new vectorial description of graphs in order to the complexity of computing distances needed for information retrieval applications with structured data. This representation is proposed to be applied to two cases of different use:

1. Finding similar graphs; 2. Finding graphs containing multiple occurrences of a query graph.

The results of preliminary tests highlight that our vectorial representation is equivalent in terms of performance to other approaches proposed in the literature to approximate distance between graphs in a task of classification.

However, we have seen throughout this article that some points remain outstanding. It now seems important to measure the influence of the size of the lexicon on the construction of the description and its complexity. Indeed, table 1 shows the need to limit the description to low rank to reduce the complexity of its construction. However, initial tests have proved that the relevance of the description was better with a important number of patterns. future work will naturally focus on the compromise between expressiveness and dimensionality of our representation.

To evaluate the relevance of our vectorial representation in the context of information retrieval to order graphs based on the number of occurrences of a query graph we have used structural representations of old document images formerly extracted from the platform AGORA (cf. [START_REF] Ramel | AGORA:the Interactive Document Image Analysis Tool of the BVH Project[END_REF]). We intend to build a set of queries with relevant documents to assess details and reminders for the k first documents according to the value of k.

The first experiments have shown that in the case of structural representations with many edges, the extraction of representation required a consequent computation time. The algorithmic optimizations would be realised.

Thanks

The works described in this article were done with the support of the ANR within the project NAVIDOMASS ANR-06-MDCA-12.

Fig. 1 .

 1 Fig. 1. The non-isomorphic graph network

Fig. 2 .

 2 Fig. 2. A simple graph and its vectorial descriptions

Fig. 3 .

 3 Fig. 3. Examples of symbols from the GREC database

Table 1

 1 gives the number of elements in the lexicon depending on the maximum rank of the non-isomorphic graph network.

	Rank Size
	0	1
	1	2
	2	3
	3	6
	4	11
	5	23
	6	51
	7 117
	8 276

Table 1 .

 1 Size of the lexicon depending on the rank of the non-isomorphic graph network

Table 2 .

 2 Summary of the first results

		Lopresti & Wilfong Our
		method	method
	Synthetic	99.45%	99.45%
	graphs
	GREC	51.14%	53.41%