데이터 과학 - 12. Clustering Part 2(DBScan)

* DB Scan

K-Means와 같은 Centroid-based Approach는 특정한 모양을 가지는 데이터에 대해 접근이 쉽지 않았다.

이러한 데이터에 대해 이전까지 내용에서 hierarchical clustering, 즉 Agglomerative clustering으로 접근을 했었다.

이제 Density-based Clustering을 알아보자.

 

* Density- based Clustering

어떤 경우는 cluster 들은 임의의 모양을 가질 수 있고, 이들이 noise처리가 되면 안된다.

우리는 그러한 cluster들을 찾기 위해 DB scan이라는 방법을 사용할 수 있다.

(noise-resistant density-based clustering)

이 방법은 다음 2가지 원칙을 적용한다.

1. noise 주변의 데이터들은 sparse 하다.

2. noise나 Outlier들은 고립되어있어야한다.

 

* Parameters and Core Points

ε는 distance threshold이다. 한 점에서 ε 거리 내에 있는 다른 점들을 그 점의 이웃으로 간주한다.

MinPts는 상수 정수로 한 점이 '코어 포인트'가 되기 위해 필요한 이웃 점들의 최소 수를 정의한다.

B(p, ε)는 중심이 점 p이고 반지름이 ε인 구를 의미한다. 이는 p 주변의 "vicinty area"로 정의된다.

P는 Clustering할 점들의 집합이다. 

코어 포인트는 집합 P에 속하는 점 p로써, B(p, ε)가 MinPts 이상의 점을 포함할 때, p를 코어 포인트라고 한다.

쉽게 말하면 각 점에서 ε만큼의 반지름을 가지는 원을 그려 원에 점이 몇개 들어가냐를 따져 기준 k보다 크면 그 점을 코어 포인트로 따지는 것이다.

이렇게 정한 core point들을 가지고 다른 non-core point를 할당하며 알고리즘이 진행된다.

 

Step 1.

core point들을 찾는다.

그 뒤, B(p, ε)안의 모든 점들을 core point와 연결한다.

완료된 모습 Cluster 2개가 형성되었다.

Step 2.

non-core point는 코어 포인트가 아니지만, 하나 이상의 B(p, ε)에 속해있는 포인트이다. 

이런 non-core point는 자신이 속한 모든 B에 추가된다.(중복 가능)

각 non-core point들은 MinPts-1 개만큼의 B에 속할 수 있다.(MinPts개 만큼 속하면 core point이다.)

예시로 든 사진을 보면 o10은 o11, o1의 B에 추가된다. 그리고 o18은 자신의 주변에 core-point가 없으므로 noise 처리가 된다.

최종 클러스터는 {o1,o2,o3,...,o10}, {o10,o11,o12,...,o17} 이다.

 

생각해볼점

1. DBscan에서 Cluster들을 구하는 것은 O(dn^2) 시간 안에 가능하다. 여기서 d는 데이터의 차원이다. 즉, 각 차원에서 각 점마다 다른 점들과의 거리를 계산해야하기 때문이다.

 

2. DBscan은 이웃하는 점들을 연결하여 클러스터를 형성하는 방식이기 때문에 single linkage 방법과 비슷하다.

 

3. 덴드로그램은 계층적 클러스터링에서 Cluster간의 유사성을 기반으로 cluster들의 계층 구조를 나타내는 트리 형태의 다이어그램이다. 이는 DBscan을 ε>=0, minPts=1 로 설정하고 실행하면 사실상 single linkage를 적용하는 것과 마찬가지여서 덴드로그램에서 수평선을 cluster를 형성하는 방법과 유사하다.