<figure><img src="image_1.png" /></figure>

HAL
open science

# Incremental clustering based on Wasserstein distance between histogram models

Xiaotong Qian, Guénaël Cabanes, Parisa Rastin, Mohamed Alae Guidani, Ghassen Marrakchi, Marianne Clausel, Nistor Grozavu

► To cite this version:

Xiaotong Qian, Guénaël Cabanes, Parisa Rastin, Mohamed Alae Guidani, Ghassen Marrakchi, et al. Incremental clustering based on Wasserstein distance between histogram models. Pattern Recognition, 2025, 162, pp.111414. 10.1016/j.patcog.2025.111414. hal-04941963

HAL Id: hal-04941963

https://hal.science/hal-04941963v1

Submitted on 12 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

# Incremental clustering based on Wasserstein distance between histogram models☆

Xiaotong Qian<sup>a, b, ∗</sup>, Guénaël Cabanes<sup>b, c</sup>, Parisa Rastin<sup>b</sup>, Mohamed Alae Guidani<sup>c</sup>, Ghassen Marrakchi<sup>d, c</sup>, Marianne Clausel<sup>b</sup>, Nistor Grozavu<sup>a, c</sup>

## ARTICLE INFO

### Keywords:

- Unsupervised learning

- Static and dynamic clustering

- Large datasets

- Data streams

- Sliding windows

- Histogram models

- Wasserstein distance

## ABSTRACT

In this article, we present an innovative clustering framework designed for large datasets and real-time data streams which uses a sliding window and histogram model to address the challenge of memory congestion while reducing computational complexity and improving cluster quality for both static and dynamic clustering. The framework provides a simple way to characterize the probability distribution of cluster distributions through histogram models, regardless of their distribution type. This advantage allows for efficient use with various conventional clustering algorithms. To facilitate effective clustering across windows, we use a statistical measure that allows the comparison and merging of different clusters based on the calculation of the Wasserstein distance between histograms.

## 1. Introduction

Machine learning is a prominent field of research that focuses on learning patterns and relationships within datasets to make intelligent predictions or analyzes. It includes two main types of algorithms: supervised learning and unsupervised learning. They are often referred to as classification and clustering [1], respectively. Although both aim to separate and group objects, there is a fundamental difference between them. In classification, the categories are predetermined and objects are assigned to a specific category (called a label). The labels are therefore necessary to train a classification model. In clustering, on the other hand, labels are not needed to train a clustering model; the goal is to group similar objects based on some definition of distance or similarity. Depending on how the data are processed, clustering analysis can be divided into two forms: conventional clustering and data stream clustering.

Conventional clustering algorithms [2] focus more on static datasets that are fixed and remain the same throughout training. With the rapidly increasing volume of data collection, clustering approaches capable of handling large and high-dimensional data have become a popular topic. In [2], the authors present clustering components and

detail key concepts related to clustering algorithms, new variants, similarity/dissimilarity measures, optimization challenges, validation, and data types. Although there are subtle differences in categorizing clustering algorithms, several broad categories are popular: hierarchical, partition, graph, density, model and grid-based clustering. Hierarchical-based clustering iteratively divides the dataset into subsets from top to bottom, or merges individual objects from bottom to top, forming a dendrogram by grouping data objects into a tree of clusters; popular examples of this type include BIRCH [3] and Agglomerative clustering [4]. Partition-based clustering aims to separate objects into K groups by optimizing some criterion such as minimizing the total intra-cluster distance; K-means [5] and ORCLUS [6] are typical examples. Graph-based clustering, such as Spectral clustering [7], uses the concept of graphs to represent data points and their relationships and involves the task of dividing nodes into clusters. Density-based clustering, such as DBSCAN [8], relies on notions of density within “neighborhoods” to determine clusters, growing a cluster as long as the density in the neighborhood exceeds some threshold. Model-based clustering assumes models for clusters and tries to best fit the data to the assumed model, for example, Gaussian Mixture [9] assumes that data points are derived from a combination of Gaussian distributions with different parameters.

<footnote><sup>a</sup> ETIS, UMR 8051, CY Cergy Paris Université, Cergy, 95000, France</footnote>

<footnote><sup>b</sup> LORIA, UMR 7503, Université de lorraine, Vandoeuvre-lès-Nancy, 54500, France</footnote>

<footnote><sup>c</sup> École nationale supérieure des mines de Nancy, Campus Artem, Nancy, 54042, France</footnote>

<footnote><sup>d</sup> LIPN, UMR 7030, Université Sorbonne Paris Nord, Villetaneuse, 93430, France</footnote>

<footnote>☆ This work was funded through the ANR project Pro-TEXT (project N° ANR-18-CE23-0024-01). More details are available at: https://pro-text.huma-num.fr/le-projet/.</footnote>

<footnote>\* Corresponding author.</footnote>

<footnote>E-mail address: xiaotong.qian@ensea.fr (X. Qian).</footnote>
Finally, grid-based clustering divides the data space into multiple cells to form a grid structure and obtains clusters based on cells within the same grid; algorithm such as CLIQUE [10] is a representation of this type. These clustering algorithms provide valuable insights and form the basis for data analysis in various fields. In addition, several clustering algorithms could be classified into multiple categories, for instance KASP [11], which is considered as a member of the large-scale clustering algorithms because it uses a sampling approach to deal with very large datasets. It works by applying K-means to identify subsets of the datasets and then performing Spectral clustering on those subsets; or like HDBSCAN [12] which uses a hierarchical approach to identify clusters after determining relationships between objects based on density.

Data stream clustering [13] differs from conventional clustering. It operates on continuous data streams, eliminating the need to wait for the entire dataset to be collected. This real-time nature allows it to dynamically process incoming data points and adapt the clustering models to any changes in the data distribution over time. Many data stream clustering approaches can be considered extensions or variations of conventional clustering, resulting in different categories within the field. The first proposed data stream clustering STREAM [14] is of the partition-based type. This algorithm reads a data stream over fixed size batches or windows, applies KMedian clustering to each batch, and merges the obtained centers into K medians to find final clusters. A few years later, the authors proposed an improved version, STREAMLSEARCH [15], by adding local search techniques. Other algorithms such as StreamK-means [15], and SequentialK-means [16] are also representations of the partition-based type. CluStream [17], a well-known hierarchical and partition-based approach, extends the clustering feature tree (CF-tree) structure of BIRCH. By using an online-offline algorithm with K-means, it effectively summarizes micro-clusters and preserves them at specific points in time within a pyramidal time frame. In addition, density-based approaches have been proposed, such as DenStream [18], which is based on the DBSCAN algorithm with the addition of a CF-tree structure, DBStream [19], which uses a shared density graph to connect micro-clusters, eliminating gaps in dense areas during online clustering refinement. These types of algorithms have the ability to detect clusters of any shape without prior knowledge of the number of clusters, and are able to deal with outliers. Apart from these, there are other types of data stream clustering, including grid-based approach such as DGClust [20], as well as model-based algorithm SWEM [21].

A wide variety of clustering algorithms exist for both static and dynamic datasets. However, no clustering algorithm is universally perfect; each type of clustering algorithm has its advantages and disadvantages. For example, partition-based algorithms have limitations: they require the number of clusters to be specified in advance and struggle with outliers, but they work efficiently and can handle large datasets with relatively low time complexity. Meanwhile, density-based clustering algorithms work on any kind of cluster distribution, automatically detect the number of clusters, and handle outliers very well, but are slower and more difficult to parameterize. Consequently, clustering algorithms can be applied in different domains and the applicability of different clustering approaches depends strongly on the context of the specific problem to solve. The application or choice of different algorithms is therefore highly dependent on the specific requirements or needs of the task. In this article, we present a fast, innovative clustering framework that is able to adapt most clustering approaches to both static and dynamic datasets. The proposed framework operates on sliding windows and uses histogram models to characterize clustering distributions. Histogram models provide simple representations of clusters without requiring prior knowledge of their distribution. To compare and merge different clusters in different windows, we take advantage of the calculation of the Wasserstein distance between histograms [22], facilitating effective cluster analysis and synthesis. A

major advantage of the proposed framework is that it allows fast application of most clustering algorithms, minimizing computational cost and memory consumption without using resource-intensive techniques such as distributed/parallel processing or GPU computing. The work presented in this paper fits into the context of frugal clustering [23], which is particularly relevant in resource-constrained environments where traditional clustering algorithms may not be feasible or efficient.

The paper is organized as follows. In Section 2, we provide an overview of the theoretical background, including the construction of the histogram models, the computation of the similarities between distributions using Wasserstein distance. In Section 3, we delve into the details of the approach, outlining the process of modeling clusters as histograms and the subsequent merging of different windows. In Section 4, we conduct experiments to compare the static and dynamic approaches to conventional clustering and data stream clustering on both artificial and real datasets. Finally, in Section 5, we summarize the results and discuss potential perspectives for future research.

## 2. Background

In this section, we present the theoretical background on which our approach is based, aiming at efficiently comparing cluster distributions with minimal computational cost to determine if clusters should remain separate or be merged. For this purpose, representing the distribution of each cluster as a set of histograms, and then compare these distributions using Wasserstein distance adapted to this representation can be an efficient solution. Finally, a specific two-sample test is computed from this measure to assess the significance of the distance obtained.

### 2.1. Data distributions using histograms

Estimating probabilistic data distributions [24] is a fundamental part of data science and machine learning, especially in unsupervised learning. Unraveling the distribution of data allows the discovery of hidden patterns in datasets and is a powerful tool for analyzing large amounts of data in an unsupervised manner. In clustering applications, clusters are often assumed to be normally distributed (i.e., have a multivariate Gaussian distribution) or sometimes have a more complex distribution, such as gamma distributions. All subsequent analysis is then based on this assumption. These parametric approaches can provide good results, but they have limited applications when it comes to representing clusters of arbitrary distributions, which is an important requirement for many real-world scenarios. One possible solution is to model the distribution as a mixture of simple functions (usually Gaussian). However, Gaussian mixture models can be computationally expensive and slow to train, especially when the number of mixture components is large. They are also sensitive to initialization, and choosing the number of mixture components in the model is often challenging. Another solution, which we focus on in this paper, is to model the cluster distributions using a set of histograms computed from the empirical distribution [25] of the data. Although this representation can lead to a loss of fine variations of the underlying distribution depending on the number of bins, it has the advantage of being independent of any assumptions and is fast and easy to compute. It also greatly simplifies the computation of the Wasserstein distance [26].

The term histogram was first proposed by [27], who described a histogram as a series of rectangles of equal width whose height could represent the number of values falling within the interval formed by their two edges. Using histograms to represent data could be a concise and flexible case of symbolic or summarized data analysis when faced with large amounts of data. In this case, the weight of each rectangle of the histogram is no longer the number of observations, but the probability or proportion of values over a set of intervals, formally defined that a histogram is a model for representing the empirical distribution of a continuous variable *Y* divided into a set of contiguous *I*<sub>Φ</sub> intervals (bins) with associated π<sub>Φ</sub> weights. A histogram *H* is thus
<figure><img src="image_5.png" /><figcaption>Fig. 1. Two types of histogram representations which display a Gaussian distribution $N(\mu, \sigma^2)$ where $\mu$ is 0 and $\sigma$ is 0.01.</figcaption></figure>

represented by a set of $\Phi$ ordered pairs $(I_{\phi}, \pi_{\phi})$, where $\pi_{\phi}$ is a non-negative measure of a probability distribution on the domain of $Y$ such that: (1) $\sum_{\phi=1}^{\Phi} \pi_{\phi} = 1$ with $\pi_{\phi} \ge 0$; (2) $I_{\phi} \cap I_{\phi'} = \emptyset, \phi \ne \phi'$; (3) $\bigcup_{\phi=1,...,\Phi} I_{\phi} = [Y_{min}, Y_{max}]$.

There are two ways of displaying histograms. The first type allows each bin to have a fixed uniform length, but not a uniform weight, expressed as: $|I_{\phi}| = \frac{Y_{max} - Y_{min}}{H}$. The second type allows each bin to have a fixed uniform weight, but not a uniform length, expressed as: $|\pi_{\phi}| = \frac{1}{H}$. Fig. 1 illustrates the difference.

The time complexity of computing a univariate histogram depends on the number of bins $\Phi$ in the histogram and the number of data points $n$ being processed which is $O(n * \Phi)$, where $\Phi$ is usually much smaller than $n$ and need not be proportional to $n$. However, computing a multivariate histogram is much more expensive because the number of bins $\Phi$ in each dimension should be considered, with a time complexity of $O(n * \Phi^v)$, where $v$ is the dimensionality of the dataset. One way to reduce the computational cost of multivariate histograms is to compute separate independent histogram for each variable, which reduces the complexity to $O(n * v * \Phi)$, but correlation information is lost in this approach. If some attributes are correlated, we cannot treat their histogram representation independently. For these reasons, in this paper we focus on independent histograms and deal with the loss of correlation information by using random projections which will be presented in Section 3.1.

## 2.2. Distribution comparison

To increase storage efficiency and achieve more consistent clustering results, it is imperative to compare the distributions of different clusters once they have been identified. Then, clusters with similar distributions should be merged to achieve better clustering results. However, comparing different distributions can be challenging and requires a suitable metric to assess the similarity between two distributions $\mu$ and $v$ on the same sample space $\mathcal{X}$. A widely used measure is the Kullback-Leibler divergence (KL divergence expressed in Eq. (1)) [28], which computes the expectation of the logarithmic difference between the probability distributions $\mu$ and $v$:

$$KL(\mu, v) = \int_{\mathcal{X}} \mu(x) \log\left(\frac{\mu(x)}{v(x)}\right) dx. \qquad (1)$$

Since the KL divergence is not symmetric, the Jensen-Shannon divergence (JS divergence expressed in Eq. (2)) [29] has been proposed to solve the symmetry problem, known as the total divergence to the average, the square root of the JS divergence is a metric often referred to as the JS distance.

$$JS(\mu, v) = \frac{KL(\mu, \frac{\mu+v}{2}) + KL(v, \frac{\mu+v}{2})}{2} \qquad (2)$$

The KL and JS divergences suffer from several drawbacks, as non robustness to outliers. In addition, KL and JS are not distances and they do not satisfy triangle inequality. For all these reasons, another metric, the so called Wasserstein distance has gained in popularity.

Wasserstein distance takes into account the cost of moving the mass from one distribution to another, which helps to mitigate the impact of outliers. The Wasserstein distance is also a continuous function, meaning that small changes in the input distributions result in small changes in the distance measurement. This is not the case with KL divergence, which can exhibit discontinuities and is therefore less suitable for some applications. In addition, Wasserstein distance satisfies the properties of a metric, such as symmetry, triangle inequality, and non-negativity. This property is not satisfied by JS and KL distances, making Wasserstein distance more suitable for use in optimization and clustering algorithms. Finally, Wasserstein distance has a natural interpretation as the minimum cost of transforming one distribution to another, which makes it easier to understand and explain in comparison to other distance measures.

Originally introduced in the context of optimal transport theory [30], this metric quantifies the minimum cost required to transform one probability distribution into another, where cost is defined as the amount of “work” required to move a given amount of mass from one point to another. The traditional approach to estimating the Wasserstein distance is outlined in [31] with a computational complexity of $O(n^3 \log(n))$ using the EMD definition of this distance.

$$W_{\text{emd}}(\mu, v) = \min_{\gamma \in \mathcal{P}} \int \|x - y\| \gamma(x, y) dxdy = \mathbf{E}_{(x,y) \sim \gamma} [\|x - y\|] \qquad (3)$$

where $\mathcal{P}$ is the set of all joint distributions $\Pi(\mu, v)$ whose marginals are $\mu$ and $v$, $\|x - y\|$ gives the cost of transporting a unit of mass from point $x$ to point $y$. A transport plan to move $\mu$ to $v$ can be described by a function $\gamma(x, y)$ which gives the amount of mass to be moved from $x$ to $y$.

The Sinkhorn distance [32] is a faster alternative to Wasserstein distance that uses an entropy regularization term into the optimal transport problem, making the problem more computationally efficient to solve with computational complexity up to $O(n^2)$. Given a cost matrix $M$, the cost of mapping $\mu$ to $v$ using the joint probability $\mathcal{P}$ can be qualified as $\langle P, M \rangle$, and the Sinkhorn distance directly regularizes the original transport problem with a regularization parameter $\lambda$ and the entropy $h(\mathcal{P}) = - \sum_{i,j=1} P_{i,j} \log P_{i,j}$ defined as follow:

$$\lambda > 0, W_{\text{sinkorn}}^{\lambda}(\mu, v) := \langle P^{\lambda}, M \rangle, P^{\lambda} = \operatorname*{argmin}\langle P, M \rangle - \frac{1}{\lambda}h(P) \qquad (4)$$

Computation of the Wasserstein distance (including Sinkhorn distance) can become exceedingly complex for large datasets, making it necessary to explore alternative methods. One such approach, which is specifically designed for histograms, can be found in [22]. This approach introduces an elegant formulation of the Wasserstein distance between two histograms $H^1$ and $H^1$ expressed as:

$$W_{\text{hist}}^{2}(H^{1}, H^{1}) = \sum_{\phi=1}^{\Phi} \pi_{\phi} d^{2}(I_{\phi}^{1}, I_{\phi}^{1}) = \sum_{\phi=1}^{\Phi} \pi_{\phi} \left[ (c_{\phi}^{i} - c_{\phi}^{j})^{2} + \frac{1}{3}(r_{\phi}^{i} - r_{\phi}^{j})^{2} \right], \quad (5)$$

which simply compute the sum of the differences between each pair of centers $C$ and radius $R$ of two histograms, where $\pi_{\phi}$ is the probability weight associated to each bin, and $I_{\phi}^{i}$ represents an interval $(I_{\phi}^{i}, \overline{I_{\phi}^{i}})$
of histogram $H^i$, $I_{\phi}^j$ represents an interval ($[\overline{y_{\phi}^j}, \overline{y_{\phi}^j}]$) of histogram $H^j$, with:

$$c_{\phi}^{i} = \frac{y_{\phi}^{j} + \overline{y_{\phi}^{j}}}{2}; \quad c_{\phi}^{j} = \frac{y_{\phi}^{j} + \overline{y_{\phi}^{j}}}{2}; \quad r_{\phi}^{i} = \frac{y_{\phi}^{j} - \overline{y_{\phi}^{j}}}{2}; \quad r_{\phi}^{j} = \frac{y_{\phi}^{j} - \overline{y_{\phi}^{j}}}{2}.$$

They also propose a way to compute the Wasserstein distance between multivariate histograms. Suppose there are p histogram variables for observation i and j ($H_1^i, \dots, H_1^p$ and $H_1^j, \dots, H_1^p$), under the hypothesis that the variables are independent, the process is expressed like:

$$W_{hist}^2[(H_1^i, \dots, H_p^i), (H_1^j, \dots, H_p^j)] = \sum_{q=1}^{p} W_{hist}^2(H_q^i, H_q^j) \quad (6)$$

The proposed approach described in this paper is to compute histograms that model the data distribution before computing the distance between the centers and the radius of each interval. The time complexity of computing the Wasserstein distance between histograms is $O(\Phi^v)$ for multivariate histograms and $O(\Phi * v)$ for independent histograms. Overall, since $\Phi$ is usually chosen as a constant positive parameter, the total time complexity of this approach for a set of $v$ independent histograms can be efficient compared to the complexity of multivariate histograms. Moreover, the time complexity of an algorithm also depends on its implementation and hardware. For example, parallelization can greatly reduce the complexity of independent histograms.

It is possible to compute the barycenter of a set of histograms by defining a distance measure between histograms. This barycenter is essentially a single histogram that minimizes the squared Wasserstein distance between itself and each member of the set. In other words, it is the optimal representative histogram that captures the essential features of the entire set. In the case of histograms with uniform bins weight, each one is described by the centers $C$ and radius $R$ of its bins, this involves computing new centers $C^b$ and radius $R^b$ while keeping the weight of each bin constant. The Eq. (7), mentioned in [22], shows that this simply requires computing the mean center and radius of each bin, where $N_h$ is the number of histograms in the set, in our case $N_h$ is set to 2:

$$C^b = N_h^{-1} \sum_{j=1}^{N_h} C^j \text{ and } R^b = N_h^{-1} \sum_{j=1}^{N_h} R^j. \quad (7)$$

## 2.3. Wasserstein two-samples testing

Performing non parametric two sample testing allows to detect, given samples $X_1, \dots, X_n \sim \mu$ and $Y_1, \dots, Y_m \sim \nu$ from the two unknown distributions $\mu$ and $\nu$, if they are significantly different. One classical test is the Kolmogorov-Smirnov test (see [33]), or K-S test, which is commonly used to compare an empirical distribution to a theoretical distribution or to compare two empirical distributions. In the case of deciding whether two one-dimensional probability distributions $(\mu, \nu)$ differ from each other by computing Eq. (8):

$$D_{\mu,\nu} = \sup_x |F_{\mu}(x) - F_{\nu}(x)| \quad (8)$$

and test the null hypothesis $(H_0): \mu = \nu$ versus $(H_1): \mu \neq \nu$. One then rejects the null hypothesis $(H_0)$ and accepts $(H_1)$ with significance level $\alpha$ if

$$D_{\mu,\nu} > C(\alpha) \sqrt{\frac{n+m}{n \cdot m}}, \text{ where } C(\alpha) = \sqrt{-\ln(\alpha/2)} \times \frac{1}{2}.$$

An alternative distribution free statistical test based on the Wasserstein distance has been proposed in [34]. This test is based on the following preliminary result on the asymptotic empirical Wasserstein distance between two samples. Denote $F_n, G_m$, the two empirical cumulative distribution functions (CDF) associated to the samples $X_1, \dots, X_n \sim \mu$ and $Y_1, \dots, Y_m \sim \nu$. Under the null hypothesis $H_0: \mu = \nu$, one has

$$T_{m,n} := \frac{n \cdot m}{n+m} \int_{0}^{1} \left( G_m \left( F_n^{-1}(t) - t \right)^2 \right) dt \to_w Z$$

$$:= \int_{0}^{1} \mathbf{B}(t)^2 dt \text{ as } n, m \to \infty \quad (9)$$

where $B(t)$ represents the Brownian bridge [35]. The Brownian bridge is defined as $B(t) = W_{pr}(t) - \frac{t}{T} W_{pr}(T)$, where $t \in [0, T]$ (in the assumption $T=1$) and $W_{pr}$ is a standard Wiener process [36]. It describes a random walk from 0 to $T$ starting at 0 and ending at 0, such as $W_{pr}(0) = W_{pr}(T) = 0$. We emphasize that on can simulate the Brownian Bridge and then compute empirically the quantiles of the random variable $Z$. Using the test statistic $T_{m,n}$, we then rejects $H_0$ and accepts $H_1$ if $T_{m,n} > z_{\alpha}$ where $z_{\alpha}$ is the $\alpha$-quantile of distribution $Z$. In short, instead of testing the vanishing of Wasserstein distance between $G_m$ and $F_n$ directly, this test computes the Wasserstein distance between $G_m(F_n^{-1})$ and a uniform distribution $U_{[0,1]}$ on $[0, 1]$ which makes it distribution free.

## 3. Proposed approach

The proposed approach uses a non-overlapping sliding window model to run a clustering algorithm on batches of data samples that are briefly held in memory. Then allowing any type of clustering algorithms to be applied across sliding windows. This flexibility is a key strength of our approach, allowing the selection of the most appropriate clustering method for the data at hand. The ability to remove noise using algorithms such as those in the DBSCAN family is particularly valuable in this context, as histograms can be sensitive to extreme values and outliers. However, our approach has shown excellent overall performance in tests with other types of clustering algorithms (see Section 4). This allows incremental clustering of large datasets and handling of data streams. The distribution of each cluster in a window is modeled as a set of unidimensional histograms computed in a random projection space, capturing correlation information between variables without the need to compute a costly multivariate histogram.

As shown in Fig. 2, input data points are continuously collected within a sliding window. A conventional clustering algorithm is then applied to identify clusters within the current window. Random projections of these data points are then computed (see Section 3.1), and the distributions of the detected clusters is modeled using a histogram plot applied on each of the projection axes (see Section 3.2). To compare the newly computed clusters with those from previous windows, we use the Wasserstein two-sample test based on the Wasserstein distance, a statistical test that aims to identify clusters with similar distributions (see Section 3.3). These similar clusters are merged and replaced by their barycentric histograms using a modified calculation form (see Section 3.4). Once this process is complete, the histogram models are stored and the data samples are discarded to leave space for a new window of data samples in memory. The main steps of the approach are also summarized in the Algorithm 2 (see Section 3.5).

### 3.1. Multivariate histogram extension

Multivariate histogram models to represent the data distribution can be very computationally costly when the number of dimensions is high. Instead of using a multivariate histogram, the distribution can be modeled as a set of univariate histograms at very low computational cost, but all correlation information is lost. One solution inspired by Sliced Wasserstein distance proposed in [37] is to compute random projections of the data onto new axes drawn uniformly on the unit sphere. If the number of new axes is large enough, the resulting model of the distribution is very close to the multivariate model in terms of computing the Wasserstein distance, while reducing the computational complexity very significantly. The axes of the projections of the data points are obtained via the dot product between the sample vectors $X$ and $M_p$, the intermediate matrix $M_p$ is expressed in Eq. (10) as follows:

$$M_p = \frac{M_{\psi}^2}{[\sqrt{\sum_{i=1}^{v} (\psi_i^1)^2}, \dots, \sqrt{\sum_{i=1}^{v} (\psi_i^p)^2}]}, \quad X^p = X \cdot M_p \quad (10)$$
<figure><img src="image_6.png" /><figcaption>Fig. 2. Proposed approach.</figcaption></figure>

where $M_\psi$ is a matrix which follows a standard normal distribution with shape $(\nu, p)$, $\nu$ is the number of variables, and $p$ is the number of projections, and $\psi_i^j \in M_\psi$.

## 3.2. Histograms computation

As mentioned in Section 2.1, we favor a fixed weight representation for the histograms, which greatly simplifies the computation of the Wasserstein distance introduced in Eq. (5), Eq. (6). In the proposed approach, each cluster is represented by a set of independent histograms. For this purpose, the samples of a cluster $X_c^p$ obtained in the previous step must be divided into $\Phi$ intervals by computing the 1 to $\Phi$-th quantile of $X_c^p$ along each dimension, keeping the same weight $\pi_\phi$ for each interval, which is equal to $\frac{1}{\Phi}$. This process is repeated for all clusters in the current window.

## 3.3. Cluster similarity test

With respect to Eq. (9), the detailed procedures for defining the similarity between two cluster distributions in the form of histograms are as follows:

1. Determine the Brownian bridge threshold $\delta$ corresponding to the dimension $p$ using linear regression.

2. Obtain the CDF $F_n$ and $G_m$ for each pairwise histogram distribution $\mu$ and $\nu$ of two clusters.

3. Compute the composition function of $G_m$ and the inverse function $F_n^{-1}$ of $F_n$: $G_m(F_n^{-1})$.

4. Compute the sum of WD between each $G_m(F_n^{-1})$ and $U_{[0,1]}$ by using Eq. (6), then multiply with $\frac{n*m}{n+m}$.

5. Compare result of step 4 with the threshold $\delta$.

6. If the result $< \delta$, it means two clusters are similar and must be merged.

To define the threshold $\delta$, we used simulations of Brownian bridges for multivariate observations. Since the threshold $\delta$ corresponds to a Wasserstein distance between a random Brownian bridge and the

uniform walk $B_t = 0$ with a probability of occurrence below 5%. The algorithm which computes the threshold $\delta$ corresponds to $p$ variables could be developed as described in Algorithm 1.

Experiments show that the threshold $\delta$ has a linear relationship with the number of dimensions $p$. Therefore, instead of repeating the process of Algorithm 1, a simple linear regression model trained by $\delta_1$ and $\delta_2$ could be applied to any dimension $p$, allowing a fast computation of $\delta_p$. Incidentally, the values of $M$ and $N$ do not matter much for the definition of the threshold; to maintain consistency, it is enough to keep them constant for the computation of $\delta_1$ and $\delta_2$. Precisely, we set them both to 10000.

<caption>**Algorithm 1:** Computation of threshold $\delta$ corresponding to $p$ dimensions</caption>

Input: $p, M, N$
Output: $\delta_p$
1 for $i$ in $1,...,p$ do
| /* Create $M$ synthetic Brownian Bridges, each one includes $N$ 1d points, i.e. a randomly normal increase/decrease at each time step */
2 B[i] ← Create_Brownian_Bridge(M, N);
3 MeanB[i] ← mean(B[i]², axis=1); /* Mean of $B[i]²$ by columns */
4 Sum_MeanB ← Sum_MeanB(MeanB, axis=0); /* Sum of MeanB by rows */
| /* Extract (95%×M)-th element of sorted Sum_MeanB as threshold */
5 $\delta_p$ ← sort(Sum_MeanB)[M*0.95];
}

## 3.4. Merging process

Once similar clusters found, merging them by computing their barycenter in order to reduce the complexity of time and space. Since some clusters may have similar distributions but large differences in
<table><caption>**Table 1**
Datasets summary.</caption><thead><tr><th>Real datasets</th><th>Nb samples</th><th>Nb dimensions</th><th>Nb clusters</th></tr></thead><tbody><tr><td>Outdoor</td><td>3501</td><td>21</td><td>40</td></tr><tr><td>Gassenor</td><td>13 377</td><td>128</td><td>6</td></tr><tr><td>IGBN</td><td>24 150</td><td>33</td><td>6</td></tr><tr><td>IABN</td><td>52 848</td><td>33</td><td>6</td></tr><tr><td>Rialto</td><td>82 250</td><td>27</td><td>10</td></tr><tr><td>IIAIN</td><td>452 044</td><td>33</td><td>6</td></tr><tr><td>IIRIN</td><td>452 044</td><td>33</td><td>6</td></tr><tr><td>Covtype</td><td>549 829</td><td>10</td><td>7</td></tr></tbody></table>

the number of data, the barycenter distributions must be computed as a weighted sum of the mean centers and radius by modifying Eq. (7):

$$C^b = \frac{\sum_{j=1}^{N_h} n_j * C^j}{\sum_{j=1}^{N_h} n_j}; \quad R^b = \frac{\sum_{j=1}^{N_h} n_j * R^j}{\sum_{j=1}^{N_h} n_j} \qquad (11)$$

Finally, the process of cluster detection and subsequent merging within a current window is achieved. By repeating this process for each window, it is possible to efficiently handle large datasets and data streams.

### 3.5. Detailed algorithm

The proposed framework can be summarized as follows: First, a clustering algorithm Clus($\theta$, X[nb\_w]) with parameters $\theta$ is applied to data points X[nb\_w] temporarily stored in memory within the nb\_w-th time window, and the resulting clusters are stored as X_c[nb\_w]. The sliding window ensures incremental data collection both for large datasets and data streams. Random projections are then performed to map the data into a p-dimensional space, stored as X_c^p[nb\_w]. Next, the clusters are modeled as empirical distributions in the form of a set of 1-D histograms, notated as H_c^p[nb\_w], applied on each random projection axis. The set of 1-D histograms on random projections approximates the full multidimensional histogram with reduced memory and computational cost. These histograms allow the representation of clusters in arbitrary shapes, which is critical for applying the framework to various clustering algorithms. Data points in the current window are then discarded to save memory. Finally, the computed cluster distributions update the overall data stream model $\Theta$ by adding new distributions and merging similar ones, as discussed in Sections 3.3 and 3.4 using the Wasserstein distance metric. The detailed process is shown in the algorithm 2.

## 4. Experimental protocol and results

### 4.1. Datasets

To evaluate the proposed approach, we performed a series of experiments on different datasets, including real datasets and artificial datasets, with a variety of number of samples, dimensions and clusters (.). Detection of clusters in arbitrary shapes plays an important role in the proposed approach, besides real popular datasets used in recent research, artificial datasets with different cluster distributions are necessarily generated. Right after the creation and collection of real and artificial datasets, two ways of dataset preprocessing are followed. This allows clustering in both static and dynamic contexts, demonstrating the flexibility of the proposed approach.

#### 4.1.1. Artificial datasets

Generate several artificial databases in different distributions to simulate real scenarios, such as comet, meteorite, square, moon, circular, and Gaussian, by adding orientation to some clusters to replicate the real case. For the square distribution, the first dimension follows a univariate Gaussian distribution, then the remaining dimensions follow a uniform distribution. Then comes the comet distribution, where

<table><thead><tr><th>Artificial datasets</th><th>Nb samples</th><th>Nb dimensions</th><th>Nb clusters</th></tr></thead><tbody><tr><td>Comet</td><td>3,20(*10<sup>4</sup>)</td><td>50,100</td><td>15,50</td></tr><tr><td>Meteorite</td><td>3,20(*10<sup>4</sup>)</td><td>50,100</td><td>15,50</td></tr><tr><td>Square</td><td>3,20(*10<sup>4</sup>)</td><td>50,100</td><td>15,50</td></tr><tr><td>Gaussian</td><td>3,20(*10<sup>4</sup>)</td><td>50,100</td><td>15,50</td></tr><tr><td>Moon</td><td>3,20(*10<sup>4</sup>)</td><td>50,100</td><td>15,50</td></tr><tr><td>Circle</td><td>3,20(*10<sup>4</sup>)</td><td>50,100</td><td>15,50</td></tr><tr><td>MixSmall</td><td>1,2,3 (*10<sup>4</sup>)</td><td>50,50,50</td><td>24,36,48</td></tr><tr><td>MixLarge</td><td>10,20,50 (*10<sup>4</sup>)</td><td>100,100,100</td><td>54,66,90</td></tr></tbody></table>

**Algorithm 2: Proposed approach**

**Input:** Number of projections $p$, number of bins $\Phi$, data points arriving by windows $X = \{X[1], X[2], \dots\}$, conventional clustering algorithm with $\theta$ parameters Clus($\theta$), similarity threshold $\delta_p$ computed by Algorithm 1, stored clusters in current model $\Theta$

**Output:** Updated clusters $\Theta$

1. nb\_w ← Index of current window;

2. while length(X[nb\_w]) != 0 do

3. X_c[nb\_w] ← Clus($\theta$, X[nb\_w]); /* Detect clusters in the nb\_w-th window */

4. X_c^p[nb\_w] ← p Random Projections of X_c[nb\_w] by Eq. (10);

5. H_c^p[nb\_w] ← Convert all the clusters X_c^p[nb\_w] to histogram models as described in Section. 3.2;

6. for each cluster i in $\Theta$ do

7. for each cluster j in $H_c^p[nb\_w]$ do
8.   if i and j are not significantly different with respect to Eq. (9) then
9.     Update i which is stored in $\Theta$ by the barycenter of i and j using Eq. (11)
10.    else
11.      $\Theta \leftarrow \Theta.add(j)$; /* Add j to the entire set $\Theta$ */
12.    nb\_w ← nb\_w + 1;

the first dimension follows a gamma distribution, then the remaining dimensions follow a univariate distribution. Similar to the comet distribution, the meteorite distribution follows a gamma distribution for all dimensions. Another type of distribution is the circle distribution, which is based on cosine and sine elements, and the moon distribution could be treated as a semicircle distribution. Then there is the Gaussian distribution, best known as the multinomial Gaussian distribution. An example of the visualization of all artificial distributions could be seen in Fig. 3

#### 4.1.2. Real datasets

The real datasets used in the experimental sections have already mentioned in including Outdoor which consists of 4000 images of 40 different objects taken with a smartphone camera in a garden environment. The images were taken under different lighting conditions and from different distances and positions; Gassor [38] contains 13910 recordings from 16 chemical sensors measuring six pure gases (ammonia, acetaldehyde, acetone, ethylene, ethanol and toluene) in a gas delivery platform at the University of California, San Diego; Rialto [39] contains 82,250 examples of ten colorful buildings near the Rialto Bridge in Venice; Covtype [40] contains 581012 instances with 54 attributes related to forest cover type obtained from the US Forest Service Region 2 Resource Information System. And datasets from [41] that involve the identification of disease-carrying insects using optical sensors. The following abbreviations are used to name them based on different impact of temperature: IABN, IGBN, IIAIN, IIRIN.
<figure><img src="image_7.png" /><figcaption>Fig. 3. Artificial datasets of different distributions.</figcaption></figure>

### 4.1.3. Datasets preprocessing

Since the proposed framework supports both static (batch) and dynamic (data stream) clustering, the experiments are performed on artificial and real datasets suitable for both types of clustering. Therefore, the setup steps are adapted to these two types of scenarios:

*   **Static Clustering:** For the static experiments, the results are compared with conventional clustering applied to the whole datasets. The order of the data is randomly shuffled, then the windows are defined according to a predefined number of data instances per window, usually expressed as a proportion of the number of instances.

*   **Dynamic Clustering:** For the dynamic experiments, the results were compared with popular data stream clustering algorithms. To simulate a dynamic process in the artificial datasets, each data instance was randomly assigned a timestamp. Real datasets were kept with their original timestamps, if available, or were timestamped according to their original order. Windows were defined according to a chosen time interval, and the number of data instances in different windows can vary according to the timestamps of the instances.

In both cases, the goal is to apply conventional clustering on non-overlapping windows to detect clusters before merging similar clusters using the proposed framework.

### 4.2. Clustering evaluation strategy

The Adjusted Rand Index (ARI), Normalized Mutual Informations (NMI) and Purity are becoming increasingly popular for assessing the quality of clustering, as they are regularly used in a large number of studies. Each of them is an external index based on a priori knowledge of the data structure. Internal indices typically check the compactness and separability of clusters and work well to evaluate clusters that are close to a Gaussian distribution. Due to the diversity of cluster distributions in the experimental datasets, we decided to restrict the evaluation to external indices. For both ARI and NMI, we used the functions implemented in the scikit-learn [42] Python package, which compute the ARI score, bounded between -0.5 and 1, and the NMI score in the range [0,1]. Both indexes are based on the computation of a contingency table (see Table 2).

*   **Adjusted Rand Index (ARI) [43]:** By considering all sample pair assignments in both the expected and actual clusterings, as well

as counting sample pair assignments in the predicted or actual clusterings the ARI formula is as follow:

$$ARI = \frac{\sum_{i,j} \binom{n_{i,j}}{2} - \frac{\sum_{i} \binom{a_i}{2} \sum_{j} \binom{b_j}{2}}{\binom{N}{2}}}{\frac{1}{2} \left( \sum_{i} \binom{a_i}{2} + \sum_{j} \binom{b_j}{2} \right) - \frac{\sum_{i} \binom{a_i}{2} \sum_{j} \binom{b_j}{2}}{\binom{N}{2}}}$$

*   **Purity [44]:** Each cluster is given a description based on the class that makes up the majority of the cluster. Purity is then computed as the fraction of all data points divided by the number of successfully matched class and cluster labels. The formula is summarized as follows, where n is the number of samples and K is the number of clusters.

$$Purity = \frac{\sum_{k=1}^{K} \max(\text{number of majority cluster in k})}{n}$$

*   **Normalized Mutual Information (NMI) [45]:** Widely used and increasingly popular metric for evaluating community detection methods, it measures the similarity between two partitions by calculating their mutual information, normalized by the entropies of the partitions. Unlike overlap metrics, NMI does not require that the two partitions have the same number of groups. This makes it particularly useful for assessing the agreement between two independent labeling strategies on the same dataset, even when the true underlying labels are unknown.

$$NMI = \frac{-2 \sum_{i,j} n_{i,j} \log\left(\frac{N \cdot n_{i,j}}{b_j \cdot a_i}\right)}{\sum_{j} b_j \log\left(\frac{b_j}{N}\right) + \sum_{i} a_i \log\left(\frac{a_i}{N}\right)}$$

As discussed in [46], it is sometimes valuable to consider the “trade-off” between computation time and clustering quality as an additional analysis of clustering performance. This consideration is important because the proposed approach may not always be the best when evaluated solely by the traditional metrics mentioned above. In some cases, its clustering quality may be slightly lower than others. However, if this difference in quality is limited while the approach significantly reduces the computation time, the practical value of the proposed framework is worth considering. To facilitate this discussion, we use a simple index:

$$Trade-off = \frac{\text{Clustering quality}}{\text{Normalized time}}$$
<table><caption>**Table 2**
Each element $n_{i,j}$ of this table correspond to the number of data points in common between cluster $C_p(i)$ and cluster $C_r(j)$.</caption><thead><tr><th>Real/Predicted clusters</th><th>C<sub>p</sub>(1)</th><th>...</th><th>C<sub>r</sub>(j)</th><th>...</th><th>C<sub>p</sub>(N<sub>r</sub>)</th><th>a<sub>i</sub> = &Sigma;<sub>j</sub> n<sub>i,j</sub></th></tr></thead><tbody><tr><td>C<sub>p</sub>(1)</td><td>n<sub>1,1</sub></td><td></td><td>n<sub>1,j</sub></td><td></td><td>n<sub>1,N<sub>r</sub></sub></td><td>a<sub>1</sub></td></tr><tr><td>...</td><td></td><td></td><td>...</td><td></td><td>...</td><td>...</td></tr><tr><td>C<sub>p</sub>(i)</td><td>n<sub>i,1</sub></td><td>...</td><td>n<sub>i,j</sub></td><td>...</td><td>n<sub>i,N<sub>r</sub></sub></td><td>a<sub>i</sub></td></tr><tr><td>...</td><td></td><td></td><td>...</td><td></td><td>...</td><td>...</td></tr><tr><td>C<sub>p</sub>(N<sub>p</sub>)</td><td>n<sub>N<sub>p</sub>,1</sub></td><td></td><td>n<sub>N<sub>p</sub>,j</sub></td><td></td><td>n<sub>N<sub>p</sub>,N<sub>r</sub></sub></td><td>a<sub>N<sub>r</sub></sub></td></tr><tr><td>b<sub>j</sub> = &Sigma;<sub>i</sub> n<sub>i,j</sub></td><td>b<sub>1</sub></td><td></td><td>b<sub>j</sub></td><td></td><td>b<sub>N<sub>r</sub></sub></td><td>N = &Sigma;<sub>i,j</sub> n<sub>i,j</sub></td></tr></tbody></table>

<figure><img src="image_8.png" /><figcaption>**Fig. 4.** Results with increasing the number of bins — Artificial datasets.</figcaption></figure>

Here, “normalized time” refers to the computation time normalized by the total time of all algorithms for each dataset. This normalization is useful for visualization purposes. Unlike standard evaluation metrics, this “trade-off” metric provides a quick comparison that highlights the balance between time consumption and clustering quality. While the exact scores/values are not the primary focus of the experiments, the resulting visualizations of this metric help to discuss the importance and efficiency of the proposed approach.

## 4.3. Parameter analysis

An analysis of the impact of different parameters of the proposed approach on its quality has been carried out. In particular, the number of bins of the histogram model, the number of random projections, and the number of windows (also related to the number of samples in a window), which could change the quality and complexity of the clustering, all these parameters could have an impact on the result of our approach. We ran each test 10 times and report the average performance with the corresponding standard deviation.

### 4.3.1. Number of bins

As can be seen from the results in Figs. 4–6, the proposed approach performs quite similarly regardless of the number of bins, on both artificial and real datasets. In fact, the quality of the clustering did not change significantly when the number of bins was adjusted. However, it is clear that the computation time is higher when the number of bins is increased. Therefore, in the following experiments, we set the number of bins to 10 in order to be efficient without losing quality.

### 4.3.2. Number of projections

We found that the quality of clustering does not vary significantly when the number of projections is changed, both on real and artificial datasets, according to the results shown in Figs. 7–9. This seems that reducing the data dimensions still preserves the histogram’s ability to efficiently detect clusters with similar distributions. The algorithm runs faster with fewer projections than variables in the dataset, but computation time increases with more projections. Therefore, we set the number of projections to 4 for the following experiments.

### 4.3.3. Window size

When the datasets are divided into more windows, the proposed cluster similarity test is applied more often on clusters with few samples, potentially leading to more errors, but the process is faster. The aim of testing the effect of changing the number of windows is the same as testing the effect of the number of samples in a window, as well as the effect of the number of times we apply the similarity test. As can be seen in Figs. 10–12, there is a gradual decrease in quality as the number of windows increases, as the number of comparisons increases, although there is also an initial dramatic decrease in computation time followed by convergence after a certain number of windows.

Therefore, to achieve better performance, we set the number of samples or time intervals in each window differently for different datasets. In our experiments, we carefully choose the number of data points (or time intervals) in each batch to ensure the effectiveness of our approach. Striking a balance is essential; using too few data points can result in scattered points, making it difficult to find clusters. Conversely, too many data points would lead to an over-reliance on
<figure><img src="image_9.png" /><figcaption>Fig. 5. Results with increasing the number of bins — Real datasets (PART I).</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Fig. 6. Results with increasing the number of bins — Real datasets (PART II).</figcaption></figure>

standard clustering within each batch, potentially obscuring the impact of the proposed approach.

To address this, we have developed a systematic configuration for the experiments on both static datasets and dynamic datasets. For smaller datasets, we ensure that the number of data points in each batch is approximately 10% of the total number. For larger datasets, this proportion is reduced to 5%. For artificial datasets, we keep the percentage constant. However, real-world datasets may consist of varying amounts of samples, we allow for slight adjustments to avoid inconsistent number of batches in the analysis. The number of samples in each window for the batch clustering tests, the total duration and the chosen time intervals of the windows for the dynamic clustering tests are both described in.

## 4.4. Quality of the distribution comparisons

We performed an experiment to confirm that the statistical test we use to identify similarity between identical distributions works

correctly, as this is important for the proposed framework. First, we create pairs of clusters drawn from the same distribution. Each pair is constructed with different distribution types and dimensions. We then apply the similarity test to these pairs. As expected, the results show that the percentage of similar clusters discovered for each distribution is about 95%, in accordance with the chosen threshold $\delta = 5\%$ (see Fig. 13).

We also evaluated the robustness of the similarity detection by shifting the position of a distribution by a fraction of its standard deviation $\sigma$ over a random axis, to check at what level the two clusters are treated as not similar. Therefore, we fix a cluster distribution and shift the position of the cluster by $1+\sigma*\text{std\_per}$. After each shift, we compute the similarity between the two cluster distributions (Fig. 14).

For datasets with different dimensions (see Fig. 15), as long as the shift remains below about 10% of the standard deviation, we observe only a slow decrease in the proportion of pairs detected as similar, from 95% to 80%. If we further increase the shift, we observe, as expected, a sharp decrease in the proportion of pairs detected as similar.
<figure><img src="image_11.png" /><figcaption>Fig. 7. Results with increasing the number of projections — Artificial datasets.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Fig. 8. Results with increasing the number of projections — Real datasets (PART I).</figcaption></figure>

<table><caption>**Table 3**
Number of samples in the windows for each dataset.</caption><thead><tr><th rowspan="2">Datasets</th><th colspan="4">Number of samples in the windows for each dataset</th></tr><tr><th>NbSamples</th><th>Datasets</th><th>NbSamples</th><th>Datasets</th><th>NbSamples</th></tr></thead><tbody><tr><td>Comet3</td><td>3000</td><td>Comet20</td><td>10000</td><td>MixSmall1</td><td>1000</td></tr><tr><td>Meteorite3</td><td>3000</td><td>Meteorite20</td><td>10000</td><td>MixSmall2</td><td>2000</td></tr><tr><td>Square3</td><td>3000</td><td>Square20</td><td>10000</td><td>MixSmall3</td><td>3000</td></tr><tr><td>Gaussian3</td><td>3000</td><td>Gaussian20</td><td>10000</td><td>MixLarge10</td><td>5000</td></tr><tr><td>Moon3</td><td>3000</td><td>Moon20</td><td>10000</td><td>MixLarge20</td><td>10000</td></tr><tr><td>Circle3</td><td>3000</td><td>Circle20</td><td>10000</td><td>MixLarge30</td><td>20000</td></tr><tr><td>Outdoor</td><td>1500</td><td>Gassenor</td><td>2000</td><td>IGBN</td><td>3000</td></tr><tr><td>IABN</td><td>6000</td><td>Rialto</td><td>8000</td><td>IIAIN</td><td>8000</td></tr><tr><td>IIRIN</td><td>40000</td><td>Covtype</td><td>60000</td><td></td><td></td></tr></tbody></table>

<table><thead><tr><th rowspan="2">Datasets</th><th colspan="4">Total duration and time interval of the windows for each dataset</th></tr><tr><th>Total_dur</th><th>Time_inter</th><th>Datasets</th><th>Total_dur</th><th>Time_inter</th></tr></thead><tbody><tr><td>Comet20</td><td>200</td><td>4</td><td>Meteorite20</td><td>200</td><td>4</td></tr><tr><td>Square20</td><td>200</td><td>4</td><td>Gaussian20</td><td>200</td><td>4</td></tr><tr><td>Moon20</td><td>200</td><td>4</td><td>Circle20</td><td>200</td><td>4</td></tr><tr><td>MixLarge10</td><td>100</td><td>5</td><td>MixLarge20</td><td>200</td><td>6</td></tr><tr><td>MixLarge50</td><td>500</td><td>7</td><td>Outdoor</td><td>30</td><td>6</td></tr><tr><td>Gassenor</td><td>50</td><td>5</td><td>IGBN</td><td>50</td><td>5</td></tr><tr><td>IABN</td><td>80</td><td>4</td><td>Rialto</td><td>80</td><td>4</td></tr><tr><td>IIAIN</td><td>150</td><td>5</td><td>IIRIN</td><td>150</td><td>5</td></tr><tr><td>Covtype</td><td>150</td><td>5</td><td></td><td></td><td></td></tr></tbody></table>
<figure><img src="image_13.png" /><figcaption>Fig. 9. Results with increasing the number of projections — Real datasets (PART II).</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Fig. 10. Results with increasing the number of windows — Artificial datasets.</figcaption></figure>

## 4.5. Assessment of algorithm quality and complexity

We performed a series of experiments to evaluate the quality and complexity of the resulting clustering in comparison to existing approaches (Fig. 16). The proposed framework can be used with any clustering algorithm, depending on the required cluster properties, by working on subsets (windows) of data and comparing the obtained clusters between windows. For experiments on static datasets, we separated the artificial datasets into small and large categories to apply two sets of appropriate clustering algorithms, while applying all algorithms to the real datasets. We expect the proposed framework to reduce the computational speed and memory requirements of most existing clustering algorithms, while preserving their interesting properties, with minimal loss of quality. For experiments on dynamic datasets,

we applied the algorithms on large artificial datasets and all the real datasets. We expect the proposed framework to be competitive with existing stream clustering approaches in terms of quality and complexity, while allowing great flexibility in the choice of the clustering algorithm to be applied. For all experiments, the mean and standard deviation over five replicates are presented as results.

### 4.5.1. Experiments on static datasets

As mentioned above, our approach relies on sliding windows and the basic idea is to first perform conventional clustering on each window, then represent the resulting clusters in a histogram model and merge the windows to obtain the final clustering results. This part of the test compares conventional clustering algorithms applied to the full dataset with the proposed approach using the same clustering
<figure><img src="image_15.png" /><figcaption>Fig. 11. Results with increasing the number of windows — Real datasets (PART I).</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>Fig. 12. Results with increasing the number of windows — Real datasets (PART II).</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>Fig. 13. Similarity tests between similar distribution. The red line represents 95% of correct detection. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)</figcaption></figure>
<figure><img src="image_18.png" /><figcaption>Fig. 14. Example of a similarity test between two similar clusters by changing the standard deviation percentage (std_per) to change the position of the second cluster.</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>Fig. 15. Similarity test on distinct distributions of different dimension numbers by increasing std_per.</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>Fig. 16. Overview of the experimental protocol for static and dynamic datasets.</figcaption></figure>

algorithms applied to sliding windows (illustrated in Fig. 16). The following clustering algorithms were selected for comparison in this section: BIRCH, Agglomerative Clustering, OPTICS, Spectral Clustering, K-means, Gaussian Mixture, HDBSCAN, and KASP. Except for spectral clustering and KASP, other algorithms were implemented in the scikit-learn package [42]. For algorithms that require a predefined number of clusters, we set it based on true labels. For spectral clustering, we used the STAGPy library [47], a C++ library with a Python wrapper, and set the neighborhood parameter to 10. Due to high complexity, BIRCH, Agglomerative, and Spectral clustering were only tested on small datasets. KASP used scikit-learn's K-means and STAGPy's spectral clustering with subsample size set to $5 * \sqrt{Nb\_samples}$ and neighborhoods set to 10. K-means, Gaussian Mixture, and KASP are optimized for large datasets, while OPTICS has only been tested on small datasets due to slower performance compared to HDBSCAN on larger datasets.

For small datasets, the ARI, Purity, NMI, and computation time results are detailed in Tables 4, 5, 6, and 7. With the means of each

index separated between artificial and real datasets, show that for artificial datasets, the proposed approaches perform similarly to BIRCH and Agglomerative Clustering, with only slight differences. Compared to OPTICS and Spectral clustering, the proposed approaches show superior quality. For real datasets, the proposed approaches generally outperform conventional clustering methods.

In addition, the proposed approaches consistently exhibit faster computation time than the original algorithms. The Trade-off analysis between clustering quality and computation time, shown in Figs. 17 and 18, further confirms the efficiency of the proposed framework.

For large datasets, the ARI, Purity, NMI and computation time results are presented in Tables 8, 9, 10, and 11. From the results of artificial datasets, the proposed approaches are comparable to K-means and GaussianMixture and superior to HDBSCAN. The difference with KASP is more noticeable for the ARI index, but the proposed framework is superior for NMI and Purity. It also always outperforms the conventional algorithms on real datasets.
<table><caption>**Table 4**
ARI results of static experiments — Small datasets.</caption><thead><tr><th rowspan="3">Datasets</th><th colspan="4">BIRCH</th><th colspan="4">Agglomerative</th><th colspan="4">OPTICS</th><th colspan="4">SpectralClustering</th></tr><tr><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th></tr><tr><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th></tr></thead><tbody><tr><td>Comet3</td><td>0.930</td><td>&lt;1e-4</td><td>0.959</td><td>&lt;1e-4</td><td>0.932</td><td>&lt;1e-4</td><td>0.958</td><td>&lt;1e-4</td><td>0.337</td><td>&lt;1e-4</td><td>0.745</td><td>&lt;1e-4</td><td>0.305</td><td>&lt;1e-4</td><td>0.182</td><td>&lt;1e-4</td></tr><tr><td>Metrooit3</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.999</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.836</td><td>&lt;1e-4</td><td>0.598</td><td>&lt;1e-4</td><td>0.431</td><td>&lt;1e-4</td></tr><tr><td>Circle3</td><td>0.981</td><td>&lt;1e-4</td><td>0.963</td><td>&lt;1e-4</td><td>0.981</td><td>&lt;1e-4</td><td>0.966</td><td>&lt;1e-4</td><td>0.025</td><td>&lt;1e-4</td><td>0.945</td><td>&lt;1e-4</td><td>0.186</td><td>&lt;1e-4</td><td>0.294</td><td>&lt;1e-4</td></tr><tr><td>Gaussian3</td><td>1.000</td><td>&lt;1e-4</td><td>0.896</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.709</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.999</td><td>&lt;1e-4</td><td>0.098</td><td>&lt;1e-4</td><td>0.319</td><td>&lt;1e-4</td></tr><tr><td>Square3</td><td>1.000</td><td>&lt;1e-4</td><td>0.978</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.993</td><td>&lt;1e-4</td><td>0.326</td><td>&lt;1e-4</td><td>0.431</td><td>&lt;1e-4</td></tr><tr><td>Moon3</td><td>1.000</td><td>&lt;1e-4</td><td>0.903</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.904</td><td>&lt;1e-4</td><td>0.865</td><td>&lt;1e-4</td><td>0.978</td><td>&lt;1e-4</td><td>0.264</td><td>&lt;1e-4</td><td>0.168</td><td>&lt;1e-4</td></tr><tr><td>MixSmall1</td><td>0.982</td><td>&lt;1e-4</td><td>0.955</td><td>&lt;1e-4</td><td>0.979</td><td>&lt;1e-4</td><td>0.956</td><td>&lt;1e-4</td><td>0.696</td><td>&lt;1e-4</td><td>0.953</td><td>&lt;1e-4</td><td>0.298</td><td>&lt;1e-4</td><td>0.356</td><td>&lt;1e-4</td></tr><tr><td>MixSmall2</td><td>0.927</td><td>&lt;1e-4</td><td>0.879</td><td>&lt;1e-4</td><td>0.931</td><td>&lt;1e-4</td><td>0.881</td><td>&lt;1e-4</td><td>0.988</td><td>&lt;1e-4</td><td>0.955</td><td>&lt;1e-4</td><td>0.407</td><td>&lt;1e-4</td><td>0.412</td><td>&lt;1e-4</td></tr><tr><td>MixSmall3</td><td>0.994</td><td>&lt;1e-4</td><td>0.984</td><td>&lt;1e-4</td><td>0.994</td><td>&lt;1e-4</td><td>0.984</td><td>&lt;1e-4</td><td>0.996</td><td>&lt;1e-4</td><td>0.984</td><td>&lt;1e-4</td><td>0.208</td><td>&lt;1e-4</td><td>0.443</td><td>&lt;1e-4</td></tr><tr><td>Average mean(Artificial)</td><td>0.979</td><td>&lt;1e-4</td><td>0.946</td><td>&lt;1e-4</td><td>0.980</td><td>&lt;1e-4</td><td>0.929</td><td>&lt;1e-4</td><td>0.767</td><td>&lt;1e-4</td><td>0.932</td><td>&lt;1e-4</td><td>0.299</td><td>&lt;1e-4</td><td>0.337</td><td>&lt;1e-4</td></tr><tr><td>Outdoor</td><td>0.003</td><td>&lt;1e-4</td><td>0.425</td><td>&lt;1e-4</td><td>0.404</td><td>&lt;1e-4</td><td>0.445</td><td>&lt;1e-4</td><td>0.248</td><td>&lt;1e-4</td><td>0.265</td><td>&lt;1e-4</td><td>0.404</td><td>&lt;1e-4</td><td>0.354</td><td>&lt;1e-4</td></tr><tr><td>Gassenor</td><td>0.127</td><td>&lt;1e-4</td><td>0.275</td><td>&lt;1e-4</td><td>0.127</td><td>&lt;1e-4</td><td>0.284</td><td>&lt;1e-4</td><td>0.013</td><td>&lt;1e-4</td><td>0.022</td><td>&lt;1e-4</td><td>0.240</td><td>&lt;1e-4</td><td>0.312</td><td>&lt;1e-4</td></tr><tr><td>IGBN</td><td>0.009</td><td>&lt;1e-4</td><td>0.286</td><td>&lt;1e-4</td><td>0.065</td><td>&lt;1e-4</td><td>0.227</td><td>&lt;1e-4</td><td>0.006</td><td>&lt;1e-4</td><td>0.013</td><td>&lt;1e-4</td><td>0.137</td><td>&lt;1e-4</td><td>0.201</td><td>&lt;1e-4</td></tr><tr><td>IABN</td><td>0.111</td><td>&lt;1e-4</td><td>0.100</td><td>&lt;1e-4</td><td>0.110</td><td>&lt;1e-4</td><td>0.062</td><td>&lt;1e-4</td><td>0.003</td><td>&lt;1e-4</td><td>0.007</td><td>&lt;1e-4</td><td>0.122</td><td>&lt;1e-4</td><td>0.078</td><td>&lt;1e-4</td></tr><tr><td>Average mean(Real)</td><td>0.062</td><td>&lt;1e-4</td><td>0.272</td><td>&lt;1e-4</td><td>0.177</td><td>&lt;1e-4</td><td>0.255</td><td>&lt;1e-4</td><td>0.068</td><td>&lt;1e-4</td><td>0.077</td><td>&lt;1e-4</td><td>0.226</td><td>&lt;1e-4</td><td>0.236</td><td>&lt;1e-4</td></tr><tr><td>Total average mean</td><td>0.697</td><td>&lt;1e-4</td><td>0.739</td><td>&lt;1e-4</td><td>0.733</td><td>&lt;1e-4</td><td>0.721</td><td>&lt;1e-4</td><td>0.552</td><td>&lt;1e-4</td><td>0.669</td><td>&lt;1e-4</td><td>0.276</td><td>&lt;1e-4</td><td>0.306</td><td>&lt;1e-4</td></tr></tbody></table>

<table><caption>**Table 5**
Purity results for static experiments — Small datasets.</caption><thead><tr><th rowspan="3">Datasets</th><th colspan="4">BIRCH</th><th colspan="4">Agglomerative</th><th colspan="4">OPTICS</th><th colspan="4">SpectralClustering</th></tr><tr><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th></tr><tr><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th></tr></thead><tbody><tr><td>Comet3</td><td>0.999</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.999</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.676</td><td>&lt;1e-4</td><td>0.825</td><td>&lt;1e-4</td></tr><tr><td>Metrooit3</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.757</td><td>&lt;1e-4</td><td>0.913</td><td>&lt;1e-4</td></tr><tr><td>Circle3</td><td>0.998</td><td>&lt;1e-4</td><td>0.999</td><td>&lt;1e-4</td><td>0.998</td><td>&lt;1e-4</td><td>0.999</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.556</td><td>&lt;1e-4</td><td>0.855</td><td>&lt;1e-4</td></tr><tr><td>Gaussian3</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.449</td><td>&lt;1e-4</td><td>0.904</td><td>&lt;1e-4</td></tr><tr><td>Square3</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.573</td><td>&lt;1e-4</td><td>0.838</td><td>&lt;1e-4</td></tr><tr><td>Moon3</td><td>1.000</td><td>&lt;1e-4</td><td>0.998</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.998</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.621</td><td>&lt;1e-4</td><td>0.798</td><td>&lt;1e-4</td></tr><tr><td>MixSmall1</td><td>0.999</td><td>&lt;1e-4</td><td>0.999</td><td>&lt;1e-4</td><td>0.999</td><td>&lt;1e-4</td><td>0.999</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.669</td><td>&lt;1e-4</td><td>0.896</td><td>&lt;1e-4</td></tr><tr><td>MixSmall2</td><td>0.998</td><td>&lt;1e-4</td><td>0.999</td><td>&lt;1e-4</td><td>0.998</td><td>&lt;1e-4</td><td>0.999</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.686</td><td>&lt;1e-4</td><td>0.895</td><td>&lt;1e-4</td></tr><tr><td>MixSmall3</td><td>0.999</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.999</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.608</td><td>&lt;1e-4</td><td>0.915</td><td>&lt;1e-4</td></tr><tr><td>Average mean(Artificial)</td><td>0.999</td><td>&lt;1e-4</td><td>0.999</td><td>&lt;1e-4</td><td>0.999</td><td>&lt;1e-4</td><td>0.999</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.622</td><td>&lt;1e-4</td><td>0.871</td><td>&lt;1e-4</td></tr><tr><td>Outdoor</td><td>0.057</td><td>&lt;1e-4</td><td>0.617</td><td>&lt;1e-4</td><td>0.564</td><td>&lt;1e-4</td><td>0.656</td><td>&lt;1e-4</td><td>0.955</td><td>&lt;1e-4</td><td>0.931</td><td>&lt;1e-4</td><td>0.559</td><td>&lt;1e-4</td><td>0.629</td><td>&lt;1e-4</td></tr><tr><td>Gassenor</td><td>0.425</td><td>&lt;1e-4</td><td>0.680</td><td>&lt;1e-4</td><td>0.425</td><td>&lt;1e-4</td><td>0.680</td><td>&lt;1e-4</td><td>0.993</td><td>&lt;1e-4</td><td>0.987</td><td>&lt;1e-4</td><td>0.500</td><td>&lt;1e-4</td><td>0.714</td><td>&lt;1e-4</td></tr><tr><td>IGBN</td><td>0.235</td><td>&lt;1e-4</td><td>0.557</td><td>&lt;1e-4</td><td>0.320</td><td>&lt;1e-4</td><td>0.632</td><td>&lt;1e-4</td><td>0.659</td><td>&lt;1e-4</td><td>0.697</td><td>&lt;1e-4</td><td>0.375</td><td>&lt;1e-4</td><td>0.648</td><td>&lt;1e-4</td></tr><tr><td>IABN</td><td>0.308</td><td>&lt;1e-4</td><td>0.374</td><td>&lt;1e-4</td><td>0.349</td><td>&lt;1e-4</td><td>0.414</td><td>&lt;1e-4</td><td>0.670</td><td>&lt;1e-4</td><td>0.647</td><td>&lt;1e-4</td><td>0.325</td><td>&lt;1e-4</td><td>0.428</td><td>&lt;1e-4</td></tr><tr><td>Average mean(Real)</td><td>0.256</td><td>&lt;1e-4</td><td>0.557</td><td>&lt;1e-4</td><td>0.414</td><td>&lt;1e-4</td><td>0.596</td><td>&lt;1e-4</td><td>0.819</td><td>&lt;1e-4</td><td>0.816</td><td>&lt;1e-4</td><td>0.440</td><td>&lt;1e-4</td><td>0.605</td><td>&lt;1e-4</td></tr><tr><td>Total average mean</td><td>0.771</td><td>&lt;1e-4</td><td>0.863</td><td>&lt;1e-4</td><td>0.819</td><td>&lt;1e-4</td><td>0.875</td><td>&lt;1e-4</td><td>0.944</td><td>&lt;1e-4</td><td>0.943</td><td>&lt;1e-4</td><td>0.566</td><td>&lt;1e-4</td><td>0.789</td><td>&lt;1e-4</td></tr></tbody></table>

<table><caption>**Table 6**
NMI results for static experiments — Small datasets.</caption><thead><tr><th rowspan="3">Datasets</th><th colspan="4">BIRCH</th><th colspan="4">Agglomerative</th><th colspan="4">OPTICS</th><th colspan="4">SpectralClustering</th></tr><tr><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th></tr><tr><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th></tr></thead><tbody><tr><td>Comet3</td><td>0.973</td><td>&lt;1e-4</td><td>0.965</td><td>&lt;1e-4</td><td>0.974</td><td>&lt;1e-4</td><td>0.964</td><td>&lt;1e-4</td><td>0.765</td><td>&lt;1e-4</td><td>0.803</td><td>&lt;1e-4</td><td>0.612</td><td>&lt;1e-4</td><td>0.601</td><td>&lt;1e-4</td></tr><tr><td>Metrooit3</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.997</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.948</td><td>&lt;1e-4</td><td>0.756</td><td>&lt;1e-4</td><td>0.708</td><td>&lt;1e-4</td></tr><tr><td>Circle3</td><td>0.986</td><td>&lt;1e-4</td><td>0.958</td><td>&lt;1e-4</td><td>0.986</td><td>&lt;1e-4</td><td>0.963</td><td>&lt;1e-4</td><td>0.386</td><td>&lt;1e-4</td><td>0.815</td><td>&lt;1e-4</td><td>0.529</td><td>&lt;1e-4</td><td>0.661</td><td>&lt;1e-4</td></tr><tr><td>Gaussian3</td><td>1.000</td><td>&lt;1e-4</td><td>0.955</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.911</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.999</td><td>&lt;1e-4</td><td>0.431</td><td>&lt;1e-4</td><td>0.702</td><td>&lt;1e-4</td></tr><tr><td>Square3</td><td>1.000</td><td>&lt;1e-4</td><td>0.990</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.989</td><td>&lt;1e-4</td><td>0.687</td><td>&lt;1e-4</td><td>0.728</td><td>&lt;1e-4</td></tr><tr><td>Moon3</td><td>1.000</td><td>&lt;1e-4</td><td>0.923</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.924</td><td>&lt;1e-4</td><td>0.707</td><td>&lt;1e-4</td><td>0.938</td><td>&lt;1e-4</td><td>0.600</td><td>&lt;1e-4</td><td>0.587</td><td>&lt;1e-4</td></tr><tr><td>MixSmall1</td><td>0.991</td><td>&lt;1e-4</td><td>0.973</td><td>&lt;1e-4</td><td>0.990</td><td>&lt;1e-4</td><td>0.973</td><td>&lt;1e-4</td><td>0.813</td><td>&lt;1e-4</td><td>0.933</td><td>&lt;1e-4</td><td>0.726</td><td>&lt;1e-4</td><td>0.751</td><td>&lt;1e-4</td></tr><tr><td>MixSmall2</td><td>0.982</td><td>&lt;1e-4</td><td>0.955</td><td>&lt;1e-4</td><td>0.982</td><td>&lt;1e-4</td><td>0.957</td><td>&lt;1e-4</td><td>0.959</td><td>&lt;1e-4</td><td>0.945</td><td>&lt;1e-4</td><td>0.788</td><td>&lt;1e-4</td><td>0.780</td><td>&lt;1e-4</td></tr><tr><td>MixSmall3</td><td>0.996</td><td>&lt;1e-4</td><td>0.987</td><td>&lt;1e-4</td><td>0.996</td><td>&lt;1e-4</td><td>0.987</td><td>&lt;1e-4</td><td>0.981</td><td>&lt;1e-4</td><td>0.961</td><td>&lt;1e-4</td><td>0.678</td><td>&lt;1e-4</td><td>0.802</td><td>&lt;1e-4</td></tr><tr><td>Average mean(Artificial)</td><td>0.992</td><td>&lt;1e-4</td><td>0.967</td><td>&lt;1e-4</td><td>0.992</td><td>&lt;1e-4</td><td>0.964</td><td>&lt;1e-4</td><td>0.846</td><td>&lt;1e-4</td><td>0.926</td><td>&lt;1e-4</td><td>0.645</td><td>&lt;1e-4</td><td>0.702</td><td>&lt;1e-4</td></tr><tr><td>Outdoor</td><td>0.068</td><td>&lt;1e-4</td><td>0.731</td><td>&lt;1e-4</td><td>0.715</td><td>&lt;1e-4</td><td>0.737</td><td>&lt;1e-4</td><td>0.779</td><td>&lt;1e-4</td><td>0.774</td><td>&lt;1e-4</td><td>0.694</td><td>&lt;1e-4</td><td>0.699</td><td>&lt;1e-4</td></tr><tr><td>Gassenor</td><td>0.275</td><td>&lt;1e-4</td><td>0.471</td><td>&lt;1e-4</td><td>0.275</td><td>&lt;1e-4</td><td>0.475</td><td>&lt;1e-4</td><td>0.419</td><td>&lt;1e-4</td><td>0.438</td><td>&lt;1e-4</td><td>0.424</td><td>&lt;1e-4</td><td>0.510</td><td>&lt;1e-4</td></tr><tr><td>IGBN</td><td>0.087</td><td>&lt;1e-4</td><td>0.431</td><td>&lt;1e-4</td><td>0.124</td><td>&lt;1e-4</td><td>0.412</td><td>&lt;1e-4</td><td>0.257</td><td>&lt;1e-4</td><td>0.297</td><td>&lt;1e-4</td><td>0.197</td><td>&lt;1e-4</td><td>0.409</td><td>&lt;1e-4</td></tr><tr><td>IABN</td><td>0.138</td><td>&lt;1e-4</td><td>0.216</td><td>&lt;1e-4</td><td>0.137</td><td>&lt;1e-4</td><td>0.191</td><td>&lt;1e-4</td><td>0.245</td><td>&lt;1e-4</td><td>0.242</td><td>&lt;1e-4</td><td>0.173</td><td>&lt;1e-4</td><td>0.216</td><td>&lt;1e-4</td></tr><tr><td>Average mean(Real)</td><td>0.142</td><td>&lt;1e-4</td><td>0.462</td><td>&lt;1e-4</td><td>0.313</td><td>&lt;1e-4</td><td>0.454</td><td>&lt;1e-4</td><td>0.425</td><td>&lt;1e-4</td><td>0.438</td><td>&lt;1e-4</td><td>0.372</td><td>&lt;1e-4</td><td>0.459</td><td>&lt;1e-4</td></tr><tr><td>Total average mean</td><td>0.730</td><td>&lt;1e-4</td><td>0.812</td><td>&lt;1e-4</td><td>0.783</td><td>&lt;1e-4</td><td>0.807</td><td>&lt;1e-4</td><td>0.716</td><td>&lt;1e-4</td><td>0.776</td><td>&lt;1e-4</td><td>0.561</td><td>&lt;1e-4</td><td>0.627</td><td>&lt;1e-4</td></tr></tbody></table>

In order to analyze the potential limitations of the proposed approach in more detail, it is important to set out the prerequisites for a high quality result. First, since the framework decomposes the dataset into smaller subsets, it is necessary that the clustering algorithm applied to each subset maintains good performance (in terms of computation time and result quality) compared to the same algorithm applied to the entire dataset. Second, since the distribution of the data in each cluster is estimated according to a set of univariate distributions based on random projections, this estimation must be reliable, which may not be the case for some specific non-convex distributions.

The first case is illustrated in our experimental result with the slight decrease in quality observed when using KASP in the proposed framework. KASP operates on a subsample of the original dataset distribution generated using K-means prototypes, followed by applying spectral clustering to this subsample to obtain preliminary partitions that guide the final clustering process. The size of the subsample has a significant impact on the clustering quality, and depends on the number of data points, leading to different performances on the whole dataset compared to its decomposition into smaller subsets. Indeed, clustering quality in KASP shows considerable variability as the number of samples changes, and the relationship between performance and
<table><caption>**Table 7**

Computation time for static experiments — Small datasets.</caption><thead><tr><th rowspan="3">Datasets</th><th colspan="4">BIRCH</th><th colspan="4">Agglomerative</th><th colspan="4">OPTICS</th><th colspan="4">SpectralClustering</th></tr><tr><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th></tr><tr><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th></tr></thead><tbody><tr><td>Comet3</td><td>46.399</td><td>5.525</td><td>7.841</td><td>0.243</td><td>127.408</td><td>58.311</td><td>5.026</td><td>0.387</td><td>493.379</td><td>29.105</td><td>163.468</td><td>4.287</td><td>12.357</td><td>1.412</td><td>8.769</td><td>1.257</td></tr><tr><td>Metroit3</td><td>67.044</td><td>7.569</td><td>8.112</td><td>0.412</td><td>98.868</td><td>3.322</td><td>4.885</td><td>0.161</td><td>918.683</td><td>38.070</td><td>150.940</td><td>2.901</td><td>13.534</td><td>2.371</td><td>8.857</td><td>1.275</td></tr><tr><td>Circle3</td><td>58.836</td><td>14.692</td><td>7.689</td><td>0.115</td><td>385.324</td><td>380.004</td><td>4.635</td><td>0.046</td><td>549.950</td><td>93.681</td><td>200.485</td><td>9.385</td><td>11.447</td><td>1.409</td><td>6.992</td><td>0.041</td></tr><tr><td>Gaussian3</td><td>50.604</td><td>6.429</td><td>7.934</td><td>0.260</td><td>149.074</td><td>54.408</td><td>4.911</td><td>0.121</td><td>907.935</td><td>7.840</td><td>156.065</td><td>15.702</td><td>8.010</td><td>0.036</td><td>6.942</td><td>0.016</td></tr><tr><td>Square3</td><td>48.930</td><td>13.221</td><td>10.005</td><td>0.339</td><td>269.327</td><td>26.808</td><td>5.556</td><td>0.319</td><td>517.414</td><td>57.988</td><td>183.234</td><td>5.660</td><td>8.706</td><td>0.077</td><td>6.885</td><td>0.056</td></tr><tr><td>Moon3</td><td>50.688</td><td>8.058</td><td>8.957</td><td>0.777</td><td>116.288</td><td>12.716</td><td>5.423</td><td>0.418</td><td>616.353</td><td>81.158</td><td>177.262</td><td>2.302</td><td>9.945</td><td>0.044</td><td>7.074</td><td>0.038</td></tr><tr><td>MixSmall1</td><td>10.356</td><td>1.137</td><td>2.038</td><td>0.042</td><td>11.855</td><td>0.824</td><td>1.266</td><td>0.021</td><td>227.003</td><td>9.311</td><td>31.719</td><td>0.944</td><td>2.887</td><td>0.004</td><td>2.572</td><td>0.011</td></tr><tr><td>MixSmall2</td><td>54.298</td><td>11.138</td><td>6.528</td><td>0.140</td><td>46.100</td><td>1.544</td><td>4.892</td><td>0.646</td><td>544.662</td><td>77.890</td><td>139.102</td><td>4.347</td><td>9.112</td><td>0.070</td><td>5.603</td><td>0.046</td></tr><tr><td>MixSmall3</td><td>90.402</td><td>9.046</td><td>11.934</td><td>0.188</td><td>173.702</td><td>75.256</td><td>8.875</td><td>0.303</td><td>762.134</td><td>181.823</td><td>291.226</td><td>7.313</td><td>13.905</td><td>0.043</td><td>8.832</td><td>0.034</td></tr><tr><td>Average mean(Artificial)</td><td>53.062</td><td>8.535</td><td>7.893</td><td>0.280</td><td>153.105</td><td>68.133</td><td>5.052</td><td>0.269</td><td>615.279</td><td>64.096</td><td>165.945</td><td>5.871</td><td>9.989</td><td>0.607</td><td>6.947</td><td>0.308</td></tr><tr><td>Outdoor</td><td>0.062</td><td>&lt;1e-4</td><td>1.026</td><td>0.030</td><td>0.312</td><td>&lt;1e-4</td><td>0.821</td><td>0.009</td><td>4.584</td><td>1.552</td><td>10.977</td><td>0.176</td><td>0.972</td><td>0.015</td><td>1.085</td><td>0.006</td></tr><tr><td>Gassenor</td><td>22.957</td><td>2.199</td><td>3.475</td><td>0.046</td><td>19.527</td><td>1.609</td><td>2.107</td><td>0.046</td><td>335.529</td><td>21.115</td><td>225.419</td><td>8.425</td><td>3.443</td><td>0.045</td><td>3.243</td><td>0.158</td></tr><tr><td>IGBN</td><td>0.743</td><td>0.006</td><td>0.685</td><td>0.037</td><td>34.408</td><td>3.658</td><td>3.480</td><td>0.150</td><td>422.940</td><td>131.530</td><td>161.536</td><td>2.347</td><td>9.125</td><td>0.925</td><td>8.629</td><td>1.812</td></tr><tr><td>IABN</td><td>0.921</td><td>0.001</td><td>1.327</td><td>0.007</td><td>48.190.256</td><td>3384.368</td><td>15.942</td><td>0.300</td><td>974.319</td><td>0.373</td><td>687.564</td><td>21.508</td><td>21.413</td><td>2.743</td><td>17.525</td><td>3.143</td></tr><tr><td>Average mean(Real)</td><td>6.171</td><td>0.551</td><td>1.628</td><td>0.030</td><td>12.061.126</td><td>847.409</td><td>5.588</td><td>0.126</td><td>434.343</td><td>38.642</td><td>271.374</td><td>8.114</td><td>8.738</td><td>0.932</td><td>7.620</td><td>1.280</td></tr><tr><td>Total average mean</td><td>38.634</td><td>6.079</td><td>5.965</td><td>0.203</td><td>3817.111</td><td>307.910</td><td>5.217</td><td>0.225</td><td>559.607</td><td>56.264</td><td>198.384</td><td>6.561</td><td>9.604</td><td>0.707</td><td>7.154</td><td>0.607</td></tr></tbody></table>

<figure><img src="image_21.png" /><figcaption>**Fig. 17.** Trade-off — Mean values of ARI (left), Purity (center) and NMI (right) for static experiments — Small datasets (Artificial).</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>**Fig. 18.** Trade-off — Mean values of ARI (left), Purity (center) and NMI (right) for static experiments — Small datasets (Real).</figcaption></figure>

dataset size is non-linear. This contrasts with other algorithms, such as K-means, where performance is more stable. As a result, the proposed framework may not fully benefit from the decomposition when using KASP or similar algorithms, as their instability on smaller subsets may lead to less accurate clustering despite a better computation time.

The second case is visible in the slightly suboptimal results obtained on the Circle20 dataset. Its artificial clusters have the shape of circles, a highly non-convex shape with a hole in the center. The cluster distributions estimated from univariate distribution models based on random projections do not correctly capture the real distribution. In particular, the central hole can never be modeled from a univariate projection. This leads to a loss of structural information present in the original distribution. Since the clustering process is based on these projections, any bias introduced by the projection can negatively affect the efficiency of the final clustering process. This is obviously an extreme case, as most distributions can be reliably modeled using random projections.

The trade-off results in Figs. 19 and 20 confirm the efficiency of the proposed framework (except, again, for KASP according to the ARI index, while the trade-off is better according to the Purity and NMI). Overall, the proposed framework significantly accelerates the clustering process for both real and artificial datasets without compromising quality, proving to be effective across different clustering algorithms and offering great flexibility on massive datasets.

### 4.5.2. *Experiments on dynamic datasets*

To evaluate our approach on dynamic datasets, we compared it with traditional methods such as CluStream and DenStream (discussed in Section 1) and two methods from the Python package River [48]: SequentialK-means (a mini-batch K-means variant with a parameter *halflife* that shifts cluster centers toward more recent observations) and StreamK-means (a STREAMLSEARCH variant that uses incremental K-means for efficiency). CluStream and DenStream were implemented based on their respective papers. For our approaches, we chose HDBSCAN and K-means as conventional clustering in each window, and named it HistStream(HDBSCAN) and HistStream(K-means)
<table><caption>**Table 8**
ARI results of static experiments — Large datasets.</caption><thead><tr><th rowspan="3">Datasets</th><th colspan="4">KMeans</th><th colspan="4">GaussianMixture</th><th colspan="4">HDBSCAN</th><th colspan="4">KASP</th></tr><tr><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th></tr><tr><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th></tr></thead><tbody><tr><td>Comet20</td><td>1.000</td><td>&lt;1e-4</td><td>0.931</td><td>&lt;1e-4</td><td>0.979</td><td>0.015</td><td>0.932</td><td>0.014</td><td>0.300</td><td>&lt;1e-4</td><td>0.936</td><td>&lt;1e-4</td><td>0.541</td><td>0.071</td><td>0.206</td><td>0.011</td></tr><tr><td>Meteroit20</td><td>1.000</td><td>&lt;1e-4</td><td>0.987</td><td>&lt;1e-4</td><td>0.998</td><td>0.002</td><td>0.963</td><td>0.017</td><td>0.741</td><td>&lt;1e-4</td><td>0.948</td><td>&lt;1e-4</td><td>0.477</td><td>0.119</td><td>0.324</td><td>0.011</td></tr><tr><td>Circle20</td><td>1.000</td><td>&lt;1e-4</td><td>0.765</td><td>0.001</td><td>0.911</td><td>&lt;1e-4</td><td>0.779</td><td>0.012</td><td>0.140</td><td>&lt;1e-4</td><td>0.906</td><td>&lt;1e-4</td><td>0.510</td><td>0.126</td><td>0.176</td><td>0.012</td></tr><tr><td>Gaussian20</td><td>1.000</td><td>&lt;1e-4</td><td>0.974</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.978</td><td>0.004</td><td>0.909</td><td>&lt;1e-4</td><td>0.982</td><td>&lt;1e-4</td><td>0.625</td><td>0.042</td><td>0.277</td><td>0.017</td></tr><tr><td>Square20</td><td>1.000</td><td>&lt;1e-4</td><td>0.984</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.945</td><td>0.011</td><td>0.634</td><td>&lt;1e-4</td><td>0.963</td><td>&lt;1e-4</td><td>0.631</td><td>0.059</td><td>0.348</td><td>0.052</td></tr><tr><td>Moon20</td><td>1.000</td><td>&lt;1e-4</td><td>0.975</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.972</td><td>0.005</td><td>0.269</td><td>&lt;1e-4</td><td>0.964</td><td>&lt;1e-4</td><td>0.304</td><td>0.038</td><td>0.314</td><td>0.013</td></tr><tr><td>MixLarge10</td><td>1.000</td><td>&lt;1e-4</td><td>0.976</td><td>0.001</td><td>0.993</td><td>0.005</td><td>0.932</td><td>0.013</td><td>0.466</td><td>&lt;1e-4</td><td>0.975</td><td>&lt;1e-4</td><td>0.548</td><td>0.087</td><td>0.317</td><td>0.017</td></tr><tr><td>MixLarge20</td><td>0.936</td><td>0.002</td><td>0.883</td><td>0.005</td><td>0.940</td><td>0.003</td><td>0.864</td><td>0.010</td><td>0.187</td><td>&lt;1e-4</td><td>0.979</td><td>&lt;1e-4</td><td>0.535</td><td>0.031</td><td>0.468</td><td>0.010</td></tr><tr><td>MixLarge50</td><td>0.948</td><td>&lt;1e-4</td><td>0.855</td><td>0.004</td><td>0.926</td><td>0.009</td><td>0.792</td><td>0.004</td><td>0.177</td><td>&lt;1e-4</td><td>0.948</td><td>&lt;1e-4</td><td>0.420</td><td>0.086</td><td>0.336</td><td>0.013</td></tr><tr><td>Average mean(Artificial)</td><td>0.987</td><td>0.000</td><td>0.926</td><td>0.001</td><td>0.972</td><td>0.004</td><td>0.906</td><td>0.010</td><td>0.425</td><td>&lt;1e-4</td><td>0.956</td><td>&lt;1e-4</td><td>0.510</td><td>0.073</td><td>0.307</td><td>0.017</td></tr><tr><td>Outdoor</td><td>0.411</td><td>0.008</td><td>0.454</td><td>0.012</td><td>0.432</td><td>&lt;1e-4</td><td>0.454</td><td>0.009</td><td>&lt;1e-4</td><td>&lt;1e-4</td><td>0.563</td><td>&lt;1e-4</td><td>0.300</td><td>0.019</td><td>0.360</td><td>0.016</td></tr><tr><td>Gassenor</td><td>0.138</td><td>&lt;1e-4</td><td>0.278</td><td>0.008</td><td>0.123</td><td>&lt;1e-4</td><td>0.306</td><td>0.011</td><td>0.383</td><td>&lt;1e-4</td><td>0.044</td><td>&lt;1e-4</td><td>0.174</td><td>0.013</td><td>0.282</td><td>0.011</td></tr><tr><td>IGBN</td><td>0.080</td><td>&lt;1e-4</td><td>0.217</td><td>0.009</td><td>0.166</td><td>&lt;1e-4</td><td>0.249</td><td>0.007</td><td>&lt;1e-4</td><td>&lt;1e-4</td><td>0.306</td><td>&lt;1e-4</td><td>0.086</td><td>0.012</td><td>0.200</td><td>0.011</td></tr><tr><td>IABN</td><td>0.100</td><td>0.018</td><td>0.078</td><td>0.001</td><td>0.262</td><td>&lt;1e-4</td><td>0.113</td><td>0.014</td><td>&lt;1e-4</td><td>&lt;1e-4</td><td>0.116</td><td>&lt;1e-4</td><td>0.091</td><td>0.003</td><td>0.090</td><td>0.012</td></tr><tr><td>Rialto</td><td>0.068</td><td>&lt;1e-4</td><td>0.063</td><td>0.002</td><td>0.058</td><td>&lt;1e-4</td><td>0.048</td><td>0.001</td><td>0.056</td><td>&lt;1e-4</td><td>0.081</td><td>&lt;1e-4</td><td>0.055</td><td>0.001</td><td>0.059</td><td>0.002</td></tr><tr><td>IIAIN</td><td>0.048</td><td>&lt;1e-4</td><td>0.021</td><td>0.001</td><td>0.299</td><td>&lt;1e-4</td><td>0.032</td><td>0.002</td><td>&lt;1e-4</td><td>&lt;1e-4</td><td>0.021</td><td>&lt;1e-4</td><td>0.064</td><td>0.003</td><td>0.019</td><td>0.001</td></tr><tr><td>IIRIN</td><td>0.049</td><td>&lt;1e-4</td><td>0.037</td><td>0.001</td><td>0.178</td><td>&lt;1e-4</td><td>0.057</td><td>0.001</td><td>&lt;1e-4</td><td>&lt;1e-4</td><td>0.073</td><td>&lt;1e-4</td><td>0.063</td><td>0.001</td><td>0.035</td><td>0.001</td></tr><tr><td>Covtype</td><td>0.014</td><td>&lt;1e-4</td><td>0.015</td><td>&lt;1e-4</td><td>0.020</td><td>&lt;1e-4</td><td>0.015</td><td>&lt;1e-4</td><td>&lt;1e-4</td><td>&lt;1e-4</td><td>0.023</td><td>&lt;1e-4</td><td>0.016</td><td>0.004</td><td>0.010</td><td>0.001</td></tr><tr><td>Average mean(Real)</td><td>0.113</td><td>0.003</td><td>0.145</td><td>0.004</td><td>0.192</td><td>&lt;1e-4</td><td>0.159</td><td>0.006</td><td>0.055</td><td>&lt;1e-4</td><td>0.153</td><td>&lt;1e-4</td><td>0.106</td><td>0.007</td><td>0.132</td><td>0.007</td></tr><tr><td>Total average mean</td><td>0.576</td><td>0.002</td><td>0.558</td><td>0.003</td><td>0.605</td><td>0.002</td><td>0.555</td><td>0.008</td><td>0.251</td><td>&lt;1e-4</td><td>0.578</td><td>&lt;1e-4</td><td>0.320</td><td>0.042</td><td>0.225</td><td>0.012</td></tr></tbody></table>

<table><caption>**Table 9**
Purity results of static experiments — Large datasets.</caption><thead><tr><th rowspan="3">Datasets</th><th colspan="4">KMeans</th><th colspan="4">GaussianMixture</th><th colspan="4">HDBSCAN</th><th colspan="4">KASP</th></tr><tr><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th></tr><tr><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th></tr></thead><tbody><tr><td>Comet20</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.760</td><td>0.040</td><td>0.873</td><td>0.006</td></tr><tr><td>Meteroit20</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.618</td><td>0.060</td><td>0.748</td><td>0.004</td></tr><tr><td>Circle20</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.749</td><td>0.044</td><td>0.844</td><td>0.005</td></tr><tr><td>Gaussian20</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.705</td><td>0.029</td><td>0.761</td><td>0.010</td></tr><tr><td>Square20</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.706</td><td>0.028</td><td>0.788</td><td>0.010</td></tr><tr><td>Moon20</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.432</td><td>0.036</td><td>0.650</td><td>0.010</td></tr><tr><td>MixLarge10</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.999</td><td>0.001</td><td>0.999</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.705</td><td>0.052</td><td>0.775</td><td>0.014</td></tr><tr><td>MixLarge20</td><td>1.000</td><td>&lt;1e-4</td><td>0.999</td><td>&lt;1e-4</td><td>0.999</td><td>0.001</td><td>0.999</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.613</td><td>0.023</td><td>0.760</td><td>0.010</td></tr><tr><td>MixLarge50</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.999</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.682</td><td>0.043</td><td>0.705</td><td>0.011</td></tr><tr><td>Average mean(Artificial)</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>0.000</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.663</td><td>0.039</td><td>0.767</td><td>0.009</td></tr><tr><td>Outdoor</td><td>0.573</td><td>0.001</td><td>0.655</td><td>0.004</td><td>0.589</td><td>&lt;1e-4</td><td>0.672</td><td>0.007</td><td>0.053</td><td>&lt;1e-4</td><td>0.877</td><td>&lt;1e-4</td><td>0.432</td><td>0.011</td><td>0.539</td><td>0.018</td></tr><tr><td>Gassenor</td><td>0.430</td><td>0.001</td><td>0.668</td><td>0.001</td><td>0.394</td><td>&lt;1e-4</td><td>0.727</td><td>0.003</td><td>0.835</td><td>&lt;1e-4</td><td>0.987</td><td>&lt;1e-4</td><td>0.458</td><td>0.002</td><td>0.688</td><td>0.002</td></tr><tr><td>IGBN</td><td>0.326</td><td>&lt;1e-4</td><td>0.611</td><td>0.005</td><td>0.409</td><td>&lt;1e-4</td><td>0.688</td><td>0.009</td><td>0.284</td><td>&lt;1e-4</td><td>0.554</td><td>&lt;1e-4</td><td>0.332</td><td>0.016</td><td>0.611</td><td>0.026</td></tr><tr><td>IABN</td><td>0.335</td><td>0.016</td><td>0.458</td><td>0.001</td><td>0.455</td><td>&lt;1e-4</td><td>0.544</td><td>0.008</td><td>0.230</td><td>&lt;1e-4</td><td>0.300</td><td>&lt;1e-4</td><td>0.331</td><td>0.002</td><td>0.442</td><td>0.003</td></tr><tr><td>Rialto</td><td>0.224</td><td>&lt;1e-4</td><td>0.331</td><td>&lt;1e-4</td><td>0.205</td><td>&lt;1e-4</td><td>0.295</td><td>0.002</td><td>0.824</td><td>&lt;1e-4</td><td>0.335</td><td>&lt;1e-4</td><td>0.217</td><td>0.004</td><td>0.318</td><td>0.004</td></tr><tr><td>IIAIN</td><td>0.382</td><td>&lt;1e-4</td><td>0.439</td><td>0.001</td><td>0.660</td><td>&lt;1e-4</td><td>0.563</td><td>0.013</td><td>0.298</td><td>&lt;1e-4</td><td>0.402</td><td>&lt;1e-4</td><td>0.423</td><td>0.005</td><td>0.445</td><td>0.003</td></tr><tr><td>IIRIN</td><td>0.382</td><td>&lt;1e-4</td><td>0.499</td><td>0.002</td><td>0.530</td><td>&lt;1e-4</td><td>0.619</td><td>0.009</td><td>0.298</td><td>&lt;1e-4</td><td>0.524</td><td>&lt;1e-4</td><td>0.420</td><td>0.004</td><td>0.518</td><td>0.002</td></tr><tr><td>Covtype</td><td>0.484</td><td>&lt;1e-4</td><td>0.631</td><td>&lt;1e-4</td><td>0.480</td><td>&lt;1e-4</td><td>0.617</td><td>&lt;1e-4</td><td>0.474</td><td>&lt;1e-4</td><td>0.555</td><td>&lt;1e-4</td><td>0.489</td><td>0.004</td><td>0.535</td><td>0.002</td></tr><tr><td>Average mean(Real)</td><td>0.392</td><td>0.002</td><td>0.536</td><td>0.002</td><td>0.465</td><td>&lt;1e-4</td><td>0.591</td><td>0.006</td><td>0.412</td><td>&lt;1e-4</td><td>0.567</td><td>&lt;1e-4</td><td>0.388</td><td>0.006</td><td>0.512</td><td>0.007</td></tr><tr><td>Total average mean</td><td>0.714</td><td>0.001</td><td>0.782</td><td>0.001</td><td>0.748</td><td>0.000</td><td>0.807</td><td>0.003</td><td>0.723</td><td>&lt;1e-4</td><td>0.796</td><td>&lt;1e-4</td><td>0.534</td><td>0.024</td><td>0.647</td><td>0.008</td></tr></tbody></table>

<table><caption>**Table 10**
NMI results of static experiments — Large datasets.</caption><thead><tr><th rowspan="3">Datasets</th><th colspan="4">KMeans</th><th colspan="4">GaussianMixture</th><th colspan="4">HDBSCAN</th><th colspan="4">KASP</th></tr><tr><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th></tr><tr><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th></tr></thead><tbody><tr><td>Comet20</td><td>1.000</td><td>&lt;1e-4</td><td>0.975</td><td>&lt;1e-4</td><td>0.995</td><td>0.003</td><td>0.977</td><td>0.004</td><td>0.730</td><td>&lt;1e-4</td><td>0.979</td><td>&lt;1e-4</td><td>0.847</td><td>0.016</td><td>0.723</td><td>0.005</td></tr><tr><td>Meteroit20</td><td>1.000</td><td>&lt;1e-4</td><td>0.992</td><td>&lt;1e-4</td><td>0.999</td><td>0.001</td><td>0.981</td><td>0.005</td><td>0.863</td><td>&lt;1e-4</td><td>0.981</td><td>&lt;1e-4</td><td>0.806</td><td>0.044</td><td>0.711</td><td>0.003</td></tr><tr><td>Circle20</td><td>1.000</td><td>&lt;1e-4</td><td>0.947</td><td>&lt;1e-4</td><td>0.987</td><td>&lt;1e-4</td><td>0.941</td><td>0.005</td><td>0.673</td><td>&lt;1e-4</td><td>0.939</td><td>&lt;1e-4</td><td>0.825</td><td>0.029</td><td>0.696</td><td>0.004</td></tr><tr><td>Gaussian20</td><td>1.000</td><td>&lt;1e-4</td><td>0.989</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.989</td><td>0.002</td><td>0.885</td><td>&lt;1e-4</td><td>0.991</td><td>&lt;1e-4</td><td>0.864</td><td>0.011</td><td>0.714</td><td>0.006</td></tr><tr><td>Square20</td><td>1.000</td><td>&lt;1e-4</td><td>0.990</td><td>0.001</td><td>1.000</td><td>&lt;1e-4</td><td>0.981</td><td>0.004</td><td>0.767</td><td>&lt;1e-4</td><td>0.987</td><td>&lt;1e-4</td><td>0.863</td><td>0.016</td><td>0.715</td><td>0.006</td></tr><tr><td>Moon20</td><td>1.000</td><td>&lt;1e-4</td><td>0.990</td><td>&lt;1e-4</td><td>1.000</td><td>&lt;1e-4</td><td>0.986</td><td>0.001</td><td>0.732</td><td>&lt;1e-4</td><td>0.986</td><td>&lt;1e-4</td><td>0.744</td><td>0.026</td><td>0.683</td><td>0.007</td></tr><tr><td>MixLarge10</td><td>1.000</td><td>&lt;1e-4</td><td>0.984</td><td>0.001</td><td>0.997</td><td>0.002</td><td>0.967</td><td>0.005</td><td>0.808</td><td>&lt;1e-4</td><td>0.984</td><td>&lt;1e-4</td><td>0.834</td><td>0.035</td><td>0.711</td><td>0.008</td></tr><tr><td>MixLarge20</td><td>0.988</td><td>&lt;1e-4</td><td>0.965</td><td>0.001</td><td>0.989</td><td>0.001</td><td>0.960</td><td>0.003</td><td>0.716</td><td>&lt;1e-4</td><td>0.984</td><td>&lt;1e-4</td><td>0.837</td><td>0.014</td><td>0.751</td><td>0.006</td></tr><tr><td>MixLarge50</td><td>0.994</td><td>&lt;1e-4</td><td>0.964</td><td>0.001</td><td>0.989</td><td>0.002</td><td>0.944</td><td>0.002</td><td>0.718</td><td>&lt;1e-4</td><td>0.978</td><td>&lt;1e-4</td><td>0.851</td><td>0.022</td><td>0.714</td><td>0.003</td></tr><tr><td>Average mean(Artificial)</td><td>0.998</td><td>&lt;1e-4</td><td>0.977</td><td>0.000</td><td>0.995</td><td>0.001</td><td>0.970</td><td>0.003</td><td>0.766</td><td>&lt;1e-4</td><td>0.979</td><td>&lt;1e-4</td><td>0.830</td><td>0.024</td><td>0.713</td><td>0.005</td></tr><tr><td>Outdoor</td><td>0.708</td><td>0.002</td><td>0.733</td><td>0.005</td><td>0.736</td><td>&lt;1e-4</td><td>0.748</td><td>0.002</td><td>&lt;1e-4</td><td>&lt;1e-4</td><td>0.813</td><td>&lt;1e-4</td><td>0.626</td><td>0.006</td><td>0.674</td><td>0.007</td></tr><tr><td>Gassenor</td><td>0.284</td><td>&lt;1e-4</td><td>0.484</td><td>0.009</td><td>0.239</td><td>&lt;1e-4</td><td>0.520</td><td>0.007</td><td>0.649</td><td>&lt;1e-4</td><td>0.459</td><td>&lt;1e-4</td><td>0.309</td><td>0.005</td><td>0.489</td><td>0.005</td></tr><tr><td>IGBN</td><td>0.127</td><td>0.001</td><td>0.397</td><td>0.007</td><td>0.275</td><td>&lt;1e-4</td><td>0.460</td><td>0.004</td><td>&lt;1e-4</td><td>&lt;1e-4</td><td>0.457</td><td>&lt;1e-4</td><td>0.135</td><td>0.008</td><td>0.395</td><td>0.015</td></tr><tr><td>IABN</td><td>0.132</td><td>0.008</td><td>0.217</td><td>&lt;1e-4</td><td>0.335</td><td>&lt;1e-4</td><td>0.287</td><td>0.004</td><td>&lt;1e-4</td><td>&lt;1e-4</td><td>0.216</td><td>&lt;1e-4</td><td>0.124</td><td>0.002</td><td>0.212</td><td>0.002</td></tr><tr><td>Rialto</td><td>0.155</td><td>&lt;1e-4</td><td>0.205</td><td>0.001</td><td>0.133</td><td>&lt;1e-4</td><td>0.185</td><td>0.001</td><td>0.406</td><td>&lt;1e-4</td><td>0.241</td><td>&lt;1e-4</td><td>0.155</td><td>0.005</td><td>0.203</td><td>0.002</td></tr><tr><td>IIAIN</td><td>0.084</td><td>&lt;1e-4</td><td>0.101</td><td>0.001</td><td>0.345</td><td>&lt;1e-4</td><td>0.173</td><td>0.004</td><td>&lt;1e-4</td><td>&lt;1e-4</td><td>0.073</td><td>&lt;1e-4</td><td>0.097</td><td>0.004</td><td>0.094</td><td>0.002</td></tr><tr><td>IIRIN</td><td>0.084</td><td>&lt;1e-4</td><td>0.140</td><td>0.002</td><td>0.247</td><td>&lt;1e-4</td><td>0.212</td><td>0.005</td><td>&lt;1e-4</td><td>&lt;1e-4</td><td>0.173</td><td>&lt;1e-4</td><td>0.092</td><td>0.006</td><td>0.141</td><td>0.002</td></tr><tr><td>Covtype</td><td>0.063</td><td>&lt;1e-4</td><td>0.141</td><td>&lt;1e-4</td><td>0.033</td><td>&lt;1e-4</td><td>0.134</td><td>&lt;1e-4</td><td>&lt;1e-4</td><td>&lt;1e-4</td><td>0.100</td><td>&lt;1e-4</td><td>0.060</td><td>0.002</td><td>0.069</td><td>0.001</td></tr><tr><td>Average mean(Real)</td><td>0.205</td><td>0.001</td><td>0.302</td><td>0.003</td><td>0.293</td><td>&lt;1e-4</td><td>0.340</td><td>0.003</td><td>0.132</td><td>&lt;1e-4</td><td>0.317</td><td>&lt;1e-4</td><td>0.200</td><td>0.005</td><td>0.285</td><td>0.005</td></tr><tr><td>Total average mean</td><td>0.625</td><td>0.001</td><td>0.660</td><td>0.002</td><td>0.665</td><td>0.001</td><td>0.673</td><td>0.003</td><td>0.467</td><td>&lt;1e-4</td><td>0.667</td><td>&lt;1e-4</td><td>0.533</td><td>0.015</td><td>0.511</td><td>0.005</td></tr></tbody></table>
<table><caption>**Table 11**

Computation time of static experiments — Large datasets.</caption><thead><tr><th rowspan="3">Datasets</th><th colspan="4">KMeans</th><th colspan="4">GaussianMixture</th><th colspan="4">HDBSCAN</th><th colspan="4">KASP</th></tr><tr><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th><th colspan="2">Original</th><th colspan="2">Proposed</th></tr><tr><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th></tr></thead><tbody><tr><td>Comet20</td><td>23.734</td><td>2.791</td><td>19.337</td><td>1.458</td><td>222.994</td><td>78.158</td><td>65.818</td><td>7.758</td><td>4213.044</td><td>171.537</td><td>214.139</td><td>13.723</td><td>44.895</td><td>4.278</td><td>35.147</td><td>0.149</td></tr><tr><td>Meteroid20</td><td>24.148</td><td>1.002</td><td>18.958</td><td>0.441</td><td>132.950</td><td>34.525</td><td>85.222</td><td>13.100</td><td>4406.303</td><td>56.387</td><td>222.485</td><td>14.603</td><td>59.371</td><td>2.900</td><td>34.722</td><td>0.230</td></tr><tr><td>Circle20</td><td>16.433</td><td>1.387</td><td>20.670</td><td>0.554</td><td>113.119</td><td>2.273</td><td>104.328</td><td>13.320</td><td>3383.867</td><td>187.844</td><td>289.187</td><td>1.569</td><td>45.265</td><td>1.233</td><td>43.100</td><td>3.870</td></tr><tr><td>Gaussian20</td><td>23.563</td><td>0.489</td><td>14.661</td><td>0.249</td><td>115.247</td><td>1.359</td><td>58.952</td><td>5.740</td><td>3979.659</td><td>184.060</td><td>144.848</td><td>1.269</td><td>54.484</td><td>1.281</td><td>41.287</td><td>1.863</td></tr><tr><td>Square20</td><td>34.939</td><td>1.601</td><td>13.419</td><td>0.436</td><td>115.244</td><td>1.931</td><td>57.755</td><td>7.963</td><td>5379.374</td><td>519.370</td><td>153.297</td><td>2.101</td><td>47.494</td><td>0.984</td><td>39.315</td><td>2.496</td></tr><tr><td>Moon20</td><td>27.831</td><td>4.163</td><td>12.889</td><td>0.304</td><td>114.948</td><td>1.686</td><td>44.908</td><td>1.449</td><td>3994.732</td><td>237.748</td><td>142.009</td><td>2.100</td><td>41.096</td><td>0.809</td><td>32.762</td><td>0.108</td></tr><tr><td>MixLarge10</td><td>18.324</td><td>3.399</td><td>14.327</td><td>0.363</td><td>72.196</td><td>5.959</td><td>42.049</td><td>6.500</td><td>1205.131</td><td>74.827</td><td>49.496</td><td>0.889</td><td>18.909</td><td>0.328</td><td>23.478</td><td>0.196</td></tr><tr><td>MixLarge20</td><td>50.899</td><td>1.612</td><td>26.494</td><td>2.309</td><td>391.995</td><td>121.818</td><td>130.698</td><td>16.686</td><td>5014.705</td><td>408.986</td><td>191.287</td><td>4.018</td><td>56.267</td><td>3.025</td><td>39.175</td><td>0.879</td></tr><tr><td>MixLarge50</td><td>95.487</td><td>27.448</td><td>79.692</td><td>5.588</td><td>1076.031</td><td>390.764</td><td>812.565</td><td>88.755</td><td>18195.626</td><td>4904.393</td><td>787.725</td><td>55.214</td><td>245.408</td><td>19.075</td><td>112.379</td><td>1.000</td></tr><tr><td>Average mean(Artificial)</td><td>35.040</td><td>4.877</td><td>24.494</td><td>1.300</td><td>261.636</td><td>70.941</td><td>155.811</td><td>17.919</td><td>5530.271</td><td>749.461</td><td>243.830</td><td>10.610</td><td>68.132</td><td>3.768</td><td>44.596</td><td>1.199</td></tr><tr><td>Outdoor</td><td>0.302</td><td>0.007</td><td>1.035</td><td>0.049</td><td>0.766</td><td>0.013</td><td>1.928</td><td>0.174</td><td>0.266</td><td>0.013</td><td>2.995</td><td>0.087</td><td>0.340</td><td>0.007</td><td>0.714</td><td>0.015</td></tr><tr><td>Gassenor</td><td>0.406</td><td>0.066</td><td>0.557</td><td>0.013</td><td>19.528</td><td>1.907</td><td>4.792</td><td>0.605</td><td>16.792</td><td>0.332</td><td>71.868</td><td>1.691</td><td>2.168</td><td>0.276</td><td>2.001</td><td>0.040</td></tr><tr><td>IGBN</td><td>0.507</td><td>0.017</td><td>1.192</td><td>0.078</td><td>5.265</td><td>2.509</td><td>2.424</td><td>0.422</td><td>12.455</td><td>2.896</td><td>5.787</td><td>0.116</td><td>2.554</td><td>0.102</td><td>2.565</td><td>0.054</td></tr><tr><td>IABN</td><td>0.989</td><td>0.181</td><td>1.690</td><td>0.031</td><td>15.504</td><td>1.708</td><td>11.095</td><td>0.324</td><td>35.226</td><td>2.451</td><td>17.093</td><td>0.020</td><td>7.354</td><td>0.315</td><td>5.927</td><td>0.264</td></tr><tr><td>Rialto</td><td>2.737</td><td>0.374</td><td>3.271</td><td>0.034</td><td>14.258</td><td>1.003</td><td>14.315</td><td>1.294</td><td>12.315</td><td>0.132</td><td>10.889</td><td>0.287</td><td>11.539</td><td>0.900</td><td>12.881</td><td>0.284</td></tr><tr><td>IIAIN</td><td>11.121</td><td>0.706</td><td>15.691</td><td>1.426</td><td>262.002</td><td>2.598</td><td>220.794</td><td>25.076</td><td>2503.787</td><td>263.043</td><td>367.586</td><td>38.623</td><td>168.647</td><td>7.423</td><td>72.061</td><td>3.659</td></tr><tr><td>IIRIN</td><td>30.035</td><td>2.565</td><td>15.250</td><td>1.923</td><td>292.251</td><td>9.682</td><td>192.213</td><td>15.150</td><td>2871.159</td><td>13.816</td><td>353.679</td><td>11.625</td><td>175.862</td><td>9.507</td><td>66.223</td><td>1.020</td></tr><tr><td>Covtype</td><td>12.711</td><td>1.346</td><td>6.836</td><td>0.261</td><td>88.757</td><td>1.030</td><td>28.667</td><td>0.561</td><td>3187.865</td><td>138.144</td><td>102.875</td><td>3.611</td><td>177.251</td><td>14.071</td><td>79.992</td><td>2.320</td></tr><tr><td>Average mean(Real)</td><td>7.351</td><td>0.658</td><td>5.690</td><td>0.477</td><td>87.291</td><td>2.556</td><td>59.529</td><td>5.451</td><td>1079.983</td><td>52.603</td><td>116.596</td><td>7.008</td><td>68.214</td><td>4.075</td><td>30.296</td><td>0.957</td></tr><tr><td>Total average mean</td><td>22.010</td><td>2.891</td><td>15.645</td><td>0.913</td><td>179.591</td><td>38.760</td><td>110.501</td><td>12.052</td><td>3436.018</td><td>421.528</td><td>183.956</td><td>8.914</td><td>68.171</td><td>3.913</td><td>37.866</td><td>1.085</td></tr></tbody></table>

<figure><img src="image_23.png" /><figcaption>**Fig. 19.** Trade-off — Mean values of ARI (left), Purity (center) and NMI (right) for static experiments — Large datasets (Artificial).</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>**Fig. 20.** Trade-off — Mean values of ARI (left), Purity (center) and NMI (right) for static experiments — Large datasets (Real).</figcaption></figure>

for comparison with partition-based methods such as SequentialK-means, StreamK-means, and CluStream, and density-based clustering DenStream, respectively. The parameter settings were the same as in the static experiments, but the window size was defined by fixed time intervals instead of a fixed number of data points, which allows more flexibility in dynamic scenarios.

The results of ARI, NMI, Purity and Computation time are stored in Tables 12, 13, 14 and 15. Similar to the previous experimental section, to gain a more complete understanding of the overall performance differences between the algorithms, we computed the mean value of each index for each approach, separated into artificial datasets and real datasets. The results from both artificial and real datasets provide compelling evidence of the superiority of HistStream(K-means) over other algorithms in terms of clustering quality across multiple scenarios, consistently maintaining competitive performance. Similarly, HistStream(HDBSCAN) consistently achieves better clustering quality

than DenStream. It is also faster than DenStream on high-dimensional datasets, which is particularly evident here with the artificial dataset, while DenStream appears to be faster than HistStream(HDBSCAN) on lower-dimensional datasets. Another interesting observation is that the stability of DenStream seems to be worse, especially when dealing with larger datasets, compared to the consistent performance of HistStream(HDBSCAN).

The results presented in terms of trade-off between clustering evaluation index and computation time (seen in Figs. 21 and 22) clearly highlight the better performance of the proposed approach over other algorithms in terms of clustering quality, without any significant compromise in computational efficiency. In particular, HistStream(K-means) exhibits significantly faster running time compared to both SequentialK-means and StreamK-means, while still being slightly faster than CluStream. Moreover, interestingly, the application of the proposed framework with HDBSCAN and K-means reveals noticeable differences. These differences highlight the distinct advantages of each
<table><caption>**Table 12**
ARI results of dynamic experiments.</caption><thead><tr><th rowspan="2">Datasets</th><th colspan="2">SequentialKmeans</th><th colspan="2">StreamKmeans</th><th colspan="2">CluStream</th><th colspan="4">HistStream</th><th colspan="2">DenStream</th></tr><tr><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th colspan="2">Kmeans</th><th colspan="2">HDBSCAN</th><th>mean</th><th>std</th></tr></thead><tbody><tr><td>Comet20</td><td>0.7955</td><td>&lt;1e-4</td><td>0.6770</td><td>0.0005</td><td>0.8516</td><td>0.0107</td><td>0.9713</td><td>&lt;1e-4</td><td>0.9321</td><td>&lt;1e-4</td><td>0.9537</td><td>&lt;1e-4</td></tr><tr><td>Meteroit20</td><td>0.8112</td><td>&lt;1e-4</td><td>0.6125</td><td>0.0034</td><td>0.8713</td><td>0.0021</td><td>0.9559</td><td>0.0002</td><td>0.9330</td><td>&lt;1e-4</td><td>0.8531</td><td>&lt;1e-4</td></tr><tr><td>Circle20</td><td>0.8849</td><td>&lt;1e-4</td><td>0.7163</td><td>0.0027</td><td>0.8174</td><td>0.0452</td><td>0.8399</td><td>&lt;1e-4</td><td>0.9508</td><td>&lt;1e-4</td><td>0.8059</td><td>&lt;1e-4</td></tr><tr><td>Gaussian20</td><td>0.9999</td><td>&lt;1e-4</td><td>0.9996</td><td>&lt;1e-4</td><td>0.8892</td><td>0.0049</td><td>0.9690</td><td>0.0008</td><td>0.9798</td><td>&lt;1e-4</td><td>0.7939</td><td>&lt;1e-4</td></tr><tr><td>Square20</td><td>0.9412</td><td>&lt;1e-4</td><td>0.7284</td><td>0.0058</td><td>0.9507</td><td>0.0001</td><td>0.9784</td><td>&lt;1e-4</td><td>0.9901</td><td>&lt;1e-4</td><td>0.9452</td><td>&lt;1e-4</td></tr><tr><td>Moon20</td><td>0.8476</td><td>&lt;1e-4</td><td>0.5151</td><td>0.0091</td><td>0.8572</td><td>0.0080</td><td>0.9741</td><td>&lt;1e-4</td><td>0.9440</td><td>&lt;1e-4</td><td>0.9907</td><td>&lt;1e-4</td></tr><tr><td>MixLarge10</td><td>0.8324</td><td>&lt;1e-4</td><td>0.7487</td><td>0.0103</td><td>0.9236</td><td>0.0259</td><td>0.9566</td><td>0.0062</td><td>0.9823</td><td>&lt;1e-4</td><td>0.8750</td><td>&lt;1e-4</td></tr><tr><td>MixLarge20</td><td>0.9369</td><td>&lt;1e-4</td><td>0.8850</td><td>0.0016</td><td>0.8841</td><td>0.0215</td><td>0.8850</td><td>0.0038</td><td>0.9621</td><td>&lt;1e-4</td><td>0.9104</td><td>&lt;1e-4</td></tr><tr><td>MixLarge50</td><td>0.8576</td><td>&lt;1e-4</td><td>0.8507</td><td>0.0022</td><td>0.0036</td><td>&lt;1e-4</td><td>0.8696</td><td>0.0025</td><td>0.9544</td><td>&lt;1e-4</td><td>0.8750</td><td>&lt;1e-4</td></tr><tr><td>Average mean(Artificial)</td><td>0.8786</td><td>&lt;1e-4</td><td>0.7481</td><td>0.0040</td><td>0.7832</td><td>0.0132</td><td>0.9333</td><td>0.0015</td><td>0.9587</td><td>&lt;1e-4</td><td>0.8892</td><td>&lt;1e-4</td></tr><tr><td>Outdoor</td><td>0.0909</td><td>&lt;1e-4</td><td>0.0477</td><td>0.0027</td><td>0.3670</td><td>0.0052</td><td>0.4500</td><td>&lt;1e-4</td><td>0.5843</td><td>&lt;1e-4</td><td>0.1301</td><td>&lt;1e-4</td></tr><tr><td>Gassenor</td><td>0.0385</td><td>&lt;1e-4</td><td>0.0425</td><td>&lt;1e-4</td><td>0.0588</td><td>0.0002</td><td>0.4020</td><td>0.0001</td><td>0.8362</td><td>&lt;1e-4</td><td>0.1978</td><td>&lt;1e-4</td></tr><tr><td>IGBN</td><td>0.0101</td><td>&lt;1e-4</td><td>0.2069</td><td>0.0892</td><td>0.0406</td><td>0.0023</td><td>0.2076</td><td>&lt;1e-4</td><td>0.3301</td><td>&lt;1e-4</td><td>0.0839</td><td>&lt;1e-4</td></tr><tr><td>IABN</td><td>0.0046</td><td>&lt;1e-4</td><td>0.0605</td><td>0.0074</td><td>0.0545</td><td>0.0003</td><td>0.0698</td><td>0.0003</td><td>0.2430</td><td>&lt;1e-4</td><td>0.0714</td><td>&lt;1e-4</td></tr><tr><td>Rialto</td><td>0.0017</td><td>&lt;1e-4</td><td>0.0002</td><td>0.0001</td><td>0.0517</td><td>0.0036</td><td>0.0514</td><td>0.0002</td><td>0.0802</td><td>&lt;1e-4</td><td>0.0655</td><td>&lt;1e-4</td></tr><tr><td>IIAIN</td><td>&lt;1e-4</td><td>&lt;1e-4</td><td>0.0087</td><td>0.0043</td><td>0.0421</td><td>0.0077</td><td>0.0202</td><td>&lt;1e-4</td><td>0.0122</td><td>&lt;1e-4</td><td>0.0395</td><td>&lt;1e-4</td></tr><tr><td>IIIRIN</td><td>0.0016</td><td>&lt;1e-4</td><td>0.0195</td><td>0.0116</td><td>0.0331</td><td>0.0020</td><td>0.0331</td><td>0.0007</td><td>0.0318</td><td>&lt;1e-4</td><td>0.0259</td><td>&lt;1e-4</td></tr><tr><td>Covtype</td><td>0.0063</td><td>0.0034</td><td>0.0015</td><td>0.0004</td><td>0.0114</td><td>0.0009</td><td>0.0057</td><td>0.0015</td><td>0.0092</td><td>&lt;1e-4</td><td>&lt;1e-4</td><td>&lt;1e-4</td></tr><tr><td>Average mean(Real)</td><td>0.0192</td><td>0.0004</td><td>0.0484</td><td>0.0145</td><td>0.0824</td><td>0.0028</td><td>0.1550</td><td>0.0004</td><td>0.2659</td><td>&lt;1e-4</td><td>0.0768</td><td>&lt;1e-4</td></tr><tr><td>Total average mean</td><td>0.4742</td><td>0.0002</td><td>0.4189</td><td>0.0089</td><td>0.4534</td><td>0.0083</td><td>0.5670</td><td>0.0010</td><td>0.6327</td><td>&lt;1e-4</td><td>0.5069</td><td>&lt;1e-4</td></tr></tbody></table>

<table><caption>**Table 13**
Purity results of dynamic experiments.</caption><thead><tr><th rowspan="2">Datasets</th><th colspan="2">SequentialKmeans</th><th colspan="2">StreamKmeans</th><th colspan="2">CluStream</th><th colspan="4">HistStream</th><th colspan="2">DenStream</th></tr><tr><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th colspan="2">Kmeans</th><th colspan="2">HDBSCAN</th><th>mean</th><th>std</th></tr></thead><tbody><tr><td>Comet20</td><td>0.8709</td><td>&lt;1e-4</td><td>0.7531</td><td>0.0005</td><td>0.9627</td><td>0.0060</td><td>1.0000</td><td>&lt;1e-4</td><td>1.0000</td><td>&lt;1e-4</td><td>1.0000</td><td>&lt;1e-4</td></tr><tr><td>Meteroit20</td><td>0.8590</td><td>&lt;1e-4</td><td>0.6799</td><td>0.0069</td><td>0.9079</td><td>0.0043</td><td>1.0000</td><td>&lt;1e-4</td><td>0.9999</td><td>&lt;1e-4</td><td>1.0000</td><td>&lt;1e-4</td></tr><tr><td>Circle20</td><td>0.9549</td><td>&lt;1e-4</td><td>0.8063</td><td>0.0051</td><td>0.9206</td><td>0.0047</td><td>0.9998</td><td>&lt;1e-4</td><td>1.0000</td><td>&lt;1e-4</td><td>0.9998</td><td>&lt;1e-4</td></tr><tr><td>Gaussian20</td><td>1.0000</td><td>&lt;1e-4</td><td>0.9997</td><td>&lt;1e-4</td><td>0.9179</td><td>&lt;1e-4</td><td>1.0000</td><td>&lt;1e-4</td><td>1.0000</td><td>&lt;1e-4</td><td>0.8565</td><td>&lt;1e-4</td></tr><tr><td>Square20</td><td>0.9301</td><td>&lt;1e-4</td><td>0.7653</td><td>0.0141</td><td>0.9535</td><td>&lt;1e-4</td><td>0.9999</td><td>&lt;1e-4</td><td>1.0000</td><td>&lt;1e-4</td><td>0.9994</td><td>&lt;1e-4</td></tr><tr><td>Moon20</td><td>0.8918</td><td>&lt;1e-4</td><td>0.6072</td><td>0.0094</td><td>0.9181</td><td>0.0100</td><td>1.0000</td><td>&lt;1e-4</td><td>0.9998</td><td>&lt;1e-4</td><td>0.9950</td><td>&lt;1e-4</td></tr><tr><td>MixLarge10</td><td>0.8978</td><td>&lt;1e-4</td><td>0.8330</td><td>0.0089</td><td>0.9597</td><td>0.0088</td><td>0.9996</td><td>&lt;1e-4</td><td>1.0000</td><td>&lt;1e-4</td><td>0.9996</td><td>&lt;1e-4</td></tr><tr><td>MixLarge20</td><td>0.9347</td><td>&lt;1e-4</td><td>0.8736</td><td>0.0018</td><td>0.9437</td><td>0.0113</td><td>0.9998</td><td>&lt;1e-4</td><td>0.9998</td><td>&lt;1e-4</td><td>0.9992</td><td>&lt;1e-4</td></tr><tr><td>MixLarge50</td><td>0.9403</td><td>&lt;1e-4</td><td>0.9206</td><td>0.0024</td><td>0.1055</td><td>&lt;1e-4</td><td>0.9998</td><td>&lt;1e-4</td><td>0.9998</td><td>&lt;1e-4</td><td>0.9996</td><td>&lt;1e-4</td></tr><tr><td>Average mean(Artificial)</td><td>0.9199</td><td>&lt;1e-4</td><td>0.8043</td><td>0.0055</td><td>0.8433</td><td>0.0050</td><td>0.9999</td><td>&lt;1e-4</td><td>0.9999</td><td>&lt;1e-4</td><td>0.9832</td><td>&lt;1e-4</td></tr><tr><td>Outdoor</td><td>0.2031</td><td>&lt;1e-4</td><td>0.1724</td><td>0.0015</td><td>0.5004</td><td>0.0133</td><td>0.6786</td><td>&lt;1e-4</td><td>0.8928</td><td>&lt;1e-4</td><td>0.1969</td><td>&lt;1e-4</td></tr><tr><td>Gassenor</td><td>0.3093</td><td>&lt;1e-4</td><td>0.3181</td><td>&lt;1e-4</td><td>0.3882</td><td>0.0019</td><td>0.6922</td><td>0.0010</td><td>0.8050</td><td>&lt;1e-4</td><td>0.4967</td><td>&lt;1e-4</td></tr><tr><td>IGBN</td><td>0.2138</td><td>&lt;1e-4</td><td>0.3853</td><td>0.0738</td><td>0.2680</td><td>0.0105</td><td>0.5453</td><td>0.0001</td><td>0.5743</td><td>&lt;1e-4</td><td>0.3789</td><td>&lt;1e-4</td></tr><tr><td>IABN</td><td>0.2020</td><td>&lt;1e-4</td><td>0.2660</td><td>0.0122</td><td>0.2950</td><td>0.0003</td><td>0.4523</td><td>0.0009</td><td>0.5175</td><td>&lt;1e-4</td><td>0.2772</td><td>&lt;1e-4</td></tr><tr><td>Rialto</td><td>0.1225</td><td>&lt;1e-4</td><td>0.1086</td><td>0.0010</td><td>0.1953</td><td>0.0038</td><td>0.3224</td><td>0.0001</td><td>0.3132</td><td>&lt;1e-4</td><td>0.2115</td><td>&lt;1e-4</td></tr><tr><td>IIAIN</td><td>0.2980</td><td>&lt;1e-4</td><td>0.3227</td><td>0.0075</td><td>0.3848</td><td>0.0122</td><td>0.4284</td><td>&lt;1e-4</td><td>0.3674</td><td>&lt;1e-4</td><td>0.4315</td><td>&lt;1e-4</td></tr><tr><td>IIIRIN</td><td>0.3156</td><td>&lt;1e-4</td><td>0.3539</td><td>0.0233</td><td>0.3685</td><td>0.0011</td><td>0.5127</td><td>0.0023</td><td>0.4426</td><td>&lt;1e-4</td><td>0.3764</td><td>&lt;1e-4</td></tr><tr><td>Covtype</td><td>0.4762</td><td>0.0017</td><td>0.4742</td><td>0.0003</td><td>0.4846</td><td>0.0001</td><td>0.5318</td><td>0.0005</td><td>0.5312</td><td>&lt;1e-4</td><td>0.4740</td><td>&lt;1e-4</td></tr><tr><td>Average mean(Real)</td><td>0.2676</td><td>0.0002</td><td>0.3002</td><td>0.0150</td><td>0.3606</td><td>0.0054</td><td>0.5205</td><td>0.0006</td><td>0.5555</td><td>&lt;1e-4</td><td>0.3554</td><td>&lt;1e-4</td></tr><tr><td>Total average mean</td><td>0.6129</td><td>&lt;1e-4</td><td>0.5671</td><td>0.0099</td><td>0.6161</td><td>0.0052</td><td>0.7743</td><td>0.0003</td><td>0.7908</td><td>&lt;1e-4</td><td>0.6878</td><td>&lt;1e-4</td></tr></tbody></table>

conventional clustering method, such as the efficiency of K-means and the better clustering quality of HDBSCAN on arbitrary clusters. This observation shows the exceptional flexibility of the proposed framework in adapting to different tasks by judiciously selecting different conventional clustering algorithms.

## 5. Conclusion

A significant advancement in clustering, especially for large datasets, is the modeling of cluster distributions using innovative representations. In this research, we present a novel approach designed for both static and dynamic clustering, based on a histogram representation using Wasserstein distance to compare distributions. The proposed framework can be used with any clustering algorithm, depending on the required cluster properties, by working on subsets of data and comparing the obtained clusters between subsets. The main goal is to reduce computation time and improve clustering quality. Specifically, experiments on real and artificial datasets show that the proposed

framework can increase the computational speed and memory requirements of most traditional clustering algorithms with minimal loss of quality. For dynamic datasets, the proposed framework is competitive with existing approaches in terms of quality and complexity, while allowing great flexibility in the application of clustering algorithm.

The proposed framework is relatively easy to parameterize due to its robustness with respect to most parameters. The only parameter that needs to be adjusted is the “window size”, as larger windows often lead to better quality at the cost of slower computation. However, defining an optimal size is not straightforward. It is also worth noting that in some cases, the proposed approach may be slower than conventional algorithms without an improvement in quality, and is therefore not optimal for such situations. This is especially the case when compared to clustering algorithms known for their low complexity (notably K-means and related algorithms) applied to relatively small datasets and/or with well-defined clusters, or algorithms that show a significant drop in performance on smaller datasets, such as KASP, which suffer from the decomposition of the original dataset into a collection of subsets. Nevertheless, the good experimental performance of the proposed
<table><caption>**Table 14**
NMI results of dynamic experiments.</caption><thead><tr><th rowspan="2">Datasets</th><th colspan="2">SequentialKmeans</th><th colspan="2">StreamKmeans</th><th colspan="2">CluStream</th><th colspan="4">HistStream</th><th colspan="2">DenStream</th></tr><tr><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th colspan="2">Kmeans</th><th colspan="2">HDBSCAN</th><th>mean</th><th>std</th></tr></thead><tbody><tr><td>Comet20</td><td>0.9391</td><td>&lt;1e-4</td><td>0.8062</td><td>0.0002</td><td>0.9499</td><td>0.0040</td><td>0.9848</td><td>&lt;1e-4</td><td>0.9734</td><td>&lt;1e-4</td><td>0.9843</td><td>&lt;1e-4</td></tr><tr><td>Meteroit20</td><td>0.9180</td><td>&lt;1e-4</td><td>0.7239</td><td>0.0018</td><td>0.9558</td><td>0.0014</td><td>0.9782</td><td>0.0001</td><td>0.9750</td><td>&lt;1e-4</td><td>0.9119</td><td>&lt;1e-4</td></tr><tr><td>Circle20</td><td>0.9664</td><td>&lt;1e-4</td><td>0.8156</td><td>0.0025</td><td>0.9302</td><td>0.0082</td><td>0.9517</td><td>&lt;1e-4</td><td>0.9164</td><td>&lt;1e-4</td><td>0.9303</td><td>&lt;1e-4</td></tr><tr><td>Gaussian20</td><td>0.9999</td><td>&lt;1e-4</td><td>0.9994</td><td>&lt;1e-4</td><td>0.9627</td><td>0.0011</td><td>0.9861</td><td>0.0005</td><td>0.9900</td><td>&lt;1e-4</td><td>0.9010</td><td>&lt;1e-4</td></tr><tr><td>Square20</td><td>0.9746</td><td>&lt;1e-4</td><td>0.7986</td><td>0.0034</td><td>0.9753</td><td>0.0003</td><td>0.9848</td><td>0.0001</td><td>0.9909</td><td>&lt;1e-4</td><td>0.9656</td><td>&lt;1e-4</td></tr><tr><td>Moon20</td><td>0.9296</td><td>&lt;1e-4</td><td>0.6858</td><td>0.0071</td><td>0.9557</td><td>0.0024</td><td>0.9854</td><td>&lt;1e-4</td><td>0.9774</td><td>&lt;1e-4</td><td>0.9950</td><td>&lt;1e-4</td></tr><tr><td>MixLarge10</td><td>0.9572</td><td>&lt;1e-4</td><td>0.8468</td><td>0.0058</td><td>0.9694</td><td>0.0068</td><td>0.9802</td><td>0.0015</td><td>0.9890</td><td>&lt;1e-4</td><td>0.9579</td><td>&lt;1e-4</td></tr><tr><td>MixLarge20</td><td>0.9662</td><td>&lt;1e-4</td><td>0.8986</td><td>0.0014</td><td>0.9662</td><td>0.0072</td><td>0.9655</td><td>0.0013</td><td>0.9756</td><td>&lt;1e-4</td><td>0.9761</td><td>&lt;1e-4</td></tr><tr><td>MixLarge50</td><td>0.9615</td><td>&lt;1e-4</td><td>0.9302</td><td>0.0015</td><td>0.0840</td><td>&lt;1e-4</td><td>0.9652</td><td>0.0008</td><td>0.9797</td><td>&lt;1e-4</td><td>0.9579</td><td>&lt;1e-4</td></tr><tr><td>Average mean(Artificial)</td><td>0.9569</td><td>&lt;1e-4</td><td>0.8339</td><td>0.0026</td><td>0.8610</td><td>0.0035</td><td>0.9758</td><td>0.0005</td><td>0.9742</td><td>&lt;1e-4</td><td>0.9533</td><td>&lt;1e-4</td></tr><tr><td>Outdoor</td><td>0.3402</td><td>&lt;1e-4</td><td>0.2249</td><td>0.0027</td><td>0.7041</td><td>0.0019</td><td>0.7346</td><td>&lt;1e-4</td><td>0.8258</td><td>&lt;1e-4</td><td>0.5115</td><td>&lt;1e-4</td></tr><tr><td>Gassenor</td><td>0.0920</td><td>&lt;1e-4</td><td>0.1149</td><td>&lt;1e-4</td><td>0.1958</td><td>0.0010</td><td>0.5079</td><td>0.0005</td><td>0.6968</td><td>&lt;1e-4</td><td>0.3671</td><td>&lt;1e-4</td></tr><tr><td>IGBN</td><td>0.0232</td><td>&lt;1e-4</td><td>0.3047</td><td>0.1116</td><td>0.0705</td><td>0.0079</td><td>0.4189</td><td>&lt;1e-4</td><td>0.5319</td><td>&lt;1e-4</td><td>0.1705</td><td>&lt;1e-4</td></tr><tr><td>IABN</td><td>0.0073</td><td>&lt;1e-4</td><td>0.1614</td><td>0.1016</td><td>0.0875</td><td>0.0007</td><td>0.2152</td><td>0.0011</td><td>0.3623</td><td>&lt;1e-4</td><td>0.1185</td><td>&lt;1e-4</td></tr><tr><td>Rialto</td><td>0.0036</td><td>&lt;1e-4</td><td>0.0006</td><td>0.0001</td><td>0.1288</td><td>0.0059</td><td>0.2059</td><td>&lt;1e-4</td><td>0.2449</td><td>&lt;1e-4</td><td>0.1336</td><td>&lt;1e-4</td></tr><tr><td>IIAIN</td><td>0.0002</td><td>&lt;1e-4</td><td>0.0142</td><td>0.0093</td><td>0.0836</td><td>0.0151</td><td>0.1024</td><td>&lt;1e-4</td><td>0.0723</td><td>&lt;1e-4</td><td>0.1384</td><td>&lt;1e-4</td></tr><tr><td>IIRIN</td><td>0.0023</td><td>&lt;1e-4</td><td>0.0240</td><td>0.0122</td><td>0.0589</td><td>0.0013</td><td>0.1479</td><td>0.0009</td><td>0.1440</td><td>&lt;1e-4</td><td>0.0884</td><td>&lt;1e-4</td></tr><tr><td>Covtype</td><td>0.0044</td><td>0.0015</td><td>0.0021</td><td>0.0002</td><td>0.0582</td><td>0.0009</td><td>0.0824</td><td>0.0011</td><td>0.0739</td><td>&lt;1e-4</td><td>&lt;1e-4</td><td>&lt;1e-4</td></tr><tr><td>Average mean(Real)</td><td>0.0592</td><td>0.0002</td><td>0.1059</td><td>0.0183</td><td>0.1734</td><td>0.0043</td><td>0.3019</td><td>0.0004</td><td>0.3690</td><td>&lt;1e-4</td><td>0.1910</td><td>&lt;1e-4</td></tr><tr><td>Total average mean</td><td>0.5345</td><td>&lt;1e-4</td><td>0.4913</td><td>0.0100</td><td>0.5374</td><td>0.0039</td><td>0.6587</td><td>0.0005</td><td>0.6894</td><td>&lt;1e-4</td><td>0.5946</td><td>&lt;1e-4</td></tr></tbody></table>

<table><caption>**Table 15**
Computation time of dynamic experiments.</caption><thead><tr><th rowspan="2">Datasets</th><th colspan="2">SequentialKmeans</th><th colspan="2">StreamKmeans</th><th colspan="2">CluStream</th><th colspan="4">HistStream</th><th colspan="2">DenStream</th></tr><tr><th>mean</th><th>std</th><th>mean</th><th>std</th><th>mean</th><th>std</th><th colspan="2">Kmeans</th><th colspan="2">HDBSCAN</th><th>mean</th><th>std</th></tr></thead><tbody><tr><td>Comet20</td><td>601.1789</td><td>0.8627</td><td>4173.0255</td><td>5.8701</td><td>111.1533</td><td>10.8181</td><td>20.0096</td><td>0.0576</td><td>136.5564</td><td>1.9086</td><td>103.7651</td><td>2.6580</td></tr><tr><td>Meteroit20</td><td>598.7418</td><td>0.3835</td><td>4048.3590</td><td>0.5028</td><td>99.2521</td><td>4.6470</td><td>20.7868</td><td>0.1174</td><td>127.1455</td><td>1.1586</td><td>9854.3365</td><td>87.1560</td></tr><tr><td>Circle20</td><td>612.8237</td><td>3.0160</td><td>4321.1806</td><td>116.6523</td><td>100.8072</td><td>5.9999</td><td>29.4217</td><td>0.5364</td><td>494.6203</td><td>7.7403</td><td>141.2185</td><td>0.5147</td></tr><tr><td>Gaussian20</td><td>603.9073</td><td>0.2887</td><td>4199.7799</td><td>3.8610</td><td>107.0685</td><td>9.2846</td><td>24.4203</td><td>0.4745</td><td>76.8281</td><td>0.5030</td><td>3105.9656</td><td>6.6823</td></tr><tr><td>Square20</td><td>602.7990</td><td>0.6457</td><td>4173.3107</td><td>3.6656</td><td>106.2824</td><td>11.4305</td><td>25.6883</td><td>2.3608</td><td>82.2653</td><td>0.9315</td><td>4769.8329</td><td>32.2027</td></tr><tr><td>Moon20</td><td>637.8218</td><td>3.3549</td><td>4435.9815</td><td>18.2940</td><td>93.5763</td><td>5.8634</td><td>25.0204</td><td>3.4944</td><td>96.8381</td><td>1.1616</td><td>85.1582</td><td>2.9777</td></tr><tr><td>MixLarge10</td><td>343.2683</td><td>0.5161</td><td>2501.5632</td><td>5.0294</td><td>56.7119</td><td>4.6763</td><td>14.6774</td><td>0.6988</td><td>52.6882</td><td>1.3952</td><td>15 544.6931</td><td>345.2638</td></tr><tr><td>MixLarge20</td><td>841.1053</td><td>1.8018</td><td>7051.6518</td><td>51.9163</td><td>137.4155</td><td>9.9892</td><td>33.4324</td><td>2.2048</td><td>179.6185</td><td>11.3344</td><td>2597.6667</td><td>59.2815</td></tr><tr><td>MixLarge50</td><td>2867.8369</td><td>7.7141</td><td>32 481.0794</td><td>1056.8821</td><td>318.0409</td><td>8.9821</td><td>117.0566</td><td>10.4723</td><td>483.7691</td><td>17.7896</td><td>15 544.6931</td><td>345.2638</td></tr><tr><td>Average mean(Artificial)</td><td>856.6092</td><td>2.0648</td><td>7487.3257</td><td>140.2971</td><td>125.5898</td><td>7.9657</td><td>34.5015</td><td>2.2686</td><td>192.2588</td><td>4.8803</td><td>5749.7033</td><td>98.0001</td></tr><tr><td>Outdoor</td><td>1.9826</td><td>0.0119</td><td>12.0543</td><td>0.0459</td><td>18.3913</td><td>0.9477</td><td>1.3999</td><td>&lt;1e-4</td><td>3.1280</td><td>&lt;1e-4</td><td>0.3405</td><td>0.0117</td></tr><tr><td>Gassenor</td><td>7.6274</td><td>0.2071</td><td>19.1491</td><td>0.7072</td><td>1.0658</td><td>0.0581</td><td>0.6815</td><td>0.2587</td><td>4.3237</td><td>0.0406</td><td>8.5452</td><td>0.0990</td></tr><tr><td>IGBN</td><td>3.7845</td><td>0.2189</td><td>6.1328</td><td>0.1192</td><td>2.9484</td><td>2.3777</td><td>0.6990</td><td>0.1686</td><td>9.8378</td><td>0.0485</td><td>2.9768</td><td>0.1999</td></tr><tr><td>IABN</td><td>8.4413</td><td>0.2436</td><td>14.6793</td><td>0.5363</td><td>4.2191</td><td>0.8793</td><td>1.6813</td><td>0.1438</td><td>14.7541</td><td>0.0692</td><td>2.6717</td><td>0.1316</td></tr><tr><td>Rialto</td><td>15.5729</td><td>0.0744</td><td>47.5999</td><td>0.2665</td><td>12.2390</td><td>1.1187</td><td>2.8241</td><td>0.1433</td><td>11.8558</td><td>0.0565</td><td>8.0523</td><td>0.1978</td></tr><tr><td>IIAIN</td><td>70.0952</td><td>3.2963</td><td>125.4809</td><td>3.5934</td><td>30.6166</td><td>0.1338</td><td>10.3653</td><td>&lt;1e-4</td><td>312.6661</td><td>&lt;1e-4</td><td>82.7187</td><td>0.2978</td></tr><tr><td>IIRIN</td><td>68.3161</td><td>0.9216</td><td>123.9349</td><td>0.8913</td><td>30.1934</td><td>0.0635</td><td>24.9010</td><td>0.7840</td><td>378.9039</td><td>12.6035</td><td>103.2595</td><td>1.5032</td></tr><tr><td>Covtype</td><td>32.2408</td><td>0.4028</td><td>86.6200</td><td>1.5781</td><td>43.3229</td><td>1.1053</td><td>12.2326</td><td>1.1983</td><td>142.8380</td><td>3.6063</td><td>21.7024</td><td>0.1732</td></tr><tr><td>Average mean(Real)</td><td>26.0076</td><td>0.6721</td><td>54.4564</td><td>0.9672</td><td>17.8746</td><td>0.8355</td><td>6.8481</td><td>0.3371</td><td>109.7884</td><td>2.0531</td><td>28.7834</td><td>0.3268</td></tr><tr><td>Total average mean</td><td>465.7379</td><td>1.4094</td><td>3989.5049</td><td>74.7301</td><td>74.9003</td><td>4.6103</td><td>21.4881</td><td>1.3596</td><td>153.4492</td><td>3.5498</td><td>3057.5057</td><td>52.0362</td></tr></tbody></table>

<figure><img src="image_25.png" /><figcaption>**Fig. 21.** Trade-off – Mean ARI (left), Purity (center) and NMI (right) values for dynamic experiments (Artificial datasets) – approaches based on K-Means are in blue and on DBSCAN are in orange – “§” denote the proposed approaches in respective categories. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)</figcaption></figure>

approach in most cases shows its flexibility and applicability to many clustering algorithms, especially in real-world scenarios.

In this article, we have compared the performance of standard clustering algorithms independently and when integrated with the proposed framework. In order to assess the quality of the proposed approach to data stream clustering, we have selected the standard

clustering algorithms to be integrated into the framework so as to ensure comparability with other families of data stream clustering, specifically prototype-based and density-based approaches. Ultimately, the choice of which clustering algorithm to use within the framework should be tailored to each particular application, based on prior knowledge of the dataset or specific expectations about the resulting
<figure><img src="image_26.png" /><figcaption>Fig. 22. Trade-off – Mean ARI (left), Purity (center) and NMI (right) values dynamic experiments (Real datasets) – approaches based on K-Means are in blue and on DBSCAN are in orange – "$" denote the proposed approaches in respective categories. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)</figcaption></figure>

clustering. While we did not further investigate the question of the
optimal choice of clustering algorithm, an issue of obvious importance,
it remains a promising area for further research. Indeed, future studies
may benefit from advanced techniques such as meta-learning or ensem-
ble clustering, which may help identify the most appropriate standard
clustering algorithms for specific scenarios or broader applications, thus
improving the overall performance of the framework.

In conclusion, our research highlights a promising new approach
that uses histogram modeling with Wasserstein distance for clustering
in both static and dynamic scenarios. It provides an efficient option
for real-world applications, offering significant advantages in terms of
computational time and clustering quality. A critical focus of our future
studies will be to automatically determine the optimal window size to
achieve the best trade-off between quality and speed, to propose more
robust clustering results and to investigate the question of the selection
of the clustering algorithm to integrate into the framework.

CRediT authorship contribution statement

**Xiaotong Qian:** Writing – review & editing, Writing – original draft, Visualization, Validation, Software, Resources, Project administration, Methodology, Investigation, Formal analysis, Data curation, Conceptualization.
**Guénaël Cabanes:** Writing – review & editing, Writing – original draft, Supervision, Project administration, Methodology, Funding acquisition, Formal analysis, Conceptualization.
**Parisa Rastin:** Writing – review & editing, Writing – original draft, Validation, Supervision, Project administration, Methodology, Funding acquisition, Formal analysis, Conceptualization.
**Mohamed Alae Guidani:** Resources, Investigation, Formal analysis.
**Ghassen Marrakchi:** Validation, Resources, Investigation.
**Marianne Clausel:** Writing – review & editing, Writing – original draft, Validation, Supervision, Project administration, Methodology, Funding acquisition, Formal analysis, Conceptualization.
**Nistor Grozavu:** Writing – review & editing, Writing – original draft, Validation, Supervision, Project administration, Methodology, Funding acquisition, Formal analysis, Conceptualization.

Declaration of competing interest

The authors declare that they have no known competing finan-
cial interests or personal relationships that could have appeared to
influence the work reported in this paper.

Data availability

Data will be made available on request.

References

[1] W.Z. Tareq, M. Davud, Classification and clustering, in: Decision-Making Models, Elsevier, 2024, pp. 351–359.

[2] G.J. Oyewole, G.A. Thopil, Data clustering: Application and trends, Artif. Intell. Rev. 56 (7) (2023) 6439–6475.

[3] T. Zhang, R. Ramakrishnan, M. Livny, BIRCH: an efficient data clustering method for very large databases, ACM Sigmod Rec. 25 (2) (1996) 103–114.

[4] F. Murtagh, P. Legendre, Ward's hierarchical agglomerative clustering method: which algorithms implement Ward's criterion? J. Classification 31 (2014) 274–295.

[5] J.A. Hartigan, M.A. Wong, Algorithm AS 136: A k-means clustering algorithm, J. R. Stat. Soc. Ser. C (Appl. Statistics) 28 (1) (1979) 100–108.

[6] C.C. Aggarwal, P.S. Yu, Redefining clustering for high-dimensional applications, IEEE Trans. Knowl. Data Eng. 14 (2) (2002) 210–225.

[7] N. Cristianini, J. Shawe-Taylor, J. Kandola, Spectral kernel methods for clustering, Adv. Neural Inf. Process. Syst. 14 (2001).

[8] M. Ester, H.-P. Kriegel, J. Sander, X. Xu, et al., A density-based algorithm for discovering clusters in large spatial databases with noise, in: Kdd, Vol. 96, 1996, pp. 226–231.

[9] C.M. Bishop, N.M. Nasrabadi, Pattern Recognition and Machine Learning, vol. 4, Springer, 2006.

[10] R. Agrawal, J. Gehrke, D. Gunopulos, P. Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, in: Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, 1998, pp. 94–105.

[11] D. Yan, L. Huang, M.I. Jordan, Fast approximate spectral clustering, in: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2009, pp. 907–916.

[12] C. Malzer, M. Baum, A hybrid approach to hierarchical density-based cluster selection, in: 2020 IEEE International Conference on Multisensor Fusion and Integration for Intelligent Systems, MFI, IEEE, 2020, pp. 223–228.

[13] X. Wang, Z. Wang, Z. Wu, S. Zhang, X. Shi, L. Lu, Data stream clustering: An in-depth empirical study, Proc. ACM Manag. Data 1 (2) (2023) 1–26.

[14] G. Sudipto, N. Mishra, R. Motwant, L. O'callaghan, Clustering data streams, in: Proc. 41st FOCS, 2000, pp. 359–366.

[15] L. O'callaghan, N. Mishra, A. Meyerson, S. Guha, R. Motwani, Streaming-data algorithms for high-quality clustering, in: Proceedings 18th International Conference on Data Engineering, IEEE, 2002, pp. 685–694.

[16] D. Sculley, Web-scale k-means clustering, in: Proceedings of the 19th International Conference on World Wide Web, 2010, pp. 1177–1178.

[17] C.C. Aggarwal, S.Y. Philip, J. Han, J. Wang, A framework for clustering evolving data streams, in: Proceedings 2003 VLDB Conference, Elsevier, 2003, pp. 81–92.

[18] F. Cao, M. Estert, W. Qian, A. Zhou, Density-based clustering over an evolving data stream with noise, in: Proceedings of the 2006 SIAM International Conference on Data Mining, SIAM, 2006, pp. 328–339.

[19] M. Hahsler, M. Bolaños, Clustering data streams based on shared density between micro-clusters, IEEE Trans. Knowl. Data Eng. 28 (6) (2016) 1449–1461.

[20] J. Gama, P.P. Rodrigues, L. Lopes, Clustering distributed sensor data streams using local processing and reduced communication, Intell. Data Anal. 15 (1) (2011) 3–28.

[21] X.H. Dang, V.C. Lee, W.K. Ng, K.L. Ong, Incremental and adaptive clustering stream data over sliding window, in: Database and Expert Systems Applications: 20th International Conference, DEXA 2009, Linz, Austria, August 31–September 4, 2009. Proceedings 20, Springer, 2009, pp. 660–674.

[22] A. Irpino, R. Verde, A new wasserstein based distance for the hierarchical clustering of histogram symbolic data, in: Data Science and Classification, Springer, 2006, pp. 185–192.

[23] M.-F. Balcan, T. Sandholm, E. Vitercik, Learning to optimize computational resources: Frugal training with generalization guarantees, in: Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34, 2020, pp. 3227–3234.
[24] P. Brito, S. Dias, Analysis of Distributional Data, CRC Press, 2022.

[25] A. Irpino, R. Verde, Basic statistics for distributional symbolic variables: a new metric-based approach, Adv. Data Anal. Classif. 9 (2015) 143-175.

[26] C. Villani, C. Villani, The Wasserstein distances, Optim. Transp. Old New (2009) 93-111.

[27] K. Pearson, Contributions to the mathematical theory of evolution, Philos. Trans. R. Soc. Lond. A 185 (1894) 71-110.

[28] S. Kullback, R.A. Leibler, On information and sufficiency, Ann. Math. Stat. 22 (1) (1951) 79-86.

[29] D. Endres, J.E. Schindelin, A new metric for probability distributions, IEEE Trans. Inform. Theory 49 (2003) 1858-1860.

[30] C. Villani, et al., Optimal Transport: Old and New, vol. 338, Springer, 2009.

[31] Y. Rubner, C. Tomasi, L.J. Guibas, The earth mover's distance as a metric for image retrieval, Int. J. Comput. Vis. 40 (2) (2000) 99-121.

[32] M. Cuturi, Sinkhorn distances: Lightspeed computation of optimal transport, Adv. Neural Inf. Process. Syst. 26 (2013).

[33] V.W. Berger, Y. Zhou, Kolmogorov-Smirnov test: Overview, in: Wiley statsref: Statistics reference online, Wiley Online Library, 2014.

[34] A. Ramdas, N.G. Trillos, M. Cuturi, On Wasserstein two-sample testing and related families of nonparametric tests, Entropy 19 (2017) 47.

[35] D. Revuz, M. Yor, Continuous Martingales and Brownian Motion, vol. 293, Springer Science & Business Media, 2013.

[36] R. Durrett, Probability: Theory and Examples, vol. 49, Cambridge University Press, 2019.

[37] N. Bonneel, J. Rabin, G. Peyré, H. Pfister, Sliced and radon wasserstein barycenters of measures, J. Math. Imaging Vision 51 (1) (2015) 22-45.

[38] A. Vergara, S. Vembu, T. Ayhan, M.A. Ryan, M.L. Homer, R. Huerta, Chemical gas sensor drift compensation using classifier ensembles, Sensors Actuators B 166 (2012) 320-329.

[39] V. Losing, B. Hammer, H. Wersing, KNN classifier with self adjusting memory for heterogeneous concept drift, in: 2016 IEEE 16th International Conference on Data Mining, ICDM, IEEE, 2016, pp. 291-300.

[40] J.A. Blackard, D.J. Dean, Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables, Comput. Electron. Agric. 24 (3) (1999) 131-151.

[41] V.M.A. Souza, D.M. Reis, A.G. Maletzke, G.E.A.P.A. Batista, Challenges in benchmarking stream learning algorithms with real-world data, Data Min. Knowl. Discov. 34 (2020) 1805-1858, http://dx.doi.org/10.1007/s10618-020-00698-5.

[42] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, E. Duchesnay, Scikit-learn: Machine learning in Python, J. Mach. Learn. Res. 12 (2011) 2825-2830.

[43] N.X. Vinh, J. Epps, J. Bailey, Information theoretic measures for clusterings comparison: is a correction for chance necessary? in: Proceedings of the 26th Annual International Conference on Machine Learning, 2009, pp. 1073-1080.

[44] G.G. Chowdhury, Introduction to Modern Information Retrieval, Facet publishing, 2010.

[45] L. Danon, A. Diaz-Guilera, J. Duch, A. Arenas, Comparing community structure identification, J. Stat. Mech. Theory Exp. 2005 (09) (2005) P09008.

[46] S. Dhar, M.K. Kundu, Accurate multi-class image segmentation using weak continuity constraints and neutrosophic set, Appl. Soft Comput. 112 (2021) 107759.

[47] A. Morison, M. Ulvrova, S. Labrosse, B4rsh, theofatou, tfrass49, Stag- Python/StagPy: v0.20.1, Zenodo, 2024, http://dx.doi.org/10.5281/zenodo. 13684760.

[48] J. Montiel, M. Halford, S.M. Mastelini, G. Bolmier, R. Sourty, R. Vaysse, A. Zouitine, H.M. Gomes, J. Read, T. Abdessalem, et al., River: machine learning for streaming data in python, J. Mach. Learn. Res. 22 (110) (2021) 1-8.

**Xiaotong Qian** received a Master's degree Data Mining and Decision-Making (EID2) at Sorbonne Paris Nord University, France in 2021. She is currently pursuing a Ph.D. degree at CY Cergy Paris University, France. Her research interest include unsupervised learning and data mining.

**Guénaël Cabanes** is an academic researcher at the University of Lorraine, France, member of the Lorraine Research Laboratory in Computer Science and its Application. His main research interest lies in data mining, particularly in unsupervised learning for dynamic and complex data, with applications in image and text mining and complex systems modeling.

**Parisa Rastin** received her Ph.D. in Computer Science from the University of Sorbonne Paris Nord. She is currently an associate professor at the University of Lorraine, École nationale supérieure des mines de Nancy. Her main research interests are in the area of unsupervised learning of dynamic and complex data with applications to text mining.

**Mohamed Alae Guidani** has graduated as an engineer from École nationale supérieure des mines de Nancy in 2018 with a major in Applied Mathematics, Mohamed Alae Guidani currently works in Data and Analytics consulting at EY. He analyzes complex datasets and implements data-driven strategies to drive innovation and optimize business performance.

**Ghassen Marrakchi** is a Master's Degree Student in Data Mining and Decision-Making (EID2) at Sorbonne Paris Nord University. He received his bachelor's degree in Computer Science from the University of Monastir. As a research enthusiast, he explores different Machine Learning fields, such as unsupervised learning.

**Marianne Clausel** is a Professor at the University of Lorraine. Her research is in statistical learning and time series analysis. She received her Ph.D. in Applied Mathematics from University of Creteil, France in 2008.

**Nistor Grozavu** is a full professor of Computer Science at CY Cergy Paris University. He holds a Ph.D. in Unsupervised Machine Learning (2009) from the University Paris 13 and an HdR (2020) from the University Sorbonne Paris Nord. His research interests include unsupervised learning, transfer learning, dimensionality reduction, quantum machine learning.