DBSCAN
Density-Based Spatial Clustering of Applications with Noise
고차원 공간에서의 군집화 알고리즘
밀도 기반의 군집화 알고리즘 : 데이터 분포에 따라 그룹을 나누는 알고리즘
일정 거리(epsilon) 이내에 데이터가 최소 몇 개(min_points) 이상이면 그룹으로 간주
구현 방법에 따라 다양한 버전 존재
Core/Border/Noise 분류
중심점(Core Point), 경계점(Border Point), 노이즈(Noise) 개념 존재
Step 1. 임의의 포인트를 하나 선정
Step 2. 선택한 포인트로부터 반경 epsilon만큼의 원 생성
Step 3-A. 원 안에 다른 포인트의 개수를 확인
| point num | cls |
|---|---|
| 0 | Noise |
| 1~min_points-1 | Border Point |
| > min_points | Core Point |
Step 3-B. 모든 포인트에 대해 분류 반복
Core Points 그룹화
Step 1. Core Points 중에서 하나의 Point를 선택하여 하나의 그룹으로 설정
Step 2. 선택한 Point의 반경 안에 포함되는 Core Points를 같은 그룹으로 그룹화
Step 3. 선택한 Point에 가장 이웃한 Core Point를 선택 후 반경 안에 다른 Core Points가 포함되지 않을 때까지 반복
Border Points 그룹화
Step 1. Core Points 중에서 하나의 Point를 선택하여 가장 이웃한 그룹화된 Core Point의 그룹으로 설정
Step 2. 남은 Border Points가 없을 때까지 반복
장단점
장점
모든 데이터에 대해 그룹화를 진행하지 않으므로 노이즈 대처 가능
그룹의 수를 미리 지정하지 않음
단점
Sparse한 데이터에 대해 잘 동작하지 않음
선택한 Point에 대해 다른 Points와의 거리를 계산하기 때문에 계산 복잡도가 높음
개선 포인트
모든 노드를 순회하기보다 Noise Point를 사전에 제외 가능?
Border Points에 대해 Cluster Point를 찾기보다 더 편한 비교 방법?
