밀도기반군집(density-based clustering)

 

군집분석(clustering)은 대표적인 비지도학습(unsupervised learning)으로 크게 중심 기반(center-based) 알고리즘과 밀도 기반(density-based) 알고리즘으로 나눌 수 있다. 중심 기반 알고리즘은 "동일 군집에 속하는 데이터는 어떠한 중심을 기준으로 분포할 것"이라는 가정을 기반으로 한다. 밀도 기반 알고리즘은 "동일 군집에 속하는 데이터는 서로 근접하게 분포할 것"이라는 가정을 기반으로 한다. 중심 기반의 가장 대표적인 알고리즘으로 k-평균(k-means)이 있으며, 밀도 기반 알고리즘에는 이 포스팅에서 소개할 DBSCAN이 있다. 

 

중심 기반 알고리즘과 밀도 기반 알고리즘의 특징에 대해 설명하면, 중심 기반 알고리즘의 경우 중심을 기준으로 군집을 형성하기 때문에 원의 형태를 가지게 된다. 반면, 밀도 기반 알고리즘의 경우 이웃 데이터를 기준으로 군집을 형성하기 때문에 불특정한 형태를 가지게 된다. 이 말은 즉, 데이터의 형태가 불특정한 분포의 형태를 띨 때, 밀도 기반 군집을 이용하면 적절하다! 또한, 지정된 밀도 안에 속하지 못해 군집에 포함되지 못한 데이터는 잡음(noise) or 이상치(outlier)로 판단할 수 있으며 이를 이용해 Anomaly detection에 활용할 수 있다.  중심-기반 알고리즘의 대표적인 방법으로는 k-평균 군집이 있다. 

 

이제부터 DBSCAN 알고리즘에 대해 알아보자.

---

○ DBSCAN(Density-based spatial clustering of application with noise)

알고리즘 작동방식을 공부하기 전에 미리 알아둬야할 용어를 익혀두자.

 

• 모수(Parameter)
  • $\epsilon$ : 데이터로부터의 반경(= $\epsilon$-neighbirhood of x)
  • minPts : 군집을 구성하는데 필요한 최소의 데이터 수

 

• 분류 점(Point)
  • core point : 한 점의 $\epsilon$-반경 내에 minPts 보다 많은 개체가 포함된 점.
  • border point : 한 점의 $\epsilon$-반경 내에 minPts 보다 적은 개체을 포함하고 있지만, 적어도 하나의 코어점의 반경에 속하는 점.
  • noise point : 코어점 또는 경계점이 아닌 점으로, $\epsilon$-반경 내에 minPts 보다 적은 수의 개체를 포함 하는 점. 

$\epsilon$ = c (임의의 값)이고, minPts = 6 인 경우

 

그림 (b) 를 보면, 점 x 는 $\epsilon$-반경으로 6개의 데이터를 포함하고 있으므로 코어점이 된다. 점 y 는 $\epsilon$-반경으로 5개의 데이터를 포함하고 있지만, 코어점 x 의 반경에 속해있으므로 경계점이 된다. 점 z 는 $\epsilon$-반경으로 2개의 데이터를 포함하고 있고, 코어점 x 의 반경에 속하지 못해 잡음점으로 분류된다. 

 

• Algorithm

DBSCAN에서 군집의 정의는 "밀도(기반)-연결된 점들의 집합" 으로, 점들과 다음의 관계들을 맺으면서 군집을 형성한다. 

 

• Direct density reachable : 점 p가 점 q의 반경에 들어오고, 점 q가 코어점일 때, "점 p가 점 q로부터 직접적으로 밀도(기반)-도달가능한 관계에 있다"고 한다. 반대의 경우는 성립하지 않음.

직접 밀도-도달가능

• Density reachable : 점 p와 점 q 사이에 $p_1, p2_, \cdots, p_n, p_1=q, p_n=p$ 들이 있고, 점 $p_{i+1}$이 점 $p_i$로 부터 직접적으로 밀도(기반)-도달가능하다면, "점 p는 점 q로부터 밀도(기반)-도달가능한 관계에 있다."고 한다. 

 

밀도-도달가능

 

• Density connected : 만약 두 점 p와 q가 모두 어떤 점 O로 부터 반경 내 MinPts 조건 하에 밀도(기반)-도달가능(density-reachable)하다면 "점 p는 점 q와 반경 내 MinPts 조건 하에 밀도(기반)-연결되었다."고 합니다.
  => (다르게 말하면, p가 O의 친구이고, q도 O의 친구이면, p와 q는 친구 O를 통해 서로 연결되었다고 보면 된다.)

밀도-연결

 

DBSCAN 알고리즘의 군집화 절차를 정리하면 다음과 같다. 

 

(1) $\epsilon$(반경)과 MinPts를 설정한다.

(2) 데이터로부터 코어점의 조건을 만족하는 임의의 점을 선택한다.

(3) 밀도-도달가능한 점들을 뽑아서 코어점과 경계점을 구분하고, 이에 속하지 않은 점들을 잡음으로 구분한다.

(4) $\epsilon$-반경 안에 있는 코어점들을 서로 연결한다.

(5) 연결된 코어점들을 하나의 군집으로 형성한다.

(6) 모든 경계점들은 어느 하나의 군집에 할당한다. (여러 군집에 걸쳐있는 경우, 반복 과정에서 먼저 할당된 군집으로 할당)

 

 

 

○ DBSCAN    vs    K-means

 

K-means 군집은 생성할 군집의 수를 지정해주어야 하지만, DBSCAN은 군집의 수를 지정해주지 않아도 된다. 또한, 서론에서 말했듯이 k-means는 평균 기반 알고리즘으로 군집이 원의 형태를 가지게 되지만, DBSCAN의 경우, 불특정한 형태의 군집을 형성할 수 있다. K-means 알고리즘은 평균을 취하기 때문에 이상치에 민감하며, DBSCAN은 잡음점을 식별하므로 이상치에 민감하지 않다(robust).

 

다음의 그림은 같은 자료에 대해 DBSCAN 군집과 K-means 군집을 적합시킨 것이다. 한 눈에 봐도 DBSCAN 군집을 이용한 방법이 데이터를 더 잘 설명하는 것으로 보인다. 

 

 

 

 

 

 

<참고문헌>

rfriend.tistory.com/587

[R] 공간데이터 밀도 기반 군집분석 DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

teamdable.github.io/techblog/Unsupervised-hdbscan

Clustering: HDBSCAN