[DBSCAN] k-dist 함수 기반 엡실론 지정 방식에 대한 문제 및 한계

 

DBSCAN(Density-Based Spatial Clustering of Application with Noise)은 오랫동안 클러스터링 알고리즘 영역의 주요 요소였으며 데이터 세트에서 밀집된 영역을 식별하는 효과적인 방법을 제공했습니다. DBSCAN의 핵심에는 Epsilon(ε)과 최소 포인트(MinPts)라는 두 가지 중요한 매개변수가 있습니다.

1. 엡실론(eps): 인접한 점을 찾을 수 있는 데이터 포인트 주변의 반경
2. 최소 포인트(MinPts): 밀집 영역을 형성하는 데 필요한 최소 데이터 포인트 수

 

이번 글에서는 제가  DBSCAN의 파라미터 지정을 자동화하기 위한 방법을 고안하던 중, DBSCAN 논문에서 제안된 엡실론 지정 휴리스틱 방법의 한계점에 대해 발견하고 이에 대해 조사한 부분을 공유하고자 합니다.

  k-dist 함수 기반 Eps 결정 방식

원 논문에서는 k-dist 함수를 기반으로 한 휴리스틱을 제안합니다. 여기서 k-dist(p)는 점 p에서 가장 가까운 k번째 이웃까지의 거리를 의미하며, k-1에 MinPts를 설정할 것을 제안합니다. -1을 하는 이유는 클러스터링 시 엡실론 반경 내의 min points의 수는 기준이 되는 데이터를 포함한 것이기 때문입니다. (minPts=4인 경우 자기 자신을 포함하여 이웃 3개와의 거리를 계산하기 때문)

높은 k-dist값(threshold의 왼쪽)의 포인트들은 noise로 간주되며, threshold의 오른쪽 포인트들은 클러스터로 할당된다고 말합니다.

1. k-dist Function:
   주어진 k에 대해 각 데이터 요소에 대해 k번째로 가까운 이웃과의 거리를 나타내는 knn 거리를 계산합니다.
   
   
2. Sorted k-dist Graph:
   논문에서는 내림차순으로 k-dist값을 정렬하여 그래프를 생성합니다.
   
   
3. Threshold Point:
   정렬된 k-dist 그래프의 첫 번째 "계곡"에 있는 첫 번째 점을 식별합니다. 이 점은 "가장 얇은" 클러스터의 최대 k-dist 값을 나타냅니다.
   
   
4. Set Parameters:
   임계점의 k-dist 값을 ε(Eps)으로, 파라미터 k-1를 MinPts로 설정합니다.
   
   
5. Result:
   임계값 포인트보다 k-dist 값이 같거나 작은 모든 포인트가 핵심 포인트로 간주됩니다. 
   
   

 

ε의 좋은 값은 그래프에서 knee가 나타나는 곳이라고 합니다. ε가 너무 작게 선택되면 데이터의 많은 부분이 클러스터링되지 않는 반면, ε가 너무 높으면 클러스터가 병합되고 대부분의 객체가 동일한 클러스터에 있게 됩니다.

위의 그림에서 임계점을 knee로 설정하면 6개의 표시된 포인트가 core point가 됩니다.

 

  문제 1) 임계값 포인트를 넘는 거리의 데이터는 실제로 모두 noise인가?

논문에서는 사용자가 노이즈의 비율을 추정할 수 있다면, 해당 비율을 입력하고 시스템은 이를 기반으로 임계점에 대한 제안을 도출할 수 있다고합니다.

그러나 아래 그림에서 knn 거리가 급격하게 감소하는 부분의 knn 거리값을 eps로 지정하는 경우 그 왼쪽의 데이터들은 노이즈가 될 수도 있고, 아닐 수도 있게 됩니다. 논문에서 말하는 것과는 다르게 실제로는 knee 포인트의 왼쪽 부분이 모두 노이즈가 되지 않습니다! 정확히 말하면 border-point 혹은 noise-point가 됩니다.

예를 들어 knee point를 지정하고 해당 knee보다 거리가 큰 세 개의 데이터가 노이즈로 분류될 것을 기대할 수 있지만, 아래 그림처럼 a, b 포인트는 border-point였기 때문에 실제로 클러스터링 결과 노이즈는 1개만 생성됩니다.

 

 

 

  문제 2) knee 지점이 최적의 엡실론 값인가?

또 다른 문제는 아래와 같이 knee 포인트 지점으로 보이는 부분을 엡실론으로 설정하고 클러스터링 하면, knee 포인트가 있어도 데이터의 밀도가 연결되어 있기 때문에 예상과는 다르게 대부분의 데이터가 하나의 클러스터로 지정됩니다.

결과는 연결된 밀도로 인해 대부분의 데이터가 단일 클러스터를 형성하는 것으로 나타났습니다. 이는 Knee Point만으로는 모든 의미 있는 클러스터를 캡처하는 데 충분하지 않을 수 있음을 나타냅니다.

 

knee 포인트를 조금 더 아래쪽으로 가져가서 엡실론을 지정하면 아래와 같이 데이터의 귀와 얼굴이 분리된 결과를 확인하게 됩니다.

 

 

  문제 3) knee 지점은 명확히 발견 가능한가?

또한, 데이터가 가우스 분포에 의해 생성된 경우, k-dist 플롯에서 매우 명확한 knee를 기대하지 말라고 말합니다.
밀도가 잘 분포되어 있기 때문에 플롯이 매끄러운 경향이 있으며, 변화율이 급격히 감소하는 뚜렷한 지점이 없을 수 있습니다.

 

 

  결론

결론적으로, k-dist 함수와 Knee Point 분석을 기반으로 하는 DBSCAN의 엡실론 결정 방법은 실제 상황에서 문제점을 드러냅니다. 임계점 너머의 지점이 순전히 노이즈라는 가정은 border point와 noise point가 공존하면서 현실을 지나치게 단순화할 수 있습니다.

또한 knee 포인트만으로는 최적의 엡실론 값을 보장하지 못하여 클러스터 형성에 실수가 발생할 수 있습니다. 또한 데이터 분포 및 일부 시나리오에서 뚜렷한 knee Point가 없을 수 있고, knee point가 여러 개 발견될 수도 있기 때문에 결정이 어려운 상황이 발생합니다.

다음 글에서는 위의 한계점을 인지한 상황에서 실제 클러스터링 서비스에서 파라미터 결정 자동화를 위해 고안한 부분에 대해 공유드리도록 하겠습니다.

 

Reference.

• https://file.biolab.si/papers/1996-DBSCAN-KDD.pdf
• https://www.youtube.com/watch?v=PoJmJ8wu6YI
• https://rfriend.tistory.com/588