KNN(K-Nearest Neighbor) 알고리즘 - Python 예제

 

 

 

머신러닝 알고리즘들 중 가장 심플하고 이해하기 쉬운 알고리즘인 KNN에 대해 알아보겠습니다.

KNN은 최근접 이웃 알고리즘이라고도 합니다.

 

알고리즘의 이름 처럼 새로운 데이터를 입력 받았을 때 이 데이터와 가장 근접한 데이터들의 종류가 무엇인지 확인하고 많은 데이터의 종류로 분류하는 알고리즘입니다.

 

Classification의 대표적인 알고리즘으로 지도 학습(supervisor Learning)에 해당합니다.

KNN의 알고리즘의 정의와 Python으로 간단한 예제를 실행해볼게요.

 

1. KNN 알고리즘

 

 

 

KNN 알고리즘을 간단하게 정의 하자면 새로운 데이터와 기존 데이터들간 거리를 측정하고 가까운 데이터들의 종류가 무엇인지 확인하여 새로운 데이터의 종류를 판별하는 알고리즘입니다.

 

여기서 K는 인접한 데이터의 갯수를 의미합니다,

그래서 K=1, K=3 일때 측정되는 종류가 달라질 수 있는데 예시로 알아보겠습니다.

 

 

 

K가 1일때는 가장 가까운 데이터의 종류로 선택됩니다.

위 그림에서 세모가 새로운 데이터라면 가장 가까운 별로 분류 됩니다.

 

K가 3일때는 가장 가까운 데이터를 순서대로 뽑습니다.

위 그림에서는 세모랑 가장 가까운 3개의 종류를 뽑으면 동그라미2, 별1 됩니다.

동그라미가 2개로 가장 많기 때문에 세모는 동그라미가 됩니다.

 

K=1, K=3의 개수에 따라 예측이 달라지는 것을 확인할 수 있습니다. 

KNN 알고리즘은 K에 따라 결과가 달라지기 때문에 K를 정해주는 것이 가장 중요한 요소 입니다.

 

K를 너무 작게 설정 했을 경우 과적합의 우려 되며 K를 너무 크게 설정했을 경우 데이터 구조 파악이 어려습니다.

 

2. KNN Python 예제

KNN을 Python으로 실행하면서 이해하도록 하겠습니다.

 

총 3단계를 가지며 아래와 같습니다.

• 거리 계산하기
• 가장 근처에 있는 요소 뽑기
• 예측하기

우선 데이터 셋을 만들어 주세요

# Test distance function
# [x, y, type]
dataset = [[2.7810836,2.550537003,0],
	[1.465489372,2.362125076,0],
	[3.396561688,4.400293529,0],
	[1.38807019,1.850220317,0],
	[3.06407232,3.005305973,0],
	[7.627531214,2.759262235,1],
	[5.332441248,2.088626775,1],
	[6.922596716,1.77106367,1],
	[8.675418651,-0.242068655,1],
	[7.673756466,3.508563011,1]]

2-1 거리 계산하기

KNN의 거리를 구하는 공식은 유클리드 거리 공식을 사용합니다.

 

 

 

위 공식을 Python 함수로 나타내보겠습니다.

 

from math import sqrt

# calculate the Euclidean distance between two vectors
# row = [x, y, type]
def euclidean_distance(row1, row2):
	distance = 0.0
	for i in range(len(row1)-1):
		distance += (row1[i] - row2[i])**2
	return sqrt(distance)

위 함수는 유클리드 거리 공식을 사용하여 두 점사이에 거리를 구하는 공식입니다.

row에는 type까지 포함되어 있기 때문에 마지막 range는 포함하지 않고 계산합니다.

row0 = [3,3]
for row in dataset:
	distance = euclidean_distance(row0, row)
	print(distance)

이제 함수를 선언했으니 거리가 정상적으로 측정되는지 테스트 해봅니다.

row0은 새로들어온 데이터 이며 이 좌표와 DataSet에 있는 좌표간의 거리를 계산합니다.

2-2 가장 근처에 있는 요소 뽑기

# Locate the most similar neighbors
def get_neighbors(train, test_row, num_neighbors):
	distances = list()
	for train_row in train:
		dist = euclidean_distance(test_row, train_row)
		distances.append((train_row, dist))
	distances.sort(key=lambda tup: tup[1])
	neighbors = list()
	for i in range(num_neighbors):
		neighbors.append(distances[i][0])
	return neighbors

이제 가장 근처에 있는 요소를 뽑아보도록 하겠습니다.

train 변수는 데이터 셋, test_row는 측정하고자 하는 좌표, num_neighbors 변수가 K를 의미 합니다.

neighbors = get_neighbors(dataset, row0, 3)
for neighbor in neighbors:
	print(neighbor)

함수를 선언하고 위와 같이 테스트 하면 가장 가까운 3개의 좌표가 나오게 됩니다.

해당 테스트는 K=3일때 테스트 입니다.

이 리스트를 보면 아래와 같이 출력 됩니다.

[3.06407232, 3.005305973, 0]
[2.7810836, 2.550537003, 0]
[3.396561688, 4.400293529, 0]

이렇게 출력 된다는 것은 0 type이 3개 이므로 우리가 측정하고자 하는 값은 0 type이라는 것이죠.

이렇게 판단할 수 있는 예측 함수를 이제 만들어 주겠습니다.

2-3 예측하기

# Make a classification prediction with neighbors
def predict_classification(train, test_row, num_neighbors):
	neighbors = get_neighbors(train, test_row, num_neighbors)
	for neighbor in neighbors:
		print(neighbor)
	output_values = [row[-1] for row in neighbors]
	prediction = max(set(output_values), key=output_values.count)
	return prediction

이는 예측하는 함수로 마지막에 예측된 type을 출력해주는 함수 입니다.

row0 = [3,3,0]

prediction = predict_classification(dataset, row0, 3)
print('Expected %d, Got %d.' % (row0[-1], prediction))

함수를 실행하면 예측 값을 출력합니다.

Expected 0, Got 0.

만약에 다른 값을 넣으면 어떻게 출력 될까요.

row0 = [6,5,0]

row0을 변경하여 실행하면 아래와 같은 출력이 되는 것을 볼 수 있습니다.

[7.673756466, 3.508563011, 1]
[3.396561688, 4.400293529, 0]
[7.627531214, 2.759262235, 1]
Expected 0, Got 1.

가까운 type은 1이 많으므로 1로 예측하게 되죠.

 

 

참고 

https://machinelearningmastery.com/tutorial-to-implement-k-nearest-neighbors-in-python-from-scratch/