Rand index calculation I'm trying to figure out how to calculate the Rand Index of a cluster algorithm, but I'm stuck at the point how to calculate the true and false negatives.
At the moment I'm using the example from the book An Introduction into Information Retrieval (Manning, Raghavan & Schütze, 2009). At page 359 they talk about how to calculate the Rand index. For this example they use three clusters and the clusters contains the following objects.


*

*a a a a a b

*a b b b b c

*a a c c c


I replace the object (orginal signs to letters, but the idea and count stay the same). I'll give the exact words from the book in order to see what they are talking about:

We first compute TP +FP. The three clusters contain 6, 6, and 5 points, respectively, so the total number of “positives” or pairs of documents that are in the same cluster is:

TP + FP = ${6 \choose 2}$ + ${6 \choose 2}$ + ${5 \choose 2}$ = 15 + 15+ 10 = 40

Of these, the a pairs in cluster 1, the b pairs in cluster 2, the c pairs in cluster 3,
  and the a pair in cluster 3 are true positives:

TP = ${5 \choose 2}$ + ${4 \choose 2}$ + ${3 \choose 2}$ + ${2 \choose 2}$ = 10 + 6 + 3 + 1 = 20

Thus, FP = 40 − 20 = 20.

Till here there calculations are clear, and if I take other examples I get the same results, but when I want to calculate the false negative and true negative Manning et al. state the following:

FN and TN are computed similarly, resulting in the following contingency table:

The contingency table looks as follows:
+--------+--------+
| TP: 20 | FN: 24 |
+--------+--------+
| FP: 20 | TN: 72 |
+--------+--------+

The sentence: "FN and TN are computed similarly" is not clear to my and I don't understand which numbers I need to calculate the TN and FN. I can calculate the right side of the table by doing the following:
TP + FP + FN + TN = ${n \choose 2}$ = ${17 \choose 2}$ = 136
Source: http://en.wikipedia.org/wiki/Rand_index
Thus, FN + TN = 136 - TP + FP = 136 - 40 = 96, but this doesn't really help my in figuring out how to calculate the variables separately. Especially when the authors say: "FN and TN are computed similarly". I don't see how. Also when I look at other examples they calculate each cell of the contingency table by looking at each pair.
For example: http://www.otlet-institute.org/wikics/Clustering_Problems.html#toc-Subsection-4.1
My first question, based on the example of Manning et al (2009), is it possible to calculate the TN and FN if you only know the TP & NP? And if so, how does the similar calculation looks like based of the given example?
 A: After having studied the other answers in this thread, here is my Python implementation, which takes arrays as inputs, sklearn-style:
import numpy as np
from scipy.misc import comb

def rand_index_score(clusters, classes):

    tp_plus_fp = comb(np.bincount(clusters), 2).sum()
    tp_plus_fn = comb(np.bincount(classes), 2).sum()
    A = np.c_[(clusters, classes)]
    tp = sum(comb(np.bincount(A[A[:, 0] == i, 1]), 2).sum()
             for i in set(clusters))
    fp = tp_plus_fp - tp
    fn = tp_plus_fn - tp
    tn = comb(len(A), 2) - tp - fp - fn
    return (tp + tn) / (tp + fp + fn + tn)

In [319]: clusters
Out[319]: [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2]

In [320]: classes
Out[320]: [0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 2, 1, 0, 2, 2, 2, 0]

In [321]: rand_index_score(clusters, classes)
Out[321]: 0.67647058823529416

A: I am not quite sure myself, but this is how I did the TN value:
TN=(7  2)  (10  2) (4  2)
(7 2) – Cluster 1 – test says ‘x’, so count those that are NOT x (and are correctly clustered in clusters 2 & 3)    
i.e. 4 ‘o’s  + 3 ‘d’s (diamonds) =(7 2)
(10 2) – Cluster 2, count those that are NOT ‘o’s and correctly clustered in clusters 1 and 3,
i.e. 5 ‘x’ +(2’x’+ 3’d’)  = (10 2)
(4 2) – Cluster 3, count those that are NOT ‘x’ and NOT ‘d’(diamond shaped element)s that are correctly clustered in clusters  1& 2.
i.e. 4 'o's in cluster 2. =(4 2)
TN = (7 2) + (10 2) + (4 2) =72.
Then FN is  :
FN = (17 2) - (TP+FP) - TN  = 136 - 40 -72 = 24.    ---> (17= total number of documents)
A: Taking the example of another question:
  | 1 | 2 | 3
--+---+---+---
x | 5 | 1 | 2
--+---+---+---
o | 1 | 4 | 0
--+---+---+---
◊ | 0 | 1 | 3

The reasonable answer for FN: 
FN = (c(8,2)-c(5,2)-c(2,2))+(c(5,2)-c(4,2))+(c(4,2)-c(3,2))=24  

Explanation:  


*

*(c(8,2)-c(5,2)-c(2,2)) 
choose 2 from 8 for 'x'(a) the combination of same class in same clusters ( c(5,2) for cluster 1 and c(2,2) for cluster 3 ),

*(c(5,2)-c(4,2)) 
choose 2 from 5 'o'(b) minus the combination of same class in same clusters ( c(4,2) for cluster 2 )

*(c(4,2)-c(3,2) 
choose 2 from 4 for '◇'(c) minus the combination of same class in same clusters ( c(3,2) for cluster 3 )
I derived it like this.
A: I was pondering about the same, and I solved it like this. Suppose you have a co-occurrence matrix/contingency table where the rows are the ground truth clusters, and the columns are the clusters found by the clustering algorithm.
So, for the example in the book, it would look like:
  | 1 | 2 | 3
--+---+---+---
x | 5 | 1 | 2
--+---+---+---
o | 1 | 4 | 0
--+---+---+---
◊ | 0 | 1 | 3

Now, you can very easily compute the TP + FP by taking the sum per column and 'choose 2' over all those values. So the sums are [6, 6, 5] and you do '6 choose 2' + '6 choose 2' + '5 choose 2'.
Now, indeed, similarly, you can get TP + FN by taking the sum over the rows (so, that is [8, 5, 4] in the example above), apply 'choose 2' over all those values, and take the sum of that.
The TP's themselves can be calculated by applying 'choose 2' to every cell in the matrix and taking the sum of everything (assuming that '1 choose 2' is 0).
In fact, here is some Python code that does exactly that:
import numpy as np
from scipy.misc import comb

# There is a comb function for Python which does 'n choose k'                                                                                            
# only you can't apply it to an array right away                                                                                                         
# So here we vectorize it...                                                                                                                             
def myComb(a,b):
  return comb(a,b,exact=True)

vComb = np.vectorize(myComb)

def get_tp_fp_tn_fn(cooccurrence_matrix):
  tp_plus_fp = vComb(cooccurrence_matrix.sum(0, dtype=int),2).sum()
  tp_plus_fn = vComb(cooccurrence_matrix.sum(1, dtype=int),2).sum()
  tp = vComb(cooccurrence_matrix.astype(int), 2).sum()
  fp = tp_plus_fp - tp
  fn = tp_plus_fn - tp
  tn = comb(cooccurrence_matrix.sum(), 2) - tp - fp - fn

  return [tp, fp, tn, fn]

if __name__ == "__main__":
  # The co-occurrence matrix from example from                                                                                                           
  # An Introduction into Information Retrieval (Manning, Raghavan & Schutze, 2009)                                                                       
  # also available on:                                                                                                                                   
  # http://nlp.stanford.edu/IR-book/html/htmledition/evaluation-of-clustering-1.html                                                                     
  #                                                                                                                                                      
  cooccurrence_matrix = np.array([[ 5,  1,  2], [ 1,  4,  0], [ 0,  1,  3]])

  # Get the stats                                                                                                                                        
  tp, fp, tn, fn = get_tp_fp_tn_fn(cooccurrence_matrix)

  print "TP: %d, FP: %d, TN: %d, FN: %d" % (tp, fp, tn, fn)

  # Print the measures:                                                                                                                                  
  print "Rand index: %f" % (float(tp + tn) / (tp + fp + fn + tn))

  precision = float(tp) / (tp + fp)
  recall = float(tp) / (tp + fn)

  print "Precision : %f" % precision
  print "Recall    : %f" % recall
  print "F1        : %f" % ((2.0 * precision * recall) / (precision + recall))

If I run it I get:
$ python testCode.py
TP: 20, FP: 20, TN: 72, FN: 24
Rand index: 0.676471
Precision : 0.500000
Recall    : 0.454545
F1        : 0.476190

I actually didn't check any other examples than this one, so I hope I did it right.... ;-)
A: I have an implementation of this in R which I will explain:
TP (a in the code) is the sum of every cell choose 2. As per the original question (0 or 1 choose 2 equating to 0) 
FN (b) is the sum of each row choose 2, all summed, less TP. Where each Row sum represents the number of documents in each True class. 
The sum of this is all documents that are similar and in the same cluster (TP) plus all documents that are similar and are not in the same cluster (FN). 
So this is (TP + FN) - TP = FN 
FP (c) is calculated similarly. The sum of each column choose 2, all summed, less TP. In this case each column sum represents the number of documents in each cluster. 
So the sum of this is all documents that are similar and in the same cluster (TP) plus all documents that are not similar and are in the same cluster (FP). 
So this is (TP + FP) - TP = FP
With these 3 calculated the remaining calculation of TN is straight forward. The sum of the table choose 2, less TP, FP & FN = TN (d)
The only query I have with this method is it's definition of TP. Using the terminology in this question, I don't understand why the 2 a's in cluster 3 are considered TP. I have found this both here and in the related textbook. However I do understand their calculation with the assumption that their TP calculation is correct. 
Hope this helps
FMeasure = function (x, y, beta) 
{
  x <- as.vector(x)
  y <- as.vector(y)
  if (length(x) != length(y)) 
    stop("arguments must be vectors of the same length")
  tab <- table(x, y)
  if (all(dim(tab) == c(1, 1))) 
    return(1)
  a <- sum(choose(tab, 2))
  b <- sum(choose(rowSums(tab), 2)) - a
  c <- sum(choose(colSums(tab), 2)) - a
  d <- choose(sum(tab), 2) - a - b - c
  ## Precision
  P = a / (a + c)
  ## Recall
  R = a / (a + b)
  ##F-Measure
  Fm <- (beta^2 + 1) * P * R / (beta^2*P + R)
  return(Fm)
}

A: Below is the picture which describes your question:

To solve this problem, you need to consider this matrix:
+--------------------------------+--------------------------------------+
| TP:                            | FN:                                  |
| Same class + same cluster      | Same class + different clusters      |
+--------------------------------+--------------------------------------+
| FP:                            | TN:                                  |
| different class + same cluster | different class + different clusters |
+--------------------------------+--------------------------------------+

This is how we calculate TP, FN, FP for Rand Index:

NOTE: In the above equations, I used a triangle to show the diamond in the picture.
For example, for False Negative, we should pick from the class but in different clusters. So, we can pick


*

*1 X from cluster 1 and 1 X from cluster 2 = ${5 \choose 1}{1 \choose 1} = 5$

*1 X from cluster 1 and 1 X from cluster 3 = ${5 \choose 1}{2 \choose 1} = 10$

*1 O from cluster 1 and 1 O from cluster 2 = ${1 \choose 1}{4 \choose 1} = 4$

*1 X from cluster 2 and 1 X from cluster 3 = ${1 \choose 1}{2 \choose 1} = 2$

*1 $\diamond$ from cluster 2 and 1 $\diamond$ from cluster 3 = ${1 \choose 1}{3 \choose 1} = 3$
Finally, we will have $24$ ($=5+10+4+2+3$) states. 
The same is for the rest of the equations. 
The hardest part is TN which can be done like the below picture:

There are some shorter paths to calculate the Rand Index, but it is the calculation in deep and step by step. Finally, The contingency table looks as follows:
+--------+--------+
| TP: 20 | FN: 24 |
+--------+--------+
| FP: 20 | TN: 72 |
+--------+--------+

A: You can compute TN and FN the same way.
Just switch the roles of labels and clusters.
a) 1 1 1 1 1 2 3 3
b) 1 2 2 2 2
c) 2 3 3 3 3

... then perform the same computations.
A: I THINK I've reverse engineered the false negative (FN) out of it. For the true positives, you made 4 groups that were positive. In cluster 1, you had the five a's; in cluster 2, you had the 4 b's; in cluster 3 you had the 3 c's AND the 2 a's. 
So for the false negative. 


*

*Start with the a's in cluster 1; there are 5 correctly placed a's in cluster 1. You have 1 false a in cluster 2, and two false a's in cluster 3. That gives (5 1) and (5 2). 

*Then for the b's. There are 4 correctly placed b's you calculated earlier. You have one false b in cluster 1, and that's it. That gives you (4 1) for the b's. 

*Then for the c's. You have one false c in cluster 2, with three correct ones in cluster 3, so there's (3 1). 

*After that, we can't forget about that pair of a's in cluster 3 that we called a true positive. So with respect to that, we have 1 false a in cluster 2. Even though there are other a's in cluster 1, we can't call them false a's because there are so many. 


Therefore, you have (5 1) + (5 2) + (4 1) + (3 1) + (2 1) which equals 5 + 10 + 4 + 3 + 2 = 24. That's where the 24 comes from, then just subtract that from the 136 you already found to get the true neg (TN).
A: Here is how to calculate every metric for Rand Index without subtracting
Side notes for easier understanding:

*

*Rand Index is based on comparing pairs of elements. Theory suggests, that similar pairs of elements should be placed in the same cluster, while dissimilar pairs of elements should be placed in separate clusters.


*RI doesn't care about difference in number of clusters. It just cares about True/False pairs of elements.
Based on this assumption, Rand Index, is calculated

Ok, let's dive in here is our example:
  | 1 | 2 | 3
--+---+---+---
x | 5 | 1 | 2
--+---+---+---
o | 1 | 4 | 0
--+---+---+---
◊ | 0 | 1 | 3

In denominator, we have total possible pairs, which is (17 2) = 136
Now lets calculate every metric for better understanding:
A) Let's start with easy a, (True Positives or correct similar)
It means, you need to find all possible pairs of elements, where prediction and true label were placed together.
On grid example it means get sum of possible pairs within each cell.
a = (5 2) + (1 2) + (2 2) + (1 2) + (4 2) + (0 2) + (0 2) + (1 2) + (3 2) = 
  = 10 + 0 + 1 + 0 + 6 + 0 + 0 + 0 + 3 = 20

C) Now, let's do c (False Negative or incorrect similar)
It means, find all pairs that we placed in different clusters, but which should be together.
On grid example it means, find all possible pairs between any 2 horizontal cells
c = 5*1 + 5*2 + 1*2 + 
  + 1*4 + 1*0 + 4*0 + 
  + 0*1 + 0*3 + 1*3 = 
  = 5 + 10 + 2 + 4 + 0 + 0 + 0 + 0 + 3 = 24

D) Calculating d ( False Positives or incorrect dissimilar)
It means, find all pairs, that we placed together, but which should be in different clusters.
On grid example, find all possible pairs between any 2 vertical cells
d = 5*1 + 5*0 + 1*0 + 
  + 1*4 + 1*1 + 4*1 + 
  + 2*0 + 2*3 + 0*3 = 
  = 5 + 0 + 0 + 4 + 1 + 4 + 0 + 6 + 0 = 20

B) And, finally let's do b (True Negatives or correct dissimilar)
It means, find all pairs that we placed in different clusters, which also should be in different clusters.
On grid, it means find all possible pairs between any 2 non-vertical and non-horizontal cells
Here is which numbers should be multiplied, to get better understanding what I meant:
b = x1*o2 + x1*o3 + x1*◊2 + x1*◊3 + 
  + x2*o1 + x2*o3 + x2*◊1 + x2*◊3 + 
  + x3*o1 + x3*o2 + x3*◊1 + x3*◊2 + 
  + o1*◊2 + o1*◊3 + 
  + o2*◊1 + o2*◊3 + 
  + o3*◊1 + o3*◊2

In numbers:
b = 5*4 + 5*0 + 5*1 + 5*3 + 
  + 1*1 + 1*0 + 1*0 + 1*3 + 
  + 2*1 + 2*4 + 2*0 + 2*1 + 
  + 1*1 + 1*3 +
  + 4*0 + 4*3 = 72

And at the end Rand Index is equal: (20 + 72) / 136 = 0.676
