# CoHiRF: A Scalable and Interpretable Clustering Framework for High-Dimensional Data

Bruno Belucci, Karim Lounici, Katia Meziani

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

To cite this version:

Bruno Belucci, Karim Lounici, Katia Meziani. CoHiRF: A Scalable and Interpretable Clustering Framework for High-Dimensional Data. 2025. hal-05382168

HAL Id: hal-05382168

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

Preprint submitted on 25 Nov 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
# CoHiRF: A Scalable and Interpretable Clustering Framework for High-Dimensional Data

Bruno Belucci*, Karim Lounici† and Katia Meziani‡

01/02/2025

## Abstract

Clustering high-dimensional data poses significant challenges due to the curse of dimensionality, scalability issues, and the presence of noisy and irrelevant features. We propose Consensus Hierarchical Random Feature (CoHiRF), a novel clustering method designed to address these challenges effectively. CoHiRF leverages random feature selection to mitigate noise and dimensional-ity effects, repeatedly applies K-Means clustering in reduced feature spaces, and combines results through a unanimous consensus criterion. This iterative approach constructs a cluster assignment matrix, where each row records the cluster assignments of a sample across repetitions, enabling the identification of stable clusters by comparing identical rows. Clusters are organized hierarchically, enabling the interpretation of the hierarchy to gain insights into the dataset. CoHiRF is computationally efficient with a running time comparable to K-Means, scalable to massive datasets, and exhibits robust performance against state-of-the-art methods such as SC-SRGF, HDBSCAN, and OPTICS. Experimental results on synthetic and real-world datasets confirm the method's ability to reveal meaningful patterns while maintaining scalability, making it a powerful tool for high-dimensional data analysis.

## 1. Introduction

Clustering is a cornerstone of unsupervised learning that involves partitioning data into groups or clusters based on similarity. It is a vital tool in various domains, including computer vision (Chao et al., 2021), bioinformatics (Karim et al., 2020), and natural language processing (Li et al., 2021), where identifying patterns in data is essential. With the rise of modern applications, datasets have become increasingly high-dimensional, often containing a large num-

ber of samples (n) and features (p). This growth poses significant challenges in clustering high-dimensional data.

High-dimensional datasets suffer from the well-known "curse of dimensionality." As the dimensionality *p* increases, the relevant information often lies in a low-dimensional subspace, with the remaining dimensions contributing predominantly to noise. Consequently, data points tend to become equidistant in high-dimensional space, rendering traditional distance-based clustering algorithms, such as K-Means, less effective (Beyer et al., 1999). Specifically, the Euclidean distance metric loses its discriminative power, resulting in poor clustering performance. Another critical challenge is scalability: traditional clustering methods, originally designed for low-dimensional or small datasets, often struggle with high computational and memory demands when applied to high-dimensional data settings (Steinbach et al., 2004; Assent, 2012; Zimek et al., 2012; Mahdi et al., 2021).

## 2. Related Work

### 2.1. Evaluating Clustering Algorithms

Assessing the performance of clustering algorithms is inherently challenging due to the unsupervised nature of the task. Unlike classification problems, clustering generally lacks ground truth labels in real-world applications. As a result, evaluation relies on metrics that either estimate the quality of clusters based on their internal structure or compare clustering results against external references when available.

Metrics such as the Silhouette Score (Rousseeuw, 1987), Calinski-Harabasz Index (Caliński & Harabasz, 1974), and Davies-Bouldin Index (Davies & Bouldin, 1979) are commonly used to evaluate clustering without reference to external labels. The Silhouette Score defined as $\frac{a-b}{\max(a,b)}$, for example, measures how well-separated clusters are by comparing the average intra-cluster distance *a* to the nearest inter-cluster distance *b*. This metric ranges from -1 indicating incorrect clustering to 1 indicating dense, well-separated clusters, with scores near 0 suggesting overlapping or indistinct clusters.

In the absence of real-world labeled data, artificial clustering problems can be generated from classification datasets or

<footnote>* CEREMADE, Université Paris Dauphine-PSL, Paris, France</footnote>

<footnote>† CMAP, École Polytechnique, Palaiseau, France</footnote>

<footnote>‡ CEREMADE, Université Paris Dauphine-PSL, Paris, France</footnote>
simulated data. By controlling the underlying structure and labels of synthetic datasets, researchers can benchmark algorithms under varying conditions, such as noise levels, cluster overlap, or dimensionality. This allows for the use of external validation metrics, like the Rand Index (RI), which measures the agreement between pairs of samples, treating cluster assignments as equivalent regardless of permutation, and the Adjusted Rand Index (ARI) which adjusts the RI to account for chance. The ARI is bounded between -0.5 for discordant clustering to 1.0 for perfect agreement clustering, having a value close to 0 for random assignment of clusters (Hubert & Arabie, 1985).

## 2.2. Clustering Algorithms

Traditional clustering methods are divided into hierarchical and partitional strategies. Hierarchical clustering builds a hierarchy of clusters, which can be visualized through dendrograms. These methods are further divided into agglomerative (bottom-up) and divisive (top-down) approaches. Agglomerative algorithms begin with each instance as an individual cluster, merging them iteratively based on a measure of dissimilarity, called linkage, such as single-linkage, complete-linkage, and Ward-linkage (Day & Edelsbrunner, 1984). In contrast, divisive methods like DIANA (Kaufman & Rousseeuw, 1990) start with a single cluster containing all instances, splitting them iteratively.

Partitional clustering methods optimize a criterion function, often requiring the number of clusters as input. These methods include distance-based algorithms (e.g., K-Means (Hartigan & Wong, 1979), and Affinity Propagation (Frey & Dueck, 2007)), density-based algorithms (e.g., DBSCAN (Ester et al., 1996), and HDBSCAN (Campello et al., 2013)), and grid-based approaches like CLIQUE (Agrawal et al., 1998). For a comprehensive review on clustering algorithms and their taxonomy, the reader is refereed to (Jain et al., 1999; Xu & Wunsch, 2005; Saxena et al., 2017; Ezugwu et al., 2022).

## 2.3. High-Dimensional Clustering

Clustering high-dimensional data presents additional challenges, including the curse of dimensionality and the sparsity of meaningful distances. To address these issues, specialized techniques have been proposed:

**Subspace and Projected Clustering:** Algorithms like CLIQUE (Agrawal et al., 1998), and PROCLUS (Aggarwal et al., 1999) identifies clusters within specific subspaces of the feature space, while methods like DOC (Procopiuc et al., 2002) and K-Means Projective Clustering (Agarwal & Mustafa, 2004), further assign data points to unique clusters in lower-dimensional subspaces. Despite their utility, these methods often struggle with overlapping clusters and require careful parameter tuning.

**Ensemble Clustering:** Ensemble (or consensus) clustering aggregates multiple clustering solutions derived from various algorithms or projections to enhance robustness and accuracy (Strehl & Ghosh, 2003). By combining diverse partitions, ensemble methods mitigate the challenges posed by high-dimensional data and leverage complementary information.

**Projection-Based Methods:** Projection-based clustering approaches reduce the dimensionality of data while retaining meaningful cluster structures. Methods such as PCA (Pearson, 1901) and t-SNE (van der Maaten & Hinton, 2008) are frequently used for dimensionality reduction before clustering. Recent techniques include Latent Low-Rank Representation (LatLRR) (Liu et al., 2013), Robust LatLRR (RLLRR) (Zhang et al., 2014), and Iterative Reweighted Frobenius norm Regularized Latent Low-Rank (IRFLLRR) (Liu et al., 2023) which adaptively project data into subspaces optimized for clustering. While projection-based methods enhance interpretability and scalability, they may require careful parameter selection and are sometimes limited by the quality of the projection.

While some algorithms can be clearly labeled as applying one of those techniques, many clustering methods combine more than one technique to tackle the challenges of clustering high-dimensional data such as Spectral Clustering by Subspace Randomization and Graph Fusion (SC-SRGF) (Cai et al., 2020) or Hierarchical High-Dimensional Unsupervised Active Learning Method (HiDUALM) (Haghzad Klidbary & Javadian, 2024) which combines techniques from Subspace Clustering and Ensemble clustering.

## 3. Contribution

We propose a novel clustering method, named Consensus Hierarchical Random Feature Clustering (CoHiRF) which integrates principles from hierarchical clustering, projection-based clustering, and ensemble clustering. Our method is designed to address the limitations of existing techniques in high-dimensional settings, with a focus on scalability, robustness to noise, and interpretability.

The key steps of our method are as follows:

1. **Feature sub-sampling:** Randomly sample subsets of features and apply any clustering method<fnref n="1" /> to the resulting low-dimensional representations.

2. **Cluster Assignment Matrix:** Repeat this process multiple times to construct a clustering matrix recording the cluster to which each sample has been assigned

<footnote n="1">¹In our experiments, we focus on *K*-means as it is really fast and not memory intensive. Applying *K*-means to all the randomly sampled subsets proved to be among the best methods in our benchmark.</footnote>
across all the repetitions.

3. **Unanimous Consensus:** Identify clusters by grouping samples consistently clustered together across all repetitions. Select a medoid for each of these clusters.

4. **Iterative Agglomeration:** Repeat the previous steps on the set of medoids of the previously created clusters to merge them iteratively until no further merging is possible.

This approach addresses the challenges of high-dimensional clustering as follows:

* **Curse of Dimensionality:** By leveraging random feature selection and repeated consensus, our method significantly mitigates the effects of high dimensionality while preserving meaningful information.

* **Scalability:** The random sampling and iterative design enable efficient processing of high-dimensional and massive datasets as we essentially perform a low-dimensional K-Means at each repetition.

* **Interpretability:** Our novel hierarchical unanimous consensus approach systematically organizes data into nested clusters, enabling an in-depth exploration of multi-level clustering structures and uncovering relationships across different levels of granularity.

* **Efficient Consensus Scheme.** Our approach differs from traditional ensemble clustering, which typically involves solving a challenging optimization problem to derive a consensus from multiple distinct clustering results. In contrast, our hierarchical method eliminates the need for a post-clustering optimization step. Instead, it aggregates the nodes of the constructed (incomplete) hierarchical clustering tree, a computationally inexpensive operation.

Our numerical experiments demonstrate that our method efficiently scales to extremely high-dimensional settings where SOTA techniques such as HDBSCAN (Campello et al., 2013), OPTICS (Ankerst et al., 1999), and SC-SRGF (Cai et al., 2020) fail to compute.

# 4. CoHiRF Algorithm

## 4.1. Detailed Method

Below, we provide a detailed description of our method's implementation and its hyperparameters. A pseudocode implementation can be found in Algorithm 1 and a visual representation of the iterative step of our method is described in Figure 1.

**Input.** Consider the data set $\mathcal{D}_n = \{\mathbf{x}_1, \dots, \mathbf{x}_n\}$. We introduce the data matrix

**Algorithm 1 CoHiRF Algorithm**

**Input:** Data $\mathcal{X}$, number of sampled features $q$, number of repetitions $R$, number of clusters $C$

**Output:** Final partition of samples $\{C_c^*\}_c$

**Initialize:** $X \leftarrow \mathcal{X}$, $n_{\text{prev}} \leftarrow 0$, $n_{\text{curr}} \leftarrow n$

**while** $n_{\text{curr}} \neq n_{\text{prev}}$ **do**

P $\leftarrow \emptyset$ {Matrix to store K-Means labels across repetitions}

**for** $r = 1$ **to** $R$ **do**

Randomly sample $q$ features from $X$

Perform K-Means on the sampled features, obtaining labels $p_r \in \{1, \dots, C\}^{n_{\text{curr}}}$

Append labels $p_r$ to P

**end for**

Assign a unique code to each row of P

Update $n_{\text{prev}} \leftarrow n_{\text{curr}}$

Update $n_{\text{curr}} \leftarrow$ number of unique codes in P

Assign codes to each sample in $X$ and their parent samples to form partition $C_j$

**Medoid Computation:**

**for** $k = 1$ **to** $n_{\text{curr}}$ **do**

Compute the medoid $\mathbf{x}_k$ of the $k$-th cluster:

Append the medoid to $X$

Assign all other samples in the cluster as children of the medoid

**end for**

**end while**

**Return:** $\{C_c^*\}_c$ {Final clusters after stabilization}

$$ \mathcal{X} = \begin{bmatrix} \mathbf{x}_1^\top \\ \vdots \\ \mathbf{x}_n^\top \end{bmatrix} \in \mathbb{R}^{n \times p}. $$

**Hyperparameters.** We denote by $[[n_1, n_2]] = \{n_1, n_1 + 1, \dots, n_2\}$ the set of all integers. Our methods depends on the following hyperparameters:

* The number of randomly sampled features: $q \in [[2, \bar{q}]]$ with $\bar{q} = \min(30, p-1)$

* Number of repetitions: $R \in [[2, 10]]$

* Number of clusters used in the internal clustering step: $C \in [[2, 10]]$. While we use K-Means by default, any other clustering algorithm could be employed.

[Initialization (Step $e=0$)] We start from the whole data set and initialize

$$ \left\{ \begin{array}{l} n^{(0)} = n \\ \mathbf{x}_i^{(0)} = \mathbf{x}_i, \quad \forall i \in [[1, n^{(0)}]] \\ e = 1 \end{array} \right. $$
[Step e] (Figure 1) From Step (e-1), we recover a data set

$$ \mathcal{D}_{n^{(e-1)}} = \{ \mathbf{x}_i, i \in [1, n^{(e-1)}] \} $$

(i.) We build the sample matrix from the data set $\mathcal{D}_{n^{(e-1)}}$

$$ \mathcal{X}^{(e)} = \begin{bmatrix} (\mathbf{x}_1^{(e-1)})^{\top} \\ \vdots \\ (\mathbf{x}_{n^{(e-1)}}^{(e-1)})^{\top} \end{bmatrix} \in \mathbb{R}^{n^{(e-1)} \times p}. $$

(ii.) We first construct R random submatrices by repeatedly sampling a subset of q features and extracting the corresponding submatrix from $\mathcal{X}^{(e)}$:

$$ \mathcal{X}_{q,1}^{(e)} = \begin{bmatrix} (\mathbf{x}_1^{(e-1)})^{\top} \\ \vdots \\ (\mathbf{x}_{n^{(e-1)}}^{(e-1)})^{\top} \end{bmatrix} \in \mathbb{R}^{n^{(e-1)} \times q} $$

This process is repeated R times, yielding the random data matrices $\mathcal{X}_{q,1}^{(e)}, \dots, \mathcal{X}_{q,R}^{(e)} \in \mathbb{R}^{n^{(e-1)} \times q}$.

(iii.) For each $r \in [1, R]$, we apply the standard K-Means algorithm to $\mathcal{X}_{q,r}^{(e)}$ with C clusters. The results of the clustering procedure across all R repetitions are collected in the matrix

$$ \mathbf{P}^{(e)} = [\mathbf{P}_{i,r}^{(e)}]_{i,r} \in \{1, \dots, C\}^{n^{(e-1)} \times R}, $$

where $p_{i,r}^{(e)}$ represents the cluster assigned to the i-th observation during the r-th repetition. Since the cluster labels are not inherently identifiable, we adopt the following convention: cluster $c = 1$ is assigned to the cluster containing the first sample $\mathbf{x}_1^{(0)}$. The cluster $c = 2$ corresponds to the next sample $\mathbf{x}_i^{(0)}$ with the smallest index $i$ that is not clustered together with $\mathbf{x}_1^{(0)}$ during the first repetition ($r = 1$), and so on for the following clusters $c \in [2, C]$.

(iv.) We denote by $n^{(e)}$ the number of distinct rows in $\mathbf{P}^{(e)}$. We partition the samples $\mathcal{D}_{n^{(e-1)}}$ of size $n^{(e-1)}$ into $n^{(e)}$ disjoint sets, denoted $C_k^{(e)}$, $k \in [1, n^{(e)}]$, which consist of observations sharing identical row vectors $p_{i,\cdot}^{(e)} \in \{1, \dots, C\}^R$. Concretely, we group together all the samples $\mathbf{x}_i^{(e-1)}$ that have been clustered together throughout all the R repetitions. Note that:

$$ n^{(e)} \leq \min \left( n^{(e-1)}, C^R \right), \quad \text{and} $$

$$ \sum_{k=1}^{n^{(e)}} |C_k^{(e)}| = n^{(e-1)}. $$

(v.) For each $[1, n^{(e)}]$, we select the **medoid** denoted $\mathbf{x}_k^{(e)} \in \mathbb{R}^p$, for each cluster $C_k^{(e)}$. Let

$$ \mathbf{x}_k^{(e)} = \arg \min_{\mathbf{x}_i^{(e-1)} \in C_k^{(e)}} \left\{ \sum_{\mathbf{x}_j^{(e-1)} \in C_k^{(e)}} \left| \langle \mathbf{x}_i^{(e-1)}, \mathbf{x}_j^{(e-1)} \rangle \right| \right\}. $$

This expression selects the sample $\mathbf{x}_i^{(e-1)}$ within the cluster $C_k^{(e)}$ that minimizes the sum of the absolute inner products with all other points in the same cluster, which defines the medoid of $C_k^{(e)}$.

[Repeat until] $n^{(e^*)} = n^{(e^*-1)}$

[Final step $e^*$] At the final step $e^*$, we collect the sets $C_k^{(e^*)}$ for $k = [1, n^{(e^*)}]$ corresponding to a cluster at step $e^*$. The final number of clusters is given by $C^* = n^{(e^*)}$. We then reconstruct the final $C^*$ clusters by tracing the evolution of the sets through all the previous steps. Specifically, for each final cluster $c \in [1, C^*]$, we have:

$$ C_c^* = \bigcup_{k_{e^*} \in C_c^{(e^*)}} \left( \bigcup_{k_{e^*-1} \in C_{k_{e^*}}^{(e^*-1)}} \left( \cdots \left( \bigcup_{k_1 \in C_{k_2}^{(1)}} C_{k_1}^{(1)} \right) \right) \right). $$

This means that each final cluster $C_c^*$ is formed by the union of clusters across all steps $e = 1, 2, \dots, e^*$. This process allows us to reconstruct the final clusters by following the evolution of each observation across all steps of the algorithm. Each final cluster $C_c^*$ contains all the observations that were grouped together throughout the iterations, with each observation $\mathbf{x}_i$ being assigned to the final cluster $c$ in which it converged after the algorithm completed.

This novel clustering procedure is best described as an agglomerative hierarchical iterative consensus-based method, where at each step, the algorithm merges clusters based on their consensus across multiple random repetitions

The process converges when no further grouping is possible, meaning each "surviving" sample becomes its own unique representative. However, at the final step, the method reconstructs the final clusters by tracing the evolution of each observation through all previous steps. This merging process reveals a hierarchical structure, where clusters formed at earlier stages are fused to form the final clusters. See Figure 2 for a concept illustration.

This flexibility allows the algorithm to adapt to varying data structures, making it particularly useful for exploratory analysis. Furthermore, the hierarchical nature of the procedure
<figure><img src="image_3.png" /><figcaption>**Figure 1.** Illustration of one iteration of the CoHiRF algorithm with $q = 2$, $C = 2$ and $R = 4$. At the beginning of step *e*, we start with $n^{(e-1)}$ samples (the medoids inherited from the previous iteration). For each repetition $r \in [R]$, subsample *q* features at random and cluster the $n^{(e-1)}$ samples using K-Means with $C = 2$, then identify clusters by grouping together the samples consistently clustered together across all repetitions. Obtain that way $n^{(e)}$ newly formed clusters and finally choose a medoid for each of the formed clusters.</figcaption></figure>

facilitates interpretability, providing insights into how the clusters evolved over iterations and allowing for an intuitive understanding of the relationships between data points across different levels of granularity. See Appendix B for an experience illustrating this aspect on the *iris* dataset.

CoHiRF does not require knowledge of the true number of clusters $C^*$. Our method stops when no further grouping can be made, meaning that the number of clusters $C^*$ is effectively identified during the process itself, removing the necessity of defining it in advance. Notably, there is no direct correspondence between parameter *C* in our method and $C^*$; we may use different values of *C*, either smaller or larger than $C^*$, in each iteration. When the clustering problem has a sufficiently high signal-to-noise ratio, CoHiRF accurately recovers the true number of clusters $C^*$.

## 4.2. Complexity Analysis

Our algorithm's running time is dominated by the number of times we run K-Means and the calculation of similarities to determine the closest sample to every other sample in the cluster. We use Lloyd's algorithm for K-Means to cluster *n* samples of dimension *p* into *C* clusters with a maximum of *I* iterations. This has a running time on the order of $O(npCI)$ (Hartigan & Wong, 1979). Since we repeat K-Means *R* times, the total running time for this step is $O(npCI R)$. As for calculating the similarities, we assume that after *R* repetitions of K-Means, the consensus step of CoHiRF has found *K* clusters, with the samples uniformly distributed across them. Therefore, for each cluster, the number of points will be approximately $n/K$. To calculate the *K* medoids, we have a theoretical running time of order $O((n/K)^2 pK) = O(n^2 p)$. Thus, the cost of the first iteration of our algorithm is $O(npCI R) + O(n^2 p)$.

<figure><img src="image_4.png" /><figcaption>**Figure 2.** Concept representation for the hierarchical clustering structure built by CoHiRF. The hierarchy is built iteratively by our method without requiring solving any additional expensive optimization problem. The final step of CoHiRF is thus immediate.</figcaption></figure>

Note that this is the theoretical running time of only one iteration, which starts with *n* samples. The number of samples for the following iterations reduces drastically after the first iteration. Typically, in our experience, we observed that after just one iteration, the number of (medoid) samples $n^{(1)} = K$ is on the order of tens, and at most a few hundred, which greatly speeds up our algorithm. This reduction allows us to compute the exact medoids more efficiently in the following iterations, resulting in a much faster overall computation time. If one does not want to use exact medoids to further reduce the theoretical time complexity, it is entirely possible to replace exact medoids with approximate medoids or centroids, which does not significantly affect the statistical performance, as demonstrated in the experiments in Section 5.

As for the space complexity, it is dominated by the storage of the data, $O(np)$, and the storage of the similarity matrix, $O((n/K)^2)$ during the first step.

## 5. Experiments

Every experiment was performed in a machine with an Intel(R) Xeon(R) CPU E5-2630 v4 and a maximum of 126 Gb of memory. Our code for running experiments can be found
in Appendix D.

**Compared methods.** We compared the performance of the following models: CoHiRF (ours), K-Means (Hartigan & Wong, 1979), Affinity Propagation (Frey & Dueck, 2007), CLIQUE (Agrawal et al., 1998), Spectral Clustering (Shi & Malik, 2000), Mean Shift (Comaniciu & Meer, 2002), IRFLLRR (Liu et al., 2023), K-Means Projective Clustering (K-Means Proj.) (Agarwal & Mustafa, 2004), Density-Based Spatial Clustering of Applications with Noise (DBSCAN) (Ester et al., 1996), Hierarchical Density-Based Spatial Clustering of Applications with Noise (HDBSCAN) (Campello et al., 2013), PROCLUS (Aggarwal et al., 1999), SC-SRGF (Cai et al., 2020), and four types of Agglomerative Clustering models with different linkage methods: Single Linkage, Complete Linkage, Average Linkage, and Ward's Method (Day & Edelsbrunner, 1984). Those methods were selected based on their performance and popularity in the literature, and the availability of their source code. All the algorithms were implemented in Python. Specifically, we translated IRFLLRR, SC-SRGF, and K-Means Proj. from Matlab to Python and updated the syntax of PROCLUS from Python 2 to Python 3. Note that the tables and figures presented below include only the models that demonstrated competitive performance in our experiments.

**Hyperparameters optimization.** We evaluated each algorithm using its optimized hyperparameters to achieve the best possible performance. By default, we used 100 trials of the Tree-structured Parzen Estimator (TPE) for hyperparameter optimization (Watanabe, 2023), unless a different optimization method was explicitly recommended in the original paper or in the algorithm's official package implementation. The hyperparameter search spaces for each algorithm are detailed in Appendix A. The objective of the hyperparameter optimization routine was to maximize the Adjusted Rand Index (Hubert & Arabie, 1985) for the real-world datasets.

## 5.1. Scalability

We evaluated the scalability of the tested models with respect to both the number of features and the number of samples. To this end, we generated datasets with the number of samples (n) and number of features (p) varying in a logarithmic grid of six values: [100, 347, 1202, 4163, 14427, 50000]. The cluster centers are drawn uniformly at random from the set of vertices of a p-dimensional hypercube, with edge length $\Delta = 100$ (i.e., the inter-cluster distance), creating $C^* = 5$ clusters. Samples within each cluster are randomly drawn from a Normal distribution with an identity covariance matrix (thus controlling the intra-cluster distance), centered at the corresponding cluster center.

Additionally we have included two variants of CoHiRF, denoted CoHiRF-1000 and CoHiRF-Sampled. The first

<figure><img src="image_5.png" /><figcaption>**Figure 3.** Running time of the tested algorithms for 14427 samples. Because of memory constraints HDBSCAN could not run with more than 4163 features.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>**Figure 4.** Running time of the tested algorithms for 14427 features. Because of memory constraints and/or time constraints HDBSCAN could not run with more than 4163 features and OPTICS, Affinity Propagation and SC-SRGF with more than 14427 features.</figcaption></figure>
variant replaces the exact calculation of the medoid in Section 4.1 step *e* (v.) by an approximated version which sub-samples the population of each cluster by a maximum of 1000 examples. This variant mitigates the quadratic running time presented in Section 4.2. The second variation samples a subset of 1024 samples in Section 4.1 after step *e* (i.), and proceeds as usual with the rest of the algorithm by considering the unsampled samples as medoids in step *e* (v.). This technique allows us to scale to high-dimensional data settings, where the number of samples is high, decreasing the running time of CoHiRF and enabling out-of-core computation by loading partial data dynamically.

It is important to note that every model we tested in this configuration could perfectly partition the generated data, obtaining a perfect ARI of 1.0. Therefore, we are not interested in the ARI performance, but rather in determining the scalability limits of each model.

The results can be found in Figure 3 and Figure 4. We observe that CoHiRF is significantly faster than the other algorithms, in general being 10x faster for smaller numbers of samples *n* and features *p*, and up to 1000x faster for larger *n*, *p*, having a runtime comparable to *K*-Means with optimized hyperparameters. Besides, CoHiRF can run for every configuration of generated datasets, including the ones with large *p* and *n*, which is not the case for other algorithms like HDBSCAN, SC-SRGF, and Affinity Propagation.

While CoHiRF is designed to be scalable, it has a quadratic dependence on the number of samples when computing the exact medoid Section 4.2. However, this limitation can be addressed through subsampling strategies that approximate the medoid without a full pairwise comparison, as shown in Section 5.3.

## 5.2. Experiment on Synthetic Data

<figure><img src="image_7.png" /><figcaption>**Figure 5.** Running time and ARI for tested algorithm for different inter-cluster distances in an experiment with 1000 samples and 10000 features.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>**Figure 6.** Running time and ARI for tested algorithm for different inter-cluster distances in an experiment with 10⁵ samples and 10⁴ features.</figcaption></figure>

To access the limit of each model in clustering data with small inter-cluster distances, we generated datasets with 1000 samples (n) and 10000 features (p) where 5 centers were chosen randomly in a p-dimensional space separated by distances varying between 70 and 200. Then we equally sampled from 5 multivariate Normal distribution with mean equal to the center value and identity covariance matrix. The result can be seen in Figure 5, where we observe that CoHiRF performs well for distances up to 100, but with time comparable to K-Means and DBSCAN. Note, however, that under these settings a simpler algorithm as K-Means seems to be better suited.

This is not anymore the case if we change the settings of the experiment to consider higher dimensional data. We present in Figure 6 the results of an experiment using the hypercube setting presented in Section 5.1 with 10⁵ samples and 10⁴ features. Note that under these conditions, only CoHiRF and K-Means can run under a reasonable amount of time with our memory constraints. CoHiRF outperforms K-Means, with the sampled variant of CoHiRF being capable to run in similar time as K-Means.

## 5.3. Experiment on Real Data

We have also tested the clustering algorithms on real-world datasets. For a fair comparison, we have used classification datasets with known labels. All datasets are available on the OpenML platform (Feurer et al., 2020), and a summary of their characteristics is provided in Table 1, including the number of samples *n*, total features *p*, categorical features *pcat*, and the number of classes which corresponds to the number of clusters *C*\*. All selected datasets have been recently considered benchmarks for classification tasks (McElfresh et al., 2023), and we have tried to include datasets which we judged can be well adapted from a classification to a clustering task, notably the dataset *Iris*, which is
widely known in the domain, the dataset Nursery which is derived from a hierarchical decision model and, the dataset Ecoli which comes from the biology domain and present protein location sites. The other datasets were selected because of their relatively large number of samples and/or number of features. All datasets were preprocessed in the same manner before being given as input to the algorithms: we have one-hot encoded categorical features and we have standardize continuous features.

<table><caption>Table 1. Characteristics of the real-world datasets.</caption><thead><tr><th>DATASET</th><th>OPENML ID</th><th>n</th><th>p</th><th>p<sub>cat</sub></th><th>C*</th></tr></thead><tbody><tr><td>ECOLI</td><td>39</td><td>336</td><td>8</td><td>1</td><td>8</td></tr><tr><td>IRIS</td><td>61</td><td>150</td><td>5</td><td>1</td><td>3</td></tr><tr><td>SATIMAGE</td><td>182</td><td>6430</td><td>37</td><td>1</td><td>6</td></tr><tr><td>HAR</td><td>1478</td><td>10299</td><td>562</td><td>1</td><td>6</td></tr><tr><td>NURSERY</td><td>1568</td><td>12958</td><td>9</td><td>9</td><td>4</td></tr><tr><td>SHUTTLE</td><td>40685</td><td>58000</td><td>10</td><td>1</td><td>7</td></tr><tr><td>SEGMENT</td><td>40984</td><td>2310</td><td>20</td><td>1</td><td>7</td></tr><tr><td>ALIZADEH-2000-v2</td><td>46773</td><td>62</td><td>2094</td><td>0</td><td>3</td></tr><tr><td>GARBER-2001</td><td>46779</td><td>66</td><td>4554</td><td>0</td><td>4</td></tr><tr><td>COIL-20</td><td>46783</td><td>1440</td><td>1025</td><td>0</td><td>0</td></tr></tbody></table>

To showcase the flexibility and potential of CoHiRF, we introduce another variant of our model, CoHiRF-RBF which modifies the medoid selection criterion in Section 4.1, step e (v.), instead of using cosine distance, CoHiRF-RBF selects the medoid that maximizes similarity with all other samples based on a radial basis function (RBF) kernel. Finally for comparison with our base model, we have added the model CoHiRF-Full which does not perform sampling of the features

We report the performance results of a subset of the algorithms tested on real datasets in Table 2 and we have included all the algorithms and their parameters in Appendix E. Our results show that CoHiRF is highly competitive compared to other methods, achieving the highest ARI on four datasets (Garbner-2001, Nursery, Segment, and Shuttle) and ranking second on three (Alizadeh-2000-v2, Ecoli, and Satimage). Additionally, CoHiRF consistently outperforms K-Means, the base clustering algorithm used within our approach, except for the dataset Coil-20 While SC-SRGF also demonstrated strong performance on real-world data, it faced computational limitations. In contrast, CoHiRF proved to be a practical and efficient alternative, capable of running on a modest setup while being up to 100x faster.

Furthermore, CoHiRF is a powerful tool for interpretation. Since CoHiRF is fast, multiple dendrograms can be displayed for various runs with different hyperparameter configurations, providing domain experts with a convenient tool to apply their expertise and identify the most relevant dendrogram. See Figure 7 in Appendix for an example of a dendrogram constructed by CoHiRF on the Iris dataset.

Finally, another advantage of our CoHiRF its computational

efficiency, which enables systematic hyperparameter optimization. Our experiments, as illustrated in Appendix C, show that only a subset of the tested configurations yield strong performance, reinforcing the importance of automated hyperparameter tuning. As a best practice, we recommend optimizing *q*, *R*, and *C* to achieve the best clustering results.

<table><caption>Table 2. RESULTS ON REAL-WORLD DATASETS.</caption><thead><tr><th>DATASET</th><th>MODEL</th><th>ARI</th><th>TIME (S)</th></tr></thead><tbody><tr><td rowspan="7">ALIZADEH-2000-v2</td><td>CoHiRF</td><td>0.831</td><td>0.016</td></tr><tr><td>COMPLETE AGGLOMERATIVE</td><td>0.539</td><td>0.009</td></tr><tr><td>DBSCAN</td><td>0.250</td><td>0.009</td></tr><tr><td>HDBSCAN</td><td>0.166</td><td>0.025</td></tr><tr><td>K-MEANS</td><td>0.815</td><td>0.011</td></tr><tr><td>PROCLUS</td><td>0.446</td><td>0.033</td></tr><tr><td>SC-SRGF</td><td>0.599</td><td>0.142</td></tr><tr><td rowspan="7">COIL-20</td><td>WARD'S METHOD</td><td>0.947</td><td>0.011</td></tr><tr><td>CoHiRF</td><td>0.464</td><td>0.514</td></tr><tr><td>COMPLETE AGGLOMERATIVE</td><td>0.178</td><td>0.355</td></tr><tr><td>DBSCAN</td><td>0.491</td><td>0.055</td></tr><tr><td>HDBSCAN</td><td>0.677</td><td>2.173</td></tr><tr><td>K-MEANS</td><td>0.655</td><td>0.073</td></tr><tr><td>PROCLUS</td><td>0.167</td><td>3.332</td></tr><tr><td rowspan="7">ECOLI</td><td>SC-SRGF</td><td>0.776</td><td>22.408</td></tr><tr><td>WARD'S METHOD</td><td>0.719</td><td>0.354</td></tr><tr><td>CoHiRF</td><td>0.758</td><td>0.273</td></tr><tr><td>CoHiRF-1000</td><td>0.751</td><td>0.297</td></tr><tr><td>CoHiRF-FULL</td><td>0.734</td><td>0.233</td></tr><tr><td>CoHiRF-RBF</td><td>0.742</td><td>0.165</td></tr><tr><td>COMPLETE AGGLOMERATIVE</td><td>0.785</td><td>0.006</td></tr><tr><td>DBSCAN</td><td>0.345</td><td>0.018</td></tr><tr><td>HDBSCAN</td><td>0.398</td><td>0.020</td></tr><tr><td>K-MEANS</td><td>0.719</td><td>0.005</td></tr><tr><td>PROCLUS</td><td>0.643</td><td>0.129</td></tr><tr><td>SC-SRGF</td><td>0.723</td><td>1.782</td></tr><tr><td>WARD'S METHOD</td><td>0.735</td><td>0.006</td></tr><tr><td rowspan="7">GARBER-2001</td><td>CoHiRF</td><td>0.298</td><td>0.128</td></tr><tr><td>COMPLETE AGGLOMERATIVE</td><td>0.283</td><td>0.019</td></tr><tr><td>DBSCAN</td><td>0.043</td><td>0.020</td></tr><tr><td>HDBSCAN</td><td>0.026</td><td>0.050</td></tr><tr><td>K-MEANS</td><td>0.188</td><td>0.022</td></tr><tr><td>PROCLUS</td><td>0.046</td><td>0.152</td></tr><tr><td>SC-SRGF</td><td>0.175</td><td>0.162</td></tr><tr><td rowspan="7">HAR</td><td>WARD'S METHOD</td><td>0.200</td><td>0.021</td></tr><tr><td>CoHiRF</td><td>0.491</td><td>1.410</td></tr><tr><td>CoHiRF-1000</td><td>0.341</td><td>0.449</td></tr><tr><td>CoHiRF-FULL</td><td>0.426</td><td>7.964</td></tr><tr><td>CoHiRF-RBF</td><td>0.495</td><td>0.932</td></tr><tr><td>COMPLETE AGGLOMERATIVE</td><td>0.332</td><td>24.954</td></tr><tr><td>DBSCAN</td><td>0.302</td><td>1.372</td></tr><tr><td>HDBSCAN</td><td>0.287</td><td>54.107</td></tr><tr><td>K-MEANS</td><td>0.438</td><td>0.433</td></tr><tr><td>PROCLUS</td><td>0.322</td><td>61.353</td></tr><tr><td>SC-SRGF</td><td>0.546</td><td>3521.249</td></tr><tr><td>WARD'S METHOD</td><td>0.511</td><td>20.600</td></tr><tr><td rowspan="7">IRIS</td><td>CoHiRF</td><td>0.631</td><td>0.146</td></tr><tr><td>CoHiRF-1000</td><td>0.733</td><td>0.163</td></tr><tr><td>CoHiRF-FULL</td><td>0.639</td><td>0.127</td></tr><tr><td>CoHiRF-RBF</td><td>0.729</td><td>0.087</td></tr><tr><td>COMPLETE AGGLOMERATIVE</td><td>0.573</td><td>0.004</td></tr><tr><td>DBSCAN</td><td>0.558</td><td>0.017</td></tr><tr><td>HDBSCAN</td><td>0.564</td><td>0.018</td></tr><tr><td>K-MEANS</td><td>0.592</td><td>0.005</td></tr><tr><td>PROCLUS</td><td>0.752</td><td>0.026</td></tr><tr><td>SC-SRGF</td><td>0.865</td><td>1.735</td></tr><tr><td>WARD'S METHOD</td><td>0.615</td><td>0.002</td></tr><tr><td rowspan="7">NURSERY</td><td>CoHiRF</td><td>0.440</td><td>0.327</td></tr><tr><td>CoHiRF-1000</td><td>0.171</td><td>0.436</td></tr><tr><td>CoHiRF-FULL</td><td>0.455</td><td>1.065</td></tr><tr><td>CoHiRF-RBF</td><td>0.510</td><td>1.439</td></tr><tr><td>COMPLETE AGGLOMERATIVE</td><td>0.040</td><td>5.067</td></tr><tr><td>DBSCAN</td><td>0.000</td><td>2.192</td></tr><tr><td>HDBSCAN</td><td>0.014</td><td>2.583</td></tr><tr><td>K-MEANS</td><td>0.150</td><td>0.018</td></tr><tr><td>WARD'S METHOD</td><td>0.254</td><td>5.598</td></tr></tbody><tfoot><tr><td colspan="4">CONTINUED ON NEXT PAGE...</td></tr></tfoot></table>
<table><thead><tr><th>DATASET</th><th>MODEL</th><th>ARI</th><th>TIME (S)</th></tr></thead><tbody><tr><td rowspan="10">SATIMAGE</td><td>CoHiRF</td><td><strong>0.583</strong></td><td>2.006</td></tr><tr><td>CoHiRF-1000</td><td>0.581</td><td>1.902</td></tr><tr><td>CoHiRF-FULL</td><td>0.518</td><td>0.523</td></tr><tr><td>CoHiRF-RBF</td><td><strong>0.583</strong></td><td>2.123</td></tr><tr><td>COMPLETE AGGLOMERATIVE</td><td>0.321</td><td>1.767</td></tr><tr><td>DBSCAN</td><td>0.297</td><td>0.110</td></tr><tr><td>HDSCAN</td><td>0.308</td><td>1.325</td></tr><tr><td>K-MEANS</td><td>0.566</td><td>0.027</td></tr><tr><td>PROCLUS</td><td>0.475</td><td>10.735</td></tr><tr><td>SC-SRGF</td><td><strong>0.618</strong></td><td>1347.919</td></tr><tr><td>WARD'S METHOD</td><td>0.485</td><td>1.902</td></tr><tr><td rowspan="10">SEGMENT</td><td>CoHiRF</td><td><strong>0.540</strong></td><td>0.220</td></tr><tr><td>CoHiRF-1000</td><td><strong>0.532</strong></td><td>1.422</td></tr><tr><td>CoHiRF-FULL</td><td>0.511</td><td>0.492</td></tr><tr><td>CoHiRF-RBF</td><td>0.518</td><td>1.008</td></tr><tr><td>COMPLETE AGGLOMERATIVE</td><td>0.280</td><td>0.161</td></tr><tr><td>DBSCAN</td><td>0.251</td><td>0.025</td></tr><tr><td>HDSCAN</td><td>0.390</td><td>0.157</td></tr><tr><td>K-MEANS</td><td>0.512</td><td>0.019</td></tr><tr><td>PROCLUS</td><td>0.509</td><td>2.267</td></tr><tr><td>SC-SRGF</td><td>0.481</td><td>194.087</td></tr><tr><td>WARD'S METHOD</td><td>0.446</td><td>0.159</td></tr><tr><td rowspan="10">SHUTTLE</td><td>CoHiRF</td><td>0.652</td><td>4.327</td></tr><tr><td>CoHiRF-1000</td><td><strong>0.771</strong></td><td>3.085</td></tr><tr><td>CoHiRF-FULL</td><td>0.601</td><td>10.839</td></tr><tr><td>CoHiRF-RBF</td><td>0.685</td><td>3.923</td></tr><tr><td>COMPLETE AGGLOMERATIVE</td><td>0.006</td><td>239.934</td></tr><tr><td>DBSCAN</td><td><strong>0.686</strong></td><td>22.333</td></tr><tr><td>HDSCAN</td><td>0.001</td><td>39.957</td></tr><tr><td>K-MEANS</td><td>0.608</td><td>0.038</td></tr><tr><td>PROCLUS</td><td>0.443</td><td>64.062</td></tr><tr><td>WARD'S METHOD</td><td>0.478</td><td>149.456</td></tr></tbody></table>

## 6. Conclusion

The proposed method, CoHiRF, leverages random feature projections, repeated K-Means clustering, and a unanimous consensus criterion to efficiently address the challenges of clustering high-dimensional data. By systematically reducing dimensionality and a novel consensus cluster assignment scheme, CoHiRF achieves robust and scalable clustering performance. Notably, CoHiRF does not require prior knowledge of the number of clusters $C^*$, as the hierarchical consensus naturally determines the cluster structure. Additionally, its iterative nature is a key advantage for interpretability, providing insights into complex data by organizing it in multi-level clustering structures.

The second key advantage of CoHiRF is its scalability, and our experiments with approximated medoids suggest that the trade-off between accuracy and computational efficiency can be adjusted dynamically, making CoHiRF adaptable to different computational constraints. By combining CoHiRF with a sampling technique in a mini-batch fashion, we effectively tackle the high-dimensionality problem in both the number of samples and the number of features and we enable out-of-core computation by loading partial data dynamically.

Our experiments on both real and synthetic datasets demonstrate that CoHiRF is a computationally efficient alternative to state-of-the-art clustering methods, particularly in high-dimensional settings where other popular methods fail to compute. It scales effectively to extremely high-dimensional datasets while maintaining strong statistical accuracy and interpretability, making it valuable for real-world applications.

We proposed to use K-Means as the base clustering algorithm in CoHiRF, primarily due to its low memory footprint and fast execution time. While this choice proved to be useful and allowed us to obtain state-of-the art results, greatly surpassing the performance of the base algorithm, our method is flexible and not restricted to K-Means. Any clustering method can be substituted in its place.

Looking ahead, we aim to extend CoHiRF by integrating alternative clustering techniques within our consensus framework to leverage their respective strengths while maintaining scalability for more challenging clustering tasks.

## References

Agarwal, P. K. and Mustafa, N. H. K-means projective clustering. In Proceedings of the Twenty-Third ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS '04, pp. 155-165, New York, NY, USA, June 2004. Association for Computing Machinery. ISBN 978-1-58113-858-0. doi: 10.1145/1055558.1055581.

Aggarwal, C. C., Wolf, J. L., Yu, P. S., Procopiuc, C., and Park, J. S. Fast algorithms for projected clustering. In Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data, SIGMOD '99, pp. 61-72, New York, NY, USA, June 1999. Association for Computing Machinery. ISBN 978-1-58113-084-3. doi: 10.1145/304182.304188.

Agrawal, R., Gehrke, J., Gunopulos, D., and Raghavan, P. Automatic subspace clustering of high dimensional data for data mining applications. SIGMOD Rec., 27(2):94-105, June 1998. ISSN 0163-5808. doi: 10.1145/276305.276314.

Ankerst, M., Breunig, M. M., Kriegel, H.-P., and Sander, J. OPTICS: Ordering points to identify the clustering structure. SIGMOD Rec., 28(2):49-60, June 1999. ISSN 0163-5808. doi: 10.1145/304181.304187.

Assent, I. Clustering high dimensional data. WIREs Data Mining and Knowledge Discovery, 2(4):340-350, 2012. ISSN 1942-4795. doi: 10.1002/widm.1062.

Beyer, K., Goldstein, J., Ramakrishnan, R., and Shaft, U. When Is "Nearest Neighbor" Meaningful? In Beeri, C. and Buneman, P. (eds.), Database Theory — ICDT'99, pp. 217-235, Berlin, Heidelberg, 1999. Springer. ISBN 978-3-540-49257-3. doi: 10.1007/3-540-49257-7_15.

Cai, X., Huang, D., Wang, C.-D., and Kwoh, C.-K. Spectral Clustering by Subspace Randomization and Graph Fusion for High-Dimensional Data. Advances in Knowledge Discovery and Data Mining, 12084:330, April 2020. doi: 10.1007/978-3-030-47426-3_26.
Caliński, T. and Harabasz, J. A dendrite method for cluster analysis. *Communications in Statistics*, 3(1):1–27, January 1974. ISSN 0090-3272. doi: 10.1080/03610927408827101.

Campello, R. J. G. B., Moulavi, D., and Sander, J. Density-Based Clustering Based on Hierarchical Density Estimates. In Pei, J., Tseng, V. S., Cao, L., Motoda, H., and Xu, G. (eds.), *Advances in Knowledge Discovery and Data Mining*, pp. 160–172, Berlin, Heidelberg, 2013. Springer. ISBN 978-3-642-37456-2. doi: 10.1007/978-3-642-37456-2_14.

Chao, G., Sun, S., and Bi, J. A survey on multiview clustering. *IEEE Transactions on Artificial Intelligence*, 2(2): 146–168, 2021. doi: 10.1109/TAI.2021.3065894.

Comaniciu, D. and Meer, P. Mean shift: A robust approach toward feature space analysis. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, 24(5):603–619, May 2002. ISSN 1939-3539. doi: 10.1109/34.1000236.

Davies, D. L. and Bouldin, D. W. A Cluster Separation Measure. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, PAMI-1(2):224–227, April 1979. ISSN 1939-3539. doi: 10.1109/TPAMI.1979.4766909.

Day, W. H. E. and Edelsbrunner, H. Efficient algorithms for agglomerative hierarchical clustering methods. *Journal of Classification*, 1(1):7–24, December 1984. ISSN 1432-1343. doi: 10.1007/BF01890115.

Ester, M., Kriegel, H.-P., Sander, J., and Xu, X. A density-based algorithm for discovering clusters in large spatial databases with noise. In *Proceedings of the Second International Conference on Knowledge Discovery and Data Mining*, KDD'96, pp. 226–231, Portland, Oregon, August 1996. AAAI Press.

Ezugwu, A. E., Ikotun, A. M., Oyelade, O. O., Abualigah, L., Agushaka, J. O., Eke, C. I., and Akinyelu, A. A. A comprehensive survey of clustering algorithms: State-of-the-art machine learning applications, taxonomy, challenges, and future research prospects. *Engineering Applications of Artificial Intelligence*, 110: 104743, April 2022. ISSN 0952-1976. doi: 10.1016/j.engappai.2022.104743.

Feurer, M., van Rijn, J. N., Kadra, A., Gijsbers, P., Mallik, N., Ravi, S., Mueller, A., Vanschoren, J., and Hutter, F. OpenML-python: An extensible python API for OpenML. *arXiv*, 1911.02490, 2020.

Frey, B. J. and Dueck, D. Clustering by Passing Messages Between Data Points. *Science*, 315(5814):972–976, February 2007. doi: 10.1126/science.1136800.

Haghzad Klidbary, S. and Javadian, M. A Novel Hierarchical High-Dimensional Unsupervised Active Learning Method. *International Journal of Computational Intelligence Systems*, 17(1):193, July 2024. ISSN 1875-6883. doi: 10.1007/s44196-024-00601-w.

Hartigan, J. A. and Wong, M. A. Algorithm AS 136: A K-Means Clustering Algorithm. *Journal of the Royal Statistical Society. Series C (Applied Statistics)*, 28(1): 100–108, 1979. ISSN 0035-9254. doi: 10.2307/2346830.

Hubert, L. and Arabie, P. Comparing partitions. *Journal of Classification*, 2(1):193–218, December 1985. ISSN 1432-1343. doi: 10.1007/BF01908075.

Jain, A. K., Murty, M. N., and Flynn, P. J. Data clustering: A review. *ACM Comput. Surv.*, 31(3):264–323, September 1999. ISSN 0360-0300. doi: 10.1145/331499.331504.

Karim, R., Beyan, O., Zappa, A., Costa, I., Rebholz-Schuhman, D., Cochez, M., and Decker, S. Deep learning-based clustering approaches for bioinformatics. *Briefings in bioinformatics*, 22, February 2020. doi: 10.1093/bib/bbb170.

Kaufman, L. and Rousseeuw, P. J. Divisive Analysis (Program DIANA). In *Finding Groups in Data: An Introduction to Cluster Analysis*, Wiley Series in Probability and Statistics, pp. 253–279. Wiley, 1 edition, March 1990. ISBN 978-0-471-87876-6 978-0-470-31680-1. doi: 10.1002/9780470316801.

Li, G., Liu, F., Sharma, A., Khalaf, O. I., Alotaibi, Y., Alsufyani, A., and Alghamdi, S. Research on the natural language recognition method based on cluster analysis using neural network. *Mathematical Problems in Engineering*, 2021(1):9982305, 2021.

Liu, G., Lin, Z., Yan, S., Sun, J., Yu, Y., and Ma, Y. Robust Recovery of Subspace Structures by Low-Rank Representation. *IEEE Trans. Pattern Anal. Mach. Intell.*, 35(1):171–184, January 2013. ISSN 0162-8828. doi: 10.1109/TPAMI.2012.88.

Liu, Z., Hu, D., Wang, Z., Gou, J., and Jia, T. LatLRR for subspace clustering via reweighted Frobenius norm minimization. *Expert Systems with Applications*, 224: 119977, August 2023. ISSN 0957-4174. doi: 10.1016/j.eswa.2023.119977.

Mahdi, M. A., Hosny, K. M., and Elhenawy, I. Scalable clustering algorithms for big data: A review. *IEEE access: practical innovations, open solutions*, 9:80015–80027, 2021.

McElfresh, D., Khandagale, S., Valverde, J., C. V. P., Feuer, B., Hegde, C., Ramakrishnan, G., Goldblum, M., and White, C. When Do Neural Nets Outperform Boosted Trees on Tabular Data?, October 2023.
Pearson, K. LIII. On lines and planes of closest fit to systems of points in space. *The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science*, 2(11): 559-572, November 1901. ISSN 1941-5982. doi: 10.1080/14786440109462720.

Procopiu, C. M., Jones, M., Agarwal, P. K., and Murali, T. M. A Monte Carlo algorithm for fast projective clustering. In *Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data*, SIGMOD '02, pp. 418-427, New York, NY, USA, June 2002. Association for Computing Machinery. ISBN 978-1-58113-497-1. doi: 10.1145/564691.564739.

Rousseeuw, P. J. Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. *Journal of Computational and Applied Mathematics*, 20:53-65, November 1987. ISSN 0377-0427. doi: 10.1016/0377-0427(87)90125-7.

Saxena, A., Prasad, M., Gupta, A., Bharill, N., Patel, O. P., Tiwari, A., Er, M. J., Ding, W., and Lin, C.-T. A review of clustering techniques and developments. *Neurocomputing*, 267:664-681, December 2017. ISSN 0925-2312. doi: 10.1016/j.neucom.2017.06.053.

Shi, J. and Malik, J. Normalized cuts and image segmentation. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, 22(8):888-905, August 2000. ISSN 1939-3539. doi: 10.1109/34.868688.

Steinbach, M., Ertöz, L., and Kumar, V. The Challenges of Clustering High Dimensional Data. In Wille, L. T. (ed.), *New Directions in Statistical Physics: Econophysics, Bioinformatics, and Pattern Recognition*, pp. 273-309. Springer, Berlin, Heidelberg, 2004. ISBN 978-3-662-08968-2. doi: 10.1007/978-3-662-08968-2_16.

Strehl, A. and Ghosh, J. Cluster ensembles — a knowledge reuse framework for combining multiple partitions. *J. Mach. Learn. Res.*, 3(nul):583–617, March 2003. ISSN 1532-4435. doi: 10.1162/153244303321897735.

van der Maaten, L. and Hinton, G. Visualizing Data using t-SNE. *Journal of Machine Learning Research*, 9(86): 2579-2605, 2008. ISSN 1533-7928.

Watanabe, S. Tree-Structured Parzen Estimator: Understanding Its Algorithm Components and Their Roles for Better Empirical Performance, May 2023.

Xu, R. and Wunsch, D. Survey of clustering algorithms. *IEEE Transactions on Neural Networks*, 16(3):645-678, May 2005. ISSN 1941-0093. doi: 10.1109/TNN.2005.845141.

Zhang, H., Lin, Z., Zhang, C., and Gao, J. Robust latent low rank representation for subspace clustering. *Neurocomputing*, 145:369-373, December 2014. ISSN 0925-2312. doi: 10.1016/j.neucom.2014.05.022.

Zimek, A., Schubert, E., and Kriegel, H.-P. A survey on unsupervised outlier detection in high-dimensional numerical data. *Statistical Analysis and Data Mining: The ASA Data Science Journal*, 5(5):363-387, 2012.
## A. Algorithms Search Space

In Table 3 we present the search space of each clustering algorithm.

<table><caption>Table 3. Search space of each clustering algorithm.</caption><thead><tr><th>MODEL</th><th>PARAMETER</th><th>VALUE</th></tr></thead><tbody><tr><td rowspan="3">COHiRF</td><td>NUMBER OF RANDOMLY SAMPLED COMPONENTS := q</td><td>[2, 30]</td></tr><tr><td>NUMBER OF REPETITIONS := R</td><td>[2, 10]</td></tr><tr><td>NUMBER OF K-MEANS CLUSTERS := C</td><td>[2, 10]</td></tr><tr><td rowspan="2">CLIQUE</td><td>NUMBER OF PARTITIONS := ξ</td><td>[5, 200]</td></tr><tr><td>DENSITY THRESHOLD := τ</td><td>[0.1, 0.8]</td></tr><tr><td rowspan="5">IRFLLRR</td><td>p</td><td>[0.0, 1.0]</td></tr><tr><td>c</td><td>{1e-3, 1e-2, 1e-1, 1.0, 1e1, 1e2}</td></tr><tr><td>λ</td><td>{1e-3, 1e-2, 1e-1, 1.0, 1e1, 1e2}</td></tr><tr><td>α</td><td>[1.0, 4.0]</td></tr><tr><td>NUMBER OF CLUSTERS := C</td><td>[2, 30]</td></tr><tr><td>K-MEANS PROJ.</td><td>NUMBER OF CLUSTERS := C</td><td>[2, 30]</td></tr><tr><td rowspan="2">PROCLUS</td><td>NUMBER OF CLUSTERS := C</td><td>[2, 30]</td></tr><tr><td>AVERAGE NUMBER OF DIMENSIONS := q</td><td>[2, 30]</td></tr><tr><td rowspan="3">SC-SRGF</td><td>NUMBER OF AFFINITY MATRICES := m</td><td>[10, 30]</td></tr><tr><td>NUMBER OF CLUSTERS := C</td><td>[2, 30]</td></tr><tr><td>SAMPLING RATIO := r</td><td>[0.2, 0.8]</td></tr><tr><td>K-MEANS</td><td>NUMBER OF CLUSTERS := C</td><td>[2, 30]</td></tr><tr><td>AFFINITY PROPAGATION</td><td>DAMPING := λ</td><td>[0.5, 1.0]</td></tr><tr><td>SPECTRAL CLUSTERING</td><td>NUMBER OF CLUSTERS := C</td><td>[2, 30]</td></tr><tr><td>AGGLOMERATIVE CLUSTERING<sup>a</sup></td><td>NUMBER OF CLUSTERS := C</td><td>[2, 30]</td></tr><tr><td rowspan="2">DBSCAN</td><td>ε</td><td>LOGARITHMIC [1e-1, 1e2]</td></tr><tr><td>MINIMUM NUMBER OF SAMPLES := n<sub>MIN</sub></td><td>[2, 10]</td></tr><tr><td>HDBSCAN</td><td>MINIMUM CLUSTER SIZE := C<sub>MIN</sub></td><td>[2, 10]</td></tr><tr><td>OPTICS</td><td>MINIMUM NUMBER OF SAMPLES := n<sub>MIN</sub></td><td>[2, 10]</td></tr></tbody></table>

## B. Hierarchical clustering experiment

Our algorithm is an agglomerative clustering method as illustrated in Figure 2. We explored this aspect with an experiment on the *iris* data where we represent the hierarchy built by CoHiRF-RBF, the result can be seen in Figure 7.

<footnote>a IT INCLUDES SINGLE LINKAGE, COMPLETE LINKAGE, AVERAGE LINKAGE, AND WARD'S METHOD</footnote>
<figure><img src="image_9.png" /><figcaption>**Figure 7.** Hierarchical clustering structure obtained by CoHiRF-RBF. We present the number of examples of each iris species inside each cluster. From left to right, we can observe the clusters that are merged at each iteration of our algorithm. Note that contrary from most hierarchical clustering algorithm, CoHiRF can merge more than one cluster at each step, which contributes to its speed.</figcaption></figure>
C. Hyperparameter tuning

Even though we do not need to specify the number of clusters, our algorithm has three main hyperparameters: the number of repetitions *R*, the number of sampled components *q* and the number of clusters *C* used in the K-Means algorithm. Find the right balance between those parameters can be challenging, fortunately, as our algorithm is fast, we can afford to tune those hyperparameters. Empirically, we have defined that a good search space is $R \in [2, 10]$, $q \in [2, 30]$, and $k \in [2, 10]$.

To illustrate the importance of hyperparameter tuning we present in Figure 8 the result of the search for optimal hyperparameters in one experience. We generated datasets with $n = 10^3$ samples, creating $C^* = 5$ clusters. The cluster centers are drawn uniformly at random from the set of vertices of a $10^4$-dimensional hypercube, with edge length $\Delta = 50$ (i.e., the inter-cluster distance). Samples within each cluster are randomly drawn from a Normal distribution with an identity covariance matrix (thus controlling the intra-cluster distance), centered at the corresponding cluster center.

Note that from 100 different runs, only 4 have find a good combination of the hyperparameters, that in this case perfectly partition the data and find the correct number of clusters. In this case, the right balance was to use a small number of repetitions and K-Means clusters with a large number of sampled components.

<figure><img src="image_10.png" /><figcaption>Figure 8. Parallel plot showing the runs from the hypercube experiment, with $n = 1000$, $p = 10000$, and Class Separation = 50. The runs in green have perfectly partition the synthetic data.</figcaption></figure>
## D. Code

The code is available on https://github.com/BrunoBelucci/cohirf
E. Experiment on Real Data

In Table 4 we present the same results as in Table 2, but with the running time of each algorithm.

<table><caption>Table 4: Results on real-world datasets.</caption><thead><tr><th>DATASET</th><th>MODEL</th><th>ARI</th><th>TIME (S)</th><th>PARAMETERS</th></tr></thead><tbody><tr><td rowspan="14">ALIZADEH-2000-V2</td><td>AFFINITY PROPAGATION</td><td>0.363</td><td>0.012</td><td>λ = 0.86</td></tr><tr><td>AVERAGE AGGLOMERATIVE</td><td>0.810</td><td>0.019</td><td>C = 4</td></tr><tr><td>CLIQUE</td><td>0.000</td><td>0.131</td><td>τ = 0.50; P = 100</td></tr><tr><td>CoHiRF</td><td><u>0.831</u></td><td>0.016</td><td>C = 2; q = 30; R = 3</td></tr><tr><td>COMPLETE AGGLOMERATIVE</td><td>0.539</td><td>0.009</td><td>C = 6</td></tr><tr><td>DBSCAN</td><td>0.250</td><td>0.009</td><td>ε = 39.56; n<sub>MIN</sub> = 2</td></tr><tr><td>HDBSCAN</td><td>0.166</td><td>0.025</td><td>C<sub>MIN</sub> = 2</td></tr><tr><td>IRFLLRR</td><td>0.080</td><td>2.838</td><td>C = 8; λ = 1; α = 4; c = 0.10; p = 0.95</td></tr><tr><td>K-MEANS</td><td>0.815</td><td>0.011</td><td>C = 2</td></tr><tr><td>OPTICS</td><td>0.395</td><td>0.050</td><td>n<sub>MIN</sub> = 2</td></tr><tr><td>PROCLUS</td><td>0.446</td><td>0.033</td><td>d = 21; C = 2</td></tr><tr><td>PROJECTIVE K-MEANS</td><td>0.117</td><td>0.235</td><td>C = 2</td></tr><tr><td>SC-SRGF</td><td>0.599</td><td>0.142</td><td>C = 4; r = 0.76; m = 21</td></tr><tr><td>SINGLE AGGLOMERATIVE</td><td>-0.022</td><td>0.011</td><td>C = 2</td></tr><tr><td><strong>WARD'S METHOD</strong></td><td><strong>0.947</strong></td><td>0.011</td><td>C = 3</td></tr><tr><td rowspan="14">COIL-20</td><td>AFFINITY PROPAGATION</td><td>0.407</td><td>3.615</td><td>λ = 0.51</td></tr><tr><td>AVERAGE AGGLOMERATIVE</td><td>0.081</td><td>0.365</td><td>C = 30</td></tr><tr><td>CoHiRF</td><td>0.464</td><td>0.514</td><td>C = 10; q = 8; R = 7</td></tr><tr><td>COMPLETE AGGLOMERATIVE</td><td>0.178</td><td>0.355</td><td>C = 30</td></tr><tr><td>DBSCAN</td><td>0.491</td><td>0.055</td><td>ε = 22.78; n<sub>MIN</sub> = 5</td></tr><tr><td>HDBSCAN</td><td>0.677</td><td>2.173</td><td>C<sub>MIN</sub> = 4</td></tr><tr><td>K-MEANS</td><td>0.655</td><td>0.073</td><td>C = 30</td></tr><tr><td>OPTICS</td><td>0.092</td><td>5.225</td><td>n<sub>MIN</sub> = 8</td></tr><tr><td>PROCLUS</td><td>0.167</td><td>3.332</td><td>d = 28; C = 18</td></tr><tr><td>PROJECTIVE K-MEANS</td><td>0.372</td><td>553.075</td><td>C = 10</td></tr><tr><td><strong>SC-SRGF</strong></td><td><strong>0.776</strong></td><td>22.408</td><td>C = 18; r = 0.23; m = 24</td></tr><tr><td>SINGLE AGGLOMERATIVE</td><td>0.000</td><td>0.981</td><td>C = 30</td></tr><tr><td>WARD'S METHOD</td><td>0.719</td><td>0.354</td><td>C = 24</td></tr><tr><td rowspan="14">ECOLI</td><td>AFFINITY PROPAGATION</td><td>0.248</td><td>0.072</td><td>λ = 0.58</td></tr><tr><td>AVERAGE AGGLOMERATIVE</td><td>0.728</td><td>0.005</td><td>C = 11</td></tr><tr><td>CoHiRF</td><td><u>0.758</u></td><td>0.273</td><td>R = 10; C = 7; q = 11</td></tr><tr><td>CoHiRF-1000</td><td>0.751</td><td>0.297</td><td>R = 4; C = 7; q = 22</td></tr><tr><td>CoHiRF-FULL</td><td>0.734</td><td>0.233</td><td>R = 10; C = 4; q = 12</td></tr><tr><td>CoHiRF-RBF</td><td>0.742</td><td>0.165</td><td>R = 4; C = 7; q = 25</td></tr><tr><td>COMPLETE AGGLOMERATIVE</td><td><strong>0.785</strong></td><td>0.006</td><td>C = 7</td></tr><tr><td>DBSCAN</td><td>0.345</td><td>0.018</td><td>n<sub>MIN</sub> = 7; ε = 0.78</td></tr><tr><td>HDBSCAN</td><td>0.398</td><td>0.020</td><td>C<sub>MIN</sub> = 10</td></tr><tr><td>IRFLLRR</td><td>0.306</td><td>0.339</td><td>λ = 1; C = 8; p = 0.95; c = 0.10; α = 4</td></tr><tr><td>K-MEANS</td><td>0.719</td><td>0.005</td><td>C = 6</td></tr><tr><td>OPTICS</td><td>0.314</td><td>5.047</td><td>n<sub>MIN</sub> = 10</td></tr><tr><td>PROCLUS</td><td>0.643</td><td>0.129</td><td>d = 7; C = 5</td></tr><tr><td>PROJECTIVE K-MEANS</td><td>0.164</td><td>0.373</td><td>C = 3</td></tr><tr><td>SC-SRGF</td><td>0.723</td><td>1.782</td><td>m = 15; C = 4; r = 0.80</td></tr><tr><td>SINGLE AGGLOMERATIVE</td><td>0.063</td><td>0.005</td><td>C = 22</td></tr><tr><td>WARD'S METHOD</td><td>0.735</td><td>0.006</td><td>C = 7</td></tr><tr><td rowspan="14">GARBER-2001</td><td>AFFINITY PROPAGATION</td><td>0.075</td><td>0.022</td><td>λ = 0.80</td></tr><tr><td>AVERAGE AGGLOMERATIVE</td><td>0.146</td><td>0.019</td><td>C = 26</td></tr><tr><td>CLIQUE</td><td>0.062</td><td>0.256</td><td>τ = 0.41; P = 23</td></tr><tr><td>CoHiRF</td><td><strong>0.298</strong></td><td>0.128</td><td>C = 2; q = 18; R = 10</td></tr><tr><td>COMPLETE AGGLOMERATIVE</td><td><u>0.283</u></td><td>0.019</td><td>C = 14</td></tr><tr><td>DBSCAN</td><td>0.043</td><td>0.020</td><td>ε = 77.80; n<sub>MIN</sub> = 5</td></tr><tr><td>HDBSCAN</td><td>0.026</td><td>0.050</td><td>C<sub>MIN</sub> = 2</td></tr><tr><td>IRFLLRR</td><td>-0.015</td><td>6.607</td><td>C = 8; λ = 1; α = 4; c = 0.10; p = 0.95</td></tr><tr><td>K-MEANS</td><td>0.188</td><td>0.022</td><td>C = 3</td></tr><tr><td>OPTICS</td><td>0.068</td><td>0.120</td><td>n<sub>MIN</sub> = 9</td></tr><tr><td>PROCLUS</td><td>0.046</td><td>0.152</td><td>d = 13; C = 15</td></tr><tr><td>PROJECTIVE K-MEANS</td><td>0.115</td><td>21.087</td><td>C = 7</td></tr><tr><td>SC-SRGF</td><td>0.175</td><td>0.162</td><td>C = 4; r = 0.76; m = 21</td></tr><tr><td>SINGLE AGGLOMERATIVE</td><td>0.145</td><td>0.025</td><td>C = 25</td></tr><tr><td>WARD'S METHOD</td><td>0.200</td><td>0.021</td><td>C = 13</td></tr></tbody></table>

CONTINUED ON NEXT PAGE
<table><thead><tr><th>DATASET</th><th>MODEL</th><th>ARI</th><th>TIME (s)</th><th>PARAMETERS</th></tr></thead><tbody><tr><td rowspan="14">HAR</td><td>AFFINITY PROPAGATION</td><td>0.313</td><td>35.781</td><td>λ = 1.00</td></tr><tr><td>AVERAGE AGGLOMERATIVE</td><td>0.002</td><td>23.677</td><td>C = 5</td></tr><tr><td>CoHiRF</td><td>0.491</td><td>1.410</td><td>R = 8; C = 4; q = 11</td></tr><tr><td>CoHiRF-1000</td><td>0.341</td><td>0.449</td><td>R = 3; C = 4; q = 18</td></tr><tr><td>CoHiRF-FULL</td><td>0.426</td><td>7.964</td><td>R = 6; C = 10; q = 10</td></tr><tr><td>CoHiRF-RBF</td><td>0.495</td><td>0.932</td><td>R = 4; C = 6; q = 13</td></tr><tr><td>COMPLETE AGGLOMERATIVE</td><td>0.332</td><td>24.954</td><td>C = 4</td></tr><tr><td>DBSCAN</td><td>0.302</td><td>1.372</td><td>n<sub>MIN</sub> = 3; ε = 13.91</td></tr><tr><td>HDBSCAN</td><td>0.287</td><td>54.107</td><td>C<sub>MIN</sub> = 6</td></tr><tr><td>K-MEANS</td><td>0.438</td><td>0.433</td><td>C = 9</td></tr><tr><td>OPTICS</td><td>0.001</td><td>209.746</td><td>n<sub>MIN</sub> = 4</td></tr><tr><td>PROCLUS</td><td>0.322</td><td>61.353</td><td>d = 26; C = 4</td></tr><tr><td>PROJECTIVE K-MEANS</td><td>0.388</td><td>1077.523</td><td>C = 4</td></tr><tr><td>SC-SRGF</td><td><strong>0.546</strong></td><td>3521.249</td><td>m = 21; C = 20; r = 0.45</td></tr><tr><td>SINGLE AGGLOMERATIVE</td><td>0.000</td><td>33.962</td><td>C = 30</td></tr><tr><td>WARD'S METHOD</td><td>0.511</td><td>20.600</td><td>C = 4</td></tr><tr><td rowspan="14">IRIS</td><td>AFFINITY PROPAGATION</td><td>0.477</td><td>0.079</td><td>λ = 0.98</td></tr><tr><td>AVERAGE AGGLOMERATIVE</td><td>0.568</td><td>0.003</td><td>C = 2</td></tr><tr><td>CoHiRF</td><td>0.631</td><td>0.146</td><td>R = 7; C = 4; q = 26</td></tr><tr><td>CoHiRF-1000</td><td>0.733</td><td>0.163</td><td>R = 10; C = 3; q = 10</td></tr><tr><td>CoHiRF-FULL</td><td>0.639</td><td>0.127</td><td>R = 7; C = 3; q = 15</td></tr><tr><td>CoHiRF-RBF</td><td>0.729</td><td>0.087</td><td>R = 3; C = 5; q = 21</td></tr><tr><td>COMPLETE AGGLOMERATIVE</td><td>0.573</td><td>0.004</td><td>C = 3</td></tr><tr><td>DBSCAN</td><td>0.558</td><td>0.017</td><td>n<sub>MIN</sub> = 5; ε = 1.37</td></tr><tr><td>HDBSCAN</td><td>0.564</td><td>0.018</td><td>C<sub>MIN</sub> = 9</td></tr><tr><td>IRFLLRR</td><td>0.142</td><td>0.218</td><td>λ = 1; C = 8; p = 0.95; c = 0.10; α = 4</td></tr><tr><td>K-MEANS</td><td>0.592</td><td>0.005</td><td>C = 3</td></tr><tr><td>OPTICS</td><td>0.396</td><td>2.291</td><td>n<sub>MIN</sub> = 10</td></tr><tr><td>PROCLUS</td><td><strong>0.752</strong></td><td>0.026</td><td>d = 2; C = 4</td></tr><tr><td>PROJECTIVE K-MEANS</td><td>0.143</td><td>0.751</td><td>C = 4</td></tr><tr><td>SC-SRGF</td><td><strong>0.865</strong></td><td>1.735</td><td>m = 26; C = 3; r = 0.79</td></tr><tr><td>SINGLE AGGLOMERATIVE</td><td>0.568</td><td>0.003</td><td>C = 2</td></tr><tr><td>WARD'S METHOD</td><td>0.615</td><td>0.002</td><td>C = 3</td></tr><tr><td rowspan="14">NURSERY</td><td>AFFINITY PROPAGATION</td><td>0.016</td><td>348.787</td><td>λ = 0.95</td></tr><tr><td>AVERAGE AGGLOMERATIVE</td><td>0.020</td><td>5.570</td><td>C = 6</td></tr><tr><td>CoHiRF</td><td>0.440</td><td>0.327</td><td>R = 6; C = 3; q = 30</td></tr><tr><td>CoHiRF-1000</td><td>0.171</td><td>0.436</td><td>R = 5; C = 3; q = 21</td></tr><tr><td>CoHiRF-FULL</td><td><strong>0.455</strong></td><td>1.065</td><td>R = 4; C = 2; q = 2</td></tr><tr><td>CoHiRF-RBF</td><td><strong>0.510</strong></td><td>1.439</td><td>R = 3; C = 2; q = 11</td></tr><tr><td>COMPLETE AGGLOMERATIVE</td><td>0.040</td><td>5.067</td><td>C = 11</td></tr><tr><td>DBSCAN</td><td>0.000</td><td>2.192</td><td>n<sub>MIN</sub> = 5; ε = 0.50</td></tr><tr><td>HDBSCAN</td><td>0.014</td><td>2.583</td><td>C<sub>MIN</sub> = 9</td></tr><tr><td>K-MEANS</td><td>0.150</td><td>0.018</td><td>C = 2</td></tr><tr><td>OPTICS</td><td>0.000</td><td>23.886</td><td>n<sub>MIN</sub> = 9</td></tr><tr><td>PROJECTIVE K-MEANS</td><td>0.010</td><td>8.547</td><td>C = 4</td></tr><tr><td>SINGLE AGGLOMERATIVE</td><td>-0.000</td><td>1.844</td><td>C = 4</td></tr><tr><td>WARD'S METHOD</td><td>0.254</td><td>5.598</td><td>C = 3</td></tr><tr><td rowspan="14">SATIMAGE</td><td>AFFINITY PROPAGATION</td><td>0.190</td><td>142.309</td><td>λ = 0.99</td></tr><tr><td>AVERAGE AGGLOMERATIVE</td><td>0.579</td><td>1.829</td><td>C = 28</td></tr><tr><td>CoHiRF</td><td><strong>0.583</strong></td><td>2.006</td><td>R = 10; C = 9; q = 19</td></tr><tr><td>CoHiRF-1000</td><td>0.581</td><td>1.902</td><td>R = 9; C = 6; q = 14</td></tr><tr><td>CoHiRF-FULL</td><td>0.518</td><td>0.523</td><td>R = 3; C = 6; q = 30</td></tr><tr><td>CoHiRF-RBF</td><td><strong>0.583</strong></td><td>2.123</td><td>R = 8; C = 9; q = 10</td></tr><tr><td>COMPLETE AGGLOMERATIVE</td><td>0.321</td><td>1.767</td><td>C = 23</td></tr><tr><td>DBSCAN</td><td>0.297</td><td>0.110</td><td>n<sub>MIN</sub> = 7; ε = 1.54</td></tr><tr><td>HDBSCAN</td><td>0.308</td><td>1.325</td><td>C<sub>MIN</sub> = 6</td></tr><tr><td>IRFLLRR</td><td>0.093</td><td>115.596</td><td>λ = 1; C = 8; p = 0.95; c = 0.10; α = 4</td></tr><tr><td>K-MEANS</td><td>0.566</td><td>0.027</td><td>C = 7</td></tr><tr><td>OPTICS</td><td>0.023</td><td>10.472</td><td>n<sub>MIN</sub> = 2</td></tr><tr><td>PROCLUS</td><td>0.475</td><td>10.735</td><td>d = 30; C = 10</td></tr><tr><td>PROJECTIVE K-MEANS</td><td>0.358</td><td>32.988</td><td>C = 4</td></tr><tr><td>SC-SRGF</td><td><strong>0.618</strong></td><td>1347.919</td><td>m = 21; C = 4; r = 0.76</td></tr><tr><td>SINGLE AGGLOMERATIVE</td><td>0.002</td><td>0.870</td><td>C = 30</td></tr><tr><td>WARD'S METHOD</td><td>0.485</td><td>1.902</td><td>C = 5</td></tr></tbody></table>

CONTINUED ON NEXT PAGE
<table><thead><tr><th>DATASET</th><th>MODEL</th><th>ARI</th><th>TIME (S)</th><th>PARAMETERS</th></tr></thead><tbody><tr><td rowspan="15">SEGMENT</td><td>AFFINITY PROPAGATION</td><td>0.280</td><td>17.007</td><td>λ = 0.93</td></tr><tr><td>AVERAGE AGGLOMERATIVE</td><td>0.244</td><td>0.142</td><td>C = 29</td></tr><tr><td><strong>CoHiRF</strong></td><td><strong>0.540</strong></td><td>0.220</td><td>R = 10; C = 5; q = 21</td></tr><tr><td>CoHiRF-1000</td><td>0.532</td><td>1.422</td><td>R = 8; C = 8; q = 2</td></tr><tr><td>CoHiRF-FULL</td><td>0.511</td><td>0.492</td><td>R = 6; C = 8; q = 2</td></tr><tr><td>CoHiRF-RBF</td><td>0.518</td><td>1.008</td><td>R = 6; C = 8; q = 2</td></tr><tr><td>COMPLETE AGGLOMERATIVE</td><td>0.280</td><td>0.161</td><td>C = 23</td></tr><tr><td>DBSCAN</td><td>0.251</td><td>0.025</td><td>n<sub>MIN</sub> = 7; ϵ = 0.54</td></tr><tr><td>HDBSCAN</td><td>0.390</td><td>0.157</td><td>C<sub>MIN</sub> = 5</td></tr><tr><td>IRFLLRR</td><td>0.405</td><td>6.677</td><td>λ = 1; C = 8; p = 0.95; c = 0.10; α = 4</td></tr><tr><td>K-MEANS</td><td>0.512</td><td>0.019</td><td>C = 10</td></tr><tr><td>OPTICS</td><td>0.097</td><td>1.835</td><td>n<sub>MIN</sub> = 10</td></tr><tr><td>PROCLUS</td><td>0.509</td><td>2.267</td><td>d = 15; C = 8</td></tr><tr><td>PROJECTIVE K-MEANS</td><td>0.338</td><td>185.655</td><td>C = 13</td></tr><tr><td>SC-SRGF</td><td>0.481</td><td>194.087</td><td>m = 23; C = 14; r = 0.65</td></tr><tr><td>SINGLE AGGLOMERATIVE</td><td>0.001</td><td>0.072</td><td>C = 26</td></tr><tr><td>WARD'S METHOD</td><td>0.446</td><td>0.159</td><td>C = 8</td></tr><tr><td rowspan="15">SHUTTLE</td><td>AVERAGE AGGLOMERATIVE</td><td>0.006</td><td>236.919</td><td>C = 27</td></tr><tr><td>CoHiRF</td><td>0.652</td><td>4.327</td><td>R = 8; C = 6; q = 5</td></tr><tr><td><strong>CoHiRF-1000</strong></td><td><strong>0.771</strong></td><td>3.085</td><td>R = 7; C = 9; q = 3</td></tr><tr><td>CoHiRF-FULL</td><td>0.601</td><td>10.839</td><td>R = 10; C = 3; q = 30</td></tr><tr><td>CoHiRF-RBF</td><td>0.685</td><td>3.923</td><td>R = 7; C = 8; q = 4</td></tr><tr><td>COMPLETE AGGLOMERATIVE</td><td>0.006</td><td>239.934</td><td>C = 30</td></tr><tr><td><strong>DBSCAN</strong></td><td><strong>0.686</strong></td><td>22.333</td><td>n<sub>MIN</sub> = 10; ϵ = 0.27</td></tr><tr><td>HDBSCAN</td><td>0.001</td><td>39.957</td><td>C<sub>MIN</sub> = 2</td></tr><tr><td>K-MEANS</td><td>0.608</td><td>0.038</td><td>C = 2</td></tr><tr><td>OPTICS</td><td>0.017</td><td>1150.920</td><td>n<sub>MIN</sub> = 5</td></tr><tr><td>PROCLUS</td><td>0.443</td><td>64.062</td><td>d = 7; C = 5</td></tr><tr><td>PROJECTIVE K-MEANS</td><td>0.644</td><td>61.634</td><td>C = 4</td></tr><tr><td>SINGLE AGGLOMERATIVE</td><td>0.003</td><td>30.612</td><td>C = 29</td></tr><tr><td>WARD'S METHOD</td><td>0.478</td><td>149.456</td><td>C = 2</td></tr></tbody></table>