# Is an $\mathcal{O}(n\times \text{Number of clusters})$ clustering algorithm useful?

I am a physicist, with little formal training in computer science - please don't assume I know even obvious things about computer science!

Within the context of data analysis, I was interested in identifying clusters within a $d$-dimensional list of $n$ data-points, for which the dimensionality $d$ could be $\sim100$, whilst the number of data-points could be $\sim 1,000,000$, or perhaps more.

I wanted the points with a cluster to be close together, with distance measured in the Euclidean manner, $$d(\vec x,\vec y) = \sqrt{\sum_{i=1}^d (x_i - y_i)^2}$$ As long as the clustering was reasonably accurate, I wasn't bothered if the exactly correct result was obtained. i.e. if of my $\sim1,000,000$, $\sim1,000$ points were wrongly categorized, it wouldn't matter much.

I have written a short algorithm that can perform typically at $\mathcal{O}(n)$ (from trials of up to $n\sim5,000,000$ and some theoretical analysis) and worst-case $\mathcal{O}(n^2)$ (from my theoretical evaluation of the algorithm). The nature of the algorithm sometimes (but not always) avoids the so-called chaining problem in clustering, where dissimilar clusters are chained together because they have a few data-points that are close.

The complexity is, however, sensitive to the a priori unknown number of clusters in the data-set. The typical complexity is, in fact, $\mathcal{O}(n\times c)$, with $c$ the number of clusters.

Is that better than currently published algorithms? I know naively it is a $\mathcal{O}(n^3)$ problem. I have read of SLINK, that optimizes the complexitiy to $\mathcal{O}(n^2)$. If so, is my algorithm useful? Or do the major uses of clustering algorithms require exact solutions?

In real applications is $c\propto n$?, such that my algorithm has no advantage. My naive feeling is that for real problems, the number of "interesting" clusters (i.e. not including noise) is a property of the physical system/situation being investigated, and is in fact a constant, with no significant dependence on $n$, in which case my algorithm looks useful.

• Welcome to Computer Science! a) I don't think $O(100)$ means what you think it means; check here. b) Without seeing your algorithm, we can't give any feedback. c) There are lots of algorithms on cluster analysis. Afaik, the general problem is NP-hard so it's unlikely that your algorithm solves the general problem. Which "clustering metric" do you try to minimise? – Raphael Dec 2 '13 at 12:19
• @Raphael OP specifies that the metric is euclidean. I believe it is solvable in time $O(n^3)$. – Pål GD Dec 2 '13 at 13:13
• @Raphael ah yes, in some places I mean $\mathcal{O}(100)$ to mean of order/roughly 100, whereas in other cases I mean $\mathcal{O}(n)$ complexity class. How can one demonstrate the success of his algorithm without revealing it!? – innisfree Dec 2 '13 at 13:51
• @innisfree: Not at all. As a physicist, you should understand what reproducability and falsifiability mean. – Raphael Dec 2 '13 at 18:44
• @Raphael why would that imply that the algorithm must be visible? Couldn't one attempt to falsfy/replicate my claim from a "black box" of my algorithm? I guess difficult to judge complexity with a black box. I do see I lack credibility... Maybe I will post it! – innisfree Dec 2 '13 at 18:58

To answer your last question: In real problems, the number of clusters $c$ is usually much less than $n$.
To compare to other algorithms, the running time of a naive implementation of the standard $k$-means algorithm is $O(ncdt)$ (here your $c$ is often called $k$, so $c=k$, and $t$ is the number of iterations needed for $k$-means to converge; $t$ is often much smaller than $n$ and roughly a small constant, but certainly not always). There are ways to speed it up further. It tends to be very fast in practice.
• @innisfree, I'm afraid I have no idea. In general, even defining "better" is non-trivial; running time is one way to compare, but the quality of the clustering produced by two algorithms is non-trivial to quantify or compare. I suggest you do some research to learn about the state of the art in clustering, before asking more questions. If you aren't familiar with the $k$-means algorithm, you haven't done enough research on your own, since $k$-means is one of the most well-known clustering algorithms and one of the first few algorithms you'll run into when you start studying this topic. – D.W. Dec 6 '13 at 1:11