카테고리 보관물: 알고리즘 Algorithm

CART – 결정 트리와 회귀 트리 Decision Tree and Regression Tree #1

결정트리(Decision Tree)인 CART 알고리즘에 대해 포스팅합니다.

제 계획대로라면 벌써 몇년전에 포스팅을 했어야 했지만 계획대로 되는 것은 언제나 그렇듯이 없습니다.

CART는 GBDT, Random Forest, XGboost, LightGBM 등의 트리계열 알고리즘의 근간이 되는 매우 중요한 알고리즘입니다. 요즘 트리 계열 알고리즘에서 가장 좋은 성능을 보이는 XGboost에게는 할아버지쯤 되는 알고리즘입니다.

CART에는 결정 트리(Decision Tree)와 회귀 트리(Regression Tree)라는 알고리즘이 2개 들어 있습니다. 한 개가 아닙니다. 그런데 둘은 거의 비슷하기 때문에 1개라고 봐도 무리가 없긴 합니다. 일란성 쌍둥이라고 생각하면 됩니다. CART는 Classification And Regression Trees의 약어인데 여기에도 분류와 회귀를 하는 트리라는 것을 알려주고 있습니다.

어쨌든 이 둘의 차이는 뒤에 설명하겠습니다.

알고리즘의 컨셉

알고리즘의 컨셉은 간단합니다. 학습 데이터를 해석해서 알아서 트리 구조를 자동으로 만든 다음 만들어진 트리를 이용해서 분류, 예측 문제를 해결하는 모델을 만드는 것입니다.

여기서 중요한 것은 트리를 자동으로 만든다는 것입니다. 트리를 사람이 만들어줘야 한다고 상상하시는 분들이 있는데 아닙니다.

분류 트리와 회귀 트리의 차이

분류 트리와 회귀 트리의 차이를 살펴보겠습니다.

결정 트리(Classification Tree)는 클래스(등급) 또는 레이블(표 딱지)을 예측하는 것으로 “남”또는 “여”, “예” 또는 “아니오”, “A”, “B”, “C” 와 같이 어떤 것인 맞추는 것(판별)이고

회귀 트리(Regression Tree)는 연속형 숫자인 1,2,3 123, 28.5와 같은 숫자를 맞추는 것입니다. 사람의 키를 맞춘다거나, 대출 상환 예상액을 맞춘다거나 하는 것(예측)입니다.

CART의 탄생

뭐든 그렇지만 자세한 설명 전에 역사를 조금 살펴보면 이해하는데 도움이 됩니다.

CART는 1980년대에 발표된 것으로 이제 나이가 들대로 든 알고리즘이지만 아직도 현역에서 많이 쓰입니다. 기계학습 알고리즘이 다들 독특한 면이 있긴하지만 CART도 상당히 독특한 기계학습 알고리즘입니다. 이 알고리즘은 학술상의 갈래로 보면 데이터마이닝 계열로 많이 분류됩니다. 비즈니스적인 결정을 과학적으로 해서 가치 창출얼 하기 위한 것. 그러니까 좋은 결정을 내리는 것을 자동화하기 위한 용도로 만들어진 것입니다.

만든 분들의 말에 의하면 통계 분석이나 문제 해결을 할 때 마다 회귀모델같은 통계 모델이나 여러 수리 모델을 매번 디자인하고 적용하는 것이 비효율적이라서 싫었다고 합니다.

데이터마이닝 계열이라고 했지만 이것도 기계학습 알고리즘이고 만들어진 원리를 보면 꽤 깊은 고급 통계 이론과 정보 이론이 함축되어 있습니다. 만만한 알고리즘은 아닙니다. 이 알고리즘의 저자들이 총 4명인데 통계학, 과학, 의학, 경제학, 컴퓨터 공학에 매우 뛰어난 석학들입니다. 이 알고리즘이 이런 분야에 고루 쓸 수 있는 다목적 도구라고 해석해 볼 수 있습니다.

CART의 저자와 논문

보통 알고리즘은 논문으로 많이 발표되는데 CART 알고리즘은 논문이 없습니다. 논문으로 발표된 알고리즘이 아니고 책으로 발표된 알고리즘입니다. 논문을 찾다가 논문이 없고 대신 책이라는 사실에 충격받았던 기억이 있습니다.

오래된 책인 만큼 표지가 매우 촌스럽습니만 아마존에서 아직도 판매하고 있습니다. 출판일을 보면 1984년 1월 출판이 첫판입니다.

CART의 저자들

앞서 말씀드렸듯이 책 표지에 있는 저자 4명은 모두 각 분야에서 상당히 유명한 분들입니다. 아래의 4명입니다.

  • Leo Breiman – University of California, Berkeley
  • Jerome H. Friedman – Stanford University
  • Richard A. Olshen – Stanford University
  • Charles J. Stone – University of California, Berkeley

책의 저자들까지 나열한 것은 위의 저자들 중에
Leo Breiman (레오 브라이먼)
Jerome H. Friedman (제롬 프리드먼)
이름을 굳이 외우실 필요는 없습니다만 이 두 사람은 알아두는 것이 기계학습을 깊이 공부하신다면 도움이 되기 때문입니다. 이 두 사람은 CART 발표 이후에 Random Forest(랜덤 포레스트)와 GBDT (Gradient Boosted Decision Tree), GBRT(Gradient Boosted Regression)를 만든 사람들입니다. 아마 기계학습을 조금이라도 공부하신 분들은 이 알고리즘들의 이름을 알고 있을 것입니다. 특히 랜덤포레스트는 너무도 유명하지요. 그리고 부럽게도 위키피디아에도 이 분들 이름이 등록되어 있습니다.

CART와 유사한 알고리즘

ID3, C4.5, C5.0 이라는 결정 트리(Decision Tree)알고리즘이 있습니다. 나열한 순서대로 개량된 버전인데 C4.5가 가장 많이 알려져 있습니다. CART와 유사하다고 하는데 동일한 시대에 발표된 것이지만 관련은 없다고합니다. 구조도 서로 비슷하다고 알려져 있습니다만 제가 이 알고리즘은 잘 알지 못합니다.

CART가 현재는 라이센스가 없이 무료인 반면 C4.5 구현체가 판매되었던 알고리즘이라서 사용자가 많지는 않습니다. 성능은 꽤 좋다고 하며 CART와 C4.5의 성능은 비슷하다고 알려져 있습니다.

CART의 개량형, 강화형

CART의 개량형, 강화형 또는 영향을 받은 것은 다음과 같은 것들이 있습니다.

  • Random Forest
  • Gradient Boosted Decision Tree / Gradient Boosted Regression Tree
  • XGboost
  • lightGBM
  • CatBoost
  • Isolation Cut Forest
  • Robust Random Cut Forest

앞서 말했듯이 요즘 각광받는 XGboost, lightGBM도 모두 CART 계열입니다. 현재 결정 트리 계열 중에 가장 주목받는 것은 lightGBM 입니다. 그래서 요즘은 CART를 사용하지 않고 바로 lightGBM이나 XGboost를 사용하는 경우도 많습니다. 다만 CART만 앙상블 모델이 아니고 다른 알고리즘은 모두 앙상블 모델입니다. 앙상블 모델은 여러 모델을 합쳐서 하나의 모델로 만든 것을 말합니다.

위의 알고리즘 중에서 저는 개인적으로 lightGBM을 매우 좋아합니다만 그 이유는 XGboost이 비해서 가볍고 범주형 변수를 지원하기 때문입니다. 자세한 얘기는 다음 기회에 하기로 하겠습니다.

Decision Tree와 Regression Tree의 차이

Decision Tree(결정 트리, 분류 트리)와 Regression Tree(회귀 트리)는 매우 유사합니다. Decision Tree가 남,녀와 같이 클래스 또는 레이블로 된 것을 분류해주는 Classification(분류) 문제 해결이라면 Regression Tree는 몸무게, 키, 확률 등의 연속형 수치값을 추정해주는 Regression 입니다.

참고로 Regression Tree에는 흔히 말하는 Linear Regression과 같은 회귀 모델이 들어 있지 않습니다. 연속형 값을 추정하는 것을 넓은 의미로 Regression(회귀)라고 하는데 Regression Tree는 종단 노드에서 평균을 사용해서 결과값을 추정합니다. 평균을 사용해서 추정하는 것은 넓은 의미에서 회귀라고 말 할 수 있습니다.

설명이 어려워졌는데 쉽게 말하자면 Regression Tree에서 말하는 Regression은 Linear Regression(선형회귀)나 Logistic Regression(로지스틱 리그레션)에서 말하는 그 회귀(Regression)이 아닙니다.

CART의 원리

복잡한 수식 같은 것을 적으려면 시간과 지면이 많이 필요합니다. 우선 원리만 적고 자세한 것은 나중에 업데이트하도록 하겠습니다.

cart algorithm에 대한 이미지 검색결과

CART 위와 같은 트리를 자동으로 만드는 것입니다. 위의 그림은 CART에서도 Decision Tree를 설명한 것인데 남 (Male), 여 (Female)를 구분하는 판별 모형을 만들때 입력 변수(Input variable, feature, 자질)인 키 (Height)와 몸무게 (Weight)를 이용하는 Decision Tree입니다.

입력 변수는 범주형 변수를 넣을 수도 있습니다. 만약 머리색을 입력 변수 중 하나로 추가해서 넣는다고 하면 Black, Brown, Pink 등과 같은 것이 됩니다.
출력 클래스도 남, 여가 아닌 남,여,모름 이렇게 3개 이상을 지정할 수 있습니다. 단 Decision Tree에 해당하고 Regression Tree는 안됩니다.

CART의 신비는 저 “트리를 어떻게 자동으로 만들어 주느냐”입니다.

이 다음 설명은 다음 편으로 짤라서 쓰겠습니다.

Banker’s Rounding – 은행원 방식 반올림

아실지 모르겠지만 반올림은 여러가지 계산 방식이 있습니다. 한가지가 아닙니다.

이 차이를 모르면 소숫점이 있는 수치 계산을 하다가 반올림 처리 방식의 차이로 인해 오차가 생겼다고 생각하고 정합성을 맞추려다 헤메는 경우가 있을 수도 있습니다.

물론 평생 이런 일이 없을 수도 있습니다.

제가 학생이던 시절에 금전 계산을 자동으로 복잡하게 하는 정산 소프트웨어를 의뢰받아 만든 적이 있었는데, 의뢰인이 제시해준 계산 방법과 확인용 정산 출력물을 기반으로 계산 소프트웨어를 작성하는 흐름으로 진행했었습니다. 단위 계산이 조금 복잡했고 반복 계산을 한 뒤에 복잡하게 역산하는 것을 한 뒤에 총 결과를 산출하는 것이었습니다. 요즘 용어로 바꾸자면 최적화 비슷한 것이었습니다.

그런데 문제가 생겼습니다.
만들 때 적은 양의 데이터로 단위 계산을 몇 개 실험해서 해본 뒤에 나온 결과를 보고 정확하게 계산되었는지를 정확하게 확인했고 문제가 없었습니다, 그 후에 전체 계산을 수행하는 것을 진행해서 총합을 확인해보니 정답지와 결과값이 미세하게 달랐습니다. 다시 단위 계산을 몇개 임의로 선택해서 결과가 어떻게 다른지 점검해 봤는데 몇개가 다르게 나온다는 것을 알았습니다. 이 문제의 원인을 찾느라 시간을 쓸데없이 허비한 적이 있습니다.

물론 이 차이로 인해 큰 일이 생기는 것은 아니었습니만 숫자는 틀려도 문제의 원인을 알지 못하면 곤란하다는 의뢰인의 말에 원인을 찾아야 했습니다.

찾아 본 결과 원인은 제가 사용하던 컴퓨터 랭귀지에서 제공하는 round 함수가 사사오입이 아닌 뱅커스 라운딩(Bankers’ rounding)을 채택했기 때문에 발생한 문제였고 round 함수를 사사오입 방식의 다른 round로 변경해서 해결했었습니다. 그 뒤로는 round를 하게될 일이 있으면 반드시 사용하는 소프트웨어의 round가 사사오입 방식인지 뱅커스 라운딩인지 확인을 하고 작업을 시작하는 습관이 있습니다. 그게 아니면 오차가 좀 크더라도 정합성을 위해서 무조건 소숫점이하는 절사 시켜버리곤 했습니다. 물론 요즘은 이것마저도 잘 하지 않는 늙은이가 되었습니다만.

어쨌든 그 당시에는 컴퓨터 랭귀지의 기본 함수에 버그가 있는 줄 알고 컴파일러 판매회사에 문의하려고 했었으나 함수 매뉴얼을 먼저 찾아보니 천절하게 설명을 해 두었더군요. 함수 매뉴얼을 자세히 읽지 않은 제가 문제였던 것이고 그리고 관련 자료를 더 찾아보고는 제가 반올림에 대해서 상당히 무식했다는 사실을 알았습니다.

“세상에 반올림 방법은 딱 하나 인 줄 만 알았어” 라고 생각했습니다. 배운 것이 그것뿐이라서요.

앞서 말씀드린 것 처럼 반올림은 여러가지 방식이 있습니다. 꽤 많은 방식들이 있습니다만 우리가 흔히 접할 수 있는 것은 위에서 말한 2가지인 사사오입과 뱅커스 라운딩입니다.
이 포스트에서 사사오입과 뱅커스라운딩의 차이를 설명하겠습니다.

사사오입( 四捨五入 ) 반올림

우선, 흔히 아는 반올림은 사사오입(四捨五入, Normal rounding)인데 4는 버림, 5는 올림을 뜻합니다. 보통은 우리는 그냥 “반올림”이라고 하지만 명확환 구분과 설명을 위해서 “사사오입”이라고 하겠습니다.
사사오입 방식은 영어로는 Round, away from zero (0으로부터 멀어지는 이라는 뜻) 라고 합니다.
사사오입으로 소숫점이 있는 숫자들을 정수로 반올림한다고 하면 다음과 같은 결과가 나옵니다.

0.4 반올림 하면 0
0.5 반올림 하면 1
0.6 반올림 하면 1
1.4 반올림 하면 1
1.5 반올림 하면 2
1.6 반올림 하면 2
2.4 반올림 하면 2
2.5 반올림 하면 3
2.6 반올림 하면 3

잘 알고 있는 그 방식입니다.

뱅커스 라운딩

뱅커스 라운딩 올려질 값이 5인 경우에 만들어질 수의 끝이 짝수가 되도록(짝수에 수렴) 하는 방식입니다.

영어의 다른 표현으로는 Round, half to even (절반을 짝수쪽으로)라고 합니다. 금융권에서 많이 채택해서 쓰기 때문에 뱅커스 라운딩이라는 별칭으로 많이 불립니다. 미국의 경우이고 한국 금융권에서도 이것을 채택해서 쓰는지는 모르겠습니다.
어쨌든 뱅커스라운딩으로 계산하면 다음과 같이 됩니다. 굵은 글씨 부분을 자세히 보세요.

0.4 반올림 하면 0
0.5 반올림 하면 0
0.6 반올림 하면 1
1.4 반올림 하면 1
1.5 반올림 하면 2
1.6 반올림 하면 2
2.4 반올림 하면 2
2.5 반올림 하면 2
2.6 반올림 하면 3
2.45 반올림 하면 2

사사오입과 뱅커스라운딩 둘을 비교 해보면 이렇습니다.

대상값 / 방식사사오입뱅커스 라운딩
0.400
0.510
1.411
1.522
1.622
2.422
2.532
2.633
4.554
4.444554
사사오입가 뱅커스라운딩의 비교표

뱅커스 라운딩은 미국 측정 계산의 표준이라고 알려져 있습니다. 직접 물어봐서 확인해 보지 않았지만 온라인 문서에 그렇게 적혀 있습니다. 그래서 최신의 컴퓨터 언어나 계산 관련 소프트웨어들에서 기본으로 지원하는 반올림 함수는 우리가 아는 사사오입 방식이 아닌 뱅커스 라운딩을 사용하는 것이 많습니다. 소프트웨어들이 여전히 미국산이 많기 때문인데 특히 과학계산 용도로 쓰는 것들이 그렇습니다.

반올림?

사사오입은 엄밀히 말하면 반올림이 아닙니다. 우리가 쓰는 반올림은 영어로 round라고 하는데 round라고 하는 것의 원래 뜻은 숫자를 단순하게 만드는 것을 말합니다.

round 는 둥글게 심플하게 밋밋하게 한다는 뜻입니다.

그래서 “무조건 올림”은 영어로 round-up이라고 하고 “무조건 내림”은 영어로 round-down이라고 합니다. round라는 단어가 들어 있지만 “무조건 내림”과 “무조건 올림”은 반올림이 아닙니다. 반만 올리는 것이 아니라 그냥 올리고 내리는 것이지요.

그리고 사사오입 반올림의 영문 표현이 away from zero인데 뜻을 보면 5를 0에서 멀어지게 하는 것이라서 반올림이라고 표현하는 것에 무리가 있다고 합니다. 반면 half to even 방식은 짝수방향으로 반을 올려주거나 절사하기 때문에 이것이 진짜 반올림 방식 중 하나입니다.

하지만 이미 관행으로 다들 사사오입을 반올림이라고 말하기 때문에 편의상 여기에서도 모두 합쳐서 다 “반올림”이라고 하겠습니다.

뱅커스 라운딩을 사용하는 이유

계산과정에서 반올림 때문에 발생하는 오차를 줄이기 위해서 고안된 것입니다. 반복계산을 하면서 반올림이 계속 반복되면 결국 오차를 만들게 되는데 반복 계산 후 최종 결과에서 이 반올림들에 의해 발생하는 오차를 줄이도록 하려는 것입니다.

숫자 0과 1이 있습니다. 이 사이에 존재하는 소숫점 첫째자리까지의 수만 보면 다음과 같이 9개의 숫자가 있습니다. 10개가 아닙니다.

0.10.20.30.40.50.60.70.80.9

이 숫자들을 다 반올림한다고 할 때 0.5는 정확하게 한가운데 있기 때문에 절사해서 버릴 것인지 1로 올려줄 것인지가 고민이 됩니다. 그리고 어느쪽으로 하든 오차를 만듭니다. 사사오입 방식은 5를 항상 위로 올리기 때문(away from zero)에 여기서 숫자가 원래 올리지 않았을 때 보다 오차가 커지는 일이 많아집니다. 그리고 잘 생각해 보면 어딘가 공평하지 않은 구석이 있다는 것을 느낄 수 있습니다.

대신 뱅커스 라운딩처럼 짝수쪽으로 수렴하게 해서 조금은 더 공평해집니다. 그리고 이 방식이 오차가 덜 발생한다는 것은 오래전에 여러가지 방법과 실험을 통해 증명되었다고 합니다.

그외의 반올림 방식

위키피디아의 rounding 페이지를 보면 반올림(rounding)방식이 상당히 많다는 것을 보고 놀랄 수 있습니다. 반올림 문제는 메소포타미아에도 기록이 남아 있는 오래된 문제라고 되어 있습니다. 그리고 뱅커스 라운딩이라고 불리는 half to even 방식은 1940년도 나온 것이라고 적혀 있습니다. 오래되었죠.

위키피디아: https://en.wikipedia.org/wiki/Rounding

반올림 비교표

너무 많은 round를 알 필요는 없겠지만 대략 아래와 같은 것이 있습니다.

round 함수의 방식 차이로 인한 정합성 문제

뱅커스 라운딩을 기본으로 채택해서 제공하는 컴퓨터 언어나 소프트웨어가 생각보다 좀 많습니다.

R, Python3과 같은 것들이 그렇습니다. 그 외의 랭귀지도 꽤 많습니다. Excel과 RDBMS 같은 소프트웨어의 반올림 함수는 대부분 우리가 아는 “사사오입”으로 되어 있습니다. 그러다보니 행수가 많은 데이터에서 나누기, 곱하기 같은 것들이 여러번 반복하고 그 결과를 모두 합한다거나 평균을 구한다거나 하면 동일한 데이터를 가지고 계산을 해도 사용하는 컴퓨터 언어나 툴에 따라 양쪽의 결과값에 미묘한 차이가 발생합니다.

즉, round함수의 방식이 다른 것을 각각 따로 어떤 데이터의 사칙 연산을 하면서 반올림이 섞인 계산을 반복하는 경우에는 양쪽에서 똑같이 계산해도 round의 방식으로 인해 서로 결과값이 안맞는 문제가 발생합니다.
이때 정합성 오류가 부동소숫점 연산 문제나 반올림 방식의 차이로 인한 문제라는 것을 알면 그것은 해결하기도 어렵고 원인을 알면 오차를 감수하고 넘어갈 수도 있지만, 그것을 모르면 오차가 어디서 발생했는지 원인를 찾기 위해서 시간을 허비하게 됩니다.

버그인지 계산을 잘못한 것인지…

그래서 차이가 있다는 것을 알고 있는 것이 좋습니다.
물론 뱅커스 라운딩을 기본으로 채택한 것들은 별도로 사사오입을 지원하는 함수를 따로 제공하는 것이 많습니다. (아닌 것도 있는데 그럴 때는 구현해야 합니다)

컴퓨터 언어, 소프트웨어의 기본 반올림 방식

직접 몇 개를 확인해 봤습니다. 결과는 아래 테이블에 있습니다.

언어/소프트웨어방식
Linux shell (printf)뱅커스 라운딩
R뱅커스 라운딩
Python2사사오입
Python3뱅커스 라운딩
C/C++사사오입
Object-C사사오입
C#뱅커스 라운딩
Visual Basic뱅커스 라운딩
Go사사오입
Ruby사사오입
Scala사사오입
PHP사사오입
Julia뱅커스 라운딩
Javascript사사오입
Java사사오입
Erlang사사오입
Pascal뱅커스 라운딩
Cobol뱅커스 라운딩 (기본으로 되어 있습니다. 변경 가능해요)
Fortran사사오입
Excel사사오입
Google Spread Sheet사사오입
MySQL사사오입
Hive사사오입
Redshift (PostgreSQL?)사사오입
BigQuery사사오입
Oracle사사오입
SQLite사사오입
Matlab사사오입
Mathematica뱅커스 라운딩
WolframAlpha뱅커스 라운딩 (매쓰메티카와 같은 언어를 쓰므로)
Tableau사사오입 (시각화 도구는 역시 짤 없습니다)

정리하면

  • Linux에 있는 printf뱅커스 라운딩 (리눅스 코맨드마다 다를 수도 있겠지만 이것만 확인했어요)
  • Java 계열사사오입
  • 닷넷(.net) 계열뱅커스 라운딩 (.net이 아닌 MFC를 확인 안해봤습니다. 귀찮아요)
  • 데이터에 중점을 둔 것들은 사사오입
  • 과학, 공학에 중점을 둔 것은 뱅커스 라운딩
  • 함수형 언어뱅커스 라운딩
  • 시스템 개발에 중점을 둔 언어는 사사오입
  • Python은 2에서 3으로 바뀔 때 뱅커스 라운딩을 기본으로 바꿈
  • 시각화 도구는 DB에서 데이터를 끌어와서 표현하는 일이 많기 때문에 DB와 같은 방식을 사용

그리고 매우 오래전부터 사용해온 소프트웨어들은 일관성과 변경한 후 달라질 정합성으로 인해 별도로 뱅커스 라운딩 함수를 사용할 수 있게 제공하고 기본 함수의 방식을 바꾸지는 않는 것 같습니다.

하지만 뱅커스 라운딩이 더 권고되는 표준이기 때문에 새로 만들어지는 것들은 뱅커스 라운딩을 지원해야 한다고 하는 사람이 많습니다.

데이터베이스의 경우에는 잘 쓰고 있는데 어느날 업그레이드를 하고 나서 계산값이 달라지거나 합계를 했는데 총합이 달라지거나 하게 되면 문제가 커질 수도 있을 것입니다.

반올림의 인해 엄청난 문제가 발생하는 경우는 일상 생활에 별로 없겠습니다. 하지만 수능점수같은 것은 반올림 문제로 학생의 인생이 바뀔 수도 있어서 매우 골치가 아플것 같습니다. 작은 차이가 큰 문제를 만드는 경우도 있습니다.

뭘 하시든지 정밀한 수치 확인이 필요한 작업을 혹시 하게 되는 경우를 위해서 알아두면 좋을 것 같습니다.

Interpolation methods – 내간법

Interpolation methods (내간법)

용어 확인을 위해서 영어사전을 찾아 보시면 내간법/내삽법/보간법이라고 나옵니다.   뭔가 다소 괴기스러운 어감인데 (^^;) 보신적이 없다면 어감상으로는 뭔가 내부에서 간섭을 하거나 삽입하는 어떤것들이 연상될 것 같습니다.

내삽법 관련된 알고리즘을 찾다가 다시 당분간 이쪽분야를 할 일이 없어질 것 같아서 전에 찾아놓은 자료를 우선 아는데까지만 적어 놓으려고 합니다.
그래서 그냥 찾아 놓은 기법들 소개 정도입니다.

Interpolation(내간법)이라는 용어를 흔히 볼 수 있는 곳은

  1. 스크립트 랭귀지같은 것들중에 변수명을 문자열에 삽입해서 대치시키는 것.

    이것은 coercing 이라고도 하는데 용어가 좀 다양하게 쓰입니다. “blah $varialbe blah” 요런거입니다. PHP, Perl등의 언어에서 쉽게 볼 수 있는데 별로 중요하지 않습니다.

  2. 데이터 분석에서 관측되지 않은 지점의 데이터를 추정하는 방법

    당연히 이 포스트에서는 두번째입니다.

(아래 플롯 참조)

Ordinary Kriging

내간법은 관측치(Observation)가 없는 부분의 데이터를 관측치(Observation)를 이용해서 얼추 추정해서 때려 맞추는 것인데요. 대부분 현실적으로 관측을 모두 다 할 수 없어 중요한 부분만 관측하고 나머지는 추정을 해야 하는 경우에 쓰입니다.

세상은 우리의 상상만큼 그렇게 만만하지 않은 것 같아요. ^^

보통 공간통계(Geo-Spatial Analysis) 분야에서 쉽게 찾아 볼 수 있는데요.
활용에 대한 대략적인 예시는 이런 것들입니다.

  1. 전국의 모든 지점의 온도나 습도, 공기오염도 등을 다 측정할 수 없으므로 적당히 중간중간 중요한 지점을 측정하고 나머지는 보정해서 때려 맞출때

  2.  제조업등에서 불량 검사를 할 때 특정 판에서 온도 측정을 모두 할 수 없으므로 군데군데 하고 빈곳은 추정할 때

  3. 최근에는 IoT 스마트헬스케어 같은 곳에서 건물이나 집안의 온도나 습도에 대한 분포를 알고 싶은데 바닥에 센서를 죄다 깔아 놓을 수 없으니 적당한 곳만 측정하고 나머지는 때려 맞출때도 사용합니다.

    사실 이것 때문에 살펴보게 된 것입니다만 그래서 어떤 방법들이 있나 봤더니 굉장히 많더군요

Regression Model (회귀 모델)

회귀 모델도 내간법에 들어갑니다.

생각해보니 그러네요. 회귀 모델도 결국 관측치도 미관측 데이터를 추정하는 것이니 그쪽으로 보면 그 분류가 맞습니다.   단 공간분석에는 적합하지 않으니 쓰지 말라는 말도 있습니다. (물론 쓰는 사람들도 있습니다)

Kernel Density Estimation (커널밀도추정)

패턴 인식이나 기계 학습 책을 보셨거나 관련된 일을 하신다면 커브피팅(curve-fitting)이나 커널밀도추정에 대해서 보신적이 있을 텐데요.
이것도 내간법으로 넣습니다.
커널 밀도 추정은 다차원 공간에서 씨알(데이터)을 하나 이상 머금은 다차원 깍두기(커널)를 만들고 깍두기를 스무딩해서 매끄럽게 만들어 밀도를 추정하는 방법입니다.
보통 2차원, 3차원까지를 많이합니다. 히스토그램의 구체화된 형태라고 할 수 있습니다.   공간 분석에서도 사용하긴 하지만 많이 사용하지는 않는 것 같습니다.

Inverse Distance Weighted Interpolation

해석을 하면 많이 어색하지만 역거리내삽법 또는 거리 반비례 가중치 내삽법등으로 바꿀 수 있을텐데 보통 IDW라고 통칭합니다. GIS나 Geo-Spatial에서 흔히 볼 수 있는 내삽법입니다.   그냥 거리가 멀어질 수록 영향을 덜 받는다입니다.

Kriging (그리깅 격자법)

만든 사람이 이름이 Krige여서 Kriging라고 합니다.   크리깅 또는 그리깅이라고 읽는데 우리말의 김치의 ㄱ과 같은 발음인 것 같습니다. 이름도 이상하지만 이건 상당히 복잡한데요.   Spatial Analysis 책을 들여다보면 분산도(Variogram) 부터 공간자기상관(Spatial Autocorrelation) 같은 말부터 Semivariogram같은 비전문가에게는 무척 생소한 용어가 나오고 알고리즘을 따라 내려가다보면 결국 최적화 문제로 라그랑지 승법이 나옵니다.

성능이 굉장히 좋다고 알려져 있어서 대부분 GIS나 Geo-Spatial에서는 항상 언급이 됩니다. IDW보다는 수학적, 통계학적으로 기반 이론이 훨씬 그럴싸하기 때문에 굉장히 자주 사용하는데 역시 좋은 만큼 안쪽은 쉽게 설명하기에는 상당히 복잡합니다.

그리고 크리깅은 다시 Simple Kriging, Universal Kriging, Ordinary Kriging 등으로 나뉩니다.
보간법 중에는 Kriging이 끝판왕쯤 되는 것 같습니다.   추가로 크리깅은 예측값에 대한 에러를 추정하는 것이 가능하다고 되어 있습니다.  

조금 신기하네요. 요건 나중에 따로 정리를 시도해 보겠습니다. (너무 어려워서…)

보간법은 이외에도 무수히 많습니다. K-NN도 사용을 하구요 당췌 뭐가 뭔지 모를 정도로 많아서 혼란스러운데 역시 가끔은 다른 쪽에서는 뭘하고 있는지 살펴보는 것도 중요한 것 같습니다.

Cosine Similarity – 코사인 유사도

삼각함수와 선형대수학에 대한 기본적인 배경지식이 있다면 코사인 유사도는 이해하기 매우 쉽습니다.  그게 아니라면 처음에 개념을 잡는 것이 어려울 수 있습니다.  그렇다고해서 겁 낼 필요는 전혀 없습니다. 어마무지하게 어려운것이 아니라서 포기하지 않고 조금 신경쓰고 조금 시간을 쓰면 누구나 이해할 수 있는 것입니다.

이 글에 대해서

이 글은 조금 쉽게 풀어서 설명하려다 보니 내용이 조금(많이) 길게 되었습니다. 그러니 만약 이 글을 읽을 것이라면 시간적 여유가 있을 때 보시면 좋겠습니다.  보통 코사인 유사도는 교과서에서 매우 간단하게 설명하고 넘어가는데 그건 다 알고 있다는 가정에서 설명하기 때문입니다. 이것은 문제가 있는데 보는 사람은 모르기 때문에 교과서를 보는데 아는 것을 가정하고 간단하게 설명한다는 것은 매우 이상합니다.  어쨌든 그런 부분까지 쉽게 풀어서 쓰다 보니 글이 장황해 졌습니다. 제 탓입니다.

코사인유사도는 대체 뭘까?

200px-Dot_Product.svg

우선 개념(concept) 이해를 위해서 코사인유사도를 아주 짧게 정의해서 설명하면 이렇습니다.
두 벡터(Vector)의 사잇각을 구해서 유사도(Similarity)로 사용하는 것

혹시 벡터라는 용어에 울렁증이 있더라도 여기에서 포기하지마세요. 별거 아닙니다.

여기서 유사도를 구할 때 두 벡터 사이의 각을 코사인(Cosine)값으로 구해서 유사도값으로 사용하기 때문에 코사인 유사도(Cosine Similarity)라고 부릅니다. 더 줄여서 말하면  두 벡터의 사잇각을 코사인으로 구하면 되는 것입니다.

수포자라면 아직도 이 설명 자체로는 이해가 어렵겠습니다만 괜찮습니다. 좀더 읽어 보세요.

코사인이 나왔으니 말인데 코사인 외에도 삼각함수에서 늘 같이 딸려 나오는 사인(Sine)이나 탄젠트(Tangent)로 값을 계산했다면 아마 “사인 유사도”나 “탄젠트 유사도”로 불렀을 것입니다만, 굳이 코사인을 사용한 것은 이런 계산을 하는데 코사인값으로 계산하는 것이 더 쉽고 편하기 때문입니다. 코사인으로 계산하면 계산을 덜 해요. 그것 뿐입니다.

벡터의 유사도를 구하는 방법은 여러가지가 있습니다. 코사인 유사도는 그 중 하나입니다. 다른 것과는 다르게 코사인 유사도의 특징은 사잇각을 쓴다는 것입니다.

저 위에 설명을 위한 매우 간단한 삼각형 그림이 있습니다. 코사인 유사도를 설명하는 문서에서 예제로 많이 보여주는 매우 흔하고 유명한 그림입니다.
저 그림을 보고 설명하면 그림에서 A와 B는 유사도를 계산할 대상이 되는 두 벡터(vector, 또는 두개의 수열값 세트)이고 두 벡터의 A와 B의 사잇각 쎄타를 코사인으로 구하는 것이고 구해진 사잇각의 값을 코사인 유사도로 사용하는 것입니다.

여기에서 각이란 원점에서 각 벡터의 위치까지 선으로 이어서 선을 만든 다음 두 선의 각을 말하는 것입니다. 원점은 모든 좌표의 값이 0이 되는 곳입니다.  이건 수학시간에 배우셨지요?

벡터는 무엇인가?

이 지면에서 벡터까지 설명해야 하는 것은 너무 길어서 무리이겠지만 그래도 벡터에 대해 익숙하지 않은 분들을 위해서 먼저 벡터에 대해서 간단히 설명을 하고 넘어가겠습니다. 이미 잘 아신다면 당연히 이 부분은 건너 뛰어도 됩니다.

위의 그림에서 두 벡터는 2차원 벡터를 표현해 놓은 것입니다. 그림은 가로와 세로로 축이 2개있는 평면이니까요. 축이 2개라서 숫자도 2개씩입니다.
벡터는 2차원 이상의 고차원 벡터도 있습니다. 현실의 데이터는 대부분 수십차원에서 수백만차원까지 가는 고차원 벡터를 다루는 일이 더 많습니다.  숫자 2개가지고는 뭐 할 수 있는 것이 별로 없습니다. 정보량도 적구요. 고차원 벡터는 그림에서 보이는 x축, y축과 같은 축들이 더 많다고 생각하면 됩니다. z, l, m, n, … 등으로 말이지요.

벡터의 차원에 대해서 잠깐 설명하고 넘어가면 예를 만들어 보면 10차원 벡터는 아래와 같습니다.

10차원의 두 벡터의 예:

  • A = 1,2,3,4,5,6,7,8,9,10
  • B = 2,3,4,5,6,7,8,9,10,11

A와 B는 각각 수열(수의 나열)이고 각각 10개씩 숫자를 가지고 있으므로 둘 다 10차원의 벡터입니다. 앞서 말씀드렸듯이 10차원 벡터는 눈으로 볼 수 있게 시각적으로 표현할 수 없습니다. 삼각형이나 선으로 좌표축에 그릴 수 없습니다.

수학 수업에서 배우기도 하는데 배우셨더라도 아마 잊어버렸겠지만 3차원까지는 시각적으로 표현이 가능하지만 4차원부터는 인간의 눈으로 한 눈에 볼 수 있게 시각적으로 표현하는 것은 불가능합니다. 인간이 통제할 수 있는 차원이 3차원까지만 가능하기 때문입니다. 그 이상은 머리속으로 추상적으로만 연상(imagination)을 해야 합니다. 이건 아인슈타인도 못 그립니다.

어쨌든 10차원 보다 숫자들이 하나씩 더 있으면 11차원이고 1000개가 되면 1000차원입니다. 그냥 각 축에서 위치를 나타내는 숫자가 1000개 있으면 1000차원 벡터, 10000개면 10000차원 벡터입니다.

물론 여러 벡터가 있다면 각 벡터에서 숫자의 순서들은 서로 같은 의미를 가지는 것에서 가져온 숫자여야 합니다. 이것 마저 설명하면 매우 복잡해지니 여기서는 그냥 잊어버리셔도 됩니다.

2차원이든 100차원이든 1000차원이든 시각적으로 표현이 불가해도 코사인 유사도는 정해진 공식으로 구할 수 있고 구하는 방법도 간단합니다.

코사인 유사도의 용도

계산법을 보기전에 아마도 많은 분들이 궁금할 것이 “두 벡터의 유사도를 구해서 어디에 쓰는가?” 라는 것일텐데요. 용도를 알게 되면 이해하는 것이 더 쉽습니다.

그런데 그전에 또 먼저, 벡터의 유사도는 무엇인가?

용도를 설명하기 전에 유사도를 먼저 설명해야 합니다. 그 참 설명을 하기위해서 먼저 설명해야할 뭔가가 정말 많습니다만. 벡터의 유사도를 구하는 것은 비슷하다는 것을 어떻게 정의하냐에 따라 계산하는 방법이나 결과들이 마구 달라집니다. 우선 벡터는 그냥 숫자들의 묶음이라고 생각해보면 이것만으로는 무작정 비슷한지 아닌지를 알 수 없는 문제도 있습니다.

유사도를 직선거리(유클리디안 디스턴스; euclidean distance)로 구하거나 사잇각이 얼마나 좁은지를 계산해서 구하거나 하는 것이 가장 잘 알려진 것입니다.  사잇각을 계산해서 유사도를 구하는 것 중에 가장 잘 알려진 것이 코사인 유사도입니다.

또 고등학교 수학책을 보면 두 벡터의 내각을 구하는 것으로 코사인 유사도가 이미 나와있습니다.  아마도 배웠지만 잊어 버린 사람들이 많을 것입니다.

코사인 유사도의 용도

코사인 유사도는 대충 다음과 같은 구체적인 용도가 있습니다. 흔히 볼 수 있는 것들입니다.

  1. 검색 엔진에서 검색어(Query)와 문서(Document)의 유사도를 구해서 가장 유사도가 높은 것을 먼저 보여주기 위한 기본 랭킹 을 위한 알고리즘으로 사용됩니다.
  2. 텍스트마이닝에서 쓰입니다. 검색엔진과 텍스트마이닝이 상당히 관련이 있기 때문에 사실 1번과 관련성이 깊습니다. 텍스트 마이닝은 흔히 벡터 스페이스 모델(Vector Space Model)을 사용하고 TF-IDF(Term Frequency – Inverse Document Frequency)를 사용하는데 단어집합들 간의 유사도를 구하기 위해서 코사인 유사도를 사용하는 것이 빈번하게 나옵니다. 그래서 word2vec 같은 딥러닝 모델에서도 나옵니다.
  3. 그 외에도 다른 분석이나 수리 모형에서도 유사도를 구할 때 사용합니다. 가끔 나옵니다. 매우 빈번하게 사용하지는 않습니다.
  4. 클러스터링(Clustering, 군집화) . 군집화 모델에서 데이터 포인트를 서로 묶을 때 쓰이긴 합니다.

위의 예에 대해서 부연설명을 더 해보겠습니다. 역시 매우 장황하니 관심 없으시면 건너 뛰셔도 됩니다.

*위의 1번의 검색 랭킹의 문제*

검색엔진이나 텍스트 마이닝에서 주로 쓰이는 이유는 문서를 숫자로 표현하는 방법중에 가장 쉽고 잘 알려진 방법이 포함된 단어들의 출현 횟수를 세고 그걸 숫자로 만드는 것이기 때문입니다.

검색엔진에서 흔히 비교할 문서들은 검색엔진의 검색창에 입력한 질의어(query라고 합니다)와 검색엔진이 가지고 있는 문서들을 비교해서 가장 비슷한 것을 찾기 때문입니다. 여기서 코사인 유사도를 구하는 대상이 사용자가 입력한 질의어와 검색엔진이 가지고 있는 모든 문서들과의 쌍입니다. 그렇게 해서 코사인 유사도를 구해서 가장 유사도가 큰 것을 가장 위에 보여줍니다. (현재의 검색엔진은 이렇게 단순하게 작동하지 않습니다. 오해를 방지하기 위해서 적어둡니다).

이때 검색엔진이나 텍스트마이닝에서는 유사도를 비교할 때 단순히 단어의 출현횟수만을 가지고 문서를 수치데이터(벡터)로 바꾸지 않고 TFIDF라는 수치값을 계산해서 씁니다. 그래서 코사인유사도와TFIDF는 늘 쌍으로 같이 언급이 됩니다. 이건 나중에 기회가 되면 설명하겠습니다. (TFIDF에 대한 포스트를 참고하세요)

*위의 3번의 클러스터링에서의 문제*

클러스터링에서의 거리 계산은 모두 연산 자원(Computational Cost) 문제와 관련이 있습니다. 코사인 유사도 역시 그렇습니다.

유사도를 구하는 목적의 근본적인 목적이 AB와 유사한지 AC가 더 유사한지와 같은 상대적인 비교를 하기 위한 것입니다.

A와 B가 둘만 있다면 둘을 비교해서 둘이 얼마나 유사한지는 사실 알 수 없습니다.  알 필요도 없습니다.

예를들어 세상에 사람이 둘 만 남았다면 이 두 사람은 서로 가장 비슷하게 생긴 사람일까요? 아니면 서로 전혀 다른 사람일까요? 두가지 모두 해당되기도 하겠지만 실제는 이게 쓸모가 없습니다. 그냥 모르는 것입니다.

즉 A와B, C, …등등이 있으면 가장 유사한 것들끼리 묶어보거나 A와 가장 비슷한것을 B, C 와 같은 것 중에서 찾아서 고르는 경우가 대부분이기 때문입니다. 그래서 여러 개의 벡터를 대상으로 각각 서로 서로 쌍을 맺어 유사도를 구해서 가장 유사도가 높은 순으로 정렬해서 가까운 것 1개를 선택한다거나 여러개를 선택해서 여러가지 목적으로 사용하게 됩니다.

클러스터링을 할 때도 마찬가지겠지요 벡터의 개수 즉, 비교할 데이터가 n개고 벡터로 표현할 수 있다면 \frac{n \times (n-1) }{2}번 만큼 연산을 해야 합니다. RDMBS에 100개의 레코드가 있고 컬럼이 여러개 있는데 모두 숫자라면 각 레코드들 간의 유사도를 모두 구하면 \frac{100(100-1)}{2} 만큼 유사도값을 뽑아야 합니다. 에… 계산하면 4950번 입니다.

코사인 유사도를 위한 전제 조건

매우 기본이 되는 것이라 설명을 할 필요가 없겠지만 이왕 이 글이 너무 장황해진 김에 적어 보자면 다음과 같은 전제 조건이 있습니다.

  • 두 벡터의 원소들은 모두 양수(플러스!)여야 합니다. x, y 직교 좌표축에서 1사분면에 오는 것들입니다. (모눈종이에서 중심을 기준으로 오른쪽 위)
    그래서 원소들의 값이 음수가 되지 않는 문제에만 가져다 씁니다.
  • 벡터의 원소수는 같아야 합니다.
    너무 당연한 것입니다. 비교하는 벡터의 원소 갯수가 일치하지 않으면 각각 빠진 것을 0으로 채워서 동일하게 만들어야 합니다. 벡터의 원소 갯수가 좌표축에서의 축의 갯수이기 때문입니다.

코사인 유사도의 특징

평면 좌표에서 1사분면의 두 벡터의 코사인 값은 0 ~ 1 사이의 값입니다. 벡터의 각이 작을 수록 1에 가까워지고 클수록 0에 가까워집니다. 따라서 결과를 재가공(rescaling)하지 않고 바로 쓰기 편합니다. 두 벡터가 정확히 직교이면 값이 0이 됩니다.

삼각함수를 배울 때 이미 배우는 것이기 때문에 이걸 기억 하고 있다면 좋겠습니다만 생각하지 않는다면 다시 한 번 찾아보세요.

공식

공식입니다. 자세히 보지 마세요.

\text{similarity} = cos(\theta) = {A \cdot B \over |A| |B|} = \frac{ \sum\limits_{i=1}^{n}{A_i \times B_i} }{ \sqrt{\sum\limits_{i=1}^{n}{(A_i)^2}} \times \sqrt{\sum\limits_{i=1}^{n}{(B_i)^2}} }

아주 간단한 공식이고 고등학교 수학교과서에도 나옵니다. 공식은 매우 쉽기 때문에 한 번 이해를 하고 나면 볼 필요도 없습니다.

공식 풀이

공식을 가능한 자세히 설명을 적어 보겠습니다. 먼저 공식에서 분자 부분과 분모 부분을 나눠서 설명하면 다음과 같습니다.

분자 부분 – 벡터 내적 (vector inner product, dot product)

코사인 유사도 공식에서의 분자 부분은 벡터의 내적(dot product)을 구하는 것입니다. 영어로는 inner product(이너 프러덕) 또는 dot product(닷프러덕)이라고 흔히 말합니다.

\ll A \cdot B \gg 이 벡터의 내적(dot product) 표기입니다.
벡터의 내적은 계산이 매우 쉽습니다.
두 벡터의 각 원소들을 순서대로 짝맞춰서 곱한 다음에 결과들을 다 더하면 됩니다.

아래와 같은 두 벡터가 있다고 하겠습니다. 차원이 5차원인 2개의 벡터입니다.  요소가 5개이기 때문에 5차원입니다.  (외계인이 산다는 그 5차원이 아닙니다) 값은 현실의 예제가 아닌 제가 임의로 마구 넣은 것입니다.

A = (1,2,3,4,5)
B = (6,7,8,9,10)

  • 각각 짝을 지어 잘 곱합니다. 순서를 맞춰서 잘 해줍니다.
    1 \times 6 = 6
    2 \times 7 = 14
    3 \times 8 = 24
    4 \times 9 = 36
    5 \times 10 = 50
  • 곱한 것을 다 더합니다.
    6 + 14 + 24 + 36 + 50 = 130

위의 과정이 벡터의 내적을 구한 것입니다.
끝입니다. 너무 힘든 계산이었습니다. 썰렁한 농담입니다.

그런데 여기서 벡터의 내적이 왜 나오는지 궁금할 수 있습니다. 각을 구하는데 왜 저런게 필요한 것이지?  이것은 뒤에 설명하겠습니다.

분모 부분 – 두 벡터의 크기를 곱한다

분모 부분은 두 벡터의 크기를 각각 구해서 곱하면 됩니다.

|A|는 A벡터의 크기를 말합니다.
|B|는 B벡터의 크기를 말합니다.

분모는 두벡터의 크기를 구해서 곱하면 되는데요 벡터의 크기(norm 이라고 부릅니다)가 기억이 안나실 수 있는데요. 원점에서부터의 거리를 말하는데. 이건 기하학적으로 보면 사실 ‘피타고라스 정리‘에서 직각삼각형의 빗변을 구하는 것을 말합니다.

그냥 “피타고라스 정리를 이용해서 빗변을 구하는 것을 하면된다”는 말입니다.

그런데 2차원까지는 직각삼각형인데 3차원부터는 입체가 되고 4차원부터는 아예 모양을 상상도 할 수 없게 됩니다만 그래도 피타고라스 정리로 구할 수 있다고 수학자들이 증명을 이미 해놓았습니다. 믿고 쓰면 됩니다. 못 믿으시겠으면 직접 증명을 해보시면 됩니다.

자! 앞에서 설명했듯이 벡터의 길이는 피타고라스 정리를 사용하면 구할 수 있고 그걸로 2개의 값을 구해서 서로 곱하면 분모 부분은 완성됩니다.

직각삼각형의 빗변의 길이를 구하는 피타고라스 정리를 기억 못하면 매우 곤란합니다.

C=\sqrt{ A^2 + B^2 }

  • A벡터의 크기를 구합니다. 피타고라스 정리.

\sqrt{ 1^2 + 2^2 + 3^2 + 4^2 + 5^2 } = 7.4161984870957

  • B벡터의 크기를 구합니다. 피타고라스 정리.

\sqrt{6^2 + 7^2 + 8^2 + 9^2 + 10^2} = 18.1659021245849

  • 이제 마무리로 구한 것을 곱합니다

7.4161984870957 \times 18.1659021245849 = 134.7219358530751

숫자값들이 소숫점 뒤로 길게 나와서 복잡해 보이지만 별거 아닙니다. 뭐 계산은 계산기나 컴퓨터가 하는 거니까요.

마무리 계산 – 분자를 분모로 나누기

이제 다 구했으니 분자를 분모로 나눕니다.  나누기는 매우 힘든 산술계산이지만 우리에게는 계산기가 있습니다.

\frac{130}{134.7219358530751}=0.9649505

위에 계산된 결과 값이 코사인 유사도 값입니다. 약 0.96이네요.

풀어놓고 보니 별거 아닙니다.
R 코드로 풀어보면 이렇습니다.

R도 되지만 Pyhon이나 다른 언어들로도 당연히 계산이 됩니다.  엑셀도 됩니다. 그리고 위의 코드에도 나와 있지만 특별한 경우가 아니라면 굳이 계산식을 따로 코딩으로 구현할 필요는 없습니다. 대부분 소프트웨어 내에서 자체 제공하거나 컴퓨터 언어들의 추가 패키지, 라이브러리로 제공하고 있어서 매우 쉽게 계산이 가능합니다.

여기에서 벡터 내적은 왜 나오는 것일까?

200px-Dot_Product.svg

내적에서 무너질 분들이 좀 있을텐데요. 고교 수학에 분명 나옵니다. 기억 안나도 괜찮습니다. 어차피 이것도 설명할꺼니까요.

벡터의 내적은 검색을 해 보시면 자료가 많이 나올 것입니다. 수학적으로 매우 중요한 것 중 하나입니다.  특히 선형대수학은 벡터의 내적이 없으면 있으나 마나한 물건이 됩니다. 사실 코사인 유사도를 이해못하는 대부분의 이유는 내적을 이해하지 못하기 때문입니다.

위의 삼각형 그림을 다시 살펴보면 코사인 법칙은 피타고라스 정리에서 출발했기 때문에 코사인값을 구하려면 두 벡터가 만드는 내부의 도형이 직각삼각형이어야 합니다. 그런데 위의 그림을 보시면 A, B와 원점이 만드는 도형이 직각삼각형이 아닌 것을 알 수 있습니다. 그냥 삼각형입니다. 하다 보면 저런 삼각형이 운이 좋게 직각삼각형인 경우도 있겠지만 매우 드물고 요행으로 “직각삼각형이 될지어다!” 라고 바라는 것은 일반화된 해결책이 아니기 때문에 의미가 없습니다.

직각삼각형이 되는 것은 위의 그림에서는 |A|와 B와 원점으로 만든 삼각형입니다. 직각 표시 보이시죠? 그래서 직각삼각형으로 만들어서 피타고라스 정리에서 출발한 코사인 법칙으로 사잇각을 계산하려면 |A|의 길이를 알아내야만 합니다.

|A|의 길이를 알아내는 방법이 벡터의 내적을 이용하는 것입니다.

A와 B의 두 벡터가 있을 때 A와 B의 내적을 계산하면 B * |A| 또는 A * |B|를 구할 수 있습니다.

여기서 |A|는 A를 B의 벡터의 선상(또는 연장선상)으로 직교(직각)이 되게 그대로 내린(정사영 영어로는 projection 한다고 표현합니다) 곳과 원점까지의 거리입니다. |B|는 반대편으로 B를 정사영 한 것입니다.

B 곱하기 |A| = |B| 곱하기 A

정사영을 어느 쪽으로 하던지 상관없습니다. 두 값은 항상 동일합니다. 왜 동일한지까지 설명하려면 지면이 너무 많이 필요해서 생략하겠습니다. (곰곰히 생각해 보면 같을 수 밖에 없다는 것을 알 수 있습니다)

네. 두 벡터의 내적값은 항상 1개입니다. 어느 방향으로 구해도 똑 같습니다.

결국 두 벡터의 내적을 구해서 벡터 하나의 크기로 나누면 |A| 또는 |B|의 길이를 구할 수 있어서 저 상황에서 직각삼각형을 만들 수 있습니다. 더 정확하게 말하면 직각삼각형을 이루는 구성요소인 세 변을 모두 찾아 낼 수 있습니다.그러면 비로서 코사인값을 계산할 수 있게 됩니다.

간단한 요약

벡터의 내적은 왜 필요하냐?
두 벡터 사이에 있는 직각삼각형때문에요.
직각삼각형은 왜 나오냐?
코사인값을 구해야 해서요.
코사인값이 직각삼각형과 무슨 관계냐?
코사인법칙이 피타고라스 정리에서 나왔기 때문에요.

그래서 두 벡터가 유사한지 어떻게 알 수 있는가?

이름이 코사인 유사도이니 이것의 용도가 어떤것이 유사한지 아닌지를 확인하는  것이라는것은 유추할 수 있는데 두 개의 벡터만으로는 서로 유사한지 아닌지를 알기 어렵습니다. 아니 모릅니다.  유사한지 아닌지와 가까운지 먼지 판단하는 기준은 상대적인 것입니다. 물론 절대적인 기준값을 하나 정해놓고 유사하다 아니다를 결정하는데 사용해도 됩니다. 하지만 그 기준값을 또 직접 결정해서 만들어줘야하고 적당히 좋은 값을 정하기가 더 어렵습니다.

위에서 잠깐 설명했지만 코사인의 특징으로 두 벡터의 각이 호도법으로 0도가 되면 코사인 유사도값은 1이되고 호도법으로 각이 커질수록(90도에 가까워 질수록) 0에 가까워진다는 것입니다.  조금 풀어서 설명하면 코사인유사도가 0 또는 Inf가 되면 전혀 유사하지 않은 직교(orthogonal)가 되고 1이 되면 두 벡터의 원점으로부터의 방향이 완전히 겹치게 됩니다.  그런데 이것만으로는 유사한지 아닌지를 판단하기 어렵습니다. 호도법으로 45도 보다 각이 작으면 유사하다고 해야 할까요?

유사도는 상대적인 개념이기 때문에 벡터 2개로는 두 벡터가 유사한지 아닌지를 알기는 어렵습니다. 벡터가 최소 3개 이상은 있어야 합니다.

그래서 N개의 벡터가 있고 A라는 1개의 벡터가 있을때 A벡터와 가장 가까운 벡터를 N개 중에서 찾을 때 코사인 유사도를 사용해서 코사인 값이 가장 큰 것을 선택해서 사용합니다. 당연히 코사인값은 N번 계산해야 합니다.

A벡터가 상대적으로 가장 가까운 벡터는 어떤 것인가를 찾는 것입니다.

어째서 두 벡터의 직선 거리를 계산하지 않고 각도를 사용하는가?

두 벡터가 가까운지 아닌지를 찾는 방법중에 가장 쉬운 것이 직선거리를 계산하는 유클리디안 거리(Euclidean distance)입니다.  유클리디안 거리의 문제점은 각 축의 숫자값의 크기에 따라 영향을 크게 받는다는 것입니다.  축이 수량값을 나타내는 것이고 각축의 값들이 매우 큰 벡터들가 매우 적은 벡터들이 섞여 있다면 벡터의 성향보다는 양적수치가 비슷한 벡터끼리 가깝게 계산되는 경우가 많습니다.

물론 이것도 나름대로 의미가 있기 때문에 이 자체로 큰 문제가 있는 것은 아닙니다. 하지만 양적 크기가 차이 클 것이 뻔한 데이터들은 유클리디안 거리를 사용하면 대부분 문제가 있습니다.

적용하려는 데이터의 특징과 사용하는 사람의 의도에 맞는 것을 선택하면 되는 것입니다.

텍스트마이닝에서의 코사인 유사도

앞서에서도 잠깐 설명을 했지만 코사인 유사도는 텍스트 데이터(텍스트 마이닝)에 사용하는 경우가 많습니다.  물론 다른 곳에도 많이 쓰입니다만 자료를 찾아보면 눈에 쉽게 띄는 쪽은 텍스트 마이닝과 관련된 것 입니다. 텍스트에서 추출한 텀(term, 단어, 색인어)들의 빈도의 분포가 지수 스케일이기 때문에 벡터의 사잇각을 두고 비슷한 방향인지 아닌지를 보는 방법이고 이것이 비교적 합리적인 방법이기 때문입니다.

그리고 검색엔진에서 질의어로 본문을 찾아서 유사한 것을 찾는데 질의어와 본문이 가지고 있는 단어들의 빈도수 같은 것의 양적차이가 매우 크기 때문에 코사인 유사도가 유리합니다.

텍스트마이닝에서 코사인 유사도의 주의점

텍스트 데이터는 분량(데이터 사이즈)이 많기 때문에 코사인유사도 값을 구하려고 해도 현실에서는 컴퓨터 연산이 많이 소모되어서 하지 못하는 경우도 있습니다. 이런 작업을 하려면 사실은 대부분의 경우 분산 프로세싱을 수행해서 계산해야 합니다.  크기가 적당하다면 RDBMS를 사용하고 아니면 Hadoop이나 Spark같은 분산 컴퓨팅 환경(빅데이터 플랫폼)에서 작업해야 할 수도 있습니다.

Excel이나 R, Python으로는 계산하기에 너무 무거울 정도로 문서가 많고 그 상황에서도 코사인유사도 계산을 해야 한다면 코사인 유사도를 계산하는 과정을 완전히 이해 해두는 것이 나중에 코사인 유사도를 직접 구현해서 계산할 때를 위해서는 좋습니다.

요즘은 빅데이터 플랫폼들이 좋아서 기능을 기본 제공하는 경우도 많습니다.  그리고 어렵지 않게 구현할 수 있기 때문에 빅데이터 플랫폼으로 손쉽게 대량의 벡터들이나 텍스트데이터에서의 텀들의 유사도를 구할 수 있습니다.

텍스트 데이터를 가지고 코사인 유사도(Cosine Similarity)를 구해서 문서간의 유사도를 구하는 것은 다음 포스트에 해 보겠습니다.

코사인 유사도의 공식 유도?

코사인 유사도는 코사인 제2법칙에서 유도한 것이라고 되어 있고 실제로 유도가 됩니다. 여기서 유도하는 것은 설명하지 않겠습니다.  딱 한 번 해봤는데 기억도 안나고 하기 싫습니다. 재미 없습니다. 혹시 궁금하신 분은 자료를 찾아 보시면 그렇게 어렵지 않게 해볼 수 있습니다. 그런데 실제 응용에는 공식 유도가 크게 중요하지 않습니다.

TFIDF – Term Frequency Inverse Document Frequency