My problem: I have two clustering (or partitions) of a set of numbers $\{1,...,n\}$, each with $k$ cluster (or subsets), that i have to compare and, to do that, i'd like to try some different indexes like Jaccard, Mirkin and the Variation of Information, so i need to compute a confusion matrix. Given that labels are random in 1,...,k, a naive implementation to compute a confusion matrix like this

enter image description here

would be to compute for every $i,j \in [1,...,k]$ the number of co-clustered pairs of elements, but this algorithm is $O(k^2) $

I've read a few papers where the authors say that confusion matrix can be calculated in $O(n)$. In Integrating Microarray Data by Consensus Clustering, for example, they choose a symmetric difference distance distance that they can compute from $b$ and $c$ values of a cunfusion matrix, values that can be computed in $O(n)$ time. How can they do that ?


Assuming you have $O(1)$ lookups of cluster memberships, you can iterate of all objects, query both cluster memberships, and tabulate this in a $k^2$ matrix (counting the frequency of object being in cluster $i$ resp. $j$). This part is $O(n)$. From this $k\times k$ matrix, you can efficiently compute the $2 \times 2$ "pair confusion" matrix. This part is $O(k^2)$.

The total algorithm thus is $O(n\cdot k^2)$ and if we assume $k^2\ll n$ to be neglibile then we have $O(n)$.

  • $\begingroup$ unfortunately, it's not true in my case that $k^2<<n$, cause i'm solving a vehicle routing problem and for 200 customers i can have 18-20 vehicles (subsets). But, if I keep a co-clustered counter , every time i update a cell during the $O(n)$ phase i update my $co-clustered$ counter (if the cell value is 3, when add an element i have 3 new co-clustred pairs) , so i can avoid the $O(k^2)$ phase. Am i wrong? $\endgroup$
    – jcsun
    Jan 23 '16 at 10:31
  • $\begingroup$ If $n=200$, asymptotic complexity is completely irrelevant. $1000\cdot n > n^2$ if $n=200$! But with $n=200$, anything should be only a few ms. So don't attempt to solve a problem that you do not have. $\endgroup$ Jan 23 '16 at 17:29
  • $\begingroup$ yes, you'right. But i've implemented it in a genetic algorithm where the distance/similarity function is called tens of thousands of times. so computation time actually changes quite a lot! $\endgroup$
    – jcsun
    Jan 23 '16 at 17:38
  • $\begingroup$ Yes, but not the asymptotic runtime. Again, $1000\cdot n > n^2$. A fast quadratic algorithm can outperform a linear algorithm on tiny data sets, in particular when called millions of times. That is why you sort tiny data sets with insertion sort (which is $O(n^2)$) and not heap sort (which is $O(n \log n)$ but has a much larger constant factor). Therefore, benchmark and profile your code. $\endgroup$ Jan 23 '16 at 18:02
  • $\begingroup$ Ok, now i understand! thank you very much for your patience! $\endgroup$
    – jcsun
    Jan 23 '16 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.