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

HAL
open science

CLASSIX: FAST AND EXPLAINABLE CLUSTERING
BASED ON SORTING

Xinye Chen, Stefan Güttel

► To cite this version:

Xinye Chen, Stefan Güttel. CLASSIX: FAST AND EXPLAINABLE CLUSTERING BASED ON SORTING. SIAM Conference on Computational Science and Engineering (CSE23), Feb 2023, Amsterdam, Netherlands. 2023. [hal-05302717](https://hal.science/hal-05302717v1)

HAL Id: hal-05302717

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

Submitted on 8 Oct 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
## CLASSIX: CLUSTERING BY SORTING

Given $n$ mean-centered data points $x_1, \dots, x_n \in \mathbb{R}^d$. CLASSIX consists of two phases explained below.

**Aggregation:** Aims at grouping nearby data points together in a computationally inexpensive manner. "Nearby" is defined in terms of the Euclidean distance $\text{dist}(x_i, x_j) = \|x_i - x_j\|$.

We compute the first principal direction $v$, $\|v\| = 1$, of the data and sort the data points $x_i$ with respect to $\alpha_i := v^T x_i$ such that

$$ \alpha_1 \le \alpha_2 \le \dots \le \alpha_n. $$

Starting with $x_1$, all data points $x_2, x_3, \dots$ (in that order) are assigned to a first group $G_1$ if $\|x_i - x_1\| \le R$ with a user-defined radius $R$.

Since $\|x_i - x_1\| \ge \alpha_i - \alpha_1$ and the $\alpha_i$'s are sorted, we can stop traversing the $x_i$ as soon as $\alpha_i - \alpha_1 > R$. This **early search termination** can keep the number of pairwise distance computations low.

We then proceed with the next unassigned data point to form a second group $G_2$, and so on, until every data point belongs to a group.

The aggregation has linear space complexity. If the number of formed groups is independent of $n$, it also has near linear time complexity (i.e., $O(n \log n)$) from the sorting).

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

**Merging:** Two groups $G_i$ and $G_j$ are merged if

$$ \text{dist}(x_{s(i)}, x_{s(j)}) \le \text{scale} \cdot R, \quad (1) $$

where $\text{scale} \in [1, 2]$ and $x_{s(i)}$ refers to the starting point of group $i$. These starting points $x_{s(j)}$ are already sorted so that $\alpha_{s(1)} \le \alpha_{s(2)} \le \dots$. We construct a graph of the starting points with an edge between any pair if (1) is satisfied. We use a disjoint union set data structure to find the connected components in the graph as clusters.

## EXPLAINABILITY

CLASSIX is a direct, noniterative clustering method. Its inherent simplicity allows for the generation of intuitive explanations of the computed clusters. We can simply track the aggregation and merging steps and use them to explain why two data points have been clustered together, or not [1]. Python implementation:

https://github.com/nla-group/classix.

## ANALYSIS: GAUSSIAN MODEL

To study CLASSIX's parameter dependencies, we consider an elongated "Gaussian blob" $\{x_i\}_{i=1}^n \subset \mathbb{R}^d$ with normally distributed components of zero mean and standard deviations $[1, s, \dots, s]$, $s < 1$.

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

The first principal direction approaches the canonical unit vector $e_1$ as $n \to \infty$ and the principal coordinates $\alpha_i = e_1^T x_i$ follow a standard normal distribution.

Assuming that $[c, 0, \dots, 0]^T$ is a starting point of a group, our goal is to count all data points $x_i$ within a radius $R$ of this starting point, and to relate this to the number of points whose first principal component is close to $c$.

For any $c \in \mathbb{R}$ the probability that $|\alpha_i - c| \le R$ is

$$ P_1 = P_1(c, R) = \frac{1}{\sqrt{2\pi}} \int_{c-R}^{c+R} e^{-r^2/2} dr. $$

The probability that $\|x_i - [c, 0, \dots, 0]^T\| \le R$ is given by

$$ P_2 = \frac{1}{\sqrt{2\pi}} \int_{c-R}^{c+R} e^{-r^2/2} \cdot F \left( \frac{R^2 - (r-c)^2}{s^2} ; d-1 \right) dr, $$

where $F$ is the $\chi^2$ cumulative distribution function.

Since $\|x_i - [c, 0, \dots, 0]^T\| \le R$ implies that $|\alpha_i - c| \le R$, we have $P_1 \ge P_2$. We define the conditional probability $P := P(\|x_i - [c, 0, \dots, 0]^T\| \le R | e_1^T x_i - c \le R) = P_2/P_1$. Ideally, $P$ is close to 1. We can show that

* $P = P_2/P_1$ decreases monotonically as $s$ ("blob elongation") and $d$ (feature dimension) increase

* $P_2/P_1 \to 1$ as $R$ (group radius) increases.

**Summary:** Our analysis shows that data that approximately aligns on a line or low-dimensional subspace is easier to cluster. If the group radius can be chosen large (well separated groups), CLASSIX is likely to be faster.

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

## EMPIRICAL PERFORMANCE EVALUATION

**Shapes benchmark:** We compare CLASSIX to k-means++, Mean shift, DBSCAN, HDBSCAN, Quickshift++. For k-means we specify the ground-truth number $k$. The other methods are optimized by grid search.

The clustering results are shown below, with the required computation time in the bottom right of each plot. For CLASSIX, the average number of distance computations per data point is shown in the bottom left.

The number of distance computations in CLASSIX is low and it is the fastest method in this test.

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

**Olivetti faces:** Following an example in [2], we cluster 100 images of 10 distinct faces. The result is shown below, with different colours corresponding to different CLASSIX clusters and with gray-scale images corresponding to outliers.

CLASSIX classifies 77 of the 100 images into 7 clusters. Six of these clusters contain ten images that are perfectly classified (60% overall). For comparison, the method in [2] classifies 10 images perfectly (10% overall).

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

## DEMO: EXPLAINING CLUSTERS

This is a demo of CLASSIX's explainability feature using a data set of $n = 2,028,780$ points in $d = 2$ dimensions.

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

CLASSIX outputs the following explanation: "The radius parameter was set to 1.00 and MinPts was set to 0. As the provided data has been scaled by a factor of 1/2.46, data points within a radius of $R = 1.00 \cdot 2.46 = 2.46$ were aggregated into groups. In total 3,920,623 comparisons were required (1.93 comparisons per data point). This resulted in 36 groups, each uniquely associated with a starting point. These 36 groups were subsequently merged into 4 clusters."

When queried about specific data points, we get:

classix.explain(10000, 16908) # in same cluster

"Data point 10,000 is in group 0 and data point 16,908 is in group 9. Both groups were merged into cluster #1. The groups are connected via groups 0 ↔ 2 ↔ 3 ↔ 4 ↔ 5 ↔ 8 ↔ 9."

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

classix.explain(14940, 16943) # diff. clusters

"Data point 14,940 is in group 7, merged into cluster 1. Data point 16,943 is in group 11, merged into cluster 3. There is no path of overlapping groups between these clusters."

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

## REFERENCES

[1] X. CHEN AND S. GÜTTEL, Fast and explainable clustering based on sorting, arXiv preprint 2202.01456, 2022.

[2] R. ALEX AND L. ALESSANDRO, Clustering by fast search and find of density peaks, Science 344, 2014.