Calcul de Jaccard ou d'un autre coefficient d'association pour des données binaires en utilisant la multiplication matricielle

Je veux savoir s'il existe un moyen possible de calculer le coefficient de Jaccard en utilisant la multiplication matricielle.

J'ai utilisé ce code

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

C'est tout à fait correct à implémenter dans R. J'ai fait la similitude des dés, mais je suis resté coincé avec Tanimoto / Jaccard. Quelqu'un peut-il aider?

$\bf{X}$$\frac{a}{a+b+c}$$\frac{a+d}{a+d+2(b+c)}$

• a - nombre de lignes où les deux colonnes sont égales à 1
• b - nombre de lignes où celle-ci et non l'autre colonne est 1
• c - nombre de lignes où l'autre et non cette colonne est 1
• d - nombre de lignes où les deux colonnes sont 0

$a+b+c+d=n$$\bf{X}$

Ensuite nous avons:

$\bf X'X=A$$a$

$\bf (not X)'(not X)=D$$d$

$\frac{\bf A}{n-\bf D}$

$\frac{\bf A+D}{\bf A+D+2(n-(A+D))}=\frac{\bf A+D}{2n-\bf A-D}$

J'ai vérifié numériquement si ces formules donnent un résultat correct. Ils font.

$\bf B$$\bf C$

$\bf B= [1]'X-A$$\bf X$$\bf B$$b$$\bf X$

$\bf C=B'$

$\bf D$$n \bf -A-B-C$

$\bf A, B, C, D$

La solution ci-dessus n'est pas très bonne si X est rare. Parce que prendre! X créera une matrice dense, prenant énormément de mémoire et de calcul.

Une meilleure solution consiste à utiliser la formule Jaccard [i, j] = #common / (#i + #j - #common) . Avec des matrices clairsemées, vous pouvez le faire comme suit (notez que le code fonctionne également pour les matrices non clairsemées):

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

Cela peut vous être utile ou non, selon vos besoins. En supposant que la similitude entre les affectations de cluster vous intéresse:

Le coefficient de similitude Jaccard ou l' indice Jaccard peut être utilisé pour calculer la similitude de deux affectations de clustering.

Compte tenu des étiquetages L1et L2, Ben-Hur, Elisseeff et Guyon (2002) ont montré que l'indice de Jaccard peut être calculé en utilisant les produits scalaires d'une matrice intermédiaire. Le code ci-dessous exploite cela pour calculer rapidement l'index Jaccard sans avoir à stocker les matrices intermédiaires en mémoire.

Le code est écrit en C ++, mais peut être chargé dans R à l'aide de la sourceCppcommande.

/**
 * 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));
}