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

밀도기반 군집분석(DBSCAN) 이란?

• 데이터의 위치 정보를 사용하여 군집 생성
• 밀도기반의 의미? 점들이 밀집된 곳을 하나의 군집으로 보는 것
• 노이즈 (아무 군집에도 들어가지 않는 데이터, 필요없는 값)을 제외시킴

 

 

 

어떠한 Dataset에 적합한가?

 

다양한 형태의 데이터셋

 

 

1) 군집의 크기가 다른 원형 데이터 셋

2) 블록 형태가 아닌 (nonconvex) 데이터 셋

3) 모양도 각기 다르고 노이즈가 있는 데이터 셋

--> 데이터셋 1,2,3 모두에 적합함

 

즉, k-means에서 만들지 못한 군집을 만들 수 있다. 크기가 각각 다르거나, 작거나, 다양한 기하학적 형태의 군집도 잘  분류 할 수 있다.

 

 

 

주요 파라미터

• ε- 거리(eps): 하나의 개체를 중심으로 eps 거리 내 몇개의 점이 있는지 파악. 이 숫자가 정해진 밀도보다 크다면 하나의 군집을 이루게 됨. 만약 없으면 pass
• 최소 점의 수 (Minimum Points): 군집을 이루기 위한 최소한의 개체 수. 최소 몇개 점이 있어야 군집을 만들 수 있는가?

 

프로세스

1)  step1 : 한 점을 중심으로 ε- 거리 내 이웃 점들 중 이웃의 수가 최소 점 이상인지 확인, 있으면 이웃점들을 포함한 군집을 생성하고, 없다면 가장 가까운 이웃 점으로 이동.

 

2) step2 : 이동한 점을 기준으로 step1 실행.  ε- 거리 내 임계점보다 많은 이웃이 있고 중심이 기존 군집에 속해 있으면 기존 군집에 이웃 추가. 만약 중심이 군집에 속하지 않았으면 새로운 군집이 생성되고 다음 이웃점으로 이동. 

 

3) step3 : 모든 비중심이 되는 점들은 ε- 거리 내 군집에 할당. 할당되지 않은 점은 노이즈로 구분됨. 

 

 

프로세스 예시

### ε : 3cm / Min points : 4개 일때 ###

 

1) step1 : 1번 점을 중심으로 3cm 거리 안에 점이 4개인지 판단. --> 이웃 점이 3개 이므로 PASS! -->  중심이 가장 가까운 이웃점인 3번으로 이동.

 

2) step2 : 3번 점을 중심으로3cm 거리 안에 점이 4개 이상 인지 판단 --> 2개이므로 PASS! --> 4번 점으로 이동.

 

3) step3 : 4번 점을 중심으로 3cm 거리 안에 점이 4개 이상인지 판단 --> 5개 이므로 1군집이 생성!! (1, 2, 3, 4, 5, 7)

 

1군집 (1, 2, 3, 4, 5, 7)

 

4) step4 : 2번 점을 중심으로 3cm 거리 안에 점이 4개 이상인지 판단 --> 3개이므로 PASS

1군집 (1, 2, 3, 4, 5, 7)

 

5) step5 : 5번 점을 중심으로 3cm 거리 안에 점이 4개 이상인지 판단 --> 5개 --> 5번 중심이 속한 군집에 6, 8번 점이 포함됨  

 

1군집 (1, 2, 3, 4, 5, 7, 6, 8)

 

6) step6: 7번 점을 중심으로 3cm 거리 안에 점이 4개 이상인지 판단 --> 2개 이므로 PASS

 

1군집 (1, 2, 3, 4, 5, 7, 6, 8)

 

7) step7: 6번 점을 중심으로 3cm 거리 안에 최소 점이 4개인지 판단 --> 2개 이므로 PASS 

 

 

8) step8: 8번 점을 중심으로 3cm 안에 최소 점이 4개인지 판단 --> 2개 이므로 PASS

 

9) step9: 9번 점을 중심으로 3cm 거리 안에 최소 점이 4개 인지 판단 --> 0개 이므로 PASS --> 9번은 이상치! 

 

 

1군집 (1, 2, 3, 4, 5, 7, 6, 8), 이상치 9

 

 

 

밀도기반 군집분석의 장단점은? 

장점

• 다양한 기하학적 형태의 군집 유형을 구분해 낼 수 있음.
• 군집의 개수를 자동으로 찾아줌 
• 노이즈를 구분하여 버림으로 의미없는 군집 생성을 차단함 (이상치를 구분해내기 위해서 활용하기도 함)
• 계산량이 적어서 빠름

 

단점

• 데이터의 밀도가 다양한 데이터에 적합하지 않음. (어떤 군집은 밀도가 듬성듬성한데, 어떤 군집은 오밀조밀 할 때)
• ε- 거리를 추정하기 어려움 (Nbclust과 같은 패키지가 적용되지 않음)
• 위의 장점들이 단점이 될 수도 있음
  • 기하학적 군집 구분 -> 군집의 중심과 특성을 정하기가 어려움. 
  • 군집의 개수를 3개로 만들고 싶은데 딱 3개로 나오지 않을 수 있음. (거리와 최소개수를 변경해가면서 찾아야 함)
  • 노이즈를 구분 -> "군집에 포함되지 않은 개체는 어떻게 처리할 것 인가?"에 대한 문제

 

k-means와의 비교

: K-means는 seed를 이용해 랜덤하게 중심을 잡기 때문에 매번 생성되는 군집이 다를 수 있음.

 

 

 

 

코드 예시

### 밀도 기반 군집 분석 (dbscan package) with wine data set 



#setting environment 

if (require("fpc")== F) install.packages("fpc") #for clustering 

library(dplyr) 
library(fpc) 
library(compareGroups) 
library(NbClust) 
library(sparcl) 
library(HDclassif) 
library(factoextra) 
library(ggplot2) 

set.seed(1234) 

#loading data 
data(wine) 
str(wine) 



names(wine) <- names(wine) <- c("Class", "Alcohol", "MalicAcid", "Ash", "Alk_ash", "magnesium", 
                                "T_phenols", "Flavanoids", "Non_flav", "Proantho", "C_Intensity", 
                                "Hue", "OD280_315", "Proline") 

wine_scale <- scale(wine[,-1]) 

#군집생성 

dbclust <- dbscan(wine[,-1], scale = T, eps = 2.5, MinPts = 10, method = "hybrid") 
dbclust <- dbscan(wine[,-1], scale = T, eps = 2, MinPts = 5, method = "hybrid") 
dbclust  
# 거리와 최소 개수를 바꿔가면서 좋은 군집을 찾아야 함. 

table(dbclust$cluster) 
table(dbclust$cluster, wine$Class) 


#시각화 (전체데이터) with PCA 
princ <- prcomp(wine_scale, retx = T) 

project <- as.data.frame(predict(princ, newdata = wine_scale)[,1:2]) 
project$class <- wine$Class 
project$dbclust <- dbclust$cluster 

ggplot(project, aes(x = PC1, y = PC2, colour = factor(dbclust), shape = factor(class))) + geom_point(size = 3)

 

 

 

1번 군집, 2번 군집, 어떠한 군집에도 속하지 않은 개체

 

 

 

[참고]

실무에서 써먹는 머신러닝 with R