Clustering

K-means

DBSCAN

• 밀도 기반 군집 알고리즘
  - 클러스터가 최초의 임이의 점 하나로부터 점점 퍼져나감.

• 변수와 용어
  - epsilon: 클러스터의 반경

  • minPts: 클러스터를 이루는 개체의 최솟값
  • core point: 반경 epsilon 내의 minPts개 이상의 점이 존재하는 중심점
  • border point: 군집의 중심이 되지는 못하지만, 군집에 속하는 점
  • noise point: 군집에 포함되지 못하는 점

• 동작 순서
  1. 임의의 점 P 설정, P를 포함한 epsilon안에 포함되어 있는 점들 수를 센다.

  2. 해당 원에 minPts 개 이상의 점이 포함되어 있으면, P가 중심점으로 간주되어 원 안에 있는 점들을 클러스터링한다.
  3. minPts개 미만이라면,pass
  4. 모든 포인트를 돌아가면서 1~3 번의 과정을 반복하는데, 만일 새로운 점 p가 코어에 들어가면 이 두 개의 클러스터는 병합된다.
  5. 클러스터링이 완료됐는데도 떠도는 점은 noise point가 되고, 클러스터링은 됐지만 core가 아닌 점은 borde point라 한다.

• 특징
  - epsilon과 minPts를 잘 정하면 클러스터의 수를 명시하지 않아도 알아서 클러스터링함.
  - K-means보다 유연함.

비교

• DBSCAN 알고리즘과 K-means 알고리즘
  - 데이터 수가 적을 때는 K-means 수행시간이 DBSCAN에 비해 더 길었으나, 군집화할 데이터 수가
  많아지면 DBSCAN의 소요 시간이 급격히 늘어남.
  • 클러스터 수를 지정하지 않아도 되지만 minPts나 epsilon을 정해줘야 함.