# Monte-Carlo algorithm for clustering

I have written an algorithm for clustering data-points with their nearest neighbours with a Euclidean distance metric. I estimate its complexity to be $\mathcal{O}(n \times k)$ for $n$ data-points with $k$ genuine clusters. The dimension $d$ of the data results in $\mathcal{O}(e^d)$ complexity, though I believe this can be mitigated.

The algorithm is Monte-Carlo, resulting in an approximate solution. In pseudo-code, for data transformed to a unit hypercube:

radius = 0.15 # This should be fine-tuned for problem.
mode_number = 0 # Label for mode currently being investigated.

while length(data) > 0:

mode_number += 1
branching = True
point = data[0] # i.e. first data point.

while branching:
within_radius = [] # Make this list empty.
for item in data:
within_radius += point # List of points within a sphere.

branching = False
continue

point = Pick_Random_From(within_radius) # Next point.
data = data.Remove_From_Data(within_radius) # Remove neighbouring points from data.


Although the for item in data loop contributes a complexity $\times$ length(data) each pass, length(data) shrinks rapidly, resulting in only $\times n$ complexity. In fact, the length(data) shrinks linearly with iteration (with a saw-tooth behaviour), e.g.

where branch is incremented every time while branching is passed, and number of deleted is the number of points removed at that pass of while branching. That result is from 3 Gaussians with 1000 points sampled from each Gaussian. My code identified six modes:

Modes: 6
Mode 5 , points: 1000
Mode 3 , points: 932
Mode 0 , points: 829
Mode 1 , points: 168
Mode 4 , points: 68
Mode 2 , points: 2


though only three substantial, which wasn't too far off.

The algorithm starts at a point, finds its nearby neighbours, and deletes them from the data list, and repeats from a point within those nearest neighbours. If a point has no nearby neighbours, it begins a new mode. If the data-points are spread in many modes, the algorithm requires more iterations to clear all the modes, resulting in $\times k$ complexity.

The dimension of the data limits performance. In higher dimensions of space, points are more "spread-out", e.g. a sphere radius $r$ takes up an $(r/R)^d$ fraction of the space, which shrinks exponentially with increasing $d$. This, I think, could be mitigated somewhat by increasing radius = 0.15 in my algorithm. This is justifiable - with larger $d$, more of the space in a unit hypercube is "around the edges".

So overall I estimate complexity: $\mathcal{O}(n\times k\times e^d)$. Is my analysis reasonable? Is the working of the algorithm clear?

As far as running time, it will depend upon the distribution of the input points. If the input points are distributed uniformly across the input space, then I would expect that each iteration of the inner loop will remove roughly a $0.15^d$ fraction of the input points. This suggests that you'll need to do about $1/0.15^d \approx 2^{2.7 d}$ iterations. Each iteration takes about $O(n)$ distance computations, and each distance computation takes $O(d)$ steps, so I'd expect the running time to be something like $O(n d 2^{2.7d})$. That's dominated by the exponential factor, so the worst-case running time estimate is very bad, in high dimensions (e.g., $d \approx 100$). Welcome to the curse of dimensionality.