[컴][알고리즘] KNN

machine-learning / 머신러닝 / 알고리즘 / machine learning / ai /

k nearest neighbors classification(KNN)

어떻게 분류하는가?

이 KNN 을 우리말로 번역하면, "K개의 가장 가까운 이웃들" 정도가 되겠다.  일단 claaification 이라는 것은 "분류"를 이야기한다. 그러니까 KNN 은 분류를 하는 방법중 하나이다.

어떤 input(입력) 이 있을 때 KNN 이 어떻게 분류를 하냐면, "input 에 대해서 거리가 가장 가까운 이웃 k개의 모습을 확인하고, 그중에 가장많은 모습으로 input 의 모습을 결정(classify)"하는 것이다. "끼리끼리 노는 느낌"이라고 보면된다.

아래 그림에서 input (녹색) 을 보자. k=3 이면, input 은 "빨강" 이 되는 것이고, k=5 이면 input 은 "파랑" 이 되는 것이다.

• k=3 일 때:  "빨강 2개" , "파랑 1개" --> input 은 빨강
• k=5 일 때:  "빨강 2개" , "파랑 3개" --> input 은 파랑

from : ref. 2

거리, distance

이제 대략적으로 KNN 이 무엇인지는 알았다. 그럼 이제 좀 더 자세하게 보자.

위에서
"input 이 들어왔을 때 input 에서 거리가 가장 가까운 녀석 k개를 보고 분류(claasify) 를 한다"
고 했다. 그럼 여기서 문제는 "거리가 가장 가까운 녀석" 에서 "거리" 이다.

이 "거리" 를 측정하는 방법에 따라서 input 에 대해 3번째로 가까울 수도 있고, 1번째로 가까운 녀석이 될 수도 있다.

ref. 1 에 보면 이런 거리를 측정하는 방법 몇가지를 소개해 주고 있다.

from : ref. 1

위의 거리를 측정하는 방법 3개는 "연속적인 변수들"(continuous variables) 에서만 유효하다고 한다. categorical variables 에서는 Hamming distance 를 사용해야 한다고 한다.

이것은 또한 data set 에 숫자형 변수(numerical variables)들과 범주형 변수(categorical variables)들이 섞여있을 때 0과 1사이의 숫자형 변수들에 대한 표준화문제를 가져온다. (얘기가 어려운데 이 부분은 아래 "distance 의 표준화" 부분을 보자.)

from : ref. 1

적절한 K 값

이제 거리에 대한 정의도 되었다. 그러면 이제 k 값을 정해서 그냥 사용하면 된다. 여기서 누군가는 그럼 k 값은 얼마로 정해야 하지? 라고 물을지 모르겠다.

사실 이것은 상황에 따라 다르다. 그렇지 않으면 왜 굳이 K개를 선택하게 했겠는가? 그냥 값을 정해서 알고리즘을 만들었을 것이다.

하지만 어느정도 사람들이 사용을 해보니, 어느정도의 결론이 나왔다. 그 이야기가 ref. 1에 있다. 대략적으로 정리를 하면,

• K값이 클수록 평균적인 잡음(noise) 를 제거해 준다면, 일반적으로 큰 K 값이 좀 더 정확한 결과를 가져다 준다.
• cross-validation 이 좋은 K 값을 결정하는 다른 방법이다. (?)
• 역사적으로 대부분의 dataset 에서 가장 적절한 K(optimal K) 는 3~10 사이의 값이다. 이 것이 k=1 보다는 훨씬 좋은 결과를 보여준다.

distance 의 표준화, standardized distance

거리를 계산할 때를 한 번 봐보자. 아래처럼 input(녹색) 에 대해 거리를 계산하게 될 텐데, 이 때 위에서 나온 함수중에 Euclidean(유클리디안) 을 이용한다고 생각해보자.

from : ref. 1

그럼 아래처럼 계산할 수 있다.

그런데 이때 문제는 '나이' 와 '대출' 의 범위가 다르다는 것이다. 그래서 숫자의 크기가 다르다. 위의 예제에서는 대출은 2십만이 넘어가는 숫자이지만, 나이는 70살이하이다. 숫자의 크기가 다르니, 거리값이 숫자가 큰 '대출' 의 값에 의해 결정될 여지가 많아지는 것이다.

그래서 이 문제를 해결하기 위해 값을 표준화(standardization, normalization) 을 해야 한다. 표준화는 그리 어렵지 않다. 아래처럼 해주면 된다.

무슨 뜻이냐 하면, 값 x 를 전체 값 대비해서 어느 위치에 있는 값인지로 변경하는 것이다.

이러면, 값의 범위(scale) 이 0 ~ 1 로 같아지게 되고, 어느 한 변수가 더 큰 영향을 미치는 경우를 막을 수 있다.

• scaling : x / (max-min) <--- 이것을 scaling 이라 한다.
• mean normalization : x - min  <---- 이것을 mean normalization 이라 한다.

References

1. KNN Classification
2. k-nearest neighbors algorithm - Wikipedia