Clustering - DBSCAN

Density-based spatial clustering of applications with noise (DBSCAN) is a density-based clustering non-parametric algorithm: given a set of points in some space, it groups together points that are closely packed together (points with many nearby neighbors), marking as outliers points that lie alone in low-density regions

간단히 말해, 사용자가 정의한 밀도에 따라 인접한 데이터를 계속해서 묶어나가는 알고리즘이다

이미지 출처: https://lucy-the-marketer.kr/ko/growth/%ED%81%B4%EB%9F%AC%EC%8A%A4%ED%84%B0%EB%A7%81%EA%B3%BC-dbscan/

• 밀도라는 개념을 도입하여, 서로 가까이 있는 데이터들을 하나의 클러스터로 묶어준다
• Noise data를 outlier로 취급하여 분류한다 (대표적인 outlier detection)
  ex) 불량품 검출, 사기 거래 탐지, ...
  

Algorithm

이미지 출처: https://medium.com/@agarwalvibhor84/lets-cluster-data-points-using-dbscan-278c5459bee5

• Eps : 같은 묶음으로 판단하는 기준이 되는 거리값 (유클리디안 거리 기준)
• MinPts : 같은 묶음으로 판단하기 위해 Eps를 반지름으로 하는 원을 그렸을 때, 최소한으로 포함되어야 하는 데이터의 개수 (range query)

1. 밀도를 정의하기 위한 파라미터 MinPts와 Eps를 정의한다
2. 각 데이터를 기준으로 Eps 크기를 가지는 원을 그려 그에 해당하는 데이터를 찾는다 (range query)
   => 만약 range query의 결과로 MinPts 이상의 데이터가 포함된다면, 그 데이터를 Core point로 지정한다
3. Core point와 연결된 모든 Core point들은 하나의 클러스터로 묶는다
4. 어떤 포인트가 range query를 했을 때 MinPts를 만족하지 못하지만 range query의 결과에 Core point가 포함되어있는 경우엔 해당 포인트는 Border point가 된다. Border point까지는 하나의 클러스터로 묶인다
5. Core point, Border point를 모두 만족하지 못하는 데이터는 Noise point(Outlier)로 판단되며, 이 때 -1의 cluster label을 부여받는다

장단점

장점

• 다양한 형태의 데이터에 대해 클러스터를 잘 파악한다 (성능이 뛰어나다)
• 어떻게든 다른 클러스터에 모든 데이터를 포함시키는 다른 방법들과는 달리, outlier를 정의하고 있기 때문에 만들어진 클러스터의 품질이 우수하다

단점

• MinPts와 Eps가 하이퍼 파라미터이다
• 모든 포인트에 range query를 계산해야 해서 속도가 느린 편이다. O(N^2)
• 고차원 공간에서 성능이 떨어진다 (차원의 저주)