[Advanced ML & DL Week 2] A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise

작성자: 15기 이병주

기존 clustering 알고리즘

기존엔 두가지 clustering 알고리즘이 존재.

 

- partitioning 알고리즘

1단계: 목적함수를 최소화하는 k를 지정해준다.

2단계: 각 개체들을 대표 객체와 가장 가까운 클러스터에 할당한다. 

 

-hierarchical 알고리즘

여러개의 군집 중에서 가장 유사도가 높은 혹은 거리가 가까운 군집 두 개를 선택하여 하나로 합치면서 군집 개수를 줄여 가는 방법

가장 처음에는 모든 군집이 하나의 데이터만을 가진다. 따라서 최초에는 데이터 개수만큼 군집이 존재하지만 군집을 합치면서 최종적으로 하나의 군집만 남게 된다.

밀도 기반 클러스터링

 

클러스터를 인식할 수 있는 이유는 클러스터의 점들이 밀도가 높기 때문이다.

그리고 바깥부분은 밀도가 매우 낮은 노이즈로 판단할 수 있다. 

 

DBSCAN 은 복잡한 형태의 클러스터를 찾을 수 있고 노이즈를 찾아 제거할 수 있다!

 

Definition 1. 입실론- neighbor hood of a point 

NEps(P) =  {q ∈D I dist(p,q) ≤ Eps}

p점에 대해서, q점 까지의 거리가 입실론 이하인 점 q들을 점 p의 입실론- neighbor hood라고 한다.

 

일반적으로 core point 의 neighborhood가 border point의 neighborhood 보다 많다.

Definition 2. directly density-reachable

q 점으로 부터 입실론만큼 거리 안에 p 가 있고 그 원안에 최소값 이상의 점들이 있으면 p는 q로부터 directly density reachable

두 점이 core point 와 border point라면 symmetric 하지 않다.

 

Definition 3. density-reachable

 

p1이 q 로부터 ddr —> p2가 p1 로부터 ddr ……..      p(n)이 p(n+1)로 부터 ddr 이면

p는 q로부터 density-reachable

이런식으로 directly density-reachable 한 것들을 순차적으로 지나서 도달 가능하면 density-reachable이다. 

Definition 4. density-connected

p와 q 가 어떤 하나의 점 v로부터 density reachable할 때를 말한다. 

양쪽의 border 포인트 연결하기 위해 필요한 개념

Definition 5. cluster

cluster C는 다음과 같이 정의

1. 모든 p,q에 대해 p가 C에 포함되고 q가 p에 density_reachable하면 q도 C에 포함

2. 모든 p,q에 대해 p가 q에 density-connected

 

Definition 6. Noise

어떤 cluster C에도 속하지 않는 point 들의 집합을 noise 라고 한다. 

어떤 cluster에도 속하지 않는 noise들

작동 모습

스마일 모양으로 클러스터링

다른 알고리즘들과의 비교

runtime 비교