밀도 기반 군집 방법 - DBSCAN

오늘은 1996년 처음으로 제안된 밀도 기반 군집 방법, DBSCAN에 대해서 알아보겠다.

---

•  ESTER, Martin, et al. A density-based algorithm for discovering clusters in large spatial databases with noise. In: kdd. 1996. p. 226-231.

---

1. Introduction

 

DBSCAN (Density-Based Spatial Clustering of Applications with Noise)는 이름에서도 나타나있는 large spatial data에 적용하기 위해 제안된 군집 방법이다.

Ester 등(1996)에 따르면 Large spatial data에 clustering algorithm을 적용하기 위해서는 충족되어야하는 몇가지 조건들이 필요하다.

(1) Minimal requirements of domain knowledge to determine the input parameters
(2) Discvery of clusters with arbitary shape
(3) Good efficiency on large databases
- Ester et al.,1996

일반적으로 널리 사용되는 중심 기반 군집 방법(ex, K-means)은 위 조건들을 동시에 충족시킬 수가 없었고, 이는 DBSCAN의 제안 배경이 되었다.

 

DBSCAN과 Partitioning/ Hierarchical clustering algorithm의 가장 큰 차이점은 군집의 개수 K를 pre-determine 할 필요가 없고, 밀도에 따라 군집을 형성하기 때문에 기하학적인 모양을 갖는 군집도 잘 찾을 수 있다는 것이다.

 

예를 들어 다음과 같은 자료를 clustering 한다고 생각해보자.

factoextra::data("multishapes"), In R

대표적인 중심 기반 군집 방법인 K-means 방법은 partitioning clustering 방법이기 때문에, 해당 자료에 적용하게 될 경우 다음과 같은 군집 결과를 보여준다.

Clustering result of K-means (K=5)

K-means 같은 경우는 데이터의 전체 공간을 각 군집의 중심점을 기준으로 partitioning 하여 군집을 형성하기 때문에, 데이터의 기하학적 형태를 정확하게 파악하지 못하는 것을 볼 수 있다.

 

하지만 DBSCAN을 사용하게 되면 더 합리적인 다음과 같은 군집 결과를 얻을 수 있다.

Clustering result of DBSCAN

---

2. Definitions and Lemma

 

본격적인 DBSCAN 알고리즘을 알아보기 전에, 알고리즘 전개를 위해 필요한 정의와 Lemma를 살펴보아야한다.

[Def 1] $\{ \epsilon - \text{neighborhood of a point}\}$ : The $\epsilon$-neighnohood of a point $p$, denoted by $N_\epsilon(p)$ is defined by 
$$N_\epsilon(p) = \{q\in D |dist(p,q) \leq \epsilon\}$$

[Def 2] {Directly density reachable} : A point $p$ is directly density-reachable from a point $q$, if
          (1) $p \in N_\epsilon(q)$
          (2) $|N_\epsilon(q)|\geq MinPts$ (core point condition)

여기서 $MinPts$는 하나의 클러스터가 포함해야하는 minimum number of points를 뜻한다.

 

[Def 1], [Def 2]를 정리하면,

"$p$와의 거리가 $\epsilon$이하인 모든 point $q$의 집합을 $N_\epsilon(p)$라고 한다."

"$p$가 $N_\epsilon(p)$안에 속한 point이며, $N_\epsilon(p)$안에 원소 개수가 $MinPts$보다 클 경우, $p$와 $q$는 directly density-reachable하다고 정의한다."

 

이해를 돕기 위해 그림을 첨부 한다. ($MinPts = 4$)

출처 : Kanii 그림 ^_^

[Def 3] {density-reachable} : A point $p$ is density-reachable from a point $q$, if there is a chain of points $p_1,\cdots,p_n,~p_1=q,p_n=p$ such that $p_{i+1}$ is directly density-reachable from $p_i$

즉, $i=1,\cdots, n$까지 $p_{i+1}$가 $p_i$에 대해 density directly reachable(def 2)할 때, $p=p_1$과 $q=p_n$은 density-reachable하다.

출처 : Kanii 그림 ^_^

[Def 4] {density-connected} : A point $p$ is density-connected to a point $q$, if there is a point $o$ such that both $p$ and $q$ are density-reachable from $o$

[Def 5] {Cluster} : Let $D$ be a database of points, A cluster $C$ w.r.t $\epsilon$, $MinPts$ is a non-empty subset of $D$ satisfying the folowing conditions:
          (1) $\forall~p,q$ : if $p\in C$ and $q$ is density-reachable from $q$, the $q\in C$
               (Maximality)
          (2) $\forall~p,q$ : $p$is density-connected to $q$  (Connectivity) 

[Def 6] {Noise} : Let $C_1,\cdots,C_k$ be the cluser of $D$, then we define the $noise$ as the set of points in $D$ not belonging to any cluster $C_i,~i=1,\cdots,k$

출처 : Wikipedia - DBSCAN https://en.wikipedia.org/wiki/DBSCAN

[Def 4] 그림 속 (B와 A) 그리고, (C와 A)는 각각 density-reachable하므로, (B와 C)는 density-connected 되어있다. 

 

[Def 5] 그림 속 모든 points, $D$에서 density-reachable, density-conneted되어있는 모든 점들은 하나의 cluster $C$에 속해있다. 즉, 그림 속 B와 C 사이에 있는 모든 점들은 하나의 cluster로 분류된다.

 

[Def 6] $D$에서 cluster에 속하지 않는 점 N은 $noise$로 분류된다.

 

위에서 DBSCAN에서 군집을 형성하기 위해 필요한 정의들을 먼저 살펴보았고, 최종적으로 DBSCAN이 군집을 찾아내는 방법은 아래 Lemma를 통해 확인 할 수 있다.

[Lemma.1] Let $p$ be a point in $D$ and $|N_\epsilon(p)| ≥ MinPts$ then the set $O = \{o|o ∈ D ~\text{and o is density − reachable from}~ p\}$ is a cluster

[Lemma.2] Let $C$ be a cluster with respecto to $\epsilon$ and $MinPts$ and let $p$ be any point in $C$ with $|N_\epsilon(p)| ≥ MinPts$ then $C$ equals to the set $O = \{o|o ∈ D ~\text{and o is density − reachable from}~ p\}$

 

[Lemma.1] : $p$가 core point condition ($|N_\epsilon(p)| ≥ MinPts$)을 만족할 때, $p$에 대해 density-reachable 한 모든 points $o$들은 $p$를 중심으로 하나의 군집을 형성한다.

 

[Lemma.2] : $C$가 하나의 cluster일 때, 해당 cluster에 포함된 core point condition을 만족하는 모든 점 $p$에 대해서 $O = \{o|o ∈ D ~\text{and o is density − reachable from}~ p\}$을 구하면 $O$는 정확히 $C$와 같다.

 

즉, 이 Lemma 2개는 cluster의 필요충분조건을 설명하고 있다고 이해하면 된다.

---

3. $\epsilon$ and $MinPts$

 

그렇다면, DBSCAN 구현을 위해 필요한 parameter $\epsilon과 $MinPts$는 어떻게 설정할까?

Ester et al. (1996)에서는 간단하지만 효율적인 설정을 위해서 $sorted~k-dist~graph$를 사용하기를 제안하였다.

 

Sorted k-dist graph는 $D$에 포함된 모든 점에 $p$에 대해서 distance를 계산한 뒤, $N_\epsilon(p)=k+1$가 되도록 하는 $\epsilon$을 내림차순으로 정렬하여 나타낸 그래프이다.

출처 : Kanii 그림 ^_^

이 때, 거리 $\epsilon$에 대한 threshold point는 k-dist graph에서 elbow point로 결정하게 된다.

 

또한, Ester et al. (1996)에 따르면 일반적으로 $k\geq 4$인 경우 대부분 $k=4$와 크게 다르지 않으며 계산 시간만 더 소요되기 때문에, 2-dimensional data에 대해서는 $MinPts = 4$로 설정하는 것을 권장하였다.

---

오늘은 DBSCAN에 대해서 살펴보았다.

DBSCAN 방법은 기존의 중심 기반 clustering 방법들과 는 달리 밀도를 기반으로 작동하기 때문에 데이터가 기하학적 형태를 띄고 있어도 군집을 잘 형성할 수 있고, 

모든 데이터 포인트를 군집에 할당하는 기존의 방식들과는 달리 어느 군집에 포함되지 않는 noise를 고려한다는 점이 large spatial data에 대해서 더 좋은 군집 결과를 얻을 수 있게 도와준다.

 

Python과 R에서 이미 DBSCAN을 위한 라이브러리가 잘 제공되어있으므로, 군집 분석이 필요한 순간에 유용하게 사용할 수 있을 것으로 기대된다.

---

library(rgl)
library(caret)
library(cluster)
library(dbscan)
library(rglwidget)
library(factoextra)

##############################################################################################
# Example #
##############################################################################################
data("multishapes")
str(multishapes)
summary(multishapes)

# Data shape
ggplot(multishapes,aes(x=x,y=y))+geom_point()


## (1) partitioning clustering using euclidean distance
clust_km=kmeans(multishapes[,-3],5)
fviz_cluster(clust_km,multishapes[,-3],ellipse=F,geom="point")

## (2) DBSCAN using euclidean distance

### Sorted k-dist plot
euc.mat=daisy(multishapes[,-3],metric = c("euclidean"))
summary(euc.mat)
euc.mat=as.matrix(euc.mat)
dist4.euc=c()

for ( i in 1:dim(multishapes)[1]){
  dist4.euc[i]=sort(euc.mat[i,],decreasing = F)[5]
}


dist4.euc=sort(dist4.euc,decreasing = T)

dist3.euc=c()
for ( i in 1:dim(multishapes)[1]){
  dist3.euc[i]=sort(euc.mat[i,],decreasing = F)[4]
}

dist3.euc=sort(dist3.euc,decreasing = T)

dist5.euc=c()
for ( i in 1:dim(multishapes)[1]){
  dist5.euc[i]=sort(euc.mat[i,],decreasing = F)[6]
}

dist5.euc=sort(dist5.euc,decreasing = T)

df=data.frame("Sorted_number"=rep(1:length(dist3.euc),3),
              "Distance"=c(dist3.euc,dist4.euc,dist5.euc),
              "K"=c(rep(3,length(dist3.euc)),rep(4,length(dist3.euc)),rep(5,length(dist3.euc))))
df$K=factor(df$K)

ggplot(df,aes(x=Sorted_number,y=Distance,color=K))+geom_line(size=1.5)+theme_bw()

#Set parameter
eps_e=dist4.euc[26];minPts_e=4
library(Rcpp)
db.euc=dbscan(multishapes[,-3],eps = eps_e,minPts = minPts_e)
fviz_cluster(db.euc,multishapes[,-3],stand=F,ellipse=F,geom="point")