# confusion matrix and Jaccard index computation in O(n) for cluster comparison

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

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)$.
• 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? Jan 23 '16 at 10:31
• 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. Jan 23 '16 at 17:29
• 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. Jan 23 '16 at 18:02