ARD KMeans++

ARD-KMeans++ (Adaptive Radius Density K-Means++) is an experimental centroid-initialization strategy. I extend K-Means++ by refining each distance-selected candidate with local density analysis before finalizing its position.

Rather than accepting a raw farthest-point candidate, I relocate it to a nearby dense region using an adaptive radius derived from k-nearest-neighbor distances.

Motivation

K-Means++ improves stability by spreading initial centroids, but it can still select sparse or tail regions when data has uneven density or elongated shapes. I created ARD-KMeans++ to investigate whether local-density information can reduce outlier sensitivity and yield more representative starting centroids.

Design overview

The algorithm first follows standard K-Means++ distance-based selection. For every candidate, it computes an adaptive radius using k-nearest-neighbor distances; points within that radius form a local neighborhood. The densest point in that neighborhood, defined by the highest local neighbor count, becomes the final centroid.

Strengths & limitations

ARD-KMeans++ reduces the chance of initializing in sparse regions and can improve stability for density-imbalanced or long-tail datasets. The density-refinement step adds neighborhood and distance computations, and gains are naturally dependent on the dataset.

Implementation & status

I implemented the full pipeline from scratch in Python: initialization, assignment, centroid updates, convergence checks, benchmarking against standard K-Means++, and visualizations of initialization behavior. Future work includes alternative density definitions, adaptive neighborhoods, and larger-scale datasets.