K-Nearest Neighbors 최근접 이웃 알고리즘 정리 A-Z

주요 머신러닝 알고리즘에 대해서 하루에 하나씩 정도라도 복습겸 정리를 진행해보려 합니다 :))

특히 수학적, 통계적인 원리를 짚고 넘어가면서 이해를 확장시켜보겠습니다.

 

K-NN알고리즘이란?

분류/회귀에 사용되는 간단하면서 보편적으로 사용되는 모델

가장 가까운 K개의 샘플을 같은 클래스(분류)/ 이웃한 샘플들의 평균 값(회귀)으로 예측함

 

Source: Twitter

K-NN 모델을 생각하면 여기여기 모여라~~~ 가 생각나는데요

그만큼 서로 인접한 K개의 데이터를 묶거나 묶어서 평균내는 방법입니다.

 

Source: DataCamp

 

그러면 여기서 K는 몇개를 의미하지 ? 인접하다는 건 어떻게 판단하지? 라는 2가지 의문이 드는데요

 

첫번째 의문은 비교적 쉽게 대답이 가능합니다

 

1. K 는 default 값이 5개이지만 설정이 가능

• 일반적으로 홀수 사용
• 최적의 K 값은 일반적으로 3개-10개이나, 교차 검증 등을 통해서 K값 탐색 필요
• 실제 sklearn에서는 n_neighbors 에서 K개 이웃의 개수를 설정함

>>> from sklearn.neighbors import KNeighborsClassifier
>>> neigh = KNeighborsClassifier(n_neighbors=3)

---

 

2. '인접한 거리' 판단의 척도

 

여기서 하나 짚고 넘어갈 점은 '거리'를 계산하는 이유인데요, 데이터간의 거리가 가깝다는건 그만큼 데이터의 특성이

상당히 유사도(similarity)를 보인다는 것이기 때문에 머신러닝에서 거리개념을 사용합니다.

https://www.saedsayad.com/k_nearest_neighbors.htm

 

1. 연속형 데이터 - 유클리디안 거리(L2 거리)

 

유클리디안 거리(L2 거리)는 중학교때 배운 개념인데요, 피타고라스 정리를 기반으로 평면상에 두 점이 있을 때

아랫변의 길이의 제곱과 세로변의 길이를 제곱하고 루트를 씌우면 각 점의 직선거리 (대각선의 길이)가 도출됩니다

 

Source: https://euriion.com/?p=412115

 

2. 연속형 데이터 - 맨해튼 거리(L1 거리)

 

맨해튼 거리는 Taxi distance, L1 distance, TAxicab geometry로 불리기도 하는데요

공식은 각 점의 차이에 절댓값을 씌운 값의 합으로 거리간 절대값의 합으로 볼 수 있습니다.

Source: Researchgate

 

그림처럼 유클리디안 거리가 대각선 직선 거리를 구한다면 맨해튼 거리는 점에서 가로변 길이의 합 + 세로변 길이의 합을 

나타낸다고 볼 수 있습니다. 기하학적으로 2가지 개념을 나타내어 보겠습니다

 

https://datascience.stackexchange.com/questions/52501/coordinate-systems-influence-on-l-distances-manhattan-and-euclidean

 

기하학에서 원을 좌측 맨해튼 거리 개념으로 적용하면 좌측과 같은 모양이 되고

우측에는 일반적인 기하학 개념에서 원입니다. 즉 둘다 기하학적으로는 원을 의미하는데요

 

 

L2 유클리디안 개념 기반의 원 먼저 보겠습니다. 원의 개념 자체가 중심점에서 일정한 거리의 점들을 모아놓은 것을 의미하기 때문에 쉽게 이해가 가능합니다.  √((x - a)^2 + (y - b)^2) = r

 

이제 L1 맨해튼 거리 개념을 원의 공식으로 생각해보면 r 이라는 반지름 길이는

|x-a| + |x-b| = r 으로 나타낼 수 있겠죠! 이 공식을 그림으로 나타내면

45도 기울어진 사각형 모양의 원으로 그릴 수 있습니다

 

 

3. 연속형 데이터 - 민코우스키 거리

 

민코우스키 거리는 맨하탄과 유클리드의 거리 개념이 일반화된 형태로 구성되어 있습니다.

'일반화' 의 표현은 p값이 고정되어 있는 것이 아니라 1이상의 값으로 표현가능하다는 점입니다.

이  p값이 1이 되면 맨해튼거리, 2가 되면 유클리디안 거리로 표현됩니다

 

https://zetawiki.com/wiki/%EB%AF%BC%EC%BD%94%ED%94%84%EC%8A%A4%ED%82%A4_%EA%B1%B0%EB%A6%AC

 

 

4. 카테고리형 데이터 - 해밍거리 (Hamming Distance)

 

이 거리 척도 개념은 문자형 카테고리, True/Fasle 값 같은 데이터를 0,1 형태의 이진분류로 변환후에 사용가능합니다

 

https://www.saedsayad.com/k_nearest_neighbors.htm

 

위에 나와 있는 거리공식을 해석하자면 만약 데이터 값이 일치한다면 0, 데이터 값이 서로 다르면 1로 나타냅니다

예를 들어, 'abc' 와 'acd'가 있으면 두번째, 세번째 자리 데이터가 불일치하기 때문에 해밍거리는 2가되고

만약 'ttt' 'ttt'가 있으면 두가지 값이 일치하기 때문에 0이 됩니다

 

---

이론적인 측면을 알아봤으니 어떻게 사이킷런에서 사용할 수 있는지 보겠습니다.

 

sklearn.neighbors.KNeighborsClassifier

파라미터의 종류 및 기능을 알아보겠습니다.

n_neighbors : K개의 이웃

weights:  예측을 위한 데이터별 가중치 설정 (uniform-균일한 가중치,'distance'-가까운 거리에 더 큰 가중치 설정)

algorithm: 계산을 위한 알고리즘을 {‘auto’, ‘ball_tree’, ‘kd_tree’, ‘brute’} 중에 선택가능, default= 'auto'

leaf_size : Ball tree 와 KDTree 적용의 경우에 사용

p : 민코우스키 거리 공식에 있는 p로 default 가 2임에 따라 다른 설정 값이 없으면 유클리디안 거리가 사용됩니다

metric: 거리 측정 방법으로 default 가 minkowski입니다

 

>>> X = [[0], [1], [2], [3]]
>>> y = [0, 0, 1, 1]
>>> from sklearn.neighbors import KNeighborsClassifier
>>> neigh = KNeighborsClassifier(n_neighbors=3)
>>> neigh.fit(X, y)
KNeighborsClassifier(...)
>>> print(neigh.predict([[1.1]]))
[0]
>>> print(neigh.predict_proba([[0.9]]))
[[0.666... 0.333...]]

 

 

sklearn.neighbors.KNeighborsRegressor

파라미터는 분류모델과 동일하지만 반환되는 값이 거리기반으로

소속된 K개 데이터의 평균값이 반환되는 차이가 있습니다

 

>>> X = [[0], [1], [2], [3]]
>>> y = [0, 0, 1, 1]
>>> from sklearn.neighbors import KNeighborsRegressor
>>> neigh = KNeighborsRegressor(n_neighbors=2)
>>> neigh.fit(X, y)
KNeighborsRegressor(...)
>>> print(neigh.predict([[1.5]]))
[0.5]

 

---

KNeighbors 모델의 장단점

장점	단점
모델이 단순하고 직관적임	데이터 양이 많으면 처리 속도가 느림
수치 기반 데이터 분류시 성능 우수	하이퍼파라미터 K 선택이 중요함 (k가 크면 언더피팅, k가 너무 작으면 오버피팅 발생)
	데이터 스케일링 (표준화)가 필수적임

 

 

 

**추가 의견이나 개선사항이 있으면 알려주세요**

 

References

https://jangansinabro.wordpress.com/2019/03/24/%EC%8B%A4%EC%A0%9C-%EA%B1%B0%EB%A6%AC%EB%A5%BC-%EA%B3%84%EC%82%B0%ED%95%98%EB%8A%94-%ED%83%9D%EC%8B%9C-%EA%B8%B0%ED%95%98%ED%95%99/

https://ko.wikipedia.org/wiki/%EB%A7%A8%ED%95%B4%ED%8A%BC_%EA%B1%B0%EB%A6%AC

https://www.saedsayad.com/k_nearest_neighbors.htm