KNN / k-NN / k-Nearest Neighber / k-최근접 이웃 알고리즘

KNN / k-NN / k-Nearest Neighber / k-최근접 이웃 알고리즘

지도학습 중 분류 문제에 사용하는 알고리즘이다.

분류 문제란 새로운 데이터가 들어왔을 때 기존 데이터의 그룹 중 어떤 그룹에 속하는지를 분류하는 문제를 말한다.

k-NN은 새로 들어온 "★은 ■ 그룹의 데이터와 가장 가까우니 ★은 ■ 그룹이다." 라고 분류하는 알고리즘이다.

여기서 k의 역할은 몇 번째로 가까운 데이터까지 살펴볼 것인가를 정한 숫자이다.

(1) k-NN의 원리

더 구체적인 예를 들어보자. 아래와 같이 6개의 기존 데이터 A~F와 1개의 신규 데이터 N이 있다고 하자.

          

만약에 k = 1 이라면, 

거리가 1번째로 가까운 C만을 보고 신규 데이터를 분류한다. 따라서 N은 C와 같은 그룹인 ●로 분류된다.

만약에 k = 3 이라면,

거리가 3번째로 가까운 C, D, E까지 보고 신규 데이터를 분류한다. 이때 그룹이 갈리면 다수결의 원칙에 따른다.

여기서는 1 : 2가 되어 N은 ▲로 분류된다.

만약에 k = 5 라면,

거리가 5번째로 가까운 C, D, E, B, A까지 보고 신규 데이터를 분류한다. 여기서는 3 : 2가 되어 N은 ●로 분류된다.

이처럼 같은 데이터임에도 k가 얼마냐에 따라 N이 ●로 분류되기도 하고 ▲로 분류되기도 한다.

그만큼 적절한 k를 정해주는 게 중요하다.

(2) 거리척도의 단위문제 - 표준화 (유클리드 거리)

k를 정하기 전에 선행되어야 하는 작업이 있다. 바로 표준화.

k-NN에서 가깝다는 개념은 유클리드 거리(Euclidean Distance)로 정의하는데, 유클리드 거리를 계산할 때는 단위가 매우 중요하다.

-

-

일단 유클리드의 거리는 아래와 같이 계산한다.

예를 들어 앞에서 다뤘던 데이터에서 y좌표의 단위가 달러($)였다고 가정하자.

이때 A-N 간의 유클리드 거리는 3.162 이고 B-N 간의 유클리드 거리는 2.828 로, B가 더 가깝다.

그런데 만약에 y좌표의 단위가 원(￦)으로 바뀌었다고 가정하자. 1달러 = 1,000원이라고 한다면 그래프가 아래처럼 바뀔 것이다.

이때 A-N 간의 유클리드 거리는 1000.004 이고 B-N 간의 유클리드 거리는 2000.001 로, A가 더 가깝다.

이렇게 변수별 단위가 무엇이냐에 따라 거리가 달라지고, 가까운 순서도 달라진다.

순서가 달라지면 k-NN에서의 분류 결과도 달라진다는 뜻이다. 그래서 반드시 k-NN 알고리즘을 적용할 때에는 데이터에 표준화를 해주어야 한다.

(3) 최적의 k 찾기

그럼 다시 돌아와서, 최적의 k는 어떻게 찾는지 알아보자.

간단히 말하자면 Train Data를 기준으로 Validation Data를 잘 분류하는 k가 얼마인지 확인해서 정하면 된다.

▼ Validation Data에 대한 설명은 아래 포스팅을 참고하자! ▼

2017/03/14 - [Analysis/R] - Train vs. Validation vs. Test Data

최적의 k를 찾는 예시는 R 코드와 병행해서 보여주는 것이 좋을 것 같아서 별도로 포스팅 하겠다.

▼ k-NN R 예제 코드 ▼

2017/03/15 - [Analysis/R] - [R 예제 코드] KNN / k-NN / k-Nearest Neighber / k-최근접 이웃

#Algorithm#Analysis#bigdata#classification#crossvalidation#data#k-nn#knn#k최근접이웃#optimalk#r#rstudio#거리척도#단위문제#데이터분석#분류#분류문제#분석#빅데이터분석#알고리즘#유클리드#유클리디안#지도학습#최적의k#표준화