K-Means

• clustering의 기초가 되는 알고리즘.
• 거리 기반 clustering
• 주어진 데이터를 K개의 cluster로 나누는 알고리즘.

1. 임의의 K개의 Centroid 선택.
2. 각 데이터를 가장 가까운 중심점에 속한 그룹으로 분류.
3. 그룹의 중심점을 새로 계산.
4. 2-3 단계를 새로운 중심점과 기존 중심점의 차이가 충분히 작아질 때까지 반복.

K-means Metric

장점

• 구현이 쉽다.
• 다양한 데이터에 활용 가능하다.

단점

• 그룹의 개수를 사전에 정의해야한다.
• 가중치 및 거리 정의가 필요하다.

DBSCAN

• 밀도 기반 clustering 알고리즘.
• cluster의 개수를 알아서 결정해줌.
• 일정 거리(epsilon) 내에 데이터가 min_points개 이상이면 하나의 그룹으로 간주.
• 구현 방법에 따라 다양한 버전이 존재한다.
• 모든 데이터는 Core Point, Border Point, Noise로 분류됨.

Core/Border/Noise 분류
1. 임의의 포인트를 하나 선택.
2. 선택한 포인트로부터 반경 epsilon의 원을 만들고 각 포인트들이 원 안에 속하는 지 확인.
3-A. 원 안에 속하는 포인트의 개수를 확인하고 분류. 
	0개이면 Noise
    1개 이상, min_points보다 적으면 Border Point
    min_points 이상이면 Core Point
3-B. 모든 포인트에 대해 분류를 반복한다.

Core Points Clustering
1. Core Points 중 하나를 선택해 하나의 그룹(n_clusters=0)으로 설정.
2. 선택한 Point의 반경 epsilon에 포함되는 Core Points를 같은 그룹으로 clustering.
3. 2단계에서 포함된 Core Points들에 대해 2단계 과정을 반복.
4. n_clusters를 1만큼 증가시키고, clustering되지 않은 Core Points 중 하나를 선택해 2-3단계를 반복.

Border Points Clustering
1. Border Points 중에서 하나를 선택해, 가장 이웃한 Core Point의 그룹으로 설정.
2. 남은 Border Points가 없을 때까지 반복.

장점

• Noise 대처가 가능하다.
• 그룹의 수를 미리 지정하지 않는다.

단점

• Sparse한 데이터에서 잘 동작하지 않는다.
• 선택한 point와 나머지 Points 사이의 거리를 계산하므로 계산복잡도가 높음.(최악의 경우 O(n^2))

RANSAC

• 주어진 데이터에 fit한 model을 추정하는 알고리즘.

1. 샘플 데이터를 선택하고 이를 이용해 모델을 추정.
2. 샘플 데이터를 제외하고, 추정한 모델과 일치(=거리함수의 값이 threshold보다 작음)하는 데이터의 개수를 계산한다. 
3. 일치하는 데이터의 개수가 N개 이상이면 최종 추정 모델로 사용.(직전 최종 값보다 높으면 최종 추정 모델 갱신.)
4. 1-3 과정을 max_trials 만큼 반복.

장점

• Outlier 제거에 효과적
• 구현이 쉽고 다양한 모델에 적용 가능.

단점

• 랜덤한 Sampling 결과에 따라 비효율적이거나 잘못된 결과를 얻을 수 있음.
• Prior Sampling을 하지 않고, 완전히 랜덤한 Sampling을 사용함.