13. KNN & K-Means Clustering

This time...

• K-Nearest Neighbors
• K-Means

Data driven approach

<머신러닝 학습>

• Rule based approach
  사람이 하나하나 조건문 제공

• Data driven approach
  데이터들에서 일관된 특징 추출
  

1. 수많은 데이터 + 라벨링 수집
2. classifier 트레이닝을 위한 머신러닝
3. 새 이미지로 classifier 테스트 진행

K-NN Algorithm

Nearest Neighbor (classifier)
입력된 test_img의 라벨을 가장 가까운 데이터 img의 라벨로 사용한다.

• example dataset : CIFAR10
  -> 이미지의 갯수 적다.
  -> 32x32 : 화질이 떨어진다.
  -> 정확도가 떨어진다.

• Distance Metric
  이미지들 간의 거리 계산

1. 유클리드 dist
   이미지 차 계산, 제곱, 루트
2. L1 dist

• algorithm 순서

1. 트레이닝 데이터 학습 : 학습시간 짧다
2. 가장 이미지 거리 짧은 것 찾기 : 테스트 시간 길다
3. 가장 가까운 이미지 찾아서 최종 라벨 예측

• k-nearest neighbors
  k값 키울수록 generalization 상승 -> 모델복잡도 떨어진다. (디시즌 바운더리가 단순화돠ㅣㄴ다.

Design choices for K-NN

hyperparameters : 사람이 무조건 입력해줘야하는 값

• setting Hyperparameters

2. train과 test로 나눔
   • 또다른 테스트 데이터에서 성능을 보여주지 못 함
3. train/validation/test
   • val부분을 바꿔가며 세팅, 가장 일반적
4. Cross Validation
   • 등분하여 1등분씩을 val로 이용하여 평균내기

Limitation of K-NN Algorithm

단점 1) knn 알고리즘은 실제 이미지에서는 활용하기 쉽지 않다.

이미지가 조금이라도 바뀌어도 distance가 너무 많이 바뀐다.

단점 2) Curse of dimensionality

차원이 커지면 급격하게 포인트가 들어난다.

K-Means Clustering

라벨이 없는 경우에 데이터를 묶어주는 것 -> Unsupervised

• input
  - K개의 클러스터 (하이퍼 파라미터 값)
  - K개의 intial 센터
• Algorithm
  - 각 샘플을 가장 가까운 클러스터의 평균값에 인덱스를 할당
  • 클러스터의 중심값 다시 설정
  • 어느정도까지 반복 (바뀌지 않을때 까지)

Clustering이 사용되는 곳

• 생물 종 분류 시 사용
  (개의 종 나누기)
• 넷플릭스 등 에서의 추천 시스템
  (하나의 클러스터링에 여러 사람이 들어가지는 것
• 고객층 분석

K-Means 특징

• 유클리드 거리를 사용하면 명확히 클러스터가 나뉜다.
• 새로운 예시가 들어와도 추가적인 클러스터링 없이 그냥 중심 인덱스를 할당해준다.
• 데이터 많을때 샘플링 -> 줄인 데이터를 사용해도 차이 없음

K-Means 단점

• 클러스터의 갯수를 모를 경우에 사용 불가
• 예시는 하나의 클러스터에만 할당
• sub optimal solution
  -> 잘못된 중심점을 찾을수도 있다. -> 잘못된 결과가 나올수도 있다.
  -> 초기값이 매우 중요
  
• non-convex Clusters를 풀어주지 못함
  

K-Means++

• 확률기반으로 샘플링
• 기존의 k-means와 같은데, intialization만 다르다.