I created a clustering algorithm SPORE (Skeleton Propagation Over Recalibrating Expansions) for normal function clustering, meant to deal with nonconvex, convex, low-d and high-d knowledge alike. I've benchmarked it on 28 datasets from 2-784D and launched a Python bundle in addition to a analysis paper.

Brief Abstract

SPORE is a density-variance-based technique meant for normal clustering in arbitrary geometries and dimensionalities. After constructing a knn graph, it has 2 phases. Part 1 (Growth) makes use of BFS with a frequently refined density-variance constraint to increase preliminary clusters in a means that adapts to their particular scale. The goal is to seize interior, well-shielded skeletons and keep again from low-separation boundary areas. Part 2 (Small-Cluster Reassignment aka SCR) takes these boundary factors and merges them into the skeletons they encompass, and might draw sharp traces between adjoining cluster boundaries, form of like kmeans partitioning to the closest centroid/consultant. So collectively, SPORE has scale-adaptive form recognition capabilities and might draw sharp boundaries when clusters are close to one another, so it may strongly resist the merge-or-fragment downside with most density based mostly clustering algorithms. It's additionally fairly sturdy to dimensionality, all the best way as much as tons of of dimensions. I’ve even used it on 1000D+ llm embeddings and gotten clear outcomes (although to be honest, llm embeddings are sometimes skilled to be well-separated regardless of being high-D).

Extra In-depth

SPORE has 3 important steps, 2 of that are phases the place the precise clustering happens:

1. Assemble a knn graph. You are able to do this both precise or approximate. I'd go along with approximate through HNSW (that's what the Python bundle makes use of as a default). Efficiency is actually the identical both means, since SPORE simply wants an approximate sense of intra-cluster density variance to constrain growth. Precise knn isn't required; so long as the neighbor error isn't too excessive, it is going to be high quality usually.
2. Carry out BFS. That is the place SPORE’s title is most becoming; like a organic spore, it seeds clusters at particular factors and grows them outward over the info manifold till the manifold is not “hospitable”.
   1. First you kind factors in reverse order of density.
   2. Then you definitely extract the densest level and start BFS round it.
   3. Throughout BFS you monitor the imply and std deviation of neighbor distance, and replace it with every accepted level. When contemplating factors so as to add, you employ the present imply and std deviation to compute the z rating of that time's distance from the frontier. If the z-score is simply too excessive (based mostly on a user-provided threshold), then the purpose is rejected. Finally the z-score of all candidate factors will probably be too excessive; this can naturally occur when the cluster is approaching its boundary and is beginning to skinny out.
   4. After cluster 1 finishes increasing, you simply seize the following densest level and begin BFS for cluster 2.
   5. By the tip, the objective is to have at the least expanded some minimal core skeleton inside every true cluster, whereas leaving the boundary fragmented, since rising into boundary areas may cause growth to bleed into adjoining clusters. If skeletons are intact and bounds are shattered off, that's the perfect setup for the following section.
      1. A pleasant consequence of the density variance method is a level of robustness to low distance distinction that helps with skeleton isolation: if distinction is low, customary deviation in distance drops accordingly, so small-but-consistent variations in distance nonetheless present some sign, and that's sufficient to separate the interior skeletons of clusters from one another in lots of instances.
      2. It's not strictly about skeletons. If the dataset is already effectively separated, growth alone may do the job, and also you don’t even want the following section.
3. Small Cluster Reassignment (SCR). As soon as skeletons are recognized, then comes small cluster reassignment, aka SCR. I consider this section like a localized Ok-means, the place you partition factors by their nearest cluster consultant. This time nevertheless, representatives are factors from a specific cluster inside a to-be-reassigned level's knn, and the partitioning algorithm is actually a knn classifier. So, this section takes all factors in small clusters (ideally fabricated from barrier factors) and reassigns them to the cluster amongst their knn that maximizes a rating measuring sure geometric circumstances like enclosure, knn rely, and nearness. That max-selection is why it may draw sharp boundaries. Even when separation is minimal, you simply want some factors to be constantly higher supported by the best cluster amongst their knn, which regularly interprets into simply being nearer to the to-be-reassigned level, even when simply by some infinitesimal quantity.
   1. Seeing it one other means, this section actually acts virtually like a resumed growth section in a unique, less-connection-greedy mode. The primary section finds the anchors with excessive shape-adaptivity, and the second section propagates them outward to better-defined stopping factors that the primary section wouldn’t have been capable of finding alone.
4. There are some particulars omitted for brevity, however that’s the core of it.