[머신러닝] DBSCAN

기상청 빅데이터 콘테스트를 참가하게 되며 결과 해석으로 DBSCAN을 사용했다.
그때 당시에는 DBSCAN 에 대해 잘 알지 못해 적어보려 한다.

 

DBSCAN

# default 값 적어둠
DBSCAN(eps=0.5, min_samples=5, 
metric='euclidean', metric_params=None, algorithm='auto',leaf_size=30, p=None, n_jobs=None)

- 서로 인접한 데이터들은 같은 클러스터 일 것이라는 아이디어에서 착안되었다.

- 클러스터를 밀도가 높은 영역으로 보고 밀도가 낮은 영역으로 구분한다.
        클러스터는 각각 서로 가까운 코어 샘플의 집합이며 코어 샘플에 가까운 비핵심 샘플의 집합이지만, 그 자체는 아니다.

- 특정 데이터를 중심으로 밀도가 높은 곳에 포함된 데이터에는 클러스터를 할당하고 밀도가 낮으면 데이터를 노이즈로 취급하는 알고리즘

- 일반적으로 DBSCAN(eps,  min_samples) 를 사전에 입력한다.

 

eps

두 표본 사이의 최대 거리 (반경) 데이터 세트와 거리함수에 적합하게 선택하는 것이 중요하다.

일반적으로 기본값으로 둘 수 없다.

너무 작게 선택하면 대부분의 클러스가 전혀 클러스터링이 되지 않지만,
너무 크게 선택하면 가까운 클러스터가 하나의 클러스터로 병합되고 결국 전체 데이터 세트가 단일 클러스터로 반환된다.

 

min_samples

핵심포인트가 되기 위해 입실론 주변 영역 내에 포함되어야할 데이터의 최소 개수를 의미 한다.
노이즈에 얼마나 관대한지를 제어한다. (노이즈가 큰 데이터 세트의 경우 이 매개 변수를 늘리는 것이 좋다)

min_samples가 더 높거나 더 낮은 eps 는 클러스터를 형성하는데 거 높은 밀도를 나타낸다.

 

K-Means Clustering 과의 차이점

DBSCAN	K-Means Clustering
어떠한 모양이든 될 수 있다.	볼록한 모양을 가지고 있다.
군집 개수를 미리 정해주지 않아도 된다.(밀도 기반) 자동으로 결정된다.	군집 개수를 미리 정해주어야 한다. (거리 기반)
서로 인접한 데이터들을 같은 클래스에 할당	클러스터 중심치와 가까운 데이터를 해당 클러스터로 할당

 

DBSCAN 특징

1. 모든 데이터에 클러스터를 할당하지 않는다.

 

2. 반경과 최소 샘플수를 조절하여 여러 형태의 클러스터 패턴을 잡아낼 수 있다.

 

3. 클러스터의 개수가 자동으로 결정된다.

Feature 개수가 많으면 군집화 성능이 떨어진다.

 

4. 최악의 경우 메모리 복잡성을 가질 수 있다.

DBSCAN은 메모리 복잡도가 O(n) 이지만, eps param 이 크고 min_samples 가 낮을 때 발생할 수 있다.

복잡성을 피하는 방법 =  to pre-compute sparse neighborhoods in chunks using NearestNeighbors.radius_neighbors_graph with mode='distance', then using metric='precomputed' here.

* 복잡도 = 알고리즘의 성능 및 효율성을 나타내는 척도로 시간복잡도와 공간복잡도가 있다.
복잡도를 나타내는 방법으로 빅 오(O), 오메가(Ω), 세타(Θ)가 있으며, 주로 빅 오와 세타 표기법이 많이 사용된다.
O(n) =  빅오 표기법을 사용한 것으로 빅오 표기법은 최악의 경우를 고려하기 때문에, 최악의 시간까지 고려할 수 있다.

 

 

 

도움받은 티스토리 : https://zephyrus1111.tistory.com/356

30. DBSCAN에 대해서 알아보자 with Python

DBSCAN

DBSCAN