참고:
https://bcho.tistory.com/1205
https://needjarvis.tistory.com/720
https://syj9700.tistory.com/40
https://choco-life.tistory.com/45
https://www.kdnuggets.com/2020/04/dbscan-clustering-algorithm-machine-learning.html
중심 기반 클러스터링이 '동일 군집 데이터는 특정 중심을 기준으로 분포한다'는 가정하에 만들어졌다면, 밀도 기반 클러스터링은 '동일 군집 데이터는 서로 근접하게 분포한다'는 가정하에 만들어진다.
따라서 전자는 군집이 원형으로 만들어지며, 후자는 불특정한 형태를 갖게 된다.
DBSCAN(density-based spatial clustering of application with noise)는 밀도 기반 클러스터링이다. 2014년에 상을 받은 알고리즘이라고 한다.
두 개의 파라미터가 주어진다. 1. 데이터로부터의 반경 e 2. 군집이 되기 위한 최소 데이터 수.
이 알고리즘에 사용할 정의 몇 개는 아래 와 같다.
1. core point: 그 점의 반경 e내의 최소 데이터 수보다 많은 데이터가 있는 점.
2. border point: 한 점의 반경 e내에 최소 데이터 수보다 적은 데이터가 있지만, 적어도 하나의 코어 점에 속하는 점
3. noise point: 1,2가 아니면서 반경 내에 최소 데이터수 보다 적은 데이터수가 있는 점.
그렇다면, core점의 반경 안에 있는, 반경 내에 최소 데이터 수보다 많은 데이터를 가진 점 또한 core점이 된다
또한 관계에 대해 추가 정의를 한다.
1. Direct density reachable: 코어 점 q의 반경에 있는 점 p는 q에서 직접적으로 밀도 기반 도달가능한 관계에 있다.
2. Density reachable : 어떤 코어점 q와 p사이에 여러 점들이 있고, 각 징검다리 점들이 1의 관계에 해당하는 경우 p는 q에서 밀도 기반 도달가능한 점이 된다. 즉, 중간 점들 또한 core 점이 되어야 한다.
3. Density Connected: 어떤 점 O에서 2의 관계인 두 점 p,q는 밀도-연결되어 있다.
알고리즘은 아래와 같다.
1. 파라미터 설정
2. 코어점이 되는 임의 점 선택
3. 밀도 도달 가능한 점들을 뽑아, 새로운 코어점, 경계점으로 나눈다. 나머지는 노이즈
4. 반경내 코어점들을 모두 연결하고 하나의 군집으로 한다.
모든 경계점은 하나의 군집에 속해 있다. 나머지는 노이즈 점이다.
결과적으로 굉장히 자유로운 모양의 군집도 찾을 수 있게 된다.
장점:
1. 언급했듯, 원형이 아닌 기하학적 모양의 군집도 찾을 수 있다.
2. 군집의 수를 먼저 정해놓지 않는다.
3. noise point들을 이용해 outlier를 찾을 수 있다. k-mean은 반드시 모든 데이터를 포함해야 되므로, 평균값이 크게 왜곡되는 현상이 나타날 수 있다. 반면 DBSCAN은 이를 노이즈 처리해 버림으로써 군집에 포함시키지 않는다.
4. 데이터 포인트가 살짝 영향을 받아도, k-mean보다 군집 결과에 미치는 영향이 훨씬 작다.
