클러스터링 - DBSCAN 장단점, 동작원리, eps

이번 포스팅에서는 밀도기반 클러스터링인 DBSCAN에 대해 살펴보도록 하겠습니다. K-means와 더불어 많이 사용하는 클러스트링 알고리즘입니다. 
 

 

DBSCAN

DBSCAN은 Density-Based Spatial Clustering of Applications with Noise 줄임말입니다. 영문 이름에서 알 수 있듯이 밀도 기반 클러스터링이라는 것이 특징입니다. 밀도 기반의 클러스터링은 데이터의 점이 세밀하게 몰려 있는 밀도가 높은 부분을 클러스터링 하는 방식입니다. 

아이디어

• 군집에 포함된 데이터는 밀도가 높을 것이다.
• 군집에 포함되지 않은 데이터는 밀도가 낮을 것이다.(노이즈는 주변 밀도가 낮다)

개념 및 용어 정리

• E(epsilon, eps) : 군집 반지름
• N(MinPts) : 군집내 최소 포인트 개수
• Core point : 한 데이터 벡터로부터 거리 E내에 위치한 다른 데이터 벡터들의 수가 N보다 클 경우 클러스터링 하는데, 이때 중심 벡터
• Border point : 핵심 벡터로부터 거리 E내에 위채허서 같은 클러스터에 분류되나 핵심이 아닌 외각을 형성하는 벡터
• Noise point : 어떠한 클러스터도 속하지 않는 벡터

 

DBSCAN 개념 및 용어 설명

동작 원리

1. 방문하지 않은 임의의 포인트에서 시작한다. 거리 앱실론(반지름)을 통해서 이웃하는 점을 추출해 나간다. 
2. 충분한 숫자의 점들이 이웃으로 위치하고 있다면, 군집화 프로세스는 현재 데이터 포인트가 새로운 클러스터의 첫 지점이 되도록 한다. 
3. 새 군집의 첫번째 점에서 거리 앱실론 내 지점도 동일한 군집의 일부가 된다. 근방의 모든 지점의 포인트를 동일 군집으로 속하도록 하는 과정은 반복한다.
4. 과정을  군집내의 모든 포인트가 결정될 때까지 반복한다.
5. 위 과정을 다른 군집도 반복한다.

DBSCAN의 최적의 반지름, 최소 군집 개수 찾는 법

• 아이디어  
  
  • 하나의 군집 안에 있는 데이터 포인트의 거리는 가깝게 함 <->
  • 노이즈 포인트와의 거리는 꽤 멀게 떨어져 있게 함            <------->
• 어떤 군집 안에 있는 데이터 포인트들과 ‘K번째 인접한 이웃 데이터 포인트까지의 거리’를 순차적으로 계산함 
• 위에서 구한 거리가 급격하게 늘어날 때까지의 점을 찾음
  
  • 여기서 K는 최소 군집 개수
  • K번째 인접한 이웃 데이터 포인트까지의 거리는 반지름 
• 아 그림에서 최소 군집 개수는 4개고, 반지름은 파란 선의 기울기가 가파르게 증가하는 지점인 10이 됨

DBSCAN의 최소 군집 수

 

장점

• 자동 군집 수 결정 : DBSCAN에서는 군집 수를 사전에 지정할 필요 없음 - 밀도에 따라 군집이 자동으로 형성됨
• 밀도 기반으로 서로 연결하기 때문에 기하학적인 모양도 군집이 가능함
• 노이즈를 찾아낼 수 있고 제거할 수도 있음 - 클러스터링 결과를 깨끗하게 유지 하는데 도움이 됨

 

단점

• 데이터 사용하는 순서에 따라 클러스터링 차이
• 고차원 데이터 즉, 차원이 많을 경우 적절한 E(epsilon) 찾기가 어려움
• 모든 유클리디안 거리를 계산하는 알고리즘은 ‘차원의 저주’를 벗어나지 어려움  
• 밀도가 높은 곳에 집중하다 보니 왼쪽에 밀도가 낮은 곳의 데이터를 하나의 군집으로 인식하지 못하고 노이즈 포인트로 구분해서 모두 버려버리는 결과 발생

DBSCAN은 이상치나 이상한 모양의 클러스터에 대해 로버스트(robust)한 성능을 보입니다. 원형이 아닌 클러스터를 잘 식별하며 데이터의 밀도 변화에 강점이 있습니다.

결과적으로 데이터의 밀도와 클러스터 모양이 다양한 경우에 효과적이며, 데이터 클러스터링 및 노이즈 제거에 유용한 도구로 많이 사용됩니다.