DBSCAN

I. 밀도기반 군집화 기법, DBSCAN

가. DBSCAN 의 개념

• 핵심 벡터로부터 ε 반경 내 접근 가능한 모든 데이터 벡터들의 집합(군집)을 생성하는 기법
• DBSCAN : Density-Based Spatial Clustering of Application with Noise

나. DBSCAN 주요 개념

ε (epsilon)	– 주어진 개체 들의 반경
minPts	– ε 반경 내 군집 위해 필요한 객체 수

II. 군집 생성 요소 및 절차

가. 군집 생성 요소

구성 요소	설명
이웃 벡터	– 한 벡터로부터 ε 반경 내 위치한 다른 데이터 벡터
핵심 벡터 (Core Point)	– n개 이상의 이웃벡터를 갖는 데이터 벡터
직접 접근 가능	– directly density-reachable – 핵심 벡터 p와 p의 이웃벡터 q에 대해 q는 p에 대해 직접 접근 가능 (p→q)
접근 가능	– density-reachable {p=p1→p2, … , →q} – 벡터 p와 q에 대해 직접 접근 가능한 데이터 벡터 배열
연결된	– density-connected – 벡터 p와 q에 대해 접근 가능한 벡터 o가 존재(o→p, o→q), p와 q는 서로 연결(p↔q)
군집 (Cluster)	– 한 핵심벡터 p에 대해 접근 가능한 모든 데이터 벡터들의 집합, 군집 내 벡터는 연결
노이즈 (Noise)	– 어떠한 군집에도 속하지 않는 데이터

나. 군집 생성 절차

절차	개념도	설명
기본 상태		– ε (epsilon) : 주어진 객체들의 반경 – minPts : 군집 최소수 – ε 반경 내 minPts개가 존재해야 군집 판단
군집 생성		– 임의 점 p1, p2 등에서 ε 반경 내 minPts 만족 시 군집
Noise 분류		– 임의 점 p1 에서 ε 반경 내 p2 미 존재 시 Noise로 분류
군집 완성		– 각 점에서 ε 반경 내 minPts 충족하는 객체집합(군집) 완성

III. DBSCAN의 장/단점

장점	단점
– 군집개수 정의 필요 없음 – 임의 모양의 군집 생성 – 잡음(Noise) 개념 존재 – 2개의 매개변수만 필요	– 유클리디안 거리 이용하여 ε 산출이 어려움 – 다차원 및 고밀도 데이터의 군집화 어려움