[머신러닝] K-Nearest Neighbors

[머신러닝] K-Nearest Neighbors

    머신러닝, 인공지능은 사실 컴퓨터를 공부하는 사람이라면 누구든 한번쯤은 관심이 있어할만한 분야이다. 난 예전부터 터미네이터같은 것을 보면서 '스스로 발전시키는 컴퓨터' 혹은 '혼자 진화하는 것' 따위에 관심이 많았다. 뜬금없이 왠 머신러닝 포스팅이냐 라고 한다면, 그에대한 답변이 되었으면 좋길 바란다. 예전부터 관심이 있다는 것이었다 ㅎㅎ... 그 외에도 예전에 한번 겉핥기로 개발했었던 Chat-bot도 관심이 있는데, 이는 논문 스터디로 따로 포스팅 할 예정이다.

    Machine Learning in Action(피터 헤링턴 저, 김연진 옮김, 2009년) 이라는 책이 있다. 옛날에 관심이 생겨서 사두고, 읽어야지 읽어야지 하다가 지금까지 오게 된 책이다. 이 내용을 중심으로 포스팅을 진행 해 볼 계획이다. 관심이 있는 사람은 한번 사서 보아도 좋을 것 같다. 설명도 쉽고, 예제도 각 알고리즘별로 2개씩 있으며, Deep Learning이 아닌 다른 알고리즘들이 자세하게 설명되어있다는 점이 인상적이다. ( 사실 대학교 / 대학원에서 배우는 것이 더 좋을 수 있지만, 사정상 독학밖에 할 수 없어서 읽는 것이다. )

[ 사진1 - 한글 번역본도 있다. 가격은 30,000원이다. ]

1. K-NN 알고리즘

    그 중 첫 단원은 K-NN( k-Nearest Neighbor ) 이라는 알고리즘이다. 이 알고리즘은 "사례 기반 학습(instance-based learning)" 이라고 설명되어 있는데, 말 그대로 주어진 학습 데이터 집합의 사례를 바탕으로 Test, 혹은 모르는 사례를 예측하는 학습 방법을 의미한다. 정확도가 높고, 데이터에 가정을 두지 않는다는 장점이 있지만, 계산 비용과 메모리 요구가 높다는 단점이 있다.

    이 알고리즘은 "모든 데이터에 라벨(Label)을 붙여두고, 라벨이 없는 데이터가 들어왔을 때 그 데이터와 유사한 기존의 데이터 중 상위 K개 ( 보통 20개를 사용한다고 한다. ) 의 데이터를 다수결로 ( Majority vote ) 라벨을 정하는 알고리즘" 이라는 설명을 하고 있다. 유사도 측정에는 거리 측정 ( Euclidean Distance ) 방식을 사용한다.

2. 유사도 측정

    알고리즘의 내용은 딱히 어려운 것이 없는데, 유사도 측정에 사용하는 Euclidean Distance 라는 내용이 눈에 띈다. 이 방식은 사실 거리 측정이랑 다를 것이 없는데, 구하는 식은 다음과 같다.

• 2차원 평면 위의 점 A(x1, y1) 과 B(x2, y2)의 점이 있고, 이 두 점의 유사도를 Euclidean Distance로 구한다면 다음과 같이 쓸 수 있다.

 

• 이는 n 차원까지 발전 가능한데, n 차원에서의 2 점 A(a1, a2, ... an)과 B(b1, b2, ... bn) 의 Euclidean Distance는 다음과 같다. 

어려울 것 없는 식이다. 이 식의 값으로는 유사도가 아닌 거리가 나오게 되므로, 이 식의 값에 더하기 1을 한다음 역수를 취해서 0~1사이의 값으로 만들어 사용하게 된다.

    근데 이건 너무 간단한 식 아닌가? 아니라고 생각해도 나는 너무 간단해서 이 식으로 충분히 유사도를 비교 가능한지에 대해서 의문이 들었다. 검색 결과, 이 식 말고도 다른 유사도 비교 알고리즘이 2개가 더 나오게 되었는데, 피어슨 유사도 측정과 코사인 유사도 측정이 바로 그것이었다. 피어슨 유사도 측정은 지금 우리가 생각하는 두 지점 사이의 유사도 측정과는 조금 다른 이야기이므로 넘어가도록 하고, 코사인 유사도 측정을 이야기 해 보도록 하겠다.

    코사인 유사도 측정은 두 지점사이의 각도의 코사인 값을 이용해서, 두 지점사이의 각도가 얼마나 되는지 -1 ~ 1사이의 값으로, 두 지점이 같은 사분면 상에 있다면 0 ~ 1 의 값이 나오게 되게 하는 유사도 측정이다. 코사인 유사도 측정은 얼핏 보기에 그냥 거리만 측정하여 역수를 취하는 과정보다 어려워 보이므로, ( 더 있어보이므로 ) 좋아보이게 된다는 생각을 하게 되었는데, 자세히 생각해보면 조금 다른 이야기임을 알 수 있다.

    다음과 같은 점들을 생각해보도록 하자. :  A(X1, Y1), B(2X1, 2Y1), C(X2, Y2) 

[ 사진 2 - 유사도 그림 설명 ]

• 단, X2는 X1의 배수가 아니며, Y2도 Y1의 배수가 아니다. 

• X1, Y1은 0보다 큰 양수이다.

    이 때, A와 B, A와 C의 유클리디안 / 코사인 유사도를 각각 측정해본다면 어느정도 해결이 될 것이다. 간단하게 계산할 필요 없이, A와 B의 유클리디안 유사도는 0보다 크고, A와 C사이의 유클리디안 유사도도 0보다 클것이다. 그러나 A와 B의 사이의 각도는 0`이므로, 코사인 유사도는 cos 0 = 1, 즉, 동일하다는 결과가 나오게 되는 것이다. 이는 우리가 생각하는 유사도 측정이 아님을 알 수 있다.

   그럼 이런 단점을 가지게 될 수도 있는 코사인 유사도는 어디에서 쓰이는 것일까?

사실 코사인 유사도는 이런 단순한 유사도의 측정에 쓰이는 것이 아니라, 각 지점(Vector)의 크기(Magnitude)에 상관 없는 요소들의 유사도 측정에 쓰인다는 것이다. 예를 들면 더 이해가 쉬울 것이다. 

    

    각 문서의 단어들을 차원으로, 각 단어들의 빈도를 a1, a2, a3 ... an 이라고 해보자. 이 때, 임의의 문서 A가 있고, 임의의 문서 B는 그 문서 A를 Ctrl C + V 200번 한 값을 가진다고 해보자. 문서 A를 Vector로 표현한 점 A(a1, a2 ... an)과 문서 B를 Vector로 표현한 B(b1, b2 .. bn)는 B(200 * a1, 200 * a2 ... ) 와 동일하게 되고, A와 B 사이의 유사도를 측정하면 유클리디안 유사도는 매우 작게 ( 유사도가 작으므로, 두 문서는 유사하지 않다는 의미 ) 책정이 되지만, 코사인 유사도는 1로 동일하다는 결과가 나오게 될 것이다.

    문서가 단순 복사 + 붙여넣기 된 것은 물론 동일하다 / 유사하다 라는 결과가 나와야 하는 것이 옳으므로, 코사인 유사도를 사용하는 것이 옳다. 이렇게 각 Vector 요소들의 크기 차이에 크게 상관 없는 유사도 측정에는 코사인 유사도를, Vector 요소들의 크기 차이에 신경을 써야하는 유사도 측정에는 유클리디언 유사도를 쓰는 것이 옳다고 보인다. K-NN에 대한 예제는 다음 포스팅에서 계속 진행할것이다.

참조 ===============================================

https://cmry.github.io/notes/euclidean-v-cosine : 코사인과 유클리디언 유사도 비교.