Frédéric Ros
email: frederic.ros@univ-orleans.fr

Serge Guillaume
email: serge.guillaume@irstea.fr

DENDIS: A new density-based sampling for clustering algorithm

Keywords: Density, distance, space coverage, clustering, Rand index

To deal with large datasets, sampling can be used as a preprocessing step for clustering. In this paper, an hybrid sampling algorithm is proposed. It is density-based while managing distance concepts to ensure space coverage and fit cluster shapes. At each step a new item is added to the sample: it is chosen as the furthest from the representative in the most important group. A constraint on the hyper volume induced by the samples avoids over sampling in high density areas. The inner structure allows for internal optimization: only a few distances have to be computed. The algorithm behavior is investigated using synthetic and real-world data sets and compared to alternative approaches, at conceptual and empirical levels. The numerical experiments proved it is more parsimonious, faster and more accurate, according to the Rand Index, with both k-means and hierarchical clustering algorithms.

Introduction

Summarizing information is a key task in information processing, either in data mining, knowledge induction or pattern recognition. Clustering [START_REF] Ling | Cluster analysis algorithms for data reduction and classification of objects[END_REF] is one of the most popular techniques. It aims at grouping items in such a way that similar ones belong to the same cluster and are different from the ones which belong to other clusters. Many methods [START_REF] Andreopoulos | A roadmap of clustering algorithms: finding a match for a biomedical application[END_REF] have been proposed to identify clusters according to various criteria. Some of them [START_REF] Nagpal | Review based on data clustering algorithms[END_REF] are based on an input space partition (k-means, spectral clustering, Clarans) or grid techniques (like Sting or Clique), others are density-based (Dbscan, Denclue, Clique). Some of these techniques benefit a tree implementation: Birch, Cure, Diana, Chameleon, Kd-tree.

Algorithms are becoming more and more sophisticated in order to be able to manage data with clusters of various shapes and densities. This leads to an increased computational cost which limits their practical use, especially when applications concern very large database like records of scientific and commercial applications, telephone calls, etc. Clearly, most of mature clustering techniques address small or medium databases (several hundreds of patterns) but fail to scale up well with large data sets due to an excessive computational time. Therefore, in addition to the usual performance requirements, response time is of major concern to most data clustering algorithms nowadays. Obviously, algorithms with quadratic or exponential complexity, such as hierarchical approaches, are strongly limited, but even algorithms like k-means are still slow in practice for large datasets.

While some approaches aim to optimize and speed up existing techniques [START_REF] Viswanath | A hybrid approach to speed-up the k-means clustering method[END_REF][START_REF] Chiang | A time-efficient pattern reduction algorithm for k-means clustering[END_REF], sampling appears as an interesting alternative to manage large data sets. In our case, sampling is a preprocessing step for clustering and clustering is assessed according to cluster homogeneity and group separability. This calls for two basic notions: density and distance.

Clusters can be defined as dense input areas separated by low density transition zones. Sampling algorithms are based upon these two notions, one driving the process while the other is more or less induced.

Various techniques have been proposed in the abundant literature. Some algorithms estimate local density, using neighborhood or kernel functions [START_REF] Kollios | Efficient biased sampling for approximate clustering and outlier detection in large data sets[END_REF], in order to bias the random sampling to make sure small clusters are represented in the sample [START_REF] Palmer | Density biased sampling: An improved method for data mining and clustering[END_REF][START_REF] Ilango | A survey of grid based clustering algorithms[END_REF]. Others work at a global scale, like the popular k-means or evolutionary approaches [START_REF] Naldi | Comparison of distributed evolutionary k-means clustering algorithms[END_REF]. In the former, the number of representatives is a priori set, each center induces an attraction basin. The third category includes incremental algorithms. They can be driven either by the attraction basin size (Yang & Wu, 2005) favoring the density search or by distance concepts [START_REF] Sarma | Speeding-up the kernel k-means clustering method: A prototype based hybrid approach[END_REF][START_REF] Rosenkrantz | An analysis of several heuristics for the traveling salesman problem[END_REF] promoting the coverage aspect.

Incremental algorithms differ in the heuristics introduced to balance the density and distance concepts, and also in the parametrization. A comparison of algorithms for initializing k-means can be found in [START_REF] Celebi | A comparative study of efficient initialization methods for the k-means clustering algorithm[END_REF].

Fulfilling the two conflicting objectives of the sampling, ensuring small clusters coverage while favoring high local density areas, especially around the modes of the spatial distribution, with a small set of meaningful parameters, is still an open challenge.

The goal of this paper is to introduce a new incremental algorithm to meet these needs. DENDIS combines density and distance concepts in a really innovative way. Density-based, it is able to manage distance concepts to ensure space coverage and fit cluster shapes. At each step a new item is added to the sample: it is chosen as the furthest from the representative in the most important group. A constraint on the hyper volume induced by the samples avoids over sampling in high density areas. The attraction basins are not defined using a parameter but are induced by the sampling process. The inner structure allows for internal optimization. This makes the algorithm fast enough to deal with large data sets.

The paper is organized as follows. Section 2 reports the main sampling techniques. Then DENDIS is introduced in Section 3 and compared at a conceptual level to alternative approaches in Section 4. The optimization procedure is detailed in Section 5. Section 6 is dedicated to numerical experiments, using synthetic and real world data, to explore the algorithm behavior and to compare the proposal with concurrent approaches. Finally Section 7 summarizes the main conclusions and open perspectives.

Literature review

The simplest and most popular method to appear was uniform random sampling, well known to statisticians. The only parameter is the proportion of the data to be kept. Even if some work has been done to find the optimal size by determining appropriate bounds [START_REF] Guha | Cure: An efficient clustering algorithm for large databases[END_REF], random sampling does not account for cluster shape or density. The results are interesting from a theoretical point of view [START_REF] Chernoff | A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations[END_REF], but they tend to overestimate the sample size in non worst-case situations.

Density methods [START_REF] Menardi | An advancement in clustering via nonparametric density estimation[END_REF] assume clusters are more likely present around the modes of the spatial distribution. They can be grouped in two main families for density estimation: space partition [START_REF] Palmer | Density biased sampling: An improved method for data mining and clustering[END_REF][START_REF] Ilango | A survey of grid based clustering algorithms[END_REF] and local estimation, using neighborhood or kernel functions [START_REF] Kollios | Efficient biased sampling for approximate clustering and outlier detection in large data sets[END_REF].

The main idea of these methods is to add a bias according to space density, giving a higher probability for patterns located in less dense regions to be selected in order to ensure small cluster representation. The results are highly dependent upon the bias level and the density estimation method. The local estimation approaches (kernel or k-nearest-neighbors) require a high computational cost. Without additional optimization based on preprocessing, like the bucketing algorithm [START_REF] Devroye | On the average complexity of some bucketing algorithms[END_REF], they are not scalable. However this new step also increases their complexity.

Distance concepts are widely used in clustering and sampling algorithms to measure similarity and proximity between patterns. The most popular representative of this family remains the k-means algorithm, and its robust version called k-medoids. It has been successfully used as a preprocessing step for sophisticated and expensive techniques such as hierarchical approaches or Support Vector Machine algorithms (SVM) [START_REF] Xiao | A k-farthest-neighbor-based approach for support vector data description[END_REF]. It is still the subject of many studies to improve its own efficiency and tractability [START_REF] Lv | An efficient and scalable density-based clustering algorithm for datasets with complex structures[END_REF][START_REF] Khan | Cluster center initialization algorithm for k-modes clustering[END_REF]Zhong et al., 2015). The proposals are based on preprocessing algorithms which are themselves related to sampling or condensation techniques (Zahra et al., 2015;[START_REF] Arthur | k-means++: The advantages of careful seeding[END_REF] including evolutionary algorithms [START_REF] Hatamlou | A combined approach for clustering based on k-means and gravitational search algorithms[END_REF][START_REF] Naldi | Comparison of distributed evolutionary k-means clustering algorithms[END_REF]. These algorithms are still computationally expensive [START_REF] Tzortzis | The minmax k-means clustering algorithm[END_REF].

While the k-means is an iterative algorithm, whose convergence is guaranteed, some single data-scan distance based algorithms have also been proposed, such as leader family [START_REF] Sarma | Speeding-up the kernel k-means clustering method: A prototype based hybrid approach[END_REF][START_REF] Viswanath | A hybrid approach to speed-up the k-means clustering method[END_REF] clustering or the furthest-first-traversal (fft) algorithm [START_REF] Rosenkrantz | An analysis of several heuristics for the traveling salesman problem[END_REF]. The pioneering versions of distance based methods are simple and fast, but they also are limited in the variety of shapes and densities they are able to manage.

When improved, for instance by taking density into account, they become more relevant but their overall performance depends on the way both concepts are associated and, also, on the increase of the computational cost. The mountain method proposed by Yager and its modified versions (Yang & Wu, 2005) are good representatives of hybrid methodologies as well as the recent work proposed by [START_REF] Feldman | Scalable training of mixture models via coresets[END_REF]. Density is managed by removing from the original set items already represented in the sample.

Strategies usually based on stratification processes have also been developed to improve and speed up the sampling process [START_REF] Gutmann | Stratified gradient boosting for fast training of conditional random fields[END_REF].

Reservoir algorithms (Al-Kateb & Lee, 2014) can be seen as a special case of stratification approaches. They have been proposed to deal with dynamic data sets, like the ones to be found in web processing applications. These method need an accurate setting to become really relevant.

Even if the context is rather different, Vector Quantization techniques [START_REF] Chang | A fast vq codebook search with initialization and search order[END_REF], coming from the signal area especially for data compression, involve similar mechanisms. The objective is to provide a codebook representative of the original cover without distortion. The LBG algorithm and its variations [START_REF] Bardekar | A review on lbg algorithm for image compression[END_REF] appear to be the most popular. The methods are incremental, similar to the global k-means family approaches [START_REF] Likas | The global k-means clustering algorithm[END_REF][START_REF] Bagirov | Fast modified global k-means algorithm for incremental cluster construction[END_REF], as at each step a new representative is added according to an appropriate criterion. Recent literature [START_REF] Tzortzis | The minmax k-means clustering algorithm[END_REF][START_REF] Ma | High-quality initial codebook design method of vector quantisation using grouping strategy[END_REF] reports the difficulty to find the balance between length of codebook en-tries, its quality and time required for its formulation. This short review shows that sampling for clustering techniques have been well investigated. Both concepts, density and distance, as well as the methods have reached a good level of maturity. Approaches that benefit from a kd-tree implementation [START_REF] Nanopoulos | An efficient and effective algorithm for density biased sampling[END_REF][START_REF] Wang | A divide-and-conquer approach for minimum spanning tree-based clustering. Knowledge and Data Engineering[END_REF] seem to represent the best alternative, among the known methods, in terms of accuracy and tractability. However, they are highly sensitive to the parameter setting.

The design of a method that would be accurate and scalable allowing to process various kinds of large data sets with a standard setting, remains an open challenge.

DENDIS: the proposed sampling algorithm

The objective of the algorithm is to select items from the whole set, T , to build the sample set, S. Each item in S is called a representative, each pattern in T is attached to its closest representative in S. The S set is expected to behave like the T one and to be as small as possible. DENDIS stands for DENsity and DIStance, meaning the proposal combines both aspects.

Overview of the algorithm It is an iterative algorithm that add a new representative at each step in order to reach two objectives. Firstly, ensure high density areas are represented in S, and, keeping in mind the small size goal, avoiding over representation. The second objective aims at homogeneous space covering to fit cluster shapes. To deal with the density requirement the new representative is chosen in the most populated set of attached patterns. For space covering purposes, the new representative is the furthest from the existing one.

Over representation is avoided by a dynamic control of both parameters that define density: volume and cardinality. The latter is defined according to the unique input parameter, granularity, noted g r , and the initial set size, n. The product defines the W t threshold: the minimum number of patterns attached to a given representative. The volume is estimated by the maximum distance between an attached pattern and the representative.

The two steps of the algorithm The algorithm is made up of two steps.

The first one, Algorithm 1, is based on space density while taking into account distance notions. The second one, Algorithm 2, can be seen as a post processing step which aims at not selecting outliers as representatives.

The unique input parameter, except the data to be sampled, is called granularity, and noted g r . Data independent, it is combined with the whole set cardinality to define a threshold, W t , on the number of patterns attached to a given representative (line 5). The granularity impacts the S size, the lower g r the higher the number of representatives. However, the relation between both is not deterministic, like in Sample Random Sampling. The number of patterns attached to a representative also depends on a volume estimation as explained below.

The first sample is randomly chosen (line 3). Then the algorithm iterates to select the representatives (lines 6-30). In a preparation phase, each not selected pattern, x ∈ T \ S 1 , is attached to the closest selected one in S (lines 7-10) and, for each set T y k , the algorithm searches for the furthest attached pattern,

x max (y k ), located at distance d max (y k ) = d(x max (y k ), y k ) (lines 11-14).
Then a new representative is selected (lines 15-26). The selected items are sorted according to the cardinality of the set of patterns they are the representative (line 16) and these sets, T y k , are analyzed in decreasing order of weight.

Each of them is split when two conditions are met (lines 18 and 22). The first one deals with the number of attached patterns: it has to be higher than the threshold, W t = n g r . Without any additional constraint, the representatives would tend to have the same number of patters attached, close to W t . This behavior would lead to an over size sample in high density areas. Therefore, the other condition is related to the density, controlled by the induced hyper

α k = max( W t |Ty k | , K) 22: if (dmax(y k ) ≥ α k dmax(y k ) y k ∈S
) then

23:

x * = xmax(y k )

24:

ADD=TRUE, break As previously explained, the new representative is chosen as the furthest attached pattern, x max (y k ), for space covering purposes (line 23).

The process is repeated until there is no more set to split (line 18-19).

Algorithm 2 The post processing algorithm

1: for all yi in S do 2: if (|Ty i | ≤ Wn) then 3: S = S -{yi}, s = s -1 4: end if 5:
if (dmax(yi) > dmax(yi)

y i ∈S ) then 6: yi = arg min x l ∈Ty i d(x l , B)
{B is the barycenter of Ty i }

7:

end if

8:

Ty i = {yi} 9: end for 10: for all x l ∈ T \ S do 11:

Find dnear(x l ) = min

y k ∈S d(x l , y k ) 12:
Ty k = Ty k ∪ {x l } 13: end for When all the s representatives are selected, the post processing step, Algorithm 2, discards outliers as representatives. As the new selected item is chosen as the furthest from the ones which are already selected, the S set is likely to include some outliers. Two cases may occur.

In the first one (lines 2-3), when the representative is isolated, the number of attached patterns is lower or equal than the noise threshold

|T yi | ≤ W n , inferred 9
Author-produced version of the article published in Expert Systems with Applications, 2016, N°56, p. 349-359. The original publication is available at http://www.sciencedirect.com Doi: 10.1016/j.eswa.2016.03.008

from the T y k distribution. Let T = {T y k | |T y k | < |T y k |} be the reduced set of
representatives with a number of attached pattern less than the average, and let m, σ and min, the mean, standard deviation and minimum of the |T |. The noise threshold is defined as: W n = max(m -2σ, min). The choice is then to remove this representative labeled as noise.

In the other case, the outlier detection is based upon the induced volume:

the corresponding d max is higher than average (line 5). In the post processing phase, the input space coverage is quite homogeneous: the mean can be used as a threshold. In this case, the new representative is chosen as the closest to the barycenter, B, of the set (line 6). This way of doing is similar to the usual practice: the representative is set at the center of the dense areas, like in kernel and neighboring approaches. By contrast, the proposal comes to select the representative at the border of the dense area. Once at least a representative has been changed or removed, an update of the attached patterns is needed (lines 10-13), and to do this the sets of attached patterns must be previously reset (line 8). In the method proposed by [START_REF] Feldman | Scalable training of mixture models via coresets[END_REF], the representatives are randomly selected, yielding a higher probability for dense areas, and inducing variable size basins. In DENDIS the attraction basin is also induced: the average volume is estimated when the space coverage is homogeneous.

It ensures space coverage. The methods which include a neighborhood definition, e.g. leader family, grids, Mountain method, achieve a total coverage.

Depending on the parameter setting they either require a large sample or may miss important details. The dynamic ones, Feldman or trees, are more powerful. In DENDIS, choosing the furthest item in the group from the representative ensures small clusters are represented. This idea is shared by the fft algorithm [START_REF] Rosenkrantz | An analysis of several heuristics for the traveling salesman problem[END_REF]. The main difference is that in fft the new sample item is chosen as the furthest from its representative, the maximum distance being computed over all the groups, while in DENDIS it is the furthest in the most populated group, balancing the density and coverage constraints. generally provides good results with the risk to be not fine enough to catch small clusters. Choosing a small value, e.g. g r = 0.001, ensures a good accuracy in most cases, whatever the data structure. The price to pay is a risk of over representation. This risk is however limited thanks to the distance constraint. Users may be interested in setting the algorithm according to the desired accuracy.

It
This opens a stimulating perspective.

DEN DIS presents similar ideas than popular algorithms that hybridize density and distance concepts and dynamically define attraction basins. The way these concepts are managed produces a really new algorithm.

Optimization

Distance-based algorithms have an usual complexity of O(n 2 ). This is not the case for the proposal. Many distance computations can be avoided thanks to the algorithm structure itself and by embedding some optimization based on the triangular inequality.

The time complexity of Algorithm 1 is mainly due to the two first loops. For each of the s iterations, the first loop, lines 7-10, computes (n -s)n distances while the second one, lines 11-14, calculates n more ones.

Reducing time complexity

These two loops can be combined in a single one, lines 8-18 in Algorithm 3.

This allows for only computing n -s distances to the new representative, y * , at each of the s iterations.

The complexity is then O(ns), with s n.

The number of distances to be computed is:

T = n l=s (l -1) = n (n -1) 2 - s (s -1) 2 (1)
The spatial complexity for this time optimization can be considered as rea- for all x l ∈ T \ S do 3:

Compute d = d(x l , y * ) 4: if (d < d near (x l )) then 5: T y * = T y * ∪ {x l }, T y(x l ) = T y(x l ) \ {x l } 6: d near (x l ) = d, y(x l ) = y * 7:
end if

8:
if (d > d max (y * )) then 9:

x P = x(x s ), Y P = y * 10:

d max (y * ) = d, x(y * ) = x l 11: end if 12:
end for 13:

Find a new representative y * {Lines 16-26 of Algorithm 1}

14: end while

Using the triangle inequality

A given iteration only impacts a part of the input space, meaning the neighborhood of the new representative. Moreover as the process goes on, the corresponding induced volume decreases. This may save many distance calculations.

When a new representative in S has been selected, y * , the question is: should a given initial pattern, x i , be attached to y * instead of remaining in T yj ? The triangular inequality states: d(y j , y * ) ≤ d(x i , y j )+d(x i , y * ). And, end for

x i ∈ T y * ⇐⇒ d(x i , y * ) < d(x i , y j ). So, if d(y j , y * ) ≥ 2 d(x i , y j ), x i

22:

Find a new representative y * {Lines 16-26 of Algorithm 1} case, the same triangle inequality provides a useful threshold. All x i ∈ T y k with d near (x i ) ≤ 0.5 d(y j , y * ) remain attached to T y k (line 10).

To take advantage of the triangular inequality properties, the number of distances between representatives to be stored is s(s -1)/2.

The optimized version of the sampling algorithm is shown in Algorithm 4.

Estimating the number of computed distances

The number of computed distances cannot be rigorously defined as it depends on the data, but it can be however roughly estimated under some weak hypothesis. Each iteration of this distance based algorithm impacts only the neighborhood of the new representative. Let k be the number of neighbors to consider. The number of distances to be calculated is (n -1) at the first step, then the number of representatives to take into account is min(k, s) and the number of patterns for which the distance to the representatives has to be computed is only a proportion, δ, of the set of the attached ones as the others are managed by the triangular inequality properties. A value of δ = 0.5 seems to be reasonable. This means that a high proportion of representatives are concerned at the starting of the algorithm but the process then becomes more and more powerful when s increases compared to k. The real number of computed distances can be estimated as follows.

C = (n -1) + n-1 i=s min(k,s-i) l=1 δ * |T y l (i)| (2)
where |T y l (i)| is the number of patterns attached to representative l when i representatives are selected.

To approximate C, one can consider that on average the representatives have a similar weight ∀y, |T y l (i)| ≈ n/i. When the two cases, i ≤ k and i > k, are developed, the approximation becomes:

C = (n -1) + δ k+1 i=2 (i -1) n i + n-k-2 i=s k n i As k+1 i=2 (i -1) (n/i) ≤ k+1 i=2 (i) (n/i) and n-k-2 i=s k n i ≤ n-k-2 i=s
k n s , an upper bound of C can be defined as follows:

C ≤ (n -1) + δ n(k -1) + k n s (n -k -2 -s) (3)
As an illustration, using n = 20000, s = 250, k = 10 and δ = 0.6 the decrease ratio, of the number of computed distances to the same number without optimization, as given in Eq. 1, is:

D = C T ≤ 5%
This estimation is clearly confirmed by the experiments.

Under some reasonable assumptions, it can be estimated that most of distance calculations can be saved by judiciously using the triangle inequality. This optimization makes the algorithm very tractable.

Numerical experiments

The main objective of the sampling is to select a part that behaves like the whole. To assess the sample representativeness, the partitions built from the sample sets are compared to the ones designed from the whole sets using the same clustering algorithm. The Rand Index, RI, is used for partition compari- , 4000, 2200, 2000, 4000, 4500, 3500, 3500, 3000, 7500, 2500, 9500}. They are plotted in Figure 3. The real world data are from the UCI public repository. dimensions, with unknown data distribution. Their main characteristics are summarized in Table 1. All the variables are centered and normalized. The reduction ratio highly depends on the data, on their inner structure. The maximum ratio on Figure 4 is 8% for S#1, which comes to 2200 × 0.08 = 176 representatives. As expected, the sample set size is higher when the granularity is lower. This evolution is monotonic but not proportional. This is explained by the restriction on the volume induced by the patterns attached to a representative (line 22 of Algorithm 1). When a dense area is covered, a lower granularity won't add new representatives.

Sample size

Quality of representation

To assess the representativeness of the sample set, the same clustering al- Index. Dealing with the sample set, each non selected pattern is considered to belonging to the cluster of its representative.

Let's consider the k-means algorithm first. The number of clusters being unknown, it has been set to each of the possible values in the range 2 to 20. As the algorithm is sensitive to the initialization, a given number of trials, 10 in this paper, are run for a configuration.

For each data set, synthetic and real world, the resulting RI is averaged over all the experiments, meaning all the trials for all the configurations.

The results are shown in Figures 6 and7. The average RI is higher than 0.85 for all the data sets except for R#4, the Poker Hand data. These results can be considered as good. Is it worth reaching a perfect match with RI = 1?

The cost increase may be high just to make sure all the items, including those located at the border of clusters, whose number varies from 2 to 20, are always in the same partition. is not required to consider the results as good.

It is expected that the bigger the sample set, the higher the RI, at least until the RI becomes high enough. This can be observed in the plots of Figures 6 and7. There is one exception, for S#11 and granularity of 0.05 and 0.01. Comparison with uniform random sampling (URS) is interesting to assess the relevance of the algorithm. Theoretical bounds like the ones proposed in [START_REF] Guha | Cure: An efficient clustering algorithm for large databases[END_REF] guarantee the URS representativeness in the worst case. As the data 415 are usually structured, this leads to an oversized sample. Table 2 reports the results of some comparisons with URS size smaller than the theoretical bounds.

The granularity parameter has been set to reach a similar Rand Index than the one yielded by URS. The results show that, for similar RI, the sample size is usually smaller when resulting from the proposal than the one given by URS.

420

However, in some cases like R#3 and R#7, the results are comparable meaning 21

Author-produced version of the article published in Expert Systems with Applications, 2016, N°56, p. 349-359. The original publication is available at http://www.sciencedirect.com Doi: 10.1016/j.eswa.2016.03.008 that the underlying structure is well captured by URS.

In the case of the hierarchical approach, various dendrograms can be built according to the linkage function, e.g. Ward criterion or single link. To get a fair comparison the number of groups is chosen in S in the range [2, 20] and the cut 425 in T is done to get a similar explained inertia. When the Ward criterion is used the number of groups in S and in T are quite similar while using the single link aggregation criterion, the generated partitions are generally of different sizes.

The average and standard deviation of the Rand Index were computed for all the databases, reduced to 3000 patterns for tractability purposes, and different for the real ones. With the single link one, it is (µ, σ) = (0.87, 0.05) for the synthetic databases and (µ, σ) = (0.88, 0.08) for the real ones. In this case, the standard deviation is higher than the one corresponding to the W ard criterion.

435

This can be due to the explained inertia which may be slightly different and more variable with the single link criterion due to its local behavior.

Computational cost

The sampling algorithm must be scalable to be used in real world problems.

The index used to characterize the algorithm efficiency is computed as a ratio.

440

The numerator is the sum of the sampling time and the time needed to cluster the sample set, while the denominator is the time for clustering the whole data.

24

Author-produced version of the article published in Expert Systems with Applications, 2016, N°56, p. 349-359. The original publication is available at http://www.sciencedirect.com Doi: 10.1016/j.eswa.2016.03.008 The results for the k-means algorithm are shown in Figures 8 and9. The time ratio drops below 10% when the granularity is higher than 0.05. With the hierarchical algorithm the same ratio is significantly smaller.

445

The average time ratios (in percent) obtained with granularity = 0.01 and for all the databases reduced to 3000 patterns are reported in Table 3. All of them fall between 0.02% and 0.048%, meaning the proposal is 2000 times faster.

Comparison with known algorithms

In order to compare DENDIS with concurrent algorithms, 12 sampling rep- The results of these extensive experiments are summarized to highlight the main trends.

The sampling time and the quality of representation are analyzed.

Sampling time. The k-means (A4) and tree (A8) algorithms are always faster than the former ones, and can yield high RI, but with a higher sample size. The competitors that meet both criteria of scalability and accuracy are A9, A10 and A12.

Complementary comparison of the best algorithms. The best algorithms (A9, A10, A12 and DEN DIS) are now compared according to their behavior in presence of noise.

A synthetic dataset (40000 patterns in R 2 ) with natural clusters of different cardinalities (from 1000 to 5000 items) was generated. An important level of noise, 4%, has been added. Noise values are computed independently in each dimension, according to the whole range of the given feature: noise j = min j +U [0, +1] * (max j -min j ). Each sampling algorithm is applied and the k-means algorithm is run with k = 10.

can note that the sample size increases with the granularity parameter, but not in a proportional way.

A12 and DEN DIS appear to be the most robust to noise as they yield the best results for all the trials. This is not so surprising as both are based upon similar concepts. In the A12 approach, dense areas are first covered by a uniform random sampling, then the initial patterns represented in the sample are no more considered in the next iterations. The corresponding sample sizes are also comparable, even if DEN DIS samples are always smaller. The main difference between both algorithms is the computational time: A12 is significantly slower than the proposal.

Figure 11 shows that DEN DIS is still able to identify and represent the data structure even with a high level of noise. The 129 representatives, plotted in orange, only belong to the clusters and ensure shape coverage.

Conclusion

A new sampling for clustering algorithm has been proposed in this paper.

DENDIS is an hybrid algorithm that manages both density and distance con- These experiments show that DENDIS has some nice properties. It is parsimonious. The sample size is not an input parameter, it is an outcome of the sampling process. It is, as expected, smaller than the theoretical bound suggested in [START_REF] Guha | Cure: An efficient clustering algorithm for large databases[END_REF] a given level of accuracy. Even if the dimensionless parameter is meaningful to the user and impacts accuracy, the relationship between both is not really modeled. From an empirical point of view, the challenge consists in finding the appropriate mechanisms without penalizing the running time which is a quite interesting feature of the proposal. The first iterations of the algorithm are the most computationally expensive. The starting steps can be improved.

From a more conceptual view, a similar approach than the one used to estimate the number of distances could be useful to investigate other research directions, for instance the relationship between the granularity, the sample size and the accuracy, based on a real time estimation of clustering cost of the whole data.

1

  '\' stands for the set difference operation. 7 Author-produced version of the article published in Expert Systems with Applications, 2016, N°56, p. 349-359. The original publication is available at http://www.sciencedirect.com Doi: 10.1016/j.eswa.2016.03.008 Algorithm 1 The density-based sampling algorithm 1: Input: T = {xi}, i = 1 . . . , n, gr 2: Output: S = {yj}, Tyj, j = 1, . . . , s 3: Select an initial pattern xinit ∈ T 4: S = {y1 = xinit}, s = 1 5: ADD=TRUE, K = 0.2, Wt = n gr 6: while (ADD==TRUE) do 7: for all x l ∈ T \ S do 8: Find dnear(x l ) = min y k ∈S d(x l , y k ) 9: Ty k = Ty k ∪ {x l } {Set of patterns represented by y k } 10: end for 11: for all y k ∈ S do 12: Find dmax(y k ) = max xm∈Ty k d(xm, y k ) 13: Store dmax(y k ), xmax(y k ) {where dmax(y k ) = d(xmax(y k ), y k )} Sort y (1) , . . . , y (s) with |Ty (1) | ≥ . . . ≥ |Ty (s)

  Run the post processing algorithm {Algorithm 2} 32: return S, Ty k , k = 1, . . . , s volume. At the beginning of the process, the d max values are quite high, as well as the cardinalities |T y k |. The fraction of minimum volume is then limited by an upper bound, K. This allows for the space to be covered in an homogeneous way, the d max values tend to a lower mean with a lower deviation. In the last steps of the process, α k dynamically promotes dense areas in order for the sample to reflect the original densities: the larger the cardinality the smaller α k and thus the constraint on the induced volume (line 21). The constant value, K = 0.2, has been empirically defined from experimental simulations.

Figure 1

 1 Figure 1 illustrates the impact of the constraint on the induced volume (Algorithm 1, line 22). The data (blue) are well structured in four clusters of heterogeneous densities. The six first selected representatives are plotted in red, while the following ones appear in black. The small groups, in the bottom part of the figure, are denser than the others. The results for these two clusters are displayed in a zoom version in Figure 2, with and without this constraint. Without the mentioned constraint, the new representatives are located in the denser areas until the number of attached patterns become smaller than the W t threshold. When the constraint is active the number of representatives in the dense area is limited by the induced volume. Density and distance are both useful to avoid an over representation in dense areas.

Figure 2 :

 2 Figure 2: Zoom of the two densest clusters

  remains in T yj , no change needs to be made. Only two distances are needed to check the inequality, and discard any further calculations in the case of no change. In our algorithm, there is no need to check this inequality for all the initial patterns. For each representative, y k , d max (y k ) is stored. If d(y k , y * ) ≥ 2 d max (y k ), meaning the furthest initial pattern from y k remains attached to y k , this also holds ∀x i ∈ T y k . Then, these representatives and their attached patterns are not concerned by the main loop of the algorithm (Algorithm 4, line 8-9). When this is not the Algorithm 4 The optimized density-based sampling algorithm 1: Input: T = {x i }, i = 1 . . . , n, g r 2: Output: S = {y j }, {T yj }, j = 1, . . . , s 3: ADD=TRUE, W t = n g r 4: Select an initial pattern x init ∈ T 5: S = {y 1 = y * = x init }, s = 1 6: d near (x i ) = ∞, i = 1 . . . , n 7: while (ADD==TRUE) do 8: F = {T yj |d(y j , y * ) ≥ 2 d max (y j )} 9: for all x l ∈ T \ {S ∪ F } do 10: if (d near (x l ) > 0.5 d(y(x l ), y * )) then 11: Compute d = d(x l , y * ) 12: if (d < d near (x l )) then 13: T y * = T y * ∪ {x l }, T y(x l ) = T y(x l ) \ {x l } 14: d near (x l ) = d, y(x l ) = y * > d max (y * )) then 17: x P = x(x s ), Y P = y * 18: d max (y * ) = d, x(y * ) = x l

  son. Two representative clustering algorithms are tested, the popular k-means and one hierarchical algorithm. The resulting sample size as well as the computational cost are carefully studied as they have a strong impact on the practical use of the algorithm. In this paper we use a time ratio to characterize the CPU cost. It is computed as the sampling time added to the clustering on sample time and divided by the time required to cluster the whole data set. Twenty databases are used, 12 synthetic, S#1 to S#12, and 8 real world data sets, R#1 to R#8. The synthetic ones are all in two dimensions and of various shapes, densities and sizes: {2200

Figure 3 :

 3 Figure 3: The twelve synthetic data sets, S#1 to S#12

Figures 4

 4 Figures 4 and 5 shows the reduction ratio of the size of the sample sets for each of the synthetic and real world data sets for different values of granularity.

Figure 4 :

 4 Figure 4: Size reduction ratio for the synthetic data sets

Figure 5 :

 5 Figure 5: Size reduction ratio for the real world data sets

430Figure 6 :

 6 Figure 6: The RI with the k-means algorithm for the synthetic data sets

Figure 7 :

 7 Figure 7: The RI with the k-means algorithm for the real world data sets

Figure 8 :

 8 Figure 8: The time ratio (%) with the k-means algorithm for the synthetic data sets

Figure 9 :

 9 Figure 9: The time ratio (%) with the k-means algorithm for the real world data sets

Figure 10 :

 10 Figure 10: Leader behavior according to λ *

  cepts. Even if the basics of these concepts are known, their specific use produces a really new algorithm able to manage high density as well as sparse areas, by selecting representatives in all clusters, even the smaller ones.It is density-based: at each iteration the new representative is chosen in the most populated group. It allows for catching small clusters: the new representative is the furthest, from the representative, of the attached patterns. There is no need to estimate local density, neither to define a neighborhood. The attraction basin is dynamically determined thanks to hidden parameters induced from the data.DENDIS is driven by a unique, and meaningful, parameter called granularity: it is dimensionless and represents the minimal proportion of data a group has to include to be split. Combined with the data size, it is quite similar to the minimal size of a node in a tree. Without any additional constraint, the representatives would tend to have a similar number of patterns. To manage different local densities, and to avoid over representation in high density areas, a volume restriction is added for group splitting. It is based upon the average induced volume estimated by the maximum within group distance. This makes the sample size independent on the data size, depending only on the data structure. Others parameters are used, but they are inferred from data. This makes the algorithm really easy to tune.The inner structure of the algorithm, especially the selection of the furthest item in the group as a new representative, favors the use of the triangle inequality because a new representative only impact its neighborhood. Even if the exact number of avoided computations cannot be rigorously defined, an upper bound can be estimated under weak assumptions. It shows that only 5% of the total number of distances are really computed.The algorithm behavior has been studied using 12 synthetic and 8 real world datasets. It has been compared to 12 concurrent approaches using the real world data sets according to three criteria: the sample size, the computational cost and the accuracy. The latter was assessed by the Rand Index, for two types of clustering algorithms, k-means or hierarchical: the partitions resulting from the clustering on the sample against the ones yielded by the same clustering method on the whole set.

10

  Author-produced version of the article published in Expert Systems with Applications, 2016, N°56, p. 349-359. The original publication is available at http://www.sciencedirect.com Doi: 10.1016sciencedirect.com Doi: 10. /j.eswa.2016.03.008 .03.008

	235
	fit the data structure, some methods propose an adaptive process. Attraction
	basin can also be induced thanks to a recursive partitioning, like in trees or
	dynamic grids, or by a probabilistic process. In the k-means++ (Arthur & Vas-
	silvitskii, 2007) a new seed is selected according to the probability computed
	11

Figure 1: Impact of the induced volume constraint 4. Conceptual comparison with alternative approaches DENDIS shares some ideas with known algorithms but the way they are combined is really innovative. This can be highlighted by describing the main characteristics of the proposal. 230 It is density based. Many methods estimate the local density thanks to a parameter that defines the attraction basin either by counting items to induce a corresponding volume, like the popular K-nearest-neighbors algorithm, or by defining a volume, e.g. Parzen window, Mountain method (Yang & Wu, 2005), or static grids. In this case, the result is highly dependent on the setting. To Author-produced version of the article published in Expert Systems with Applications, 2016, N°56, p. 349-359. The original publication is available at http://www.sciencedirect.com Doi: 10.1016/j.eswa.2016.03.008

  This also holds for other biased random methods like k-means++ or Feldman. DENDIS is aware that noisy representatives are likely to be selected as they are chosen at the group border. A post-processing step is dedicated to noise management.It is little sensitive to randomness. It is well known that random use highly impacts processes. This is true for k-means initialization, but also holds for other algorithms like Feldman. In k-means++, as denser areas have a higher probability to be selected, this impact is reduced. In DENDIS, only the first representative is randomly chosen. After a few iterations, the same border items are selected. DENDIS could be made fully deterministic by adding an extra iteration to select as the first representative the furthest from the minimum (or The granularity parameter is not dependent on the size, like the one of uniform random sampling, nor on the number of groups, like in the k-means, k-means++ or fft algorithms. It is a dimensionless number whose meaning is very clear: it represents the minimal proportion of data a group has to include to be split. Combined with the data size, it is quite similar to the minimal size of a node in a tree.Author-produced version of the article published in Expert Systems withApplications, 2016, N°56, p. 349-359. The original publication is available at http://www.sciencedirect.com Doi: 10.1016sciencedirect.com Doi: 10. /j.eswa.2016.03.008 .03.008

	Granularity is not directly linked to accuracy. As there are several internal pa-
	rameters induced from data, even if accuracy is sensitive to granularity, the re-

is little sensitive to noise. Looking after small clusters may result in selecting noise. Introducing a bias according to local density to favor sparse areas 12 Author-produced version of the article published in Expert Systems with Applications, 2016, N°56, p. 349-359. The original publication is available at http://www.sciencedirect.com Doi: 10.1016/j.eswa.2016.03.008 increases this risk. maximum) in each dimension.

It is data size independent. Density based methods aim to design groups with a similar density: the sample size increases with the data size. This is not the case for neighborhood based methods: in this case the sample size only depends on the neighborhood one. Thanks to the constraint on the induced volume, DENDIS adapts the sample size to the data structure not to the data size.

It is driven by one meaningful parameter. Most of sampling methods require several parameters which are more meaningful to the computer engineer than to the user and remain difficult to set. DENDIS, like k-means++ or fft, needs only one. lationship between both is not modeled. An intermediate value, e.g. g r = 0.01, 13

  Author-produced version of the article published in Expert Systems with Applications, 2016, N°56, p. 349-359. The original publication is available at http://www.sciencedirect.com Doi: 10.1016/j.eswa.2016.03.008Algorithm 3 The first two loops are combined into a single one

sonable: n+2s distances between the representatives are stored: n d near (x)and s d max (y) as well as the corresponding elements, y for d near (x), and x for d max (y). 14 1: while (ADD==TRUE) do 2:

  They are of various sizes and space 18 Author-produced version of the article published in Expert Systems with Applications, 2016, N°56, p. 349-359. The original publication is available at http://www.sciencedirect.com Doi: 10.1016/j.eswa.2016.03.008

Table 1 :

 1 gorithm, either k-means or the hierarchical one, is run with the whole set and the sample set. Then the resulting partitions are compared using the Rand 19 Author-produced version of the article published in Expert Systems with Applications, 2016, N°56, p. 349-359. The original publication is available at http://www.sciencedirect.com Doi: 10.1016/j.eswa.2016.03.008 The eight real world data sets

		Size Dim Name
	R#1	434874	4 3D Road Network
	R#2	45781	4 Eb.arff
	R#3	5404	5 Phoneme
	R#4 1025010	10 Poker Hand
	R#5	58000	9 Shuttle
	R#6	245057	4 Skin Segmentation
	R#7	19020	10 Telescope
	R#8	45730	10 CASP

  This situation can be explained by the stochastic part of the test protocol and the data structure: two large clusters with different densities, and a very dense tiny one. In this case, with a fixed small number of clusters, different from the 20 Author-produced version of the article published in Expert Systems withApplications, 2016, N°56, p. 349-359. The original publication is available at http://www.sciencedirect.comDoi: 10.1016Doi: 10. /j.eswa.2016.03.008 .03.008

Table 3 :

 3 Author-produced version of the article published in Expert Systems with Applications, 2016, N°56, p. 349-359. The original publication is available at http://www.sciencedirect.com Doi: 10.1016/j.eswa.2016.03.008 Time ratio with the hierarchical algorithm

	450
	resentative approaches were considered.
	25

Table 4 :

 4 The twelve concurrent approaches

		Name	Param(s)		Range
	A1 A2 A3	Uniform Random Sampling Leader (pioneer) (Ling, 1981) Leader (improved) (Viswanath et al., 2013)	|S| = t = d m |T | λ * λ * |S| = |T | λ * , c =	|T | µ *	[10, 500] [2, 10] [10, 500], [2, 5]
	A4 A5	k-means sampling(Xiao et al., 2014) Kernel sampling(Kollios et al., 2003)	b,|S| = b,|S| =	|T | λ * |T | λ *		[10, 500] [10, 500]
	A6	Grid sampling(Palmer & Faloutsos, 2000)	b, N * cut (axis)		[2, 10]
	A7	k-nearest-neighbors (Franco-Lopez et al., 2001) b, k = λ * |T |		[0.2, 0.5]
	A8 A9 A10 k-means++ (Arthur & Vassilvitskii, 2007) Tree sampling(Ros et al., 2003) Bagged sampling (Dolnicar & Leisch, 2004) A11 fft (Rosenkrantz et al., 1977) A12 Hybrid (Feldman et al., 2011)	b, min size = N * strata , N r = |T | λ * , N * cut |T | λ * |S| = |T | λ * |S| = |T | λ * β * , |S| = |T | λ *	[50, 200], [1, 4] [4, 20], [2, 100] [10, 500] [10, 500] [10, 100], [10, 500]

Table 5 :

 5 Concurrent approaches: Cumulative averaged time (s) over the 8 data sets means clustering were considered but the whole tests have been restricted to the k-means algorithm as some data are not tractable with the hierarchical one.

	A1	A2	A3	A4	A5	A6	A7
	0.004 7.7 858	52	4951 2.3 9651
	A8	A9 A10 A11 A12	DENDIS
	27	2.4 4.3 6.0	2.7	0.5

Table 6 :

 6 Table5summarizes the average (over all the experiments including the different data and partitions) sampling times in seconds. As expected the URS, A1, is the fastest algorithm, but DENDIS is quite swift too, faster than the grid ones (A6, A9) and other competitors (A10 to A12).Quality of representation. The results reported inTable 6 are the best RI, on average, over the 8 real data sets, of all the tested configurations. The maximum of the RI for each data set is highlighted in bold font. When several algorithms have reached the same accuracy, and DENDIS is among this group, the bold font is used in the DENDIS row. Author-produced version of the article published in Expert Systems with Applications, 2016, N°56, p. 349-359. The original publication is available at http://www.sciencedirect.com Doi: 10.1016/j.eswa.2016.03.008 Best Rand Index on average over the real data for each algorithm Author-produced version of the article published in Expert Systems with Applications, 2016, N°56, p. 349-359. The original publication is available at http://www.sciencedirect.com Doi: 10.1016/j.eswa.2016.03.008

	These

The algorithms' performances are highly dependent on the setting as they require several parameters that need to be combined. The concern is particularly checked for the leader methods: they are the most difficult to parameterize as illustrated in Figure

10

. The d m parameter was estimated on a random sample, 10% of the whole set, and computed as: d m = max d(µ, x i ), µ being the average of the set of vectors x i . The results for different values of λ * are shown in Figure

10

. The left part shows the sample size (% of the whole), the right part illustrates the RI variation according to λ * : no monotonicity can be deduced; the best value depends on the data.

Table 7 :

 7 Best concurrent approaches: Detailed comparisons with noise

		Sr-(%) time RI	Sr-(%) time RI	Sr-(%)	time RI
	A9	0.5	318 0.956 0.6	314 0.945 0.83	376 0.948
	A10	0.49	541 0.900 1	1663 0.932 5	30056 0.952
	A12	0.33	1163 0.967 0.59	1225 0.971 1.09	1365 0.986
	DENDIS	0.15	44 0.964 0.23	93 0.987 0.35	113 0.995
	A5 and A7 are too computational expensive. Without additional optimization
	like the bucketing algorithm, which is itself a pre-processing step, they are not
	scalable.

  for uniform random sampling. DENDIS yields comparable accuracy to the most popular concurrent techniques with a similar number, or even fewer, representatives. It is fast. Thanks to an internal optimization, it has a very low computational cost. This scalability property allows for its use with very large data sets. It is robust to noise: a post-processing step remove representatives labeled as noise. Future work will be mainly dedicated to improve the hybrid algorithm to become self-tuning, capable of finding by itself the suitable granularity to reach 33Author-produced version of the article published in Expert Systems withApplications, 2016, N°56, p. 349-359. The original publication is available at http://www.sciencedirect.com Doi: 10.1016sciencedirect.com Doi: 10. /j.eswa.2016.03.008 .03.008

Author-produced version of the article published in Expert Systems with Applications, 2016, N°56, p. 349-359. The original publication is available at http://www.sciencedirect.com Doi: 10.1016sciencedirect.com Doi: 10. /j.eswa.2016.03.008 .03.008

A8 is similar to[START_REF] Ros | Development of predictive models by adaptive fuzzy partitioning. application to compounds active on the central nervous system[END_REF] except that the bins are not fuzzy, and are ordered via their weights until reaching a lower bound. For A12 the input parameters (β and λ) are directly linked to the original parameters δ, ε, k[START_REF] Feldman | Scalable training of mixture models via coresets[END_REF].

Author-produced version of the article published in Expert Systems with Applications, 2016, N°56, p. 349-359. The original publication is available at http://www.sciencedirect.com Doi: 10.1016Doi: 10. /j.eswa.2016.03.008 .03.008 Author-produced version of the article published in Expert Systems with Applications, 2016, N°56, p. 349-359. The original publication is available at http://www.sciencedirect.com Doi: 10.1016/j.eswa.2016.03.008 7 where three of them are reported. In the first one, columns 2-4 in Table 7, the corresponding input setting for these methods is: λ 135 (in the range [134,137] for the four sets and g r = 0.1. Then the input parameter has been set to get a higher sample size, up to 5% for A9, A10, A12. The DEN DIS granularity was 0.03 and 0.008. The reported results in the two last trials are kept in a range where the RI is improved. Beyond this range, even with a 5% size sample, no improvement can be observed, only the running time is different. Using A9 the sample size which yields the best results is below 1%. Using DEN DIS, one Pattern analysis and applications, 8 , 125-138. Zahra, S., Ghazanfar, M. A., Khalid, A., Azam, M. A., Naeem, U., & Prugel-Bennett, A. (2015). Novel centroid selection approaches for kmeans-clustering based recommender systems. Information Sciences, 320 , 156-189.

Zhong, C., Malinen, M., Miao, D., & Fränti, P. (2015). A fast minimum spanning 700 tree algorithm based on k-means. Information Sciences, 295 , 1-17.

Author-produced version of the article published in Expert Systems with Applications, 2016, N°56, p. 349-359. The original publication is available at http://www. sciencedirect.com Doi: 10.1016sciencedirect.com Doi: 10. /j.eswa.2016.03.008 .03.008


B Juanals

J L Minel

Categorizing Air Quality Information Flow on Twitter Using Deep Learning Tools

Keywords: Environmental health, Air quality, Instrumented methodology, Circulation of information, Mediation, Social network, Twitter

Environmental health is an emerging and hotly debated topic that covers several fields of study such as pollution in urban or rural environments and the consequences of these changes on health populations. In this field of intersectorial forces, the complexity of stakeholders' logics is realized in the production, use and communication of data and information on air quality. The Twitter platform is a " partial public space " that can throw light on the different types of stakeholders involved, the information and issues discussed and the dynamics of articulation between these different aspects. A methodology aiming at describing and representing, on the one hand, the modes of circulation and distribution of message flows on this social media and, on the other hand, the content exchanged between stakeholders, is presented. To achieve this, we developed a classifier based on Deep Learning approaches in order to categorize messages from scratch. The conceptual and instrumented methodology presented is part of a broader interdisciplinary methodology, based on quantitative and qualitative methods, for the study of communication in environmental health.

Introduction

Environmental health is an emerging and hotly debated topic that covers several fields of study such as pollution in urban or rural environments and the consequences of these changes on health populations. Its progressive conceptualization reveals divergent positions that may include "an extremely wide range of environmental factors related to the notion of human well-being". The environmental factors analyzed in the work of the French School of Advanced Studies in Public Health (EHESP) fall into four broad thematic dimensions relating to polluted sites and soils, water quality and air quality and habitat; Among these factors, we focused on air quality, which was the subject of many alerts in major cities at the end of 2016 and which is becoming a national concern with the regular peaks of fine particles matter in urban areas.

D R A F T

From a societal perspective, air is one of the "commons" [START_REF] Ostrom | The institutional analysis and development framework and the commons[END_REF] that are described as natural or material resources that can be extended to information and knowledge commons [START_REF] Ostrom | Understanding Knowledge As a Commons: From Theory to Practice[END_REF]. Pooling and sharing these resources raises issues about their modes of governance. Air is a common good that is subject to conflicts of interest. As a result, data and information on air quality become political issues that provoke debate, even clashes, concerning the modes of production and dissemination of these data. In particular, the modes of production and interpretation of these data call for the specification of technical criteria in the distribution and control domains. The specification of measurements is a political, industrial and environmental issue. It is linked to the scientific validity of the selection of pollutants and pollution thresholds that are used. These open data make sense only in the light of standards used to interpret them and to take decisions at European, national and regional levels.

The production and dissemination of these data are regulated. They are part of European regulations and national or regional public policies, interdisciplinary cross-knowledge, militant positions as well as industrial and commercial logics. In France, environmental health (with which air quality is associated) is part of the State prerogatives; it is therefore governed by public health policies.

The European Directive on Ambient Air Quality -Clean Air for Europewas adopted on 14 April 2008; it merged the main Directive (96/62 / EC), the first three specific directives (99/30 / EC, 2000/69 / EC, 2002/3 / EC) and the Council of Europe decision concerning data exchange (97/101 / EC). These legal constraints were gradually applied in France by a 1991 decree then by laws: the so-called Barnier law (1995) and the law on air and the rational use of energy (LAURE Act) of December 30, 1996.

In France, the Ministry of Environment and Sustainable Development no longer centralizes actions in the field of education, awareness raising, production and dissemination of information. Communication initiatives are now carried out at the regional scale defined by the administrative organization in the context of decentralization. In this perspective, the LAURE act stipulates that the State entrusts the monitoring of air quality to approved Non-governmental organizations (NGO) in charge of this surveillance. The result is the distribution of some 40 NGOs on the national territory. These organizations are "monitoring networks" characterized by a hybrid status. They bring together companies, public organizations and NGOs [START_REF] Boutaric | Les réseaux de la qualité de l'air : des associations stratèges de l'action publique[END_REF]. These NGOs are now linked by their status and their missions to the public authorities while maintaining their vocation of integrating the demands of civil society in their initiatives.These developments led the Air Quality Monitoring Associations (AASQA) to build a national federation, ATMO France, in order to become a lobby able to negotiate with national and local authorities on the subject of air quality.

In the US, the Clean Air Act (CAA) is the comprehensive federal law that regulates air emissions from stationary and mobile sources. "Among other things, this law authorizes the Environmental Protection Agency (EPA) to establish National Ambient Air Quality Standards (NAAQS) to protect public health and D R A F T public welfare and to regulate emissions of hazardous air pollutants." 1 .In June 2014, EPA proposed The Clean Power Plan, an Obama administration policy aimed at combating anthropogenic climate change, but in March 28, 2017 Donald Trump, signed an executive order mandating the EPA to review the plan and following his announcement on June 1, 2017, United States withdrawal from the Paris Agreement.

In this legal and regulatory framework, the setting up of a public debate on the implementation of a policy to monitor air quality opens up political questions about the production and the circulation of information on air quality in the public space. In this field of intersectorial forces, the complexity of stakeholders' logics is realized in the production, use and communication of data and information on air quality. The Twitter platform is a " partial public space " that can throw light on the different types of stakeholders involved, the information and issues discussed and the dynamics of articulation between these different aspects.

The purpose of our work is to conceive, by relying jointly on methods anchored in social sciences and digital humanities, a representation of the modes of circulation and distribution of message flows on Twitter about air quality in relation with stakeholders and the content exchanged.

The outline of this paper is the following. First, in Section 2, we present the litterature review and then specify the contribution of the proposed methodology to tackle this field. In Section 3, we will present the specificities and the contribution of our approach, our methodology to collect and analyze flows of tweets and the results from classification analysis. Finally, we conclude in Section 4.

Literature Review and Methodology

In this section, we begin with a review of the literature, and then we present the interdisciplinary and instrumented methodology we developed to conduct the analysis of messages.

Literature Review

As mentioned in [START_REF] Foucault | Automatic classification of tweets for analyzing communication behavior of museums[END_REF], tweet analysis has led to a large number of studies in many domains such as ideology prediction in Information Sciences [START_REF] Djemili | What does twitter have to say about ideology? In: NLP 4 CMC: Natural Language Processing for Computer-Mediated Communication[END_REF], spam detection [START_REF] Yamasaki | A trust rating method for information providers over the social web service: A pragmatic protocol for trust among information explorers, and provider in formation[END_REF], dialog analysis in Linguistics [START_REF] Boyd | Tweet, tweet, retweet conversational aspects of retweeting on twitter[END_REF], and natural disaster anticipation in Emergency [START_REF] Sakaki | Tweet analysis for real-time event detection and earthquake reporting system development[END_REF], while work in Social Sciences and Digital Humanities has developed tweet classifications . However, few studies aim at classifying tweets according to communication classes. They mostly rely on small reference sets analyzed by experts in Information Communication (InfoCom) rather than by Twitter users. Two exceptions worth mentioning are first the work presented in Lovejoy and Saxton [START_REF] Lovejoy | Information, community, and action: How nonprofit organizations use social media[END_REF] in which the authors (Twitter users) analyze the global behavior of nonprofit organizations on Twitter based on three communication classes: Information, Community and Action classes. The second work [START_REF] Lin | Exploring extreme events on social media: A comparison of user reposting retweeting behaviors on twitter and weibo[END_REF] compares the 1 https://www.epa.gov/ D R A F T use of the Chinese Weibo service during a 2013 smog emergency with data on Twitter concerning a weather event in North America. The data collected were hand-coded and the authors discussed the implications of their results for agencies designing social media campaigns to inform and motivate the public affected by those events, which is one of the goals of the agency we are working with.

Recently, several studies on tweet classification have been carried out in NLP. Basically, these analyses aim at categorizing open-domain tweets using a reasonable amount of manually classified data and either small sets of specific classes (e.g. positive versus negative classes in sentiment analysis) or larger sets of generic classes (e.g. News, Events and Memes classes in topic filtering). The advantage of NLP approaches is that they can automatically classify large corpora of tweets. Until recently, the most commonly used models were supervised learning, Support Vector Machine (SVM), Random Forest, Gradient Boosting Machine and Naive Bayes (NB). In supervised machine learning, features are extracted from tweets and metadata and then vectorized as training examples to build models.

An Instrumented Methodology using Convolutional Neural Networks

The main drawback of shallow supervised machine learning approaches presented above, is that they require a very time consuming step to identify linguistic or semiotic features and raise issues about the relevance of these features. Recently, new approaches based on Deep Learning techniques and especially on convolutional neural networks (convets), which no longer require researchers to identify features, have been proposed . A second advantage of convets is that they obtain better results in terms of accuracy than shallow machine learning systems [START_REF] Kim | Convolutional neural networks for sentence classification[END_REF][START_REF] Manning | Computational linguistics and deep learning[END_REF] . It is for these reasons that we developed a classifier based on convets. The proposed methodology, based on convets, aims to describe and analyze the informational and communicational dynamics at work on the Twitter platform. It explores the circulation patterns of message flows and exchanges, apprehended as a dynamic process, as well as the relationships which are established between different stakeholders. Our aim is to question the forms of engagement, participation and relationships between organizations and audiences by analyzing the flow of their messages. We consider that the field of environmental health and the socio-technical device Twitter contribute to configuring the relations and the interactions between the participants. In this perspective, hashtags on Twitter may be seen as meeting points of different categories of stakeholders interested in the same themes while being anchored in different spheres -the environment and health, politics, the media, industry, the economy, etc.. The architecture of our classifier is composed of several layers as shown on figure 1. The first layer is a pre-trained word embedding as proposed by [START_REF] Mikolov | Efficient estimation of word representations in vector space[END_REF] with a kernel that matches the 5 words used as neighbors. A word-embedding is a distributed representation where each word is mapped to a fixed-sized vector of continuous values. The benefit of this approach is that different words with a similar meaning will have a similar representation. A fixed-vector size of 100 was D R A F T chosen. The following layers, a Conv1D with 200 filters and a MaxPooling1D are based on the works reported in [START_REF] Kim | Convolutional neural networks for sentence classification[END_REF][START_REF] Brownlee | Deep Learning for Natural Language Processing[END_REF]. The back-end of the model is a standard Multilayer Perceptron layer to interpret the convets features. The output layer uses a softmax activation function to output a probability for each of the three classes affected at the tweet processed (see Section 3.3.1). Finally, only the class with the highest probability is kept. We would like to point out several important features : first, although this classifier is not a very deep convets, the results are satisfactory (see section 3.2.1) and moreover it does not require significant computing resources; second, the different parameters of the architecture were determined after several trials and errors; and finally, building such a network does not require advanced programming, so it is within the reach of an interdisciplinary team.

We implemented our methodology by building a workflow based on the open access tools Gephi2 (graph visualization), Neo4j3 (graph mining), Scikit-learn 4and Keras library (deep learning) 5 . We also developed some scripts python to manage the interoperability between all these different tools.

D R A F T 3 Analyzing Tweets about Air Quality

Data Acquisition The data acquisition stage consisted in harvesting tweets with the following hashtags :the hashtag #Air and one other hashtag among the following list :#pollution, #santé (health), #qualité(quality) or #environnement(environment). Twitter maintains an Application Programming Interface (API) that returns approximately 200 features about a tweet. We developed a Python script , based on the Twarc module proposed by Ed Summers (http://github.com/docnow/twarc) using the search option of Twitter API.

Our analysis focuses on Twitter messages (called tweets) sent by accounts of organizations and non-institutional stakeholders. A first step was to build a terminology to describe the objects studied according to three dimensions: the message, the stakeholders, and the forms of stakeholder participation.

Concerning messages, we will call a message sent by a twitter account an 'original tweet' and an original message sent by an account different from the issuing account a 'retweet'. The current Twitter API gives access to the original tweet (and its sending account) of a retweet. The generic term tweet includes 'original tweet' and 'retweet'.

Regarding stakeholder qualification, we distinguished Twitter accounts, accounts managed by institutions (called 'organizational account'), and accounts managed by individuals (called 'private account'). This distinction was carried out by human analysts based on the description field filled out by the account holder. When this field was unfilled, the private account category was assigned.

In this paper, we limit the analysis to French tweets, by using the "lang" features in Tweeter API, sent between the first of November 2017 and the 17th of March 2018. This period of time is considered as a proof of concept and we intent to use the classifier to process all the tweets that will be sent during the year 2018.

The main figures are the following: 3027 tweets of which 30% of original tweets and 70% of retweets sent by 902 participants (405 organizational accounts, 497 private accounts). More specifically : 41% of organizational accounts and only 25% of private accounts produced original tweets. Participation for private accounts was largely limited to the action of retweeting (75% of tweets) the messages sent by the institutional partners. A peak during the week 46 in 2017 is the consequence of the COP22 event (World Climate Conference) which was the major event of the observed period of time.

Analyzing the modes of involvement and interaction between organizational and private accounts

Categorical analysis relying on automatic classification is a relevant processing method to characterize the semantics of the messages as it makes possible to analyze the modes of engagement of the stakeholders on Twitter. Automatic classification implies a prior human classification (supervised machine learning).

Taking into account the size of the corpus of tweets, a human analysis would still have been possible but first, as mentioned in [START_REF] Lachlan | Screaming into the wind:examining the volume and content of tweets associated with hurricane sandy[END_REF], the inter-coder minimum

D R A F T
reliability is usually around 0.74, and secondly, we intend to process in real time all the tweets that will be sent during the year 2018. These two reasons argue in favour of developing an automatic classification.

In order to build a classifier, a classification analysis of the contents of a sample of 350 randomly chosen original tweets was carried out in two stages. First, a team composed of one linguist and one researcher in communication analyzed the sample of tweets to determine the classes in which to categorize the tweets. Based from three classes were identified ("informative", "promoting", "humorous" (in the sense of emotional or expressive ).

"Informative " tweets were those providing information concerning technical aspects of air quality or specific mitigation efforts.

If an advertisement, generally associated with a link on a Web site was present, the tweet was categorized as "promoting".

"Humorous" tweets contained the expression of emotions (such as worry, anger, dread) or political comments. It must be noted that there were no tweets containing insults. Consequently, 350 tweets were annotated by hand by the same two experts according to the categories defined in the previous step.

In the second stage, a classifier, based on convets (see Section 2.3), was trained on the annotated samples. It must be pointed out that none modification of the raw text of tweets was carried out, that is to say, we did not use stop words list or stemming transformation. A simple tokenizer from the Keras library was used to compute embedded vectors associated with tokens. The training loss decreases with every epoch, and the training accuracy increases with every epoch; to prevent overfitting, the training was stopped after ten epochs.

Results of the evaluation using the standard cross-validation 10-fold test [START_REF] Kohavi | A study of cross-validation and bootstrap for accuracy estimation and model selection[END_REF] gave an accuracy of 0.97 in line with the state of the arts [START_REF] Kim | Convolutional neural networks for sentence classification[END_REF].

The classifier was applied to the corpus of all tweets to categorize them. Figure 2 show the findings. There is a main difference between institutional and individuals accounts concerning the "humorous" class. Private accounts sent twice as many "Humorous" tweets as institutional accounts. Similarly, institutional accounts sent much more "Promoting" tweets.

Analyzing Networks of Accounts

Observing the flow of information through the circulation of messages involves looking at the modes of stakeholder participation. They are materialized in information-communication practices. To answer this question, the analysis is based on the classification of the accounts.

In order to characterize Twitter accounts we used some of attributes proposed by [START_REF] Juanals | Information flow on digital social networks during a cultural event: Methodology and analysis of the "european night of museums 2016" on twitter[END_REF]. The attribute "relayed" is assigned to an account if at least one of its tweets was retweeted or quoted . The "relaying" attribute is assigned to an account if the account retweeted or quoted at least one tweet. The "mentioned" attribute is assigned to an account if its Twitter account name was mentioned at least once in a tweet. And finally, the attribute "passing" is assigned to an account if it was both "relayed" and is "relaying"; this attribute is computed as the product of the "relayed" and "relaying score" .

D R A F T

Fig. 2. Comparing tweets classification

As pointed out by [START_REF] Juanals | Information flow on digital social networks during a cultural event: Methodology and analysis of the "european night of museums 2016" on twitter[END_REF], the value of this index is not significant in itself; it simply provides a means of comparing accounts. There are several ways to compute the importance of a node in a network [START_REF] Brandes | Network Analysis[END_REF]. Network theory proposes the notion of degree and betweenness centrality. The degree is the sum of the indegree and the outdegree. But from our point of view, an influencer must be both. Vertices with high betweenness have control over information passing between others vertices. A vertex can have quite a low degree, be connected to others that have a low degree and still have high betweenness. Vertices in roles like this are sometimes referred to as brokers because they play the role of a bridge. But from our point of view, they are not necessarily influencers. For all these reasons, we preferred to use the passing score proposed by [START_REF] Juanals | Information flow on digital social networks during a cultural event: Methodology and analysis of the "european night of museums 2016" on twitter[END_REF], which is the product of the indegree and the outdegree. The hypothesis is that an account with a high passing score is a key influential user who actively participates in the circulation of information. We indentified six top accounts and a remarkable point is the non-correlation between their passing score and their number of followers. The Kendall-correlation computed on these six passing accounts is 0.04761, i.e. is close to zero.

The list of the top six passing accounts illustrates our description of the stakeholders (see section 1) who have a hybrid status, both public and private. The analysis of these passing accounts makes it possible to identify some of their characteristics. These are all accounts of organizations with the exception of one influencer.

@Ambassad Air is the official account of an operation run by the city of Rennes, located in the West of France, and the House of Consumption and the Environment (in connection with the other associative actors and citizens) mobilizing inhabitants about the air quality in Rennes. @Anne Hidalgo is the official account of the mayor of the city of Paris who is also the chairman of @C40Cities and @AIMFrancophones. Since her election in 2014, she has promoted a very strong policy about air quality. The number of her followers (1 375 410), twenty times higher than the second passing account (in followers number), attests her D R A F T notoriety. @ARS Paca is the official account ot the Regional Health Agency of the South of France. It is an autonomous public institution at the administrative and financial level. It ensures coordination between the services of the State and the Health insurance by grouping several structures dealing with public health and the organization of care'. @INERIS is the official account of the French National Institute of Industrial Environment and Risks. @RennesVilleMetropole is the official account of the city of Rennes, located in the West of France. It must be pointed out that the city of Rennes is also involved in the @Amabassad Air account. @ATMOFRANCE is the official account of the network of associations authorized to monitor air quality. French law has entrusted this network (see Section 2.1) with the responsibility for implementing air quality monitoring and public information. @Charlotte Marchandis is the private account ("My tweets are only my commitment") of an elected member of Rennes City Council, chairman of @VillesSanteOMS who ran for the French presidential election in 2017.

It is remarkable that the number of followers of these passing accounts extends over a scale of 1 to 3300 and that these key influential accounts do not share their communities of accounts.

Conclusions

The construction of an instrumented methodology for the analysis of the flow of messages about air quality on the Twitter platform reveals the complexity of this object of study, which led us to choose a multi-dimensional approach to be able to apprehend it. This research is part of a broader framework of ongoing work on the evolution of environmental communication in the public space.

We developed a classifier based on convolutional neural networks to categorize the flow of tweets. This classifier will be running throughout 2018 year in order to feed a National agency in charge of informing inhabitants and changing their behavior.

Acknowledgments

This study is partially funded by iGlobes (UMI 3157).

Fig. 1 .

 1 Fig. 1. Architecture of the convets classifier

https://gephi.org/

https://neo4j.com/

http://scikit-learn.org/stable/

https://keras.io/