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

 

이번 포스팅에서는 하나의 예를 가지고 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

댓글을 달아 주세요

  1. 닥터케빈 2017.11.09 11:38  댓글주소  수정/삭제  댓글쓰기

    안녕하세요? 먼저 좋은 내용의 포스팅 잘 봤습니다.

    오늘 '마할라노비스 거리'에 대해서 궁금한 게 있어서 이 포스팅에 오게 되었습니다.
    예시로 올려주신 내용은 첫 번째 학생과 두 번째 학생 간의 유사도를 다양한 거리 측도로 비교해주신 것으로 보입니다.

    저는 주어진 3차원 행렬 X에 대해서 '마할라노비스 거리'를 일괄적으로 계산하고 싶어서 다른 사이트를 찾아보니
    mahalonobis() 함수가 있고, 아래와 같이 실행을 하면 거리 벡터가 출력되는 것 같습니다.
    mahalonobis(x=X, center=colmeans(X), cov=cov(X))

    이와 같은 경우, 각 row 간 거리가 아닌 각 row별 거리를 계산해 주는 것이 맞겠죠?
    그러니까 이 결과값이 큰 것을 이상치로 가정하고 제외하면 무리가 없는지 궁금합니다. ^^

    • R Friend R_Friend 2017.11.12 19:35 신고  댓글주소  수정/삭제

      안녕하세요 닥터케빈님,
      답변 늦어서 정말 죄송합니다.
      퇴근 후에 답변 단다는게 그만 깜빡했습니다. ^^;;;

      거리는 row 간 거리, 즉 각 관측치 간 거이입니다.

      저는 mahalanobis() 함수가 있는줄 댓글로 달아주셔서 처음 알았는데요, 유용하게 잘 쓰겠습니다. mahalanobis() 함수 적용하면 각 관측치간 거리가 matrix 형태로 나오지요?

      이 마하라노비스 거리 행렬을 가지고 군집분석을 수행해서 outlier 성격의 군집을 detect 해보는 시도도 의미있을 것 같습니다.

      단, 댓글에 질문 남겨주신 것처럼 거리가 row 별 거리는 아닙니다.

  2. 어렵다어려워 2019.04.16 14:09  댓글주소  수정/삭제  댓글쓰기

    안녕하세요 r 프로그래밍 검색하다가 보게됐는데요
    유클리드 거리 구할때 1번학생과 2번학생 유클리드 거리 구하는법은 알겠는데
    1번학생과 3번학생의 유클리드 거리는 어떻게 구하는지 모르겠네요 ..
    r 돌려보니까 첨자의 혀용범위를 넘었다고 하는데
    시간되시면 답변부탁드립니다...!

지난번 포스팅에서는 군집분석(Cluster Analysis)의 개념과 유형에 대해서 알아보았습니다.

 

군집분석은 데이터를 유사한 혹은 동질의 군집(cluster)으로 묶어주는 것이라고 했었는데요, 그렇다면 "유사하다"(Similarity) 혹은 "유사하지 않다"(Dis-similarity)를 어떻게 측정할 수 있을지에 대한 방법이 이번 포스팅의 주제입니다.

 

이번에 살펴볼 거리 측도는 데이터와 데이터간 (비)유사성을 보는 군집분석뿐만이 아니라 변수와 변수간 관계를 보는 다변량 통계 분석에서도 기본기가 되는 중요한 내용이므로 유심히 보시기 바랍니다.  

 

데이터 간의 비유사성(Dis-similarity)거리(Distance)를 가지고 주로 측정하며, 유사성(Similarity)은 비유사성과 반비례의 관계에 있다고 보면 됩니다.  거리 말고 상관계수(Correlation coefficient)를 쓰기도 하는데요(→ collaborative filtering에서 상관계수 사용함), 이번 포스팅에서는 거리만 설명하도록 하겠습니다.

 

거리는 데이터의 속성, 구조에 따라서 적합한 것을 사용해야 하는데요, 이번 포스팅에서는 다중 변수의 구간식(Interval data type) 또는 비율식(Ratio data type) 데이터 속성에 대한 비유사성 측도로서 '거리'(Distance as a dis-similarity mesaure)척도로서,

 

  (1) 맨하탄 거리 (Manhattan distance)

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

  (3) 표준화 거리 (Standardized distance)

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

 

에 대해서 소개하겠습니다.  이밖에 확장 자카르드 계수(Extended Jaccard Coefficient), 상관계수(Correlation Coefficient), 브레그만 거리(Bregman Divergence)는 생략합니다.

 

[ 표기 관련 (denotation) ]

- 두 변수값 x와 y비유사성 척도로서 거리(distance) 는 d(x, y) 또는 간단히 d 로 표기함

 

 

[ 거리 척도 (Distance measures) ]

 

 

 

(1) 맨하탄 거리 (Manhattan distance)

 

 

맨하탄 거리는 뉴욕의 택시가 출발지에서 도착지로 갈 때 빌딩을 피해 동, 서, 남, 북의 격자 모양의 도로를 직선으로 갈 때의 거리(즉, 가로 블록 + 세로 블록 절대합)를 본따서 이름을 붙힌 거리입니다. ("Manhattan distance" is a rectilinear distance, named after the number of blocks north, south, east, or west a taxicab must travel on to reach its destination on the grid of streets in parts of New York City. - from Wikipedia -).  물리적인 길거리를 생각하면 쉽습니다. 자동차가 아무리 마음이 급하다고 길과 길 사이에 있는 빌딩(방해물, obstacle)을 뚫고 대각선으로 지나갈 수는 없는 노릇이며, 좋으나 싫으나 아래 그림처럼 빌딩을 피해 '도로'가 놓여진 한계 안에서 '최단 route'를 찾는 수밖에 없습니다. (<= 바로 이런 상황의 데이터를 분석해야할 때 맨하탄 거리를 사용하면 됩니다)

 

다른 말로 "City block distance", "Chessboard distance", "Chebyshev distance" 라고도 합니다. 서양 체스의 Rook move (상/하/좌/우, 동/서/남/북 방향으로만 이동 가능)를 생각하면 됩니다.

 

두 점의 값(starting point -> destination)에 대한 맨하탄 거리(Manhattan Distance)를 그림과 수식으로 나타내면 아래와 같습니다.  그래프 이론(Graph theory)에서는 두 지점의 거리를 '최단 경로(shortest route)'로 정의하는데요, 아래 그림에서 보면 각 도러의 블록별 단위거리가 동일하다고 하면 최단경로가 route 1, route 2, route 3, .... 많습니다 (좌에서 우로 8번 & 하에서 상으로 7번 경로 조합인 모든 route).

 

 

맨하탄 거리(Manhattan distance)는 민코우스키 거리(Minkowski distance)에서 r=1 인 거리이기도 합니다.  r=2 (2-norm distance) 인 경우는 유클리드 거리 (Euclidean distance) 입니다.

 

 

For a point (x1, x2, ...,xm) and a point (y1, y2, ...,ym), Minkowski distance is...

 

 

 

 

 

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

 

유클리드 거리는 두 점을 잇는 가장 짧은 직선 거리입니다.  아래 그림을 예로 들면, 헬리콥터를 타고 x 지점에서 y지점으로 날아간다고 했을 때 x와 y 지점 사이에 아무리 많은 빌딩(방해물)이 있더라도 상관없이 최단 직선 코스로 날아갈 수 있다고 연상하면 쉽게 이해할 수 있을 것입니다. 창공을 나는 새의 관점(from a bird's eye view)으로 본 거리입니다.  (↔ 위의 택시를 타고 가는 맨하탄 거리와의 차이를 비교해보세요)

 

서양 체스로 치면 상, 하, 좌, 우, 대각선 어느 방향으로나 이동이 자유로운 King move 나 Queen move 를 생각하면 되겠네요. (↔ 맨하탄 거리는 Rook move)

 

m차원 유클리드 공간 (Euclidean space ) 에서 두 점 (x1, x2), (y1, y2)의 거리는 피타고라스 정리(Pythagorean theorem)에 의해서 아래 그림에서 제시한 공식으로 구할 수 있습니다. 

 

 

민코우스키 거리(Minkowski distance)에서 r=2 (2-norm distance) 인 거리가 바로 유클리드 거리 (Euclidean distance) 입니다

 

 

 

 

만약 세 점 (x1, x2, x3), (y1, y2, y3) (in three-space) 간의 거리는 어떻게 구하면 될까요?  이 또한 피타고라스 정리에 의해서 아래처럼 유클리드 거리 공식으로 구하면 됩니다.

 

 

아주 많은 분석에서 유클리드 거리를 사용하며, 그렇다보니 대부분 '거리'하면 '유클리드 거리'를 가장 먼저 떠올리게 되곤 합니다.  그만큼 친숙하고도 아주 유용한 거리 개념입니다.

 

그런데 유클리드 거리에도 한가지 고려해야 할 점이 있습니다.  만약 두 변수의 분산, scale이 서로 다르다면 어떻게 될까요?  ☞ 표준화 거리에 대해서 얘기할 시간이군요.

 

 

 

 

(3) 표준화 거리 (Standardized distance)

 

 표준화 거리는 각 변수를 해당변수의 표준편차(standard deviation)로 척도 변환한 후에 유클리드 거리를 계산한 거리입니다.  표준화를 하게 되면 척도(scale)의 차이, 분산의 차이로 인한 왜곡을 피할 수 있습니다.  

표준화 거리는 다른 말로 통계적 거리 (Statistical distance) 라고도 합니다.

 

 

 

표준화 거리를 이용하여 한 점에서 거리가 같은 점들의 집합을 구하면 표본평균을 중심으로 좌표축에 장축(major axis)과 단축(minor axis)이 반듯하게 놓인 타원(Ellipse) 또는 타원체를 이루게 됩니다. 변수가 2개인 경우 두 개체간의 표준화 거리를 구하면 타원의 중심은 각 변수의 평균값이 위치한 곳이 되며, 아래 그림과 같은 형태로 그려져 각 변수의 평균점을 중심으로 하는 타원이 됩니다. ("R 다변량 통계분석", 김재희)

 

 

 

 

 

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

 

마할라노비스 거리는 변수의 표준편차와 더불어 변수 간 상관성(correlation)까지 고려한 거리측도입니다. (참고로, 마할라노비스(Prasanta Chandra Mahalanobis, 29 June 1893 – 28 June 1972) 는 인도의 과학자 겸 응용통계학자로서 '마할라노비스 거리'를 제안한 분입니다.)

 

 

 

한 점에서 마할라노비스 거리가 같은 점들의 집합을 구하면 표본평균을 중심으로 축이 회전된 타원체(rotated ellipse)를 이루게 됩니다. 변수간의 상관성이 있을 때의 거리 측도로서 방향성을 고려하여 아래의 그림과 같이 회전된 축을 생각할 수 있습니다. ("R 다변량 통계분석", 김재희)

(↔ 바로 앞의 그림 '표준화 거리를 이용해 구한 한점에서 거리가 같은 점들의 집합 : 타원'과 비교해보세요)

 

 

 

맨하탄 거리와 유클리드 거리는 그래도 제법 접해봤을 기회가 있었을 것 같은데요, 표준화 거리와 마할라노비스 거리는 낯설기도 하고 수식도 선형대수 표기법이 나오고 해서 이해하기가 좀 어려울것 같습니다. 

 

수식을 자세히 보시면 SVD(Singular Value Decomposition), 특이값 분해(축 rotation -> scale 변환 -> 축 rotation)와 비슷함을 알 수 있습니다.

 

다변량통계분석 하는 분이라면 Hotelling's T-squared 통계량 수식과 매우 유사함을 알 수 있을거예요. 마할라노비스 거리를 1/n 로 나누어주면 Hotelling's T-squared 통계량이 됩니다. 재미있죠? ^^

 

다음번 포스팅에서는 간단한 예를 들어서 유클리드 거리, 표준화 거리, 마할라노비스 거리를 설명하고, R script 도 소개하도록 하겠습니다.

 

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

 

[Reference]

(1) Distance from Wikipedia (https://en.wikipedia.org/wiki/Distance)

(2) "R 다변량 통계분석", 김재희 지음, 교우사

(3) Mahalanobis distance from Wikipedia (https://en.wikipedia.org/wiki/Mahalanobis_distance)

 

참고로, 명명식(Norminal) 데이터에 대한 비유사성 척도로는 단순일치계수(Simple Matching Coefficient, SMC), 자카드 계수(Jaccard Coefficient, JC), 문서 비유사도 측정에 코사인 거리(cosine distance), 문자열 편집 거리(edit distance, Levenshtein metric)를 사용합니다.  순서식(Ordinal) 데이터에 대한 비유사성 척도로는 순위상관계수(Rank Correlation Coefficient)를 사용합니다.

 

Posted by R Friend R_Friend

댓글을 달아 주세요