# A Novel Mean-Shift Algorithm for Data Clustering

Claude Cariou, Steven Le Moan, Kacem Chehdi

► To cite this version:

Claude Cariou, Steven Le Moan, Kacem Chehdi. A Novel Mean-Shift Algorithm for Data Clustering. IEEE Access, 2022, 10, pp.14575-14585. 10.1109/ACCESS.2022.3147951. hal-03593568

HAL Id: hal-03593568

https://hal.science/hal-03593568

Submitted on 6 May 2022

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Received November 25, 2021, accepted January 21, 2022, date of publication January 31, 2022, date of current version February 9, 2022.

Digital Object Identifier 10.1109/ACCESS.2022.3147951

# A Novel Mean-Shift Algorithm for Data Clustering

CLAUDE CARIOU<sup>1</sup>, (Member, IEEE), STEVEN LE MOAN<sup>2</sup>, (Member, IEEE),
AND KACEM CHEHDI<sup>1</sup>, (Member, IEEE)

¹CNRS, IETR, UMR 6164, University of Rennes 1, 22300 Lannion, France

²Department of Computer Science, Norwegian University of Science and Technology, 2815 Gjøvik, Norway

Corresponding author: Claude Cariou (claude.cariou@univ-rennes1.fr)

**ABSTRACT** We propose a novel Mean-Shift method for data clustering, called Robust Mean-Shift (RMS). A new update equation for point iterates is proposed, mixing the ones of the standard Mean-Shift (MS) and the Blurring Mean-Shift (BMS). Despite its simplicity, the proposed method has not been studied so far. RMS can be set up in both a kernel-based and a nearest-neighbor (NN)-based fashion. Since the update rule of RMS is closer to BMS, the convergence of point iterates is conjectured based on the Chen's BMS convergence theorem. Experimental results on synthetic and real datasets show that RMS in several cases outperforms MS and BMS in the clustering task. In addition, RMS exhibits larger attraction basins than MS and BMS for identical parametrization; consequently, its kernel variant requires a lower aperture of the kernel function, and its NN variant a lower number of nearest neighbors compared to MS or BMS, to achieve optimal clustering results. In addition, the NN version of RMS does not need to specify a convergence threshold to stop the iterations, contrary to the NN-BMS algorithm.

**INDEX TERMS** Data mining, data clustering, mean-shift, kernel-based method, nearest neighbors.

## I. INTRODUCTION

Data clustering is a type of unsupervised learning which consists of automatically grouping data points having similar characteristics into identified clusters without training sample points. It is a central task in various application fields such as medicine, genomics, content-based image and video indexing, and Big Data mining to cite a few. Clustering is also increasingly relevant in the context of Artificial Intelligence, in order to unveil the existence of underlying complex structures in datasets [2], and especially in applications where little or no training data is available. Despite several decades of research, clustering remains a challenging task for many applications because of the increasing size (number of data points) and dimensionality (number of features) of modern datasets. This is particularly true for applications that require on-the-fly data partitioning [3].

Clustering methods can be broadly categorized into several families, comprising centroid clustering [4]–[6], hierarchical clustering [7], [8], density-based [9], [10], Mean-Shift and mode seeking [11]–[14], clustering based on mixture resolving [15]–[17], and, more recently, affinity

propagation (AP) [18], information theoretic clustering [19], and convex clustering [20].

From a general viewpoint, clustering remains an ill-posed problem [21] because, depending on the partitioning process, several legitimate solutions can be obtained which are all acceptable [22], [23]. In fact, most popular methods claimed as unsupervised require a significant prior knowledge about the data structure, i.e. the number of clusters to be found. This is particularly true for centroid clustering, mixture resolving, and spectral clustering in their baseline implementation. However, while some of their parameters are necessary and can be difficult to tune, several other approaches do not require to specify the number of clusters. For instance, among them are hierarchical methods, as well as DBSCAN [9], AP [18], convex clustering [20], nearest-neighbor density-based (NN-DB) methods [24] and Mean-Shift based methods. In this work, we focus on the latter.

Mean-Shift (MS) was originally proposed by Fuku-naga and Hostetler in 1975 [11] essentially as a means to provide the modes of an unknown probability density function (p.d.f.). MS relies on kernel density estimation (KDE), a non-parametric way to estimate a p.d.f. from data samples [25], [26]. In MS, each point of the dataset is moved iteratively by a small amount (the so-called *mean shift*) until convergence to some stationary point, i.e. a local mode of

The associate editor coordinating the review of this manuscript and approving it for publication was Amir Masoud Rahmani.
the estimated p.d.f.. MS has first been used as an unsupervised data clustering method, for which the retained local modes after convergence of the point iterates serve as cluster representatives (or exemplars). A connected component post-processing stage [26] is therefore necessary after the convergence is achieved to assign a cluster label to each of the original data points.

A number of studies have followed the seminal work of Fukunaga and Hostetler [12], [25], [27]–[31], and several proofs pertaining to convergence and p.d.f. estimation have been proposed [1], [12], [25]–[28], [32]–[34]. In [26], Carreira-Perpiñán provides a comprehensive review of MS-based methods and their application to data clustering and data denoising. Mean-Shift has also been successfully applied to image filtering and segmentation in [25].

In the present work, we propose a novel approach to the classical Mean-Shift algorithm focusing data clustering; the KDE problem is not investigated herein. To the best of our knowledge, the proposed approach has not been published. Despite relying on a modification of the original MS algorithm, we demonstrate that our method leads to significantly different features. This method, which we name Robust Mean-Shift (RMS) is a hybridization of the standard Mean-Shift (MS) algorithm [25], and of the so-called Blurring Mean-Shift (BMS) method [27]. It is worth recalling that BMS was actually first proposed in [11], as pointed out in [26]. Our algorithm is based on iteratively moving updates of initial data points, similar to MS and BMS, but the update equation of RMS fundamentally differs from both methods.

The proposed RMS approach proposed in this work has several valuable properties:

* We find experimentally that RMS requires a lower bandwidth parameter (in the kernel-based variant) and a lower number of nearest neighbors (in the NN variant) than MS and BMS to achieve comparable or even better results in the clustering task; this is especially interesting to speed up the computation of point iterates, and in the case of the NN-RMS variant, to reduce the size of the NN graph compared to the ones required by the NN variants of MS and BMS;

* Compared to MS and BMS, RMS generally performs better, as evidenced experimentally through the analysis of various datasets;

* In most experiments, RMS converges faster than BMS, the latter being proved to converge faster than MS [35];

* The (classical) kernel-based RMS can be easily turned to a K-nearest neighbor (KNN) algorithm, similarly to MS and BMS [30], [31];

* The NN variant of RMS does not require a termination threshold, unlike the NN variant of BMS.

The paper is organized as follows. Section II provides a brief overview of related works, including kernel-based and KNN-based Mean-Shift (MS) approaches published so far. In Section III, we introduce the proposed clustering method and explain how it relates to MS and BMS. The convergence of RMS in the kernel-based framework is then discussed

in Section IV. Section V describes the NN-based variant of RMS. An experimental study of RMS and its comparison with other similar clustering approaches on various datasets is provided in Section VI. Conclusions and perspectives of this work are given in Section VII.

## II. NOTATIONS AND RELATION TO PRIOR WORKS

Let $\mathcal{X} = \{\mathbf{x}_i\}$, $\mathbf{x}_i \in \mathbb{R}^n$, $i = 1, \dots, N$ the set of data points to classify. Let $f: \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}_+$ a kernel function such that $(\mathbf{u}, \mathbf{v}) \mapsto f(\mathbf{u}, \mathbf{v}) \ge 0$, and $f(\mathbf{u}, \mathbf{v})$ decreases monotonically with $\|\mathbf{u} - \mathbf{v}\|$. Kernel density functions are generally tuned with a bandwidth parameter, and they can follow several models; flat, Epanechnikov, biweight, and especially Gaussian kernels are commonly used [27]. However, it is well established that the shape of the kernel has very little effect on the results in comparison to the bandwidth parameter. With that in mind, Gaussian kernels are most commonly used for their convenience.

MS and BMS aim at estimating a p.d.f. and finding its local modes from the observations $\mathcal{X}$. This is done by moving the initial data points $\{\mathbf{x}_i\}_{i=1,\dots,N}$ iteratively until convergence to stationary points, which are the estimated local modes of the true p.d.f.. Let $\{\mathbf{y}_i^{(t)}\}_{i=1,\dots,N}$ be the set of moved points at iteration $t$, and assume $\mathbf{y}_i^{(0)} = \mathbf{x}_i \quad \forall i$.

We briefly recall below the original MS and BMS update rules, i.e. the operation applied to the data points at each iteration.

### A. MEAN-SHIFT (MS)

MS can be used to partition a dataset by assigning each data point a label corresponding to the unique point it converges to after some (expected) finite number of iterations of an update equation. More precisely, with the above notations, the update equation of MS writes, $\forall i$:

$$ \mathbf{y}_i^{(t+1)} = \frac{\sum_{k=1}^{N} f(\mathbf{x}_k, \mathbf{y}_i^{(t)}) \cdot \mathbf{x}_k}{\sum_{j=1}^{N} f(\mathbf{x}_j, \mathbf{y}_i^{(t)})} \quad (1) $$

With the above assumption on the kernel function $f$, the updated points $\{\mathbf{y}_i^{(t+1)}\}_{i=1,\dots,N}$ are obtained as a convex linear combination (i.e. with non-negative coefficients summing up to unity) of the initial data points $\{\mathbf{x}_i\}_{i=1,\dots,N}$.

### B. BLURRING MEAN-SHIFT (BMS)

The update rule for BMS is different from MS since it is based on a convex linear combination of the previously moved data points (hence the so-called blurring effect, as coined by Cheng in [27]), i.e. $\forall i$:

$$ \mathbf{y}_i^{(t+1)} = \frac{\sum_{k=1}^{N} f(\mathbf{y}_k^{(t)}, \mathbf{y}_i^{(t)}) \cdot \mathbf{y}_k^{(t)}}{\sum_{j=1}^{N} f(\mathbf{y}_j^{(t)}, \mathbf{y}_i^{(t)})} \quad (2) $$

It can be noticed that, over the iterations, this update rule progressively ‘forgets’ the initial data points in $\mathcal{X}$, contrarily to MS.
## C. DISCUSSION

### 1) MAIN ADVANTAGES AND DRAWBACKS

As pointed out in [26] MS and BMS algorithms have several advantages compared to other clustering techniques, among which:

* their parametrization is limited to the choice of an appropriate kernel function, and a single bandwidth (or aperture) parameter for this kernel function;

* they allow to discover non-convex clusters;

* they can automatically determine the number of clusters, depending on the chosen bandwidth parameter;

* the algorithms are totally deterministic.

These advantages make a significant difference with respect to classical clustering methods like k-means or fuzzy c-means for which none of the last three items above is ensured. However, MS-based methods have two main drawbacks which are the lack of scalability to large datasets, and a high sensitivity of clustering performances for high-dimensional datasets with respect to the bandwidth parameter [26]. The latter is a consequence of the so-called *curse of dimensionality* [36] and the fact that distances tend to be less meaningful in high dimensions.

### 2) CONVERGENCE OF MS-BASED METHODS

Since the early works on MS-based clustering, and until very recently, the convergence of MS and BMS has been studied. A comprehensive study of the convergence of both MS and BMS algorithms is summarized in [26], but specific results were provided for MS in [25], [35], and for BMS in [1], [27].

For MS, the convergence of moved points to local modes is ensured theoretically and practically in the general case. However the situation may vary from one kernel to another as for the number of iterations required to convergence: the latter is proven in a finite number of steps for the Epanechnikov kernel [25], but infinite for the Gaussian kernel, moreover with a linear convergence rate [37].

For BMS, the convergence issue depends on the kernel aperture: for large ones which encompass the whole dataset $\mathcal{X}$, convergence is ensured to a unique mode, whereas for narrower ones with finite support, the BMS update rule allows the iterates to converge quickly to well-separated distinct modes during the first steps. However, pursuing the iterations can eventually lead to the merging of these modes into a single one. Therefore BMS must be stopped before this case occurs [29]. The convergence rate of Gaussian BMS has been proven cubic [35], hence much faster than Gaussian MS.

### 3) KNN-MS BASED METHODS

Choosing the optimal set of hyperparameters (kernel function and bandwidth) for a specific task can become very challenging. This is why, since the early works on Mean-Shift-based density estimation and data clustering [11], [12], the use of nearest neighbors as an alternative to the standard kernel approach has been proposed by many researchers. Indeed, the NN approach (i) does not require to specify an underlying parametric function, so that only one parameter K is required;

and (ii) the KNN principle makes it possible to maintain the relationship between data points located far from each other, especially on the external border of clusters. In this sense, the NN-based framework is data-adaptive, contrarily to the kernel-based one. In [11], a mean-shift estimate calculated from K nearest neighbors was proposed as a natural way to automatically adapt the density estimation to its local variations. The nearest neighbor paradigm can also be used to estimate the bandwidth parameter of kernel-based MS, for instance as the average distance of each point to its KNNs [26].

Koontz et al. [12] adopted a graph-based clustering approach which enables the assignment of any data point (or node) to a parent node, using the number of neighbors found within the constant radius ball centered on it. The clustering result is then produced via a directed tree traversal [38]. In [29], Grillenzoni proposed a Gaussian BMS based on KNNs, which provides a data-driven technique to select the bandwidth and is shown to have low sensitivity to K. Duong et al. [30] also provided a data-driven closed-form solution to estimate the optimal number of NNs in NN-MS. Recently, Beck et al. [31] proposed an extension of the Nearest Neighbor Gradient Ascent (NNGA) method (which is in fact a KNN version of MS) incorporating Locality Sensitivity Hashing (LSH) to approximate nearest neighbors and $\epsilon$-proximity cluster labeling rule into NNGA, and renamed this method NNGA$^+$, NNGA and NNGA$^+$ have the advantage of being scalable for large datasets.

### 4) IMPLEMENTATION ISSUES

An important issue of MS-based methods is related to their practical implementation. Actually, there is a major difference between MS and BMS in this regard. Indeed, Eq. (1) shows that each point can be treated independently from others because, as soon as kernel evaluations are computed, the update $y_i^{(t+1)}$ is a linear combination of the original data points. In contrast, BMS in Eq. (2) requires the whole set of current iterates to calculate $y_i^{(t+1)}$. Therefore, BMS cannot be parallelized, whereas MS can be parallelized efficiently. For both approaches and for arbitrary data, the complexity is quadratic in the number of points [26].

## III. ROBUST MEAN-SHIFT

In this section, we propose another MS-like clustering approach, which we name Robust Mean-Shift (RMS). The rationale behind RMS is to combine MS and BMS, so that the next iterate remains a convex linear combination of the current ones, like BMS in Eq. (2), whereas the kernel weighting is kept identical to the MS update in Eq. (1). Therefore, the proposed update equation writes:

$$ \mathbf{y}_i^{(t+1)} = \frac{\sum_{k=1}^{N} f(\mathbf{x}_k, \mathbf{y}_i^{(t)}) \cdot \mathbf{y}_k^{(t)}}{\sum_{j=1}^{N} f(\mathbf{x}_j, \mathbf{y}_i^{(t)})} \quad (3) $$

The main idea of RMS is based on the following expectations:
* Since the next iterate is a combination of the current ones, a behavior similar to BMS can be anticipated, especially in terms of faster convergence with respect to MS;

* Since the kernel weights remain dependent on the initial data points {$\mathbf{x}_k$}$_{k=1,...,N}$, it is expected that iterates remain 'bound' to the initial data points, therefore avoiding convergence to a unique mode for broad kernels, which is a known drawback of BMS [35];

* The kernel-based update rule in Eq. (3) can be easily modified to involve nearest neighbors, similarly to NNGA [31] and the graph-theoretic approach in [12].

Surprisingly, this update equation has not been reported so far in the literature to the best of our knowledge.

Figure 1 illustrates with a simple example the differences between MS, BMS and RMS. For the three methods, the same kernel parametrization is used, i.e.

$$f(\mathbf{u}, \mathbf{v}) = \exp\left(-\frac{\|\mathbf{u} - \mathbf{v}\|^2}{\sigma^2}\right), \quad (4)$$

with bandwidth parameter $\sigma = 0.15$. The dataset is drawn randomly from three 2-D normal distributions with identical diagonal covariance matrices, centered at [0, 0], [0, 1], [1, 1]. One can see that the modes of these distributions are hardly distinguishable on Figure 1-(a). Figures 1-(b-d) display the evolution of each data point to its corresponding mode for the three methods.

In this example, RMS is able to recover the three components of the original distribution, as well as tiny modes or single outliers, whereas MS and BMS identify a higher number of local modes after convergence. Moreover, RMS requires less iterations to converge (9 iterations) than MS (96 iterations) and BMS (33 iterations).

## IV. CONVERGENCE OF RMS

In this section, we discuss the convergence property of RMS. Though it is not fully theoretically established here, the convergence of RMS is conjectured, based on the adaptation of the BMS convergence theorem of Chen [1]. This theorem states that there exists {$\mathbf{y}_1^{(t)},...,\mathbf{y}_N^{(t)}$} s.t. $\lim_{t\to\infty} \mathbf{y}_i^{(t)} = \mathbf{y}_i^*$. This theorem is based on three lemmas:

* The convex hull of all updated data points along the iterations are nested and converge to a limiting convex hull (Lemma 1);

* For each vertex of the converged convex hull, at least one sequence of the data points converge to this vertex (Lemma 2);

* The influence of the vertices of one converging convex hull to other data points outside this convex hull vanishes along the iterations (Lemma 3).

Based on these partial results, we discuss below the convergence of RMS under the same assumptions on $f$.

First, it is easy to show that Lemma 1 in [1] still holds for RMS. Let $C_1^{(t)}$ be the convex hull of the set of data points {$\mathbf{y}_1^{(t)},...,\mathbf{y}_N^{(t)}$} at iteration $t$. Since $\mathbf{y}_i^{(t+1)}$ in the updating equation (3) is still a convex linear combination of

<figure><img src="image_2.png" /><figcaption>FIGURE 1. Illustration of the differences between MS, BMS and RMS mode seeking algorithms, for a Gaussian kernel with bandwidth parameter $\sigma = 0.15$. (a) 300 2-D data points drawn randomly from three normal distributions $\mathcal{N}([0, 0], 0.091)$, $\mathcal{N}([0, 1], 0.091)$, $\mathcal{N}([1, 1], 0.091)$. Successive moves of iterates towards their corresponding mode with (b) the MS algorithm (14 modes); (c) the BMS algorithm (14 modes); (d) the RMS algorithm (5 modes). RMS recovers the main three modes, and two extra modes due to outliers. Final modes are displayed as green dots, and the convex hull of the original points belonging to a same final cluster is drawn in blue.</figcaption></figure>

$\{\mathbf{y}_k^{(t+1)}\}_{k=1,...,N}$ (though different from the one in BMS), then $\mathbf{y}_i^{(t+1)} \in C_1^{(t)}$. The same is true $\forall i$, which implies:

$$C_1^{(t)} \supseteq C_1^{(t+1)} \quad \forall t.$$

The proof of Lemma 2 in [1] requires showing that, for a large enough $t$, no exchange can happen at iteration $(t+1)$ between a point $\mathbf{y}_j^{(t)}$ in the interior of the convex hull $C_1^{(t)}$ and one of its vertices $\mathbf{y}_j^{(t)}$, i.e. $\mathbf{y}_j^{(t+1)}$ cannot 'pass' $\mathbf{y}_j^{(t+1)}$ to become a new vertex of $C_1^{(t+1)}$. The transposition of this lemma to the RMS update equation remains to be formally proven, but our computer simulations indicate that the same lemma can be conjectured.

The Lemma 3 of Chen can also be transposed to RMS. More precisely, the adaptation of Eq. (6) in [1] writes:

$$\sum_{k \neq i} f(\mathbf{x}_k, \mathbf{y}_i^{(t)}) \cdot (\mathbf{y}_k^{(t)} - \mathbf{y}_i^{(t+1)}) = f(\mathbf{x}_i, \mathbf{y}_i^{(t)}) \cdot (\mathbf{y}_i^{(t+1)} - \mathbf{y}_i^{(t)}) \quad (5)$$

where without loss of generality $\mathbf{y}_i^{(t)}$ is assumed being the only point converging to a vertex of $C_1^{(t)}$. For large enough $t$, since $\mathbf{y}_i^{(t+1)} - \mathbf{y}_i^{(t)}$ vanishes to zero from the above adapted Lemma 1, then depending on $k$, either $f(\mathbf{x}_k, \mathbf{y}_i^{(t)})$ or $\mathbf{y}_k^{(t)} - \mathbf{y}_i^{(t+1)}$ go down to zero. In the first case, $\mathbf{y}_i^{(t)}$ is no longer influenced by $\mathbf{x}_k$, and $\mathbf{y}_k^{(t)}$ will converge to another limit point, whereas in the second case, $\mathbf{y}_k^{(t)}$ will converge to the same limit point as $\mathbf{y}_i^{(t)}$. Note that this only sketches the proof of the third Lemma.
In summary, convergence of RMS can be conjectured at this point, but further investigations would be necessary to thoroughly prove it. In addition, why RMS provides larger attraction basins than MS and BMS remains an open question.

## V. NEAREST-NEIGHBOR RMS

Similarly to MS and BMS, the kernel-based RMS algorithm can be cast to a nearest-neighbor-based algorithm, by setting *f* as a variable-radius flat kernel based on the KNNs:

$$f_{KNN}(\mathbf{x}, \mathbf{y}) = \begin{cases} 1 & \text{if } \mathbf{x} \in \text{KNN}(\mathbf{y}) \\ 0 & \text{else} \end{cases}. \qquad (6)$$

This yields the following nearest-neighbor robust Mean-Shift (NN-RMS) update rule:

$$\begin{aligned} \mathbf{y}_i^{(t+1)} &= \frac{\sum_{k=1}^{N} f_{KNN}(\mathbf{x}_k, \mathbf{y}_i^{(t)}) \cdot \mathbf{y}_k^{(t)}}{\sum_{j=1}^{N} f_{KNN}(\mathbf{x}_j, \mathbf{y}_i^{(t)})} \\ &= \frac{1}{K} \sum_{k: \mathbf{x}_k \in \text{KNN}(\mathbf{y}_i^{(t)})} \mathbf{y}_k^{(t)} \end{aligned} \qquad (7)$$

The corresponding algorithm is detailed in Algorithm 1.

Notice that, contrarily to the kernel-based RMS approach, the new one is point-wise (local), i.e. its radius around one data point $\mathbf{y}_j$ is equal to the distance to its Kth NN in $\mathcal{X}$. By doing so, one can expect that NN-RMS better captures the local complexity of the data distribution, compared to the kernel-based version.

### Algorithm 1 NN-RMS

**Input:**

$\mathcal{X} = \{\mathbf{x}_m\}, \mathbf{x}_m \in \mathbb{R}^n, m = 1, \dots, N; \text{ the dataset}$

$K$, the number of NNs;

**Output:** The vector of points' labels $\mathbf{c} = [c_1, \dots, c_N]^t$; the set of cluster exemplars $\mathcal{E}$;

$1) \text{ Initialize } \mathcal{Y}^{(0)} = \{\mathbf{y}_m^{(0)}\} = \{\mathbf{x}_m\}, m = 1, \dots, N;$

$t = 1; \{\mathbf{y}_m^{(1)}\} = \{\mathbf{y}_m^{(0)}\};$

2) Core loop

$\text{while } t = 1 \lor \{\mathbf{y}_m^{(t)}\} \neq \{\mathbf{y}_m^{(t-1)}\} \text{ do}$

$\text{for } m = 1:N \text{ do}$

$\mathbf{j} = [j_1, j_2, \dots, j_K] = \text{KNN}(\mathcal{X}, \mathbf{y}_m^{(t)});$

$\mathbf{y}_m^{(t+1)} = \frac{1}{K} \sum_{k=1}^{K} \mathbf{y}_{j_k}^{(t)};$

$c_m^{(t+1)} = j_1;$

$t \leftarrow t + 1;$

end for

end while

3) Set $\mathcal{E}$ as the set of unique indices in $\mathbf{c}^{(t)}$;

4) Remap $\mathcal{E}$ to cluster labels in $[1 \dots C], C = |\mathcal{E}|$;

Contrarily to NN-BMS, NN-RMS does not update any- more after a small number of iterations. This can be explained easily: the KNN search in NN-RMS operates so as to find the NNs of the current updates within the set of original data points, which remain static. On the one hand, this is different

from NN-BMS in which the KNN search is performed within the set of current updates, which do continuously move along the iterations. On the other hand, the KNN search is similar to NN-MS (or NNGA [31]), but since NN-RMS is essentially a BMS algorithm (because next updates are weighted sums of the current moving points), its convergence is faster than MS. Indeed, NN-RMS stops if all the moving points have reached the condition that they share the same NNs within the original dataset, even if the last current iterates are close to each other, but distinct.

Figure 2 exemplifies the differences between three NN-based MS algorithms for mode seeking, namely Nearest-Neighbor Mean-Shift (NN-MS), Nearest-Neighbor Blurring Mean-Shift (NN-BMS), and NN-RMS. The dataset is randomly drawn from three 2-D normal distributions with identical diagonal covariance matrices, and centered at $[0, 0], [0, 1], [1, 1]$. This dataset is challenging for the clustering task, the modes of the mixture distribution being hard to distinguish on Figure 2-(a). Figures 2-(b-d) display the evolution of each data point to its corresponding mode for the three methods. Notice that NN-RMS is run until strict fixed-point convergence, whereas NN-MS and NN-BMS must be stopped as soon as the mean squared difference between successive iterates $\mathcal{Y}^{(t)}$ and $\mathcal{Y}^{(t-1)}$ is below some threshold $\epsilon$. In this experiment, we set $\epsilon = 10^{-8}$. It can be seen that NN-RMS again creates larger attraction basins than its MS and BMS counterparts. NN-RMS is able to recover the exact number of components in the actual distribution, whereas NN-MS and NN-BMS still identify a much higher number of local modes after convergence. Moreover, NN-RMS requires less iterations to converge (14 iterations) than NN-MS (16 iterations) and NN-BMS (55 iterations), as shown in Figure 3.

## VI. EXPERIMENTS

In this section, we provide experimental results obtained with several datasets, both synthetic and real, in order to assess the performance of the proposed RMS approach for clustering, and to compare it with the state-of-the-art MS and BMS, in both configurations, i.e. kernel-based and KNN-based.

### A. DATASETS

1) SYNTHETIC DATASETS

To perform the experiments and compare our approach with other clustering algorithms, we have selected a number of publicly available synthetic and real datasets. The synthetic datasets are displayed in Figure 4 with their actual (ground truth) label shown in specific colors. These datasets show diverse configurations, from well separated to highly overlapped clusters, from convex to non-convex and highly intricate clusters, and from balanced to unbalanced clusters.

2) REAL DATASETS

The real datasets used in the experiments are summarized in Table 1. They show different configurations, from low to moderate dimensionality, and various number of instances
<figure><img src="image_3.png" /><figcaption>**FIGURE 2.** Illustration of the differences between NN-MS, NN-BMS and NN-RMS mode seeking algorithms, for $K = 17$. (a) 300 2-D data points drawn randomly from 3 normal distributions $N([0, 0], 0.16I)$. $N([0, 1], 0.16I)$, $N([1, 1], 0.16I)$. Successive moves of iterates towards their corresponding mode with (b) the NN-MS algorithm (56 distinct modes); (c) the NN-BMS algorithm (11 distinct modes); (d) the NN-RMS algorithm. NN-RMS recovers the exact number of 3 modes. The final modes are displayed as green dots, and the convex hull of the original points belonging to a same final cluster is drawn in blue.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>**FIGURE 3.** Evolution of the mean squared error (in log scale) between successive iterates for NN-MS, NN-BMS and NN-RMS for the dataset shown in Figure 2. Notice that NN-RMS is stopped at iteration 14 with zero mean squared error.</figcaption></figure>

and number of clusters. All these datasets have been used without any pre-processing, except the *AttFace* dataset for which the original dimension $n = 4096$ has been reduced to $n = 20$ by means of principal component analysis (PCA).

## B. SELECTED METHODS

With regard to similar methods based on the MS principle and their NN variants, we have compared both the NN-based and the kernel-based RMS proposed method to their equivalent MS and BMS counterparts. For comparison, we selected the

<figure><img src="image_5.png" /><figcaption>**FIGURE 4.** Various 2D synthetic datasets used in experiments. All but the DataS1 dataset (available at https://www.science.org/doi/10.1126/science.1242072) can be downloaded from http://cs.joensuu.fi/sipu/datasets/.</figcaption></figure>

<table><caption>**TABLE 1.** Real datasets.</caption><thead><tr><td>Name</td><td>N</td><td>n</td><td>C<sub>true</sub></td><td>Location</td></tr></thead><tbody><tr><td>Iris</td><td>150</td><td>4</td><td>3</td><td>https://archive.ics.uci.edu/</td></tr><tr><td>Ecoli</td><td>336</td><td>7</td><td>8</td><td>https://archive.ics.uci.edu/</td></tr><tr><td>Seeds</td><td>210</td><td>7</td><td>3</td><td>https://archive.ics.uci.edu/</td></tr><tr><td>Banknote</td><td>1372</td><td>4</td><td>2</td><td>https://archive.ics.uci.edu/</td></tr><tr><td>Segment</td><td>2310</td><td>19</td><td>7</td><td>https://archive.ics.uci.edu/</td></tr><tr><td>AttFace</td><td>400</td><td>20</td><td>40</td><td>https://scikit-learn.org/</td></tr></tbody></table>

MedoidShift method proposed in [38], which was adapted to the KNN case, as suggested by the authors. We also compared our approach with two nearest-neighbor density-based clustering methods, namely kNN-DPC, and GWENN. These methods were recently improved and compared in [24] for their applicability to pixel clustering in hyperspectral images. They were chosen because they require the same input parameter $K$ as the NN-based MS methods. Also, due to the specific convergence of NN-BMS as illustrated in Figure 3, an additional parameter $\epsilon$ was used to stop the algorithm. In all our experiments, we set $\epsilon = 10^{-6}$. For kernel-based MS methods, we have chosen the Gaussian kernel detailed in Eq. (4).

## C. SELECTED VALIDATION CRITERIA

To allow the comparison of different results, we used the following cluster validation criteria:

* Since all the datasets include a ground truth labeling as an external data for cluster assessment, the overall accuracy (OA), average accuracy (AA), kappa index, can be obtained after optimal pairing of cluster labels with
the actual ground truth classes owing to the Munkres assignment algorithm [39];

* The purity and normalized mutual information (NMI) indices [40] are also based on the relationship between the ground truth and the predicted labels, but do not require label reassignment;

* The consistency violation ratio (CVR) [41] is a clustering index based on an information-theoretic concept, which is also fitted to non-convex clusters; a lower CVR indicates a better clustering result. Contrarily to the previous criteria, the CVR index does not require the ground truth labels, which makes it useful to assess the results of unsupervised classification.

In Figure 5, we illustrate the evaluation of the results obtained by applying NN-MS, NN-BMS, NN-RMS, and NN-MedoidShift to the *Flame* dataset, as a function of the number of NNs *K* in the range [6, 50]. The results clearly show that NN-RMS provides an estimation of the correct number of clusters close to the actual one for a much lower number of NNs *K*. In comparison, NN-MS gives a very high number of clusters, as well as NN-BMS and NN-MedoidShift. The latter reaches the correct number of clusters for a higher number of NNs than NN-RMS, and for NN-BMS even higher. The OA index shown on Figure 5-(b) reveals the potential of NN-RMS to quickly approach the ideal partition for very low *K*. On Figure 5-(c), the low CVR indices within a large range of *K* confirms the robustness of NN-RMS with respect to the selection of the parameter *K*.

## D. RESULTS

### 1) SYNTHETIC DATA

The results obtained on synthetic datasets are given in Table 2. In addition to the cluster indices mentioned above, we also added the number of output clusters, the computation time and the number of iterations for each method used for comparison. For each dataset, the clustering task was performed with two groups of methods, namely NN-based and kernel-based methods. The values displayed in Table 2 correspond to the specific values of *K* (for NN-based methods) or $\sigma$ (for the kernel-based methods) providing the best kappa index.

Concerning the NN-based methods, it can be seen that NN-RMS provided the best kappa indices on five over the nine datasets (*Aggregation*, *DataS1*, *S4*, *Unbalance* and *Worms2d*). Furthermore, NN-RMS provided the second best kappa on three other datasets (*Flame*, *Spiral* and *Birch1*). One important issue of this comparison is that these best kappa results for NN-RMS were obtained for the lowest number of NNs among all the compared methods on eight over the nine datasets. This result can be considered as significant since most of the optimal values of *K* for the other methods are often more than twice the optimal values for NN-RMS. It is also noticeable that NN-RMS found the correct number of clusters in seven over nine datasets, and that this number is very close to the actual one in the remaining cases.

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

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

<figure><img src="image_8.png" /><figcaption>**FIGURE 5.** Clustering results for the *Flame* dataset for various methods, as a function of the number of neighbors *K*. (a) Number of clusters; (b) Overall Accuracy; (c) Consistency Violation Ratio (CVR).</figcaption></figure>

With regard to kernel-based Mean-Shift methods, over the nine datasets, G-RMS again outperforms G-MS and G-BMS on six datasets (*Flame*, *Spiral*, *Aggregation*, *DataS1*, *S4* and *Worms2d*). Also, in all cases, G-RMS never requires a higher Gaussian kernel aperture than G-MS and G-BMS to achieve the results with the best kappa indices, and for most datasets the optimal aperture is well below the ones provided by G-MS and G-BMS. This finding is in accordance with the results of the NN-based MS methods.

Note that for the *R15* dataset, all methods (NN- or kernel-based) perform equally well, except NN-MS and NN-MedShift with lower kappa, NMI and purity, and higher CVR.
<table><caption>TABLE 2. Comparison of clustering methods for various synthetic datasets.</caption><thead><tr><th>Dataset</th><th>Method</th><th>K / σ</th><th>C</th><th>AA</th><th>OA</th><th>kappa</th><th>CVR</th><th>NMI</th><th>purity</th><th>time (s)</th><th>nitr</th></tr></thead><tbody><tr><td rowspan="7">Flame<br>n = 2<br>N = 240<br>C<sub>true</sub> = 2</td><td>kNNDPC</td><td>28</td><td>2</td><td>100</td><td>100</td><td>1</td><td>0.026</td><td>1</td><td>1</td><td><strong>0.00186</strong></td><td>5</td></tr><tr><td>GWENN</td><td>26</td><td>2</td><td>98.5</td><td>98.8</td><td>0.973</td><td>0.0197</td><td>0.899</td><td>0.988</td><td>0.00943</td><td>2</td></tr><tr><td>NN-MS</td><td>48</td><td>10</td><td>53.5</td><td>50.8</td><td>0.332</td><td>0.277</td><td>0.479</td><td>0.508</td><td>0.00662</td><td>35</td></tr><tr><td>NN-BMS</td><td>42</td><td>2</td><td>98.3</td><td>98.8</td><td>0.973</td><td>0.0238</td><td>0.911</td><td>0.988</td><td>4.03</td><td>843</td></tr><tr><td>NN-RMS</td><td>18</td><td>2</td><td>99.1</td><td>99.2</td><td>0.982</td><td><strong>0.0186</strong></td><td>0.927</td><td>0.992</td><td>0.0665</td><td>12</td></tr><tr><td>NN-MedShift</td><td>26</td><td>2</td><td>99.1</td><td>99.2</td><td>0.982</td><td><strong>0.0186</strong></td><td>0.927</td><td>0.992</td><td>0.0265</td><td>5</td></tr><tr><td>G-MS</td><td>1.7</td><td>2</td><td>98.5</td><td>98.8</td><td>0.973</td><td>0.0197</td><td>0.899</td><td>0.988</td><td>0.824</td><td>123</td></tr><tr><td rowspan="3">Spiral<br>n = 2<br>N = 321<br>C<sub>true</sub> = 3</td><td>G-BMS</td><td>1.7</td><td>5</td><td>75.8</td><td>70.4</td><td>0.538</td><td>0.0605</td><td>0.622</td><td>0.704</td><td>0.0826</td><td>10</td></tr><tr><td>G-RMS</td><td><strong>1.08</strong></td><td>2</td><td><strong>99.1</strong></td><td><strong>99.2</strong></td><td><strong>0.982</strong></td><td><strong>0.0186</strong></td><td><strong>0.927</strong></td><td><strong>0.992</strong></td><td>0.201</td><td>22</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="7">Aggregation<br>n = 2<br>N = 788<br>C<sub>true</sub> = 7</td><td>kNNDPC</td><td>14</td><td>3</td><td>100</td><td>100</td><td>1</td><td>0.0686</td><td>1</td><td>1</td><td><strong>0.0026</strong></td><td>7</td></tr><tr><td>GWENN</td><td>12</td><td>3</td><td>85.9</td><td>85.9</td><td>0.789</td><td><strong>0.0432</strong></td><td>0.634</td><td>0.859</td><td>0.0127</td><td>2</td></tr><tr><td>NN-MS</td><td>22</td><td>108</td><td>27.5</td><td>27.6</td><td>0.129</td><td>0.231</td><td>0.314</td><td>0.279</td><td>0.00957</td><td>21</td></tr><tr><td>NN-BMS</td><td>16</td><td>14</td><td>26.5</td><td>26.6</td><td>0.194</td><td>0.119</td><td>0.318</td><td>0.266</td><td>0.411</td><td>71</td></tr><tr><td>NN-RMS</td><td>8</td><td>3</td><td>90.7</td><td>90.7</td><td>0.861</td><td>0.064</td><td>0.721</td><td>0.907</td><td>0.0883</td><td>12</td></tr><tr><td>NN-MedShift</td><td>12</td><td>12</td><td>34.3</td><td>34.3</td><td>0.258</td><td>0.118</td><td>0.357</td><td>0.343</td><td>0.033</td><td>6</td></tr><tr><td>G-MS</td><td>1.76</td><td>21</td><td>50.4</td><td>50.3</td><td>0.403</td><td>0.241</td><td>0.611</td><td>0.503</td><td>7.11</td><td>1e+03</td></tr><tr><td rowspan="3">RI5<br>n = 2<br>N = 600<br>C<sub>true</sub> = 15</td><td>G-BMS</td><td><strong>1.39</strong></td><td>26</td><td>26.3</td><td>26.3</td><td>0.16</td><td>0.344</td><td>0.43</td><td>0.263</td><td>0.00778</td><td>208</td></tr><tr><td>G-RMS</td><td><strong>1.39</strong></td><td>3</td><td><strong>95.5</strong></td><td><strong>95.5</strong></td><td><strong>0.933</strong></td><td><strong>0.139</strong></td><td><strong>0.841</strong></td><td><strong>0.955</strong></td><td>0.179</td><td>16</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="7">DataS1<br>n = 2<br>N = 2000<br>C<sub>true</sub> = 5</td><td>kNNDPC</td><td>16</td><td>15</td><td>99.7</td><td>99.7</td><td><strong>0.996</strong></td><td><strong>0.00181</strong></td><td><strong>0.994</strong></td><td><strong>0.997</strong></td><td><strong>0.00252</strong></td><td>4</td></tr><tr><td>GWENN</td><td>16</td><td>15</td><td>99.7</td><td>99.7</td><td><strong>0.996</strong></td><td><strong>0.00181</strong></td><td><strong>0.994</strong></td><td><strong>0.997</strong></td><td>0.0157</td><td>2</td></tr><tr><td>NN-MS</td><td>38</td><td>16</td><td>99.5</td><td>99.5</td><td>0.995</td><td>0.0025</td><td>0.993</td><td>0.995</td><td>0.0239</td><td>8</td></tr><tr><td>NN-BMS</td><td>22</td><td>15</td><td>99.7</td><td>99.7</td><td><strong>0.996</strong></td><td><strong>0.00181</strong></td><td><strong>0.994</strong></td><td><strong>0.997</strong></td><td>0.286</td><td>18</td></tr><tr><td>NN-RMS</td><td>10</td><td>15</td><td>99.7</td><td>99.7</td><td><strong>0.996</strong></td><td><strong>0.00181</strong></td><td><strong>0.994</strong></td><td><strong>0.997</strong></td><td>0.207</td><td>12</td></tr><tr><td>NN-MedShift</td><td>16</td><td>15</td><td>99.3</td><td>99.3</td><td>0.993</td><td>0.0024</td><td>0.989</td><td>0.993</td><td>0.0873</td><td>4</td></tr><tr><td>G-MS</td><td>0.424</td><td>15</td><td>99.7</td><td>99.7</td><td><strong>0.996</strong></td><td>0</td><td><strong>0.994</strong></td><td><strong>0.997</strong></td><td>0.247</td><td>13</td></tr><tr><td rowspan="3">S4<br>n = 2<br>N = 5000<br>C<sub>true</sub> = 15</td><td>G-BMS</td><td>0.424</td><td>15</td><td>99.7</td><td>99.7</td><td><strong>0.996</strong></td><td>0</td><td><strong>0.994</strong></td><td><strong>0.997</strong></td><td>0.0186</td><td>7</td></tr><tr><td>G-RMS</td><td><strong>0.267</strong></td><td>15</td><td>99.7</td><td>99.7</td><td><strong>0.996</strong></td><td>0</td><td><strong>0.994</strong></td><td><strong>0.997</strong></td><td>0.238</td><td>13</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="7">Unbalance<br>n = 2<br>N = 6500<br>C<sub>true</sub> = 8</td><td>kNNDPC</td><td>200</td><td>4</td><td>78.5</td><td>92.8</td><td>0.899</td><td>0.0173</td><td>0.897</td><td><strong>0.986</strong></td><td><strong>0.0121</strong></td><td>7</td></tr><tr><td>GWENN</td><td>180</td><td>4</td><td>78.5</td><td>92.8</td><td>0.898</td><td>0.0198</td><td>0.892</td><td>0.985</td><td>0.0804</td><td>2</td></tr><tr><td>NN-MS</td><td>180</td><td>29</td><td>83</td><td>70.3</td><td>0.643</td><td>0.0886</td><td>0.721</td><td>0.703</td><td>0.391</td><td>16</td></tr><tr><td>NN-BMS</td><td>140</td><td>10</td><td>74.4</td><td>59</td><td>0.528</td><td>0.0337</td><td>0.714</td><td>0.59</td><td>4.81</td><td>21</td></tr><tr><td>NN-RMS</td><td>60</td><td>5</td><td><strong>97.5</strong></td><td><strong>98.4</strong></td><td><strong>0.977</strong></td><td><strong>0.0167</strong></td><td><strong>0.938</strong></td><td>0.984</td><td>3.17</td><td>15</td></tr><tr><td>NN-MedShift</td><td>190</td><td>5</td><td>66.7</td><td>71.2</td><td>0.63</td><td>0.0322</td><td>0.73</td><td>0.749</td><td>1.19</td><td>5</td></tr><tr><td>G-MS</td><td>0.0815</td><td>14</td><td>95.6</td><td>95.9</td><td>0.943</td><td>0.0442</td><td>0.9</td><td>0.959</td><td>2.5</td><td>24</td></tr><tr><td rowspan="3">Birch1<br>n = 2<br>N = 100000<br>C<sub>true</sub> = 100</td><td>G-BMS</td><td>0.0815</td><td>7</td><td>95.7</td><td>95.9</td><td>0.943</td><td>0.0212</td><td>0.896</td><td>0.959</td><td>1.25</td><td>15</td></tr><tr><td>G-RMS</td><td><strong>0.0409</strong></td><td>6</td><td><strong>98.7</strong></td><td><strong>99.4</strong></td><td><strong>0.991</strong></td><td><strong>0.012</strong></td><td><strong>0.976</strong></td><td><strong>0.994</strong></td><td>0.977</td><td>9</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="7">Worms2d<br>n = 2<br>N = 105600<br>C<sub>true</sub> = 35</td><td>kNNDPC</td><td>190</td><td>15</td><td>79.8</td><td>79.9</td><td>0.785</td><td>0.0215</td><td>0.728</td><td>79.9</td><td><strong>0.0387</strong></td><td>6</td></tr><tr><td>GWENN</td><td>140</td><td>15</td><td>79.9</td><td>80</td><td>0.785</td><td>0.0227</td><td>0.726</td><td>80</td><td>0.263</td><td>2</td></tr><tr><td>NN-MS</td><td>200</td><td>36</td><td>73.2</td><td>73.3</td><td>0.716</td><td>0.0416</td><td>0.704</td><td>73.3</td><td>1.83</td><td>26</td></tr><tr><td>NN-BMS</td><td>200</td><td>15</td><td>79.8</td><td>79.9</td><td>0.784</td><td>0.0234</td><td>0.722</td><td>79.9</td><td>1.04</td><td>14</td></tr><tr><td>NN-RMS</td><td>40</td><td>15</td><td><strong>80.2</strong></td><td><strong>80.3</strong></td><td><strong>0.789</strong></td><td><strong>0.0209</strong></td><td><strong>0.732</strong></td><td><strong>80.3</strong></td><td>0.504</td><td>14</td></tr><tr><td>NN-MedShift</td><td>90</td><td>15</td><td>79.8</td><td>79.9</td><td>0.784</td><td>0.0235</td><td>0.722</td><td>79.9</td><td>0.167</td><td>4</td></tr><tr><td>G-MS</td><td>4.4e4</td><td>17</td><td>79.8</td><td>79.9</td><td>0.785</td><td>0.0232</td><td>0.728</td><td>0.799</td><td>36.3</td><td>63</td></tr><tr><td rowspan="3">Worms2d<br>n = 2<br>N = 105600<br>C<sub>true</sub> = 35</td><td>G-BMS</td><td>3.5e4</td><td>26</td><td>79.1</td><td>79.1</td><td>0.776</td><td>0.0236</td><td>0.724</td><td>0.791</td><td>69.4</td><td>61</td></tr><tr><td>G-RMS</td><td><strong>2.2e4</strong></td><td>19</td><td><strong>79.9</strong></td><td><strong>79.9</strong></td><td><strong>0.785</strong></td><td><strong>0.019</strong></td><td><strong>0.729</strong></td><td><strong>0.799</strong></td><td>36.3</td><td>23</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="7">Birch1<br>n = 2<br>N = 100000<br>C<sub>true</sub> = 100</td><td>kNNDPC</td><td>170</td><td>4</td><td>50</td><td>93.8</td><td>0.914</td><td>0</td><td>0.954</td><td>1</td><td><strong>0.0321</strong></td><td>7</td></tr><tr><td>GWENN</td><td>150</td><td>4</td><td>50</td><td>93.8</td><td>0.914</td><td>0</td><td>0.954</td><td>1</td><td>0.186</td><td>2</td></tr><tr><td>NN-MS</td><td>200</td><td>73</td><td>58.4</td><td>26.2</td><td>0.213</td><td>0.0836</td><td>0.564</td><td>0.266</td><td>4.37</td><td>48</td></tr><tr><td>NN-BMS</td><td>190</td><td>24</td><td>32.6</td><td>21.8</td><td>0.167</td><td>0.0297</td><td>0.584</td><td>0.257</td><td>70.8</td><td>28</td></tr><tr><td>NN-RMS</td><td>50</td><td>8</td><td><strong>100</strong></td><td><strong>100</strong></td><td>1</td><td>7e-5</td><td>1</td><td>1</td><td>50.2</td><td>22</td></tr><tr><td>NN-MedShift</td><td>200</td><td>12</td><td>30.7</td><td>46.4</td><td>0.374</td><td>0.0348</td><td>0.681</td><td>0.525</td><td>16</td><td>6</td></tr><tr><td>G-MS</td><td>1.05e4</td><td>8</td><td><strong>100</strong></td><td><strong>100</strong></td><td>1</td><td>7e-5</td><td>1</td><td>1</td><td>34.8</td><td>39</td></tr><tr><td rowspan="3">Birch1<br>n = 2<br>N = 100000<br>C<sub>true</sub> = 100</td><td>G-BMS</td><td>1.05e4</td><td>8</td><td><strong>100</strong></td><td><strong>100</strong></td><td>1</td><td>7e-5</td><td>1</td><td>1</td><td>2.95</td><td>1e+03</td></tr><tr><td>G-RMS</td><td><strong>1.05e4</strong></td><td>8</td><td><strong>100</strong></td><td><strong>100</strong></td><td>1</td><td>7e-5</td><td>1</td><td>1</td><td>788</td><td>1e+03</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="7">Worms2d<br>n = 2<br>N = 105600<br>C<sub>true</sub> = 35</td><td>kNNDPC</td><td>300</td><td>100</td><td>97.8</td><td>97.8</td><td>0.977</td><td><strong>0.00615</strong></td><td>0.973</td><td>97.8</td><td><strong>0.808</strong></td><td>7</td></tr><tr><td>GWENN</td><td>500</td><td>100</td><td><strong>99.3</strong></td><td><strong>99.3</strong></td><td><strong>0.993</strong></td><td>0.00664</td><td><strong>0.99</strong></td><td><strong>99.3</strong></td><td>7.05</td><td>2</td></tr><tr><td>NN-MS</td><td>500</td><td>183</td><td>83.2</td><td>83.2</td><td>0.83</td><td>0.014</td><td>0.957</td><td>83.2</td><td>85.3</td><td>31</td></tr><tr><td>NN-BMS</td><td>500</td><td>122</td><td>88.7</td><td>88.6</td><td>0.885</td><td>0.00865</td><td>0.974</td><td>88.6</td><td>172</td><td>59</td></tr><tr><td>NN-RMS</td><td>500</td><td>101</td><td>99.2</td><td>99.2</td><td>0.992</td><td>0.00673</td><td>0.989</td><td>99.2</td><td>50.9</td><td>18</td></tr><tr><td>NN-MedShift</td><td>300</td><td>100</td><td>99</td><td>99</td><td>0.99</td><td>0.00688</td><td>0.986</td><td>99</td><td>9.61</td><td>5</td></tr><tr><td>G-MS</td><td>3.06e4</td><td>102</td><td><strong>99.4</strong></td><td><strong>99.4</strong></td><td><strong>0.994</strong></td><td>0.00668</td><td><strong>0.991</strong></td><td><strong>99.4</strong></td><td>2.36e3</td><td>36</td></tr><tr><td rowspan="3">Worms2d<br>n = 2<br>N = 105600<br>C<sub>true</sub> = 35</td><td>G-BMS</td><td>2.43e4</td><td>100</td><td>99.4</td><td>99.4</td><td>0.993</td><td>0.00657</td><td>0.991</td><td>99.4</td><td>205</td><td>10</td></tr><tr><td>G-RMS</td><td><strong>1.53e4</strong></td><td>100</td><td>99</td><td>99</td><td>0.99</td><td><strong>0.0064</strong></td><td>0.986</td><td>99</td><td>186</td><td>11</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="7">Worms2d<br>n = 2<br>N = 105600<br>C<sub>true</sub> = 35</td><td>kNNDPC</td><td>800</td><td>40</td><td>56.2</td><td>56.5</td><td>0.551</td><td><strong>0.00738</strong></td><td>0.639</td><td>59.2</td><td><strong>1.62</strong></td><td>9</td></tr><tr><td>GWENN</td><td>750</td><td>40</td><td>55.3</td><td>55.6</td><td>0.543</td><td>0.00805</td><td>0.636</td><td>58.5</td><td>10.6</td><td>2</td></tr><tr><td>NN-MS</td><td>1e+03</td><td>331</td><td>42.5</td><td>39.4</td><td>0.382</td><td>0.0341</td><td>0.583</td><td>40.9</td><td>1e+03</td><td>175</td></tr><tr><td>NN-BMS</td><td>950</td><td>75</td><td>39.6</td><td>32.8</td><td>0.318</td><td>0.0115</td><td>0.598</td><td>32.9</td><td>455</td><td>78</td></tr><tr><td>NN-RMS</td><td>350</td><td>36</td><td><strong>60.5</strong></td><td><strong>59.6</strong></td><td><strong>0.582</strong></td><td>0.00985</td><td><strong>0.646</strong></td><td><strong>63.2</strong></td><td>47.6</td><td>21</td></tr><tr><td>NN-MedShift</td><td>950</td><td>46</td><td>45</td><td>44.1</td><td>0.426</td><td>0.00994</td><td>0.604</td><td>47.2</td><td>32.9</td><td>6</td></tr><tr><td>G-MS</td><td>89.9</td><td>182</td><td>49.4</td><td>53.2</td><td>0.517</td><td><strong>0.0105</strong></td><td>0.626</td><td>59.5</td><td>4.08e4</td><td>469</td></tr><tr><td rowspan="3">Worms2d<br>n = 2<br>N = 105600<br>C<sub>true</sub> = 35</td><td>G-BMS</td><td>89.9</td><td>229</td><td>49.2</td><td>43.6</td><td>0.423</td><td>0.0114</td><td>0.603</td><td>46.9</td><td>2.00e3</td><td>23</td></tr><tr><td>G-RMS</td><td><strong>28.4</strong></td><td>613</td><td><strong>55.8</strong></td><td><strong>54.5</strong></td><td><strong>0.531</strong></td><td>0.0143</td><td><strong>0.627</strong></td><td><strong>61.4</strong></td><td>3.78e3</td><td>54</td></tr></tbody></table>
<table><caption>TABLE 3. Comparison of clustering methods for various real datasets.</caption><thead><tr><th>Dataset</th><th>Method</th><th>K</th><th>C</th><th>AA</th><th>OA</th><th>kappa</th><th>CVR</th><th>NMI</th><th>purity</th><th>time (s)</th><th>nitr</th></tr></thead><tbody><tr><td rowspan="6">Iris<br>n = 4<br>N = 150<br>C<sub>true</sub> = 3</td><td>kNNDPC</td><td>20</td><td><b>3</b></td><td>90.7</td><td>90.7</td><td>0.86</td><td>0.0172</td><td>0.806</td><td>0.907</td><td><b>0.00255</b></td><td>4</td></tr><tr><td>GWENN</td><td>20</td><td><b>3</b></td><td>89.3</td><td>89.3</td><td>0.84</td><td>0.0223</td><td>0.791</td><td>0.893</td><td>0.00741</td><td>2</td></tr><tr><td>NN-MS</td><td>46</td><td>5</td><td>84</td><td>84</td><td>0.776</td><td>0.182</td><td>0.735</td><td>0.84</td><td>0.00403</td><td>11</td></tr><tr><td>NN-BMS</td><td>48</td><td><b>3</b></td><td><b>94</b></td><td><b>94</b></td><td><b>0.91</b></td><td>0.13</td><td><b>0.817</b></td><td><b>0.94</b></td><td>0.0362</td><td>6</td></tr><tr><td>NN-RMS</td><td><b>12</b></td><td><b>3</b></td><td>90</td><td>90</td><td>0.85</td><td><b>0.0151</b></td><td>0.798</td><td>0.9</td><td>0.0516</td><td>12</td></tr><tr><td>NN-MedShift</td><td>26</td><td><b>3</b></td><td>90</td><td>90</td><td>0.85</td><td>0.0812</td><td>0.778</td><td>0.9</td><td>0.0107</td><td>4</td></tr><tr><td rowspan="6">Ecoli<br>n = 7<br>N = 336<br>C<sub>true</sub> = 8</td><td>kNNDPC</td><td>40</td><td>3</td><td>34.7</td><td>76.5</td><td>0.662</td><td>0.0612</td><td>0.662</td><td><b>0.946</b></td><td>0.0371</td><td>4</td></tr><tr><td>GWENN</td><td>26</td><td>3</td><td>34.7</td><td>76.2</td><td>0.659</td><td><b>0.0437</b></td><td><b>0.663</b></td><td>0.943</td><td><b>0.00897</b></td><td>2</td></tr><tr><td>NN-MS</td><td>50</td><td>6</td><td>36.4</td><td>75.6</td><td>0.658</td><td>0.209</td><td>0.636</td><td>0.836</td><td>0.0161</td><td>15</td></tr><tr><td>NN-BMS</td><td>46</td><td>4</td><td><b>41.7</b></td><td><b>78</b></td><td><b>0.694</b></td><td>0.108</td><td>0.648</td><td>0.86</td><td>0.204</td><td>11</td></tr><tr><td>NN-RMS</td><td><b>8</b></td><td>3</td><td>34.7</td><td>76.2</td><td>0.659</td><td>0.0445</td><td><b>0.663</b></td><td>0.943</td><td>0.18</td><td>13</td></tr><tr><td>NN-MedShift</td><td>40</td><td>3</td><td>32.1</td><td>72.9</td><td>0.604</td><td>0.114</td><td>0.585</td><td>0.899</td><td>0.0631</td><td>4</td></tr><tr><td rowspan="6">Seeds<br>n = 7<br>N = 210<br>C<sub>true</sub> = 3</td><td>kNNDPC</td><td>18</td><td><b>3</b></td><td>89</td><td>89</td><td>0.836</td><td>0.136</td><td>0.719</td><td>0.89</td><td><b>0.00452</b></td><td>4</td></tr><tr><td>GWENN</td><td>20</td><td><b>3</b></td><td>90</td><td>90</td><td>0.85</td><td>0.147</td><td>0.723</td><td>0.9</td><td>0.00619</td><td>2</td></tr><tr><td>NN-MS</td><td>46</td><td><b>6</b></td><td>84.8</td><td>84.8</td><td>0.778</td><td>0.402</td><td>0.663</td><td>0.848</td><td>0.00595</td><td>21</td></tr><tr><td>NN-BMS</td><td>46</td><td><b>3</b></td><td>90</td><td>90</td><td>0.85</td><td>0.203</td><td>0.704</td><td>0.9</td><td>0.111</td><td>12</td></tr><tr><td>NN-RMS</td><td><b>8</b></td><td><b>3</b></td><td>90.5</td><td>90.5</td><td>0.857</td><td><b>0.129</b></td><td>0.731</td><td>0.905</td><td>0.14</td><td>18</td></tr><tr><td>NN-MedShift</td><td>16</td><td><b>3</b></td><td><b>91.9</b></td><td><b>91.9</b></td><td><b>0.879</b></td><td>0.184</td><td><b>0.743</b></td><td><b>0.919</b></td><td>0.0677</td><td>5</td></tr><tr><td rowspan="6">Banknote<br>n = 4<br>N = 1372<br>C<sub>true</sub> = 2</td><td>kNNDPC</td><td>180</td><td><b>2</b></td><td>76.4</td><td>73.8</td><td>0.498</td><td><b>0.00974</b></td><td>0.342</td><td>0.738</td><td><b>0.00847</b></td><td>6</td></tr><tr><td>GWENN</td><td>180</td><td><b>2</b></td><td>74.7</td><td>72.3</td><td>0.469</td><td>0.0636</td><td>0.257</td><td>0.723</td><td>0.0783</td><td>2</td></tr><tr><td>NN-MS</td><td>440</td><td><b>2</b></td><td>70.6</td><td>68.4</td><td>0.392</td><td>0.125</td><td>0.162</td><td>0.684</td><td>0.36</td><td>35</td></tr><tr><td>NN-BMS</td><td>320</td><td><b>2</b></td><td>70.3</td><td>68.4</td><td>0.388</td><td>0.0951</td><td>0.146</td><td>0.684</td><td>9</td><td>46</td></tr><tr><td>NN-RMS</td><td><b>120</b></td><td><b>2</b></td><td><b>91.9</b></td><td><b>91.6</b></td><td><b>0.832</b></td><td>0.0587</td><td><b>0.594</b></td><td><b>0.916</b></td><td>3.7</td><td>24</td></tr><tr><td>NN-MedShift</td><td>160</td><td><b>3</b></td><td>77.3</td><td>75</td><td>0.583</td><td>0.155</td><td>0.531</td><td>0.75</td><td>0.732</td><td>7</td></tr><tr><td rowspan="6">Segment<br>n = 19<br>N = 2310<br>C<sub>true</sub> = 7</td><td>kNNDPC</td><td>90</td><td>13</td><td>65</td><td>65</td><td>0.6</td><td>0.215</td><td>0.627</td><td>0.67</td><td><b>0.0127</b></td><td>6</td></tr><tr><td>GWENN</td><td>90</td><td>8</td><td>66.4</td><td>66.4</td><td>0.609</td><td>0.218</td><td>0.598</td><td>0.689</td><td>0.0791</td><td>2</td></tr><tr><td>NN-MS</td><td>180</td><td>19</td><td>45.1</td><td>45.1</td><td>0.371</td><td>0.744</td><td>0.435</td><td>0.494</td><td>0.925</td><td>36</td></tr><tr><td>NN-BMS</td><td>200</td><td><b>7</b></td><td>59.5</td><td>59.5</td><td>0.527</td><td>0.409</td><td>0.525</td><td>0.595</td><td>38.9</td><td>71</td></tr><tr><td>NN-RMS</td><td><b>50</b></td><td><b>7</b></td><td><b>71.2</b></td><td><b>71.2</b></td><td><b>0.664</b></td><td><b>0.141</b></td><td><b>0.643</b></td><td><b>0.74</b></td><td>8.31</td><td>18</td></tr><tr><td>NN-MedShift</td><td>120</td><td><b>7</b></td><td>59</td><td>59</td><td>0.521</td><td>0.559</td><td>0.488</td><td>0.597</td><td>2.25</td><td>4</td></tr><tr><td rowspan="6">AttFace<br>n = 20<br>N = 400<br>C<sub>true</sub> = 40</td><td>kNNDPC</td><td>6</td><td>42</td><td>72</td><td>72</td><td>0.713</td><td>0.47</td><td><b>0.866</b></td><td>0.762</td><td><b>0.00229</b></td><td>3</td></tr><tr><td>GWENN</td><td>5</td><td>45</td><td>70.3</td><td>70.3</td><td>0.695</td><td>0.438</td><td>0.856</td><td>0.748</td><td>0.0143</td><td>2</td></tr><tr><td>NN-MS</td><td>10</td><td>103</td><td>53.5</td><td>53.5</td><td>0.526</td><td><b>0.404</b></td><td>0.778</td><td>0.555</td><td>0.0263</td><td>11</td></tr><tr><td>NN-BMS</td><td>7</td><td>37</td><td><b>75.8</b></td><td><b>75.8</b></td><td><b>0.751</b></td><td>0.464</td><td>0.846</td><td><b>0.797</b></td><td>0.44</td><td>30</td></tr><tr><td>NN-RMS</td><td><b>4</b></td><td><b>40</b></td><td>70</td><td>70</td><td>0.692</td><td>0.456</td><td>0.847</td><td>0.76</td><td>0.188</td><td>12</td></tr><tr><td>NN-MedShift</td><td>5</td><td>43</td><td>67</td><td>67</td><td>0.662</td><td>0.438</td><td>0.8</td><td>0.693</td><td>0.0586</td><td>4</td></tr></tbody></table>

## 2) REAL DATA

Table 3 provides the clustering results obtained on the real datasets described above. Here, only NN-based MS methods were considered, as well as kNNDPC, GWENN and NN-MedShift. Again, these results correspond to the optimal parameter *K* in terms of output kappa index. The variety in data size (from *N* = 150 to 2310), dimensionality (up to *n* = 20), and cluster shape makes it difficult to draw clear conclusions from these observations. Here, over the six datasets, in terms of kappa index, NN-RMS performs better than the other methods in two cases (*Banknote* and *Segment*), whereas NN-BMS is better for three others (*Iris*, *Ecoli* and *Attface*). However, NN-RMS was able to provide the correct number of clusters in all cases, except for the *Ecoli* dataset for which all the methods failed. This is particularly true for the *Attface* dataset, despite the relative high dimensionality (*n* = 20) and low populated classes (only 10 data points per class) which makes it a challenging clustering problem.

Finally, similarly as above for the synthetic datasets, the best results in terms of kappa index reported for NN-RMS in all cases correspond to lower values of *K* than that of the other methods.

## 3) APPLICATION TO PIXEL CLUSTERING IN HYPERSPECTRAL IMAGES

We provide here early experimental results of the application of NN-RMS to hyperspectral image pixel clustering. Hyperspectral images are composed of hundreds of spectral

bands covering a specific spectral range, generally including the visible range, the near-infrared range and sometimes the short-wave infrared range. Each pixel can be viewed as a high-dimensional vector of spectral radiances (or reflectances) from which a high amount of valuable information can be extracted to remotely identify objects or land cover types when the hyperspectral camera is operated on board an aerial platform (aircraft of UAV). We have selected a publicly available hyperspectral image [42]. It comprises 86 × 83 pixels, has 204 spectral bands (*n* = 204) and includes six classes of vegetation cover. Figure 6-(a) and (b) show respectively a color composite of the hyperspectral image and the corresponding ground truth map used for clustering assessment. In this experiment, we applied the same protocol as above, i.e. we applied several nearest-neighbor-based clustering method with *K* varying in the range from 100 to 400 by steps of 20. Four methods were compared: kNNDPC and GWENN as density-based clustering methods, and NN-MedShift and NN-RMS as Mean-Shift-type methods. For each method, we retained the best result as the one maximizing the kappa index, because this index mixes both the OA and the AA issued from the confusion matrix (after label reassignment) and generally better represents the clustering quality. Figure 6-(c)-(f) displays the corresponding clustering maps with an effort to keep the same color scale than the ground truth. It is interesting to notice that all four methods can discover two additional clusters with respect to the available ground truth. These clusters are visually
<figure><img src="image_9.png" /><figcaption>**FIGURE 6.** Comparison of the best results in hyperspectral image pixel clustering with NN-density based methods and NN-MS methods. (a) Salinas-A hyperspectral image, color composite of spectral bands (R: band 30; G: band 20; B: band 10) (b) Ground truth map (white pixels are unlabeled); (c) kNNDPC (K = 240, C = 12, kappa = 0.666); (d) GWENN (K = 280, C = 9, kappa = 0.663); (e) NN-MedShift (K = 380, C = 8, kappa = 0.658); (f) NN-RMS (K = 200, C = 8, kappa = 0.701).</figcaption></figure>

coherent both from the spectral viewpoint as can be seen from the composite image, and from the spatial viewpoint since the additional segments in the maroon and light blue regions of the ground truth map follow the same spatial structure as the labeled ones. Despite the high dimensionality of the dataset, here again, NN-RMS provides the best overall clustering result among the four methods, still with the lowest number of nearest neighbors *K*.

## VII. CONCLUSION AND PERSPECTIVES

In this paper, we have proposed a novel Mean-Shift-like method to data clustering, called Robust Mean-Shift (RMS). This approach differs from the standard Mean-Shift (MS) and Blurring Mean-Shift (BMS) ones by its update equation. More precisely, RMS uses a linear combination of the current point iterates (similarly to BMS) with weights depending on the similarity (or distance) of these iterates to the original data points (similarly to MS). Surprisingly, the proposed method does not seem to have been studied so far despite its simplicity.

The RMS update equation has been set up in both a kernel-based and a nearest-neighbor-based version. In the kernel-based case, the convergence of point iterates has been conjectured based on the BMS convergence theorem of Chen [1].

RMS has several advantages over MS and BMS:

* For a same kernel bandwidth (in the kernel-based implementation) or number of NNs (in nearest-neighbor-based implementation), RMS shows larger basins of attraction than MS and BMS. One consequence is that the size of the NN graph required to achieve the same number of clusters is smaller for NN-RMS than for NN-MS and NN-BMS.

* Experimental results on synthetic and real datasets show that RMS in most cases outperforms MS and BMS in the clustering task.

* Though the RMS update equation is closer in spirit to BMS, their NN-based versions have different behaviors when the iterates get close to their fixed-point limit: whereas NN-BMS iterates continue to evolve until the mean squared error between the current and the previous iterates reach a specified small value, NN-RMS stops as soon as all iterates share the same set of NNs within the original dataset. This property is also valid for NN-MS (or NNGA).

Perspectives of this work are two-fold, and will concern (i) the optimization of RMS parametrization (kernel definition, kernel aperture, and number of NNs), and (ii) theoretical proofs of RMS convergence properties, especially with regard to convergence rate and larger attraction basins with respect to the standard MS and BMS clustering methods.

## REFERENCES

[1] T.-L. Chen, "On the convergence and consistency of the blurring mean-shift process," *Ann. Inst. Stat. Math.*, vol. 67, pp. 157-176, Oct. 2015.

[2] E. Min, X. Guo, Q. Liu, G. Zhang, J. Cui, and J. Long, "A survey of clustering with deep learning: From the perspective of network architecture," *IEEE Access*, vol. 6, pp. 39501-39514, 2018.

[3] S. C. H. Hoi, D. Sahoo, J. Lu, and P. Zhao, "Online learning: A comprehensive survey," *Neurocomputing*, vol. 459, pp. 249-289, Oct. 2021. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0925231221006706

[4] J. MacQueen, "Some methods for classification and analysis of multivariate observations," in *Proc. 5th Berkeley Symp. Math. Statist. Probab.*, vol. 1, Jan. 1967, pp. 281-297.

[5] J. Bezdek, *Pattern Recognition With Fuzzy Objective Function Algorithms*. New York, NY, USA: Plenum Press, 1981.

[6] B. Schölkopf, A. Smola, and K.-R. Müller, "Nonlinear component analysis as a kernel eigenvalue problem," *Neural Comput.*, vol. 10, no. 5, pp. 1299-1319, Jul. 1998.

[7] J. H. Ward, Jr., "Hierarchical grouping to optimize an objective function," *J. Amer. Statist. Assoc.*, vol. 58, no. 301, pp. 236-244, 1963.

[8] P. Sneath and R. Sokal, *Numerical Taxonomy. The Principles and Practice of Numerical Classification*. London, U.K.: Freeman, 1973.

[9] M. Ester, H.-P. Kriegel, J. Sander, and X. Xu, "A density-based algorithm for discovering clusters in large spatial databases with noise," in *Proc. 2nd Intern. Conf. Knowl. Discovery Data Mining*, 1996, pp. 226-231.

[10] M. Ankerst, M. M. Breunig, H.-P. Kriegel, and J. Sander, "Optics: Ordering points to identify the clustering structure," in *Proc. ACM SIGMOD Int. Conf. Manage. Data*, Philadelphia, PA, USA, 1999, pp. 49-60.

[11] K. Fukunaga and L. Hostetler, "The estimation of the gradient of a density function, with applications in pattern recognition," *IEEE Trans. Inf. Theory*, vol. IT-21, no. 1, pp. 32-40, Jan. 1975.

[12] Koontz, Narendra, and Fukunaga, "A graph-theoretic approach to non-parametric cluster analysis," *IEEE Trans. Comput.*, vol. C-25, no. 9, pp. 936-944, Sep. 1976.

[13] R. P. W. Duin, A. L. N. Fred, M. Loog, and E. Pekalska, "Mode seeking clustering by knn and mean shift evaluated," in *SSPR/SPR* (Lecture Notes in Computer Science), vol. 7626. Berlin, Germany: Springer, 2012, pp. 51-59.

[14] A. Rodriguez and A. Laio, "Clustering by fast search and find of density peaks," *Science*, vol. 344, no. 6191, pp. 1492-1496, 2014.

[15] A. P. Dempster, N. M. Laird, and D. B. Rubin, "Maximum likelihood from incomplete data via the EM algorithm," *J. Roy. Statist. Soc., B Methodol.*, vol. 39, no. 1, pp. 1-38, 1977.

[16] G. Celeux and G. Govaert, "A classification EM algorithm for clustering and two stochastic versions," *Comput. Statist. Data Anal.*, vol. 14, no. 3, pp. 315-332, 1992.

[17] C. E. Rasmussen, "The infinite Gaussian mixture model," in *Advances in Neural Information Processing Systems (NIPS)*, S. A. Solla, T. K. Leen, and K. R. Müller, Eds. Cambridge, MA, USA: MIT Press, 2000, pp. 554-560.
[18] B. J. Frey and D. Dueck, "Clustering by passing messages between data points," *Science*, vol. 315, no. 5814, pp. 972-976, Feb. 2007.

[19] M. Sugiyama, G. Niu, M. Yamada, M. Kimura, and H. Hachiya, "Information-maximization clustering based on squared-loss mutual information," *Neural Comput.*, vol. 26, no. 1, pp. 84-131, Jan. 2014.

[20] T. Hocking, J.-P. Vert, F. R. Bach, and A. Joulin, "ClusterPath: An algorithm for clustering using convex fusion penalties," in *Proc. Int. Conf. Mach. Learn.*, 2011, pp. 745-752.

[21] F. Chazal, L. J. Guibas, S. Y. Oudot, and P. Skraba, "Persistence-based clustering in Riemannian manifolds," *J. ACM*, vol. 60, no. 6, p. 38, 2013.

[22] F. Masulli and S. Rovetta, "Clustering high-dimensional data," in *Proc. 1st Intern. Workshop Clustering High-Dimensional Data*, vol. 7627. New York, NY, USA: Springer-Verlag, 2015, pp. 1-13.

[23] I. Goodfellow, Y. Bengio, and A. Courville, *Deep Learning*. Cambridge, MA, USA: MIT Press, 2016.

[24] C. Cariou, S. Le Moan, and K. Chehdi, "Improving K-nearest neighbor approaches for density-based pixel clustering in hyperspectral remote sensing images," *Remote Sens.*, vol. 12, no. 22, p. 3745, Nov. 2020.

[25] D. Comaniciu and P. Meer, "Mean shift: A robust approach toward feature space analysis," *IEEE Trans. Pattern Anal. Mach. Intell.*, vol. 24, no. 5, pp. 603-619, May 2002.

[26] M. A. Carreira-Perpiñán, "A review of mean-shift algorithms for clustering," *CoRR*, vol. abs/1503.00687, pp. 1-4, Oct. 2015.

[27] Y. Cheng, "Mean shift, mode seeking, and clustering," *IEEE Trans. Pattern Anal. Mach. Intell.*, vol. 17, no. 8, pp. 790-799, Aug. 1995.

[28] M. A. Carreira-Perpiñan, "Generalised blurring mean-shift algorithms for nonparametric clustering," in *Proc. IEEE Conf. Comput. Vis. Pattern Recognit.*, Jun. 2008, pp. 1-8.

[29] C. Grillenzoni, "Design of blurring mean-shift algorithms for data classification," *J. Classification*, vol. 33, no. 2, pp. 262-281, Jul. 2016.

[30] T. Duong, G. Beck, H. Azzag, and M. Lebbah, "Nearest neighbour estimators of density derivatives, with application to mean shift clustering," *Pattern Recognit. Lett.*, vol. 80, pp. 224-230, Sep. 2016.

[31] G. Beck, T. Duong, M. Lebbah, H. Azzag, and C. Cérin, "A distributed approximate nearest neighbors algorithm for efficient large scale mean shift clustering," *J. Parallel Distrib. Comput.*, vol. 134, pp. 128-139, Dec. 2019.

[32] X. Li, Z. Hu, and F. Wu, "A note on the convergence of the mean shift," *Pattern Recognit.*, vol. 40, no. 6, pp. 1756-1762, Jun. 2007.

[33] Y. Aliyari Ghassabeh, "A sufficient condition for the convergence of the mean shift algorithm with Gaussian kernel." *J. Multivariate Anal.*, vol. 135, pp. 1-10, Mar. 2015.

[34] K. Huang, X. Fu, and N. D. Sidiropoulos, "On convergence of epanechnikov mean shift," in *Proc. AAAI*, S. A. McIlraith and K. Q. Weinberger, Eds., 2018, pp. 3263-3270.

[35] M. A. Carreira-Perpiñán, "Fast nonparametric clustering with Gaussian blurring mean-shift," in *Proc. ICML*, W. W. Cohen and A. W. Moore, Eds., vol. 148, 2006, pp. 153-160.

[36] R. Bellman, *Adaptive Control Processes*. Princeton, NJ, USA: Princeton Univ. Press, 1961.

[37] M. A. Carreira-Perpiñan, "Gaussian mean-shift is an EM algorithm," *IEEE Trans. Pattern Anal. Mach. Intell.*, vol. 29, no. 5, pp. 767-776, May 2007.

[38] Y. A. Sheikh, E. A. Khan, and T. Kanade, "Mode-seeking by medoid-shifts," in *Proc. IEEE 11th Int. Conf. Comput. Vis.*, Oct. 2007, pp. 1-8.

[39] H. W. Kuhn, "The Hungarian method for the assignment problem," *Naval Res. Logist.*, vol. 2, nos. 1-2, pp. 83-97, Mar. 1995.

[40] C. D. Manning, P. Raghavan, and H. Schütze, *An Introduction to Information Retrieval*. Cambridge, U.K.: Cambridge Univ. Press, 2008.

[41] G. Ver Steeg, A. Galstyan, F. Sha, and S. DeDeo, "Demystifying information-theoretic clustering," in *Proc. Int. Conf. Mach. Learn.*, Beijing, China, 2014, pp. 1-8.

[42] Grupo de Inteligencia Computacional (UPV/EHU). (2021). *Hyperspectral Remote Sensing Scenes*. [Online]. Available: http://www.ehu.es/ccwintco/index.php/Hyperspectral Remote Sensing Scenes

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

**CLAUDE CARIOU** (Member, IEEE) received the Ph.D. degree in electronics from the University of Brest, France, in 1991. Since 1992, he has been with the Engineering School of Applied Sciences and Technology (ENSSAT), University of Rennes 1, where he is currently with the Image Department, Institut d'Électronique et des Technologies du numéRique - UMR CNRS 6164. His research interests include image analysis, pattern recognition, unsupervised classification, texture

modeling and segmentation, image registration and feature extraction/selection, mostly dedicated to multispectral and hyperspectral imagery.

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

**STEVEN LE MOAN** (Member, IEEE) received the Ph.D. degree in image processing from the University of Burgundy, France, in 2012. He then worked as a Postdoctoral Researcher at the Technical University of Darmstadt, Germany, and the Gjøvik University College, Norway. Until 2021, he was a Senior Lecturer in electronics, information and communication systems with Massey University, New Zealand. He is currently an Associate Professor

of color imaging at the Norwegian University of Science and Technology, Gjøvik, Norway. His research interests include multi/hyperspectral image analysis, color science, and visual perception.

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

**KACEM CHEHDI** (Member, IEEE) received the Ph.D. and "Habilitation à Diriger des Recherches" degrees in signal processing and telecommunications from the University of Rennes 1, France, in 1986 and 1992, respectively. From 1986 to 1992, he was an Assistant Professor at the University of Rennes 1. Since 1993, he has been a Professor of signal and image processing at the University of Rennes 1. From 1998 to 2003, he has been the Head of the LASTI Laboratory, and of the TSI2M

Laboratory (Signal and Multicomponent/Multimodal Image Processing), since 2004. His research activities concern adaptive processing at every level of the pattern recognition chain. In the framework of blind restoration and blind filtering, his main interests are the identification of the physical nature of image degradations and the development of adaptive algorithms. In the segmentation and registration topics, his research concerns the development of unsupervised, cooperative, and adaptive systems. The main applications under current investigation concern multispectral and hyperspectral image processing and analysis.

...