Monte-Carlo algorithm for clustering

Question

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?

Answer 1

I suspect this clustering algorithm is going to give a poor quality clustering. The cluster heads are chosen just about arbitrarily (randomly, essentially) and then points are assigned to a cluster if they are near a cluster head or near some other randomly chosen points in the cluster. The whole algorithm looks unprincipled and I have serious doubts about the quality of the clustering it will produce.

Of course, if the clustering is of low quality, then it just doesn't matter what the running time is. I can suggest an extremely fast algorithm if you don't care about the quality of its output....

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.

This algorithm does not look promising to me. Of course, before drawing any serious conclusions, you'd need to do a serious evaluation of both its running time and the quality of its clustering, on relevant input distributions, as compared to other standard clustering algorithms. So, if you want to seriously pursue this direction, you need to start studying the state of the art and work on performing such a careful evaluation. But personally, I think your time would be better spent by starting to look at what's available in the literature and seeing if you can make any standard algorithm work for your application.