머신러닝 개념 정리) K-최근접 이웃, 유클리드 거리, 맨해튼 거리, 체비쇼프 거리, 민코스프키 거리

K-최근접 이웃이란?

K-Nearest Neighbors, KNN은 데이터의 형식을 제한하지 않고, 데이터의 분포 자체로부터 학습하는 비모수모델이다.

비모수란?

• 非(비) → 아닐 비 → “~이 아니다”, “부정”
• 母(모) → 어미 모 / 근본 모 → 여기서 모(母)는 ‘기준, 근본, 중요한 축’
  → 통계학에서는 모수(parameter)의 “모(母)”를 뜻함
• 數(수) → 셈 수, 숫자

‘모수(母數)를 사용하지 않는다’라는 뜻이다.
비모수 모델은 정해진 수(파라미터)를 전제로 하지 않으며,
모델의 형태(선형, 비선형 등)를 미리 가정하지 않고,
데이터의 분포(정규분포 등)를 특정 모양으로 정해두지 않는다.

 

따라서 데이터 자체로 예측하는 방식이 된다.

참고로 비모수라고 해서 들어온 데이터를 전처리 하지 않는다는 것은 아니다.
단순히 입력 데이터의 형태를 정해두지 않는다는 뜻이지
원핫 인코딩이나 라벨 인코딩 같은 전처리는 가능하다.

K-최근접 이웃은 머신러닝에서 분류 방식과 회귀 방식 둘 다에 적용이 가능하다.

k값에 따른 새로운 데이터 분류

분류 : 새로운 점(데이터)이 들어오면 가장 가까운 k개의 이웃을 찾아서, 제일 많이 포함되는 범주로 분류

즉, 가까운 k개 중 가장 많은 클래스를 선택하는 방식이다.

1. 새 데이터와 모든 학습 데이터의 거리를 계산
2. 그중에서 가까운 순서대로 k개를 선택
3. 제일 많이 선택된 클래스로 분류한다.

회귀 : 입력 데이터값 k개의 평균이나 가중평균을 이용하여 데이터의 범주를 예측하는 방식
즉, 가까운 k개의 y값을 이용해 숫자 예측하는 방식이다.

 

가중 평균이란 거리가 가까울수록 더 큰 점수를 주어 계산하여 평균 내는 방식이다.
그렇다 보니 회귀방식에서는 분류방식과 달리 입력데이터가 수치 데이터여야만 한다.

 

분류방식에서는 카테고리 형식이면 가능하다.
문자열 데이터, 수치 데이터 모두 상관없다.

보통 분류 방식으로 더 많이 활용된다.
k를 몇으로 둘 지가 중요하다.
k가 너무 작으면 이상치나 노이즈에 휘둘리고, 너무 크면 분류로써 의미가 없어져 세밀한 패턴을 놓친다.
이때 노이즈는 데이터 자체의 오류(측정, 입력 실수 등)나 패턴 인식측면의 노이즈가 있다.

패턴 인식 측면의 노이즈는 본래 같은 클래스에 속해야 할 데이터가 다른 클래스에 속했을 경우,
이를 토대로 다음에 들어온 새로운 데이터가 잘못 분류되어 악순환하는 것을 말한다.

가까운 k개를 선택할 때 가깝다의 기준, 즉 거리를 계산하는 방식은 4가지 정도가 있다.

1. 유클리드 거리

- 두 점 사이의 직선 거리를 계산

유클리드 거리의 수식

위 수식에서 k는 1부터 n개의 차원수까지 두 점 x와 y의 거리를 구한다.
즉 x1은 점 x의 첫번째 요소의 수치,
x2는 점 x의 두번쨰 요소의 수치이다.
만약 3차원이라면?
x3도 있을 것이다.

예를들어 3차원일 때, 점 x가 (1,2,3)이고 점 y가(4,5,6)이라면
이렇게 계산될 것이다.
( (1-4)^2 + (2-5)^2 + (3-6)^2 )을 루트 씌운 값이
거리일 것이다.

그럼 이 두 점을 정하는 기준은 무엇이냐?
바로 새로운 점과 새로운 점으로부터 k번째 가까운 점이다.

만약 2차원이라면 새로운 점이 (3,6)이고,
k가 3이어서 k번째의 점이 3번째 점이 되고,
그 점은 (6,12)라고 해보자.
그럼 유클리드 거리 공식에 의해 거리는 (3-6)의 제곱 + (6-12)의 제곱의 루트를 씌운 것으로 나온다.

2. 맨해튼 거리

- 두 점 사이의 좌표 차이를 절댓값으로 반환한 후 모두 더해 얻은 값이다.

맨해튼 거리의 수식

이상치의 덜 민감하며, 데이터 간의 절대적 차이의 총량을 분석할 때 유용하다.

참고로 새로운 데이터를 기준으로 k번째 가까운 점이 원 위에 존재하는
유클리드 거리와 달리
맨해튼 거리는 마름모 위에 위치하게 된다.

상세설명 : 
- 유클리드 거리 (Euclidean Distance)

• 공식:
  거리 = √(x² + y²)
• 등거리 곡선:
  동그란 원

설명:
두 점 사이의 직선거리를 의미한다.
피타고라스 정리에 기반하여, 각 축(x, y)의 차이를 제곱해서 더한 뒤
그 전체에 제곱근을 취해 구한다.

- 맨해튼 거리 (Manhattan Distance)

• 공식:
  거리 = |x| + |y|
• 등거리 곡선:
  마름모(다이아몬드) 형태

설명:
가로 이동 거리 + 세로 이동 거리의 합으로 계산한다.
격자형 도시(맨해튼)에서 이동하는 방식과 동일하다.
등거리(r=const)를 찍으면 원이 아니라 마름모 모양이 된다.

3. 체비쇼프 거리

두 점 간의 차이 중 가장 큰 축 방향의 차이인 최대 절댓값을 기준으로 측정한다.

체비쇼프 거리의 수식

등거리 모양은 가장 큰 축 방향의 차이인 최대 절대값을 기준으로
정사각형 모양이 된다.

4. 민코프스키 거리

위의 1,2,3번 거리를 p 값에 따라서 선택할 수 있는 거리이다.

p값에 따라 변한다.

 

p가 1일 때 맨해튼 거리,
2일 때 유클리드 거리,

무한대일 때 체비쇼프 거리가 된다.
실제로 p값을 대입해 보면 알 수 있다.

p값은 실수값이면 뭐든 가능하다.
p값에 따라서 등거리 모양은
p가 1일 때 마름모,
2일 때 원,
3일 때 원이 약간 네모처럼 찌그러진 모양,
10일 때 거의 정사각형,
무한대일 때 완전 직사각형이 된다.

참고로 p가 1.5라면 살짝 굴곡진 마름모 모양이 된다.

단, p가 1 이상일 때만 사용한다.

모델이 단순하고 직관적이라 데이터의 구조가 복잡해도 사용가능하지만, 
데이터가 커질수록 연상량이 기하급수적으로 증가해
처리속도가 느려지고 메모리 소모량이 많아진다.