태그 보관물: association-measure

association-measure

행렬 곱셈을 사용하여 이진 데이터에 대한 Jaccard 또는 기타 연관 계수 계산 for(j in

행렬 곱셈을 사용하여 Jaccard 계수를 계산할 수있는 방법이 있는지 알고 싶습니다.

이 코드를 사용했습니다

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

이것은 R에서 구현하는 것이 좋습니다. 주사위 유사성 하나를 수행했지만 Tanimoto / Jaccard에 붙어 있습니다. 누구든지 도울 수 있습니까?



답변

Jaccard (2 진 데이터의 두 사이에서 계산 됨)

X

)는

aa+b+c

로저스-타니 모토는

a+da+d+2(b+c)

, 어디

  • a-두 열이 모두 1 인 행 수
  • b-다른 열이 아닌 1 인 행 수
  • c-이 열이 아닌 다른 열이 1 인 행 수
  • d-두 열이 모두 0 인 행 수

a+b+c+d=n

의 행 수

X

그럼 우리는 :

XX=A

의 제곱 대칭 행렬입니다

a

모든 열 사이.

(notX)(notX)=D

의 제곱 대칭 행렬입니다

d

모든 열 사이에서 ( “X가 아님”은 X에서 1-> 0 및 0-> 1로 변환 됨)

그래서,

AnD

모든 열 사이의 Jaccard의 사각형 대칭 행렬입니다.

A+DA+D+2(n(A+D))=A+D2nAD

모든 열 사이의 Rogers-Tanimoto의 사각형 대칭 행렬입니다.

이 공식이 올바른 결과를 제공하는지 수치로 확인했습니다. 그들이하다.


Upd. 행렬을 얻을 수도 있습니다

B

C

:

B=[1]XA

여기서 “[1]”은 다음과 같이 크기가 지정된 1의 행렬을 나타냅니다.

X

.

B

제곱 비대칭 행렬입니다

b

모든 열 사이; 요소 ij 는 행의 수입니다.

X

컬럼에서 0 I 열에서 1 J .

따라서,

C=B

.

매트릭스

D

물론 이런 식으로 계산할 수도 있습니다.

nABC

.

행렬 알기

A,B,C,D

, 이진 데이터에 대해 발명 된 쌍 유사 (비 유사) 계수의 행렬을 계산할 수 있습니다.


답변

X가 드문 경우 위의 해결책은 그리 좋지 않습니다. ! X를 사용하면 밀도가 높은 행렬이 만들어 지므로 엄청난 양의 메모리와 계산이 필요합니다.

더 좋은 해결책은 공식 Jaccard [i, j] = #common / (#i + #j-#common)을 사용하는 것 입니다. 희소 행렬을 사용하면 다음과 같이 수행 할 수 있습니다 (코드는 희소 행렬에도 적용됨).

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


답변

이것은 귀하의 필요에 따라 귀하에게 유용 할 수도 있고 그렇지 않을 수도 있습니다. 클러스터링 할당 간의 유사성에 관심이 있다고 가정합니다.

Jaccard 유사성 계수 또는 Jaccard 색인 을 사용하여 두 군집 지정의 유사성을 계산할 수 있습니다.

주어진 labelings L1하고 L2, 벤허, Elisseeff 및 귀용 (2002) 인 Jaccard 인덱스 중간 행렬의 내적을 이용하여 계산 될 수 있음을 보여 주었다. 아래 코드는이를 활용 하여 중간 행렬을 메모리에 저장하지 않고도 Jaccard Index 를 빠르게 계산합니다.

코드는 C ++로 작성되었지만 sourceCpp명령을 사용하여 R에로드 할 수 있습니다 .

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


답변