Keywords: Clustering, Partition-based clustering, Density-based clustering, Cal-culation time acceleration Résumé Regroupement, Regroupement

encadrants et enseignants que j'ai pu avoir. Mes sincères remerciements vont également aux membres du jury qui m'ont accordé l'honneur de participer à l'évaluation de ma thèse. Je remercie particulièrement les rapporteurs Mme Fadila Bentayeb et M. Ladjel Bellatreche d'avoir accepté de rapporter soigneusement mon travail. Je remercie également Mme Josiane Mothe et Mr. Pascal Poncelet pour avoir accepté avec grand intérêt d'examiner mes travaux de thèse. J'exprime mes remerciements pour Robin Cugny pour son aimable collaboration durant mes travaux de recherche, pour son sérieux et sa persévérance incontestables et surtout pour les nuits blanches passées ensemble à rédiger avant les deadlines. Je remercie chaleuresement Capgemini et ses collaborateurs de m'avoir accueilli. Je remercie également ma responsable de Capgemini Flore Mounier pour son excellent encadrement et son accompagment durant toute la période de ma thèse. Je remercie également Luis de Juan pour ses précieux conseils. Je remercie aussi Daniel Sandrine, responsable du pôle scientifique, pour tout le soutien qu'elle m'a apporté et son souci de me faciliter le déroulement

 and𝑑1). The circles represent the points of the dataset. The 𝑚𝑎𝑥 (resp. 𝑚𝑖𝑛) function returns the maximum (resp. minimum) of the values in each dimension. Although the example deals with a two-dimensional space, the hyper-rectangle can also be defined in a space of more than two dimensions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III.12Example of the Kd-tree instantiation method on a two-dimensional space.

The method is also applicable to spaces of more than two dimensions. . . . III.13Process of hierarchical bottom-up merging of clusters. Square shapes are leaves, while circle shapes are internal nodes. The merging process starts with the leaves and gradually and hierarchically reaches the root. The leaves only play the role of children while the internal nodes are first parents and then children. Each color, involving three nodes, represents a fusion operation.

The child nodes are processed if they are not already, then the father node is processed in turn using the results of its child nodes.

I.1 Research context I.1.1 Classification

Classification of objects is an important human activity. Indeed, every day, classification is part of our learning process; e.g., the child learns to differentiate man from woman, cat from dog, truck from car etc. In computer science, this classification is automated and constitutes a sub-domain belonging to machine learning [START_REF] Hastie | Introduction[END_REF]. The latter cuts across several scientific fields such as biology, speech processing, image processing etc. It has enabled them to gain new fundamental knowledge and thus has enabled them to solve significant problems.

There are three main types of classification. Supervised classification [START_REF] Alpaydin | Introduction to Machine Learning[END_REF] classifies objects while knowing a priori their nature. In a supervised vehicle classification, each object's label or nature is known in advance; e.g., motorbike, car.

In this category, the task consists in establishing a model that best represents the data, and then use it to make predictions about labels of new unlabelled objects not yet seen.

In unsupervised classification [START_REF] Berkhin | A Survey of Clustering Data Mining Techniques[END_REF], objects are not labeled. It consists of finding underlying structures that best represent the nature of different objects. In semi-supervised classification [START_REF] Zhu | Semi-supervised learning literature survey[END_REF], there are labeled and unlabelled objects.

Those that are labeled are used, via strategies, to improve unsupervised classification and to allow a supervised classification alternative when not all objects are labeled.

The advantage of this category is that it provides some knowledge in advance about the properties of certain structures that are useful for the first two types of classification.

It also reduces the human task of expert manual labeling in the process of supervised classification.

This manuscript focuses on unsupervised classification and, more specifically, its important sub-domain, named clustering [START_REF] Aggarwal | Data Clustering: Algorithms and Applications[END_REF].

I.1.2 Clustering

Clustering is one of the most useful data analysis tasks to discover interesting groups and patterns in the underlying data. In clustering, the objective is to partition a set of points (also called objects, observations or simply data points) into groups (clusters) so that the points in a cluster are more similar to each other than the points in different clusters (Figure I.1). Each point is described by attributes that could be called dimensions. To get a better idea of how clustering has been used in practice, below are two different lists of use cases. In the first one clustering is generally a pre-processing tool for other data processing methods (1), while in the second one it is an essential solution in its own right in several application areas (2).

(1) Clustering as an pre-processing tool: • data summarization [START_REF] Kleindessner | Fair k-center clustering for data summarization[END_REF]: data compression to give compact and easier to interpret representations. Also, compression leads to a reduction in the use of memory space. Different strategies are implemented more or less explicitly to ensure the level of compromise between the loss of relevant information and memory gain;

• labeling [START_REF] Trivedi | The utility of clustering in prediction tasks[END_REF]: the user may have to opt, for a specific task, for a supervised classification method. However, this requires the data are labeled.

The unsupervised classification is integrated into a pre-processing phase in which it puts the points in groups. From then on, each group is associated with a label.

After the end of the pre-processing phase, the data and their associated labels are consumed by the supervised classification method;

• outlier detection [START_REF] Hodge | A survey of outlier detection methodologies[END_REF]: outliers are a portion of data, which, due to their characteristics, are abnormally different from the majority of other data in a dataset. These outliers can lead, the methods processing the dataset, to biased results. Clustering is called upstream of these methods to clean the outliers from the dataset. However, others tasks are developed specifically to identify outliers that are not considered as errors or biases but rather as phenomena in their own right; e.g., fraudulent transactions. In this case, clustering is not a cleaner but rather a detector of rare phenomena.

(2) Clustering in different application areas:

• genetics [START_REF] Kiselev | Challenges in unsupervised clustering of single-cell rna-seq data[END_REF]. with the massive collection of genomic data due to new biological techniques developed in recent years, different diseases have been categorized according to different gene expression levels. In this way, a disease could be rapidly detected early on via information obtained by the group;

• marketing [START_REF] Huang | Marketing segmentation using support vector clustering[END_REF]. given an e-commerce site, its customers are grouped into segments according to their characteristics. Each segment is a group of customers with similar tastes. These segments are targeted according to the product that the site is trying to sell with maximum gains. This technique leads to the facilitation or even abstraction of the conversion step from hesitant or uninterested customers to buying customers.

There are many other application domains using clustering, such as health [START_REF] Thanh | A novel clustering algorithm in a neutrosophic recommender system for medical diagnosis[END_REF], aeronautics [START_REF] Yang | Examining the capability of reanalyses in capturing the temporal clustering of heavy precipitation across europe[END_REF], information retrieval [START_REF] Chifu | Word sense discrimination in information retrieval: A spectral clustering-based approach[END_REF], document classification [START_REF] Amine | Concept-based clustering of textual documents using SOM[END_REF], databases [START_REF] Bentayeb | Rok: Roll-up with the k-means clustering method for recommending OLAP queries[END_REF] etc.

I.2 Research problems

Clustering is a powerful and useful tool for a wide range of use cases. However, it has to face the different challenges to be successful for the areas in which it is called. Despite the development of successful clustering algorithms, they are gradually becoming insufficient for various reasons; i.e. there is a continuous technological advancement, the amount of data collected by modern companies is rapidly increasing, and the data is becoming more and more complex. Clustering is forced to adapt to these developments to meet the needs of data scientists and enterprises. There are two main aspects to consider when evaluating a clustering method: its execution time and data clustering quality. The quality depends essentially on the algorithm used as well as the users' expectations. These two aspects guide the way to meet the challenges. These are diverse and each of them is treated in a specific way. Below are the challenges:

• number of points. Clustering algorithms must produce a result in a reasonable amount of time relative to the number of points contained in the dataset. This is even more true when the method is used as a pre-processing tool for more expensive tasks such as deep learning tasks;

• number of dimensions. This data characteristic is important because it could make a clustering method ineffective when the number of dimensions is relatively large. Indeed, data analysis becomes too complicated because the distances between points tend to become more uniform. In addition, each dimension brings its share of errors and implies biases in the clustering algorithm used.

• data distribution. The way in which points are arranged in a data space brings involved different issues and, consequently, the development of different clustering methods. These issues are also diverse:

outliers. datasets are not always clean, especially for real ones. They may contain errors such as input errors, malfunctions of measuring devices, or data collection. In addition to these errors, some data points have particular characteristics compared to other data and errors. They could correspond to a different nature or even be isolated from the majority of the data. Their identification may be necessary for the success of certain tasks. Therefore, algorithms should be able to work in the presence of outliers, at best, to differentiate between errors and rare phenomena relevant to data scientists;

cluster imbalance. clusters of points in the dataset can be of different sizes.

They are a source of difficulty for algorithms because small clusters can be confused with outliers or even absorbed by large clusters. In this sense, knowledge or detection of certain phenomena could be neglected. Besides, the results may be biased and not reflect the data's natural reality and the way the data was generated;

cluster forms. Depending on the source that generated the clusters, each cluster of data has a particular form to it or common to other clusters in the same dataset. The form in itself is a significant difficulty in clustering because it implies three assertions: a priori from the launch of a chosen clustering algorithm, the shapes of the clusters are known, not known, or partially known. In the case where the clusters' forms are not known, robust strategies with the fewest possible assumptions about the data must be implemented to best approach the cluster shape's true nature;

cluster number. many algorithms require the number of clusters to be filled in before the algorithm is run. This information is difficult to obtain and requires a deep knowledge of the dataset. This is often not the case when the algorithm is used as a tool to explore the data before doing specific processing. Giving an incorrect cluster number compared to the data's reality leads to a partitioning of the data that is not of good quality or even not useful.

Generally, to meet these challenges with significantly more performance and efficiency, new alternatives to existing clustering algorithms suffering from specific difficulties should be implemented, or existing algorithms should be revised to make them more robust. This thesis makes contributions to both approaches.

Different clustering paradigms exist [START_REF] Aggarwal | Data Clustering: Algorithms and Applications[END_REF]. Their difference is explained by the fact that data is not labeled. So, each paradigm brings its own rules to establish its cluster definition and its strategies for partitioning a dataset. In this thesis, the focus is essentially on the paradigms of centroid-based [START_REF] Reddy | A Survey of Partitional and Hierarchical Clustering Algorithms[END_REF] and density-based clustering methods [START_REF] Kriegel | Density-based clustering[END_REF]. We tackle the two paradigms on different issues.

Centroid-based methods consider that a cluster has a centroid that best represents the points of the same cluster. Indirectly they minimize an objective function, i.e., they minimize as much as possible for each cluster the variance between the points and the centroid (intra-cluster variance). They are based on an iterative approach, i.e., at each iteration, the intermediate solution is improved until convergence, i.e., the maximum possible minimization of the objective function. However, intermediate calculations are costly when a relatively large number of points, dimensions, and clusters are to be processed, especially when the number of iterations is large. Moreover, these methods are sensitive to the parameters set by the users and the characteristics of the data.

In practice, these methods are run several times to choose the most optimal result. This makes the use of these methods even more expensive and slower. This problem is discussed in chapter III, section III.2. The contribution focuses on k-means because it is the best-known method in this category. Also, it is widely used in practice and implemented by the majority of known machine learning libraries.

Despite its algorithmic simplicity and wide use, k-means remains nevertheless dependent on input parameters, mainly the number of clusters 𝑘. As emphasized above, the 𝑘 value must be within a range of possible and reasonable values or even a single potential value to produce a partitioning of the dataset that is as close as possible to the field truth. This problem has been addressed by proposing several heuristics. In their operation, they are based on multiple calls of k-means. However, they do not work in certain spatial configurations of the data, i.e, dataset with overlapping clusters, which lead to biased results and very long process time. Moreover, many of these methods estimating 𝑘 require clusters to be strictly spherical, which is not always the case in reality. This strong apriori assumption about the cluster's shape also leads to a bad estimation of 𝑘 if the assumption is not respected in the dataset. These problem are addressed in chapter III, section III.3.

Density-based methods adopt another definition of a cluster, unlike centroid based methods. A dense region, i.e., a subspace of data where the points are very close together, represents a potential cluster or part of it [START_REF] Kriegel | Density-based clustering[END_REF]. Although these methods have less a priori assumptions about the data than the centroids-based methods, they are sensitive to the spatial distribution of the data. Indeed, they expect at the boundaries between clusters a variation in density. The intensity of this variance depends on the method used. Clusters of the same density with a strong overlap are potentially considered as a single cluster. Another problem is that they might consider a low-density cluster as a group of outliers, i.e., as points that do not provide useful information. However, this low-density cluster may represent a real phenomenon existing in the ground truth. Moreover, density calculations, with very large dimensions, tend to give a clustering far from the ground truth. This problem is called the curse of dimensionality [START_REF] Donoho | High-dimensional data analysis: The curses and blessings of dimensionality[END_REF]. These problems are dealt with in chapter IV.

I.3 Outline

In this manuscript, three contributions have been made. The first two are grouped in chapter III. They deal with problematics around k-means. The third contribution, presented in chapter IV, deals with a density-based method:

• Acceleration of k-means versions based on triangular inequality in a massive data context. A strategy for accelerating k-means, Sk-means, is proposed. It stores information on the movements of points during the k-means process (standard version and optimized versions based on geometric reasoning). This information allows not to apply useless calculations on certain points. In this way, k-means is accelerated in execution time, especially when running in large datasets;

• Kd-means. Proposal of a clustering method that automatically estimates the number of clusters present in a dataset. Kd-means is based on kd-tree, a hierarchical data structure used to organize data. In Kd-tree, we introduced fusion measures that use geometric properties used in a hierarchical process (bottomup). These measures guide the aggregations between sub-groups of points to produce, at the process end, final clusters with a more complex shape than those found by k-means and by the mixture of Gaussian models. Kd-means has the advantage of producing quality clustering that is fast compared to competitors;

• Decwa. A clustering method capable of detecting irregularly shaped clusters.

It is based on a probabilistic approach as well as optimal transport. It has the advantage of producing a quality clustering carried out on very large dimensions.

Chapter II

II.1 Introduction

Given 𝑘 ∈ N * and 𝑋 = {𝑥 1 , ..., 𝑥 𝑛 } a set of points where 𝑥 𝑖 is defined in the data space R 𝑑 , the clustering aims to partition 𝑋 into a set of clusters 𝐶 = {𝐶1, ..., 𝐶 𝑘 } so that the points of a cluster are as similar as possible and the points of different clusters as dissimilar as possible. Note that a dimension corresponds to a characteristic of the data point, e.g., if a point represents a vehicle, its characteristics could be the color, the number of wheels, the registration, etc.

First, we overview the different clustering approaches (section II.2.2 ) and then identify their main differences. A focus is then essentially put on partition-based methods (section II.3 ) and density-based methods (section II.5 ) since our contributions have been made in both approaches. Another section is devoted to optimization strategies (section II.4) for k-means. Even if they can speed up the execution time of methods, these strategies could also improve the quality of partitioning, i.e., obtain even more homogeneous clusters.

II.2 Clustering methods

II.2.1 Introduction

Although clustering methods have to build homogeneous clusters, they do not have the same definition of the cluster nor on how to carry out partitioning because of the unsupervised aspect of these methods. The clustering methods are broadly classified into partition-based, hierarchical-based, density-based and grid-based [START_REF] Aggarwal | Data Clustering: Algorithms and Applications[END_REF]. We will briefly discuss these paradigms.

II.2.2 clustering methods taxonomy

Partition-based methods1 . The aim of this paradigm consists in dividing a dataset 𝑋 into 𝑘 clusters according to a particular objective function. Each cluster is represented by a centroid, also called a gravity center or center, which is not necessarily contained in the data set. For example, in the k-means algorithm (Lloyd, 1982b), the centroid is the arithmetic mean of all the cluster points' values. In the k-medoid algorithm [START_REF] Kaufmann | Clustering by means of medoids. Data Analysis based on the L1-Norm and Related Methods[END_REF], the centroid is one of the points in the cluster called the medoid.

To produce data partitioning, the methods of this paradigm go through an iterative process. The partitioning is improved at each iteration compared to the previous iteration according to the objective function until convergence. The improvement in an iteration refers to the change of cluster for some points.

Hierarchical methods. In this paradigm, clusters are represented hierarchically, at different granularity levels, through a tree structure called a dendrogram. In this dendrogram, clusters are nested, i.e., they are made up of other smaller clusters.

Different strategies exist to recover clusters from the dendrogram, e.g., by cutting the dendrogram at a given height. The recovery of a different set of clusters is possible by cutting the dendrogram at a different height without rebuilding the tree. The methods are divided into two groups:

• divisive: these methods proceed to a recursive dichotomy of the dataset. At each division, one or more clusters are obtained, each of these clusters is then divided and so on;

• agglomerative: these methods recursively agglomerate clusters. At the very beginning, each point is a cluster. The merging is done pair by pair of clusters.

Often, a set distance is involved to calculate the similarity between two clusters.

Density-based methods. This group considers that clusters are dense regions of points separated by less dense regions. The latter are assimilated to outliers. A cluster is defined as follows: given a volume in a data space, the more data points there are in this volume, the denser the volume is. Clusters are arbitrary in shape, i.e. they can take practically any shape. Moreover, generally, there are no a priori assumptions about the shape of clusters.

Grid-based methods. Commonly, these methods first quantify the original data space into a finite number of cells. Partitioning operations are performed on the quantized space (grid stucture). The main feature of this approach is its ability to reduce processing time since similar data points fall into the same cell, and each cell is treated as a single point. This makes the algorithms independent of the number of objects in the dataset. However, the clustering quality is compromised by the size of the cells chosen. The definition of quality depends on the method used and the user. Moreover, the uniform grid (i.e. cells with the same size) may not be efficient for very irregular data distributions. Below the common successive instructions of the grid-based methods:

• Define a set of grid cells

II.2.3 Conclusion

We discussed the five paradigms. These one correspond to very different approaches, although they have the same goal, i.e., to divide a dataset into several homogeneous groups (clusters) of data points. There are several aspects involved in the differentiation of the five paradigms. Without being exhaustive, below are some of them [START_REF] Fahad | A survey of clustering algorithms for big data: Taxonomy and empirical analysis[END_REF]:

• what type of cluster is produced? 1) nested cluster, i.e., a cluster composed of smaller clusters; 2) flat cluster, i.e., a whole cluster containing no sub-clusters;

• what kind of cluster shape is produced? Spherical, elliptical or arbitrary shape;

• is inner processing based on data structures? e.g., tree (hierarchical approach), grid (grid-based approach), no structure needed for partition-based methods.

In this thesis, we focus essentially on the two following approaches: partition-based methods (also called centroid-based methods) and density-based methods. Despite this focus, we have used some tools from other paradigms in our contributions.

II.3 Partition-based clustering methods

II.3.1 Introduction

In this sub-section, we discuss partition-based methods. We recall that clusters each have a center that represents the points of the cluster in these methods. First, we focus on the best-known algorithm of this group of methods, k-means. Then we discuss its alternatives and the reason that led to the development of these alternatives. [START_REF] Forgy | Cluster analysis of multivariate data: efficiency versus interpretability of classifications[END_REF], Lloyd, 1982a) is one of the most widely used data clustering algorithms. Due to its practicality in many fields of application, this algorithm has been popular from 1965 (Jain, 2010b[START_REF] Liu | Which distance metric is right: An evolutionary k-means view[END_REF]. K-means implicitly seeks to optimize the following objective function, i.e. for each cluster, k-means minimizes the distance between the points and their centroid:

II.3.2 K-means

II.3.2.1 Problem definition K-means
𝑘 ∑ 𝑗=1 ∑ ∀𝑥∈𝐶 𝑘 𝑑𝑖𝑠(𝑥, 𝐺 𝑘 ) 2 (II.1)
where 𝐺 𝑘 is the centroid of the cluster 𝐶 𝑘 and 𝑑𝑖𝑠 is the distance function. Lloyd's version consists of an iterative process that ends when centroids do not change between two iterations. This process consists of two steps:

• assigning each point to the nearest centroid using the euclidean distance;

• recalculating the centroids, i.e., the average of the point values of the newly formed clusters.

It has been shown that k-means can be seen as a probabilistic approach. Indeed it produces about the same results as Gaussian Mixture Model (GMM) (Titterington et al., 1985) under certain conditions. GMM considers that the points of each cluster are sampled from a Gaussian distribution. During its process, it learns the parameters of each Gaussian cluster via the Expectation-Maximation (EM) algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the em algorithm[END_REF]. When GMM imposes that the Gaussian distribution is isotropic, then, in this case, the clusters it produces are strictly spherical, so GMM and k-means produce similar results.

II.3.2.2 Limitations

The quality of clustering and convergence depends on the choice of the number of clusters (𝑘), the initial centroids and the distribution of data (Jain, 2010a). These It should be noted that even if the initialization of centroids is good, the difficulties discussed so far are not solved. Other strategies are needed to limit or solve these problems.

Another limit concerns the centroid representation. Indeed, the centroid is the artihmetic mean of the point values of the cluster. This representation is not appropriate for use cases wherein the means are not meaningful or the data is not continuous and numeric (e.g. categorical data).

Even if k-means has a probalistic equivalent via GMM. This latter requires the user to specify the value of 𝑘, and its clustering quality is sensitive to this value.

Moreover, the EM algorithm has difficulties converging towards an optimal solution in some cases, for example, when it faces medium-dimensional data. Consequently, to limit this difficulty, some constraints are imposed, such as limiting spatial orientations of clusters that can be identified.

The limitations will be discussed in more detail later in the chapter.

II.3.2.3 Versatility

One of the advantages of k-means is its versatility, i.e., at the algorithmic level, that its subparts can be improved independently. Changing one sub-part does not necessarily have a negative impact on another part. We distinguish two types of changes that can

II.3.3 K-means alternatives

In this part, we discuss partition-based clustering methods inherited directly from k-means. Their development is due to k-means versatility.

II.3.3.1 K-median

K-median [START_REF] Bradley | Clustering via concave minimization[END_REF] differs from k-means in the definition of the cluster centroid. K-median uses the median instead of the mean to represent a cluster. Indeed, it is known that medians are less sensitive to extremes of a list of values. The purpose of k-median is to assign each point to the nearest median while minimizing the following it is more robust to outliers and noise.

II.3.3.2 K-medoids

In some use cases, the mean or median does not make sense in practice; e.g. if the points are telecom network stations, then the average of the stations is meaningless.

In the k-medoid algorithm [START_REF] Kaufmann | Clustering by means of medoids. Data Analysis based on the L1-Norm and Related Methods[END_REF], close to k-means, the centroid's value is taken from the data set. Therefore, the value is real because it is not derived from an aggregation of points, as is the case in k-means and k-medoid, where the centroid does not exist in the dataset. The centroid is called medoid. It corresponds to the most centralized point of the cluster. The other points of the cluster are non-medoid.

At each iteration, the points are assigned to the nearest medoid. By this, the algorithm minimizes the quadratic sum of the dissimilarities between each point and the medoid representing it. Indeed, the objective function is similar to that of kmedians except that the centroid is a medoid instead of a median. Then follows the phase of updating the medoids, it corresponds to an iterative sub-process wherein each iteration, a test of replacement of each medoid by a non-medoid. By calculating scoring functions, this test verifies whether it is better to replace one medoid by another. This phase is costly. On the one hand, the solution search space is exponential, and on the other hand, (𝑘 -𝑛)𝑘 tests are carried out.

II.3.3.3 K-modes

The basic concept of k-means is based on mathematical calculations (averages, Euclidean distances). It is not suitable for categorical (qualitative) data. These are discrete and even non-ordered in some cases (e.g., first names). Therefore, clustering algorithms dedicated only to numerical data cannot be used to classify categorical data that exist in many real-world applications. One could think about transforming categorical data into numerical data and possibly apply k-means. However, k-means uses numerical distances, so it could consider two close data points that are far apart but have been assigned two close numbers. In clustering research, much effort has been put into developing new methods for clustering categorical data. One of them is the k-mode method [START_REF] Huang | A fast clustering algorithm to cluster very large categorical data sets in data mining[END_REF], which is widely used in various applications.

k-modes is similar to k-means except that cluster centroids are modes and the distance calculation is adapted for categorical data.

Points and modes are vectors of 𝑑 ∈ N * dimensions (attributes). The mode of an attribute in a given cluster is the most represented or frequent value.

Formally, the objective function to be minimized is :

𝑘 ∑ 𝑗=1 𝑛 ∑ 𝑖=1 𝑓 𝑖,𝑗 𝑑𝑖𝑠(𝑥 𝑖 , 𝐺 𝑗 ) (II.3)
with 𝑓 ( 𝑖, 𝑗) indicating whether or not the ith point belongs (binary value) to cluster 𝑗 and 𝐺 𝑗 the mode of cluster 𝑗 and 𝑑𝑖𝑠(𝑥 𝑖 , 𝐺 𝑗 ) is the dissimilarity between points 𝑥 𝑖 and 𝐺 𝑗 and it is computed as follows:

𝑑 ∑ 𝑙=1 𝜎(𝑥 𝑖,𝑙 , 𝐺 𝑗,𝑙 ) (II.4)
where

𝜎(𝑥 𝑖,𝑙 , 𝐺 𝑗,𝑙 ) = ⎧ ⎪ ⎨ ⎪ ⎩ 1 𝑥 𝑖,𝑙 = 𝐺 𝑗,𝑙 0 𝑥 𝑖,𝑙 ̸ = 𝐺 𝑗,𝑙 (II.5)
with 𝑥 𝑖,𝑙 and 𝐺 𝑗,𝑙 are values of attribute 𝑙 of points.

II.3.4 Conclusion

Partition-based methods perform clustering while optimizing an objective function, which is the sum of squared errors, i.e., minimizing the squared distance between the points and the centroid in each cluster.

The difference between these methods is essentially focused on the type of cluster center (mean, median, medoid, mode) and the distance to compute the similarity between points and cluster centers. Nevertheless, k-means is still widely used because of its linear complexity as a function of the number of points and clusters. For this reason, we are particularly interested in this method in this manuscript. Moreover, the contributions made to k-means could be extended to other partition-based methods with some adaptations.

II.4 Optimization strategies for k-means

II.4.1 Introduction

In this section, we discuss the optimization strategies explicitly implemented for kmeans. They are either designed for speeding up time execution or improving quality or both. These strategies respond to different limitations of k-means. First, we address the problem of estimating the number of clusters in the dataset. This number is a parameter whose value is left to the free choice of the users. This parameter is essential because it has a strong influence on the intensity of cluster homogeneity. Different strategies have been developed to answer this problem. However, they use k-means several times before arriving at an estimate. We discuss their concept and their limits in more detail in subsection II.4.1.1. Another problem concerns the initialization of the centroids (subsection II.4.1.2), which also affects the clusters' homogeneity and is also done manually by the users. Strategies are proposed to initialize the centroids. Some of them do not call k-means but provide their set of centroids that they consider optimal.

They generally make k-means converge faster and improve quality. Others use k-means several times or are complex in computation. In this case, they generally initialize the centroids and partition the dataset into clusters. Due to this complexity, the quality is generally better than the first centroid initialization strategies, but less so in terms of execution time. Finally, the last problem we discuss is the high cost of computations in k-means in a large amount of data environment. We present three fundamentally different strategies (subsections II.4.1.3,II.4.1.4,II.4.1.5) that accelerate the execution time of k-means. This time, optimization is totally internal to the k-means algorithm.

II.4.1.1 K estimation

Due to the unsupervised clustering nature, estimating the number of clusters (𝑘) is a major problem. In the case where the clusters are all spherical and well distinguishable (without overlapping), if the user does not provide the actual value of 𝑘 then the clustering result is unsatisfactory. In reality, this simple configuration of cluster distribution is rare. Indeed, clusters can be of different shapes, sizes, orientations, and localities, making the task of estimating 𝑘 more complex. This complexity is accentuated when clusters overlap in the data but correspond to different phenomena.

This problem has been studied for many years [START_REF] Halkidi | On clustering validation techniques[END_REF]. Among the most representative works are X-means (Pelleg and Moore, 2000) and G-means [START_REF] Hamerly | Learning the k in k-means[END_REF]. They are based on information theory and probability tools. We study them in more detail in this part. These algorithms not only estimate the number of centroids but also propose a partitioning of the dataset. Indeed, they correspond to hybrid solutions wrapping the k-means algorithm.

II.4.1.1.1 X-MEANS X-means (Pelleg and Moore, 2000) is a k-means based algorithm that searches for the number of automatic centroids while ensuring that these centroids best match the dataset. Starting from a minimum 𝑘 (𝑘 𝑚𝑖𝑛 ), generally equal to one, the algorithm iteratively adds new centroids if necessary until the maximum value of 𝑘 (𝑘 𝑚𝑎𝑥 ) is reached. At each iteration, the algorithm identifies the subset of centroids that must be divided into two. This identification is made using a statistical criterion called Bayesian Information Criterion (BIC). The latter is used for model selection and is based on the likelihood function.

The X-means process consists of two operations that are iterated until completion:

𝐼𝑚𝑝𝑟𝑜𝑣𝑒_𝑝𝑎𝑟𝑎𝑚 and 𝑖𝑚𝑝𝑟𝑜𝑣𝑒_𝑠𝑡𝑟𝑢𝑐𝑡𝑢𝑟𝑒. 𝐼𝑚𝑝𝑟𝑜𝑣𝑒_𝑝𝑎𝑟𝑎𝑚 is only the execution of k-means with the current 𝑘 as a parameter while 𝐼𝑚𝑝𝑟𝑜𝑣𝑒 _𝑠𝑡𝑟𝑢𝑐𝑡𝑢𝑟𝑒 researches where new centroids would be added. For each centroid and its associated region of points, three sub-operations follow each other:

• the corresponding BIC is calculated;

• k-means is executed with 𝑘 = 2, two children's centroids are obtained;

• the BIC of the same region is calculated but taking into account the two children's centroids instead of their parent centroid.

If the previous BIC is smaller than the next BIC, then the parent centroid is replaced by its two children's centroids, or the parent centroid is retained. [START_REF] Hamerly | Learning the k in k-means[END_REF] wraps k-means and adopts almost the same approach as X-means. Instead of the BIC criterion, the gaussianity test (at the level of 𝛼 confidence defined by the user) on clusters is used to decide whether to divide a centroid in two. The G-means algorithm starts with a small number of centroids and increases the number of centroids following a hierarchical process.

II.4.1.1.2 G-means This algorithm
In fact, at each iteration, each centroid is assigned points, forming a cluster. Then a statistical test of gaussianity is applied to this cluster. If the test validates the hypothesis that the cluster is not Gaussian, the corresponding points must be represented by several centroids. Hence the division of the centroid in two using a strategy proposed by the authors using Principal Component Analysis (PCA) [START_REF] Wold | Principal component analysis[END_REF] . Otherwise, if it is Gaussian, the points are represented by this centroid. Between each division cycle, k-means is executed on all dataset and all centroids to refine the current solution (equivalent to the 𝑖𝑚𝑝𝑟𝑜𝑣_𝑝𝑎𝑟𝑎𝑚 step of x-means).

II.4.1.1.3 Limitations The limitations of the above methods are related to the difficulty of dealing with overlapping clusters, the quality of clustering (and therefore also the value of k) they produce as well as the execution time to provide a result.

Each of the both algorithms can identify only a limited number of more or less spherical cluster types. X-means is suitable for data whose clusters are strictly spherical [START_REF] Hamerly | Learning the k in k-means[END_REF]. If other forms of clusters are present, then the estimate of 𝑘 could be overestimated. On the other hand, G-means could identify clusters whose spherical shape is less strict than that identified by X-means. If the clusters are well spaced apart, G-means could provide the relevant value of 𝑘 [START_REF] Hamerly | Learning the k in k-means[END_REF]. In addition to this distribution, the strict sphericity requirement must be added to the clusters for X-means to have the same performance. If the clusters overlap, then none of them estimates the correct value of k. Under these conditions, X-means and G-means tend to overestimate 𝑘.

These cases are illustrated in Figure II.3. Five Gaussian clusters have been generated but with more or less different sphericity. Two clusters are well separated from each other, the other three overlap. The two algorithms were run on this set of 20,000 data points. The 𝑘 𝑚𝑎𝑥 has been set at 140. G-means identified 26 clusters but detected the 2 clusters well separated from the others. However, there are overfitting on the remaining three clusters and an overestimation of 24 clusters instead of only estimating 3. X-means estimated k at 76. Overestimation is slightly higher for overlapping clusters than for separate clusters.

In terms of execution time, the two algorithms are not suitable when the data are massive. It is even more accentuated when the estimated value of k tends to be significant.

II.4.1.2 Centroid initialization methods

The partitioning of the dataset is dependent on the centroid initialization step, which by default, consists of randomly selecting 𝑘 centroids from the points in the dataset [START_REF] Celebi | A comparative study of efficient initialization methods for the k-means clustering algorithm[END_REF]. A wrong choice of centroids leads to a partitioning of low quality or even meaningless for the users. Depending on the applications using k-means, centroid initializations' level of efficiency and accuracy could be very strict.

Algorithms are available for initializing 𝑘 centroids. However, they do not necessarily lead to the same result or the optimal solution. An initialization algorithm's choice influences two aspects: clustering quality and the execution time. A compromise is involved, and its balance is defined according to the type of data analysis project.

Some algorithms have a higher probability of proposing an initialization that leads to a correct result than others, i.e. a result that could be exploited by the users. In the same way, some are faster than others without necessarily being better in quality. We list some of them for more details but without being exhaustive.

One of the most widely used methods is Forgy's method [START_REF] Forgy | Cluster analysis of multivariate data: efficiency versus interpretability of classifications[END_REF]. It randomly takes 𝑘 centroids from the dataset and then assigns the remaining points to the clusters with the closest centroid. Macqueen's method (MacQueen, 1967) follows the same logic except that the way of assigning points to clusters is different. Each time a point is assigned to a cluster, its centroid is recalculated while considering the new point. The justification behind these methods based on a quasi-random strategy is that random selection is likely to select points in dense regions, i.e., regions that are likely to be final clusters or contribute strongly to them. According to these randomized methods, the points of dense regions are considered to lead to correct results. However, in practice, these methods are likely to take outliers or points that are too close together as centroids. This reality is due to the strategy based on chance without any regularisation to avoid falling into these scenarios. Besides, several executions are necessary to choose the best method to get the best result.

The Bradley and Fayyad method [START_REF] Bradley | Refining initial points for k-means clustering[END_REF]) is a method that reduces the random effect compared to the above methods, starts by randomly partitioning the dataset into 𝐽 subsets. These subsets are clustered using k-means initialized by the MacQueen method, producing 𝐽 sets of intermediate centroids, each with a cardinality of 𝑘. These sets of centroids are combined into a superset, which is then clustered by k-means 𝐽 times, each time initialized with a different set of centroids.

The group of centroids that minimizes the objective function of k-means the most is then taken as the final centroid group. Besides this method, 𝑘𝑚𝑒𝑎𝑛𝑠 + + [START_REF] Arthur | k-means++: the advantages of careful seeding[END_REF], a method recognized for its performance and efficiency. Its goal is to identify the 𝑘 centroids furthest away from each other. Gradually, one by one, it selects a new centroid among the points of the dataset such that this centroid is the furthest from the other centroids possibly already existing.

The methods discussed so far are of linear temporal complexity. Other methods have been proposed with greater complexity but more complex in operation. Among them, the binary division method [START_REF] Linde | An algorithm for vector quantizer design[END_REF] takes 𝐺 1 = 𝑚𝑒𝑎𝑛(𝑋) as the first centroid. At iteration 𝑡 ∈ {1, 2, ..., 𝑙𝑜𝑔 2𝑘 }, each of the existing 2 (𝑡-1) centroids is split into two new centroids by subtracting and adding a fixed perturbation vector 𝑒, i.e.

𝐺 𝑗 -𝑒 and 𝐺 𝑗 + 𝑒 (𝑗 ∈ {1, 2, ..., 2 (𝑡-1) }). These 2 𝑡 new centroids are then refined using k-means. There are two main disadvantages associated with this method. Firstly, there is no indication of the choice of an appropriate value for 𝑒, which determines the split direction. Secondly, the method is computationally demanding since, after each iteration, k-means must be run for the whole dataset. The value of 𝑒 could be determined by the PCA method [START_REF] Huang | A comparison of several vector quantization codebook generation approaches[END_REF]. However, the calculation requirements are higher because of the generation of eigenvectors in PCA. Another known method, the global k-means method [START_REF] Likas | The global k-means clustering algorithm[END_REF], takes 𝐺 1 = 𝑚𝑒𝑎𝑛(𝑋)

as the first centroid. At the iteration 𝑖 ∈ {1, 2, ..., 𝑘 -1} it considers each of the 𝑛 points as a candidate for the ith (𝑖+1) centroid and runs k-means with (𝑖+1) centroids on the data set. This method is computationally prohibitive for large datasets because it involves 𝑛(𝑘 -1) executing k-means on the dataset.

In short, expensive methods are deterministic and lead to a better result. They also improve the convergence of k-means. Indeed, they correspond to hybrid and complex approaches. However, for applications requiring a fast response time, they are not practical. On the other hand, relatively cheaper (compared to previous methods) methods are faster (linear complexity) and could offer correct results. Nevertheless, it is advisable to repeat the initialization method several times to get a reasonable quality one. This is especially true for methods based on quasi-random approaches. Moreover, non-expensive methods are sensitive to outliers or even to the order of points, such as Macqueen's method (MacQueen, 1967). K-means++ [START_REF] Arthur | k-means++: the advantages of careful seeding[END_REF] presents a relatively good compromise between quality and execution time. Given its reasonable practicability, it is implemented in several reputable libraries of statistics and machine learning.

II.4.1.3 Parallelization

Despite the simplicity of k-means at several levels, such as implementation, application to various domains, and interpretation of results, it remains problematic for its execution time in the context of large data. At several levels of the algorithm, the computation time increases when its parameters increase. In the first step of k-means, at each iteration, the more the number of points 𝑛 and the number of clusters 𝑘 increase, the more the number of point-centroid distances increases. In the second phase, the more 𝑛 and 𝑘 increase, the more expensive the centroids' calculation is.

One way to reduce these costs is to parallelize computations. Various works (Kucukyilmaz, 2014) have focused on parallelizing k-means to save execution time; e.g.

versions based on the MPI platform [START_REF] Dhillon | A data-clustering algorithm on distributed memory multiprocessors[END_REF]Modha, 2000, Zhang et al., 2013), or the MapReduce paradigm [START_REF] Zhao | Parallel K-Means Clustering Based on MapReduce[END_REF][START_REF] Zhao | Parallel K-Means Clustering Based on MapReduce[END_REF][START_REF] Zhao | Parallel K-Means Clustering Based on MapReduce[END_REF]. These works are generally based on one of the two following architectures:

• shared-memory architectures: the processors have direct access to common data located in the main memory. However, this architecture has a small number of processors because the bus interconnection's physical network has a limited data transfer capacity. The connection between the processors and the memories becomes a bottleneck since all the processors share the same bus.

• shared-nothing architectures: the processors share neither the memory nor the disk. Data is shared across the processors. The processors communicate by passing messages through an interconnection network. This architecture is scalable because each processor is independent of the other processors, and communication is iter-processors could be expensive.

In the k-means version, due to its iterative aspect and the dependencies between the two phases of k-means, the exchange of intermediate results between processors is important. Therefore k-means can be parallelized in both architectures. However, these architectures have to face the communication cost, which increases when the amount of data and the number of calculations increases.

II.4.1.4 Tree-based k-means versions

The purpose of parallelized versions of k-means is to store data on distributed memory spaces and parallelize calculations to save execution time. Indeed, they do not seek to propose strategies for optimizing k-means algorithmically, i.e., avoiding unnecessary calculations.

We discuss other k-means optimization strategies that effectively deal with this aspect of avoiding useless computations. The first of them is based on indexing data in a hierarchical data structure. The underlying idea of these versions is, during the phase of assigning the point to its nearest centroid, not to calculate the distance between the point and all other centroids. Hence the saving in execution time.

In this sense, the authors of (Kanungo et al., 2002, Pelleg and[START_REF] Pelleg | Accelerating exact k -means algorithms with geometric reasoning[END_REF] have proposed tree-based versions of k-means. Basically, these versions work as follows:

before the k-means process, the points are indexed in a tree. Each node refers to a set of points and its children refer to subsets whose union represents their father.

Then during the k-means process, when assigning each point to its closest cluster, the list of centroids in the tree is propagated in the up-down direction. During the propagation, nodes reject some centroids from the list because they are considered far enough from their points. As soon as the list contains only one centroid for a given node, all points of this node (including recursively nodes and children) are assigned to this single centroid. In this way, the calculation of the distances between centroid points is accelerated.

However, these versions are not suitable for large dimensions (usually > 20 dimensions). In [START_REF] Moore | The anchors hierarchy: Using the triangle inequality to survive high dimensional data[END_REF], the author proposes Moore's Anchors Hierarchy algorithm which uses a tree built with a middle-out technique. It is effective for much larger dimensions.

In practice, these methods are much less efficient than versions of k-means based on geometric reasoning (number of dimensions ≥ 8) [START_REF] Hamerly | Making k -means even faster[END_REF]. These versions are discussed in the rest of this sub-section. Note that these methods do not avoid all point-centroid distances. The rate of So in the remainder of this part we discuss chronologically the best known methods belonging to this category.

In the following, by language misuse, the algorithms could be called by their name or that of their author without being preceded by the word algorithm (e.g., Elkan instead of Elkan's algorithm).

II.4.1.5.1 Compare-means Compare-means [START_REF] Phillips | Acceleration of k-means and related clustering algorithms[END_REF] is an accelerated version of the Lloyd version (Lloyd, 1982a). During the phase of assigning points to their nearest centroid, compare-means states that if centroids are spatially located very far from the centroid representing a given point, then those centroids are also far from that point. The idea is not to calculate the distance between this point and the centroids, which are judged to be far enough away.

Let When looping the list of centroids for each point (first phase of k-means), the inequation validity II.6, for the given point and the current centroid, is checked. The actual distance is only calculated between the point and the centroid if the verification has been validated. Then, the same procedure is repeated for the next centroid. Note that all inter-centroid distances are computed, at the beginning of the first phase of k-means and each iteration, to verify the inequation.

II.4.1.5.2 Sort-means Sort-means [START_REF] Phillips | Acceleration of k-means and related clustering algorithms[END_REF] is an improvement of comparemeans. Indeed, for each centroid 𝐺 𝑗 , the other centroids are sorted in the increasing order based on their distance from 𝐺 𝑗 . Thus, when looping the sorted list of centroids, as soon as the inequality validity (same as compare-means) is verified for a centroid, the centroids following it are not processed. Since these are more distant than the current centroid, so their processing is useless.

II.

II.4.2 Conclusion

In this part of state-of-the art, the different strategies that improve k-means efficiency and performance are discussed (table II.1). So, optimization concerns the execution time acceleration as well as the clustering quality or the objective function optimization.

We first discussed methods for automatically estimating the number of 𝑘 clusters in a dataset. More precisely, the methods (G-means and X-means) which are based on a hierarchical process and statistical tests or tests derived from information theory.

We have shown experimentally that these estimation methods do not work properly when real clusters overlap and that X-means does not support non-strictly spherical clusters. These data characteristics induce them to an overestimation of k and poor clustering quality. We also discussed methods for initializing centroid 𝑘. Some They also generate maintenance costs to update the limits and inter-center distance matrices at each iteration.

II.5 Density-based clustering II.5.1 Introduction

In this part, we discuss the paradigm of density-based methods [START_REF] Kriegel | Density-based clustering[END_REF].

Contrary to centroid-based methods, it does not assume a priori assumptions on the distribution of points. Table II.1: Advantages and drawbacks of k-means optimization strategies some of them are considered as outliers. This is useful if the data is noisy. In addition, users do not need to specify the number of clusters in advance.

We first discuss the basic concept of this paradigm and then its most representative methods.

II.5.2 Density-based concepts

Density-based clustering is based on the exploration of dense regions of points in the dataset [START_REF] Aggarwal | Data Clustering: Algorithms and Applications[END_REF]. A dense region corresponds to a subspace of data where many points are relatively close to each other. Thus, a cluster in data space is a contiguous region of points with a high density of points, separated from the other clusters by less dense regions. [START_REF] Kriegel | Density-based clustering[END_REF].

The fundamental pillar of this paradigm is the consideration of a dataset as coming from an unknown probability density function (𝑝.𝑑.𝑓 ). This function describes how the dataset was generated. Indeed, it corresponds to a representation of the source of the data. In this paradigm, through this function, one is not only interested in assigning each point to its most appropriate cluster but also in the generator of the cluster points to be able to subsequently generate new points in this cluster not yet existing in the dataset. The approximate estimation of this function is carried out by parametric or non-parametric statistical approaches. Parametric approaches consider that each cluster follows a probability law known a priori and whose parameters must be estimated. On the other hand, the density-based paradigm uses more or less explicitly tools of the density function's non-parametric approaches. As mentioned above, the cluster has an irregular shape, which implies that the density function of the dataset or, more specifically that of the cluster, does not follow a pre-defined law.

Nevertheless, these methods do not integrate the notion of centroids, which problematic for applications requiring representatives. Moreover, the cluster definition of density-based paradigm implies no minimization of variance in each cluster, contrary to clustering methods based on centroids. This element differentiating them is an important factor orienting users on which clustering method to choose.

II.5.3 Dbscan

Dbscan [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF] is, by far, one of the best-known algorithms in this category.

It uses two concepts, essential to its operation, connectivity between points, and local density in a point's neighborhood. These concepts are controlled by two parameters entered by the user, 𝑒𝑝𝑠 ∈ R + and 𝑚𝑝 ∈ N * . The basic principle is to build clusters according to the values of 𝑒𝑝𝑠 and 𝑚𝑝. To define a cluster in Dbscan, the introduction of specific properties is essential, and these properties constitute the theoretical basis of this paradigm for the algorithms that followed Dbscan :

• Let a point 𝑥 𝑏 ∈ 𝑋, 𝑥 𝑏 is an interior point if in its neighbourhood (of radius 𝑒𝑝𝑠) it has at least 𝑚𝑝 points, more formally |𝑁 𝑒𝑝𝑠 | ≥ 𝑚𝑝 with 𝑁 𝑒𝑝𝑠 = {𝑥 𝑖 ∈ 𝑋|𝑑𝑖𝑠(𝑥 𝑏 , 𝑥 𝑖 ) ≤ 𝑒𝑝𝑠} the points in the 𝑥 𝑏 neighbourhood; • Let 𝑥 𝑎 ∈ 𝑋 and 𝑥 𝑏 ∈ 𝑋 an inner point, 𝑥 𝑎 is directly density-reachable from 𝑥 𝑏 if 𝑥 𝑎 ∈ 𝑁 𝑒𝑝𝑠 (𝑥 𝑏 )) and |𝑁 𝑒𝑝𝑠 | >= 𝑚𝑝; • Let 𝑥 𝑎 , 𝑥 𝑏 ∈ 𝑋, 𝑥 𝑎 is density-reachable from 𝑥 𝑏 if
there is a chain of points 𝑥 1 , ..., 𝑥 𝑡 with 𝑥 1 = 𝑥 𝑎 and 𝑥 𝑡 = 𝑥 𝑏 where 𝑥 𝑖 is directly density-reachable from x 𝑖-1 ;

• Let 𝑥 𝑎 , 𝑥 𝑏 ∈ 𝑋, 𝑥 𝑎 and 𝑥 𝑏 are density-connected if there is an third inner point so that 𝑥 𝑎 and 𝑥 𝑏 are density-reachable from that point. So a region of points, 𝑅, is a cluster if only two conditions are met :

• Maximality: ∀𝑥 𝑎 , 𝑥 𝑏 with 𝑥 𝑏 ∈, if 𝑥 𝑎 is density-reachable from 𝑥 𝑏 then 𝑥 𝑎 ∈ 𝑅;
• Connectivity: ∀𝑥 𝑎 , 𝑥 𝑏 ∈ 𝑅, 𝑥 𝑎 and 𝑥 𝑏 are densiy-connected.

Dbscan has a certain sensitivity concerning border points (points that are not interior points but are in a neighborhood of an interior point). Indeed, if Dbscan is executed several times with the same parameters, the interior points remain unchanged, whereas the border points could change cluster through different Dbscan calls. This is due to the sorting order of the points. Also, it is not able to detect clusters of different densities or nested clusters of different densities. It could also produce a lot of noise in many configurations of parameter values.

II.5.4 Denclue/Dbclasd

Denclue [START_REF] Hinneburg | An efficient approach to clustering in large multimedia databases with noise[END_REF] From 𝑓 , particular points are identified, called attractors. They have a density higher than a predefined threshold and are indeed local maxima of 𝑓 . A heuristic called climbing hill is applied to assign it to its most suitable attractor for each remaining point. The points around each attractor constitute a sub-cluster. Clusters are formed by the agglomeration of sub-clusters whose distance is less than another predefined threshold.

In addition, to access the neighborhood of a point more efficiently and make calculations locally, Denclue uses a grid-based data structure.

Denclue is presented as generalizing from Dbscan, k-means and hierarchical approaches. Nevertheless, it inherits from these also their difficulty in detecting clusters of very close density. A Denclue 2.0 [START_REF] Hinneburg | Denclue 2.0: Fast clustering based on kernel density estimation[END_REF] version has been proposed to automate the step size in the climbing hill and improve the quality of points assignment to attractors. Still, it keeps almost the same solution as its predecessor.

Dbclasd is another algorithm based on a probabilistic approach of the density.

Dbclasd assumes that clusters follow a uniform probability law allowing it to be parameter-free [START_REF] Xu | A distribution-based clustering algorithm for mining in large spatial databases[END_REF]. However, it has difficulties to detect non-uniform clusters because of this strong assumption. Also, it is dependent on the order in which the points are processed. Clustering results can vary significantly from one order to another. Dbclasd also has difficulty to separate nested densities, especially those close in density.

II.5.5 Optics/Hdbscan

Indeed, the Dbscan parameters do not allow identifying different densities, especially those that are imbricated. If the 𝑚𝑝 parameter is set, then very high-density clusters are absorbed by less dense clusters because high-density clusters require a smaller 𝑒𝑝𝑠 radius than that of less dense clusters to cover the same minimum number of points.

In this way, we lose information about the particularity of denser clusters.

Optics (Ordering Points To Identify the Clustering Structure) [START_REF] Ankerst | Optics: Ordering points to identify the clustering structure[END_REF] has been proposed to address this problem. The main idea is to order the points according to local point densities to identify denser clusters. OPTICS does not produce clustering directly but a visual hierarchical structure, called reachability-plot, allowing users to extract clusters.

The reachability-plot is a sequence of valleys and peaks. The x-axis refers to the points, ordinate so that the same cluster points are practically contiguous. The y-axis is the reachability-distance, a distance introduced by OPTICS. In reachability-plot, a cluster is a valley, i.e., points with a low reachability-distance and the peaks correspond to cluster separations or noise points. To extract clusters, a horizontal line, called a cut-off, is drawn at a given reachability-distance. By reading the plot from left to right, valleys and peaks are identified from where are clusters are derived.

In short, Optics offers a visual solution where a cut is a Dbscan solution. Indeed, it offers a multitude of Dbscan solutions. However, the automatic extraction of clusters from the reachability-plot remains a complicated task. Hdbscan (Campello et al., 2013, McInnes and[START_REF] Mcinnes | Accelerated hierarchical density based clustering[END_REF] is an algorithm that also provides a visual solution with a As a result, they could space out points in their new measurement space that should not be and therefore consider points as outliers and be absorbed by other clusters.

Although these approaches solve part of the problem of varying density clusters, they suffer from unevenly distributed density and high-dimensional datasets. They still mismanage low-density clusters by tending to consider them as outliers or to merge them into a higher-density cluster.

II.5.6 Conclusion

The density-based methods paradigm is based on the density notion (in the general sense of a number of points in a given volume of data space). This concept allows identifying any form of clusters without specifying the number of clusters a priori.

The Dbscan, Denclue, Dbclasd methods have difficulties in finding imbricated clusters with different densities. Optics and Hdbscan have been proposed to meet this need.

Nevertheless, they have difficulties in working in high-dimensional data and dealing with unevenly distributed densities.

Common problems with existing density-based clustering approaches are related to the difficulty of dealing with low-density clusters, clusters close to similar densities, and high-dimensional data. The other limitation relates to their inefficiency in dealing properly with nested clusters of different shapes and uneven distribution of densities.

II.6 Discussion

We discussed the methods of two paradigms. First, we reviewed partition-based methods with a particular focus on k-means. Several limitations were identified regarding k-means and its environment:

• k-means and its associated reasoning-based versions are increasingly expensive in execution time as the data quantity increases;

• the computational cost of 𝑘 automatic estimation methods makes them slow on large datasets;

• the 𝑘 estimation methods deviate excessively from the real 𝑘 cluster number in their estimation when clusters overlap or when the constraints they impose on real cluster forms are not respected.

In the density-based methods paradigm, the methods have difficulties working on high-dimensional spaces and correctly managing low density clusters or clusters close to the same density.

In the following chapters, we respond to the above-mentioned limitations with

III.1 Introduction

In this chapter, our contributions focus on the k-means algorithm. Improvements concern both execution time and partitioning results.

In the literature, two main limitations related to k-means have been identified. The first one is the execution time of k-means, which becomes longer and longer as datasets get more massive. So, k-means has difficulties in scaling because it has a temporal complexity proportional to 𝑘𝑛𝑡 with 𝑡 the number of iterations, 𝑘 number of clusters and 𝑛 number of points (Jain, 2010b). Indeed, the calculation cost in a single iteration increases significantly as 𝑛 and 𝑘 increase. This limitation remains true for accelerated versions of geometry-based k-means even though they perform fewer calculations than the standard version. Typically k-means is used for pre-processing applications. Its usage time must be fast. In a large data environment, this property could be lost.

The other limit consists in requiring the user, for k-means, to predefine the value of 𝑘. Thus, determining inaccurately value of 𝑘 has a direct negative impact on the clustering quality. Different solutions have been proposed to estimate the relevant number 𝑘 of clusters [START_REF] Hamerly | Making k -means even faster[END_REF]Elkan, 2003, Pelleg and[START_REF] Moore | The anchors hierarchy: Using the triangle inequality to survive high dimensional data[END_REF]. Among the limitations of these solutions, we show three major ones:

• they call k-means several times on the same data. Consequently, in a large data context, repetitive access to data caused by the repetitive use of k-means on the same data make them computational time-consuming or unusable for applications that require applications that require a relatively fast response time;

• they hardly support overlapped clusters. This problem can lead to two different cases. i) overestimating the number of clusters exaggeratedly compared to the actual number, thus producing a very poor clustering quality. ii) significantly increasing the processing time;

• they pose a priori a strong hypothesis on the shape of the real cluster. Thus, X-means seeks to form isotropic Gaussian clusters (i.e. strictly spherical clusters where the dimensions have the same variance). G-means seeks to form Gaussian clusters (i.e. spherical or elliptical). In reality, clusters may not be Gaussian and could have a complex shape integrating more or less spherical sub-forms.

In response to the limitations mentioned, we propose two different contributions to k-means:

• sk-means: a solution designed to meet the first limitation, i.e., the one related to execution time. Sk-means aims to accelerate the execution time of standard k-means (Lloyd's version) and its versions based on geometric reasoning while having a near similar partitioning result. Indeed, the acceleration is due to the • Kd-means: a solution addressing the limitations related to the a priori estimation of the number of clusters, i.e., the limitations related to the estimation execution time, the overlap of real clusters, and the strong assumption on the shape of clusters. Kd-means estimates the number of 𝑘 clusters for large datasets. Indeed, Kd-means is an algorithm based on the KD-tree [START_REF] Bentley | Multidimensional binary search trees used for associative searching[END_REF] data tree structure and a hierarchical process. In the first step, the data and their corresponding metadata are hierarchized in Kd-tree. These data, organized in groups in the Kd-tree leaves, are merged progressively from bottom to top to form final clusters. To guide point group merges, we have defined several new inter-cluster merge criteria to support complex and overlapping clusters more effectively. Kd-means is better suited than its competitors for large datasets and pre-processing tasks for data analysis projects requiring a reasonable response time.

In this chapter, the sections III.2 and III.3 are devoted respectively to Sk-means and Kd-means. Each of these sections is divided into two parts: 1) the presentation and explanation of the solution process; 2) and the solution robustness experimental validation against its competitors.

III.2 SK-means

III.2.1 Introduction

In the standard version of k-means (Lloyd's version), and especially in its assignment phase, 𝑛 × 𝑘 distances are calculated at each iteration with 𝑛 the number of points and 𝑘 the number of clusters to be identified. This phase is formulated as a problem of finding the nearest neighbor for each point, except that the neighbor of a point is not any point but a centroid. Each point is then assigned to its neighboring centroid cluster. In this context, the larger 𝑛 and 𝑘 are, the higher the computational cost.

This cost is even higher if the distance function is also computationally expensive.

As we have seen in the literature, several accelerated versions of k-means have been proposed. Among them, the versions based on geometric reasoning whose most essential tool is the triangular inequality. These versions focus precisely on the kmeans first phase. Their goal is to identify each point's closest neighbor while being computationally less expensive than Lloyd's version.

In order for versions based on geometrical reasoning to generate run-time accelerations, they rely on new variables they have introduced and calculations associated with them. It should be noted that the gain (in execution time) should absorb these additional costs. In some cases, these costs may exceed the gain.

Each point is assigned variables, called bounds. These variables' function is to ensure the validation of tests using triangular inequality to minimize the number of point-centroid distance calculations. Nevertheless, they must be maintained and updated at least once at each iteration. If the tests fail, further updates may be required. E.g., in the Elkan version, each point is associated with an upper bound and 𝑘 lower bounds, which means that a total 𝑛 + 𝑛 * 𝑘 limits must be managed at each iteration for the whole dataset. Updates result in either addition or subtraction adjustments or distance calculations.

One of the reasons for these costs is that the information on the data points' longterm movements during the iterations is not exploited for the following iterations(note that a movement of a point means that it changes cluster). Whether in k-means or its accelerated versions, there is no information saved on the long-term dynamicity of the points during the process (i.e., during a sufficiently long number of iterations). Instead, the accelerated versions focus more on the nearest neighbor (centroid) problem for a given iteration without having a strategy with a global view on all iterations where information can be exchanged even between two inconsequential and distant iterations.

In short, the information of one iteration is lost for the following iterations and, more particularly, the iterations that are a bit distant.

The objective of our contribution in this section is to propose a novel strategy to reduce the additional computational cost of Lloyd's version and the versions based on geometric reasoning while keeping the partitioning almost identical. This strategy can be integrated into the standard version of k-means (Llyod version) and its accelerated versions based on geometric reasoning. The integration of the strategy in these versions always allows them to work with the external environment. Indeed, they can always be coupled with the same centroid initialization methods as if they did not integrate the strategy and support the same distance metrics, including Euclidean distance.

III.2.2 Optimization strategy

In this sub-section, we introduce the strategy, as well as elements containing it, whose goal is to accelerate standard k-means and its geometry-based accelerated versions.

During the k-means process (including its geometry-based versions), there are several point categories defined by the movement degree of the points (the cluster change of a point in an iteration is a movement):

• points move from one cluster to another in a recurrent way. These points are very dynamic;

• points that move less frequently, they are less dynamic;

• points, which during a series of consecutive iterations, change clusters, then from a given iteration, they remain attached to a cluster until the process end;

• points that do not move from the first iteration, they are assigned to a cluster to which they will remain fixed until the process end.

The points of the first group are very dynamic, they are the ones that keep the process going. So, as soon as the points in this category no longer change cluster then the k-means process ends. So, we focus mainly on the last three categories.

Our goal is to identify the least dynamic points, i.e. belonging to one of the last three categories. Indeed, these points represent a significant cost in time because they As a consequence of the introduction of 𝑠, we define for each cluster 𝐶 𝑗 two different parts corresponding to two data disjoint subsets: the kernel 𝐼𝐶 𝑗 ⊆ 𝐶 𝑗 and the outer part 𝐶 𝑗 ∖𝐼𝐶 𝑗 . The kernel consists of points fixed to the cluster 𝐶 𝑗 until the process end. The outer part is the point set that are likely to change cluster in the following iterations. Before the process begins, 𝐼𝐶 𝑗 = ∅, while the other part is equal to 𝐶 𝑗 . By using the information about the points' stability in 𝑠, the 𝐼𝐶 𝑗 kernel is gradually fed during the process. Each time a point is considered to be stabilizing, it is moved into the kernel. We call this point as passive. In this example III.2, we will show how points are moved between the kernels and the outer parts through different iterations. In the example, a k-means process of three clusters is schematized. At iteration 𝑡 (𝑡 > 1, which does not correspond to the process beginning), a kernel is already constituted in each cluster. In clusters 𝐶 1 and 𝐶 2 , there are still points (red points) that can change clusters. In cluster 𝐶 3 , the kernel is equivalent to the whole cluster. However, it could receive new points from the other clusters in the following iterations. At iteration 𝑡 + 𝑎(𝑎 > 1), clusters 𝐶 1 and 𝐶 2 lose points, which were not in the kernel, to 𝐶 3 . On the other hand, cluster 𝐶 3 considers these points unstable (red) and, therefore, not integrated into its kernel. At iteration 𝑡 + 𝑏(𝑏 > 𝑎), 𝐶 3 integrates the points into the kernel, gained at iteration 𝑡 + 𝑎, because they are considered passives. At the same time, it gains two other points from 𝐶 1 , but it considers them dynamic. Among the three points considered as dynamic in 𝐶 2 at iteration (𝑡 + 𝑎), 𝐶 2 considers two of them as passive at iteration 𝑡 + 𝑏. Nevertheless, the rest remained dynamic. The question that arises is why this point has not been given the same consideration as the other two, whereas from iteration 𝑡 to iteration 𝑡 + 𝑏 -1, they were all dynamic. There are two possible answers to this. The first one indicates that if the dynamic point is fixed to the 𝐶 2 cluster from iteration 𝑡 to 𝑡 + 𝑏, then the two other passive points are fixed to the 𝐶 2 cluster before their dynamic neighbor, i.e., before the iteration 𝑡 until their integration in the 𝐶 2 kernel. The second considers that if the third points are set to 𝐶 2 from 𝑡, then the dynamic point has at least once changed cluster between 𝑡 and 𝑡 + 𝑏, and the others have not.

During all these iterations of the example, 𝑠 was updated and used to integrate points into kernels. Indeed, before the process was launched, all 𝑠 𝑖 is equal to zero. At each iteration, for any point 𝑥 𝑖 that does not belong to a kernel and does not change cluster during two successive iterations, then 𝑠 𝑖 is incremented. Otherwise, it is reset to zero.

As soon as a point integrates a kernel, it is no longer treated in the following iterations in the calculation of point-centroid distances because it is considered passive.

Consequently, most likely, its current centroid remains closest to it compared to the other centroids until the end of the process.

To assert that a point is passive and therefore sufficiently justified to integrate it into a kernel, so we defined the following condition setting the minimum stability threshold of a point according to its cluster changes :

Definition III.1. Given 𝑟 ∈ N * , 𝑥 𝑖 ∈ 𝑋 a data point, 𝑥 𝑖 is passive if at least during 𝑟 successive iterations, it has not changed cluster.
As soon as the point 𝑥 𝑖 is considered stabilizing, i.e., 𝑠 𝑖 ≥ 𝑟, it is passive because it is integrated into the kernel and is no longer the object of calculations in the subsequent iterations. On the other hand, active points (points outside the kernel) continue to be involved in calculations until they are passive. The value of 𝑟 must be large enough to ensure that the kernel centroid containing 𝑥 𝑖 is always the closest after the qualification of 𝑥 𝑖 as passive.

The value of 𝑟 is calculated from an estimator 𝐸 that we have developed. It depends on several characteristics of the data. The relationship between 𝑟 and these

III.2.3 Intact convergence

In the following, we discuss the convergence of k-means and its versions that integrate the Sk-means strategy. However, before detailing this aspect, we introduce the following definition (see also figure III.3):

Definition III.2. Given 𝑥 𝑖 ∈ 𝑋 a given point, 𝑥 𝑖 is stable if it 1) passive (i.e. it respects the definition III.1) and 2) its centroid (that of the iteration in which 𝑥 𝑖 became passive) remained the closest until the k-means process end. If the second condition is not met then the point is passive non-stable.

The convergence property of k-means (Lloyd's version and the versions based on geometrical reasoning) is maintained even if they integrate the Sk-means strategy.

Convergence means that the values of all centroids do not change during two successive iterations. This means that the objective function has been locally optimally optimized according to the initial centroids (the objective function result differs according to the spatial positions of the initial centroids). In our case, convergence, in addition to its first meaning, could also be due to the change of all active points into passive points.

A first element contributing to the k-means convergence is that there is a finite number of ways to divide a set of 𝑛 points into 𝑘 clusters. This number is an a priori known integer equivalent to the Stirling number

𝑠𝑡 = 1 𝑘! ∑ 𝑘 𝑗=0 (-1) 𝑘-𝑗 ( 𝑘 𝑗
)

𝑗 𝑛 [START_REF] Graham | Concrete Mathematics: A Foundation for Computer Science[END_REF]. So, it depends only on 𝑛 and 𝑘. This number remains unchanged even if some data points become passive. Moreover, in a k-means (integrating or not sk-means) run, only a few of 𝑠𝑡 possible solutions are produced (one possibility by iteration). However, this first element in itself is not enough. It is necessary to show that k-means, iteratively, improves the partitioning more and more according to the objective function until reaching the final partitioning. From the optimization view point, this consists in minimizing the k-means objective function (𝑠𝑠𝑒) monotonically at each iteration until the minimum possible local solution is obtained. Note that both phases of k-means contribute to this minimization. So we will show that Lloyd's version and the versions based on geometric reasoning integrating Sk-means converge.

We show this in the first phase and then in the second phase.

Let 𝑎 = {𝑎 𝑖 |𝑖 = 1...𝑛} with 𝑎 𝑖 the index (natural number) of the cluster to which point 𝑥 𝑖 has been assigned. Let 𝑎 ′ = {𝑎 ′ 𝑖 |𝑖 = 1...𝑛} where 𝑎 ′ 𝑖 , corresponds to the new index of the centroid of point 𝑥 𝑖 , replacing 𝑎 𝑖 .

First phase. Let 𝐺 be the set of centroids where 𝐺 𝑗 is the centroid of cluster 𝐶 𝑗 , the objective function (also called intra-cluster variance or sum of squared errors(𝑠𝑠𝑒)) that k-means minimizes is defined as follows:

𝑃 (𝑋, 𝐺, 𝑎) = 𝑛 ∑ 𝑖=1 𝑑𝑖𝑠(𝑥 𝑖 , 𝐺 𝑎 𝑖 ) 2 (III.1)
If the objective function 𝑃 must decrease monotonically during iterations, so the following equation must be respected:

𝑃 (𝑋, 𝐺, 𝑎 ′ ) -𝑃 (𝑋, 𝐺, 𝑎) = 𝑛 ∑ 𝑖=1 (𝑑𝑖𝑠(𝑥 𝑖 , 𝐺 𝑎 ′ 𝑖 ) 2 -𝑑𝑖𝑠(𝑥 𝑖 , 𝐺 𝑎 𝑖 ) 2 ) ≤ 0 (III.2)
If we reduce 𝑃 to the individual level of each point, we get:

𝑑𝑖𝑠(𝑥 𝑖 , 𝐺 𝑎 ′ 𝑖 ) 2 -𝑑𝑖𝑠(𝑥 𝑖 , 𝐺 𝑎 𝑖 ) 2 ≤ 0 (III.3)
When the point is active, the inequation III.3 is necessarily respected. Indeed, if

𝑥 𝑖 changes cluster, i.e. 𝑎 𝑖 ̸ = 𝑎 ′ 𝑖 then 𝐺 𝑎 ′
𝑖 is necessarily closer to 𝑥 𝑖 than 𝐺 𝑎 𝑖 because the first phase of k-means looks for the nearest centroid for each point. If 𝑥 𝑖 does not change cluster, III.3 is true because the difference in its left part is zero.

If the point is passive, whether it is stable or not, then III.3 is null. It acts on 𝑃 as if it was active but except that it does not change cluster (i.e., 𝑎 𝑖 = 𝑎 ′ 𝑖 ). Thus, removing points from the point-centroid distance calculations in the k-means first phase, this phase still reduces the intra-cluster variance between the points and the centroid of each cluster.

44CHAPTER III. PARTITION-BASED CLUSTERING METHODS OPTIMIZATION

Second phase

Let 𝐺 ′ be the set of new centroid values calculated from 𝐺. We show that the intracluster variance of each cluster (local 𝑠𝑠𝑒 of the cluster) is reduced from one iteration to another. We show that this variance is minimized optimally at each iteration by updating centroids using the arithmetic mean. We reason with the Euclidean distance for this phase, but the underlying idea remains the same for other distances, i.e., showing that the intra-cluster variance decreases monotonically.

Let the intra-cluster variance 𝑃 (𝑋, 𝐺 ′ 𝑗 , 𝑎 ′ ) = ∑ ∀𝑥 𝑖 ∈𝐶 𝑗 𝑑𝑖𝑠(𝑥 𝑖 , 𝐺 ′ 𝑗 ) 2 (we consider that 𝐶 is up to date with respect to a'). Since 𝑃 (𝑋, 𝐺 ′ 𝑗 , 𝑎 ′ ) is quadratic (and therefore convex) (Jain, 2010a) then it is optimal when the derivative of 𝑃 (𝑋, 𝐺 ′ 𝑗 , 𝑎 ′ ) is zero:

𝑑𝑃 (𝑋, 𝐺 ′ 𝑗 , 𝑎 ′ ) 𝑑𝐺 ′ 𝑗 = ∑ ∀𝑥 𝑖 ∈𝐶 𝑗 2(𝑥 𝑖 -𝐺 ′ 𝑗 ) = 0 (III.4)
,which implies

𝐺 ′ 𝑗 = 1 |𝐶 𝑗 | × ∑ ∀𝑥 𝑖 ∈𝐶 𝑗 𝑥 𝑖 (III.5) , hence 𝑃 (𝑋, 𝐺 ′ 𝑗 , 𝑎 ′ ) -𝑃 (𝑋, 𝐺 𝑗 , 𝑎 ′ ) = ∑ ∀𝑥 𝑖 ∈𝐶 𝑗 𝑑𝑖𝑠(𝑥 𝑖 , 𝐺 ′ 𝑗 ) 2 - ∑ ∀𝑥 𝑖 ∈𝐶 𝑗 𝑑𝑖𝑠(𝑥 𝑖 , 𝐺 𝑗 ) 2 ≤ 0 (III.6)
The active, stable passive and non-stable passive points, in this phase, are not differentiated because their values, at a given iteration, in a given cluster 𝐶 𝑗 , are taken into account in the calculation of the new arithmetic mean, the centroid average

𝐺 ′ 𝑗 .
Note that the arithmetic mean is not the value that minimizes the second phase at best for other distances; e.g, for the Manhattan distance, the median is chosen instead of the average. In this case, another version is obtained, k-medians instead of k-means.

III.2.4 Integration

In If not, the inner test is then activated. The latter conducts additional tests, via bounds, in order not to calculate all the distances between the point and the other centroids, i.e., some distances must be calculated while others must not.

We have integrated Sk-means in four algorithms: Lloyd's (Lloyd, 1982a), Comparemeans [START_REF] Phillips | Acceleration of k-means and related clustering algorithms[END_REF], Sort-means [START_REF] Phillips | Acceleration of k-means and related clustering algorithms[END_REF] and Exponion [START_REF] Newling | Fast k-means with accurate bounds[END_REF] versions (they are called original algorithms). The latter resulted, via integration, in optimized versions. The algorithm 1 describes how Sk-means integrates with the original versions. The algorithm is general and adapted to these versions.

The adaptation of this algorithm to one of the original versions results in the optimized version. Among the inputs of this algorithm is the value of 𝑟. This value is either calculated using our 𝐸 estimator or the user provides it. Then the set of 𝑠 is initialized to 0 for each of the points of 𝑋.

III.2.5 Experimental assessments III.2.5.1 Introduction

In this part, the Sk-means robustness against competitors is assessed.

First of all, we will also study how the 𝐸 estimator was constructed experimentally (part III.2.5.2). Then, using this estimator, we will show that the algorithms that benefit from the Sk-means strategy are significantly faster than the corresponding versions that do not benefit from it while having almost identical partitionings (part III.2.5.4). Various data sets have been used to show this gain.

III.2.5.2 Experimental protocol for the estimator 𝐸

In part III.2.2, we discussed about the estimator 𝐸 estimating the minimum number of successive iterations (noted 𝑟) during a point must remain attached to a cluster to be considered a passive point. In this section, we explain the experimental approach that led to this estimator.

Before starting experiments, we postulate that the value 𝑟 depends on the number of points, the dimension, the number of clusters, and the spatial distribution of the initial centroids. In other words, this dependence means that the value 𝑟 is defined according to the data characteristics (controlled by parameters). To verify this postulate, three steps were performed. First, different synthetic data sets were generated.

Then on each of them, k-means was run. Then, statistical tests were applied to the launches' results, which led to the validation of the postulate and the 𝐸 estimator's inference.

Data generation. This step aims to generate datasets that are varied enough for better representativeness of the synthetic and real data encountered in practice.

The data sets are generated in hyper-cubes (generalized multi-dimensional cubes). A hyper-cube, associated with a single dataset, allows to frame the dataset and control the data's spatial distribution. To obtain varied data sets, the values of different parameters characterizing the datasets have been varied (see table III.3). As an example, the inter-cube distance is one of the parameters for obtaining various data sets. Its influence is clear in the figures III.6 and III.7 showing two data sets of eight clusters of the same dimension (𝑑) and each having the same number of points (𝑛). By having an inter-cube distance of 0.2, the dataset (figure III.6) is easier to cluster (under certain conditions), in the sense that the same clusters could be found as they are in the ground truth. With a distance of -0.2, the clusters are overlapping (figure III.7), which makes the dataset much more difficult to cluster. Between the two levels of difficulty, other values of inter-cube distance make it possible to have data sets that are more or less complicated to cluster.

In addition to the choices of the data characteristics, there are different types of

Parameter

Value set dataset cardinality(𝑛 = |𝑋|) {2 × 10 3 ,1 × 10 4 ,2 × 10 4 ,4 × 10 4 ,5 × 10 5 ,1 × 10 5 , 2 × 10 5 ,4 × 10 5 ,6 × 10 5 ,1 × 10 6 } dataset dimension (𝑑) {2,4,6,8,10} number of real clusters (𝑐) {4,8,12,16,20,25,30} inter-cube distance {-0.2,-0.1,0,0.1,0.2} • centroid initialization method (which we refer to as 𝑖𝑚). Two methods have been chosen: 1) random choice of initial centroids, so there is no guarantee that the centroids are chosen correctly in order to have a reasonable local optimal solution according to the objective function of k-means; 2) k-means++, another alternative, is chosen because globally it proposes centroids which are sufficiently far from each other and which leads to k-means generally producing a better clustering than the random method. Nevertheless, in a concern of generality as underlined above, we wish to study the initialization method's influence on 𝑟.

Consequently, a parameter (𝑠𝑝) is proposed to characterize the spatial distribution of the initial centr oids. It is calculated as follows: given 𝑙 𝑚𝑎𝑥 the maximum value of the pairwise distances(between centroids) and a hyper-rectangle encompassing these centroids, 𝑠𝑝 is equal to the ratio of 𝑙 𝑚𝑎𝑥 to the maximum length of the hyper-rectangle. Another type of calculation of 𝑠𝑝 has been tested, but it is less efficient as shown below in the experimental results;

• the cluster number to be identified by k-means and its accelerated versions (𝑘). Indeed, 𝑘 is equal to the real cluster number in the dataset (i.e., 𝑐 = 𝑘). Despite this, in practice, the variation of the parameters 𝑠𝑝, inter-cube distance and 𝑖𝑚 leads to challenging datasets in the sense that several centroids can be in the same cluster or have very close or overlapping clusters as outlined above, which makes their clustering difficult.

A total of 1750 synthetic datasets were generated, and 3500 experiments were carried out. The results are analyzed graphically before being statistically validated.

III.2.5.3 Experimental inference of estimator 𝐸

Visual results. Graphically a monotony of scatterplots defined on two variables (parameters) is expected to state that these variables are dependent. Concretely, monotony consists in the fact that the more one variable increases in value, the more the other variable studied increases or otherwise decreases (one direction only, not both).

In figure III.8(a), in general, the scatterplot tends to grow, i.e., the more the number of points increases, the more the number of iterations increases as well. In figure This decrease means that, globally, the greater 𝑘 is, the fewer iterations there are. In figure III.8(d), a decreasing trend is noted. Even if noise is present around the majority of the points (dense region), it still maintains the general decreasing trend. We infer from this scatterplot that the closer the centroids(the smaller the 𝑠𝑝 ) are to each other (i.e., the distance between two centroids is small compared to the inter-point distances of the whole dataset), the greater the number of iterations.

In summary, graphically, we conclude that there is monotony in the four scatterplots III.8(a,b,c,d). Therefore there is dependence between the number of iterations and the other parameters 𝑘, 𝑑, 𝑛 and 𝑠𝑝.

𝑇 (𝑘, 𝑑, 𝑛) = 𝑙𝑜𝑔 2 ( 𝑓 1 * 𝑛 * 𝑓 2 * 𝑑 𝑓 3 * 𝑘 ) (III.7)
The function 𝑇 (𝑘, 𝑑, 𝑛) models these monotonies. Knowing that the scatterplots involving 𝑛 and 𝑑 have an increasing monotony, they are put in the numerator, whereas 𝑘 is in the denominator because its corresponding scatterplot is decreasing. Nevertheless, the real numbers 𝑓 1 , 𝑓 2 , 𝑓 3 are used to weight the importance of influence on 𝑟 of 𝑛, 𝑑 and 𝑘, respectively. In practice, the number of iterations is generally very small or even negligible compared to the values of 𝑛,𝑑 and 𝑘. Intuitively, the binary logarithmic is adapted. Moreover, the factor 𝑓 4 is integrated to either increase or decrease the logarithmic. Statistical results. The 𝑆𝑝𝑒𝑎𝑟𝑚𝑎𝑛 test is a statistical measure used to confirm or disprove the dependence (or correlation) hypothesis between two variables. It produces two values: the correlation level and the p-value. The correlation is between -1 and 1, where 0 indicates independence of the variables, and the closer the value is to 1 or -1, the stronger the correlation. The p-value indicates the probability of making an error by rejecting the assumption (called the null hypothesis) that the two variables are independent. In a classical hypothesis test, a significance threshold 𝑠𝑔 is set to decide whether or not to reject the null hypothesis. Generally 𝑠𝑔 = 0.04, but in our study, 𝑔𝑠 = 0.01 is set to be more demanding. Note that even if the level of correlation is strong, but the p-value is higher than 𝑠𝑔, then we declare that there is independence.

𝐸(𝑘

According to the table results III.3, the null hypothesis is rejected for 𝑟 and 𝑛 because the probability of error (p-value) is 0. Moreover, their correlation rate is in line with this probability of erroneous results. It is 0.88 for 𝑛 and 0.93 for 𝑟, which repre- sents a solid correlation. Concerning 𝑘, 𝑑 and 1-𝑠𝑝, the p-value is negligible compared to 𝑠𝑔, and therefore, the null hypothesis is rejected. The dimension 𝑑 has the least influence on the number of iterations, although it is correlated with it. The spatial distribution of the initial centroids, as underlined graphically, has an important influence on the number of iterations. Another type of 𝑠𝑝 calculation tested, as mentioned above, consists in dividing the average of the pairwise distances (between centroids)

over the maximum length of the hyper-rectangle. So, the test on 1 -𝑠𝑝 produced a p-value of 4.00 × 10 -59, which shows the existence of a correlation. Nevertheless, the correlation is 0.27. It is weaker than the first type of calculation of 𝑠𝑝 (0.47).

The value of 𝑘 is a negative correlation, which validates the decreasing monotony seen graphically. In sum, the null hypothesis is rejected for all parameters, and thus, the dependence between 𝑘, 𝑑, 𝑛, 𝑠𝑝, and 𝑟, and the total number of iterations is validated.

III.2.5.4 Experimental protocol for comparing algorithms

We evaluate the Sk-means strategy applied to Lloyd's (Lloyd, 1982a), Compare-means [START_REF] Phillips | Acceleration of k-means and related clustering algorithms[END_REF], Sort-means [START_REF] Phillips | Acceleration of k-means and related clustering algorithms[END_REF] and Exponion [START_REF] Newling | Fast k-means with accurate bounds[END_REF] versions. So, our optimized versions associated with these algorithms are Ollyod, OCompare-means, Osort, OExponion. The datasets (table III.4) used are of different cardinalities and dimensions and are of different types (images, sensory data, synthetic data). All algorithms have been coded in python 3.6.

An experiment consists in running each of the eight algorithms (the four versions of k-means and their optimized versions via Sk-means) on a given dataset whose entries are :

• 𝑘 ∈ {8, 60, 200, 500}

• method of initialization (random, k-means++). Oexponion and Osort remain, on average, the favorites for practically all datasets.

They have benefited the most from the Sk-means strategy. In small and large dimensions with a very high 𝑘 value, the gains brought by the optimized versions can be very significant (191× for {Oexponion,birch,𝑘 = 500}, 149× for {Osort,covtype,𝑘 = 500}, 97× for {Osort,cup98,𝑘 = 500}. On two datasets, when 𝑘 = 8, Exponion is better than OExponion. In all other datasets, Oxponion is better, and in many cases, very much better. The other optimized versions are, in all cases, better than their original associated versions. The optimized algorithms are always better than Lloyd, which is not the case for the original compare and sort (mnist784). For very large dimensions, these two algorithms have difficulty to outperform Lloyd except slightly at 𝑘 = 500.

In this configuration, Oexponion outperforms all the others.

The quality mentioned above is measured from the relative difference. Let 𝐴 be an algorithm to evaluate and 𝐵 be a reference algorithm, the relative difference is equal:

Δ𝑠𝑠𝑒 = 𝑠𝑠𝑒 𝐴 -𝑠𝑠𝑒 𝐵 𝑠𝑠𝑒 𝐵 (III.9)
The smaller the difference, the closer A and B are in terms of clustering results.

In all cases (

III.2.6 Conclusion

K-means (Lloyd's version) is one of the best known and most used partitioning algorithms.

Nevertheless, it becomes more and more expensive to calculate as the number of points (𝑛) and the number of clusters (𝑘) increase. This is particularly true in the kmeans first phase, which requires calculating the distance between each point and the 𝑘 centroids. This is impractical in a large dataset environment. Therefore, k-means versions based on geometric reasoning have been developed to reduce point-centroid distance calculations in this phase. However, their computational complexity also increases as the 𝑛 and 𝑘 increase. Moreover, for each point, the variables (bounds) are updated at each iteration.

Therefore, we have developed Sk-means, a strategy that further reduces the number of distances between points and centroids. Its objective is to detect stable points as quickly as possible, i.e., points that will not change the cluster before the process end.

For each cluster, we defined two different parts (kernel and outer part) to separate the dynamic points (i.e., very likely to change cluster) from those that are not or slightly dynamic. Indeed, the core concentrates the stable points and the passive points (points in the process of stabilization). On the other hand, the outer part contains dynamic points. We have also designed an estimator (𝐸) to decide whether the point is passive or dynamic.

The advantage of this strategy occurs when the kernel absorbs a point. In this case, this point is no longer involved in point-centroid distance calculations until the process end. This means that 𝑘 distances are avoided at each iteration for this point.

In addition, in versions based on geometric reasoning, the bounds associated with this point are no longer maintained and updated. The higher the number of points in the kernels, the more advantageous our strategy is.

III.3.1 Introduction

As we have pointed out, three limitations have been identified concerning estimators for estimating the number of clusters 𝑘, namely:

• the overlap of clusters in the ground-truth leads estimators to deviate exaggeratedly from real 𝑘;

• the execution time is long because k-means is called at each iteration, and this time is even longer when there is an overlap of clusters;

• estimators constrain clusters to have a particular shape (spherical, elliptical).

So, we propose Kd-means to address these limitations. First, we give a global overview of the steps of the solution in III.3.2. Then, we detail these steps corresponding mainly to the Kd-tree data structure and the information stored in it (III.3.3), the construction of the data structure (III.3.4), the initialization of Kd-tree leaves (III.3.5), the hierarchical merging of clusters (III.3.6) and the cluster regularization (III.3.7).

This is followed by experimental validation of Kd-means on large and varied datasets in III.3.8. The Kd-means robustness against its competitors is demonstrated in terms of 𝑘 estimation, the quality of clustering (similarity between partitioning and ground-truth) and execution time.

III.3.2 Overview

The solution is composed of three main parts (figure III.10):

• the storage and organization of the dataset 𝑋 provided by the user in a data structure (Kd-tree);

• the processing is done on this structure to estimate 𝑘 (Merging task);

• optional improvement of the results of the previous step (Cluster regularization).

We opted for the Kd-tree [START_REF] Bentley | Multidimensional binary search trees used for associative searching[END_REF] data structure to fulfill the roles of storage and data organization. A Kd-tree is a binary tree representing a hierarchical subdivision of space using splitting planes that are orthogonal to the dimensions1 . In Subsection III.3.3.1, we discuss the advantages of Kd-tree as well as the method that builds the Kd-tree in III.3.3.

In the processing part, first of all, each leaf's points are processed independently from the points on the other leaves (see III.3.5). This process results in several clusters in the leaf. As a result, in each leaf, several clusters are constituted. Then the clusters of the nodes are merged recursively from the leaves to the root according to rules and algorithms defined in part III.3.6. These are built to manage cluster shapes as well as cluster overlap.

The final step is a regularization phase (part III.3.7). It detects small clusters and decides whether they remain separate from other clusters, or they should be merged with other clusters. This phase avoids having an overestimation of 𝑘 due to small clusters.

III.3.3 Data structure elements III.3.3.1 Kd-tree

Kd-tree puts points that are spatially close together in the same node [START_REF] Bentley | Multidimensional binary search trees used for associative searching[END_REF].

This property is exploited by several machine learning methods to accelerate calculations related to point space. One of the best-known cases is the k-closest neighbor's algorithm [START_REF] Cover | Nearest neighbor pattern classification[END_REF]. This property is advantageous to us in two cases.

First of all, it partly addresses the problem of k-means because it groups the most similar points possible in the same node. Second, it provides an optimized spatial subdivision of space to accelerate data processing. It recursively splits the whole dataset into partitions, like a decision tree acting on numerical datasets [START_REF] Gan | Data Clustering: Theory, Algorithms, and Applications[END_REF].

The root node represents the whole data space, while the leaves are the smallest possible partitions of the data space. So, a node is either a leaf, i.e., a node without child nodes, or an internal node, i.e., a node with two child nodes.

III.3.3.2 Node components

To allow the node merging step (III.3.6) to run, all nodes each have at least one cluster.

Note that the clusters are formed in the leaf nodes during the leaf initialization step (III.3.5). On the other hand, in the internal nodes, they are dynamically constituted during the node merging step. Each cluster is associated with:

• the indexes referring to its points. Therefore, the data points are not stored in the node (by extension in the whole tree) but are accessible via the indexes;

• the arithmetic mean of its points, representing its centroid;

• the sum of the squared deviations (between its points and its centroid), also called sse;

• its hyper-rectangle, a geometrical object used because of its advantages in terms of set calculation and set representation in Kd-means. This object is detailed in the part III.3.3.3. Note that in each node, we annotate 𝜁 its list of hyperrectangles.

The internal nodes also have, in particular, the splitting dimension index 𝑠𝑑 as well as the associated value 𝑠𝑣. These two values are used in the construction phase of the Kd-tree (part III.3.4).

III.3.3.3 Hyper-rectangle

As outlined above, each cluster is associated with a hyper-rectangle. The latter is a necessary element for the node merging step. Formally, it corresponds to the smallest possible rectangle (generalized to 𝑛 dimensions) covering all the data points of a set.

It is defined by the following equation:

𝐻 = {𝑥 𝑖 |∀𝑖 𝑥 𝑚𝑛 ≤ 𝑥 𝑖 ≤ 𝑥 𝑚𝑥 } (III.10)
where, 𝑚𝑛 and 𝑚𝑥 respectively represent indexes of the lower (𝑚𝑖𝑛𝑠) and upper (𝑚𝑎𝑥𝑒𝑠) bounds of the hyper-rectangle. Indeed, 𝑚𝑖𝑛𝑠(𝑚𝑎𝑥𝑒𝑠) is a vector corresponding to the minimum (maximum) values of each dimension of a cluster's points(see figure III.11).

In our case, we consider a hyper-rectangle as a geometric object to approximate the overall spatial distribution of a set of points contained in the node. In other words, each of the clusters of a node is geometrically represented by a hyper-rectangle. From this representation results, in KD-means, in time-saving on the calculations that involve sets (a set is a cluster of points). For example, to calculate a distance between two sets or perform a set operation involving at least two sets, their corresponding hyperrectangles could be used. Therefore, instead of visiting all the data points of the sets, it is only necessary to use the 𝑚𝑖𝑛𝑠, and 𝑚𝑎𝑥𝑒𝑠 vectors of the hyper-rectangles for the above calculations. This greatly saves much time on large amounts of data. Although the example deals with a two-dimensional space, the hyper-rectangle can also be defined in a space of more than two dimensions.

III.3.4 Data structure construction

In this part, we focus on the strategy we adopted to build Kd-tree.

The Kd-tree is built from top to bottom. In the beginning, Kd-tree contains only one node (root), then from this one, two child nodes are formed. Then the nodes are recursively divided until the leaves are created. Each child node represents a sub-space of points. The union of the sub-spaces of both child nodes corresponds to the point space of their father. In the following, we focus on the splitting strategy of the internal nodes. The method is also applicable to spaces of more than two dimensions.

The partitioning of a data space of an internal node (i.e., not the leaf) is performed mainly based on two cutting elements that must be specified: a given dimension (𝑠𝑑)

of the node data space and a value of this dimension (𝑠𝑣). Thus the points whose value at the dimension 𝑠𝑑 is less (resp. greater) than 𝑠𝑣, then they are assigned to the child node, which is called 𝑙𝑒𝑠𝑠𝑐ℎ𝑖𝑙𝑑 (resp. 𝑔𝑟𝑒𝑎𝑡𝑒𝑟𝑐ℎ𝑖𝑙𝑑). This process is carried out recursively from the root to the leaves.

The figure III.12 illustrates this process through an example. On the left of the figure, a two-dimensional data space (axis 1 and axis 2, axis and dimension are used interchangeably) and the right the associated Kd-tree. At the beginning of the process, Kd-tree contains only the root. To divide it in two, the dimension "axis 1" is assigned to 𝑠𝑑 and the value 0.5 to 𝑠𝑣. As a consequence, the data space is divided into two at the vertical red line. A 𝑙𝑒𝑠𝑠𝑐ℎ𝑖𝑙𝑑 node (resp. 𝑟𝑖𝑔ℎ𝑡𝑐ℎ𝑖𝑙𝑑 node) is instantiated to represent the points which are to the left (resp. to the right) of the red line (i.e., their value on axis 1 is less (resp. greater) than 0.5). At this level, 𝑙𝑒𝑠𝑠𝑐ℎ𝑖𝑙𝑑 represents only the subspace on the left and 𝑟𝑖𝑔ℎ𝑡𝑐ℎ𝑖𝑙𝑑 only the subspace on the right. If we focus at the level of the left child of the root, 𝑠𝑑 = 𝑎𝑥𝑖𝑠2 and 𝑠𝑣 = 0.4, the corresponding subspace is divided in two at the black horizontal line. From this node, two child nodes result. The same procedure is used for the right thread of the root.

Several rules for splitting nodes are proposed to choose the optimal dimension and associated value for correct data separation. Among them, we opted for sliding midpoint splitting rule [START_REF] Samet | Foundations of Multidimensional and Metric Data Structures[END_REF] because it provides an optimized data organization than other classical rules [START_REF] Maneewongvatana | It's okay to be skinny, if your friends are fat[END_REF]. This performance on others is explained because:

• it does not produce empty nodes or nodes whose data space is very sparse (i.e., a very large space, specifically at the sides, compared to the data it represents when it should be small);

• it is less expensive. Indeed, the classical rules choose the median as the cutting value 𝑠𝑣. In contrast, the sliding midpoint splitting rule chooses the middle of the points ((𝑚𝑎𝑥 + 𝑚𝑖𝑛)/2), which is less expensive. The dimension 𝑠𝑑 chosen is the one that is the longest (𝑚𝑎𝑥 -𝑚𝑖𝑛).

Note even with this splitting rule, theoretically there is no guarantee on the limit of the depth that Kd-tree can have, the trees could be very deep (so the time of tree construction is increased). As a result, we have added two stopping conditions to avoid deep trees. These two conditions are performed at the beginning of the method that partitions the node in two. If one of the conditions is verified then the node is not divided and it is considered as a leaf:

• the depth of the leaf is limited to 𝑙𝑜𝑔(𝑛) to save construction time compared to the normal time taken if the depth is not limited. The root has a depth of 1;

• each node is limited by a minimum number of points annotated ψ. It is not interesting to have leaves with a number of points close to one in a context of massive data. This would result in a very long Kd-tree construction time and therefore make our solution unsuitable for near real-time applications. Besides, if the sum of the number of points of the node is less than 2 * ψ then it is a leaf. Indeed, two cases are possible if this limit is not defined. Either the two children will be leaves if their number of points (size) is less than ψ. Either the size of one will be greater than ψ and therefore the other is a leaf. In the latter case a difference in depth will occur which brings a certain imbalance of the tree.

This condition limits the number of small leaves and the depth of the tree, and contributes to the tree's balance.

III.3.5 Leaf initialization

After building the Kd-tree, we estimate in each leaf (we annotate 𝜐 the leaf node's index) the number of clusters. At the same time, the clusters are produced. For this we have adapted G-means [START_REF] Hamerly | Learning the k in k-means[END_REF] called 𝑒𝑠𝑡𝑖𝑚𝑎𝑡𝑒𝐾 (see Algorithm 2). It takes into account the problem related to G-means concerning the exaggerated overestimation of the number of clusters in the case of overlapping. Then, the 𝑒𝑠𝑡𝑖𝑚𝑎𝑡𝑒𝐾 algorithm produces a limited number of clusters in the leaves. Indeed, at each iteration 𝑡, 𝑒𝑠𝑡𝑖𝑚𝑎𝑡𝑒𝐾 produces 𝑘 𝑡 clusters. We introduce 𝜌 a threshold that controls the maximum number of clusters to produce. Let 𝑤 be the number of leaves that Kd-tree has, 𝜌 is then defined as follows: 𝜁 𝑗 𝑚𝑖𝑛𝑠 ← 𝑚𝑖𝑛(𝐿𝐷 𝐼 𝑗 ) 10: end for As soon as 𝑘 𝑡 ≥ 𝜌 then 𝑘 𝑡 is chosen for the leaf. Note that 𝑘 𝑡 could be up to 2 𝑡 . This case occurs when all centroids have been divided into two new centroids because they have not been evaluated as Gaussian. Note that even if the total number of clusters in all leaves exceeds 𝑘 𝑚𝑎𝑥 , then our merging algorithms bring this number closer to the real 𝑘 of the dataset.

𝜌 = ⎧ ⎪ ⎨ ⎪ ⎩ √ 𝑘 𝑚𝑎𝑥 , if
If we assume that in equation III.11, only the second condition exists, this would cause 𝜌 to tend towards a value of 1 or 0. Indeed for a given value of 𝑘 𝑚𝑎𝑥 , the greater 𝑤 is the greater the 𝜌 tends towards 1 if 𝑤 ≤ 𝑘 𝑚𝑎𝑥 . When 𝑤 > 𝑘 𝑚𝑎𝑥 then 𝜌 tends towards 0. These cases could make the solution ineffective because they would underestimate the number of clusters in the leaf and, by extension, underestimate the number of clusters in the tree dataset. The first condition is essential to balance between having an underestimation of 𝑘 if there is only the second condition and having an overestimation of 𝑘 if there is no condition that would limit the value of 𝑘.

After estimating 𝑘 in the leaf 𝜐, each cluster produced is represented by a hyperrectangle along with the associated aggregate calculations (arithmetic mean (𝐺) and the sum of the squared differences between the points and 𝐺 (𝑠𝑠𝑒)).

III.3.6 Node merging

The leaf initialization step produces clusters of points in each leaf. These clusters do not necessarily represent the final clusters, i.e., the clusters that the user has as output. In order to obtain the final clusters, the leaves' clusters are used as inputs in a hierarchical process from bottom to top.

In order to obtain final clusters, we have developed an algorithm called global merger. It consists in recursively merging clusters from the leaves to the root. The final clusters are indeed in the root. The nodes are processed according to the post-fixed path, i.e., each node is processed after each of its children is processed. Indeed, processing a node consists in executing another algorithm, local merger, on its clusters.

The purpose of this algorithm is to merge as many clusters as possible in a given node.

The local merger result contains at least:

• new clusters resulting from the merge if at least two clusters have been merged;

• clusters that may not have been merged. So, for a given node, when the results (clusters) are produced in its child nodes, then local merger is applied on this node. In this case, the algorithm has as input the child results. This merger operation is repeated recursively from child nodes to the parent node. And this, up to the root (see the example III.13 for more clarity). To summarize, the global merger algorithm visits the nodes according to the postfixed path. At each visit, the local merger algorithm is executed on a set of clusters.

In this one, we apply the merger test process per cluster pair (figure III.14).

In the following, we introduce some definitions (part III.3.6.1) in order to detail the hierarchical merging process (part III.3.6.2).

In the following, we first introduce definitions used by the local merger algorithm (by extension also by the merge test process). Then we discuss the properties of the mergeability concept, i.e., the properties that guide the decision to merge or not a cluster pair. Then we detail the merge test process (using the mergeability concept) then the local merger algorithm.

𝑎𝑝𝑑(𝜁) = ∑ (𝑢,𝑣)∈𝑃 ||𝐺 𝑢 -𝐺 𝑣 || 𝑐𝑎𝑟𝑑(𝑃 ) (III.13)
with 𝐺 𝑢 and 𝐺 𝑣 the centroids, respectively, of the points of the hyper-rectangles ℎ 𝑢 and ℎ 𝑣 .

Definition III.5. The minimum distance between two hyper-rectangles ℎ 𝑢 and ℎ 𝑣 is calculated as follows:

𝑚𝑖𝑛𝐻(ℎ 𝑢 , ℎ 𝑣 ) = ||0 -𝑓 || (III.14)
where 𝑓 = 𝑚𝑎𝑥({0, 𝑚𝑎𝑥({ℎ 𝑢 .𝑚𝑖𝑛𝑠 -ℎ 𝑣 .𝑚𝑎𝑥𝑒𝑠, ℎ 𝑣 .𝑚𝑖𝑛𝑠 -ℎ 𝑢 .𝑚𝑎𝑥𝑒𝑠})}).

Lemma III.6. Given two datasets 𝐿 ⊆ R 𝑑 and 𝑀 ⊆ R 𝑑 with 𝑛 1 = 𝑐𝑎𝑟𝑑(𝐿) and 𝑛 2 = 𝑐𝑎𝑟𝑑(𝑀 ), if the sum of squared errors (𝑠𝑠𝑒) of 𝐿 and 𝑀 are as follow:

𝑞 𝑙 = 𝑛 1 ∑ 𝑖=1 ||𝐿 𝑖 -L|| 2 𝑞 𝑚 = 𝑛 2 ∑ 𝑖=1 ||𝑀 𝑖 -M || 2
then the sum of squared errors of 𝐵 = 𝐿 ∪ 𝑀 is:

𝑞 𝑏 = 𝑞 𝑢 + 𝑞 𝑚 + 𝑛 1 || L -B|| 2 + 𝑛 2 * || M -B|| 2 (III.15)
where B is computed as the average of the weighted averages

𝑛 1 L + 𝑛 2 M 𝑛 1 + 𝑛 2 (III.16)
The formula III.15 allows calculating the 𝑠𝑠𝑒 of 𝐵 from the 𝑠𝑠𝑒 of 𝐿 and 𝑀2 . It represents a considerable gain because there is no need to iterate on the points of 𝐵.

Proof. We are trying to calculate the sum of two 𝑠𝑠𝑒:

𝑞 𝑏 = 𝑛 1 ∑ 𝑖=1 ||𝐿 𝑖 -B|| 2 ⏟ ⏞ 𝑞 𝑙𝑏 + 𝑛 2 ∑ 𝑖=1 ||𝑀 𝑖 -B|| 2 ⏟ ⏞ 𝑞 𝑚𝑏
Let focus on the first term of this equation:

𝑞 𝑙𝑏 = 𝑛 1 ∑ 𝑖=1 ||𝐿 𝑖 -B|| 2 = 𝑛 1 ∑ 𝑖=1 ||(𝐿 𝑖 -L) + ( L -B)|| 2 = 𝑛 1 ∑ 𝑖=1 ||𝐿 𝑖 -L|| 2 + 2 ( 𝑛 1 ∑ 𝑖=1 (𝐿 𝑖 -L) ) ( L -B) + 𝑛 1 || L -B|| 2 But: 𝑛 1 ∑ 𝑖=1 (𝐿 𝑖 -L) = 𝑛 1 ∑ 𝑖=1 𝐿 𝑖 - 𝑛 1 ∑ 𝑖=1 L = 𝑛 1 L -𝑛 1 L = 0 So 𝑞 𝑙𝑏 = 𝑞 𝑙 + 𝑛 1 || L -B|| 2 .
If we repeat the same calculation for the second term 𝑞 𝑚𝑏 then we obtain equation III.15.

III.3.6.2 Mergeability concept

We focus on the detection of clusters that k-means could detect (i.e., clusters close to strict sphericity) and less spherical clusters present in real data. So our goal is, first, to capture natural clusters as defined in section III.1, i.e., clusters with spherical, elliptical or more complex shapes, e.g., curved elliptical shapes. Secondly, to identify these clusters even if they overlap with each other. To achieve these two objectives, it is necessary to define the properties that lead to consider that two clusters can be merged. We have set two properties to allow us to evaluate the mergeability between any two clusters, i.e., to determine the certainty level of the hypothesis that two clusters belong to the same cluster is true. The first one is connectivity. It corresponds to the level of proximity between the masses of points of two clusters. A mass of points is the smallest sub-space of a cluster concentrating the majority of the points practically. The second property corresponds to the spatial proximity between the two clusters without necessarily their masses being close. The stronger the connectivity and proximity between two clusters, the stronger the mergeability. Proximity alone is not enough to state that two clusters are mergeable because two clusters may be contiguous or overlapping without their two masses being close to each other. In this case, connectivity is necessary.

III.3.6.3 Merger test process (MTP)

We define a set of four criteria (represented as inequalities) to evaluate how much two clusters correspond to the same cluster and therefore, to decide whether two clusters can be merged following the properties that we have mentioned. So, these criteria involve measures of proximity and connectivity between clusters. Note that the verification of the hypothesis that two clusters must be merged is done via their hyper-rectangles ℎ 𝑢 and ℎ 𝑣 . As shown in figure III.15, the sequence of these criteria forms the merge test process. This test verifies if the clusters of ℎ 𝑢 and ℎ 𝑣 belong to the same natural cluster. The test follows a precise order of the criteria. First of all, the first criterion must be validated before moving on to the second criterion; otherwise, the process stops. Similarly, the second criterion must be validated to activate the third criterion. If the latter is not checked, then the fourth criterion is triggered. It is therefore not necessary that the third criterion is validated to call the last one.

Note that merging several clusters means merging their associated hyper-rectangles.

This also involves calculating the weighted average of the already calculated averages pairs of all clusters. The pairwise distances reduce the bias brought by the very distant centroids from the majority of other centroids. The value of 𝜖 controls the boundary between the qualifiers "distant" and "close" when referring to the distance between clusters of ℎ 𝑢 and ℎ 𝑣 . If this criterion is verified, then other criteria must be verified to confirm the fusion between ℎ 𝑢 and ℎ 𝑣 . Note that the higher the value of 𝜖 is, the fewer hyper-rectangles validate the criterion. Moreover, if 𝜖 = 1, then a significant amount of hyper-rectangles will validate the criterion. This could lead to further unnecessary tests and probably to a non-merger result because if two clusters are very far apart, then there is no merger. The 𝜖 value is to be adjusted according to the strictness level of the "enough close" notion required by the criterion.

Criterion 2. Let ℎ 𝑢 and ℎ 𝑣 two hyper-rectangles, Δ𝐶 the distance between the centers of ℎ 𝑢 and ℎ 𝑣 and Δ𝐺 the distance between the centroids of the clusters 𝐶 𝑢 and 𝐶 𝑣 . If Δ𝐺 < Δ𝐶 then ℎ 𝑢 and ℎ 𝑣 are possibly mergeable.

Criterion 2 refines the set of hyper-rectangles from the first criterion. It estimates how strong the connectivity between the two clusters is. We know that a hyper-rectangle is the smallest rectangular envelope covering all the data points in a cluster.

We could then decide that the center of the hyper-rectangle would correspond approximately to the centroid of the cluster if the cluster points are uniformly distributed with some sphericity. So the cluster with these characteristics is probably a natural cluster apart. As a result, the closer the distance between centroids (Δ𝐺) is to the distance between centers (Δ𝐶), the smaller the probability of merging ℎ 𝑢 and ℎ 𝑣 . This probability is considered null when Δ𝐺 ≥ Δ𝐶. Figure III.16 illustrates an example that validates this criterion.

The first two criteria make it possible to identify relatively close clusters. However, they also consider that two clusters are distant if their centroids are also distant, even if the two clusters are contiguous. The latter could occur if the majority of points surround the centroid while a minority is far from the centroid. However, these criteria are based only on the distances applied to centroids and centers. Two clusters could be considered as close, but one or more clusters could be located between them.

In this case, they cannot be merged directly. They could only be if at least one cluster between them merges with them. The following two criteria require stricter distances and more robust connectivity to avoid directly merging two nearby clusters separated by other clusters. Criterion 3 only deals with contiguous or overlapping hyper-rectangles. Indeed 𝑚𝑖𝑛𝐻(𝑥, 𝑦) returns 0 if the two hyper-rectangles overlap or if their distance is zero. Also, a connectivity constraint is added. It results in a constraint on the proximity between centroids: for two hyper-rectangles ℎ 𝑢 and ℎ 𝑣 , the distance between centroids must be less than Δ𝐶 * 𝜆. The smaller 𝜆, the more the notion of "close enough" between clusters to match the same cluster is strict.

Criterion 4. Let ℎ 𝑢 and ℎ 𝑣 two hyper-rectangles and 𝜖 ∈ N * . We merge ℎ 𝑢 and ℎ 𝑣 when:

• Criteria 1 and 2 are verified,

• 𝑚𝑖𝑛𝐻(𝑥, 𝑦) ≤ τ 𝜖 ,

• 𝑒𝑣𝑜 ≤ 𝑡ℎ_𝑒𝑣𝑜 ∈ R + where:

𝑒𝑣𝑜 = |𝑠𝑠𝑒 𝑢∪𝑣 -(𝑠𝑠𝑒 𝑢 + 𝑠𝑠𝑒 𝑣 )| 𝑠𝑠𝑒 𝑢∪𝑣 (III.18)
with 𝑠𝑠𝑒 is the sum of the squared errors and 𝑠𝑠𝑒 𝑢∪𝑣 the 𝑠𝑠𝑒 of the 𝐶 𝑢 and 𝐶 𝑣 data points union Unlike Criterion 3, to validate Criterion 4 hyper-rectangles are not necessary to be contiguous but a maximum distance is required. Two clusters may not be contiguous or maybe nearly contiguous. A threshold on the distance between them is necessary to prevent a cluster from interposing between them. This results in the following inequity:

the distance 𝑚𝑖𝑛𝐻(𝑥, 𝑦) must be less than τ 𝜖 . The criterion also adds a requirement on the compactness of 𝐶 𝑢 and 𝐶 𝑣 clusters. To do this, it uses the homogeneity measure called sum of square error (𝑠𝑠𝑒). In this criterion, we choose to limit the quantity of 𝑠𝑠𝑒 for possible mergers. Indeed, two clusters are merged only if their 𝑒𝑣𝑜 value is less than the limit is 𝑡ℎ_𝑒𝑣𝑜. The latter is entered by the user. However, 𝑡ℎ_𝑒𝑣𝑜 is adapted according to the value of Δ𝑘 provided Equation III.19. The latter evaluates the difference between the value of 𝑘 𝑚𝑎𝑥 and the total sum of the values of 𝑘 specific to each leaf ( ∑ 𝜐∈ϑ 𝑘 𝜐 ) with ϑ the index list of all Kd-tree leaves. The purpose of this adaptation is to approach the estimated 𝑘 value on the entire dataset at 𝑘 𝑚𝑎𝑥 and avoid an overestimation of 𝑘 compared to 𝑘 𝑚𝑎𝑥 . If 𝛿𝑘 ≥ 1 it means end for 42: end while ascending ordered numerical indices. Thus the indices of the first and last elements of 𝜁 are respectively 0 and 𝑐𝑎𝑟𝑑(𝜁) -1. We consider ℎ 𝑢 to be a temporary variable of hyper-rectangle type that runs through the 𝜁 elements. The algorithm process is as follows. First, we assign the first element of 𝜁 to ℎ 𝑢 . This one is now a hyperrectangle representing a cluster. We then check if all the other clusters represented by hyper-rectangles ℎ 𝑣 are mergeable with the cluster represented by ℎ 𝑢 . If ℎ 𝑢 is not mergeable to any of them, then the next hyper-rectangle in 𝜁 is assigned to ℎ 𝑢 . On the other hand, if it is mergeable to at least one hyper-rectangle, then the concerned hyper-rectangles merge, resulting in a new hyper-rectangle (merging operated by the 𝑚𝑒𝑟𝑔𝑒 function). In this case, the first item of freshly reconstituted 𝜁 is reassigned to ℎ 𝑢 . This procedure is repeated until ℎ 𝑢 is the second last element of 𝜁, and there are no more mergers. At the level of the fusion test process, the first two criteria only select the hyper-rectangles candidates ℎ 𝑣 for the merger. At the same time, they reduce the number of hyper-rectangles to be processed in the other two criteria. While the last two decide whether to merge ℎ 𝑢 and ℎ 𝑣 or not. The global merger fusion algorithm can be seen as a layer that envelops the algorithm local merger. Intuitively, for a given internal and parent node, a good part of the clusters of one of its children is closer to each other than to the other child's clusters.

III

So we process the clusters of a child node locally but in the data space of the parent node. Hence the proposal of the global merger algorithm. It performs the merging of clusters node by node using the local merger algorithm. It starts first with the children of the "internal" node and then concatenates the hyper-rectangles lists of both children to form the list of hyper-rectangles of the internal node. Finally, local merger 76CHAPTER III. PARTITION-BASED CLUSTERING METHODS OPTIMIZATION is applied to internal. On the other hand, the value of 𝑎𝑝𝑑 changes from one node to another because it depends only on the concerned node's clusters. Consequently, if two clusters have not been merged into one of the two children nodes, they could be merged into the parent node.

III.3.7 Cluster regularization

This subsection discusses the strategy we have defined to identify clusters that should not be as such but rather be part of another cluster. The previous step algorithms could produce small (in a number of points) but compact clusters. A small cluster is located in three cases: either it is a natural cluster different from the others, or it is part of an agglomeration of small clusters that represent a single cluster, or it is part of a large cluster. The definition of a small cluster has no objective purpose. We consider the definition of the small cluster resulting from the work [START_REF] Ailon | Breaking the small cluster barrier of graph clustering[END_REF] as a cluster with a number of points less than √ 𝑛 with 𝑛 the size of the cluster. We have developed an algorithm that makes it possible to match a small cluster to one of the three cases. The goal of the algorithm is to get as many natural clusters as possible. Knowing that our solution's final result is in the root of the tree, then this algorithm is unrolled only in this one. The algorithm consists of two parts that are executed consecutively once. The first identifies the small clusters and then merges those that are close to each other. The second re-identifies small clusters from the new list of small clusters from the first part and affects those close to large clusters. If a small cluster has not undergone a merger operation in both parts, it is considered a separate natural cluster.

One of the reasons for the presence of small clusters is due to Criteria 3 and 4 where the limit of the minimum distance between hyper-rectangles is very strict. Indeed, if the minimum distance between two hyper-rectangles, at least one of which is a small cluster, is greater than this limit, they cannot be merged. This limit is respectively equal to 0 in Criterion 3 and τ 𝜖 in Criterion 4. The τ 𝜖 limit is more flexible than the first one. It was used in both parts of the algorithm to define the boundary between "close" and "distant" w.r.t the distance between hyper-rectangles. • 4-band multispectral images; they characterize different types of soil. The corresponding dataset is 𝑠𝑎𝑡𝑖𝑚𝑎𝑔𝑒;

• sounds; the 𝐽𝑎𝑝𝑎𝑛𝑒𝑠𝑒𝑉 𝑜𝑤𝑒𝑙𝑠 dataset is a set of digitized Japanese vowel sounds.

Each sound is associated with a speaker;

• historization of people's activities; the 𝑙𝑑𝑝𝑎 dataset is a collection of the positions of sensors present on people to identify the movement they perform at a given time. The 𝑤𝑎𝑙𝑘𝑖𝑛𝑔 dataset is a set of people's activities designed to determine the authors;

• images represented by a set of characteristics. These are related to the objects to be identified and are extracted from the images.. For example, in the 𝐹 𝑜𝑢𝑟𝑖𝑒𝑟 dataset, each record is a set of coefficients of the character (between 0 and 9) shapes. Similarly, in 𝑍𝑒𝑟𝑛𝑖𝑘𝑒, each instance is a rotation invariant Zernike moments of the digit image(between 0 and 9). In 𝑃 𝑒𝑛𝑑𝑖𝑔𝑖𝑡𝑠 each individual is a sequence of positions characterizing a digit. In 𝐿𝑒𝑡𝑡𝑒𝑟, each instance of a letter of the English alphabet contains statistical moments and edge counts of the given letter. In 𝑉 𝑒ℎ𝑖𝑐𝑙𝑒 dataset a data point is just a set of geometric characteristics of a given vehicle;

III.3.8.2.3 Metrics for evaluating experimental results

For evaluating the results of the three algorithms, we used three metrics: first, the execution time (Δ𝑡) of the algorithm, the relative difference (Δ𝑘) [START_REF] Bennett | Using and Understanding Mathematics: A Quantitative Reasoning Approach[END_REF] between the 𝑘 actual value and the 𝑘 estimated value, and finally, the distance between the actual partitioning and the partitioning proposed by the algorithm.

The relative difference is calculated as follows:

Δ𝑘 = |𝑘 𝑟𝑒𝑎𝑙 -𝑘 𝑒𝑠𝑡𝑖𝑚𝑎𝑡𝑒𝑑 | 𝑘 𝑟𝑒𝑎𝑙 (III.21)
The relative difference compares two measurements relative to a reference measure-80CHAPTER III. PARTITION-BASED CLUSTERING METHODS OPTIMIZATION ment (𝑘 𝑟𝑒𝑎𝑙 ). In our case, the relative difference is better than the absolute difference |𝑘 𝑟𝑒𝑎𝑙 -𝑘 𝑒𝑠𝑡𝑖𝑚𝑎𝑡𝑒𝑑 | because the latter does not consider the measurement scale, e.g., the difference between 10 and 11 is not the same as between 1000 and 1001.

The more the relative difference Δ𝑘 tends towards 0, the closer the estimated value 𝑘 is to that of the ground truth. The variation of the information (𝑣𝑖) [START_REF] Meilă | Comparing clusterings by the variation of information[END_REF] Table III.9: Comparison of the three algorithms executed on synthetic data. Note that Δ𝑡 is expressed in seconds. In the Δ𝑡 sub-column of the G-means and X-means columns, the number in brackets represents how many times our algorithm is faster than the compared algorithm.

III.3.8.3 Runtime analysis

If we consider the three algorithms' performance according to the metric Δ𝑡, Kdmeans takes the least time to provide a clustering result. This is true in synthetic and real data and regardless of the value of 𝑘, 𝑑 and 𝑛. Our algorithm is 5.5 to 12.9 for X-means and Kd-means. That is 15.48 minutes for Kd-means and 10 hours for X-means. In the case of G-means, the maximum is even higher comparing to the other algorithms, and it is reached at 16.48 hours (𝑘 = 4, 𝑑 = 18, 𝑛 = 1 × 10 6 ).

III.3.8.4 Cluster quality analysis

Kd-means is better than other algorithms in estimating k with good clustering quality in synthetic and real data.

In the synthetic data, Kd-means does not exceed 0.47 in Δ𝑘 and 1.2 in 𝑣𝑖. Xmeans even reaches Δ𝑘 = 3.72 and 𝑣𝑖 = 3.4. The same for G-means with Δ𝑘 = 8.1

and 𝑣𝑖 = 2.8. The decrease in Δ𝑘 G-means when 𝑘 increased in the synthetic data is due to the presence of many Gaussian clusters that are well separated from each other. Kd-means has a better estimate of good quality than the others. In terms of 𝑣𝑖, it is, on average, 2.46 and 3.05 better than G-means and X-means. Same performance in Δ𝑘, it is better on average by 2.83 (G-means) and 4.29 (X-means). It could be pointed out that G-means is better than X-means in terms of quality (𝑣𝑖) in several combinations of (𝑘, 𝑑, 𝑛).

In real data, the Kd-means maxima do not exceed Δ𝑘 = 3.81 and 𝑣𝑖 = 7.2. They are higher for X-means and G-means, they reach respectively (Δ𝑘 = 4. 1.2 186.9(1.34) 2.0 366.6(3.58) 3.4 6 1 × 10 6 96.2(0.37) 0.9 167.0(1.09) 1.6 376.1(3.7) 3.2 2 × 10 6 97.4(0.39) 0.9 186.2(1.33) 1.8 375.0(3.69) 3.2 4 × 10 6 92.8(0.4) 1.1 200.4(1.51) 1.7 363.3(3.54) 2.9 8 1 × 10 6 57.5(0.28) 1.2 207.8(1.6) 2.0 377.2(3.71) 2.2 2 × 10 6 98.6(0.43) 0.9 150.2(0.88) 1.4 373.6(3.67) 3.2 4 × 10 6 99.2(0.47) 1.0 166.9(1.09) 1.5 377.7(3.72) 3.2 Table III.12: Comparison of the three algorithms, on real data, with respect to the quality of clustering(vi) and the k estimation.

synthetic clusters (Gaussian). As a result, these complex representations of clusters are difficult to capture completely point by point. This increase is much higher for G-means because it tends to identify Gaussian clusters in particular. However, clusters in real data are not necessarily Gaussian because they are not constituted by Gaussian distribution generators. As a result, G-means makes an excessive overestimation of k (therefore Δ𝑘 high) compared to Kd-means. Our algorithm is the least affected by the gaussianity aspect of the clusters. Because, in its operation, gaussianity is not explicitly sought.

III.3.8.5 Clustering complexity analysis of real data

Figure III.17: Real datasets characterized by overlap and eccentricity measurements.

In this sub-section, we analyze the intrinsic complexity of the real datasets. For each dataset, we evaluate its difficulty to be clustered. For this, we used two metrics: eccentricity and overlap. These make it possible to characterize the problems to which Kd-means responds. Eccentricity is a positive real number that characterizes the shape of a set of points [START_REF] Chekanov | Searches for tev-scale particles at the lhc using jet shapes[END_REF]. If it is equal to 0, the shape is strictly spherical, and when it approaches 1, it tends towards a very elongated elliptical shape. When it is equal to 1, it corresponds to another more complex shape. It is calculated in the following way for two-dimensional datasets:

𝑒𝑐𝑐 = √ 1 - 𝑏 2 𝑎 2 (III.22)
Where b is the smaller half axis (i.e., half the length of a dimension) and a is the larger 84CHAPTER III. PARTITION-BASED CLUSTERING METHODS OPTIMIZATION half axis.

For datasets of more than two dimensions, the eccentricity is estimated as follows.

First of all, all pairs of dimensions of a dataset are listed. Then the eccentricity is calculated for this dataset at the level of each pair. Then the average of all eccentricities is calculated. This is done for each class independently. Then the maximum of the eccentricities of the classes is calculated. Note that a class is a set of points belonging, in the ground truth, to the same group or phenomenon. The choice of the maximum is justified by the fact that if there is a class with a complex form, the algorithms for estimating 𝑘 have more difficulties, even if other classes with simpler forms are in the same dataset. This difficulty is reflected in the clustering quality produced as well as in the overestimation of 𝑘 with respect to reality.

The measure of overlap is a positive value between 0 and 1, which indicates at the global level of the dataset the level of overlap between classes of points. The value 0 indicates that there is no overlap, and 1 indicates that the classes are practically confused. It is calculated as follows. First of all, for each data point, we calculate its distance to 𝑝 (set to 11) nearest neighbors, then we count the number of points belonging to the same class as the current point in its neighborhood. Intuitively, if there are many points not belonging to the same class as the current point in its neighborhood, it means that it is close to one or more other classes. So there is overlapping. A threshold of 25% is set at which overlapping is considered to exist.

That is to say that at least 25% of points in the neighborhood of the current point must be different from it to consider the point as contributing to overlapping. Finally, a ratio is calculated by counting the points generating overlapping over the total number of points.

In figure III.17, we notice that all datasets have a strong ellipticity concerning the class shapes (eccentricity > 0.69 for all real datasets). Almost 72% of the datasets have an eccentricity higher than 0.95. This means that classes at this level have more difficult shapes than the elliptical one. Almost all of them correspond either directly to images or datasets related to images. The most difficult datasets could be those with high eccentricity and a high degree of overlap. Taking tables III.10 and III.12 into account, they correspond to walking, letter, ldpa, emnist, and zernike. In the case of Kd-means, it succeeds in estimating the number of clusters closest to real 𝑘 while maintaining good quality and a short execution time compared to competitors. This is the case when it is used on the most complex datasets either with a high overlapping rate (e.g., vehicle overlapping rate > 0.6) or with elliptic classes or with a complex shape (e.g., zernike eccentricity > 0.9981 or fashionmnist eccentricity equal to 1.0). We analyze the three metrics (Δ𝑡, 𝑣𝑖 and Δ𝑘) according to 𝑡ℎ_𝑒𝑣𝑜 and ψ. This is done in both data contexts (real and synthetic).

In Tables III.13 and III.14, 𝑡ℎ_𝑒𝑣𝑜 and ψ do not have a particular influence on the execution time of Kd-means. Indeed, the range (the difference between the maximum and minimum values) of Δ𝑡 does not exceed 10.2 seconds concerning ψ. It is about 30 seconds for 𝑡ℎ_𝑒𝑣𝑜. If we take into account the Δ𝑡 magnitude of the three algorithms, these differences are negligible.

In the synthetic data, concerning ψ, the values of Δ𝑘 are identical except for ψ = 4 where the value is slightly higher than the others by 0.2. The values of 𝑣𝑖 have a maximum difference of 0.4. This difference is 0.1 when ψ ∈ [8, 10, 12] for which 𝑣𝑖 is minimal. At ψ = 4 Δ𝑘 is slightly higher by 0.3 compared to the rest. In real data, the range is 1.1 for 𝑣𝑖 but at 0.2 if ψ ∈ [4,8]. This range is 0.7 for Δ𝑘 but drops to 0.2 for ψ ∈ [4,8,10].

Concerning 𝑡ℎ_𝑒𝑣𝑜 in the synthetic data, the values of Δ𝑘 and 𝑣𝑖 have a range of 0.2. In real data, the respective ranges of Δ𝑘 and 𝑣𝑖 are 0.5 and 0.4. They drop to 0.2 when ψ ∈ [0.20, 0.25, 0.30] for Δ𝑘 and ψ ∈ [0.15, 0.20, 0.25, 0.30] for 𝑣𝑖.

The observed ranges of the two metrics 𝑣𝑖 and Δ𝑘 are lower than those of the same metrics of the competitor's algorithms in the real and synthetic data. However, if we are stricter by just accepting ranges less than or equal to 0.2, then the optimal values, when the data are Gaussian, are ψ ∈ [8,10,12] and 𝑡ℎ_𝑒𝑣𝑜 taking all the values tested. When the data is real (not necessarily Gaussian clusters), the optimal values are ψ ∈ . Also, we compare the results of Kd-means and the Gaussian Mixture Model(GMM) (Titterington et al., 1985) method. Because the latter can detect spherical and elliptical clusters, nevertheless, it does not correspond to an estimator of 𝑘. It is then necessary to provide to GMM the 𝑘 value. We provide as an input to GMM the exact number of clusters present in the ground truth. On the other hand, we let Kd-means estimate this value automatically. Index. In six classes, Kd-means has less impurity than GMM. Among these six classes are the overlapping gravel class (overlapping rate = 0.907) and the less overlapping shadows class (overlapping rate = 0.001). A difference in impurity between Kd-means and GMM of nearly 6% is found to the advantage of Kd-means. In the second figure III.20, the results' distribution is presented through boxplots. In the latter, the Kdmeans median (0.24) is lower than that of GMM (0.36), i.e., Kd-means, globally, produces purer classes. Moreover, the results' dispersion, measured by the interquartile range, is smaller in Kd-means than in GMM, which shows that Kd-means has greater stability in Gini purity than GMM.

In estimating the final clusters, Kd-means found 12, including two clusters with a cardinality of 1 and 4. Without taking into account these last two clusters, we could say that it produced 10 clusters.

To sum up, Kd-means produced a quality result globally better than GMM. Indeed, the values of vi of Kd-means and GMM are 1.29 and 1.63, respectively. This shows that Kd-means globally managed to capture more information from the field truth than GMM. Taking into account all the comparative results, Kd-means represents a good alternative to GMM.

III.3.9 Conclusion

In this part, the main objective is to estimate the actual number of clusters in a dataset and, at the same time, to build these clusters.

In the literature, several solutions have been proposed to meet this objective. The X-means and G-means methods are among the best known and most efficient. They are based on information theory and statistical tools. However, these methods deviate excessively in the estimation of k when the clusters are not strictly spherical or elliptical or when the clusters overlap. Consequently, the clustering quality is negatively impacted, i.e., the actual clusters have not been identified correctly. Moreover, X-means and G-means, iterative methods, use k-means on all points at each iteration.

This makes them expensive for large datasets.

In response to these limitations, we have developed Kd-means, a solution based on the Kd-tree binary hierarchical data structure. It identifies clusters with spherical, elliptical, and even more complex shapes in large datasets. And this, even if the clusters overlap.

Kd-means consists of four consecutive steps:

• structuring and organization of data in Kd-tree. Kd-tree allows to pre-cluster the data, i.e., to put in the same node similar points. In this structure, we have integrated the hyper-rectangle geometric tool (a rectangle generalized to multidimensional data spaces) to frame a group of points while allowing to approximate the group's spatial distribution. Moreover, it allows quick calculations between two groups of points because there is no more need to visit these groups' points.

This tool is used in the following steps;

• leaf initialization. once kd-tree is built, we find groups of points, called clusters in the leaves. So each leaf has its own clusters that are independent of those of the other leaves;

• Merging of clusters. Clusters in the leaves may not correspond to the real clusters, i.e., they correspond to the final clusters' subclusters and should be merged. For this reason, we have proposed a merge test process (MTP) to evaluate whether two clusters should be merged or not. Using this process, clusters are merged recursively in a hierarchical way from the leaves to the root; 90CHAPTER III. PARTITION-BASED CLUSTERING METHODS OPTIMIZATION

• Regularization. At the end of the previous step, small clusters (in number of points) can be isolated from larger clusters. This step makes it possible to assign small clusters to the larger ones, agglomerate small clusters to form a single one or consider them separate clusters.

Experimentally, Kd-means has been compared to X-means and G-means on various data sets (synthetic and real). It has been shown that Kd-means could be better in runtime up to more than 1500 times. Moreover, in the estimation of real 𝑘 and clustering quality Kd-means is much better than its competitors. It was also compared to GMM (Gaussian Mixture Models)5 on a hyper-spectral image where GMM was given the real number of clusters 𝑘 to identify, and Kd-means had to estimate this number automatically. Overall, in this application framework, the results were encouraging for Kd-means on the clustering quality and the estimation of 𝑘.

III.4 Conclusion

In this chapter, we have developed two solutions for different problems. The first, Sk-means, is a strategy that reduces the number of unnecessary calculations in kmeans and its associated versions based on geometric reasoning. So its goal is to reduce execution time in a large dataset environment. The second solution, kd-means, automatically estimates the number of clusters while forming them. Kd-means also addresses its competitors' limitations, such as the strong constraint on cluster shape, cluster overlapping, and long execution time in a large dataset environment.

So far, we have contributed to the paradigm of partition-based methods (El Malki et al., 2019b)(El Malki et al., 2019a)(El Malki et al., 2020b). The next chapter focuses on the density-based methods paradigm (adopting a different cluster definition than the previous paradigm)(El Malki et al., 2020a). In the following, we do not focus on the execution time but the clustering quality and the data's high dimensionality.

IV.1 Introduction

In this chapter, we focus on the density-based methods paradigm. It takes a different clustering approach from the paradigm based on partitioning methods, and more specifically, on the cluster's definition. As a result, the paradigms, in practice, may have different applications. In this paradigm, a cluster is a dense region of points separated from other clusters by less dense regions [START_REF] Kriegel | Density-based clustering[END_REF]. This definition has allowed these methods to detect arbitrary-shaped clusters. Nevertheless, density-based clustering has difficulties in detecting clusters having low densities regarding high-density clusters. Low-density clusters are either considered as outliers or included in another cluster. Moreover, near clusters of similar densities are often grouped in one cluster. Finally, density-based clustering does not manage well in high-dimensional data [START_REF] Kriegel | Clustering high-dimensional data: A survey on subspace clustering, pattern-based clustering, and correlation clustering[END_REF].

Our proposals consist of a new way to divide datasets into homogeneous groups in terms of density, a novel agglomerative method based on the Wasserstein metric, and a new clustering algorithm, called Decwa, based on spatial density and probabilistic approach.

First, we present the global approach of our solution (section IV.3), then we detail each of its steps. Finally, we experimentally evaluate the robustness of the solution on various data sets (section IV.9).

IV.2 Notations

In addition to table IV.1, we give more information about the cluster, sub-cluster, and distance probability density function.

Cluster. we consider a cluster as a contiguous region of points where density follows its own law of probability. Formally, we represent a cluster 𝐶 𝑖 by a set of pairwise distances between the points contained in the cluster 𝐶 𝑖 . This set is annotated 𝐷 𝑖 and follows any law of probability. 𝐷 𝑖 is computed via any distance defined as 𝑋 ×𝑋 → R + that has to be at least symmetric and reflexive.

Sub-cluster. It corresponds to a subset of a cluster. The latter can be made up of several sub-clusters. In the solution intermediate steps, the sub-clusters are produced and used so that in the last step, a cluster set is returned.

Distance probability density function (distance 𝑝.𝑑.𝑓 ). It characterizes the probability law of the distances between the points of a group (cluster or sub-cluster). In other words, it informs about the group spatial density as well as the source that generated the points.

Symbols

Meaning To generate the new distance space of 𝑋, we calculate distances between the points of the dataset. Our computation strategy of pairwise distances is based on the 𝑘nearest neighbor method [START_REF] Aggarwal | Data Clustering: Algorithms and Applications[END_REF] The interest of the MST in clustering is its capability to detect clusters of irregular boundaries [START_REF] Zahn | Graph-theoretical methods for detecting and describing gestalt clusters[END_REF]. As the MST, denoted 𝐺 𝑚𝑖𝑛 , is built thanks to the 𝑘𝑛𝑛𝑔, therefore, 𝑘 must be superior to a certain value so that the algorithm has enough edges to construct an optimal MST. Except for that matter, the value of 𝑘 has no further influence as the MST will model the dataset.

𝑋 𝑋 = {𝑥 1 , . . . , 𝑥 𝑛 }, 𝑛 = |𝑋| is a dataset 𝐶 𝐶 = {𝐶 1 , . . . , 𝐶 𝑐 }, 𝑐 = |𝐶| is a set of clusters, 𝐶 𝑖 , 𝐶 𝑗 𝐶 𝑖 ∈ 𝐶, 𝐶 𝑗 ∈ 𝐶 are clusters 𝐷 𝐷 = {𝐷 1 , . . . , 𝐷 |𝐷| } is a set of distance distributions 𝐷 𝑖 , 𝐷 𝑗 𝐷 𝑖 ∈ 𝐷, 𝐷 𝑗 ∈ 𝐷 are distance distributions 𝐷 ′ the set of distances 𝐺 𝐺 = (𝑉, 𝐸) is an undirected weighted graph 𝑉 𝑉 = {𝑣 1 , . . . , 𝑣 |𝑉 |} is a set of vertices 𝑣 𝑥 , 𝑣 𝑦 𝑣 𝑥 ∈ 𝑉 , 𝑣 𝑦 ∈ 𝑉 are vertices 𝐸 {𝑒 1 , . . . , 𝑒 |𝐸| } is a set of edges 𝑒 𝑞 𝑒 𝑞 ∈ 𝐸 is an edge (𝑣 𝑥 , 𝑣 𝑦 , 𝑤 𝑞 ) (𝑣 𝑥 , 𝑣 𝑦 , 𝑤 𝑞 ) = 𝑒 𝑞 is an edge, (𝑣 𝑥 , 𝑣 𝑦 ) ∈ 𝑉 2 , 𝑤 𝑞 ∈ N 𝑤 𝑞 𝑤 𝑞 is

IV.5 Probability density estimation

The overall objective of the 𝑝.𝑑.𝑓 estimation is to extract new information to delimit sub-clusters. {If there is an increase in the number of extremes and update authorization, the elbow value is modified} 5:

if 𝑒𝑥𝑡𝑟𝑒𝑚𝑎(ℎ) > 𝑒𝑥𝑡𝑟𝑒𝑚𝑎(ℎ -1) AND 𝑒𝑙𝑏𝑜𝑤 = 𝑟𝑒𝑓 𝑒𝑟𝑒𝑛𝑐𝑒 then 6:

𝑒𝑙𝑏𝑜𝑤 = ℎ 7: end if 8:
{If there is a decrease in the number of extremes, the update is authorized in line 5}

9:

if 𝑒𝑥𝑡𝑟𝑒𝑚𝑎(ℎ) < 𝑒𝑥𝑡𝑟𝑒𝑚𝑎(ℎ -1) then 10:

𝑟𝑒𝑓 𝑒𝑟𝑒𝑛𝑐𝑒 = 𝑒𝑙𝑏𝑜𝑤 11:

end if 12: end for areas from a 𝑝.𝑑.𝑓 𝑓 : 𝑋 → R + . They correspond in 𝑓 to the zones around the peaks (included) called level sets [START_REF] Hartigan | Clustering Algorithms[END_REF]. Let 𝑙 > 0 be a density threshold, a level set is a set of points defined as {𝑥 𝑖 |𝑓 (𝑥 𝑖 ) > 𝑙}. This threshold 𝑙 is on both sides of the bell (level set) centered around the peak. The sets of points {𝑥 𝑖 |𝑓 (𝑥) ≤ 𝑙} are either considered as outliers or assigned to denser clusters. This approach is not suitable for capturing clusters of different densities.

Another solution [START_REF] Hartigan | Clustering Algorithms[END_REF], based on the hierarchical approach, cuts 𝑓 at different levels 𝑙 to better capture clusters of different densities. In our case, 𝑓 is defined as 𝑓 : 𝐷 ′ → R + with 𝐷 ′ the set of distances. We consider in our case that a level set has two thresholds that are not necessarily equal. Areas of 𝑓 below these thresholds are not considered as outliers. They are the less frequent distances that correspond to phenomenons with fewer points such as overlapping areas or small clusters.

For estimating the 𝑝.𝑑.𝑓 , we use the Kernel Density Estimation (𝐾𝐷𝐸) [START_REF] Davis | Remarks on Some Nonparametric Estimates of a Density Function[END_REF]. Its interest lies in the fact that it makes no a priori hypothesis on the probability law of distances. The density function is defined as the sum of the kernel functions 𝐾 on every distance. The commonly used kernels are Gaussian, uniform, triangular, etc. The 𝐾𝐷𝐸 equation is below:

 𝑓 ℎ (𝑧 𝑡 ) = 1 (𝑛 -1)ℎ 𝑛-1 ∑ 𝑖=1 𝐾 ( 𝑧 𝑡 -𝑧 𝑖 ℎ ) (IV.1)
In our case, 𝑧 𝑡 and 𝑧 𝑖 correspond to the distances contained in 𝐺 𝑚𝑖𝑛 . We have [START_REF] Silverman | Density Estimation for Statistics and Data Analysis[END_REF]. Most existing algorithms estimating ℎ focus on having a bias-variance trade off and are not well suited for our algorithm. Intuitively, we want to have important phenomenons represented as peaks in the estimated 𝑝.𝑑.𝑓 and we want the best precision possible while avoiding noise to appear as peaks on the curve. Therefore, the solution we propose aims at finding when noise begins to generate peaks on the curve, it is based on the Elbow method [START_REF] Satopaa | Finding a "kneedle" in a haystack: Detecting knee points in system behavior[END_REF]. Indeed, the curve corresponding to the number of extrema associated with each value of ℎ tends to have an Elbow shape. The proposed method finds 𝑒𝑙𝑏𝑜𝑤, the first point of the last peak in this curve, 𝑒𝑥𝑡𝑟𝑒𝑚𝑎(ℎ), with ℎ ∈ 𝐻 and 𝐻 the set of possible bandwidths. It is detailed in algorithm 5.

℘ 𝑡 ← ℘ 𝑡+1 ∪ {(𝑉 𝑡+1 ∖ 𝑉 𝑡 , 𝐸 𝑡+1 ∖ 𝐸 𝑡 )} 8: end for 9: ℘ 1 ← ℘ 1 ∪ ℵ 1 is Silverman's rule of thumb

IV.6 Graph division

The purpose of the distance 𝑝.𝑑.𝑓 is to associate to each distance its density. The latter is a number that quantifies the intensity of the distance appearance frequency.

The current step's goal is to extract the different density groups from the distance 𝑝.𝑑.𝑓 and the minimum spanning tree 𝐺 𝑚 𝑖𝑛. Each group represents a finite list of sub-clusters. The difficulty lies in how to extract these groups.

To separate different densities, the distance 𝑝.𝑑.𝑓 the decomposed into several parts via cuts. The significantly different densities are detected with the peaks of the distance 𝑝.𝑑.𝑓 curve. To separate highly represented distances to less represented distances, we consider an extraction threshold as the mid-distance between each maximum and its consecutive minimum, and conversely between each minimum and its consecutive maximum. Mid-distances allow capturing regions that are difficult to detect (low-density regions, or dense regions containing few points). Another interesting consequence concerns overlapping regions that have the same densities. These regions are often very difficult to capture properly, whilst our mid-distance approach makes it possible to detect these cases because overlapping between regions induces a density curve, we apply a process (algorithm 6) to treat successively the list of mid-distances in descending order. We generate sub-clusters, from the nodes of 𝐺 𝑚𝑖𝑛 , and sets of distances of sub-clusters, from the edges of 𝐺 𝑚𝑖𝑛 .

From 𝐺 𝑚𝑖𝑛 , via the process, we extract connected sub-graphs ℘ 𝑡 where all the nodes that are exclusively linked by edges greater or equal than the current mid-distance 𝑙 𝑡 .

A node linked to an edge greater or equal to the 𝑙 𝑡 and another edge less than the 𝑙 𝑡 is not included. A sub-cluster 𝐶 𝑖 is composed of points that belong to one connected sub-graph. For each sub-cluster, we produce its associated set of distances 𝐷 𝑖 from edges between nodes of the sub-graph. A residual graph ℵ 𝑡 is made up of edges whose distances are less than 𝑙 𝑡 , and all the nodes linked by these edges. This residual graph is used in the successive iterations. The residual graph can consist of several unconnected sub-graphs. At the last iteration (i.e. at the level of 𝑙 1 ), the residual graph ℵ 1 is also used to generate sub-clusters and associated sets of distances. After this step, some sub-graphs are close to each other while having a similar 𝑝.𝑑.𝑓 . According to our cluster characteristics, they should be merged. Let us consider the list of mid-distances , and a connected sub-graph 𝑠𝑔 𝑖 with the weighted edges 𝐸 𝑖 . Suppose that is iterated consecutively in descending order as illustrated in algorithm 6. In a given iteration 𝑡, the current threshold is 𝑙 𝑡 . One 100CHAPTER IV. DECWA: DENSITY-BASED CLUSTERING USING WASSERSTEIN DISTANCE of the two following situations is performed: either ∀𝑒 𝑞 ∈ 𝐸 𝑖 , 𝑤 𝑞 < 𝑙 𝑡 , in which case no action is taken on 𝑠𝑔 𝑖 ; or else if ∃𝑒 𝑞 ∈ 𝐸 𝑖 , 𝑤 𝑞 ≥ 𝑙 𝑡 then from 𝑠𝑔 𝑖 is extracted a set of connected sub-graphs called ℵ 𝑡 with 𝑤 𝑞 < 𝑙 𝑡 and another set of connected subgraphs ℘ 𝑡 with 𝑤 𝑞 ≥ 𝑙 𝑡 . At this point, for all edges into ℵ 𝑡 , 0 < 𝑤 𝑞 < 𝑙 𝑡 . At the next iteration, ℵ 𝑡 undergoes the same processing for the threshold 𝑙 𝑡-1 . If ∃𝑤 𝑞 ≥ 𝑙 𝑡-1 , the set of sub-graphs ℘ 𝑡-1 is extracted from ℵ 𝑡 . In this case, for all edges into ℘ 𝑡-1 ,

𝑙 𝑡-1 ≤ 𝑤 𝑞 < 𝑙 𝑡 .
While homogeneous sub-clusters are constituted, some are close and have a similar density. They should be merged according to our definition of cluster. Therefore, the next step consists in identifying these sub-clusters to agglomerate them.

IV.7 Agglomeration of sub-clusters

This step aims at generating clusters from sub-cluster agglomeration. The main difficulty of this step is to determine which sub-clusters should be merged. When the distances between two sub-clusters are close, it is difficult to decide whether or not to merge them.

To arbitrate this decision, we use their density, represented as the distance 𝑝.𝑑.𝑓 .

Only sub-clusters that near spatially and have similar distance 𝑝.𝑑.𝑓 will be merged.

As To fulfill these objectives, we define the two following conditions. Given two subclusters 𝐶 𝑖 and 𝐶 𝑗 , the first condition is that these sub-clusters must be spatially close enough. To ensure this, ||𝐶 𝑖 -𝐶 𝑗 || ≤ 𝜆 must be respected, with 𝜆 ∈ R + . It is necessary to determine the distance between sub-clusters (||𝐶 𝑖 -𝐶 𝑗 ||) to verify this condition. However, calculating every pairwise distance between two sub-clusters is a time-consuming operation. Therefore, we propose another solution based on 𝐺 𝑚𝑖𝑛 .

We consider that the value of the edge linking sub-graphs corresponding to 𝐶 𝑖 and 𝐶 𝑗 as the distance between 𝐶 𝑖 and 𝐶 𝑗 . Because of the MST structure, we assume that this distance is nearly the minimum distance between the points of 𝐶 𝑖 and 𝐶 𝑗 .

The second condition relates to the similarity of the distance distributions 𝐷 𝑖 and 𝐷 𝑗 . The purpose of this condition is to ensure 𝑤𝑠(𝐷 𝑖 , 𝐷 𝑗 ) ≤ 𝜇, with 𝜇 ∈ R + , and 𝑤𝑠 the Wasserstein distance. We have opted for the Wasserstein distance as a measure of similarity between probability distributions. Two advantages of this distance led us to its choice [START_REF] Villani | Optimal transport : old and new[END_REF]):

• it seamlessly takes into account the geometric shape of the 𝑝.𝑑.𝑓. curves; • if the two distributions are very close, then the small difference will be captured by Wasserstein, allowing a fine precision.

We introduce now an iterative process (algorithm 7) for merging sub-clusters.

IV.8 Parameter estimation

In the merging phase, 𝜆 and 𝜇 are metric thresholds for 𝑑 and 𝑤𝑠. Therefore they are defined in ]0, +∞[. It is difficult for users to operate with this unbounded interval.

In this sub-section, the objective is to map this interval to a bounded interval defined between 0 and 1. We argue that a bounded interval is more meaningful for users.

We consider 𝑚 ∈ R + , 𝑀 ∈ R + respectively the lower bound and the upper bound of 𝐷 ′ the set of distances and 𝛾, 𝜏 ∈]0, 1] , so 𝜆, 𝜇 are simplified as follows:

𝜆 = 𝛾 * (𝑀 -𝑚) + 𝑚 (IV.2) 𝜇 = 𝜏 * (𝑀 -𝑚) + 𝑚 (IV.3)
So when merging sub-clusters, the spatial distance between sub-clusters can never be greater than 𝑀 and not smaller than 𝑚, hence the equation IV.2. The 𝛾 factor is a hyperparameter that indicates the level of severity on the merge. If it is equal to 1, the less strict value, it tends to allow all sub-clusters to be merged and inversely if it is near to 0. Similarly, the factor 𝜏 (equation IV.3) is also a hyperparameter and has the same effect on the probabilistic distance. Equation IV.3 is justified by the fact that the Wasserstein distance is bounded between 0 and (𝑀 -𝑚). The lower bound is 0 because Wasserstein is a metric. The following evidence proves that the upper bound is (𝑀 -𝑚).

Proof. Given 𝑈 : Ω → 𝐷 ′ and 𝑉 : Ω → 𝐷 ′ two random variables with 𝐷 ′ ⊂ R + and Ω the set of possible outcomes. 𝐷 ′ is the set of distances in our case, 𝑈 and 𝑉 represents two sub-clusters and their inner distances. According to [START_REF] Ramdas | On wasserstein two sample testing and related families of nonparametric tests[END_REF] the first Wasserstein distance between the distributions of 𝑈 and 𝑉 is:

𝑤𝑠(𝑢, 𝑣) = ∫ +∞ -∞ |𝐹 𝑈 (𝑢) -𝐹 𝑉 (𝑣)|𝑑𝑢𝑑𝑣 (IV.
𝐷 ← 𝐷 ∪ {𝐷 𝑖 ∪ 𝐷 𝑗 ∪ {𝑤 𝑞 }} 23: ℘ 1 ← (℘ 1 ∖ 𝑠𝑔 𝑖 ) ∖ 𝑠𝑔 𝑗 24: ℘ 1 ← ℘ 1 ∪ {𝑠𝑔 𝑖 ∪ 𝑠𝑔 𝑗 ∪ {𝑒 𝑞 }} 25: 𝜖 ← 𝜖 + 1 26: end if 27: end if 28:
end for 29: until 𝜖 = 0 During the merging process, DECWA runs through 𝐺 𝑚𝑖𝑛 and therefore evaluates edges in an order which has a small influence over the result. Multiple sorting methods were tested and DECWA is not very sensitive to the order (ARI difference on average is less than 4% in the worst case). We obtained the best results by sorting edges by weight in ascending order, therefore, we suggest this sorting method for DECWA.

To cut 𝑝.𝑑.𝑓 , different methods are tested and evaluated. Inspired by Hartigan's level set idea, the minima in the 𝑝.𝑑.𝑓 curve are tested to separate distance groups (44% ARI on average). The G-means algorithm, based on Gaussian Mixture Models, was tested to separate distance groups by considering them as sub-populations of a Gaussian mixture distribution (57% ARI on average). In the end, our mid-distance solution has better performances (67% ARI on average).

IV.9.2.3 Synthetic datasets

The two-dimensional, jain, compound, pathbased [START_REF] Fränti | K-means properties on six clustering benchmark datasets[END_REF], and cluto-t7.10k [START_REF] Karypis | Chameleon: hierarchical clustering using dynamic modeling[END_REF] For Oncology) [START_REF] Stiglic | Stability of ranked gene lists in large microarray analysis studies[END_REF]. It consists of 384 tumor samples to be classified into two classes (kidney or uterus). Each sample is the expression level of 10937 genes. Given that the attributes all correspond to the same nature (gene expression) then the Bray-Curtis distance was applied to it. New3 [START_REF] Han | Centroid-based document classification: Analysis and experimental results[END_REF], a very high-dimensional dataset, is a set of 1519 documents grouped into 6 classes. Each document is represented by the term-frequency (𝑇 𝐹 ) vector of size 26833. Each element of this vector is the frequency of the 𝑖 𝑡ℎ term in the document.

The cosine distance was used to measure the similarity between documents.

IV.9.3 Results and discussion

The results are reported in the We conducted a statistical study, as recommended in [START_REF] Demsar | Statistical comparisons of classifiers over multiple data sets[END_REF], to confirm the significant difference in performance between the algorithms and the robustness of DECWA comparing to the others. The overall concept of the study has two steps.

1) First, a statistical test (Iman-Davenport [START_REF] Sheskin | Handbook of Parametric and Nonparametric Statistical Procedures[END_REF]) is performed to determine if there is a significant difference between the algorithms at the ARI level. 2) If so, a pairwise comparison of algorithms is performed, via a post-hoc test (Shaffer [START_REF] Shaffer | Modified sequentially rejective multiple test procedures[END_REF])), to identify the gain of one method over the others. Both tests return a p-value (in the case of the second test, it is returned for each comparison). The p-value allows us to decide on the rejection of the hypothesis of equivalence between algorithms. To reject the hypothesis, the p-value must be lower than a significance threshold 𝛼 that we set at 0.01. The p-value by returned the first test is 5.38𝑒 -5 .

It is significantly small compared to 𝛼. This means that the algorithms are different in terms of ARI performance. Second, these differences are analyzed by the Shaffer Post-hoc test. It returns a 𝑝-value for each test on a pair of algorithms. Indeed, for the case of DECWA, the p-value is much lower than 𝛼 when comparing DECWA to others (7.5𝑒 -4 with DBCLASD, 4.6𝑒 -3 with DENCLUE and 3.0𝑒 -3 with HDBSCAN), which proves that DECWA is significantly different from the others. For the others, the p-value is equal to 1.0 in all the tests concerning them, which statistically shows that they are equivalent. The ranking of the algorithms according to the ARI was done by Friedman's aligned rank [START_REF] Garía | An extension on "statistical comparisons of classifiers over multiple data sets" for all pairwise comparisons[END_REF]. DECWA is ranked as the best. All in all, DECWA is significantly different from the others and is the best performing.

IV.9.4 h estimation

This experiment aims to find the best method to determine the value of ℎ using Elbow approach. For these tests, we use Yellowbrick's implementation [START_REF] Satopaa | Finding a "kneedle" in a haystack: Detecting knee points in system behavior[END_REF] of Elbow Method, Silverman's rule of thumb [START_REF] Silverman | Density Estimation for Statistics and Data Analysis[END_REF], and the proposed method. Yellowbrick is able to give one point or to detect several points in the elbow, therefore we test two other methods by selecting a point among them. The first method is to take the median point among the set of proposed points. The intuition behind this method is that doing so ℎ is less likely to induce noise than the last proposed point while being more precise than the first point. The second method is based on the observation that actual phenomenons, resulting in clusters, are likely to induce stable peaks on the 𝑝.𝑑.𝑓 curve. Therefore this method finds the point with the biggest plateau on the 𝑒𝑥𝑡𝑟𝑒𝑚𝑎(ℎ) curve. for jain, a synthetic dataset, and the points found by every solution. On this example, our method found ℎ = 0.17 which induce 3 extrema in the estimated 𝑝.𝑑.𝑓 . Table IV.4

shows the evaluation of each method on the presented datasets. This experiment is

IV.9.5 k estimation

As explained in this paper [START_REF] Gower | Minimum spanning trees and single linkage cluster analysis[END_REF], the MST can be used for agglomerative clustering, which is the case for DECWA. However, it is also pointed out that the exact distances may be lost during the process of creating the MST. A connected graph is recommended before applying an MST generation algorithm because it contains inter-sub-cluster relationships. These relations are useful to better ensure the DECWA merging part. The value of 𝑘 must be large enough for the graph to be connected. The authors of [START_REF] Brito | Connectivity of the mutual k-nearestneighbor graph in clustering and outlier detection[END_REF] stipulate that for 𝑘𝑛𝑛𝑔 to be connected 𝑘 is chosen to the order 𝑙𝑜𝑔(|𝑉 |).

In Table . IV.5, we compared the distances between sub-clusters retained by the for the number of connected subgraphs in case where 𝐺 is not connected. On average, the smaller the 𝑛𝑐𝑠𝑏, the larger the ARI. At the same time, 𝑛𝑐𝑠𝑏 decreases as 𝑘 grows.

In the context of DECWA, the connectivity of the graph brings a better precision

IV.10 Conclusion

Density-based methods can detect clusters with arbitrary shapes. However, they have difficulties operating in high-dimensional data and separating outliers from low-density clusters or close clusters of similar density.

To face these difficulties, we proposed Decwa, a solution based on a probabilistic approach and the spatial density concept. First of all, it structures the dataset in a minimum spanning tree (MST), where the nodes are the points and the edges are the distances between points, in order to obtain a unidimensional space of inter-112CHAPTER IV. DECWA: DENSITY-BASED CLUSTERING USING WASSERSTEIN DISTANCE point distances. A density probability function (𝑝.𝑑.𝑓 ) is applied to this new space to identify the level of representability of different distances. From this function and the MST, sub-clusters of points with different spatial densities are extracted. This is carried out by a strategy we have developed based on particular thresholds called mid-points to obtain the most homogeneous sub-clusters possible in density. Thus, in a high-dimensional data space, low-density clusters and outliers are separated as well as clusters that are densely and spatially close. Some sub-clusters are then merged (because belonging to the same real cluster) by a process based on the MST we have designed. This in order to bring the final result closer to the ground-truth. The intersub-cluster merging is carried out according to conditions based on the minimum spatial inter-cluster distance and the Wasserstein inter-cluster probabilistic distance.

Experimentally, DECWA (El Malki et al., 2020a) has been compared to densitybased methods among the best known and performing methods in the literature on various data sets and different distances. DECWA is significantly better than competitors with a margin of 23% in clustering quality. More precisely, on high dimensional datasets, it outperforms competitors by a wide margin of 29%. DECWA is better by 20% and 23%, respectively, on datasets with low-density clusters and datasets with densely and spatially close clusters.

Chapter V Conclusion & Perspectives

Clustering is a technique used to find automatically relationships in data that are either too slow or too difficult to analyze by humans [START_REF] Aggarwal | Data Clustering: Algorithms and Applications[END_REF]. It has the advantage of being able to find relationships in more than three dimensions, which is a limitation for humans in terms of analysis. The main particularity of clustering is that it works on unlabeled data, i.e., without knowing a priori their nature (e.g., if the data is vehicles, nature can be the car, bicycle, plane, etc.). Concretely, clustering aims to divide a dataset into several groups of points (clusters) so that a cluster's points are as similar as possible.

Despite being widely used in practice, clustering has to face different challenges:

• in addition to the difficulty of storing large datasets, there is a more important problem, which is the automatic analysis of this data to derive knowledge.

• the greater the number of dimensions, the more difficult it is for clustering methods to work correctly;

• due to its unsupervised aspect, knowledge of the actual number of clusters existing in a dataset is difficult to access;

• another challenge lies in the internal structure of the data. Indeed, datasets could correspond to data distributions that are difficult to exploit. Different clustering methods exist and are grouped into paradigms. In this manuscript, we are interested in two of them: partition-based methods and densitybased methods. In the first paradigm, we focus on k-means (Llyod's version (Lloyd, 1982a)) because it is algorithmically practical and is one of the most widely used algorithms in data analysis.

In this manuscript, we have presented three contributions to address the problems mentioned above. For each paradigm, different problems are solved. For k-means, we made two contributions Sk-means and Kd-means. In the paradigm of density-based methods, we developed the Decwa solution.

Sk-means

The k-means standard version (Lloyd's version (Lloyd, 1982a)) divides a data set of size n into k clusters while minimizing an objective function (the quadratic error). It improves data partitioning from one iteration to the next until convergence. However, this version becomes more and more expensive as 𝑘 and 𝑛 increase, which is impractical for large sets of points. Moreover, it does not include strategies to avoid unnecessary and repetitive calculations. So to reduce the latter, versions of k-means based on geometric reasoning [START_REF] Newling | Fast k-means with accurate bounds[END_REF] have been developed. They are based on a property of distance metrics, called triangular inequality, attempting to avoid calculating unnecessary point-centroid distances. Nevertheless, this strategy does not avoid all unnecessary and repetitive calculations through several iterations.

To address this problem, we proposed an optimization strategy, called Sk-means, to reduce more unnecessary calculations in Lloyd's version and in versions based on geometric reasoning. Its main objective is to detect the points where the calculations performed on them do not improve the data partitioning. These points correspond to points that no longer change cluster from a given iteration to the end of the process of a k-means version. First of all, we introduced, for each cluster, two types of subsets.

The first one is the kernel of the cluster. It contains only points called passive. They correspond to points considered as not improving clustering if they are subject to distance calculations. These calculations are then considered unnecessary. The second is the outer part containing points of the cluster that are likely to change cluster and thus contribute to clustering evolution. During iterations, the points move from the outer part to the kernel. We have designed an estimator 𝐸 to estimate at which iteration the point of the outer part must pass into the kernel. The advantage of this strategy occurs as soon as the points switch into the kernel. At that moment, the points are no longer involved in the calculations until the k-means process end. So at each iteration, 𝑘 distances are avoided for all points belonging to the kernel. In addition, in versions based on geometric reasoning, the variables associated with each point of the kernel are no longer updated and maintained. This is not the case for the points in versions not adopting Sk-means where the variables are treated at each iteration. So, the Sk-means advantages result in significant time-saving. This gain is all the more important as 𝑛, 𝑘 and the number of iterations is large.

Two types of experiments were conducted. The first allowed the model of the 𝐸 estimator to be inferred. 1750 synthetic data sets were generated, having different cardinalities, dimensions, number of clusters and data spatial distributions. A total of 3500 experiments were launched. The results were visually and statistically validated to infer 𝐸. In the second experiment, versions of k-means integrating Sk-means (Lloyd, Compare-means, Sort-means and Exponion) were compared against their original associated versions while using our 𝐸 estimator. The datasets are various (synthetic and real), including images. A total of 384 experiments have been launched wherein each one we compare a version with Sk-means with its associated original version (i.e., without Sk-means).

The comparison criteria were the execution time and the relative difference between the final values proposed by the objective functions (i.e., the minimum quadratic errors they found at the end of the k-means process). In execution time, versions with Skmeans are up to 191 times faster than Lloyd's version. They are up to more than five times faster than the non-Sk-means related versions. Apart from this time saving, the overall relative difference is negligible and does not exceed 1%. This shows that the data partitionings calculated by the versions with and without Sk-means are practically similar.

In terms of short-term perspectives, the passive nature of the points could be extended to clusters as well. Suppose the cluster has no output and input of points from a given iteration and during a certain number of consecutive iterations. In that case, it is considered as not contributing to the partitioning evolution. So this cluster is removed from calculations involving inter-center distances to save more execution time.

In the medium term, we could extend the previous perspective by considering that the cluster is passive if there are few entries and exits of points. These points are probably at the cluster boundary, and their influence on data partitioning is negligible. This new consideration increases the time saving because the cluster will be considered passive more quickly in a k-means version process compared to the previous definition of cluster passivity. Another improvement could be made on the 𝐸 estimator. Currently, the 𝐸 estimator produces a global estimate, i.e., it considers that all points stabilize at the same speed. The goal here is to individualize the stability estimate, i.e., to consider that each point has its own speed of stabilization. This could be done by integrating into the 𝐸 model the distance between the point and its centroid. If it is very close to the centroid, then it should stabilize faster than the one far away from it. Another perspective could be to study the behavior of Sk-means, at least its adaptation to Lloyd's version, in shared-memory and shared-nothing architectures.

Kd-means K-means requires from the user the number of 𝑘 clusters before forming the clusters.

If the user provides a wrong value of 𝑘, then the data partitioning may not make sense or be unusable. The estimation of 𝑘 has been studied in the literature. The Xmeans and G-means methods are among the best known and most efficient. They correspond to iterative methods based on information theory and, more generally, on the probabilistic approach.

These methods have limitations on different aspects. First, they require iteratively executing k-means on the entire data set. Thus they are more and more expensive as the number of points and the number of iterations increases. Second, they exaggerate on the 𝑘 real value estimate when the shapes of the clusters are not Gaussian (i.e., G-means and X-means expect the real clusters to be respectively Gaussian (spherical or elliptical) and isotropic Gaussian (strictly spherical)) or the clusters overlap.

We have designed Kd-means to automatically estimate 𝑘 while meeting the above limitations. It can detect clusters of more complex shapes (thus not necessarily Gaussian) even if they overlap. Kd-means is based on a hierarchical binary Kd-tree data structure and a hierarchical process. Kd-means consists of four consecutive steps.

Firstly, the data are organized hierarchically through Kd-tree. This organization can be seen as a binary and recursive subdivision of the data. We have formulated conditions on the construction of Kd-tree so that it is not very deep and does not contain leaves with few points, to be suitable for large data sets. The second step forms clusters in each of the Kd-tree sheets. These clusters are indeed sub-clusters of the final clusters returned to the user. So after this step, a hierarchical process is launched on Kd-tree to merge clusters. The merge is performed recursively from the leaves to the root. In the root are then the final clusters. To carry out this process and meet the limits of overlapping and shapes of clusters, we have developed four criteria for intercluster merging. As soon as one seeks to verify the mergeability of two clusters, the criteria must be validated to merge them. The fourth step is optional and consists in improving the final data partitioning. It either assigns small clusters to larger clusters or groups the small clusters together to form a single cluster, or considers the small clusters as separate clusters because they are quite far apart from each other.

We compared the robustness of Kd-means against G-means and X-means. The types of data experienced are varied. 135 large synthetic data sets were generated with different cardinalities, dimensions and number of real clusters. Similarly, 11 large and real data sets were used, including spectral images, black/white or grayscale images, sound and logs. The comparison was performed on three different metrics: 𝑘 estimation accuracy, partitioning quality and execution time. The experiments clearly showed that Kd-means is very competitive compared to G-means and X-means, even if the clusters overlap or have a complex shape. As a result, it is much better in quality and accuracy in estimating 𝑘. In addition, it was up to 1500 times faster than competitors.

In the short term, we could evaluate our solution to other tree data structures. For example, using Quadtree or Octree [START_REF] Samet | Foundations of Multidimensional and Metric Data Structures[END_REF] instead of Kd-tree allows having for each node up to four child nodes or eight. This assumes that the data space is recursively divided into four or eight instead of two. So by increasing the number of child nodes, we would expect a better separation of the data.

In the medium term, another close alternative to Kd-tree could be Ball-tree. In the latter, the subspaces of data resulting from partitioning correspond to hyperspheres.

So, if we use Ball tree in our solution, the calculations of fusion tests are performed on hyper-spheres instead of hyper-rectangles. The spatial distribution of the cluster points could be more accurate with hyper-spheres than hyper-rectangles although they are more expensive to compute. Another interesting binary tree data structure to implement is Vantage point trees (Vp-tree) [START_REF] Nielsen | Bregman vantage point trees for efficient nearest neighbor queries[END_REF]. The process of partitioning spaces does not depend on the dimension but the distance metric. For each node, its left child node is associated with a hyper-sphere. The other child is associated with everything external to this hyper-sphere. Another perspective consists in associating a weight vector to each data point where each ith weight corresponds to the degree of belonging of the point to cluster j. This weight is calculated according to its distance from each of the centroids or hyper-rectangles. This operation is performed only at the Kd-tree root.

Decwa

The third contribution deals with the density-based methods paradigm. It corresponds to a different clustering approach compared to partition-based methods, mainly on cluster definition. A cluster is a dense region of points separated from other clusters by less dense regions. This paradigm's methods can detect clusters of arbitrary shapes without having to inform the number of clusters a priori. Nevertheless, they present difficulties when dealing with complex spatial data distributions. Among these difficulties, they may consider low-density clusters considered as groups of outliers or have them absorbed by a cluster of greater density while these low-density clusters represent a phenomenon in their own right. Moreover, they can lead clusters of similar density and very close in space to form a single cluster when they should not be. The third difficulty is related to the phenomenon of the curse of dimensionality. Indeed, when the data are of very high dimensionality, the methods may not work properly as for low dimensionality data. Decwa is, on average, 29% better than the others. Moreover, Decwa has the best results on datasets with low-density clusters with a margin of 20%. For datasets with similar density and spatial clusters, it is better with a margin of 23%.

In the short term, other kernels of the kernel density estimation method could be tested. For example, apart from the Gaussian kernel used in Decwa, it is interesting to study the impact of cosine, triangular, triweight and uniform kernels during cluster extraction. Moreover, Decwa could be experimented on more complex data such as multidimensional time series.

In the long term, Decwa could belong to the multi-view clustering methods approach [START_REF] Fu | An overview of recent multi-view clustering[END_REF]. At this stage, it will be able to cluster data from heterogeneous data sources. Indeed, data could be represented under different views. A view corresponds to a data representation. In the presence of these different data sources, it is necessary to deploy strategies that extract the most useful knowledge from each source to produce a global clustering closer to the ground truth than using only one data source.

In this part, we complete the content of the related work chapter as well as the Kd-means experimental part.

.

Additional related work

We extend the the optimization strategies for k-means section II.4. Indeed in this section, we discussed the optimizations brought specifically to k-means. In the appendices, specifically in .1.1, we discuss optimization techniques for supervised and unsupervised classification methods. Then in .1.2, we complete the part on k-means versions based on geometric reasoning (II.4.1.5).

.

General strategies

This sub-section extends the optimization strategies for k-means section II.4. We discuss strategies that improve algorithms' execution time (supervised, unsupervised or semi-supervised). The first three strategies focus on distances, i.e., functions that measure similarity between points. Indeed, distance is an essential function in many algorithms performing classification. So accelerating the distance calculation accelerates the algorithms' execution time. The last strategy is devoted to dimension processing.

The distance functions and other tools necessary for classification are executed on data points and thus on their dimensions. In this sense, dimensions are also concerned with optimization strategies. These could lead to considerable execution time acceleration and improve classification quality if the reduced format data are more reliable for classification methods than the original data.

.

Distance reformulation

The distance, a function measuring the similarity between two points, can be broken down into several independent parts. Some parts can be calculated and stored in advance of the process of an algorithm and remain unchanged. Only the other parts could be calculated during the process. In this way, the calculation of distances is accelerated in time. As an example, the squared Euclidean distance can be expressed from the inner products (equation 1). So in this equation, if we consider that 𝑥 𝑖 is a point in the dataset known in advance and 𝑐 is another point that remains to be determined during the process, we could still calculate and store < 𝑥 𝑖 , 𝑥 𝑖 > in advance (Hamerly and Drake, 2015a).

||𝑥 𝑖 -𝑐|| 2 =< 𝑥 𝑖 , 𝑥 𝑖 > -2 < 𝑥 𝑖 , 𝑐 > + < 𝑐, 𝑐 >

(1)

.

Reduced distance

To speed up the process execution time, the clustering algorithms replace the distances they usually use with faster alternatives called reduced distances [START_REF] Hamerly | Making k -means even faster[END_REF]. A reduced distance is an amount of dissimilarity that is more efficient to compute than the actual distance, but which preserves relative rankings. It is suitable when one is not looking for the value of the actual distance itself but just the relative orders of the points in relation to a given point as generated by the actual distance. In this case, it is more convenient to use an alternative distance than the actual distance.

For example, in k-means, the used distance is the Euclidean distance. The alternative distance could be the squared Euclidean distance; this avoids calculating the square root.

.1.1.3 Partial distance search (PDS)

PDS [START_REF] Bei | An improvement of the minimum distortion encoding algorithm for vector quantization[END_REF] is a way to speed up the search for the nearest points.

It is used in algorithms where knowledge of exact distances is not necessary but only minimal distance. This is the case for k-means, when searching for the nearest centroid for a given point 𝑥. Suppose we already have 𝑚 the distance between 𝑥 𝑖 and 𝑐 1 and want to know if 𝑐 2 is closer to 𝑥 𝑖 than 𝑐 1 . The distance between 𝑥 and 𝑐 2 can be computed according to the equation 2. The value of 𝑝 is the dimension index such that 0 ≤ 𝑝 < 𝑑 with 𝑑 the number of dimensions. As 𝑝 is incremented, the sum in the equation 2 increases. If it exceeds 𝑚, for a value of 𝑝, the distance calculation is then stopped because it cannot be close to 𝑥 𝑖 more than 𝑐 1 even if the distance calculation process continues to the last dimension.

𝑑𝑖𝑠(𝑥

.

Dimensionality reduction

The calculation of distances between points involves taking into account the dimensions of these points. Indeed, the greater the number of dimensions, the more expensive the distance is. Another consequence of having a large number of dimensions is that the data space volume is very large. As a result, in this space, data points often constitute a small unrepresentative dataset, making the classification task challenging. This problem is known as the curse of dimensionality.

The dimensionality reduction [START_REF] Cunningham | Linear Dimensionality Reduction: Survey, Insights, and Generalizations[END_REF] is a solution to reduce the both problems. It is an operation transforming a dataset from a large dimensional space to a smaller dimensional space. Although it is used for 2D or 3D visualization, it used to keep only the important information in the data and to reduce the algorithms' execution time (Boutsidis et al., 2010) Different approaches to dimension reduction exist. Dimension selection (Chandrashekar and Sahin, 2014) consists in choosing as many as possible non-redundant and reliable dimensions according to pre-defined metrics. Another known approach, based on linear algebra (e.g., PCA, SVD) (Boutsidis et al., 2010, Tipping and[START_REF] Tipping | Probabilistic principal component analysis[END_REF], performs a projection from the high dimensional data space into a lower-dimensional space while trying to preserve essential properties of the original data. This projection leads to new dimensions. The reduction is also carried out by deep neural networks (autoencoders) [START_REF] Makhzani | Adversarial autoencoders[END_REF]. They consist in learning how to encode a dataset and then decode it to reproduce the original data. Indeed, the data in encoded format represents the dataset in lower dimensions that could be used by other algorithms.

We point out that the reduction of dimensionality could have a significant time cost.

If several executions of the classification method are performed and the reduction of dimensionality is called once. In that case, there could be a significant time-saving. Although it has some similarity with Kd-means because it performs clustering via a tree structure called CF-Tree, it is nevertheless not comparable to Kd-means because it has not been specifically developed to estimate the number of clusters 𝑘. Moreover, Birch should be followed by another clustering algorithm (e.g., k-means) to refine its clustering result. Consequently, the problem of estimating 𝑘 clusters reappears because 𝑘 is necessary to produce the final result of clusters. However, we experimented Birch to study the clustering results produced by its hierarchical process.

Birch (Balanced Iterative Reducing and Clustering Hierarchies) [START_REF] Zhang | BIRCH: An Efficient Data Clustering Method for Very Large Databases[END_REF] is a clustering method proposing a hierarchical data structure called CF-tree in which it integrates the points. In CF-tree, each node can have no more than 𝐵 subclusters whose radius 𝑅 does not exceed a threshold 𝑇 . The Birch process consists of sequentially integrating the points into CF-Tree. At each given point, the tree is traversed to the nearest leaf, and then the nearest subcluster is identified in the leaf. If the addition of this point in this subcluster involves 𝑅 > 𝑇 , then a new subcluster is added. If adding leads to the number of subclusters exceeding 𝐵, then the leaf is split in two, which are initialized with the furthest subclusters. Then the others are assigned to one of the two nearest leaves. This task of updating and adding nodes is repeated from child to father up to the root. If, during the process, the tree does not fit in memory, then the tree is rebuilt while aggregating the subclusters. One of its advantages is that it does not require the value of 𝑘. Nevertheless, it tends to produce a large number of clusters. A clustering algorithm is usually needed (k-means or hierarchical clustering algorithm) that clusters the final Birch results. This brings us back to the problem of how to estimate 𝑘. Moreover, the clusters it produces are spherical, so it has the same limitations as k-means in terms of the types of clusters to be found.

In this part we compare the Birch [START_REF] Zhang | BIRCH: An Efficient Data Clustering Method for Very Large Databases[END_REF] Birch overestimates with respect to X-means for 𝑘 = 10 and 𝑘 = 32. The sensitivity of Birch to the order of the point entries, the overlap and shape of the clusters (Birch tends to capture only spherical clusters), the maximum number of subclusters required for each node, and the dataset's size results in Birch results that are not very homogeneous.

For a given real 𝑘 and two datasets with the same data generation process (synthetic datasets), it could produce from the first dataset hundreds of subclusters and the other thousands. For example, for 𝑘 = 10 and 𝑑 = 8, Birch produces 12622 subclusters for 𝑛 = 1 × 10 6 and 170 subclusters for 𝑛 = 4 × 10 6 . In case of real datasets, Birch overestimates 𝑘 in a very exaggerated way compared to competitors and the real 𝑘.

Except for the dataset japeneseVowels when Birch is compared to G-means, both overestimate 𝑘.

Compared to quality measurement 𝑣𝑖, Kd-means is clearly better than Birch. It outperforms it on all datasets. Birch slightly outperforms X-means and/or G-means, e.g. for (𝑘 = 10, 𝑑 = 6, 𝑛 ∈ {2 × 10 6 , 4 × 10 6 }) and (𝑘 = 10, 𝑑 = 8, 𝑛 = 4 × 10 6 ) in synthetic datasets. In real datasets, Birch produces better quality in only three datasets compared to G-means but on average it has a 𝑣𝑖 of 11.9 compared to 9.7 for G-means. It exceeds X-means only on one dataset.

In terms of time execution, even though it is incremental, the construction of CFtree is slow. For 𝑘 = 10, the maximum time performed by the other three algorithms is 3061 seconds (X-means), while the minimum time for Birch is 5296 seconds on synthetic datasets. The same trend is observed for the other 𝑘 values. The average time executions (in seconds) of the four algorithms on the actual data are respectively for Birch, G-means, 731,25,770 ,4,938 and 136. Birch is more than twice as slow as G-means and 402 times slower than Kd-means. Several factors explain the slowness of Birch. They include 1) Calculating the distance between the point that is about to be added and several nodes and subclusters at each depth of CF-tree. 2) Calculating the distance between several subclusters in order to merge or fragment the node. 3) Constantly update and eventually split parent nodes recursively when adding a point. 4) Reconstruction of the CF-tree when it no longer fits in memory. 5) Medium and large dimensional datasets are difficult to support. 6) sensitivity to the order of points.

In summary, according to the analyses made on the quality measure 𝑣𝑖 and the estimate of 𝑘, Birch should be coupled with another algorithm to refine and aggregate the clusters it has produced. Depending on the execution time, it is slow compared to competitors. Coupling it to another algorithm (e.g., k-means) takes even more time, and the user has to provide as an input to the added algorithm a value of 𝑘.

III. 1

 1 Type of cluster forms: a) spherical clusters b) clusters of different ellipticity and orientation, c) clusters more complex than elliptical clusters. III.2 K-means process of three clusters. Illustration of the clusters and their kernels evolving according to the point movements. . . . . . . . . . . . III.3 The description of the point state during a k-means process integrating Sk-means. Circles refer to the point state. once the passive point, it is no longer involved in the calculations in the following iterations. . . . . III.4 On the left, the optimized versions (Sk-means) and the original associated versions are compared in execution time. On the right, these versions are compared in the number of distance calculations performed. III.5 Clustering results proposed by the different versions of k-means. Each color represents a cluster. Names beginning with O correspond to the names of the optimized versions. The optimized versions produce the same clustering result. . . . . . . . . . . . . . . . . . . . . . . . . . . . III.6 a cube of eight well-separated clusters (inter-cube distance = 0.2). . . . III.7 A cube of eight overlapping clusters (inter-cube distance = -0.2). . . . III.8 Different scatterplots each involving the total number of iterations, which k-means took to converge, depending on another parameter (𝑛, 𝑑, 𝑘, 𝑠𝑝, 𝑟). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . LIST OF FIGURES III.9 Gain in execution time of the optimized version compared to the original version as a function of 𝑘. . . . . . . . . . . . . . . . . . . . . . . . . . III.10Overall solution for estimating the value of 𝑘 and clustering. . . . . . . . . III.11A 2-dimensional hyper-rectangle 𝐻 and the associated bounds 𝑚𝑎𝑥𝑒𝑠 and 𝑚𝑖𝑛𝑠 located on the corners (upper right and lower left). The dataset has two dimensions (𝑑0

  . . . . . . . . . . . III.14Merger test process (MTP) is nested in the local merger algorithm, which in turn is nested in the global merger algorithm. MTP could be called multiple times during local merger execution in a node. . . . . . . . . . . . . . . . . III.15criteria-based merging process between two hyper-rectangles 𝑥 and 𝑦. This process is called merger test. . . . . . . . . . . . . . . . . . . . . . . . . . III.16Example of the situation that validates the criterion 2. Blue circles are data points. The orange and black lines represent respectively, the distance between centroids and the distance between centers of the hyperrectangles 𝑥 and 𝑦. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III.17Real datasets characterized by overlap and eccentricity measurements. . . . III.18a) Original RGB color image, b) Ground truth classes, c) Projection of the Pavia hyperspectral image on two of the most informative axes generated by PCA d) result produced by Kd-means, e) result produced by GMM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III.19Gini impurity index for each class. The index is framed between 0 and 1; the more it tends towards 0, the purer the class is. . . . . . . . . . . III.20On the right, the comparison of GMM and Kdmeans by boxplots. Solid circles are the Gini results. On the left, the boxplot legend. . . . . . . . IV.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IV.2 Density detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IV.3 Comparison of the division result (on the left of the figure) with actual clusters for jain dataset (right) . . . . . . . . . . . . . . . . . . . . . . . IV.4 In the top sub-figure, two clusters 𝐶 𝑖 and 𝐶 𝑗 are shown. In the lower sub-figure, on the left the distance 𝑝.𝑑.𝑓 of 𝐶 𝑖 and on the right the distance 𝑝.𝑑.𝑓 of 𝐶 𝑗 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IV.5 Maximum possible area between two CDF . . . . . . . . . . . . . . . . IV.6 Elbow shaped curve of extrema in function of ℎ for jain dataset . . . . List of Tables II.1 Advantages and drawbacks of k-means optimization strategies . . . . . III.1 Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III.2 Parameter value range . . . . . . . . . . . . . . . . . . . . . . . . . . . . III.3 Spearman's test results on the correlations between 𝑘,𝑑,𝑛, 𝑠𝑝 and 𝑟, and the total number of iterations that k-means took to converge. . . . . . . . . . III.4 Description of the datasets used to evaluate Sk-means . . . . . . . . . . III.5 Number of times the algorithms are accelerated compared to Lloyd's version. Algorithms beginning with the letter o refer to algorithms that have benefited from the Sk-means strategy. The numbers in bold correspond to the best acceleration for a given dataset and 𝑘. . . . . . . III.6 Relative difference in SSE between each optimized algorithm and the LLoyd version. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III.7 Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III.8 Real data sets characteristics. . . . . . . . . . . . . . . . . . . . . . . . . III.9 Comparison of the three algorithms executed on synthetic data. Note that Δ𝑡 is expressed in seconds. In the Δ𝑡 sub-column of the G-means and X-means columns, the number in brackets represents how many times our algorithm is faster than the compared algorithm. . . . . . . . . . . . . . . . . . . . . III.10Comparison of the three algorithms, on real data, with respect to execution time(Δ𝑡). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III.11Comparison of the three algorithms, executed on synthetic data, with respect to the quality of clustering(vi) and the k estimation. . . . . . . . . . . . . III.12Comparison of the three algorithms, on real data, with respect to the quality of clustering(vi) and the k estimation. . . . . . . . . . . . . . . . . . . . . III.13Performance of our algorithm as a function of the value of 𝑡ℎ_𝑒𝑣𝑜 . . . . . III.14Performance of our algorithm as a function of the value of ψ . . . . . . . . III.15Overlapping rate of each of the nine classes of Pavia. The rate is calculated as detailed in subsection III.3.8.5 but adapted to the class level instead of the entire dataset. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IV.1 Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IV.2 Characteristics of data sets. . . . . . . . . . . . . . . . . . . . . . . . . . context . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.1.1 Classification . . . . . . . . . . . . . . . . . . . . . . . . . I.1.2 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . I.2 Research problems . . . . . . . . . . . . . . . . . . . . . . . . . . . I.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure I. 1 :

 1 Figure I.1: An example of three clusters, each containing data points

  three factors can lead to good or reasonable clustering or clustering making no sense in practice. In figure II.1, three different data sets highlight the limitations of k-means in the face of different data distributions. In figure II.1(a), k-means could not identify the two elliptical clusters. Indeed, k-means only identifies spherical clusters or tries to form spherical clusters even if they do not exist in the ground truth. In figure II.1(b), three clusters which do not have the same cardinality in points but which are separated. In this case, k-means failed to detect the clusters correctly. Indeed, anarea with a high density of points leads to points around or a little far away being in the same cluster even if they are not in the ground truth. Moreover, isolated points also strongly influence the location of the centroids. As a result, very distant points can be found in the same cluster. In II.1(c), k-means unrolled on two clusters that do not have the same variance; i.e., they do not have the same diameter, resulted in one cluster absorbing another. K-means has difficulties when the clusters do not have the same variance or with very different relative variances.

  be made on k-means (figure II.2). The first one is external. It consists in proposing the most optimal possible inputs for k-means to lead it to converge more quickly and to better optimize the objective function as opposed to providing random inputs, which often produces a poor final result. Possible improvements include determining a locally optimal initial set of centroids for k-means or identifying the actual number of clusters in the dataset. The second one is internal, it consists in deploying strategies 1) to improve the clustering quality in the sense of having a good correspondence between the result and the ground-truth and 2) to speed up the k-means execution time. Obtaining good clustering could imply an optimized objective function but not necessarily. The same logic applies in the sense optimized objective function to good clustering.

Figure

  Figure II.1: To the left of each figure, the ground truth (one color for a cluster). On the right, an example of clustering by k-means. Crosses represent centroids.

Figure

  Figure II.2: K-means versality

Figure II. 3 :

 3 Figure II.3: Estimation of 𝑘 by each of the both algorithms when clusters overlap. The dataset contains 5 true Gaussian clusters. The respective estimates of X-means and G-means are 67 and 26. The centroids are represented by black crosses. The horizontal and vertical axes refer to both dimensions of the used dataset.

Figure II. 4 :

 4 Figure II.4: Triangle inequality

  are time-consuming but deterministic, and others are less costly but not deterministic and the objective function of k-means is less optimized. K-means++ stands out from the crowd by providing a good compromise between optimizing the objective function and the cost in time. It is de facto a standard in many automatic classification libraries. We also discussed the k-means parallelization. There are different parallelization paradigms, one of which is MapReduce, for distributing data and parallelizing computations. However, they have to deal with the network communication management of intermediate computation results, which can be costly when 𝑘 et the number of points are large. We then focused only on accelerating the execution time of k-means (more precisely the Lloyd version) while maintaining the same clustering result. Among these accelerations, the tree-based versions avoid a certain amount of point-centroid distance computation in the first phase of k-means. In practice, when there are more than eight dimensions, they are less performant than the k-means versions based on geometric reasoning. We have studied their geometric tools for reducing the rate of calculation of unnecessary distances and their various methods among the most well known. Nevertheless, these versions do not avoid all unnecessary distances.

  is an algorithm based on a probabilistic approach. It consists in modeling the probabilistic density function 𝑓 of 𝑋 from the aggregation of influence functions. Then use 𝑓 directly to get the final clusters. Each point is associated with an influence function. This one characterizes the influence of the point on its neighborhood. Indeed, the probability density function at a given point 𝑝 ∈ 𝑋 is the sum of the influence functions of all the points at 𝑝, more formally 𝑓 (𝑝) = ∑ |𝑋| 𝑖=1 𝑦 𝑖 (𝑝) with 𝑦 𝑖 the influence function of the point 𝑥 𝑖 . The type of influence function is defined and parameterized by the user before the clustering process. It can be, e.g., Gaussian or square wave.

  hierarchical cluster structuring. Compared to Optics, it facilitates better automation of cluster extraction. Instead of a reachability-plot, it produces a condensed cluster tree, in which clusters have a hierarchical relationship (father-son clusters). It induces a new mutual reachability distance quite close to the reachability-distance of Optics.

  three different contributions, one chapter with two contributions responding to the limitations of k-means. The other chapter responds to the limitations of density-based methods. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III.2 SK-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . III.2.2 Optimization strategy . . . . . . . . . . . . . . . . . . . . III.2.3 Intact convergence . . . . . . . . . . . . . . . . . . . . . . III.2.4 Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . III.2.5 Experimental assessments . . . . . . . . . . . . . . . . . . III.2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . III.3 KD-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . III.3.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . III.3.3 Data structure elements . . . . . . . . . . . . . . . . . . . III.3.4 Data structure construction . . . . . . . . . . . . . . . . . III.3.5 Leaf initialization . . . . . . . . . . . . . . . . . . . . . . . III.3.6 Node merging . . . . . . . . . . . . . . . . . . . . . . . . . III.3.7 Cluster regularization . . . . . . . . . . . . . . . . . . . . . III.3.8 Experimental assessments . . . . . . . . . . . . . . . . . . III.3.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . III.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure

  Figure III.1: Type of cluster forms: a) spherical clusters b) clusters of different ellipticity and orientation, c) clusters more complex than elliptical clusters.

Figure

  Figure III.2: K-means process of three clusters. Illustration of the clusters and their kernels evolving according to the point movements.

Figure

  Figure III.3: The description of the point state during a k-means process integrating Sk-means. Circles refer to the point state. once the passive point, it is no longer involved in the calculations in the following iterations.

  this part, we show how Sk-means fits into the different versions of k-means. First of all, we recall that Lloyd's version and the versions based on geometric reasoning are made of two main steps repeated in an iterative process. The first step consists in assigning each point to the cluster whose centroid is closest. The second step recalculates the centroids of the clusters. At a given iteration and at a visit of a given point iteration in the first phase, we differentiate two other steps named outer test and inner test. The outer test step allows deciding whether to iterate to the next point because the current point does not change cluster at the current iteration. Before the decision, in the outer test, some tests are run via variables called bounds framing the point-centroid distances. If the tests pass, then calculating the distances between the point and the k centroids is avoided.

  {updates of variables specific to a given version of k-means} 25: end while and Exponion). The 𝑟 stability value was estimated by our 𝐸 estimator.To see Sk-means' benefits, we used three results produced by each of the eight versions: data partitioning, execution time, and the number of centroid-point calculations performed. In figure III.4, we compare each version of k-means to its optimized version (i.e., integrating Sk-means) in terms of execution time and the number of performed calculations. In terms of the number of performed calculations, the optimized versions avoid on average 66% calculations than the original versions. This results into the fact that Optimized versions are significantly faster by two to more than three times than their original associated versions. As an example, the optimized version of Lloyd's avoided 71% of calculations compared to the original, which resulted in the optimized version being 3.4 times faster. Even if the optimized versions are faster, the clustering results proposed by the optimized and non-optimized versions are similar (figure III.5). This shows that removing the points from the distance calculation operations, considered passive by Sk-means, does not really influence the data partitioning.

Figure

  Figure III.4: On the left, the optimized versions (Sk-means) and the original associated versions are compared in execution time. On the right, these versions are compared in the number of distance calculations performed.

Figure

  Figure III.5: Clustering results proposed by the different versions of k-means. Each color represents a cluster. Names beginning with O correspond to the names of the optimized versions. The optimized versions produce the same clustering result.

Figure

  Figure III.6: a cube of eight well-separated clusters (inter-cube distance = 0.2).

Figure

  Figure III.7: A cube of eight overlapping clusters (inter-cube distance = -0.2).

  , 𝑑, 𝑛, 𝑠𝑝) = 𝑓 4 * 𝑇 (𝑘, 𝑑, 𝑛) * (1 -𝑠𝑝) (III.8)From 𝑇 , 𝐸(𝑘, 𝑑, 𝑛, 𝑠𝑝) is inferred. The spatial distribution of the initial centroids has a non-negligible influence on the total number of iterations, hence its inclusion in 𝐸. The factor (1 -𝑠𝑝) corresponds to an increasing version of the scatterplot III.8(d) to mean that the closer the centroids are to each other (i.e., the larger (1 -𝑠𝑝) is), the greater 𝑟 = 𝐸(𝑘, 𝑑, 𝑛, 𝑠𝑝).

Figure

  FigureIII.8(e) shows the relationship between 𝑟 (by extension 𝐸) and the number of iterations. The factor 𝑓 4 is set to 2 and 𝑓 1 ,𝑓 2 and 𝑓 3 to 1. The monotony is much stronger compared to those of the other parameters. The scatterplot is more concentrated and less noisy. The monotony is increasing, which shows that the total number of iterations and 𝐸 evolve in the same direction.

AFigure

  Figure III.8: Different scatterplots each involving the total number of iterations, which k-means took to converge, depending on another parameter (𝑛, 𝑑, 𝑘, 𝑠𝑝, 𝑟).

Figure III. 9 :

 9 Figure III.9: Gain in execution time of the optimized version compared to the original version as a function of 𝑘.

Figure III. 10 :

 10 Figure III.10: Overall solution for estimating the value of 𝑘 and clustering.

Figure

  Figure III.11: A 2-dimensional hyper-rectangle 𝐻 and the associated bounds 𝑚𝑎𝑥𝑒𝑠 and 𝑚𝑖𝑛𝑠 located on the corners (upper right and lower left). The dataset has two dimensions (𝑑0and 𝑑1). The circles represent the points of the dataset. The 𝑚𝑎𝑥 (resp. 𝑚𝑖𝑛) function returns the maximum (resp. minimum) of the values in each dimension. Although the example deals with a two-dimensional space, the hyper-rectangle can also be defined in a space of more than two dimensions.

64CHAPTER

  Figure III.12: Example of the Kd-tree instantiation method on a two-dimensional space.

Figure

  Figure III.13: Process of hierarchical bottom-up merging of clusters. Square shapes are leaves, while circle shapes are internal nodes. The merging process starts with the leaves and gradually and hierarchically reaches the root. The leaves only play the role of children while the internal nodes are first parents and then children. Each color, involving three nodes, represents a fusion operation. The child nodes are processed if they are not already, then the father node is processed in turn using the results of its child nodes.

68CHAPTER

  Figure III.14: Merger test process (MTP) is nested in the local merger algorithm, which in turn is nested in the global merger algorithm. MTP could be called multiple times during local merger execution in a node.

Figure

  Figure III.15: criteria-based merging process between two hyper-rectangles 𝑥 and 𝑦. This process is called merger test.

(

  of the point values) of the hyper-rectangles; concatenating the sets of indices; calculating the 𝑠𝑠𝑒 according to the equation III.15; and calculating the 𝑚𝑖𝑛𝑠 and 𝑚𝑎𝑥𝑒𝑠 vectors according to the equation III.12. Criterion 1. Let 𝑚𝑖𝑛𝑠 and 𝑚𝑎𝑥𝑒𝑠 the limits of a defined data space ∈ R 𝑑 and 𝜁 the hyper-rectangles set belonging to this space then two clusters represented by the hyper-rectangles ℎ 𝑢 ∈ 𝜁 and ℎ 𝑣 ∈ 𝜁 are possibly mergeable if: Δ𝐺 < τ 𝜖 (III.17) where τ = 𝑎𝑝𝑑(𝜁), Δ𝐺 = ||𝑥 𝐺 -𝑦 𝐺 || and 𝜖 ∈ N * . Criterion 1 is based on the proximity measure. It checks whether two hyperrectangles are close enough to be possibly considered mergeable. It is based on the average of the pairwise distances between centroids (𝑎𝑝𝑑) to approximate the average distance between clusters of a node without calculating the distances between all point

Figure III. 16 :

 16 Figure III.16: Example of the situation that validates the criterion 2. Blue circles are data points. The orange and black lines represent respectively, the distance between centroids and the distance between centers of the hyper-rectangles 𝑥 and 𝑦.

  times faster than G-means and 15.4 to 75.2 times faster than X-means in synthetic data, respectively. The same trend occurs in real data, but from 16.3 to 1566.6 times compared to G-means and from 6.4 to 108.6 times compared to X-means. Maximum execution times were reached for all three algorithms at 𝑑 = 8, 𝑛 = and 𝑘 = 80 in the synthetic data. In this combination, the elapsed execution times are 10.43 minutes for Kd-means, 59.41 minutes for G-means, and 13h05 for X-means. In the real data, the maximums are reached in the configuration 𝑑 = 784, 𝑛 = 697932 and 𝑘 = 62

  [4.8] and 𝑡ℎ_𝑒𝑣𝑜 ∈ [0.20, 0.25, 0.30]. 86CHAPTER III. PARTITION-BASED CLUSTERING METHODS OPTIMIZATION III.3.8.7 Hyperspectral image use case To see more concretely the Kd-means use, we propose to study a use case consisting in segmentation of a hyperspectral image named Pavia (figure III.18.a)

Figure

  Figure III.18: a) Original RGB color image, b) Ground truth classes, c) Projection of the Pavia hyperspectral image on two of the most informative axes generated by PCA d) result produced by Kd-means, e) result produced by GMM.

  Figure III.19: Gini impurity index for each class. The index is framed between 0 and 1; the more it tends towards 0, the purer the class is.

Figure III. 20 :

 20 Figure III.20: On the right, the comparison of GMM and Kdmeans by boxplots. Solid circles are the Gini results. On the left, the boxplot legend.

  Figure IV.1: Overview

Figure

  Figure IV.3: Comparison of the division result (on the left of the figure) with actual clusters for jain dataset (right)

  Figure IV.3 shows a comparison of the division result and the actual clusters for jain dataset.

  Figure IV.3 (a) is the result of the division. However, clusters are homogeneous it appears that many can be merged and still respect our cluster characteristics. FigureIV.3 (b) is the ground truth.The connected sub-graphs of 𝐺 𝑚𝑖𝑛 have edge weights that are homogeneous overall. Indeed, the weight values of a connected sub-graph, annotated 𝑠𝑔 𝑖 are framed between consecutive thresholds 𝑙 𝑡 ∈ , 𝑙 𝑡+1 ∈ , which guarantees its homogeneity in terms of spatial density.

  an example, at the top of the figure IV.4, two clusters 𝐶𝑖 and 𝐶𝑗 are indeed subclusters of the same cluster. Spatially, they are contiguous. In terms of probability law, at the bottom of the same figure, they are also close because their 𝑝.𝑑.𝑓 are similar, which in practice translates into similarity in spatial density.

Figure IV. 4 :

 4 Figure IV.4: In the top sub-figure, two clusters 𝐶 𝑖 and 𝐶 𝑗 are shown. In the lower sub-figure, on the left the distance 𝑝.𝑑.𝑓 of 𝐶 𝑖 and on the right the distance 𝑝.𝑑.𝑓 of 𝐶 𝑗

  Figure IV.5 illustrates this proposition with an example. The two curves are 𝐹 𝑈 and 𝐹 𝑉 . Grey area between them corresponds to the area actually measured by Wasserstein and the rectangle area is the upper bound for 𝑤𝑠(𝑢, 𝑣).

  Fig. IV.6 shows the Elbow shaped curve obtained

  MST and the distance between the two closest points each belonging to a different sub-cluster. On previously used datasets, for 𝑘 = 3 a notable percentage of edges are different (2.3%), however it decreases as 𝑘 gets bigger : 0.2% for 𝑘 = 𝑙𝑜𝑔(|𝑉 |) and 0% for 𝑘 = √ |𝑉 |. This results are shown in 𝑑𝑖𝑓 𝑓 𝑒𝑑𝑔𝑒𝑠 column. Another experiment was carried out to study the influence of 𝑘 on the DECWA final result and see if it is efficient in the case where 𝑘 is of the order of 𝑙𝑜𝑔(|𝑉 |). For each dataset, DECWA is called with 𝑘 = 3, 𝑘 = 𝑙𝑜𝑔(|𝑉 |) and 𝑘 = √ (|𝑉 |). The value of ℎ is estimated by our proposed Elbow method. The values of 𝛾 and 𝜏 are set by using the random-search strategy. We have found (table IV.5) that the greater the 𝑘, the better the ARI. But between 𝑘 = 𝑙𝑜𝑔(|𝑉 |) and 𝑘 = √ (|𝑉 |) the difference is only of 0.02. Regarding the outlier ratio, the difference between 𝑘 = 𝑙𝑜𝑔(|𝑉 |) and others is negligible. 𝑛𝑐𝑠𝑏 stands

Figure

  Figure IV.6: Elbow shaped curve of extrema in function of ℎ for jain dataset

  We have designed, Decwa, a density-based clustering algorithm based on a probabilistic approach. Decwa proposes a new way of dividing into homogeneous clusters and a new way of aggregating clusters. In an environment of high dimensional data spaces, these two methods lead to the separation, on the one hand, between low-density clusters and outliers and, on the other hand, between clusters that are close in density and spatially. Decwa consists of four consecutive steps. First, the dataset is projected on a one-dimensional space via the minimum spanning tree (MST) where nodes are points and edges are inter-point distances. So the new space consists only of spatial inter-point distances. Then, from this space, a probability density function (𝑝.𝑑.𝑓 ) is computed to obtain different distances' representation level. Then the process of dividing the set of points into clusters begins. In this process, we have proposed a new way of extracting clusters via the 𝑝.𝑑.𝑓 jointly exploited with the MST. It results on homogeneous clusters on the aspect of spatial density, i.e., each cluster follows its own probability law. These clusters are only intermediate and may need to be merged to produce final clusters. For this, we have proposed an agglomeration method. Two clusters are merged if only they are relatively close spatially and in probability laws. The spatial proximity is based on the distance proposed by the user, while the probabilistic proximity is calculated by Wasserstein distance. Agglomeration is performed using the MST to avoid having to recalculate the inter-point distances. Experimentally, we compared the robustness of Decwa against Hdbscan, Denclue and Dbclasd, the most well-known and efficient methods among density-based methods. The datasets used are quite varied in type, cardinalities and dimensions. The actual data include biological, medical, botanical and textual data. Different distances have been used, including Cosine, Manhattan, Braycurits and Euclidean distances. In terms of clustering quality, Decwa outperformed its competitors by a wide margin of 23%. Especially on very high dimensional data (containing up to 26833 dimensions),

  𝑖 , 𝑐 2 ) = 𝑑-1 ∑ 𝑝=0 𝑑𝑖𝑠(𝑥 𝑖,𝑝 , 𝑐 2,𝑝 )

  The first three above-mentioned strategies (table 1) are dedicated to accelerating the distance calculation. The distance reformulation decomposes the distance function into sub-functions, among which the results are obtained and stored in advance of the classification process. It requires nevertheless to store for each point a list of pre-calculated results. The reduced distance strategy associates to a distance another equivalent one less costly in time. During the process, the alternative is used instead of the actual distance. Even if both distances do not produce the same similarity values, they propose the same ordered list of points (e.g., in case of sorting task). The partial .2 Kd-means .2.1 BIRCH

  clustering algorithm with the three others presented in the section III.3.8 . Note that we consider the same three metrics used to compare the three algorithms. In the experiments we focus only on subclusters of the CF-tree leaves. The value of threshold 𝑇 has been initialized as follows: 𝑇 = 𝑅 𝑟𝑜𝑜𝑡 * 𝑞 where 𝑅 𝑟𝑜𝑜𝑡 the average distance between the points and the centroid of 𝑋 and 𝑞 ∈]0, 1]. 𝑇 is then updated during Birch execution when the CF-Tree is reconstructed as recommended by the Birch authors. Similarly, the number of subclusters per node 𝐵 was also tuned. So, 𝐵 = √ 𝑐𝑎𝑟𝑑(𝑋) * 𝑏 with 𝑋 the dataset and 𝑏 ∈]0.1]. The results in the table correspond to the mean of the results.

  .2.1.1 Analysis of Birch's resultsOverall, in synthetic datasets, Birch overestimates the number of clusters compared to the actual 𝑘 and even to the number of clusters produced byKd-means and G-means.

  𝑥 𝑖 , 𝐺 𝑎 , 𝐺 𝑏 ∈ 𝑅 𝑑 , 𝑥 𝑖 a point, 𝐺 𝑏 the actual centroid of 𝑥 𝑖 and 𝐺 𝑎 another centroid, compare-means asserts that if the distance between 𝐺 𝑎 and 𝐺 𝑏 is strictly greater than twice the distance between the point 𝑥 𝑖 and its centroid 𝐺 𝑏 then the distance between 𝑥 𝑖 and 𝐺 𝑎 should not be calculated because 𝐺 𝑎 is indeed far enough from 𝑥 𝑖 in relation to 𝐺 𝑏 . This assertion is summarized in the inequation II.6 and

	proved via the triangular inequality in the appendices (section .1.2).
	2 × 𝑑𝑖𝑠(𝑥 𝑖 , 𝐺 𝑏 ) < 𝑑𝑖𝑠(𝐺 𝑏 , 𝐺 𝑎 )	(II.6)

it checks if 𝑢 𝑖 ≤ 𝑠 𝑣 𝑖 is true (𝑠 𝑣 𝑖 is half the distance between 𝐺 𝑣𝑖 and its nearest centroid). If it is true, it means that there is no other centroid closer to

  For each point 𝑥 𝑖 it maintains 1) an upper bound 𝑢 𝑖 on the distance between 𝑥 𝑖 and the centroid 𝐺 𝑣 𝑖 to which it is assigned (inequation II.7, 𝑣 𝑖 is the index of the cluster containing the point whose index is 𝑖), and 2) 𝑘 lower bound, where each lower 𝑙 𝑖,𝑗 is on the distance between point 𝑥 𝑖 and a centroid 𝑥 𝑖 than 𝐺 𝑣 𝑖 . In this case, the same test is repeated on the next point. Otherwise, the inner test is called and loops the centroids list to determine if it is necessary tocalculate 𝑑𝑖𝑠(𝑥 𝑖 , 𝐺 𝑗 ). If 𝑢 𝑖 ≤ 𝑙 𝑖,𝑗 or 𝑢 𝑖 ≤ 𝑑𝑖𝑠(𝐺𝑣 𝑖 ,𝐺 𝑗 ) 2then 𝐺 𝑗 cannot be closer to 𝑥 𝑖 than 𝐺 𝑣 𝑖 and the distance between 𝑥 𝑖 and 𝐺 𝑗 is useless. Instead of limiting the distance between 𝑥 𝑖 and a centroid 𝐺 𝑗 , it limits the minimum distance between 𝑥 𝑖 and its nearest second centroid. The upper limit remains unchanged from Elkan.In each iteration and for each point 𝑥 𝑖 , the following test must be checked:𝑢 𝑖 < 𝑚𝑎𝑥(𝑙 𝑖 , 𝑠 𝑣 𝑖 ) (II.9) If (II.9) succeeds, then it implies that no centroid is closer to 𝑥 𝑖 than 𝐺 𝑣𝑖 . In this case, we move on to the next point. If it fails, then 𝑢 𝑖 is updated with the distance between 𝑥 𝑖 and its current centroid. The test is re-performed taking into account the new value of 𝑢 𝑖 . If the test fails again, then the distances between 𝑥 𝑖 and all 𝑘 centroids 𝑑𝑖𝑠(𝑥 𝑖 , 𝐺 𝑗 ) -||𝑥 𝑖 || ≤ ||𝐺 𝑗 ′ || ≤ 𝑑𝑖𝑠(𝑥 𝑖 , 𝐺 𝑗 ) + ||𝑥 𝑖 || (II.10) The inequation (II.10) is the Annulus representation. The norms ||𝑥 𝑖 || and ||𝐺 𝑗 ′ || correspond respectively to the distance from 𝑥 𝑖 and 𝐺 𝑗 ′ to the origin. The Annulus has the center at the origin, and its mathematic model is derived from the inverted triangular inequality. Geometrically, the Annulus is the difference between two circles with the same center as the origin. The radius of the first circle is 𝑑𝑖𝑠(𝑥 𝑖 , 𝐺 𝑗 ) -||𝑥 𝑖 ||. The second larger circle has a radius of 𝑑𝑖𝑠(𝑥 𝑖 , 𝐺 𝑗 ) + ||𝑥 𝑖 ||. So the Annulus width is twice 𝑑𝑖𝑠(𝑥 𝑖 , 𝐺 𝑗 ). Indeed the centroids 𝐺 𝑗 ′ are in the Annulus.

	4.1.5.3 Elkan's version Although compare-means and sort-means reduce the cal-culation rate of point-centroid distances, other methods, developed later, reduce it even more under certain conditions. Among the most well-known of these methods is the Elkan version (Elkan, 2003). It uses the triangular inequality tool several times and in different ways to avoid unnecessary calculations. It introduces, via this tool, bounds on the point-centroid distances. 𝐺 𝑗 (inequation II.8). 𝑑𝑖𝑠(𝑥 𝑖 , 𝐺 𝑣 𝑖 ) ≤ 𝑢 𝑖 (II.7) 𝑙 𝑖,𝑗 ≤ 𝑑𝑖𝑠(𝑥 𝑖 , 𝐺 𝑗 ) (II.8) These inequalities are exploited in the first phase of k-means. In Elkan version, this phase is subdivided into two parts: the outer test and the inner test. The outer test checks whether the point should change cluster without looping through the list of centroids. Concretely, II.4.1.5.4 Hamerly's version Hamerly version (Hamerly, 2010) is a modified version of Elkan. It seeks to minimize the use of inner tests in favor of outer tests. Instead of 𝑘 lower limits for each point, it sets just one. However, this does not have the same II.4.1.5.5 Annulus's version Annulus (Hamerly and Drake, 2015b) is a variant of Hamerly, implemented to optimize the assignment phase. When Hamerly fails in its test (II.9), it must calculate the distances between point 𝑥 𝑖 and all centroids. This is where Annulus brings its touch. Instead of visiting all the centroids, only some of them are involved in calculating the distances with the point 𝑥 𝑖 .This approach is a meaning as Elkan. are recalculated. reduction of the search space on the centroids.

So when looping the centroids, only the centroids 𝐺 𝑗 ′ are visited. The others are considered to be quite far from 𝑥 𝑖 .

	II.4.1.5.6 Exponion's version The Exponion algorithm (Newling and Fleuret, 2016)

is a geometric improvement of the Annulus algorithm. In practice, it is faster than the Annulus algorithm. The difference between them lies in the geometric tool used to reduce the search space of the centroids. Instead of Annulus centered on the origin, hyper-balls (generalized multi-dimensional circles) centered on centroids are chosen.

Geometrically, the centroid closest to 𝑥 𝑖 is located on the hyper-ball centered on 𝐺 𝑣 𝑖 (its closest centroid in the previous iteration) of radius 𝑢 𝑖 (upper bound on 𝑑𝑖𝑠(𝑥 𝑖 , 𝐺 𝑣 𝑖 ).

The two centroids closest to 𝑥 𝑖 are in the hyper-ball of centroid 𝐺 𝑣 𝑖 with a radius of 2 × 𝑢 𝑖 + 𝛿 𝑖 with 𝛿 𝑖 = 𝑑𝑖𝑠(𝐺 𝑣 𝑖 , 𝐺 𝑗 ′ ) with 𝐺 𝑗 ′ the closest centroid to 𝐺 𝑣 𝑖 .

  {𝑥 1 , . . . , 𝑥 𝑛 } is a dataset 𝑘 number of clusters 𝐶 𝐶 = {𝐶 1 , . . . , 𝐶 𝑘 }, is a set of clusters, 𝐺 𝐺 = {𝐺 1 , . . . , 𝐺 𝑘 }, is a set of centroids, each cluster 𝐶 𝑗 is associated with its centroid 𝐺 𝑗 𝑑𝑖𝑠(𝑥 𝑖 , 𝑥 𝑗 ) 𝑑𝑖𝑠 is a distance between the points 𝑥 𝑖 and 𝑥 𝑗 𝑠 𝑠 = {𝑠 𝑖 |𝑖 = 1...𝑛} set of stability levels, each point 𝑥 𝑖 is associated with its stability level 𝑠 𝑖 .

	Symbols Meaning
	𝑛	number of data points
	𝑋	𝑋 = Table III.1: Symbols

  In each iteration, in the first phase, we iterate on the 𝑘 𝑜𝑙𝑑 ← 𝑎 𝑖 {with 𝑎 𝑖 the index of the cluster to which point 𝑥 𝑖 is closest}

	4:	{first step}
	5:	for 𝑖 in 𝑖𝑛𝑑𝑒𝑥𝑒𝑠 do
	6:	{outer test is conducted}
	7:	if outer test fails then
	8:
	9:	{inner test}
	10:	{tests, specific to a given version of k-means, are performed in order to
		modify 𝑎 𝑖 or not}
	11:	if 𝑎 𝑖 ̸ = 𝑘 𝑜𝑙𝑑 then
	12:	𝑠 𝑖 ← 𝑠 𝑖 + 1
	13:	if 𝑠 𝑖 ≥ 𝑟 then
	14:	𝑖𝑛𝑑𝑒𝑥𝑒𝑠 ← 𝑖𝑛𝑑𝑒𝑥𝑒𝑠∖𝑖
	15:	end if
	16:	else
	17:	𝑠 𝑖 ← 0
	18:	end if
	19:	end if
	20:	end for
	21:	{second step}
	22:	{centroids update}
	23:	{update of the boolean variable convergence}
	24:
		First, the outer test and inner test for passive points are removed, which means that
		bounds calculations and point-center distance calculations are avoided. Secondly, the
		updating of the passive point bounds, which requires additional calculations, is also
		removed.
		We ran Sk-means on a sample dataset to show its benefits. The dataset used has
		100,000 two-dimensional points and consists of 11 real clusters, some of which are con-

points' indexes. Then, the outer test and inner test are eventually triggered. Indeed, depending on the k-means version, the outer test and the inner test are both triggered, only one of the both, or neither of the two. If at least one is used, the tests associated with the original version are used. After these tests, we check if the point has changed the cluster. If it is the case, we check if the point is likely to become passive using the value of 𝑟. If it becomes passive, then its index is removed from the list of point indices. In other words, at the next iteration, we no longer iterate on this point until convergence. Then follows the second step, which is the updating of the clusters' centroids. Then other updates of the variables specific to the original version are carried out, i.e., calculations of new values of the bounds associated with each point. In this case, when the point is passive, the bounds of the point are no longer updated. Lloyd's version does not intrinsically have a computational optimization strategy compared to algorithms based on geometric reasoning. So it does not have the inner test and the outer test. Consequently, it is the version that takes the most advantage of the Sk-means strategy. Compare-means and Sort-means do not adopt the outer-test and therefore focus on the inner test. Exponion exploits the outer test and the inner test. The effect of Sk-means on versions based on geometrical reasoning is twofold. tiguous. The purpose of k-means is then to identify these clusters. We have launched on the dataset the versions benefiting from Sk-means (OLloyd, OSort, OCompare and OExponion) and the versions not benefiting from Sk-means (Lloyd, Sort, Compare Algorithm 1 Sk-means Input: 𝑘,𝐺,𝑋,𝑟 Output: 𝐶 1: 𝑠 ← {0∀𝑖 = 1...𝑐𝑎𝑟𝑑(𝑋)} 2: convergence ← true 3: while convergence = true do

Table III

 III

	.2: Parameter value range
	expression:

  TableIII.3: Spearman's test results on the correlations between 𝑘,𝑑,𝑛, 𝑠𝑝 and 𝑟, and the total number of iterations that k-means took to converge.

	Parameter correlation p-value
	𝑛	0.88	0.00
	𝑑	0.13	1.60𝑒 -14
	𝑘	-0.28	9.91𝑒 -65
	1 -𝑠𝑝	0.47	3.37𝑒 -190
	𝑟	0.93	0.0

  Table III.4: Description of the datasets used to evaluate Sk-means function is considered better. The LLoyd, Compare-means, Sort-means and Exponion algorithms all produce the same 𝑠𝑠𝑒 value.

	Data name d	n	Description
	birch	2	100000 a list of Gaussian clusters organised in a data space divided into
				10x10 squares
	covtype	54	150000 remote measurements of ground cover
	cup98	56	95412	dataset proposed by KDD98
	mnist50	50	60000	database of handwritten digits (MNIST), having undergone
				a random projection.
	mnist784	784 70000	database of handwritten digits (original MNIST)
	vehicle	100 98528	database of vehicles whose characteristics are obtained from seismic and
				acoustic sensors
	III.2.5.5 Results analysis

  ) . The gains of these two algorithms, on different values of 𝑘, are stable as for the other algorithms, ranging from 3.7 to 4.8 for compare-means and from 3.4 to 4.8 for sort-means. All in all, the versions benefiting from Sk-means bring an overall gain that is not negligible, especially when 𝑘 is large. This table III.5 compares the different versions of k-means compared to Lloyd's version in terms of execution time. The experiments' results, launched on the same data set and at the same value of 𝑘 but different by the initialization of the centroids, are averaged in this table (in fact, the average of two experiments).

  table III.6), in absolute value, Δ𝑠𝑠𝑒 is less than 0.01 (i.e. 1%) except for birch at 𝑘 = 200 which is at 0.012 exceeding very slightly the 1%. The difference is null in several cases or even negative (at cup98, 𝑘 = 8) i.e., slightly better quality for the optimized versions. For each dataset and k value, the optimized versions have almost TableIII.5: Number of times the algorithms are accelerated compared to Lloyd's version. Algorithms beginning with the letter o refer to algorithms that have benefited from the Sk-means strategy. The numbers in bold correspond to the best acceleration for a given dataset and 𝑘.

							k	k
	data name Data name Method method	8	8	60	60	200	200	500	500
		compare ocompare 0.003 3.55	13.36 0.009 0.012 0.008 19.45 21.35
	birch	exponion 18.03 33.57 lloyd 1.00 1.00 oexponion 0.003 0.009 0.012 0.008 58.25 80.46 1.00 1.00 olloyd 0.003 0.009 0.012 0.008
	birch	ocompare 23.14 95.93 133.62 113.08 osort 0.003 0.009 0.012 0.008 oexponion 18.96 76.29 160.69 191.12 ocompare 0 0.002 0.003 0.005
	covtype	olloyd osort oexponion 0 olloyd 0	7.03 24.72 109.03 135.64 105.60 7.96 7.17 5.41 0.002 0.003 0.005 0.002 0.003 0.005
		osort	sort	0	4.13	26.12 0.002 0.003 0.005 61.31 75.38
		compare ocompare -0.005 0.001 0.003 0.006 3.46 10.34 15.24 18.64
	cup98	exponion lloyd oexponion -0.005 0.001 0.003 0.006 7.00 16.63 23.90 32.32 1.00 1.00 1.00 1.00 olloyd -0.005 0.001 0.003 0.006
	covtype	ocompare osort oexponion 4.02 5.10 -0.005 0.001 0.003 0.006 30.88 73.04 111.16 23.63 53.04 92.80 ocompare 0 0.008 0.002 0.001
	mnist50	olloyd osort oexponion 0 olloyd 0	1.56 5.65	3.12 38.77 0.008 0.002 0.001 4.91 6.31 94.18 149.50 0.008 0.002 0.001
		osort	sort	0	3.79	15.90 0.008 0.002 0.001 32.85 61.07
		compare ocompare 0	2.64	7.32 0.001 0.001 0.001 10.17 11.84
	mnist784	exponion lloyd oexponion 0 olloyd 0	4.66 1.00	4.46 1.00 0.001 0.001 0.001 5.83 7.74 1.00 1.00 0.001 0.001 0.001
	cup98	ocompare osort oexponion 5.81 7.05 0 ocompare 0.001	22.11 0.001 0.001 0.001 57.07 87.23 7.61 19.20 31.11 0.001 0.001 0.001
	vehicle	olloyd osort oexponion 0.001 2.77 7.53 olloyd 0.001	3.39 26.33 0.001 0.001 0.001 6.21 8.03 66.43 97.85 0.001 0.001 0.001
		osort	sort	2.88 0.001	9.59 0.001 0.001 0.001 14.97 22.71
		compare		4.54		5.89		6.58	7.21
		exponion 16.65		9.91		8.54	6.62
			lloyd		1.00		1.00		1.00	1.00
	mnist50	ocompare 12.80 53.24 oexponion 16.38 37.58	29.34 20.57	16.25 11.11
		olloyd		2.88		9.29		4.45	2.21
		osort		14.56 60.25	32.82	18.05
			sort		5.27		7.41		8.37	9.15
		compare		0.88		1.01		1.13	1.17
		exponion		2.90		4.03		3.12	1.99
			lloyd		1.00		1.00		1.00	1.00
	mnist784	ocompare oexponion 3.09 1.75		5.18 8.84		5.34 9.48	4.78 5.48
		olloyd		1.83		5.33		6.05	4.03
		osort		1.74		5.23		6.22	4.78
			sort		1.04		1.19		1.13	1.19
		compare		0.98		1.47		1.66	1.88
		exponion		5.06		2.95		2.28	2.17
			lloyd		1.00		1.00		1.00	1.00
	vehicle	ocompare oexponion 10.51 5.05		4.92 5.50		7.64 5.85	7.92 5.71
		olloyd		4.72		4.27		4.81	4.13
		osort		4.87		5.32		7.64	7.99
			sort		1.05		1.45		1.72	1.90

the same rate of difference. This shows that the optimized versions converge almost at the same speed in terms of the number of iterations. Moreover, it is experimentally observed that there are always fewer iterations in the optimized versions than in the original versions. Table III.6: Relative difference in SSE between each optimized algorithm and the LLoyd version.

  Experimentally, k-means versions integrating Sk-means are up to 191 times faster than Lloyd's version. A version with Sk-means can be up to 5 times faster than its original non-optimized version. Moreover, overall, the relative error between partitionings is below 1%. Therefore, the objective functions of k-means versions with Sk-means and those without Sk-means provide almost the same local solutions, i.e. i.e. the differences in terms of clustering results are negligible. {𝑥 1 , . . . , 𝑥 𝑛 } is a dataset, with 𝑥 𝑖 ∈ R 𝑑 𝑘 number of clusters 𝐶 𝐶 = {𝐶 1 , . . . , 𝐶 𝑘 }, is a set of clusters, 𝐺 𝐺 = {𝐺 1 , . . . , 𝐺 𝑘 }, is a set of centroids, each cluster 𝐶 𝑗 is associated with its centroid 𝐺 𝑗 𝑑𝑖𝑠(𝑥 𝑖 , 𝑥 𝑗 ) 𝑑𝑖𝑠 is a distance between the points 𝑥 𝑖 and 𝑥 𝑗 𝑤 number of leaf nodes in the Kd-tree data structure 𝜐 index used to refer to a leaf node, or to iterate on a list of leaf indices annotated ϑ ℎ 𝑗 it corresponds to a hyper-rectangle encompassing the points of cluster 𝐶 𝑗

	III.3 KD-means
	Symbols Meaning
	𝑛	number of data points
	𝑑	dimension of data points
	𝑋	𝑋 = Table III.7: Symbols

  𝑥 𝜐 ⊂ 𝑋 2: Γ, 𝑘, 𝐼 ← 𝑒𝑠𝑡𝑖𝑚𝑎𝑡𝑒𝐾(𝐿𝐷, 𝑘 𝑚𝑎𝑥 ) 3: { 𝐼 is defined as {𝐼 𝑗 |𝑗 = 1..𝑘} with 𝐼 𝑗 the set of point indices of cluster 𝑗 and Γ set of centroids.} 4: {For each cluster, a hyper-rectangle is instantiated as well as its 𝑠𝑠𝑒 is calculated.}

	Algorithm 2 InitializeLeaf
	Input: 𝑘 𝑚𝑎𝑥 ,𝑋,𝜐
	Output: 𝜁
	5: for 𝑗 = 1 to 𝑗 = 𝑘 do
	6: 7:	𝜁 𝑗 𝐼 ← 𝐼 𝑗 𝜁 𝑗 𝐺 ← Γ 𝑗
	8:	𝜁 𝑗 𝑚𝑎𝑥𝑒𝑠 ← 𝑚𝑎𝑥(𝐿𝐷 𝐼 𝑗 )
		𝑤 , 𝑘𝑚𝑎𝑥	𝑤 ≥ otherwise √ 𝑘 𝑚𝑎𝑥	(III.11)

1: 𝐿𝐷 ← 9:

  ∑𝜐∈ϑ 𝑘 𝜐 is at least equal to 𝑘 𝑚𝑎𝑥 and therefore 𝑡ℎ_𝑒𝑣𝑜 will be unchanged. Otherwise, if 𝑘 𝑚𝑎𝑥 >

	Algorithm 3 Local merger
	Input: 𝜁, τ, 𝑡ℎ_𝑒𝑣𝑜
	Output: 𝜁
	1: 𝑚𝑒𝑟𝑔𝑒𝑑 ← 𝑇 𝑟𝑢𝑒
	2: 𝑖𝑡 ← 0
	3: 𝑜𝑙𝑑_𝑐𝑎𝑟𝑑_𝑙ℎ ← 𝑐𝑎𝑟𝑑(𝜁)
	4: while 𝑚𝑒𝑟𝑔𝑒𝑑 = 𝑇 𝑟𝑢𝑒 do
	5:	ℎ 𝑢 ← 𝜁 𝑖𝑡
	6:	𝑇 ← {𝑖𝑡}
	7:	𝑡𝑚𝑝_𝑖𝑛𝑑𝑒𝑥𝑒𝑠 ← {0, ..., 𝑜𝑙𝑑_𝑐𝑎𝑟𝑑_𝑙ℎ}
	8:	𝑡𝑚𝑝_𝑖𝑛𝑑𝑒𝑥𝑒𝑠 ← 𝑡𝑚𝑝_𝑖𝑛𝑑𝑒𝑥𝑒𝑠∖{𝑖𝑡}
	9:	for 𝑖 𝑖𝑛 𝑡𝑚𝑝_𝑖𝑛𝑑𝑒𝑥𝑒𝑠 do
	10:	ℎ 𝑣 ← 𝜁 𝑖
	11:	Δ𝐺 ← ||𝐺 𝑢 -𝐺 𝑣 ||
		{Criteria 1}
	12: 13:	if Δ𝐺 < τ 𝜖 then Δ𝐶 ← || ℎ𝑢.𝑚𝑖𝑛𝑠+ℎ𝑢.𝑚𝑎𝑥𝑒𝑠 2	-ℎ𝑣.𝑚𝑖𝑛𝑠+ℎ𝑣.𝑚𝑎𝑥𝑒𝑠 2	||
	14:	𝑒 ← 𝐹 𝑎𝑙𝑠𝑒
		{Criteria 2}
	15:	if Δ𝐺 < Δ𝐶 then
	16:	𝑚𝑖𝑛𝐷𝑖𝑠𝑡𝑎𝑛𝑐𝑒𝑋𝑌 ← 𝑚𝑖𝑛𝐻(ℎ 𝑢 , ℎ 𝑣 )
		{Criteria 3}
	17:
	18:	𝑒 ← 𝑇 𝑟𝑢𝑒
	19:	end if
		{Criteria 4}
	20:
	21:	𝑒 ← 𝑇 𝑟𝑢𝑒
	22:	end if '
	23:	if 𝑒 = 𝑇 𝑟𝑢𝑒 then
	24:	𝑇 ← 𝑇 ∪ 𝑖
	25:	end if
	26:	end if
	27:	end if			∑ 𝜐∈ϑ 𝑘 𝜐
	28:	then 𝑡ℎ_𝑒𝑣𝑜 is recalculated according Equation III.20. if 𝑐𝑎𝑟𝑑(𝑇 ) > 1 then
	29:	𝜁 ← 𝑚𝑒𝑟𝑔𝑒(𝑇 )
	30: 31:	𝛿𝑘 = |1 -{The new hyper-rectangles are placed at the end of the list} 𝑘 𝑚𝑎𝑥 ∑ | end if 𝜐∈ϑ 𝑘 𝜐 𝑛𝑒𝑤_𝑐𝑎𝑟𝑑_𝑙ℎ ← 𝑐𝑎𝑟𝑑(𝜁)	(III.19)
	32: 33: 34:	𝑡ℎ_𝑒𝑣𝑜 = if 𝑜𝑙𝑑_𝑐𝑎𝑟𝑑_𝑙ℎ < 𝑛𝑒𝑤_𝑐𝑎𝑟𝑑_𝑙ℎ then ⎧ ⎪ ⎨ ⎪ ⎩ 𝑡ℎ_𝑒𝑣𝑜, 𝑡ℎ_𝑒𝑣𝑜 + 𝛿𝑘, otherwise if 𝛿𝑘 ≥ 1 𝑜𝑙𝑑_𝑐𝑎𝑟𝑑_𝑙ℎ ← 𝑛𝑒𝑤_𝑐𝑎𝑟𝑑_𝑙ℎ 𝑖𝑡 ← 0	(III.20)
	35:	else
	36: 37:	if 𝑖𝑡 + 1 < 𝑛𝑒𝑤_𝑐𝑎𝑟𝑑_𝑙ℎ then III.3.6.4 Local merger algorithm 𝑖𝑡 ← 𝑖𝑡 + 1
	38:	else
		𝑚𝑒𝑟𝑔𝑒𝑑 ← 𝐹 𝑎𝑙𝑠𝑒
	39:	end if
	40:	end if
	41:

. Algorithm 3 ( local merger) allows us to merge clusters whose representative hyperrectangles are included in the 𝜁 set. 𝜁 hyper-rectangles are associated with a list of if 𝑚𝑖𝑛𝐷𝑖𝑠𝑡𝑎𝑛𝑐𝑒𝑋𝑌 = 0 and Δ𝐺 < Δ𝐶 * 𝜆 then if 𝑒 = 𝑇 𝑟𝑢𝑒 and 𝑒𝑣𝑜 ≤ 𝑡ℎ_𝑒𝑣𝑜 and 𝑚𝑖𝑛𝐷𝑖𝑠𝑡𝑎𝑛𝑐𝑒𝑋𝑌 ≤ τ 𝜖 then

  Table III.8: Real data sets characteristics.

	dataset	k	d	n
	vehicle	4	18	1000000
	satimage	6	36	1000000
	japaneseVowels 9	14	1000000
	fourier	10 76	1000000
	pendigits	10 16	1000000
	fashionmnist	10 784 70000
	ldpa	11 5	164860
	walking	22 4	149332
	letter	26 16	999999
	zernike	47 47	1000000
	emnist	62 784 697932

  was used as a distance between two partitionings. It measures the amount of information gained and lost for a dataset passing from a partition A to another partition B. It respects the three properties of triangular inequality. So the smaller the 𝑣𝑖 is, the closer the partitionings are to each other.

			Kd-means G-means	X-means
	k	d n	Δ𝑡	Δ𝑡 (× slower than Kd-means)
	10 4 1 × 10 6 39.7	344.3(8.7)	816.2(20.6)
		2 × 10 6 65.4	774.1(11.8)	1420.5(21.7)
		4 × 10 6 117.4	1517.3(12.9) 2203.6(18.8)
		6 1 × 10 6 41.9	396.4(9.5)	1101.5(26.3)
		2 × 10 6 72.9	926.9(12.7)	1869.9(25.7)
		4 × 10 6 133.7	1628.0(12.2) 3061.4(22.9)
		8 1 × 10 6 45.9	386.0(8.4)	789.4(17.2)
		2 × 10 6 81.2	823.1(10.1)	1253.5(15.4)
		4 × 10 6 153.6	1727.2(11.2) 2378.8(15.5)
	32 4 1 × 10 6 77.6	535.6(6.9)	2817.2(36.3)
		2 × 10 6 132.5	1152.8(8.7)	4831.0(36.5)
		4 × 10 6 233.7	2468.4(10.6) 7628.1(32.6)
		6 1 × 10 6 79.2	586.7(7.4)	3689.9(46.6)
		2 × 10 6 146.9	1375.6(9.4)	7880.7(53.7)
		4 × 10 6 260.2	2485.1(9.5)	7901.8(30.4)
		8 1 × 10 6 82.2	665.7(8.1)	2491.6(30.3)
		2 × 10 6 154.9	1383.3(8.9)	3740.0(24.2)
		4 × 10 6 299.5	2883.7(9.6)	5037.7(16.8)
	80 4 1 × 10 6 141.5	781.9(5.5)	7807.2(55.2)
		2 × 10 6 283.2	1673.6(5.9)	14147.0(50.0)
		4 × 10 6 570.8	3417.8(6.0)	21887.1(38.3)
		6 1 × 10 6 148.3	893.0(6.0)	10385.8(70.1)
		2 × 10 6 285.4	1892.4(6.6)	22403.6(78.5)
		4 × 10 6 578	4039.2(7.0)	37716.6(65.3)
		8 1 × 10 6 151.5	1016.0(6.7)	7834.6(51.7)
		2 × 10 6 308.2	1708.6(5.5)	21824.6(70.8)
		4 × 10 6 626.4	3581.8(5.7)	47130.8(75.2)

  Table III.10: Comparison of the three algorithms, on real data, with respect to execution time(Δ𝑡).

Table III .

 III 11: Comparison of the three algorithms, executed on synthetic data, with respect to the quality of clustering(vi) and the k estimation.

		Kd-means		G-means		X-means
	dataname	k(Δ𝑘)	vi	k(Δ𝑘)	vi	k(Δ𝑘)	vi
	vehicle	3.0(0.28)	2.9 2226(555.5)	11.8 16.0(3.0)	5.3
	satimage	28.9(3.81) 2.7 1177(195.17) 8.8	28.7(3.78)	3.8
	japaneseVowels 9.4(0.83)	4.5 3377(374.22) 12.5 32.0(2.56)	7.7
	pendigits	29.1(1.91) 3.6 2574(256.4)	9.1	32.0(2.2)	4
	fourier	39.2(2.92) 3	1309(129.9)	8	57.3(4.73)	3.9
	fashionmnist	10.9(0.11) 3.3 533(52.3)	7.1	32.0(2.2)	4
	ldpa	32.5(1.96) 6.3 1766(159.55) 10.8 47.2(3.3)	7.1
	walking	39.6(1.35) 6.7 1257(56.14)	10	100.7(3.58) 8.4
	letter	59.7(1.3)	7.2 1581(59.81)	11.1 117.0(3.5)	8.6
	zernike	86.9(1.08) 5.3 1157(23.62)	9	128.0(1.72) 6.4
	emnist	45.6(0.26) 6	3073(48.56)	8.6	256.0(3.13) 6.7

  Table III.13: Performance of our algorithm as a function of the value of 𝑡ℎ_𝑒𝑣𝑜 Table III.14: Performance of our algorithm as a function of the value of ψ III.3.8.6 Parameter sensitivity analysis

		Synthetic data	Real data
	th_evo Δ𝑘	vi	Δ𝑡 Δ𝑘	vi	Δ𝑡
	0.05	0.3 0.8 213.2 1.7 4.9 132.5
	0.10	0.3 0.8 203.1 1.6 4.8 144.5
	0.15	0.3 0.8 198.2 1.5 4.7 134.0
	0.20	0.3 0.8 193.5 1.4 4.7 141.1
	0.25	0.3 0.9 188.6 1.2 4.5 136.5
	0.30	0.4 1.0 183.8 1.3 4.6 130.5
		Synthetic data	Real data
	ψ Δ𝑘	vi	Δ𝑡 Δ𝑘	vi	Δ𝑡
	4	0.5 1.1 195.0 1.3 4.2 131.1
	8	0.3 0.8 201.5 1.2 4.4 141.3
	10 0.3 0.7 200.0 1.4 4.8 136.1
	12 0.3 0.8 190.5 1.9 5.3 137.5

  TableIII.15: Overlapping rate of each of the nine classes of Pavia. The rate is calculated as detailed in subsection III.3.8.5 but adapted to the class level instead of the entire dataset.

	class	asphalt meadows gravel trees metal sheets
	overlapping rate 0.225	0.172	0.907	0.325 0.033
	class		bare soil bitumen bricks shadows
	overlapping rate 0.729	0.489	0.423 0.001

  . The 𝑘-nearest neighbor graph highlights the local relationships between each point and its surrounding points in the data space. By extension, these relations make it possible to better capture the different spatial densities with local precision.Therefore, the first step is the construction of the 𝑘-nearest neighbor graph of the dataset. From the dataset 𝑋, an undirected weighted graph annotated 𝐺 = (𝑉, 𝐸) is constructed, where 𝑉 = {𝑣 1 , 𝑣 2 ...} is the set of vertices representing data points, and 𝐸 = {𝑒 𝑞 = (𝑣 𝑥 , 𝑣 𝑦 , 𝑤 𝑞 )|𝑣 𝑥 ∈ 𝑉, 𝑣 𝑦 ∈ 𝑉, 𝑤 𝑞 ∈ R + } is the set of edges between data points. For each point, we determine 𝑘 edges to 𝑘-nearest neighbor points. The weight 𝑤 𝑞 of each edge 𝑒 𝑞 is the distance between the two linked points 𝑣 𝑥 and 𝑣 𝑦 .To gain efficiency and accuracy, it is possible to get rid of many unnecessary distances. We favor short distances, avoiding keeping too large distances in the 𝑘-nearest neighbors. To obtain dense (connected) sub-graphs, we generate a Minimum Spanning Tree (MST) from 𝐺. Constructing the MST of 𝐺 consists in minimizing the number of edges while minimizing the total sum of the weights and keeping 𝐺 connected.

  𝑛 = |𝑋| (number of nodes in 𝐺 𝑚𝑖𝑛 ), and 𝑛 -1 is the number of distances. The smoothing factor ℎ ∈ [0; +∞] is called the bandwidth. It acts as a precision parameter, and in our case, it influences the number of peaks detected in the 𝑝.𝑑.𝑓 and therefore, the number of different densities. A commonly used method to estimate ℎ 98CHAPTER IV. DECWA: DENSITY-BASED CLUSTERING USING WASSERSTEIN DISTANCE Algorithm 6 Graph division process Input: 𝐺 𝑚𝑖𝑛 = (𝑉 𝑚𝑖𝑛 , 𝐸 𝑚𝑖𝑛 ), = {..., 𝑙 𝑡 , 𝑙 𝑡+1 , ...} Output: ℘ 1 1: ℘ | | ← ∅ 2: ℵ | | ← (𝑉 𝑚𝑖𝑛 , 𝐸 𝑚𝑖𝑛 ) 3: for 𝑡 ← | | -1 to 1 do 𝐸 𝑡 ← {𝑒 𝑞 ∈ 𝐸 𝑡+1 |𝑤 𝑞 < 𝑙 𝑡 } 𝑉 𝑡 ← {𝑣 𝑞 ∈ 𝑉 𝑡+1 |∃(𝑣 𝑞 , 𝑣 𝑦 , 𝑤 𝑞 ) ∈ 𝐸 𝑡 ∨ (𝑣 𝑥 , 𝑣 𝑞 , 𝑤 𝑞 ) ∈ 𝐸 𝑡 }

	4:
	5:
	6:	ℵ 𝑡 ← (𝑉 𝑡 , 𝐸 𝑡 )
	7:

  First of all, it identifies the edge set 𝐸 𝑔 ⊂ 𝐸 𝑚𝑖𝑛 containing only nodes whose respective subgraphs are different. Then it runs an iterative sub-process consisting in iterating on the edges of 𝐸 𝑔 . For each edge 𝑒 𝑞 ∈ 𝐸 𝑔 we verify that ||𝐶 𝑖 -𝐶 𝑗 || ≤ 𝜆 and 𝑤𝑠(𝐷 𝑖 , 𝐷 𝑗 ) ≤ 𝜇. In this case, 𝐶 𝑖 and 𝐶 𝑗 are merged. This is operated by the union of 𝐷 𝑖 , 𝐷 𝑗 and 𝑤 𝑞 and considering the points of 𝐶 𝑖 and 𝐶 𝑗 as belonging to the same sub-graph. Note that if 𝑚𝑖𝑛(|𝐷 𝑖 |, |𝐷 𝑗 |) ≤ 1 then only the first condition applies as 𝑤𝑠 can't be calculated with this cardinality. The iterative sub-process is repeated until there are no longer merges. The last iteration does not result in any merging and the points of the clusters whose cardinality is 1 are considered as outliers. As an example, the result obtained on the jain dataset corresponds exactly to the real clusters as on the right side of the 102CHAPTER IV. DECWA: DENSITY-BASED CLUSTERING USING WASSERSTEIN DISTANCE figure IV.3.

  Algorithm 7 Sub-cluster mergerInput: 𝐷, ℘ 1 = {..., 𝑠𝑔 𝑖 , ..., 𝑠𝑔 𝑗 , ...}, 𝜆 ≥ 0, 𝜇 ≥ 0 Output: ℘ 1 1: 𝐸 𝑔 ← ∅ 2: for all 𝑒 𝑞 ∈ 𝐸 𝑚𝑖𝑛 |𝑒 𝑞 = (𝑣 𝑥 , 𝑣 𝑦 , 𝑤 𝑞 ) do 3: if 𝑣 𝑥 ∈ 𝑠𝑔 𝑖 ∧ 𝑣 𝑦 ∈ 𝑠𝑔 𝑗̸ =𝑖 then 𝐸 𝑔 ← 𝐸 𝑔 ∪ {𝑒 𝑞 } 𝐷 𝑖 (respectively 𝐷 𝑗 ) is associated to 𝑠𝑔 𝑖 (𝑠𝑔 𝑗 )//the subgraph 𝑖 and/or 𝑗 as small, so it is considered close to the other w.r.t. wasserstein distance.// wasserstein distance 𝑤𝑠 between 𝐷 𝑖 and 𝐷 𝑗 is computed

	4:
	5:	end if
	6: end for
	7: repeat
	8:	𝜖 ← 0
	9:	for all 𝑒 𝑞 ∈ 𝐸 𝑔 do
	10:	if 𝑤 𝑞 < 𝜆 then
	11: // 12: if 𝐷 𝑖 ≤ 1 ∧ 𝐷 𝑗 ≤ 1 then
	13:
	14:	𝛿 ← -1
	15:	else
	16:
	17:	𝛿 ← 𝑤𝑠(𝐷 𝑖 , 𝐷 𝑗 )
	18:	end if
	19:	if 𝛿 < 𝜇 then
	20:	// agglomeration of 𝑠𝑔 𝑖 and 𝑠𝑔 𝑗
	21:	𝐷 ← (𝐷 ∖ 𝐷 𝑖 ) ∖ 𝐷 𝑗
	22:

  Table IV.2: Characteristics of data sets.

	Dataset	Dimensions Size	LD SD
	jain	2	373
	compound	2	399	x	x
	pathbased	2	300		x
	cluto-t7.10k	2	10000
	iris	4	150		x
	cardiotocography 35	2126
	plant	65	1600	x	x
	GCM	16064	190	x	x
	new3	26833	1519		x
	kidney_uterus	10936	384		x

  datasets are synthetic. They contain clusters of different shapes and spatial densities( i.e. clusters are not necessarily generated by the same law of probability). For these data, the Euclidean distance was used.

		DECWA	DBCLASD	DENCLUE	HDBSCAN
	Dataset	ARI outliers(%) ARI outliers(%) ARI outliers(%) ARI outliers(%)
	jain	0.94 0.00	0.90 0.03	0.45 0.06	0.94 0.01
	compound	0.95 0.05	0.77 0.06	0.82 0.05	0.83 0.04
	pathbased	0.76 0.00	0.47 0.03	0.56 0.00	0.42 0.02
	cluto-t7.10k	0.95 0.03	0.79 0.06	0.34 0.00	0.95 0.10
	iris	0.77 0.04	0.62 0.07	0.74 0.00	0.57 0.00
	cardiotocography 0.47 0.04	0.24 0.17	0.47 0.02	0.08 0.28
	plant	0.18 0.03	0.04 0.07	0.14 0.17	0.04 0.38
	GCM	0.46 0.05	0.18 0.18	0.24 0.06	0.27 0.27
	new3	0.41 0.01	0.09 0.45	0.08 0.13	0.13 0.27
	kidney_uterus	0.80 0.00	0.53 0.08	0.56 0.09	0.53 0.26
	Average	0.67 0.02	0.46 0.12	0.44 0.06	0.48 0.16
		Table IV.3: Experimental results
	consists of 190 tumor samples. Each one represented by the expression levels of 16063
	genes. The second dataset (kidney_uterus) is proposed by expO (EXpression Project
	IV.9.2.4 Real datasets
	The cardiotocography dataset (Ayres-de Campos et al., 2000) is a set of 2126 fetal
	cardiotocogram records, with 35 attributes providing vital information on the state of
	the fetus. The records are grouped into 10 classes, therefore 10 clusters are expected.
	Canberra distance was applied to it. Plant dataset (Mallah et al., 2013) is considered
	as a classification problem. It consists of 1600 leaves of 100 different classes. Each
	leaf is characterized by 64 shape measurements retrieved from its binary image. The

Euclidean distance was used on Plant. Another known dataset, Iris

[START_REF] Dua | UCI machine learning repository[END_REF]

) (150 iris flowers, 4 dimensions, 3 classes) was used with the Manhattan distance.

A collection of two very large biological datasets were tested. The first dataset, GCM

[START_REF] Ramaswamy | Multiclass cancer diagnosis using tumor gene expression signatures[END_REF]

, is used to diagnose the type of cancer (14 classes). It 108CHAPTER IV. DECWA: DENSITY-BASED CLUSTERING USING WASSERSTEIN DISTANCE

  TableIV.4: Comparison of methods for estimating ℎ. Pm refers to our proposed method.conducted using 𝑘 = 𝑙𝑜𝑔(|𝑉 |). Our proposed method achieves good scores and is even able to catch up Silverman's rule of thumb on average.

	110CHAPTER IV. DECWA: DENSITY-BASED CLUSTERING USING WASSERSTEIN DISTANCE
			pm	yellowbrick	biggest plateau	median	silverman
	dataset	ARI ouliers ARI ouliers ARI	ouliers	ARI ouliers ARI ouliers
	jain	0.94	0.00	0.94	0.00	0.94	0.00	0.94	0.00	1.00	0.00
	compound	0.91	0.03	0.91	0.02	0.89	0.10	0.89	0.10	0.91	0.02
	pathbased	0.61	0.02	0.44	0.00	0.68	0.00	0.61	0.02	0.68	0.00
	cluto-t7.10k	0.91	0.02	0.55	0.00	0.49	0.01	0.49	0.01	0.93	0.03
	iris	0.70	0.09	0.60	0.01	0.70	0.09	0.72	0.09	0.58	0.02
	cardiotocography 0.38	0.05	0.38	0.03	0.36	0.06	0.36	0.06	0.47	0.04
	plant	0.18	0.03	0.11	0.00	0.12	0.01	0.18	0.02	0.20	0.03
	GCM	0.43	0.09	0.44	0.04	0.43	0.18	0.43	0.18	0.44	0.04
	new3	0.40	0.04	0.42	0.03	0.40	0.04	0.40	0.01	0.40	0.05
	kidney_uterus	0.77	0.00	0.80	0.02	0.65	0.03	0.35	0.04	0.51	0.00
	Average	0.62	0.04	0.56	0.01	0.57	0.05	0.54	0.06	0.61	0.02

Table IV

 IV

.5: Influence of k in terms of clustering but it is not a prerequisite. If 𝑘 = 𝑙𝑜𝑔(|𝑉 |) or 𝑘 = √ (|𝑉 |), even if the connectivity is not fully ensured DECWA remains efficient. Therefore, 𝑘 = 𝑙𝑜𝑔(|𝑉 |) might be a valid choice to consider rather than 𝑘 = √ |𝑉 | if speed is required.

Table 1 :

 1 . Dimensionality reduction is Advantages and drawbacks of general optimization strategies usually applied upstream of the classification process. It is at the process beginning that the space resulting from the dimensionality reduction is exploited.

	type	advantages		limitations
	distance re-	speed up distance calcula-	requires to store for
	formulation	tions			each point a list of
					pre-calculated results
	reduced dis-				not suitable for methods
	tance				requiring precise distances
	pds	speeds	up	distance
		calculations on high-
		dimensional data
	dimensionality	reduces the algorithmic	classification quality af-
	reduction	complexity in time of the	fected if significant useful
		calculations performed on	information is lost
		the points because the
		dimension is considerably
		reduced

Table 2 :

 2 Experimental results from Birch's execution of the synthetic data. Note that Δ𝑡 is expressed in seconds.

	dataset	k	d	n	k(estimated) vi	Δ𝑡
	vehicle	4	18	1 × 10 6 185367	14.9 19878
	satimage	6	36	1 × 10 6 78816	8.8	15977
	japaneseVowels 9	14	1 × 10 6 133	8.3	5586
	fourier	10 76	1 × 10 6 121954	6.4	15513
	pendigits	10 16	1 × 10 6 70560	15.9 39768
	fashionmnist	10 784 70000	36655	12.8 217
	ldpa	11 5	164860 87375	14.6 381
	walking	22 4	149332 20076	7.1	159
	letter	26 16	999999 10580	11.6 18430
	zernike	47 47	1 × 10 6 81693	16.6 49564
	emnist	62 784 697932 92767	14.1 55956

Table 3 :

 3 Experimental results from Birch's execution of the real data. Note that Δ𝑡 is expressed in seconds.

This paradigm has another well-known name, centroid-based methods. In this manuscript, both names are used.

do not confuse the 𝑘 of Kd-tree, which is just the dimension of the data stored in the tree while the 𝑘 of k-means which corresponds to the number of clusters

We consider the 𝑠𝑠𝑒 of 𝐿 and 𝑀 respectively 𝑞 𝑙 and 𝑞 𝑚 already calculated, which is the case because the 𝑠𝑠𝑒 are calculated entirely only in the leaves, but in the internal nodes the formula III.15 is used.

PCA(Principal component analysis) is a method that reduces a dataset defined in 𝑞-dimensional data space to another 𝑝-dimensional data space with 𝑞 > 𝑝 while keeping as much relevant information as possible. In our case, this method allows us to visualize the approximate arrangement between the different classes of the dataset.

A color present in different figures do not identify the same object(one instance of a class, e.g., meadows is a class, and an object is a meadow located in a zone of the image), i.e., a color of an object in one of the three figures b,d and e (figure III.18) could correspond to another color in the other two remaining figures.

GMM is a probabilistic approach that produces both spherical and elliptical clusters. Nevertheless, it requires the number of clusters to be provided a priori.

Remerciements

Je dois une gratitude particulière à mes directeurs de thèse Olivier Teste et Franck Ravat pour leur profonde préoccupation, leurs encouragements perpétuels, leurs excellents conseils, leur coopération aimable et leur soutien incontestable pendant mes travaux de recherche. Aussi, je les remercie chaleureusement pour leur rigueur scientifique, leur encadrement de qualité et la confiance qu'ils ont accordé à ces travaux de thèse. Je tiens à rappeler jusqu'à maintenant qu'ils sont de très loin mes meilleurs

III.3.8 Experimental assessments III.3.8.1 Introduction

We compare Kd-means to known methods of estimating 𝑘 from literature (X-means (Pelleg and Moore, 2000) and G-means (Foina et al., 2011, Hamerly and[START_REF] Elkan | Using the triangle inequality to accelerate k-means[END_REF]).

We show that our solution is faster than current methods while ensuring better clustering quality on massive data. The datasets used are various (synthetic and real).

We also show its efficiency through a use case on a hyperspectral image. Moreover, we give recommendations on the values that the parameters of our solution could take (the minimum size of an internal node ψ and limit 𝑡ℎ_𝑒𝑣𝑜 of Equation III.20).

III.3.8.2 Experimental protocol

Our solution and the compared algorithms were implemented in python 3.6. Moreover, k-means++ [START_REF] Arthur | k-means++: the advantages of careful seeding[END_REF] is used for initializing the centroids before applying Elkan algorithm.

Different values are assigned to parameters 𝑘,𝑑, 𝑛, 𝑡ℎ_𝑒𝑣𝑜 and ψ to study the sensitivity of our algorithm to these parameters. All combinations of the values of these parameters have been tested: 05, 0.10, 0.15, 0.20, 0.25, 0.30] • ψ ∈ [4,8,10,12] The parameter 𝑘 represents the actual number of clusters in the dataset. The above-mentioned values of 𝑘, 𝑑 and 𝑛 are valid only for synthetic datasets. These three parameters are used to generate synthetic datasets. For the real data sets, the values of these parameters are in table III.8.

An experiment is structured as follows:

• first of all, then all combinations of the values of the five parameters mentioned just above are defined;

• then, either the experiment si to be performed on a synthetic dataset, so this one is generated according to the above-mentioned parameters' values. If it is on a real dataset, so this one is loaded;

• finally, the estimation of 𝑘 is performed by the three algorithms.

78CHAPTER III. PARTITION-BASED CLUSTERING METHODS OPTIMIZATION

For each combination of these parameters, the experiment is conducted five times.

We set the values of 𝜖 and 𝜆 in the different criteria as follows:

• 𝜖 has been defined as 2 and 10 respectively in Criteria 1 and 4. The value 2 is the least strict while 10 is the most strict;

• in the cluster regularization algorithm, 𝜖 = 8 in the first part of the algorithm.

If there are still small clusters left, then the second part is executed. In this case 𝜖 = 4;

• in Criterion 3, 𝜆 = 0.75. As a result, Δ𝐺 must be less than 75% of Δ𝐶.

We allow our algorithm and X-means to search up to 𝑘 𝑚𝑎𝑥 = 5𝑘 centroids.

III.3.8.2.1 Synthetic data

We generated synthetic data so as to have overlapping and Gaussian clusters. These synthetic data have the following properties:

• a cluster is a set of data that follows a normal distribution. For generating this set, a semi-positive covariance matrix and an average (a vector) are generated randomly. Indeed, the covariance matrix values allow to define a cluster shape that is not isotropic (strictly spherical), and that can have different variances separately on an arbitrary basis of directions and not necessarily on those of the dimensions;

• there are at least two overlapping clusters;

• if the centroid of one cluster is in the hyperectangle of another cluster, then we consider that the maximum degree of overlap has been exceeded. So as a result at least one of the clusters concerned is replaced by a new cluster;

• clusters do not have the same number of points. The cardinalities are chosen randomly so that their sum is equal to the total number of points 𝑛 defined previously.

III.3.8.2.2 Real data

The real data comes from three known sources: Openml, UCI, and Kaggle. They are all of a numerical type. These data are used in other research projects to perform benchmarking machine learning methods [START_REF] Van Rijn | Algorithm selection on data streams[END_REF].

The values of real 𝑘, 𝑛 and 𝑑 are given in Table III.8. The data sets used are diverse, and they can be organized into several groups:

• black and white or grayscale images; clustering is applied directly to the pixels in this case. 𝐸𝑚𝑛𝑖𝑠𝑡 and 𝐹 𝑎𝑠ℎ𝑖𝑜𝑛𝑚𝑛𝑖𝑠𝑡 contain images respectfully on the first ten digits, clothing, and shoes. Each image was flattened to form a single vector.

And each vector has been assigned its corresponding class (label);

IV.9 Experimental assessments IV.9.1 Introduction

We conducted an experimental study to show the effectiveness and the robustness of DECWA compared to state-of-the-art density-based methods. It was applied to a variety of synthetic and real datasets, using different distances depending on the data.

First, an analysis comparing DECWA to other concurrent algorithms is performed.

We showed that DECWA outperforms well known state-of-the-art density-based algorithms in clustering quality.

An other study followed concerns the influence of two internal parameters of DECWA: the bandwidth (ℎ) and the k-nearest neighbors (𝑘). In this study, we compare the different strategies for estimating these two parameters while maintaining a good clustering quality.

IV.9.2 Experiment protocol IV.9.2.1 Algorithms DECWA was compared to DBCLASD [START_REF] Xu | A distribution-based clustering algorithm for mining in large spatial databases[END_REF], DENCLUE [START_REF] Hinneburg | Denclue 2.0: Fast clustering based on kernel density estimation[END_REF] and HDBSCAN [START_REF] Campello | Density-based clustering based on hierarchical density estimates[END_REF]. For the experiments conducted in this chapter, DECWA used the Gaussian kernel in the division phase. Algorithm parameter values are defined through the repetitive application of the random search approach (1000 iterations). This, in order to obtain the best score that the four algorithms can have. DBCLASD (parameter-free and incremental) was subject to the same approach but by randomizing the order of the data points because it is sensitive to it. The hierarchical structure proposed by HDBSCAN is exploited by the Excess Of Mass (EOM) method to extract clusters, as used by the authors in [START_REF] Campello | Density-based clustering based on hierarchical density estimates[END_REF].

Clustering quality is measured by the commonly used metric named Adjusted Rand Index (𝐴𝑅𝐼) [START_REF] Hubert | Comparing partitions[END_REF]. In addition, we also report the ratio of outliers produced by each algorithm for each dataset.

IV.9.2.2 DECWA environement

Several algorithms (e.g. Kruskal [START_REF]On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem[END_REF], Boruvka [START_REF] Nešetřil | Otakar borůvka on minimum spanning tree problem translation of both the 1926 papers[END_REF], Prim [START_REF] Prim | Shortest connection networks and some generalizations[END_REF]) exist to generate an MST. DECWA uses Kruskal algorithm to build the MST, it has a complexity of 𝑂(|𝐸|𝑙𝑜𝑔(|𝐸|)) with |𝐸| the cardinal of edges. Kruskal is faster than Boruvka and Prim in sparse graphs (few edges) while Prim and Boruvka take less time than 𝐾𝑟𝑢𝑠𝑘𝑎𝑙 in dense graphs [START_REF] Kershenbaum | Computing minimum spanning trees efficiently[END_REF].

As 𝐺 is a 𝑘-nearest neighbor graph, it is often sparse because of the small value of 𝑘 which is studied in sub-section IV.9.5. distance search (PDS) approximates a distance value between two points using only a subset of dimensions to assert a given hypothesis is true. It is applicable for large spaces and also when actual distance values are not required. The reduced distance and PDS strategies are not suitable for classification methods requiring precise distances. However, they are suitable for nearer neighbor calculations, usually requiring only sorting the points. The fourth strategy, dimensionality reduction, does not implicitly accelerate the execution time but it could contribute to it indirectly. The strategy produces another subset of dimensions from the original dimensional space. This new space is then consumed by a classification method. Although this space reduction could lead to an acceleration of runtime, the classification quality could be poorer or even worse if there was too much loss of useful information during the reduction.

.1.2 Compare-means

We complete the section on versions of k-means based on geometric reasoning and particularly Compare-means (II.4.1.5.1).

Let 𝑥 𝑖 , 𝐺 𝑎 , 𝐺 𝑏 ∈ 𝑅 𝑑 , 𝑥 𝑖 a point, 𝐺 𝑏 the actual centroid of 𝑥 𝑖 and 𝐺 𝑎 another centroid.

In the following, we prove that Compare-means assertion based the inequation 3 is true. Indeed, the assertion states that if this inequation is validated, then 𝐺 𝑎 cannot be closer to 𝑥 𝑖 than 𝐺 𝑏 . Therefore, there is no need to calculate the distance between 𝑥 𝑖 and 𝐺 𝑎 . To prove the veracity of the assertion , the following triangular inequality is used: