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:
if Euclidean_Distance(item,point) < radius:
within_radius += point # List of points within a sphere.
if length(within_radius) == 0:
branching = False
continue
point = Pick_Random_From(within_radius) # Next point.
data = data.Remove_From_Data(within_radius) # Remove neighbouring points from data.
mode[mode_number] += within_radius # Add points to mode.
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?