Berechnung von Jaccard oder einem anderen Assoziationskoeffizienten für Binärdaten unter Verwendung der Matrixmultiplikation

9

Ich möchte wissen, ob es eine Möglichkeit gibt, den Jaccard-Koeffizienten mithilfe der Matrixmultiplikation zu berechnen.

Ich habe diesen Code verwendet

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

Dies ist in R. in Ordnung zu implementieren. Ich habe die Würfelähnlichkeit eins gemacht, bin aber bei Tanimoto / Jaccard hängen geblieben. Kann jemand helfen?

user4959
quelle
Sieht so aus, als hätte @ttnphns dies behandelt, aber da Sie R verwenden, dachte ich, ich würde auch darauf hinweisen, dass eine Reihe von Ähnlichkeitsindizes (einschließlich Jaccards) bereits im veganPaket implementiert sind . Ich denke, sie sind auch ziemlich schnell optimiert.
David J. Harris

Antworten:

11

Wir wissen , dass Jaccard (berechnet zwischen zwei beliebigen Spalten von binären Daten ) ist eineX. , während Rogers-Tanimotoa+d isteinein+b+c , wobeiein+dein+d+2(b+c)

  • a - Anzahl der Zeilen, in denen beide Spalten 1 sind
  • b - Anzahl der Zeilen, in denen diese und nicht die andere Spalte 1 ist
  • c - Anzahl der Zeilen, in denen die andere und nicht diese Spalte 1 ist
  • d - Anzahl der Zeilen, in denen beide Spalten 0 sind

, die Anzahl der Zeilen in X.ein+b+c+d=nX.

Dann haben wir:

ist die quadratische symmetrische Matrix von a zwischen allen Spalten.X.'X.=EINein

sind die quadratische symmetrische Matrix von d zwischen allen Spalten ( "not X" konvertiert 1-> 0 und 0-> 1 in X).(nÖtX.)'(nÖtX.)=D.d

Also, ist die quadratische symmetrische Matrix von Jaccard zwischen allen Spalten.EINn- -D.

ist die quadratische symmetrische Matrix von Rogers-Tanimoto zwischen allen Spalten.EIN+D.EIN+D.+2(n- -(EIN+D.))=EIN+D.2n- -EIN- -D.

Ich habe numerisch geprüft, ob diese Formeln das richtige Ergebnis liefern. Tun sie.


Upd. Sie können auch die Matrizen und C erhalten :B.C.

, wobei "[1]" eine Matrix von Einsen mit der Größe X bezeichnet . B ist die quadratische asymmetrische Matrix von b zwischen allen Spalten; sein Elementijist die Anzahl der Zeilen in X mit 0 in Spalteiund 1 in Spaltej.B.=[1]]'X.- -EINX.B.bX.

Folglich ist .C.=B.'

Matrix kann auch auf diese Weise berechnet werden, natürlich: n - A - B - C .D.n- -EIN- -B.- -C.

Wenn Sie die Matrizen , können Sie eine Matrix eines beliebigen paarweisen (Dis-) Ähnlichkeitskoeffizienten berechnen, der für Binärdaten erfunden wurde.EIN,B.,C.,D.

ttnphns
quelle
Brüche sind für Matrizen nur dann sinnvoll, wenn sie pendeln: Wenn Sie rechts mit einer Inversen multiplizieren, erhalten Sie ansonsten ein anderes Ergebnis als wenn Sie links multiplizieren. Darüber hinaus ist es normalerweise nicht der Fall, dass ein Produkt aus zwei symmetrischen Matrizen symmetrisch ist. Meinen Sie vielleicht die Aufteilung nach Komponenten? Könnten Sie Ihre Notation so korrigieren, dass sie die richtige Formel widerspiegelt?
whuber
@whuber Ich verwende weder Inversion noch Multiplikation von quadratischen symmetrischen Matrizen. X ist die binäre Datenmatrix und X'X ist ihre SSCP-Matrix. not Xist X, wobei 1-> 0, 0-> 1. Und jede Teilung hier ist elementweise Teilung. Bitte korrigieren Sie meine Notation, wenn Sie sehen, dass sie nicht angemessen ist.
ttnphns
Wie berechnet man das innere Produkt (notX) '(notX) in R?
user4959
@ user4959, ich kenne R. Hier nicht ! X wird empfohlen; Das Ergebnis ist jedoch boolean TRUE / FALSE, nicht numerisch 1/0. Beachten Sie, dass ich meine Antwort aktualisiert habe, in der ich sage, dass es auch einen anderen Weg gibt, um zur D-Matrix zu gelangen.
ttnphns
9

Die obige Lösung ist nicht sehr gut, wenn X dünn ist. Weil das Nehmen von! X eine dichte Matrix ergibt, die viel Speicher und Rechenaufwand beansprucht.

Eine bessere Lösung ist die Verwendung der Formel Jaccard [i, j] = #common / (#i + #j - #common) . Mit spärlichen Matrizen können Sie dies wie folgt tun (beachten Sie, dass der Code auch für nicht spärliche Matrizen funktioniert):

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 )
}
user41844
quelle
1

Dies kann für Sie nützlich sein oder auch nicht, je nachdem, welche Anforderungen Sie haben. Angenommen, Sie interessieren sich für die Ähnlichkeit zwischen Clustering-Zuweisungen:

Der Jaccard-Ähnlichkeitskoeffizient oder Jaccard-Index kann verwendet werden, um die Ähnlichkeit von zwei Clusterzuordnungen zu berechnen.

Angesichts der Markierungen L1und L2haben Ben-Hur, Elisseeff und Guyon (2002) gezeigt, dass der Jaccard-Index unter Verwendung von Punktprodukten einer Zwischenmatrix berechnet werden kann. Der folgende Code nutzt dies, um den Jaccard-Index schnell zu berechnen, ohne die Zwischenmatrizen im Speicher speichern zu müssen.

Der Code ist in C ++ geschrieben, kann aber mit dem sourceCppBefehl in R geladen werden .

/**
 * 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
quelle