Diego Perez-Galacho

Laurent Bramerie

Charles Baudot

Mohamed Chaibi

Sonia Messaoudène

Nathalie Vulliet

Laurent Vivien

Frederic Boeuf

Christophe Peucheret

Delphine Marris-Morini

Silicon modulators for the generation of advanced modulation formats

Keywords: Silicon modulators, silicon photonics, integrated optics, advanced modulation formats, coherent optical communications

Silicon photonics has appeared in the recent years as the best suited technology for fulfilling the demands of future optical interconnects. In this framework, modulators are key elements in the performance of an optical link. In order to achieve modulation in silicon the Free-Carrier Plasma Dispersion (FCPD) effect is normally used. In fact, silicon modulators based on carrier depletion have been demonstrated with outstanding performance up to 40Gbps. However, keeping up with bandwidth demands will require the use of more complex modulation formats like PAM4 or QPSK. At the same time, to avoid dispersion compensation circuits, the use of the O-Band (1260nm-1360nm) is preferred for short range optical communications. In this work we present our results on the generation of BPSK/QPSK signals using silicon modulators.

INTRODUCTION

Silicon photonics technology has evolved enormously since the first demonstrations of active functionalities until nowadays high-performance transmitters and receivers [START_REF] Boeuf | Silicon Photonics R&D and manufacturing on 300-nm wafer platform[END_REF][START_REF] Dong | Silicon photonic devices and integrated circuits[END_REF]. The use of Si photonics in the long haul network, based on coherent optical communications will set a path for next industrialization of low cost and high performance optoelectronics transceivers [START_REF] Dong | Silicon photonic devices and integrated circuits[END_REF]. Currently, standards are based on 100 Gbps transmission, however, growing bandwidth demands provoked by cloud based applications and multi-media will require new standards based on 200-400 Gbps [START_REF] Witzens | Modulators make efficiency leap[END_REF]. Silicon based state-of-the-art OOK modulators are already reaching the 50 Gbps operation [START_REF] Dong | High-speed low-voltage single-drive push-pull silicon Mach-Zehnder modulators[END_REF][START_REF] Thomson | 50-Gb/s Silicon Optical Modulator[END_REF], nevertheless, scaling to higher bit rates require advanced modulation formats like PAM-n, QPSK or 16-QAM [START_REF] Dong | 112-Gb/s monolithic PDM-QPSK modulator in silicon[END_REF][START_REF] Dong | 224-Gb/s monolithic PDM-16-QAM modulator and receiver based on silicon photonic integrated circuits[END_REF][START_REF] Ding | Silicon 16-QAM optical modulator driven by four binary electrical signals[END_REF][START_REF] Chagnon | Experimental study of 112-Gb/s short reach transmission employing PAM formats and SiP intensity modulator at 1.3µm[END_REF][START_REF] Samani | Experimental parametric study of 128 Gb/s PAM-4 transmission system using a multielectrode silicon photonic Mach Zehnder modulator[END_REF][START_REF] Milivojevic | Small-Size Silicon Photonic IQ Modulator and Low-Power CMOS Driver for Next Generation Coherent Transceiver[END_REF][START_REF] Shastri | Ultra-Low-Power Single-Polarization QAM-16 Generation Without DAC Using a CMOS Photonics Based Segmented Modulator[END_REF]. This was possible because the phase efficiency of the modulators has been significantly improved [START_REF] Hiraki | Heterogeneously integrated III-V/Si MOS capacitor Mach-Zehnder modulator[END_REF][START_REF] Han | Efficient low-loss InGaAsP/Si hybrid MOS optical modulator[END_REF]. Even though the vast majority of these demonstrations have been carried out in C-Band of optical communications (around 1550nm), the use of the of the O-Band (around 1310nm) is normally preferred for short distance intra-data-center communications where silicon photonics based systems are being deployed [START_REF] Pinguet | Monolithically integrated high-speed CMOS photonic transceivers[END_REF]. Therefore, a lot of effort has been put to overcome the lower free carrier dispersion effect at the O-Band compared to the C-Band and high performance devices have been demonstrated, exhibiting low voltage operation or OOK modulation at 50 Gbps [START_REF] Streshinsky | Low power 50 Gb/s silicon traveling wave Mach-Zehnder modulator near 1300nm[END_REF][START_REF] Perez-Galacho | Low voltage 25Gbps silicon Mach-Zehnder modulator in the O-band[END_REF]. However, even higher bit rates will be required as the data exchanged inside data centers is continuously growing. For that reason, the development of higher modulation formats in the O-Band has been receiving increasing attention in the last years [START_REF] Xiong | Monolithic 56Gb/s silicon photonic pulse-amplitude modulation transmitter[END_REF][START_REF] Chagnon | Experimental study of 112-Gb/s short reach transmission employing PAM formats and SiP intensity modulator at 1.3µm[END_REF]. PAM-8 at 112 Gbps was demonstrated [START_REF] Chagnon | Experimental study of 112-Gb/s short reach transmission employing PAM formats and SiP intensity modulator at 1.3µm[END_REF], however it is noticeable that QPSK modulator based on encoding data both in amplitude and phase has not been reported up to now in the O-Band.

The generation of QPSK signals is normally carried out using standard IQ modulators based on nested Mach-Zehnder Modulators [START_REF] Dong | 112-Gb/s monolithic PDM-QPSK modulator in silicon[END_REF], however a single dual-drive Mach-Zehnder modulator (DD-MZM) can be employed as a simpler way to generate it, reducing the power consumption of the transceiver [START_REF] Doerr | Silicon Photonics Coherent Modulator/Receiver[END_REF]. This approach was fist demonstrated using LiNbO3 a modulator [START_REF] Ho | Generation of Arbitrary Quadrature Signals Using One Dual-Drive Modulator[END_REF]. This approach offers key advantages for short distance intra data center communications like good power efficiency and scalability. In this work we report the first demonstration of QPSK signal generation using DD-MZM in silicon working in the O-Band. Operation at 20 Gbps is demonstrated with potential to scale data rate and spectral efficiency.

MODULATOR DESIGN

The silicon modulator designed was based on carrier depletion. We used phase shifters based on a PN diode embedded in the core of silicon-on-insulator (SOI) waveguide. In Fig. 1 (a) and (b) the schematic of the cross section and its SEM image are shown. The used phase shifter was based on a previously reported work demonstrating high modulation efficiency with VπLπ products of 0.95 to 1.15 Vcm for reverse bias from 1 to 4 V at 1310 nm wavelength [START_REF] Perez-Galacho | Low voltage 25Gbps silicon Mach-Zehnder modulator in the O-band[END_REF]. The schematic of the DD-MZM is shown in Fig. 1 (c). A symmetric Mach-Zehnder structure is sued with 2 mm long phase-shifters embedded in both arms. MMI couplers implement the input/output splitter and combiner. The biasing of the interferometer is carried out by tuning the DC phase shift Φ between both arms (see Fig. 1 (c)). This DC phase shift is actually implemented by metallic heaters that act as low-speed/high-efficient phase shifter, as shown in Fig. 1(d). The modulator was fabricated on the 300-mm CMOS DAPHNE technological platform of STMicroelectronics [START_REF] Baudot | Daphne silicon photonics technological platform for research and development on wdm applications[END_REF]. RF signals can be applied independently to each phase shifter by means of GSGSG coplanar traveling wave electrodes.

MEASUREMENTS RESULTS

Firstly the DD-MZM was characterized in DC. The obtained fiber-to-fiber transmission was 17 dB, this includes grating coupler loss, on-chip passive propagation loss and modulator insertion loss (IL). Normalizing by an onchip straight waveguide of similar length, the IL of the modulator was calculated to be 3.8 dB. The measured Vπ of each phase shifter was between 6 V and 7V, considering the 2 mm active length of the modulator, the deduced modulation efficiency is between 1.2 Vcm and 1.4 Vcm. The small signal electro-optical 6-dB bandwidth of the modulator was measured around 15 GHz. QPSK operation at 10 Gbaud was then targeted.

Using the aforementioned setup high-speed measurements were performed on the DD-MZM. The bit error rate (BER) was measured as a function of the signal average received power, the resulting curve is shown in Fig. 3 (a). Five BER measurements were carried out for each received power point, therefore each point on Fig. 3 (a) is the result of averaging five measurements of 10 5 transmitted symbols each. Considering 10 -3 as the limit in BER for error free transmission based on forward error correction, the required received power is -20dBm. The received constellation diagram after digital signal processing (DSP) performed offline can be seen in Fig. 3 (b), this constellation corresponds to a received power of -22 dBm. It can be observed a clear QPSK constellation, the corresponding error vector magnitude (EVM) for this constellation is 33%.

Figure 1 .

 1 Figure 1. Cross section of the silicon phase-shifter: (a) schematic and (b) SEM image. Architecture of a DD-MZM: (c) schematic and (d) actual layout.

Figure 2 .

 2 Figure 2. Experimental setup employed for QPSK signal characterization.

Figure 3 . 3

 33 Figure 3. 3 BER as a function of the received power (a) and measured constellation diagram for a received power of -22dBm (b).

ACKNOWLEDGEMENTS

This work was supported by the European projects Plat4m (FP7-2012-318178), Cosmicc (H2020-ICT-27-2015-688516) and BlueSpace (H2020-ICT-2016-2-762055). We acknowledge the support of French Industry Ministry/DGE through the Nano2017 program.


Sergio Peignier

Christophe Rigotti

Anthony Rossi

Guillaume Beslon

Proclus Inscy

Proclus * Subcmedians

Weight-based search to find clusters around medians in subspaces

Keywords:

There exist several clustering paradigms, leading to different techniques that are complementary in the analyst toolbox, each having its own merits and interests. Among these techniques, the K-medians approach is recognized as being robust to noise and outliers, and is an important optimization task with many different applications (e.g., facility location). In the context of subspace clustering, several paradigms have been investigated (e.g., centroid-based, cell-based), while the median-based approach has received less attention. Moreover, using standard subspace clustering outputs (e.g., centroids, medoids) there is no straightforward procedure to compute the cluster membership that optimizes the dispersion around medians. This paper advocates for the use of median-based subspace clustering as a complementary tool. Indeed, it shows that such an approach exhibits satisfactory quality clusters when compared to well-established paradigms, while medians have still their own interests depending on the user application (robustness to noise/outliers and location optimality). This paper shows that a weight-based hill climbing algorithm using a stochastic local exploration step can be sufficient to produce the clusters.

Introduction

Clustering is a data mining task that aims to group objects sharing similar characteristics over the whole data space. There exist various clustering algorithms relying on different similarity measures and paradigms. They provide complementary tools to the analyst, each having its own merits and interests. Among the major categories, clustering-oriented approaches [START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF] group objects mainly using distance-based similarities and tend to build center-based hyperspherical shaped clusters. For example the very well known K-means algorithm relies on the Euclidean distance and produces clusters around centroids. Other techniques known as the K-medians approaches [START_REF] Har-Peled | Smaller coresets for K-median and K-means clustering[END_REF], use the Manhattan distance to group data objects around medians that are less sensitive to unusual and extreme values and more robust to noise and outliers [START_REF] Maronna | Robust statistics[END_REF]. Moreover according to [START_REF] Aggarwal | On the surprising behavior of distance metrics in high dimensional space[END_REF] the use of the Manhattan distance should be preferred for high dimensional data mining applications, since this metric is less impacted by the problem known as the curse of dimensionality. Beside these interesting properties, the K-medians problem is an important optimization task with many different applications.

Given a set of objects in a D-dimensional space, K-medians clustering aims to partition the given objects into K clusters so as to minimize the sum of the Manhattan distances between each object and the median of its cluster [START_REF] Har-Peled | Smaller coresets for K-median and K-means clustering[END_REF]. This technique has been applied for instance to facility locations (e.g., finding optimal location for resource storage). K-medians have also been used to clusterize histograms and then retrieve consensus histograms [START_REF] Lim | Using positional distribution to identify splicing elements and predict pre-mrna processing defects in human genes[END_REF]. More recently K-medians have also been used for data allocation in communication networks [START_REF] Sen | Exact approaches for static data segment allocation problem in an information network[END_REF].

Various concepts have been investigated in the subspace clustering community. However despite their importance, medians seem to have received less attention than other clustering paradigms. Literature reviews (e.g., [START_REF] Kriegel | Subspace clustering[END_REF][START_REF] Parsons | Subspace clustering for high dimensional data: A review[END_REF]) do not report subspace clustering algorithms based on medians and such an approach has not been investigated in more recent works either (e.g., [START_REF] Wang | Dp-space: Bayesian nonparametric subspace clustering with small-variance asymptotics[END_REF][START_REF] Liu | An efficient matrix factorization based low-rank representation for subspace clustering[END_REF]). In addition, even if various subspace clustering techniques have been developed to build groups of objects around centroids or medoids, there is no straitforward procedure to use these groups to compute cluster memberships that optimize the dispersion around medians.

The main contribution of this paper is to show that a pure median-based subspace clustering exhibits satisfactory clusters when compared to well-established paradigms (using the evaluation framework of [START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF]). This advocates for its use as a complementary tool in the family of the subspace clustering approaches, since medians have their own interests depending on the user application, notably their robustness to noise/outliers and their inherent location optimality (e.g., for facility location).

This paper shows that even an easy to implement strategy is promising to find such subspace clusters. Indeed a simple hill climbing algorithm based on stochastic local exploration steps can be used to produce the clusters. As many algorithms that aim at producing hyper spherical clusters (or subspace clusters) by minimizing dispersion (e.g., K-means, PROCLUS [START_REF] Aggarwal | Fast algorithms for projected clustering[END_REF]), the algorithm presented here, can be stuck in local minima and different clusterings can be obtained for different executions (due to some stochastic steps). So, as for the other algorithms, the one presented in this paper needs to be launched several times.

The presented algorithm relies on three key hints: 1) New guesses for candidate median locations can be obtained directly from the data objects themselves.

2) The algorithm uses a weight-based strategy to guide its local search towards promising subspace clusters. 3) In order the guide the search and build the candidate median locations, it turns out that using a dynamic sample of the dataset is sufficient. This allows thus to reduce the amount of data to handle at each iteration, while the appropriateness of sampling based strategies remains an open question for many subspace clustering approaches.

Related works

Median-based clustering

The K-medians problem (e.g., [START_REF] Har-Peled | Smaller coresets for K-median and K-means clustering[END_REF]) is a well defined and NP-hard problem that is a research topic of interest for both the computational geometry and the clustering communities. This problem has been studied in the computational geometry domain with the aim to find optimal locations for centers and facilities in order to minimize costs. We refer the reader to [START_REF] Jamshidi | Median location problem[END_REF] for examples of real world applications of K-medians. On the other hand the clustering community studied the K-medians problem in order to develop techniques to find clusters that are robust to noise and outliers. The K-medians clustering and facility location tasks have been investigated from the perspective of combinatorial optimization, approximation algorithms, worst-case and probabilistic analysis (e.g., [START_REF] Jain | Approximation algorithms for metric facility location and K-median problems using the primal-dual schema and lagrangian relaxation[END_REF]). However, locating centers having optimal locations or partitioning the objects of the dataset to form center-based clusters are two different ways to see the same problem.

Subspace clustering

The purpose of subspace clustering is not only to partition a dataset into groups of similar objects, this technique also aims to detect the subspaces where similarities occur. Therefore each cluster is associated to a particular subspace. Many approaches have been investigated for subspace clustering in the literature using various clustering paradigms. The reader is referred for instance to [START_REF] Kriegel | Clustering high-dimensional data: A survey on subspace clustering, pattern-based clustering, and correlation clustering[END_REF][START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF][START_REF] Parsons | Subspace clustering for high dimensional data: A review[END_REF] for detailed reviews and comparisons of the methods, including the main categories: Cell-based, density based, clustering-oriented approaches and also pattern-based clustering or biclustering approaches (e.g., [START_REF] Sim | A survey on enhanced subspace clustering[END_REF]).

A subspace clustering technique based on medians belongs to the family of clustering-oriented approaches. These approaches are based on parameters specifying properties of the targeted clustering such as the expected number of clusters or the cluster average dimensionality. According to these constraints, the objects are grouped together mainly using distance-based similarities. Most of these methods tend to build hyper-spherical shaped clusters around centers (e.g., centroids, medoids). No subspace clustering technique based on medians, as the one presented in this paper, has been reported in relevant reviews, e.g., [START_REF] Kriegel | Clustering high-dimensional data: A survey on subspace clustering, pattern-based clustering, and correlation clustering[END_REF][START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF] nor in recent subspace clustering proposals, e.g., [START_REF] Wang | Dp-space: Bayesian nonparametric subspace clustering with small-variance asymptotics[END_REF][START_REF] Liu | An efficient matrix factorization based low-rank representation for subspace clustering[END_REF].

Problem statement

This section recalls some preliminary definitions and specifies the task considered in the paper.

Dataset and preprocessing

Let a set of objects S = {s 1 , s 2 . . . } denote a dataset. Each object in S has a unique identifier and is described in R D by D features (the coordinates of the object). Let D denote the number of dimensions (i.e., the dimensionality) of S. Each dimension is represented by a number from 1 to D and the set of all dimensions of the dataset is denoted D = {1, . . . , D}.

To avoid being impacted by the original offsets and scales of the features, we suppose that the data have been standardized, as in many clustering frameworks. We rely here on the usual z-score standardization, leading to a mean of zero and a standard deviation equal to one for each feature.

K-medians problem

Given a dataset S in a space D, let H = {m 1 , . . . , m k } be a non-empty set of centers where each center m ∈ H is an element in R D . The Manhattan (L 1 ) distance between two objects u and v in space D is defined as ||u,

v|| 1 = d∈D |u d -v d |.
The Manhattan distance between an object s and its closest center defines the so-called Absolute Error associated to s for H: AE(s, H) = min m∈H (||s, m|| 1 ). The K-medians problem can be formulated as the optimization problem that aims to find a set H of K centers that minimizes the Sum of Absolute Errors of the objects in S defined as SAE(S, H) = s∈S AE(s, H). Such a set H defines a partition of S into K clusters C = {C 1 , . . . , C K }, where a cluster C i contains the objects of S for which m i ∈ H is the closest center (using the Manhattan distance).

Subspace clustering based on medians

A subspace clustering M, called hereafter a model , is a set of centers where each center m i ∈ M is associated to a subspace D i of D. From the point of view of center-based subspace clustering, a cluster center described in a given subspace can be perceived informally as a summary of the cluster objects. Indeed this set of objects can be represented in a more abstract way simply by the location of the center along the dimensions considered in the cluster subspace. For a dimension d that is not in D i , the intended meaning is that, along d, the objects of the cluster follow the same distribution as the other objects of the dataset. For an object s, the Absolute Error is then AE(s, M) = min m∈M dist(s, m), where dist(s, m

i ) = d∈Di |s d -m i,d | + d∈D\Di |s d -µ d |, with m i,d the coordinate of m i in dimension d,
and with µ d the mean of the location of all objects in S along d. Notice that, since the dataset is supposed to be normalized using a z-score, then µ d = 0 for all d.

The SAE is still defined as SAE(S, M) = s∈S AE(s, M). Each object is associated to the cluster C i such that dist(s, m i ) is minimized. If several clusters minimize this expression then the object is non-deterministically associated to one of them. Finally, the size of a model M, noted Size(M), is defined as the sum of the dimensionalities of all subspaces associated to the centers in M, and is interpreted as the level of detail captured by the clustering. To perform such a median-based subspace clustering, the core task considered in this paper is then to find a set of centers M that minimizes the SAE and such that Size(M) ≤ SD max , where SD max is a parameter denoting the maximum Sum of Dimensions used in M to define all the subspaces.

Algorithm

This section introduces the SubCMedians algorithm to handle the mediansbased subspace clustering task.

General hill climbing procedure

Let S be a dataset and M a model (a set of centers each being defined in its own subspace). The algorithm presented in this paper is a hill climbing oriented technique that aims to minimize the objective function SAE(S, M). It updates iteratively a model using a stochastic optimization approach, while keeping the maximum model size constraint satisfied.

The hill climbing process can be perceived as a local search process on a graph of models. Each vertex M in the graph is a model such that Size(M) ≤ SD max and there is an edge from M to a vertex M if M ∈ N eighbors(M), where N eighbors(M) is a function that defines the set of neighbors of M.

The algorithm takes as initial vertex the empty model (a model containing no center), denoted M ∅ , and for which the definition of AE is extended as follows: AE(s, M ∅ ) = d∈D |s d -µ d |, all µ d being still equal to 0 due to the dataset standardization.

At each iteration the algorithm evaluates the SAE for a random neighbor of the current vertex, whenever the SAE associated to the new node is smaller or equal to the current SAE, the algorithm moves towards the neighbor. The algorithm uses the data objects themselves to generate the neighborhood of a model M. Indeed, a neighbor of a model M is a model that can be obtained from M by inserting/removing a dimension in a subspace, and setting a center coordinate to a value equal to a coordinate of an existing object. The neighbors generation is fully described in Section 5.2.

Sampling the dataset

An advantage of a median based subspace clustering is that the location of the median can be estimated using a sample. This is the case for other approaches (for example centroid based ones), but remains an open question for subspace clustering techniques in general. Let X be a continuous random variable with a density function f (x) and a median θ. The median of a sample of n independent realizations of X is an estimator (noted θ) of the median of X and is normally distributed around θ with a standard deviation σ θ = 1: function SubCMedians(S,SD max ,N ,N bIter)

2:

S ← {s 1 , . . . , s N } uniformly drawn from S without replacement samples. Let us suppose that X follows a Gaussian distribution X ∼ N (µ, σ), where µ and σ denote respectively the mean and standard deviation of X. The density function of the distribution is f

(x) = 1 σ √ 2π e -1 2 ( x-µ σ ) 2 .
Since the mean and the median of a Gaussian distribution are equal, f (θ) simplifies to f (θ) = 1 σ √ 2π , and we have σ θ = σ π 2n . So θ ∼ N (µ, σ π 2n ), and thus a subspace clustering algorithm based on medians does not require to use the entire dataset. Indeed, a dataset sample S ⊆ S, should allow the algorithm to build a model without important degradation of the clustering quality, while reducing the amount of data to handle. This choice is retained in SubCMedians, but to limit the negative effects of a possible bad sample choice, the algorithm will modify dynamically the sample along the iterations.

Lazy hill climbing procedure

The algorithm is given in Figure 1. It takes as input a dataset S described in a space D and three parameters: the maximum model size SD max , the sample size N and the number of iterations N bIter. The setting of these parameters is presented in Section 6.3 (technical details provided in Appendix A.3). The first step of the algorithm is to initialize the model M, the sample S (N objects randomly chosen in S) and to compute the error err corresponding to M.

At each iteration, a data object picked at random in S is replaced by an object uniformly drawn from S\ S in order to change dynamically the sample. Then (lines 10 and 11) the SAE err * on the new sample is computed incrementally by substracting the AE associated to the object that has been removed and adding the AE for the new object.

Next, the algorithm performs a lazy hill climbing step. Indeed, if the SAE on the new sample is better (i.e., lesser) than the SAE on the previous sample the algorithm does not try to improve the model itself during this iteration. Otherwise a new model M is computed using the function One-Neighbor() (detailed in the next section) and M is retained if it improves the SAE.

Finally, the algorithm outputs a subspace clustering in the form of a set of disjoint clusters and their corresponding subspaces using a call to function BuildSubspaceClusters(). This function is very simple and not detailed further, it simply associates each data object to its closest center (the one minimizing AE). If several centers give the same minimal AE, then one is chosen in a nondeterministic way. At the end, if a center has no associated object then it does not lead to a cluster and BuildSubspaceClusters() discards it.

Neighborhood exploration heuristic

The local exploration can be guided by the expected gain in SAE associated to the optimization of the location of a given center. Intuitively adjusting the center of a cluster containing many objects and having high dispersion is likely to have a higher effect on the the SAE (see Appendix A.1 for technical details).

Weighted candidate model

Since the clusters and their standard deviations are not known beforehand, SubCMedians uses two heuristics to favor some of the centers that could be most promising. The first one is to guide the local exploration by modifying the current model with a coordinate of a uniformly chosen object in the sample. Therefore coordinates drawn from clusters with more objects in the sample are more likely to be used for exploration.

The second heuristic to favor promising centers consists in counting for each dimension of each center the number of adjustments that have led to a reduction of the SAE. The algorithm keeps track of weights reflecting these counts. The weight of a center (sum of the weights of its dimensions) is then used as an evidence to encourage further the improvement of its location. In the optimization process the weights should not only increase, since when a promising center has already been optimized sufficiently it is then likely to lead to minor gains, and then should receive less attention. The weights of the dimensions in the clusters are thus decreased during the exploration, using a random selection with a probability proportional to the weights. A weight of zero for a dimension in a cluster is an evidence that it is not important to keep or adjust it, and thus that it should not be retained to form the subspace associated to this cluster. A non-zero weight is then interpreted as denoting a dimension being potentially meaningful for that cluster. To permit to encode a model of size SD max , but no more, the maximum sum of all weights is set to SD max .

In SubCMedians, a candidate model M is defined as a pair of matrices L, W . In the algorithm given in Figure 1, the model M = L, W is initialized line 3 by filling all rows of the two matrices with zeros, to represent an initial empty model. The heuristic based neighborhood exploration is performed by the successive calls to function One-Neighbor() detailed in the next section.

L = 1 2               0.5 0 1 0 -0.8 2 0 0 3 0 0 4 -0.3 0.2 5 0 0 6 W = 1 2               2 0 1 0 1 2 0 0 3 0 0

One neighbor computation function

The function One-Neighbor() is given in Figure 2. First, it computes ω the total current model weight. Then operations carried out from lines 4 to 10 decrease the model weight when the total weight reaches the maximum model size (i.e., SD max ). This is performed by picking at random a pair of indices i, j with a probability proportional to W i,j (line 5). Then the corresponding weight W i,j is decreased (line 6). For the sake of clarity the associated coordinate L i,j is set to zero if W i,j = 0 (line 8), even though this is not useful for the rest of the process. Next, the algorithm draws uniformly an object s in the sample and a dimension d in the space D (lines 11 and 12). Line 13 computes the set Γ of the indices of the valid centers. Then the algorithm chooses a random center index c that corresponds either to an unused center with probability 1 ω (lines

1: function One-Neighbor( L, W , S, SD max ) 2: L , W ← L, W 3: ω ← SDmax i=1 D j=1 W i,j 4:
if ω = SD max then 5:

Draw i, j ∈ {1, . . . , SD max } × {1, . . . , D} with probability of each i, j equals to

W i,j ω 6: W i,j ← W i,j -1 7:
if W i,j = 0 then 8:

L i,j ← 0 9:
end if 15 and 16), or one of the current valid centers (line 18). In the latter case, the valid center is picked with a probability proportional to its total weight. Finally the weight W c,d is increased and the location encoded in L c,d is replaced by the coordinate of s along dimension d.

Complexity

Consider one iteration of SubCMedians using sample S and let N bCenters denote the number of centers currently used (the valid centers). It can be easily derived (see Appendix A.2) that the complexity of an iteration in SubCMedians is then O(| S| × N bCenters × D) and its memory requirement is simply O(D × (| S| + SD max )).

6 Experimental Setup

Experimental protocol

The SubCMedians algorithm extends the subspace clustering tool family towards medians based clustering. Even if cluster center locations based on medians can be interesting on their own (depending on the targeted task), an open question is to what extent the clusters obtained make sense with respect to those given by other paradigms? We used the evaluation framework of reference designed for subspace clustering described in [START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF] that reports the results obtained by well-established approaches for different evaluation measures, on both real and synthetic datasets. The method presented in [START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF] relies on a broad exploration of the parameter space for each algorithm in order to find the best parameter setting on each data set and then compare the best results obtained by the different methods (see Appendix A.4). However such parameter tuning is most of the time a difficult task and these high quality subspace clustering models are likely to be difficult to obtain. For SubCMedians, for each dataset, a single parameter setting was used based on a default setting presented in Section 6.3. Since SubCMedians is nondeterministic (as many subspace clustering approaches), it can achieve different results on different runs. Consequently the algorithm was executed 10 times independently using the same parameter setting. The results obtained after each run were assessed with the same criteria as in [START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF]: the coverage, the number of clusters found, the average cluster dimensionality and different quality measures (F 1 , accuracy, CE, RN IA and entropy).

All experiments were run on an Intel 2.67GHz CPU running Linux Debian 8.3, using a single core and less than 150 MB of RAM. The SubCMedians algorithm has been implemented in C++ (as a Python library) and is available upon request.

Datasets

The performances of SubCMedians are reported on real world data using the seven benchmark datasets selected in [START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF] for their representativity: breast, diabetes, liver, glass, shape, pendigits and vowel (most of them coming from the UCI archive [START_REF] Bache | UCI machine learning repository[END_REF]). These datasets have different dimensionalities and contain different numbers of objects. These objects are already structured in classes, and the class membership is used by quality measures to assess the cluster purity. However, the number of classes does not necessarily reflect the number of subspace clusters, and the objects of a class can form different groups in space and/or strongly overlap with the objects of other classes.

SubCMedians was also executed on the 16 synthetic benchmark datasets provided by [START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF]. These datasets are particularly useful to study the algorithm performances, as the true clusters and their subspaces are known. Each dataset contains 10 hidden subspace clusters laying in subspaces made by 50%, 60% and 80% of the total dimensions of the dataset. Seven synthetic datasets allow to study scalability with respect to the dataset dimensionality [START_REF] Jain | Approximation algorithms for metric facility location and K-median problems using the primal-dual schema and lagrangian relaxation[END_REF][START_REF] Liu | An efficient matrix factorization based low-rank representation for subspace clustering[END_REF][START_REF] Sen | Exact approaches for static data segment allocation problem in an information network[END_REF]20,25, 50 and 75 dimensions). These datasets contain about 1500 objects each and are extended with about 10% of noise objects. Five other synthetic datasets permit to analyse the scalability with respect to the dataset size (1500, 2500, 3500, 4500 and 5500 objects), over 20 dimensions, also with about 10% of noise objects. Finally four datasets allow to study the capacity to cope with noise, containing 10%, 30%, 50% and up to 70% of noise objects.

All datasets are made available by the authors of [START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF] at http://dme.rwthaachen.de/openSubspace/evaluation. We applied a z-score standardization to all real and synthetic datasets in a preprocessing step.

Parameter values

The SubCMedians algorithm has three parameters: SD max , N bIter, and N . The most important is SD max , the maximum model size, constraining the level of detail of the subspace clustering performed. The number of iterations N bIter is also important but it should be noticed that its setting could be avoided since the user could monitor the value of the SAE during the clustering and stop the process when this value does no longer improve. The third one, the sample size N is a way to reduce the computing resources needed, and of course if possible it makes sense to use the full dataset instead of a sample.

In this section, we provide guidelines for easy default parameter setting. In this context, the user only needs to provide an expected or suggested number of clusters N bExpClust. Let D denote the dimensionality of each particular dataset. The default setting is SD max = N bExpClust × D, N bIter = 10 × SD max × N bExpClust and N = 25 × N bExpClust (see Appendix A.3 for justification and technical details). For the synthetic datasets the number of expected clusters is about 10, thus the maximum model size was set to SD max = D × 10, the sample size was set to N = 25 × 10 and the number of iterations was set to N bIter = 10 × 10 × SD max . A weaker setting, not based on the true number of clusters, but based on 20 expected clusters, was also used, and as reported in Section 7 still permitted to exhibit structures of about 10 clusters. For the real world datasets, the only information available about the structure of the datasets is the number of classes. However, as already mentioned, the number of classes may not correspond to the number of clusters. Indeed, according to the results provided by [START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF], in these datasets the state-of-the-art algorithms exhibit most of the time structures composed of more clusters than the number of classes. The setting of SubCMedians parameters is thus based on an expected number of clusters equal to three times the number of classes and we let the algorithm regulate itself the number of output clusters. Hence the maximum model size was set to SD max = 3 × N bClasses × D, the sample size was set to N = 25 × 3 × N bClasses and the number of iterations was set to N bIter = 10 × 3 × N bClasses × SD max .

Evaluation measures

In order to compare our algorithm to the others, we used the same standard evaluation measures for clusters and subspace clusters as in [START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF]: entropy (the normalized entropy), accuracy, F 1, RN IA and CE. We performed also the same simple transformation on entropy and RN IA, by computing RN IA = 1-RN IA and entropy = 1 -entropy to have all evaluation measures ranging from 0 (low quality) to 1 (high quality). The three first measures (entropy, accuracy and F 1) reflect how well objects that should have been grouped together were effectively grouped. The two last measures (RN IA and CE) take into account the way the objects are grouped and also the relevance of the subspaces found by the algorithm. For these measures, when the true dimensions of the subspace clusters were not known (for real datasets), then as in [START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF] all dimensions were considered as relevant, but then the interpretation of these two measures should remain cautious since the true sets of dimensions are likely to be smaller. Of course this does not apply to the synthetic datasets, since for them the reference clusters and their dimensions are known. We refer the reader to [START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF] for the detailed recall of the evaluation measures.

Experimental Results

Because of the large number of results (23 datasets and 11 algorithms) used in the comparison, aggregated figures reflecting the real detailed results are given. However, there is no ever winning paradigm or clustering method, each having its own advantages or interest.

Real dataset

This section presents the results obtained on the 7 representative real datasets selected in [START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF]. In order to assess if SubCMedians produced decent results with respect to well-established methods, we ranked the different methods with respect to their quality measures, their coverage (fraction of objects of the dataset that were grouped into clusters) and the number of clusters they produced (see Appendix A.5 for a detailed presentation of this procedure).

The average rank of each algorithm regarding the cluster quality measures, the coverage and the number of clusters found are given in Figure 3 (highest ranks meaning best results). In addition, two tables representative of the results at a more detailed level are presented in Figure 4. These tables report on two of the real world datasets the values for the coverage, the number of clusters found, their average dimensionality and the runtimes. Runtimes are given only as complementary information since for SubCMedians they were obtained on a computer (2.67GHz CPU) different from the one used by [START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF] (2.3GHz CPU). At the bottom of these tables, we grouped the results obtained by methods belonging to the same family as SubCMedians (clustering-oriented techniques), results for the other algorithms are provided for the sake of completeness.

Figures 3 and4 show evidence that the robustness of the medians still operates in this subspace clustering task since competitive cluster qualities can be obtained without discarding any object (100% coverage). In all experiments SubCMedians was run using the default parameter setting. For the number of clusters found, SubCMedians is above the average, and it seems that it does not tend to split the dataset into too many clusters. However, the true numbers of clusters are not known here, in contrast to the synthetic datasets.

Synthetic data

In this section, we report the results obtained on the 16 synthetic datasets of [START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF], each one containing 10 known clusters. For each dataset, SubCMedians was executed 10 times and the model having the lowest SAE was retained (no use of external labeling). These models are depicted as red circles in Figure 7 (blue triangles correspond to models obtained with an unweighted version of SubCMedians discussed here after). The green shapes represent the areas where are located the best models found by the 10 other algorithms over their parameter spaces (optimized using external ground truth labeling). Here again, the results show evidences that a median based approach is an interesting complementary tool for subspace clustering, and in particular that SubCMedians reaches a competitive quality for the measures that take into account not only the objects grouping, but also the dimensions associated to the clusters (RN IA and CE). Runtimes as functions of the size of the sample and the dimensionality of the dataset are provided in Figure 6. In these experiments the parameters where set according to the guidelines of Section 6. of clusters of 10, but no constraint on the sizes of their subspaces. Interestingly, a weaker setting based on an expected number of clusters of 20 still permitted to SubCMedians to exhibit most of the time a good quality clustering of about 10 clusters (not shown, very similar to Figure 7). Figure 5 illustrates the clustering quality in terms of RN IA for increasing percentages of noise points in the dataset (respectively 10, 30, 50 and 70% of the data points were noise points). Even if the quality of the subspace clusters obtained tends to decrease when the amount of noise in the dataset increases, the degradation is not severe. Here again, this seems to indicates that the robustness to noise of the medians still operates in a subspace clustering task.

In order to assess the impact of the weighted neighborhood exploration of the model space used by SubCMedians, the algorithm was compared to an unweighted version. In this version, the candidate center undergoing the modification is uniformly drawn by modifying line 18 in Figure 2, and in the same figure line 20 is replaced by W c,d ← 1 to have weight matrices that contain simply a 1 for a dimension that is used and a 0 otherwise.

The results of the more naïve unweighted version of SubCMedians are represented in Figure 7 by blue triangles (same procedure used, retaining also the lowest SAE over 10 runs). The unweighted-SubCMedians outputted slightly more clusters than expected, and has another more important drawback, that is the lower quality obtained with respect to the dimensions found (RN IA and CE graphics). As targeted by the design of the neighborhood exploration in Section 5, the weighted strategy of SubCMedians could focus on more promising clusters while unweighted-SubCMedians produced more (useless) candidate centers (Figure 8) and failed to develop sufficiently the center dimensionalities when the hidden cluster dimensionalities increased (Figure 9). Moreover, SubCMedians turned out to be slightly faster (see Figure 6), and unweighted-SubCMedians suffered from a small overhead likely to be caused by its handling of more candidate centers in the models.

Conclusion

In this paper we presented SubCMedians, a median-based subspace clustering method, and assessed it on real and synthetic benchmark datasets, using the evaluation framework of [START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF]. These results showed that a median-based subspace clustering approach can exhibit satisfactory results when compared to well-established subspace clustering paradigms, and is thus a good candidate as a complementary tool, in particular for users interested by the properties of medians themselves (facility location, robustness to noise and outliers). We also proposed some guidelines for easy default parameter setting. These guidelines were effective when dealing with all the datasets of the benchmark. Since the median-based subspace clusters seem to be obtained in rather short runtimes, promising future work includes the use of these clusters as initial guesses to guide other techniques that could be more time consuming.

A Appendix

A.1 Expected gain in SAE to guide local exploration ). This means that larger gains are likely to be obtained for clusters having a high σ d and having many of their elements belonging to the sample S.

A.2 Complexity

Consider one iteration of SubCMedians using sample S in a D dimensional space. Let N bCenters denote the number of centers currently used (the valid centers). Operations in non-constant time are the calls to AE, SAE and One-Neighbor(). AE computes the distance of one object to each center and is in O(N bCenters × D). SAE does the same for each object in the sample and then has a complexity O(| S| × N bCenters × D). The computation cost of One-Neighbor() lies in part in the computation of weights: the total weight of the model ω (line 3) and the weights in the probabilities used line 18. These values can be maintained incrementally when W is modified resulting in a constant cost for ω and in a cost proportional to N bCenters for the probabilities line 18. The remaining cost is due to the non-uniform random selections (lines 5 and 18), having a cost proportional to the number of possible outcomes. Line 5 there are at most N bCenters × D possible outcomes with a non-zero probability (other pairs i, j having a weight of zero). And for line 18 there are N bCenters possible outcomes. The cost of one call to One-Neighbor() is thus in O(N bCenters × D). The complexity of an iteration in SubCMedians is then O(| S| × N bCenters × D).

The memory requirement of one iteration of SubCMedians corresponds to the storage of the sample S and the two matrices L and W of size SD max × D and thus is simply in O(| S| × D + SD max × D).

A.3 Parameter Setting

The easy default parameter setting (for preliminary exploration of the data) requires to provide only one value: the expected number of clusters N bExpClust. Notice that this is not a crisp constraint, but only a suggested number of clusters that the algorithm should adjust to build a structure. Notice also that a hard part of the subspace clustering task is to determine the subspaces and that this aspect is not directly constrained by N bExpClust.

Maximum model size SD max The intuition to set SD max is very simple, the value of SD max should allow to build a model containing N bExpClust even if all dimensions are useful, leading to a default SD max value equal to N bExpClust × D. Of course, as for any subspace clustering algorithm, obtaining very satisfactory results are likely to require from the user finer parameter tuning.

From N bExpClust and SD max we now derive minimum recommended values for the number of iterations and for the sample size. These settings are the ones used in the experiments reported Section 7, but of course the statistical thresholds used in the setting method could be enforced in order to have more conservative recommended parameter values.

Number of iterations N bIter

Let C be any expected cluster and d be any of its dimensions. Let k be the number of attempts to set the coordinate of the center of C along d to a reasonable approximation of the median value, during N bIter iterations in SubCMedians. The default value proposed for N bIter is the minimum number of iterations such that the expected value of k is at least 1.

Let us suppose that all clusters have the same size and that the number of clusters is equal to N bExpClust. Consider an iteration of SubCMedians. In One-Neighbor() (Figure 2) the probability to pick an object s belonging to C (line 11) is 1/N bExpClust and the probability to choose dimension d (line 12) is 1/D. Let x be the coordinate of s along dimension d, and let us accept as a reasonable approximation a value x at a distance of less than 1/8 of the standard deviation away from the median. Then, supposing a Gaussian distribution, this implies that the median is equal to the mean, and that the probability of x as being a reasonable approximation is about 0.1 (according to the standard normal cumulative distribution). At line 15, the probability to jump to line 18 to modify an existing cluster is 1 -1/ω. If we suppose that the current model contains already N bExpClust clusters, including C (possibly with the presence of a single dimension of C), and that all clusters have similar weights in matrix W, then the probability of C to be chosen in line 18 is about 1/N bExpClust. So the probability p of the center corresponding to C in the current model, to have its coordinate along dimension d to be set to a reasonable approximation x in line 21, is p =

1 N bExpClust × 1 D × 0.1 × (1 -1 ω ) × 1 N bExpClust .
As ω increases at each iteration (up to SD max ) we quickly have (1 -

A.4 Evaluation framework

The evaluation framework of [START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF] relies on a systematic approach to compare the results of representative algorithms that address the major subspace clustering paradigms. The comparison detailed in [START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF] was made using different evaluation measures on both real and synthetic datasets, using the following method. Given that each algorithm requires several parameters (from 2 to 9), for each dataset, the algorithms were executed with 100 different parameter settings to explore the parameter space. Then, using an external labeling of the objects, only the outputs that were among the best with respect to the external labeling (taken as a ground truth) were retained. So, the results reported in [START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF] are in some sense the best possible subspace clusterings that could be achieved if we were able to find the most appropriate parameter values. More precisely, for each real world dataset only two outputs were retained: 1) the one computed for the parameter setting that maximizes the F 1 measure, and 2) the one obtained when maximizing the accuracy. These two outputs led to two values for each measure, the smallest of the two being called bestMin and the other bestMax. For each synthetic dataset, all the settings maximizing at least one quality measures among F 1 , accuracy, CE, RN IA and entropy were retained. bestMin and bestMax are reported as min and max in Figure 4.

Since generally no external labeling is available when we search for clusters, parameter tuning is most of the time a difficult task and these high quality subspace clustering models are likely to be hard to obtain. Instead, for SubCMedians, the parameters were not optimized using any external criteria and were set to the default values suggested in Section A.3. For each real world dataset, the highest and lowest values of each evaluation measure over 10 runs were computed, so as to compare them to the bestMax and bestMin values retained by the evaluation method of [START_REF] Müller | Evaluating clustering in subspace projections of high dimensional data[END_REF]. For each synthetic dataset, we simply took the clustering having the lowest SAE measure (internal criterion of quality).

A.5 Ranking method over real world datasets

The algorithms were ranked over the seven real world datasets using the following procedure.

Cluster quality measures For each measure, on each data set, two rankings of the 11 algorithms were computed: one for the bestM ax score and one for the bestM in score (see Appendix A.4), with ranks ranging from 1 to 11, rank 11 being associated to the algorithm obtaining the highest quality. The overall ranking of an algorithm was then simply the average of its rank values.

Coverage The same procedure was used to compare the coverages obtained. The coverage denotes the fraction of objects of the dataset that are associated to clusters. This measure is less than 1 if some objects are not associated to one of the output clusters, or if they are identified as outliers or as reflecting noise. When the coverage decreases, discarding some objects can result in a direct improvement of several quality measures (because of clusters being more homogeneous). Of course putting apart too many objects is likely to lead to less representative models and is most of the time not desirable. For the coverage a rank value of 11 was associated to the highest coverage.

Number of clusters

The rankings were computed using the absolute value of the difference between the number of clusters found by the algorithm and the number of classes in the dataset. The rank value 11 is given to the smallest absolute value. However, as previously mentioned, the number of classes does not necessarily reflect the number of subspace clusters in the datasets.

The global trade-off is then to reach high quality measures while preserving a high coverage (except for data containing many outliers or important noise), and without splitting the data into too many clusters.

8 :Figure 1 :

 81 Figure 1: SubCMedians algorithm.

  L and W describe respectively to the locations and to the weights of the centers along each dimension, both matrices having SD max rows and D columns. An element L i,d represents the coordinate of a center m i along dimension d, and an element W i,d denotes the weight of dimension d for m i . The subspace associated to a center m i is D i = {d ∈ {1, . . . , D}|W i,d > 0}. Valid centers are those for which at least one dimension is defined. Their set of indices is simply Γ = {c ∈ {1, . . . , SD max }| D d=1 W c,d > 0}. The total model weight, noted ω, is i,j W i,j and the model size is simply c∈Γ |D c |. Example Let us consider two matrices L and W defined for SD max = 6 and D = 2:

6

  Rows 3, 4 and 6 describe no valid center (all weights equal to zero in W), while rows 1, 2 and 5 represent the centers m 1 , m 2 and m 5 and their subspaces: D 1 = {1}, D 2 = {2} and D 5 = {1, 2}. The respective coordinates in their associated subspaces are given by L: m 1 = (0.5), m 2 = (-0.8) and m 5 = (-0.3, 0.2).

else 18 :

 18 Draw c ∈ Γ, with for each c a probability P (c) proportional to D j=1 W c,j ω 19: end if 20: W c,d ← W c,d + 1 21: L c,d ← Coordinate of s along dimension d 22: return L , W ; 23: end function

Figure 2 :

 2 Figure 2: Generation of one neighbor.

Figure 4 :

 4 Figure 4: Details of the cluster structures and of the runtimes on Pendigits and Diabetes.

RNIAFigure 5 :

 5 Figure 5: Mean RN IA vs percentage of noise points in the dataset.

  Consider a cluster C and a dimension d. Let us suppose that the coordinates X d of the objects in C along d follow a Gaussian distribution N (µ d , σ d ). Let us consider that a badly placed center m is simply an object in C taken randomly. Along dimension d, the difference between the location of an object X chosen Runtime vs. dataset dimensionality

Figure 6 :

 6 Figure 6: Runtimes (avg. 10 runs) for SubCMedians vs sample sizes (| S|) for the synthetic dataset of size 5500 (6a), and vs the synthetic dataset dimensionalities (6b). Runtimes of the unweighted version of SubCMedians as blue triangles.

Figure 7 :2n + 1 . 2 ,

 712 Figure 7: Quality measures and number of clusters obtained on synthetic datasets by SubCMedians (red circles) and the other algorithms (green areas). Results of the unweighted version of SubCMedians as blue triangles.

1 ω ) 1 ,

 1 and since we set SD max = N bExpClust × D, we have p 0.1 × 1 SDmax×N bExpClust . The expected value of k is E(k) = N bIter × p, thus to have E(k) ≥ 1, the default minimum N bIter value is set to 10 × SD max × N bExpClust. Dataset sample size N Consider a cluster C and a dimension d, supposing that the coordinates in C along d follow N (µ d , σ d ). As stated in Section 4.2, θd the median estimator of these coordinates, using a sample of size n, follows N (µ d , σ d π 2n ). If we accept a standard error of 1/4 of the original σ d then the minimum sample size satisfies σ θd = σ d 4 = σ d π 2n and we have n = 8π 25. Such sample allows to estimate the median location of a cluster in the D dimensions, but if there are N bExpClust clusters, more objects are needed. Let us suppose that all clusters have the same size, and thus are likely to be represented by similar numbers of objects in the sample, then the recommended minimum value for N is 25 × N bExpClust.

Figure 8 :

 8 Figure 8: Number of candidate centers (avg. 10 runs) for SubCMedians (red circles) and unweighted-SubCMedians (blue triangles) vs dataset dimensionality.

  3 using an expected number

		Pendigits: 16 dimensions, 10 classes, 7494 objects
		Coverage Cluster Number Average Dim Runtime (seconds)
		max min	max	min max	min	max	min
	CLIQUE	1.00 1.00 1890.0	36.0 3.10	1.50	67891	219
	DOC	0.91 0.91	15.0	15.0 5.50	5.50	178358	178358
	MINECLUS	1.00 1.00	64.0	64.0 12.10 12.10	780167	692651
	SCHISM	1.00 0.93 1092.0	290.0 10.10	3.40 500000000	21266
	SUBCLU	Runtime exceeding the maximal runtime allowed
	FIRES	0.94 0.94	27.0	27.0 2.50	2.50	169999	169999
	INSCY	0.91 0.82 262.0	106.0 5.30	4.60	2000000 1000000
	PROCLUS	0.90 0.74	37.0	17.0 14.00	8.00	6045	4250
	P3C	0.90 0.90	31.0	31.0 9.00	9.00	2000000 2000000
	STATPC	0.99 0.84 4109.0	56.0 16.00 16.00 50000000 3000000
	SUBCMEDIANS 1.00 1.00	41.0	34.0 12.21 10.51	556	523
		Diabetes: 8 dimensions, 2 classes, 768 objects
		Coverage Cluster Number Average Dim Runtime (seconds)
		max min	max	min max	min	max	min
	CLIQUE	1.00 1.00	349.0	202.0 4.20	2.40	11953	203
	DOC	1.00 0.93	64.0	17.0 8.00	5.10 1000000	51640
	MINECLUS	0.99 0.96	39.0	3.0 6.00	5.20	3578	62
	SCHISM	1.00 0.79	270.0	21.0 4.20	3.90	35468	250
	SUBCLU	1.00 1.00 1601.0	325.0 4.70	4.00	190122	58718
	FIRES	0.81 0.03	17.0	1.0 2.50	1.00	4234	360
	INSCY	0.83 0.73	132.0	3.0 6.70	5.70	112093	33531
	PROCLUS	0.92 0.78	9.0	3.0 8.00	6.00	360	109
	P3C	0.97 0.88	2.0	1.0 7.00	2.00	656	141
	STATPC	0.97 0.75	363.0	27.0 8.00	8.00	27749	4657
	SUBCMEDIANS 1.00 1.00	16.0	13.0 3.69	2.87	3	3

2f (θ) √ n[START_REF] Maritz | A note on estimating the variance of the sample median[END_REF][START_REF] Sheather | A finite sample estimate of the variance of the sample median[END_REF]. This approximation derives from the central limit theorem and holds for large enough

B Acknowledgements

This research has been supported by EU-FET grant EvoEvo (ICT-610427). Other support: Christophe Rigotti is a member of LabEx IMU (ANR-10-LABX-0088).


Mehdi Saqalli
email: mehdi.saqalli@univ-tlse2.fr

Nicolas Maestripieri
email: nicolas.maestripieri@univ-tlse2.fr

Melio Saenz
email: msaenz47@gmail.com

Mahamadou Belem
email: mahamadou.belem@gmail.com

"The world is not enough" : pleading against the data gap postulate for building interdisciplinary research actions

Introduction

« We have not enough data about that ». This is often the answer one modeler may encounter. The common answer the modeler think about is "ok, but then? We can do something ugly, fuzzy, and not precise but clearly, the mistake will be lower than not putting the process because of the lack of data". Even more, the "not-enough-data" assertion is theoretically always valid: whatever the issue, data will be lacking. Where to position the limit after which one can say "ok, let us combine what we know to see it has a meaning", i.e. try to build a theory, a model of the reality for answering a question? More generally, our purpose in this communication is to argue that asking "how can we model without all the necessary information?" means actually ""how can we model?".

One may consider that modelling is the last avatar of the less known and less visible and valorizing second part of research: the construction and creation of theories from data and information scientists have previously collected. This demarche (or modality of inference), often called "inductive" in the most accepted hypothetico-deductive research approach, i.e. deduction, induction and abduction (Blecic & Cecchini, 2008, p. 539-540), implies to combine altogether "elements", pieces of science along a plan that may enlighten an issue. This may have been assessed in the past along an intuitive process, such as described by [START_REF] Bergson | L'Intuition philosophique[END_REF]: he described this capacity of connecting processes, patterns and dynamics along sometimes illogical analogies, comparisons and consistencies as a purely human action, impossible to formalize. Nowadays, modelling tools, especially when implemented to integrate both qualitative and quantitative information and rules, do have this ability if and only if they are used along a formalized and epistemologically relevant methodology. They can then be used as a way to explicit relations along a systemic approach. We do consider that they should be used as a way to fulfill the second fraction of research: connecting data.

Interdisciplinarity: when do we need it?

Actually, several scientific disciplines do not need interest for other disciplines. So, one may ask: "when do we need "interdisciplinarity"? Even more important, how can we characterize it? Better than using a philosophic background we do consider as relevant but beyond our competency and our level of abstraction, let us use the vox populi argument: When, where and in what domain can we see a plea for interdisciplinarity?

1. The need facing an "epistemological obstacle" [START_REF] Bachelard | La Formation de l'esprit scientifique. Contribution à une psychanalyse de la connaissance objective[END_REF]: This is a necessary but not sufficient condition for an interdisciplinary need. It only means that one scholar from one discipline faces an issue that goes beyond the "normal" science he/she belongs to.

The background need:

The first criterion is obvious: "when a scientist cannot borrow data and information from other disciplines he/she may need without having knowledge of the mechanisms that create such information. For instance, using prices of goods collected from economic census for better characterizing the needs of a social group into a socio-anthropologic study does not mean it is an interdisciplinary study because some economics is used. It means that each discipline having its own point of view and paradigms on the reality, having the corresponding background that gives access to this point of view and these paradigms is thereby a sine qua non condition for interdisciplinarity.

3. The need for a paradigm on dynamics and variables: The second criterion is related to the previous one and come naturally when thinking about interdisciplinarity: it concerns combination of disciplines very different one from one another. Actually, three groups can be considered:

• The Physics group: It belongs to disciplines where refutation [START_REF] Popper | Realism and the Aim of Science: From the Postscript to The Logic of Scientific Discovery[END_REF]) can be assessed with fully controlled experiences, i.e. where the experience is considered as ceteris paribus i (here "considered" means that the related scientific community accepts that it is ceteris paribus and has tried to refute it).

Relations and dynamics are defined according to a limited range of variables. Full determinism is not reached only because of the principle of Heisenberg and the importance of the knowledge of initial conditions which ignorance leads to chaos. Only quantitative data are considered.

• The Biology group: it belongs to disciplines where refutation can be assessed with observations and samples, with the support of some controlled experiences. Relations and dynamics are defined according to a medium range of variables. Along the effects of Heisenberg and initial conditions, non-determinism is brought by the lack of information on differential biological functions (for instance, the absorption capacity regarding water or other elements differ from one plant to another) but also emergence, i.e. the property of a phenomenon which is a combination of several elements and which behavior cannot be reduced to each element [START_REF] Müller | Des systèmes autonomes aux systèmes multi-agents : Interaction, émergence et systèmes complexes (HDR Habilitation à Diriger les Recherches en Informatique)[END_REF]. However, only quantitative data are considered, but dynamics may be described along qualitative schemes without determinism (for instance, animals do not pilot their fate in absence of self-reflexivity).

• The group of social sciences: Practically, no experiences can be assessed except some well-famous but questionable very controlled behavior experiments such as the one of Milgram. Because it is far more difficult to characterize which variables are not part of the studied system (Why social psychology is not fully part of economics?), relations and dynamics are defined according to a large range of variables.

Hypotheses are proposed with far more conditions and many anthropologists do tend to avoid theorizations. Refutation can be assessed only with observations and samples. Along the effects of Heisenberg, initial conditions, lack of differential knowledge and emergence, non-determinism is everywhere: no human groups ever behave in the same manner twice. To face the diversity of variables and the structural non-determinism, dynamics are mainly described and characterized along qualitative manners supported by quantitative data. Both qualitative and quantitative tools and data are used.

These three groups do have, because of differences between paradigms, principles, methods and practices large difficulties for inter-dialogue. We do consider that interdisciplinarity is needed if and only if it concerns sciences that belong to at least two of these groups.

4. Finally, another factor does act as an incentive for interdisciplinary: applicability. For instance, the Apollo program did have to include psychology and sociology counter-intuitively for space scientists once the program did raise the application level, i.e. the time when the group of Physics sciences did have to be built, i.e. integrate the oekoumen, the human community.

Interdisciplinarity: Why are socio-ecological sciences its most prominent supporter?

Let us consider a macro-scenario where Nature, Life and Society coexist. This scenario has the three properties which define a system: a universe with elements which have a position and leads to identify the system's structure, a set of properties and attributes on which basis it is possible to assign qualitative and quantitative variables to describe the states of the system and, among its elements we can find or establish a set of relationships which determines the behavior of the system.

1. Socio-ecological systems need formalism for apprehending a fluctuant, complex system, i.e. a model: We have seen that any system, whatever the discipline it belongs cannot be fully known, observed and described. That is impossible because the quantity of variables needed to do so is infinite and the variability of them in time.

Then, we have to choose a subset of relevant variables in agreement with our interest and needs. At this time we are not describing the reality but a part of it. We call this, a model. Value of models can be established by conceptual validation, accurate representation of the reality, stability of the simulation processes and convergence of solutions or simply that the model meets our objectives/expectations (Turning principle).

2. Once the world of academy finds that its own existence is only justified in the measure that it gets community needs, social life would involve a very near and strong relationship with scientific and fundamental knowledge and with solutions which can be provided from research and development. At this moment, the interdependence between Science and Society encounters an amazing growth which is completed with the integration of Nature as the main source of resources for life.

Reality cannot be explained in terms of an isolated thinking discipline. We must take into account the consequences produced by interactions. Knowledge models need to reflect at least those consequences which are enough to explain the behavior of the macro-system and which will be useful to solve the community problems.

Models need to be fed with qualitative and quantitative data which could lead to increment the value of the second step in scientific research: the construction and creation of theories from data and information that scientists have previously collected and qualified.

Nowadays, modelling tools, especially when implemented to integrate both qualitative and quantitative information and rules, have this ability if and only if they are used along a formalized and epistemologically relevant methodology.

They can then be used as a way to establish explicit relations along a systemic approach. We do consider that they should be used as a way to fulfill the second fraction of research: connecting data.

Along with this necessity of a formalization of information as the second mandatory part of the research process, formalizing elements is a cure for self-focusing scientific approaches.

Interdisciplinarity: what for?

Several points are supporting the plea for interdisciplinarity:

• "the better complexity": Because interdisciplinary research objects such as socio-ecological systems include de facto many disciplines, eliminating some (and sometimes because of the lack of data on them, which we deeply deplore as in the introduction) is an important error. More exactly, we consider that taking into account all the components of a socio-ecological system (including society, environment and economy) and simplifying each component is more relevant and less harmful than neglecting some activities by focusing on the one which seems to be the most important.

• Holism: More globally and following [START_REF] Verburg | Land use change modelling: current practice and research priorities Peter[END_REF] our observations are bound to the extent and resolution of measurement causing each observation to provide only a partial description of the whole multiscale land use system. Beyond the scale of analysis of for instance land use change, it means that scientists and stakeholders have to tear down the walls of disciplinary approach and cultural context which lead to misinterpretation (subjective interpretation) about these phenomena. For instance, analyzing socioecological processes, one of the most complex interdisciplinary scientific objects, combining social and biophysical sciences, the complexity of it must be tackled with the analysis of the holistic character of reality.

• "for the greater good": Indeed, the main quality of social and environmental formalization, and by then a "loud and clear" formalized interdisciplinarity, is to "force" scientists and scholars to represent reality in itself: the need to achieve the model, computerized or not, required for every scholar to sacrifice a portion of the complexity of its own theme on the altar of the combination of disciplines. The importance of encouraging the success of the object as a whole and not solely one's task as oneself is crucial as is the legitimacy of the objective and the people in charge.

• Exactitude: Following the previous point, interdisciplinarity is a test for scientific rigor and more precisely, exactitude. Exactitude is often confounded with precision and precision do have this shiny power of data with several figures after the comma. But what do means such figures for cases such as, for instance, demographic analyses without including migration? It often happens that scientists do present their datasets without justifying the origins of the variables on which the data were collected: why these lasts were chosen and not others? One should then differentiate variables and data and by then characterize the scope of the object of research, i.e. its exactitude before looking after precision. Variables allow getting relationships and dynamics while data parameterize these relationships.

• Epistemological formalism: Again following the previous point, these variables have to be identified and hierarchized according to a paradigm or a principle (local perception? Experts' common agreement?) which legitimizes their selection to the detriment of other variables. We do plea for a formalization of the criteria, the principle on which variables are designated as relevant. Along the go & return flux between induction and deduction, they should be de jure also the criteria for "validation".

• Plausibility: Along with this necessity of a formalization of information as the second mandatory part of the research process, formalizing elements is a cure against self-focusing scientific approaches. Along the traditional self-checking loop mistake (a set of data is used to characterize a function describing a phenomenon and for "validating this function, it is compared to the very same data which created it), one may consider that "validating" a function coming from one scientific discipline with data from the same discipline has much more risks to create a similar loop. We then plea for "validation" steps that implies using sets from other disciplines to lower the risks of such loops.

The complexity of socio-ecological systems is not inherent to a specific discipline or a domain. Interdisciplinary must avoid all reproduction of domination and should -ideally -transcend frontiers of each discipline. Dawn [START_REF] Youngblood | Interdisciplinary Studies and the Bridging Disciplines: A Matter of Process[END_REF] explains that "what interdisciplinary studies can therefore learn from the bridging disciplines is the importance of not becoming a domain, as domain creates territory and territory creates niche dominance […]".

As a human animals, researchers act -in a certain way -like non-human animals. Ethological studies talk about social animals in a hierarchic community. We have the alpha, the beta and the omega which interact (and fight) for a social position and/or recognition of liability within a territory. Maybe researchers should think about "adisciplinarity" which is located elsewhere in another space outside of discipline's boundaries.

One may then ask why, if it is so interesting and relevant, it is not so practiced? The answer may come from this clue: Our own observations support the idea that interdisciplinarity is harmful for scholars [START_REF] Turner | Contested identities: Human-environment geography and disciplinary implications in a restructuring academy[END_REF].

So, why it is so hard and boring?

• Interpreting complex phenomena, especially when one looks after a socio-ecological system, is related de facto to the way it is interpreted, i.e. how it is perceived and what part is seen as interesting and relevant: it does have all to do with notions of subjectivity and objectivity, even in science. We do plea for the inclusion of the affective part of each scientist (why do you like this aspect of the object of research?) not as anthropology dealt with it in the past, with a high level of honesty but with a low efficiency in the dialogue with other disciplines, but more as a factor among others.

• In a way, we find complexity (different scientific point of view and/or approach) inside complexity (socioecological systems). It could be "hard and boring" because one phenomenon generates various complex questions: where and when ends a complex phenomenon? Considering the whole hypothetical variables would allow optimum accuracy of prediction? [START_REF] Maestripieri | Validation spatiale de deux modèles de simulation : l'exemple des plantations industrielles au Chili[END_REF]. Are the limits the same between physical sciences, mathematics and social and human sciences? [START_REF] Deffuant | Visions de la complexité. Le démon de Laplace dans tous ses états[END_REF] questioned different visions of complexity and have questions about -among others -time and spatial scales, the relevance of Big Data. What about the cognitive status of the individual, unexpected phenomena, uncertainty, multiplicity and instability of itself?

• Again and pursuing on the emotional part that is often neglected, interdisciplinarity implies that one scholar from other sciences may discuss one's own methodologies and results. However, this may have harmful effects and we also plea for a gentleman's agreement for more clarity. Game theory supports the idea that any group, including scholars, does have conflictual relations. Such conflicts are "sociologically normal" and we consider that open formal oppositions are less harmful than hidden agendas. Such a gentleman's agreement may include the necessity for each scholar to involve a moment in the discipline of others with whom he/she wants to collaborate, the formalization of the research construction along management methods such as ARDI [START_REF] Toit | ARDI: a co-construction method for participatory modelling in natural resources management[END_REF] or the use of a model which should "force" the dialogue.

• Following the above statement, the creation of an object is like the establishment of a research project. One seeks to place his discipline to have more assets before the project itself. This is reinforced by the powers that be (who own the management? The financing? The institutional connections). The interdisciplinary problem lies in the use of method. The methods remaining to build, they are most easily influenced by the context and there is no project that is not "the plaything" of extra-scientific aspects. The interdisciplinary is the least armed, because it is naturally under construction. The use of recognized tools (ZADA, ADM, ARDI, and UML) can reduce this confusion but not make it disappear.

• The principle of « each one at home and the sheep will be well kept » is easy, much more than interdisciplinary. Hence the need to seek a compromise and not a consensus. The latter is becoming more inaccessible as partners include a research project (the more people are, the more emergence of conflict is high). According to M. [START_REF] Nachi | Concept commun et concept analogique de compromis : « un air de famille[END_REF] "a compromise is a process that develops between partners seeking to reach agreement at the price of some accommodations, modifications, and reciprocal concessions between competing interests." This relates to the question of domination discussed earlier.

Conclusion

There is a palpable cognitive impasse. Many researchers (reinforced by the media image) see science as a collection of data. Otherwise, they are inventors who press the buttons. We, modelers, seeking to make connections, are seen as technicians. This comes back to the original idea of cultural cognition. According to the Cultural Cognition Project (http://www.culturalcognition.net/) it "refers to the tendency of individuals to conform their beliefs about disputed matters of fact (e.g., whether global warming is a serious threat; whether the death penalty deters murder; whether gun control makes society more safe or less) to values that define their cultural identities".

The difficulty is to build a true transdisciplinary approach beyond the emotional aspect. The latter has an impact on the question of the research question, the subject and the object of research (two different things). In short, the ability to question everything.