머신러닝 - 군집 - DBSCAN

[개념] 주어진 밀도를 이용하여 데이터를 코어, 경계, 노이즈로 구분하여 클러스터링하는 군집 모델링 기법

            데이터 셋에서 고밀도와 저밀도 공간을 구별함으로 써 군집을 생성

             k-평균 군집화 방법과 같이 거리가 계산되므로, 수치 형 데이터를 사용하는 것이 바람직

 

[특징] 데이터 내의 노이즈와 아웃라이어에 강한 모델링. K-Means와 다르게, 오목하거나 동심원 형태 군집에 우수.

 

 

[구성] 

1)neighbors: 한 데이터 벡터로부터 거리 e내에 위치한 다른 데이터 벡터

2)핵심벡터(core point) : n개 이상 neighbors 갖는 데이터 벡터

3)군집: core point p에 대해 접근 가능한 모든 데이터 벡터들의 집합(벡터간 연결성 보장)

4)노이즈: 어떤 군집에도 속하지 않는 데이터들

 

 

[초기설정] 주변 공간 정의, 군집 set 개수

[분류]

1)핵심벡터: 한 데이터 벡터로부터 거리 ee 내에 위치한 다른 데이터 벡터들의 수가 n보다 큰 경우 하나의 군집으로 생성하며, 해당 군집의 중심 벡터

2)외곽벡터: 핵심벡터로부터 거리 e 내에 위치해서 같은 군집으로 분류되나, 군집의 외각을 형성하는 벡터

3)노이즈 벡터:거리 e 내에 n개 미만의 벡터, 벡터 모두 핵심벡터가 아닌 경우, 핵심 벡터도 아니고, 외곽벡터도 아닌 벡터

 

[관계]

1)직접 접근 밀도 관계: core point p, neighbors q(p->q) (조건;q가 core point인 경우)

2)접근가능 밀도 관계: p, q 내 직접접근가능 데이터 배열 {p=p1->p2,...->q) 라면 q는 p로부터 접근가능(p=>q)

3)연결관계:p,q에 접근 가능한 벡터 o가 존재시(o=>p, o=>q), (p=>q)

 

[절차]

(가) Epsilon과 MinPoints의 정의

       데이터 포인트 주변이 고밀도 또는 저밀도 인지를 결정하기 위해서, 데이터 포인트에 대하여 임계 값(MinPoint)을 설정

 

(나) 데이터 포인트의 분류

        데이터 셋에서 주어진 경과 임계값에 따라 모든 데이터 포인트들을 세 가지로 분류한다.

         1) 핵심 포인트(Core Point)

         2) 경계 포인트(Border Point)

         3) 잡음 포인트(Noise Point)

 

1) 임의의 반지름과 최소 이웃점(MinPts) 결정

2) 주어진 점을 차례로 대입하여, 반지름 내의 이웃점 계산

 N(x) >= MinPts 이면, 해당 x 는 코어(Core)

 N(x) < MinPts 이고, 반지른 내에 있으면, 해당 x 는 경계(Border)

 N(x) < MinPts 이면, 반지름 내에 있지 않으면, 해당 x 는 노이즈(Noise)

3) 주어진 데이터 내의 모든 점 조사 후, 클러스터링 라벨링

 코어 > 코어 > 곙계 순으로 조사. 경계 > 코어로는 진행 불가

 

[알고리즘]

– 만약 점 p 주변 거리 e 안에 Minpts 개 이상의 점이 있다면 p를 core point로 지정 하고 e 내에 있는 점들과 함께 Cluster형성, 이때 e 내에 있는 점들을 neighbors 라고 정의

– neighbors 중 core point 가 될 수 있는 점이 있다면 그 점의 neighbors 또한 cluster 에 포함

– 위와 같은 방법으로 모든 점에 대해서 탐색

 

[장점]

– 특수한 형태의 cluster를 추출할 수 있음

– 데이터 상의 noise를 허용

 

[단점]

– Parameter e 를 어떻게 설정 하느냐에 따라 도출되는 cluster들이 달라짐

– Mixture 형태의 데이터에 대한 cluster 능력이 떨어짐

 

[비교] 임의의 초기 매개변수 관점 K-Means 와 비교

-K-means는 유클리디안 거리 사용, DBSCAN은 임의의 반지름, 밀도, 코어/경계/노이즈 활용

-K-means는 모여있는 데이터 클러스터링 강점. DBSCAN은 오목하거나 동심원 형태의 비선형 데이터 클러스터링 강점

 

[개선] OPTICS(Ordering Points To Identify the Clustering Structure)

– e 를 직접 정하기보다 각 점 마다 가장 가까운 core point까지의 거리를 미리 계산

– 특정 e 값이 설정되었을 때 도출되는 Cluster를 자동으로 만들어 낼 수 있도록 데이터를 정리(Ordering)

– Dense한 Cluster에 속할 수록 낮은 거리(reachability distance)를 가지게 됨