Obliczanie indeksu Rand

Próbuję wymyślić, jak obliczyć Indeks Rand algorytmu klastra, ale utknąłem w punkcie, w jaki sposób obliczyć prawdziwe i fałszywe negatywy.

W tej chwili korzystam z przykładu z książki An Introduction to Information Retrieval (Manning, Raghavan & Schütze, 2009). Na stronie 359 mówią o tym, jak obliczyć indeks Rand. W tym przykładzie używają trzech klastrów, a klastry zawierają następujące obiekty.

1. aaaaab
2. abbbbc
3. aaccc

Zamieniam przedmiot (oryginalne znaki na litery, ale idea i liczba pozostają takie same). Podam dokładne słowa z książki, aby zobaczyć, o czym mówią:

Najpierw obliczamy TP + FP. Trzy klastry zawierają odpowiednio 6, 6 i 5 punktów, więc łączna liczba „pozytywów” lub par dokumentów znajdujących się w tym samym klastrze wynosi:

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

Spośród nich pary w grupie 1, pary b w grupie 2, pary c w grupie 3 i para w grupie 3 są prawdziwie pozytywne:

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

Zatem FP = 40-20 = 20.

Do tego czasu obliczenia są jasne, a jeśli wezmę inne przykłady, otrzymam te same wyniki, ale kiedy chcę obliczyć fałszywie ujemny i prawdziwie negatywny Manning i in. podać następujące informacje:

FN i TN są obliczane podobnie, co daje następującą tabelę zdarzeń:

Tabela awaryjna wygląda następująco:

+--------+--------+
| TP: 20 | FN: 24 |
+--------+--------+
| FP: 20 | TN: 72 |
+--------+--------+

Zdanie: „FN i TN są obliczane podobnie” nie jest dla mnie jasne i nie rozumiem, które liczby potrzebuję do obliczenia TN i FN. Mogę obliczyć prawą stronę tabeli, wykonując następujące czynności:

TP + FP + FN + TN = = = 136${n \choose 2}$${17 \choose 2}$

Źródło: http://en.wikipedia.org/wiki/Rand_index

Zatem FN + TN = 136 - TP + FP = 136 - 40 = 96, ale tak naprawdę nie pomaga mi to w samodzielnym obliczeniu sposobu obliczania zmiennych. Zwłaszcza gdy autorzy mówią: „FN i TN są obliczane podobnie”. Nie rozumiem jak. Również gdy patrzę na inne przykłady, obliczają każdą komórkę tabeli awaryjnej, patrząc na każdą parę.

Na przykład: http://www.otlet-institute.org/wikics/Clustering_Problems.html#toc-Subsection-4.1

Moje pierwsze pytanie, oparte na przykładzie Manninga i in. (2009), czy można obliczyć TN i FN, jeśli znasz tylko TP i NP? A jeśli tak, to jak wygląda podobne obliczenie na podstawie podanego przykładu?

Zastanawiałem się nad tym samym i tak rozwiązałem. Załóżmy, że masz macierz współbieżności / tabelę zdarzeń, w której rzędy są klastrami bazowymi, a kolumny są klastrami znalezionymi przez algorytm klastrowania.

Na przykład w książce wyglądałoby to tak:

  | 1 | 2 | 3
--+---+---+---
x | 5 | 1 | 2
--+---+---+---
o | 1 | 4 | 0
--+---+---+---
◊ | 0 | 1 | 3

Teraz możesz bardzo łatwo obliczyć TP + FP, biorąc sumę na kolumnę i „wybierz 2” spośród wszystkich tych wartości. Tak więc sumy wynoszą [6, 6, 5] i robisz „6 wybierz 2” + „6 wybierz 2” + „5 wybierz 2”.

Teraz podobnie można uzyskać TP + FN, biorąc sumę nad wierszami (czyli [8, 5, 4] w powyższym przykładzie), zastosuj „wybierz 2” dla wszystkich tych wartości i weź suma tego.

Same TP można obliczyć, stosując „wybierz 2” do każdej komórki w macierzy i biorąc sumę wszystkiego (zakładając, że „1 wybierz 2” to 0).

W rzeczywistości oto kod Pythona, który robi dokładnie to:

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

Jeśli go uruchomię, otrzymuję:

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

Właściwie nie sprawdziłem żadnych innych przykładów niż ten, więc mam nadzieję, że zrobiłem to dobrze .... ;-)

Po przestudiowaniu innych odpowiedzi w tym wątku, oto moja implementacja Python, która przyjmuje tablice jako dane wejściowe, 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

Sam nie jestem do końca pewien, ale tak zrobiłem wartość
TN : TN = (7 2) (10 2) (4 2)

(7 2) - Klaster 1 - test mówi „x”, więc policz te, które NIE są x (i są poprawnie połączone w klastry 2 i 3)

tj. 4 'o + 3' d (diamenty) = (7 2)

(10 2) - Klastra 2, policz te, które NIE są „o” i poprawnie zgrupowane w klastrach 1 i 3,

tj. 5 'x' + (2'x '+ 3'd') = (10 2)

(4 2) - Klaster 3, policz te, które NIE są „x” i NIE „d” (element w kształcie rombu), które są poprawnie zgrupowane w klastrze 1 i 2.

tj. 4 'o w klastrze 2. = (4 2)

TN = (7 2) + (10 2) + (4 2) = 72.

Zatem FN to:

FN = (17 2) - (TP + FP) - TN = 136 - 40-72 = 24. ---> (17 = całkowita liczba dokumentów)

Biorąc przykład z innego pytania:

  | 1 | 2 | 3
--+---+---+---
x | 5 | 1 | 2
--+---+---+---
o | 1 | 4 | 0
--+---+---+---
◊ | 0 | 1 | 3

Rozsądna odpowiedź dla FN:

FN = (c(8,2)-c(5,2)-c(2,2))+(c(5,2)-c(4,2))+(c(4,2)-c(3,2))=24  

Wyjaśnienie:

• (c (8,2) -c (5,2) -c (2,2))

  wybierz 2 z 8 dla „x” (a) kombinację tej samej klasy w tych samych klastrach (c (5,2) dla klastra 1 i c (2,2) dla klastra 3),

• (c (5,2) -c (4,2))

  wybierz 2 z 5 'o' (b) minus kombinacja tej samej klasy w tych samych klastrach (c (4,2) dla klastra 2)

• (c (4,2) -c (3,2)

  wybierz 2 z 4 dla „◇” (c) minus kombinacja tej samej klasy w tych samych klastrach (c (3,2) dla klastra 3)

Wyprowadziłem to w ten sposób.

Mam implementację tego w języku R, który wyjaśnię:

TP (a w kodzie) to suma każdej wybranej komórki 2. 2. Zgodnie z pierwotnym pytaniem (0 lub 1 wybierz 2 równe 0)

FN (b) to suma każdego wiersza, wybierz 2, wszystkie zsumowane, pomniejszone o TP. Gdzie każda suma wiersza reprezentuje liczbę dokumentów w każdej klasie True.

Suma tego to wszystkie dokumenty, które są podobne i znajdują się w tym samym klastrze (TP) oraz wszystkie dokumenty, które są podobne i nie znajdują się w tym samym klastrze (FN).

To jest (TP + FN) - TP = FN

FP (c) oblicza się podobnie. Suma każdej kolumny wybiera 2, wszystkie zsumowane, minus TP. W tym przypadku każda suma kolumn reprezentuje liczbę dokumentów w każdym klastrze.

Tak więc sumą tego są wszystkie dokumenty, które są podobne i znajdują się w tym samym klastrze (TP) plus wszystkie dokumenty, które nie są podobne i znajdują się w tym samym klastrze (FP).

To jest (TP + FP) - TP = FP

Po obliczeniu tych 3 pozostałych obliczeń TN jest proste. Suma tabeli wybiera 2, mniej TP, FP i FN = TN (d)

Jedyne zapytanie, jakie mam przy użyciu tej metody, to definicja TP. Używając terminologii w tym pytaniu, nie rozumiem, dlaczego 2a w klastrze 3 są uważane za TP. Znalazłem to zarówno tutaj, jak i w powiązanym podręczniku. Jednak rozumiem ich obliczenia przy założeniu, że ich obliczenia TP są prawidłowe.

Mam nadzieję że to pomoże

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)
}

Możesz obliczyć TN i FN w ten sam sposób.

Po prostu zmień role etykiet i klastrów .

a) 1 1 1 1 1 2 3 3
b) 1 2 2 2 2
c) 2 3 3 3 3

... następnie wykonaj te same obliczenia.

MYŚLĘ, że stworzyłem z niego fałszywie negatywny (FN). Dla prawdziwych pozytywów stworzyłeś 4 grupy, które były pozytywne. W grupie 1 miałeś pięć a; w grupie 2 miałeś 4 b; w grupie 3 miałeś 3 c ORAZ 2 a.

Tak dla fałszywie negatywnego.

1. Zacznij od a w klastrze 1; 5 jest poprawnie umieszczonych a w klastrze 1. Masz 1 fałsz a w klastrze 2 i dwa fałszywe a w klastrze 3. To daje (5 1) i (5 2).
2. Następnie dla b. Są 4 poprawnie umieszczone b, które obliczyłeś wcześniej. Masz jedno fałszywe b w grupie 1 i to wszystko. To daje (4 1) za b.
3. Następnie dla c's. Masz jedno fałszywe cw grupie 2, a trzy prawidłowe w grupie 3, więc jest (3 1).
4. Po tym nie możemy zapomnieć o tej parze a w klastrze 3, którą nazwaliśmy prawdziwym pozytywem. W związku z tym mamy 1 fałszywy a w grupie 2. Nawet jeśli w grupie 1 są inne a, nie możemy nazwać ich fałszywymi a, ponieważ jest ich tak wiele.

Dlatego masz (5 1) + (5 2) + (4 1) + (3 1) + (2 1), co równa się 5 + 10 + 4 + 3 + 2 = 24. Stąd pochodzi 24, a następnie po prostu odejmij to od 136, które już znalazłeś, aby uzyskać prawdziwy neg (TN).

Oto jak obliczyć każdą metrykę dla indeksu Rand bez odejmowania

Dodatkowe informacje dla łatwiejszego zrozumienia:

1) Indeks Rand opiera się na porównaniu par elementów. Teoria sugeruje, że podobne pary elementów powinny być umieszczone w tym samym klastrze, natomiast różne pary elementów powinny być umieszczone w osobnych klastrach.

2) RI nie dba o różnicę w liczbie klastrów. Troszczy się tylko o prawdziwe / fałszywe pary elementów.

Na podstawie tego założenia obliczany jest Indeks Rand

Ok, zanurzmy się tutaj jest nasz przykład:

  | 1 | 2 | 3
--+---+---+---
x | 5 | 1 | 2
--+---+---+---
o | 1 | 4 | 0
--+---+---+---
◊ | 0 | 1 | 3

W mianowniku mamy całkowitą liczbę możliwych par, czyli (17 2) = 136

Teraz obliczmy każdą metrykę dla lepszego zrozumienia:

A) Zacznijmy od łatwego a ( Prawdziwe pozytywne lub popraw podobne )

Oznacza to, że musisz znaleźć wszystkie możliwe pary elementów, w których predykcja i prawdziwa etykieta zostały umieszczone razem. Na przykładzie siatki oznacza uzyskanie sumy możliwych par w każdej komórce.

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) Teraz zróbmy c ( Fałszywe pozytywy lub niepoprawne odmienne )

Oznacza to, znajdź wszystkie pary, które umieściliśmy razem, ale które powinny znajdować się w różnych grupach. Na przykładzie siatki oznacza to znalezienie wszystkich możliwych par między dowolnymi 2 poziomymi komórkami

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) Obliczanie d ( False Negative lub niepoprawne podobne ) Oznacza to, znajdź wszystkie pary, które umieściliśmy w różnych grupach, ale które powinny być razem. Na przykładzie siatki znajdź wszystkie możliwe pary między dowolnymi 2 komórkami pionowymi

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) I wreszcie zróbmy b ( True Negative lub popraw niepodobne )

Oznacza to, znajdź wszystkie pary, które umieściliśmy w różnych klastrach, które również powinny znajdować się w różnych klastrach. Na siatce oznacza to znalezienie wszystkich możliwych par między dowolnymi 2 niepionowymi i nie poziomymi komórkami

Oto, które liczby należy pomnożyć, aby lepiej zrozumieć, co miałem na myśli:

d = 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

W liczbach:

d = 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

I na koniec Rand Index jest równy: (20 + 72) / 136 = 0.676

Poniżej znajduje się zdjęcie, które opisuje twoje pytanie:

Aby rozwiązać ten problem, musisz wziąć pod uwagę tę macierz:

+--------------------------------+--------------------------------------+
| TP:                            | FN:                                  |
| Same class + same cluster      | Same class + different clusters      |
+--------------------------------+--------------------------------------+
| FP:                            | TN:                                  |
| different class + same cluster | different class + different clusters |
+--------------------------------+--------------------------------------+

W ten sposób obliczamy TP, FN, FP dla indeksu Rand:

UWAGA: W powyższych równaniach użyłem trójkąta, aby pokazać diament na zdjęciu.

Na przykład dla False Negative powinniśmy wybierać z klasy, ale w różnych klastrach. Więc możemy wybrać

• ${5 \choose 1}{1 \choose 1} = 5$
• ${5 \choose 1}{2 \choose 1} = 10$
• ${1 \choose 1}{4 \choose 1} = 4$
• ${1 \choose 1}{2 \choose 1} = 2$
• $\diamond$$\diamond$${1 \choose 1}{3 \choose 1} = 3$

$24$$=5+10+4+2+3$

To samo dotyczy pozostałych równań.

Najtrudniejszą częścią jest TN, którą można wykonać jak na poniższym obrazku:

Istnieje kilka krótszych ścieżek do obliczania Indeksu Rand, ale jest to obliczenie głębokie i krok po kroku. Wreszcie tabela kontyngentów wygląda następująco:

+--------+--------+
| TP: 20 | FN: 24 |
+--------+--------+
| FP: 20 | TN: 72 |
+--------+--------+