19
$\begingroup$

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.

  1. a a a a a b
  2. a b b b b c
  3. 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?

$\endgroup$
0

10 Answers 10

11
$\begingroup$

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.... ;-)

$\endgroup$
4
  • $\begingroup$ ty for answer but you dont explain. you say both times column based. can you update your answer and include FN + TN like you did FP + TP $\endgroup$ Commented Sep 4, 2015 at 20:41
  • $\begingroup$ I didn't understand why for TP '2 choose 2' is considered. Doesn't it mean that x is incorrectly classified as ◊? $\endgroup$
    – vcosk
    Commented Nov 5, 2015 at 23:27
  • $\begingroup$ dont you mean "sum over the rows" for TP + FN ? $\endgroup$
    – zython
    Commented Jan 26, 2019 at 16:06
  • $\begingroup$ I am sorry, yes you're right. Fixed it in the answer. $\endgroup$
    – Tom
    Commented Jan 27, 2019 at 17:18
7
$\begingroup$

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
$\endgroup$
4
$\begingroup$

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)

$\endgroup$
3
  • $\begingroup$ This is the answer that makes the most sense to me, although it doesn't really show how "FN and TN are computed similarly", as the book says and the question refers to. I suspect there might be a simpler way, as perhaps the answer mentioning the clusters/classes switching strategy hints at. $\endgroup$
    – cjauvin
    Commented Jun 16, 2015 at 22:34
  • $\begingroup$ This is wrong, this description doesn't work in other examples. Give my upvote back ! Correct answer is @user9668 's. $\endgroup$
    – Özgür
    Commented Dec 11, 2015 at 20:00
  • $\begingroup$ This answer actually makes perfect sense. $\endgroup$
    – EhsanF
    Commented Jul 6, 2017 at 14:35
2
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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)
}
$\endgroup$
3
  • $\begingroup$ This is so vogue , what do you mean by dell, row, column? $\endgroup$
    – Özgür
    Commented Dec 11, 2015 at 19:45
  • $\begingroup$ I'm not sure why you're describing the Rand Statistic as vogue? Cell, row and columns refer to the cells rows & columns of the confusion matrix. As per the OP's question. $\endgroup$ Commented Dec 12, 2015 at 2:09
  • $\begingroup$ Well, because there isn't a confusion matrix in the original question? and you nowhere stated that it is the confusion matrix. It is in the first answer above and once used, yes your method seems to be working. $\endgroup$
    – Özgür
    Commented Dec 12, 2015 at 6:51
1
$\begingroup$

Below is the picture which describes your question:

Rand-Index-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:

TP, FN, and FP calculation 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:

TN calculation for Rand Index

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 |
+--------+--------+
$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Can you be more explicit? Also, you've got one extra 3 in your list (c) I believe, as there should be 17 items. $\endgroup$
    – cjauvin
    Commented Jun 16, 2015 at 22:29
  • $\begingroup$ very unclear answer $\endgroup$ Commented Sep 4, 2015 at 20:43
0
$\begingroup$

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.

  1. 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).
  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.
  3. 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).
  4. 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).

$\endgroup$
0
$\begingroup$

Here is how to calculate every metric for Rand Index without subtracting

Side notes for easier understanding:

  1. 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.

  2. 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

enter image description here

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

$\endgroup$
0
$\begingroup$

A deliberately step-by-step answer that follows, however, the principle laid out by user @Hadij above and is implemented here in Python, could be as shown below.

Of course, this is meant as a didactical implementation that may help to understand the logic of the Rand Index, not as an efficient or succinct implementation.

# Make necessary imports 
from itertools import combinations

# Define the clusters, as in the book, using a "d" for diamonds. 
# Here, this is done using a dict.
clusters = {
    "c1" : ["x", "x", "x", "x", "x", "o"],
    "c2" : ["x", "o", "o", "o", "o", "d"],
    "c3" : ["x", "x", "d", "d", "d"],          
    }

# For each item, create tuples of item and cluster assignment. 
allitems = []
for cluster,items in clusters.items(): 
    allitems.extend([(item, cluster) for item in items])
print(allitems)

# For each item + cluster assignment tuple, get all its combinations. 
combs_with_cluster = list([i for i in combinations(allitems, 2)])
print(combs_with_cluster)

# Initialize TP, TN, FP, FN with zeroes. 
TP, TN, FP, FN = [0,0,0,0]

# Check agreement between item labels and cluster assignments. 
# For each combination, compare:
# - the two items' labels ([0][0] to [1][0]) 
# - the two items' cluster assignments ([0][1] to [1][1])
# Increment TP, TN, FP, FN depending on the result. 
for item in combs_with_cluster: 
    # identical items AND identical clusters => true positive
    if item[0][0] == item[1][0] and item[0][1] == item[1][1]: 
        TP +=1
    # identical items BUT different clusters => true negative
    if item[0][0] != item[1][0] and item[0][1] != item[1][1]: 
        TN +=1
    # different items BUT same clusters => false positive
    if item[0][0] != item[1][0] and item[0][1] == item[1][1]: 
        FP +=1
    # different item AND different clusters => false negative
    if item[0][0] == item[1][0] and item[0][1] != item[1][1]: 
        FN +=1
    print(TP, TN, FP, FN)
    
# Based on these, calculate the Rand Index RI
RI = (TP+TN) / (TP+TN+FP+FN)
print(np.round(RI,3))
    
# Based on the same, calculate F1-Score (P=precision, R=recall)
P = TP / (TP+FP)
R = TP / (TP+FN)
F1Score = (2*P*R) / (P+R)
print(np.round(F1Score,3))

This yields the values for TP, TN, FP, FN in the confusion matrix from the book on page 331 (TP=20, TN=72, FP=20, FN=24) as well as the resulting values for RI (0.676) and F1-Score (0.476).

$\endgroup$

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