연속형 변수에 대한 비유사성 측도(dissimilarity measure)로서 매우 다양한 측도가 있는데요, 예전 포스팅에서 맨하탄 거리(Manhattan distance), 유클리드 거리(Euclidean distance), 표준화 거리(Standardized distance), 마할라노비스 거리(Mahalanobis distance) 에 대해서 알아보았습니다. (=> http://rfriend.tistory.com/199 , http://rfriend.tistory.com/201)


이번 포스팅에서는 범주형 데이터에 대해서 비유사성을 측정하는 지표로 Jaccard distance 를 소개하겠습니다. 


Jaccard distance 는 비교 대상의 두 개의 객체를 특징들의 집합(sets of characteristics)으로 간주합니다. 기본 개념이나 표기법이 집합론(set theory)에 기반을 두고 있습니다. 


Jaccard Index는 유사성 측도이고, 1에서 Jaccard Index값을 뺀 Jaccard distance는 비유사성 측도입니다. 


특징들의 두 개의 집합 X, Y가 있다고 했을 때, Jaccard Index는 집합 X와 집합 Y의 교집합(Intersection)의 원소의 개수()를 집합 X와 집합 Y의 합집합(Union)의 원소의 개수()로 나눈 값입니다.   따라서 Jaccard Index는 0~1 사이의 값을 가집니다. 


참고로, 표기는 집합론에서는 원소의 개수를 나타낼 때 사용하는 표기법이며, 다 아시겠지만, 는 교집합, 는 합집합을 의미합니다. 

Jaccard Distance 는 1 에서 Jaccard Index를 뺀 값입니다. ()


만약 두 집합의 합집합과 교집합이 서로 비슷하다면 자카드 지수는 거의 1에 근접(즉, 매우 유사)할 것이구요, 자카드 거리는 거의 0에 근접(즉, 매우 거리가 가깝다는 뜻, 즉 유사)할 것입니다. 


자카드 거리는 "두 집합에 공통으로 공유되는 항목은 중요한 반면에, 두 집합에서 모두 존재하지 않는 항목에 대해서는 무시해도 되는 상황, 문제"에 적합한 비유사성 측도입니다. 비교 대상이 되는 두 집합의 합집합, 교집합에 해당되는 않는 항목(item)은 그냥 제껴버리고 무시해버립니다. 


그 동안 군집분석을 소개하면서 비유사성 측도로서 거리(Distance)를 사용해왔는데요, 여기서도 Jaccard Distance를 가지고 예를 들어서 소개하고, R 로 실습도 해보겠습니다.  



[그림 1] 자카드 지표 & 자카드 거리 (Jaccard Index & Jaccard Distance)





이해를 쉽게 하기 위해서 아주 간단한 예를 하나 들어보겠습니다. 


5개의 상자가 있는데요, 거기에는 빨강, 노랑, 파랑 색깔의 공이 들어있다고 해봅시다. 그리고 각 상자별로 들어있는 공의 색깔을 가지고 상자들 끼리의 비유사성을 Jaccard 거리로 재보도록 하겠습니다. 



 -. 상자 1 = {노랑}

 -. 상자 2 = {노랑}

 -. 상자 3 = {빨강, 노랑, 파랑}

 -. 상자 4 = {빨강, 노랑}

 -. 상자 5 = {파랑}

 



(1) '상자 1'과 '상자 2'의 합집합(union)의 개수는 |{노랑}| = 1 이구요, 교집합(intersection)의 개수는 |{노랑}| =  1 이므로, 자카드 거리(상자 1, 상자 2) = 1 - (1/1) = 0 입니다. 


(2) '상자 1'과 '상자 3'의 합집합의 개수는 |{빨강, 노랑, 파랑}| = 3 이구요, 교집합의 개수는 |{노랑}| =  1 이므로, 자카드 거리(상자 1, 상자 3) = 1 - (1/3) = 약 0.667 입니다. 


(3) '상자 1'과 '상자 4'의 합집합의 개수는 |{빨강, 노랑}| = 2 이며, 교집합의 개수는 |{노랑}| =  1 이므로, 자카드 거리(상자 1, 상자 4) = 1 - (1/2) = 0.5 입니다. 


(4) '상자 1'과 '상자 5'의 합집합의 개수는 |{노랑, 파랑}| =  2 이며, 교집합의 개수는 |{NA}| = 0 이므로, 자카드 거리(상자 1, 상자 5) = 1 - (0/2) = 1 입니다. 


(5) '상자 3'과 '상자 4'의 합집합의 개수는 |{빨강, 노랑, 파랑}| = 3 이구요, 교집합의 개수는 |{빨강, 노랑}| = 2 이므로, 자카드 거리(상자 3, 상자 4) = 1 - (2/3) = 약 0.333 입니다. 


(6) '상자 3'과 '상자 5'의 합집합의 개수는 |{빨강, 노랑, 파랑}| = 3, 교집합의 개수는 |{파랑}| =  1 이므로, 자카드 거리(상자 3, 상자 5) = 1 - (1/3) = 약 0.667 입니다. 


(7) '상자 4'와 '상자 5'의 합집합의 개수는 |{빨강, 노랑, 파랑}| =  3 이며, 교집합의 개수는 |{NA}| = 0 이므로, 자카드 거리(상자 4, 상자 5) = 1 - (0/3) = 1 입니다. 






이를 R의 proxy package를 사용해서 풀어보겠습니다. 


먼저 proxy package를 설치하고 불러오도록 합니다. 



#===========================================

# distance(dissimilarity) calculation using proxy package

#===========================================


> install.packages("proxy")

> library(proxy)

 




proxy package는 2017년 초에 CRAN에 등록이 된 따끈따근한 패키지인데요, 총 49개의 proximity 지표(similarity measures, distance measures) 가 들어있습니다. 



> # show available proximities

> pr_DB

An object of class "registry" with 49 entries.

> summary(pr_DB)

* Similarity measures:

Braun-Blanquet, Chi-squared, Cramer, Dice, Fager, Faith, Gower, Hamman, Jaccard,

Kulczynski1, Kulczynski2, Michael, Mountford, Mozley, Ochiai, Pearson, Phi, Phi-squared,

Russel, Simpson, Stiles, Tanimoto, Tschuprow, Yule, Yule2, correlation, cosine, eDice,

eJaccard, simple matching


* Distance measures:

Bhjattacharyya, Bray, Canberra, Chord, Euclidean, Geodesic, Hellinger, Kullback,

Levenshtein, Mahalanobis, Manhattan, Minkowski, Podani, Soergel, Wave, Whittaker,

divergence, fJaccard, supremum





proxy package의 Jaccard 클래스에 대해서 간략한 설명을 살펴보면 아래와 같습니다. binary 형태의 데이터에 대한 (비)유사성 척도라고 되어 있습니다.  그리고 (FALSE, FALSE) pairs 에 대해서는 고려하지 않고 무시하며, 비교 대상의 두 객체 집합의 합집합과 교집합을 비교한다고 되어 있습니다. 


> names(pr_DB)

 [1] "get_field"              "get_fields"             "get_field_names"       

 [4] "set_field"              "entry_exists"           "get_entry"             

 [7] "get_entries"            "get_entry_names"        "set_entry"             

[10] "modify_entry"           "delete_entry"           "n_of_entries"          

[13] "get_field_entries"      "get_permissions"        "restrict_permissions"  

[16] "seal_entries"           "get_sealed_entry_names" "get_sealed_field_names"


> pr_DB$get_entry("Jaccard")

      names Jaccard, binary, Reyssac, Roux

        FUN R_bjaccard

   distance FALSE

     PREFUN pr_Jaccard_prefun

    POSTFUN NA

    convert pr_simil2dist

       type binary

       loop FALSE

      C_FUN TRUE

    PACKAGE proxy

       abcd FALSE

    formula a / (a + b + c)

  reference Jaccard, P. (1908). Nouvelles recherches sur la distribution florale. Bull.

            Soc. Vaud. Sci. Nat., 44, pp. 223--270.

description The Jaccard Similarity (C implementation) for binary data. It is the proportion

            of (TRUE, TRUE) pairs, but not considering (FALSE, FALSE) pairs. So it compares

            the intersection with the union of object sets.

 




위의 상자 5개의 공 색깔 예제를 R로 실습해 보기 위해서 아래 처럼 5개의 행(row)은 상자를 나타내고, 3개의 열(column)은 색깔(순서대로 빨강, 노랑, 파랑)을 나타내는 걸로 하겠습니다. 그리고 각 상자별 빨강, 노랑, 파랑 색깔의 공이 있으면 ' 1(TRUE)'을 입력하고, 공이 없으면 '0(FALSE)'을 입력해서 행렬(matrix)을 만들어보겠습니다. proxy package가 타카드 거리를 계산할 수 있도록 binary 형태의 데이터셋을 만드는 것입니다. 



> # making binary dataset as a matrix

> x <- matrix(c(0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1), 

+             byrow = TRUE, 

+             ncol = 3)

> x

     [,1] [,2] [,3]

[1,]    0    1    0

[2,]    0    1    0

[3,]    1    1    1

[4,]    1    1    0

[5,]    0    0    1 





dist(x, method = "Jaccard") 함수를 사용해서 Jaccard distance를 계산해보겠습니다.  위의 예에서 손으로 푼 결과와 동일한 값들이 나왔습니다. 



> # Jaccard distance

> dist(x, method = "Jaccard")

          1         2         3         4

2 0.0000000                              

3 0.6666667 0.6666667                    

4 0.5000000 0.5000000 0.3333333          

5 1.0000000 1.0000000 0.6666667 1.0000000

 




아래처럼 cross Jaccard distances 를 계산하려면 dist(x, x, method = "Jaccard") 처럼 행렬 x 를 두번 입력해주면 됩니다. 



> # cross Jaccard distances

> dist(x, x, method = "Jaccard")

     [,1]      [,2]      [,3]      [,4]      [,5]     

[1,] 0.0000000 0.0000000 0.6666667 0.5000000 1.0000000

[2,] 0.0000000 0.0000000 0.6666667 0.5000000 1.0000000

[3,] 0.6666667 0.6666667 0.0000000 0.3333333 0.6666667

[4,] 0.5000000 0.5000000 0.3333333 0.0000000 1.0000000

[5,] 1.0000000 1.0000000 0.6666667 1.0000000 0.0000000

 




proxy package에 비해서는 조금 비효율적이기는 하지만 stats package 의 dist(x, method = "binary")함수를 사용해서도 Jaccard distance를 계산할 수 있습니다. 



> # using stats package (less efficient than proxy package)

> as.matrix(stats::dist(x, method = "binary"))

          1         2         3         4         5

1 0.0000000 0.0000000 0.6666667 0.5000000 1.0000000

2 0.0000000 0.0000000 0.6666667 0.5000000 1.0000000

3 0.6666667 0.6666667 0.0000000 0.3333333 0.6666667

4 0.5000000 0.5000000 0.3333333 0.0000000 1.0000000

5 1.0000000 1.0000000 0.6666667 1.0000000 0.0000000

 



많은 도움 되었기를 바랍니다. 

이번 포스팅이 도움이 되었다면 아래의 '공감~' 단추를 꾸욱 눌러주세요. ^^


다음번 포스팅에서는 코사인 거리(Cosine Distance),  문자열 편집 거리(edit distance, Levenshtein metric)를 알아보겠습니다. 




Posted by R Friend R_Friend

지난번 포스팅에서는 (구간식 또는 비율식 데이터 속성의 다변수일 경우의) 유사성, 비유사성 측도로서 다양한 거리의 정의에 대해서 알아보았습니다.

 

이번 포스팅에서는 하나의 예를 가지고 R을 사용하여 각 거리 종류별 거리를 계산, 비교해보도록 하겠습니다.

 

예로 사용할 데이터는 5명의 학생의 '선형대수(linear algebra)'와 '기계학습(machine learning)' 기말고사 시험성적입니다.  이 중에서 1번째와 2번째 학생(아래 산점도의 빨간점)의 선형대수와 기계학습 시험점수의 거리를 (1) 맨하탄 거리(manhattan distance), (2) 유클리드 거리(euclidean distance), (3) 표준화 거리(standadized distance), (4) 마할라노비스 거리(mahalanobis distance)로 계산해보도록 하겠습니다.

 

> ##----------------------------------
> ## Dis-similarity measure - Distance
> ##----------------------------------
> 
> # 'linear algebra' and 'machine learning' score per student
> st_1 <- c(70, 65)
> st_2 <- c(90, 95)
> st_3 <- c(65, 60)
> st_4 <- c(85, 90)
> st_5 <- c(60, 75)
> 
> st_all <- rbind(st_1, st_2, st_3, st_4, st_5)
> st_all
     [,1] [,2]
st_1   70   65
st_2   90   95
st_3   65   60
st_4   85   90
st_5   60   75
> 
> # scatter plot
> plot(st_all, xlab = "linear algebra", ylab = "machine learning", 
+      xlim = c(50, 100), ylim = c(50, 100), 
+      main = "scatter plot of final scores")
> 
> # adding student label
> text(st_all[,1], st_all[,2], labels = abbreviate(rownames(st_all)), 
+      cex = 0.8, pos = 1, col = "blue")
> 
> # marking student 1, student 2 with red point
> points(st_all[1,1], st_all[1,2], col = "red", pch = 19)
> points(st_all[2,1], st_all[2,2], col = "red", pch = 19)

 

 

 

 

 

1) 맨하탄 거리 (Manhattan distance)

 

dist(dataset, method = "manhattan") 함수를 사용하여 맨하탄 거리를 계산할 수 있습니다.

 

아니면 아래의 두번째 방법처럼 두 변수의 관측치별 차이 절대값을 더해주면 됩니다 ( <- 달랑 2개 관측치 거리를 계산하는 거니깐 이 방식도 사용할만 하지만요, 만약 관측치 학생 1,000 명의 거리를 구하는 것이라면요? ^^;  두 방식의 결과값 포맷이 조금 다르다는 점도 눈여겨 봐주세요.)

 

 

> ##-- Manhattan distance between 1st and 2nd student
> ## (1) dist(dataset, method = "manhattan") function
> dist_mht <- dist(st_all[1:2, ], method = "manhattan")
> dist_mht
     st_1
st_2   50
> 
> ##-- Manhattan distance between 1st and 2nd student
> ## (2) calculation
> dist_mht_2 <- abs(st_all[1,1] - st_all[2,1]) + abs(st_all[1,2] - st_all[2,2])
> dist_mht_2
st_1 
  50 

 

 

 

 

2) 유클리드 거리 (Euclidean distance)

 

dist(dataset, method = "euclidean") 함수를 사용하여 유클리드 거리를 계산할 수 있습니다.

 

 

> ##-- Euclidean distance between 1st and 2nd student
> dist_euclid <- dist(st_all[1:2, ], method = "euclidean")
> dist_euclid
         st_1
st_2 36.05551

 

 

 

 

 

3) 표준화 거리, 통계적 거리 (Standadized distance, Statistical distance)

 

표준화 거리는 2가지 방법을 사용해서 계산해보겠습니다.

  (1) 데이터를 표준화한 후에 -> 유클리드 거리 계산

  (2) 

 

'2.501805' 로서 두 가지 계산 방법의 결과가 똑같습니다.

 

> ##-- Standadized distance > # (way 1) standadization -> euclidean distance > st_all [,1] [,2] st_1 70 65 st_2 90 95 st_3 65 60 st_4 85 90 st_5 60 75 > mean(st_all[,1]); sd(st_all[,1]) [1] 74 [1] 12.94218 > mean(st_all[,2]); sd(st_all[,2]) [1] 77 [1] 15.24795 > > # standadization of st_1's score > z_st_1 <- (st_all[,1] - mean(st_all[,1]))/sd(st_all[,1]) > z_st_1 st_1 st_2 st_3 st_4 st_5 -0.3090670 1.2362679 -0.6954007 0.8499342 -1.0817344 > > # standadization of st_2's score > z_st_2 <- (st_all[,2] - mean(st_all[,2]))/sd(st_all[,2]) > z_st_2 st_1 st_2 st_3 st_4 st_5 -0.7869910 1.1804865 -1.1149039 0.8525736 -0.1311652 > > z_st_all <- cbind(z_st_1, z_st_2) > z_st_all z_st_1 z_st_2 st_1 -0.3090670 -0.7869910 st_2 1.2362679 1.1804865 st_3 -0.6954007 -1.1149039 st_4 0.8499342 0.8525736 st_5 -1.0817344 -0.1311652 > > # euclidean distance between 1st and 2nd student's standadized score > dist_z_st_all <- dist(z_st_all[1:2, ], method = "euclidean") > dist_z_st_all st_1 st_2 2.501805 > > # ======================================================================= > # (way 2) [(X-Y)'D^-1(X-Y)]^1/2

> # covariance : cov()

> cov_st_all <- cov(st_all)

> cov_st_all

      [,1]  [,2]
[1,] 167.5 165.0
[2,] 165.0 232.5

> Diag <- rbind(c(cov_st_all[1,1], 0), + c(0, cov_st_all[2,2])) > Diag [,1] [,2] [1,] 167.5 0.0 [2,] 0.0 232.5 > > dist_stand <- sqrt(t(st_all[1,] - st_all[2,])%*%solve(Diag)%*% + (st_all[1,] - st_all[2,])) > dist_stand # exactly the same with the above result [,1] [1,] 2.501805

 

 

 

 

 

4) 마할라노비스 거리 (Mahalanobis distance) 

마할라노비스 거리는 아래 식을 사용해서 계산해보겠습니다.

 

 

 

> ##-- Mahalanobis distance
> # covariance : cov()
> cov_st_all <- cov(st_all)
> cov_st_all
      [,1]  [,2]
[1,] 167.5 165.0
[2,] 165.0 232.5
> dist_mahal <- sqrt(t(st_all[1,] - st_all[2,])%*%solve(cov_st_all)%*%
+                      (st_all[1,] - st_all[2,]))
> dist_mahal
         [,1]
[1,] 1.975854

 

 

 

위에서 계산한 4가지 방법별 거리 계산 결과를 종합하면 아래와 같습니다.

맨하탄 거리가 가장 길고 > 유클리드 거리 > 표준화 거리 > 마할라노비스 거리 순으로 나왔네요.

 

> ## overall
> dist_all <- cbind(dist_mht[1], dist_euclid[1], dist_stand, dist_mahal)
> dist_all
     [,1]     [,2]     [,3]     [,4]
[1,]   50 36.05551 2.501805 1.975854
> 
> barplot(dist_all, 
+         col = "blue", 
+         names.arg =  c("manhattan", "euclidean", "standadized", "mahalanobis"), 
+         main = "Distance between st_1 and st_2's score")

 

 

 

이상으로 군집분석 들어가기 전에 기초 체력을 다지는 의미에서 비유사성 측도로서의 거리(distance)에 대해서 알아보았습니다.

 

다음번 포스팅에서는 본격적으로 군집분석 세부 내용으로 들어가 보겠습니다. 첫 테잎은 '계층적 군집(hierarchical clustering) 모형'이 끊는 것으로 해보겠습니다.

 

이번 포스팅이 도움이 되었다면 아래의 '공감 ~♡'을 꾸욱 눌러주세요. ^^

 

 

 

Posted by R Friend R_Friend