k-Nearest Neighbors 알고리즘

기존의 데이터와 비교해서 입력이 들어왔을 때 이 입력 값이 기존의 데이터와 얼마만큼 연관 관계가 있느냐에 착안해서 만들어진 알고리즘.

입력 값이 들어왔을 경우 입력 값과 기존 데이터들과의 거리를 구하고, 가장 거리가 가까운 곳을 찾아서 비슷함을 찾아내는 방법이다.

말로는 설명하기 어려우니 코드로 이해하자.

처음 코드를 보면 createDataSet이란 함수를 통해 사전 데이터 집합을 생성하였다. 사전 데이터는 [1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]의 값을 가지는 데이터이며 각각 'A','A','B','B'의 Label을 가진다.

이렇게 데이터 셋을 생성한 후에, classify 함수를 호출하는데, classify 함수는 입력 데이터가 사전 데이터 셋과 비교하여 어떤 Label을 가지게 될지를 분류해주는 기능을 한다.

classify 함수에 대해 조금 더 자세히 살펴보자.

우선 사전 데이터 set 크기를 가져온 후에, 사전 데이터 set과 입력 값 과의 차이를 구한다. 예를 들어 사전 데이터가 [1.0, 1.1] 이고 입력 값이 [1.0, 1.0]이라면, 결과 값은 [0, 0.1]이 되는 것이다.

tile 함수를 쓴 이유는 dataSet과 동일한 크기의 array 행렬을 만들기 위해 사용되었으며, 위와 같은 경우에는 [[0, 0], [0, 0], [0, 0], [0, 0]]의 4x1의 행렬이 만들어진다.

이렇게 만들어진 행렬과 데이터 set의 차이 값을 구하고(diffMat), 구해진 diffMat를 2제곱을 한다.

2제곱 한 결과 행렬에 대해 각각을 더한다. (sqDiffMat.sum(axis = 1)) 그 후에 다시 0.5제곱을 곱하면 거리 값이 나타나게 된다.

글로는 엄청 어렵게 썼는데 결국은 거리 구하는 공식을 코딩으로 구현 한 것이다. 공식으로 하면 아래와 같다.

이제 구한 거리 값에 대하여 작은 순서대로 sorting을 해준다.

가장 가까운 거리부터 해서 어느 정도 까지 루프를 돌려서 가장 많이 나온 Label을 찾아야 한다.

그에 해당하는 부분이 for문과 그 아래의 코드 부분이다.

이렇게 해서 나온 Label 결과가 입력 값에 대해 가장 가까운 Label이다. 입력 값이 어떤 값이 들어왔는지는 확실히 알 수가 없지만 대략 가장 가까운 거리에 있는 Label과 비슷한 값이라고 추측을 해볼 수가 있다.

위에서 설명한 방법이 가장 단순화시킨 kNN 알고리즘이라고 할 수 있다. 

실제 시스템에 적용하기 위해서는 저렇게 실데이터 값을 집어넣어서 거리를 구하기 보다는 정규화 과정등을 거치는 것이 더 효율적이다.

두 속성간의 비교 연산을 통한 결과 값을 구하는 것이기 때문에 속성 간의 값 차이가 크게 나버리면 정확도가 떨어지기 때문이다.

가령 두 속성 값이 (100000, 0.1), (40, 0.9) 를 나타낸다고 가정할 시에 0.1과 0.9의 차이가 아무리 크게 나더라도 100000과 40 사이에 끼치는 영향의 효과가 더 크기 때문에 0.1과 0.9 차이는 묻혀져 버리게 된다.

이를 피하기 위해 거리를 구하기 전에 값의 정규화 작업은 필수적으로 이루어져야 한다.

정규화작업은 대부분 아래와 같은 방식으로 이루어 진다.

(value - min)/ (max - min)

여기서 min, max는 각 속성이 가지고 있는 값 내에서의 최소값, 최대값을 나타낸다.

예를들어 사람1에 해당하는 속성 값이 (1, 100, 0.1)이고 사람2에 해당하는 속성 값이 (5, 300, 0.5), 사람3이 (10, 200, 0.3)일 경우, 첫 번째 속성에 대한 min max는 1, 10, 두 번째 속성에 대한 min max는 100, 300, 세 번째 속성에 대한 min max는 0.1, 0.5가 되는 것이다.