[240408] 클러스터링 분석 - ⑤ DBSCAN

[파이썬으로 하는 클러스터링 분석 by 강민구 튜터]

 

1. DBSCAN

1) 정의 

- Density-Based Spatial Clustering Of Applications With Noise의 약자
- Noise를 포함한 데이터에 대해 밀도 기반으로 클러스터링 하는 알고리즘
- 데이터가 밀집되어 있는 집합을 클러스터로 간주하고 이를 군집화

출처 - https://github.com/pilsung-kang/Business-Analytics-ITS504-

출처 - https://medium.com/analytics-vidhya/cluster-analysis-with-dbscan-density-based-spatial-clustering-of-applications-with-noise-6ade1ec23555

 

2) DBSCAN의 장점과 한계 

(1) 장점 
 ① 기하학적으로 패턴이 있는 데이터 군집화에 유리

출처 - https://www.kdnuggets.com/2020/04/dbscan-clustering-algorithm-machine-learning.html

 ② K-means 같은 알고리즘과 달리 군집 갯수를 정할 필요가 없음 (단, 다른 하이퍼 파라미터가 존재)

(2) 한계
 ① 다양한 밀도를 가지고 있는 데이터 형태는 군집화 성능이 떨어짐 
 ② 하이퍼 파라미터 값에 따라 클러스터링 결과가 크게 달라지며, 적정 하라미터 값 지정이 어려움 

   └ 도메인 지식 활용, 다른 알고리즘 적용 등 여러 시행착오를 거쳐 적절한 하이퍼 파라미터 설정 필요 

3) DBSCAN 이해를 위한 용어 정리

- DBSCAN은 밀도 기반 클러스터팅으로, 밀도는 단위 부피당 질량을 나타냄 

출처 -  https://www.geeksforgeeks.org/dbscan-clustering-in-ml-density-based-clustering/

 

① 사용자가 지정해야 할 하이퍼 파라미터
  - Eps(Epsilon): 특정 데이터 포인트를 중심으로 몇 개의 데이터 포인트가 있는지 찾기 위한 반경 (반지름)

  - MinPts(Minimun Points): Eps 내 존재하는 데이터 포인트가 같은 클러스터로 묶이기 위한 최소한의 점 갯수 
② 데이터 포인트 구분 
  - Core Point: 특정 포인트 기준 Eps 범위 내 존재하는 데이터 포인트 갯수가 MinPts 이상인 경우 Core Point로 지정
  - Border Point: 특정 포인트 기준 Eps 범위 내 존재하는 데이터 포인트 갯수가 MinPts 미만 & Core Point 포함한 경우 

  - Noise Point: 특정 포인트 기준 Eps 범위 내 존재하는 데이터 포인트 갯수가 MinPts 미만 & Core Point 미포함한 경우

 4) DBSCAN 동작 과정

출처 -  https://levelup.gitconnected.com/visualizing-clustering-algorithms-k-means-and-dbscan-c4ce62de23c1

 

① 임의의 데이터 포인트 선택
② 선택한 데이터 포인트와 Eps 거리 내에 있는 모든 포인트 탐색

  └ Eps 거리 내 데이터 포인트가 MinPts 이상: 초기 포인트를 Core Point로 지정

  └ Eps 거리 내 데이터 포인트가 MinPts 미만: 코어 포인트 포함 시 Border Point, 미포함 시 Noise Point 
③ 클러스터 내 다른 군집의 Core Point가 있다면, 그 점을 Core Point로 하는 클러스터도 동일한 군집으로 간주

④ 클러스터의 모든 점에 대해서 ②~③ 과정을 반복합니다.
⑤ 모든 포인트가 Core Point / Border Point / Noise Point 중 하나로 구분되면 종료 

 

2. 하이퍼 파라미터 설정 팁 

1) MinPts 설정하기
- 일반적 가이드라인
└ 데이터 셋 크기가 클수록 MinPts 값을 크게 잡는 것이 유리 (너무 작으면 노이즈가 많아짐)
└ 데이터에 Noise가 많은 경우에도 MinPts를 크게 잡는 것이 유리
└ 도메인 지식이 있다면 이를 활용해 설정
- Rule of thumb
└ 데이터 포인트 차원 D에 대해 MinPts ≥ D+1 로 지정
└ 보통 MinPts = 2 * D (차원의 2배수)로 둔다고 하는데, 항상 옳은 값은 아님 

2) Eps 설정하기
- K-NN 알고리즘을 활용한 Epsilon 값 설정
└ K-NN: 특정 포인트 주변 k개의 데이터 포인트를 이용해 예측 또는 분류하는 알고리즘
└ K개 이웃 점과의 평균 거리를 순서대로 정렬해 갑자기 값이 확 커지는 지점(Elbow Point)의 거리를 Eps로 설정
└ K는 보통 MinPts(또는 MinPts - 1)값을 사용

 

출처 -  https://rfriend.tistory.com/588

 

(부록) 참고자료
- [고려대학교 강필성 교수님 강의 - DBSCAN]
- [DBSCAN Clustering Algorithm in Machine Learning]