k-최근접 이웃(k-NN) 알고리즘으로 분류하기

기후 변화 패턴을 어떻게 분류할까?

전 세계 주요 도시들의 기후 데이터(온도, 강수량 등)를 분류하면 각 도시가 직면하고 있는 기후 변화를 파악하여 대응할 수 있습니다. 이번 시간에는 k-최근접 이웃(k-NN, k-Nearest Neighbors) 알고리즘의 수학적 원리와 분류 방법을 탐구해 봅니다.

k-NN 알고리즘과 유클리디언 거리

k-NN 알고리즘은 판별하고 싶은 데이터와 인접한 $k$개의 데이터를 찾아 데이터 간의 거리(distance)를 측정하여 다수결에 따라 새로운 데이터를 기존 클래스로 분류하는 방법입니다. 중요한 것은 새로운 데이터와 기존 데이터와의 거리를 측정하는 것이며, 이때 유클리디언 거리(Euclidean distance)가 주로 사용됩니다.

$\overline{PQ}=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$

예를 들어 $P(4,4)$, $Q(2,2)$ 사이의 유클리디언 거리는 $\overline{PQ}=\sqrt{(4-2)^2+(4-2)^2}=2\sqrt2$입니다.

k-NN 분류기 — k값에 따라 달라지는 분류

훈련 데이터는 노란 사각형, 파란 원의 클래스 2개로 나뉘어 있습니다. 새로운 테스트 데이터(★)가 어느 클래스에 속하는지, $k$값을 바꾸며 확인해 보세요.

교과서 확인 결과와 비교해 보세요 — $k=3$일 때 사각형 2개, 원 1개로 사각형으로 분류, $k=7$일 때 사각형 3개, 원 4개로 원으로 분류, $k=10$일 때는 사각형 5개, 원 5개로 분류할 수 없습니다 (동점).

해밍 거리로 재활용품 분류하기

이미지를 행렬로 변환한 뒤 해밍 거리를 이용하면 재활용품(페트병, 캔)을 분류할 수 있습니다. $l_1, l_2$가 서로 다른 페트병이고 $l_3$가 캔, $l_4$가 페트병이라고 합시다. 해밍 거리는 0에 가까울수록 유사도가 높습니다.

기준 페트병 이미지($l_1$)와 해밍 거리가 0에 가까운 것을 찾아 다른 페트병을 분류할 수 있습니다. 다만 크기가 다르거나 형태가 일부 왜곡된 이미지에서는 정확한 분류가 어렵고, 해밍 거리는 위치에 따른 차이만 고려하므로 이미지의 전체적인 차이를 비교하기는 어렵다는 한계가 있습니다.