Obliczanie Jaccarda lub innego współczynnika asocjacji dla danych binarnych przy użyciu mnożenia macierzy

9

Chcę wiedzieć, czy istnieje jakikolwiek sposób obliczenia współczynnika Jaccard przy użyciu mnożenia macierzy.

Użyłem tego kodu

    jaccard_sim <- function(x) {
    # initialize similarity matrix
    m <- matrix(NA, nrow=ncol(x),ncol=ncol(x),dimnames=list(colnames(x),colnames(x)))
    jaccard <- as.data.frame(m)

    for(i in 1:ncol(x)) {
     for(j in i:ncol(x)) {
        jaccard[i,j]= length(which(x[,i] & x[,j])) / length(which(x[,i] | x[,j]))
        jaccard[j,i]=jaccard[i,j]        
       }
     }

Jest to w porządku do zaimplementowania w R. Zrobiłem kostkę podobną, ale utknąłem z Tanimoto / Jaccard. Czy ktoś może pomóc?

użytkownik4959
źródło
Wygląda na to, że @ttnphns ma to ujęte, ale ponieważ używasz R, pomyślałem, że zwrócę również uwagę, że wiele wskaźników podobieństwa (w tym Jaccard) jest już zaimplementowanych w veganpakiecie. Myślę, że są one również dość dobrze zoptymalizowane pod kątem prędkości.
David J. Harris

Odpowiedzi:

11

Wiemy, że Jaccard (obliczony między dowolnymi dwiema kolumnami danych binarnych ) to , podczas gdy Rogers-Tanimoto to , gdzieXaa+b+ca+da+d+2(b+c)

  • a - liczba wierszy, w których obie kolumny to 1
  • b - liczba wierszy, w których ta, a nie druga kolumna, to 1
  • c - liczba wierszy, w których druga, a nie ta kolumna, to 1
  • d - liczba wierszy, w których obie kolumny mają wartość 0

a+b+c+d=n , liczba wierszy wX

Potem będzie:

XX=A jest kwadratem symetryczny matrycy pomiędzy wszystkimi kolumnami.a

(notX)(notX)=D jest kwadratową macierzą symetryczną między wszystkimi kolumnami („nie X” konwertuje 1-> 0 i 0-> 1 w X).d

Tak więc to kwadratowa symetryczna macierz Jaccard między wszystkimi kolumnami.AnD

A+DA+D+2(n(A+D))=A+D2nAD to kwadratowa macierz symetryczna Rogers-Tanimoto między wszystkimi kolumnami.

Sprawdziłem numerycznie, czy te formuły dają poprawny wynik. Oni robią.


Aktualizacja Możesz także uzyskać macierze i :BC

B=[1]XA , gdzie "[1]" oznacza macierz te, ustawione w . jest kwadratową macierzą asymetryczną między wszystkimi kolumnami; jego elementem ij jest liczba wierszy w z 0 w kolumnie i i 1 w kolumnie j .XBbX

W związku z tym .C=B

Macierz można również obliczyć w ten sposób, oczywiście: .DnABC

Znając macierze , jesteś w stanie obliczyć macierz dowolnego (nie) współczynnika podobieństwa wymyślonego dla danych binarnych.A,B,C,D

ttnphns
źródło
Ułamki nie mają sensu dla macierzy, chyba że dojeżdżają do pracy: pomnożenie po prawej stronie przez odwrotność da inny wynik niż mnożenie po lewej stronie. Co więcej, zwykle nie jest tak, że iloczyn dwóch macierzy symetrycznych jest symetryczny. Czy może masz na myśli podział element po elemencie? Czy mógłbyś naprawić swój zapis, aby odzwierciedlał to, co zamierzasz, jest prawidłową formułą?
whuber
@ whuber Nie używam inwersji ani mnożenia kwadratowych macierzy symetrycznych . X jest macierzą danych binarnych, a X'X jest macierzą SSCP. not Xoznacza X, gdzie 1-> 0, 0-> 1. I każdy podział tutaj jest podziałem elementarnym. Proszę poprawić moją notację, jeśli uważasz, że jest nieodpowiednia.
ttnphns
Jak obliczyć iloczyn wewnętrzny (notX) ′ (notX) w R?
user4959
@ user4959, nie wiem R. Tutaj ! X jest zalecane; jednak wynik jest logiczny PRAWDA / FAŁSZ, a nie liczbowy 1/0. Zauważ, że zaktualizowałem swoją odpowiedź tam, gdzie mówię, że istnieje również inny sposób na dojście do macierzy D.
ttnphns
9

Powyższe rozwiązanie nie jest zbyt dobre, jeśli X jest rzadki. Ponieważ wzięcie! X stworzy gęstą matrycę, wymagającą dużej ilości pamięci i obliczeń.

Lepszym rozwiązaniem jest użycie formuły Jaccard [i, j] = #common / (#i + #j - #common) . W przypadku rzadkich macierzy można to zrobić w następujący sposób (zwróć uwagę, że kod działa również w przypadku macierzy nielicznych):

library(Matrix)
jaccard <- function(m) {
    ## common values:
    A = tcrossprod(m)
    ## indexes for non-zero common values
    im = which(A > 0, arr.ind=TRUE)
    ## counts for each row
    b = rowSums(m)

    ## only non-zero values of common
    Aim = A[im]

    ## Jacard formula: #common / (#i + #j - #common)
    J = sparseMatrix(
          i = im[,1],
          j = im[,2],
          x = Aim / (b[im[,1]] + b[im[,2]] - Aim),
          dims = dim(A)
    )

    return( J )
}
użytkownik41844
źródło
1

Może to być przydatne dla Ciebie, w zależności od Twoich potrzeb. Zakładając, że interesuje Cię podobieństwo między zadaniami klastrowania:

Współczynnik podobieństwa Jaccard lub Indeks Jaccard można wykorzystać do obliczenia podobieństwa dwóch przypisań klastrowych.

Biorąc pod uwagę labelings L1i L2, Ben-Hur, Elisseeff i Guyon (2002) wykazały, że indeks jaccarda można obliczyć kropka produkty o pośrednim matrycy. Poniższy kod wykorzystuje to do szybkiego obliczenia Indeksu Jaccard bez konieczności przechowywania macierzy pośrednich w pamięci.

Kod jest napisany w C ++, ale można go załadować do R za pomocą sourceCpppolecenia.

/**
 * The Jaccard Similarity Coefficient or Jaccard Index is used to compare the
 * similarity/diversity of sample sets. It is defined as the size of the
 * intersection of the sets divided by the size of the union of the sets. Here,
 * it is used to determine how similar to clustering assignments are.
 *
 * INPUTS:
 *    L1: A list. Each element of the list is a number indicating the cluster
 *        assignment of that number.
 *    L2: The same as L1. Must be the same length as L1.
 *
 * RETURNS:
 *    The Jaccard Similarity Index
 *
 * SIDE-EFFECTS:
 *    None
 *
 * COMPLEXITY:
 *    Time:  O(K^2+n), where K = number of clusters
 *    Space: O(K^2)
 *
 * SOURCES:
 *    Asa Ben-Hur, Andre Elisseeff, and Isabelle Guyon (2001) A stability based
 *    method for discovering structure in clustered data. Biocomputing 2002: pp.
 *    6-17. 
 */
// [[Rcpp::export]]
NumericVector JaccardIndex(const NumericVector L1, const NumericVector L2){
  int n = L1.size();
  int K = max(L1);

  int overlaps[K][K];
  int cluster_sizes1[K], cluster_sizes2[K];

  for(int i = 0; i < K; i++){    // We can use NumericMatrix (default 0) 
    cluster_sizes1[i] = 0;
    cluster_sizes2[i] = 0;
    for(int j = 0; j < K; j++)
      overlaps[i][j] = 0;
  }

  //O(n) time. O(K^2) space. Determine the size of each cluster as well as the
  //size of the overlaps between the clusters.
  for(int i = 0; i < n; i++){
    cluster_sizes1[(int)L1[i] - 1]++; // -1's account for zero-based indexing
    cluster_sizes2[(int)L2[i] - 1]++;
    overlaps[(int)L1[i] - 1][(int)L2[i] - 1]++;
  }

  // O(K^2) time. O(1) space. Square the overlap values.
  int C1dotC2 = 0;
  for(int j = 0; j < K; j++){
    for(int k = 0; k < K; k++){
      C1dotC2 += pow(overlaps[j][k], 2);
    }
  }

  // O(K) time. O(1) space. Square the cluster sizes
  int C1dotC1 = 0, C2dotC2 = 0;
  for(int i = 0; i < K; i++){
    C1dotC1 += pow(cluster_sizes1[i], 2);
    C2dotC2 += pow(cluster_sizes2[i], 2);
  }

  return NumericVector::create((double)C1dotC2/(double)(C1dotC1+C2dotC2-C1dotC2));
}
Richard
źródło