Nearest Neighbor Algorithm

A에 해당하는 모양은?

• 새로운 데이터를 입력받았을 때 가장 가까이 있는 것이 무엇인지를 찾아 데이터의 종류를 정해주는 알고리즘
• 매우 간단하고 직관적인 알고리즘

---

K-Nearest Neighbor Algorithm

A에서 가장 가까운 것은 파란 동그라미, but 조금 넓혀서 보면 뭔가 잘못 됐음

• 단순히 주변에 가장 가까이 있는 것을 보는 것이 아닌
  주변에 있는 몇 개의 특징을 같이 보고 다수결에 따라 골라내는 방식
  • k = preferably a small odd number
• 특정 입력 데이터 x에 대해, 주변 K개의 훈련 샘플까지의 거리를 기준으로
  가장 많은 클래스로 분류를 수행하는 알고리즘

---

K-Nearest Neighbor Regression

• KNN 알고리즘을 이용해 회귀 문제를 해결 가능
• K개의 가장 가까운 이웃 샘플을 찾고 이 샘플들의 타깃값의 평균을 사용하거나, 가중합한 후 평균을 구하여 예측
  • 분류와 회귀 모두 더 가까운 이웃일수록 더 먼 이웃보다 평균에 더 많이 기여하도록 이웃의 기여에 가중치를 주는 것이 유용할 수 있음
  • 예를 들어, 가장 흔한 가중치 스키마는 d가 이웃까지의 거리일 때 각각의 이웃에게 1/d의 가중치를 주는 것
• Train Dataset을 저장하는 것이 모델 생성의 전부이며 이 데이터를 사용하여 예측

가장 근접한 k=7 개의 이웃 중, 가장 많은 초록 클래스로 분류

---

거리 계산

• 거리(distance)를 왜 구해야 할까?

  거리는 일종의 유사도(Similarity) 개념이기 때문

  거리가 가까울수록 그 특성(feature)들이 비슷하다는 뜻

1. 유클리드 거리 (Euclidean Distance)
   • 가장 널리 쓰이는 거리 계산 방법
   • 2차원 일 경우
   \[d= \sqrt{(a_1-b_1)^2 + (a_2-b_2)^2}\]
   • n차원 일 경우
   \[d= \sqrt{(a_1-b_1)^2 + (a_2-b_2)^2 + ... + (a_n-b_n)^2}\]
2. 맨하탄 거리 (Manhattan Distance)
   • 유클리드 거리와 유사하긴 한데, 각 차원의 차를 제곱해서 사용하는 것이 아닌 절대값을 합산함
   • 맨하탄 거리는 항상 유클리드 거리보다 크거나 같다
   \[d= \vert a_1-b_1\vert + \vert a_2-b_2\vert\]
   • n차원 일 경우
   \[d= \vert a_1-b_1\vert + \vert a_2-b_2\vert + ... + \vert a_n-b_n\vert\]
3. 해밍 거리 (Hamming Distance)
   • 각 차원마다 차이를 찾는 것이 아니라 ‘정확히 같은지’ 여부만 고려함
   • 맞춤법 검사와 같은 알고리즘에서 많이 사용
     • 단어 “there”, 오타 “thete” 사이의 해밍 거리는 1

---

정규화

• 데이터의 각 특성마다 스케일(단위)이 다르다면 모든 특성들을 모두 고르게 반영하기 위해 정규화(Normalization)를 함
  • 최소값을 0, 최대값을 1로 고정한 뒷 모든 값들을 0과 1 사이의 값으로 변환하는 방법
  • 평균과 표준편차를 활용해서 평균으로부터 얼마나 떨어져 있는지 z-점수로 변환하는 방법

---

결정계수 \(R^2\)

\(R^2 = 1 - \frac{(타깃 - 예측)^2의 합}{(타깃 - 평균)^2의 합}\)

• 대표적인 회귀 문제의 성능 측정 도구
• 1에 가까울 수록 좋고, 0에 가까울 수록 성능이 나쁜 모델
  • 예측을 잘하면 분자가 0에 가까워 짐
• 종속변수의 분산 중에서 독립변수로 설명되는 비율
• 쉽게 말해, 이 통계 모델로 대상을 얼마나 잘 설명할 수 있는가를 숫자로 나타낸 것

---

과대적합과 과소적합

• 과대적합

  훈련세트에서 점수가 좋았는데 테스트 세트에서 점수가 나쁠 경우

  훈련세트에만 잘 맞는 모델이라 테스트세트와 실전 데이터에 대한 예측에 잘 동작 못함

• 과소적합

  테스트 세트의 점수가 높거나 훈련, 테스트세트 점수가 모두 너무 낮은 경우

  모델이 너무 단순하여 훈련 세트에 적절히 훈련되지 않은 경우

---

K 개수의 선택

• k가 너무 작을 때 => Overfitting (과대적합)
  • k가 너무 작으면 -> 시야가 좁음, 지역적 특성을 지나치게 반영 -> 아주 근처에 있는 특성에 민감하게 영향을 받음
• k가 너무 클 때 => Underfitting (과소적합)
  • k가 너무 크면 -> 너무 관대해짐

---

KNN의 장단점

• 장점
  • 학습 데이터의 노이즈에 크게 영향을 받지 않는다
  • 학습 데이터의 수가 충분하다면, 상당히 좋은 성능을 낸다
• 단점
  • 최적 이웃의 수(k)와 사용할 거리 척도를 데이터 각가의 특성에 맞게 임의로 설정해줘야 한다
  • 새로운 관측치와 각 학습 데이터 사이의 거리를 전부 측정해야 하므로, 계산 시간이 오래 걸린다
  • Purpledog

---

Quiz

KNN Regression에서는 새로운 샘플에 대한 예측을 어떻게 만드나요?

1. 이웃 샘플 클래스 중 다수인 클래스
2. 이웃 샘플의 타깃값의 평균
3. 이웃 샘플 중 가장 높은 타깃값
4. 이웃 삼플 중 가장 낮은 타깃값