[Data Mining] kNN Classification

Classification을 공부해보자. Classification은 말 그대로 분류를 하는 model을 만드는 것이다. 이전 포스팅에서 설명한 logistic regression은 binary값을 분류하는데 사용되었다. 그래서 마지막에 logistic regression은 사람에 따라서 Classification으로 분류하는 사람도 있다고 말했다. 이번엔 진짜 Classification을 공부해보자

아래와 같이 data가 마구자비로 분산되어 있다고 가정해보자.

일부러 x, y축은 안 그렸다. 왜냐하면 x, y 축을 그려버리면 2차원으로 보일테니까. 위의 각 하나의 점은 n dimension이다. 즉, (1,2)와 같은 2 dimensional data도 될 수 있지만, (1,2,3,4,5)와 같은 5 dimensional data도 될 수 있다는 것을 나타내고 싶어서 x, y축을 그리지 않았다. 이번 data는 가령 5 dimensional data이고 4개의 attribute은 numeric data, 나머지 하나는 nominal data라고 가정해보자. 예를 들어 아래와 같은 data들이라고 가정해보자.

(1,4,3,6,'a')

(4,8,3,1,'b')

(6,8,11,3,'c')

(6,5,8,3,'a')

....

(마지막 attribute은 class attribute이라고 부르고 'a', 'b', 'c' 중 하나라고 하자.)

kNN classification은 k개의 가장 가까운 data를 기반으로 예측을 하는 것이다. 데이터가 몰려있으면 그 몰려있는 그룹끼리 비슷한 특징을 지닐 것이라고 가정했기 때문이다. 우선 k=3으로 가정하고 아래의 data를 다시 봐보자.

뭐지... 별로 쓰지도 않았는데, 왠지 포스팅 다 한 것 같은 이 기분은... 음 아무튼 위의 그림을 다시 한번 보자. 빨간 점과 가장 가까운 세 개의 data가 원으로 묶여있다. 그 세 개의 data는 각각 'a', 'a', 'b'인데, 이것을 바탕으로 빨간점의 class attribute은 'a'일 것이다. 라고 추측하는 것이다.

그런데 여기서 궁금한 점이 생길 것이다. 가장 가까운 점을 어떻게 구할까? 거리를 구하는 공식에는 여러가지가 있다.

Hammington distance

Manhattan distance

Euclidean distance

여기서는 Euclidean distance로 거리를 측증하려고 한다. Euclidean distance는 우리가 가장 잘 아는 거리 계산법이다. 예를 들어, (0,0)과 (3,4)의 거리는 아래와 같다.

우리의 data set은 지금 4개의 numeric data를 가지고 있고 1개의 nominal data를 가지고 있다고 했다. 그 1개의 nominal data는 class attribute이고, 나머지 4개의 numeric data를 가지고 거리를 계산하면 된다. 가령 아래와 같이 계산 한다.

결국 거리 계산은 같은 방법으로 된다는 것을 알 수 있다. 아무튼 이러한 방법을 통해 우리는 빨간점에서 모든 데이터들간의 거리를 구한 후, 그것을 sorting하여 가장 가까운 k개, 여기서는 3개를 구하면 된다.(k=3으로 가정했으므로)

위의 그림을 다시 보면, 이제 뭐가 좀 더 자세히 보일 것이다. 빨간점을 기준으로 다른 점들과의 Euclidean distance를 이용하여 거리를 구한 후, 그 거리들을 Sorting하여 가장 가까운 k개(3개)를 구한 것이다.

여기서 Classification의 전제를 하나 설명해보자. Classification을 돌릴 때는 기본적으로 training set과 test set으로 나눈 후 돌리게 되어있다. 무슨 말이냐하면... 기본적으로 training set을 통해서 배우고 test set로 검사를 한다는 것이다. 예를 들어 아래와 같다.

세보면 알겠지만, training set은 29개이고 test set은 15개이다. 비율이 대충 2:1이다. 그렇다. 일반적으로!! 하나의 data set을 66%의 training set과 34%의 test set으로 나눈다. training set과 test set을 나누는 또 다른 방법으로 k fold cross validation이라는 방법도 있는데 이 방법은 나중에 설명하도록 하자.(어려운건 아니다. 그냥 지금 설명하기 귀찮을 뿐)

위의 training set과 test set을 통해서 kNN classification을 돌린다는 말은 무엇이냐면..

test set의 data 하나를 골라서 training data들과의 거리를 구한다.(Euclidean distance) 그것들을 Sorting하여 가장 가까운 k개의 점을 구한 후, 그 k개가 가지고 있는 class attribute 숫자를 세서 많은 쪽의 attribute value로 test set data 하나를 예측하는 것이다. 이 과정을 15개의 test set에 대하여 반복하여 값을 비교한다. 예를 들어 아래와 같이 계산한다.

test1 data로부터 10개의 training data들까지의 거리

test2 data로부터 10개의 training data들까지의 거리

test3 data로부터 10개의 training data들까지의 거리

를 모두 구하고

test1에서 가장 적은 distance 3개 구하고 class attribute 비교한다. (a 1개, c2개)

test2에서 가장 적은 distance 3개 구하고 class attribute 비교한다. (a 1개, c2개)

test3에서 가장 적은 distance 3개 구하고 class attribute 비교한다. (a 2개, c1개)

따라서,

test1은 c로 추측하고

test2는 c로 추측하고

test3은 a로 추측한다.

실제 test1, test2, test3의 class attribute과 비교해보자.

위의 경우에는 kNN Classification을 적용했을 경우, test set 3개 중에서 하나 밖에 안 맞았다는 결론이 나온다. 위의 엑셀 데이터는 그냥 랜덤으로 아무 값이나 체워넣은 것이기 때문에 맞을 확률이 별로 없다는 것을 참고하길 바란다.(1/3맞았으니 확률 상 맞긴 하네)

지금까지 kNN classification을 설명했다. 이것을 실제 data에 적용해보자. data set은 iris data set으로 매우 매우 유명한 data set이다.(구글 검색으로 아주 쉽게 구할 수 있다.) 이 data set은 4개의 numeric data와 1개의 nominal data로 이루어져있고, nominal data는 Iris-setosa, Iris-virginica, Iris-versicolor 셋 중에 하나이다. 4개의 numeric data를 통해 nominal data를 예측해보자. training data set은 전체의 67%로 잡고 나머지는 test data set으로 잡자.

python을 통해 위의 코드를 구현하여 accuracy를 구하면 다음과 같이 매우 좋은 accuracy를 구할 수 있다.

코드 구현은 여기를 참고하자.

참고 : http://......

다음 포스팅에서는 classification을 측정할 때 어떤 식으로 측정을 하는지 무엇이 중요한지 알아보고자 한다.